Giống như tất cả mô hình học máy có giám sát, cây quyết định được huấn luyện để giải thích chính xác nhất một tập hợp các ví dụ huấn luyện. Phương thức huấn luyện tối ưu cây quyết định là một bài toán NP-hard. Do đó, việc huấn luyện thường được thực hiện bằng cách sử dụng phương pháp phỏng đoán – một thuật toán học tập dễ tạo sẽ đưa ra một cây quyết định không tối ưu nhưng gần với khả năng tối ưu.
Hầu hết các thuật toán dùng để huấn luyện cây quyết định đều hoạt động với chiến lược chia và chinh phục một cách tham lam. Thuật toán bắt đầu bằng cách tạo một nút duy nhất (gốc) và phát triển cây quyết định theo định kỳ.
Ở mỗi nút, tất cả các điều kiện có thể có đều được đánh giá và tính điểm. Thuật toán chọn điều kiện "tốt nhất", tức là điều kiện có điểm số cao nhất. Hiện tại, chỉ cần biết rằng điểm số là một chỉ số tương quan với tác vụ và các điều kiện được chọn để tối đa hoá chỉ số đó.
Ví dụ: trong tập dữ liệu Chim cánh cụt Palmer (được dùng cho các ví dụ về mã sau này trong khoá học này), hầu hết chim cánh cụt Adelie và Chinstrap đều có chiều dài hoá đơn lớn hơn 16 mm, trong khi hầu hết chim cánh cụt Gentoo có hoá đơn nhỏ hơn. Do đó, điều kiện bill_length_mm ≥ 16 đưa ra dự đoán gần như hoàn hảo cho chim cánh cụt Gentoo, nhưng không thể phân biệt giữa Adelies và Chinstraps. Thuật toán có thể sẽ chọn điều kiện này.
Hình 7. Bước đầu tiên khi trồng cây.
Sau đó, thuật toán này lặp lại đệ quy và độc lập trên cả hai nút con. Khi không tìm thấy điều kiện thoả mãn, nút sẽ trở thành một lá. Thông tin dự đoán về lá được xác định là giá trị nhãn tiêu biểu nhất trong các ví dụ.
Thuật toán như sau:
def train_decision_tree(training_examples):
root = create_root() # Create a decision tree with a single empty root.
grow_tree(root, training_examples) # Grow the root node.
return root
def grow_tree(node, examples):
condition = find_best_condition(examples) # Find the best condition.
if condition is None:
# No satisfying conditions were found, therefore the grow of the branch stops.
set_leaf_prediction(node, examples)
return
# Create two childrens for the node.
positive_child, negative_child = split_node(node, condition)
# List the training examples used by each children.
negative_examples = [example for example in examples if not condition(example)]
positive_examples = [example for example in examples if condition(example)]
# Continue the growth of the children.
grow_tree(negative_child, negative_examples)
grow_tree(positive_child, positive_examples)
Hãy cùng tìm hiểu các bước huấn luyện một cây quyết định cụ thể một cách chi tiết hơn.
Bước 1: Tạo một thư mục gốc:
Bước 2: Phát triển nút #1. Đã tìm thấy điều kiện "x1 ≥ 1". Hai nút con được tạo:
Bước 3: Phát triển nút #2. Không tìm thấy điều kiện thoả mãn nào. Vì vậy, hãy đưa nút thành một lá:
Bước 4: Phát triển nút #3. Điều kiện "x2 ≥ 0,5" đã được tìm thấy. Hai nút con được tạo.
Ngoài ra còn có các phương pháp khác để phát triển cây quyết định. Một cách thay thế phổ biến là tối ưu hoá các nút trên toàn hệ thống thay vì sử dụng chiến lược chia để trị.
growing_strategy="BEST_FIRST_GLOBAL".
Hãy xem
tài liệu để biết thêm thông tin chi tiết.
Tuỳ thuộc vào số lượng và loại tính năng đầu vào, số lượng điều kiện có thể xảy ra cho một nút nhất định có thể là rất lớn và thường là vô hạn. Ví dụ: với một điều kiện ngưỡng $\mathrm{feature}_i \geq t$, tổ hợp của tất cả các giá trị ngưỡng có thể có cho $t \in \mathbb{R}$ là vô hạn.
Quy trình giúp tìm điều kiện tốt nhất được gọi là bộ tách. Vì cần thử nghiệm nhiều điều kiện có thể xảy ra, nên bộ phân tách là nút thắt cổ chai khi huấn luyện cây quyết định.
Điểm số được tối đa hoá bằng trình phân tách phụ thuộc vào việc cần làm. Ví dụ:
- Mức thu thập thông tin và Gini (cả hai đều được đề cập sau) thường được dùng để phân loại.
- Sai số bình phương trung bình thường được dùng để hồi quy.
Có nhiều thuật toán phân tách, mỗi thuật toán có hỗ trợ khác nhau cho:
- Loại đối tượng; ví dụ: dạng số, phân loại, văn bản
- Tác vụ; ví dụ: phân loại nhị phân, phân loại nhiều lớp, hồi quy
- Loại điều kiện; ví dụ: điều kiện ngưỡng, điều kiện đặt sẵn, điều kiện xiên
- Tiêu chí chính quy; ví dụ: bộ phân tách chính xác hoặc gần đúng cho các điều kiện ngưỡng
Ngoài ra, còn có các biến thể bộ phân tách tương đương với những ưu điểm khác nhau về mức sử dụng bộ nhớ, mức sử dụng CPU, sự phân bổ điện toán, v.v.