HILL-CLIMBING FEATURE SELECTION WITH MAX-RELEVANCY AND MINIMUM REDUNDANCY CRITERIA

• US 20140207800A1
• Filed: 09/18/2013
• Published: 07/24/2014
• Est. Priority Date: 01/21/2013
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: HAWS, David, HE, Dan, PARIDA, Laxmi P.
• Application Number:
  US14/030,806
• Publication Number:
  US 20140207800A1
• Time in Patent Office: Days
• US Class Current: 707/749
• CPC Class Codes: G06F 16/24578 using ranking

Abstract

Various embodiments select features from a feature space. In one embodiment a candidate feature set of k′ features is selected from at least one set of features based on maximum relevancy and minimum redundancy (MRMR) criteria. A target feature set of k features is identified from the candidate feature set, where k′>k. Each a plurality of features in the target feature set is iteratively updated with each of a plurality of k′−k features from the candidate feature set. The feature from the plurality of k′−k features is maintained in the target feature set, for at least one iterative update, based on a current MRMR score of the target feature set satisfying a threshold. The target feature set is stored as a top-k feature set of the at least one set of features after a given number of iterative updates.

Claims

1. An information processing system for selecting features from a feature space, the information processing system comprising:

a memory;

a processor communicatively coupled to the memory; and

a feature selection module coupled to the memory and the processor, wherein the feature selection module is configured to perform a method comprising;

selecting, by a processor, a candidate feature set of k′

features from at least one set of features based on maximum relevancy and minimum redundancy (MRMR) criteria;

identifying a target feature set of k features from the candidate feature set, where k′

>

k;

iteratively updating each of a plurality of features in the target feature set with each of a plurality of k′

−

k features from the candidate feature set;

maintaining, for at least one iterative update, the feature from the plurality of k′

−

k features in the target feature set based on a current MRMR score of the target feature set satisfying a threshold; and

storing, after a given number of iterative updates, the target feature set as a top-k feature set of the at least one set of features.

2. The information processing system of claim 1, wherein the method further comprises:

ranking each of the set of candidate features based on an order in which each of the set of candidate features were selected from the at least one set of features,

wherein the k features are a set of k highest ranking features in the set of candidate features.

3. The information processing system of claim 1, wherein the current MRMR score of the target set of features for each iterative update comprises:

determining a relevance of each of the set of target features with respect to a class value associated with the at least one set of features;

determining a redundancy between each pair of features in the target set of features; and

determining the MRMR score based on a sum each determined relevances minus a sum of each of the determined redundancies.

4. The information processing system of claim 1, wherein maintaining the feature from the plurality of k′

−

k features in the target feature set comprises;

comparing the current MRMR score to a previous MRMR score of the target feature set; and

maintaining the feature from the plurality of k′

−

k features in the target feature set based on the current MRMR score being an improvement over the previous MRMR score.

5. The information processing system of claim 1, wherein the method further comprises:

removing, for at least one iterative update, the feature in the plurality of k′

−

k features from the target feature set based on a current MRMR score for the target feature failing to satisfy a threshold.

6. The information processing system of claim 5, wherein removing the feature in the plurality of k′

−

k features from the target feature set comprises;

comparing the current MRMR score to a previous MRMR score of the target feature set; and

removing the feature in the plurality of k′

−

k features from the target feature set based on the current MRMR score failing to be an improvement over the previous MRMR score.

7. A non-transitory computer program product for selecting features from a feature space, the computer program product comprising:

a storage medium readable by a processing circuit and storing instructions for execution by the processing circuit for performing a method comprising;

selecting, by a processor, a candidate feature set of k′

features from at least one set of features based on maximum relevancy and minimum redundancy (MRMR) criteria;

identifying a target feature set of k features from the candidate feature set, where k′

>

k;

iteratively updating each of a plurality of features in the target feature set with each of a plurality of k′

−

k features from the candidate feature set;

maintaining, for at least one iterative update, the feature from the plurality of k′

−

k features in the target feature set based on a current MRMR score of the target feature set satisfying a threshold; and

storing, after a given number of iterative updates, the target feature set as a top-k feature set of the at least one set of features.

8. The non-transitory computer program product of claim 7, wherein determining the candidate feature set of k′

features comprises;

determining, for each of the at least one set of features, a relevancy with respect to a class value;

determining, for each of the at least one set of features, a redundancy with respect to the one or more of the at least one set of features; and

selecting each feature of the candidate feature set from the at least one set of features based on the relevancy and the redundancy determined for each of the at least one set of features.

9. The non-transitory computer program product of claim 7, wherein the method further comprises:

ranking each of the set of candidate features based on an order in which each of the set of candidate features were selected from the at least one set of features,

wherein the k features are a set of k highest ranking features in the set of candidate features.

10. The non-transitory computer program product of claim 7, wherein the current MRMR score of the target set of features for each iterative update comprises:

determining a relevance of each of the set of target features with respect to a class value associated with the at least one set of features;

determining a redundancy between each pair of features in the target set of features; and

determining the MRMR score based on a sum each determined relevances minus a sum of each of the determined redundancies.

11. The non-transitory computer program product of claim 7, wherein maintaining the feature from the plurality of k′

−

k features in the target feature set comprises;

comparing the current MRMR score to a previous MRMR score of the target feature set; and

maintaining the feature from the plurality of k′

−

k features in the target feature set based on the current MRMR score being an improvement over the previous MRMR score.

12. The non-transitory computer program product of claim 7, wherein the method further comprises:

removing, for at least one iterative update, the feature in the plurality of k′

−

k features from the target feature set based on a current MRMR score for the target feature failing to satisfy a threshold.

13. The non-transitory computer program product of claim 12, wherein removing the feature in the plurality of k′

−

k features from the target feature set comprises;

comparing the current MRMR score to a previous MRMR score of the target feature set; and

removing the feature in the plurality of k′

−

k features from the target feature set based on the current MRMR score failing to be an improvement over the previous MRMR score.