entropy

The decision tree algorithm is a supervised learning method that makes predictions by asking a series of simple questions about the features, such as “Is the petal length below 2.45 cm?” Each answer sends an example down one branch of a tree until it reaches a final box, called a leaf, that holds the prediction. A decision tree can classify categories or predict numbers, and people like it because you can read the finished model like a flowchart. This guide explains how decision trees work. You will learn the parts of a tree, how recursive splitting chooses questions, how Gini impurity, entropy, and information gain measure a good split, and how stopping rules and pruning control overfitting. A Python example with real output closes the article. For the broader context, see What Is Supervised Learning? Table of contents The parts of a decision tree How a tree learns: recursive splitting Gini impurity, entropy, and information gain A worked numeric example Stopping criteria Pruning and overfitting Regression trees Python example Advantages and limitations Frequently asked questions Conclusion The parts of a decision tree A decision tree looks like an upside-down tree, with the first question at the top. Four terms describe its parts: Root node: the first question, at the top. It sees the entire training set. Internal node (decision node): any question below the root. Each one splits its examples into two or more groups. Branch: the path that an answer takes, for example “yes” or “no.” Leaf node: an endpoint with no further questions. A leaf holds the prediction, which is a class label for classification or a number for regression. To predict, you start at the root, answer each question using the example’s features, follow the matching branch, and repeat until you land on a leaf. The leaf’s value becomes the prediction. Because every step is a plain question, you can explain any individual prediction by listing the path. How a tree learns: recursive splitting The algorithm builds the tree from the top down using a process called recursive splitting. In simple terms: Start with all training examples in the root node. For every feature, and every possible cutoff value, try splitting the examples into two groups. Score each candidate split using an impurity measure (explained next), and pick the one that separates the classes best. Apply the same procedure again to each of the two new groups, using only the examples in that group. Stop when a stopping rule applies, and turn the node into a leaf. The word “recursive” means the algorithm repeats the same steps on smaller and smaller subsets. The method is also greedy: at every node it picks the split that looks best right now, without planning ahead. That is fast, but it does not guarantee the best possible tree overall. Scikit-learn uses an optimized version of the CART algorithm (Classification and Regression Trees), which builds binary trees. Older algorithms such as ID3 and C4.5 use entropy, and they can create more than two branches for categorical features. Gini impurity, entropy, and information gain A good split produces groups that are as pure as possible, meaning each group mostly holds a single class. Impurity measures put a number on this. Gini impurity Gini impurity measures the chance of labeling a random example wrongly if you label it by sampling from the node’s class mix. For a node where pₖ is the share of class k: Gini = 1 − Σ pₖ² A node that holds only one class has Gini = 0 (perfectly pure). In a two-class problem, a 50/50 mix gives the maximum value, 0.5. Lower is better. Scikit-learn uses Gini by default. Entropy Entropy comes from information theory and measures disorder: Entropy = − Σ pₖ × log₂(pₖ) A pure node has entropy 0. A 50/50 two-class node has entropy 1. Like Gini, lower is better. Information gain Information gain is the drop in impurity that a split produces. You compute the parent node’s impurity, subtract the weighted average impurity of the child nodes (weighted by how many examples each child holds), and the difference is the gain: Information gain = impurity(parent) − Σ (nᶜʰⁱˡᵈ / nᵖᵃʳᵉⁿᵗ) × impurity(child) The algorithm picks the split with the highest gain. The term “information gain” usually refers to entropy, but the same pattern works with Gini, where some people call the result “Gini gain.” In practice, Gini and entropy usually choose the same or very similar splits, and Gini is slightly cheaper to compute. Tuning the depth of the tree usually matters far more than choosing between the two. A worked numeric example Suppose a node holds 10 customers: 6 bought a product and 4 did not. A candidate question, “Is the customer under 30?”, sends 6 customers left and 4 right. The left group has 5 buyers and 1 non-buyer. The right group has 1 buyer and 3 non-buyers. Node Buyers / non-buyers Gini Entropy Parent 6 / 4 0.480 0.971 Left child (6 customers) 5 / 1 0.278 0.650 Right child (4 customers) 1 / 3 0.375 0.811 The weighted Gini of the children is 0.6 × 0.278 + 0.4 × 0.375 ≈ 0.317, so the Gini gain is 0.480 − 0.317 ≈ 0.163. The weighted entropy is 0.6 × 0.650 + 0.4 × 0.811 ≈ 0.715, so the information gain is 0.971 − 0.715 ≈ 0.256. The algorithm would compute the same quantities for every other candidate question and choose the question with the largest gain. Stopping criteria If a tree keeps splitting until every leaf is perfectly pure, it memorizes the training data. Stopping criteria prevent this by telling the algorithm when to stop. Common rules include: Maximum depth (max_depth): limit how many levels the tree can have. Minimum samples to split (min_samples_split): do not split a node that has too few examples. Minimum samples per leaf (min_samples_leaf): require each leaf to contain at least a certain number of examples. Minimum impurity decrease (min_impurity_decrease): refuse splits that improve purity