Chương 4: Phân lớp và dự báo
Tổng quan
• 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
Chương 4: Phân lớp và dự báo
Phân lớp là gì?
• 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
Chương 4: Phân lớp và dự báo
Ứng dụng phân lớp
• Tín dụng
• Tiếp thị
• Chẩn đoán y khoa
• Phân tích hiệu quả điều trị
•
....
Chương 4: Phân lớp và dự báo
Dự đoán là gì?
- Xây dựng một mô hình - Sử dụng mô hình để dự đoán cho những giá trị
• Tương tự với phân lớp: 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
Chương 4: Phân lớp và dự báo
Quy trình phân lớp
- Mô tả các lớp xác định trước - Tìm luật phân lớp
• Bước 1: Xây dựng mô hình • 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
Chương 4: Phân lớp và dự báo
Các kỹ thuật phân lớp
• 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ô • ......
Chương 4: Phân lớp và dự báo
Phân lớp dựa trên cây quyết định
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) - y: là biến phụ thuộc cần phân loại Trong đó: - 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
Chương 4: Phân lớp và dự báo
Các kiểu cây quyết định
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
Cây hồi quy (Regression tree): 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).
Chương 4: Phân lớp và dự báo
Ví dụ cây quyết định
Tập dữ liệu huấn luyện
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
Không
Nhẹ
Nắng
Nóng
Cao
Không
Mạnh
Â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
Mạnh
Cao
Có
Âm u
Nóng
Trung bình Nhẹ
Có
Mưa
Ấm áp
Cao
Mạnh
Không
Chương 4: Phân lớp và dự báo
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
Ví dụ: - Thuộc tính mô tả (Quang cảnh, Gió,..)
- Thuộc tính phân loại (Chơi Tennis?)
- Có khả năng phân loại đúng đắn các ví dụ trong
- Phân loại đúng cho cả các ví dụ chưa gặp trong
Đầ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ó. Đầu ra: Cây quyết định tập dữ liệu rèn luyện tương lai.
Chương 4: Phân lớp và dự báo
Giải thuật quy nạp cây ID3
tính P;
nhánh V
- 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 - Gọi Induce_tree(phân_vùngV, tập_thuộc_tính), gắn kết quả vào End For
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 End If End Function
Chương 4: Phân lớp và dự báo
Thuộc tính dùng để phân loại tốt nhất?
Độ đ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
Chương 4: Phân lớp và dự báo
Thuộc tính dùng để phân loại tốt nhất?
Entropy(S) = -pYlog2pY – pNlog2pN
Entropy(S) =
Độ đ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 đó:
Tổng quát cho tập S có nhiều hơn n thuộc tính phân loại
(n>2):
Chương 4: Phân lớp và dự báo
Thuộc tính dùng để phân loại tốt nhất?
Độ đ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.
- SV là tập con của S chứa các ví dụ có thuộc tính A mang giá
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
trị v.
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
1. Độ hỗn loạn của tập dữ liệu:
Entropy(S) = - (
) - (
) = 0.940
) log2 (
) log2(
𝟗
𝟏𝟒
𝟗
𝟏𝟒
𝟓
𝟏𝟒
𝟓
𝟏𝟒
Tập dữ liệu huấn luyện
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng Nắng Cao Mạnh Không Nóng Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát Âm u Trung bình Mạnh Có Mát Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
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) – (
𝟒
𝟏𝟒
= 0.940 – (
)(- (
) – (
)(0) - (
)(- (
) – (
))
)) - (
)log2(
)log2(
)log2(
)log2(
𝟓
𝟏𝟒
𝟓
𝟏𝟒
𝟐
𝟓
)Entropy(SNắng) – (
𝟑
𝟓
𝟐
𝟓
𝟑
𝟓
)Entropy(SÂm u) – (
𝟓
𝟒
𝟏𝟒
𝟏𝟒
𝟑
𝟓
𝟓
) Entropy(SMưa)
𝟏𝟒
𝟑
𝟓
𝟐
𝟓
𝟐
𝟓
Quang cảnh
= 0.246
Tập dữ liệu huấn luyện
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng Nắng Cao Mạnh Không Nóng
Âm u
Nắng
Mưa
Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát Âm u Trung bình Mạnh Có Mát Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát
Chơi: 4
Không: 0
Chơi: 2
Không: 3
Chơi: 3
Không: 2
Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
2. Tính Gain cho từng thuộc tính:
Thuộc tính “Nhiệt độ”
Gain(S, Nhiệt độ)
= Entropy(S) – (
𝟒
𝟏𝟒
𝟔
𝟏𝟒
= 0.940 – (
)(1) - (
) – (
)(- (
)) - (
)(- (
) – (
))
)log2(
)log2(
)log2(
)log2(
𝟒
𝟏𝟒
)Entropy(SNóng) – (
𝟐
𝟔
𝟔
𝟏𝟒
𝟒
𝟔
𝟒
𝟔
)Entropy(SẤm áp) – (
𝟒
𝟏𝟒
𝟐
𝟔
𝟑
𝟒
𝟒
) Entropy(SMát)
𝟏𝟒
𝟑
𝟒
𝟏
𝟒
𝟏
𝟒
Nhiệt độ
= 0.029
Tập dữ liệu huấn luyện
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng Nắng Cao Mạnh Không Nóng
Ấm áp
Nóng
Mát
Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát Âm u Trung bình Mạnh Có Mát Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát
Chơi: 4
Không: 2
Chơi: 2
Không: 2
Chơi: 3
Không: 1
Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
2. Tính Gain cho từng thuộc tính:
Thuộc tính “Gió”
Gain(S, Gió)
= Entropy(S) – (
)Entropy(SNhẹ)
𝟔
𝟏𝟒
𝟖
𝟏𝟒
= 0.940 – (
)(1) - (
) – (
)(- (
))
)log2(
)log2(
𝟔
𝟏𝟒
)Entropy(SMạnh) – (
𝟐
𝟖
𝟖
𝟏𝟒
𝟔
𝟖
𝟔
𝟖
𝟐
𝟖
Gió
= 0.048
Tập dữ liệu huấn luyện
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng Nắng Cao Mạnh Không Nóng
Mạnh
Nhẹ
Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát Âm u Trung bình Mạnh Có Mát Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát
Chơi: 3
Không: 3
Chơi: 6
Không: 2
Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
= Entropy(S) – (
𝟕
𝟏𝟒
= 0.940 – (
) – (
)(- (
)) - (
)(- (
) – (
))
)log2(
)log2(
)log2(
)log2(
2. Tính Gain cho từng thuộc tính:
Thuộc tính “Độ ẩm”
Gain(S, Độ ẩm)
𝟕
𝟏𝟒
𝟑
𝟕
)Entropy(SCao) – (
𝟒
𝟒
𝟕
𝟕
𝟕
𝟏𝟒
𝟑
𝟕
)Entropy(ST.Bình)
𝟔
𝟕
𝟕
𝟏𝟒
𝟔
𝟕
𝟏
𝟕
𝟏
𝟕
Độ ẩm
= 0.151
Tập dữ liệu huấn luyện
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng Nắng Cao Mạnh Không Nóng
Cao
T.bình
Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát Âm u Trung bình Mạnh Có Mát Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát
Chơi: 3
Không: 4
Chơi: 6
Không: 1
Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
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
Mưa
Âm u
Nắng
Tập dữ liệu huấn luyện
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng
Chơi
Nắng Cao Mạnh Không Nóng
Chơi -
Không chơi
Chơi -
Không chơi
Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát Âm u Trung bình Mạnh Có Mát Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
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:
) - (
) = 0.971
) log2 (
) log2(
𝟑
𝟓
𝟑
𝟓
𝟐
𝟓
𝟐
𝟓
Entropy(SNắng) = - (
Tập dữ liệu huấn luyện
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng Nắng Cao Mạnh Không Nóng Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát Âm u Trung bình Mạnh Có Mát Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
) Entropy(SMát)
𝟐
)Entropy(SNóng) – (
𝟓
𝟐
𝟓
𝟏
)Entropy(SẤm áp) – (
𝟓
)(0) = 0.571
= 0.971 – (
)(1) - (
)(0) - (
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) – (
𝟐
𝟐
𝟓
𝟓
𝟏
𝟓
Quang cảnh
Nắng
Tập dữ liệu huấn luyện
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng
Nhiệt độ
Nắng Cao Mạnh Không Nóng Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát Âm u Trung bình Mạnh Có Mát
Ấm áp
Nóng
Mát
Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chơi: 1
Không: 1
Chơi: 0
Không: 2
Chơi: 1
Không: 0
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
𝟐
𝟓
= 0.971 – (
)(1) - (
)(-(
)) = 0.020
)-(
)log2(
)log2((
4. Tính Gain cho từng thuộc tính:
Thuộc tính “Gió”
Gain(SNắng, Gió)
= Entropy(SNắng) – (
𝟑
𝟐
𝟓
𝟓
𝟑
)Entropy(SMạnh)
)Entropy(SNhẹ) – (
𝟓
𝟐
𝟏
𝟏
𝟑
𝟑
𝟑
𝟐
𝟑
Quang cảnh
Nắng
Tập dữ liệu huấn luyện
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng
Gió
Nắng Cao Mạnh Không Nóng Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát Âm u Trung bình Mạnh Có Mát
Nhẹ
Mạnh
Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chơi: 1
Không: 1
Chơi: 1
Không: 2
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
)Entropy(ST.Bình)
𝟐
)Entropy(SCao) – (
𝟓
𝟑
𝟓
)(0) = 0.971
= 0.971 – (
)(0) - (
4. Tính Gain cho từng thuộc tính:
Thuộc tính “Độ ẩm”
Gain(SNắng, Độ ẩm)
= Entropy(SNắng) – (
𝟐
𝟑
𝟓
𝟓
Quang cảnh
Nắng
Tập dữ liệu huấn luyện
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng
Độ ẩm
Nắng Cao Mạnh Không Nóng Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát Âm u Trung bình Mạnh Có Mát
Cao
T.Bình
Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chơi: 0
Không: 3
Chơi: 2
Không: 0
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
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
Mưa
Âm u
Nắng
Chơi
Tập dữ liệu huấn luyện
Độ ẩm
Chơi -
Không chơi
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng Nắng Cao Mạnh Không Nóng
T.Bình
Cao
Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát
Không
Chơi
Âm u Trung bình Mạnh Có Mát Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
6. Xét nhánh Mưa:
Độ hỗn loạn của tập SMưa:
) - (
) = 0.971
) log2 (
) log2(
𝟑
𝟓
𝟑
𝟓
𝟐
𝟓
𝟐
𝟓
Entropy(SMưa) = - (
Tập dữ liệu huấn luyện
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng Nắng Cao Mạnh Không Nóng Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát Âm u Trung bình Mạnh Có Mát Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
)Entropy(SMát)
𝟑
𝟓
= 0.971 – (
)) - (
)(-(
)-(
)(1) = 0.020
)log2(
)log2(
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) – (
𝟓
𝟏
𝟐
𝟑
𝟑
𝟐
𝟑
𝟐
𝟓
𝟏
𝟑
Quang cảnh
Mưa
Tập dữ liệu huấn luyện
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng
Nhiệt độ
Nắng Cao Mạnh Không Nóng Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát Âm u Trung bình Mạnh Có Mát
Ấm áp
Nóng
Mát
Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chơi: 2
Không: 1
Chơi: 0
Không: 0
Chơi: 1
Không: 1
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
)Entropy(SMạnh)
𝟐
)Entropy(SNhẹ) – (
𝟓
𝟑
𝟓
)(0) = 0.971
= 0.971 – (
)(0) - (
7. Tính Gain cho từng thuộc tính:
Thuộc tính “Gió”
Gain(SMưa, Gió)
= Entropy(SMưa) – (
𝟐
𝟑
𝟓
𝟓
Quang cảnh
Mưa
Tập dữ liệu huấn luyện
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng
Gió
Nắng Cao Mạnh Không Nóng Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát Âm u Trung bình Mạnh Có Mát
Nhẹ
Mạnh
Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chơi: 3
Không: 0
Chơi: 0
Không: 2
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
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
Mưa
Âm u
Nắng
Chơi
Gió
Độ ẩm
Mạnh
Nhẹ
T.Bình
Cao
Có
Không
Không
Chơi
Chương 4: Phân lớp và dự báo
Luật rút ra từ cây quyết định
Quang cảnh
Mưa
Âm u
Nắng
Chơi
Gió
Độ ẩm
Mạnh
Nhẹ
T.Bình
Cao
Có
Không
Không
Chơi
• 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
Chương 4: Phân lớp và dự báo
Bài tập
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
Mua máy
tính
Đánh giá độ tín
nhiệm (trong tín
dụng mua chịu)
Cao
Cao
Cao
Không
Không
Không
Trung bình Không
Thấp
Thấp
Thấp
Có
Có
Có
Thanh niên
Thanh niên
Trung niên
Già
Già
Già
Trung niên
Thanh niên Trung bình Không
Thanh niên
Già
Có
Có
Có
Thấp
Trung bình
Thanh niên Trung bình
Trung niên Trung bình Không
Trung niên
Già
Cao
Trung bình
Có
không
Trung bình
Tốt
Trung bình
Trung bình
Trung bình
Tốt
Tốt
Trung bình
Trung bình
Trung bình
Tốt
Tốt
Trung bình
Tốt
Không
Không
Có
Có
Có
Không
Có
Không
Có
Có
Có
Có
Có
Không
Chương 4: Phân lớp và dự báo
Thuật toán ILA (Inductive Learning Algorithm)
Thuật toán phân lớp sinh luật trực tiếp
- 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.
Chương 4: Phân lớp và dự báo
Thuật toán ILA (Inductive Learning Algorithm)
+ 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
- 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
đ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 áp
Cao
Mưa
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ó
Số lượng
thuộc tính
kết hợp j = 1
Âm u
Mát
Có
Trung bình
Mạnh
Quang cảnh
Nhiệt độ
Độ ẩm
Gió
Chơi
Nắng
Nóng
Nhẹ
Không
Cao
Nắng
Nóng
Mạnh
Không
Cao
Mưa
Mát
Trung bình
Mạnh
Không
Nắng
Ấm áp
Nhẹ
Không
Cao
Mưa
Ấm áp
Mạnh
Không
Cao
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 áp
Cao
Nhẹ
Có
Mưa
Trung bình
Nhẹ
Có
Mưa
Mát
Trung bình
Nhẹ
Có
Mưa
Ấm áp
Trung bình
Mạnh
Có
Nắng
Ấm áp
Trung bình
Nhẹ
Có
Nắng
Mát
Số lượng
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ó”
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
Số lượng
thuộc tính
kết hợp j = 3
Không
còn bảng con
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)
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
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ó
Số lượng
thuộc tính
kết hợp j = 1
max_combin
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
Có
Trung bình
Mạnh
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
Quang cảnh
Nhiệt độ
Độ ẩm
Gió
Chơi
Ấm áp
Cao
Mưa
Nhẹ
Có
Số lượng
thuộc tính
kết hợp j = 2
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
Có
Trung bình
Mạnh
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
Ấm áp
Cao
Mưa
Nhẹ
Có
Mưa
Mát
Trung bình
Nhẹ
Có
Nắng
Mát
Trung bình
Nhẹ
Có
Số lượng
thuộc tính
kết hợp j = 3
Không
Mưa
Ấm áp
Trung bình
Nhẹ
Có
còn bảng
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
Có
Trung bình
Mạnh
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(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
Chương 4: Phân lớp và dự báo
Phương pháp Naϊve Bayes
Tính lượng giá P(Ci)
Tính lượng giá P(Xk|Ci)
𝒏
𝒌=𝟏
argmax P(Ci) 𝑷(𝒙𝒌|𝑪𝒊)
Ck
Thuật toán:
Bước 1: Huấn luyện Naive Bayes trên tập dữ liệu huấn luyện:
Bước 2: Xnew được gán vào lớp cho giá trị công thức lớn nhất:
Chương 4: Phân lớp và dự báo
Quang
Phương pháp Naϊve Bayes
Nhiệt độ
Độ ẩm
Gió
Chơi
cảnh
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
Quang
Nhiệt độ
Độ ẩm
Gió
Chơi
cảnh
Mưa
Ấm áp
Cao
Nhẹ
Có
Mưa
Mát
Trung bình Nhẹ
Có
b. Ước lượng P(xk|Ci)
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
Mạnh Có
Cao
Ví dụ: Cho Xnew =
Âm u
Nóng
Trung bình Nhẹ
Có
Nắng, Mưa, Âm u
Âm u
Nóng
Cao
Nhẹ
Có
Âm u
Mát
Trung bình Mạnh Có
•
•
•
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
Chương 4: Phân lớp và dự báo
Quang
Phương pháp Naϊve Bayes
Nhiệt độ
Độ ẩm
Gió
Chơi
cảnh
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
* Với thuộc tính Nhiệt độ, có các giá trị: Nóng,
Mát, Ấm áp
•
Nắng
Ấm áp
Cao
Nhẹ
Không
Mưa
Ấm áp
Cao
Mạnh Không
•
Quang
Nhiệt độ
Độ ẩm
Gió
Chơi
cảnh
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ó
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
Mưa
Ấm áp
Trung bình Nhẹ
Có
Nắng
Ấm áp
Trung bình Mạnh Có
Âm u
Ấm áp
Mạnh Có
Cao
Âm u
Nóng
Trung bình Nhẹ
Có
•
* Với thuộc tính Độ ẩm, có các giá trị: Cao, T.Bình
•
Âm u
Nóng
Cao
Nhẹ
Có
Âm u
Mát
Trung bình Mạnh Có
•
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
Chương 4: Phân lớp và dự báo
Quang
Phương pháp Naϊve Bayes
Nhiệt độ
Độ ẩm
Gió
Chơi
cảnh
Nắng
Nóng
Cao
Nhẹ
Không
Nắng
Nóng
Cao
Mạnh Không
* Với thuộc tính Gió, có các giá trị: Nhẹ,Mạnh
•
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
•
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
Quang
Nhiệt độ
Độ ẩm
Gió
Chơi
cảnh
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ó
Bước 2: Phân lớp:
Xnew =
Mưa
Ấm áp
Trung bình Nhẹ
Có
Nắng
Ấm áp
Trung bình Mạnh Có
Âm u
Ấm áp
Mạnh Có
Cao
Â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ó
Xnew thuộc lớp C2 (“Không”)
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
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:
- Tập thử nghiệm:
2/3
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
Chương 4: Phân lớp và dự báo
Thuộc tính dùng để phân loại tốt nhất?
Entropy(S) = -pYlog2pY – pNlog2pN
Entropy(S) =
Độ đ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 đó: Tổng quát cho tập S có nhiều hơn n thuộc tính phân loại (n>2):
Chương 4: Phân lớp và dự báo
Thuộc tính dùng để phân loại tốt nhất?
Độ đ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.
- SV là tập con của S chứa các ví dụ có thuộc tính A mang giá
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 trị v.
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
1. Độ hỗn loạn của tập dữ liệu:
Entropy(S) = - (
) - (
) = 0.940
) log2 (
) log2(
𝟗 𝟏𝟒
𝟗 𝟏𝟒
𝟓 𝟏𝟒
𝟓 𝟏𝟒
Tập dữ liệu huấn luyện
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng Nắng Cao Mạnh Không Nóng Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát Âm u Trung bình Mạnh Có Mát Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
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) – (
𝟒 𝟏𝟒
= 0.940 – (
)(- (
) – (
)(0) - (
)(- (
) – (
))
)) - (
)log2(
)log2(
)log2(
)log2(
𝟓 𝟏𝟒
𝟓 𝟏𝟒 𝟐 𝟓
)Entropy(SNắng) – ( 𝟑 𝟓
𝟐 𝟓
𝟑 𝟓
)Entropy(SÂm u) – ( 𝟓 𝟒 𝟏𝟒 𝟏𝟒
𝟑 𝟓
𝟓 ) Entropy(SMưa) 𝟏𝟒 𝟑 𝟓
𝟐 𝟓
𝟐 𝟓
Quang cảnh
= 0.246
Tập dữ liệu huấn luyện
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng Nắng Cao Mạnh Không Nóng
Âm u
Nắng
Mưa
Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát Âm u Trung bình Mạnh Có Mát Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát
Chơi: 4 Không: 0
Chơi: 2 Không: 3
Chơi: 3 Không: 2
Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
2. Tính Gain cho từng thuộc tính: Thuộc tính “Nhiệt độ” Gain(S, Nhiệt độ)
= Entropy(S) – (
𝟒 𝟏𝟒
𝟔 𝟏𝟒
= 0.940 – (
)(1) - (
) – (
)(- (
)) - (
)(- (
) – (
))
)log2(
)log2(
)log2(
)log2(
𝟒 𝟏𝟒
)Entropy(SNóng) – ( 𝟐 𝟔 𝟔 𝟏𝟒
𝟒 𝟔
𝟒 𝟔
)Entropy(SẤm áp) – ( 𝟒 𝟏𝟒
𝟐 𝟔
𝟑 𝟒
𝟒 ) Entropy(SMát) 𝟏𝟒 𝟑 𝟒
𝟏 𝟒
𝟏 𝟒
Nhiệt độ
= 0.029
Tập dữ liệu huấn luyện
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng Nắng Cao Mạnh Không Nóng
Ấm áp
Nóng
Mát
Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát Âm u Trung bình Mạnh Có Mát Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát
Chơi: 4 Không: 2
Chơi: 2 Không: 2
Chơi: 3 Không: 1
Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
2. Tính Gain cho từng thuộc tính: Thuộc tính “Gió” Gain(S, Gió)
= Entropy(S) – (
)Entropy(SNhẹ)
𝟔 𝟏𝟒
𝟖 𝟏𝟒
= 0.940 – (
)(1) - (
) – (
)(- (
))
)log2(
)log2(
𝟔 𝟏𝟒
)Entropy(SMạnh) – ( 𝟐 𝟖 𝟖 𝟏𝟒
𝟔 𝟖
𝟔 𝟖
𝟐 𝟖
Gió
= 0.048
Tập dữ liệu huấn luyện
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng Nắng Cao Mạnh Không Nóng
Mạnh
Nhẹ
Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát Âm u Trung bình Mạnh Có Mát Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát
Chơi: 3 Không: 3
Chơi: 6 Không: 2
Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
= Entropy(S) – (
𝟕 𝟏𝟒
= 0.940 – (
) – (
)(- (
)) - (
)(- (
) – (
))
)log2(
)log2(
)log2(
)log2(
2. Tính Gain cho từng thuộc tính: Thuộc tính “Độ ẩm” Gain(S, Độ ẩm) 𝟕 𝟏𝟒 𝟑 𝟕
)Entropy(SCao) – ( 𝟒 𝟒 𝟕 𝟕
𝟕 𝟏𝟒
𝟑 𝟕
)Entropy(ST.Bình) 𝟔 𝟕
𝟕 𝟏𝟒
𝟔 𝟕
𝟏 𝟕
𝟏 𝟕
Độ ẩm
= 0.151
Tập dữ liệu huấn luyện
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng Nắng Cao Mạnh Không Nóng
Cao
T.bình
Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát Âm u Trung bình Mạnh Có Mát Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát
Chơi: 3 Không: 4
Chơi: 6 Không: 1
Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
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
Mưa
Âm u
Nắng
Tập dữ liệu huấn luyện
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng
Chơi
Nắng Cao Mạnh Không Nóng
Chơi - Không chơi
Chơi - Không chơi
Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát Âm u Trung bình Mạnh Có Mát Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
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:
) - (
) = 0.971
) log2 (
) log2(
𝟑 𝟓
𝟑 𝟓
𝟐 𝟓
𝟐 𝟓
Entropy(SNắng) = - (
Tập dữ liệu huấn luyện
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng Nắng Cao Mạnh Không Nóng Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát Âm u Trung bình Mạnh Có Mát Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
) Entropy(SMát)
𝟐 )Entropy(SNóng) – ( 𝟓
𝟐 𝟓
𝟏 )Entropy(SẤm áp) – ( 𝟓
)(0) = 0.571
= 0.971 – (
)(1) - (
)(0) - (
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) – ( 𝟐 𝟐 𝟓 𝟓
𝟏 𝟓
Quang cảnh
Nắng
Tập dữ liệu huấn luyện
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng
Nhiệt độ
Nắng Cao Mạnh Không Nóng Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát Âm u Trung bình Mạnh Có Mát
Ấm áp
Nóng
Mát
Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chơi: 1 Không: 1
Chơi: 0 Không: 2
Chơi: 1 Không: 0
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
𝟐 𝟓
= 0.971 – (
)(1) - (
)(-(
)) = 0.020
)-(
)log2(
)log2((
4. Tính Gain cho từng thuộc tính: Thuộc tính “Gió” Gain(SNắng, Gió) = Entropy(SNắng) – ( 𝟑 𝟐 𝟓 𝟓
𝟑 )Entropy(SMạnh) )Entropy(SNhẹ) – ( 𝟓 𝟐 𝟏 𝟏 𝟑 𝟑 𝟑
𝟐 𝟑
Quang cảnh
Nắng
Tập dữ liệu huấn luyện
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng
Gió
Nắng Cao Mạnh Không Nóng Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát Âm u Trung bình Mạnh Có Mát
Nhẹ
Mạnh
Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chơi: 1 Không: 1
Chơi: 1 Không: 2
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
)Entropy(ST.Bình)
𝟐 )Entropy(SCao) – ( 𝟓
𝟑 𝟓
)(0) = 0.971
= 0.971 – (
)(0) - (
4. Tính Gain cho từng thuộc tính: Thuộc tính “Độ ẩm” Gain(SNắng, Độ ẩm) = Entropy(SNắng) – ( 𝟐 𝟑 𝟓 𝟓
Quang cảnh
Nắng
Tập dữ liệu huấn luyện
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng
Độ ẩm
Nắng Cao Mạnh Không Nóng Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát Âm u Trung bình Mạnh Có Mát
Cao
T.Bình
Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chơi: 0 Không: 3
Chơi: 2 Không: 0
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
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
Mưa
Âm u
Nắng
Chơi
Tập dữ liệu huấn luyện
Độ ẩm
Chơi - Không chơi
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng Nắng Cao Mạnh Không Nóng
T.Bình
Cao
Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát
Không
Chơi
Âm u Trung bình Mạnh Có Mát Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
6. Xét nhánh Mưa: Độ hỗn loạn của tập SMưa:
) - (
) = 0.971
) log2 (
) log2(
𝟑 𝟓
𝟑 𝟓
𝟐 𝟓
𝟐 𝟓
Entropy(SMưa) = - (
Tập dữ liệu huấn luyện
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng Nắng Cao Mạnh Không Nóng Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát Âm u Trung bình Mạnh Có Mát Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
)Entropy(SMát)
𝟑 𝟓
= 0.971 – (
)) - (
)(-(
)-(
)(1) = 0.020
)log2(
)log2(
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) – ( 𝟓 𝟏 𝟐 𝟑 𝟑
𝟐 𝟑
𝟐 𝟓
𝟏 𝟑
Quang cảnh
Mưa
Tập dữ liệu huấn luyện
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng
Nhiệt độ
Nắng Cao Mạnh Không Nóng Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát Âm u Trung bình Mạnh Có Mát
Ấm áp
Nóng
Mát
Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chơi: 2 Không: 1
Chơi: 0 Không: 0
Chơi: 1 Không: 1
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
)Entropy(SMạnh)
𝟐 )Entropy(SNhẹ) – ( 𝟓
𝟑 𝟓
)(0) = 0.971
= 0.971 – (
)(0) - (
7. Tính Gain cho từng thuộc tính: Thuộc tính “Gió” Gain(SMưa, Gió) = Entropy(SMưa) – ( 𝟐 𝟑 𝟓 𝟓
Quang cảnh
Mưa
Tập dữ liệu huấn luyện
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Nắng Cao Nhẹ Không Nóng
Gió
Nắng Cao Mạnh Không Nóng Âm u Cao Nhẹ Có Nóng Mưa Cao Nhẹ Có Ấm áp Mưa Có Trung bình Nhẹ Mát Mưa Trung bình Mạnh Không Mát Âm u Trung bình Mạnh Có Mát
Nhẹ
Mạnh
Nắng Ấm áp Cao Nhẹ Không Nắng Trung bình Nhẹ Có Mát Mưa Trung bình Nhẹ Có Ấm áp Nắng Trung bình Mạnh Có Ấm áp Âm u Cao Mạnh Có Ấm áp Âm u Trung bình Nhẹ Có Nóng Mưa Ấm áp Cao Mạnh Không
Chơi: 3 Không: 0
Chơi: 0 Không: 2
Chương 4: Phân lớp và dự báo
Xây dựng cây quyết định
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
Mưa
Âm u
Nắng
Chơi
Gió
Độ ẩm
Mạnh
Nhẹ
T.Bình
Cao
Có
Không
Không
Chơi
Chương 4: Phân lớp và dự báo
Luật rút ra từ cây quyết định
Quang cảnh
Mưa
Âm u
Nắng
Chơi
Gió
Độ ẩm
Mạnh
Nhẹ
T.Bình
Cao
Có
Không
Không
Chơi
• 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
Chương 4: Phân lớp và dự báo
Bài tập
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
Mua máy tính
Đánh giá độ tín nhiệm (trong tín dụng mua chịu)
Cao Cao Cao
Không Không Không Trung bình Không
Thấp Thấp Thấp
Có Có Có
Thanh niên Thanh niên Trung niên Già Già Già Trung niên Thanh niên Trung bình Không Thanh niên Già
Có Có Có
Thấp Trung bình Thanh niên Trung bình Trung niên Trung bình Không Trung niên Già
Cao Trung bình
Có không
Trung bình Tốt Trung bình Trung bình Trung bình Tốt Tốt Trung bình Trung bình Trung bình Tốt Tốt Trung bình Tốt
Không Không Có Có Có Không Có Không Có Có Có Có Có Không
Chương 4: Phân lớp và dự báo
Thuật toán ILA (Inductive Learning Algorithm) Thuật toán phân lớp sinh luật trực tiếp
- 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.
Chương 4: Phân lớp và dự báo
Thuật toán ILA (Inductive Learning Algorithm)
+ 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
- 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 đ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 áp
Cao
Mưa
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ó
Số lượng thuộc tính kết hợp j = 1
Âm u
Mát
Có
Trung bình
Mạnh
Quang cảnh
Nhiệt độ
Độ ẩm
Gió
Chơi
Nắng
Nóng
Nhẹ
Không
Cao
Nắng
Nóng
Mạnh
Không
Cao
Mưa
Mát
Trung bình
Mạnh
Không
Nắng
Ấm áp
Nhẹ
Không
Cao
Mưa
Ấm áp
Mạnh
Không
Cao
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 áp
Cao
Nhẹ
Có
Mưa
Trung bình
Nhẹ
Có
Mưa
Mát
Trung bình
Nhẹ
Có
Mưa
Ấm áp
Trung bình
Mạnh
Có
Nắng
Ấm áp
Trung bình
Nhẹ
Có
Nắng
Mát
Số lượng 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ó”
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
Số lượng thuộc tính kết hợp j = 3 Không còn bảng con
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)
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
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ó
Số lượng thuộc tính kết hợp j = 1 max_combin 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
Có
Trung bình
Mạnh
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
Quang cảnh
Nhiệt độ
Độ ẩm
Gió
Chơi
Ấm áp
Cao
Mưa
Nhẹ
Có
Số lượng thuộc tính kết hợp j = 2
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
Có
Trung bình
Mạnh
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
Ấm áp
Cao
Mưa
Nhẹ
Có
Mưa
Mát
Trung bình
Nhẹ
Có
Nắng
Mát
Trung bình
Nhẹ
Có
Số lượng thuộc tính kết hợp j = 3 Không
Mưa
Ấm áp
Trung bình
Nhẹ
Có
còn bảng
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
Có
Trung bình
Mạnh
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(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
Chương 4: Phân lớp và dự báo
Phương pháp Naϊve Bayes
Tính lượng giá P(Ci) Tính lượng giá P(Xk|Ci)
𝒏 𝒌=𝟏
argmax P(Ci) 𝑷(𝒙𝒌|𝑪𝒊) Ck
Thuật toán: Bước 1: Huấn luyện Naive Bayes trên tập dữ liệu huấn luyện: Bước 2: Xnew được gán vào lớp cho giá trị công thức lớn nhất:
Chương 4: Phân lớp và dự báo
Quang
Phương pháp Naϊve Bayes
Nhiệt độ
Độ ẩm
Gió
Chơi
cảnh
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
Quang
Nhiệt độ
Độ ẩm
Gió
Chơi
cảnh
Mưa
Ấm áp
Cao
Nhẹ
Có
Mưa
Mát
Trung bình Nhẹ
Có
b. Ước lượng P(xk|Ci)
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
Mạnh Có
Cao
Ví dụ: Cho Xnew =
Âm u
Nóng
Trung bình Nhẹ
Có
Nắng, Mưa, Âm u
Âm u
Nóng
Cao
Nhẹ
Có
Âm u
Mát
Trung bình Mạnh Có
•
•
•
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
Chương 4: Phân lớp và dự báo
Quang
Phương pháp Naϊve Bayes
Nhiệt độ
Độ ẩm
Gió
Chơi
cảnh
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
* Với thuộc tính Nhiệt độ, có các giá trị: Nóng,
Mát, Ấm áp
•
Nắng
Ấm áp
Cao
Nhẹ
Không
Mưa
Ấm áp
Cao
Mạnh Không
•
Quang
Nhiệt độ
Độ ẩm
Gió
Chơi
cảnh
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ó
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
Mưa
Ấm áp
Trung bình Nhẹ
Có
Nắng
Ấm áp
Trung bình Mạnh Có
Âm u
Ấm áp
Mạnh Có
Cao
Âm u
Nóng
Trung bình Nhẹ
Có
•
* Với thuộc tính Độ ẩm, có các giá trị: Cao, T.Bình
•
Âm u
Nóng
Cao
Nhẹ
Có
Âm u
Mát
Trung bình Mạnh Có
•
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
Chương 4: Phân lớp và dự báo
Quang
Phương pháp Naϊve Bayes
Nhiệt độ
Độ ẩm
Gió
Chơi
cảnh
Nắng
Nóng
Cao
Nhẹ
Không
Nắng
Nóng
Cao
Mạnh Không
* Với thuộc tính Gió, có các giá trị: Nhẹ,Mạnh
•
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
•
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
Quang
Nhiệt độ
Độ ẩm
Gió
Chơi
cảnh
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ó
Bước 2: Phân lớp:
Xnew =
Mưa
Ấm áp
Trung bình Nhẹ
Có
Nắng
Ấm áp
Trung bình Mạnh Có
Âm u
Ấm áp
Mạnh Có
Cao
Â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ó
Xnew thuộc lớp C2 (“Không”)
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
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:
- Tập thử nghiệm:
2/3
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
Âm u
Nóng
Trung bình Nhẹ
Có
Nắng, Mưa, Âm u
Âm u
Nóng
Cao
Nhẹ
Có
Âm u
Mát
Trung bình Mạnh Có
•
•
•
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
Chương 4: Phân lớp và dự báo
Quang
Phương pháp Naϊve Bayes
Nhiệt độ
Độ ẩm
Gió
Chơi
cảnh
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
* Với thuộc tính Nhiệt độ, có các giá trị: Nóng, Mát, Ấm áp •
Nắng
Ấm áp
Cao
Nhẹ
Không
Mưa
Ấm áp
Cao
Mạnh Không
•
Quang
Nhiệt độ
Độ ẩm
Gió
Chơi
cảnh
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ó
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
Mưa
Ấm áp
Trung bình Nhẹ
Có
Nắng
Ấm áp
Trung bình Mạnh Có
Âm u
Ấm áp
Mạnh Có
Cao
Âm u
Nóng
Trung bình Nhẹ
Có
• * Với thuộc tính Độ ẩm, có các giá trị: Cao, T.Bình •
Âm u
Nóng
Cao
Nhẹ
Có
Âm u
Mát
Trung bình Mạnh Có
•
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
Chương 4: Phân lớp và dự báo
Quang
Phương pháp Naϊve Bayes
Nhiệt độ
Độ ẩm
Gió
Chơi
cảnh
Nắng
Nóng
Cao
Nhẹ
Không
Nắng
Nóng
Cao
Mạnh Không
* Với thuộc tính Gió, có các giá trị: Nhẹ,Mạnh •
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
•
![SQL: Ngôn Ngữ Truy Vấn Cấu Trúc và DDL, DML, DCL [Hướng Dẫn Chi Tiết]](https://cdn.tailieu.vn/images/document/thumbnail/2025/20250812/kexauxi10/135x160/13401767990844.jpg)
