Cây quyết định (Decision Tree): Một câu hỏi chia đôi dữ liệu

Từ phép chia đầu tiên đến một mô hình dự đoán hoàn chỉnh

2026-Aug-30 1604 từ 8 phút

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 viên gạch cơ sở cho Random Forest.

1. Một cây gồm những gì?

Mỗi quan sát bắt đầu ở nút gốc. Một nút trong kiểm tra một điều kiện, thường có dạng

$$ x_j\le s, $$

trong đó $x_j$ là một đặc trưng và $s$ là ngưỡng chia. Điều kiện đúng dẫn sang nhánh trái, điều kiện sai dẫn sang nhánh phải. Quá trình lặp lại cho tới một nút lá.

Trong bài toán phân loại, lá thường lưu tỷ lệ các lớp trong những quan sát huấn luyện đi tới lá đó. Lớp có tỷ lệ lớn nhất có thể được dùng làm nhãn dự đoán. Trong hồi quy với mất mát bình phương, một lựa chọn thông dụng là giá trị trung bình của các đáp ứng trong lá.

Như vậy, cây đồng thời có hai cách nhìn:

dưới dạng quy tắc, cây là một chuỗi câu hỏi dễ lần theo;
dưới dạng hình học, mỗi câu hỏi cắt không gian đặc trưng thành hai phần, tạo nên các miền dự đoán hình chữ nhật khi phép chia song song với các trục.

2. Thế nào là một phép chia tốt?

Xét bài toán phân loại hai lớp A và B. Nếu một nút chỉ chứa một lớp, nút đó thuần nhất. Nếu hai lớp trộn lẫn gần ngang nhau, nút có độ hỗn tạp cao. Một thước đo thường dùng trong CART là chỉ số Gini (Gini Impurity)

$$ G(t)=1-p_A(t)^2-p_B(t)^2, $$

với $p_A(t),p_B(t)$ là tỷ lệ hai lớp tại nút $t$. Chỉ số bằng $0$ khi nút thuần nhất và đạt $0{,}5$ khi hai lớp có cùng tỷ lệ.

Giả sử một phép chia tạo nút trái $L$ và nút phải $R$. Độ hỗn tạp sau khi chia là trung bình có trọng số

$$ 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 là

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

Cây thử các đặc trưng và ngưỡng ứng viên, rồi chọn phép chia có $\Delta G$ lớn nhất trong số đang xét. Đây là lựa chọn tham lam: tốt nhất tại nút hiện tại, không phải lời bảo đảm rằng toàn bộ cây sau cùng là tối ưu trong mọi cấu trúc cây có thể có.

THÍ NGHIỆM 1 · CHỌN NGƯỠNG

Kéo đường chia và theo dõi chỉ số Gini

Ngưỡng s 0,50

Gini trước khi chia—

Gini sau khi chia—

Mức giảm ΔG—

Nút gốc không thay đổi nên Gini trước khi chia là cố định. Nút con càng thuần nhất, Gini sau khi chia càng nhỏ. Hoạt ảnh chỉ quét các điểm giữa hai giá trị kề nhau — những vị trí duy nhất có thể làm cách phân nhóm thay đổi.

Hình 1. Ngưỡng tốt nhất không nhất thiết tách hai lớp hoàn toàn; nó chỉ giảm độ hỗn tạp nhiều nhất trong các ngưỡng ứng viên.

3. Từ một phép chia đến toàn bộ cây

Sau phép chia đầu tiên, cùng một quy trình được áp dụng riêng cho từng nút con:

tìm phép chia làm giảm độ hỗn tạp nhiều nhất tại nút hiện tại;
chia các quan sát sang hai nút con;
tiếp tục đệ quy cho tới khi gặp điều kiện dừng.

Vì các quyết định nằm gần gốc tác động tới nhiều quan sát hơn, một thay đổi nhỏ trong dữ liệu có thể làm phép chia đầu tiên đổi chỗ và kéo theo một cấu trúc cây khác. Đây là một nguồn phương sai cao của cây sâu.

Hình tiếp theo dùng cùng kiểu dữ liệu hai vành cung như bài Random Forest. Thanh độ sâu không chỉ làm đường biên “mượt” hơn. Với phép chia theo trục, cây thực chất ghép thêm các hình chữ nhật nhỏ để xấp xỉ một ranh giới cong.

THÍ NGHIỆM 2 · TRỒNG CÂY

Quan sát cây lớn dần từng mức

Độ sâu tối đa 1

Số lá—

Độ chính xác huấn luyện—

Quy tắc ở gốc—

Xem cấu trúc cây hiện tại

Mô phỏng dùng cây CART giới hạn độ sâu và số quan sát tối thiểu ở lá trên một tập dữ liệu nhỏ. Độ chính xác hiển thị là trên chính dữ liệu huấn luyện, không phải ước lượng hiệu quả dự đoán ngoài mẫu.

Hình 2. Khi độ sâu tăng, cây có thêm miền dự đoán và có thể bám dữ liệu huấn luyện sát hơn. Mức tăng độ chính xác huấn luyện không tự động chuyển thành cải thiện trên dữ liệu mới.

4. Dừng cây và cắt tỉa

Nếu tiếp tục chia cho tới khi mỗi lá gần như thuần nhất, cây có thể ghi nhớ cả cấu trúc tín hiệu lẫn dao động ngẫu nhiên trong mẫu. Có hai nhóm cách kiểm soát độ phức tạp.

Dừng sớm giới hạn cây ngay khi huấn luyện, chẳng hạn bằng độ sâu tối đa, số quan sát tối thiểu để tách một nút, số quan sát tối thiểu ở lá hoặc mức giảm độ hỗn tạp tối thiểu.

Cắt tỉa (pruning) trước hết trồng một cây lớn, sau đó loại bớt những nhánh không đem lại đủ cải thiện. Trong cost-complexity pruning của CART, ta cân bằng sai số của cây với số lá qua đại lượng dạng

$$ R_\alpha(T)=R(T)+\alpha |\widetilde T|, $$

trong đó $R(T)$ đo sai số hoặc độ không thuần của các lá, $|\widetilde T|$ là số lá và $\alpha\ge 0$ phạt cây phức tạp. Giá trị $\alpha$ cùng các tham số dừng nên được chọn bằng dữ liệu kiểm định hoặc một quy trình đánh giá ngoài mẫu phù hợp, thay vì nhìn vào độ chính xác huấn luyện.

5. Phân loại, xác suất và hồi quy

Một cây phân loại có thể trả về nhiều mức thông tin:

nhãn lớp: chọn lớp chiếm đa số tại lá;
tỷ lệ lớp tại lá: dùng tỷ lệ mẫu huấn luyện như một ước lượng xác suất;
chi phí quyết định: thay ngưỡng chọn lớp khi hai loại sai lầm có hậu quả khác nhau.

Tỷ lệ lớp tại lá là một ước lượng từng bậc và có thể thiếu ổn định khi lá chứa ít quan sát. Con số 80% ở một lá vì thế không tự động là xác suất đã được hiệu chỉnh tốt trên dữ liệu tương lai.

Với hồi quy, tiêu chí chia thường dựa trên mức giảm tổng bình phương sai số hoặc một hàm mất mát khác. Dự đoán ở lá là một giá trị tóm tắt của các đáp ứng huấn luyện trong lá. Do đó, cây hồi quy thường không ngoại suy một xu hướng tuyến tính ra ngoài miền đã quan sát.

6. Điểm mạnh và giới hạn

Cây quyết định hấp dẫn vì có thể biểu diễn quan hệ phi tuyến và tương tác giữa đặc trưng mà không cần viết sẵn dạng hàm. Cây cũng không đòi hỏi mọi đặc trưng phải được chuẩn hóa về cùng thang đo chỉ để so sánh các ngưỡng.

Tuy nhiên, cần giữ một số giới hạn gần phần diễn giải:

Lựa chọn tham lam: phép chia tốt nhất ở mỗi nút không bảo đảm cây cuối cùng tối ưu toàn cục.
Ranh giới theo trục: một ranh giới chéo hoặc cong có thể cần nhiều nút để xấp xỉ.
Nhạy với mẫu: thay đổi ít quan sát có thể làm cấu trúc cây thay đổi đáng kể.
Dễ quá khớp: cây sâu có nhiều khả năng bám nhiễu nếu không được kiểm soát và đánh giá ngoài mẫu.
Độ quan trọng của đặc trưng không phải quan hệ nhân quả: việc một đặc trưng được chọn sớm hoặc làm giảm Gini nhiều không chứng minh rằng can thiệp vào đặc trưng đó sẽ gây ra thay đổi ở đáp ứng.

7. Cầu nối sang Random Forest

Một cây đơn dễ đọc nhưng có thể dao động mạnh theo mẫu huấn luyện. Random Forest giữ nguyên viên gạch cơ sở này rồi thay đổi cách xây dựng:

dùng Bagging để mỗi cây nhận một mẫu bootstrap khác nhau;
tại mỗi nút, chỉ cho cây xét một tập con ngẫu nhiên của các đặc trưng;
gộp dự đoán của nhiều cây bằng bỏ phiếu hoặc lấy trung bình.

Mục tiêu không phải làm từng cây dễ diễn giải hơn, mà làm các cây đủ khác nhau để việc gộp dự đoán có thể giảm phương sai. Vì vậy, hiểu cách một cây chọn phép chia và vì sao cây sâu nhạy với dữ liệu chính là cơ sở để hiểu Random Forest.

Tài liệu tham khảo

Leo Breiman, Jerome H. Friedman, Richard A. Olshen và Charles J. Stone (1984), Classification and Regression Trees, Wadsworth & Brooks/Cole.
J. Ross Quinlan (1986), Induction of Decision Trees, Machine Learning, 1, 81–106.