Decision Trees: Structure and Algorithms

While Binary Search Trees excel at organizing data for efficient lookups based on inherent order, tree structures in machine learning often serve a different purpose: making predictions. Decision Trees are a fundamental supervised learning algorithm that uses a tree-like structure to model decisions and their possible consequences. Rather than storing data points directly, as Binary Search Trees do, decision trees encode a sequence of questions or tests about the features of data points to arrive at a prediction.

The Structure of a Decision Tree

Imagine a flowchart where each step asks a question about your data. This is essentially what a decision tree represents. It consists of:

• Root Node: The starting point of the tree, representing the entire dataset. It branches out based on the outcome of the first test.
• Internal Nodes (Decision Nodes): Each internal node represents a test on a specific feature. For numerical features, the test is typically a threshold comparison (e.g., feature_X <= 5.0). For categorical features, it might check for equality or membership in a set of categories (e.g., feature_Y == 'category_A').
• Branches (Edges): Each branch emerging from an internal node corresponds to an outcome of the test (e.g., True or False for a threshold split, or specific categories for a categorical split). These branches lead to the next node.
• Leaf Nodes (Terminal Nodes): These nodes represent the final outcome or prediction. In classification tasks, a leaf node typically holds the majority class of the training samples that reached it. In regression tasks, it usually holds the average target value of the samples.

A new data point is classified or predicted by starting at the root node and traversing down the tree according to the outcomes of the tests at each internal node based on the data point's feature values, until a leaf node is reached.

A simple decision tree for predicting whether to play tennis based on weather conditions. Internal nodes test features, branches represent outcomes, and leaf nodes give the prediction.

Building Decision Trees: Recursive Partitioning

Decision trees are typically built using a recursive algorithm that aims to partition the data into subsets that are as "pure" as possible with respect to the target variable. The core idea is to repeatedly select the best feature and split point (threshold or category) that maximally separates the classes or reduces variance in the target value.

Common algorithms like CART (Classification and Regression Trees) and ID3 (Iterative Dichotomiser 3) implement this recursive partitioning. The process involves:

1. Starting with the entire dataset at the root node.

2. Evaluating Splits: For each feature, evaluate all possible split points. For numerical features, this often involves sorting the unique values and testing thresholds between them. For categorical features, different groupings of categories can be tested.

3. Selecting the Best Split: Choose the feature and split point that results in the greatest "information gain" or the largest reduction in "impurity". Impurity measures quantify how mixed the target values are within a node.

   • Gini Impurity: Commonly used in CART. For a node with $C$ classes, where $p_i$ is the fraction of samples belonging to class $i$, the Gini impurity is: $$Gini = 1 - \sum_{i=1}^{C} p_i^2$$ A Gini score of 0 indicates perfect purity (all samples belong to one class), while a maximum score (approaching 0.5 for two classes, higher for more classes) indicates maximum impurity (classes are evenly mixed).
   • Entropy: Often used in ID3 and C4.5. It measures the level of disorder or uncertainty in a node: $$Entropy = - \sum_{i=1}^{C} p_i \log_2(p_i)$$ Where $p_i$ is the fraction of samples of class $i$. Entropy is 0 for a pure node and maximum when classes are uniformly distributed. By convention, $0 \log_2 0 = 0$.

   Information Gain is calculated as the difference between the impurity of the parent node and the weighted average impurity of the child nodes resulting from a split:

   $$InformationGain = Impurity_{parent} - \sum_{j \in children} \frac{N_j}{N} Impurity_{child_j}$$

   Where $N$ is the total number of samples at the parent node, and $N_j$ is the number of samples in child node $j$. The split maximizing this gain is chosen. For regression trees, variance reduction is often used instead of impurity measures.

4. Creating Child Nodes: Split the dataset based on the chosen feature and threshold, creating new child nodes.

5. Recursion: Repeat steps 2-4 for each newly created child node.

6. Stopping Criteria: The recursion stops for a branch when a predefined condition is met:

   • The node is pure (all samples belong to the same class or have very similar target values).
   • A maximum tree depth is reached.
   • The number of samples in a node falls below a minimum threshold.
   • No split can be found that significantly improves impurity. The node then becomes a leaf node.

Connecting Structure to Prediction

The tree structure directly encodes the learned decision logic. Traversing the tree mirrors the process of applying a series of conditional checks based on feature values. This hierarchical partitioning allows decision trees to approximate complex, non-linear decision boundaries in the feature space.

While simple and interpretable, individual decision trees can easily overfit the training data, capturing noise rather than the underlying signal. They can also be unstable, meaning small changes in the training data can lead to significantly different tree structures. These limitations are often addressed by using ensemble methods like Random Forests and Gradient Boosted Trees (discussed in the next section), which combine multiple decision trees to improve robustness and predictive performance. Understanding the fundamental structure and construction algorithm of a single decision tree is essential before exploring these more advanced ensemble techniques.