Patent Publication Number: US-10311084-B2

Title: Method and system for constructing a classifier

Description:
The present invention relates to the field of constructing a classifier. In particular, the present invention relates to constructing a classifier with reference to the context in which it is to be applied. 
     A classifier is a data mining system used to classify data records into specific categories. Classifiers are used in a wide range of applications, for example, from classifying customers in retail applications to classifying aircraft in defence applications. The traditional method used to construct a classifier is to use a training set of example records from which the decision boundaries are determined that separate the data records into different classes. The classifier is then applied to previously unseen records (for example, new customers) and the record is classified, usually with a statistical measure of the level of confidence that the record is in the class. 
     The challenge is to build a classifier from the training example records, that best generalizes the decision boundaries such that the classifier can be used in any context. This is often non-trivial since there are usually many classifiers that could be generated from the same training example records. Indeed, many data mining vendors claim that it is necessary to use a wide range of different classification techniques to ensure that the best possible classification results are obtained. 
     In many cases, if the actual class of the previously unseen records had been known a priori, a different and better classifier would have been constructed. This observation is true even in the case where the records to be classified are identical to example records within the training set. The reason for this apparent contradiction is simply that there are many contexts in which the training example records exist but when the classifier is applied it is usually in a specific context. 
     As a simple example, when it is a hot day customer behaviour may be different than when it is cold; however, the training example records do not record the temperature. A classifier built on all training example records would be different from one constructed only on records collected when it is a hot day. In general, it is not possible to discover the different contexts under which the sample example records are measured since in many cases the factors are unknown or are simply not easily measurable. 
     The problem of requiring context to construct an accurate classifier is understood in the prior art and known techniques used to address the problem are based on analysis of the training data, for example, by using gaussian mixture models. 
     The invention solves this problem by inverting the way in which the classifier is constructed using information contained in the records to be classified to determine the context, whilst still making full use of relevant training example records. In the context in which the classifier is to be used, there are a number of records to be classified. The records include examples from different possible classes. 
     According to a first aspect of the present invention there is provided a method of constructing a classifier for a set of records to be classified into predicted classes, comprising the steps of: a) clustering a set of records that are to be classified into a plurality of clusters, b) creating a first classifier that classifies records into the plurality of clusters; and c) applying the first classifier to a set of training records, each of the training records having a predicted class. 
     Step c) may classify the training records into the plurality of clusters. The method may include a further step of d) creating a classifier for each sub-set of training records classed into each of the plurality of clusters. The method may further include the step of, e) applying a classifier created for a sub-set of training records to a sub-set of records to be classified formed in step a) for the corresponding cluster. 
     The records to be classified may be labelled with a cluster identifier at step a). The records to be classified in a given sub-set may be labelled with the same cluster identifier. The training records may be labelled with a cluster identifier at step c). The training records in a given sub-set may be labelled with the same cluster identifier. 
     According to a second aspect of the present invention there is provided a system for constructing a classifier for a set of records to be classified into predicted classes, comprising: a clustering means to group a set of records that are to be classified into a plurality of clusters, a first classifier that classifies records into the plurality of clusters; and a set of training records, each of the training records having a predicted class; wherein the first classifier is applied to the set of training records. 
     The first classifier may classify the training records into the plurality of clusters. The system may include a classifier for each sub-set of training records classed into each of the plurality of clusters. The classifier for a sub-set of training records may be applied to a sub-set of records to be classified grouped in a cluster by the clustering means. 
     The clustering means may label the records to be classified with a cluster identifier. The first classifier may label the training records with a cluster identifier. 
     According to a third aspect of the present invention there is provided a computer program product stored on a computer readable storage medium, comprising computer readable program code means for performing the steps of: a) clustering a set of records that are to be classified into a plurality of clusters; b) creating a first classifier that classifies records into the plurality of clusters; and c) applying the first classifier to a set of training records, each of the training records having a predicted class. 
     The computer program product may include the step of: d) creating a classifier for each sub-set of training records classed into each of the plurality of clusters. The computer program product may further include the step of: e) applying a classifier created for a sub-set of training records to a sub-set of records to be classified formed in step a) for the corresponding cluster. 
     According to a fourth aspect of the present invention there is provided a method of providing a service to a customer over a network, comprising: a) clustering a set of records that are to be classified into a plurality of clusters; b) creating a first classifier that classifies records into the plurality of clusters; c) applying the first classifier to a set of training records, each of the training records having a predicted class. 
     The method of providing a service to a customer may include the step of: d) creating a classifier for each sub-set of training records classed into each of the plurality of clusters. The method of providing a service to a customer may further include the step of: e) applying a classifier created for a sub-set of training records to a sub-set of records to be classified formed in step a) for the corresponding cluster. 
    
    
     
       Embodiments of the present invention with now be described, by way of examples only, with reference to the accompanying drawings in which: 
         FIG. 1  is a block diagram of a computer system in accordance with the present invention: 
         FIG. 2  is a flow diagram of a method of constructing a classifier in accordance with the present invention. 
         FIG. 3  is a schematic diagram showing the record components in accordance with the present invention; and 
         FIG. 4  is an illustration of a worked example in accordance with the present invention. 
     
    
    
     An example embodiment of a data processing system is provided for practising the described data classification method. 
     Referring to  FIG. 1 , a computer system  100  is provided including a processor  102 . A classifier constructor  104  is provided that may be local to the processor  102  on which it runs or which may be provided remotely via a network such as the Internet. A classifier constructor  104  may be a computer software component, a hardware component or a combination of software and hardware. The classifier constructor  104  constructs one or more classifiers that can classify a data set of records  108  into a set of predicted classes. 
     A classifier is a learning system that learns one or more sets of relationships that define each of a known set of predicted classes. Examples of known classifiers include decision tree classifiers, Bayesian classifiers, and Support Vector Machines. Any known form of classifier may be used in the implementation of the present invention. 
     In the embodiment described herein, the classifier constructor  104  references the context in which the classifier is to be applied. The context in which the classifier is to be applied is referenced by using the data set of records to be classified as a reference when constructing the classifier. 
     The data set of records  108  to be classified may be any form of data set and may be provided local to the processor  102  on which the classifier constructor  104  is provided, for example, as a local database, or may be distributed remotely via a network, for example, as data records distributed across the Internet. 
     A set of training records  110  is provided that is available at the point at which the classifier is to be used. The set of training records  110  includes examples of known classes that are presented to the classifier that learns the relationships that define the known classes. When the classifier is applied to the data set of records  108  it classifies the data using the learned relationships. 
     In the described embodiment, the classifier constructor  104  includes a clustering means  112  and a classifier creator  114 . The clustering means  112  is applied to the data set of records  108  that are to be classified. This is not the set of training records  110 , but the actual data for classification. 
     The clustering means organises the records into separate groups or clusters such that the records within a group or cluster are similar to each other and dissimilar to the records in other groups or clusters. The clustering means seeks to maximise the similarity within a cluster and the dissimilarity between clusters to determine the actual number of clusters. Examples of known clustering methods include K-means, fuzzy C-means, hierarchical and mixture of Gaussians. 
     The classifier creator  114  creates a training classifier  106  based on the clusters generated by the clustering means  112 . The training classifier  106  thus created is then applied to the set of training records  110 . Further classifiers  107  are then created for classifying in the predicted classes, each of the clusters of records in the data set of records  108   
     The process of the classifier constructor  104  is now described with reference to  FIG. 2  that shows a flow diagram  200  of the method of constructing a classifier. 
     Apply a clustering algorithm  201  to the data set of records to be classified. The records are clustered to determine if they are sufficiently similar to be representative of the same class. Label each record  202  with a cluster identifier. 
     Create a training classifier  203  that can classify records into the clusters using the cluster identifier as the class. This training classifier wilt automatically select the best features to discriminate between the different classes under the conditions in which they are to be discriminated. 
     Apply the resulting training classifier  204  to a set of training records and label  205  each record with the predicted cluster identifier. 
     For all records in the training set with the same cluster identifier, create  206  a new classifier using the classification of the training records as the predicted class (i e. the required classes). This will result in N classifiers where N is the number of clusters from the first step of the method. 
     Apply the new classifiers  207  to the records from the data set of records with corresponding cluster identifier. The predicted class label is the required classification  208 . 
     In the limiting case, the resulting classification can be no worse than that built from the training examples alone and in most cases is significantly improved. 
       FIG. 3  illustrates the process showing the components of  FIG. 1 . The clustering means  112  is applied to the data set of records  108  and each record R 1   301 , R 2   302 , R 3   303 , R 4   304  is labeled with a cluster identifier  305 . In the simplified example illustrated in  FIG. 3 , there are three clusters that have cluster identifiers A, B, C. The data set of records  108  has subsets of records  311 ,  312 ,  313  in each of the clusters. In this example, record R 4   304  is in sub-set  311  for cluster A, records R 1   301  and R 3   303  are in sub-set  312  for cluster B, and record R 2   302  is in sub-set  313  for cluster C. 
     Training classifier  106  is created to classify records into the clusters A, B, C using the cluster identifier  305  as the class  321 ,  322 ,  323 . In this example, there are three classes  321 ,  322 ,  323  corresponding to the three clusters A, B, C. 
     The training classifier  106  is applied to the set of training records  110  and classifies the training records T 1   331 , T 2   332 , T 3   333 , T 4   334  into the classes  321 ,  322 ,  323  corresponding to the three clusters A, B, C and labels each record  331 ,  332 ,  333 ,  334  with the cluster identifier  305 . Each of the training records T 1   331 , T 2   332 , T 3   333 , T 4   334  has a classification  306  for a final predicted class P  351 , Q  352 . S  353 . 
     The set of training records  110  has sub-sets of records  341 ,  342 ,  343  classified in each of the clusters A, B, C. In this example, records T 1   331  and T 2   332  are in sub-set  341  for cluster A, record T 4   334  is in sub-set  342  for cluster B, and record T 3  is in sub-set  343  for cluster C. 
     For each sub-set  341 ,  342 ,  343  of the set of training records  110  with the same cluster identifier  305 , a new classifier  107 A,  1078 ,  107 C is created, Each of the new classifiers  107 A,  1076 ,  107 C classifies records into predicted classes P  351 , Q  352 , S  353  using the learned classification  306  of the training records  331 - 334 . 
     The new classifiers  107 A,  1076 ,  1070  are applied to the corresponding sub-set  311 ,  312 ,  313  of the data set of records  108  for the cluster A, B or C. In this way, each sub-set  311 ,  312 ,  313  of the data set of records  108  is classified into the predicted classes  351 ,  352 ,  353  using a classifier optimized for the context of the cluster. 
     A worked example is now provided with reference to  FIG. 4  that illustrates a set of training records with two features (X,Y).  FIG. 4  shows a graph  400  with the training records  401 ,  402  plotted with values of a first feature X along the x-axis  403  and the values of a second feature Y along the y-axis  404 . The training records  401 ,  402  belong to two classes A  401  and B  402 . 
     In a practical example, the two classes A and B could represent two categories of vehicle (for example, poor and good) and the two features X, Y could represent speed and fuel efficiency. 
     A decision tree classifier, such as that used in the DB2 Intelligent Miner product (DB2 and Intelligent Miner are trade marks of International Business Machines Corporation), will not be able to discriminate between the two classes A, B since neither feature X or feature Y provides an obvious boundary condition that can divide the two classes of object. 
     This is indicated by the confusion matrix shown in Table 1 below for the corresponding decision tree. 
     Class Data test 
     
         
         Number of classes=2 
         Errors=10 (50%) 
       
    
     
       
         
           
               
             
               
                 TABLE 1 
               
             
            
               
                   
               
               
                 Confusion matrix for pruned tree all values of X and Y 
               
            
           
           
               
               
               
               
               
            
               
                   
                 Predicted Class 
                 Class A 
                 Class B 
                   
               
               
                   
               
               
                   
                 Class A 
                 10 
                 0 
                 Total = 10 
               
               
                   
                 Class B 
                 10 
                 0 
                 Total = 10 
               
               
                   
                   
                 20 
                 0 
                 Total = 20 
               
               
                   
               
            
           
         
       
     
     If unseen records are generated for high values of Y then these will automatically cluster into two clusters with high (Cluster 1) and low (Cluster 2) values of X. Classifying these two clusters results in a training classifier with the simple boundary conditions;
 
Y&gt;0.7 Ymax &amp; X&gt;0.5Xmax then Cluster 1 (100%)
 
Y&gt;0.7 Ymax &amp; X&lt;0.5Xmax then Cluster 2 (100%)
 
     Applying this training classifier to the original set of training records shows that all examples in Cluster 1 are Class A and all in Cluster 2 are Class B. No further classifier is therefore required and the final classifier is
 
Y&gt;0.7 Ymax &amp; X&gt;0.5Xmax then Class A (100%)
 
Y&gt;0.7 Ymax &amp; X&lt;0.5Xmax then Class B (100%)
 
Class Data Test
     Number of classes=2   Errors=0 (0%)   

     
       
         
           
               
             
               
                 TABLE 2 
               
             
            
               
                   
               
               
                 Confusion matrix for pruned tree Y &gt; 0.7 Ymax 
               
            
           
           
               
               
               
               
               
            
               
                   
                 Predicted Class 
                 Class A 
                 Class B 
                   
               
               
                   
               
               
                   
                 Class A 
                 4 
                 0 
                 Total = 4 
               
               
                   
                 Class B 
                 0 
                 4 
                 Total = 4 
               
               
                   
                   
                 4 
                 4 
                 Total = 8 
               
               
                   
               
            
           
         
       
     
     The described classifier constructor may be provided as a data mining toolkit in the form of a computer program product. The classifier constructor may also be provided in an embedded system requiring a classifier. 
     The present invention is typically implemented as a computer program product, comprising a set of program instructions for controlling a computer or similar device. These instructions can be supplied preloaded into a system or recorded on a storage medium such as a CD-ROM, or made available for downloading over a network such as the Internet or a mobile telephone network. 
     The present invention may be provided as a service to a customer over a network. In particular, the service may construct a classifier for the customer. 
     Improvements and modifications can be made to the foregoing without departing from the scope of the present invention.