Decision Tree: Regression & Classification

1. Core Idea - Decision Tree là gì?

1.1 Định nghĩa

Decision Tree là supervised learning algorithm học simple decision rules từ data features để dự đoán.

Cơ chế: Hoạt động như flowchart of if-else questions:

1IF Age < 30 THEN
2    IF Income > 50k THEN
3        Prediction: Buy
4    ELSE
5        Prediction: Don't Buy
6ELSE
7    Prediction: Buy

1.2 Key Terms

2. Types of Trees

2.1 Classification Tree

Output: Categorical (Class label)

Ví dụ: Spam or Not Spam? (Binary), Flower Species (Multiclass)

Prediction ở Leaf: Majority class trong leaf đó

1from sklearn.tree import DecisionTreeClassifier
2
3# Create classifier
4clf = DecisionTreeClassifier(max_depth=3)
5clf.fit(X_train, y_train)
6
7# Predict
8y_pred = clf.predict(X_test)

2.2 Regression Tree

Output: Continuous (Number)

Ví dụ: House Price Prediction, Sales Forecast

Prediction ở Leaf: Mean (average) của target values trong leaf đó

1from sklearn.tree import DecisionTreeRegressor
2
3# Create regressor
4reg = DecisionTreeRegressor(max_depth=5)
5reg.fit(X_train, y_train)
6
7# Predict
8y_pred = reg.predict(X_test)

Leaf Node Prediction:

3. Splitting Criteria - Chọn "Best Split"

Mục tiêu: The "Best Split" minimizes impurity (độ hỗn loạn/chaos).

3.1 Classification Metrics

Gini Impurity (Mặc định - Faster)

Đo xác suất misclassifying một random element. Range: [0, 0.5]

$Gini = 1 - \sum_{i=1}^{C} p_i^2$

Ví dụ: Node có 60% Class A, 40% Class B $Gini = 1 - (0.6^2 + 0.4^2) = 1 - 0.52 = 0.48$

Entropy (Slower - log calculation)

Đo information/disorder. Range: [0, 1]

$Entropy = -\sum_{i=1}^{C} p_i \log_2(p_i)$

Ví dụ: Node có 60% Class A, 40% Class B $Entropy = -(0.6 \times \log_2(0.6) + 0.4 \times \log_2(0.4)) = 0.971$

Information Gain

$IG = Entropy(\text{Parent}) - \text{Weighted Avg } Entropy(\text{Children})$

1# So sánh Gini vs Entropy
2from sklearn.tree import DecisionTreeClassifier
3
4# Using Gini (default, faster)
5clf_gini = DecisionTreeClassifier(criterion='gini')
6
7# Using Entropy
8clf_entropy = DecisionTreeClassifier(criterion='entropy')
9
10# Using Log Loss (similar to Entropy)
11clf_log = DecisionTreeClassifier(criterion='log_loss')

3.2 Regression Metrics

MSE (Mean Squared Error) - Default

Variance reduction:

$MSE = \frac{1}{n}\sum_{i=1}^{n}(y_i - \bar{y})^2$

MAE (Mean Absolute Error)

Robust to outliers:

$MAE = \frac{1}{n}\sum_{i=1}^{n}|y_i - \bar{y}|$

1from sklearn.tree import DecisionTreeRegressor
2
3# Using MSE (default)
4reg_mse = DecisionTreeRegressor(criterion='squared_error')
5
6# Using MAE (robust to outliers)
7reg_mae = DecisionTreeRegressor(criterion='absolute_error')

3. Ví dụ tính toán thủ công chi tiết

3.1 Bài toán

Dự đoán khách hàng MUA hay KHÔNG MUA:

Dataset: 5 Co, 3 Khong

3.2 Buoc 1: Tinh Gini goc

$Gini_{root} = 1 - \left(\frac{5}{8}\right)^2 - \left(\frac{3}{8}\right)^2 = 1 - 0.391 - 0.141 = 0.468$

3.3 Buoc 2: Thu split theo "Sinh vien"

Nhanh "Co" (4 samples): 1 Mua, 3 Khong mua $Gini_{SV=Co} = 1 - \left(\frac{1}{4}\right)^2 - \left(\frac{3}{4}\right)^2 = 1 - 0.0625 - 0.5625 = 0.375$

Nhanh "Khong" (4 samples): 4 Mua, 0 Khong mua $Gini_{SV=Khong} = 1 - \left(\frac{4}{4}\right)^2 - \left(\frac{0}{4}\right)^2 = 1 - 1 - 0 = 0$

Weighted Gini: $Gini_{split} = \frac{4}{8} \times 0.375 + \frac{4}{8} \times 0 = 0.1875$

Information Gain: $IG = Gini_{root} - Gini_{split} = 0.468 - 0.1875 = 0.2805$

3.4 Buoc 3: Thu split theo Tuoi nho hon hoac bang 30

Nhanh Yes (4 samples): ID 1, 3, 6, 8 - 1 Mua, 3 Khong $Gini_{nho} = 1 - (0.25)^2 - (0.75)^2 = 0.375$

Nhanh No (4 samples): ID 2, 4, 5, 7 - 4 Mua, 0 Khong $Gini_{lon} = 0$

Weighted Gini: $Gini_{split} = 0.5 \times 0.375 + 0.5 \times 0 = 0.1875$

Information Gain: $0.468 - 0.1875 = 0.2805$

3.5 Buoc 4: So sanh va chon split tot nhat

Ca hai nhu nhau - Chon "Sinh vien" (categorical don gian hon)

3.6 Kết quả cây

Cây quyết định cuối cùng:

4. Entropy và Information Gain (Alternative)

4.1 Công thức Entropy

$Entropy = -\sum_{i=1}^{C} p_i \log_2(p_i)$

4.2 So sánh Gini vs Entropy

5. Thực hành với Scikit-learn

5.1 Train Decision Tree

1import numpy as np
2import pandas as pd
3from sklearn.tree import DecisionTreeClassifier, plot_tree
4from sklearn.model_selection import train_test_split
5from sklearn.metrics import accuracy_score, classification_report
6import matplotlib.pyplot as plt
7
8# Du lieu
9data = {
10    'Tuoi': [25, 35, 28, 45, 32, 22, 40, 30],
11    'Thu_nhap': [30, 80, 50, 90, 60, 25, 70, 55],
12    'Sinh_vien': [1, 0, 1, 0, 0, 1, 0, 1],
13    'Mua': [0, 1, 0, 1, 1, 0, 1, 1]
14}
15df = pd.DataFrame(data)
16
17X = df[['Tuoi', 'Thu_nhap', 'Sinh_vien']]
18y = df['Mua']
19
20# Train model
21model = DecisionTreeClassifier(
22    criterion='gini',  # hoac 'entropy'
23    max_depth=3,
24    random_state=42
25)
26model.fit(X, y)
27
28# Visualize tree
29plt.figure(figsize=(15, 10))
30plot_tree(model, 
31          feature_names=['Tuoi', 'Thu_nhap', 'Sinh_vien'],
32          class_names=['Khong mua', 'Mua'],
33          filled=True,
34          rounded=True)
35plt.title('Decision Tree')
36plt.show()
37
38# Feature Importance
39importance = pd.DataFrame({
40    'Feature': X.columns,
41    'Importance': model.feature_importances_
42}).sort_values('Importance', ascending=False)
43print(importance)

5. Hyperparameters - Kiểm soát Complexity

5.1 Key Hyperparameters

Control complexity để prevent overfitting:

1from sklearn.tree import DecisionTreeClassifier
2
3model = DecisionTreeClassifier(
4    max_depth=5,            # Max levels (chiều sâu tối đa)
5    min_samples_split=10,   # Min samples to split a node
6    min_samples_leaf=5,     # Min samples in a leaf node
7    max_features='sqrt',    # Features to consider for split
8    criterion='gini',       # 'gini', 'entropy', or 'log_loss'
9    random_state=42
10)
11
12model.fit(X_train, y_train)

6. Over/Underfitting & Pruning

6.1 Bias-Variance Tradeoff

Underfitting (Too Simple)

• Tree quá nông (shallow)
• Fails to capture patterns
• High Bias: Train và Test scores đều thấp

Overfitting (Too Complex)

• Tree quá sâu (deep)
• Memorizes noise in training data
• High Variance: Perfect train score, poor test score

6.2 Pruning - Cắt tỉa cây

Trimming the tree để improve generalization.

Pre-Pruning (Early Stopping)

Stop growing during training:

1# Control via hyperparameters
2clf = DecisionTreeClassifier(
3    max_depth=5,           # Stop at depth 5
4    min_samples_split=10,  # Need 10+ samples to split
5    min_samples_leaf=5     # Each leaf must have 5+ samples
6)

Pros: Fast ⚡
Cons: Might stop too early ❌

Post-Pruning (Cost Complexity)

Grow full tree, then cut branches that add little predictive power:

1# Cost Complexity Pruning
2clf = DecisionTreeClassifier(ccp_alpha=0.01)
3clf.fit(X_train, y_train)
4
5# Find optimal alpha
6from sklearn.model_selection import cross_val_score
7import numpy as np
8
9alphas = np.arange(0, 0.1, 0.01)
10scores = []
11
12for alpha in alphas:
13    clf = DecisionTreeClassifier(ccp_alpha=alpha)
14    score = cross_val_score(clf, X_train, y_train, cv=5).mean()
15    scores.append(score)
16
17optimal_alpha = alphas[np.argmax(scores)]
18print(f"Optimal ccp_alpha: {optimal_alpha}")

7. Advantages & Limitations (Chi tiết từ PDF)

7.1 Pros ✅

1# Get feature importance
2importances = clf.feature_importances_
3feature_names = ['Feature1', 'Feature2', 'Feature3']
4
5for name, imp in zip(feature_names, importances):
6    print(f"{name}: {imp:.4f}")

7.2 Cons ❌

7.3 When to Use?

✅ Use Decision Tree khi:

• Explainability is critical (Banking, Medical, Legal)
• Baseline model để so sánh
• Small to medium structured datasets
• Features are mixed (numerical & categorical)

❌ Don't use khi:

• Need highest accuracy → Use Random Forest, XGBoost
• Data is high-dimensional và sparse → Use Linear models
• Want stable predictions → Use ensemble methods

8. Quick Comparison với các algorithms khác

9. Real-World Examples

9.1 Classification Use Cases

Loan Approval: Risk level (Low/Medium/High)

1# Features: Income, Credit Score, Employment Status, Debt Ratio
2# Target: Approved (Yes/No)

Medical Diagnosis: Disease present? (Yes/No)

1# Features: Age, Blood Pressure, Cholesterol, BMI
2# Target: Heart Disease (0/1)

Customer Churn: Will customer leave?

1# Features: Usage, Support Tickets, Contract Type, Tenure
2# Target: Churn (Yes/No)

9.2 Regression Use Cases

Pricing: Estimating used car prices

1# Features: Year, Mileage, Brand, Condition
2# Target: Price ($)

Demand Forecasting: Predicting daily sales volume

1# Features: Day of Week, Season, Promotions, Weather
2# Target: Sales Units

10. Next Steps - Upgrade to Ensembles

Random Forest (Bagging)

• Bags multiple trees to reduce variance
• Runs trees in parallel
• Reduces overfitting dramatically

Gradient Boosting (XGBoost)

• Trains trees sequentially to fix errors of previous ones
• High performance but risk of overfitting
• Tuning required

Chúng ta sẽ học chi tiết trong bài Ensemble Methods!

Bài tập tự luyện

1. Bài tập 1: Tính Gini cho node [3 Red, 5 Blue, 2 Green]
2. Bài tập 2: Train Decision Tree trên Titanic dataset, visualize tree
3. Bài tập 3: So sánh performance với max_depth=[3, 5, 10, None]
4. Bài tập 4: Implement Cost Complexity Pruning và tìm optimal alpha

Tài liệu tham khảo

Câu hỏi tự kiểm tra

1. Gini Impurity và Entropy khác nhau như thế nào? Khi nào dùng criterion nào?
2. Information Gain được tính như thế nào và nó giúp Decision Tree chọn best split ra sao?
3. Tại sao Decision Tree dễ bị Overfitting? Pruning giúp giải quyết vấn đề này như thế nào?
4. So sánh Decision Tree với Linear/Logistic Regression — khi nào nên dùng Decision Tree?