Bài giảng Học máy: Bài 5 - Nguyễn Hoàng Long

Chia sẻ: Minh Vũ | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

27
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Học máy - Bài 5: Cây phân loại và hồi quy" cung cấp cho người học các kiến thức: Các giải thuật học máy, cây quyết định, biểu diễn cây quyết định, tập luật từ cây quyết định,... Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Học máy: Bài 5 - Nguyễn Hoàng Long

Cây phân loại và hồi quy Nguyễn Thanh Tùng Khoa Công nghệ thông tin – Đại học Thủy Lợi tungnt@tlu.edu.vn Website môn học: https://sites.google.com/a/wru.vn/cse445fall2016 Bài giảng có sử dụng hình vẽ trong cuốn sách “An Introduction to Statistical Learning with Applications in R” với sự cho phép của tác giả, có sử dụng slides các khóa học CME250 của ĐH Stanford và IOM530 của ĐH Southern California CSE 445: Học máy | Học kỳ 1, 2016-2017 1
Các giải thuật Học máy Do you have labeled data? Yes No Supervised Unsupervised What do you want to predict? Do you want to group the data? Category Quantity Yes No Classiﬁcation Regression Cluster Dimensionality Analysis Reduction KNN LASSO ICA PCA Logistic Linear Hierarchical Regression Regression Clustering K--means NMF SOM CSE 445: Học máy | Học kỳ 1, 2016-2017 2
Các giải thuật Học máy Do you have labeled data? Yes No Supervised Unsupervised What do you want to predict? Do you want to group the data? Category Quantity Yes No Classiﬁcation Regression Cluster Dimensionality Analysis Reduction KNN CART LASSO ICA PCA Logistic Linear Hierarchical Regression Regression Clustering K--means NMF SOM CSE 445: Học máy | Học kỳ 1, 2016-2017 3
Cây quyết định (Decision tree) CSE 445: Học máy | Học kỳ 1, 2016-2017 4
Cây quyết định là gì? • Học cây quyết định (Decision tree –DT– learning) • Để học (xấp xỉ) một hàm mục tiêu có giá trị rời rạc (discrete- valued target function) – hàm phân lớp • Hàm phân lớp được biểu diễn bởi một cây quyết định • Một cây quyết định có thể được biểu diễn (diễn giải) bằng một tập các luật IF-THEN (dễ đọc và dễ hiểu) • Học cây quyết định có thể thực hiện ngay cả với các dữ liệu có chứa nhiễu/lỗi (noisy data) • Được áp dụng thành công trong rất nhiều các bài toán ứng dụng thực tế nguồn: Nguyễn Nhật Quang-Học máy CSE 445: Học máy | Học kỳ 1, 2016-2017 5
Cây quyết định là gì? “sport”? is present is absent “player”? “football”? is present is absent is present is absent Interested Uninterested Interested “goal”? is present is absent Ví dụ về DT: Những tin tức nào mà tôi quan tâm? Interested Uninterested • (…,“sport”,…,“player”,…) → Interested • (…,“goal”,…) → Interested • (…,“sport”,…) → Uninterested nguồn: Nguyễn Nhật Quang-Học máy CSE 445: Học máy | Học kỳ 1, 2016-2017 6
Cây quyết định là gì? Outlook=? Sunny Rain Overcast Humidity=? Yes Windy=? High Normal True False No Yes No Yes • (Outlook=Overcast, Temperature=Hot, Humidity=High, Windy=False) → Yes • (Outlook=Rain, Temperature=Mild, Humidity=High, Windy=True) → No • (Outlook=Sunny, Temperature=Hot, Humidity=High, Windy=True) → No Ví dụ về DT: Một người có chơi tennis không? CSE 445: Học máy | Học kỳ 1, 2016-2017 7
Cây quyết định là gì? Hastie, Trevor, et al. The elements of statistical learning. Vol. 2. No. 1. New York: Springer, 2009. CSE 445: Học máy | Học kỳ 1, 2016-2017 8
Cây quyết định là gì? Hastie, Trevor, et al. The elements of statistical learning. Vol. 2. No. 1. New York: Springer, 2009. CSE 445: Học máy | Học kỳ 1, 2016-2017 9
Cây quyết định là gì? ĐÚNG SAI Hastie, Trevor, et al. The elements of statistical learning. Vol. 2. No. 1. New York: Springer, 2009. CSE 445: Học máy | Học kỳ 1, 2016-2017 10
Dữ liệu đầu vào của cây quyết định CSE 445: Học máy | Học kỳ 1, 2016-2017 11
Biểu diễn cây quyết định • Mỗi nút trong (internal node) biểu diễn một biến cần kiểm tra giá trị (a variable to be tested) đối với các mẫu • Mỗi nhánh (branch) từ một nút sẽ tương ứng với một giá trị có thể của biến gắn với nút đó • Mỗi nút lá (leaf node) biểu diễn một phân lớp (a classification) • Một cây quyết định học được sẽ phân lớp đối với một mẫu, bằng cách duyệt cây từ nút gốc đến một nút lá → Nhãn lớp gắn với nút lá đó sẽ được gán cho mẫu cần phân lớp CSE 445: Học máy | Học kỳ 1, 2016-2017 12
Minh họa cây quyết định Children 0 Married Realincom e YES NO 14996.4 Mortgage Mortgage No Yes NO YES NO YES No Save_act Yes Save_act YES NO YES NO No Yes No Yes CSE 445: Học máy | Học kỳ 1, 2016-2017 13
Tập luật từ cây quyết định Rule #1 Rule #3 if children =< 0 if children =< 0 and married == YES and married == NO and mortgage == YES and mortgage == YES and save_act == NO and save_act == NO then -> YES (9.0, 0.889) then -> YES (3.0, 1.0) Rule #2 Rule #4 if children =< 0 if children > 0 and married == NO and realincome > 14996.4 and mortgage == NO then -> YES (85.0, 0.953) then -> YES (29.0, 0.931) CSE 445: Học máy | Học kỳ 1, 2016-2017 14
Tập luật từ cây quyết định Rule #1 Rule #3 if children =< 0 if children =< 0 and married == YES and married == NO and mortgage == NO and mortgage == YES then -> NO (59.0, 0.898) and save_act == YES then -> NO (12.0, 1.0) Rule #2 if children =< 0 Rule #4 and married == YES if children > 0 and mortgage == YES and realincome =< 14996.4 and save_act == YES then -> NO (87.0, 0.908) then -> NO (16.0, 0.875 CSE 445: Học máy | Học kỳ 1, 2016-2017 15
Biểu diễn cây quyết định • Một cây quyết định biểu diễn một phép tuyển (disjunction) của các kết hợp (conjunctions) của các ràng buộc đối với các giá trị thuộc tính của các mẫu • Mỗi đường đi (path) từ nút gốc đến một nút lá sẽ tương ứng với một kết hợp (conjunction) của các kiểm tra giá trị biến (variable tests) • Cây quyết định (bản thân nó) chính là một phép tuyển của các kết hợp này CSE 445: Học máy | Học kỳ 1, 2016-2017 16
Tập dữ liệu Weather Xét tập dữ liệu Weather ghi lại những ngày mà một người chơi (không chơi) tennis: Day Outlook Temperature Humidity Windy Play Tennis D1 Sunny Hot High FALSE No D2 Sunny Hot High TRUE No D3 Overcast Hot High FALSE Yes D4 Rain Mild High FALSE Yes D5 Rain Cool Normal FALSE Yes D6 Rain Cool Normal TRUE No D7 Overcast Cool Normal TRUE Yes D8 Sunny Mild High FALSE No D9 Sunny Cool Normal FALSE Yes D10 Rain Mild Normal FALSE Yes D11 Sunny Mild Normal TRUE Yes D12 Overcast Mild High TRUE Yes D13 Overcast Hot Normal FALSE Yes [Mitchell, D14 Rain Mild High TRUE No 1997] CSE 445: Học máy | Học kỳ 1, 2016-2017 17
Mô hình cây QĐ có (không) chơi tennis Outlook sunny overcast rainy [(Outlook=Sunny) ∧ (Humidity=Normal)] ∨ yes (Outlook=Overcast) ∨ Humidity Windy [(Outlook=Rain) ∧ (Windy=False)] high normal TRUE FALSE no yes no yes CSE 445: Học máy | Học kỳ 1, 2016-2017 18
Xây dựng cây QĐ thế nào? Phương pháp dựng cây theo Top-down Ban đầu, tất cả các mẫu trong tập huấn luyện đều đặt tại nút gốc. Tách các mẫu theo đệ quy bằng cách chọn 1 thuộc tính trong mỗi lần tách cho đến khi gặp điều kiện dừng. Phương pháp tỉa cây theo Bottom-up Ban đầu dựng cây lớn nhất có thể Chuyển phần cây con hoặc nhánh từ phần đáy của cây lên nhằm cải thiện tính chính xác khi dự đoán mẫu mới CSE 445: Học máy | Học kỳ 1, 2016-2017 19
Giải thuật ID3 • Thực hiện giải thuật tìm kiếm tham lam (greedy search) đối với không gian các cây quyết định có thể • Xây dựng (học) một cây quyết định theo chiến lược top-down, bắt đầu từ nút gốc • Ở mỗi nút, biến kiểm tra (test variable) là biến có khả năng phân loại tốt nhất đối với các mẫu gắn với nút đó • Tạo mới một cây con (sub-tree) của nút hiện tại cho mỗi giá trị có thể của biến kiểm tra, và tập huấn luyện sẽ được tách ra (thành các tập con) tương ứng với cây con vừa tạo • Mỗi biến chỉ được phép xuất hiện tối đa 1 lần đối với bất kỳ một đường đi nào trong cây • Quá trình phát triển (học) cây quyết định sẽ tiếp tục cho đến khi: Cây quyết định phân loại hoàn toàn (perfectly classifies) các mẫu, hoặc tất cả các thuộc tính đã được sử dụng CSE 445: Học máy | Học kỳ 1, 2016-2017 20