Recursive feature elimination method using support vector machines

• US 10,402,685 B2
• Filed: 11/11/2010
• Issued: 09/03/2019
• Est. Priority Date: 10/27/1999
• Status: Active Grant

• Current Assignee: Curtis Anderson, Health Discovery Corporation, James Roberts, Joe Mckenzie, Jules B. Paderewski, Julian N. Stern, Memorial Health Systems Incorporated, Timothy P. O'Hayer
• Original Assignee: Health Discovery Corporation
• Inventors: Guyon, Isabelle, Weston, Jason Aaron Edward
• Primary Examiner(s): Gonzales, Vincent
• Application Number:
  US12/944,197
• Publication Number:
  US 20110106735A1
• Time in Patent Office: 3,218 Days
• CPC Class Codes: G06F 18/2115 by evaluating different subsets according to an optimisation criterion, e.g. class separability, forward selection or backward elimination
• 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: G16B 25/00 ICT specially adapted for hybridisation; ICT specially adapted for gene or protein expression
• CPC Class Codes: G16B 25/10 Gene or protein expression profiling; Expression-ratio estimation or normalisation
• CPC Class Codes: G16B 40/00 ICT specially adapted for biostatistics; ICT specially adapted for bioinformatics-related machine learning or data mining, e.g. knowledge discovery or pattern finding
• CPC Class Codes: G16B 40/20 Supervised data analysis
• CPC Class Codes: G16B 40/30 Unsupervised data analysis

Abstract

Identification of a determinative subset of features from within a group of features is performed by training a support vector machine using training samples with class labels to determine a value of each feature, where features are removed based on their the value. One or more features having the smallest values are removed and an updated kernel matrix is generated using the remaining features. The process is repeated until a predetermined number of features remain which are capable of accurately separating the data into different classes. In some embodiments, features are eliminated by a ranking criterion based on a Lagrange multiplier corresponding to each training sample.

Claims

1. A method, comprising:

retrieving training data from one or more storage devices in communication with a processor, the processor operable for;

determining a value for each feature in a group of features provided by the training data;

eliminating at least one feature with a minimum ranking criterion from the group, wherein the minimum ranking criterion is obtained based on the value for each feature in the group;

subtracting a matrix from the kernel data to provide an updated kernel data, each component of the matrix comprising a dot product of two of training samples provided by at least a part of the training data that corresponds to the eliminated feature;

updating the value for each feature of the group based on the updated kernel data;

repeating of eliminating the at least one feature from the group and updating the value for each feature of the group until a number of features in the group reaches a predetermined value to generate a feature ranking list; and

recognizing a new data corresponding to the group of features with the feature ranking list.

2. The method of claim 1, wherein the training data further comprises a plurality of training samples, each of the training samples corresponding to the group of features.

3. The method of claim 1, wherein determining the value comprises:

computing a kernel data based on the training data;

computing the value for each feature of the group based on the kernel data; and

storing the kernel data in a memory.

4. The method of claim 3, wherein computing the kernel data further comprises computing a matrix as the kernel data, each component of the matrix comprising a dot product of two of training samples provided by the training data.

5. The method of claim 1, wherein eliminating at least one feature comprises:

computing a ranking criterion for each feature of the group based on the value for the each feature;

eliminating the at least one feature with the minimum ranking criterion from the group; and

recording the eliminated feature in a feature ranking list.

6. The method of claim 5, wherein the ranking criterion is based on a Lagrange multiplier corresponding to each training sample.

7. A non-transitory machine-readable medium comprising a plurality of instructions, that in response to being executed, result in a computing system executing a support vector machine, comprising:

a training function to determine a value for each feature in a group of features provided by a training data; and

an eliminate function to eliminate at least one feature with a minimum ranking criterion from the group, wherein the minimum ranking criterion is obtained based on the value for each feature in the group, wherein the training function further comprises a kernel data function to subtract a matrix from the kernel data to provide an updated kernel data, each component of the matrix comprising a dot product of two of training samples provided by at least a part of the training data that corresponds to the eliminated feature, and a value update function to update the value for each feature based on the updated kernel data, and wherein the apparatus support vector machine further repeats eliminating the at least one feature from the group and updating the value for each feature of the group until a number of features in the group reaches a predetermined value, to generate a feature ranking list for a use of recognizing a new data corresponding to the group of features.

8. The non-transitory machine-readable medium of claim 7, wherein the training data comprises a plurality of training samples, each of the training samples having the group of features.

9. The non-transitory machine-readable medium of claim 7, further comprising:

a decision function to decide whether to repeat the elimination of the at least one features from the group and update of the value for each feature of the group until a number of features in the group reaches a predetermined value.

10. The non-transitory machine-readable medium of claim 7, wherein the eliminate function further comprises a ranking criterion function to compute a ranking criterion for each feature of the group based on the value for the each feature.

11. The non-transitory machine-readable medium of claim 10, wherein the ranking criterion is based on a Lagrange multiplier corresponding to each training sample.

12. A non-transitory machine-readable medium comprising a plurality of instructions that in response to being executed result in a computing system:

determining a value for each feature in a group of features provided by a training data;

eliminating at least one feature with a minimum ranking criterion from the group, wherein the minimum ranking criterion is obtained based on the value for each feature in the group;

subtracting a matrix from the kernel data to provide an updated kernel data, each component of the matrix comprising a dot product of two of training samples provided by at least a part of the training data that corresponds to the eliminated feature;

updating the value for each feature of the group based on the updated kernel data;

repeating of eliminating the at least one feature from the group and updating the value for each feature of the group until a number of features in the group reaches a predetermined value to generate a feature ranking list; and

recognizing a new data corresponding to the group of features with the feature ranking list.

13. The non-transitory machine-readable medium of claim 12, wherein the training data further comprises a plurality of training samples, each of the training samples corresponding to the group of features.

14. The non-transitory machine-readable medium of claim 12, wherein the plurality of instructions that result in the computing system determining the value, further result in the computing system:

computing a kernel data based on the training data; and

computing the value for each feature of the group based on the kernel data;

15. The non-transitory machine-readable medium of claim 14, wherein the plurality of instructions that result in the computing system computing the kernel data, further result in the computing system computing a matrix as the kernel data, each component of the matrix comprising a dot product of two of training samples provided by the training data.

16. The non-transitory machine-readable medium of claim 12, wherein the plurality of instructions that result in the computing system eliminating at least one feature, further result in the computing system:

computing a ranking criterion for each feature of the group based on the value for the each feature;

eliminating the at least feature with the minimum ranking criterion from the group; and

recording the eliminated feature in a feature ranking list.

17. The non-transitory machine-readable medium of claim 16, wherein the ranking criterion is based on a Lagrange multiplier corresponding to each training sample.

18. A computer-implemented method for predicting patterns in sample data, wherein the sample data comprises a group of features that describe the data, the method comprising:

identifying a determinative subset of features that are most correlated to the patterns comprising;

retrieving a training data having class labels with respect to the patterns from a memory in communication with a computer processor programmed for executing a support vector machine comprising a kernel;

calculating a kernel matrix using the training data to determine a value for each feature in the group of features;

eliminating at least one feature with a minimum value from the group;

calculating an updated kernel matrix, each component of the updated kernel matrix comprising a dot product of two training samples provided by at least a part of the training data that corresponds to the eliminated feature;

determining an updated value for each remaining feature of the group of features based on the updated kernel matrix;

repeating steps eliminating, calculating an updated kernel matrix and determining an updated value for a plurality of iterations until a pre-determined number of features in the group remain; and

generating an output comprising a feature ranking list, wherein the features in the feature ranking list comprise the determinative subset of features for predicting patterns in new data.

19. The method of claim 18, wherein eliminating comprises eliminating multiple features from the group so that the number of features is reduced by the closest power of two to the number of remaining features.

20. The method of claim 18, wherein the one or more features removed in eliminating comprises up to half of the remaining features.

21. The method of claim 18, wherein eliminating comprises eliminating a plurality of features so that the number of features in the first iteration is reduced by up to half of the remaining features until a specified number of features remain and thereafter removing one feature per iteration.

22. The method of claim 18, wherein eliminating at least one feature comprises:

computing a ranking criterion for each feature of the group based on the value for the each feature;

eliminating the at least one feature with the minimum rnking criterion from the group; and

recording the eliminated feature in a feature ranking list.

23. The method of claim 22, wherein the ranking criterion is based on a Lagrange multiplier corresponding to each training sample.