Chỉ số Gini (Gini Impurity): Đo độ hỗn tạp từ một trò chơi xác suất

Thuật toán cây phân loại CART (Classification and Regression Trees) thực chất là bài toán Cô Tấm lựa đậu được tự động hoá, vận hành nhờ sự phối hợp nhịp nhàng giữa hai vai trò: The Doer (người thực thi) và The Tester (giám khảo đánh giá).

• Cô Tấm (The Doer — Bộ phân nhánh): Bắt đầu với một rổ đậu lẫn lộn (tập dữ liệu), nhiệm vụ của Tấm là liên tục đề xuất phương pháp phân loại.
• Thước đo Gini (The Tester — Giám khảo): Mỗi khi Tấm chia thử, “máy đo Gini” sẽ quét qua hai rổ mới để định lượng độ hỗn tạp:
  • $\text{Gini} = 0$: Rổ thuần khiết tuyệt đối (chỉ còn một loại hạt) $\to$ Tấm cất rổ đó đi, nhánh này hoàn tất.
  • $\text{Gini} > 0$: Rổ vẫn hỗn tạp (còn lẫn nhiều loại hạt) $\to$ Tấm phải tiếp tục tìm tiêu chí để lựa tiếp.

“Doer” thử mọi cách chia khả dĩ, còn “Tester” kiên nhẫn chấm điểm mức độ giảm độ hỗn tạp $\Delta G$ — tức hiệu số giữa độ hỗn tạp của rổ ban đầu trừ đi độ hỗn tạp trung bình của các rổ con sau khi chia ($\Delta G = G_{\text{trước}} - G_{\text{sau}}$). Cách lựa nào mang lại $\Delta G$ lớn nhất (giúp rổ đậu sạch nhanh nhất) sẽ được chốt hạ, và chu trình cứ thế lặp lại cho đến khi các rổ đạt độ thuần khiết mong muốn (hoặc chạm ngưỡng dừng của cây).

Thước đo đứng sau chiếc máy chấm điểm ấy chính là độ hỗn tạp Gini (Gini Impurity). Bài viết này sẽ đi vào trực giác (intuition) tự nhiên để từng bước xây dựng nên công thức Gini.

---

1. Trực giác cốt lõi: Trò chơi đoán đậu của Cô Tấm

Để đo độ hỗn tạp của một rổ đậu, ta đặt ra trò chơi: nhắm mắt bốc ngẫu nhiên 1 hạt và đoán tên loại đậu dựa trên tỷ lệ thực tế. Độ hỗn tạp Gini chính là xác suất đoán sai.

Phiên bản 2 loại đậu ($K=2$)

Xét rổ chỉ trộn lẫn hai loại: Đậu Đen (tỷ lệ $p_1$) và Đậu Xanh (tỷ lệ $p_2 = 1 - p_1$):

• Xác suất đoán đúng (2 ô xanh trên đường chéo chính): $P(\text{Đoán đúng}) = p_1^2 + p_2^2$.
• Độ hỗn tạp Gini (xác suất đoán sai — biến cố bù):

$$ I = 1 - (p_1^2 + p_2^2) = p_1 p_2 + p_2 p_1 = 2p_1 p_2. $$

Nhìn vào bảng tiếp liên $2 \times 2$ ở cột bên phải, chỉ số Gini chính là tổng xác suất của 2 ô màu cam ngoài đường chéo (bốc nhầm Đen đoán Xanh: $p_1 p_2$, hoặc bốc Xanh đoán Đen: $p_2 p_1$). Khi rổ càng “thuần khiết” ($p_1 \to 1$ hoặc $p_1 \to 0$), 2 ô sai này co dần về $0$. Cực đại đạt được khi rổ chia đều $p_1 = p_2 = 0{,}5$, khi đó $I_{\max} = 2(0{,}5)(0{,}5) = 0{,}5$.

Phiên bản 3 loại đậu ($K=3$)

Giả sử rổ đậu có thêm Đậu Đỏ: gồm 3 loại Đậu Đen ($p_1$), Đậu Xanh ($p_2$), và Đậu Đỏ ($p_3$), thỏa mãn $p_1 + p_2 + p_3 = 1$.

Lúc này, toàn bộ không gian biến cố mở rộng thành bảng tiếp liên $3 \times 3$ gồm đúng 9 ô:

• 3 ô trên đường chéo chính (người chơi đoán đúng loại hạt):

$$ P(\text{Đoán đúng}) = p_1^2 + p_2^2 + p_3^2. $$

• 6 ô ngoài đường chéo (người chơi đoán sai — độ hỗn tạp Gini):

$$ I = 1 - (p_1^2 + p_2^2 + p_3^2) = 2(p_1 p_2 + p_1 p_3 + p_2 p_3) = \sum_{i \neq j} p_i p_j. $$

6 ô sai sót này phân bổ thành 3 cặp đối xứng qua đường chéo chính:

• Nhầm Đen — Xanh: $p_1 p_2 + p_2 p_1 = 2p_1 p_2$.
• Nhầm Đen — Đỏ: $p_1 p_3 + p_3 p_1 = 2p_1 p_3$.
• Nhầm Xanh — Đỏ: $p_2 p_3 + p_3 p_2 = 2p_2 p_3$.

Khi cả 3 loại hạt chia đều tỷ lệ ($p_1 = p_2 = p_3 = \frac{1}{3}$), độ hỗn tạp đạt cực đại:

$$ I_{\max} = 1 - 3 \times \left(\frac{1}{3}\right)^2 = 1 - \frac{1}{3} = \frac{2}{3} \approx 0{,}667. $$

---

2. Công thức tổng quát cho bài toán $K$ lớp

Mở rộng từ ma trận tiếp liên cho $K$ lớp với tỷ lệ $(p_1, \ldots, p_K)$ thỏa mãn $\sum_{k=1}^K p_k = 1$, tổng xác suất đoán đúng trên đường chéo chính là $\sum_{k=1}^K p_k^2$. Độ hỗn tạp Gini chính là phần bù — tổng xác suất đoán sai ở các ô ngoài đường chéo:

$$ G(t) = 1 - \sum_{k=1}^K p_k^2 = \sum_{k=1}^K p_k(1 - p_k) = \sum_{i \neq j} p_i p_j. $$

Nói cách khác, Gini chính là xác suất để hai phần tử rút ngẫu nhiên độc lập (có hoàn lại) từ nút $t$ mang hai nhãn khác nhau. Nút càng gần trạng thái thuần khiết (pure node), xác suất rút trúng hai nhãn khác nhau càng tiệm cận về $0$.

Giá trị cực đại của Gini theo số lớp $K$

Khi toàn bộ $K$ lớp xuất hiện với tỷ lệ đồng đều chằn chặn ($p_k = \frac{1}{K}, \forall k$), độ bất định đạt đỉnh:

$$ G_{\max} = 1 - \sum_{k=1}^K \left(\frac{1}{K}\right)^2 = 1 - K \cdot \frac{1}{K^2} = 1 - \frac{1}{K} = \frac{K - 1}{K}. $$

• Với $K = 2$: $G_{\max} = \frac{1}{2} = 0{,}500$.
• Với $K = 3$: $G_{\max} = \frac{2}{3} \approx 0{,}667$.
• Khi $K \to \infty$: $G_{\max} \to 1$.

Ba yêu cầu chuẩn mực của một thước đo độ hỗn tạp

Một hàm đo độ hỗn tạp $I(t) = f(p_1, \ldots, p_K)$ hợp lý trong cây quyết định cần đáp ứng ba yêu cầu chuẩn mực:

1. Thuần khiết tuyệt đối (Độ hỗn tạp bằng 0): Nếu nút chỉ chứa duy nhất một lớp (tồn tại một lớp $k$ có $p_k = 1$ và mọi $p_{j \neq k} = 0$), không còn bất kỳ sự mơ hồ nào về nhãn, độ hỗn tạp phải đạt cực tiểu: $I(t) = 0$.
2. Hỗn tạp cực đại: Nếu tất cả các lớp xuất hiện với tỷ lệ đồng đều chằn chặn ($p_1 = p_2 = \cdots = p_K = \frac{1}{K}$), độ hỗn tạp đạt mức cao nhất, $I(t)$ phải đạt giá trị cực đại $G_{\max} = \frac{K - 1}{K}$.
3. Tính đối xứng: Thứ tự đánh chỉ số các lớp không làm thay đổi bản chất của độ hỗn tạp: $f(\ldots, p_i, \ldots, p_j, \ldots) = f(\ldots, p_j, \ldots, p_i, \ldots)$.

Công thức Gini $G(t) = 1 - \sum_{k=1}^K p_k^2$ bắt nguồn từ trò chơi xác suất tự nhiên này thỏa mãn trọn vẹn cả ba điều kiện tiên đề nêu trên mà không cần bất kỳ giả định khiên cưỡng nào.

---

3. Trường hợp hai lớp ($K=2$) & Đồ thị Parabol

Xét bài toán phân loại nhị phân phổ biến với hai lớp $A$ và $B$. Đặt tỷ lệ lớp $A$ là $p$, khi đó tỷ lệ lớp $B$ là $1 - p$. Công thức Gini trở thành:

$$ G(p) = 1 - p^2 - (1 - p)^2 = 2p(1 - p). $$

Khảo sát hàm số $G(p) = 2p - 2p^2$ trên đoạn $[0, 1]$:

• Tại $p = 0$ (100% lớp B) hoặc $p = 1$ (100% lớp A): $G(0) = G(1) = 0$.
• Đạo hàm bậc nhất: $G’(p) = 2 - 4p = 0 \iff p = 0{,}5$.
• Giá trị cực đại: $G(0{,}5) = 2(0{,}5)(0{,}5) = 0{,}5$.
• Đạo hàm bậc hai: $G’’(p) = -4 < 0$, chứng minh $G(p)$ là một hàm lõm nghiêm ngặt (strictly concave).

Theo Bất đẳng thức Jensen, tính lõm nghiêm ngặt đảm bảo rằng độ hỗn tạp của phân phối gộp không bao giờ nhỏ hơn trung bình có trọng số của các phân phối thành phần: $G(\sum w_j p_j) \ge \sum w_j G(p_j)$. Đây là đặc tính toán học cốt lõi bảo đảm rằng việc phân chia dữ liệu thành các nhóm con thuần hơn sẽ không bao giờ làm tăng độ hỗn tạp kỳ vọng.

Gini vs. Sai số phân loại (Misclassification Error):
Dù cùng đo độ hỗn tạp của nút nhị phân (với tỷ lệ lớp đa số $p$), chúng đảm nhận hai vai trò hoàn toàn khác nhau:

• Sai số phân loại ($E = 1 - p$): Dùng để đánh giá độ chính xác hoặc cắt tỉa cành (pruning), nhưng ít nhạy cảm với sự thay đổi xác suất nên hiếm khi dùng để chọn điểm chia.
• Chỉ số Gini ($G = 2p(1 - p)$): Đo độ phân tán và giảm rất nhanh khi nút thuần hơn. Độ nhạy này biến Gini thành tiêu chí mặc định để quyết định chia nhánh (splitting).

Về mặt toán học, Gini luôn chặn trên sai số phân loại ($G \ge E$), và cả hai cùng bằng $0$ khi nút đạt độ thuần khiết tuyệt đối ($p = 0$ hoặc $p = 1$).

(Để đối chiếu chi tiết giữa ba thước đo độ hỗn tạp thông dụng và xem chứng minh toán học của bất đẳng thức chặn trên $E(t) \le G(t)$, bạn có thể đọc bài viết riêng: So sánh ba thước đo độ hỗn tạp: Gini, Entropy và Sai số phân loại.)

---

4. Tóm tắt

Khái niệm	Ý nghĩa cốt lõi
Bản chất xác suất	Xác suất phân loại sai khi rút ngẫu nhiên một quan sát và gán nhãn ngẫu nhiên theo phân phối của nút: $G(t) = 1 - \sum p_k^2$.
Dạng hai lớp	Parabol úp đối xứng: $G(p) = 2p(1-p)$, cực đại tại $p = 0{,}5$ với giá trị $0{,}5$.
Tính lõm & Jensen	$G’’(p) < 0$, bảo đảm việc phân chia dữ liệu thành các nhóm con không bao giờ làm tăng độ hỗn tạp kỳ vọng.
Chặn trên sai số	Luôn chặn trên sai số đa số: $E(t) \le G(t)$, cả hai cùng triệt tiêu về $0$ tại nút thuần khiết (pure node).
Ưu thế trong CART	Nhạy hơn sai số phân loại đa số ở hai biên và tính toán nhanh hơn Entropy vì tránh được hàm logarit.

Độ hỗn tạp Gini đóng vai trò là tiêu chí định lượng đơn giản để đánh giá chất lượng phân tách tại mỗi nút. Dựa trên tiêu chí này, thuật toán liên tục phân chia không gian đặc trưng để xây dựng Cây quyết định (Decision Tree), đồng thời làm cơ sở cho các mô hình kết hợp như Random Forest.

---

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 Advanced Books & Software.
• Trevor Hastie, Robert Tibshirani, Jerome Friedman (2009), The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd Edition, Springer (Chương 9.2: Tree-Based Methods).