Hướng xây dựng cây quyết định với chi phí hiệu quả

Abstract

Cây quyết định là một kỹ thuật máy học phổ biến có nhiều ứng dụng trong thực tế. Cây quyết định có thể được mở rộng để bao gồm chi phí liên quan đến mỗi lần kiểm thử, cho phép ưu tiên về không gian đặc trưng. Bài toán giảm thiểu chi phí dự kiến của một cây quyết định được gọi là bài toán NP- đầy đủ. Kết quả là, hầu hết các phương pháp tiếp cận để tạo cây quyết định đều dựa vào một heuristic. Luận văn này nhằm mở rộng các phƣơng pháp được sử dụng trong các nghiên cứu trước đây để tìm kiếm các cây quyết định với một chi phí dự kiến nhỏ hơn so với cách sử dụng một heuristic đơn giản. Ngược lại với các nghiên cứu trước đây về các cây quyết định nhỏ hơn sử dụng các phương pháp tiếp cận chính xác, nhiều nghiên cứu cho rằng các phương pháp tiếp cận chính xác nói chung không tìm ra các cây quyết định thấp hơn các cách tiếp cận heuristic. Luận văn chỉ ra sự thành công của các nghiên cứu trước đây về vấn đề giảm thiểu kích thước cây quyết định phụ thuộc một phần vào việc chuyển đổi dữ liệu sang dạng nhị phân. Chuyển đổi này sử dụng các giá trị của thuộc tính như là các phép thử nhị phân thay vì các thuộc tính khi xây dựng cây quyết định. Phương pháp chuyển đổi dữ liệu sang dạng nhị phân được kiểm tra chi tiết và thông qua nhiều phép đo dữ liệu