Developer Guide for Intel® Data Analytics Acceleration Library 2019 Update 1
Given n feature vectors x 1=(x 11, ..., x 1p ), ..., x n =(x n1, ..., x np ) of size p, the vector of responses y=(y 1, ..., y n), the problem is to build a decision tree.
The library provides the decision tree classification algorithm based on split criteria Gini index [Breiman84] and Information gain [Quinlan86], [Mitchell97]. See Classification: Decision tree > Details > Split criteria for more information.
The library also provides the decision tree regression algorithm based on the mean-squared error (MSE) [Breiman84]. See Regression: Decision tree > Details > Split Criterion for details.
The library inducts decision trees with the following types of tests:
For continuous features, the test has a form of f j < constant, where f j is a feature, j ∈ {1, ..., p}.
While enumerating all possible tests for each continuous feature, the constant can be any threshold as midway between sequential values for sorted unique values of given feature f j that reach the node.
For categorical features, the test has a form of f j = constant, where f j is a feature, j ∈ {1, ..., p}.
While enumerating all possible tests for each categorical feature, the constant can be any value of given feature f j that reach the node.
For ordinal features, the test has a form of f j < constant, where f j is a feature, j ∈ {1, ..., p}.
While enumerating all possible tests for each ordinal feature, the constant can be any unique value except for the first one (in the ascending order) of given feature f j that reach the node
Optionally, the decision tree can be post-pruned using given m feature vectors x 1 pruning = (x 1 1 pruning, …, x 1 p pruning), …, x m pruning = (x m 1 pruning, …, x m p pruning) of size p, a vector of class labels y pruning = (y 1 pruning, …, y m pruning) for classification or a vector of responses y pruning = (y 1 pruning, …, y m pruning) for regression. For more details about pruning, see [Quinlan87].
Pruned dataset can be some fraction of original training dataset (e.g. randomly chosen 30% of observations), but in this case those observations must be excluded from the training dataset.
The library uses the following algorithmic framework for the training stage.
The decision tree grows recursively from the root node, which corresponds to the entire training dataset. This process takes into account pre-pruning parameters: maximum tree depth and minimum number of observations in the leaf node . For each feature, each possible test is examined to be the best one according to the given split criterion. The best test is used to perform partition of the feature space into a set of hypercubes, and each hypercube represents appropriate part of the training dataset to accomplish the construction of each node at the next level in the decision tree.
After the decision tree is built, it can optionally be pruned by Reduced Error Pruning (REP) [Quinlan87] to avoid overfitting. REP assumes that there is a separate pruning dataset, each observation in which is used to get prediction by the original (unpruned) tree. For every non-leaf subtree, the change in mispredictions is examined over the pruning dataset that would occur if this subtree was replaced by the best possible leaf:
where
If the new tree gives an equal or fewer mispredictions
(
)
and the subtree contains no subtree with the same property, the subtree is
replaced by the leaf. The process continues until any further replacements
increase mispredictions over the pruning dataset. The final tree is the most
accurate subtree of the original tree with respect to the pruning dataset and
is the smallest tree with that accuracy.
The training procedure contains the following steps:
The library uses the following algorithmic framework for the prediction stage.
Given the decision tree and vectors x 1, …, x r , the problem is to calculate the responses for those vectors.
To solve the problem for each given vector x i , the algorithm examines x i by tests in split nodes to find the leaf node, which contains the prediction response.