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?

Năm 1948, nhà toán học Claude Shannon đặt nền móng cho thời đại số với bài báo kinh điển “A Mathematical Theory of Communication”. Trọng tâm công trình ấy là câu hỏi tưởng chừng mang tính triết học: Làm thế nào để lượng hoá “lượng thông tin” chứa trong một thông điệp?

Câu trả lời của Shannon là khái niệm Entropy — thước đo độ bất định (uncertainty) và mức độ hỗn tạp của một nguồn dữ liệu. Trong học máy, Entropy chính là tiêu chí phân nhánh nền tảng của các thuật toán cây quyết định nổi tiếng như ID3 và C4.5.

Trong toán học và xác suất, phép lấy trung bình (hay kỳ vọng toán học $\mathbb{E}$) là một toán tử tuyến tính mẫu mực. Nếu ta có một hàm tuyến tính $f(x) = ax + b$, việc áp dụng hàm trước rồi lấy trung bình hay lấy trung bình trước rồi áp dụng hàm luôn cho cùng một kết quả:

Tuy nhiên, thế giới tự nhiên và các mô hình thống kê hiếm khi tuyến tính. Khi $f$ là một hàm phi tuyến (như $x^2, e^x, \ln x$), câu hỏi căn bản xuất hiện: $f(\mathbb{E}[X])$ và $\mathbb{E}[f(X)]$, đại lượng nào lớn hơn?

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

Một cây quyết định (Decision Tree) có cách suy luận trực quan và dễ theo dõi: đặt liên tiếp các câu hỏi để chia nhỏ dữ liệu. Tuy nhiên, một cây đơn lẻ có thể dao động rất mạnh theo mẫu huấn luyện (phương sai cao) — chỉ vài quan sát thay đổi cũng có thể làm phép chia gần gốc đổi chỗ và kéo theo toàn bộ cấu trúc cây đảo lộn.

Một cây quyết định học bằng cách đặt liên tiếp những câu hỏi đơn giản. Chẳng hạn, với một hồ sơ tín dụng, cây có thể hỏi “tỷ lệ nợ có vượt 40% không?”, rồi ở mỗi nhánh lại hỏi thêm về thu nhập hoặc lịch sử trả nợ. Đi hết một đường từ gốc tới lá, ta nhận được một dự đoán.

Sự đơn giản này dễ tạo cảm giác rằng cây chỉ là một sơ đồ if–else được viết bằng tay. Điểm khác biệt nằm ở chỗ dữ liệu quyết định câu hỏi nào được đặt, đặt ở đâu và khi nào dừng lại. Bài viết sẽ đi từ một phép chia duy nhất tới toàn bộ cây, sau đó chỉ ra vì sao một cây đơn thường được dùng làm mô hình cơ sở (base learner) cho Random Forest.