Decision Tree: powerful algorithm capable of fitting complex datasets

Decision Trees are versatile Machine Learning algorithms that can perform both classification and regression tasks, even multioutput tasks. The goal is to create a model that predicts the value of a target variable by learning simple decision rules inferred from the data features.

---

Some general advantages are:

• Simple to understand and to interpret.
• Requires little data preparation. Other techniques often require data normalisation, dummy variables need to be created and blank values to be removed. Note however that this module does not support missing values.
• The cost of using the tree (i.e., predicting data) is logarithmic in the number of data points used to train the tree.
• Able to handle both numerical and categorical data. However scikit-learn implementation does not support categorical variables for now. Other techniques are usually specialised in analysing datasets that have only one type of variable. See algorithms for more information.
• Able to handle multi-output problems.
• Uses a white box model. If a given situation is observable in a model, the explanation for the condition is easily explained by boolean logic. By contrast, in a black box model (e.g., in an artificial neural network), results may be more difficult to interpret.
• Possible to validate a model using statistical tests. That makes it possible to account for the reliability of the model.
• Performs well even if its assumptions are somewhat violated by the true model from which the data were generated.

---

Some general disadvantages are:

• Decision-tree learners can create over-complex trees that do not generalise the data well. This is called overfitting. Mechanisms such as pruning, setting the minimum number of samples required at a leaf node or setting the maximum depth of the tree are necessary to avoid this problem.
• Decision trees can be unstable because small variations in the data might result in a completely different tree being generated. This problem is mitigated by using decision trees within an ensemble.
• Predictions of decision trees are neither smooth nor continuous, but piecewise constant approximations as seen in the above figure. Therefore, they are not good at extrapolation.
• The problem of learning an optimal decision tree is known to be NP-complete under several aspects of optimality and even for simple concepts. Consequently, practical decision-tree learning algorithms are based on heuristic algorithms such as the greedy algorithm where locally optimal decisions are made at each node. Such algorithms cannot guarantee to return the globally optimal decision tree. This can be mitigated by training multiple trees in an ensemble learner, where the features and samples are randomly sampled with replacement.
• There are concepts that are hard to learn because decision trees do not express them easily, such as XOR, parity or multiplexer problems.
• Decision tree learners create biased trees if some classes dominate. It is therefore recommended to balance the dataset prior to fitting with the decision tree.

---

Decision Tree Classifier using Scikit-Learn

Getting the data

We will be using the famous Iris dataset for this post.

# Getting the data
iris = load_iris()
X = iris['data']
y = iris.target

Defining Decision Tree Classifier

# Basic Decision Tree
tree_clf = DecisionTreeClassifier()
tree_clf.fit(X, y)

# Predicting Classes
predicted_values = tree_clf.predict(X)

---

Parameters for DecisionTreeClassifier

Parameters	Description
criterion	{“gini”, “entropy”}, default=”gini” The function to measure the quality of the split.
splitter	{“best”, “random”}, default=”best” The strategy used to choose the split at each node. Supported strategies are “best” to choose the best split and “random” to choose the best random split.
max_depth	int, default=None The maximum depth of the tree. If None, then nodes are expanded until all leaves are pure or until all leaves contain less than min_samples_split samples.
min_samples_split	int or float, default=2 The minimum number of samples required to split an internal node: – If int, then consider min_samples_split as the minimum number. – If float, then min_samples_split is a fraction and ceil(min_samples_split * n_samples) are the minimum number of samples for each split.
min_samples_leaf	int or float, default=1 The minimum number of samples required to be at a leaf node. A split point at any depth will only be considered if it leaves at least min_samples_leaf training samples in each of the left and right branches. This may have the effect of smoothing the model, especially in regression. – If int, then consider min_samples_leaf as the minimum number. – If float, then min_samples_leaf is a fraction and ceil(min_samples_leaf * n_samples) are the minimum number of samples for each node.
min_weight_fraction_leaf	float, default=0.0 The minimum weighted fraction of the sum total of weights (of all the input samples) required to be at a leaf node. Samples have equal weight when sample_weight is not provided.
max_features	int, float or {“auto”, “sqrt”, “log2”}, default=None The number of features to consider when looking for the best split: – If int, then consider max_features features at each split. – If float, then max_features is a fraction and int(max_features * n_features) features are considered at each split. – If “auto”, then max_features=sqrt(n_features). – If “sqrt”, then max_features=sqrt(n_features). – If “log2”, then max_features=log2(n_features). – If None, then max_features=n_features.
max_leaf_nodes	int, default=None Grow a tree with max_leaf_nodes in best-first fashion. Best nodes are defined as relative reduction in impurity. If None, then unlimited number of leaf nodes.
min_impurity_decrease	float, default=0.0 A node will be split if this split induces a decrease of the impurity greater than or equal to this value.
class_weight	dict, list of dict or “balanced”, default=None Weights associated with classes in the form {class_label: weight}. If None, all classes are supposed to have weight one. For multi-output problems, a list of dicts can be provided in the same order as the columns of y. Note that for multioutput (including multilabel) weights should be defined for each class of every column in its own dict. For example, for four-class multilabel classification weights should be [{0: 1, 1: 1}, {0: 1, 1: 5}, {0: 1, 1: 1}, {0: 1, 1: 1}] instead of [{1:1}, {2:5}, {3:1}, {4:1}]. The “balanced” mode uses the values of y to automatically adjust weights inversely proportional to class frequencies in the input data as n_samples / (n_classes * np.bincount(y)) For multi-output, the weights of each column of y will be multiplied. Note that these weights will be multiplied with sample_weight (passed through the fit method) if sample_weight is specified.
ccp_alplha	non-negative float, default=0.0 Complexity parameter used for Minimal Cost-Complexity Pruning. The subtree with the largest cost complexity that is smaller than ccp_alpha will be chosen. By default, no pruning is performed.

Attributes for DecisionTreeClassifier

Attributes	Description
classes_	ndarray of shape (n_classes,) or list of ndarray The classes labels (single output problem), or a list of arrays of class labels (multi-output problem).
feature_importances_	ndarray of shape (n_features,) Return the feature importances.
max_features_	int The inferred value of max_features.
n_classes_	int or list of int The number of classes (for single output problems), or a list containing the number of classes for each output (for multi-output problems).
n_features_in_	int The number of features seen during fit.
featrue_names_in_	ndarray of shape (n_features_in_,) Names of features seen during the fit. Defined only when X has feature names that are all strings.
n_outputs_	int The number of outputs when fit is performed.
tree_	Tree instance The underlying Tree object.

Tips of practical use:

• Decision trees tend to overfit on data with a large number of features. Getting the right ratio of samples to number of features is important, since a tree with few samples in high dimensional space is very likely to overfit.
• Consider performing dimensionality reduction (PCA, ICA, or Feature selection) beforehand to give your tree a better chance of finding features that are discriminative.
• Understanding the decision tree structure will help in gaining more insights about how the decision tree makes predictions, which is important for understanding the important features in the data.
• Visualise your tree as you are training by using the export function. Use max_depth=3 as an initial tree depth to get a feel for how the tree is fitting to your data, and then increase the depth.
• Remember that the number of samples required to populate the tree doubles for each additional level the tree grows to. Use max_depth to control the size of the tree to prevent overfitting.
• Use min_samples_split or min_samples_leaf to ensure that multiple samples inform every decision in the tree, by controlling which splits will be considered. A very small number will usually mean the tree will overfit, whereas a large number will prevent the tree from learning the data.
  • Try min_samples_leaf=5 as an initial value. If the sample size varies greatly, a float number can be used as percentage in these two parameters. While min_samples_split can create arbitrarily small leaves, min_samples_leaf guarantees that each leaf has a minimum size, avoiding low-variance, over-fit leaf nodes in regression problems.
  • For classification with few classes, min_samples_leaf=1 is often the best choice. Note that min_samples_split considers samples directly and independent of sample_weight, if provided (e.g. a node with m weighted samples is still treated as having exactly m samples). Consider min_weight_fraction_leaf or min_impurity_decrease if accounting for sample weights is required at splits.
• Balance your dataset before training to prevent the tree from being biased toward the classes that are dominant. Class balancing can be done by sampling an equal number of samples from each class, or preferably by normalizing the sum of the sample weights (sample_weight) for each class to the same value. Also note that weight-based pre-pruning criteria, such as min_weight_fraction_leaf, will then be less biased toward dominant classes than criteria that are not aware of the sample weights, like min_samples_leaf.
• If the samples are weighted, it will be easier to optimize the tree structure using weight-based pre-pruning criterion such as min_weight_fraction_leaf, which ensure that leaf nodes contain at least a fraction of the overall sum of the sample weights.
• All decision trees use np.float32 arrays internally. If training data is not in this format, a copy of the dataset will be made.
• If the input matrix X is very sparse, it is recommended to convert to sparse csc_matrix before calling fit and sparse csr_matrix before calling predict. Training time can be orders of magnitude faster for a sparse matrix input comparedto a dense matrix when features have zero values in most of the samples.