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), mục tiêu cuối cùng của chúng ta là tối thiểu hoá tỷ lệ dự đoán sai trên tập dữ liệu. Vậy tại sao cả hai thuật toán kinh điển — CART (Breiman et al., 1984) và C4.5 (Quinlan, 1986) — đều 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à lại sử dụng Độ hỗn tạp Gini và 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 trơn, vi phân tốt	Đường cong lồi trơn	Đường gấp khúc tuyến tính
Độ nhạy cận biên	Rất cao gần 0 và 1	Rất cao gần 0 và 1	Không nhạy (đạo hàm hằng số)
Chi phí tính toán	Rất nhẹ (chỉ nhân và cộng)	Nặng hơn (gọi hàm $\log_2$)	Rất nhẹ

---

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 thực hành: Gini và Entropy đóng vai trò như các chặn trên trơn và khả vi (smooth upper bounds) của sai số phân loại đa số. Việc tối thiểu hoá Gini ở từng bước chia sẽ gián tiếp ép sai số phân loại thực tế đi xuống.

---

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 số: $$E'(p) = \begin{cases} 1 & \text{khi } p < 0{,}5 \\ -1 & \text{khi } p > 0{,}5 \end{cases}$$ Đạo hàm không đổi này khiến $E(p)$ có một điểm mù rất lớn: nó hoàn toàn “vô cảm” trước bất kỳ sự phân chia nào miễn là tỷ lệ lớp ở hai nhánh con chưa vượt qua ngưỡng $0{,}5$ để làm đổi nhãn đa số.

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

Xét nút cha chứa $800$ quan sát gồm $400A$ và $400B$ ($E(t) = 0{,}5$). Giả sử có hai phép chia ứng viên:

• Phép chia 1: Tách thành $(300A, 100B)$ và $(100A, 300B)$. $$E_{\text{sau}} = \frac{400}{800}\left(1 - \frac{300}{400}\right) + \frac{400}{800}\left(1 - \frac{300}{400}\right) = 0{,}25 \implies \Delta E = 0{,}25.$$
• Phép chia 2: Tách thành $(300A, 0B)$ và $(100A, 400B)$. Nhánh trái trở thành một nút thuần khiết (pure node) $100%$. $$E_{\text{sau}} = \frac{300}{800}(0) + \frac{500}{800}\left(1 - \frac{400}{500}\right) = \frac{500}{800}(0{,}2) = 0{,}125 \implies \Delta E = 0{,}375.$$

Nếu xét một phép chia giữ nguyên nhãn đa số ở hai nhánh con, $\Delta E$ sẽ bằng $0$, hoàn toàn không nhận diện được sự cô đọng của dữ liệu.

Ngược lại, cả Parabol Gini $G(p)$ và Entropy $H(p)$ đều là các hàm lõm nghiêm ngặt có đạo hàm dốc đứng ở gần hai đầu biên ($p \to 0$ và $p \to 1$). Độ nhạy cận biên cao này giúp Gini và Entropy ưu tiên rõ rệt cho các phép chia tạo ra dù chỉ một nút thuần khiết (pure node), định hướng cho thuật toán cây tìm được đường chia tối ưu.

(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. Cầu nối toán học: Gini là xấp xỉ Taylor bậc 1 của Entropy

Giữa Gini và Entropy có một mối liên hệ giải tích thanh lịch: Gini Impurity chính là xấp xỉ tuyến tính bậc một của Entropy.

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). $$

Điều này giải thích vì sao:

1. Đồ thị tương đồng: Hai hàm số có hình dạng gần như đồng dạng sau khi chia tỷ lệ, nên trong hầu hết các tập dữ liệu thực tế, việc chọn tiêu chí Gini hay Entropy chỉ mang lại sự khác biệt dưới 2% về cấu trúc cây phân loại.
2. Ưu thế tốc độ của Gini: Để tính Entropy, máy tính phải tính giá trị hàm $\log_2$ hàng triệu lần khi duyệt qua mọi đặc trưng và ngưỡng cắt. Gini chỉ đòi hỏi các phép nhân và trừ số học cơ bản, giúp CART huấn luyện nhanh hơn đáng kể.

---

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):
  • Ưu tiên hàng đầu cho tốc độ huấn luyện.
  • Phù hợp với các tập dữ liệu lớn, nhiều đặc trưng liên tục cần thử nhiều điểm cắt.
  • Được sử dụng rộng rãi trong Random Forest nơi hàng trăm cây cần được xây dựng nhanh chóng.
• Chọn criterion='entropy' (hoặc log_loss):
  • Phù hợp khi bạn cần kết quả diễn giải trực tiếp theo lý thuyết thông tin (Information Gain).
  • Entropy có xu hướng tạo ra các nhánh cân bằng hơn một chút so với Gini trong một số trường hợp phân phối đa lớp phức tạp.
• Không dùng Sai số phân loại đa số làm tiêu chuẩn phân nhánh:
  • Sai số đa số chỉ nên dùng ở giai đoạn đánh giá hiệu năng ngoài mẫu hoặc làm tiêu chí cắt tỉa cây (cost-complexity pruning), không bao giờ dùng làm tiêu chuẩn chia nhánh vì dễ bị mắc kẹt ở các điểm mù đạo hàm bằng 0.

---

6. Tóm tắt

• Sai số phân loại $E(t)$: Phản ánh đúng mục tiêu cuối cùng nhưng có đạo hàm hằng số, không nhạy ở biên và dễ bị mù trước các bước tiến cục bộ.
• Gini $G(t)$ và Entropy $H(t)$: Là các hàm lõm nghiêm ngặt, đóng vai trò là chặn trên trơn $E(t) \le G(t)$, nhạy cảm ở hai biên và ưu tiên tạo ra các nút thuần khiết (pure node).
• Gini vs Entropy: Gini chính là xấp xỉ Taylor bậc 1 của Entropy, đem lại chất lượng phân nhánh gần như tương đương nhưng với chi phí tính toán nhẹ hơn nhiều.

---

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.
• Trevor Hastie, Robert Tibshirani, Jerome Friedman (2009), The Elements of Statistical Learning, 2nd Edition, Springer (Mục 9.2.3: Other Impurity Measures).