Đại học Kinh tế Quốc dân – National Economics UniversityMICRO4ASIA
🏆 Arena
Sign inSign up
MICRO4ASIAThe six micro-credentials

Courses are delivered on the Limio learning platform. Limio

← Fundamental of Machine Learning

You are viewing a public preview

Sign in to save your progress, do assignments, join discussions and get feedback.

Sign in
Module 2: Core Machine Learning Algorithms

Decision Trees

Print / Save as PDF

Decision Trees

Structure

ComponentRole
Root nodeThe root node — the first question
Decision nodeA node in the middle that asks about a condition
Leaf nodeThe leaf node — the final conclusion

The biggest strength: you can read the path that leads to each decision. For a rejected loan application, the tree tells you exactly which condition ruled it out — something a bank is required to be able to explain to the customer.

Choosing the Splitting Attribute: Gini impurity

Gini = 1 − Σ (pᵢ)²

Gini measures how "mixed" a branch is:

  • A branch with 4 Yes, 0 No → p(Yes) = 1 → Gini = 1 − 1² = 0 (pure)
  • A branch with 3 Yes, 2 No → Gini = 1 − (0.6² + 0.4²) = 0.48
  • A 50/50 branch → Gini = 1 − (0.5² + 0.5²) = 0.5 (most mixed)

The algorithm tries each attribute, computes the weighted Gini of the child branches, then picks the attribute with the smallest Gini.

In the loan-approval example from the lecture: splitting on age gives Gini = (5/14)(0.48) + (4/14)(0) + (5/14)(0.48) = 0.343.

from sklearn.tree import DecisionTreeClassifier, plot_tree
model = DecisionTreeClassifier(max_depth=4, random_state=100)
model.fit(x_train, y_train)
plot_tree(model, feature_names=x.columns, filled=True)

The Fatal Weakness: Very Prone to Overfitting

A tree with no depth limit keeps splitting until each leaf holds a single sample — that is, it memorizes. Accuracy on train reaches 100%, but on test it is poor.

Ways to control it: max_depth, min_samples_leaf, min_samples_split.

From One Tree to a Whole Forest

Random Forest trains many trees on subsets sampled with replacement (bootstrapping), then takes a majority vote. The random mistakes of individual trees cancel each other out, so the forest is far more stable than a single tree — at the price of losing most of the interpretability.

The Most Common Mistake

Letting the tree grow freely and then being surprised that train accuracy is 100%. That is not a good model, that is a lookup table.

Study notes

By the end of this lesson you can:

  • Describe the three components of a decision tree and read a decision path
  • Explain why trees are valued for explainability, for example in loan decisions
  • Compute Gini impurity and use the weighted Gini to choose a split
  • Recognise overfitting in a tree and control it with max_depth, min_samples_leaf and min_samples_split
  • Explain how Random Forest trades interpretability for stability

Key idea: A decision tree is the easiest model to explain, but left to grow freely it memorises the training data; depth limits, or a whole forest of trees, keep it useful on new data.

Structure and explainability

ComponentRole
Root nodethe first question
Decision nodea node in the middle that asks about a condition
Leaf nodethe final conclusion

The biggest strength of a tree is that you can read the path that leads to each decision. For a rejected loan application, the tree shows exactly which condition ruled it out. Banks are often required to explain such decisions to customers, which makes trees attractive in regulated settings.

Choosing the split with Gini impurity

Gini = 1 - sum of (pi)^2, where pi is the proportion of samples of class i in a branch. It measures how mixed a branch is:

BranchCalculationGini
4 Yes, 0 No1 - 1^20 (pure)
3 Yes, 2 No1 - (0.6^2 + 0.4^2)0.48
50/501 - (0.5^2 + 0.5^2)0.5 (most mixed)

The algorithm tries each attribute, computes the weighted Gini of the child branches (each branch weighted by its share of samples), and picks the attribute with the smallest value. In the loan-approval example from the lecture, splitting on age gives (5/14)(0.48) + (4/14)(0) + (5/14)(0.48) = 0.343.

from sklearn.tree import DecisionTreeClassifier, plot_tree
model = DecisionTreeClassifier(max_depth=4, random_state=100)
model.fit(x_train, y_train)
plot_tree(model, feature_names=x.columns, filled=True)

plot_tree draws the learned tree so you can read every question and leaf.

The fatal weakness: overfitting

A tree with no depth limit keeps splitting until every leaf holds a single sample: it memorises the training data. Train accuracy reaches 100%, but test accuracy is poor, because the tree has learned noise rather than general patterns.

Ways to control it:

HyperparameterEffect
max_depthlimits how many levels of questions the tree may ask
min_samples_leafeach leaf must contain at least this many samples
min_samples_splita node needs at least this many samples before it may split

If a tree scores 100% on train but much less on test, max_depth is usually the first parameter to adjust.

From one tree to a whole forest

Random Forest trains many trees on subsets sampled with replacement (bootstrapping) and takes a majority vote. The random mistakes of individual trees cancel each other out, so the forest is far more stable than one tree. The price: you lose most of the interpretability, because you can no longer read one simple path.

Worked example

A tree reaches 100% accuracy on the training set and 71% on the test set. Diagnose and fix it.

  1. The gap (100% vs 71%) is the classic sign of overfitting: the tree is acting as a lookup table for the training rows.
  2. Limit depth and compare several values on the same split:
from sklearn.tree import DecisionTreeClassifier

for depth in [None, 2, 4, 6]:
    tree = DecisionTreeClassifier(max_depth=depth, random_state=100)
    tree.fit(x_train, y_train)
    print(depth, tree.score(x_train, y_train), tree.score(x_test, y_test))
  1. Expected pattern: with None the train score is 1.0 and the test score is the lowest or close to it; as depth is limited, the train score falls while the test score usually rises, and the gap shrinks.
  2. Choose the depth with a good test score and a small gap (in a full project, choose it with cross-validation on the training set, as Module 3 explains).

Common mistakes

  • Letting the tree grow freely and being pleased with 100% train accuracy. That is not a good model, it is a lookup table.
  • Choosing the attribute with the largest Gini. Gini is impurity; the smallest weighted Gini wins.
  • Expecting a Random Forest to be as explainable as one tree. Voting across hundreds of trees removes the single readable path.
  • Thinking bootstrapping samples without replacement. Each bootstrap sample is drawn with replacement, so rows can repeat.

Summary

  • Trees consist of a root node, decision nodes and leaf nodes; each decision follows a readable path.
  • Splits are chosen by the smallest weighted Gini impurity; age in the loan example gives 0.343.
  • Unlimited trees overfit: 100% train accuracy with poor test accuracy.
  • Control complexity with max_depth, min_samples_leaf, min_samples_split.
  • Random Forest (bootstrapping plus majority vote) is more stable but less interpretable.

Flashcards · Decision Trees

8 words
WordMeaningExample
  • Decision path

    The sequence of questions from the root to a leaf that explains one prediction.

    credit_rating = fair -> income = low -> Reject.

  • Gini impurity

    1 minus the sum of squared class proportions in a branch; 0 is pure, 0.5 is a 50/50 mix.

    3 Yes, 2 No -> 0.48

  • plot_tree()

    A scikit-learn function that draws a fitted decision tree with its questions and leaves.

    plot_tree(model, feature_names=x.columns, filled=True)

  • Overfitting (tree)

    An unlimited tree memorises training rows, scoring 100% on train but poorly on test.

    Train 100%, test 71%.

  • max_depth

    The maximum number of levels a tree may grow; the first parameter to adjust when a tree overfits.

    DecisionTreeClassifier(max_depth=4)

  • min_samples_leaf

    The minimum number of samples every leaf must contain, which prevents tiny, over-specific leaves.

    DecisionTreeClassifier(min_samples_leaf=5)

  • min_samples_split

    The minimum number of samples a node needs before it is allowed to split.

    DecisionTreeClassifier(min_samples_split=10)

  • Interpretability trade-off

    Random Forest gains stability over a single tree but loses most of its readability.

    One tree explains a loan; 300 voting trees do not.