So sánh ba thước đo độ hỗn tạp: Gini, Entropy và Sai số phân loại

Khi huấn luyện một cây quyết định phân loại (Decision Tree), giảm tỷ lệ dự đoán sai ngoài mẫu thường là một mục tiêu quan trọng. Vậy tại sao các thuật toán kinh điển như CART (Breiman et al., 1984) và C4.5 (Quinlan, 1993) không dùng trực tiếp Sai số phân loại (Misclassification Error) để tìm điểm phân nhánh, mà dùng Độ hỗn tạp Gini hoặc tiêu chí dựa trên Shannon Entropy?

Bài viết này so sánh trực diện ba thước đo độ hỗn tạp, làm sáng tỏ “điểm mù” của sai số phân loại, và chứng minh bất đẳng thức toán học $E(t) \le G(t)$ liên kết chúng với nhau.

---

1. Ba thước đo trên bài toán hai lớp ($K=2$)

Xét một nút dữ liệu gồm hai lớp với tỷ lệ tương ứng là $p$ (lớp A) và $1 - p$ (lớp B). Ba thước đo độ hỗn tạp được định nghĩa như sau:

1. Sai số phân loại đa số (Misclassification Error): Tỷ lệ các phần tử không thuộc lớp đa số nếu gán tất cả quan sát tại nút cho lớp chiếm ưu thế: $$E(p) = 1 - \max(p, 1 - p).$$
2. Độ hỗn tạp Gini (Gini Impurity): Xác suất đoán sai khi bốc ngẫu nhiên một quan sát và gán nhãn theo phân phối của nút: $$G(p) = 2p(1 - p).$$
3. Shannon Entropy (đã chuẩn hóa $H(p)/2$): Lượng thông tin kỳ vọng (chia 2 để đưa giá trị cực đại về $0{,}5$ nhằm dễ đối chiếu trên cùng hệ trục): $$\frac{H(p)}{2} = \frac{-p\log_2 p - (1 - p)\log_2(1 - p)}{2}.$$

Tiêu chí	Gini Impurity $G(p)$	Shannon Entropy $H(p)$	Sai số đa số $E(p)$
Công thức ($K=2$)	$2p(1-p)$	$-p\log_2 p - (1-p)\log_2(1-p)$	$1 - \max(p, 1-p)$
Giá trị cực đại	$0{,}5$ (tại $p=0{,}5$)	$1{,}0$ (tại $p=0{,}5$)	$0{,}5$ (tại $p=0{,}5$)
Đặc tính hình học	Parabol lõm, trơn	Lõm nghiêm ngặt, trơn trên $(0,1)$	Tuyến tính từng khúc, không khả vi tại $0{,}5$
Độ dốc gần biên	Hữu hạn	Độ lớn tiến tới vô hạn	Hằng trên mỗi nửa khoảng
Chi phí tính toán mỗi lần	Chỉ cần phép toán số học cơ bản	Có thêm phép tính logarit	Chỉ cần tìm tỷ lệ lớn nhất

---

2. Bất đẳng thức chặn trên: $E(t) \le G(t)$

Quan sát đồ thị ở Hình 1, đường cong Parabol của Gini $G(p)$ luôn nằm phía trên hoặc tiếp xúc với đường gấp khúc của sai số đa số $E(p)$. Đây không phải là sự trùng hợp hình học ngẫu nhiên ở trường hợp 2 lớp, mà là một bất đẳng thức toán học tổng quát cho mọi bài toán $K$ lớp.

Chứng minh tổng quát cho $K$ lớp

Giả sử tại một nút $t$, tập dữ liệu gồm $K$ lớp với tỷ lệ $(p_1, \ldots, p_K)$ thỏa mãn $\sum_{k=1}^K p_k = 1$. Gọi lớp chiếm đa số có tỷ lệ lớn nhất là $p_{\max} = \max_k p_k$. Khi đó:

• Sai số phân loại đa số: $$E(t) = 1 - p_{\max}.$$
• Vì $p_k \le p_{\max}$ với mọi $k \in {1, \ldots, K}$, ta có $p_k^2 \le p_{\max} \cdot p_k$. Lấy tổng qua cả $K$ lớp: $$\sum_{k=1}^K p_k^2 \le p_{\max} \sum_{k=1}^K p_k = p_{\max} \cdot 1 = p_{\max}.$$
• Từ định nghĩa của độ hỗn tạp Gini: $$G(t) = 1 - \sum_{k=1}^K p_k^2 \ge 1 - p_{\max} = E(t).$$

Như vậy, sai số phân loại luôn bị chặn trên bởi độ hỗn tạp Gini:

$$ E(t) \le G(t). $$

Các hệ quả quan trọng:

1. Nút thuần khiết (pure node): Khi một nút chỉ chứa duy nhất một lớp ($p_{\max} = 1$), cả sai số phân loại lẫn chỉ số Gini và Entropy đều đồng thời bằng $0$: $$E(t) = G(t) = H(t) = 0.$$ Nút càng tiến gần trạng thái thuần khiết ($p_{\max} \to 1$), tất cả các chỉ số này đều tiệm cận về $0$.
2. Dấu đẳng thức: $E(t) = G(t)$ xảy ra khi các lớp không rỗng có tỷ lệ xuất hiện đồng đều (ví dụ: $K=2$ với $p_1 = p_2 = 0{,}5 \implies E = G = 0{,}5$). Trong các tình huống còn lại, Gini luôn lớn hơn nghiêm ngặt so với sai số phân loại.
3. Chặn hai phía cho trường hợp hai lớp: Nếu đặt sai số là $e = E(p) \le 0{,}5$, ta có chuỗi bất đẳng thức chặt chẽ: $$E(p) \le G(p) = 2e(1 - e) \le 2E(p).$$

Ý nghĩa của bất đẳng thức này khá giới hạn nhưng hữu ích: tại cùng một phân phối lớp ở nút, Gini không nhỏ hơn sai số phân loại đa số. Tuy nhiên, việc giảm Gini trên dữ liệu huấn luyện ở từng bước chia không bảo đảm sai số dự đoán ngoài mẫu cũng giảm; kết quả còn phụ thuộc dữ liệu, độ sâu cây và cách kiểm soát quá khớp.

---

3. Điểm mù của Sai số phân loại & Độ nhạy cận biên

Tại sao ta không tối ưu trực tiếp $E(t)$ mà phải mượn đường vòng qua Gini hay Entropy?

Câu trả lời nằm ở độ nhạy cận biên (đạo hàm) của các hàm đo:

• Sai số đa số $E(p)$ là một hàm tuyến tính từng khúc với đạo hàm hằng trên mỗi phía: $$E'(p) = \begin{cases} 1 & \text{khi } p < 0{,}5 \\ -1 & \text{khi } p > 0{,}5 \end{cases}$$ Nếu cả hai nút con giữ cùng lớp đa số với nút cha, tổng sai số có trọng số sau phép chia bằng sai số ở nút cha. Vì thế tiêu chí này không phân biệt được nhiều phép chia đã làm thay đổi đáng kể phân phối lớp nhưng chưa đổi nhãn đa số.

Ví dụ minh họa điểm mù

Xét nút cha chứa $1000$ quan sát gồm $720A$ và $280B$, nên $E(t)=0{,}28$. Một phép chia tạo ra hai nút con $(450A,50B)$ và $(270A,230B)$. Cả hai vẫn dự đoán lớp A, do đó:

$$ E_{\text{sau}}=\frac{500}{1000}\frac{50}{500}+\frac{500}{1000}\frac{230}{500}=0{,}28, $$

và mức giảm sai số bằng $0$. Trong khi đó, Gini giảm từ $2(0{,}72)(0{,}28)=0{,}4032$ xuống

$$ \frac{1}{2}\,2(0{,}9)(0{,}1)+\frac{1}{2}\,2(0{,}54)(0{,}46)=0{,}3384. $$

Gini và Entropy đều lõm nghiêm ngặt theo phân phối lớp, nên có thể ghi nhận mức cải thiện này dù nhãn đa số chưa đổi. Riêng Entropy có độ dốc tiến tới vô hạn ở hai biên; đạo hàm của Gini vẫn hữu hạn. Cả hai chỉ chọn phép chia tốt nhất trong số ứng viên theo tiêu chí cục bộ, không bảo đảm tạo ra cây tối ưu toàn cục.

(Bạn có thể thử nghiệm trực tiếp 4 kịch bản phân nhánh này trong widget tương tác tại bài Cây quyết định (Decision Tree)).

---

4. Một liên hệ hình thức qua khai triển Taylor

Nếu tuyến tính hóa từng số hạng logarit quanh $1$, ta thu được công thức Gini:

Khai triển chuỗi Taylor của hàm $\ln(x)$ quanh điểm $x = 1$ cho ta:

$$ \ln(x) \approx x - 1 \implies -\ln(p) \approx 1 - p. $$

Thay xấp xỉ này vào công thức Entropy tự nhiên $H_e(t) = -\sum_{k=1}^K p_k \ln(p_k)$:

$$ H_e(t) \approx \sum_{k=1}^K p_k (1 - p_k) = 1 - \sum_{k=1}^K p_k^2 = G(t). $$

Tuy nhiên, xấp xỉ $\ln p \approx p-1$ chỉ tốt khi $p$ gần $1$. Nó không chính xác đồng đều trên toàn miền xác suất và đặc biệt kém với các $p_k$ nhỏ. Vì vậy, phép biến đổi trên chỉ cho một liên hệ đại số gợi trực giác; nó không đủ để kết luận rằng hai tiêu chí sẽ tạo ra cùng cấu trúc cây.

Hai đường cong có hình dạng tương tự sau khi đổi thang đo và thường có thể xếp hạng nhiều phép chia giống nhau, nhưng chúng vẫn có thể chọn các phép chia khác nhau. Gini tránh phép tính logarit; lợi ích thời gian huấn luyện cụ thể phụ thuộc thư viện, dữ liệu và các chi phí khác trong quá trình tìm điểm chia.

---

5. Khi nào nên chọn tiêu chí nào?

Trong các thư viện học máy phổ biến như scikit-learn (DecisionTreeClassifier):

• Chọn criterion='gini' (mặc định):
  • Là lựa chọn khởi đầu hợp lý và không cần tính logarit.
  • Thường được dùng trong Random Forest.
• Chọn criterion='entropy' (hoặc log_loss):
  • Phù hợp khi muốn diễn giải mức giảm độ hỗn tạp theo Information Gain hoặc log loss.
• Sai số phân loại đa số:
  • Hữu ích để báo cáo tỷ lệ lỗi và có thể xuất hiện trong tiêu chí cắt tỉa, nhưng thường kém nhạy hơn Gini và Entropy khi chọn phép chia.

Không có lựa chọn nào mặc nhiên tốt hơn trên mọi dữ liệu. Nếu khác biệt có ý nghĩa với bài toán, cách kiểm tra đáng tin cậy là so sánh bằng tập validation hoặc cross-validation với cùng các siêu tham số còn lại.

---

6. Tóm tắt

• Sai số phân loại $E(t)$: Trực tiếp đếm tỷ lệ thiểu số ở nút nhưng không phân biệt được nhiều phép chia vẫn giữ nguyên nhãn đa số.
• Gini $G(t)$: Là một hàm lõm nghiêm ngặt và thỏa $E(t) \le G(t)$; nó có thể ghi nhận thay đổi mà sai số đa số bỏ qua.
• Entropy $H(t)$: Cũng lõm nghiêm ngặt, nhưng nhạy hơn Gini ở gần biên. Gini và Entropy có nhiều tính chất chung song có thể chọn các phép chia khác nhau.

---

Tài liệu tham khảo

• Leo Breiman, Jerome H. Friedman, Richard A. Olshen, Charles J. Stone (1984), Classification and Regression Trees, Wadsworth & Brooks/Cole.
• J. Ross Quinlan (1986), Induction of Decision Trees, Machine Learning, 1, 81–106.
• J. Ross Quinlan (1993), C4.5: Programs for Machine Learning, Morgan Kaufmann.
• Trevor Hastie, Robert Tibshirani, Jerome Friedman (2009), The Elements of Statistical Learning, 2nd Edition, Springer (Mục 9.2.3: Other Impurity Measures).