 |
|
|
|
|
|
 Title: |
US6138115:
Method and system for generating a decision-tree classifier in parallel in a multi-processor system
[ 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: |
2000-10-24
/ 1999-02-05
|
| Application Number: |
US1999000245765
|
| IPC Code: |
Advanced:
G06F 17/30;
Core:
more...
IPC-7:
G06F 17/30;
|
| ECLA Code: |
G06F17/30T4; G06F17/30T1P3;
|
| U.S. Class: |
Current:
707/003;
707/006;
707/007;
707/010;
707/103.R;
707/E17.087;
707/E17.089;
709/215;
709/252;
Original:
707/003;
707/006;
707/007;
707/103;
707/010;
709/215;
709/252;
|
| Field of Search: |
707/003,6,7,103,10
709/215,252
|
| Priority Number: |
|
| Abstract: |
A method and system are disclosed for generating a decision-tree classifier in parallel in a multi-processor system, from a training set of records. The method comprises the steps of: partitioning the records among the processors, each processor generating an attribute list for each attribute, and the processors cooperatively generating a decision tree by repeatedly partitioning the records using the attribute lists. For each node, each processor determines its best split test and, along with other processors, selects the best overall split for the records at that node. Preferably, the gini-index and class histograms are used in determining the best splits. Also, each processor builds a hash table using the attribute list of the split attribute and shares it with other processors. The hash tables are used for splitting the remaining attribute lists. The created tree is then 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: |
Breene, John E.; Lewis, Cheryl
|
| INPADOC Legal Status: |
None
Family Legal Status Report
|
|
|
|
|
|
|
| Parent Case: |
This is a divisional of application Ser. No. 08/641,404 filed on May 1, 1996, U.S. Pat. No. 5,870,735.
|
| Family: |
Show 2 known family members
|
First Claim:
Show all 36 claims |
What is claimed is:
1. A method for generating a decision-tree classifier in parallel in a system having a plurality of processors, 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:
- partitioning the records among the processors of the system;
- generating in parallel by each processor 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; and
- creating a decision tree cooperatively by the processors, the decision tree being formed 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 19 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| Foreign References: |
None
|
| Other Abstract Info: |
DERABS G1999-153241
DERABS G2001-181025
DERABS G2001-181025
|
| Other References: |
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.
D. J. DeWitt, J. F. Naughton and D. A. Schneider, Parallel Sorting on Shared-Nothing Architecture Using Probabilistic Splitting, In Proc. of the 1st Int'l Conf. on Parallel and Distributed Information Systems, pp. 280-291, Dec. 1991.
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.
MPI: A Message-Passing Interface Standard, Message Passing Interface Forum May 5, 1994.
M. Mehta, R. Agrawal & J. Rissanen, SLIQ: Fast Scalable Classifier for Data Mining, In EDBT 96, Avignon, France, Mar. 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.
D. J. DeWitt, S. Ghandeharizadeh, D. A. Schneider, A. Bricker, H. Hsiao & R. Rasmussen, The Gamma Database Machine Project, IEEE Transactions on Knowledge and Data Eng. vol. 2, No. 1, pp. 44-62, Mar. 1990.
No. 08/500,717, filed Jul. 11, 1995, for System and Method for Parallel Mining of Association Rules in Databases, Pat. No. 5,842,200.
No. 08/541,665, filed Oct. 10, 1995, for Method and System for Mining Generalized Sequential Patterns in a Large Database, Pat. No. 5,742,811.
No. 08/564,694, filed Nov. 29, 1995, for Method and System for Generating a Decision-tree Clarifier for Data Records, Pat. No. 5,787,274.
|
|
 Nominate this for the Gallery...
|
|
