›
›

Bài giảng Trí tuệ nhân tạo - Cây quyết định (ID3), học quy nạp (ILA)

pdf 28 trang hapham 1240
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Trí tuệ nhân tạo - Cây quyết định (ID3), học quy nạp (ILA)", để 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:

  • pdfbai_giang_tri_tue_nhan_tao_cay_quyet_dinh_id3_hoc_quy_nap_il.pdf

Nội dung text: Bài giảng Trí tuệ nhân tạo - Cây quyết định (ID3), học quy nạp (ILA)

  1. CÂY QUYT ðNH (ID3) HC QUI NP (ILA) TRÍ TU NHÂN TO
  2. Ni dung trình bày 2  Cây quyt đnh  Hc cây quyt đnh – Thut tốn ID3  Biu din tri thc bng lut  Rút lut t cây quyt đnh  Thut tốn hc quy np
  3. Cây quyt đnh 3 Cây quyt đnh biu din: • Mi nút trong kim tra mt thuc tính • Mi nhánh tương ng vi giá tr thuc tính • Mi nút lá đưc gán mt phân lp Nguyên lý Occam: nhng cây đơn gin là nhng cây quyt đnh tt hơn
  4. Thut tốn hc ID3 4 ðưc phát trin đng thi bi Quinlan trong AI và Breiman, Friedman, Olsen và Stone trong thng kê Lp: 1. Chn A  thuc tính quyt đnh “tt nht” cho nút k tip 2. Gán A là thuc tính quyt đnh cho nút 3. Vi mi giá tr ca A, to nhánh con mi ca nút 4. Phân loi các mu hun luyn cho các nút lá 5. Nu các mu hun luyn đưc phân loi hồn tồn thì NGƯNG, Ngưc li, lp vi các nút lá mi. Thuc tính tt nht là gì?
  5. Entropy 5  S là tp các mu hun luyn  p là t l các mu dương trong S  H ≡ – p.log 2p – (1 – p).log 2(1 – p)
  6. Thut tốn hc ID3 6 ðưc phát trin đng thi bi Quinlan trong AI và Breiman, Friedman, Olsen và Stone trong thng kê Lp: 1. Chn A  thuc tính quyt đnh “tt nht” cho nút k tip 2. Gán A là thuc tính quyt đnh cho nút 3. Vi mi giá tr ca A, to nhánh con mi ca nút 4. Phân loi các mu hun luyn cho các nút lá 5. Nu các mu hun luyn đưc phân loi hồn tồn thì NGƯNG, Ngưc li, lp vi các nút lá mi. Thuc tính tt nht s làm ti thiu hố entropy trung bình ca d liu trong các nút con
  7. Ví d Hun luyn 7
  8. Ví d (tt) 8 Outlook Rain Sunny Overcast 3+,2 4+,0 2+,3 H = 0.971 H = 0 H = 0.971 Hrain = – 3/5.log 23/5 – 2/5.log 22/5 = 0.442 + 0.529 = 0.971 Hovercast = – 4/4.log 24/4 – 0/4.log 20/4 = 0 + 0 = 0 Hsunny = – 2/5.log 22/5 – 3/5.log 23/5 = 0.529 + 0.442 = 0.971 AE(ðHLTB) = ∑ pv H Av v∈Value( A)
  9. Ví d (tt) 9 Outlook Temparature Rain Sunny Hot Cool Overcast Mild 3+,2 4+,0 2+,3 2+,2 4+,2 3+,1 H = 0.971 H = 0 H = 0.971 H = 1 H = 0.918 H = 0.811 AE = 5/14*.971 + 4/14*0 + 5/14*.971 AE = 4/14*1 + 6/14*.918 + 4/14*.811 = 0.694 = 0.911
  10. Ví d (tt) 10 Humidity Wind High Normal Weak Strong 3+,4 6+,1 6+,2 3+,3 H = 0.985 H = 0.592 H = 0.811 H = 1 AE = 7/14*.985 + 7/14*.592 AE = 8/14*.811 + 6/14*1 = 0.788 = 0.892 Chn Outlook là thuc tính quyt đnh
  11. Ví d (tt) 11 Outlook Rain Sunny Overcast 3+,2 Yes 2+,3 Chn thuc tính gì tip theo? Tip tc thc hin vic phân chia
  12. Ví d (tt) 12 Outlook Rain Sunny Overcast 3+,2 Yes 2+,3 AE (Rain, Temperature) = 2/5*1 + 3/5*.918 = 0.951 AE (Rain, Humidity) = 2/5*1 + 3/5*.918 = 0.951 AE (Rain, Wind) = 2/5*0 + 3/5*0 = 0
  13. Ví d (tt) 13 Outlook Rain Sunny Overcast 3+,2 Yes 2+,3 AE (Sunny, Temperature) = 2/5*0 + 2/5*1 + 1/5*0= 0.4 AE (Sunny, Humidity) = 2/5*0 + 3/5*0 = 0 AE (Sunny, Wind) = 2/5*1 + 3/5*.918 = 0.951
  14. Ví d (tt) 14 Outlook Rain Sunny Overcast Wind Yes Humidity Weak Strong Normal High Yes Yes No No
  15. Tri thc dng lut 15  Tri thc đưc biu din dưi dng lut: IF ðiu kin 1 ^ ðiu kin 2 THEN Kt lun  D hiu vi con ngưi, đưc s dng ch yu trong các h chuyên gia  Rút lut t cây quyt đnh: đi t nút gc đn nút lá, ly các phép th làm tin đ và phân loi ca nút lá làm kt qu
  16. Rút lut t cây quyt đnh 16  IF Outlook = Overcast THEN Yes Outlook  IF Outlook = Rain AND Rain Sunny Wind=Weak THEN Yes Overcast  IF Outlook = Rain AND Wind Yes Humidity Wind=Strong THEN No Weak Strong Normal High  IF Outlook = Sunny AND Humidity=Normal THEN Yes Yes Yes No No  IF Outlook = Sunny AND Humidity=High THEN No
  17. Thut gii Hc Quy np (ILA) 17 Dùng đ rút các lut phân lp t tp mu d liu: 1. Chia tp mu thành các tp con ng vi thuc tính quyt đnh 2. Vi mi bng con 3. Vi mi t hp thuc tính cĩ th (bt đu vi s lưng = 1) 4. Tìm các giá tr ch xut hin bng con này mà khơng xut hin các bng con khác 5. (Nu cĩ nhiu t hp thì chn t hp cĩ s lưng mu tin nhiu nht) 6. S dng t hp thuc tính, giá tr va tìm đưc đ to lut 7. ðánh du các dịng đã xét 8. Nu cịn dịng chưa xét, lp li bưc 3 9. Lp li bưc 2 vi các bng con
  18. Ví d ILA 18 STT Kích c Màu sc Hình dáng Quyt đnh 1 Va Xanh dương Hp Mua 2 Nh ð Nĩn Khơng mua 3 Nh ð Cu Mua 4 Ln ð Nĩn Khơng mua 5 Ln Xanh lá Tr Mua 6 Ln ð Tr Khơng mua 7 Ln Xanh lá Cu Mua
  19. Ví d ILA (tt) 19 STT Kích c Màu sc Hình dáng Quyt đnh 1 Va Xanh dương Hp Mua 3 Nh ð Cu Mua 5 Ln Xanh lá Tr Mua 7 Ln Xanh lá Cu Mua STT Kích c Màu sc Hình dáng Quyt đnh 2 Nh ð Nĩn Khơng mua 4 Ln ð Nĩn Khơng mua 6 Ln ð Tr Khơng mua
  20. Ví d ILA (tt) 20 STT Kích c Màu sc Hình dáng Quyt đnh 1 Va Xanh dương Hp Mua 3 Nh ð Cu Mua 5 Ln Xanh lá Tr Mua 7 Ln Xanh lá Cu Mua STT Kích c Màu sc Hình dáng Quyt đnh 2 NhChn thuc ð tính Màu sc Nĩn Khơng mua vi giá tr Xanh lá 4 Ln ð Nĩn Khơng mua 6 Ln ð Tr Khơng mua
  21. Ví d ILA (tt) 21 STT Kích c Màu sc Hình dáng Quyt đnh 1 Va Xanh dương Hp Mua 3 Nh ð Cu Mua IF Màu sc = Xanh lá THEN Quyt đnh = Mua STT Kích c Màu sc Hình dáng Quyt đnh 2 Nh ð Nĩn Khơng mua 4 Ln ð Nĩn Khơng mua 6 Ln ð Tr Khơng mua
  22. Ví d ILA (tt) 22 STT Kích c Màu sc Hình dáng Quyt đnh 3 Nh ð Cu Mua IF Màu sc = Xanh lá THEN Quyt đnh = Mua IF Kích c = Va THEN Quyt đnh = Mua STT Kích c Màu sc Hình dáng Quyt đnh 2 Nh ð Nĩn Khơng mua 4 Ln ð Nĩn Khơng mua 6 Ln ð Tr Khơng mua
  23. Ví d ILA (tt) 23 IF Màu sc = Xanh lá THEN Quyt đnh = Mua IF Kích c = Va THEN Quyt đnh = Mua IF Hình dáng= Cu THEN Quyt đnh = Mua STT Kích c Màu sc Hình dáng Quyt đnh 2 Nh ð Nĩn Khơng mua 4 Ln ð Nĩn Khơng mua 6 Ln ð Tr Khơng mua
  24. Ví d ILA (tt) 24 STT Kích c Màu sc Hình dáng Quyt đnh 1 Va Xanh dương Hp Mua 3 Nh ð Cu Mua 5 Ln Xanh lá Tr Mua 7 Ln Xanh lá Cu Mua STT Kích c Màu sc Hình dáng Quyt đnh 2 Nh ð Nĩn Khơng mua 4 Ln ð Nĩn Khơng mua 6 Ln ð Tr Khơng mua IF Hình dáng = Nĩn THEN Quyt đnh = Khơng mua
  25. Ví d ILA (tt) 25 STT Kích c Màu sc Hình dáng Quyt đnh 1 Va Xanh dương Hp Mua 3 Nh ð Cu Mua 5 Ln Xanh lá Tr Mua 7 Ln Xanh lá Cu Mua STT Kích c Màu sc Hình dáng Quyt đnh 6 Ln ð Tr Khơng mua IF Hình dáng = Nĩn THEN Quyt đnh = Khơng mua
  26. Ví d ILA (tt) 26 STT Kích c Màu sc Hình dáng Quyt đnh 1 Va Xanh dương Hp Mua 3 Nh ð Cu Mua 5 Ln Xanh lá Tr Mua 7 Ln Xanh lá Cu Mua STT Kích c Màu sc Hình dáng Quyt đnh 6 Ln ð Tr Khơng mua IF Hình dáng = Nĩn THEN Quyt đnh = Khơng mua IF Kích c = Ln AND Màu sc = ð THEN Quyt đnh = Khơng mua
  27. ðiu cn nm 27  Nm đưc khái nim cây quyt đnh  Hiu và vn dng thut tốn ID3  Hiu và vn dng thut tốn hc quy np
  28. Thc mc 28