System and method of mining time-changing data streams using a dynamic rule classifier having low granularity

Abstract

A dynamic rule classifier for mining a data stream includes at least one window for viewing data contained in the data stream and a set of rules for mining the data. Rules are added and the set of rules are updated by algorithms when an drift in a concept within the data occurs, causing unacceptable drops in classification accuracy. The dynamic rule classifier is also implemented as a method and a computer program product.

1 . A dynamic rule classifier for classifying data from a data stream comprising at least one drifting concept, the dynamic rule classifier comprising: 
 a window for viewing a plurality of records of the data stream;    a plurality of rules wherein each rule is derived from the plurality of records appearing in the window;    at least one data tree for maintaining the plurality of rules; and,    an engine for evaluating the plurality of records against the plurality of rules, detecting a concept drift in the data stream, invoking at least one algorithm for deriving at least one new rule and updating the plurality of rules.    
   
   
       2 . The dynamic rule classifier as in  claim 1 , wherein the engine comprises a user defined threshold for invoking the at least one algorithm.  
   
   
       3 . The dynamic rule classifier as in  claim 1 , wherein the engine provides a class label for each of the records in the plurality of records.  
   
   
       4 . A method using a dynamic rule classifier for mining data from a data stream having at least one drifting concept, the method comprising: 
 detecting the at least one drifting concept by performing quality estimation; and,    deriving new components for the dynamic rule classifier when quality is below a threshold.    
   
   
       5 . The method of  claim 4  wherein detecting the at least one drifting concept comprises: 
 maintaining a set of valid dynamic rules, and    estimating a quality of classification using the valid dynamic rules.    
   
   
       6 . The method of  claim 4 , where the at least one drifting concept is detected by analyzing a number of misclassified records.  
   
   
       7 . The method of  claim 4 , where a reference window is used for detecting the at least one drifting concept.  
   
   
       8 . The method of  claim 4 , wherein the quality estimation is performed by tracking misclassified records from the data stream for comparison to the threshold.  
   
   
       9 . The method of  claim 4 , further comprising: 
 providing a class label for each record of data in the data stream for assigning a concept to the record.    
   
   
       10 . The method of  claim 4 , wherein deriving new components for the dynamic rule classifier comprises: 
 finding records of data that are misclassified by valid dynamic rules;    deriving patterns from found records; and    composing patterns to form new dynamic rules for the dynamic rule classifier.    
   
   
       11 . The method of  claim 10 , where current misclassified records are derived from previous misclassified records.  
   
   
       12 . The method for  claim 10 , where predicates are derived from the misclassified records.  
   
   
       13 . The method for  claim 10 , where an algorithm is used to construct predicates to form new dynamic rules.  
   
   
       14 . A method for classifying data from a data stream on an ongoing basis, the data stream comprising at least one drifting concept, the method comprising: 
 viewing a plurality of records of the data stream appearing in a window;    deriving from the plurality of records appearing in the window a plurality of rules;    classifying data in the plurality of records according to the plurality of rules;    comparing a first classification of the data to a second classification of the data to detect a concept drift; and, upon detecting the concept drift;    deriving at least one new rule to account for the concept drift and updating the plurality of rules.    
   
   
       15 . A computer program product stored on machine readable media, the product for classifying data from a data stream on an ongoing basis, the data stream comprising at least one drifting concept, and comprising instructions for: 
 viewing a plurality of records of the data stream appearing in a window;    deriving from the plurality of records appearing in the window a plurality of rules;    classifying data in the plurality of records according to the plurality of rules;    comparing a first classification of the data to a second classification of the data to detect a concept drift; and, upon detecting the concept drift;    deriving at least one new rule to account for the concept drift and updating the plurality of rules.    
   
   
       16 . The computer program product of  claim 15 , wherein deriving a plurality of rules comprises: 
 sorting the plurality of records according to predicates thereof;    choosing a list of predicates to construct a candidate rule set;    computing a support statistic and a confidence statistic for the candidate rule set; and    adding each rule from the candidate rule set to the plurality of rules when a support value for the rule and a confidence value for the rule are greater than or equal to the support statistic and the confidence statistic, respectively.    
   
   
       17 . The computer program product of  claim 15 , wherein at least one tree structure is constructed for maintaining the plurality of rules.  
   
   
       18 . The computer program product of  claim 17 , wherein each node of the at least one tree structure represents a rule.  
   
   
       19 . The computer program product of  claim 15 , wherein deriving at least one new rule comprises: 
 determining at least one update rule for an entrance record that is moved into the window;    inputting the at least one update rule into the plurality of rules;    computing a support value and a confidence value for the entrance record; and    updating rules that are matched to an exit record moved from the window.    
   
   
       20 . The computer program product of  claim 19 , wherein deriving at least one new rule further comprises: 
 comparing the first classification of the data to the second classification of the data to detect concept drift, and, upon detecting the concept drift;    deriving a plurality of rules.