Methods and apparatus for selecting a data classification model using meta-learning

• US 6,842,751 B1
• Filed: 07/31/2000
• Issued: 01/11/2005
• Est. Priority Date: 07/31/2000
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Rish, Irina, Vilalta, Ricardo
• Primary Examiner(s): Corrielus, Jean M.
• Assistant Examiner(s): Ly, Anh
• Application Number:
  US09/629,086
• Time in Patent Office: 1,625 Days
• Field of Search: 707 1- 10, 707/100, 707/101, 706/16, 706/15, 706/28, 706/30
• US Class Current: 1/1
• CPC Class Codes: G06F 2216/03 Data mining
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A data classification method and apparatus are disclosed for labeling unknown objects. The disclosed data classification system employs a model selection technique that characterizes domains and identifies the degree of match between the domain meta-features and the learning bias of the algorithm under analysis. An improved concept variation meta-feature or an average weighted distance meta-feature, or both, are used to fully discriminate learning performance, as well as conventional meta-features. The “concept variation” meta-feature measures the amount of concept variation or the degree of lack of structure of a concept. The present invention extends conventional notions of concept variation to allow for numeric and categorical features, and estimates the variation of the whole example population through a training sample. The “average weighted distance” meta-feature of the present invention measures the density of the distribution in the training set. While the concept variation meta-feature is high for a training set comprised of only two examples having different class labels, the average weighted distance can distinguish between examples that are too far apart or too close to one other.

Claims

1. A method for classifying data, comprising the steps of:

representing at least one domain dataset using a set of meta-features, wherein said meta-features includes a concept variation meta-feature;

evaluating the performance of a plurality of learning algorithms on said at least one domain dataset;

identifying at least one of said learning algorithms having a performance that exceeds predefined criteria for said at least one domain dataset;

identifying a learning algorithm to classify a new dataset described using a set of meta-features.

2. The method of claim 1, wherein said concept variation meta-feature estimates the variation of the whole example population through a training sample.

3. The method of claim 1, wherein said concept variation meta-feature includes numeric features.

4. The method of claim 1, wherein said concept variation meta-feature includes categorical features.

5. The method of claim 1, wherein said concept variation meta-feature includes boolean features.

6. The method of claim 1, wherein said predefined criteria selects a learning algorithm that performs best for said domain dataset.

7. The method of claim 1, wherein said identifying step further comprises the step of identifying a model in accordance with said identified learning algorithm.

8. The method of claim 1, wherein said concept variation meta-feature utilizes a distance metric to determine the contribution of each example to the amount of concept variation.

9. A method for classifying data, comprising the steps of:

representing at least one domain dataset using a set of meta-features, wherein said meta-features includes an average weighted distance meta-feature that measures the density of the distribution of said at least one domain dataset;

evaluating the performance of a plurality of learning algorithms on said at least one domain dataset;

identifying at least one of said learning algorithms having a performance that exceeds predefined criteria for said at least one domain dataset;

identifying a learning algorithm to classify a new dataset described using a set of meta-features.

10. The method of claim 9, wherein said predefined criteria selects a learning algorithm that performs best for said domain dataset.

11. The method of claim 9, wherein said identifying step further comprises the step of identifying a model in accordance with said identified learning algorithm.

12. A system for classifying data, comprising:

a memory that stores computer-readable code; and

a processor operatively coupled to said memory, said processor configured to implement said computer-readable code, said computer-readable code configured to;

represent at least one domain dataset using a set of meta-features, wherein said meta-features includes a concept variation meta-feature;

evaluate the performance of a plurality of learning algorithms on said at least one domain dataset;

identify at least one of said learning algorithms having a performance that exceeds predefined criteria for said at least one domain dataset;

identify a learning algorithm to classify a new dataset described using a set of meta-features.

13. The system of claim 12, wherein said concept variation meta-feature estimates the variation of the whole example population through a training sample.

14. The system of claim 12, wherein said concept variation meta-feature includes numeric features.

15. The system of claim 12, wherein said concept variation meta-feature includes categorical features.

16. The system of claim 12, wherein said concept variation meta-feature includes boolean features.

17. The system of claim 12, wherein said predefined criteria selects a learning algorithm that performs best for said domain dataset.

18. The system of claim 12, wherein said identifying step further comprises the step of identifying a model in accordance with said identified learning algorithm.

19. The system of claim 12, wherein said concept variation meta-feature utilizes a distance metric to determine the contribution of each example to the amount of concept variation.

20. A system for classifying data, comprising:

a memory that stores computer-readable code; and

a processor operatively coupled to said memory, said processor configured to implement said computer-readable code, said computer-readable code configured to;

represent at least one domain dataset using a set of meta-features, wherein said meta-features includes an average weighted distance meta-feature that measures the density of the distribution of said at least one domain dataset;

evaluate the performance of a plurality of learning algorithms on said at least one domain dataset;

identify at least one of said learning algorithms having a performance that exceeds predefined criteria for said at least one domain dataset;

identify a learning algorithm to classify a new dataset described using a set of meta-features.

21. The system of claim 20, wherein said predefined criteria selects a learning algorithm that performs best for said domain dataset.

22. The system of claim 20, wherein said identifying step further comprises the step of identifying a model in accordance with said identified learning algorithm.

23. An article of manufacture, comprising:

a computer readable medium having computer readable code means embodied thereon, said computer readable program code means comprising;

a step to represent at least one domain dataset using a set of meta-features, wherein said meta-features includes a concept variation meta-feature;

a step to evaluate the performance of a plurality of learning algorithms on said at least one domain dataset;

a step to identify at least one of said learning algorithms having a performance that exceeds predefined criteria for said at least one domain dataset;

a step to identify a learning algorithm to classify a new dataset described using a set of meta-features.

24. An article of manufacture, comprising:

a computer readable medium having computer readable code means embodied thereon, said computer readable program code means comprising;

a step to represent at least one domain dataset using a set of meta-features, wherein said meta-features includes an average weighted distance meta-feature that measures the density of the distribution of said at least one domain dataset;

a step to evaluate the performance of a plurality of learning algorithms on said at least one domain dataset;

a step to identify at least one of said learning algorithms having a performance that exceeds predefined criteria for said at least one domain dataset;

a step to identify a learning algorithm to classify a new dataset described using a set of meta-features.