Methods for feature selection in a learning machine

• US 7,318,051 B2
• Filed: 05/20/2002
• Issued: 01/08/2008
• Est. Priority Date: 05/18/2001
• Status: Expired due to Fees

• 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: Elisseeff, Andre, Schoelkopf, Bernhard, Perez-Cruz, Fernando, Weston, Jason Aaron Edward
• Primary Examiner(s): Holmes, Michael B.
• Application Number:
  US10/478,192
• Publication Number:
  US 20050216426A1
• Time in Patent Office: 2,059 Days
• Field of Search: 706 15- 16
• US Class Current: 706/12
• CPC Class Codes: G06F 18/2113 by ranking or filtering the set of features, e.g. using a measure of variance or of feature cross-correlation
• 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: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06F 18/217 Validation; Performance evaluation; Active pattern learning techniques
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• 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: G09B 5/00 Electrically-operated educational appliances working with questions and answers G09B7/00; simulators G09B9/00; advertising or displaying in general G09F
• CPC Class Codes: G09B 7/00 Electrically-operated teaching apparatus or devices working with questions and answers mechanically operated G09B3/00; computing arrangements G06F

Abstract

In a pre-processing step prior to training a learning machine, pre-processing includes reducing the quantity of features to be processed using feature selection methods selected from the group consisting of recursive feature elimination (RFE), minimizing the number of non-zero parameters of the system (l_o-norm minimization), evaluation of cost function to identify a subset of features that are compatible with constraints imposed by the learning set, unbalanced correlation score and transductive feature selection. The features remaining after feature selection are then used to train a learning machine for purposes of pattern classification, regression, clustering and/or novelty detection. (FIG. 3, 300, 301, 302, 304, 306, 308, 309, 310, 311, 312, 314)

Claims

1. A computer-implemented method for identifying a pattern within a large dataset, wherein data points in the dataset correspond to a physical measurement and have a plurality of features that describe attributes of the data point, the method comprising:

inputting the large dataset into a computer system having a processor and a memory;

selecting a feature subset of the large number of features for processing in a learning machine by executing a feature selection algorithm on the dataset to identify the subset of features, wherein the algorithm is selected from the group consisting of l₀-norm minimization and unbalanced correlation, wherein l₀-norm minimization comprises finding a smallest number of non-zero elements of a weight vector w in the relationship D(x)=w·

x+b, and unbalanced correlation comprises dividing the dataset into unbalanced groups of positive and negative examples and ranking features according to a success criterion for correctly classifying the dataset;

processing the feature subset of the data points of the large dataset to identify the pattern; and

generating an output to a printer or display device, the output comprising the identified pattern within the large dataset for the feature subset.

2. The method of claim 1, wherein the learning machine is a support vector machine.

3. The method of claim 1, wherein the algorithm is l₀-norm minimization and the dataset comprises a multi-label dataset, and further comprising calculating a label set size.

4. The method of claim 3, wherein the step of calculating label set size comprises minimizing a ranking loss.

5. The method of claim 3, wherein the dataset comprises gene expression data obtained from DNA micro-arrays and the output comprises identities of a group of genes for detecting a disease or condition.

6. The method of claim 1, wherein the algorithm is l₀-norm minimization and the algorithm comprises approximately minimizing l₀-norm by minimizing l₁-norm.

7. The method of claim 1, wherein the algorithm is l₀-norm minimization and the algorithm comprises approximately minimizing l₀-norm by minimizing l₂-norm.

8. The method of claim 1, further comprising mapping the dataset into feature space prior to executing the feature selection algorithm.

9. The method of claim 1, wherein the algorithm is unbalanced correlation and the dataset comprises labeled and unlabeled data, the method further comprising using transductive learning to classify the unlabeled data prior to executing the feature selection algorithm.

10. The method of claim 1, wherein the dataset comprises gene expression data obtained from DNA micro-arrays and the output comprises identities of a group of genes for detecting a disease or condition.

19. The method of claim 10, wherein the large dataset is a prostate cancer database.

11. A computer-implemented method for identifying a pattern within a large dataset, wherein the data points in the dataset correspond to physical measurements and each data point has a plurality of features that describe attributes of the data point, the method comprising:

inputting the large dataset into a computer system having a processor and a memory;

selecting a feature subset of the large number of features for processing in a learning machine by executing a feature selection algorithm on the dataset to identify the subset of features, wherein the algorithm comprises l₀-norm minimization, wherein l₀-norm minimization comprises finding a smallest number of non-zero elements of a weight vector w in the relationship D(x)=w·

x+b;

processing the feature subset of the data points of the large dataset to identify the pattern; and

generating an output to a printer or display device, the output comprising the identified pattern within the large dataset for the feature subset.

12. The method of claim 11, wherein the learning machine is a support vector machine.

13. The method of claim 11, wherein the dataset comprises a multi-label dataset, and further comprising calculating a label set size.

14. The method of claim 13, wherein the step of calculating label set size comprises minimizing a ranking loss.

15. The method of claim 11, wherein the dataset comprises gene expression data obtained from DNA micro-arrays and the output comprises identities of a group of genes for detecting a disease or condition.

16. The method of claim 11, wherein the algorithm comprises approximately minimizing l₀-norm by minimizing l₁-norm.

17. The method of claim 11, wherein the algorithm comprises approximately minimizing l₀-norm by minimizing l₂-norm.

18. The method of claim 11, further comprising mapping the dataset into feature space prior to executing the feature selection algorithm.

20. The method of claim 15, wherein the large dataset is a prostate cancer database.