Method of performing data mining tasks for generating decision tree and apparatus therefor

• US 6,662,189 B2
• Filed: 03/13/2001
• Issued: 12/09/2003
• Est. Priority Date: 03/31/2000
• Status: Expired due to Fees

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Sakai, Hiroshi, Kubota, Kazuto, Oyanagi, Shigeru
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US09/803,931
• Publication Number:
  US 20010051934A1
• Time in Patent Office: 1,001 Days
• Field of Search: 707/102, 707/6, 707/100, 707/101, 707/103.R, 707/104.1, 706/45, 706/20, 345/440
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 2216/03 Data mining
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• 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
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A method of performing data mining tasks using a decision tree comprising, when insertion data is input, applying the insertion data to a decision tree created by a data set before the data is inserted in the decision tree, and dividing a leaf node corresponding to the insertion data from the decision tree in accordance with the value of insertion data.

Claims

1. A computer implemented method of modifying a decision tree already created by data mining, comprising:

applying insertion data to the already created decision tree, when the insertion data is newly input; and

dividing a leaf node corresponding to the insertion data from the already created decision tree to modify the already created decision tree in accordance with the insertion data.

2. A method according to claim 1, wherein the dividing step includes searching for the leaf node corresponding to the insertion data and dividing the leaf node in accordance with relation between the insertion data and the leaf node.

3. A method according to claim 2, wherein the dividing step includes dividing the leaf node after the leaf nodes corresponding to all insertion data are searched.

4. A computer implemented method of modifying a decision tree already created by data mining, comprising:

applying deletion data to the already created decision tree, when the deletion data is newly input; and

merging a given node connected to a leaf node corresponding to the deletion data to another leaf node connected to the given node to modify the already created decision tree in accordance with the deletion data.

5. A method according to claim 4, wherein the merging step includes searching for the leaf node corresponding to the deletion data, and performing the merging in accordance with contents of a record set corresponding to the deletion data when the leaf node is searched.

6. A method according to claim 5, wherein the merging step includes merging the leaf nodes after leaf nodes corresponding to all deletion data are searched.

7. A computer implemented method of modifying a decision tree already created by data mining, comprising:

applying insertion data or deletion data to the already created decision tree, when the insertion data or deletion data is newly input;

recalculating an evaluation value by division about a passing node through which the data passes; and

reconstructing a partial tree below the passing node to modify the already created decision tree, when the evaluation value obtained in the recalculating step satisfies a specific condition.

8. A computer implemented decision tree modification apparatus for modifying a decision tree already created by data mining, comprising:

an application unit configured to, when insertion data is newly input, apply the insertion data to the already created decision tree; and

a modification unit configured to divide a leaf node corresponding to the insertion data in accordance with the application result to modify the already created decision tree.

9. An apparatus according to claim 8, which includes a modification data list which stores the application result generated by the application unit and wherein the modification unit modifies the already created decision tree based on the application result read out from the modification data list.

10. An apparatus according to claim 9, wherein when the insertion data is input to a database, the application unit applies the insertion data to the already created decision tree, searches for a leaf node corresponding to the insertion data and stores, in the modification data list, the number used for identifying the node, the insertion data and a flag indicating insertion, and the modification unit modifies the already created decision tree as referring to the modification data list.

11. An apparatus according to claim 9, wherein the modification unit divides the leaf node after leaf nodes corresponding to all insertion data are searched.

12. A computer implemented decision tree modification apparatus for modifying a decision tree already created by data mining, comprising:

an application unit configured to, when deletion data is input, apply the deletion data to the decision tree already created; and

a modification unit configured to merge a given node connected to a leaf node of the decision tree already created, the leaf node corresponding to the deletion data, to another node connected to the given node to modify the already created decision tree.

13. An apparatus according to claim 12, which includes a modification data list which stores the application result generated by the application unit and wherein the modification unit modifies the already created decision tree based on the application result read out from the modification data list.

14. An apparatus according to claim 13, wherein the modification unit searches for the leaf node corresponding to the deletion data, and performs the merging in accordance with contents of a record set corresponding to the deletion data when the leaf node is searched.

15. An apparatus according to claim 14, wherein the modification unit merges leaf nodes after the leaf nodes corresponding to all deletion data are searched.

16. An apparatus according to claim 13, wherein the application unit applies the deletion data to a root node of the already created decision tree to search for the leaf node corresponding to the deletion data and stores the number used for identifying the leaf node, the deletion data and a flag indicating the deletion data in the modification data list.

17. A computer implemented decision tree modification apparatus for modifying a decision tree already generated by data mining, comprising:

an application unit configured to, when insertion data or deletion data is input, apply the insertion data or deletion data to the decision tree already created, recalculate an evaluation value by division about a passing node through which the data passes, and generate the recalculated evaluation value; and

a modification unit configured to reconstruct a partial tree below the passing node when the evaluation value satisfies a specific condition.

18. An apparatus according to claim 17, which further comprises a modification data list configured to store the application result generated by the application unit, and wherein the modification unit modifies the already created decision tree on the basis of the application result read out from the modification data list.