Bài giảng Máy học và mạng neural: Bài 3 - TS. Vũ Đức Lung

Bài 3 cung cấp cho người học những kiến thức về cây quyết định (Decision tree learning). Trong bài này người học có thể tìm hiểu một số nội dung sau: Định nghĩa, giới thiệu về cây quyết định; biểu diễn mô hình/giả thuyết bằng DT, Khả năng ứng dụng của DT, giải thuật học cơ bản,...và một số nội dung khác.
Nội dung trích xuất từ tài liệu:
Bài giảng Máy học và mạng neural: Bài 3 - TS. Vũ Đức Lung 07/08/2013 Bài 03 – Cây quyết định Decision tree learning 1 Nội dung  Định nghĩa, giới thiệu  Biểu diễn mô hình/giả thuyết bằng DT.  Khả năng ứng dụng của DT.  Giải thuật học cơ bản.  Các vấn đề học với cây quyết định  Thuật toán ID3.  Các vấn đề trong DT.  Giới thiệu C4.5. 2 1 07/08/2013 Định Nghĩa  Cây Quyết định là một cây phân lớp  Nút nội : là nút thử nghiệm  Nút lá : nút phân loại ( phân lớp )  Cây phân lớp bằng cách lọc mẫu nhập từ trên xuống  Kết quả là phân biệt và đầy đủ 3 Định Nghĩa Cây quyết định có thể khác nhau trên một số khía cạnh : – Nút thử nghiệm có thể là đơn biến hay đa biến – Có thể có 2 hoặc hơn 2 kết quả đầu ra – Các đặc trưng hoặc thuộc tính có thể là phân loại hoặc là số – Đầu ra (cuối cùng) có thể có hai hoặc nhiều lớp 4 2 07/08/2013 Định Nghĩa  Ví dụ 5 Giới thiệu Cây quyết định là phương pháp suy luận qui nạp được sử dụng và thực hành rộng rãi nhất. Là một phương pháp xấp xỉ hàm mục tiêu của tập các giá trị rời rạc. Cách biểu diễn các hàm học được – Cây quyết định hoặc – Tập các luật if-then mà người có thể đọc được. 6 3 07/08/2013 Giới thiệu (tt) Các phương pháp học được sử dụng rộng rãi: – ID3 – ASSISTANT – C4.5 Nhiệm vụ của các phương pháp học: – Tìm kiếm không gian giả thuyết hoàn chỉnh – Loại bỏ khó khăn của không gian giả thuyết có giới hạn. 7 Cách biểu diễn cây quyết định  Cây quyết định phân loại các thể hiện bằng cách sắp xếp chúng vào một cây từ gốc đến lá – Mỗi node trong cây là một thuộc tính của các thể hiện – Mỗi nhánh là một giá trị có thể có của các thuộc tính này  Cây quyết định được sử dụng trong phân lớp bằng cách duyệt từ nút gốc của cây cho đến khi đụng đến nút lá, từ đó rút ra lớp của đối tượng cần xét 8 4 07/08/2013 Mô hình cây quyết định Ví dụ 1: Playing Tennis. Day Outlook Temp. Humidity Wind Play tennis 1 Sunny Hot High Weak No 2 Sunny Hot High Strong No 3 Overcast Hot High Weak Yes 4 Rain Mild High Weak Yes 5 Rain Cool Normal Weak Yes 6 Rain Cool Normal Strong No 7 Overcast Cool Normal Strong Yes 8 Sunny Mild High Weak No 9 Sunny Cold Normal Weak Yes 10 Rain Mild Normal Weak Yes 11 Sunny Mild Normal Strong Yes 12 Overcast Mild High Strong Yes 13 Overcast Hot Normal Weak Yes 9 14 Rain Mild High Strong No Decision Tree for PlayTennis Outlook Sunny Overcast Rain Humidity Yes Wind High Normal Strong Weak No Yes No Yes 10 5 07/08/2013 Decision Tree for PlayTennis Outlook Sunny Overcast Rain Humidity Each internal node tests an attribute High Normal Each branch corresponds to an attribute value node No Yes Each leaf node assigns a classification 11 Decision Tree for PlayTennis Outlook Temperature Humidity Wind PlayTennis Sunny Hot High Weak ? No Outlook Sunny Overcast Rain Humidity Yes Wind High Normal Strong Weak ...