Decision Trees

Decision trees are powerful and widely used machine learning algorithms that are popular for both classification and regression tasks. They’re simple to understand and interpret, making them valuable tools for data analysis and decision-making. Apart from their standalone usage, they often serve as a default choice for a weak learner in ensemble learning. In this lesson, we’ll explore the concept of decision trees, how they work, and implement a basic decision tree from scratch using numpy in Python. We’ll also present its implementation using sklearn.

How do decision trees work?

Decision trees are tree-like structures where each internal node represents a decision based on a specific feature, and each leaf node represents the outcome (class label for classification or predicted value for regression). They work by recursively splitting the dataset into subsets based on the most significant attribute (feature) at each step, with the goal of creating leaf nodes that represent the final predicted class or value.

For example, a decision tree makes predictions by answering a sequence of simple questions like:

• “Is Age ≤ 30?”

• “Is Occupation = Engineer?”

At each step, the data is split based on a feature that best separates the classes. This process continues until the subsets become pure, meaning all the samples in a node belong to the same class (for classification) or have very similar values (for regression). A pure subset tells the tree that no further splitting is needed because the data is already perfectly separated. When this happens, the node becomes a leaf node, which gives the final prediction.

Gini impurity

One of the key concepts in decision trees is the calculation of impurity to determine how heterogeneous (mixed) a dataset is. One common impurity measure is the Gini impurity, which measures the probability of incorrectly classifying a randomly chosen element from the dataset. Lower Gini impurity values indicate purer subsets. The formula for Gini impurity is given below:

$$\begin{align*} G = 1- \sum_{i=1}^{k}{p_i}^2 \end{align*}$$

Here, $G$ is the Gini impurity, $k$ is the number of classes in the dataset, and $p_i$ is the probability of an element in the given dataset belonging to class $i$.

For binary classes its value would range from 0 (perfectly pure) to 0.5 (maximum impurity). For example, in a “pure” scenario where a fruit basket contains only apples [Apple, Apple, Apple, Apple], the probability of selecting an apple ($p_1$) is $4/4 = 1.0$, while the probability of selecting an orange ($p_2$) is $0/4 = 0$. Plugging these values into the Gini formula, we calculate $1 - (1.0^2 + 0^2)$, resulting in a Gini Impurity of 0. On the other hand, in a “mixed” scenario where the basket contains two apples and two oranges [Apple, Apple, Orange, Orange], the probability of selecting an apple ($p_1$) is $2/4 = 0.5$ and the probability of selecting an orange ($p_2$) is $2/4 = 0.5$. By applying the Gini formula, $1 - (0.5^2 + 0.5^2)$, we arrive at a Gini Impurity of 0.5 which is the maximum possible impurity for a two-class system, indicating that the node is a complete “toss-up” with no ...