›
›

Các hệ thống thông minh nhân tạo & ứng dụng - Máy học - Bùi Thị Danh

pdf 58 trang Gia Huy 17/05/2022 2830
Download
Bạn đang xem 20 trang mẫu của tài liệu "Các hệ thống thông minh nhân tạo & ứng dụng - Máy học - Bùi Thị Danh", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfcac_he_thong_thong_minh_nhan_tao_ung_dung_may_hoc_bui_thi_da.pdf

Nội dung text: Các hệ thống thông minh nhân tạo & ứng dụng - Máy học - Bùi Thị Danh

  1. CÁC HỆ THỐNG THƠNG MINH NHÂN TẠO & ỨNG DỤNG Máy Học THS. BÙI THỊ DANH BM.KHMT, KHOA CNTT, ĐH.KHTN TP.HCM
  2. Nội dung chính Máy học là gì? Phương pháp Nạve Bayes Phương pháp ID3 Phương pháp ILA 2
  3. Máy học là gì? Arthur Samuel (1959): Máy học là một lĩnh vực nghiên cứu mang lại cho máy tính khả năng học mà khơng phải lập trình một cách tường minh. 3
  4. Máy học là gì? Tom Mitchell (1998): Một chương trình máy tính được nĩi là “học” từ 𝑖푛ℎ 푛𝑔ℎ𝑖ệ tương ứng với ơ푛𝑔 푣𝑖ệ và độ đo ℎ𝑖ệ 푠 ấ푡 푃 nếu hiệu suất trên , được đo bởi 푃, cải thiện nhờ kinh nghiệm Ví dụ: một chương trình máy tính xem xét các emails mà chúng ta đã đánh dấu và khơng đánh dấu là “spam”, từ đĩ học được cách để lọc các email spam. ◦ ơ푛𝑔 푣𝑖ệ : phân loại email là spam hay khơng phải spam ◦ 퐾𝑖푛ℎ 푛𝑔ℎ𝑖ệ : xem xét việc đánh dấu và khơng đánh dấu spam của chúng ta ◦ 𝑖ệ 푠 ấ푡 푃: số lượng email phân loại đúng là spam/khơng phải spam 4
  5. Máy học là gì? Máy học cĩ thể được dùng để: ◦ Khai thác dữ liệu: nhiều tập dữ liệu lớn đến từ sự phát triển của tự động hĩa/web ◦ Dữ liệu click web, hồ sơ bệnh án, mạng xã hội ◦ Xây dựng các ứng dụng khơng thể lập trình thủ cơng ◦ Xe hơi tự lái, nhận dạng chữ viết tay, xử lý ngơn ngữ tự nhiên (NLP), thị giác máy tính ◦ Các chương trình tự điều chỉnh ◦ Hệ thống đề cử sản phẩm của Amazon, Netflix ◦ Hiểu về việc học của con người (bộ não) 5
  6. Máy học là gì? Các thuật tốn máy học cĩ thể chia thể các nhĩm: ◦ Supervised learning (học cĩ giám sát) ◦ Unsupervised learning (học khơng cĩ giám sát) ◦ Reinforcement learning (học tăng cường) ◦ 6
  7. Học cĩ giám sát Dữ liệu dùng để “học” (hay huấn luyện) cần cĩ “câu trả lời đúng” đi kèm. Ví dụ - Phát hiện và lọc email spam ◦ Dữ liệu học: các email đã được đánh dấu là spam và khơng được đánh dấu là spam. ◦ Dựa trên các thuộc tính(đặc trưng): chiều dài email, tỉ lệ kí tự, số lượng url ◦ Phân loại cho các email mới. Ví dụ - Dự đốn giá nhà ◦ Dữ liệu học: các căn nhà và giá tương ứng ◦ Dựa trên các thuộc tính (đặc trưng): vị trí, diện tích, năm xây dựng ◦ Dự đốn giá cho các ngơi nhà khơng cĩ trong dữ liệu học 7
  8. Học cĩ giám sát Ví dụ - Chẩn đốn y khoa ◦ Học từ dữ liệu là những bệnh án của các bệnh nhân. ◦ Các thuộc tính: Sốt, nơn, tiêu chảy, rét run, ◦ Dự đốn cho các ca mới Mẫu Sốt Nơn Tiêu chảy Rét run Phân loại d1 khơng khơng khơng khơng khỏe mạnh d2 trung bình khơng khơng khơng cúm d3 cao khơng khơng cĩ cúm d4 cao cĩ cĩ khơng ngộ độc salmonella d5 trung bình khơng cĩ khơng ngộ độc salmonella d6 khơng cĩ cĩ khơng viêm ruột d7 trung bình cĩ cĩ khơng viêm ruột d8 khơng khơng cĩ cĩ ? 8
  9. Học khơng giám sát Dữ liệu dùng để học khơng cĩ “câu trả lời đúng” đi kèm Cố gắng hiểu dữ liệu và phát hiện ra các cấu trúc hay các mẫu trong dữ liệu 9
  10. Học khơng cĩ giám sát 10
  11. Học tăng cường Tương tác với mơi trường, nhận phản hồi và từ đĩ rút ra mơ hình mà mơi trường đang vận hành. Thực hiện tương tác agent Mơi trường Nhận phản hồi (phần thưởng r) 11
  12. Học tăng cường 12
  13. Nội dung chính Máy học là gì? Phương pháp Nạve Bayes Phương pháp ID3 Phương pháp ILA 13
  14. Chẩn đốn y khoa Tính xác suất cho từng khả Mẫu Sốt Nơn Tiêu chảy Rét run Phân loại năng: d1 khơng khơng khơng khơng khỏe mạnh ◦ 푃 ℎỏ푒 ạ푛ℎ 8 d2 trung bình khơng khơng khơng cúm ◦ 푃( ú | 8) d3 cao khơng khơng cĩ cúm ◦ 푃 푛𝑔ộ độ 8 d4 cao cĩ cĩ khơng ngộ độc salmonella ◦ 푃(푣𝑖ê ộ푡| 8) d5 trung bình khơng cĩ khơng ngộ độc salmonella Chọn ra xác suất lớn nhất để d6 khơng cĩ cĩ khơng viêm ruột d trung bình cĩ cĩ khơng viêm ruột quyết định nhĩm bệnh của 8 7 d8 khơng khơng cĩ cĩ ? Tính như thế nào? 14
  15. Phương pháp Nạve Bayes Gọi 1, 2, , 푛 là các thuộc tính trong tập dữ liệu, 푌 là thuộc tính phân lớp. Giả sử 1, 2, , 푛 độc lập điều kiện với nhau khi cho 푌 Phương pháp dựa trên luật suy diễn xác suất Bayes: 푃 푌 . 푃(푌) 푃 푌 = 푃( ) 푃 = 8 푌 = ú .푃(푌= ú ) Ví dụ: 푃 푌 = ú = 8 = 푃( = 8) Mẫu Sốt Nơn Tiêu chảy Rét run Phân loại d1 khơng khơng khơng khơng khỏe mạnh d2 trung bình khơng khơng khơng cúm 15
  16. Phương pháp Nạve Bayes Ước lượng giá trị của 푃 푌 = : 푪풐풖풏풕( ) 퐏(퐘 = 퐜) = 푪풐풖풏풕(푫) ◦ 표 푛푡 : số mẫu cĩ 푌 = ◦ 표 푛푡( ): tổng số mẫu cĩ trong dữ liệu học. Ước lượng giá trị của 푃 = d 푌 = ): ◦ được xác định bởi các thuộc tính 1, 2, , 푛 và chúng độc lập nhau nên: 풏 푷 푿 = 풅 풀 = = 푷 푿 = 풙 , , 푿풏 = 풙풏 풀 = = ෑ 푷(푿풊 = 풙풊|풀 = ) 풊= ◦ Theo đĩ, chúng ta cần ước lượng 푃( 푖 = 푖|푌 = ): 푪풐풖풏풕(풙 , ) 푷 푿 = 풙 풀 = = 풊 풊 풊 푪풐풖풏풕( ) ◦ C표 푛푡( 푖, ): số mẫu cĩ 푌 = và thuộc tính thứ 𝑖 cĩ giá trị là 푖 ◦ 표 푛푡( ): số mẫu cĩ 푌 = 16
  17. Ví dụ 1 Mẫu Tuyết Thời tiết Mùa Sức khỏe Trượt tuyết? 1 ẩm sương mù vắng tốt khơng 2 khơ nắng vắng bị thương khơng 3 khơ nắng vắng tốt cĩ 4 khơ nắng cao điểm tốt cĩ 5 khơ nắng vừa phải tốt cĩ 6 băng giĩ cao điểm mệt mỏi khơng 7 ẩm nắng vắng tốt cĩ 8 băng sương mù vừa phải tốt khơng 9 khơ giĩ vắng tốt cĩ 10 khơ giĩ vắng tốt cĩ 11 khơ sương mù vắng tốt cĩ 12 khơ sương mù vắng tốt cĩ 13 ẩm nắng vừa phải tốt cĩ 14 băng sương mù vắng bị thương khơng 17
  18. Ví dụ 1 Ước lượng 푃(푌 = ): ◦ 푃( ượ푡 푡 ế푡 = ĩ) = 9/14 ◦ 푃( ượ푡 푡 ế푡 = ℎơ푛𝑔) = 5/14 Ước lượng 푃 1 = 푖 푌 = , với 1 ≡ ế푡 ◦ 푃( ế푡 = ẩ | ượ푡 푡 ế푡 = ĩ) = 2/9 ◦ 푃( ế푡 = ℎơ | ượ푡 푡 ế푡 = ĩ) = 7/9 ◦ 푃( ế푡 = ă푛𝑔 | ượ푡 푡 ế푡 = ĩ) = 0/9 ◦ 푃( ế푡 = ă푛𝑔 | ượ푡 푡 ế푡 = ℎơ푛𝑔) = 3/5 ◦ 푃( ế푡 = ẩ | ượ푡 푡 ế푡 = ℎơ푛𝑔) = 1/5 ◦ 푃( ế푡 = ℎơ | ượ푡 푡 ế푡 = ℎơ푛𝑔) = 1/5 18
  19. Ví dụ 1 Ước lượng 푃 2 = 푖 푌 = , với 2 ≡ ℎờ𝑖 푡𝑖ế푡 ◦ 푃( ℎờ𝑖 푡𝑖ế푡 = 𝑔𝑖ĩ | ượ푡 푡 ế푡 = ĩ) = 2/9 ◦ 푃( ℎờ𝑖 푡𝑖ế푡 = 푛ắ푛𝑔 | ượ푡 푡 ế푡 = ĩ) = 5/9 ◦ 푃( ℎờ𝑖 푡𝑖ế푡 = 푠ươ푛𝑔 ù | ượ푡 푡 ế푡 = ĩ) = 2/9 ◦ 푃( ℎờ𝑖 푡𝑖ế푡 = 𝑔𝑖ĩ | ượ푡 푡 ế푡 = ℎơ푛𝑔) = 1/5 ◦ 푃( ℎờ𝑖 푡𝑖ế푡 = 푛ắ푛𝑔 | ượ푡 푡 ế푡 = ℎơ푛𝑔) = 1/5 ◦ 푃( ℎờ𝑖 푡𝑖ế푡 = 푠ươ푛𝑔 ù | ượ푡 푡 ế푡 = ℎơ푛𝑔) = 3/5 19
  20. Ví dụ 1 Ước lượng 푃 3 = 푖 푌 = , với 3 ≡ ù ◦ 푃( ù = 표 đ𝑖ể | ượ푡 푡 ế푡 = ĩ) = 1/9 ◦ 푃( ù = 푣ắ푛𝑔 | ượ푡 푡 ế푡 = ĩ) = 6/9 ◦ 푃( ù = 푣ừ ℎả𝑖 | ượ푡 푡 ế푡 = ĩ) = 2/9 ◦ 푃( ù = 표 đ𝑖ể | ượ푡 푡 ế푡 = ℎơ푛𝑔) = 1/5 ◦ 푃( ù = 푣ắ푛𝑔 | ượ푡 푡 ế푡 = ℎơ푛𝑔) = 3/5 ◦ 푃( ù = 푣ừ ℎả𝑖 | ượ푡 푡 ế푡 = ℎơ푛𝑔) = 1/5 20
  21. Nạve Bayes – Bài tập ví dụ 1 Ước lượng 푃 4 = 푖 푌 = , với 4 ≡ 푆ứ ℎỏ푒 ◦ 푃(푆ứ ℎỏ푒 = ị 푡ℎươ푛𝑔 | ượ푡 푡 ế푡 = ĩ) = 0/9 ◦ 푃(푆ứ ℎỏ푒 = ệ푡 ỏ𝑖 | ượ푡 푡 ế푡 = ĩ) = 0/9 ◦ 푃(푆ứ ℎỏ푒 = 푡ố푡 | ượ푡 푡 ế푡 = ĩ) = 9/9 ◦ 푃(푆ứ ℎỏ푒 = ị 푡ℎươ푛𝑔 | ượ푡 푡 ế푡 = ℎơ푛𝑔) = 2/5 ◦ 푃(푆ứ ℎỏ푒 = ệ푡 ỏ𝑖 | ượ푡 푡 ế푡 = ℎơ푛𝑔) = 1/5 ◦ 푃(푆ứ ℎỏ푒 = 푡ố푡 | ượ푡 푡 ế푡 = ℎơ푛𝑔) = 2/5 21
  22. Phân loại cho mẫu mới Mẫu Tuyết Thời tiết Mùa Sức khỏe Trượt tuyết 15 ẩm nắng vắng Mệt mỏi ? 푃( ượ푡 푡 ế푡 = ĩ | ) = 푃( ượ푡 푡 ế푡 = ℎơ푛𝑔 | ) = = 푃( ế푡 = ẩ | ượ푡 푡 ế푡 = ĩ) = 푃( ế푡 = ẩ | ượ푡 푡 ế푡 = ℎơ푛𝑔) × 푃( ℎờ𝑖 푡𝑖ế푡 = 푛ắ푛𝑔 | ượ푡 푡 ế푡 = ĩ) × 푃( ℎờ𝑖 푡𝑖ế푡 = 푛ắ푛𝑔| ượ푡 푡 ế푡 = ℎơ푛𝑔) × 푃 ù = 푣ắ푛𝑔 ượ푡 푡 ế푡 = ĩ) × × 푃 ù = 푣ắ푛𝑔 ượ푡 푡 ế푡 = ℎơ푛𝑔) × × 푃(푆ứ ℎỏ푒 = ệ푡 ỏ𝑖| ượ푡 푡 ế푡 = ĩ) × 푃(푆ứ ℎỏ푒 = ệ푡 ỏ𝑖| ượ푡 푡 ế푡 = ℎơ푛𝑔) × 푃 ượ푡 푡 ế푡 = ĩ × 푃 ượ푡 푡 ế푡 = ℎơ푛𝑔 Khơng đi trượt 2 5 6 0 9 1 1 3 1 5 = × × × × = tuyết = × × × × ≅ . 17 9 9 9 9 14 5 5 5 5 14 22
  23. Làm trơn Laplace Khắc phục trường hợp 푃( 푖 = 푖 | 푌 = ) = 0 do khơng cĩ mẫu nào trong dữ liệu huấn luyện thỏa mãn điều kiện 표 푛푡 + 1 푃 푌 = = 표 푛푡( ) + 표 푛푡 , + 1 푃 = | 푌 = = 푖 푖 푖 표 푛푡 + ◦ là số giá trị trong thuộc tính phân lớp ◦ là số giá trị của thuộc tính 푖 23
  24. Ví dụ 1 푃( ượ푡 푡 ế푡? = ĩ) = 9/14 10/16 푃( ượ푡 푡 ế푡? = ℎơ푛𝑔) = 5/14 6/16 푃( ế푡 = ă푛𝑔 | ượ푡 푡 ế푡 = ĩ) = 0/9 1/12 푃( ℎờ𝑖 푡𝑖ế푡 = 𝑔𝑖ĩ | ượ푡 푡 ế푡 = ĩ) = 2/9 3/12 푃( ế푡 = ẩ | ượ푡 푡 ế푡 = ĩ) = 2/9 3/12 푃( ℎờ𝑖 푡𝑖ế푡 = 푛ắ푛𝑔 | ượ푡 푡 ế푡 = ĩ) = 5/9 6/12 푃( ế푡 = ℎơ | ượ푡 푡 ế푡 = ĩ) = 7/9 8/12 푃( ℎờ𝑖 푡𝑖ế푡 = 푠ươ푛𝑔 ù | ượ푡 푡 ế푡 = ĩ) = 2/9 3/12 푃( ế푡 = ă푛𝑔 | ượ푡 푡 ế푡 = ℎơ푛𝑔) = 3/5 4/8 푃( ℎờ𝑖 푡𝑖ế푡 = 𝑔𝑖ĩ | ượ푡 푡 ế푡 = ℎơ푛𝑔) = 1/5 2/8 푃( ế푡 = ẩ | ượ푡 푡 ế푡 = ℎơ푛𝑔) = 1/5 2/8 푃( ℎờ𝑖 푡𝑖ế푡 = 푛ắ푛𝑔 | ượ푡 푡 ế푡 = ℎơ푛𝑔) = 1/5 2/8 푃( ế푡 = ℎơ | ượ푡 푡 ế푡 = ℎơ푛𝑔) = 1/5 2/8 푃( ℎờ𝑖 푡𝑖ế푡 = 푠ươ푛𝑔 ù| ượ푡 푡 ế푡 = ℎơ푛𝑔) = 3/5 4/8 24
  25. Ví dụ 1 푃( ù = 표 đ𝑖ể | ượ푡 푡 ế푡 = ĩ) = 1/9 2/12 푃(푆ứ ℎỏ푒 = ị 푡ℎươ푛𝑔 | ượ푡 푡 ế푡 = ĩ) = 0/9 1/12 푃( ù = 푣ắ푛𝑔 | ượ푡 푡 ế푡 = ĩ) = 6/9 7/12 푃(푆ứ ℎỏ푒 = ệ푡 ỏ𝑖 | ượ푡 푡 ế푡 = ĩ) = 0/9 1/12 푃( ù = 푣ừ ℎả𝑖 | ượ푡 푡 ế푡 = ĩ) = 2/9 3/12 푃(푆ứ ℎỏ푒 = 푡ố푡 | ượ푡 푡 ế푡 = ĩ) = 9/9 10/12 푃( ù = 표 đ𝑖ể | ượ푡 푡 ế푡 = ℎơ푛𝑔) = 1/5 2/8 푃(푆ứ ℎỏ푒 = ị 푡ℎươ푛𝑔 | ượ푡 푡 ế푡 = ℎơ푛𝑔) = 2/5 3/8 푃( ù = 푣ắ푛𝑔 | ượ푡 푡 ế푡 = ℎơ푛𝑔) = 3/5 4/8 푃(푆ứ ℎỏ푒 = ệ푡 ỏ𝑖 | ượ푡 푡 ế푡 = ℎơ푛𝑔) = 1/5 2/8 푃( ù = 푣ừ ℎả𝑖 | ượ푡 푡 ế푡 = ℎơ푛𝑔) = 1/5 2/8 푃(푆ứ ℎỏ푒 = 푡ố푡 | ượ푡 푡 ế푡 = ℎơ푛𝑔) = 2/5 3/8 25
  26. Ví dụ 1 Mẫu Tuyết Thời tiết Mùa Sức khỏe Trượt tuyết? 15 ẩm nắng vắng mệt mỏi ? Phân loại cho mẫu mới: ◦ 푃( ượ푡 푡 ế푡 = ĩ | ) = 10/16 × 3/12 × 6/12 × 7/12 × 1/12 ≅ 0.0038 ◦ 푃( ượ푡 푡 ế푡 = ℎơ푛𝑔 | ) = 6/16 × 2/8 × 2/8 × 4/8 × 2/8 ≅ 0.0029 Vậy kết luận là đi trượt tuyết. 26
  27. Ví dụ 2 Áp dụng phương pháp Nạve Bayes với tập dữ liệu huấn luyện như bên dưới, biết rằng thuộc tính phân lớp là Lớp Mẫu Độ tuổi Hệ số Khu vực Lớp 1 15 1 A C1 2 20 3 B C2 3 25 2 A C1 4 30 4 A C1 5 35 2 B C2 6 25 4 A C1 7 15 2 B C2 8 20 3 B C2 Phân loại một mẫu dữ liệu mới X = (20, 4, B), cho biết X thuộc lớp C1 hay C2? 27
  28. Nội dung chính Máy học là gì? Phương pháp Nạve Bayes Phương pháp ID3 Phương pháp ILA 28
  29. Cây quyết định Cấu trúc cây quyết định: Tuyết ◦ Mỗi nút trong kiểm tra một thuộc tính ◦ Mỗi nhánh tương ứng với giá trị thuộc tính ẩm băng khơ ◦ Mỗi nút lá được gán một phân lớp Thời tiết khơng Sức khỏe Dựa trên cây quyết định, chúng ta cĩ thể rút ra các luật cho phân nắng sương mù bị thương tốt lớp: cĩ khơng khơng cĩ ◦ 푰푭 ế푡 = ẩ 푵푫 ℎờ𝑖 푡𝑖ế푡 = 푛ắ푛𝑔 푻푯푬푵 ượ푡 푡 ế푡 = ĩ. ◦ 푰푭 ế푡 = ẩ 푵푫 ℎờ𝑖 푡𝑖ế푡 = 푠ươ푛𝑔 ù 푻푯푬푵 ượ푡 푡 ế푡 = ĩ. ◦ 푰푭 ế푡 = ă푛𝑔 푻푯푬푵 ượ푡 푡 ế푡 = ℎơ푛𝑔. ◦ 푰푭 ế푡 = ℎơ 푵푫 푆ứ ℎỏ푒 = ị 푡ℎươ푛𝑔 푻푯푬푵 ượ푡 푡 ế푡 = ℎơ푛𝑔. ◦ 푰푭 ế푡 = ℎơ 푵푫 푆ứ ℎỏ푒 = 푡ố푡 푻푯푬푵 ượ푡 푡 ế푡 = ĩ. 29
  30. Thuật tốn ID3 Được phát triển đồng thời bởi Quinlan trong lĩnh vực Trí tuệ nhân tạo và Breiman, Friedman, Olsen và Stone trong Thống kê. Thực hiện lặp: ◦ Chọn là thuộc tính quyết định “tốt nhất” cho nút kế tiếp ◦ Gán là thuộc tính quyết định cho nút ◦ Với mỗi giá trị của , tạo nhánh con mới của nút ◦ Phân loại các mẫu huấn luyện cho các nút lá. ◦ Nếu các mẫu huấn luyện được phân loại hồn tồn thì dừng; ngược lại, lặp với các nút lá mới. Làm sao chọn thuộc tính quyết định tốt nhất? 30
  31. Thuật tốn ID3 Một số độ đo cho phép xác định “độ tốt” của thuộc tính: ◦ Entropy ◦ Độ lợi thơng tin (Information Gain) ◦ Chỉ mục Gini 31
  32. Độ đo Entropy Entropy của tập dữ liệu D, ( ), là độ đo sự khơng chắc chắn (hỗn loạn) trong tập dữ liệu = − ෍ . log2 ∈ ◦ ( ): tỉ lệ mẫu cĩ 푌 = trong tập dữ liệu ◦ : tập các giá trị cĩ thể cĩ của 푌 Thuộc tính quyết định Entropy cho một thuộc tính A: là thuộc tính cĩ entropy nhỏ nhất = ෍ p v . H( A=푣) 푣∈Values(A) ◦ 푣: một giá trị cĩ thể cĩ của thuộc tính . ◦ p(푣): tỉ lệ các mẫu cĩ giá trị là 푣 trong tập dữ liệu D ◦ H( A=푣): Entropy cho tập dữ liệu con của D chỉ gồm những mẫu cĩ thuộc tính A = 푣. 32
  33. Ví dụ Mẫu Tuyết Thời tiết Mùa Sức khỏe Trượt tuyết 1 ẩm sương mù vắng tốt khơng 2 khơ nắng vắng bị thương khơng 3 khơ nắng vắng tốt cĩ 4 khơ nắng cao điểm tốt cĩ 5 khơ nắng vừa phải tốt cĩ 6 băng giĩ cao điểm mệt mỏi khơng 7 ẩm nắng vắng tốt cĩ 8 băng sương mù vừa phải tốt khơng 9 khơ giĩ vắng tốt cĩ 10 khơ giĩ vắng tốt cĩ 11 khơ sương mù vắng tốt cĩ 12 khơ sương mù vắng tốt cĩ 13 ẩm nắng vừa phải tốt cĩ 14 băng sương mù vắng bị thương khơng 33
  34. Chọn thuộc tính quyết định ă푛𝑔 = −0/3 × log20/3 − 3/3 × log23/3 = 0 Tuyết ẩ = −2/3 × log22/3 − 1/3 × log21/3 = 0.918 log 7/8 − 1/8 × log 1/8 = 0.544 băng ẩm khơ ℎơ = −7/8 × 2 2 ( ế푡) = 3/14 × 0 + 3/14 × 0.918 + 8/14 × 0.544 = 0.508 0+,3- 2+,1- 7+,1- log 2/3 − 1/3 × log 1/3 = 0.918 𝑔𝑖ĩ = −2/3 × 2 2 푛ắ푛𝑔 = −5/6 × log25/6 − 1/6 × log21/6 = 0.65 Thời tiết 푠 = −2/5 × log22/5 − 3/5 × log23/5 = 0.971 ( ℎờ𝑖 푡𝑖ế푡) = 3/14 × 0.918 + 6/14 × 0.65 + 5/14 × 0.971 = 0.822 sương giĩ nắng mù 2+,1- 5+,1- 2+,3- 34
  35. Chọn thuộc tính quyết định log 1/2 − 1/2 × log 1/2 = 1 đ = −1/2 × 2 2 Mùa 푣ắ푛𝑔 = −6/8 × log26/8 − 3/8 × log23/8 = 0.918 cao điểm vừa phải 푣 = −2/3 × log22/3 − 1/3 × log21/3 = 0.918 vắng ( ù ) = 2/14 × 1 + 9/14 × 0.918 + 3/14 × 0.918 = 0.93 1+,1- 6+,3- 2+,1- ị 푡ℎươ푛𝑔 = −0/2 × log20/2 − 2/2 × log22/2 = 0 ệ푡 ỏ𝑖 = −0/1 × log20/1 − 1/1 × log21/1 = 0 Sức khỏe 푡ố푡 = −9/11 × log29/11 − 2/11 × log22/11 = 0.684 (푆ứ ℎ표ẻ) = 2/14 × 0 + 1/14 × 0 + 11/14 × 0.684 = 0.537 mệt tốt bị thương mỏi 0+,2- 0+,1- 9+,2- 35
  36. Chọn thuộc tính quyết định Tuyết băng ẩm khơ khơng 2+,1- 7+,1- Dừng Tiếp tục chọn thuộc tính để phân chia 36
  37. Chọn thuộc tính quyết định Chọn thuộc tính cho nhánh ế푡 = ẩ . Thời tiết Mùa Sức khỏe sương vắng vừa phải tốt nắng mù 2+,0- 0+,1- 1+,1- 1+,0- 2+,1- 푣ắ푛𝑔 = 1 푡ố푡 = 0.918 푛ắ푛𝑔 = 0 푣 = 0 (SK) = 3/3 × 0.918 푠 = 0 Mùa = 2/3 × 1 + 1/3 × 0 = 0.918 (Thời tiết) = 0 = 0.667 37
  38. Chọn thuộc tính quyết định Chọn thuộc tính cho nhánh ế푡 = ℎơ. Thời tiết Mùa Sức khỏe giĩ nắng sương mù cao điểm vắng vừa phải bị thương tốt 2+,0- 3+,1- 2+,0- 1+,0- 5+,1- 1+,0- 0+,1- 7+,0- đ 0 푡ố푡 = 0 𝑔𝑖ĩ = 0 = = 0.650 = 0 푛ắ푛𝑔 = 0.811 푣ắ푛𝑔 ị 푡ℎươ푛𝑔 = 0 (푆퐾) = 0 푠 = 0 푣 (Thời tiết) ( ù ) = 6/8 ∗ 0.650 = 0.488 = 4/8 × 0.811 = 0.401 38
  39. Ví dụ Tuyết ẩm băng khơ Thời tiết khơng Sức khỏe nắng sương bị thương tốt mù cĩ khơng khơng cĩ 39
  40. Độ lợi thơng tin (Information Gain) Độ lợi thơng tin của một thuộc tính trên tập dữ liệu được tính theo cơng thức: IG A, D = H D − AE A Thuộc tính cĩ độ lợi thơng tin cao nhất được chọn làm thuộc tính quyết định. Độ lợi thơng tin cĩ xu hướng thiên vị cho các thuộc tính cĩ nhiều giá trị nên cần chuẩn hĩa độ đo. IG(A, D) IGRatio A, D = SplitInfo(A, D) 푣 Count( 푗) Count( 푗) SplitInfo A, D = − ෍ log2 j=1 Count(D) Count(D) 40
  41. Chỉ mục Gini Chỉ mục Gini cho tập dữ liệu Gini D = 1 − ෍ 2(c) c∈ Chỉ mục Gini cho thuộc tính trên tập dữ liệu : 푣 Count( 푗) Gini A, D = ෍ Gini( j) j=1 Count(D) Thuộc tính tốt nhất là thuộc tính cĩ Gini nhỏ nhất 41
  42. Tri thức dạng luật Tri thức được biểu diễn dưới dạng luật: IF Điều kiện 1  Điều kiện 2 THEN Kết luận Dễ hiểu với con người, được sử dụng chủ yếu trong các hệ chuyên gia Rút luật từ cây quyết định: đi từ nút gốc đến nút lá, lấy các phép kiểm tra làm tiền đề và phân loại của nút lá làm kết quả 42
  43. Tri thức dạng luật 퐹 ế푡 = ẩ ℎờ𝑖 푡𝑖ế푡 = 푛ắ푛𝑔 ượ푡 푡 ế푡 = ĩ. Tuyết 퐹 ế푡 = ẩ ℎờ𝑖 푡𝑖ế푡 = 푠ươ푛𝑔 ù ượ푡 푡 ế푡 = ĩ. ẩm băng khơ 퐹 ế푡 = ă푛𝑔 ượ푡 푡 ế푡 = ℎơ푛𝑔. Thời tiết Sức khỏe 퐹 ế푡 = ℎơ 푆ứ ℎỏ푒 = ị 푡ℎươ푛𝑔 ượ푡 푡 ế푡 = khơng ℎơ푛𝑔. nắng sương mù tốt bị thương 퐹 ế푡 = ℎơ 푆ứ ℎỏ푒 = 푡ố푡 ượ푡 푡 ế푡 = ĩ cĩ khơng khơng cĩ 43
  44. Nội dung chính Máy học là gì? Phương pháp Nạve Bayes Phương pháp ID3 Phương pháp ILA 44
  45. Phương pháp ILA ILA (Inductive Learning Algorithm) phát minh bởi M. Tolun, 1998 Là một thuật tốn xác định các luật IF THEN trực tiếp từ tập dữ liệu huấn luyện (học) Ý tưởng: ◦ Chia tập dữ liệu huấn luyện thành các bảng con theo từng giá trị của thuộc tính phân lớp. ◦ So sánh giá trị của các thuộc tính giữa các bảng con để chọn ra sự kết hợp các thuộc tính cĩ khả năng phân biệt lớp này với lớp kia. 45
  46. Phương pháp ILA Chia tập dữ liệu thành 푛 bảng con, với 푛 là số giá trị của thuộc tính phân lớp Bước 1: Khởi tạo số lượng thuộc tính kết hợp = 1 Bước 2: Xét từng bảng con, tạo danh sách các kết hợp gồm thuộc tính Bước 3: Với mỗi kết hợp thuộc tính trong danh sách ở bước 2 ◦ Đếm số lần xuất hiện các giá trị thuộc tính ở các dịng chưa đánh dấu ở bảng con đang xét, nhưng giá trị khơng được xuất hiện ở những bảng con khác Bước 4: Chọn kết hợp đầu tiên cĩ số lần xuất hiện các giá trị thuộc tính nhiều nhất, tạm gọi là max − 표 𝑖푛 푡𝑖표푛. Bước 5: Nếu max-combination = 0 thì = + 1, quay lại bước 2. Bước 6: Trong bảng con đang xét, đánh dấu các dịng cĩ xuất hiện giá trị của max − 표 𝑖푛 푡𝑖표푛 Bước 7: Tạo luật IF AND(thuộc tính = giá trị) (thuộc max − 표 𝑖푛 푡𝑖표푛) THEN giá trị thuộc tính lớp của bảng con Bước 8: ◦ Nếu tất cả các dịng của bảng con đều được đánh dấu chuyển sang bảng con tiếp theo và quay lại bước 1 ◦ Ngược lại thì quay lại bước 3. 46
  47. Ví dụ Mẫu Kích cỡ Màu sắc Hình dáng Quyết định 1 Vừa Xanh dương Hộp Mua 2 Nhỏ Đỏ Nĩn Khơng mua 3 Nhỏ Đỏ Cầu Mua 4 Lớn Đỏ Nĩn Khơng mua 5 Lớn Xanh lá Trụ Mua 6 Lớn Đỏ Trụ Khơng mua 7 Lớn Xanh lá Cầu Mua 47
  48. Ví dụ Chia tập dữ liệu thành 푛 bảng con, với 푛 là số giá trị của thuộc tính phân lớp STT Kích cỡ Màu sắc Hình dáng Quyết định 1 Vừa Xanh dương Hộp Mua Quyết định = mua 3 Nhỏ Đỏ Cầu Mua 5 Lớn Xanh lá Trụ Mua 7 Lớn Xanh lá Cầu Mua STT Kích cỡ Màu sắc Hình dáng Quyết định 2 Nhỏ Đỏ Nĩn Khơng mua Quyết định = khơng mua 4 Lớn Đỏ Nĩn Khơng mua 6 Lớn Đỏ Trụ Khơng mua 48
  49. Ví dụ Xét bảng con 1, khởi tạo = 1 (thuộc tính) STT Kích cỡ Màu sắc Hình dáng Quyết định ◦ Tạo danh sách các kết hợp gồm k thuộc tính: 1 Vừa Xanh dương Hộp Mua ◦ Kích cỡ 3 Nhỏ Đỏ Cầu Mua ◦ Màu sắc 5 Lớn Xanh lá Trụ Mua ◦ Hình dáng 7 Lớn Xanh lá Cầu Mua ◦ Tìm các giá trị xuất hiện ở bảng này mà khơng xuất hiện ở bảng kia STT Kích cỡ Màu sắc Hình dáng Quyết định ◦ Đếm số lần xuất hiện 2 Nhỏ Đỏ Nĩn Khơng mua 4 Lớn Đỏ Nĩn Khơng mua 6 Lớn Đỏ Trụ Khơng mua 49
  50. Ví dụ Chọn kết hợp thuộc tính đầu tiên cĩ số lần xuất hiện nhiều nhất và tạo luật ◦ IF (Màu sắc = Xanh lá) THEN Quyết định = Mua Đánh dấu các dịng đã xét. STT Kích cỡ Màu sắc Hình dáng Quyết định 1 Vừa Xanh dương Hộp Mua 3 Nhỏ Đỏ Cầu Mua 5 Lớn Xanh lá Trụ Mua 7 Lớn Xanh lá Cầu Mua 50
  51. Ví dụ Xét các dịng chưa được đánh dấu ◦ IF (Màu sắc = Xanh lá) THEN Quyết định = Mua ◦ IF (Kích cỡ = Vừa) THEN Quyết định = Mua STT Kích cỡ Màu sắc Hình dáng Quyết định 1 Vừa Xanh dương Hộp Mua 3 Nhỏ Đỏ Cầu Mua 5 Lớn Xanh lá Trụ Mua 7 Lớn Xanh lá Cầu Mua 51
  52. Ví dụ Xét các dịng chưa được đánh dấu ◦ IF (Màu sắc = Xanh lá) THEN Quyết định = Mua ◦ IF (Kích cỡ = Vừa) THEN Quyết định = Mua ◦ IF (Hình dáng = Cầu) THEN Quyết định = Mua STT Kích cỡ Màu sắc Hình dáng Quyết định 1 Vừa Xanh dương Hộp Mua 3 Nhỏ Đỏ Cầu Mua 5 Lớn Xanh lá Trụ Mua 7 Lớn Xanh lá Cầu Mua 52
  53. Ví dụ Hồn tất bảng con đầu tiên ◦ IF (Màu sắc = Xanh lá) THEN Quyết định = Mua ◦ IF (Kích cỡ = Vừa) THEN Quyết định = Mua ◦ IF (Hình dáng = Cầu) THEN Quyết định = Mua STT Kích cỡ Màu sắc Hình dáng Quyết định 1 Vừa Xanh dương Hộp Mua 3 Nhỏ Đỏ Cầu Mua 5 Lớn Xanh lá Trụ Mua 7 Lớn Xanh lá Cầu Mua 53
  54. Ví dụ Thực hiện cho bảng con tiếp theo STT Kích cỡ Màu sắc Hình dáng Quyết định 1 Vừa Xanh dương Hộp Mua 3 Nhỏ Đỏ Cầu Mua 5 Lớn Xanh lá Trụ Mua 7 Lớn Xanh lá Cầu Mua STT Kích cỡ Màu sắc Hình dáng Quyết định 2 Nhỏ Đỏ Nĩn Khơng mua 4 Lớn Đỏ Nĩn Khơng mua 6 Lớn Đỏ Trụ Khơng mua 54
  55. Ví dụ ◦ IF (Hình dáng = Nĩn) THEN Quyết định = Khơng mua STT Kích cỡ Màu sắc Hình dáng Quyết định 2 Nhỏ Đỏ Nĩn Khơng mua 4 Lớn Đỏ Nĩn Khơng mua 6 Lớn Đỏ Trụ Khơng mua 55
  56. Ví dụ Tăng số thuộc tính kết hợp = 2 ◦ Kích cỡ & Màu sắc ◦ Kích cỡ & Hình dáng ◦ Màu sắc & HÌnh dáng Luật thu được: ◦ IF (Hình dáng = Nĩn) THEN Quyết định = Khơng mua ◦ IF (Kích cỡ = Lớn AND Màu sắc = đỏ) THEN Quyết định = Khơng mua STT Kích cỡ Màu sắc Hình dáng Quyết định 2 Nhỏ Đỏ Nĩn Khơng mua 4 Lớn Đỏ Nĩn Khơng mua 6 Lớn Đỏ Trụ Khơng mua 56
  57. Ví dụ Tất cả các dịng đều được đánh dấu. Khơng cịn bảng con Dừng thuật tốn ◦ IF (Màu sắc = Xanh lá) THEN Quyết định = Mua ◦ IF (Kích cỡ = Vừa) THEN Quyết định = Mua ◦ IF (Hình dáng = Cầu) THEN Quyết định = Mua ◦ IF (Hình dáng = Nĩn) THEN Quyết định = Khơng mua ◦ IF (Kích cỡ = Lớn AND Màu sắc = đỏ) THEN Quyết định = Khơng mua STT Kích cỡ Màu sắc Hình dáng Quyết định 2 Nhỏ Đỏ Nĩn Khơng mua 4 Lớn Đỏ Nĩn Khơng mua 6 Lớn Đỏ Trụ Khơng mua 57
  58. Tài liệu tham khảo Cơ sở Trí tuệ Nhân tạo, Lê Hồi Bắc, Tơ Hồi Việt, NXB Khoa học & Kỹ thuật. Slide bài giảng Trí tuệ nhân tạo, GV. Tơ Hồi Việt, GV. Lê Ngọc Thành, Khoa CNTT, ĐH. KHTN TP.HCM Artificial Intelligence: A Modern Approach, 3rd Edition, S. Russel and P. Norvig, Pearson Education Inc., 2010 Techniques in Artificial Intelligence (SMA 5504) , MIT OpenCourseWare, Massachusetts Institute of Technology Artificial Intelligence: Principles and Techniques, Stanford courses, Autumn 2015. Machine Learning, Stanford course trên trang www.coursera.org 58