Hierarchical determination of feature relevancy

• US 7,313,279 B2
• Filed: 07/08/2003
• Issued: 12/25/2007
• Est. Priority Date: 07/08/2003
• Status: Active Grant

• Current Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Original Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Inventors: Duan, Baofu, Pao, Yoh-Han, Meng, Zhuo
• Primary Examiner(s): MARIAM, DANIEL G
• Application Number:
  US10/615,885
• Publication Number:
  US 20050008227A1
• Time in Patent Office: 1,631 Days
• Field of Search: 382/173, 382/190, 382/195, 382/209, 382/225, 382/282, 707 4- 5
• US Class Current: 382/195
• 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/24323 Tree-organised classifiers

Abstract

Methods for feature selection based on hierarchical local-region analysis of feature relationships in a data set are provided.

Claims

1. A method for feature selection based on hierarchical local-region analysis of feature characteristics in a data set, comprising:

partitioning a data space associated with a data set into a hierarchy of pluralities of local regions;

evaluating a relationship measure for each local region using a metric based on similarity between input features and a selected output; and

identifying one or more relevant features, by using the relationship measure for each local region.

2. The method of claim 1 further comprising:

determining a feature relevancy of a selected feature by performing a weighted sum of the relationship measures for the selected feature over the plurality of local regions.

3. The method of claim 2, wherein weights for the weighted sum are based on sizes of the respective local regions.

4. The method of claim 1, wherein the partitioning of the data space into the hierarchy of pluralities of local regions is performed by hierarchical clustering of the data set in a plurality of levels.

5. The method of claim 4, wherein feature relevancies are determined for each of the input features based on the relationship measures at each level of the hierarchical clustering and the relevant features are identified based on the feature relevancies.

6. The method of claim 1 further comprising:

determining for each local region a corresponding subset of relevant features based on the relationship measures for the local region.

7. The method of claim 6, wherein the subsets of relevant features for respective local regions are non-identical.

8. The method of claim 1, wherein the local regions are nonoverlapping.

9. The method of claim 1, wherein the metric is linear.

10. The method of claim 1, wherein the metric includes a projection or distance.

11. The method of claim 1, wherein the relationship measure includes a correlation.

12. The method of claim 1, wherein the relationship measure includes an R-squared value.

13. A computer system, comprising:

a processor; and

a program storage device readable by the computer system, tangibly embodying a program of instructions executable by the processor to;

partition a data space associated with a data set into a hierarchy of pluralities of local regions;

evaluate a relationship measure for each local region using a metric based on similarity between input features and a selected output; and

identify one or more relevant features, by using the relationship measure for each local region.

14. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to:

partition a data space associated with a data set into a hierarchy of pluralities of local regions;

evaluate a relationship measure for each local region using a metric based on similarity between input features and a selected output; and

identify one or more relevant features, by using the relationship measure for each local region.

15. A method for feature selection based on hierarchical local-region analysis of feature characteristics in a data set, comprising:

partitioning a data space corresponding to a data set into a hierarchy of pluralities of local regions;

evaluating a relationship measure for each local region using a metric based on similarity between input features and a selected output; and

determining a relevancy of a selected feature by performing a weighted sum of the relationship measures for the feature over the plurality of local regions at appropriate levels.

16. The method of claim 15, wherein the partitioning of the data space is performed through hierarchical clustering of the data set in a plurality of cluster levels.

17. The method of claim 16 further comprising:

identifying relevant features at each level of the hierarchical clustering and determining corresponding feature relevancies.

18. The method of claim 15, wherein weights for the weighted sum are based on sizes of the respective local regions.

19. The method of claim 15 further comprising:

ranking the input features according to the corresponding feature relevancies of the input features.

20. The method of claim 15, wherein the local regions are nonoverlapping.

21. The method of claim 15, wherein the metric is linear.

22. The method of claim 15, wherein the metric includes a projection or distance.

23. The method of claim 15, wherein the relationship measure includes a correlation.

24. The method of claim 15, wherein the relationship measure includes an R-squared value.

25. A computer system, comprising:

a processor; and

a program storage device readable by the computer system, tangibly embodying a program of instructions executable by the processor to;

partition a data space corresponding to a data set into a hierarchy of pluralities of local regions;

evaluate a relationship measure for each local region using a metric based on similarity between input features and a selected output; and

determine a relevancy of a selected feature by performing a weighted sum of the relationship measures for the feature over the plurality of local regions at appropriate levels.

26. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to:

partition a data space corresponding to a data set into a hierarchy of pluralities of local regions;

evaluate a relationship measure for each local region using a metric based on similarity between input features and a selected output; and

determine a relevancy of a selected feature by performing a weighted sum of the relationship measures for the feature over the plurality of local regions at appropriate levels.