Bài giảng Các hệ cơ sở tri thức (KBS: Knowledge Based Systems) - Trần Nguyên Hương

Nội dung text: Bài giảng Các hệ cơ sở tri thức (KBS: Knowledge Based Systems) - Trần Nguyên Hương

1. Các hệ cơ sở tri thức KBS: Knowledge Based Systems Trần Nguyên Hương 1
2. Hệ cơ sở tri thức ⚫ Chương 1: Tổng quan về hệ cơ sở tri thức ⚫ Chương 2: Biểu diễn và suy luận tri thức ⚫ Chương 3: Hệ MYCIN ⚫ Chương 4: Hệ học ⚫ Chương 5: Hệ thống mờ cho các biến liên tục ⚫ . 2
3. Tài liệu tham khảo 1. GS.TSKH. Hoàng Kiếm. Giáo trình các hệ cơ sở tri thức. NXB Đại học Quốc gia Thành phố Hồ Chí Minh – 2007 2. Đỗ Trung Tuấn. Hệ Chuyên gia. NXB Giáo dục 1999 3. Robert I Levine. Knowledge Based Systems. Wissenschafs Verlag, 1991. 3
4. Chương 1. Tổng quan về Hệ cơ sở tri thức 1.1. Khái niệm về Hệ cơ sở tri thức (CSTT) ⚫ Hệ CSTT là chương trình máy tính được thiết kế để mô hình hoá khả năng giải quyết vấn đề của chuyên gia con người ⚫ Hệ CSTT là hệ thống dựa trên tri thức, cho phép mô hình hoá các tri thức của chuyên gia, dùng tri thức này để giải quyết vấn đề phức tạp thuộc cùng lĩnh vực. ⚫ Hai yếu tố quan trọng trong Hệ CSTT là: tri thức chuyên gia và lập luận, tương ứng với 2 khối chính là cơ sở tri thức và động cơ suy diễn. 4
5. 1.2. Cấu trúc của Hệ chuyên gia Bộ xử lý ngôn Động cơ suy diễn ngữ tự nhiên Tìm kiếm Điều khiển Giải thích Cơ sở tri thức Vùng nhớ làm việc Sự kiện Luật Tiếp nhận tri thức Người 7 chuyên gia
6. 1.4. Hệ học ⚫ Trong nhiều tình huống, sẽ không có sẵn tri thức như: – Kỹ sư tri thức cần thu nhận tri thức từ chuyên gia lĩnh vực. – Cần biết các luật mô tả lĩnh vực cụ thể – Bài toán không được biểu diễn tường minh theo luật, sự kiện hay quan hệ. ⚫ Có 2 tiếp cận cho hệ thống học – Học từ ký hiệu: Bao gồm việc hình thức hoá, sửa chữa các luật tường minh, sự kiện và các quan hệ. – Học từ dữ liệu số: được áp dụng cho những hệ thống được mô hình dưới dạng số liên quan đến các kỹ thuật nhằm tối ưu các tham số. Học theo dạng số bao gồm: Mạng Noron nhân tạo, thuật giải di truyền, bài toán tối ưu truyền thống. Các kỹ thuật học theo số không tạo ra CSTT tường minh. 11
7. Chương 2. Biểu diễn và suy luận tri thức Trần Nguyên Hương 15
8. Chương 2: Biểu diễn và suy luận tri thức 2.1. Mở đầu ⚫ Tri thức, lĩnh vực và biểu diến tri thức. 2.2. Các loại tri thức: được chia thành 5 loại 1. Tri thức thủ tục: mô tả cách giải quyết một vấn đề. Loại tri thức này đưa ra giải pháp để thực hiện một công việc nào đó. Các dạng tri thức thủ tục tiêu biểu thường là các luật, chiến lược, lịch trình và thủ tục. 2. Tri thức khai báo: cho biết một vấn đề được thấy như thế nào. Loại tri thức này bao gồm các phát biểu đơn giản, dưới dạng các khẳng định logic đúng hoặc sai. Tri thứ khai báo cũng có thể là một danh sách các khẳng định nhằm mô tả đầy đủ hơn về đối tượng hay một khái niệm nào đó. 16
9. 2.2.Các loại tri thức (tiếp) 3. Siêu tri thức: mô tả tri thức về tri thức. Loại tri thức này giúp lựa chọn tri thức thích hợp nhất trong số các tri thức khi giải quyết một vấn đề. Các chuyên gia sử dụng tri thức này để điều chỉnh hiệu quả giải quyết vấn đề bằng cách hướng các lập luận về miền tri thức có khả năng hơn cả. 4. Tri thức heuristic: Mô tả các “mẹo” để dẫn dắt tiến trình lập luận. Tri thức heuristic là tri thức không bảo đảm hoàm toán 100% chính xác về kết quả giải quyết vấn đề. Các chuyên gia thường dùng các tri thức kho học như sự kiện, luật, sau đó chuyển chúng thành các tri thức heuristic để thuận tiện hơn trong việc giải quyết một số bài toán. 17
10. 2.2.Các loại tri thức (tiếp) 5. Tri thức có cấu trúc: mô tả tri thức theo cấu trúc. Loại tri thức này mô tả mô hình tổng quan hệ thống theo quan điểm của chuyên gia, bao gồm khái niêm, khái niệm con, và các đối tượng; diễn tả chức năng và mối liên hệ giữa các tri thức dựa theo cấu trúc xác định. 18
11. 2.3. CÁC KỸ THUẬT BIỂU DIỄN TRI THỨC 2.3.1. Bộ ba: Đối tượng - Thuộc tính – Giá trị 2.3.2. Các luật dẫn 2.3.3. Mạng ngữ nghĩa 2.3.4. Frames 2.3.5. Logic 19
12. 2.3.1. Bộ ba Đối tượng-Thuộc tính–Giá trị ⚫ Một sự kiện có thể được dùng để xác nhận giá trị của một thuộc tính xác định của một vài đối tượng. Ví dụ, mệnh đề “quả bóng màu đỏ” xác nhận “đỏ” là giá trị thuộc tính “màu” của đối tượng “quả bóng”. Kiểu sự kiện này được gọi là bộ ba Đối tượng-Thuộc tính–Giá trị (O-A-V – Object – Attribute - Value) Màu Chó Nâu Đối tượng Thuộc tính Giá trị 20
13. 2.3.3. Mạng ngữ nghĩa ⚫ Là một phương pháp biểu diễn tri thức dùng đồ thị trong đó nút biểu diễn đối tượng và cung biểu diễn quan hệ giữa các đối tượng. Cánh CÓ LÀ Sẻ Chim DI CHUYỂN Bay Hình 2.3. “Sẻ là Chim” thể hiện trên mạng ngữ nghĩa 26
14. 2.3.3. Mạng ngữ nghĩa (tiếp) Cánh Không khí CÓ THỞ Chip Sẻ Chim Con vật LÀ LÀ LÀ DI CHUYỂN Cánh cụt Bay DI CHUYỂN ĐI 27 Hình 2.4. Phát triển mạng ngữ nghĩa
15. 2.3.4. Frame Frame là cấu trúc dữ liệu để thể hiện tri thức đa dạng về khái niệm hay đối tượng nào đó Hình 2.6. Cấu trúc Frame 28
16. 2.3.4. Frame (tiếp) Chim Chim sẻ Vịt Chim cảnh Sẻ đồng Sẻ nhà Vịt cỏ Vẹt Yểng Hình 2.7. Nhiều mức của Frame mô tả quan hệ phức tạp hơn 29
17. 2.4.2. Các hoạt động của Hệ thống Suy diễn tiến THÊM THÔNG TIN VÀO BỘ NHỚ LÀM VIỆC XÉT LUẬT TIẾP THEO XÉT LUẬT ĐẦU TIÊN Đúng GIẢ THIẾT KHỚP VỚI BỘ NHỚ CÒN LUẬT KHÁC Sai Đúng Sai THÊM LUẬT VÀO BỘ NHỚ LÀM VIỆC DỪNG CÔNG VIỆC 32
18. Chương 3. Hệ MYCIN Trần Nguyên Hương 39
19. Hình 3.1. Mạng suy diễn C5 0.8 C4 C1 0.9 0.8 C2 C3 1 e 0.9 0.7 0.6 0.5 e2 e3 e4 e5 49
20. Chương 4. HỆ HỌC Trần Nguyên Hương 53
21. 4.1. Mở đầu ⚫ Các chương trước đã thảo luận về biểu diễn và suy luận tri thức. Trong trường hợp này giả định đã có sẵn tri thức và có thể biểu diễn tường minh tri thức. ⚫ Tuy vậy, trong nhiều tình huống sẽ không có sẵn tri thức: – Cần biết các luật mô tả lĩnh vực cụ thể – Bài toán không được biểu diễn tường minh dưới dạng các luật sự kiện – 54
22. Conclusion Skin Colour Size Flesh safe Hairy brown large Hard 4.1. Mở đầu safe hairy green large Hard ⚫ Một người lạc dangerous smooth red large Soft trên hoang đảo. safe hairy green large Soft Để sống, cần safe hairy red small Hard phải thử xem loại quả nào ăn được safe smooth red small Hard loại nào độc. Sau safe smooth brown small Hard nhiều lần thử, sẽ dangerous hairy green small Soft lập được bảng thống kê sau dangerous smooth green small Hard safe hairy red large Hard safe smooth brown large Soft Identifying dangerous smooth green small soft what's good safe hairy red small soft to eat? dangerous smooth red large hard safe smooth red small hard dangerous hairy green small hard
23. 4.2. Các hình thức học 1. Học vẹt 2. Học bằng cách chỉ dẫn 3. Học bằng quy nạp Xem giáo trình 4. Học bằng tương tự (chương 7) 5. Học dựa trên giải thích 6. Học dựa trên tình huống 7. Học không giám sát 56
24. 4.3. Bài toán - Cho bảng nhiều cột, mỗi cột là một dấu hiệu (thuộc tính ), - Một cột là kết luận chỉ 2 khả năng “có” | “không”. - Mỗi dòng của bảng là một trường hợp (có được từ người chuyên gia, từ kinh nghiệm quá khứ ). -> Cây quyết định biểu diễn tri thức từ bảng này các nút = lựa chọn, rẽ thành nhiều nhánh, tùy theo giá trị của một dấu hiệu ( thuộc tính ). - Nút lá là một phương án quyết định: có | không. 58
25. Conclusion Skin Colour Size Flesh Ví dụ safe Hairy brown large Hard safe hairy green large Hard ⚫ Một người lạc dangerous smooth red large Soft trên hoang đảo. safe hairy green large Soft Để sống, cần safe hairy red small Hard phải thử xem loại quả nào ăn được safe smooth red small Hard loại nào độc. Sau safe smooth brown small Hard nhiều lần thử, sẽ dangerous hairy green small Soft lập được bảng thống kê sau dangerous smooth green small Hard safe hairy red large Hard safe smooth brown large Soft Identifying dangerous smooth green small soft what's good safe hairy red small soft to eat? dangerous smooth red large hard safe smooth red small hard dangerous hairy green small hard
26. Ví dụ ⚫ Mỗi dòng trong bảng là một ví dụ học. ⚫ Bảng là tập ví dụ học ⚫ Mỗi dòng có thể coi là một luật dạng IF skin = hairy and colour = brown and size = large and flesh = hard THEN conclusion = safe
27. Ví dụ ⚫ Có thể tạo ra một cây quyết định để thay thế tập hợp các luật ⚫ Một nút lựa chọn của cây quyết định có dạng tổng quát như sau IF thuộc tính = giá trị1 then else if thuộc tính = giá trị2 then else if else if thuộc tính = giá trịN then ⚫ Trên cây quyết định, một đường đi từ gốc đến nút lá sẽ ứng với một luật.
28. 4.4. Tạo cây quyết định - Thuật toán CLS ⚫ Do Hunt đề xuất sử dụng trong hệ thống học khái niệm CLS – concept learning system, 1966. ⚫ Là Thuật toán học quy nạp lần đầu tiên 62
29. 4.4. Tạo cây quyết định - Thuật toán CLS Xuất phát: cây rỗng. Bổ xung thêm dần các nút cho đến khi cây quyết định phân loại được đúng tất cả các ví dụ trong tập học C. 1- Nếu các ví dụ trong C đều “đúng” thì tạo nút lá “có” và kết thúc Nếu các ví dụ trong C đều “sai” thì tạo nút lá “không” và kết thúc. Trái lại: 2- Chọn một thuộc tính A có các giá trị V1,V2 Vm. Tạo nút quyết định m nhánh. 3- Chia tập ví dụ học thành m tập con C1,C2 Cm tùy theo giá trị của thuộc tính đã chọn 4- Quay lại từ bước 1. 63
30. 4.4. Tạo cây quyết định - Thuật toán CLS ⚫ Trong thuật toán CLS, việc chọn thuộc tính A ở bước 2 là ngẫu nhiên. ⚫ Thuật toán Quinland sẽ cải tiến để tăng hiệu quả bằng cách chọn thuộc tính có độ phân biệt cao nhất. 64
31. Conclusion Skin Colour Size Flesh Minh hoạ safe Hairy brown large Hard CLS safe hairy green large Hard dangerous smooth red large Soft safe hairy green large Soft safe hairy red small Hard safe smooth red small Hard safe smooth brown small Hard dangerous hairy green small Soft dangerous smooth green small Hard safe hairy red large Hard safe smooth brown large Soft dangerous smooth green small soft safe hairy red small soft dangerous smooth red large hard safe smooth red small hard dangerous hairy green small hard
32. Minh hoạ CLS Skin=“Hairy” Conclusion Skin Colour Size Flesh safe Hairy brown large Hard safe hairy green large Hard safe hairy green large Soft safe hairy red small Hard dangerous hairy green small Soft safe hairy red large Hard safe hairy red small soft dangerous hairy green small hard
33. Minh hoạ Skin=“Smooth” CLS Conclusion Skin Colour Size Flesh dangerous smooth red large Soft safe smooth red small Hard safe smooth brown small Hard dangerous smooth green small Hard safe smooth brown large Soft dangerous smooth green small soft dangerous smooth red large hard safe smooth red small hard
34. Minh hoạ CLS Skin=“Hairy” and Size = “large” Conclusion Skin Colour Size Flesh safe Hairy brown large Hard safe hairy green large Hard safe hairy green large Soft safe hairy red large Hard R1: If Skin=“Hairy” and Size = “large” Then Safe 68
35. Minh hoạ CLS Skin=“Hairy” and Size = “Small” Conclusion Skin Colour Size Flesh safe hairy red small Hard dangerous hairy green small Soft safe hairy red small soft dangerous hairy green small hard R2: If Skin=“Hairy” and Size = “Small” and Colour=“Green” then Dangerous R3: If Skin=“Hairy” and Size = “Small” and Colour=“Red” then Safe 69
36. Skin=“Smooth” and Size = “Small” Conclusion Skin Colour Size Flesh safe smooth red small Hard safe smooth brown small Hard dangerous smooth green small Hard safe smooth red small hard R4: If Skin=“Smooth” and Size = “Small” and Colour=“Green” then Dangerous R5: If Skin=“Smooth” and Size = “Small” and Colour=“Red” then Safe R6: If Skin=“Smooth” and Size = “Small” and Colour=“Brown” 70 then Safe
37. Skin=“Smooth” and Size = “Large” Conclusion Skin Colour Size Flesh dangerous smooth red large Soft safe smooth brown large Soft dangerous smooth red large hard R7: If Skin=“Smooth” and Size = “Large” and Colour=“Red” then Dangerous R8: If Skin=“Smooth” and Size = “Small” and Colour=“Brown” then Safe 71
38. Cây quyết định Skin Hairy Smooth Size Size Small Large Small Large Color Green Safe Color Color Dangerous Brown Green Red Red Red Safe Brown Dangerous Safe Dangerous Safe Safe
39. 4.5. Entropy và mức độ phân biệt của một thuộc tính ⚫ Thế nào là độ phân biệt của một thuộc tính? ⚫ Lí thuyết thông tin cho phép lượng hóa thông tin. ⚫ Một cách tổng quát, giả sử kết luận C có thể nhận một trong n giá trị c1, c2, cn. Trong ví dụ trên, C nhận 2 giá trị “ăn được”, “độc”. 73
40. 4.5. Entropy và mức độ phân biệt của một thuộc tính (tiếp) ⚫ Giả sử thuộc tính A có thể nhận m giá trị a1, a2, am. ⚫ Kí hiệu xác suất điều kiện P(C= ci | A = aj) hay gọn hơn P(ci | aj). ⚫ Ví dụ P(C= safe | Skin = hairy) = 6/8 = ¾, (8 dòng với Skin=hairy, (trong đó 6 dòng kết luận C = safe. 74
41. 4.5. Entropy và mức độ phân biệt của một thuộc tính (tiếp) Entropy(C) = - ∑ P(C = ci) log2 P(C = ci) i=1, 2. ,,, n 75
42. 4.5. Entropy và mức độ phân biệt của một thuộc tính (tiếp) ⚫ Entropy của thông tin A= aj đối với kết luận C Biểu thức - log2 P(ci | aj) là lượng tin mà A = aj mang lại cho kết luận C = ci. Tổng theo i = 1 n là entropy của thông tin A= aj đối với kết luận C: Entropy(aj) = - ∑ P(ci | aj ) log2 P(ci | aj) Entropy của thuộc tính A đối với C được định nghĩa là tổng Entropy (A) = - ∑ P(A = aj) * Entropy(aj) = - ∑ P(A =aj) ∑ P(ci | aj ) log2 P(ci | aj) 76
43. 4.5. Entropy và mức độ phân biệt của một thuộc tính (tiếp) ⚫ Entropy là một số biến thiên trong đoạn [0,1]. Entropy là độ đo mức nghi ngờ, mức ngẫu nhiên của kết luận. – Nó càng cao thì nghi ngờ về kết luận C càng lớn. – Entropy càng thấp thì aj càng mang nhiều thông tin về kết luận C. – Entropy = 0 nghĩa là tất cả các ví dụ thuộc cùng 1 lớp, có cùng một kết luận. 77 – Entropy = 1 nghĩa là hoàn toàn ngẫu nhiên
44. 4.5. Entropy và mức độ phân biệt của một thuộc tính (tiếp) ⚫ Ví dụ Xét thuộc tính Size trong ví dụ trên. Từ bảng dữ liệu ta có – P(safe | large ) = 5/7 – P(dangerous | large ) = 2/7 – P(large ) = 7/16 – P(safe | small ) = 5/9 – P(dangerous | small ) = 4/9 – P(small ) = 9/16 78
45. 4.5. Entropy và mức độ phân biệt của một thuộc tính (tiếp) ⚫ Như vậy entropy của thuộc tính Size đối với kết luận “safe | dangerous” là 7/16* {5/7 *log2 5/7 + 2/7 * log2 2/7} + 9/16* {5/9 *log2 5/9 + 4/9* log2 4/9} = 0.9350955 79
46. 4.5. Entropy và mức độ phân biệt của một thuộc tính (tiếp) ⚫ Định nghĩa lượng tin mà thuộc tính A mang lại đối với tập ví dụ Gain(C, A) = Entropy(C) – Entropy (A) ở đây: Thuộc tính có entropy thấp nhất chính là có độ phân biệt cao nhất (cho kết luận C). 80
47. 4.6. Thuật giải Quinlan ⚫ Là thuật toán học theo quy nạp dùng luật, đa mục tiêu ⚫ Do Quinlan đưa ra năm 1979. Cải tiến thuật toán CLS. ⚫ Còn gọi là thuật toán ID3 (ID là viết tắt của ‘iterative dichotomiser = chia đôi nhiều lần) ⚫ Ý tưởng: – 1- CLS làm việc với toàn bộ tập thí dụ học có sẵn từ đầu. ID3 giảm số lượng thí dụ học, dùng một tập con xuất phát. – 2- ở mỗi bước ID3 chọn thuộc tính có mức phân 81 biệt cao nhất để phân nhánh.
48. 4.6. Thuật giải Quinlan ⚫ Các bước của thuật toán ID3 1. Chọn ngẫu nhiên một tập con W của tập các ví dụ học, gọi là cửa sổ 2. Áp dụng thuật toán CLS tạo cây (hay luật) quyết định cho W 3. Duyệt toàn bộ các ví dụ còn lại (trừ W) trên cây để phát hiện các ngoại lệ 4. Nếu có ví dụ là ngoại lệ, thêm vào W và lặp lại từ bước 2. Trái lại, kết thúc cho kết 82 quả là cây nhận được
49. 4.6. Thuật giải Quinlan Chi tiết bước 2 1. Tính entropy của tất cả các thuộc tính (đối với kết luận cần quyết định); 2. Chọn thuộc tính (ví dụ A) có entropy thấp nhất 3. Chia tập ví dụ thành các tập con tùy theo giá trị của thuộc tính A. A nhận cùng một giá trị trên mỗi tập con. 4. Xây dựng cây phân nhánh theo giá trị của A: if A=a1 then (subtree1) if A=a2 then (subtree2) etc 5. Lặp lại từ bước 1 với mỗi cây con. 6. Mỗi lần lặp xét được 1 thuộc tính. Quá trình dừng khi đã xét hết các thuộc tính, hoặc không cần phân nhánh nữa 83 (vì mọi ví dụ trong một cây con đã có cùng kết luận.
50. Minh hoạ Thuật giải Quinlan – Tập C gồm 14 ví dụ như trong bảng dưới. Cột kết luận là có chơi bóng hay không. – Các thuộc tính: outlook, temperature, humidity, wind speed. – Các giá trị có thể: ⚫ Outlook (thời tiết) = { sunny, overcast – u ám , rain } ⚫ temperature (nhiệt độ)= {hot, mild, cool } ⚫ Humidity (độ ẩm) = { high, normal } ⚫ Wind (gió) = {weak, strong } 84
51. Day Outlook Temperature Humidity Wind Play ball D1 Sunny Hot High Weak No D2 Sunny Hot High Strong No D3 Overcast Hot High Weak Yes D4 Rain Mild High Weak Yes D5 Rain Cool Normal Weak Yes D6 Rain Cool Normal Strong No D7 Overcast Cool Normal Strong Yes D8 Sunny Mild High Weak No D9 Sunny Cool Normal Weak Yes D10 Rain Mild Normal Weak Yes D11 Sunny Mild Normal Strong Yes D12 Overcast Mild High Strong Yes D13 Overcast Hot Normal Weak Yes D14 Rain Mild High Strong No
52. Minh hoạ Thuật giải Quinlan ⚫ Xác định thuộc tính làm nút gốc cây. ⚫ Tính Gain của tất cả các thuộc tính ⚫ Ví dụ Gain(C, Wind) = ? Gain(C,Wind) = Entropy(C)-(8/14)*Entropy(weak) - (6/14)*Entropy(strong) Entropy(weak) = - (6/8)*log2(6/8) - (2/8)*log2(2/8) = 0.811 Entropy(Strong) = - (3/6)*log2(3/6) - (3/6)*log2(3/6) = 1.00 Vậy: Gain(C,Wind) = 0.940 - (8/14)*0.811 - (6/14)*1.00 = 0.048 86
53. Minh hoạ Thuật giải Quinlan Kết quả: Gain(C, Outlook) = 0.246 Gain(C, Temperature) = 0.029 Gain(C, Humidity) = 0.151 Gain(C, Wind) = 0.048 Thuộc tính Outlook có Gain cao nhất. Do đó, nó được dùng làm nút gốc. 87
54. Minh hoạ Thuật giải Quinlan Outlook có 3 giá trị, cần phân 3 nhánh sunny, overcast, rain. 88
55. Minh hoạ Thuật giải Quinlan ⚫ Tiếp tục phân nhánh. Xét nút Sunny. Chỉ còn các thuộc tính Humidity, Temperature, Wind. ⚫ Csunny = {D1, D2, D8, D9, D11} = 5 trường hợp với outlook = sunny – Gain(Csunny, Humidity) = 0.970 – Gain(Csunny, Temperature) = 0.570 – Gain(Csunny, Wind) = 0.019 89
56. Minh hoạ Thuật giải Quinlan ⚫ Thuộc tính Humidity có Gain cao nhất. Lấy nó làm nút phân nhánh tiếp theo. Quá trình lặp lại 90
57. Minh hoạ Thuật giải Quinlan Cây quyết định thể hiện các luật, là tri thức rút ra từ bảng trên. 1. IF outlook = sunny AND humidity = high THEN playball = no 2. IF outlook = rain AND humidity = high THEN playball = no 3. IF outlook = rain AND wind = strong THEN playball = yes 4. IF outlook = overcast THEN playball = yes 5. IF outlook = rain AND wind = weak THEN 91 playball = yes
58. Ưu điểm của giải thuật Quinlan 1. Dùng cửa sổ hay phương pháp lọc các ngoại lệ. Giảm số ví dụ cần xử lí, tập trung vào các ví dụ tốt 2. Chọn thuộc tính có độ phân biệt cao nhất ở mỗi bước, là một heuristic cho phép tăng hiệu quả của hệ thống. 92
59. Nhược điểm của giải thuật Quinlan 1. Thuật toán không biết phát hiện thuộc tính không liên quan đến kết luận. - Ví dụ nếu trong bảng trên có cả cột chứa thông tin về “ăn quả vào ngày thứ mấy trong tuần” thì thuật toán vẫn xử lí mối tương quan giữa việc “ăn quả vào ngày thứ mấy trong tuần” và kết luận “ăn được” / “độc” một cách giả tạo. 93
60. Nhược điểm của giải thuật Quinlan 2. Thuật toán chỉ xét mỗi lần một Outcome X Y thuộc tính. Nếu có 2 thuộc tính có entropy trùng khớp nhau thì yes 3 3 nó vẫn xét riêng mặc dù đúng no 2 1 ra nên xem xét chúng cùng với yes nhau. 4 4 no 2 4 Thuật toán ID3 sẽ không thể phát no 1 3 hiện ra luật đơn giản là : yes 1 1 if X = Y then outcome = yes yes else outcome = no 2 2 94 no 2 3
61. Nhược điểm của giải thuật Quinlan 3. Khi quy nạp rút ra luật từ một tập ví dụ với nhiều khả năng kết luận khác nhau (n lớn chứ không phải là 2) thì thuật toán quá nhạy cảm với những thay đổi tầm thường trong tập ví dụ. 4. Thuật toán không xử lí các luật không chắc chắn, dữ liệu không chắc chắn. 5. Nhiều thí dụ tương tự cũng chỉ như một thí dụ. 6. Không xử lí được các thí dụ mâu thuẫn nhau 95
62. Conclusion Skin Colour Size Flesh Bài tập 1 safe Hairy brown large Hard safe hairy green large Hard ⚫ Một người lạc dangerous smooth red large Soft trên hoang đảo. Để sống, cần safe hairy green large Soft phải thử xem loại safe hairy red small Hard quả nào ăn được safe smooth red small Hard loại nào độc. Sau safe smooth brown small Hard nhiều lần thử, sẽ lập được bảng dangerous hairy green small Soft thống kê sau dangerous smooth green small Hard safe hairy red large Hard Xây dựng safe smooth brown large Soft các tập luật dangerous smooth green small soft dùng thuật safe hairy red small soft toán Quinlan dangerous smooth red large hard safe smooth red small hard dangerous hairy green small hard
63. Bài tập 2. Xây dựng tập luật để suy diễn ra Conclusion sử dụng thuật toán Quinlan
64. Bài tập 2. Kết quả
65. Bài tập 3. Xây dựng tập luật suy diễn ra Profit sử dụng thuật toán Quinlan
66. Kết quả 100
67. 4.7. Thuật giải ILA (Inductive Learning Algorithm) 101
68. 4.7. Thuật giải ILA 102
69. 4.7. Thuật giải ILA 103
70. 4.7. Thuật giải ILA 104
71. Bài tập: Xây dựng tập luật cho kết luận sử dụng thuật toán ILA (Bảng 7.1. trang 129 giáo trình) 112
72. STT Tên Màu tóc Chiều cao Cân nặng Dùng Kết quả người thuốc 1 Hoa Đen Tầm thước Nhẹ Không Bị rám 2 Lan Đen Cao Vừa phải Có Không 3 Xuân Râm Thấp Vừa phải Có Không 4 Hạ Đen Thấp Vừa phải Không Bị rám 5 Thu Bạc Tầm thước Nặng Không Bị rám 6 Đông Râm Cao Nặng Không Không 7 Mơ Râm Tầm thước Nặng Không Không 8 Đào Đen Thấp Nhẹ Có Không
73. Chương 5. HỆ THỐNG MỜ CHO CÁC BIẾN LIÊN TỤC Trần Nguyên Hương 11 4