tailieunhanh - Báo cáo " Một tiêu chuẩn mới chọn nút xây dựng cây quyết định"

Một tiêu chuẩn mới chọn nút xây dựng cây quyết định | TẠP CHI KHOA HỌC VÁ CỒNG NGHỆ Tập 47 số 2 2009 Tr 17-27 MỘT TIỀU CHUẨN MỚI CHỌN NÚT XÀY DỰNG CÂY QUYẾT ĐỊNH NGUYỄN THANH TÚNG 1. MỞ ĐẦU Cho tập mẫu huấn luyện 5 gồm n đối tượng. Mỗi đối tượng X được mô tà bằng một véc tơ x cl x c2 x . c x 1 x trong đó c x là giá trị của thuộc tính điều kiện ck tại đối tượng X k 1 2 . p d x là giá trị thuộc tính quyết định nhãn lớp . Bài toán phân lớp là bài toán tim quy tắc xếp các đối tượng vào một trong các lớp đã cho dựa trên tập mẫu huấn luyện s. Có nhiêu phương pháp tiếp cận bài toán phân lớp Hàm phân biệt tuyến tính Fisher Naive Bayes Logistic Mạng nơ-ron Cây quyết định . trong đó phương pháp cây quyết định là phương pháp phổ biến do tính trực quan dễ hiểu và hiệu quà cùa nó I 0 Cây quyết định là một cấu trúc cây biểu diễn một vấn đề quyết định. Mỗi nút trong không phải nút lá gắn với một thuộc tính điều kiện mỗi nhánh từ nút trong gan với một giá trị hay một tập các giá trị của thuộc tính điều kiện tương ứng mỗi nút lá gắn với một giá trị thuộc tính quyết định thuộc tính đích . Cây quyết định được xây dựng dựa trên một tập dữ liệu huấn luyện bao gồm các đối tượng mẫu. Mỗi đối tượng được mô tả bởi một tập giá trị các thuộc tính và nhãn lớp. Đe xây dựng cây quyết định tại mỗi nút trong cần xác định một thuộc tính thích hợp để kiểm tra phân chia dữ liệu thành các tập con. Quá trình xây dựng một cây quyêt định cụ thê bát đầu bằng một cây rỗng toàn bộ tập mẫu huấn luyện và là như sau 8 1. Nếu tại nút hiện thòi tất cả các đối tượng huấn luyện đều thuộc vào một lớp nào đó thi cho nút này thành nút lá có tên là nhãn lớp chung của các đối tượng. 2. Trường họp ngược lại sử dụng một độ đo chọn thuộc tính điều kiện phân chia tốt nhất tập mẫu huấn luyện có tại nút. 3. Tạo một lượng nút con cùa của nút hiện thời bằng số các giá trị khác nhau của thuộc tính được chọn. Gán cho mỗi nhánh từ nút cha đến nút con một giá trị của thuộc tính rồi phân chia các các đối tượng huấn luyện vào các nút con tương ứng. 4. Nút con l được gọi là thuần nhất