Cây quyết định và ID3
Cây quyết định là một trong những mô hình học máy dễ hiểu nhất, vì kết quả của nó chính là một chuỗi câu hỏi có hoặc không, đúng như cách con người ra quyết định hằng ngày. Bạn có mang ô đi làm không? Nếu trời nhiều mây thì có; nếu trời quang thì xem dự báo có mưa không; cứ thế đi xuống cho tới khi ra một câu trả lời dứt khoát. Mô hình này không cho ra một công thức toán bí ẩn mà cho ra một sơ đồ rẽ nhánh ai cũng đọc được, nên nó được ưa dùng ở những nơi cần giải thích vì sao máy quyết định như vậy.
Trong bài này ta tìm hiểu cách máy tự xây cây đó từ dữ liệu, thông qua thuật toán kinh điển ID3 và hai khái niệm lõi của nó: entropy và độ lợi thông tin.
Thử ngay: chia nút và xem độ lợi thông tin
Nói gọn trước khi đi vào chi tiết: entropy đo độ hỗn tạp về nhãn của một nhóm dữ liệu, càng gần 0 thì nhóm càng thuần nhất; độ lợi thông tin là phần entropy giảm được nhờ chia nhóm theo một đặc trưng. Bạn hãy tự tay thử chia nút bằng công cụ dưới đây. Bấm chọn từng đặc trưng để xem dữ liệu tách thành các nhánh ra sao, entropy mỗi nhánh, entropy trung bình có trọng số, và độ lợi thông tin thu được. Đặc trưng cho độ lợi cao nhất được đánh dấu là lựa chọn tốt nhất. Công cụ mở ra với đúng bảng 14 dòng in ở phần dưới, nhưng bạn có thể mở mục dữ liệu để tắt bớt vài dòng và xem entropy cùng độ lợi đổi theo.
Dữ liệu: đang dùng 14/14 dòng. Bấm để bật hoặc tắt từng dòng.
| Dùng | # | Trời | Độ ẩm | Gió | Chơi |
|---|---|---|---|---|---|
| 1 | Nắng | Cao | Nhẹ | Không | |
| 2 | Nắng | Cao | Mạnh | Không | |
| 3 | Âm u | Cao | Nhẹ | Có | |
| 4 | Mưa | Cao | Nhẹ | Có | |
| 5 | Mưa | Vừa | Nhẹ | Có | |
| 6 | Mưa | Vừa | Mạnh | Không | |
| 7 | Âm u | Vừa | Mạnh | Có | |
| 8 | Nắng | Cao | Nhẹ | Không | |
| 9 | Nắng | Vừa | Nhẹ | Có | |
| 10 | Mưa | Vừa | Nhẹ | Có | |
| 11 | Nắng | Vừa | Mạnh | Có | |
| 12 | Âm u | Cao | Mạnh | Có | |
| 13 | Âm u | Vừa | Nhẹ | Có | |
| 14 | Mưa | Cao | Mạnh | Không |
Ý tưởng cây quyết định
Một cây quyết định gồm ba loại thành phần. Mỗi nút trong hỏi về một đặc trưng, ví dụ "trời thế nào". Mỗi nhánh đi ra từ nút ứng với một giá trị của đặc trưng đó, ví dụ nắng, âm u, mưa. Mỗi lá ở cuối cây cho ra một nhãn dự đoán cuối cùng, ví dụ có chơi hoặc không chơi. Để phân loại một mẫu mới, ta xuất phát từ gốc, trả lời câu hỏi ở mỗi nút, đi theo nhánh tương ứng, và dừng lại khi tới một lá.
Câu hỏi khó nhất khi xây cây không phải là cách đi xuống cây, mà là: ở mỗi nút, nên hỏi về đặc trưng nào trước? Nếu hỏi đúng đặc trưng quan trọng, dữ liệu sẽ tách nhanh thành các nhóm rõ ràng và cây gọn. Nếu hỏi nhầm đặc trưng vô nghĩa, cây phình to mà chẳng tách được gì. ID3 đưa ra một câu trả lời cụ thể cho câu hỏi này.
Thuật toán ID3 (viết tắt của Iterative Dichotomiser 3) dùng một nguyên tắc tham lam: ở mỗi nút, chọn đặc trưng nào chia dữ liệu thành các nhóm thuần nhất nhất, tức là mỗi nhóm con càng đồng nhất về nhãn càng tốt. Một nhóm mà mọi mẫu cùng một nhãn là nhóm lý tưởng, vì khi tới đó ta đã biết chắc câu trả lời. Để đo được khái niệm "thuần nhất" này thành một con số, ID3 mượn đại lượng entropy từ lý thuyết thông tin.
Entropy đo độ hỗn loạn
Entropy đo mức độ hỗn loạn, hay bất định, của một tập dữ liệu xét theo nhãn. Trực giác rất đơn giản. Một tập mà mọi mẫu cùng một nhãn thì hoàn toàn thuần nhất, không còn gì để đoán, nên entropy bằng 0. Một tập mà các nhãn chia đều năm mươi năm mươi thì khó đoán nhất, nên entropy đạt cực đại.
Với một tập S mà các nhãn xuất hiện theo tỉ lệ p_1, p_2, ..., p_k, entropy được định nghĩa là tổng có dấu trừ của mỗi tỉ lệ nhân với logarit cơ số 2 của chính nó:
H(S) = -sum(p_i * log2(p_i)) với i chạy từ 1 đến k
Trong đó p_i là tỉ lệ mẫu mang nhãn thứ i, và ta quy ước 0 * log2(0) = 0 để công thức không bị vô nghĩa khi một nhãn vắng mặt. Đơn vị của entropy là bit.
Với bài toán hai nhãn (có và không), đặt p là tỉ lệ nhãn có, công thức rút gọn lại còn:
H = -p * log2(p) - (1 - p) * log2(1 - p)
Khi p = 0 hoặc p = 1 thì H = 0, tập thuần nhất. Khi p = 0.5 thì H = 1, giá trị lớn nhất, tập hỗn loạn nhất. Điều này đúng với trực giác: chia đều là tình huống khó đoán nhất.
Logarit cơ số 2 khiến entropy được đo bằng bit, tức số câu hỏi có hoặc không trung bình cần để xác định nhãn. Tập càng hỗn loạn thì càng cần nhiều câu hỏi, nên entropy càng cao. Đây là cách diễn giải trực quan cho con số này.
Ví dụ tập chơi quần vợt
Ta dùng tập dữ liệu kinh điển sau xuyên suốt phần còn lại của bài. Mỗi hàng là một ngày, với ba đặc trưng thời tiết và một nhãn cho biết hôm đó có đi chơi quần vợt hay không. Tập có 14 mẫu.
| Trời | Độ ẩm | Gió | Chơi |
|---|---|---|---|
| Nắng | Cao | Nhẹ | Không |
| Nắng | Cao | Mạnh | Không |
| Âm u | Cao | Nhẹ | Có |
| Mưa | Cao | Nhẹ | Có |
| Mưa | Vừa | Nhẹ | Có |
| Mưa | Vừa | Mạnh | Không |
| Âm u | Vừa | Mạnh | Có |
| Nắng | Cao | Nhẹ | Không |
| Nắng | Vừa | Nhẹ | Có |
| Mưa | Vừa | Nhẹ | Có |
| Nắng | Vừa | Mạnh | Có |
| Âm u | Cao | Mạnh | Có |
| Âm u | Vừa | Nhẹ | Có |
| Mưa | Cao | Mạnh | Không |
Đếm nhãn trong tập gốc: có 9 ngày chơi và 5 ngày không chơi. Vậy p_co = 9/14 và p_khong = 5/14. Entropy của tập gốc là:
H(S) = -(9/14) * log2(9/14) - (5/14) * log2(5/14)
~ 0.940 bit
Con số gần 1 cho thấy tập gốc khá hỗn loạn, hai nhãn xen kẽ, chưa lộ ra quy luật rõ ràng. Mục tiêu của ID3 là chọn đặc trưng giúp giảm entropy này nhiều nhất.
Độ lợi thông tin chọn đặc trưng
Khi ta dùng một đặc trưng A để chia tập S thành các tập con theo từng giá trị của A, mỗi tập con thường thuần nhất hơn tập cha, nên entropy trung bình giảm xuống. Phần entropy giảm đi nhờ phép chia này gọi là độ lợi thông tin (information gain). ID3 chọn đặc trưng có độ lợi thông tin lớn nhất, vì đó là đặc trưng giải thích được nhiều bất định nhất.
Độ lợi thông tin của đặc trưng A trên tập S được tính bằng entropy của tập cha trừ đi entropy trung bình có trọng số của các tập con sau khi chia:
IG(S, A) = H(S) - sum_v( |S_v| / |S| * H(S_v) )
Trong đó S_v là tập con gồm các mẫu có giá trị A = v, còn |S_v| / |S| là trọng số theo kích thước tập con đó. Số hạng tổng chính là entropy trung bình sau khi chia: tập con nào lớn thì đóng góp nhiều, tập con nào nhỏ thì đóng góp ít.
Tính độ lợi cho đặc trưng Trời
Đặc trưng Trời có ba giá trị, ta chia tập gốc thành ba nhóm.
- Nhóm Nắng gồm 5 mẫu: 2 có và 3 không, nên
H ~ 0.971. - Nhóm Âm u gồm 4 mẫu: cả 4 đều có, hoàn toàn thuần nhất, nên
H = 0. - Nhóm Mưa gồm 5 mẫu: 3 có và 2 không, nên
H ~ 0.971.
Entropy trung bình có trọng số sau khi chia theo Trời:
(5/14) * 0.971 + (4/14) * 0 + (5/14) * 0.971 ~ 0.694
Vậy độ lợi thông tin của Trời:
IG(S, Troi) = 0.940 - 0.694 ~ 0.246 bit
Tính tương tự cho hai đặc trưng còn lại, độ ẩm cho độ lợi khoảng 0.151 và gió cho khoảng 0.048. Đặc trưng Trời có độ lợi lớn nhất, nên ID3 chọn Trời làm nút gốc của cây.
Một lưu ý nhỏ để bạn khỏi bối rối khi đối chiếu: các phép tính tay ở trên làm tròn từng bước trung gian về ba chữ số, nên kết quả lệch một đơn vị ở chữ số cuối. Tính đủ độ chính xác thì Trời cho 0.247 và độ ẩm cho 0.152, đúng bằng những gì widget ở đầu bài và đoạn mã Python bên dưới in ra. Sai lệch này không hề đổi thứ hạng, Trời vẫn cao nhất.
Một hiểu nhầm thường gặp là cứ đặc trưng nào cho độ lợi thông tin cao thì đặc trưng đó tốt. Thực ra độ lợi thông tin nghiêng về những đặc trưng có nhiều giá trị khác nhau. Hãy tưởng tượng thêm cột mã số ngày vào tập dữ liệu: mỗi giá trị chỉ ứng với đúng một mẫu, nên chia theo cột đó cho ra toàn nhóm thuần nhất và độ lợi đạt cực đại, dù cột này chẳng mang chút ý nghĩa dự đoán nào. Biến thể C4.5 khắc phục bằng tỉ lệ độ lợi (gain ratio), tức chia độ lợi cho một số hạng phạt các đặc trưng quá nhiều nhánh, để không bị đánh lừa bởi những cột giống như mã định danh.
Xây tiếp các nhánh
Sau khi chọn Trời làm gốc, nhánh Âm u đã thuần nhất hoàn toàn (4 mẫu đều là có), nên nó trở thành ngay một lá nhãn có, không cần hỏi gì thêm. Hai nhánh Nắng và Mưa vẫn còn hỗn loạn, nên ID3 lặp lại đúng quy trình trên từng tập con: tính lại entropy của tập con, tính độ lợi của các đặc trưng còn lại, chọn đặc trưng tốt nhất làm nút tiếp theo.
Trên nhánh Nắng, hóa ra độ ẩm tách hoàn hảo: ẩm cao thì luôn không chơi, ẩm vừa thì luôn chơi. Trên nhánh Mưa, gió tách hoàn hảo: gió nhẹ thì chơi, gió mạnh thì không. Cây kết quả rút gọn như sau:
Troi?
├── Nang -> Do am? ── Cao -> Khong
│ └─ Vua -> Co
├── Am u -> Co
└── Mua -> Gio? ── Nhe -> Co
└─ Manh -> Khong
Quá trình dừng khi một nhánh đã thuần nhất, hoặc khi hết đặc trưng để hỏi. ID3 chỉ là chiến lược tham lam chọn đặc trưng tốt nhất tại mỗi bước; nó không bảo đảm cho ra cây nhỏ nhất có thể trên toàn cục, nhưng nhanh và cho cây dễ giải thích.
ID3 nguyên bản chỉ làm việc với đặc trưng rời rạc. Thuật toán C4.5 kế thừa trực tiếp ID3, còn CART là một dòng thuật toán cây phát triển độc lập; cả hai đều xử lý được đặc trưng số (chia theo ngưỡng), giá trị thiếu, và bổ sung cơ chế cắt tỉa. Thư viện scikit-learn cài đặt CART qua lớp DecisionTreeClassifier.
Quá khớp và cắt tỉa
Cây quyết định có một điểm yếu cố hữu: nếu cứ chia mãi cho tới khi mọi lá hoàn toàn thuần nhất, cây sẽ học thuộc lòng từng mẫu huấn luyện, kể cả những mẫu nhiễu hay cá biệt. Một cây như vậy đạt độ chính xác gần như tuyệt đối trên tập huấn luyện nhưng dự đoán kém trên dữ liệu mới. Hiện tượng này gọi là quá khớp (overfitting): mô hình bám quá sát dữ liệu đã thấy thay vì học quy luật chung.
Với cây quyết định, dấu hiệu quá khớp thường là cây quá sâu, có những nhánh chỉ phục vụ một hai mẫu. Cách chống lại là cắt tỉa (pruning): bớt đi những nhánh đóng góp ít vào khả năng dự đoán. Có hai hướng cắt tỉa. Cắt tỉa trước (pre-pruning) dừng chia sớm khi tập con đã đủ nhỏ hoặc độ lợi quá thấp. Cắt tỉa sau (post-pruning) xây cây đầy đủ rồi gộp ngược các nhánh không cải thiện độ chính xác trên một tập kiểm tra riêng.
Hai liều thuốc chung cho mọi mô hình là giữ mô hình đủ đơn giản và thu thập thêm dữ liệu. Với cây quyết định cụ thể, giới hạn độ sâu tối đa hoặc số mẫu tối thiểu ở mỗi lá là cách cắt tỉa trước đơn giản và hiệu quả.
Bất ổn định và rừng ngẫu nhiên
Cây quyết định còn một điểm yếu ít người để ý: nó rất nhạy với thay đổi nhỏ của dữ liệu. Chỉ cần thêm bớt vài mẫu hay đổi một giá trị nằm gần ranh giới, đặc trưng được chọn ở nút gốc có thể đổi khác, kéo theo toàn bộ cây bên dưới rẽ theo một hướng mới. Nói theo ngôn ngữ thiên lệch và phương sai, một cây sâu để mọc tự do có phương sai cao: huấn luyện lại trên một mẫu dữ liệu chỉ khác đôi chút cũng cho ra một cây khác hẳn.
Rừng ngẫu nhiên (random forest) ra đời để chữa đúng bệnh này. Ý tưởng là gộp nhiều cây thay vì tin vào một cây duy nhất. Mỗi cây được huấn luyện trên một tập con lấy mẫu ngẫu nhiên có hoàn lại từ dữ liệu gốc, và tại mỗi nút chỉ được xét một tập con ngẫu nhiên của các đặc trưng thay vì toàn bộ. Nhờ vậy các cây khác nhau đủ để sai theo những kiểu khác nhau. Khi dự đoán, rừng lấy biểu quyết đa số của các cây cho bài toán phân loại, hoặc lấy trung bình cho hồi quy. Trung bình nhiều dự đoán lệch theo kiểu khác nhau làm phương sai giảm mạnh mà không đẩy thiên lệch tăng theo, nên rừng thường chính xác và ổn định hơn hẳn một cây đơn. Cái giá phải trả là mất tính dễ diễn giải: một cây ta còn đọc được từng câu hỏi, còn một rừng vài trăm cây thì không còn nhìn ra một sơ đồ gọn để giải thích nữa.
Mã nguồn Python
Đoạn mã sau cài đặt ba viên gạch lõi của ID3: tính entropy của một danh sách nhãn, tính độ lợi thông tin của một đặc trưng, và chọn đặc trưng tốt nhất để chia. Đây chính là phần lõi mà một thuật toán dựng cây đầy đủ sẽ gọi đệ quy. Mã chỉ dùng thư viện chuẩn, không cần numpy.
import math
from collections import Counter
def entropy(labels):
# Shannon entropy in bits of a list of labels
n = len(labels)
if n == 0:
return 0.0
counts = Counter(labels)
total = 0.0
for c in counts.values():
p = c / n
total -= p * math.log2(p) # convention: 0 * log2(0) = 0
return total
def information_gain(rows, feature, target):
# rows: list of dicts; feature/target are column keys
base = entropy([r[target] for r in rows])
n = len(rows)
weighted = 0.0
values = set(r[feature] for r in rows)
for v in values: # split by feature value
subset = [r for r in rows if r[feature] == v]
weight = len(subset) / n
weighted += weight * entropy([r[target] for r in subset])
return base - weighted # entropy reduction
def best_feature(rows, features, target):
# pick the feature with the highest information gain
best, best_gain = None, -1.0
for f in features:
g = information_gain(rows, f, target)
if g > best_gain:
best, best_gain = f, g
return best, best_gain
# tennis dataset as a list of dictionaries
dataset = [
{"troi": "nang", "am": "cao", "gio": "nhe", "choi": "khong"},
{"troi": "nang", "am": "cao", "gio": "manh", "choi": "khong"},
{"troi": "amu", "am": "cao", "gio": "nhe", "choi": "co"},
{"troi": "mua", "am": "cao", "gio": "nhe", "choi": "co"},
{"troi": "mua", "am": "vua", "gio": "nhe", "choi": "co"},
{"troi": "mua", "am": "vua", "gio": "manh", "choi": "khong"},
{"troi": "amu", "am": "vua", "gio": "manh", "choi": "co"},
{"troi": "nang", "am": "cao", "gio": "nhe", "choi": "khong"},
{"troi": "nang", "am": "vua", "gio": "nhe", "choi": "co"},
{"troi": "mua", "am": "vua", "gio": "nhe", "choi": "co"},
{"troi": "nang", "am": "vua", "gio": "manh", "choi": "co"},
{"troi": "amu", "am": "cao", "gio": "manh", "choi": "co"},
{"troi": "amu", "am": "vua", "gio": "nhe", "choi": "co"},
{"troi": "mua", "am": "cao", "gio": "manh", "choi": "khong"},
]
features = ["troi", "am", "gio"]
print(round(entropy([r["choi"] for r in dataset]), 3)) # expected ~ 0.94
for f in features:
print(f, round(information_gain(dataset, f, "choi"), 3))
feat, gain = best_feature(dataset, features, "choi")
print("root:", feat, round(gain, 3)) # expected: troi
Khi chạy, đoạn mã in ra entropy gốc khoảng 0.94, độ lợi của ba đặc trưng (Trời cao nhất, khoảng 0.247), và xác nhận Trời được chọn làm nút gốc, đúng như tính tay ở trên. Để dựng cây đầy đủ, ta chỉ cần gọi best_feature lặp đi lặp lại: chọn đặc trưng tốt nhất, chia dữ liệu theo từng giá trị, rồi gọi lại chính quy trình đó trên mỗi tập con cho tới khi tập con thuần nhất hoặc hết đặc trưng.
Bài tập thực hành
Bài 1. Tính entropy của nhánh Nắng (5 mẫu: 2 có và 3 không) bằng tay, rồi đối chiếu với con số 0.971 đã nêu trong bài.
Gợi ý
Đặt p_co = 2/5 = 0.4 và p_khong = 3/5 = 0.6. Thay vào H = -0.4 * log2(0.4) - 0.6 * log2(0.6). Ta có log2(0.4) ~ -1.322 và log2(0.6) ~ -0.737, nên H ~ 0.4 * 1.322 + 0.6 * 0.737 ~ 0.529 + 0.442 ~ 0.971 bit. Khớp với giá trị trong bài.
Bài 2. Tính độ lợi thông tin của đặc trưng Gió trên tập gốc 14 mẫu. Gió có hai giá trị: nhẹ (8 mẫu) và mạnh (6 mẫu). Trong nhóm nhẹ có 6 có và 2 không; trong nhóm mạnh có 3 có và 3 không.
Gợi ý
Entropy nhóm nhẹ với tỉ lệ 6/8 và 2/8 cho khoảng 0.811. Nhóm mạnh chia đều 3/6 và 3/6 nên entropy đúng bằng 1.0. Entropy trung bình có trọng số là (8/14) * 0.811 + (6/14) * 1.0 ~ 0.892. Vậy IG = 0.940 - 0.892 ~ 0.048 bit, đúng bằng con số nêu trong bài. Đây là độ lợi thấp nhất trong ba đặc trưng.
Bài 3. Mở rộng đoạn mã Python: viết hàm đệ quy build_tree(rows, features, target) trả về cây dưới dạng dict lồng nhau. Dừng đệ quy khi tập con thuần nhất (trả về nhãn) hoặc khi danh sách features rỗng (trả về nhãn đa số).
Gợi ý
Kiểm tra trước: nếu set(r[target] for r in rows) chỉ có một phần tử thì trả về luôn nhãn đó. Nếu features rỗng thì trả về nhãn xuất hiện nhiều nhất qua Counter(...).most_common(1). Ngược lại gọi best_feature để lấy đặc trưng chia, tạo một dict ánh xạ mỗi giá trị của đặc trưng đó sang kết quả gọi đệ quy build_tree trên tập con tương ứng, với features đã loại bỏ đặc trưng vừa dùng.
Tự kiểm tra
Vì sao một lá hoàn toàn thuần nhất lại có entropy bằng 0?
Lá thuần nhất chỉ chứa một nhãn duy nhất, nên tỉ lệ của nhãn đó là p = 1 và mọi nhãn khác có tỉ lệ 0. Trong công thức entropy, số hạng của nhãn có mặt là -1 * log2(1) = 0 (vì log2(1) = 0), còn các số hạng của nhãn vắng mặt là 0 theo quy ước 0 * log2(0) = 0. Tổng lại bằng 0, nghĩa là không còn bất định nào: tới lá này ta biết chắc câu trả lời.
Vì sao ID3 chọn đặc trưng có độ lợi thông tin lớn nhất chứ không phải nhỏ nhất?
Độ lợi thông tin là phần entropy giảm đi sau khi chia. Độ lợi lớn nghĩa là phép chia làm các tập con thuần nhất hơn nhiều so với tập cha, tức đặc trưng đó giải thích được nhiều bất định nhất và đưa ta gần tới câu trả lời nhanh nhất. Chọn độ lợi lớn nhất giúp cây tách dữ liệu hiệu quả và gọn ngay từ những nút đầu.
Câu hỏi tự kiểm
- 1Một nút lá chỉ chứa toàn một nhãn duy nhất thì entropy của nó bằng bao nhiêu?
- 2Vì sao độ lợi thông tin có thể chọn nhầm một cột kiểu mã định danh (mỗi mẫu một giá trị)?
- 3ID3 chọn đặc trưng nào để đặt tại mỗi nút?
- 4Rừng ngẫu nhiên cải thiện một cây quyết định đơn chủ yếu bằng cách nào?
Cây quyết định phân loại bằng một chuỗi câu hỏi rẽ nhánh, dễ giải thích như cách con người ra quyết định. Thuật toán ID3 xây cây theo lối tham lam: ở mỗi nút chọn đặc trưng có độ lợi thông tin lớn nhất, tức đặc trưng làm giảm entropy nhiều nhất, rồi đệ quy trên các tập con cho tới khi thuần nhất. Entropy đo độ hỗn loạn theo nhãn (0 là thuần nhất, lớn nhất khi chia đều), còn độ lợi thông tin đo phần entropy giảm đi nhờ phép chia. Cây để mọc tự do dễ quá khớp, nên thực tế ta cắt tỉa bằng cách giới hạn độ sâu hoặc gộp các nhánh ít giá trị.