CLASSIFICATION USING A CASCADE APPROACH

• US 20080319932A1
• Filed: 06/21/2007
• Published: 12/25/2008
• Est. Priority Date: 06/21/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hulten, Geoffrey J., Goodman, Joshua T., Yih, Wen-tau
• Granted Patent: US 7,693,806 B2
• Time in Patent Office: Days
• US Class Current: 706/20
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: H04L 51/212 using filtering or selective blocking

Abstract

A system and method that facilitates and effectuates optimizing a classifier for greater performance in a specific region of classification that is of interest, such as a low false positive rate or a low false negative rate. A two-stage classification model can be trained and employed, where the first stage classification is optimized over the entire classification region and the second stage classifier is optimized for the specific region of interest. During training the entire set of training data is employed by a first stage classifier. Only data that is classified by the first stage classifier or by cross validation to fall within a region of interest is used to train the second stage classifier. During classification, data that is classified within the region of interest by the first classification is given the first stage classifier'"'"'s classification value, otherwise the classification value for the instance of data from the second stage classifier is used.

Claims

1. A method for classification of data using a multi-stage stage classifier comprising:

training a first stage classifier of the multi-stage classifier with an entire set of training data

classifying each of instance of training data in the set of training by employing the first stage classifier;

adding each instance of the training data that has been classified by the first stage classifier to have a classification value within a predefined threshold range into a set of second stage training data; and

training a second stage classifier of the multi-stage classifier with the entire set of second stage training data.

storing the multi-stage classifier on a computer readable storage medium.

2. The method of claim 1, wherein adding each instance of the training data that has been classified by the first stage classifier to have a classification value above a predefined threshold into a set of second stage training data comprises:

splitting the set of training data into disjoint subsets of training data;

adding instances of training data to a set of second stage training data by iteratively performing the following acts on each subset of training data;

training a subset classifier associated with a subset of training data by using all of the instances of training data except the instances of training data within the subset of training data;

applying the subset classifier on the subset of training data;

adding each instance of data from the subset of training data that has been classified with a classification value within a predefined threshold range by the subset classifier to a set of second stage training data;

3. The method of claim 2, wherein the classification value is a probability.

4. The method of claim 1, wherein the features of the training data used by the first stage classifier for classification and the features of the training data used by second stage classifier for classification are identical.

5. The method of claim 1, wherein the threshold is defined based on a desired false positive rate or a desired false negative rate.

6. The method of claim 1, wherein instances of training data are duplicated according to defined utility values associated with each instance.

7. The method of claim 1, wherein at least one of the first stage classifier or second stage classifier is modified according to defined utility values.

8. The method of claim 1, classifying an instance of unclassified data by employing the multi-stage classifier by:

producing a classification value for the instance of unclassified data by employing the first stage classifier;

outputting the classification value produced by the first stage classifier if the classification value produced by the first stage classifier is below a predefined threshold; and

producing a classification value for the instance of unclassified data by employing the second stage classifier and outputting the classification value produced by the second stage classifier if the classification value produced by the first stage classifier is not below the predefined threshold.

9. The method of claim 1, wherein the set of training data comprises a plurality of e-mail, each e-mail is labeled as spam or non-spam.

10. The method of claim 1, wherein the set of training data comprises at least one of fraud detection data, intrusion detection data, patient diagnostic data, biometric data, incoming phone call data, audio data, video data, document data, web page data, pop-up window data, or image data.

11. The method of claim 1, wherein there are more than two classes and a threshold range is defined for each class.

12. A system for classification of classification of data, comprising:

a set of training data containing a plurality of instances of training data;

a multi-stage classifier component that has at least a first stage classifier and second stage classifier, wherein cross validation of the training data with respect to a predefined threshold is employed by the multi-stage classifier component to produce a set of second stage training data.

13. The system of claim 12, wherein the first stage classifier is trained using the entire set of training data and the second stage classifier is trained using the entire set of second stage training data.

14. The system of claim 12, wherein the multi-stage classifier component is trained with utility.

15. The system of claim 12, wherein the set of training data comprises at least one of fraud detection data, intrusion detection data, medical diagnostic data, biometric data, incoming phone call data, audio data, video data, document data, web page data, pop-up window data, or image data.

16. The system of claim 12, further comprising an instance of unclassified data that is classified by the multi-stage classifier component, wherein the multi-stage classifier component outputs classification value from the first stage classifier'"'"'s classification of the instance of data if the classification value is below the threshold, otherwise the multi-stage classifier component outputs the classification value from the second stage classifiers classification of the instance of data.

17. The system of claim 12, wherein the threshold is defined based on a desired false positive rate or a desired false negative rate.

18. A system for classification of classification of data, comprising:

one or more instances of data;

a multi-stage classifier component that has at least a first stage classifier and a second stage classifier, wherein the multi-stage classifier classifies at least one of the one or more instances of data by outputting the classification value from the first stage classifier'"'"'s classification of the at least one instance of data if the classification value is within a threshold range, otherwise the multi-stage classifier component outputs the classification value from the second stage classifiers classification of the at least one instance of data.

19. The system of claim 18, wherein the features employed for classification by the first stage classifier and the second stage classifier are identical.

20. The system of claim 18, wherein the at least one or more instances of data comprise at least one of fraud detection data, intrusion detection data, or email labeled as spam or not spam.