System and method for learning models from scarce and skewed training data

• US 20080071721A1
• Filed: 08/18/2006
• Published: 03/20/2008
• Est. Priority Date: 08/18/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Yin, Jian, Wang, Haixun, Yu, Philip Shi-lung
• Granted Patent: US 7,630,950 B2
• Time in Patent Office: Days
• US Class Current: 706/48
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/20 Ensemble learning

Abstract

A system and method for learning models from scarce and/or skewed training data includes partitioning a data stream into a sequence of time windows. A most likely current class distribution to classify portions of the data stream is determined based on observing training data in a current time window and based on concept drift probability patterns using historical information.

Claims

1. A method for learning models from scarce and/or skewed training data, comprising:

building a classifier based on accumulated training data;

estimating a most likely current class distribution using historical training data; and

selecting historical classifiers based on the most likely class distribution to form a set of classifiers used to classify streaming data with evolving concepts.

2. The method as recited in claim 1, further comprising classifying unlabelled events in streaming data using the set of classifiers.

3. The method as recited in claim 1, wherein building a classifier based on accumulated training data includes representing the classifier by a decision tree wherein the decision tree includes leaf nodes.

4. The method as recited in claim 3, wherein the training data is partitioned into a sequence of time windows and each window includes a feature space which is divided into regions with each leaf node representing one region.

5. The method as recited in claim 1, wherein estimating includes developing a concept drift model to estimate the most likely class distribution.

6. The method as recited in claim 1, wherein estimating includes optimizing a probability function to determine the most likely current class distribution.

7. The method as recited in claim 1, further comprising determining classifier weights based on a number of cases of a class in a portion of the training data.

8. The method as recited in claim 1, further comprising adjusting weights of the classifiers.

9. The method as recited in claim 1, wherein building a classifier includes employing current and historical training data.

10. A computer program product for learning models from scarce and/or skewed training data comprising a computer useable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to perform steps of:

building a classifier based on accumulated training data;

estimating a most likely current class distribution using historical training data; and

selecting historical classifiers based on the most likely class distribution to form a set of classifiers used to classify streaming data with evolving concepts.

11. The computer program product as recited in claim 10, further comprising classifying unlabelled events in streaming data using the set of classifiers.

12. The computer program product as recited in claim 10, wherein building a classifier based on accumulated training data includes representing the classifier by a decision tree wherein the decision tree includes leaf nodes.

13. The computer program product as recited in claim 12, wherein the training data is partitioned into a sequence of time windows and each window includes a feature space which is divided into regions with each leaf node representing one region.

14. The computer program product as recited in claim 10, wherein estimating includes developing a concept drift model to estimate the most likely class distribution.

15. The computer program product as recited in claim 10, wherein estimating includes optimizing a probability function to determine the most likely current class distribution.

16. The computer program product as recited in claim 10, further comprising determining classifier weights based on a number of cases of a class in a portion of the training data.

17. The computer program product as recited in claim 10, further comprising adjusting weights of the classifiers.

19. The system as recited in claim 17, wherein the concept drift probability model is configured to predict concept drift probabilities for each region.

20. The system as recited in claim 17, wherein the weight is based on a number of cases of the class in a region and the weight has an exponential decay time.

18. A system for learning models and classifying evolving data, comprising:

a partition module configured to receive a data stream and partition the data stream into a sequence of time windows, each time window including a feature space partitioned into regions; and

at least one classifier having a weight based on a number of classes in each region, the at least one classifier being configured to determine a most likely current class distribution for each window by employing observations of training data in the data stream and employing historical patterns using a concept drift probability model to classify portions of the data stream.