System and method for selection of important attributes

• US 6,026,399 A
• Filed: 05/30/1997
• Issued: 02/15/2000
• Est. Priority Date: 05/30/1997
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Kohavi, Ron, Sommerfield, Daniel A.
• Primary Examiner(s): Kulik, Paul V.
• Assistant Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US08/866,314
• Time in Patent Office: 991 Days
• Field of Search: 707/2, 707/3, 707/5, 707/6, 707/7
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• 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: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A system and method determines how well various attributes in a record discriminate different values of a chosen label attribute. An attribute is considered a relevant attribute if it discriminates different values of a chosen label attribute either alone or in conjunction with other attributes. According to the present invention, a label attribute is selected by a user from a set of records, with each record having a plurality of attributes. Next, one or more first important attributes considered important by the user are selected. The present invention then generates one or more second important attributes. The second important attributes together with the user chosen first important attributes discriminate well between different values of the label attribute. A measure called "purity" (a number from 0 to 100) informs how well each attribute discriminates the different label attributes. The purity measure allows the attributes to be ranked based on their importance.

Claims

1. A method for determining important attributes for discriminating between different values of a label attribute, the method comprising the steps of:

receiving a set of records, each record having a plurality of attributes;

permitting a user to choose the label attribute;

permitting a user to choose at least one first attribute that is considered important;

generating at least one second important attribute, said generated at least one second important attribute together with the said chosen at least one first important attribute discriminate well between the different values of the label attribute;

generating non-cumulative purity for each of said chosen at least one first important attribute and each of said generated at least one second important attribute, said non-cumulative purity indicating how well each first and second important attribute individually discriminates between different values of the label attribute; and

generating cumulative purity for each of said chosen at least one first important attribute and each of said generated at least one second important attribute, said cumulative purity indicating how well a respective important attribute in combination with other first and second important attributes discriminates between different values of the label attribute.

2. The method according to claim 1, wherein said permitting a user to choose at least one first important attribute step comprises:

permitting a user to choose a first important attribute that is empty.

3. The method according to claim 1, wherein said permitting a user to choose the label attribute step further includes the steps of:

displaying a panel;

permitting a user to input into said panel how many important attributes to generate; and

permitting a user to select a label attribute from a list of important attributes in said panel.

4. The method according to claim 1, further comprising the step of:

permitting a user to select a simple mode or an advanced mode for selecting at least how many important attributes to generate.

5. The method according to claim 4, wherein said permitting a user to select an advanced mode step further comprises the steps of:

displaying an advanced panel;

displaying a list of important attributes in said advanced panel; and

permitting a user to select whether to compute improved purity for left columns and cumulative purity for right columns in said advanced panel.

6. A method for determining important attributes for discriminating between the different values of a label attribute, the method comprising the steps of:

receiving a set of records, each record having a plurality of attributes;

permitting a user to choose the label attribute;

permitting a user to choose at least one first important attribute that is considered important;

generating at least one second important attribute, wherein each generated at least one second important attribute together with the said chosen at least one first important attribute discriminate better than at least one of the other attributes between the different values of the label attribute;

generating purity for said generated at least one second important attribute, said purity indicating how well each generated at least one second important attribute discriminates different values of the chosen label attribute; and

generating rank of each said generated at least one second important attribute based on its purity.

7. The method according to claim 6, wherein said permitting a user to choose at least one first important attribute step comprises:

permitting a user to choose a first important attribute that is empty.

8. The method according to claim 6, wherein said permitting a user to choose the label attribute step further includes the steps of:

displaying a panel;

permitting a user to input into said panel how many important attributes to generate; and

permitting a user to select a label attribute from a list of important attributes in said panel.

9. The method according to claim 6, further comprising the step of:

permitting a user to select a simple mode or an advanced mode for selecting at least how many important attributes to generate.

10. The method according to claim 9, wherein said permitting a user to select an advanced mode step further comprises the steps of:

displaying an advanced panel;

displaying a list of important attributes in said advanced panel; and

permitting a user to select whether to generate purity for important attributes in said advanced panel.

11. The method according to claim 6, wherein said generating at least one second important attribute step comprises:

generating at least one second important attribute, wherein said generated at least one second important attributes together with the said chosen at least one first important attribute best discriminate between the different values of the label attribute.

12. The method according to claim 6, wherein said generating purity step comprises:

measuring said purity by a number from 0 to 100, with 0 indicating lowest purity and 100 indicating highest purity.

13. A method for determining the most important attributes from a set of records in a database, said most important attributes discriminate different values of a chosen label attribute, the method comprising the steps of:

(a) receiving a set of records having a total of n attributes;

(b) receiving a parameter k, said parameter k indicates number of important variables desired;

(c) selecting a first set of attributes S;

(d) discretizing non-categorical attributes in S;

(e) discretizing non-categorical attributes not in S;

(f) computing separability criterion for each attribute not in S conditioned on first set of attributes S;

(g) adding attribute A to S, A being the attribute with the highest separability criterion; and

(h) if the number of attributes in S is less than k input attributes, returning to step (e),

else, computing separability criteria for all attributes not in S.

14. A system for determining important attributes for discriminating between different values of a label attribute, comprising:

means for receiving a set of records, each record having a plurality of attributes;

means for permitting a user to choose the label attribute;

means for permitting a user to choose at least one first important attribute that is considered important;

means for generating at least one second important attribute, said generated at least one second important attribute together with the said chosen at least one first important attribute discriminate better than at least one of the other attributes between different values of the label attribute;

means for generating non-cumulative purity of each of said chosen at least one first attribute and each of said generated at least one second important attributes, said non-cumulative purity indicating how well each first and second important attribute individually discriminates between different values of the label attribute; and

means for generating cumulative purity of each of said chosen at least one first important attribute and each of said generated at least one second important attribute, said cumulative purity indicates how well a respective important attribute in combination with all other first and second important attributes discriminates between different values of the label attribute.

15. The system according to claim 14, wherein said at least one first important attribute is empty.

16. The system according to claim 14, wherein said means for permitting a user to choose the label attribute further includes a graphical user interface, wherein said graphical user interface comprises:

means for permitting a user to select a simple mode.

17. The system according to claim 14, wherein said means for permitting a user to choose the label attribute further includes a graphical user interface, wherein said graphical user interface comprises:

means for permitting a user to select an advanced mode;

means for displaying a list of important attributes;

means for permitting a user to select important attributes;

means for permitting a user to select the number of important attributes to generate; and

means for permitting a user to select whether to compute improved purity for left columns and cumulative purity for right columns.

18. The system according to claim 14, wherein said means for generating at least one second important attribute comprises:

means for generating at least one second important attribute, wherein said generated at least one second important attributes together with the said chosen at least one first important attribute best discriminate between the different values of the label attribute.

19. A system for determining important attributes for discriminating between different values of a label attribute, comprising:

means for receiving a set of records, each record having a plurality of attributes;

means for permitting a user to choose the label attribute;

means for permitting a user to choose at least one first important attribute that is considered important;

means for generating at least one second important attribute, wherein each generated at least one second important attribute together with the said chosen at least one first important attribute discriminate better than at least one of the other attributes between the different values of the label attribute;

means for generating purity for said generated at least one second important attribute, said purity indicating how well each generated at least one second important attribute discriminates different values of the chosen label attribute; and

means for generating rank of each said generated at least one second important attribute based on its purity.

20. The system according to claim 19, wherein said chosen at least one first important attribute is empty.

21. The system according to claim 19, wherein said means for permitting a user to choose the label attribute further includes a graphical user interface, wherein said graphical user interface comprises:

means for permitting a user to select a simple mode.

22. The system according to claim 19, wherein said means for permitting a user to choose the label attribute further includes a graphical user interface, wherein said graphical user interface comprises:

means for permitting a user to select an advanced mode;

means for displaying a list of important attributes;

means for permitting a user to select important attributes;

means for permitting a user to select the number of important attributes to generate; and

means for permitting a user to select whether to compute improved purity for left columns and cumulative purity for right columns.

23. The system according to claim 19, wherein said means for generating at least one second important attribute comprises:

means for generating at least one second important attribute, wherein said generated at least one second important attributes together with the said chosen at least one first important attribute best discriminate between the different values of the label attribute.

24. The system according to claim 19, wherein said means for generating purity comprises:

means for measuring said purity by a number from 0 to 100, with 0 indicating lowest purity and 100 indicating highest purity.

25. A system for determining the most important attributes from a set of records in a database, said most important attributes discriminate different values of a chosen label attribute, comprising:

(a) means for receiving a set of records having a total of n attributes;

(b) means for receiving a parameter k, said parameter k indicates number of important variables desired;

(c) means for selecting a first set of attributes S;

(d) means for discretizing non-categorical attributes in S;

(e) means for discretizing non-categorical attributes not in S;

(f) means for computing separability criterion for each attribute not in S conditioned on first set of attributes S;

(g) means for adding attribute A to S, A being the attribute with the highest separability criterion;

(h) means for returning to step (e), if the number of attributes in S is less than k input attributes; and

(g) means for computing separability criteria for all attributes not in S.

26. A computer program product for determining important attributes for discriminating between different values of a label attribute, comprising:

means for receiving a set of records, each record having a plurality of attributes;

means for permitting a user to choose the label attribute;

means for permitting a user to choose at least one first important attribute that is considered important;

means for generating at least one second important attribute, said generated at least one second important attribute together with the said chosen at least one first important attribute discriminate better than at least one of the other attributes between different values of the label attribute;

means for generating non-cumulative purity of each of said chosen at least one first attribute and each of said generated at least one second important attributes, said non-cumulative purity indicating how well each first and second important attribute individually discriminates between different values of the label attribute; and

means for generating cumulative purity of each of said chosen at least one first important attribute and each of said generated at least one second important attribute, said cumulative purity indicates how well a respective important attribute in combination with all other first and second important attributes discriminates between different values of the label attribute.

27. The computer program product according to claim 26, wherein said chosen at least one first important attribute is empty.

28. The computer program product according to claim 26, wherein said means for permitting a user to choose the label attribute further includes a graphical user interface, wherein said graphical user interface comprises:

means for permitting a user to select a simple mode.

29. The computer program product according to claim 26, wherein said means for permitting a user to choose the label attribute further includes a graphical user interface, wherein said graphical user interface comprises:

means for permitting a user to select an advanced mode;

means for displaying a list of important attributes;

means for permitting a user to select important attributes;

means for permitting a user to select the number of important attributes to generate; and

means for permitting a user to select whether to compute improved purity for left columns and cumulative purity for right columns.

30. The computer program product according to claim 26, wherein said means for generating at least one second important attribute comprises:

means for generating at least one second important attribute, wherein said generated at least one second important attributes together with the said chosen at least one first important attribute best discriminate between the different values of the label attribute.