Cây quyết định (tiếng Anh: decision tree) là một mô hình học máy có giám sát biểu diễn cấu trúc phân cấp phi tham số dưới dạng cây có hướng, được sử dụng phổ biến cho cả hai bài toán phân loại và hồi quy. Cấu trúc mô hình bao gồm một nút gốc chứa toàn bộ tập dữ liệu ban đầu, các nút nội bộ đại diện cho các điều kiện kiểm tra trên từng thuộc tính, các nhánh biểu thị kết quả của phép kiểm tra và các nút lá đại diện cho nhãn lớp dự đoán hoặc giá trị đích liên tục. Mục từ này trình bày bản chất toán học, các thuật toán xây dựng cây kinh điển, tiêu chuẩn phân chia nút, kỹ thuật cắt tỉa hạn chế quá khớp và các mô hình mở rộng trong khoa học dữ liệu.
Cấu trúc và nguyên lý hoạt động
Theo khảo sát phương pháp luận của Safavian và Landgrebe (1991), nguyên lý cốt lõi của cây quyết định là chiến lược chia để trị. Thuật toán liên tục phân chia không gian đặc trưng nhiều chiều thành các siêu hình hộp chữ nhật không chồng lấn, trong đó mỗi vùng cục bộ được gán một mô hình dự đoán đơn giản nhất.
Các thành phần hình học và cấu trúc nút
- Nút gốc (Root node): Nút khởi đầu của cây, tiếp nhận toàn bộ tập dữ liệu huấn luyện và thực hiện phép phân chia đầu tiên.
- Nút nội bộ (Internal node): Nút thực hiện phép kiểm tra điều kiện trên một biến đầu vào xác định nhằm dẫn hướng mẫu dữ liệu sang các nhánh con.
- Nhánh (Branch): Đường nối biểu diễn kết quả phép thử logic hoặc khoảng giá trị của biến thuộc tính.
- Nút lá (Leaf node): Nút kết thúc không còn phân nhánh, lưu trữ quyết định phân loại cuối cùng hoặc giá trị trung bình cục bộ của hàm hồi quy.
Các tiêu chuẩn phân tách nút
Tại mỗi nút nội bộ, thuật toán cần chọn thuộc tính và điểm phân chia tối ưu nhằm cực đại hóa độ thuần khiết của các tập con được tạo ra.
1. Độ hỗn loạn Entropy và Độ lợi thông tin
Được Quinlan (1986) ứng dụng trong thuật toán ID3, độ hỗn loạn thông tin Shannon của tập dữ liệu gồm lớp được định nghĩa theo công thức:
Trong đó là tỷ lệ mẫu thuộc về lớp thứ trong tập dữ liệu . Khi tập dữ liệu hoàn toàn thuần khiết, giá trị entropy bằng không. Khi các lớp phân bố đồng đều, entropy đạt giá trị cực đại.
Độ lợi thông tin của một thuộc tính biểu thị mức độ giảm entropy sau khi phân chia tập thành các tập con :
IG(S, A) = H(S) - \sum_{v \in ext{Values}(A)} rac{|S_v|}{|S|} H(S_v)
2. Tỷ lệ độ lợi thông tin
Nhằm khắc phục nhược điểm của độ lợi thông tin khi ưu tiên các thuộc tính có quá nhiều giá trị riêng biệt, thuật toán C4.5 chuẩn hóa độ lợi thông tin bằng thông tin phân tách:
ext{SplitInfo}_A(S) = - \sum_{v \in ext{Values}(A)} rac{|S_v|}{|S|} \log_2\left( rac{|S_v|}{|S|} ight)
ext{GainRatio}(S, A) = rac{IG(S, A)}{ ext{SplitInfo}_A(S)}
3. Chỉ số tạp chất Gini
Theo phân tích của Loh (2011), thuật toán CART sử dụng chỉ số Gini để đo lường xác suất một mẫu ngẫu nhiên bị phân loại sai nếu gán nhãn theo phân phối xác suất của tập con:
Chỉ số Gini có ưu điểm tính toán nhanh hơn entropy do không yêu cầu thực hiện phép tính hàm logarit.
So sánh các thuật toán cây quyết định kinh điển
Bảng dưới đây tóm tắt các đặc tính kỹ thuật cơ bản của các dòng thuật toán cây quyết định phổ biến:
| Thuật toán | Dạng phân nhánh | Tiêu chuẩn phân tách | Xử lý thuộc tính liên tục | Xử lý dữ liệu khuyết thiếu |
|---|---|---|---|---|
| ID3 | Đa nhánh | Độ lợi thông tin | Không hỗ trợ trực tiếp | Không hỗ trợ |
| C4.5 | Đa nhánh hoặc nhị phân | Tỷ lệ độ lợi | Có phân ngưỡng động | Có phân bổ trọng số |
| CART | Nhị phân nghiêm ngặt | Chỉ số Gini hoặc phương sai | Có tìm điểm cắt tối ưu | Có dùng biến đại diện |
| CHAID | Đa nhánh | Kiểm định Chi bình phương | Rời rạc hóa thành thứ bậc | Xử lý như phân lớp riêng |
Hiện tượng quá khớp và kỹ thuật cắt tỉa
Cây quyết định có xu hướng phát triển sâu cho đến khi phân loại hoàn hảo toàn bộ tập huấn luyện, dẫn đến hiện tượng quá khớp và làm giảm khả năng tổng quát hóa trên dữ liệu thực tế.
Cắt tỉa sớm
Thuật toán dừng quá trình phân nhánh trước khi cây đạt độ sâu tối đa dựa trên các điều kiện dừng định trước:
- Giới hạn độ sâu tối đa của cây mô hình.
- Quy định số lượng mẫu tối thiểu tại nút nội bộ để tiếp tục phân chia.
- Quy định số lượng mẫu tối thiểu tại nút lá.
- Ngưỡng suy giảm tối thiểu của độ tạp chất phân tách.
Cắt tỉa muộn
Cây được phát triển đầy đủ trước, sau đó tiến hành loại bỏ các nhánh con không mang lại ý nghĩa thống kê trên tập kiểm định độc lập. Phương pháp phổ biến nhất là cắt tỉa theo độ phức tạp chi phí:
R_lpha(T) = R(T) + lpha |T|
Trong đó là tổng sai số huấn luyện của cây , là số nút lá và lpha là hệ số phạt độ phức tạp.
Mở rộng mô hình: Phương pháp học tập hợp
Nhằm khắc phục nhược điểm phương sai cao và độ nhạy cảm với biến động nhỏ của tập dữ liệu, các phương pháp học tập hợp đã được phát triển mạnh mẽ:
- Đóng bao và Rừng ngẫu nhiên: Nghiên cứu của Breiman (2001) đã chứng minh việc xây dựng các tập hợp cây quyết định độc lập trên các tập mẫu lấy lại có hoàn lại kết hợp chọn ngẫu nhiên tập con đặc trưng giúp giảm phương sai đáng kể mà không làm tăng độ chệch.
- Tăng cường độ dốc: Các thuật toán hiện đại xây dựng tuần tự các cây quyết định nông, trong đó mỗi cây mới tập trung học và tối ưu hóa phần dư sai số của các cây đứng trước.
Ưu điểm và giới hạn áp dụng
Cây quyết định giữ vị trí quan trọng trong học máy thực hành nhờ những đặc tính độc đáo nhưng cũng đi kèm các giới hạn cần lưu ý:
| Khía cạnh | Ưu điểm nổi bật | Hạn chế chính |
|---|---|---|
| Khả năng diễn giải | Rất cao nhờ cấu trúc trực quan dạng luật logic | Dễ mất tính diễn giải trực quan khi kết hợp thành mô hình tập hợp lớn |
| Chuẩn bị dữ liệu | Không yêu cầu chuẩn hóa thang đo biến số | Nhạy cảm với mất cân bằng lớp và dữ liệu có nhiễu cao |
| Mối quan hệ phi tuyến | Tự động nắm bắt các tương tác phi tuyến phức tạp | Ranh giới quyết định phân đoạn vuông góc với các trục tọa độ |
| Tính ổn định thống kê | Tính toán dự đoán nhanh chóng trên dữ liệu lớn | Độ bất ổn định cao do thay đổi nhỏ ở dữ liệu có thể đổi cấu trúc cây |