Hierarchical determination of feature relevancy

• US 20050008227A1
• Filed: 07/08/2003
• Published: 01/13/2005
• 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
• Granted Patent: US 7,313,279 B2
• Time in Patent Office: Days
• 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;

using a similarity metric to evaluate for each local region a relationship measure between input features and a selected output feature; 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 similarity metric is linear.

10. The method of claim 1, wherein the similarity 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 R².

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 perform the method claimed in claim 1.

14. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform the method claimed in claim 1.

15. A computer data signal transmitted in one or more segments in a transmission medium which embodies instructions executable by a computer to perform the method claimed in claim 1.

16. 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;

on each level of the hierarchy, using a similarity metric to evaluate for each local region in the level a relationship measure between input feature values on the one hand and a selected output on the other hand; 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.

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

18. The method of claim 17 further comprising:

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

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

20. The method of claim 16 further comprising:

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

21. The method of claim 16, wherein the local regions are nonoverlapping.

22. The method of claim 16, wherein the. similarity metric is linear.

23. The method of claim 16, wherein the similarity metric includes a projection or distance.

24. The method of claim 16, wherein the relationship measure includes a correlation.

25. The method of claim 16, wherein the relationship measure includes R².

26. 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 perform the method claimed in claim 16.

27. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform the method claimed in claim 16.

28. A computer data signal transmitted in one or more segments in a transmission medium which embodies instructions executable by a computer to perform the method claimed in claim 16.