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 một tập hợp ví dụ huấn luyện. Cách huấn luyện tối ưu cho cây quyết định là một bài toán khó NP. 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 cách thuật toán học tập dễ tạo ra kết quả không tối ưu, nhưng gần với tối ưu, cây quyết định.
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 theo mô hình phân chia tham lam và chiến thuật chinh phục. Thuật toán bắt đầu bằng cách tạo một nút (nút gốc) và phát triển cây quyết định theo cách đệ quy và tham lam.
Tại mỗi nút, tất cả các điều kiện có thể có sẽ được đánh giá và tính điểm. Chiến lược phát hành đĩa đơn thuật toán sẽ chọn phương án "phù hợp nhất" điều kiện, tức là điều kiện có giá trị cao nhất điểm số. Hiện tại, chỉ cần biết rằng điểm số là chỉ số tương quan với công việc và điều kiện được chọn để tối đa hoá chỉ số đó.
Ví dụ: trong trò chơi Palmer Chim cánh cụt (được dùng cho các ví dụ về mã sau trong khoá học này), hầu hết Adelie và Chinstrap chim cánh cụt có chiều dài hơn 16mm, trong khi hầu hết loài Gentoo chim cánh cụt có hoá đơn nhỏ hơn. Do đó, điều kiện bill_length_mm ≥ 16 đưa ra những 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 được 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 trong quy trình trồng cây.
Sau đó, thuật toán sẽ lặp lại theo cách đệ quy và độc lập trên cả hai nút con. Khi không tìm thấy điều kiện nào thoả mãn, nút sẽ trở thành một lá. Chiếc lá dự đoán đượ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ể theo chi tiết hơn.
Bước 1: Tạo thư mục gốc:
Bước 2: Phát triển nút số 1. Điều kiện "x1 ≥ 1" đã được tìm thấy. Hai nút con được tạo:
Bước 3: Phát triển nút số 2. Không tìm thấy điều kiện nào thoả mãn. Vì vậy, hãy làm cho nút vào một lá:
Bước 4: Phát triển nút số 3. Điều kiện "x2 ≥ 0,5" đã được tìm thấy. Hai trẻ em các nút mới được tạo.
Có các phương pháp khác để trồng 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 cầu thay vì sử dụng chiến lược chia để trị.
growing_strategy="BEST_FIRST_GLOBAL".
Xem
tài liệu để biết thêm chi tiết.
Tuỳ thuộc vào số lượng và loại đối tượng nhập, số lượng thuộc tính điều kiện khả dĩ cho một nút nhất định có thể là rất lớn, thường là vô hạn. Ví dụ: với điều kiện ngưỡng $\mathrm{feature}_i \geq t$, kết hợp mọi thuộc tính có thể giá trị ngưỡng cho $t \in \mathbb{R}$ là vô hạn.
Quy trình chịu trách nhiệm tìm ra điều kiện tốt nhất được gọi là bộ chia. Vì cần phải kiểm thử nhiều điều kiện có thể xảy ra, nên bộ chia là điểm tắc nghẽn khi huấn luyện cây quyết định.
Điểm số mà công cụ chia tách sẽ đạt mức tối đa tuỳ thuộc vào nhiệm vụ. Ví dụ:
- Thông tin thu thập được và Gini (cả hai đề 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 cho 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ụ: số, phân loại, văn bản
- Việc cần làm; ví dụ: phân loại nhị phân, nhiều lớp phân loại, hồi quy
- Loại điều kiện; ví dụ: điều kiện ngưỡng, điều kiện đã đặt, điều kiện xiên
- Các tiêu chí điều chỉnh; ví dụ: bộ chia chính xác hoặc gần đúng cho các điều kiện về ngưỡng
Ngoài ra, còn có các biến thể tương đương với bộ chia tách nhưng có nhiều ưu điểm khác biệt liên quan đến mức sử dụng bộ nhớ, mức sử dụng CPU, việc phân phối tính toán, v.v.