Constrained tree structure method and system
AssigneeSalford Systems
InventorsDan Steinberg, Scott Cardell
Life of this patent
Estimating the term…
Abstract
The present invention provides a method and system for imposing constraints on the induction of decision trees to control where in the decision tree, and in what order specific attributes may be used as node splitters. The invention is used to force a decision tree to contain a specified attribute in one or more locations, or to require the construction of a decision tree in which nodes split using one group of attributes always appear above or always appear below nodes using another group of attributes. This constrained tree is grown and optionally pruned in the same way that a prior art tree is grown and optionally pruned, subject only to the constraints imposed by the method of the present invention.
Claims20
A method of ordering data in a decision tree, the method comprising the steps of:
- a. identifying training data;
- b. identifying a set-of attributes, the set of attributes comprising:
- a target attribute;
- and
- allowable predictor attributes;
- c. characterizing the set of attributes;
- d. specifying constraints on the decision tree in terms of the characterized set of attributes;
- e. determining which of the allowable predictor attributes can be used in nodes of the decision tree for splitting at a region of the decision tree;
- f. determining the best splitter from the allowable predictor attributes that can be used in a specific node of the decision tree for splitting at the region;
- g. splitting any of the nodes at the region if the any of the nodes are splittable;
- h. incrementing the region of the decision tree by 1;
- and
- i. repeating steps e through h until there are no splittable nodes remaining.
A computer program product comprising a computer useable medium having a computer readable program code embodied in the medium for causing a computer to execute the steps of:
- a. identifying training data;
- b. identifying a set of attributes, the set of attributes comprising:
- a target attribute;
- and
- allowable predictor attributes;
- c. characterizing the set of attributes;
- d. specifying constraints on the decision tree in terms of the characterized set of attributes;
- e. determining which of the allowable predictor attributes can be used in nodes of the decision tree for splitting at regions of the decision tree;
- f. determining the best splitter from the allowable predictor attributes that can be used in a specific node of the decision tree for splitting at the region;
- g. splitting any of the nodes at the region if the any of the nodes are splittable;
- h. incrementing the region of the decision tree by 1;
- and
- i. repeating steps e through h until there are no splittable nodes remaining.
A system for ordering data in a decision tree, the decision tree identifying training data and a set of attributes, characterizing the set of attributes, specifying constraints on the decision tree in terms of the characterized set of attributes, determining which of the set of attributes can be used in nodes for splitting at a region, determining the best splitter from the set of attributes that can be used for splitting at the region, and splitting any of the nodes at the region if the any of the nodes are splittable.
Dependencies are inferred from the claim text.