📝 Decision Tree

Description

• Decision tree is a popular machine learning algorithm used for classification and regression tasks. It works by recursively splitting the data into subsets based on the most significant feature at each node, creating a tree-like structure. The decision tree can be visualized to understand the decision-making process and the importance of different features in the dataset.

Key points

< Gini impurity >

• Node impurity: Gini impurity measures how mixed a classification node's classes are:

  $$G(\text{node}) = 1-\sum_{k=1}^{K}p_k^2$$

  Here, $p_k$ is the fraction of examples in class $k$ within that node. Lower values mean a purer node; $G=0$ means every example belongs to one class.

• Split impurity: assess a candidate split using the sample-weighted average of its children's impurities:

  $$G_{\text{split}}=\frac{n_L}{n}G_L+\frac{n_R}{n}G_R$$

  Symbol	Meaning
  $G_L$	Gini impurity of the left child, calculated from its own class proportions
  $G_R$	Gini impurity of the right child, calculated from its own class proportions
  $n_L$, $n_R$	Numbers of samples in the left and right children
  $n=n_L+n_R$	Number of samples in the parent node

• Gini gain: among eligible candidate splits at the same parent, the tree chooses the lowest weighted child impurity, equivalently the largest decrease from the parent's impurity:

  $$\text{Gini gain}=G_{\text{parent}}-G_{\text{split}}$$

  “Gini score” can mean either node impurity or weighted split impurity, so state which one is being used.

• Example — recommend a lipstick to a user: train a decision tree to predict whether a user will click a recommendation for one particular lipstick. Inputs are gender, age, annual income, and nationality; the training label is clicked (1) or did not click (0) after the lipstick was shown. The predicted click probability can be used as a recommendation score.

  1. Start with the same training data for every candidate split. This synthetic dataset is deliberately constructed so gender has the largest Gini gain. It illustrates the calculation, not a general claim about demographic groups or lipstick preferences.

  User	Gender	Age	Annual income (USD)	Nationality	Clicked
  U1	Woman	24	80,000	Japan	1
  U2	Woman	24	80,000	France	1
  U3	Woman	24	40,000	Japan	1
  U4	Woman	40	80,000	France	1
  U5	Woman	40	40,000	Japan	1
  U6	Man	40	80,000	France	1
  U7	Man	40	40,000	France	1
  U8	Man	24	80,000	Japan	0
  U9	Man	24	40,000	Japan	0
  U10	Man	24	40,000	France	0

  The parent has 7 clicked and 3 did-not-click samples:

  $$G_{\text{parent}}=1-(7/10)^2-(3/10)^2=0.42$$

  2. Calculate the gender split. The question is “Is gender Woman?” Its left child contains the five women; its right child contains the five men in this dataset.

  Child	Label counts	Sample count	Gini impurity
  Left: Woman	5 clicked, 0 did not click	$n_L=5$	$G_L=1-(5/5)^2-(0/5)^2=0$
  Right: Man	2 clicked, 3 did not click	$n_R=5$	$G_R=1-(2/5)^2-(3/5)^2=0.48$

  Weight the child impurities by their sample counts, then subtract from the parent impurity:

  $$G_{\text{split, gender}}=\frac{5}{10}\times0+\frac{5}{10}\times0.48=0.24$$ $$\text{Gini gain}_{\text{gender}}=0.42-0.24=0.18$$

  3. Compare the four candidate splits. Counts below are written as clicked / did not click. Each right child is the complement of the left-child condition.

  Feature / left-child condition	Left counts	Right counts	$G_L$	$G_R$	Weighted child Gini	Gini gain
  Gender: Woman	5 / 0	2 / 3	$0$	$0.48$	$0.5\times0+0.5\times0.48=0.24$	$0.18$
  Age: at most 30	3 / 3	4 / 0	$0.50$	$0$	$0.6\times0.50+0.4\times0=0.30$	$0.12$
  Income: above USD 60,000	4 / 1	3 / 2	$0.32$	$0.48$	$0.5\times0.32+0.5\times0.48=0.40$	$0.02$
  Nationality: Japan	3 / 2	4 / 1	$0.48$	$0.32$	$0.5\times0.48+0.5\times0.32=0.40$	$0.02$

  

  4. Choose gender at the root. It has the lowest weighted impurity ($0.24$) and largest gain ($0.18$). The pure left child becomes a leaf; the right child can be split again using the remaining features if the stopping criteria allow it. “Helps the most” here means the largest impurity reduction at this node, not a causal effect or a universal feature ranking.

  5. Produce a recommendation score. If the tree stops after this one split, a new user with features (Woman, 24, 40000, Japan) reaches the left leaf and receives an empirical click probability of $5/5=1.0$. A user with (Man, 40, 80000, France) reaches the right leaf and receives $2/5=0.4$. These tiny-sample estimates demonstrate leaf scoring; they are not reliable real-world click probabilities. A deeper tree may produce different scores.

Comparison

< Decision Tree vs. Naive Bayes >

• When to use each: see Naive Bayes vs. Decision Tree for task choices, feature interactions, interpretability, and validation guidance.

Implementation

• https://github.com/yujie-hao/decision-tree

Favorites

⛳️

Magic

Video Tutorial

Decision & Classification Trees

Decision Tree: Important things to know

Decision Tree Explained Visually | Gini Impurity, Random Forests & Feature Importance

The Gini Impurity Index

Reference

• Decision Tree in Machine Learning (geeksforgeeks.org)