Work Files Saved Searches
   My Account                                                  Search:   Quick/Number   Boolean   Advanced   Derwent    Help   


 The Delphion Integrated View

  Buy Now:   Buy PDF- 19pp  PDF  |   File History  |   Other choices   
  Tools:  Citation Link  |  Add to Work File:    
  View:  Expand Details   |  INPADOC   |  Jump to: 
  Go to:  Derwent  
 Email this to a friend  Email this to a friend 
       
Title: US5870735: Method and system for generating a decision-tree classifier in parallel in a multi-processor system
[ Derwent Title ]


Country: US United States of America

View Images High
Resolution

 Low
 Resolution

 
19 pages

 
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: 1999-02-09 / 1996-05-01

Application Number: US1996000641404

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/E17.087; 707/E17.089;
Original: 707/003; 707/006; 707/007; 707/103;

Field of Search: 707/003,7,6,103

Priority Number:
1996-05-01  US1996000641404

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: Amsbury, Wayne; Lewis, Cheryl

INPADOC Legal Status: Show legal status actions          Buy Now: Family Legal Status Report

Family: Show 2 known family members

First Claim:
Show all 18 claims
What is claimed is:     1. A computer program product for use with a computer system for directing the system to generate a decision-tree classifier in parallel from a training set of records, the system having a plurality of processors, 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 computer program product comprising:
  • a computer readable medium;
  • means, provided on the computer-readable medium, for directing the system to partition the records among the processors of the system;
  • means, provided on the computer-readable medium, for directing each processor to generate in parallel 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
  • means, provided on the computer-readable medium, for directing the processors to cooperatively create a decision tree, 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 26 U.S. patent(s) that reference this one

       
U.S. References: Go to Result Set: All U.S. references   |  Forward references (26)   |   Backward references (0)   |   Citation Link

       
Foreign References: None

Other Abstract Info: DERABS G1999-153241 DERABS G1999-153241

Other References:
  • R. Agrawal, T. Imielinski, & A. Swami, "Database Mining: A Performance Perspective", IEEE Transactions On Knowledge And Data Engineering, vol. 5, No. 6, Dec. 1993.
  • S. M. Weiss & C. A. Kukikowski, "Computer Systems That Learn", pp. 113-143, Kaufmann Pub. Inc., 1991.
  • 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, Jan. 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, Jan. 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 Jan. 1992.
  • M. James, Classification Algorithms (book), Chapters 1-3, QA278.65, J281 Wiley-Interscience Pub., Jan. 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, Jan. 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, Jan. 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, Jan. 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), Jan. 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.
  • No. 08/541,665, filed Oct. 10, 1995, for Method and System for Mining Generalized Sequential Patterns in a Large Database.
  • No. 08/564,694, filed Nov. 29, 1995, for Method and System for Generating a Decision-tree Clarifier for Data Records.


  • Inquire Regarding Licensing

    Powered by Verity


    Plaques from Patent Awards      Gallery of Obscure PatentsNominate this for the Gallery...

    Thomson Reuters Copyright © 1997-2010 Thomson Reuters 
    Subscriptions  |  Web Seminars  |  Privacy  |  Terms & Conditions  |  Site Map  |  Contact Us  |  Help