Incremental clustering classifier and predictor

Abstract

The present invention provides mathematical model-based incremental clustering methods for classifying sets of data and predicting new data values, based upon the concepts of similarity and cohesion. In order to increase processing efficiency, these methods employ weighted attribute relevance in building unbiased classification trees and sum pairing to reduce the number of nodes visited when performing classification or prediction operations. In order to increase prediction accuracy, these methods employ weighted voting over each value of target attributes to calculate a prediction profile. The present invention allows an operator to determine the importance of attributes and reconstitute classification trees without those attributes deemed unimportant to further increase classification structure node processing efficiency. An operator can vary instance attribute values via a graphical user interface to explore the domain space of a classified data set, and use the visualization aspect of the present invention to visually contrast data set members with distinguishing features.

1. A computer implemented method of predicting, comprising the steps of:
 receiving a pre-existing classification structure; 
 receiving an instance to be predicted, comprising at least one attribute to be predicted; 
 determining a best host for the instance to be predicted; 
 optionally placing the instance to be predicted into a location relative to at least one child of the best host within the pre-existing classification structure; 
 determining a confidence level for an occurrence of an at least one possible value for the at least one attribute to be predicted; 
 querying each member of the pre-existing classification structure to perform a prediction process on the instance, wherein the prediction process is based at least in part on a relevance factor associated with the attribute; and 
 returning a prediction profile, comprising at least one possible value for the at least one attribute to predict and the corresponding confidence level for the at least one possible value for the at least one attribute to be predicted. 
 
     
     
       2. The computer implemented method of  claim 1 , wherein determining the best host for the instance to be classified comprises:
 processing class concept nodes of the classification structure, comprising the steps of: 
 receiving a class concept node of the classification structure; 
 calculating a delta cohesiveness measurement (ΔCM) value between the instance to be classified and the class concept node; and 
 storing the largest ΔCM value and the corresponding class concept node at each level of the classification tree; 
 determining the largest ΔCM value over all levels of the classification structure; and 
 storing the class concept node corresponding to the largest ΔCM value over all levels of the classification structure. 
 
     
     
       3. The computer implemented method of  claim 1 , further comprising the step of:
 displaying the classification structure; 
 determining at least one distinguishing feature of the instance to be predicted; and 
 visually contrasting the instance to be predicted within the classification structure, based upon the value of the at least one distinguishing feature. 
 
     
     
       4. The computer implemented method of  claim 3 , wherein the at least one distinguishing feature comprises at least one of an attribute value, a context value and a relationship value. 
     
     
       5. The computer implemented method of  claim 3 , wherein determining the confidence level comprises applying weighted voting over each value for the at least one target attribute of the at least one child of the best host. 
     
     
       6. The computer implemented method of  claim 3 , wherein determining the confidence level comprises, in the alternative, the step of:
 applying weighted voting over each value for the at least one target attribute of the at least one child of the best host, if the best host is a class concept node; or, 
 assigning the confidence level of the best host, if the best host is an instance node. 
 
     
     
       7. The computer implemented method of  claim 1 , wherein the method steps are carried out in real-time. 
     
     
       8. The computer implemented method of  claim 1 , wherein the classification structure comprises recorded patient data and the attribute comprises a result of a diagnostic test. 
     
     
       9. The computer implemented method of  claim 1 , wherein the classification structure comprises records of network traffic and the attribute comprises network activity of a possible intruder. 
     
     
       10. The computer implemented method of  claim 1 , wherein the classification structure comprises records of criminal activity and the attribute comprises a location of a crime. 
     
     
       11. The computer implemented method of  claim 1 , wherein the classification structure comprises records of purchasing habits and the attribute comprises data associated with a product. 
     
     
       12. The computer implemented method of  claim 1 , wherein the classification structure comprises records of testing data at a school and the attribute is associated with a teacher at the school. 
     
     
       13. A computer implemented method of predicting comprising the steps of:
 receiving a group of classification structures; 
 receiving an instance with an at least one attribute to predict; 
 querying each member of a subset of the group of classification structures to perform a prediction process on the instance, wherein the prediction process is based at least in part on a relevance factor associated with the attribute; and 
 returning a coalesced prediction profile. 
 
     
     
       14. The computer implemented method of  claim 13 , wherein the coalesced prediction profile comprises an Ameliorate prediction profile. 
     
     
       15. The computer implemented method of  claim 13 , wherein the coalesced prediction profile comprises a Winner-take-all prediction profile. 
     
     
       16. The computer implemented method of  claim 13 , wherein the methods steps are executed on at least one of a parallel processor and a multiprocessor.