Detecting interesting decision rules in tree ensembles

• US 10,394,779 B2
• Filed: 09/14/2015
• Issued: 08/27/2019
• Est. Priority Date: 09/14/2015
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Spisic, Damir, Xu, Jing
• Primary Examiner(s): Zhen, Li B.
• Assistant Examiner(s): Pellett, Daniel T
• Application Number:
  US14/852,826
• Publication Number:
  US 20170076213A1
• Time in Patent Office: 1,443 Days
• Field of Search: None
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/20 Ensemble learning
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: G06N 5/046 Forward inferencing; Production systems

Abstract

Mechanisms are provided for detecting interesting decision rules from a set of decision rules in a tree ensemble. Each tree in the tree ensemble is traversed in order to assign each individual data record from a set of data records to an identified leaf node in each tree. Predicted values are determined for the tree ensemble based on predictions provided by each leaf node to which each individual data record is assigned. Interesting sub-indices for decision rules from the set of decision rules are determined and, for each decision rule corresponding to the leaf nodes in the tree ensemble, the sub-indices are combined into interestingness index I_t. The decision rules are ranked corresponding to the leaf nodes in the tree ensemble according to the associated value of the interestingness index I_t and a subset of the decision rules corresponding to the leaf nodes in the tree ensemble are reported.

Claims

1. A computer program product comprising a computer readable storage medium having a computer readable program stored therein, wherein the computer readable program, when executed on a computing device, causes the computing device to:

traverse each tree in a tree ensemble in order to assign each individual data record from a set of data records in an evaluation data set to an identified leaf node in a set of leaf nodes in each tree;

determine predicted values defined by the tree ensemble based on predictions provided by each leaf node to which each individual data record is assigned;

determine interesting sub-indices for decision rules from a set of decision rules corresponding to the leaf nodes in the tree ensemble, wherein the computer readable program to determine the interesting sub-indices for decision rules corresponding to the leaf nodes in the tree ensemble for categorical targets further causes the computing device to;

identify a proportion of data records P(R(t)) determined by the leaf node t where the decision rule is accurate, R(t) being the event that the decision rule based on the node t is accurate;

identify a proportion of data records P(E(t) determined by the leaf node t where the tree ensemble model is accurate, E(t) being an event that the ensemble prediction is accurate based on a data record determined by node t;

determine a proportion P(Ē

(t)) that the ensemble prediction is inaccurate based on a data record determined by node t by defining P(Ē

(t))=1−

P(E(t));

identify a proportion of data records P(E(t)R(t))determined by the node t that are predicted accurately by both the ensemble model and the decision rule;

identify a proportion of data records P(Ē

(t)(R(t)) determined by the node t that are predicted inaccurately by both the ensemble model and the decision rule;

determine a first sub-index of interestingness I₁^t based on prediction agreement between the ensemble model and the decision rule as I₁^t=P(E(t)R(t))+P(Ē

(t)R(t));

determine a second sub-index of interestingness I₂^t on the decision rule accuracy as I₂^t=P(R(t));

and

determine a third sub-index of interestingness I₃^t he ensemble model accuracy as I₃^t=P(E(t));

for each decision rule corresponding to the leaf nodes in the tree ensemble, combine the sub-indices into interestingness index I_t;

rank the decision rules corresponding to the leaf nodes in the tree ensemble according to the associated value of the interestingness index I_t; and

report a subset of the decision rules corresponding to the leaf nodes in the tree ensemble in order to provide a notification of the interesting decision rules in the tree ensemble.

2. The computer program product of claim 1, wherein the subset of the decision rules corresponding to the leaf nodes in the tree ensemble is at least one of a predetermined number of decision rules, a percentage of the total number of decision rules, or decision rules whose interestingness index I_t is above a predetermined threshold.

3. The computer program product of claim 1, wherein each decision rule in the set of decision rules comprise at least one of variables, constraints, and the predicted target value on a path to the corresponding leaf node.

4. The computer program product of claim 1, wherein the computer readable program to determine the interesting sub-indices for decision rules corresponding to the leaf nodes in the tree ensemble are performed for categorical targets or continuous targets.

5. The computer program product of claim 1, wherein the interestingness index I_t is a product of a first sub-index of interestingness I₁^t, a second sub-index of interestingness I₂^t, and a third sub-index of interestingness I₃^t.

6. An apparatus comprising:

a processor; and

a memory coupled to the processor, wherein the memory comprises instructions which, when executed by the processor, cause the processor to;

traverse each tree in a tree ensemble in order to assign each individual data record from a set of data records in an evaluation data set to an identified leaf node in a set of leaf nodes in each tree;

determine predicted values defined by the tree ensemble based on predictions provided by each leaf node to which each individual data record is assigned;

determine interesting sub-indices for decision rules from a set of decision rules corresponding to the leaf nodes in the tree ensemble, wherein the instructions to determine the interesting sub-indices for decision rules corresponding to the leaf nodes in the tree ensemble for categorical targets further cause the processor to;

identify a proportion of data records P(R(t)) determined by the leaf node t where the decision rule is accurate, R(t) being the event that the decision rule based on the node t is accurate;

identify a proportion of data records P(E(t)) determined by the leaf node t where the tree ensemble model is accurate, E(t) being an event that the ensemble prediction is accurate based on a data record determined by node t;

determine a proportion P(Ē

(t)) that the ensemble prediction is inaccurate based on a data record determined by node t by defining P(Ē

(t))=1−

P(E(t));

identify a proportion of data records P(E(t)R(t)) determined by the node t that are predicted accurately by both the ensemble model and the decision rule;

identify a proportion of data records P(Ē

(t)R(t)) determined by the node t that are predicted accurately by both the ensemble model and the decision rule;

determine a first sub-index of interestingness I₁^t based on prediction agreement between the ensemble model and the decision rule as I₁^t=P(E(t)R(t))+P(Ē

(t)R(t));

determine a second sub-index of interesting I₂^t on the decision rule accuracy I₂^t=P(R(t)); and

determine a third sub-index of interestingness I₃^t on the ensemble model accuracy as I₃^t=P(E(t));

for each decision rule corresponding to the leaf nodes in the tree ensemble, combine the sub-indices into interestingness index I_t;

rank the decision rules corresponding to the leaf nodes in the tree ensemble according to the associated value of the interestingness index I_t; and

report a subset of the decision rules corresponding to the leaf nodes in the tree ensemble in order to provide a notification of the interesting decision rules in the tree ensemble.

7. The apparatus of claim 6, wherein the subset of the decision rules corresponding to the leaf nodes in the tree ensemble is at least one of a predetermined number of decision rules, a percentage of the total number of decision rules, or decision rules whose interestingness index I_t is above a predetermined threshold.

8. The apparatus of claim 6, wherein each decision rule in the set of decision rules comprise at least one of variables, constraints, and the predicted target value on a path to the corresponding leaf node.

9. The apparatus of claim 6, wherein the instructions to determine the interesting sub-indices for decision rules corresponding to the leaf nodes in the tree ensemble are performed for categorical targets or continuous targets.

10. The apparatus of claim 6, wherein the interestingness index I_t is a product of a first sub-index of interestingness I₁^t, a second sub-index of interestingness I₂^t,and a third sub-index of interestingness I₃^t.