Transductive feature selection with maximum-relevancy and minimum-redundancy criteria

• US 9,471,881 B2
• Filed: 01/21/2013
• Issued: 10/18/2016
• Est. Priority Date: 01/21/2013
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Haws, David, He, Dan, Parida, Laxmi P., Rish, Irina
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Seck, Ababacar
• Application Number:
  US13/745,930
• Publication Number:
  US 20140207711A1
• Time in Patent Office: 1,366 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• 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: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• 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

Abstract

Various embodiments select features from a feature space. In one embodiment, a set of training samples and a set of test samples are received. The set of training samples includes a set of features and a class value. The set of test samples includes the set of features absent the class value. A relevancy with respect to the class value is determined for each of a plurality of unselected features based on the set of training samples. A redundancy with respect to one or more of the set of features is determined for each of the plurality of unselected features in the first set of features based on the set of training samples and the set of test samples. A set of features is selected from the plurality of unselected features based on the relevancy and the redundancy determined for each of the plurality of unselected features.

Claims

1. A computer implemented method for selecting features from a feature space, the computer implemented method comprising:

obtaining, by a processor, a set of training samples and a set of test samples, wherein the set of training samples comprises a first set of features and a class value, and wherein the set of test samples comprises a second set of features, where the second set of features is the first set of features absent the class value;

determining, for each of a plurality of unselected features in a plurality of features comprising the first and second set of features, a relevancy with respect to the class value based on only the set of training samples;

determining, for each of the plurality of unselected features, a redundancy with respect to the plurality of features based on both the set of training samples and the set of test samples;

selecting a set of features from the plurality of unselected features based on the relevancy and the redundancy determined for each of the plurality of unselected features, wherein the selecting is performed based on

2. The computer implemented method of claim 1, wherein each of the set of features that has been selected has a maximum relevancy among each of the plurality of unselected features with respect to the class value based on the set of training samples, and has a minimum redundancy among each of the plurality of unselected features with respect to the set of features based on the set of training samples and the set of test samples.

3. The computer implemented method of claim 1, wherein the relevancy is determined based on mutual information between a given unselected feature in the plurality of unselected features and the class value based on the set of training samples.

4. The computer implemented method of claim 3, wherein the mutual information is determined based on comprising:

determining that the class value is within a given threshold;

rounding the class value; and

multiplying the class value by a scalar, wherein an entropy of the class value after being multiplied by the scalar is within a given threshold of an original entropy of the class value.

5. The computer implemented method of claim 1, wherein the redundancy is determined based on mutual information between a given unselected feature in the plurality of unselected features and each feature in the plurality of features.

6. The computer implemented method of claim 5, further comprising:

storing a set of counts for each of a set of values used to determine the mutual information between the given unselected feature and the plurality of features; and

determining the mutual information between the given unselected feature and the plurality of features based on the set of counts that has been stored.