Bài giảng Khai phá dữ liệu - Chương 4: Phân lớp và dự báo

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. Chương 4: Phân lớp và dự báo Thuật toán ILA (Inductive Learning Algorithm) 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ó Số lượng Âm u Nóng Cao Nhẹ Có thuộc tính Âm u Mát Trung bình Mạnh Có kết hợp j = 1 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 Chương 4: Phân lớp và dự báo Thuật toán ILA (Inductive Learning Algorithm) IF Quang cảnh=“Âm u” then Chơi Tennis=“Có” 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ó Số lượng Nắng Mát Trung bình Nhẹ Có thuộc tính kết hợp j = 2 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 Chương 4: Phân lớp và dự báo Thuật toán ILA (Inductive Learning Algorithm) 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 Quang cảnh Nhiệt độ Độ ẩm Gió Chơi thuộc tính Nắng Nóng Cao Nhẹ Không kết hợp j = 3 Nắng Nóng Cao Mạnh Không Mưa Mát Trung bình Mạnh Không  Không Nắng Ấm áp Cao Nhẹ Không còn bảng con Mưa Ấm áp Cao Mạnh Không Chương 4: Phân lớp và dự báo Thuật toán ILA (Inductive Learning Algorithm) 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 Quang cảnh Nhiệt độ Độ ẩm Gió Chơi thuộc tính Mưa Ấm áp Cao Nhẹ Có Mưa Mát Trung bình Nhẹ Có kết hợp j = 1 Nắng Mát Trung bình Nhẹ Có  Mưa Ấm áp Trung bình Nhẹ Có max_combin Nắng Ấm áp Trung bình Mạnh Có ation =0 Â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ó Chương 4: Phân lớp và dự báo Thuật toán ILA (Inductive Learning Algorithm) 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 Quang cảnh Nhiệt độ Độ ẩm Gió Chơi thuộc tính Mưa Ấm áp Cao Nhẹ Có Mưa Mát Trung bình Nhẹ Có kết hợp j = 2 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ó Chương 4: Phân lớp và dự báo Thuật toán ILA (Inductive Learning Algorithm) 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” Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Số lượng Mưa Ấm áp Cao Nhẹ Có thuộc tính Mưa Mát Trung bình Nhẹ Có kết hợp j = 3 Nắng Mát Trung bình Nhẹ Có Mưa Ấm áp Trung bình Nhẹ Có  Không Nắng Ấm áp Trung bình Mạnh Có còn bảng Â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ó Chương 4: Phân lớp và dự báo Phương pháp Naϊve Bayes 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) = 풌 푷 푿=풙풋 풀=풚풌 ∗푷(풀=풚풌) Chương 4: Phân lớp và dự báo Phương pháp Naϊve Bayes 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(C |X) = 풊 풊 i 푷(푿)  Ý tưởng: Cần xác định xác suất P(Ci|X) lớn nhất new hay: Luật phân lớp cho X = {x1,x2,...,xn} là: 풏 argmax P(Ci) 풌=ퟏ 푷(풙풌|푪풊) Ck Chương 4: Phân lớp và dự báo Phương pháp Naϊve Bayes 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 Chương 4: Phân lớp và dự báo Phương pháp Naϊve Bayes Quang Nhiệt độ Độ ẩm Gió Chơi cảnh Ví dụ: Cho Xnew = <Quang cảnh=“Nắng”, Nhiệt Nắng Nóng Cao Nhẹ Không độ=“Mát”, Độ ẩm=“Cao”, Gió=“Mạnh” Nắng Nóng Cao Mạnh Không Mưa Mát Trung bình Mạnh Không  Cần tự động nhận biết lớp của đối tượng này? Nắng Ấm áp Cao Nhẹ Không Mưa Ấm áp Cao Mạnh Không Bước 1: a. Ước lượng P(C ) với C =“Chơi” và Quang i 1 Nhiệt độ Độ ẩm Gió Chơi cảnh C2=“Không” Mưa Ấm áp Cao Nhẹ Có b. Ước lượng P(xk|Ci) 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ó a. P(C1)=9/14=0.643 và P(C2)=5/14=0.357 Nắng Ấm áp Trung bình Mạnh Có b. Với thuộc tính Quang cảnh, có các giá trị: Âm u Ấm áp Cao Mạnh Có Nắng, Mưa, Âm u Âm u Nóng Trung bình Nhẹ Có Âm u Nóng Cao Nhẹ Có • P(“Nắng”|”Chơi”)=2/9 Âm u Mát Trung bình Mạnh Có 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 Chương 4: Phân lớp và dự báo Phương pháp Naϊve Bayes Quang Nhiệt độ Độ ẩm Gió Chơi cảnh * Với thuộc tính Nhiệt độ, có các giá trị: Nóng, Nắng Nóng Cao Nhẹ Không Mát, Ấm áp Nắng Nóng Cao Mạnh Không Mưa Mát Trung bình Mạnh Không • P(“Nóng”|”Chơi”)=2/9 Nắng Ấm áp Cao Nhẹ Không P(“Nóng”|”Không”)=2/5 Mưa Ấm áp Cao Mạnh Không • P(“Mát”|”Chơi”)=3/9 Quang Nhiệt độ Độ ẩm Gió Chơi P(“Mát”|”Không”)=1/5 cảnh • P(“Ấm áp”|”Chơi”)=4/9 Mưa Ấm áp Cao Nhẹ Có Mưa Mát Trung bình Nhẹ Có P(“Ấm áp”|”Không”)=2/5 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ó * Với thuộc tính Độ ẩm, có các giá trị: Cao, T.Bình Âm u Ấm áp Cao Mạnh Có • P(“Cao”|”Chơi”)=3/9 Âm u Nóng Trung bình Nhẹ Có Âm u Nóng Cao Nhẹ Có P(“Cao”|”Không”)=4/5 Âm u Mát Trung bình Mạnh Có • P(“T.Bình”|”Chơi”)=6/9 P(“T.Bình”|”Không”)=1/5 Chương 4: Phân lớp và dự báo Phương pháp Naϊve Bayes Quang Nhiệt độ Độ ẩm Gió Chơi cảnh * Với thuộc tính Gió, có các giá trị: Nhẹ,Mạnh Nắng Nóng Cao Nhẹ Không • P(“Nhẹ”|”Chơi”)=6/9 Nắng Nóng Cao Mạnh Không Mưa Mát Trung bình Mạnh Không P(“Nhẹ”|”Không”)=1/5 Nắng Ấm áp Cao Nhẹ Không • P(“Mạnh”|”Chơi”)=3/9 Mưa Ấm áp Cao Mạnh Không P(“Mạnh”|”Không”)=3/5 Quang Nhiệt độ Độ ẩm Gió Chơi cảnh Bước 2: Phân lớp: Mưa Ấm áp Cao Nhẹ Có Xnew = <Quang cảnh=“Nắng”, Nhiệt độ=“Mát”, Độ Mưa Mát Trung bình Nhẹ Có Nắng Mát Trung bình Nhẹ Có ẩm=“Cao”, Gió=“Mạnh” Mưa Ấm áp Trung bình Nhẹ Có Nắng Ấm áp Trung bình Mạnh Có P(C1)*P(X,C1) = Âm u Ấm áp Cao Mạnh Có Âm u Nóng Trung bình Nhẹ Có P(C1)*P(“Nắng”|”Chơi”)*P(“Mát”|”Chơi”)* Âm u Nóng Cao Nhẹ Có P(“Cao”|”Chơi”)*P(“Mạnh”|”Chơi”) Âm u Mát Trung bình Mạnh Có =(9/14)*(2/9)*(3/9)*(3/9)*(3/9)=0.005 new X thuộc lớp C2 (“Không”) 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 Chương 4: Phân lớp và dự báo Đánh giá mô hình 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