Trồng cây quyết định

Giống như tất cả cá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 tốt nhất một tập hợp các ví dụ về việc huấn luyện. Việc huấn luyện tối ưu cho cây quyết định là một vấn đề khó NP. Do đó, việc huấn luyện thường được thực hiện bằng phương pháp phỏng đoán – một thuật toán học dễ tạo, cung cấp cây quyết định không tối ưu nhưng gần như 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 theo chiến lược chia để trị. Thuật toán bắt đầu bằng cách tạo một nút duy nhất (nút gốc) và tăng trưởng cây quyết định một cách đệ quy và tham lam.

Tại mỗi nút, tất cả các điều kiện có thể xảy ra đề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, bạn chỉ cần biết rằng điểm số là một chỉ số tương quan với nhiệm 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 Palmer Penguins (chim cánh cụt Palmer) (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 có chiều dài mỏ lớn hơn 16 mm, trong khi hầu hết chim cánh cụt Gentoo có mỏ nhỏ hơn. Do đó, điều kiện bill_length_mm ≥ 16 đưa ra kết quả 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 chim cánh cụt Adelie và chim cánh cụt Chinstrap. Thuật toán có thể sẽ chọn điều kiện này.

Hình 7. Bước đầu tiên để trồng cây.

 

Sau đó, thuật toán 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 nào thoả mãn, nút sẽ trở thành một lá. Dự đoán về lá được xác định là giá trị nhãn đại diện nhất trong các ví dụ.

Thuật toán như sau:

Lưu ý: Trừ phi bạn đang triển khai thư viện rừng quyết định của riêng mình, bạn sẽ không cần viết thuật toán này.

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 chi tiết hơn về các bước huấn luyện một cây quyết định cụ thể.

Bước 1: Tạo 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 nào thoả mãn. Vì vậy, hãy biến nút thành một lá:

Bước 4: Phát triển nút #3. Tìm thấy điều kiện "x2 ≥ 0,5". Hai nút con được tạo.

Có các phương pháp khác để phát triển cây quyết định. Một giải pháp thay thế phổ biến là tối ưu hoá các nút trên toàn cục thay vì sử dụng chiến lược chia để trị.

Mã YDF

Trong YDF, cây quyết định được phát triển bằng thuật toán "chia để trị" được mô tả ở trên theo mặc định. Ngoài ra, bạn có thể bật mức tăng trưởng chung bằng thông số 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 đối tượng đầu vào, số lượng điều kiện có thể có cho một nút nhất định có thể 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$, tổ hợp của tất cả giá trị ngưỡng có thể có cho $t \in \mathbb{R}$ là vô hạn.

Quy trình chịu trách nhiệm tìm điều kiện tốt nhất được gọi là splitter (trình phân tách). Vì cần kiểm thử nhiều điều kiện có thể xảy ra, nên bộ chia là nút thắt cổ chai khi huấn luyện cây quyết định.

Điểm số được trình phân tách tối đa hoá phụ thuộc vào tác vụ. Ví dụ:

• Mức tăng 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 cho hồi quy.

Có nhiều thuật toán phân tách, mỗi thuật toán có mức độ hỗ trợ khác nhau cho:

• Loại đặc điểm; ví dụ: số, danh mục, 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 trong tập hợp, điều kiện xiên
• Tiêu chí chuẩn hoá; ví dụ: bộ chia chính xác hoặc gần đúng cho các điều kiện ngưỡng

Ngoài ra, có các biến thể bộ chia tương đương với nhiều điểm đánh đổi khác nhau về mức sử dụng bộ nhớ, mức sử dụng CPU, phân phối điện toán, v.v.

Mã YDF

Trong YDF, các bộ chia được chọn ngầm ẩn từ loại tính năng được phát hiện tự động (hoặc được chỉ định theo cách thủ công), các tham số siêu dữ liệu và tốc độ ước tính của từng bộ chia (trong quá trình huấn luyện, YDF chạy một mô hình nhỏ để dự đoán tốc độ của từng bộ chia đề xuất).