Creating ensembles of decision trees through sampling

• US 6,938,049 B2
• Filed: 06/11/2002
• Issued: 08/30/2005
• Est. Priority Date: 06/11/2002
• Status: Expired due to Fees

• Current Assignee: Lawrence Livermore National Security LLC (Government of the United States of America)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Cantu-Paz, Erick, Kamath, Chandrika
• Primary Examiner(s): Amsbury, Wayne
• Application Number:
  US10/167,892
• Publication Number:
  US 20030229630A1
• Time in Patent Office: 1,176 Days
• Field of Search: 707/102, 707/6, 706/14, 705/7
• US Class Current: 1/1
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A system for decision tree ensembles that includes a module to read the data, a module to sort the data, a module to evaluate a potential split of the data according to some criterion using a random sample of the data, a module to split the data, and a module to combine multiple decision trees in ensembles. The decision tree method is based on statistical sampling techniques and includes the steps of reading the data; sorting the data; evaluating a potential split according to some criterion using a random sample of the data, splitting the data, and combining multiple decision trees in ensembles.

Claims

1. A decision tree system, comprising:

a module to read the data and use the data to create multiple decision trees having nodes,

a module to sort the data,

a module to evaluate a potential split of the data according to some criterion, using a random sample of the data at said nodes,

a module to split the data, and

a module to combine said multiple decision trees in ensembles.

2. The decision tree system of claim 1 including a file and a main memory, wherein said module to read the data reads the data from said file to said main memory.

3. The decision tree system of claim 1 wherein the said module to sort the data, sorts it N times for each of the N trees in the ensemble.

4. The decision tree system of claim 1 wherein the said module to sort the data, sorts it once for the N trees in the ensemble.

5. The decision tree system of claim 1 wherein said module to evaluate a potential split of the data according to some criterion using a random sample of the data, with said criterion including attributes, uses a different sample for each attribute.

6. The decision tree system of claim 5 wherein said random sample of the data uses instances of the data and said sample is a fixed number of the instances.

7. The decision tree system of claim 5 wherein said random sample of the data uses instances of the data and said sample is a percentage of the instances.

8. The decision tree system of claim 1 wherein said module to evaluate a potential split of the data according to some criterion using a random sample of the data, with said criterion including attributes, uses the same sample for each attribute.

9. The decision tree system of claim 8 wherein said random sample of the data uses instances of the data and said sample is a fixed number of the instances.

10. The decision tree system of claim 8 wherein said random sample of the data uses instances of the data and said sample is a percentage of the instances.

11. The decision tree system of claim 1, wherein the said criterion to evaluate a potential split of the data is the information gain criterion.

12. The decision tree system of claim 1, wherein the said criterion to evaluate a potential split of the data is the gain criterion.

13. The decision tree system of claim 1, wherein the said criterion to evaluate a potential split of the data is the information gain ratio criterion.

14. The decision tree system of claim 1, wherein the said criterion to evaluate a potential split of the data is the Twoing rule.

15. The decision tree system of claim 1, wherein the said module to combine multiple trees in ensembles uses plurality (that is majority) voting.

16. The decision tree system of claim 1, wherein the said module to combine multiple trees in ensembles uses weighted voting, where different weights are given to the output from each tree.

17. A decision tree system, comprising the:

means to read the data and use the data to create multiple decision trees having nodes,

means to sort the data,

means to evaluate a potential split of the data according to some criterion, using a random sample of the data at said nodes,

means to split the data, and the

means to combine said multiple decision trees in ensembles.

18. The decision tree system of claim 17 including a file and a main memory and wherein said means to read the data reads the data from said file to said main memory.

19. The decision tree system of claim 17 wherein the said means to sort the data, sorts it N times for each of the N trees in the ensemble.

20. The decision tree system of claim 17 wherein the said means to sort the data, sorts it once for the N trees in the ensemble.

21. The decision tree system of claim 17 wherein the said means to evaluate a potential split of the data according to some criterion using a random sample of the data, with said criterion including attributes, uses a different sample for each attribute.

22. The decision tree system of claim 21 wherein said random sample of the data uses instances of the data and said sample is a fixed number of the instances.

23. The decision tree system of claim 21 wherein said random sample of the data uses instances of the data and said sample is a percentage of the instances.

24. The decision tree system of claim 17 wherein the said means to evaluate a potential split of the data according to some criterion using a random sample of the data, with said criterion including attributes, uses the same sample for each attribute.

25. The decision tree system of claim 24 wherein said random sample of the data uses instances of the data and said sample is a fixed number of the instances.

26. The decision tree system of claim 24 wherein said random sample of the data uses instances of the data and said sample is a percentage of the instances.

27. The decision tree system of claim 17, wherein the said means to evaluate a potential split of the data is the information gain criterion.

28. The decision tree system of claim 17, wherein the said means to evaluate a potential split of the data is the gini criterion.

29. The decision tree system of claim 17, wherein the said means to evaluate a potential split of the data is the information gain ratio criterion.

30. The decision tree system of claim 17, wherein the said means to evaluate a potential split of the data is the Twoing rule.

31. The decision tree system of claim 17, wherein the said means for combining multiple trees in ensembles uses plurality (that is, majority) voting.

32. The decision tree system of claim 17, wherein the said means for combining multiple trees in ensembles uses weighted voting, where different weights are given to the output from each tree.

33. A decision tree method, comprising the steps of:

reading the data and using the data to create multiple decision trees having nodes,

sorting the data,

evaluating a potential split of the data according to some criterion, using a random sample of the data at said nodes,

splitting the data, and

combining said multiple decision trees in ensembles.

34. The decision tree method of claim 33 including a file and a main memory and wherein the said step to read the data, reads the data from said file to said main memory.

35. The decision tree method of claim 33 wherein the said step to sort the data, sorts it N times for each of the N trees in the ensemble.

36. The decision tree method of claim 33 wherein the said step to sort the data, sorts it once for the N trees in the ensemble.

37. The decision tree method of claim 33 wherein the said step to evaluate a potential split of the data according to some criterion using a random sample of the data, with said criterion including attributes, uses a different sample for each attribute.

38. The decision tree method of claim 37 wherein said random sample of the data uses instances of the data and the said sample is a fixed number of the instances.

39. The decision tree method of claim 37 wherein said random sample of the data uses instances of the data and said sample is a percentage of the instances.

40. The decision tree method of claim 33 wherein the said step to evaluate a potential split of the data according to some criterion using a random sample of the data, with said criterion including attributes, uses the same sample for each attribute.

41. The decision tree method of claim 40 wherein said random sample of the data uses instances of the data and the said sample is a fixed number of the instances.

42. The decision tree method of claim 40 wherein said random sample of the data uses instances of the data and said sample is a percentage of the instances.

43. The decision tree method of claim 33, wherein the said step to evaluate a potential split of the data uses the information gain criterion.

44. The decision tree method of claim 33, wherein the said step to evaluate a potential split of the data uses the gini criterion.

45. The decision tree method of claim 33, wherein the said step to evaluate a potential split of the data uses the information gain ratio criterion.

46. The decision tree method of claim 33, wherein the said step to evaluate a potential split of the data uses the Twoing rule.

47. The decision tree method of claim 33, wherein the said step to combine multiple trees in ensembles uses plurality (that is majority) voting.

48. The decision tree method of claim 33, wherein the said step to combine multiple trees in ensembles uses weighted voting, where different weights are given to the output from each tree.