06_Decision_Tree

Tags: #◇CSINTSY #◇Computational Thinking #◇Computer Science #◇Artificial Intelligence #◇Machine Learning #◇Intelligent Systems #◇Probability #◇Data Analysis

---

◇Overview

A Decision Tree is a supervised learning model used for classification and regression. It predicts the value of a target variable by learning simpl...

◇Details / Theory

6. Decision Tree Reviewer

◇Overview

A Decision Tree is a supervised learning model used for classification and regression. It predicts the value of a target variable by learning simple decision rules inferred from the data features. It looks like a flowchart structure.

◇Structure

Root Node: The top-most node that represents the entire dataset. It is the first decision point. Internal Nodes: Decision points that test an attribute (e.g., "Is it raining?"). Each branch represents the outcome of the test (e.g., "Yes" or "No"). Leaf Nodes: Terminal nodes that represent the final outcome or class label (e.g., "Play Tennis" or "Don't Play").

◇How it Works

1. Start at the root node.
2. Test the attribute specified by the node.
3. Move down the branch corresponding to the value of the attribute.
4. Repeat until a leaf node is reached.
5. Return the class label of the leaf node.

◇Splitting Criteria

How do we choose which attribute to split on? We want the attribute that best separates the data into pure classes.

Gini Index (Impurity)

Definition: A measure of how often a randomly chosen element from the set would be incorrectly labeled if it was randomly labeled according to the distribution of labels in the subset. Goal: Minimize the Gini Index. A Gini Index of 0 means the node is pure (all elements belong to the same class). Formula:
$Gini(D) = 1 - \sum\_{i=1}^{c} (p_i)^2$
$D$: The dataset at the node.
$c$: Number of classes.
$p_i$: Probability (proportion) of class $i$ in $D$.

Example Calculation

Suppose a node has 5 examples: 3 Positive (+), 2 Negative (-).
$p(+) = 3/5 = 0.6$ $p(-) = 2/5 = 0.4$ $Gini = 1 - (0.6^2 + 0.4^2) = 1 - (0.36 + 0.16) = 1 - 0.52 = 0.48$

Weighted Gini Index (for a split)

When splitting a parent node into children nodes, we calculate the weighted average of the Gini Impurity of the children.
$Gini*{split} = \sum \frac{N*{child}}{N\_{parent}} \times Gini(child)$
We choose the attribute that produces the lowest weighted Gini index.

◇Overfitting

Problem: Trees can become very deep and complex, memorizing the training data (including noise). This leads to poor performance on new data. Solutions:
Pruning: Removing branches that provide little power.
Max Depth: Limiting how deep the tree can grow.
Min Samples Split: Requiring a minimum number of samples to create a split.

◇Solved Example: Choosing the Best Split

Dataset: 10 Students.
Target: Passed (6 Yes, 4 No). Feature A: Studied (Yes/No).
Studied=Yes: 5 Students (5 Passed, 0 Failed).
Studied=No: 5 Students (1 Passed, 4 Failed).

Step 1: Calculate Gini of Parent (Root)
$P(Pass) = 6/10 = 0.6$ $P(Fail) = 4/10 = 0.4$ $Gini(Parent) = 1 - (0.6^2 + 0.4^2) = 1 - (0.36 + 0.16) = 0.48$

Step 2: Calculate Gini of Split on "Studied"
Left Node (Studied=Yes):
Total: 5. Pass: 5. Fail: 0.
$Gini(Yes) = 1 - ((5/5)^2 + (0/5)^2) = 1 - (1 + 0) = 0$. (Pure node!)
Right Node (Studied=No):
Total: 5. Pass: 1. Fail: 4.
$Gini(No) = 1 - ((1/5)^2 + (4/5)^2) = 1 - (0.04 + 0.64) = 1 - 0.68 = 0.32$.

Step 3: Calculate Weighted Gini for Split
$Gini\_{split} = \frac{5}{10}(0) + \frac{5}{10}(0.32) = 0 + 0.16 = 0.16$

Conclusion:
The Gini dropped from 0.48 (Parent) to 0.16 (Split). This is a huge improvement (Information Gain), so "Studied" is a very good feature to split on.

---

---

◇Common Pitfalls

Confusing Gini Index (impurity) with information gain (entropy-based) — both measure split quality but use different formulas. Forgetting to use weighted Gini when child nodes have different sample sizes. Overfitting by growing the tree too deep — use pruning or maximum depth limits.

◇Summary

TL;DR — Decision trees split data recursively by choosing the attribute that minimizes impurity (Gini Index) or maximizes information gain. The best split creates the most homogeneous child nodes. Pruning prevents overfitting.

◇Links

Related: Source / Reference:

---

Made by 2ru17

Please contact me through discord or my the university email for any problems regarding the reviewer. Thanks!

◇References & Navigation

• Previous Topic: ◇Machine Learning
• Next Topic: ◇Naive Bayes
• Related Notes: ◇Decision Trees