Đồ án Trí tuệ nhân tạo - Học máy

6 Rain Cool Normal Strong No 7 Overcast Cool Normal Strong Yes 8 Sunny Mild High Weak No 9 Sunny Cool Normal Weak Yes 10 Rain Mild Normal Weak Yes 11 Sunny Mild Normal Strong Yes 12 Overcast Mild High Strong Yes 13 Overcast Hot Normal Weak Yes 14 Rain Mild High Strong No Sau đó, để giải quyết bài toán, người ta đã đưa ra một mô hình cây quyết định. Kết luận thứ nhất: nếu trời nhiều mây, người ta luôn luôn chơi tennis. Tiếp theo, ta lại chia nhóm trời nắng thành hai nhóm con. Ta thấy rằng khách hàng không muốn chơi golf nếu độ ẩm cao. Cuối cùng, ta chia nhóm trời có gió thành hai và thấy rằng khách hàng sẽ không chơi tennis nếu trời nhiều gió. Và đây là lời giải ngắn gọn cho bài toán mô tả bởi cây phân loại. Người quản lý phần lớn cho nhân viên nghỉ vào những ngày trời nắng và ẩm, hoặc những ngày gió mạnh. Vì hầu như sẽ chẳng có ai chơi trong những ngày đó. Vào những hôm khác, khi nhiều người sẽ đến chơi tennis, anh ta có thể thuê thêm nhân viên thời vụ để phụ giúp công việc. Kết luận là cây quyết định giúp ta biến một biểu diễn dữ liệu phức tạp thành một cấu trúc đơn giản hơn rất nhiều. Các kiểu cây quyết định Cây quyết định còn có hai tên khác: Cây hồi quy (Regression tree): ước lượng các hàm có giá trị là số thực thay vì được sử dụng cho các nhiệm vụ phân loại. (ví dụ: ước tính giá một ngôi nhà hoặc khoảng thời gian một bệnh nhân nằm viện) Cây phân loại (Classification tree): là một biến phân loại như: giới tính (nam hay nữ), kết quả của một trận đấu (thắng hay thua). Ưu điểm cây quyết định Cây quyết định dễ hiểu. Người ta có thể hiểu mô hình cây quyết định sau khi được giải thích ngắn. Việc chuẩn bị dữ liệu cho một cây quyết định là cơ bản hoặc không cần thiết. Các kỹ thuật khác thường đòi hỏi chuẩn hóa dữ liệu, cần tạo các biến phụ (dummy variable) và loại bỏ các giá trị rỗng. Cây quyết định có thể xử lý cả dữ liệu có giá trị bằng số và dữ liệu có giá trị là tên thể loại. Các kỹ thuật khác thường chuyên để phân tích các bộ dữ liệu chỉ gồm một loại biến. Chẳng hạn, các luật quan hệ chỉ có thể dùng cho các biến tên, trong khi mạng nơ-ron chỉ có thể dùng cho các biến có giá trị bằng số. Cây quyết định là một mô hình hộp trắng. Nếu có thể quan sát một tình huống cho trước trong một mô hình, thì có thể dễ dàng giải thích điều kiện đó bằng logic Boolean. Mạng nơ-ron là một ví dụ về mô hình hộp đen, do lời giải thích cho kết quả quá phức tạp để có thể hiểu được. Có thể thẩm định một mô hình bằng các kiểm tra thống kê. Điều này làm cho ta có thể tin tưởng vào mô hình. Cây quyết định có thể xử lý tốt một lượng dữ liệu lớn trong thời gian ngắn. Có thể dùng máy tính cá nhân để phân tích các lượng dữ liệu lớn trong một thời gian đủ ngắn để cho phép các nhà chiến lược đưa ra quyết định dựa trên phân tích của cây quyết định. Phần II: Thuật toán ID3 1. Thuật toán: Thuật toán ID3 do Ross Quinlan đề xuất dùng để xây dựng những cây quyết định thỏa các tính chất trên. Thuật toán tuân theo nguyên tắc dao cạo Occam để xây dựng những cây quyết định bằng cách ở mỗi bước kiểm tra, cố gắng chọn thuộc tính (nút nhánh) đơn giản nhất. Để xác định độ đơn giản của thuộc tính, ID3 sử dụng giá trị độ đo là entropy thông tin (độ hỗn loạn thông tin). Với một thuộc tính cho trước, một tập dữ liệu được chia thành n tập con với các tỷ lệ Pi tương ứng (ví dụ, với thuộc tính Target, tập dữ liệu huấn luyện được chia thành 2 tập con Yes với Po = 9/14 và tập con No với P;=5/14). Khi đó, entropy của tập dữ liệu trên thuộc tính được chọn là: n H Ví dụ, entropy của tập dữ liệu tennis theo thuộc tính kết quả là: H = - 9/14 * log29/14 - 5/14 * log25/14 = 0,94 Entropy đo độ hỗn loạn của một tập. Entropy càng cao thì độ hỗn loạn của tập đó càng cao. Tập dữ liệu là hoàn toàn đồng nhất khi entropy = 0. Và trong trường hợp tập dữ liệu có 2 lớp, tập dữ liệu hoàn toàn hỗn loạn sẽ có entropy = 1. Thuật toán ID3: Bắt đầu với nút gốc, 1. Chọn A ß thuộc tính quyết định "tốt nhất" cho nút kế tiếp Gán A là thuộc tính quyết định cho nút Với mỗi giá trị của 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 nhánh Nếu các mẫu huấn luyện trong một nhánh được phân loại hoàn toàn (đồng nhất một loại) thì NGƯNG, ta được một nút lá. Ngược lại, lặp với các nút nhánh mới. Thuộc tính tốt nhất ở đây là thuộc tính có entropy trung bình thấp nhất theo thuộc tính kết quả. Entropy trung bình của một thuộc tính bằng trung bình theo tỉ lệ của entropy các nhánh: 2. Ví dụ: Áp dụng thuật toán ID3 cho bài toán học chơi tennis: * Lưu ý: Các số khoan tròn của tất cả hình bên dưới đều có thuộc tính Target là Yes, ngược lại là No. Ÿ Lặp lần 1: Xét lần lượt các thuộc tính Outlook: # Outlook Temperature Humidity Wind Target 1 Sunny Hot High Weak No 2 Sunny Hot High Strong No 3 Overcast Hot High Weak Yes 4 Rain Mild High Weak Yes 5 Rain Cool Normal Weak Yes 6 Rain Cool Normal Strong No 7 Overcast Cool Normal Strong Yes 8 Sunny Mild High Weak No 9 Sunny Cool Normal Weak Yes 10 Rain Mild Normal Weak Yes 11 Sunny Mild Normal Strong Yes 12 Overcast Mild High Strong Yes 13 Overcast Hot Normal Weak Yes 14 Rain Mild High Strong No Outlook Rain Overcast Sunny 6 10 5 14 4 3 7 12 13 1 2 11 8 9 HRain = - 3/5 * log23/5 - 2/5 * log22/5 = 0,97 HOvercast = - 4/4 * log24/4 - 0/4 * log20/4 = 0 HSunny = - 2/5 * log22/5 - 3/5 * log23/5 = 0,97 AE (Outlook) = 5/14 * 0,97 + 4/14 * 0 + 5/14 * 0,97 = 0,693 Temperature: # Outlook Temperature Humidity Wind Target 1 Sunny Hot High Weak No 2 Sunny Hot High Strong No 3 Overcast Hot High Weak Yes 4 Rain Mild High Weak Yes 5 Rain Cool Normal Weak Yes 6 Rain Cool Normal Strong No 7 Overcast Cool Normal Strong Yes 8 Sunny Mild High Weak No 9 Sunny Cool Normal Weak Yes 10 Rain Mild Normal Weak Yes 11 Sunny Mild Normal Strong Yes 12 Overcast Mild High Strong Yes 13 Overcast Hot Normal Weak Yes 14 Rain Mild High Strong No Temperature Hot Mid Cool 13 3 4 5 10 11 12 9 7 1 2 8 14 6 HHot = - 2/4 * log22/4 - 2/4 * log22/4 = 1 HMid = - 4/6 * log24/6 - 2/6 * log22/6 = 0,918 HCool = - 3/4 * log23/4 - 1/4 * log21/4 = 0,811 AE (Temperature) = 4/14 * 1 + 6/14 * 0,918 + 4/14 * 0,811 = 0,911 Humidity: # Outlook Temperature Humidity Wind Target 1 Sunny Hot High Weak No 2 Sunny Hot High Strong No 3 Overcast Hot High Weak Yes 4 Rain Mild High Weak Yes 5 Rain Cool Normal Weak Yes 6 Rain Cool Normal Strong No 7 Overcast Cool Normal Strong Yes 8 Sunny Mild High Weak No 9 Sunny Cool Normal Weak Yes 10 Rain Mild Normal Weak Yes 11 Sunny Mild Normal Strong Yes 12 Overcast Mild High Strong Yes 13 Overcast Hot Normal Weak Yes 14 Rain Mild High Strong No HHigh = - 3/7 * log23/7 - 4/7 * log24/7 = 0,985 HNormal = - 6/7 * log26/7 - 1/7 * log21/7 = 0,592 AE (Humidity) = 7/14 * 0,985 + 7/14 * 0,592 = 0,79 Humidity High Normal 13 3 4 5 10 11 12 9 7 1 2 8 14 6 Wind: # Outlook Temperature Humidity Wind Target 1 Sunny Hot High Weak No 2 Sunny Hot High Strong No 3 Overcast Hot High Weak Yes 4 Rain Mild High Weak Yes 5 Rain Cool Normal Weak Yes 6 Rain Cool Normal Strong No 7 Overcast Cool Normal Strong Yes 8 Sunny Mild High Weak No 9 Sunny Cool Normal Weak Yes 10 Rain Mild Normal Weak Yes 11 Sunny Mild Normal Strong Yes 12 Overcast Mild High Strong Yes 13 Overcast Hot Normal Weak Yes 14 Rain Mild High Strong No Wind Weak Strong 13 3 4 5 10 11 12 9 7 1 2 8 14 6 Hweak = - 2/8 * log22/8 - 6/8 * log26/8 = 0,81 HStrong = - 3/6 * log23/6 - 3/6 * log23/6 = 1 AE (Wind) = 8/14 * 0,81 + 6/14 * 1 = 0,89 So sánh ta thấy thuộc tính Outlook có entropy trung bình thấp nhất nên ta chọn thuộc tính này làm gốc. Lặp lần 2: Xét nhánh Rain Xét các thuộc tính Temperature # Outlook Temperature Humidity Wind Target 4 Rain Mild High Weak Yes 5 Rain Cool Normal Weak Yes 6 Rain Cool Normal Strong No 10 Rain Mild Normal Weak Yes 14 Rain Mild High Strong No Temperature Hot Cool 4 5 10 14 6 Entropy trung bình: HMid = - 2/3 * log22/3 - 1/3 * log21/3 = 0,918 HCool = - 1/2 * log21/2 - 1/2 * log21/2 = 1 AE (Temperature) = 3/5 * 0,918 + 2/5 * 1 = 0,8308 Xét các thuộc tính Humidity # Outlook Temperature Humidity Wind Target 4 Rain Mild High Weak Yes 5 Rain Cool Normal Weak Yes 6 Rain Cool Normal Strong No 10 Rain Mild Normal Weak Yes 14 Rain Mild High Strong No Humidity High Normal 4 5 10 14 6 Entropy trung bình: HHigh = - 1/2 * log21/2 - 1/2 * log21/2 = 1 HNormal = - 2/3 * log22/3 - 1/3 * log21/3 = 0,918 AE (Humidity) = 2/5 * 1 + 3/5 * 0,918 = 0,9508 Xét các thuộc tính Wind: # Outlook Temperature Humidity Wind Target 4 Rain Mild High Weak Yes 5 Rain Cool Normal Weak Yes 6 Rain Cool Normal Strong No 10 Rain Mild Normal Weak Yes 14 Rain Mild High Strong No Wind Weak Strong 4 5 10 14 6 Entropy trung bình: HHigh = - 3/3 * log23/3 – 0/3 * log20/3 = 0 HNormal = - 0/2 * log20/2 – 2/2 * log22/2 = 0 AE (Humidity) = 0 Thuộc tính Wind có entropy trang bình thấp nhất nên chọn làm nút nhánh. Lặp lần 3: Xét nhánh Sunny Xét các thuộc tính Temperature # Outlook Temperature Humidity Wind Target 1 Sunny Hot High Weak No 2 Sunny Hot High Strong No 8 Sunny Mild High Weak No 9 Sunny Cool Normal Weak Yes 11 Sunny Mild Normal Strong Yes Temperature Mid Hot Cool 9 11 1 8 2 HMid = - 1/2 * log21/2 – 1/2 * log21/2 = 1 HHot = - 0/2 * log20/2 – 2/2 * log20/2 = 0 HCool = - 1 * log21 – 0 * log20 = 0 AE (Temperature) = 2/5 * 1 + 0 + 0 = 0,4 Xét các thuộc tính Humidity # Outlook Temperature Humidity Wind Target 1 Sunny Hot High Weak No 2 Sunny Hot High Strong No 8 Sunny Mild High Weak No 9 Sunny Cool Normal Weak Yes 11 Sunny Mild Normal Strong Yes Humidity High Normal 9 8 11 1 2 Entropy trung bình: HHigh = - 0/3 * log20/3 – 3/3 * log23/3 = 0 HNormal = - 2/2 * log22/2 – 0 = 0 AE (Humidity) = 0 Thuộc tính Humidity có entropy trung bình thấp nhất nên chọn làm nút nhánh. à Cây quyết định kết quả: • Sau khi xây dựng cây, ta có thể rút ra các luật tương ứng bằng cách duyệt các đường đi trên cây từ nút gốc đến nút lá, mỗi đường đi ứng với một luật: L1: Nếu Outlook = Overcast thì chơi tennis. L2: Nếu Outlook = Rain và Wind = Weak thì chơi tennis. L3: Nếu Outlook = Rain và Wind = Strong thì không chơi tennis. L4: Nếu Outlook = Sunny và Hub = High thì không chơi tennis. L5: Nếu Outlook = Sunny và Hub = Normal thì chơi tennis. Lưu ý: Một phiên bản khác của thuật toán ID3 sử dụng Informatic Gain thay cho entropy để chọn thuộc tính quyết định. Công thức tính Informatic Gain như sau: Gain(A) = Entropy(S) – Entropy(A) Trong đó: S là tập mẫu và A là một thuộc tính. Entropy(S): độ hỗn loạn của tập S. Entropy(A): độ hỗn loạn trung bình của thuộc tính A (cách tính như trên) Nguyên tắc thực hiện: tương tự trên ngoại trừ Gain lớn nhất. Phần II: Thuật toán QuinLan 1. Thuật toán: Quinlan quyết định thuộc tính phân hoạch bằng cách xây dựng các vector đặc trưng cho mỗi giá trị của từng thuộc tính dẫn xuất và thuộc tính mục tiêu. Cách tính cụ thể như sau : Với mỗi thuộc tính dẫn xuất A còn có thể sử dụng để phân hoạch, tính : VA(j) = ( T(j , r1), T(j , r2) ,…, T(j , rn) ) T(j, ri) = (tổng số phần tử trong phân hoạch có giá trị thuộc tính dẫn xuất A là j và có giá trị thuộc tính mục tiêu là ri ) / ( tổng số phần tử trong phân hoạch có giá trị thuộc tính dẫn xuất A là j ) * Trong đó:  r1, r2, … , rn là các giá trị của thuộc tính mục tiêu *  Như vậy nếu một thuộc tính A có thể nhận một trong 5 giá trị khác nhau thì nó sẽ có 5 vector đặc trưng. Một vector V(Aj ) được gọi là vector đơn vị nếu nó chỉ có duy nhất một thành phần có giá trị 1 và những thành phần khác có giá trị 0. Thuộc tính được chọn để phân hoạch là thuộc tính có nhiều vector đơn vị nhất. 2. Ví dụ: Bài toán dự đoán việc chơi tennis # Outlook Temperature Humidity Wind Target 1 Sunny Hot High Weak No 2 Sunny Hot High Strong No 3 Overcast Hot High Weak Yes 4 Rain Mild High Weak Yes 5 Rain Cool Normal Weak Yes 6 Rain Cool Normal Strong No 7 Overcast Cool Normal Strong Yes 8 Sunny Mild High Weak No 9 Sunny Cool Normal Weak Yes 10 Rain Mild Normal Weak Yes 11 Sunny Mild Normal Strong Yes 12 Overcast Mild High Strong Yes 13 Overcast Hot Normal Weak Yes 14 Rain Mild High Strong No Phân hoạch lần 1: VOutlook(Sunny) = (2/5, 3/5) VOutlook(Overcast) = (4/4, 0/4) = (1, 0) { vector đơn vị} VOutlook(Sunny) = (2/5, 3/5) VTemperature(Hot) = (2/4, 2/4) VTemperature(Mid) = (4/6, 2/6) = (2/3, 1/3) VTemperature(Cool) = (3/4, 1/4) VHumidity(High) = (3/7, 4/7) VHumidity(Normal) = (6/7, 6/7) VWind(Weak) = (3/7, 4/7) VWind(Strong) = (6/8, 2/8) = (3/4, 1/4) Ta chọn thuộc tính Outlook vì có vector đơn vị nên ta chọn làm nhánh gốc. Trong Outlook còn có thuộc tính Rain và Sunny là chứa những người chơi tennis hoặc không chơi. Vì vậy ta sẽ phân hoạch tiếp hai nhánh này. Dữ liệu còn lại là: # Outlook Temperature Humidity Wind Target 1 Sunny Hot High Weak No 2 Sunny Hot High Strong No 4 Rain Mild High Weak Yes 5 Rain Cool Normal Weak Yes 6 Rain Cool Normal Strong No 8 Sunny Mild High Weak No 9 Sunny Cool Normal Weak Yes 10 Rain Mild Normal Weak Yes 11 Sunny Mild Normal Strong Yes 14 Rain Mild High Strong No Phân hoạch lần 2: - Nhánh Sunny # Outlook Temperature Humidity Wind Target 1 Sunny Hot High Weak No 2 Sunny Hot High Strong No 8 Sunny Mild High Weak No 9 Sunny Cool Normal Weak Yes 11 Sunny Mild Normal Strong Yes VTemperature(Hot) = (0/2, 2/2) = (1, 0) { vector đơn vị} VTemperature(Mid) = (1/2, 1/2) VTemperature(Cool) = (1, 0) { vector đơn vị} VHumidity(High) = (0/3, 3/3) = (0, 1) { vector đơn vị} VHumidity(Normail) = (2/2, 0/2) = (1, 0) { vector đơn vị} VWind(Weak) = (2/3, 1/3) VWind(Strong) = (0/2, 2/2) = (0, 1) { vector đơn vị} è Hai thuộc tính Temperature và Humidity đều có 2 vector đơn vị. Tuy nhiên, số phân hoạch của thuộc tính Humidity là ít hơn nên ta chọn phân hoạch theo thuộc tính Humidity. Phân hoạch lần 3: - Nhánh Rain # Outlook Temperature Humidity Wind Target 4 Rain Mild High Weak Yes 5 Rain Cool Normal Weak Yes 6 Rain Cool Normal Strong No 10 Rain Mild Normal Weak Yes 14 Rain Mild High Strong No VTemperature(Mild) = (2/3, 1/3) VTemperature(Cool) = (1/2, 1/2) VHumidity(High) = (1/2, 1/2) VHumidity(Normal) = (2/3, 1/3) VWind(Weak) = (2/3, 1/3) VWind(Strong) = (0/2, 2/2) = (0, 1) { vector đơn vị} è Thuộc tính Wind có vector đơn vị nên ta chọn phân hoạch. Vậy, cây định danh cuối cùng của chúng ta sẽ như sau : Phần IV: Thuật toán học quy nạp (ILA) Thuật toán học quy nạp ILA đưa ra hướng tiếp cận ngược lại so với thuật toán ID3. Trong toán ID3, quá trình rút tri thức từ dữ liệu được xuất phát từ các thuộc tính quan sát của tập dữ liệu. Từ việc kiểm tra trên các thuộc tính quan sát, ID3 chọn những thuộc tính có các giá trị mà chúng chia tập huấn luyện thành những tập con một cách tốt nhất. Các thuộc tính này sẽ được chọn để rút ra luật cho dữ liệu. Ngược lại, trong ILA, quá trình học xuất phát từ các thuộc tính quyết định. ILA chia tập dữ liệu huấn luyện thành các tập con rời nhau, mỗi tập con là một phân lớp dựa trên thuộc tính quyết định. Tiếp đến ILA sẽ xem xét trong từng phân lớp xem có thuộc tính nào (hoặc tổ hợp thuộc tính nào) có giá trị chỉ xuất hiện trong lớp đó mà không xuất hiện trong các lớp khác hay không. Nếu có, những (tổ hợp) thuộc tính và giá trị đó sẽ được chọn làm đặc trưng phân lớp cho lớp đó. Thuật toán ILA 1. Chia tập mẫu thành các bảng con ứng với thuộc tính quyết định 2. Với mỗi bảng con 3. Với mỗi tổ hợp thuộc tính có thể có (bắt đầu với số lượng = 1) 4. Tìm các giá trị chỉ xuất hiện ở bảng con này mà không xuất hiện ở các bảng con khác 5. (Nếu có nhiều tổ hợp thì chọn tổ hợp có số lượng mẫu tin nhiều nhất) 6. Sử dụng tổ hợp thuộc tính, giá trị vừa tìm được để tạo luật 7. Đánh dấu các dòng đã xét 8. Nếu còn dòng chưa xét, lặp lại bước 3 9. Lặp lại từ bước 2 với các bảng còn lại Áp dụng ILA cho bảng bài toán tennis: 1. Chia tập dữ liệu ban đầu thành 2 bảng con: # Outlook Temperature Hudmidity Wind Target 3 Overcast Hot High Weak Yes 4 Rain Mild High Weak Yes 5 Rain Cool Normal Weak Yes 7 Overcast Cool Normal Strong Yes 9 Sunny Cool Normal Weak Yes 10 Rain Mild Normal Weak Yes 11 Sunny Mild Normal Strong Yes 12 Overcast Mild High Strong Yes 13 Overcast Hot Normal Weak Yes # Outlook Temperature Hudmidity Wind Target 1 Sunny Hot High Weak No 2 Sunny Hot High Strong No 6 Rain Cool Normal Strong No 8 Sunny Mild High Weak No 14 Rain Mild High Strong No 2. Với bảng Yes: các giá trị sau không xuất hiện trong bảng No: • Tổ hợp 1 thuộc tính: Outlook = Overcast, các mẫu: 3, 7, 12, 13 ⇒ Luật L1: Nếu Outlook = Overcast thì Target = Yes (xoá các mẫu 3, 7, 12, 13) • Tổ hợp 2 thuộc tính: # Outlook Temperature Hudmidity Wind Target 4 Rain Mild High Weak Yes 5 Rain Cool Normal Weak Yes 9 Sunny Cool Normal Weak Yes 10 Rain Mild Normal Weak Yes 11 Sunny Mild Normal Strong Yes O = S ∧ T= C, mẫu: 9 O = S ∧ H = N, mẫu: 11, 9 O=R ∧ W = W, mẫu: 5, 4, 10 H = N∧ T = M, mẫu: 11, 10 T = C∧ W = W, mẫu: 5, 9 H = N ∧ W = W, mẫu: 5, 9, 10 ⇒ Luật L2: Nếu O = R ∧ W = W thì Target = Yes (xoá các mẫu 4, 5, 10) còn lại o O = S ∧ T = C, mẫu: 9 o O = S ∧ H = N, mẫu: 9, 11 o T = M ∧ H = N, mẫu: 11 o T = C ∧ W = W, mẫu: 9 ⇒ Luật L3: Nếu O = S ∧ H = N thì Target = Yes (xoá các mẫu_9, 11) Với bảng No: • Tổ hợp 1 thuộc tính: không có • Tổ hợp 2 thuộc tính: o O = S ∧ T= H, mẫu: 1, 2 o O = S ∧ H = H, mẫu: 1, 2, 8 o O = R ∧ W = S, mẫu: 6, 14 o T = H ∧ W = S, mẫu: 2 ⇒ Luật L4: Nếu O = S ∧ H = H thì Target = Yes (xoá các mẫu 1, 2, 8) còn lại o O = R ∧ W= S, mẫu: 6 ⇒ Luật L5: Nếu O = R ∧ W = S thì Target = Yes (xoá các mẫu_6) è Kết luận: vậy các luật phân lớp là L1 à L5. Phần III: Thuật toán Naïve Bayes Tiếp cận thống kê và Luật Bayes Trong cách tiếp cận thống kê, lý thuyết quyết định được sử dụng để chọn giá trị kết xuất cho mẫu mới. Theo lý thuyết quyết định, khi một mẫu mới x được cung cấp, giá trị của thuộc tính quyết định y là giá tri yk sao cho xác suất P(y = yk|x) là lớn nhất. Ví dụ trong bài toán tennis, với mẫu #16 ta cần xác định hai giá trị xác xuất P(Target = Yes|#16) và P(Target = No|#16) và chọn phân lớp ứng với giá trị lớn nhất trong hai giá trị này. Giá trị P(y = yk|x) thường khó tính được (do phải có rất nhiều mẫu huấn luyện mới có thể xấp xỉ chính xác). Công thức Bayes giúp đưa giá trị trên về dạng dễ tính hơn: Giá trị P(x) là như nhau đối với mọi phân lớp nên ta chỉ cần so sánh từ số của phân số trên. Một lần nữa, giá trị P(x|y=yk) (gọi là phân số của dữ liệu trong phân lớp) cũng khó tính toán. Giả định độc lập có điều kiện giữa các thuộc tính (Naïve) cho phép ta tính phân bố xác suất của mẫu dữ liệu thông qua phân bố xác suất của từng giá trị thuộc tính thành phần: Ví dụ với #16, ta có thể tính: P(#16| Target=Yes)= P(Outlook=Rain| Target=Yes) x P(Temp=Cool| Target=Yes) x P(Humidity=High| Target=Yes) x P(Wind=Strong| Target=Yes) và tính tương tự cho mẫu P(#16| Target=No). Thuật toán học máy Naïve Bayes Thuật toán học máy Naïve Bayes biểu diễn ánh xạ học dưới dạng một tập các giá trị phân bố xác suất. Các giá trị phân bố xác xuất được tính trong giai đoạn huấn luyện và được sử dụng để xác định giá trị quyết định cho những mẫu mới. Thuật toán Naïve Bayes 1. Huấn luyện Thống kê (đếm) xác suất của các lớp yk P(yk) và các giá trị phân bố xác suất P(Ai=vij|yk). Để đơn giản ta ký hiệu RAi(vij, yk) là tỷ lệ các mẫu có thuộc tính Ai = vij thuộc phân lớp yk: Sử dụng Với mỗi mẫu mới x, tính khả năng x rơi vào các phân lớp yk và chọn phân lớp có giá trị S lớn nhất. Sửa lỗi Laplace: khi dữ liệu ít, một trong những giá trị R có thể = 0 do bị nhiễu. Nếu R = 0 các thì giá trị S tương ứng cũng = 0. Để tránh trường hợp đó, phép sửa lỗi được đưa ra nhằm đảm bảo các giá trị xác suất luôn > 0. Sửa lỗi Laplace thực hiện như sau: Các giá trị P và R sau khi sửa lỗi được sử dụng như bình thường. Ví dụ Áp dụng thuật toán Naïve Bayes vào ví dụ tennis, ta thực hiện các bước sau: # Outlook Temperature Humidity Wind Target 1 Sunny Hot High Weak No 2 Sunny Hot High Strong No 3 Overcast Hot High Weak Yes 4 Rain Mild High Weak Yes 5 Rain Cool Normal Weak Yes 6 Rain Cool Normal Strong No 7 Overcast Cool Normal Strong Yes 8 Sunny Mild High Weak No 9 Sunny Cool Normal Weak Yes 10 Rain Mild Normal Weak Yes 11 Sunny Mild Normal Strong Yes 12 Overcast Mild High Strong Yes 13 Overcast Hot Normal Weak Yes 14 Rain Mild High Strong No Huấn luyện: P(Yes) = 9/14 sửa lỗi: P(Yes) = 10/16 P(No) = 5/14 sửa lỗi: P(No) = 6/16 ROverlook(Sunny, Yes) = 2/9, (sửa lỗi) = 3/12 {Tử + 1, Mẫu + 3 (S, O, R)} ROverlook(Overcast, Yes) = 4/9, (sửa lỗi) = 5/12 ROverlook(Rain, Yes) = 3/9 = 4/12 (sửa lỗi) ROverlook(Sunny, No) = 3/5 = 4/8 (sửa lỗi) ROverlook(Overcast, No) = 0/5 = 1/8 (sửa lỗi) ROverlook(Rain, No) = 2/5 = 3/8 (sửa lỗi) RTemperature (sửa lỗi) RHumidity (sửa lỗi) RWind (sửa lỗi) Weak Strong Yes 7/11 4/11 No 3/7 4/7 Hot Mild Cool Yes 3/12 5/12 4/12 No 3/8 3/8 2/8 Normal High Yes 7/11 4/11 No 2/7 5/7 Dự đoán cho mẫu #16: S(Yes) = P(Yes) x RO(Rain, Yes) x RT(Cool, Yes) x RH(Hum, Yes) x RW(Sunny, Yes) = 10/16 * 4/12 * 4/12 * 4/11 * 4/11 = 0,009 S(No) = P(No) x RO(Rain,No) x RT(Cool,No) x RH(Hum,No) x RW(S,No) = 6/12 * 3/8 * 2/8 * 5/7 * 4/7 = 0,019 Vậy #16 thuộc về lớp No vì S(No) > S(Yes). Phần V: Code xây dựng cây quyết định bằng thuật toán ID3 Kết quả cây định danh Giao diện: Chọn dữ liệu khác Tạo cây định danh Dữ liệu có sẵn từ file input.txt Code chương trình: using System; using System.Collections; using System.Data; using System.IO; using System.Collections.Generic; namespace ExemploID3 { public class Attribute { ArrayList mValues; string mName; object mLabel; public Attribute(string name, string[] values) { mName = name; mValues = new ArrayList(values); mValues.Sort(); } public Attribute(object Label) { mLabel = Label; mName = string.Empty; mValues = null; } public string AttributeName { get { return mName; } } public string[] values { get { if (mValues != null) return (string[])mValues.ToArray(typeof(string)); else return null; } } public bool isValidValue(string value) { return indexValue(value) >= 0; } public int indexValue(string value) { if (mValues != null) return mValues.BinarySearch(value); else return -1; } public override string ToString() { if (mName != string.Empty) { return mName; } else { return mLabel.ToString(); } } } // Tạo Treeview public class TreeNode { private ArrayList mChilds = null; private Attribute mAttribute; public TreeNode(Attribute attribute) { if (attribute.values != null) { mChilds = new ArrayList(attribute.values.Length); for (int i = 0; i < attribute.values.Length; i++) mChilds.Add(null); } else { mChilds = new ArrayList(1); mChilds.Add(null); } mAttribute = attribute; } public void AddTreeNode(TreeNode treeNode, string ValueName) { int index = mAttribute.indexValue(ValueName); mChilds[index] = treeNode; } public int totalChilds { get { return mChilds.Count; } } public TreeNode getChild(int index) { return (TreeNode)mChilds[index]; } public Attribute attribute { get { return mAttribute; } } public TreeNode getChildByBranchName(string branchName) { int index = mAttribute.indexValue(branchName); return (TreeNode)mChilds[index]; } } //Xây dựng cây public class DecisionTreeID3 { private DataTable mSamples; private int mTotalPositives = 0; private int mTotal = 0; private string mTargetAttribute = "Target"; private double mEntropySet = 0.0; private int countTotalPositives(DataTable samples) { int result = 0; foreach (DataRow aRow in samples.Rows) { if ((bool)aRow[mTargetAttribute] == true) result++; } return result; } private double calcEntropy(int positives, int negatives) { int total = positives + negatives; double ratioPositive = (