 |
|
|
|
|
|
 Title: |
US5799311:
Method and system for generating a decision-tree classifier independent of system memory size
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Agrawal, Rakesh; San Jose, CA
Mehta, Manish; San Jose, CA
Shafer, John Christopher; Amherst, MA
|
| Assignee: |
International Business Machines Corporation, Armonk, NY
other patents from INTERNATIONAL BUSINESS MACHINES CORPORATION (280070) (approx. 44,393)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
1998-08-25
/ 1996-05-08
|
| Application Number: |
US1996000646893
|
| IPC Code: |
Advanced:
G06F 17/30;
Core:
more...
IPC-7:
G06F 17/30;
|
| ECLA Code: |
G06F17/30T4; G06F17/30T1P3;
|
| U.S. Class: |
Current:
707/102;
382/168;
707/E17.058;
707/E17.087;
707/E17.089;
711/100;
Original:
707/102;
364/225.3;
364/225.4;
364/282.3;
364/974;
364/DIG.1;
364/DIG.2;
711/100;
382/036;
|
| Field of Search: |
395/613
364/200,225.3,225.4,282.3,974
707/102
711/100
382/036
|
| Priority Number: |
| 1996-05-08 |
US1996000646893 |
|
| Abstract: |
A method and system are disclosed for generating a decision-tree classifier from a training set of records, independent of the system memory size. The method comprises the steps of: generating an attribute list for each attribute of the records, sorting the attribute lists for numeric attributes, and generating a decision tree by repeatedly partitioning the records using the attribute lists. For each node, split points are evaluated to determine the best split test for partitioning the records at the node. Preferably, a gini index and class histograms are used in determining the best splits. The gini index indicates how well a split point separates the records while the class histograms reflect the class distribution of the records at the node. Also, a hash table is built as the attribute list of the split attribute is divided among the child nodes, which is then used for splitting the remaining attribute lists of the node. The created tree is further pruned based on the MDL principle, which encodes the tree and split tests in an MDL-based code, and determines whether to prune and how to prune each node based on the code length of the node.
|
| Attorney, Agent or Firm: |
Tran, Khanh Q. ;
|
| Primary / Asst. Examiners: |
Black, Thomas G.; Corrielus, Jean M.
|
| INPADOC Legal Status: |
Show legal status actions
|
| Family: |
None
|
First Claim:
Show all 51 claims |
We claim:
1. A method for generating a decision-tree classifier from a training set of records, each record having: (i) at least one attribute, each attribute having a value, (ii) a class label of the class to which the record belongs, and (iii) a record ID, the method comprising the steps of:
- generating an attribute list for each attribute of the records, each entry in the attribute lists having the attribute value, class label, and record ID of the record from which the attribute value is obtained;
- sorting the attribute lists for numeric attributes based on attribute values; and
- creating a decision tree by repeatedly partitioning the records using the attribute lists, the resulting decision tree becoming the decision-tree classifier.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 37 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| Foreign References: |
None
|
| Other References: |
R.G.& G. Nagy, "Decision tree design using probabilistic model," IEEE Trans, vol. 30, pp. 191-199, Jan. 1984.
Gini index, L Breiman, J. H. Friedman, R. A. Olshen, & C. Stone, "Classification & Regression Trees", Wadsworth International Group, Belmont, CA, Jan. 1984.
Moura Pires, "Adecision Tree Algorithm with Segmenation", Proceedings IECON 91. International Conference on Industrial Electronics Control, and Instrumentation, vol. 3, pp. 2077-2082, Nov. 1991.
J. R. Quinlan, "Introduction of Decision Trees," (Abstract), Machine Learning 1:86-106, Jan. 1986.
Mehta et al., "A fast scalable classifier for data mining,"In EDBT 96, Avignon, France, Mar. 1996.
R. Agrawal et al., An Interval Classifier for Database Mining Applications, Proceedings of the 18th VLDB Conference Vancouver, British Columbia, Aug. 1992.
R. Agrawal et al., Database Mining: A Performance Perspective, IEEE Transactions on Knowledge and Data Engineering, vol. 5, No. 6, pp. 914-925, Special Issue on Learning and Discovery in Knowledge-Based Databases, Dec. 1993.
(12 pages)
Cited by 35 patents
[ISI abstract]
L. Breiman (Univ. of CA-Berkeley) et al. Classification and Regression Trees (Book) Chapter 2. Introduction to Tree Classification pp. 18-58, Wadsworth International Group, Belmont, CA 1984.
J. Catlett, Megainduction: Machine Learning on Very Large Databases, PhD thesis, Univ. of Sydney, Jun./Dec. 1991.
P. K. Chan et al., Experiments on Multistrategy Learning by Meta-learning. In Proc. Second Intl. Conf. on Info. and Knowledge Mgmt., pp. 314-323, 1993.
U. Fayyad et al., The Attribute Selection Problem in Decision Tree Generation. In 105h Nat'l Conf. on AI AAAI-92, Learning: Inductive 1992.
M. James, Classification Algorithms (book), Chapters 1-3, QA278.65, J281 Wiley-Interscience Pub., 1985.
M. Mehta et al., Mdl-based Decision Tree Pruning. Int'l Conference on Knowledge Discovery in Databases and Data Mining (KDD-95) Montreal, Canada, pp. 216-221, Aug. 1995.
J. R. Quinlan et al., Inferring Decision Trees Using Minimum Description Length Principle, Information and Computation 80, pp. 227-248, 1989. (0890-5401/89 Academic Press, Inc.).
(22 pages)
Cited by 15 patents
Wallace et al., Coding Decision Trees, Machine Learning, 11, pp. 7-22, 1993. (Kluwer Academic Pub., Boston. Mfg. in the Netherlands.).
(16 pages)
Cited by 4 patents
[ISI abstract]
S. M. Weiss et al., Computer Systems that learn, Classification and Prediction Methods from Statistics, Neural Nets, Machine Learning, and Expert Systems, pp. 113-143, 1991. Q325.5, W432, C2, Morgan Kaufmann Pub. Inc., San Mateo, CA.
M. Mehta, R. Agrawal & J. Rissanen, SLIQ: Fast Scalable Classifier for Data Mining, In EDBT 96, Avignon, France, March 1996.
R. P. Lippmann, An Introduction to Computing with Neural Nets, IEEE ASSP Magazine, pp. 4-22, 0740-7467/87/0400, Apr. 1987.
D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Chapter 6, Intro. to Genetics Based Machine Learning, pp. 218-257, (Book), 1989.
U.S. Application No. 08/500,717, filed Jul. 11, 1995, for System and Method for Parallel Mining of Association Rules in Databases.
U.S. Application No. 08/541,665, filed Oct. 10, 1995, for Method and System for Mining Generalized Sequential Patterns in a Large Database.
U.S. Application No. 08/564,694, filed Nov. 29, 1995, for Method and System for Generating a Decision-tree Clarifier for Data Records.
No serial number. Filed May 1, 1996, IBM Doc. No. AM9-96-015, Method and System for Generating a Decision-Tree Classifier in Parallel in a Multi-Processor System.
|
|
 Nominate this for the Gallery...
|
|
