Decision tree data structure for use in case-based reasoning

• US 6,704,719 B1
• Filed: 09/27/2000
• Issued: 03/09/2004
• Est. Priority Date: 09/27/2000
• Status: Expired due to Term

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: NCR Corporation (NCR Voyix Corporation)
• Inventors: Ericson, Barbara J.
• Primary Examiner(s): Davis, George B.
• Application Number:
  US09/671,222
• Time in Patent Office: 1,259 Days
• Field of Search: 706/48, 706/53, 705/9
• US Class Current: 706/48
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06Q 10/10 Office automation; Time management

Abstract

An apparatus, computer-readable medium and method for use in association with case-based reasoning and the like utilize a novel decision tree data structure that incorporates a search criterion in association with each test answer to a test criterion defined within a decision node, for use in selecting cases from a search space that match the associated test answer to the test criterion. As such, rather than storing identifiers to the actual cases in a case library, or search space, within a decision tree data structure, search criteria are used to provide the mechanism by which those cases that represent most likely best matches can be dynamically selected.

Claims

1. A computer-implemented method of applying case-based reasoning on an unknown case, the method comprising:

(a) generating a decision tree data structure from a search space within which is stored a plurality of cases said search space being saved within a database;

(b) traversing a path among a plurality of paths defined in said decision tree data structure to identify a subset of cases from said search space suitable for performing nearest-neighbor matching on the unknown case, wherein each path includes a plurality of decision nodes, each decision node including a test criterion defining a plurality of test answers, each test answer having associated therewith a search criterion that selects cases in the search space that match the associated test answer, wherein traversing the path includes, at each decision node in the path;

.

(i) selecting a test answer among the plurality of test answers defined by the test criterion for such decision node based upon an attribute associated with the unknown case; and

(ii) applying the search criterion associated with the selected test answer to the search space to select cases in the search space that match the selected test answer to the test criterion; and

(c) performing nearest-neighbor matching on the identified subset of cases.

2. The method of claim 1, wherein traversing the path further comprises, at each decision node in the path other than the last decision node, traversing to a next decision node in the path that is associated with the;

selected answer to the test criterion.

3. The method of claim 2, wherein traversing the path further comprises generating the subset of cases from those cases in the search space that match the selected test answers for all of the decision nodes traversed in the path.

4. The method of claim 3, wherein applying the search criterion at each decision node comprises applying the search criterion to the entire search space to generate a node-specific subset of cases, and wherein generating the subset of cases includes performing a set intersection on the node-specific subsets of cases generated by all of the decision nodes traversed in the path.

5. The method of claim 3, wherein applying the search criterion at each decision node comprises, for each decision node after the first decision node in the path, applying the associated search criterion to a preceding subset of cases selected by a preceding decision node in the path to generate a current subset of cases for such decision node.

6. The method of claim 5, wherein traversing the path further comprises, at each decision node in the path determining whether the current subset of cases generated for such decision node has less than a predetermined number of cases, wherein performing nearest-neighbor matching occurs on a current subset of cases for a decision node in the path subsequent to a determination in such decision node that the current subset of cases generated for such decision node has less than the predetermined number of cases.

7. The method of claim 1, further comprising:

(a) adding the first unknown case to the search space after performing nearest-neighbor matching; and

(b) performing case-based reasoning on a second unknown case using the decision tree data structure after the first unknown case has been added to the search space and before the decision tree data structure has been modified subsequent to traversing the path in the decision tree data structure for the first unknown case.

8. A computer-implemented method of accessing a search space that includes a plurality of cases, said search space being saved within a database the method comprising:

(a) analyzing a test criterion resident in a decision tree data structure to select a test answer from a plurality of test answers associated with the test criterion;

(b) retrieving a search criterion associated with the selected test answer; and

(c) applying the retrieved search criterion to the search space to select at least one case from the search space that matches the selected test answer to the test criterion.

9. The method of claim 8, further comprising,after applying the first retrieved search criterion to the search space:

(a) analyzing a second test criterion resident in the decision tree data structure and associated with the first selected test answer to select a second test answer from a second plurality of test answers associated with the second test criterion;

(b) retrieving a second search criterion associated with the second selected test answer; and

(c) applying the second retrieved search criterion to the search space to select at least one case from the plurality of cases that matches the second selected test answer to the second test criterion.

10. The method of claim 9, wherein applying the first retrieved search criterion comprises applying the first retrieved search criterion to the entire search space to select a first subset of cases from the search space that match the first selected test answer, wherein applying the second retrieved search criterion comprises applying the second retrieved search criterion to the entire search space to generate a second subset of cases from the search space that match the second selected test answer, the method further comprising performing a set intersection on the first and second subsets of cases to generate a third subset of cases that match both of the first and second selected test answers.

11. The method of claim 9, wherein applying the first retrieved search criterion comprises applying the first retrieved search criterion to the search space to select a first subset of cases from the search space that match the first selected test answer, wherein applying the second retrieved search criterion comprises applying the second retrieved search criterion to the first subset of cases to generate a second subset of cases from the search space that match both of the first and second selected test answers.

12. The method of claim 9, further comprising,after applying the first and second retrieved search criteria to the search space:

(a) identifying a subset of cases that match both of the first and second selected test answers; and

(b) performing nearest-neighbor matching on the identified subset of cases.

13. A computer-implemented method of generating a decision tree data structure for use in accessing a plurality of cases in a search space, said search space being saved within a database the method comprising:

(a) generating a plurality of decision nodes, each decision node including a test criterion that defines a plurality of test answers; and

(b) associating a search criterion with each test answer defined by each test criterion, wherein each search criterion is configured to select at least one case from the search space that matches the associated test answer to the test criterion for which the associated test answer is defined.

14. The method of claim 13, further comprising storing each search criterion within the decision node from the plurality of decision nodes within which is resident the test criterion for which the associated test answer is defined.

15. A computer-readable medium comprising a decision tree data structure for use in accessing a plurality of cases in a search space, said search space being saved within a database, the decision tree data structure comprising:

(a) a test criterion configured to test an attribute associated with at least a portion of the plurality of cases, the test criterion defining a plurality of test answers; and

(b) a plurality of search criteria, each associated with a test answer from the plurality of test answers, and each configured to select at least one case from the search space that matches the associated test answer to the test criterion.

16. The computer-readable medium of claim 15, further comprising a decision node within which the test criterion and plurality of search criteria are logically arranged in the decision tree data structure.

17. The computer-readable medium of claim 16, wherein the decision node comprises:

(a) a question node including an attribute to be tested by the test criterion; and

(b) a plurality of answer nodes accessible via the question node and with which are logically arranged the plurality of search criteria, each answer node including an attribute test associated with a test answer defined by the test criterion.

18. The computer-readable medium of claim 17, further comprising a second decision node including a second test criterion defining a second plurality of test answers, and a second plurality of search criteria, each associated with a test answer from the plurality of test answers.

19. The computer-readable medium of claim 18, wherein a first answer node from the plurality of answer nodes includes a reference to the second decision node.

20. The computer-readable medium of claim 15, wherein the computer-readable medium includes at least one of a transmission medium and a recordable medium.

21. A computer system, comprising:

(a) a memory;

(b) a search space saved within a database;

(c) a decision tree data structure resident in the memory, the decision tree data structure for use in accessing a plurality of cases in a said search space and including a test criterion configured to test an attribute associated with at least a portion of the plurality of cases, the test criterion defining a plurality of test answers, the decision tree data structure further including a plurality of search criteria, each associated with a test answer from the plurality of test answers, and each configured to select at least one case from the search space that matches the associated test answer to the test criterion.

22. The apparatus of claim 21, further comprising:

(a) a processor coupled to the memory; and

(b) a program configured to be executed by the processor to test an unknown case with the decision tree data structure by analyzing the test criterion based upon an attribute of the unknown case to select a test answer from the plurality of test answers, retrieving the search criterion associated with the selected test answer, and applying the retrieved search criterion to the search space to select at least one case from the search space that matches the selected test answer to the test criterion.

23. The apparatus of claim 22, wherein:

(a) the decision tree data structure further comprises a second test criterion defining a second plurality of test answers, and a second plurality of search criteria, each associated with a test answer from the second plurality of test answers, and each configured to select at least one case from the search space that matches the associated test answer to the second test criterion; and

(b) the program is further configured to analyze the second test criterion based upon an attribute of the unknown case to select a second test answer from the second plurality of test answers, retrieve the second search criterion associated with the second selected test answer, and apply the second retrieved search criterion to the search space to select at least one case from the search space that matches the second selected test answer to the second test criterion.

24. The apparatus of claim 23, wherein the program is configured to:

(a) apply the first retrieved search criterion by applying the first retrieved search criterion to the entire search space to select a first subset of cases from the search space that match the first selected test answer;

(b) apply the second retrieved search criterion by applying the second retrieved search criterion to the entire search space to generate a second subset of cases from the search space that match the second selected test answer; and

(c) perform a set intersection on the first and second subsets of cases to generate a third subset of cases that match both of the first and second selected test answers.

25. The apparatus of claim 23, wherein the program is configured to apply the first retrieved search criterion by applying the first retrieved search criterion to the search space to select a first subset of cases from the search space that match the first selected test answer, and to apply the second retrieved search criterion by applying the second retrieved search criterion to the first subset of cases to generate a second subset of cases from the search space that match both of the first and second selected test answers.

26. The apparatus of claim 23, wherein the program is further configured to perform nearest-neighbor matching on the unknown case subsequent to applying the retrieved search criterion to the search space.

27. The apparatus of claim 21, further comprising a program configured to generate the decision tree data structure by generating a plurality of decision nodes, each decision node including a test criterion that defines a plurality of test answers, and associating a search criterion with each test answer defined by each test criterion such that each search criterion is configured to select at least one case from the search space that matches the associated test answer to the test criterion for which the associated test answer is defined.

28. A computer system, comprising:

(a) a memory;

(b) a search space saved within a database;

(c) a decision tree data structure resident in the memory, the decision tree data structure for use in identifying a subset of cases from a said search space suitable for performing nearest-neighbor matching on an unknown case, the decision tree data structure including a plurality of decision nodes defining a plurality of paths in the decision tree data structure, each decision node including a test criterion defining a plurality of test answers, each test answer having associated therewith a search criterion that selects cases in the search space that match the associated test answer.

29. The apparatus of claim 28, further comprising:

(a) a processor coupled to the memory; and

(b) a program configured to be executed by the processor to traverse a path in the decision tree data structure by, at each decision node in the path, selecting a test answer among the plurality of test answers defined by the test criterion for such decision node based upon an attribute associated with the unknown case, and applying the search criterion associated with the selected test answer to the search space to select cases in the search space that match the selected test answer to the test criterion.

30. The apparatus of claim 29, wherein the program is further configured to perform nearest-neighbor matching on the identified subset of cases.

31. The apparatus of claim 30, wherein the program is further configured to add the first unknown case to the search space after performing nearest-neighbor matching,and perform case-based reasoning on a second unknown case using the decision tree data structure after the first unknown case has been added to the search space and before the decision tree data structure has been modified subsequent to traversing the path in the decision tree data structure for the first unknown case.

32. The apparatus of claim 29, wherein the program is further configured to traverse the path by, at each decision node in the path other than a last decision node, traversing to a next decision node in the path that is associated with the selected answer to the test criterion.