Granular support vector machine with random granularity

• US 8,160,975 B2
• Filed: 01/25/2008
• Issued: 04/17/2012
• Est. Priority Date: 01/25/2008
• Status: Active Grant

• Current Assignee: McAfee, LLC
• Original Assignee: McAfee, Inc. (McAfee, LLC)
• Inventors: Tang, Yuchun, He, Yuanchen
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): Hill, Stanley K
• Application Number:
  US12/020,253
• Publication Number:
  US 20090192955A1
• Time in Patent Office: 1,544 Days
• Field of Search: None
• US Class Current: 706/12
• CPC Class Codes: G06F 18/2411 based on the proximity to a decision surface, e.g. support vector machines
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]
• CPC Class Codes: H04L 51/212 using filtering or selective blocking

Abstract

Methods and systems for granular support vector machines. Granular support vector machines can randomly select samples of datapoints and project the samples of datapoints into a randomly selected subspaces to derive granules. A support vector machine can then be used to identify hyperplane classifiers respectively associated with the granules. The hyperplane classifiers can be used on an unknown datapoint to provide a plurality of predictions which can be aggregated to provide a final prediction associated with the datapoint.

Claims

1. A method comprising:

receiving a training dataset comprising a plurality of tuples and a plurality of attributes for each of the tuples;

deriving a plurality of granules from the training dataset, each granule comprising a plurality of sample tuples and a plurality of sample attributes, wherein for each of the plurality of granules;

the plurality of sample tuples is randomly selected from among the plurality of tuples with replacement; and

the plurality of sample attributes is randomly selected from among the plurality of attributes without replacement;

processing the granules using a support vector machine process to identify a hyperplane classifier associated with each of the granules;

predicting a classification of a new tuple using each of the hyperplane classifiers to produce a plurality of predictions;

aggregating the predictions to derive a decision on a final classification of the new tuple;

validating a first hyperplane classifier associated with a granule by classifying a plurality of tuples from the training dataset which were not included in the granule;

generating a hyperplane classifier effectiveness level based upon the validation of the first hyperplane classifier against tuples from the training dataset which were not included in the granule;

determining whether the hyperplane classifier effectiveness level exceeds a threshold effectiveness level; and

in response to determining that the hyperplane classifier effectiveness level does not exceed the threshold effectiveness level;

removing the first hyperplane classifier; and

requesting a second plurality of sample attributes, each sample attribute in the second plurality of sample attributes different from each sample attribute in the plurality of sample attributes, for use in identifying new hyperplane classifiers.

2. The method of claim 1, wherein the selection of granule tuples and granule attributes for each granule is independent of the selection of granule tuples and granule attributes for other granules.

3. The method of claim 1, wherein the training dataset comprises a relational database of tuples with associated attributes, each of the tuples having a known classification.

4. The method of claim 1, wherein aggregating the predicted classifications comprises weighting the predictions based upon hyperplane classifier effectiveness levels associated with the granules, respectively, and aggregating the weighted predictions.

5. The method of claim 1, further comprising:

weighting the predictions based upon a distance of the new tuple from the hyperplane classifiers, respectively; and

aggregating the weighted predictions.

6. The method of claim 1, wherein each of the predictions comprises a vote, and aggregating the predictions comprises adding the votes together and determining which classification is most common.

7. The method of claim 1, wherein the tuples are gene sequences and the attributes are features of the gene sequences, whereby the method is operable to determine whether a gene sequence is likely to share known characteristics of other gene sequences.

8. The method of claim 1, wherein the tuples are documents and the attributes are features of the documents, whereby the method is operable to determine whether a document is likely to share known characteristics of other documents.

9. The method of claim 8, wherein the known characteristics comprise one or more of spam characteristics, virus characteristics, spyware characteristics, or phishing characteristics, and the method is operable to determine whether the new tuple should be classified as including one or more of the known characteristics.

10. The method of claim 1, wherein processing the granules comprises processing the granules on a plurality of processors in parallel, the processors being operable to operate support vector machines to identify hyperplane classifiers associated with the granules.

11. The method of claim 10, further comprising selecting the plurality of processors based upon the processing power available on the respective processors.

12. A system for performing the disclosed methods) comprising:

one or more computers;

one or more memory devices in data communication with the one or more computers and storing instructions defining;

a granule selection module operable to select a plurality of granules from a training dataset, each of the granules comprising a plurality of tuples and a plurality of attributes, wherein, for each of the plurality of granules, the plurality of tuples are randomly selected with replacement and the plurality of attributes are randomly selected without replacement;

a plurality of granule processing modules operable to process granules using a support vector machine process to identify a hyperplane classifier associated with each of the granules;

one or more prediction modules operable to predict a classification associated with an unknown tuple based upon the hyperplane classifiers to produce a plurality of granule predictions; and

an aggregation module operable to aggregate the granule predictions to derive a decision on a final classification associated with the unknown tuple; and

a validation module operable to;

validate a first hyperplane classifier associated with a granule by attempting to classify a plurality of tuples from the training dataset which were not included in the granule;

generate a hyperplane classifier effectiveness level based upon the validation of the first hyperplane classifier against tuples from the training dataset which were not included in the granule;

determine whether the hyperplane classifier effectiveness level exceeds a threshold effectiveness level; and

in response to determining that the hyperplane classifier effectiveness level does not exceed the threshold effectiveness level;

remove the first hyperplane classifier; and

request a second plurality of attributes, each attribute in the second plurality of sample attributes different from each attribute in the plurality of attributes, for use in identifying new hyperplane classifiers.

13. The system of claim 12, wherein the unknown tuple comprises features of an unclassified document, and the system further comprises a parsing module operable to parse the unclassified document to derive a plurality of unclassified attributes associated with the unknown tuple.

14. The system of claim 13, wherein the one or more prediction modules are operable to extract a portion of the unclassified attributes based upon the granule and the hyperplane classifier, and is operable to compare the unclassified attributes to the hyperplane classifier to derive the prediction associated with the granule.

15. The system of claim 14, wherein the one or more prediction modules are operable to generate a prediction for each of the hyperplane classifiers to produce the plurality of granule predictions.

16. The system of claim 15, wherein the aggregation module is operable to count each of the predictions as a vote, and to derive a final prediction based upon which of the classifications accumulates the most votes.

17. The system of claim 12, wherein each prediction includes a distance metric from the hyperplane classifier, and the aggregation module is operable to weight each prediction based upon the associated distance metric.

18. The system of claim 12, wherein the plurality of granule modules are operable to be processed independently.

19. The system of claim 12, wherein the plurality of granule processing modules are operable to be processed in parallel.

20. The system of claim 12, wherein the plurality of granule processing modules are operable to be executed by separate processors.

21. The system of claim 12, wherein the system is operable to classify a tuple as one or more of a spam risk, a phishing risk, a virus risk, or a spyware risk.

22. A method comprising:

receiving a training dataset comprising a plurality of tuples and a plurality of attributes for each of the tuples;

deriving a plurality of granules from the training dataset, each granule comprising a plurality of sample tuples and a plurality of sample attributes, wherein for each of the plurality of granules;

the plurality of sample tuples is randomly selected from among the plurality of tuples with replacement; and

the plurality of sample attributes is randomly selected from among the plurality of attributes without replacement;

processing the granules using a support vector machine process to identify a hyperplane classifier associated with each of the granules;

predicting a classification of a new tuple using each of the hyperplane classifiers to produce a plurality of predictions;

aggregating the predictions to derive a decision on a final classification of the new tuple;

validating a first hyperplane classifier associated with a granule by attempting to classify a plurality of tuples from the training dataset which were not included in the granule;

generating a hyperplane classifier effectiveness level based upon the validation of the first hyperplane classifier against tuples from the training dataset which were not included in the granule;

determining whether the hyperplane classifier effectiveness level exceeds a threshold effectiveness level; and

in response to determining that the hyperplane classifier effectiveness level does not exceed the threshold effectiveness level;

removing the first hyperplane classifier; and

requesting a new training dataset for use in identifying new hyperplane classifiers, wherein the new training dataset does not include data from the training dataset.

23. A computer program product, encoded on a computer-readable medium, operable to cause one or more processors to perform operations comprising:

receiving a training dataset comprising a plurality of tuples and a plurality of attributes for each of the tuples;

deriving a plurality of granules from the training dataset, each granule comprising a plurality of sample tuples and a plurality of sample attributes, wherein for each of the plurality of granules;

the plurality of sample tuples is randomly selected from among the plurality of tuples with replacement; and

the plurality of sample attributes is randomly selected from among the plurality of attributes without replacement;

processing the granules using a support vector machine process to identify a hyperplane classifier associated with each of the granules;

predicting a classification of a new tuple using each of the hyperplane classifiers to produce a plurality of predictions;

aggregating the predictions to derive a decision on a final classification of the new tuple;

validating a first hyperplane classifier associated with a granule by attempting to classify a plurality of tuples from the training dataset which were not included in the granule;

generating a hyperplane classifier effectiveness level based upon the validation of the first hyperplane classifier against tuples from the training dataset which were not included in the granule;

determining whether the hyperplane classifier effectiveness level exceeds a threshold effectiveness level; and

in response to determining that the hyperplane classifier effectiveness level does not exceed the threshold effectiveness level;

removing the first hyperplane classifier; and

requesting a new training dataset for use in identifying new hyperplane classifiers, wherein the new training dataset does not include data from the training dataset.