Bỏ qua đến nội dung chính
Mục lục

Gini impurity, entropy và information gain của cây

AIDev Team · duyệt: Nguyễn Việt Chung

Bài 2/8 · Chương 12

Toán vừa đủ cho Machine Learning

  • 8 phút
  • Trung cấp
  • Python 3.14
  • Cập nhật

Information gain (độ lợi thông tin) của một lần chia là entropy của nút cha trừ đi trung bình có trọng số của entropy hai nhánh con, trọng số là tỉ lệ số dòng rơi vào mỗi nhánh. Cây quyết định thử từng cột và từng ngưỡng, rồi chọn lần chia có information gain lớn nhất. Gini impurity cũng chấm theo cách đó, chỉ thay entropy bằng một độ đo khác.

Cần biết trước: decision tree và trung bình có trọng số.

Entropy của một nút

Mười hội viên Sóc Vàng, ghi số tuần liên tiếp không mở app (tuan_vang) và có hủy gói ở kỳ sau không (huy). Bốn người hủy, sáu người ở lại. Entropy của nút đo độ lẫn lộn của nhãn: với tỉ lệ từng lớp p₁, p₂, …, entropy là H = −Σ pₖ · log₂ pₖ. Nút chỉ có một lớp có entropy 0. Nút chia đều hai lớp có entropy 1, mức lẫn lộn cao nhất với hai lớp.

Nút gốc có p = 0,4 (hủy) và 0,6 (ở):

Bước

Việc

Kết quả

1

0,4 · log₂ 0,4

0,4 · (−1,3219) = −0,5288

2

0,6 · log₂ 0,6

0,6 · (−0,7370) = −0,4422

3

Đổi dấu tổng

0,971

Gini impurity của cùng nút là 1 − Σ pₖ², tức 1 − 0,16 − 0,36 = 0,48. Hai độ đo khác thang (entropy tới 1, Gini tới 0,5 với hai lớp) nhưng cùng chiều: nút càng thuần thì cả hai càng nhỏ.

Information gain của một lần chia

Thử chia ở tuan_vang <= 2. Nhánh trái có 6 hội viên, 1 hủy. Nhánh phải có 4 hội viên, 3 hủy.

IG=H(S)−∑knknH(Sk)IG = H(S) - \sum_{k} \frac{n_k}{n} H(S_k)

Trong đó:

  • S (huy): nhãn của nút cha, n dòng.

  • S với chỉ số k (huy[trai], huy[~trai]): nhãn của nhánh con thứ k.

  • n với chỉ số k (trai.sum()): số dòng của nhánh k; số dòng của nhánh chia cho n chính là w hay 1 - w.

  • H (entropy()): entropy của một nhóm nhãn.

  • IG: information gain của lần chia.

Bước

Việc

Kết quả

1

Entropy nhánh trái, p = 1/6

0,650

2

Entropy nhánh phải, p = 3/4

0,811

3

Trung bình có trọng số: 0,6 · 0,650 + 0,4 · 0,811

0,715

4

IG = 0,971 − 0,715

0,256

python
import numpy as np

def entropy(nhan):
    _, dem = np.unique(nhan, return_counts=True)
    p = dem / dem.sum()
    return -(p * np.log2(p)).sum()

huy = np.array([0, 0, 0, 1, 0, 0, 1, 1, 0, 1])
tuan_vang = np.array([0, 1, 1, 2, 2, 2, 3, 4, 5, 6])
trai = tuan_vang <= 2
w = trai.mean()
con = w * entropy(huy[trai]) + (1 - w) * entropy(huy[~trai])
print("trái:", entropy(huy[trai]).round(4))
print("phải:", entropy(huy[~trai]).round(4))
print("IG:", (entropy(huy) - con).round(4))

KẾT QUẢ

trái: 0.65
phải: 0.8113
IG: 0.2564

np.unique(..., return_counts=True) đếm từng lớp, np.log2 là log cơ số 2 (xem hàm toán học NumPy), chia cho tổng ra tỉ lệ. Hàm chỉ thấy các lớp có mặt, nên không bao giờ gặp log₂ 0. w = trai.mean() là tỉ lệ dòng sang trái vì True được đếm là 1. Đổi trai = tuan_vang <= 2 thành trai = tuan_vang <= 1 rồi chạy lại: dòng cuối in IG: 0.2813, một ngưỡng tốt hơn.

Cây thử mọi ngưỡng

Cây không đoán ngưỡng mà thử từng điểm giữa hai giá trị liền kề của cột. Cùng hàm entropy() ở trên, chạy qua sáu ngưỡng:

python
import numpy as np

def entropy(nhan):
    _, dem = np.unique(nhan, return_counts=True)
    p = dem / dem.sum()
    return -(p * np.log2(p)).sum()

huy = np.array([0, 0, 0, 1, 0, 0, 1, 1, 0, 1])
tuan_vang = np.array([0, 1, 1, 2, 2, 2, 3, 4, 5, 6])
for nguong in [0.5, 1.5, 2.5, 3.5, 4.5, 5.5]:
    trai = tuan_vang <= nguong
    w = trai.mean()
    con = w * entropy(huy[trai]) + (1 - w) * entropy(huy[~trai])
    print(nguong, (entropy(huy) - con).round(4))

KẾT QUẢ

0.5 0.079
1.5 0.2813
2.5 0.2564
3.5 0.0913
4.5 0.0074
5.5 0.1445

Ngưỡng 1,5 thắng: nhánh trái gồm ba hội viên đều ở lại, entropy 0. Gini của một lần chia tính cùng kiểu, trung bình có trọng số Gini hai nhánh. Với hai ngưỡng dẫn đầu, mỗi dòng in ngưỡng, Gini nút cha và Gini của lần chia:

python
import numpy as np

def gini(nhan):
    _, dem = np.unique(nhan, return_counts=True)
    p = dem / dem.sum()
    return 1 - (p ** 2).sum()

huy = np.array([0, 0, 0, 1, 0, 0, 1, 1, 0, 1])
tuan_vang = np.array([0, 1, 1, 2, 2, 2, 3, 4, 5, 6])
for nguong in [1.5, 2.5]:
    trai = tuan_vang <= nguong
    w = trai.mean()
    chia = w * gini(huy[trai]) + (1 - w) * gini(huy[~trai])
    print(nguong, round(gini(huy), 4), round(chia, 4))

KẾT QUẢ

1.5 0.48 0.3429
2.5 0.48 0.3167

Gini thích ngưỡng 2,5 hơn (giảm từ 0,48 xuống 0,3167), còn entropy thích 1,5. Hai tiêu chí thường chọn giống nhau, nhưng với dữ liệu nhỏ như mười dòng này chúng có thể lệch.

Kiểm lại với DecisionTreeClassifier

criterion="entropy" bảo sklearn chấm bằng entropy cơ số 2, max_depth=1 giữ đúng một lần chia. Bảng có thêm cột dung_ma (có dùng mã giảm giá tháng trước) để cây phải chọn giữa hai cột:

python
import pandas as pd
from sklearn.tree import DecisionTreeClassifier, export_text

bang = pd.DataFrame({
    "tuan_vang": [0, 1, 1, 2, 2, 2, 3, 4, 5, 6],
    "dung_ma": [1, 1, 0, 0, 1, 0, 1, 0, 1, 0],
    "huy": [0, 0, 0, 1, 0, 0, 1, 1, 0, 1],
})
X, y = bang[["tuan_vang", "dung_ma"]], bang["huy"]
cay = DecisionTreeClassifier(criterion="entropy", max_depth=1,
                             random_state=0).fit(X, y)
ten = list(X.columns)
print(export_text(cay, feature_names=ten, show_weights=True))
print(cay.tree_.impurity.round(4))

KẾT QUẢ

|--- tuan_vang <= 1.50
|   |--- weights: [3.00, 0.00] class: 0
|--- tuan_vang >  1.50
|   |--- weights: [3.00, 4.00] class: 1

[0.971  0.     0.9852]

Cây chọn đúng ngưỡng 1,5. tree_.impurity liệt kê entropy theo thứ tự nút gốc, nhánh trái, nhánh phải. Số 0,971 khớp bảng tính tay của nút gốc, 0 là nhánh trái thuần, còn 0,9852 là entropy của nhánh phải gồm 3 dòng ở lại và 4 dòng hủy. Cột dung_ma chỉ cho information gain 0,1245 nên thua. Bỏ criterion="entropy" thì cây dùng Gini mặc định và chia ở 2,5.

Kiểm tra nhanh

  1. Sau import numpy as np, print(-(np.array([0.5, 0.5]) * np.log2([0.5, 0.5])).sum()) in ra gì?

    • 1.0
    • 0.5
    • 0.6931471805599453
  2. Vì sao entropy của hai nhánh được lấy trung bình có trọng số theo số dòng?

    • Để nhánh chứa nhiều hội viên ảnh hưởng nhiều hơn nhánh chứa ít
    • Để kết quả luôn nằm từ 0 tới 1
    • Vì sklearn không biết số dòng của từng nhánh
  3. Những câu nào đúng về entropy và Gini của mười hội viên?

    • Nút gốc 4 hủy, 6 ở có entropy 0,971 và Gini 0,48
    • Entropy chọn ngưỡng 1,5, Gini chọn ngưỡng 2,5
    • Information gain có thể âm khi chia sai cột
    • Nhánh có ba hội viên đều ở lại có entropy 1
  4. Trong khung bẫy, vì sao kết quả là −23,5?

    • Vì log₂ của số âm
    • Vì value_counts() trả số đếm 6 và 4, không phải tỉ lệ
    • Vì nhãn phải là chuỗi
Đúng hết lần đầu +15 XP

Bài tập

Information gain của một lần chia

nhan là list nhãn của một nút (số hay chuỗi). sang_trai là list True/False cùng độ dài: True nghĩa là dòng đó đi sang nhánh trái. Mỗi nhánh có ít nhất một dòng.

Viết thân hàm loi_thong_tin(nhan, sang_trai): tính entropy cơ số 2 của nút cha và hai nhánh, rồi trả về information gain theo công thức của bài. Không dùng DecisionTreeClassifier.

Hàm không sửa nhan, sang_trai của nơi gọi.

Trả về: information gain, một float.

Ví dụ: với cột huy của mười hội viên và sang_trai là tuan_vang <= 2 (sáu True đầu, bốn False sau), hàm trả về khoảng 0.2564.

python
import numpy as np

def loi_thong_tin(nhan, sang_trai):
    pass  # Viết thân hàm thay cho dòng này

Tóm tắt

  • Entropy của một nút là −Σ pₖ · log₂ pₖ: 0 khi thuần, 1 khi hai lớp chia đều.

  • Gini impurity là 1 − Σ pₖ², tối đa 0,5 với hai lớp.

  • Information gain = entropy nút cha − trung bình có trọng số entropy hai nhánh, trọng số là tỉ lệ số dòng.

  • Gini của một lần chia cũng là trung bình có trọng số Gini hai nhánh.

  • Cây thử từng ngưỡng của từng cột và chọn lần chia tốt nhất; entropy và Gini có thể chọn khác nhau.

  • tree_.impurity cho entropy hay Gini của từng nút để kiểm lại số tính tay.

Câu hỏi thường gặp

Information gain là gì trong cây quyết định?

Là mức giảm entropy khi chia một nút thành hai nhánh, tính bằng entropy nút cha trừ trung bình có trọng số entropy hai nhánh. Ở mười hội viên, chia tại tuan_vang <= 1.5 cho 0,2813, cao hơn mọi ngưỡng khác, nên cây chọn lần chia đó.

Nên chọn criterion gini hay entropy?

Gini là mặc định của DecisionTreeClassifier. Trên dữ liệu lớn hai tiêu chí hiếm khi đổi kết quả nhiều. Coi criterion là một siêu tham số và chọn bằng cross validation như bài GridSearchCV, đừng chọn bằng tập test.

Entropy decision tree dùng log cơ số mấy?

sklearn dùng log cơ số 2, nên entropy hai lớp chia đều là 1. Đổi sang log tự nhiên chỉ nhân mọi entropy với cùng hằng số ln 2, nên thứ tự các lần chia và ngưỡng được chọn không đổi.

Information gain có thiên vị cột nhiều giá trị không?

Có, với cây chia nhiều nhánh: một cột như mã hội viên chia mỗi dòng một nhánh, entropy các nhánh bằng 0 và gain cao nhất dù vô dụng. Cây của sklearn chỉ chia đôi nên đỡ hơn, nhưng cột số nhiều ngưỡng vẫn dễ được chọn. Bài permutation importance giải thích vì sao feature_importances_ của cây nên đọc thận trọng.

Chủ đề

information gain

Bài này có hữu ích?

Hỏi đáp

Đang tải câu hỏi…

Tham vấn chuyên môn

Nguyễn Việt Chung

Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE

  • Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
  • Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
  • Xây hệ thống AI cho doanh nghiệp tại VietPlatform.
Biên soạn: AIDev Team · Rà soát · Quy trình biên tập