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

Khi thuật toán cây phân loại CART (Classification and Regression Trees) đứng trước một tập dữ liệu, nhiệm vụ cốt lõi của nó là tìm ra một câu hỏi dạng $x_j \le s$ để tách các quan sát thành hai nhánh sao cho dữ liệu ở mỗi nhánh trở nên “ngăn nắp” hơn nút ban đầu.

Để máy tính tự động chọn được đặc trưng $x_j$ và ngưỡng chia $s$ tối ưu, ta cần một con số cụ thể trả lời câu hỏi: Nút này đang thuần khiết hay đang hỗn loạn, xáo trộn?

Thước đo chuẩn mực được sử dụng phổ biến nhất trong CART là độ hỗn tạp Gini (Gini Impurity hoặc Gini Index). Bài viết này sẽ phân tích nguồn gốc xác suất tự nhiên đằng sau công thức Gini, lý do vì sao dạng toán học của nó xuất hiện và cách nó định hướng các quyết định phân nhánh trong Cây quyết định và Random Forest.

---

1. Ta thực sự muốn đo lường điều gì?

Giả sử tại một nút $t$, ta có tập dữ liệu huấn luyện gồm các quan sát thuộc $K$ lớp khác nhau với tỷ lệ tương ứng là $(p_1, p_2, \ldots, p_K)$, thỏa mãn:

$$ \sum_{k=1}^K p_k = 1, \qquad p_k \ge 0. $$

Một hàm đo độ hỗn tạp $I(t) = f(p_1, \ldots, p_K)$ hợp lý cần đáp ứng ba yêu cầu trực quan:

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 (nghĩa là 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 loạn 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}$), độ bất định đạt mức cao nhất, $I(t)$ phải đạt giá trị cực đại.
3. Tính đối xứng: Thứ tự liệt kê các lớp không làm thay đổi bản chất của sự xáo trộn: $f(\ldots, p_i, \ldots, p_j, \ldots) = f(\ldots, p_j, \ldots, p_i, \ldots)$.

Độ hỗn tạp Gini không phải là một công thức được nghĩ ra ngẫu nhiên để thỏa mãn ba điều kiện trên, mà nó bắt nguồn trực tiếp từ một bài toán xác suất rất đẹp mắt.

---

2. Trực giác cốt lõi: Trò chơi gán nhãn ngẫu nhiên

Để định nghĩa độ hỗn tạp, hãy đặt ra một thí nghiệm tư duy:

Giả sử ta có một hộp đựng các quả bóng thuộc $K$ màu khác nhau với tỷ lệ $p_1, p_2, \ldots, p_K$. Ta nhắm mắt bốc ngẫu nhiên một quả bóng.

Sau đó, vì chưa được nhìn quả bóng, ta phải đoán màu của nó. Ta chọn chiến lược đoán ngẫu nhiên theo đúng phân phối thực nghiệm của hộp: tức là đoán quả bóng mang màu $k$ với xác suất đúng bằng $p_k$.

Hỏi: Xác suất ta đoán sai nhãn của quả bóng là bao nhiêu?

Ta tính xác suất đoán đúng trước:

• Xác suất bốc trúng bóng màu $k$ là $p_k$.
• Xác suất ta đoán quả bóng là màu $k$ cũng là $p_k$.
• Hai hành động này độc lập, nên xác suất bốc trúng màu $k$ và đoán đúng màu $k$ là:

$$ P(\text{Đúng màu } k) = p_k \times p_k = p_k^2. $$

Tổng xác suất đoán đúng trên tất cả $K$ màu là:

$$ P(\text{Đoán đúng}) = \sum_{k=1}^K p_k^2. $$

Do đó, xác suất ta đoán sai (phân loại nhầm) chính là biến cố bù:

$$ G(t) = 1 - P(\text{Đoán đúng}) = 1 - \sum_{k=1}^K p_k^2. $$

Đây chính là định nghĩa toán học của Độ hỗn tạp Gini (Gini Impurity).

Một góc nhìn tương đương: Rút hai quả bóng khác màu

Vì $\sum_{k=1}^K p_k = 1$, ta có thể viết:

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

Công thức này mang một ý nghĩa trực quan sâu sắc: Chỉ số 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 có nhãn khác nhau.

• Nếu nút chỉ có một màu ($p_1 = 1$): Rút hai quả luôn cùng màu $\implies G(t) = 0$.
• Nếu nút có nhiều màu trộn lẫn: Rút hai quả rất dễ gặp hai màu khác nhau $\implies G(t)$ tăng cao.

---

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

---

4. Đánh giá một phép chia: Gini Gain & Bất đẳng thức Jensen

Khi xây dựng cây, tại nút cha $t$ có $n_t$ quan sát, thuật toán thử một điều kiện chia $x_j \le s$ để tách thành hai nút con:

• Nút trái $L$: gồm $n_L$ quan sát với độ hỗn tạp $G(L)$.
• Nút phải $R$: gồm $n_R$ quan sát với độ hỗn tạp $G(R)$.

Độ hỗn tạp trung bình có trọng số sau khi chia được tính bởi:

$$ G_{\text{sau}} = \frac{n_L}{n_t} G(L) + \frac{n_R}{n_t} G(R). $$

Mức giảm độ hỗn tạp (thường gọi là Gini Gain hay Impurity Reduction) là:

$$ \Delta G = G(t) - G_{\text{sau}}. $$

Thuật toán CART sẽ quét qua tất cả các đặc trưng $x_j$ và tất cả các ngưỡng $s$ khả dĩ, rồi chọn cặp $(j, s)$ mang lại $\Delta G$ lớn nhất.

Vì sao phép chia không bao giờ làm tăng độ hỗn tạp kỳ vọng?

Tỷ lệ lớp ở nút cha $p_t$ là trung bình có trọng số của tỷ lệ lớp ở hai nút con:

$$ p_t = \frac{n_L}{n_t} p_L + \frac{n_R}{n_t} p_R. $$

Vì $G(p)$ là hàm lõm nghiêm ngặt ($G’’(p) < 0$), theo Bất đẳng thức Jensen:

$$ G\left(\frac{n_L}{n_t} p_L + \frac{n_R}{n_t} p_R\right) \ge \frac{n_L}{n_t} G(p_L) + \frac{n_R}{n_t} G(p_R). $$

Tức là:

$$ G(t) \ge G_{\text{sau}} \iff \Delta G \ge 0. $$

Dấu đẳng thức $\Delta G = 0$ chỉ xảy ra khi $p_L = p_R = p_t$ (nghĩa là phép chia hoàn toàn vô dụng, không làm thay đổi phân phối ở hai nhánh). Kết quả này đảm bảo cây quyết định luôn tiến về trạng thái thuần khiết hơn sau mỗi bước chia hợp lý.

---

5. So sánh: Gini Impurity, Entropy và Sai số Đa số

Tại sao các nhà sáng lập CART không dùng trực tiếp Sai số phân loại đa số (Misclassification Error), mà lại dùng Gini? Và Gini khác gì so với Entropy của Shannon?

Tiêu chí	Gini Impurity $G(p)$	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/cộng)	Nặng hơn (hàm logarit)	Rất nhẹ

1. Điểm mù của Sai số đa số $E(p)$

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:

• 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 đạt độ thuần khiết $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 trường hợp chia $(400A, 400B) \to (300A, 100B) + (100A, 300B)$, $E(p)$ không phân biệt được với một phép chia giữ nguyên tỷ lệ nhãn ở từng lá. Nhờ đạo hàm dốc đứng ở hai đầu $p \to 0$ và $p \to 1$, Gini “thưởng điểm” rất cao cho các phép chia tạo ra ít nhất một nhánh thuần khiết.

2. Gini chính là xấp xỉ Taylor bậc 1 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). $$

Đây là một phát hiện toán học vô cùng thanh lịch: Gini Impurity chính là phiên bản xấp xỉ tuyến tính bậc một của Entropy! Nó mang lại hành vi phân tách gần như tương đương với Entropy nhưng không đòi hỏi máy tính phải gọi hàm $\log_2$ hàng triệu lần khi duyệt qua mọi điểm chia trên tập dữ liệu lớn.

---

6. Phân biệt: Gini Impurity (CART) và Hệ số Gini (Kinh tế học)

Một nhầm lẫn rất phổ biến giữa những người học thống kê và khoa học dữ liệu là đồng nhất Độ hỗn tạp Gini trong máy học với Hệ số Gini (Gini Coefficient) trong kinh tế học:

• Hệ số Gini kinh tế (Corrado Gini, 1912): Đo lường mức độ bất bình đẳng thu nhập hoặc tài sản trong một quần thể, dựa trên diện tích nằm giữa đường cong Lorenz và đường phân phối hoàn hảo. Giá trị dao động từ $0$ (bình đẳng tuyệt đối) đến $1$ (bất bình đẳng tuyệt đối).
• Độ hỗn tạp Gini trong CART (Breiman et al., 1984): Đo lường xác suất phân loại sai trên phân phối xác suất rời rạc của các lớp trong một nút của cây quyết định. Giá trị cho bài toán 2 lớp dao động từ $0$ (thuần khiết tuyệt đối) đến $0{,}5$ (hỗn tạp tối đa).

Mặc dù cả hai đều mang tên nhà thống kê người Ý Corrado Gini vì cùng kế thừa triết lý đo mức độ phân tán/tập trung của một phân phối, công thức cụ thể và bài toán ứng dụng của chúng là hoàn toàn riêng biệt.

---

7. 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$.
Gini Gain	$\Delta G = G(t) - \left[\frac{n_L}{n_t}G(L) + \frac{n_R}{n_t}G(R)\right] \ge 0$, luôn bảo đảm phép chia không làm tăng độ hỗn tạp kỳ vọng.
Ư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 là viên gạch toán học nền tảng tạo nên sức mạnh cho các mô hình dạng cây. Từ cơ chế chọn ngưỡng đơn giản này, cây có thể liên tục phân tách không gian đặc trưng để tạo thành Cây quyết định (Decision Tree) hoàn chỉnh, và làm cơ sở cho hàng trăm cây cùng bỏ phiếu trong 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).
• Corrado Gini (1912), Variabilità e mutabilità, Reprinted in Memorie di metodologica statistica (Ed. E. Pizetti, T. Salvemini).