Tổng quan về Giải thuật cây quyết định

Giới thiệu cây quyết định

Cây quyết định là một công cụ đưa quyết định sử dụng cấu trúc cây biểu đồ luồng có thể gọi là model của những quyết định và những kết quả tích cực, bao gồm, đầu ra, giá trị đầu vào và những liên quan khác. Giải thuật cây quyết định là một giải thuật học máy thuộc các giải thuật học máy có giám sát. Giải thuật cây quyết định có thể được sử dụng cho cả bài toán phân lớp và bài toán dự đoán. Mục tiêu tạo mô hình để dự đoán các giá trị cảu biến mục tiêu bởi việc học các nguyên tắc quyets định từ các đặc tính của dữ liệu. Nguyên tắc đưa ra quyết định thường được theo quy tắc của mệnh đề if – then – else trong ngôn ngữ lập trình.

Cây quyết định có thể coi là thuật toán học máy khá mạnh mẽ và cho kết quả tốt hơn các giải thuật như: Random Forest, XGBoost, AdaBoost và LightGB.

Thành phần biểu thị kết quả của node và các node có thể được biểu diễn:

Các thuật ngữ trong giải thuật cây quyết định

• Trường hợp (Instances): là các vector đặt tính định nghĩa cho mỗi dữ liệu (sample nhưng khoogn có label)
• Đặc tính (Atribute): Mô tả đặc tính của trường hợp (sample)
• Concept: Hàm để map giữa input tới output
• Target concept: Hàm để tìm ra câu trả lời mục tiêu
• Hypothesis class: Tập hợp của các hàm
• Sample: Tập hợp các đầu vào với label
• Testing set: Tương tự như tập training set được sử dụng để làm tập kiểm thử và đánh giá cho mode

Các bước xây dựng 1 giải thuật cây quyết định:

• Bắt đầu từ điểm cao nhất của cây
• Phát triển nó bằng cách chia từng thành phần một. Để quyết định nhánh được chia ta có “node impurity”
• Một node là lá node chính trên cây, nếu cây quá tải thì có thể cắt tỉa bớt lá

Một ví dụ về cách hoạt động của thuật toán Cây quyết định

TT	Tuổi	Thu nhập	Sinh viên	Tín dụng	Ci: Mua
1	Trẻ	Cao	Không	Cao	không
2	Trẻ	Cao	Không	rất cao	không
3	Trung niên	Cao	Không	cao	Có
4	Cao niên	Trung bình	Không	cao	Có
5	Cao niên	Thấp	Có	cao	Có
6	Trung niên	Thấp	Có	Rất cao	không
7	Trẻ	Thấp	Có	Rất cao	Có
8	Trẻ	Trung bình	Không	Cao	không
9	Trẻ	Thấp	Có	Cao	Có
10	Cao niên	Trung bình	Có	Cao	Có
11	Trẻ	Trung bình	Có	Rất cao	Có
12	Trung niên	Trung bình	Không	Rất cao	Có
13	Trung niên	Cao	Có	Cao	Có
14	Cao niên	Trung bình	Không	Rất cao	Không

Xây dựng giải thuật cây quyết định bằng C#

Tài liệu tham khảo:

Python | Decision Tree Regression using sklearn – GeeksforGeeks

Decision Tree Algorithm (towardsmachinelearning.org)