Cây quyết định (decision tree) là cơ chế dạng biểu đồ dòng chảy (flow-chart-like tree mechanism), nơi mỗi nút nội bộ (internal node) chỉ ra một kiểm tra trên một thuộc tính, mỗi nhánh (branch) xác định một kết quả của kiểm tra, và các nút lá (leaf nodes) mô tả các lớp hoặc phân phối lớp. Nút lớn nhất trong một cây là nút gốc (root node).
Vấn đề xây dựng cây quyết định có thể được định nghĩa đệ quy (recursively). Trước tiên, chọn một thuộc tính đặt tại nút gốc, và tạo một nhánh cho mỗi giá trị có thể. Điều này chia tập ví dụ thành các tập con, một cho mỗi giá trị của thuộc tính. Quy trình có thể lặp lại đệ quy cho mỗi nhánh, chỉ sử dụng những thể hiện đến nhánh đó. Nếu một số thể hiện tại một nút có cùng phân loại, dừng xây dựng phần đó của cây.
Đo lường độ tinh khiết (measure of purity) mà chúng ta sẽ dùng được gọi là thông tin (information) và được đo bằng đơn vị gọi là bit. Liên kết với mỗi nút của cây, nó đại diện cho lượng thông tin kỳ vọng cần thiết để xác định xem một thể hiện mới nên được phân loại là có hay không, với điều kiện rằng các thể hiện đã đến nút đó.
Cắt tỉa (Pruning) là quy trình giảm kích thước cây quyết định. Nó được dùng để giảm nguy cơ overfitting (quá khớp) bằng cách giới hạn kích thước cây hoặc loại bỏ các khu vực của cây cung cấp ít sức mạnh. Cắt tỉa hoạt động bằng cách cắt bỏ các nhánh tuân theo các bất thường trong dữ liệu huấn luyện do nhiễu (noise) hoặc giá trị ngoại lai (outliers) và cung cấp cây ban đầu theo cách cải thiện hiệu quả tổng quát hóa (generalization) của cây.
Một số phương pháp thường dùng các đo lường thống kê để loại bỏ các nhánh ít tin cậy nhất, thường dẫn đến phân loại nhanh hơn và cải thiện khả năng của cây phân loại chính xác dữ liệu kiểm tra độc lập.
Các thuật toán học Cây Quyết định
Thuật toán — Tạo cây quyết định từ thông tin huấn luyện cho trước.
Đầu vào — Các mẫu huấn luyện (training samples), các mẫu, được mô tả bởi các thuộc tính giá trị rời rạc (discrete-valued attributes); tập các thuộc tính sinh viên (attribute-list).
Đầu ra — Một cây quyết định.
Phương pháp
- Tạo một nút N;
- Nếu các mẫu thuộc cùng một lớp, C thì
- Trả về N như một nút lá được gán nhãn với lớp C
- Nếu attribute-list là null thì
- Trả về N như một nút lá được gán nhãn với lớp phổ biến nhất trong các mẫu. // bỏ phiếu đa số (majority voting)
- Chọn test-attribute, thuộc tính giữa attribute-list có information gain lớn nhất.
- Gán nhãn nút N với test attribute.
- Với mỗi giá trị đã biết ai của test-attribute // phân hoạch các mẫu.
- Mọc một nhánh từ nút N cho điều kiện test-attribute = ai.
- Cho si là tập các mẫu trong samples mà test-attribute = ai.
- Nếu si rỗng thì
- Có thể liên kết với một lá gán nhãn với lớp phổ biến nhất trong samples.
- Ngược lại gắn nút được trả về bởi Generate decision tree (si, attribute-list - test-attribute)