System and method for adaptive pruning

• US 8,301,584 B2
• Filed: 12/16/2003
• Issued: 10/30/2012
• Est. Priority Date: 12/16/2003
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Fan, Wei, Wang, Haixun, Yu, Philip S.
• Primary Examiner(s): Le, Miranda
• Application Number:
  US10/737,123
• Publication Number:
  US 20050131873A1
• Time in Patent Office: 3,241 Days
• Field of Search: 707 1- 10, 707100-102, 707/104.1, 707200-201, 707/603, 707/999.002, 706/20, 706/21
• US Class Current: 707/603
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06N 20/20 Ensemble learning
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound

Abstract

Disclosed in a method and structure for searching data in databases using an ensemble of models. First the invention performs training. This training orders models within the ensemble in order of prediction accuracy and joins different numbers of models together to form sub-ensembles. The models are joined together in the sub-ensemble in the order of prediction accuracy. Next in the training process, the invention calculates confidence values of each of the sub-ensembles. The confidence is a measure of how closely results form the sub-ensemble will match results from the ensemble. The size of each of the sub-ensembles is variable depending upon the level of confidence, while, to the contrary, the size of the ensemble is fixed. After the training, the invention can make a prediction. First, the invention selects a sub-ensemble that meets a given level of confidence. As the level of confidence is raised, a sub-ensemble that has more models will be selected and as the level of confidence is lowered, a sub-ensemble that has fewer models will be selected. Finally, the invention applies the selected sub-ensemble, in place of the ensemble, to an example to make a prediction.

Claims

1. A method of searching data in databases using an ensemble of models, said method comprising:

ordering models within said ensemble in order of prediction accuracy, with the most accurate model being first in said order, using a computer;

calculating confidence values of each of said sub-ensembles, using said computer;

selecting a sub-ensemble of said models that meets a given level of confidence, using said computer, wherein models are joined together in said sub-ensemble in said order of prediction accuracy, and wherein as the level of confidence is raised, a sub-ensemble that has more models will be selected in said selecting process, and as the level of confidence is lowered, a sub-ensemble that has fewer models will be selected in said selecting process; and

applying said sub-ensemble, in place of said ensemble, to an example to make a prediction, using said computer.

2. The method in claim 1, wherein said sub-ensemble includes fewer models than said ensemble.

3. The method in claim 1, wherein said confidence is a measure of how closely results from said sub-ensemble will match results from said ensemble.

4. The method in claim 1, wherein, the size of each sub-ensemble is different and has a potentially different level of confidence.

5. The method in claim 1, wherein the size of said ensemble is fixed.

6. A method of searching data in databases using an ensemble of models, said method comprising:

ordering models within said ensemble in order of prediction accuracy, with the most accurate model being first in said order, using a computer;

calculating confidence values of each of said sub-ensembles, using said computer;

selecting a sub-ensemble of said models that meets a given level of confidence, wherein models are joined together in said sub-ensemble in said order of prediction accuracy, such that said sub-ensemble include only the most accurate models, and wherein as the level of confidence is raised, a sub-ensemble that has more models will be selected in said selecting process, and as the level of confidence is lowered, a sub-ensemble that has fewer models will be selected in said selecting process; and

applying said sub-ensemble, in place of said ensemble, to an example to make a prediction, using said computer.

7. The method in claim 6, wherein said sub-ensemble includes fewer models than said ensemble.

8. The method in claim 6, wherein said confidence is a measure of how closely results from said sub-ensemble will match results from said ensemble.

9. The method in claim 6, wherein the size of each sub-ensemble is different and has a potentially different level of confidence.

10. The method in claim 6, wherein the size of said ensemble is fixed.

11. A method of searching data in databases using an ensemble of models, said method comprising:

performing training comprising;

ordering models within said ensemble in order of prediction accuracy, with the most accurate model being first in said order, using a computer;

joining different numbers of models together to form sub-ensembles, wherein models are joined together in said sub-ensemble in said order of prediction accuracy, using said computer;

calculating confidence values of each of said sub-ensembles; and

making a prediction comprising;

selecting a sub-ensemble of said models that meets a given level of confidence, using said computer, wherein as the level of confidence is raised, a sub-ensemble that has more models will be selected in said selecting process, and as the level of confidence is lowered, a sub-ensemble that has fewer models will be selected in said selecting process; and

applying said sub-ensemble, in place of said ensemble, to an example to make a prediction, using said computer.

12. The method in claim 11, wherein said sub-ensemble includes fewer models than said ensemble.

13. The method in claim 11, wherein said confidence is a measure of how closely results from said sub-ensemble will match results from said ensemble.

14. The method in claim 11, wherein the size of each sub-ensemble is different and has a potentially different level of confidence.

15. The method in claim 11, wherein the size of said ensemble is fixed.

16. A non-transitory program storage device readable a computer tangibly embodying a program of instructions executable by said computer for performing a method of searching data in databases using an ensemble of models, said method comprising:

ordering models within said ensemble in order of prediction accuracy, with the most accurate model being first in said order, using a computer;

calculating confidence values of each of said sub-ensembles, using said computer;

selecting a sub-ensemble of said models that meets a given level of confidence, using said computer, wherein models are joined together in said sub-ensemble in said order of prediction accuracy, and wherein as the level of confidence is raised, a sub-ensemble that has more models will be selected in said selecting process, and as the level of confidence is lowered, a sub-ensemble that has fewer models will be selected in said selecting process; and

applying said sub-ensemble, in place of said ensemble, to an example to make a prediction, using said computer.

17. The non-transitory program storage device in claim 16, wherein said sub-ensemble includes fewer models than said ensemble.

18. The non-transitory program storage device in claim 16, wherein said confidence is a measure of how closely results from said sub-ensemble will match results from said ensemble.

19. The non-transitory program storage device in claim 16, wherein the size of each sub-ensemble is different and has a potentially different level of confidence.

20. The non-transitory program storage device in claim 16, wherein the size of said ensemble is fixed.