[DS Blog #68] Thuật Toán K-NN & Cây Quyết Định (Decision Tree): Bản Chất Trực Quan Đời Thường, Tiêu Chí Gini & Cách Chống Học Vẹt (Overfitting)

1. Bối cảnh thực tế (Context & Problem Statement)

Ở bài viết trước, chúng ta đã làm quen với Linear Regression và Logistic Regression. Hai thuật toán này cố gắng dùng một đường thẳng phẳng để dự đoán hoặc phân chia dữ liệu.

Tuy nhiên, thế giới thực tế hiếm khi nào thẳng tắp:

Khách hàng trẻ tuổi và khách hàng lớn tuổi đều có thể thích xem phim hành động, trong khi nhóm trung niên lại thích xem thời sự $\rightarrow$ Dữ liệu bị uốn cong, đan xen phức tạp mà một đường thẳng không thể nào phân tách được.

Để giải quyết các bài toán phi tuyến tính này một cách tự nhiên nhất, các nhà khoa học máy tính đã phát minh ra 2 thuật toán mô phỏng trực tiếp cách con người đưa ra quyết định hàng ngày:

K-Nearest Neighbors (K-NN): Dựa trên kinh nghiệm của những người xung quanh ta ("Hãy cho tôi biết 5 người bạn thân nhất của bạn, tôi sẽ nói cho bạn biết bạn là ai").
Decision Tree (Cây Quyết Định): Dựa trên một chuỗi các câu hỏi Đúng/Sai liên tiếp ("Nếu trời mưa thì mang dù, nếu không mưa thì đi bộ; nếu có gió lớn thì mặc áo khoác").

2. Các Khái Niệm & Cơ Chế Cốt Lõi

2.1. Thuật Toán K-Láng Giềng Gần Nhất (K-Nearest Neighbors - K-NN)

1. Triết lý hoạt động: "Ngưu tầm ngưu, mã tầm mã":

K-NN là thuật toán đơn giản và trực quan nhất trong toàn bộ thế giới Machine Learning. Nó hoàn toàn không cần trải qua quá trình huấn luyện phức tạp (Lazy Learner):

Khi có một điểm dữ liệu mới $X$ $X$ cần dự đoán:
1. Tính khoảng cách từ $X$ đến tất cả mọi điểm dữ liệu có sẵn trong bộ nhớ.
2. Chọn ra $K$ điểm nằm gần $X$ nhất.
3. Lấy ý kiến biểu quyết số đông: Trong $K$ người hàng xóm đó, nhãn nào chiếm đa số thì gán nhãn đó cho $X$ !

                  (Lớp Đỏ: Tam giác)
                  ▲       ▲
                     ▲  * [Điểm X cần đoán]
                        / \
                       ●   ●  (Lớp Xanh: Hình tròn)
                       
- Nếu chọn K = 1: Điểm gần nhất là ▲ -> Đoán X là Tam giác Đỏ!
- Nếu chọn K = 3: Có 2 điểm ● và 1 điểm ▲ -> Đa số là Tròn Xanh -> Đoán X là Tròn Xanh!

2. Tầm quan trọng sống còn của việc Chuẩn hóa dữ liệu (Feature Scaling):

Khoảng cách giữa hai điểm trong không gian thường được đo bằng khoảng cách đường chim bay (Euclidean Distance): $d(A, B) = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$

Cạm bẫy chí mạng:
- Giả sử bạn dự đoán người mua xe dựa trên 2 thuộc tính: Tuổi ( $20 - 60$ tuổi) và Thu nhập ( $10,000,000 - 100,000,000$ VNĐ).
- Chênh lệch về tuổi chỉ tối đa $40$ đơn vị, trong khi chênh lệch về thu nhập lên tới hàng chục triệu đơn vị!
- Khi đưa vào công thức căn bậc hai, thuộc tính Thu nhập sẽ hoàn toàn đè bẹp và nuốt chửng thuộc tính Tuổi, biến biến Tuổi thành vô dụng!
$\rightarrow$ Quy tắc vàng: BẮT BUỘC phải dùng StandardScaler hoặc MinMaxScaler đưa mọi biến số về cùng một thang đo trước khi chạy K-NN!

3. Cách chọn số lượng hàng xóm $K$ :

Luôn chọn $K$ là số LẺ (ví dụ $K = 3, 5, 7$ ) để tránh tình trạng hòa phiếu ( $50/50$ ).
Nếu chọn $K = 1$ : Rất dễ bị Overfitting vì chỉ cần một điểm nhiễu bất thường cũng sẽ làm sai lệch dự đoán.
Nếu chọn $K$ quá lớn (bằng toàn bộ số mẫu $N$ ): Dẫn đến Underfitting vì mô hình sẽ luôn dự đoán nhãn của lớp chiếm đa số trong tập dữ liệu.

2.2. Thuật Toán Cây Quyết Định (Decision Tree)

1. Bản chất: Trò chơi 20 câu hỏi đoán đồ vật:

Decision Tree tổ chức dữ liệu thành cấu trúc cây phân cấp từ trên xuống dưới:

Gốc cây (Root Node): Câu hỏi phân loại đầu tiên quan trọng nhất.
Các nhánh cây (Decision Nodes): Các câu hỏi điều kiện rẽ nhánh tiếp theo.
Lá cây (Leaf Nodes): Kết quả dự đoán cuối cùng (không phân nhánh nữa).

                            [ Tuổi > 30? ]
                               /      \
                        ĐÚNG  /        \ SAI
                             v          v
                  [ Thu nhập > 20M? ]   [ KHÔNG MUA ] (Leaf)
                       /      \
                ĐÚNG  /        \ SAI
                     v          v
                 [ MUA ]    [ KHÔNG MUA ] (Leaf)

2. Tiêu chí chọn câu hỏi tốt nhất: Độ vẩn đục Gini (Gini Impurity):

Làm thế nào để máy tính tự biết nên hỏi câu nào trước, câu nào sau? Thuật toán chọn câu hỏi giúp chia tách dữ liệu thành các nhóm thuần khiết nhất (Purest Groups).

$\text{Gini Impurity} = 1 - \sum_{i=1}^{C} p_i^2$ (trong đó $p_i$ là tỷ lệ phần trăm của lớp thứ $i$ trong nhóm).

Ý nghĩa đời thường của Gini Impurity:
- Nếu trong một rổ toàn bộ đều là Táo đỏ ( $100\%$ đỏ, $0\%$ xanh):
  $\text{Gini} = 1 - (1.0^2 + 0.0^2) = \mathbf{0.0}$ $\rightarrow$ Thuần khiết tuyệt đối!
- Nếu trong rổ có nửa Táo đỏ và nửa Táo xanh ( $50/50$ ):
  $\text{Gini} = 1 - (0.5^2 + 0.5^2) = 1 - 0.5 = \mathbf{0.5}$ $\rightarrow$ Vẩn đục tối đa, cực kỳ hỗn tạp!
Thuật toán sẽ thử tất cả các cột và các ngưỡng cắt, câu hỏi nào giúp giảm độ vẩn đục Gini nhiều nhất sẽ được chọn làm điểm phân nhánh!

3. Bệnh nan y của Decision Tree: Học vẹt (Overfitting) & Kỹ thuật cắt tỉa:

Nếu để cây tự do phát triển, nó sẽ tiếp tục đặt câu hỏi cho đến khi mỗi chiếc lá chỉ chứa đúng $1$ điểm dữ liệu duy nhất $\rightarrow$ Đạt độ chính xác $100\%$ trên tập Train, nhưng dự đoán hoàn toàn sai bét trên tập Test thực tế!

3 Siêu tham số cắt tỉa cây (Pruning) quan trọng nhất:
1. max_depth: Giới hạn độ sâu tối đa của cây (thường đặt từ $3$ đến $5$ tầng).
2. min_samples_split: Số lượng mẫu tối thiểu cần có ở một nút thì mới cho phép chia nhánh tiếp.
3. min_samples_leaf: Số lượng mẫu tối thiểu bắt buộc phải có ở một chiếc lá (ngăn chặn việc sinh ra những chiếc lá chỉ có $1-2$ điểm dữ liệu dị biệt).

3. Các Bảng Markdown So Sánh Chi Tiết

📊 Bảng 1: So Sánh Toàn Diện: Logistic Regression vs. K-NN vs. Decision Tree

Tiêu chí	Hồi quy Logistic (Logistic Regression)	K-Láng giềng gần nhất (K-NN)	Cây quyết định (Decision Tree)
Bản chất mô hình	Mô hình tham số tuyến tính (Linear)	Mô hình phi tham số, dựa trên bộ nhớ (Instance-based)	Mô hình phi tham số, phi tuyến tính (Rule-based)
Bắt buộc chuẩn hóa dữ liệu?	BẮT BUỘC (Để gradient hội tụ)	BẮT BUỘC TUYỆT ĐỐI (Do dùng khoảng cách Euclidean)	HOÀN TOÀN KHÔNG CẦN (Chỉ so sánh thứ tự lớn hơn/nhỏ hơn)
Tốc độ huấn luyện (Training)	Nhanh	Siêu tốc (Bằng 0 - Chỉ cần lưu dữ liệu vào RAM)	Nhanh
Tốc độ dự đoán (Inference)	Siêu tốc (Chỉ cần nhân ma trận $w^Tx$ )	Rất chậm khi dữ liệu lớn (Phải tính khoảng cách tới mọi điểm)	Siêu tốc (Chỉ cần đi theo các nhánh IF-ELSE)
Khả năng giải thích (Explainability)	Khá tốt (Nhìn vào trọng số $w$ )	Kém	Xuất sắc nhất (Vẽ cây ra là giải thích được 100% cho sếp)
Độ nhạy cảm với Outliers	Trung bình/Cao	Cao	Rất thấp (Outlier chỉ rơi vào 1 chiếc lá riêng lẻ)

📊 Bảng 2: So Sánh Hai Tiêu Chí Phân Nhánh: Gini Impurity vs. Entropy (Information Gain)

Tiêu chí	Gini Impurity	Entropy / Information Gain
Công thức toán học	$1 - \sum p_i^2$	$-\sum p_i \log_2(p_i)$
Dải giá trị nhị phân	Từ $0.0$ (Thuần khiết) đến $0.5$ (Hỗn tạp)	Từ $0.0$ (Thuần khiết) đến $1.0$ (Hỗn tạp)
Tốc độ tính toán	Nhanh hơn đáng kể (Chỉ có phép nhân và trừ)	Chậm hơn (Phải tính hàm Logarit)
Cài đặt mặc định	Mặc định trong Scikit-Learn (`criterion='gini'`)	Tùy chọn (`criterion='entropy'`)
Sự khác biệt thực tế	Trong $98\%$ trường hợp, hai tiêu chí này cho ra cấu trúc cây gần như giống hệt nhau

📊 Bảng 3: Bảng Tra Cứu Các Tham Số Chống Overfitting Cho Decision Tree

Tham số trong Scikit-Learn	Ý nghĩa kỹ thuật	Giá trị khuyến nghị ban đầu	Tác động khi tăng giá trị
`max_depth`	Độ sâu tối đa từ gốc đến lá	`3` hoặc `5`	Tăng độ phức tạp $\rightarrow$ Dễ Overfitting
`min_samples_split`	Số lượng mẫu tối thiểu để được phép rẽ nhánh	`10` đến `20`	Giảm độ phức tạp $\rightarrow$ Cây nông hơn, chống Overfitting
`min_samples_leaf`	Số lượng mẫu tối thiểu phải có ở mỗi chiếc lá	`5` đến `10`	Ngăn chặn lá đơn lẻ $\rightarrow$ Chống học vẹt cực tốt
`max_features`	Số lượng thuộc tính tối đa được xét tại mỗi lần chia	`'sqrt'` hoặc `None`	Giúp đa dạng hóa cây (nền tảng của Random Forest)

4. Thực Hành Thực Chiến: Code Scikit-Learn Chuẩn Mực Từng Dòng (Walkthrough)

📌 Bài toán: Dự đoán Khách hàng Mua bảo hiểm dựa trên Tuổi, Thu nhập và Điểm tín dụng

import numpy as np
import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.tree import DecisionTreeClassifier, export_text
from sklearn.metrics import accuracy_score

# 1. Tạo dữ liệu mẫu thực tế:
data = {
    'age': [22, 25, 45, 52, 23, 40, 60, 48, 33, 55],
    'income': [15, 18, 65, 90, 12, 50, 110, 85, 35, 95], # Triệu đồng/tháng
    'credit_score': [600, 620, 750, 780, 580, 710, 800, 760, 650, 790],
    'buy_insurance': [0, 0, 1, 1, 0, 1, 1, 1, 0, 1]      # 1: Mua, 0: Không mua
}
df = pd.DataFrame(data)

X = df[['age', 'income', 'credit_score']]
y = df['buy_insurance']

# 2. Chia tập Train và Test:
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)

# =========================================================================
# PHẦN 1: HUẤN LUYỆN THUẬT TOÁN K-NN (BẮT BUỘC PHẢI SCALING)
# =========================================================================
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)

# Chọn K = 3 (số lẻ chống hòa phiếu):
knn = KNeighborsClassifier(n_neighbors=3)
knn.fit(X_train_scaled, y_train)
knn_pred = knn.predict(X_test_scaled)
print(f"Độ chính xác mô hình K-NN: {accuracy_score(y_test, knn_pred) * 100:.1f}%")

# =========================================================================
# PHẦN 2: HUẤN LUYỆN CÂY QUYẾT ĐỊNH (KHÔNG CẦN SCALING, CẮT TỈA TRÁNH OVERFIT)
# =========================================================================
# Giới hạn max_depth = 3 để cây không bị học vẹt:
dtree = DecisionTreeClassifier(criterion='gini', max_depth=3, min_samples_leaf=1, random_state=42)
dtree.fit(X_train, y_train) # Dùng trực tiếp dữ liệu gốc X_train, không cần scale!
dtree_pred = dtree.predict(X_test)
print(f"Độ chính xác Cây quyết định: {accuracy_score(y_test, dtree_pred) * 100:.1f}%")

# 3. Trích xuất toàn bộ logic cây quyết định ra văn bản trực quan:
print("\n=== CẤU TRÚC LUẬT RA QUYẾT ĐỊNH CỦA CÂY (DECISION RULES) ===")
tree_rules = export_text(dtree, feature_names=list(X.columns))
print(tree_rules)

5. Góc Ôn Luyện Phỏng Vấn (Interview Corner)

❓ Câu hỏi 1: Tại sao trước khi áp dụng thuật toán K-Nearest Neighbors (K-NN), chúng ta BẮT BUỘC phải thực hiện chuẩn hóa dữ liệu (Feature Scaling)? Điều này có bắt buộc đối với Cây quyết định (Decision Tree) hay không và tại sao?

Gợi ý trả lời ngắn gọn, chuẩn xác:
- Với K-NN (Bắt buộc $100\%$ ):
  - K-NN đưa ra dự đoán hoàn toàn dựa trên việc tính toán khoảng cách hình học (như Euclidean) giữa các điểm dữ liệu.
  - Nếu các thuộc tính có đơn vị đo lường và thang giá trị chênh lệch lớn (ví dụ: Tuổi từ $1-100$ , nhưng Thu nhập từ vài triệu đến hàng trăm triệu), thì khoảng cách sẽ bị chi phối hoàn toàn bởi thuộc tính có giá trị lớn hơn. Thuộc tính có thang đo nhỏ sẽ bị triệt tiêu tác dụng. Do đó bắt buộc phải đưa tất cả về cùng thang đo (như chuẩn hóa $Z$ -Score).
- Với Decision Tree (Hoàn toàn KHÔNG cần thiết):
  - Cây quyết định không hề tính toán bất kỳ khoảng cách nào.
  - Tại mỗi bước phân nhánh, nó chỉ thực hiện phép so sánh thứ tự lớn hơn hoặc nhỏ hơn trên từng thuộc tính một cách độc lập (ví dụ: Thu nhập > 50 triệu?).
  - Dù bạn để nguyên $50,000,000$ hay chia cho một tỷ, thứ tự sắp xếp của các điểm dữ liệu vẫn giữ nguyên, điểm cắt tối ưu Gini không hề thay đổi. Do đó, Decision Tree hoàn toàn miễn nhiễm với sự khác biệt về thang đo của dữ liệu.

❓ Câu hỏi 2: Làm thế nào để lựa chọn giá trị $K$ tối ưu trong thuật toán K-NN? Điều gì sẽ xảy ra về mặt thiên lệch (Bias) và phương sai (Variance) nếu ta chọn $K = 1$ hoặc $K = N$ (với $N$ là toàn bộ số dòng dữ liệu)?

Gợi ý trả lời:
- Trường hợp $K = 1$ (High Variance, Low Bias $\rightarrow$ Overfitting):
  - Mô hình chỉ nhìn vào đúng 1 người hàng xóm duy nhất gần nhất.
  - Ranh giới quyết định sẽ bị bẻ cong ngoằn ngoèo để bao bọc từng điểm một. Nếu có một điểm nhiễu (Outlier) lạc loài, mô hình sẽ lập tức đoán sai. Độ chính xác trên tập Train là $100\%$ nhưng trên tập Test sẽ rất kém.
- Trường hợp $K = N$ (Low Variance, High Bias $\rightarrow$ Underfitting):
  - Với mọi điểm dữ liệu cần dự đoán, mô hình đều tham khảo ý kiến của toàn bộ $N$ người trong tập dữ liệu.
  - Kết quả: Nó sẽ luôn luôn dự đoán nhãn của lớp chiếm đa số trong tập dữ liệu, hoàn toàn bỏ qua mọi đặc trưng riêng biệt của điểm đầu vào. Ranh giới quyết định trở thành một đường thẳng trơ lì.
- Cách chọn $K$ tối ưu trong thực tế:
  - Sử dụng kỹ thuật K-Fold Cross-Validation chạy thử nghiệm qua một dải các số lẻ (ví dụ: $K \in [3, 5, 7, 9, 11]$ ).
  - Vẽ đồ thị biểu diễn sai số (Validation Error) theo $K$ . Giá trị $K$ tối ưu là điểm nằm ở "khuỷu tay" (Elbow point) nơi sai số trên tập kiểm định đạt mức thấp nhất.

❓ Câu hỏi 3: Decision Tree rất dễ bị hiện tượng Overfitting (học vẹt dữ liệu). Nêu 3 siêu tham số (Hyperparameters) quan trọng nhất trong Scikit-Learn giúp bạn kiểm soát và ngăn chặn Overfitting cho cây.

Gợi ý trả lời:
1. max_depth (Giới hạn độ sâu tối đa):
  - Đây là tham số trực tiếp và quan trọng nhất. Nó quy định cây chỉ được phép rẽ nhánh tối đa bao nhiêu tầng (thường chọn từ 3 đến 5 tầng). Ngăn chặn cây tiếp tục đặt câu hỏi xuống các tầng quá sâu chỉ để khớp với vài điểm dữ liệu cá biệt.
2. min_samples_leaf (Số lượng mẫu tối thiểu ở một lá):
  - Quy định một nút lá cuối cùng bắt buộc phải đại diện cho ít nhất bao nhiêu điểm dữ liệu (ví dụ: $\ge 5$ hoặc $\ge 10$ mẫu). Nếu một phép rẽ nhánh tạo ra một chiếc lá chỉ chứa 1 hoặc 2 điểm dữ liệu, phép chia nhánh đó sẽ bị cấm.
3. min_samples_split (Số lượng mẫu tối thiểu để được chia nhánh):
  - Quy định một nút phải có ít nhất bao nhiêu mẫu dữ liệu thì mới được phép xem xét chia nhánh tiếp. Nếu số mẫu còn lại quá ít, quá trình phân nhánh tại nút đó sẽ lập tức dừng lại và trở thành một chiếc lá.

6. Tóm Tắt Ghi Nhớ Nhanh (Key Takeaways)

K-NN là thuật toán Lười biếng (Lazy Learner): Không học trước, khi có dữ liệu mới thì tính khoảng cách Euclidean tới $K$ người láng giềng gần nhất để biểu quyết đa số.
K-NN bắt buộc phải Scale dữ liệu bằng StandardScaler; luôn chọn $K$ là số lẻ ( $3, 5, 7$ ) để tránh hòa phiếu.
Decision Tree hoạt động như trò chơi 20 câu hỏi; không cần chuẩn hóa dữ liệu, không bị ảnh hưởng bởi Outliers và có khả năng giải thích tuyệt vời.
Độ vẩn đục Gini = 0.0 nghĩa là nhóm hoàn toàn thuần khiết (chỉ có 1 nhãn duy nhất).
Luôn chống Overfitting cho Cây quyết định bằng các tham số cắt tỉa: max_depth, min_samples_leaf, và min_samples_split.