Chương 4: Phân lớp và dự báo

Tổng quan Chương 4: Phân lớp và dự báo • Phân lớp là gì? • Dự báo là gì? • Giới thiệu cây quyết định • Phân lớp kiểu Bayes • Những phương pháp phân lớp khác • Độ chính xác trong phân lớp Phân lớp là gì? Chương 4: Phân lớp và dự báo • Mục đích: dự đoán những nhãn phân lớp cho các bộ dữ liệu/mẫu mới • Đầu vào: một tập các mẫu dữ liệu huấn luyện, với một nhãn phân lớp cho mỗi mẫu dữ liệu • Đầu ra: mô hình (bộ phân lớp) dựa trên tập huấn luyện và những nhãn phân lớp Ứng dụng phân lớp Chương 4: Phân lớp và dự báo • Tín dụng • Tiếp thị • Chẩn đoán y khoa • Phân tích hiệu quả điều trị • .... Dự đoán là gì? Chương 4: Phân lớp và dự báo • Tương tự với phân lớp: - Xây dựng một mô hình - Sử dụng mô hình để dự đoán cho những giá trị chưa biết • Phương thức chủ đạo: - Hồi quy tuyến tính và nhiều cấp - Hồi quy không tuyến tính Quy trình phân lớp Chương 4: Phân lớp và dự báo • Bước 1: Xây dựng mô hình - Mô tả các lớp xác định trước - Tìm luật phân lớp • Bước 2: Sử dụng mô hình - Phân lớp các đối tượng chưa biết - Xác định độ chính xác của mô hình Các kỹ thuật phân lớp Chương 4: Phân lớp và dự báo • Phương pháp sử dụng cây quyết định • Phương pháp phân lớp xác suất Bayes • Mạng Nơron • Tập thô • ...... Phân lớp dựa trên cây quyết định Chương 4: Phân lớp và dự báo Cây quyết định: là một cấu trúc phân cấp của các nút và các nhánh biểu diễn dưới dạng cây. 1. Dữ liệu dạng các bản ghi: (x,y)=(x1,x2,x3,..,xk,y) Trong đó: - y: là biến phụ thuộc cần phân loại - xi: là các biến độc lập giúp phân loại 2. Có 3 loại nút: - Nút gốc: đỉnh trên cùng của cây - Nút trong: biểu diễn một thuộc tính - Nút lá: lớp quyết định 3. Nhánh: biểu diễn giá trị có thể có của thuộc tính Các kiểu cây quyết định Chương 4: Phân lớp và dự báo  Cây hồi quy (Regression tree): Uớc lượng các hàm có giá trị là số thực Ví dụ: ước tính giá một ngôi nhà, khoảng thời gian một bệnh nhân nằm viện  Cây phân loại (Classification tree): Phân loại theo các thuộc tính quyết định Ví dụ: kết quả của một trận đấu (thắng hay thua). Ví dụ cây quyết định Chương 4: Phân lớp và dự báo Dữ liệu chơi golf Các biến độc lập Biến phụ thuộc Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Nóng Cao Nhẹ Không Nắng Nóng Cao Mạnh Không Âm u Nóng Cao Nhẹ Có Mưa Ấm áp Cao Nhẹ Có Mưa Mát Trung bình Nhẹ Có Mưa Mát Trung bình Mạnh Không Âm u Mát Trung bình Mạnh Có Nắng Ấm áp Cao Nhẹ Không Nắng Mát Trung bình Nhẹ Có Mưa Ấm áp Trung bình Nhẹ Có Nắng Ấm áp Trung bình Mạnh Có Âm u Ấm áp Cao Mạnh Có Âm u Nóng Trung bình Nhẹ Có Mưa Ấm áp Cao Mạnh Không Tập dữ liệu huấn luyện Ví dụ cây quyết định Chương 4: Phân lớp và dự báo Giải thuật quy nạp cây ID3 Chương 4: Phân lớp và dự báo  Đầu vào: Một tập hợp các tập huấn luyện. Mỗi tập huấn luyện bao gồm các thuộc tính mô tả một tình huống, hay một đối tượng nào đó, và một giá trị phân loại của nó. Ví dụ: - Thuộc tính mô tả (Quang cảnh, Gió,..) - Thuộc tính phân loại (Chơi Tennis?)  Đầu ra: Cây quyết định - Có khả năng phân loại đúng đắn các ví dụ trong tập dữ liệu rèn luyện - Phân loại đúng cho cả các ví dụ chưa gặp trong tương lai. Giải thuật quy nạp cây ID3 Chương 4: Phân lớp và dự báo Function Induce_tree(tập_ví_dụ, tập_thuộc_tính) if mọi ví dụ trong tập_ví_dụ đều nằm trong cùng một lớp then return một nút lá được gán nhãn bởi lớp đó else if tập_thuộc_tính là rỗng then return nút lá được gán nhãn bởi tuyển của tất cả các lớp trong tập_ví_dụ else - chọn một thuộc tính P, lấy nó làm gốc cho cây hiện tại; - xóa P ra khỏi tập_thuộc_tính; For mỗi giá trị V của P - tạo một nhánh của cây gán nhãn V; - Đặt vào phân_vùngV các ví dụ trong tập_ví_dụ có giá trị V tại thuộc tính P; - Gọi Induce_tree(phân_vùngV, tập_thuộc_tính), gắn kết quả vào nhánh V End For End If End Function Thuộc tính dùng để phân loại tốt nhất? Chương 4: Phân lớp và dự báo Độ đo độ hỗn loạn Entropy: Gọi S là tập ví dụ  Thành viên của S là một ví dụ Trong đó: mỗi ví dụ thuộc một lớp quyết định hay có một giá trị phân loại. • 0<Entropy(S)<1  Tập ví dụ S có số lượng ví dụ thuộc các loại khác nhau • Entropy(S) = 0  Tập ví dụ S chỉ toàn ví dụ thuộc cùng một loại, hay S là thuần nhất. • Entropy(S) = 1  tập ví dụ S có các ví dụ thuộc các loại khác nhau với độ pha trộn là cao nhất. Thuộc tính dùng để phân loại tốt nhất? Chương 4: Phân lớp và dự báo Độ đo độ hỗn loạn Entropy: Tập S là tập dữ liệu rèn luyện. Giả sử thuộc tính phân loại có hai giá trị (Y/N) Ta gọi: - pY là phần các ví dụ có thuộc tính Y trong tập S. - pN là phần các ví dụ có thuộc tính N trong tập S. Khi đó: Entropy(S) = -pYlog2pY – pNlog2pN Tổng quát cho tập S có nhiều hơn n thuộc tính phân loại (n>2): Entropy(S) =    C 1i i2i plogp Thuộc tính dùng để phân loại tốt nhất? Chương 4: Phân lớp và dự báo Độ đo độ lợi thông tin Information Gain: - Phép đo này gọi là lượng thông tin thu được - Lượng giảm entropy bị gây ra bởi việc phân chia các ví dụ theo thuộc tính này. Tập S là tập dữ liệu rèn luyện Độ lợi thông tin Gain(S,A) của thuộc tính A trên tập S, được định nghĩa như sau: Trong đó: - Values(A) là tập hợp có thể có các giá trị của thuộc tính A - SV là tập con của S chứa các ví dụ có thuộc tính A mang giá trị v. )Entropy(S |S| |S| Entropy(S)A)Gain(S, v Values(A)v v   Xây dựng cây quyết định Chương 4: Phân lớp và dự báo Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Nóng Cao Nhẹ Không Nắng Nóng Cao Mạnh Không Âm u Nóng Cao Nhẹ Có Mưa Ấm áp Cao Nhẹ Có Mưa Mát Trung bình Nhẹ Có Mưa Mát Trung bình Mạnh Không Âm u Mát Trung bình Mạnh Có Nắng Ấm áp Cao Nhẹ Không Nắng Mát Trung bình Nhẹ Có Mưa Ấm áp Trung bình Nhẹ Có Nắng Ấm áp Trung bình Mạnh Có Âm u Ấm áp Cao Mạnh Có Âm u Nóng Trung bình Nhẹ Có Mưa Ấm áp Cao Mạnh Không Tập dữ liệu huấn luyện 1. Độ hỗn loạn của tập dữ liệu: Entropy(S) = - ( 𝟗 𝟏𝟒 ) log2 ( 𝟗 𝟏𝟒 ) - ( 𝟓 𝟏𝟒 ) log2( 𝟓 𝟏𝟒 ) = 0.940 Xây dựng cây quyết định Chương 4: Phân lớp và dự báo Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Nóng Cao Nhẹ Không Nắng Nóng Cao Mạnh Không Âm u Nóng Cao Nhẹ Có Mưa Ấm áp Cao Nhẹ Có Mưa Mát Trung bình Nhẹ Có Mưa Mát Trung bình Mạnh Không Âm u Mát Trung bình Mạnh Có Nắng Ấm áp Cao Nhẹ Không Nắng Mát Trung bình Nhẹ Có Mưa Ấm áp Trung bình Nhẹ Có Nắng Ấm áp Trung bình Mạnh Có Âm u Ấm áp Cao Mạnh Có Âm u Nóng Trung bình Nhẹ Có Mưa Ấm áp Cao Mạnh Không Tập dữ liệu huấn luyện 2. Tính Gain cho từng thuộc tính: Thuộc tính “Quang cảnh” Gain(S, Quang cảnh) = Entropy(S) – ( 𝟓 𝟏𝟒 )Entropy(SNắng) – ( 𝟒 𝟏𝟒 )Entropy(SÂm u) – ( 𝟓 𝟏𝟒 ) Entropy(SMưa) = 0.940 – ( 𝟓 𝟏𝟒 )(- ( 𝟐 𝟓 )log2( 𝟐 𝟓 ) – ( 𝟑 𝟓 )log2( 𝟑 𝟓 )) - ( 𝟒 𝟏𝟒 )(0) - ( 𝟓 𝟏𝟒 )(- ( 𝟑 𝟓 )log2( 𝟑 𝟓 ) – ( 𝟐 𝟓 )log2( 𝟐 𝟓 )) = 0.246 Quang cảnh Âm u Nắng Mưa Chơi: 2 Không: 3 Chơi: 4 Không: 0 Chơi: 3 Không: 2 Xây dựng cây quyết định Chương 4: Phân lớp và dự báo Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Nóng Cao Nhẹ Không Nắng Nóng Cao Mạnh Không Âm u Nóng Cao Nhẹ Có Mưa Ấm áp Cao Nhẹ Có Mưa Mát Trung bình Nhẹ Có Mưa Mát Trung bình Mạnh Không Âm u Mát Trung bình Mạnh Có Nắng Ấm áp Cao Nhẹ Không Nắng Mát Trung bình Nhẹ Có Mưa Ấm áp Trung bình Nhẹ Có Nắng Ấm áp Trung bình Mạnh Có Âm u Ấm áp Cao Mạnh Có Âm u Nóng Trung bình Nhẹ Có Mưa Ấm áp Cao Mạnh Không Tập dữ liệu huấn luyện 2. Tính Gain cho từng thuộc tính: Thuộc tính “Nhiệt độ” Gain(S, Nhiệt độ) = Entropy(S) – ( 𝟒 𝟏𝟒 )Entropy(SNóng) – ( 𝟔 𝟏𝟒 )Entropy(SẤm áp) – ( 𝟒 𝟏𝟒 ) Entropy(SMát) = 0.940 – ( 𝟒 𝟏𝟒 )(1) - ( 𝟔 𝟏𝟒 )(- ( 𝟒 𝟔 )log2( 𝟒 𝟔 ) – ( 𝟐 𝟔 )log2( 𝟐 𝟔 )) - ( 𝟒 𝟏𝟒 )(- ( 𝟑 𝟒 )log2( 𝟑 𝟒 ) – ( 𝟏 𝟒 )log2( 𝟏 𝟒 )) = 0.029 Nhiệt độ Ấm áp Nóng Mát Chơi: 2 Không: 2 Chơi: 4 Không: 2 Chơi: 3 Không: 1 Xây dựng cây quyết định Chương 4: Phân lớp và dự báo Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Nóng Cao Nhẹ Không Nắng Nóng Cao Mạnh Không Âm u Nóng Cao Nhẹ Có Mưa Ấm áp Cao Nhẹ Có Mưa Mát Trung bình Nhẹ Có Mưa Mát Trung bình Mạnh Không Âm u Mát Trung bình Mạnh Có Nắng Ấm áp Cao Nhẹ Không Nắng Mát Trung bình Nhẹ Có Mưa Ấm áp Trung bình Nhẹ Có Nắng Ấm áp Trung bình Mạnh Có Âm u Ấm áp Cao Mạnh Có Âm u Nóng Trung bình Nhẹ Có Mưa Ấm áp Cao Mạnh Không Tập dữ liệu huấn luyện 2. Tính Gain cho từng thuộc tính: Thuộc tính “Gió” Gain(S, Gió) = Entropy(S) – ( 𝟔 𝟏𝟒 )Entropy(SMạnh) – ( 𝟖 𝟏𝟒 )Entropy(SNhẹ) = 0.940 – ( 𝟔 𝟏𝟒 )(1) - ( 𝟖 𝟏𝟒 )(- ( 𝟔 𝟖 )log2( 𝟔 𝟖 ) – ( 𝟐 𝟖 )log2( 𝟐 𝟖 )) = 0.048 Gió Mạnh Nhẹ Chơi: 3 Không: 3 Chơi: 6 Không: 2 Xây dựng cây quyết định Chương 4: Phân lớp và dự báo Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Nóng Cao Nhẹ Không Nắng Nóng Cao Mạnh Không Âm u Nóng Cao Nhẹ Có Mưa Ấm áp Cao Nhẹ Có Mưa Mát Trung bình Nhẹ Có Mưa Mát Trung bình Mạnh Không Âm u Mát Trung bình Mạnh Có Nắng Ấm áp Cao Nhẹ Không Nắng Mát Trung bình Nhẹ Có Mưa Ấm áp Trung bình Nhẹ Có Nắng Ấm áp Trung bình Mạnh Có Âm u Ấm áp Cao Mạnh Có Âm u Nóng Trung bình Nhẹ Có Mưa Ấm áp Cao Mạnh Không Tập dữ liệu huấn luyện 2. Tính Gain cho từng thuộc tính: Thuộc tính “Độ ẩm” Gain(S, Độ ẩm) = Entropy(S) – ( 𝟕 𝟏𝟒 )Entropy(SCao) – ( 𝟕 𝟏𝟒 )Entropy(ST.Bình) = 0.940 – ( 𝟕 𝟏𝟒 )(- ( 𝟑 𝟕 )log2( 𝟑 𝟕 ) – ( 𝟒 𝟕 )log2( 𝟒 𝟕 )) - ( 𝟕 𝟏𝟒 )(- ( 𝟔 𝟕 )log2( 𝟔 𝟕 ) – ( 𝟏 𝟕 )log2( 𝟏 𝟕 )) = 0.151 Độ ẩm Cao T.bình Chơi: 3 Không: 4 Chơi: 6 Không: 1 Xây dựng cây quyết định Chương 4: Phân lớp và dự báo Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Nóng Cao Nhẹ Không Nắng Nóng Cao Mạnh Không Âm u Nóng Cao Nhẹ Có Mưa Ấm áp Cao Nhẹ Có Mưa Mát Trung bình Nhẹ Có Mưa Mát Trung bình Mạnh Không Âm u Mát Trung bình Mạnh Có Nắng Ấm áp Cao Nhẹ Không Nắng Mát Trung bình Nhẹ Có Mưa Ấm áp Trung bình Nhẹ Có Nắng Ấm áp Trung bình Mạnh Có Âm u Ấm áp Cao Mạnh Có Âm u Nóng Trung bình Nhẹ Có Mưa Ấm áp Cao Mạnh Không Tập dữ liệu huấn luyện 3. Xác định thuộc tính làm nút gốc: Thuộc tính “Quang cảnh” có độ lợi thông tin cao nhất nên được chọn làm nút gốc. Quang cảnh Chơi - Không chơi Chơi - Không chơi Chơi Nắng Âm u Mưa Xây dựng cây quyết định Chương 4: Phân lớp và dự báo Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Nóng Cao Nhẹ Không Nắng Nóng Cao Mạnh Không Âm u Nóng Cao Nhẹ Có Mưa Ấm áp Cao Nhẹ Có Mưa Mát Trung bình Nhẹ Có Mưa Mát Trung bình Mạnh Không Âm u Mát Trung bình Mạnh Có Nắng Ấm áp Cao Nhẹ Không Nắng Mát Trung bình Nhẹ Có Mưa Ấm áp Trung bình Nhẹ Có Nắng Ấm áp Trung bình Mạnh Có Âm u Ấm áp Cao Mạnh Có Âm u Nóng Trung bình Nhẹ Có Mưa Ấm áp Cao Mạnh Không Tập dữ liệu huấn luyện 3. Sau khi lập được cấp đầu tiên của cây quyết định ta lại xét nhánh Nắng: Độ hỗn loạn của tập SNắng: Entropy(SNắng) = - ( 𝟑 𝟓 ) log2 ( 𝟑 𝟓 ) - ( 𝟐 𝟓 ) log2( 𝟐 𝟓 ) = 0.971 Xây dựng cây quyết định Chương 4: Phân lớp và dự báo Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Nóng Cao Nhẹ Không Nắng Nóng Cao Mạnh Không Âm u Nóng Cao Nhẹ Có Mưa Ấm áp Cao Nhẹ Có Mưa Mát Trung bình Nhẹ Có Mưa Mát Trung bình Mạnh Không Âm u Mát Trung bình Mạnh Có Nắng Ấm áp Cao Nhẹ Không Nắng Mát Trung bình Nhẹ Có Mưa Ấm áp Trung bình Nhẹ Có Nắng Ấm áp Trung bình Mạnh Có Âm u Ấm áp Cao Mạnh Có Âm u Nóng Trung bình Nhẹ Có Mưa Ấm áp Cao Mạnh Không Tập dữ liệu huấn luyện 4. Tính Gain cho từng thuộc tính: Thuộc tính “Nhiệt độ” Gain(SNắng, Nhiệt độ) = Entropy(SNắng) – ( 𝟐 𝟓 )Entropy(SNóng) – ( 𝟐 𝟓 )Entropy(SẤm áp) – ( 𝟏 𝟓 ) Entropy(SMát) = 0.971 – ( 𝟐 𝟓 )(0) - ( 𝟐 𝟓 )(1) - ( 𝟏 𝟓 )(0) = 0.571 Quang cảnh Ấm áp Nóng Mát Chơi: 0 Không: 2 Chơi: 1 Không: 1 Chơi: 1 Không: 0 Nhiệt độ Nắng Xây dựng cây quyết định Chương 4: Phân lớp và dự báo Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Nóng Cao Nhẹ Không Nắng Nóng Cao Mạnh Không Âm u Nóng Cao Nhẹ Có Mưa Ấm áp Cao Nhẹ Có Mưa Mát Trung bình Nhẹ Có Mưa Mát Trung bình Mạnh Không Âm u Mát Trung bình Mạnh Có Nắng Ấm áp Cao Nhẹ Không Nắng Mát Trung bình Nhẹ Có Mưa Ấm áp Trung bình Nhẹ Có Nắng Ấm áp Trung bình Mạnh Có Âm u Ấm áp Cao Mạnh Có Âm u Nóng Trung bình Nhẹ Có Mưa Ấm áp Cao Mạnh Không Tập dữ liệu huấn luyện 4. Tính Gain cho từng thuộc tính: Thuộc tính “Gió” Gain(SNắng, Gió) = Entropy(SNắng) – ( 𝟐 𝟓 )Entropy(SNhẹ) – ( 𝟑 𝟓 )Entropy(SMạnh) = 0.971 – ( 𝟐 𝟓 )(1) - ( 𝟑 𝟓 )(-( 𝟏 𝟑 )log2(( 𝟏 𝟑 )-( 𝟐 𝟑 )log2( 𝟐 𝟑 )) = 0.020 Quang cảnh Nhẹ Mạnh Chơi: 1 Không: 1 Chơi: 1 Không: 2 Gió Nắng Xây dựng cây quyết định Chương 4: Phân lớp và dự báo Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Nóng Cao Nhẹ Không Nắng Nóng Cao Mạnh Không Âm u Nóng Cao Nhẹ Có Mưa Ấm áp Cao Nhẹ Có Mưa Mát Trung bình Nhẹ Có Mưa Mát Trung bình Mạnh Không Âm u Mát Trung bình Mạnh Có Nắng Ấm áp Cao Nhẹ Không Nắng Mát Trung bình Nhẹ Có Mưa Ấm áp Trung bình Nhẹ Có Nắng Ấm áp Trung bình Mạnh Có Âm u Ấm áp Cao Mạnh Có Âm u Nóng Trung bình Nhẹ Có Mưa Ấm áp Cao Mạnh Không Tập dữ liệu huấn luyện 4. Tính Gain cho từng thuộc tính: Thuộc tính “Độ ẩm” Gain(SNắng, Độ ẩm) = Entropy(SNắng) – ( 𝟑 𝟓 )Entropy(SCao) – ( 𝟐 𝟓 )Entropy(ST.Bình) = 0.971 – ( 𝟑 𝟓 )(0) - ( 𝟐 𝟓 )(0) = 0.971 Quang cảnh Cao T.Bình Chơi: 0 Không: 3 Chơi: 2 Không: 0 Độ ẩm Nắng Xây dựng cây quyết định Chương 4: Phân lớp và dự báo Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Nóng Cao Nhẹ Không Nắng Nóng Cao Mạnh Không Âm u Nóng Cao Nhẹ Có Mưa Ấm áp Cao Nhẹ Có Mưa Mát Trung bình Nhẹ Có Mưa Mát Trung bình Mạnh Không Âm u Mát Trung bình Mạnh Có Nắng Ấm áp Cao Nhẹ Không Nắng Mát Trung bình Nhẹ Có Mưa Ấm áp Trung bình Nhẹ Có Nắng Ấm áp Trung bình Mạnh Có Âm u Ấm áp Cao Mạnh Có Âm u Nóng Trung bình Nhẹ Có Mưa Ấm áp Cao Mạnh Không Tập dữ liệu huấn luyện 5. Xác định thuộc tính làm nút gốc: Thuộc tính “Độ ẩm” có độ lợi thông tin cao nhất trong nhánh Nắng nên được chọn làm nút gốc. Quang cảnh Chơi - Không chơi Chơi Nắng Âm u Mưa Độ ẩm Cao Không Chơi T.Bình Xây dựng cây quyết định Chương 4: Phân lớp và dự báo Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Nóng Cao Nhẹ Không Nắng Nóng Cao Mạnh Không Âm u Nóng Cao Nhẹ Có Mưa Ấm áp Cao Nhẹ Có Mưa Mát Trung bình Nhẹ Có Mưa Mát Trung bình Mạnh Không Âm u Mát Trung bình Mạnh Có Nắng Ấm áp Cao Nhẹ Không Nắng Mát Trung bình Nhẹ Có Mưa Ấm áp Trung bình Nhẹ Có Nắng Ấm áp Trung bình Mạnh Có Âm u Ấm áp Cao Mạnh Có Âm u Nóng Trung bình Nhẹ Có Mưa Ấm áp Cao Mạnh Không Tập dữ liệu huấn luyện 6. Xét nhánh Mưa: Độ hỗn loạn của tập SMưa: Entropy(SMưa) = - ( 𝟑 𝟓 ) log2 ( 𝟑 𝟓 ) - ( 𝟐 𝟓 ) log2( 𝟐 𝟓 ) = 0.971 Xây dựng cây quyết định Chương 4: Phân lớp và dự báo Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Nóng Cao Nhẹ Không Nắng Nóng Cao Mạnh Không Âm u Nóng Cao Nhẹ Có Mưa Ấm áp Cao Nhẹ Có Mưa Mát Trung bình Nhẹ Có Mưa Mát Trung bình Mạnh Không Âm u Mát Trung bình Mạnh Có Nắng Ấm áp Cao Nhẹ Không Nắng Mát Trung bình Nhẹ Có Mưa Ấm áp Trung bình Nhẹ Có Nắng Ấm áp Trung bình Mạnh Có Âm u Ấm áp Cao Mạnh Có Âm u Nóng Trung bình Nhẹ Có Mưa Ấm áp Cao Mạnh Không Tập dữ liệu huấn luyện 7. Tính Gain cho từng thuộc tính: Thuộc tính “Nhiệt độ” Gain(SMưa, Nhiệt độ) = Entropy(SMưa) – ( 𝟑 𝟓 )Entropy(SẤm áp) – ( 𝟐 𝟓 )Entropy(SMát) = 0.971 – ( 𝟑 𝟓 )(-( 𝟐 𝟑 )log2( 𝟐 𝟑 )-( 𝟏 𝟑 )log2( 𝟏 𝟑 )) - ( 𝟐 𝟓 )(1) = 0.020 Quang cảnh Ấm áp Nóng Mát Chơi: 0 Không: 0 Chơi: 2 Không: 1 Chơi: 1 Không: 1 Nhiệt độ Mưa Xây dựng cây quyết định Chương 4: Phân lớp và dự báo Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Nóng Cao Nhẹ Không Nắng Nóng Cao Mạnh Không Âm u Nóng Cao Nhẹ Có Mưa Ấm áp Cao Nhẹ Có Mưa Mát Trung bình Nhẹ Có Mưa Mát Trung bình Mạnh Không Âm u Mát Trung bình Mạnh Có Nắng Ấm áp Cao Nhẹ Không Nắng Mát Trung bình Nhẹ Có Mưa Ấm áp Trung bình Nhẹ Có Nắng Ấm áp Trung bình Mạnh Có Âm u Ấm áp Cao Mạnh Có Âm u Nóng Trung bình Nhẹ Có Mưa Ấm áp Cao Mạnh Không Tập dữ liệu huấn luyện 7. Tính Gain cho từng thuộc tính: Thuộc tính “Gió” Gain(SMưa, Gió) = Entropy(SMưa) – ( 𝟑 𝟓 )Entropy(SNhẹ) – ( 𝟐 𝟓 )Entropy(SMạnh) = 0.971 – ( 𝟑 𝟓 )(0) - ( 𝟐 𝟓 )(0) = 0.971 Quang cảnh Nhẹ Mạnh Chơi: 3 Không: 0 Chơi: 0 Không: 2 Gió Mưa Xây dựng cây quyết định Chương 4: Phân lớp và dự báo 8. Xác định thuộc tính làm nút gốc: Thuộc tính “Gió” có độ lợi thông tin cao nhất trong nhánh Mưa nên được chọn làm nút gốc. Quang cảnh Chơi Nắng Âm u Mưa Độ ẩm Cao Không Chơi T.Bình Nhẹ Có Không Mạnh Gió Luật rút ra từ cây quyết định Chương 4: Phân lớp và dự báo • if (Quang cảnh = Nắng) and (Độ ẩm = cao) then Chơi tennis = Không • if (Quang cảnh = Nắng) and (Độ ẩm = Trung bình) then Chơi tennis= Có • if (Quang cảnh = Âm u) then Chơi tennis = Có • if (Quang cảnh = Mưa) and (Gió = Nhẹ) then Chơi tennis = Có • if (Quang cảnh = Mưa) and (Gió = Mạnh) then Chơi tennis = Không Quang cảnh Chơi Nắng Âm u Mưa Độ ẩm Cao Không Chơi T.Bình Nhẹ Có Không Mạnh Gió Bài tập Chương 4: Phân lớp và dự báo Xây dựng cây quyết định và rút ra các luật từ dữ liệu huấn luyện sau: Tuổi Thu nhập Sinh viên Đánh giá độ tín nhiệm (trong tín dụng mua chịu) Mua máy tính Thanh niên Cao Không Trung bình Không Thanh niên Cao Không Tốt Không Trung niên Cao Không Trung bình Có Già Trung bình Không Trung bình Có Già Thấp Có Trung bình Có Già Thấp Có Tốt Không Trung niên Thấp Có Tốt Có Thanh niên Trung bình Không Trung bình Không Thanh niên Thấp Có Trung bình Có Già Trung bình Có Trung bình Có Thanh niên Trung bình Có Tốt Có Trung niên Trung bình Không Tốt Có Trung niên Cao Có Trung bình Có Già Trung bình không Tốt Không Thuật toán ILA (Inductive Learning Algorithm) Chương 4: Phân lớp và dự báo - Bước 1: Chia bảng có chứa m mẫu thành n bảng con. Một bảng ứng với một giá trị có thể có của thuộc tính lớp. (Từ bước 2 đến bước 8 sẽ đuợc lặp lại cho mỗi bảng) - Bước 2: Khởi tạo số lượng thuộc tính kết hợp j với j = 1. - Bước 3: Với mỗi bảng con đang xét, phân chia các thuộc tính của nó thành một danh sách các thuộc tính kết hợp, mỗi thành phần của danh sách có j thuộc tính phân biệt. - Bước 4: Với mỗi kết hợp các thuộc tính trong danh sách trên, đếm số lần xuất hiện các giá trị cho các thuộc tính trong kết hợp đó ở các dòng chưa bị khóa của bảng đang xét nhưng nó không được xuất hiện cùng giá trị ở những bảng con khác. Chọn ra một kết hợp trong danh sách sao cho nó có giá trị tương ứng xuất hiện nhiều nhất và được gọi là Max_combination. Thuật toán phân lớp sinh luật trực tiếp Thuật toán ILA (Inductive Learning Algorithm) Chương 4: Phân lớp và dự báo - Bước 5: If max_combination = 0 thì j = j + 1 quay lại bước 3. - Bước 6: Khóa các dòng ở bảng con đang xét mà tại đó nó có giá trị bằng với giá trị tạo ra max_combination. - Bước 7: Thêm vào R luật mới với giả thiết là max_combination các thuộc tính và giá trị tương ứng phân biệt và kết nối các bộ này bằng AND, kết luận của luật là giá trị của thuộc tính quyết định tương ứng với bảng con này. - Bước 8: Nếu tất cả các dòng đều khóa + Nếu còn bảng con thì qua bảng con tiếp theo và quay lại bước 2. + Ngược lại chấm dứt thuật toán + Ngược lại (nghĩa là vẫn còn dòng chưa khóa trong bảng con đang xét) thì quay lại bước 4. Thuật toán ILA (Inductive Learning Algorithm) Chương 4: Phân lớp và dự báo Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Mưa Ấm áp Cao Nhẹ Có Mưa Mát Trung bình Nhẹ Có Nắng Mát Trung bình Nhẹ Có Mưa Ấm áp Trung bình Nhẹ Có Nắng Ấm áp Trung bình Mạnh Có Âm u Ấm áp Cao Mạnh Có Âm u Nóng Trung bình Nhẹ Có Âm u Nóng Cao Nhẹ Có Âm u Mát Trung bình Mạnh Có Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Nóng Cao Nhẹ Không Nắng Nóng Cao Mạnh Không Mưa Mát Trung bình Mạnh Không Nắng Ấm áp Cao Nhẹ Không Mưa Ấm áp Cao Mạnh Không Số lượng thuộc tính kết hợp j = 1 Thuật toán ILA (Inductive Learning Algorithm) Chương 4: Phân lớp và dự báo Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Mưa Ấm áp Cao Nhẹ Có Mưa Mát Trung bình Nhẹ Có Mưa Ấm áp Trung bình Nhẹ Có Nắng Ấm áp Trung bình Mạnh Có Nắng Mát Trung bình Nhẹ Có Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Nóng Cao Nhẹ Không Nắng Nóng Cao Mạnh Không Mưa Mát Trung bình Mạnh Không Nắng Ấm áp Cao Nhẹ Không Mưa Ấm áp Cao Mạnh Không IF Quang cảnh=“Âm u” then Chơi Tennis=“Có” Số lượng thuộc tính kết hợp j = 2 Thuật toán ILA (Inductive Learning Algorithm) Chương 4: Phân lớp và dự báo Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Nóng Cao Nhẹ Không Nắng Nóng Cao Mạnh Không Mưa Mát Trung bình Mạnh Không Nắng Ấm áp Cao Nhẹ Không Mưa Ấm áp Cao Mạnh Không IF Quang cảnh=“Âm u” then Chơi Tennis=“Có” IF Quang cảnh=“Mưa” and Gió=“Nhẹ” then Chơi Tennis=“Có” IF Quang cảnh=“Nắng” and Độ ẩm=“Trung bình” then Chơi Tennis=“Có” Số lượng thuộc tính kết hợp j = 3  Không còn bảng con Thuật toán ILA (Inductive Learning Algorithm) Chương 4: Phân lớp và dự báo Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Mưa Ấm áp Cao Nhẹ Có Mưa Mát Trung bình Nhẹ Có Nắng Mát Trung bình Nhẹ Có Mưa Ấm áp Trung bình Nhẹ Có Nắng Ấm áp Trung bình Mạnh Có Âm u Ấm áp Cao Mạnh Có Âm u Nóng Trung bình Nhẹ Có Âm u Nóng Cao Nhẹ Có Âm u Mát Trung bình Mạnh Có Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Nóng Cao Nhẹ Không Nắng Nóng Cao Mạnh Không Mưa Mát Trung bình Mạnh Không Nắng Ấm áp Cao Nhẹ Không Mưa Ấm áp Cao Mạnh Không Số lượng thuộc tính kết hợp j = 1  max_combin ation =0 Thuật toán ILA (Inductive Learning Algorithm) Chương 4: Phân lớp và dự báo Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Mưa Ấm áp Cao Nhẹ Có Mưa Mát Trung bình Nhẹ Có Nắng Mát Trung bình Nhẹ Có Mưa Ấm áp Trung bình Nhẹ Có Nắng Ấm áp Trung bình Mạnh Có Âm u Ấm áp Cao Mạnh Có Âm u Nóng Trung bình Nhẹ Có Âm u Nóng Cao Nhẹ Có Âm u Mát Trung bình Mạnh Có Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Nóng Cao Nhẹ Không Nắng Nóng Cao Mạnh Không Mưa Mát Trung bình Mạnh Không Nắng Ấm áp Cao Nhẹ Không Mưa Ấm áp Cao Mạnh Không Số lượng thuộc tính kết hợp j = 2 Thuật toán ILA (Inductive Learning Algorithm) Chương 4: Phân lớp và dự báo Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Mưa Ấm áp Cao Nhẹ Có Mưa Mát Trung bình Nhẹ Có Nắng Mát Trung bình Nhẹ Có Mưa Ấm áp Trung bình Nhẹ Có Nắng Ấm áp Trung bình Mạnh Có Âm u Ấm áp Cao Mạnh Có Âm u Nóng Trung bình Nhẹ Có Âm u Nóng Cao Nhẹ Có Âm u Mát Trung bình Mạnh Có IF Quang cảnh=“Âm u” then Chơi Tennis=“Có” IF Quang cảnh=“Mưa” and Gió=“Nhẹ” then Chơi Tennis=“Có” IF Quang cảnh=“Nắng” and Độ ẩm=“Trung bình” then Chơi Tennis=“Có” IF Quang cảnh=“Nắng” and Độ ẩm=“Cao” then Chơi Tennis=“Không” IF Quang cảnh=“Mưa” and Gió=“Mạnh” then Chơi Tennis=“Không” Số lượng thuộc tính kết hợp j = 3  Không còn bảng Phương pháp Naϊve Bayes Chương 4: Phân lớp và dự báo Phân lớp theo mô hình xác suất - Dự đoán xác suất là thành viên của một lớp - Nền tảng: Dựa trên Định lý Bayes: * Cho X, Y là các biến bất kỳ (rời rạc, số,...). * Dự đoán Y từ X. * Định lý Bayes: P(y|x) = 𝑷 𝒙 𝒚 ∗𝑷(𝒚) 𝑷(𝒙) Cụ thể hơn: P(Y=yi|X=xj) = 𝑷 𝑿=𝒙𝒋 𝒀=𝒚𝒊 ∗𝑷(𝒀=𝒚𝒊) 𝑷(𝑿=𝒙𝒋)  (∀𝒊, 𝒋)P(Y=yi|X=xj) = 𝑷 𝑿=𝒙𝒋 𝒀=𝒚𝒊 ∗𝑷(𝒀=𝒚𝒊) 𝑷 𝑿=𝒙𝒋 𝒀=𝒚𝒌 ∗𝑷(𝒀=𝒚𝒌)𝒌 Phương pháp Naϊve Bayes Chương 4: Phân lớp và dự báo Giả sử: - D: Tập huấn luyện gồm các mẫu biểu diễn dạng X= - Ci,D: Tập các mẫu của D thuộc lớp Ci với: i={1,2,...,m} - Các thuộc tính x1,x2,... độc lập điều kiện đôi một với nhau khi cho lớp C P(x1,x2,...,xn|C)=P(x1|C)*P(x2|C)*...*P(xn|C) - Định lý Bayes: P(Ci|X) = 𝑷 𝑿 𝑪𝒊 ∗𝑷(𝑪𝒊) 𝑷(𝑿)  Ý tưởng: Cần xác định xác suất P(Ci|X) lớn nhất hay: Luật phân lớp cho Xnew = {x1,x2,...,xn} là: argmax P(Ci) 𝑷(𝒙𝒌|𝑪𝒊) 𝒏 𝒌=𝟏 Ck Phương pháp Naϊve Bayes Chương 4: Phân lớp và dự báo Thuật toán: Bước 1: Huấn luyện Naive Bayes trên tập dữ liệu huấn luyện: Tính lượng giá P(Ci) Tính lượng giá P(Xk|Ci) Bước 2: Xnew được gán vào lớp cho giá trị công thức lớn nhất: argmax P(Ci) 𝑷(𝒙𝒌|𝑪𝒊) 𝒏 𝒌=𝟏 Ck Phương pháp Naϊve Bayes Chương 4: Phân lớp và dự báo Ví dụ: Cho Xnew = <Quang cảnh=“Nắng”, Nhiệt độ=“Mát”, Độ ẩm=“Cao”, Gió=“Mạnh”  Cần tự động nhận biết lớp của đối tượng này? Bước 1: a. Ước lượng P(Ci) với C1=“Chơi” và C2=“Không” b. Ước lượng P(xk|Ci) a. P(C1)=9/14=0.643 và P(C2)=5/14=0.357 b. Với thuộc tính Quang cảnh, có các giá trị: Nắng, Mưa, Âm u • P(“Nắng”|”Chơi”)=2/9 P(“Nắng”|”Không”)=3/5 • P(“Mưa”|”Chơi”)=3/9 P(“Mưa”|”Không”)=2/5 • P(“Âm u”|”Chơi”)=4/9 P(“Âm u”|”Không”)=0/5 Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Mưa Ấm áp Cao Nhẹ Có Mưa Mát Trung bình Nhẹ Có Nắng Mát Trung bình Nhẹ Có Mưa Ấm áp Trung bình Nhẹ Có Nắng Ấm áp Trung bình Mạnh Có Âm u Ấm áp Cao Mạnh Có Âm u Nóng Trung bình Nhẹ Có Âm u Nóng Cao Nhẹ Có Âm u Mát Trung bình Mạnh Có Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Nóng Cao Nhẹ Không Nắng Nóng Cao Mạnh Không Mưa Mát Trung bình Mạnh Không Nắng Ấm áp Cao Nhẹ Không Mưa Ấm áp Cao Mạnh Không Phương pháp Naϊve Bayes Chương 4: Phân lớp và dự báo * Với thuộc tính Nhiệt độ, có các giá trị: Nóng, Mát, Ấm áp • P(“Nóng”|”Chơi”)=2/9 P(“Nóng”|”Không”)=2/5 • P(“Mát”|”Chơi”)=3/9 P(“Mát”|”Không”)=1/5 • P(“Ấm áp”|”Chơi”)=4/9 P(“Ấm áp”|”Không”)=2/5 * Với thuộc tính Độ ẩm, có các giá trị: Cao, T.Bình • P(“Cao”|”Chơi”)=3/9 P(“Cao”|”Không”)=4/5 • P(“T.Bình”|”Chơi”)=6/9 P(“T.Bình”|”Không”)=1/5 Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Mưa Ấm áp Cao Nhẹ Có Mưa Mát Trung bình Nhẹ Có Nắng Mát Trung bình Nhẹ Có Mưa Ấm áp Trung bình Nhẹ Có Nắng Ấm áp Trung bình Mạnh Có Âm u Ấm áp Cao Mạnh Có Âm u Nóng Trung bình Nhẹ Có Âm u Nóng Cao Nhẹ Có Âm u Mát Trung bình Mạnh Có Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Nóng Cao Nhẹ Không Nắng Nóng Cao Mạnh Không Mưa Mát Trung bình Mạnh Không Nắng Ấm áp Cao Nhẹ Không Mưa Ấm áp Cao Mạnh Không Phương pháp Naϊve Bayes Chương 4: Phân lớp và dự báo * Với thuộc tính Gió, có các giá trị: Nhẹ,Mạnh • P(“Nhẹ”|”Chơi”)=6/9 P(“Nhẹ”|”Không”)=1/5 • P(“Mạnh”|”Chơi”)=3/9 P(“Mạnh”|”Không”)=3/5 Bước 2: Phân lớp: Xnew = <Quang cảnh=“Nắng”, Nhiệt độ=“Mát”, Độ ẩm=“Cao”, Gió=“Mạnh” P(C1)*P(X,C1) = P(C1)*P(“Nắng”|”Chơi”)*P(“Mát”|”Chơi”)* P(“Cao”|”Chơi”)*P(“Mạnh”|”Chơi”) =(9/14)*(2/9)*(3/9)*(3/9)*(3/9)=0.005 P(C2)*P(X,C2) = P(C2)*P(“Nắng”|”Không”)*P(“Mát”|”Không”)* P(“Cao”|”Không”)*P(“Mạnh”|”Không”) =(5/14)*(3/5)*(1/5)*(4/5)*(3/5)=0.021 Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Mưa Ấm áp Cao Nhẹ Có Mưa Mát Trung bình Nhẹ Có Nắng Mát Trung bình Nhẹ Có Mưa Ấm áp Trung bình Nhẹ Có Nắng Ấm áp Trung bình Mạnh Có Âm u Ấm áp Cao Mạnh Có Âm u Nóng Trung bình Nhẹ Có Âm u Nóng Cao Nhẹ Có Âm u Mát Trung bình Mạnh Có Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Nóng Cao Nhẹ Không Nắng Nóng Cao Mạnh Không Mưa Mát Trung bình Mạnh Không Nắng Ấm áp Cao Nhẹ Không Mưa Ấm áp Cao Mạnh Không Xnew thuộc lớp C2 (“Không”) Đánh giá mô hình Chương 4: Phân lớp và dự báo Phương pháp Holdout Phân chia ngẫu nhiên tập dữ liệu thành 2 tập độc lập: - Tập huấn luyện: 2/3 - Tập thử nghiệm: 1/3 Phương pháp Cross-Validation Phân chia tập dữ liệu thành k tập con có cùng kích thước: - Tại mỗi vòng lặp: * Sử dụng một tập con làm tập thử nghiệm * k-1 tập còn lại làm tập huấn luyện - Giá trị của k thường là 10