Cây quyết định là cấu trúc dạng flowchart, nơi mỗi nút nội bộ chỉ ra kiểm tra trên thuộc tính, mỗi nhánh định nghĩa kết quả kiểm tra, và nút lá mô tả lớp hoặc phân phối lớp. Nút cao nhất trong cây là nút gốc (root node).
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 − Mẫu huấn luyện, samples, mô tả bởi thuộc tính giá trị rời rạc; tập thuộc tính học sinh, attribute-list.
Đầu Ra − Một cây quyết định.
Phương Pháp
Tạo nút N;
Nếu samples cùng một lớp C thì
Trả về N như nút lá gán nhãn lớp C
Nếu attribute-list rỗng thì
Trả về N như nút lá gán nhãn lớp phổ biến nhất trong samples. // bỏ phiếu đa số
Chọn test-attribute, thuộc tính trong attribute-list có information gain cao 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 samples.
Mọc nhánh từ nút N cho điều kiện test-attribute = aᵢ.
sᵢ là tập samples trong samples mà test-attribute = aᵢ.
Nếu sᵢ rỗng thì
Gán lá với lớp phổ biến nhất trong samples.
Ngược lại gán nút trả về bởi Generate decision tree(sᵢ, attribute-list - test-attribute)
Khởi Tạo Cây Quyết Định (Decision Tree Induction)
Sản xuất tự động quy tắc quyết định cho instance gọi là khởi tạo quy tắc (rule induction) hoặc khởi tạo quy tắc tự động. Tạo quy tắc quyết định trong dạng ngầm của cây quyết định cũng thường gọi là khởi tạo quy tắc, nhưng thuật ngữ tree induction hoặc decision tree induction luôn được ưu tiên.
Thuật toán cơ bản cho khởi tạo cây quyết định là thuật toán tham lam. Dùng tạo cây quyết định theo cách đệ quy chia-để-trị từ trên xuống. Thuật toán cơ bản học cây quyết định là dạng ID3, thuật toán khởi tạo cây quyết định nổi tiếng.
Các phương pháp cơ bản:
Cây bắt đầu như nút đơn lẻ đại diện mẫu huấn luyện.
Nếu samples cùng lớp, nút biến thành lá gán nhãn lớp đó.
Thuật toán dùng thước độ dựa trên entropy gọi là information gain làm heuristic chọn thuộc tính chia samples thành các lớp đơn lẻ. Thuộc tính này thành "test" hoặc "quyết định" tại nút. Trong dạng này, tất cả thuộc tính categorical (giá trị rời rạc). Thuộc tính giá trị liên tục phải rời rạc hóa.
Nhánh tạo cho mỗi giá trị biết của test-attribute, samples phân hoạch tương ứng.
Thuật toán dùng quy trình tương tự lặp để tạo cây quyết định cho samples tại mỗi phân hoạch. Vì thuộc tính xuất hiện tại nút, nó không được xem xét trong các con cháu của nút.