Method for apparatus for efficient mining of classification models from databases

• US 6,212,526 B1
• Filed: 12/02/1997
• Issued: 04/03/2001
• Est. Priority Date: 12/02/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chaudhuri, Surajit, Fayyad, Usama
• Primary Examiner(s): HO, RUAY L
• Application Number:
  US08/982,760
• Time in Patent Office: 1,218 Days
• Field of Search: 707/1-10, 707/100-104, 707/200-206, 711/100
• US Class Current: 1/1
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Method and apparatus for the construction of a classification model (for example a decision tree) from data in a large database. The database is stored in the form of data records on a storage medium for access by a computer. The computer executes a software component for building a classification model from the data in the database. The classification building component has a scheduler that directs the computer to sequentially access all records in the database one or more times as required for extracting the necessary sufficient statistics to construct the classification model. The method optimizes the construction of the classifier from the database by minimizing the number of database scans and making as much use of the computer'"'"'s fast main memory (RAM) as possible. The method prescribes three different modes for scanning data and includes a scheduler component that decides which of these modes to employ and on what parts of the database. During the generation of a classification model from the database, the number of active data records is reduced on subsequent scans. As the number of records that must be accessed to construct the classifier is reduced, the scheduler switches from sequential access of all records in the database to indexed access of a subset of records within the database to complete the building of the classifier. As record subset sizes decrease to the point where a subset now fits in the computer'"'"'s RAM, the scheduler ultimately switches to loading the data subset and performing all subsequent processing in-memory.

Claims

1. A method of building a data classifier from data stored on a storage medium using a computer having a rapid access memory comprising the steps of:

a) storing a database of data records on a storage medium;

b) sequentially scanning records in the database one or more times to build a classifier based on data contained within the data records;

c) subsequent to at least one sequential scan of the records in the database, splitting the data records into nodes representing data record subsets for classification wherein the choice of data splitting is based on sufficient statistics extracted from the one sequential scan;

d) prior to additional sequential scans of the records in the database, scheduling records of one or more identified nodes for indexed access from the storage medium; and

e) during a next sequential scan of the records creating the index for accessing the records of said identified nodes from the storage medium for further classification of records in the identified nodes.

2. The method of claim 1 wherein each sequential scan of the database evaluates a new set of nodes different from a previous set of nodes wherein the new set of nodes is based upon a splitting of the records in the database.

3. The method of claim 1 including the step of comparing a specified portion of the computer'"'"'s rapid access memory with the amount of rapid access memory needed to load records from a specified node into the computer'"'"'s rapid access memory for in-memory classification of the records within said specified node.

4. The method of claim 1 wherein the specified nodes are scheduled for indexed access of records from the storage medium by gathering of keys for the records within the specified nodes.

5. The method of claim 1 wherein prior to a sequential scan of the records in the database specified nodes are scheduled for loading into the rapid access memory to enable in-memory classification.

6. The method of claim 1 wherein the specified nodes are scheduled based upon the size of rapid access memory available for storing a sufficient statistics for each node that is evaluated during the sequential scan of the database.

7. The method of claim 1 wherein the database is classified into nodes of data records wherein each node contains a subset of the records in the entire database of records and wherein each sequential scan of the database identifies records of certain nodes for either in memory evaluation or indexed access of the records belonging to said certain nodes.

8. A method of evaluating a database stored on a storage medium using a computer having a rapid access memory comprising the steps of:

a) storing a database of records having multiple attributes or fields per record on a storage medium;

b) sequentially scanning records in the database a first time to obtain sufficient statistics based on the contents of the records;

said sufficient statistics determined by counting the occurrences of one or more classifier fields for attributes and attribute values;

c) using the results of the count of said occurrences to partly define a classifier model of the database for use in predicting the one or more classifier field; and

d) continuing to build the classifier model by again sequentially scanning data records in the database and either i) bringing a subset of records from the database into the rapid access memory for using in further building of the classifier model or ii) building an index into the database for retrieval of data records from the database during the further building of the classifier model.

9. The method of claim 8 wherein the results of the statistical count are used to identify subsets of data in the database that are brought into the rapid access memory or for whom the index into the database is created.