Decision Trees

A decision tree is a data structure used in machine learning for both regression and classification. As the name suggests, a decision tree is based on a binary tree structure in computer science, where each node is a decision point that has two child nodes, a left child and a right child. Unlike biological trees, computer scientists imagine that trees grow downward, with the root at the top and the leaves toward the bottom.

A decision tree works by considering a single data point and passing it down from the root of the tree to a leaf node. At each internal node of the tree, a decision is made to pass the current data point to either the left child or the right child based on a feature value compared against a threshold value at that node. Once a data point arrives at a leaf node, it is assigned the label associated with that leaf node. Decision trees can be applied to both regression and classification problems.

Decision trees are fast, interpretable, robust for serving, and support numerical and categorical features with equal ease. They are used directly or within ensemble models such as random forests. Decision trees are widely applied in credit scoring, fraud detection, and customer segmentation.

By the end of this lesson, you'll have a better idea of how to answer the following commonly asked questions:

1. Can we use batches of data to train a decision tree?
2. How do we train a decision tree model if the entire dataset cannot be loaded into memory during the training process?
3. How do we update an existing Decision Tree model with new incremental data?

We'll provide the answers at the end of this lesson.

Overview

Algorithm

Let $f_1, f_2, … f_n$ be the feature names and $c$ (for class) be the label name. Each data point is a row that contains a label value $c^i$ and feature values $x_1^i, x_2^i… x_n^i$. We shall use a generic score function in the description below to capture the fact that the criteria for growing trees differ yet are closely related concepts for regression trees and classification trees.

The training process is as follows:

1. Initialize the hyperparameters for the decision tree - max_depth and min_samples. max_depth is the maximum depth of the decision tree. min_samples is the minimum number of training data samples that must occupy a decision tree node so that the node becomes eligible for further splitting of data, otherwise the node remains a leaf node and no further child nodes are created during training.
2. For each feature $f_p$, sort the data points by their feature values.
3. For each of these features, pick threshold values $t_{k_1}, …, t_{k_p}$ and split the data into a left child and a right child based on the data points under consideration at the current node.
4. Compute the score function reduction between the current node, its left child and right child.
5. The feature and threshold value that achieves the greatest reduction in this score function value will be assigned to the node as the decision feature and decision threshold value
6. Repeat steps 2 to 5 for the left child node and right child node, until the node under consideration has fewer than min_samples or max_depth has been achieved.
7. For the leaf nodes, we assign class labels or prediction values. In the case of classification, the label associated with a leaf node is the majority class label. For regression, the prediction value is the average of the target values among all the training data points that occupy the leaf node.

In the context of decision trees, “serving” refers to the process where the trained decision tree model is used to make predictions or classifications on new, unseen data. During serving:

1. New data inputs are provided to the decision tree model.
2. The input traverses from the root of the decision tree down through internal nodes based on feature values, following the decision rules learned during training.
3. Once the input reaches a leaf node, the prediction or classification associated with that leaf node is returned as the output.

Although decision trees are robust computationally during serving for new data points with missing values or null data, it’s important to note that learned decision trees can vary significantly between training sessions due to the selection of features for data splitting when growing nodes. This instability can be a concern from a training or learning perspective. Therefore, machine learning engineers and data scientists often consider ensembles of trees, such as random forests, as robust models. Random forests aggregate multiple independent decision tree models. The term “random” in random forests signifies that the subsample of data points at each node, along with the features and feature thresholds, are randomly chosen.

During the training of a decision tree, no batching is performed, unless one intends to build an ensemble model like a random forest, which comprises multiple trees. All training data must be utilized during decision tree construction, which can impose size limitations on the tree or training data.

There are several decision tree algorithms, with CART and ID3 being popular ones. They use Gini impurity values for classification instead of entropy, chosen for computational efficiency. Some decision trees have multiple child nodes and are not limited to binary decisions. Certain decision trees allow for decision thresholds that represent linear relationships between two features. These configurations enable inclined decision boundaries, rather than strictly axis-aligned ones.

Computing entropy at node

$$\text{Entropy}(D) = -\sum_{i=1}^k p_i\log_2(p_i)$$

Where

• $k$ is the number of classes
• $p_i$ is the proportion of data points at node D that belong to class i.

Suppose there are two classes, Red and Blue, with 2 instances of Red and 3 instances of Blue at the current node. The entropy calculation for this node would be:

$$\text{Entropy} = -\left(\frac{2}{5} \log_2 \frac{2}{5} + \frac{3}{5} \log_2 \frac{3}{5}\right) \approx 0.97$$

This value indicates relatively high entropy because the node contains a mixed distribution of Red and Blue instances. Entropy is highest when the data is evenly split among all classes, reflecting maximum uncertainty in classification.

Now, assume a data split at a node as shown below:

Computing entropy reduction by the data split

Compute the entropy of parent minus weighted entropy of children = H(node) - H(children) = 0.97 - (3/5)*0.918 - (2/5)*1.0= 0.0199

Computing variance of data at a node

1. Compute the mean for the r data points that arrive at the node. $\mu = \frac{1}{r}\sum_{i=1}^r y_i$ where $y_i$ is the regression label for the $i$th data point that arrives at the node.
2. Compute the variance at the node $D$, $Var(D) = \frac{1}{r}\sum_{i=1}^r(y_i-\mu)^2$

Computing variance reduction

1. Compute the variance at the parent node and its child nodes.
2. Weight the variances of the child nodes by the proportion of data points arriving at each node.

Pseudocode

From the outlined algorithm, we can construct a pseudocode for a decision tree as follows:

Python
class DecisionTreeNode:
	def __init__(self, indices, feature, threshold):
		self.indices = indices[::]
		self.feature_ix = feature
		self.threshold = threshold
		self.label = None

# stitch together a tree during training
def train(X, y, max_depth=10, min_samples=0.1, clf_or_reg):
	# input features, labels, hyperparameters max_depth, min_samples
	# type: classification or regression

	# create multi-index sorted by each feature
	multi_indices = {..}

	# level-wise traversal to create nodes and wire them together
	depth, root = 0, None
	stack = [(range(len(X)), None, 'L')] # root has no parent
	while stack:
		# deep enough already
		if depth == max_depth:
			break
		for _ in range(len(stack)):
			indices, parent, left_right = stack.pop(0)

			# too few samples
			if len(indices) <= min_samples:
				continue
			current, lxs, rxs = compute_node_lx_rx(indices)
			if parent:
				{
				'L': parent.left,
				'R': parent.right,
				}[left_right] = current
			elif not root:
				root = current

			stack.append((lxs, current, 'L'))
			stack.append((rxs, current, 'R'))

		depth += 1
	return root

def compute_node_lx_rx(indices):
	#
	# use multi-index pick the feature and threshold
	# that yields the best reduction in score fn
	#

	# 
	# left_ixs are the data indices that end up in the left child
	# right_ixs end up in the right child
	#
	return DecisionTreeNode(indices, feature, threshold), left_ixs, right_ixs)

def score_fn(clf_or_regr, indices):
	# entropy if classifier
	if clf_or_regr == 'classifier':
		return entropy(indices)

	# variance if regression
	return variance(indices)

def variance(indices):
	mean = sum([y[i] for i in indices])/len(indices)
	return sum([(y[i] - mean)**2 for i in indices])/len(indices)

def weighted_variance(lxs, rxs):
	L, R = len(lxs), len(rxs)
	return L/(L+R) * variance(lxs) + R/(L+R) * variance(rxs)

def entropy(indices):
	class1 = sum([y[i] == 1 for i in indices])
	p1 = class1/len(indices)
	return -p1*log(p1) - (1 - p1)*log (1 - p1)

# evaluate for a datapoint
def predict_single(x, root):
	node = root
	while not node.is_leaf:
		if x[node.feature_ix] <= node.threshold:
				node = node.left
		else:
			node = node.right
	return node.label

# evaluate for batch of data
def predict(X, model):
	return [predict_single(x, model) for x in X]

Evaluation

Decision trees can be used for both classification and regression tasks. Check out our lesson on model evalution to learn more about how to evaluate the performance of this model.

Limitations

• Brittleness: Decision trees are susceptible to changes in training data, which can lead to learning significantly different trees for similar datasets. This inherent brittleness is addressed by using ensemble methods such as random forests or gradient boosted decision trees, which combine multiple trees to improve robustness and predictive performance.
• Computational Complexity: Finding the optimal feature and threshold for each split in a decision tree is an NP-complete problem, which is computationally exhaustive. To mitigate this, heuristics are typically embedded in algorithms. Random forests address this by randomly selecting subsets of features and samples to determine thresholds within each tree, reducing computational demand.
• Overfitting: Decision trees have a tendency to overfit to the training data, capturing noise and specifics of the training set that may not generalize well to new data. Techniques like tree pruning (e.g., limiting the maximum depth of trees, setting minimum samples per leaf) are commonly used to prevent overfitting. These strategies help simplify decision trees and improve their ability to generalize to unseen data.

Employing decision trees

Here are a few prevalent methods and libraries for utilizing decision trees in code:

Using scikit-learn (Python) for Classification:

Python
from sklearn.tree import DecisionTreeClassifier

# create a new classifier
clf = DecisionTreeClassifier()

# labeled dataset
X = [[0, 0], [1, 1]]
y = [0, 1]

# learn
clf = clf.fit(X, y)

# predict for new data
y_pred = clf.predict([[-1,0]])

# plot metrics, AUC-ROC curve etc.

Using scikit-learn (Python) for Regression:

Python
from sklearn.tree import DecisionTreeRegressor

# model
clf = tree.DecisionTreeRegressor()

# dataset
X = [[0, 0], [2, 2]]
y = [0.5, 2.5]

# learn
clf = clf.fit(X, y)

# predict
y_pred = clf.predict([[1, 1]])

# plot eval / test metrics, MSE etc.

Note that due to the uniform API contract supported by sklearn, there is no code difference in the code between classification and regression.

Common questions

Q: Can we use batches of data to train a decision tree?

A: Training a vanilla decision tree requires the entire dataset, or its multi-indices, to be loaded into memory. This ensures effective selection of feature thresholds at each node. Therefore, using batches of training data is not practical for training a single decision tree. However, ensemble methods allow us to train multiple decision trees, each on a subset of the training data. During prediction or serving, the decisions from these individual trees are typically averaged out to provide the final prediction. This approach not only leverages batch-like training for efficiency but also enhances the model’s robustness and predictive accuracy through ensemble averaging.

Q: How do we train a decision tree model if the entire dataset cannot be loaded into memory during the training process?

A: In such cases, we employ ensemble methods where multiple decision trees are trained, each using a subset of the dataset. These individual trees collectively form an ensemble that is used for making predictions. Ensemble methods provide a robust approach to prediction, leveraging the diversity of multiple models to improve accuracy and generalization.

This ensemble approach also enhances efficiency during serving, as each tree can independently and concurrently compute predictions. The final prediction is typically obtained through aggregation, which may involve averaging the predictions or using majority voting, potentially with weighting to emphasize more accurate models within the ensemble.

Q: How do we update an existing Decision Tree model with new incremental data (akin to online training)? This question is for mid to senior candidates

A: Performing incremental updates or online learning directly with a single decision tree is not feasible. In practical scenarios, engineers typically utilize ensembles of decision trees. Each decision tree in the ensemble is weighted based on the number of examples it was trained on.

For updating with new incremental data, the approach involves mini-batching the new data points to train a new decision tree. This new tree’s weight in the ensemble is determined by factors such as the number of samples it has processed and the recency of the data. The newly trained decision tree is then incorporated into the existing ensemble, possibly replacing a previous decision tree to maintain ensemble size and efficiency.

This method enables the adaptation of decision tree models to evolving data streams, facilitating scenarios resembling online training while ensuring the ensemble remains effective and up-to-date.