Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với maple

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN CAO HỌC CÔNG NGHỆ THÔNG TIN QUA MẠNG LẬP TRÌNH SYMBOLIC VÀ ỨNG DỤNG BÀI THU HOẠCH: NGHIÊN CỨU VÀ CÀI ĐẶT CÁC THUẬT TOÁN PHÂN LỚP DỮ LIỆU VỚI MAPLE Giảng viên: PGS. TS. Đỗ Văn Nhơn Học viên thực hiện: Huỳnh Tuấn Anh CH1101004 Khóa 6 TpHCM, 02/2013 Lời cám ơn. Em xin chân thành cám ơn PGS. TS. Đỗ Văn Nhơn đã tận tình hướng dẫn, chỉ bảo chúng em trong suốt thời gian học chuyên đề này. Xin chân thành cám ơn quý thầy cô trong Trường Đại Học Công Nghệ Thông Tin, Đại Học Quốc Gia Tp.HCM đã tận tình giảng dạy, trang bị cho em những kiến thức quý báu, tạo mọi điều kiện tốt cho chúng em học tập và nghiên cứu. Xin chân thành cám ơn gia đình và bạn bè đã ủng hộ, giúp đỡ và động viên em trong thời gian học tập và nghiên cứu. Mặc dù đã cố gắng hoàn thành bài luận nhưng chắc chắn không tránh khỏi thiếu sót. Em kính mong nhận được sự thông cảm và tận tình chỉ bảo của quý thầy cô. Học viên thực hiện Huỳnh Tuấn Anh TpHCM, 02/2013 Mục Lục Chương 1: THUẬT TOÁN FIND-S HỌC KHÁI NIỆM VÀ BÀI TOÁN CỤ THỂ Theo Tom M.Mitchell: “Nhiều vấn đề học đòi hỏi các khái niệm tổng quát thu được từ các ví dụ huấn luyện. Vấn đề tự động kết luận về sự xác định tổng quát nhất của một vài khái niệm, các ví dụ cho trước được ghi nhãn có phải là bộ phận của khái niệm hay không, nhiệm vụ đó thường được xem như là học khái niệm.” Học khái niệm Cho trước các ví dụ huấn luyện. mỗi ví dụ huấn luyện cho biết có thuộc khái niệm hay không? (thuộc: positive; không: negative) Đưa ra khái niệm tổng quát phân loại tập huấn luyện. Khái niệm tổng quát là hàm boolean được định nghĩa trên tập cá thể. “Học khái niệm là đưa ra một hàm boolean từ tập input và putput của các ví dụ huấn luyện” (Tom M.Mitchell – Machine Learning) Ví dụ: (Input) Các ví dụ huấn luyện: Tập các animal cùng thuộc tính của nó. (Output) Khái niệm được trích ra: Bird Cat Bài toán cụ thể (Input) Tập ví dụ huấn luyện gồm 4 cá thể sau: Tập này nói về những ngày (như thế nào đó) mà Aldo thích chơi môn thể thao dưới nước của anh ta (Table 2.1 – Positive and negative training examples gor thw target concept EnjoySport, Machine Learning – Tom M.Mitchell, 2003). Example Sky AirTemp Humidity Wind Water Forecast EnjoySport 1 Sunny Warm Normal Strong Warm Same Positive 2 Sunny Warm High Strong Warm Same Positive 3 Rainy Cold High Strong Warm Change Negative 4 Sunny Warm High Strong Cool Change Positive Bảng 1.1 – Các ví dụ huấn luyện thuộc và không thuộc khái niệm đích EnjoySport (Output) Khái niệm được học: “EnjoySport” Giả thiết Cũng được hiểu là khái niệm. Là hội của các ràng buộc trên thuộc tính của cá thể. X là cá thể, và X thoả mãn tất cả các ràng buộc trên giả thiết h thì h [hân loại X là positive (h(X) = 1) Ví dụ: Giả thiết là Aldo thích môn thể thao dưới nước vào nagỳ “cold days with high humidity”, giả thiết được ghi là: Giả thiết tổng quát nhất: Giả thiết cụ thể nhất: Ký hiệu Tập cá thể (set of instances) Tập được dùng để trích khái niệm từ đó Ký hiệu: X Ví dụ trên: tập cá thể = tập ngày, mỗi ngày có 6 thuộc tính. Khái niệm đích (target concep) Khái niệm (hàm) được học. Ký hiệu: c c: X à {0,1} Ví dụ trên: c(X) = 1 nếu EnjoySport = Yes Ví dụ trên: c(X) = 0 nếu EnjoySport = No Các ví dụ huấn luyện, gồm có: Một cá thể thuộc X. Khái niệm đích c(X). Viết là: Tập các giả thiết (H): các giả thiết về sự phân loại tập cá thể. Chương trình học: Cho trước tập ví dụ huấn luyện. Đưa ra giả thiết về sự phân loại tập cá thể: h(X) = c(X) Thứ tự các giả thiết Các giả thiết trong không gian đều có thứ tự Có thể sắp xếp theo dạng: Tổng quát à cụ thể. Thứ tự: hj và hk là hai giả thiết. hj được nó là tổng quát hơn hay bằng hk nếu và chỉ nếu: (∀x Є X)[(hk(x) = 1) à (hj(x) =1)] Ký hiệu: hj ≥g hk Ví dụ: h2 ≥g h1 với h1 và h2 sau: h1 = h2 = THUẬT TOÁN FIND – S: TÌM MỘT GIẢ THUYẾT ĐẶC THÙ NHẤT Thuật toán Find-S h = giả thiết cụ thể nhất trong H. Với mỗi x Є tập ví dụ huấn luyện, mà c(X) = 1 Với mỗi ràng buộc ai trong h IF ai thoả bởi x THEN do nothing ELSE thay ai bởi ràng buộc tổng quát hơn kế tiếp mà nó được thoả bởi x Xuất ra h. Áp dụng thuật toán với ví dụ huấn luyện mục 1.2: h ß Cá thể 1 (positive): h ß Cá thể 2 (positive): h ß Cá thể 3 (negative): h không đổi. Cá thể 4 (positive): h ß OUTPUT: CÀI ĐẶT CHƯƠNG TRÌNH Ngôn ngữ lập trình, biến môi trường, các thư viện được sử dụng Thuật toán Find-S được viết bằng ngôn ngữ Maple (dùng Maple 12), sau đó đóng gói lại thành môt thư viện và lưu vào thư mục “C:\Find-S\”. Chương trình được viết hoàn chỉnh dưới dạng thể hiện form liên kết bên dưới với package đã được tạo ra ở trên, bằng ngôn ngữ Java (dùng NetBeans IDE 6.5). Biến môi trường: Mục đích: kết nối Maple với Java Cách đặt biến môi trường: Click chuột phải vào My computer, chọn Properties. Trong hộp thoại mới hiện ra, chọn tiếp Advanced System Setting nếu là Win Vista hoặc Win 7, Win XP thì chọn Advanced. Trong hộp thoại System Properties, chọn Environment Variables Trong bảng System Variables, chọn Path trong phần Variables, rồi bấm Edit. Trong hộp thoại Edit System Variable, thêm dòng sau vào mục Variable value “C:\Program Files\Maple 12\bin.win”. Lưu ý: ngăn cách giữa các Variable value là các dấu “;”. Bấm chọn OK (hoặc Apply) để đồng ý thay đổi. Khởi động lại máy. Một số thư viện đặc biệt được sử dụng: com.maplesoft.openmaple.* : import các lớp OpenMaple của Java. com.maplesoft.externalcall.MapleException : import lớp MapleException. Ngoài ra, chương trình còn sử dụng Maple Engine, engine này có chức năng kết nối với Maple để thực hiện các lệnh trong Maple. Cấu trúc, chức năng các tập tin cài đặt và tập tin training examples Các tập tin cài đặt: Tập tin Find-S.mw: cài đặt thuật toán Find-S rồi đóng gói lại thành thư viện bằng chương trình Maple 12. Tập tin demo.mw: chạy thử thuật toán đã được cài đặt ở trên với một số dữ liệu huấn luyện. Tập tin Main.java: tạo form với các thao tác tương ứng trong chương trình (Tạo bảng, Đọc ví dụ huấn luyện từ tập tin, Hiển thị giả thiết đặc thù nhất). Các tập tin training examples: Cấu trúc chung của các tập tin training examples dạng .txt là: Mỗi dòng là một mô tả chi tiết các thuộc tính của một cá thể trong tập cá thể, mỗi thuộc tính cách nhau ít nhất một khoảng trắng hoặc một tab. Mỗi thuộc tính có một số giá trị hữu hạn. Cuối cùng là khái niệm đích. Thứ tự giá trị cho mỗi thuộc tính trong ví dụ đó được nhập tương ứng. Tên tập tin, thuộc tính và các giá trị không chấp nhận các giá trị đặc biệt như: `, ~, &, (, ), !, #, %, ^, -, \, |, {, }, [, ], ;, ... có thể chấp nhận ký tự gạch dưới. Nội dung các hàm chính và các tham số có liên quan Trong Java, tập tin Main.java: public Main() throwMapleException: Khởi tạo Maple Engine với Java. Đồng thời đặt Table không có Header. void jButton2ActionPerformed(java.awt.event.ActionEvent evt): Sự kiện của button Show Version Space, hiển thị những giả thiết phù hợp với Training Examples. Gọi ShowMaximallySpecificHypothesis() void jButton3ActionPerformed(java.awt.event.ActionEvent evt): Sự kiện của button ReadFromFile. void jButton4ActionPerformed(java.awt.event.ActionEvent evt): Sự kiện button Create Table. Tạo bảng với số dòng và số cột được cho trong jTextField1 ColunmCount và jTextField2 RowCount void ShowMaximallySpecificHypothesis() Hiển thị Maximally Specific Hypothesis lên jTextArea1 Thực hiện hàm FindS của package FindSAlgorithm bằng Maple với tập ví dụ huấn luyện đưa vào là D, sau đó lấy kết quả Maximally Specific Hypothesis trả về hiển thị lên jTextArea1 Maximally Specific Hypothesis trong form. Chuỗi S chứa tập ví dụ từ D[1] đến D[i], nhằm hiển thị kết quả theo từng bước thực hiện giải thuật. Trong Maple, tập tin Find-S.mw: + Finding maximally specific hypothesis consistent with the training examples D FindS:=proc(D::list) h: kết quả trả về x: danh sách lưu mỗi ví dụ, không bao gồm giá trị phân loại cx: bằng 1 nếu giá trị của thuộc tính phân loại là positive, bằng 0 nếu là negative local h,x,cx,d,i; h:=[]; h ← giả thiết đặc thù nhất if nops(D)0 then for i from 1 to nops(D[1][1]) do h:=[op(h),` `]; od; fi; Với mỗi ví dụ huấn luyện d for d in D do x:=d[1]; cx:=d[2]; Nếu d là 1 positive example if cx=1 then Đối với mỗi ràng buộc trên thuộc tính trong h for i from 1 to nops(h) do Nếu x thỏa ràng buộc trên thuộc tính trong h thì không làm gì cả if h[i]=x[i] or h[i]=`?` then # do nothing Ngược lại, thay thế ràng buộc trong h bằng một ràng buộc tổng quát hơn để x thỏa nó else if h[i]=` ` then h[i]:=x[i]; else h[i]:=`?`; fi; fi; od; fi; od; RETURN (h); end: + Kiểm tra x có thỏa h hay không (x thỏa h nghĩa là h(x)=1, bất kể x là positive hay negative), kết quả trả về bằng 1 nếu thỏa, bằng 0 nếu ngược lại Classification:=proc(h::list,x::list) local i; for i from 1 to nops(h) do if h[i]=`?` or h[i]=x[i] then # do nothing elif h[i]=` ` or h[i]x[i] then RETURN (0); fi; od; RETURN (1); end: HƯỚNG DẪN SỬ DỤNG CHƯƠNG TRÌNH Đặt biến môi trường như mục 3.1 Tạo thư mục Find-S tại thư mục gốc ổ đĩa C (tức là thư mục Find-S có đường dẫn như sau “C:\Find-S\”). Sau đó chạy tập tin Find-S.mw với phần mềm Maple để đóng gói thuật toán thành package lưu vào thư mục vừa tạo ở trên. Chạy project Find-S với NetBeans. Giao diện chương trình như sau: Có thể tạo tập ví dụ huấn luyện bằng một trong hai cách sau: Tạo mới một Table: bằng cách nhập số cột (vào mục Column Count) và số dòng (vào mục Row Count) rồi bấm nút Create Table. Bấm nút Read From File để load tập tin Training Examples sẵn có với cấu trúc giống như mô tả trong mục 3.2.2 Bấm nút Show để hiện thị các giả thiết đặc thù nhất từ tập ví dụ huấn luyện. MỘT SỐ VÍ DỤ VÀ KẾT QUẢ CHƯƠNG TRÌNH EnjoySport training examples: TrainingExample1.txt Sunny Warm Normal Strong Warm Same Positive Sunny Warm High Strong Warm Same Positive Rainy Cold High Strong Warm Change Negative Sunny Warm High Strong Cool Change Positive Hiển thị Maximally Specific Hypothesis theo từng bước tính toán: h1 = [Sunny, Warm, Normal, Strong, Warm, Same] h2 = [Sunny, Warm, `?`, Strong, Warm, Same] h3 = [Sunny, Warm, `?`, Strong, Warm, Same] h4 = [Sunny, Warm, `?`, Strong, `?`, `?`] Kết quả thuật toán chính xác với phần áp dụng thuật toán cho ví dụ huấn luyện mục 2.2 Phân lớp một New Instance mới: x:= [Sunny,Cold,Low,Strong,Warm,Same] Kết quả x thuộc lớp: Negative Sunburned training examples: TrainingExample2.txt blonde average light no negative blonde tall average yes positive brown short average yes positive blonde short average no negative red average heavy no negative brown tall heavy no positive brown average heavy no positive blonde short light yes positive Hiển thị Maximally Specific Hypothesis theo từng bước tính toán: h1 = [` `, ` `, ` `, ` `] h2 = [blonde, tall, average, yes] h3 = [`?`, `?`, average, yes] h4 = [`?`, `?`, average, yes] h5 = [`?`, `?`, average, yes] h6 = [`?`, `?`, `?`, `?`] h7 = [`?`, `?`, `?`, `?`] h8 = [`?`, `?`, `?`, `?`] Phân lớp một New Instance mới: x:=[blonde,short,light,no] Kết quả x thuộc lớp: Positive Auto training examples: TrainingExample3.txt Japan Honda Blue 1980 Sedan Positive Japan Toyota Green 1970 Sports Negative Japan Toyota Blue 1990 Sedan Positive USA Dodge Red 1980 Sedan Negative Japan Honda White 1980 Sedan Positive Hiển thị Maximally Specific Hypothesis theo từng bước tính toán: h1 = [Japan, Honda, Blue, `1980`, Sedan] h2 = [Japan, Honda, Blue, `1980`, Sedan] h3 = [Japan, `?`, Blue, `?`, Sedan] h4 = [Japan, `?`, Blue, `?`, Sedan] h5 = [Japan, `?`, `?`, `?`, Sedan] Phân lớp một New Instance mới: x:= [Japan,Honda,Red,1990,Sports] Kết quả x thuộc lớp: Negative Chương 2: THUẬT TOÁN ID3 MÔ TẢ CHUNG THUẬT TOÁN ID3 VÀ BÀI TOÁN Thuật toán ID3 Thuật toán học quy nạp (inductive learning algorithm) cây quyết định ID3 là một thuật toán được sử dụng rộng rãi trong số nhiều thuật toán được đưa ra theo tiếp cận học dựa trên ký hiệu biểu diễn vấn đề dưới dạng các ký hiệu (symbol-based learning). Thuật toán học quy nạp cây ID3 (gọi tắt là ID3) là một thuật toán học đơn giản nhưng tỏ ra thành công trong nhiều lĩnh vực. ID3 là một thuật toán hay vì cách biểu diễn tri thức học được của nó, tiếp cận của nó trong việc quản lý tính phức tạp, Heuristic của nó dùng cho việc chọn lựa các khái niệm ứng viên và tiềm năng của nó đối với việc xử lý dữ liệu nhiễu. ID3 biểu diễn các khái niệm ở dạng các cây quyết định. Biểu diễn này cho phép chúng ta xác định phân loại của một đối tượng bằng cách kiểm tra các giá trị của nó trên một số thuộc tính nào đó. Như vậy, nhiệm vụ của thuật toán ID3 là học cây quyết định từ một tập các ví dụ huấn luyện (training examples) hay còn gọi là dữ liệu huấn luyện. Hay nói khác hơn, thuật toán có: Đầu vào: Một tập hợp các ví dụ. Mỗi ví dụ 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 có khả năng phân loại đúng đắn các ví dụ trong tập dữ liệu huấn luyện, cũng như đối với các ví dụ khác. Xét một bài toán phân loại cụ thể Xét bài toán phân loại xem “có đi chơi Tennis” (PlayTennis) ứng với một điều kiện nào đó hay không? Thuật toán ID3 sẽ học cây quyết định từ tập hợp các ví dụ huấn luyện sau (Table 3.2 – Training examples for target concept PlayTennis, Machine Learning – Tom M.Mitchell, 2003): Day Outlook Temp Humidity Wind PlayTennis 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 Bảng 1.1 – Tập dữ liệu huấn luyện cho khái niệm “PlayTennis” Tập dữ liệu này bao gồm 14 ví dụ. Mỗi ví dụ biểu diễn cho điều kiện thời tiết gồm các thuộc tính Outlook (quang cảnh), Temp (nhiệt độ), Humidity (độ ẩm) và Wind (gió); và đều có một thuộc tính phân loại PlayTennis (Yes, No), còn được gọi là thuộc tính đích. “No” nghĩa là không đi chơi Tennis ứng với thời tiết đó, “Yes” nghĩa là ngược lại. Giá trị phân loại ở đây chỉ có hai loại (Yes, No). Mỗi thuộc tính đều có một tập các giá trị hữu hạn. Thuộc tính Outlook có ba giá trị (Overcast, Rain, Sunny), Temp có ba giá trị (Hot, Cool, Warm), Humidity có hai giá trị (High, Normal) và Wind có hai giá trị (Strong, Weak). Các giá trị này chính là ký hiệu (symbol) dùng để biểu diễn bài toán. THUẬT TOÁN ID3 VÀ CƠ SỞ LÝ THUYẾT Quinlan (1983) là người đầu tiên đề xuất việc sử dụng lý thuyết thông tin để tạo ra các cây quyết định và công trình của ông là cơ sở cho phần trình bày ở đây. Lý thuyết thông tin của Shannon (1948) cung cấp khái niệm Entropy để đo tính thuần nhất (hay ngược lại là độ pha trộn) của một tập hợp. Một tập hợp là thuần nhất nếu như tất cả các phần tử của tập hợp đều thuộc cùng một loại, và khi đó ta nói tập hợp này có độ pha trộn là thấp nhất. Trong trường hợp của tập ví dụ, thì tập ví dụ là thuần nhất nếu như tất cả các ví dụ đều có cùng giá trị phân loại. Khi tập ví dụ là thuần nhất thì có thể nói: ta biết chắc chắn về giá trị phân loại của một ví dụ thuộc tập này, hay ta có lượng thông tin về tập đó là cao nhất. Khi tập ví dụ có độ pha trộn cao nhất, nghĩa là số lượng các ví dụ có cùng giá trị phân loại cho mỗi loại là tương đương nhau, thì khi đó ta không thể đoán chính xác được một ví dụ có thể có giá trị phân loại gì, hay nói khác hơn, lượng thông tin ta có được về tập này là ít nhất. Vậy, ta cần chọn thuộc tính để hỏi sao cho có thể chia tập ví dụ ban đầu thành các tập ví dụ thuần nhất càng nhanh càng tốt. Vậy trước hết, ta cần có một phép đo để đo độ thuần nhất của một tập hợp, từ đó mới có thể so sánh tập ví dụ nào thì tốt hơn. Entropy đo tính thuần nhất của tập ví dụ Khái niệm entropy của một tập S được định nghĩa trong Lý thuyết thông tin là số lượng mong đợi các bít cần thiết để mã hóa thông tin về lớp của một thành viên rút ra một cách ngẫu nhiên từ tập S. Trong trường hợp tối ưu, mã có độ dài ngắn nhất. Theo lý thuyết thông tin, mã có độ dài tối ưu là mã gán –log2p bits cho thông điệp có xác suất là p. Trong trường hợp S là tập ví dụ, thì thành viên của S là một ví dụ, mỗi ví dụ thuộc một lớp hay có một giá trị phân loại. Entropy có giá trị nằm trong khoảng [0..1], Entropy(S) = 0 ó tập ví dụ S chỉ toàn ví dụ thuộc cùng một loại, hay S là thuần nhất. Entropy(S) = 1 ó tập ví dụ S có các ví dụ thuộc các loại khác nhau với độ pha trộn là cao nhất. 0 < Entropy(S) < 1 ó tập ví dụ S có số lượng ví dụ thuộc các loại khác nhau là không bằng nhau. Để đơn giản ta xét trường hợp các ví dụ của S chỉ thuộc loại âm (-) hoặc dương (+). Hình 3.4 – Entropy(S) Hình 3.4 minh họa sự phụ thuộc của giá trị entropy vào xác suất xuất hiện của ví dụ dương. Cho trước: • Tập S là tập dữ liệu rèn luyện, trong đó thuộc tính phân loại có hai giá trị, giả sử là âm (-) và dương (+) • p+ là phần các ví dụ dương trong tập S. • p_ là phần các ví dụ âm trong tập S. Khi đó, entropy đo độ pha trộn của tập S theo công thức sau: Entropy(S) = - p+ log2 p+ - p- log2 p- Một cách tổng quát hơn, nếu các ví dụ của tập S thuộc nhiều hơn hai loại, giả sử là có c giá trị phân loại thì công thức entropy tổng quát là: Entropy(S) = i=1c-pI log2 pi Lượng thông tin thu được đo mức độ giảm entropy mong đợi Entropy là một số đo đo độ pha trộn của một tập ví dụ, bây giờ chúng ta sẽ định nghĩa một phép đo hiệu suất phân loại các ví dụ của một thuộc tính. Phép đo này gọi là lượng thông tin thu được, nó đơn giản là lượng giảm entropy mong đợi gây ra bởi việc phân chia các ví dụ theo thuộc tính này. Một cách chính xác hơn, Gain(S,A) của thuộc tính A, trên tập S, được định nghĩa như sau: Gain (S,A) = Entropy (S) - v∈Values(A)SvS Entropy (Sv) trong đó Values(A) là tập hợp có thể có các giá trị của thuộc tính A, và Sv là tập con của S chứa các ví dụ có thuộc tính A mang giá trị v. Áp dụng cụ thể cho ví dụ huấn luyện ở Bảng 1.1 Bước 1: cây cho S Gain(S, Outlook) = 0.246 Gain(S, Humidity) = 0.151 Gain(S, Wind) = 0.048 Gain(S, Temperature) = 0.029 Outlook : thuộc tính phân loại tốt nhất tại bước này. Outlook: root node. Cây như sau: Bước 2: Cây cho Ssunny Ssunny={D1,D2,D8,D9,D11} Gain(Ssunny, Humidity) = 0.97- (3/5)0.0 – (2/5)0.0 = 0.97 Gain(Ssunny, Wind) = 0.97 – (2/5)1.0 –(3/5)0.918 = 0.019 Gain(Ssunny, Temperature) = 0.97-(2/5)0.0-(2/5)1.0-(1/5)0.0=0.57 Humidity : thuộc tính phân loại tốt nhất tại bước này. Humidity: root của Ssunny. Cây như sau: Bước 3: Cây cho Srain Srain={D4,D5,D6,D10,D14} Kết quả: Điều kiện dừng: Mọi nút là đều nằm vào 1 trong hai trường hợp: 1. Tất cả các thuộc tính đều đã nằm trên node thuộc con đường từ root đến lá đó. 2. Node lá có entropy = 0. Entropy=0, Tất cả cá thể đều + à Phân loại Yes. Entropy=0, Tất cả cá thể đều - à Phân loại No. Thuật toán ID3 Tạo node gốc cho cây. if tất cả các cá thể là positive then trả về cây chỉ có node, nhãn là + if tất cả các cá thể là negative then trả về cây chỉ có node, nhãn là – if Attributes trống then trả về cây chỉ có 1 node, nhãn là giá trị chung nhất của Target_Attribute trong tập cá thể. else: Begin A ß Thuộc tính từ Attributes tốt nhất phân loại tập cá thể. Thuộc tính cho root là A. (root ß A) For each trị Vi của A: Thêm 1 nhánh mới dưới root, tương ứng A = Vi. ExamplesVi = tập con các cá thể thuộc Examples có A=Vi. if ExamplesVi trống: then dưới nhánh mới này, thêm 1 node lá có nhãn = trị chung nhất của Target_Attribute trong Examples. else dưới nhánh mới này thêm 1 cây con, trả về từ lời gọi: ID3(ExamplesVi, Target_Attribute, Attributes – {A}) End. /*Begin*/ Return Root. CÀI ĐẶT CHƯƠNG TRÌNH Ngôn ngữ lập trình, biến môi trường, các thư viện được sử dụng Thuật toán ID3 được viết bằng ngôn ngữ Maple (dùng Maple 12), sau đó đóng gói lại thành môt thư viện và lưu vào thư mục “C:\ID3\”. Chương trình được viết hoàn chỉnh dưới dạng thể hiện form liên kết bên dưới với package đã được tạo ra ở trên, bằng ngôn ngữ Java (dùng NetBeans IDE 6.5). Biến môi trường: Mục đích: kế nối Java với Maple Cách đặt biến môi trường: Click chuột phải vào My computer, chọn Properties. Trong hộp thoại mới hiện ra, chọn tiếp Advanced System Setting nếu là Win Vista hoặc Win 7, Win XP thì chọn Advanced. Trong hộp thoại System Properties, chọn Environment Variables Trong bảng System Variables, chọn Path trong phần Variables, rồi bấm Edit. Trong hộp thoại Edit System Variable, thêm dòng sau vào mục Variable value “C:\Program Files\Maple 12\bin.win”. Lưu ý: ngăn cách giữa các Variable value là các dấu “;”. Bấm chọn OK (hoặc Apply) để đồng ý thay đổi Khởi động lại máy. Một số thư viện đặc biệt được sử dụng: com.maplesoft.openmaple.* : import các lớp OpenMaple của Java. com.maplesoft.externalcall.MapleException : import lớp MapleException. Ngoài ra, chương trình còn sử dụng Maple Engine, engine này có chức năng kết nối với Maple để thực hiện các lệnh trong Maple. Cấu trúc, chức năng các tập tin cài đặt và tập tin training examples Các tập tin cài đặt: Tập tin ID3.mw: cài đặt thuật toán ID3 rồi đóng gói lại thành thư viện bằng chương trình Maple 12. Tập tin demo.mw: chạy thử thuật toán đã được cài đặt ở trên với một số dữ liệu huấn luyện; tính các chỉ số Entropy, Gain trong các trường hợp tương ứng. Tập tin DecisionTreeFrame.java: hiển thị cây quyết định. Tập tin Main.java: tạo form với các thao tác tương ứng (Tạo bảng, Đọc ví dụ huấn luyện từ tập tin, Hiển thị các luật, Hiển thị cây quyết định). Các tập tin training examples: Cấu trúc chung của các tập tin training examples dạng .txt là: Dòng đầu tiên mô tả các thuộc tính có trong ví dụ huấn luyện, mỗi thuộc tính cách nhau ít nhất một khoảng trắng hoặc một tab. Thuộc tính cuối cùng là thuộc tính phân loại. Mỗi thuộc tính có một số giá trị hữu hạn. Mỗi dòng kế tiếp là một ví dụ huấn luyện, thứ tự giá trị cho mỗi thuộc tính trong ví dụ đó được nhập tương ứng. Tên tập tin, thuộc tính và các giá trị không chấp nhận các giá trị đặc biệt như: `, ~, &, (, ), !, #, %, ^, -, \, |, {, }, [, ], ;, ... có thể chấp nhận ký tự gạch dưới. Nội dung các hàm chính và các tham số có liên quan Trong Java: + Tập tin Main.java: public Main() throws MapleException: Khởi tạo Maple Engine với Java. Đồng thời đặt Table không có Header. String GetDecisionTree(): Gán các thuộc tính cho chuỗi A, gán các tập ví dụ cho S lấy từ bảng dữ liệu Training Examples trong form. Thực hiện các lệnh trong Maple với package ID3.lib trong thư mực C:/ID3/, gán các giá trị cho từng thuộc tính trong bảng dữ liệu Training Examples (từ form); thực hiện giải thuật ID3 bằng Maple cho tập thuộc tính A và tập ví dụ S Vector ListNodes(String Nodes): Chuyển chuỗi Nodes kết quả trả về của hàm GetNodes(T) trong Maple thành 1 Vector trong Java. Thành phần của Vector sẽ là mỗi nút được lưu thành 1 danh sách gồm nút cha và các nút con, mỗi nút sẽ được tách bởi dấu "|" để phân biệt giữa 2 nút, để vẽ các nút trong form DecisionTreeFrame.java. void jButton1ActionPerformed(java.awt.event.ActionEvent evt): Sự kiện của button ShowDecisionTree, hiển thị cây quyết định trên form DecisionTreeFrame. Thực hiện lệnh GetNodes(T) để chuyển chuỗi T, là danh sách các nhánh của cây quyết định từ Maple với Training Examples lấy từ bảng dữ liệu trong form, sang danh sách các nút để vẽ cây quyết định ở Form DecisionTreeFrame. void jButton2ActionPerformed(java.awt.event.ActionEvent evt): Sự kiện của button ShowRules, hiển thị các luật. Chuyển từ chuỗi T, là danh sách các nhánh của cây quyết định từ Maple với Training Examples lấy từ bảng dữ liệu trong form, sang các luật. + Tập tin DecisionTreeFrame: void paintComponent(Graphics g): hàm vẽ cây quyết định Duyệt qua các nút con của nút parent (khởi tạo = 0). Trường hợp nếu chỉ có 1 nút con, vẽ nút đó ngay bên dưới nút parent; nếu số nút con là chẵn, vẽ bên dưới nút parent, lấy nút parent là điểm giữa cách đều các nút con; nếu số nút con là lẻ, vẽ bên dưới nút parent, lấy phần tử ở giữa của nút con là điểm cách đều. Vẽ 1 đường thẳng từ nút parent đến các nút con. Trong Maple, tập tin ID3.mw: + Hàm tìm tập con Sv của S1 cho mỗi thuộc tính attr có giá trị là val(Sv = {s ∈S ∣ A(s) = 0}) Sv:=proc(S1,attr,val) result: lưu tập con Sv của S1 (dưới dạng danh sách) local i,j,result; result:=[]; for i from 1 to nops(A) do if attr=A[i] then for j from 1 to nops(S1) do if S1[j][i]=val then result:=[op(result),S1[j]]; fi; od; fi; od; if attr=target_attribute then for j from 1 to nops(S1) do if S1[j][nops(A)+1]=val then result:=[op(result),S1[j]]; fi; od; fi; RETURN (result); end: + Hàm tính Entropy của tập S1: Entropy(S1)= Entropy:=proc(S1) E: biến lưu giá trị Entropy p: tỉ lệ của ví dụ huấn luyện ứng với mỗi giá trị của thuộc tính phân loại val: danh sách giá trị của thuộc tính phân loại local E,p,i,val; E:=0; val:=GetValue(target_attribute); for i from 1 to nops(val) do if nops(S1)0 then p = số phần tử tập con Sv của S1 cho thuộc tính phân loại có giá trị là val[i] trên tổng số phần tử của S1 p:=nops(Sv(S1,target_attribute,val[i]))/nops(S1); fi; if p0 then E:=E+(-p*log[2](p)); fi; od; RETURN (E); end: + Hàm tính Gain của thuộc tính attr trên tập S Gain:=proc(S1,attr) G: Entropy(S) - s; s = Entropy(Sv1) local G,s,Sv1,i,val; G:=0;s:=0; val:=GetValue(attr); for i from 1 to nops(val) do Sv1:=Sv(S1,attr,val[i]); if nops(S1)0 then s:=s+nops(Sv1)/nops(S1)*Entropy(Sv1); fi; od; G:=Entropy(S1)-s; RETURN (G); end: + Hàm tính giá trị phổ biến của thuộc tính attr CommonValue:=proc(attr) val: danh sách giá trị của thuộc tính attr s: tập con Sv của S cho thuộc tính attr có giá trị là val[i] CV: giá trị phổ biến local i,max,val,s,CV; max:=0; val:=GetValue(attr); for i from 1 to nops(val) do s:=Sv(S,attr,val[i]); if max<nops(s) then max:=nops(s); CV:=val[i]; fi; od; RETURN (CV); end: + Hàm xây dựng cây quyết định Các tham số đầu vào: Examples: training examples Attributes: danh sách các thuộc tính đã được kiểm tra bởi cây quyết định Trả về cây quyết định của Examples InduceTree:=proc(Examples,Attributes) global branch,T; g: Tính giá trị Gain của mỗi thuộc tính trong danh sách các thuộc tính Attributes trên tập Examples maxG: giá trị Gain cao nhất A1: thuộc tính được chọn bởi giá trị Gain cao nhất V: danh sách các giá trị của thuộc tính A1 Vi: mỗi giá trị trong V ExamplesVi: tập con của Examples cho thuộc tính A1 có giá trị là Vi val: danh sách các giá trị của thuộc tính phân loại vertice: mỗi đỉnh trong cây quyết định turn: lưu lại đỉnh rẽ nhánh trước đó của cây quyết định T: danh sách các nhánh của cây, có nhánh ko lưu hết từ nút gốc đến nút lá mà chỉ lưu từ chỗ rẽ nhánh của nhánh cây trước đến nút lá local g,maxG,i,A1,V,Vi,ExamplesVi,val,vertice,turn; maxG:=0; val:=GetValue(target_attribute); Nếu mọi ví dụ trong tập ví dụ đều nằm trong cùng một lớp thì return một lớp được gán nhãn bởi lớp đó for i from 1 to nops(val) do if nops(Sv(Examples,target_attribute,val[i]))=nops(Examples) then branch:=[op(branch),val[i]]; T:=[op(T),branch]; RETURN; fi; od; Nếu tập thuộc tính là rỗng thì return nút lá là giá trị phổ biến trong thuộc tính phân loại if Attributes={} then branch:=[op(branch),CommonValue(target_attribute)]; T:=[op(T),branch]; Otherwise else Tìm thuộc tính có giá trị Gain lớn nhất, trả kết quả cho A1 for i from 1 to nops(Attributes) do g:=evalf(Gain(Examples,Attributes[i])); if maxG<g then maxG:=g; A1:=Attributes[i]; fi; od; vertice:=A1; Gán A1 là 1 đỉnh của cây quyết định turn:=vertice; Gán đỉnh rẽ nhánh là vertice branch:=[op(branch),vertice]; Thêm vào nhánh đỉnh vertice V:=GetValue(A1); lấy danh sách giá trị thuộc tính của A1 for Vi in V do với mỗi giá trị của A1 vertice:=Vi; Lưu đỉnh tiếp theo trong nhánh branch:=[op(branch),vertice]; Tiếp tục thêm vào nhánh đỉnh vertice ExamplesVi:=Sv(Examples,A1,Vi); Nếu Examples là [] thì thêm vào nhánh giá trị phổ biến của thuộc tính phân loại if ExamplesVi=[] then branch:=[op(branch),CommonValue(target_attribute)]; T:=[op(T),branch]; Kết thúc một nhánh, thêm nhánh vào cây else Tiếp tục đệ qui để lần xuống nút lá branch:=[op(branch),InduceTree(ExamplesVi,`minus`(Attributes,{A1}))]; branch:=turn; fi; od; fi; RETURN (T); end: + Chuyển cây về các luật, trước khi chuyển cây về các luật, do một số nhánh của cây chưa lưu từ nút gốc đến nút lá nên chuyển những nhánh như thế về nhánh lưu từ nút gốc đến nút lá, sau đó mới chuyển về các luật có dạng: If attr1=Values(attr1) ∧attr2=Values(attr2) ∧... then target_attribute=Values(target_attribute) GetRules:=proc(T) root: nút gốc b: những nhánh không lưu từ nút gốc đến lá temp: nhánh trước đó của b pos: vị trí của nút đầu tiên trong b trong nhánh temp str: chuỗi lưu từng phần của luật khi xử lý rule: chuỗi lưu mỗi luật rules: danh sách các rule local i,j,b,root,temp,pos,str,rule,rules,T1; T1:=T; root:=T1[1][1]; for i from 2 to nops(T1) do b:=T1[i]; if b[1] root then temp:=T1[i-1]; pos:=ListTools[Search](b[1],temp)-1; T1[i]:=[op(1..pos,T1[i-1]),op(T1[i])]; fi; od; rule:=[]; rules:=[]; for i from 1 to nops(T1) do b:=T1[i]; for j from 1 to (nops(b)-2) do if type(j/2,integer)=false then str:=StringTools[CaseJoin]([b[j]," = "]); rule:=[op(rule),str]; else str:=StringTools[CaseJoin]([b[j]," and "]); rule:=[op(rule),str]; fi; od; str:=StringTools[CaseJoin]([b[nops(b)-1]," then ",target_attribute," = ",b[nops(b)]]); rule:=[op(rule),str]; rule:=StringTools[CaseJoin](rule); rule:=StringTools[CaseJoin](["if ",rule]); rules:=[op(rules),rule]; rule:=[]; od; RETURN (rules); end: HƯỚNG DẪN SỬ DỤNG CHƯƠNG TRÌNH Đặt biến môi trường như mục 3.1 Tạo thư mục ID3 tại thư mục gốc ổ đĩa C (tức là thư mục ID3 có đường dẫn như sau “C:\ID3\”). Sau đó chạy tập tin ID3.mw với phần mềm Maple để đóng gói thuật toán thành package lưu vào thư mục vừa tạo ở trên. Chạy project ID3 với NetBeans. Giao diện chương trình như sau: Có thể tạo tập ví dụ huấn luyện bằng một trong hai cách sau: Tạo mới một Table: bằng cách nhập số cột (vào mục Column Count) và số dòng (vào mục Row Count) rồi bấm nút Create Table. Bấm nút Read From File để tải từ một tập tin Training Examples sẵn có với cấu trúc giống như mô tả trong mục 4.2.2 Bấm nút Show Rules để chuyển cây về các luật. Bấm nút Show Decision Tree để tiến hành phân loại, hiển thị cây quyết định. MỘT SỐ VÍ DỤ VÀ KẾT QUẢ CHƯƠNG TRÌNH PlayTennis training examples Tiến hành cho chương trình phân loại với ví dụ đã phân tích ở mục 2.3. Tập ví dụ huấn luyện đã có sẵn (tập tin TrainingExamples1.txt đính kèm). Hiển thị luật. Hiển thị cây quyết định. Phân lớp cho New Instance mới: x:=[Sunny,Hot,High,Weak] Kết quả sau khi phân lớp: PlayTennis = No Chương trình cho kết quả chính xác với phần phân tích lí thuyết (mục 2.3). EnjoySport training examples Tải tập ví dụ huấn luyện đã có sẵn (tập tin TrainingExamples3.txt trong cùng thư mục). Hiển thị luật. Hiển thị cây quyết định. Phân lớp cho New Instance mới: x:=[Sunny,Warm,Noraml,Weak,Warm,Same] Kết quả sau khi phân lớp: EnjoySport = No Sunburned training examples Tải tập ví dụ huấn luyện đã có sẵn (tập tin TrainingExamples3.txt trong cùng thư mục). Hiển thị luật. Hiển thị cây quyết định. Phân lớp cho New Instance mới: x:=[blonde,average,light,no] Kết quả sau khi phân lớp: Result = sunburned Chương 3: THUẬT TOÁN CANDIDATE ELIMINATION 1. MÔ TẢ THUẬT TOÁN Thuật toán Candidate-Elimination tính version space chứa tất cả những giả thiết phù hợp với tập các ví dụ huấn luyện. Bắt đầu bằng việc khởi tạo version space để chứa tất cả những giả thiết trong H, khởi tạo G là tập các giả thiết tổng quát nhất trong H Go ß {} và khởi tạo S là tập các giả thiết cụ thể nhất So ß {} Hai tập G, S này bao đóng toàn bộ giả thiết, bởi vì mỗi giả thiết trong H đều tổng quát hơn So và đặc thù hơn Go. Với mỗi ví dụ huấn luyện, S và G sẽ được tổng quát hóa và đặc thù hóa để loại bỏ từ version space bất kỳ những giả thiết nào tìm thấy là không phù hợp. Sau tất cả những ví dụ, version space đã tính sẽ bao đóng tất cả những giả thiết phù hợp với những ví dụ huấn luyện và chỉ với những ví dụ huấn luyện này. Thuật toán Candidate Elimination được viết dưới dạng mã giả như sau: G ß các giả thiết tổng quát nhất trong H S ß các giả thiết đặc thù nhất trong H Với mỗi ví dụ huấn luyện d, thực hiện: 1/ Nếu d là một positive example Xóa từ trong G tất cả các giả thiết inconsistent với d Đối với mỗi giả thiết s trong S mà inconsistent với d Xóa s trong S Thêm vào S tất cả các giả thiết h được tổng quát hóa tối thiểu từ s, sao cho: a/ h consistent với d, và b/ Một số giả thiết trong G tổng quát hơn h. Xóa từ S bất kỳ giả thiết nào tổng quát hơn các giả thiết khác trong S. 2/ Nếu d là một negative example Xóa trong S bất kỳ giả thiết nào inconsistent với d. Đối với mỗi giả thiết g trong G mà inconsistent với d Xóa g trong G. Thêm vào G tất cả các giả thiết h được đặc thù hóa tối thiểu từ g, sao cho: a/ h consistent với d, và b/ Một số giả thiết trong S đặc thù hơn h. Xóa trong G tất cả các giả thiết nào ít tổng quát hơn các giả thiết khác trong G. 2. CÀI ĐẶT THUẬT TOÁN 2.1 Hướng dẫn sử dụng chương trình: - Chương trình cài đặt thuật toán Candidate Elimination sử dụng ngôn ngữ Java và Maple, IDE Netbeans. Dùng Maple để cài đặt thuật toán Candidate Elimination (file CE.mw đính kèm), sau đó dùng Java, kết nối với Maple để thực hiện những hàm trong package CandidateEliminationAlgorithm mà file CE.mw đã tạo ra để thể hiện kết quả lên form trong Java (project CandidateElimination của Netbeans đính kèm). - Để có thể chạy được chương trình, các bước cần phải thực hiện: + Cài đặt IDE Netbeans và phần mềm Maple. + Đặt biến môi trường để Java có thể kết nối với Maple: Click chuột phải vào MyComputer à Properties (có thể dùng phím tắt Windows+Break) à Advanced (nếu là Win XP, còn Win Vista hay Win 7 thì chọn Advanced system settings) à Environment Variables. Ở mục System Variables, tìm dòng có chữ “Path” à chọn dòng này rồi click Edit à trên dòng có chứa “Variable Value” di chuyển đến cuối -> đặt dấu chấm phẩy (;) rồi paste đường dẫn thư mục bin.win trong thư mục cải đặt của Maple vào (thường là C:\Program Files\Maple 12\bin.win), chọn OK, sau đó khởi động lại máy (chú ý bước khởi động lại máy quan trọng vì sau khi khởi động Windows mới nhận được biến môi trường mới thêm vào). + Tạo thư mục CandidateElimination trong ổ C (C:/CandidateElimination). Sau đó mở file CE.mw bằng Maple, click vào nút có kí hiệu là “!!!” (Excute the entire worksheet) để Maple build thành package CandidateEliminationAlgorithm, sau khi build xong package sẽ nằm trong thư mục C:/CandidateElimination. + Dùng IDE Netbeans để mở project CandidateElimination (file đính kèm), sau đó nhấn F6 để Run project. - Chương trình có thể cho người dùng tự nhập tập ví dụ huấn luyện trên form hoặc đọc file ví dụ huấn luyện có sẵn, định dạng file là *.txt và mỗi dòng sẽ là mỗi ví dụ huấn luyện, ngoại trừ dòng đầu tiên là các thuộc tính, mỗi thuộc tính hay mỗi giá trị của thuộc tính sẽ được ngăn cách bởi khoảng trắng hay tab và nếu thuộc tính hay giá trị có từ 2 từ trở lên thì viết liền nhau, không có khoảng trắng, nhằm phân biệt thuộc tính này với thuộc tính khác, giá trị này với giá trị khác. Giá trị của thuộc tính phân loại sẽ là được ghi là “Positive” nếu giá trị đó thuộc loại positive, ngược lại là “Negative” nếu giá trị đó thuộc loại negative. Kết quả trả về sau khi người dùng bấm nút Show (Show Version Space) sẽ là giá trị của S và G bao đóng tất cả các giả thiết phù hợp tập ví dụ huấn luyện. Còn khi người dùng muốn phân loại một ví dụ mới, thì nhập ví dụ đó vào theo cấu trúc [Value, Value, , Value] trong Text Field New Instance, sau đó khi nhấn button Classification thì sẽ sẽ cho ra kết quả 1 trong 3 kết quả phân loại là Positive, Negative, hay Don’t Know - Ngoài ra chương trình vẫn có thể chạy trong Maple mà không kết nối với Java (file demo.mw đính kèm). 2.2 Cài đặt thuật toán: - Hàm chính cài đặt thuật toán Candidate Elimination trong Maple như sau: > Tính version space chứa những giả thiết phù hợp với training examples D CandidateElimination:=proc(D::list) G: giả thiết tổng quát nhất S: giả thiết đặc thù nhất d: mỗi ví dụ huấn luyện V: danh sách tập hợp các giá trị đã xuất hiện cho từng thuộc tính tính đến thời điểm đang xét ví dụ thứ i x: danh sách lưu mỗi ví dụ, không bao gồm giá trị phân loại cx: bằng 1 nếu giá trị của thuộc tính phân loại là positive, bằng 0 nếu là negative local G,S,d,V,x,cx,g,s,i,j,tmp; G:=[]; S:=[]; V:=[]; G ← giả thiết tổng quát nhất trong H S ← giả thiết đặc thù nhất trong H for i from 1 to nops(D[1][1]) do G:=[op(G),`?`]; S:=[op(S),` `]; V:=[op(V),{}]; od; G:=[[op(G)]]; S:=[[op(S)]]; V:=[op(V)]; Với mỗi ví dụ huấn luyện d, thực hiện: for d in D do x:=d[1]; cx:=d[2]; for i from 1 to nops(x) do if not member(x[i],V[i]) then V[i]:=V[i] union {x[i]}; fi; od; Nếu d là 1 positive example if cx=1 then Xóa từ trong G tất cả các giả thiết inconsistent với d for g in G do if Consistent(g,d)=false then G:=DeleteHypothesis(G,g); fi; od; Đối với mỗi giả thiết s trong S mà inconsistent với d for s in S do if Consistent(s,d)=false then Xóa s trong S S:=DeleteHypothesis(S,s); Thêm vào s tất cả các giả thiết h được tổng quát hóa tối thiểu từ S, sao cho: h consistent với và một số giả thiết trong G tổng quát hơn h S:=[op(S),MinimalGeneralizations(s,d,G)]; Xóa từ S bất kỳ giả thiết nào tổng quát hơn các giả thiết khác trong S tmp:=S; for i from 1 to nops(S) do for j from 1 to nops(S) do if ji then if MoreGeneralThan(S[i],S[j]) then tmp:=DeleteHypothesis(tmp,S[i]); fi; fi; od; od; S:=tmp; fi; od; Nếu d là một negative example else Xóa trong S bất kỳ giả thiết nào inconsistent với d for s in S do if Consistent(s,d)=false then S:=DeleteHypothesis(S,s); fi; od; Đối với mỗi giả thiết g trong G mà inconsistent với d for g in G do if Consistent(g,d)=false then Xóa g trong G G:=DeleteHypothesis(G,g); Thêm vào G tất cả các giả thiết h được đặc thù hóa tối thiểu từ g, sao cho: h consistent với d và một số giả thiết trong S đặc thù hơn h G:=[op(G),op(MinimalSpecializations(g,d,S,V))]; Xóa trong G tất cả các giả thiết nào ít tổng quát hơn các giả thiết khác trong G tmp:=G; for i from 1 to nops(G) do for j from 1 to nops(G) do if ji then if MoreGeneralThan(G[i],G[j]) then tmp:=DeleteHypothesis(tmp,G[j]); fi; fi; od; od; G:=tmp; fi; od; fi; od; RETURN (G,S); end: - Hàm phân lớp New Instance: > Phân loại lớp của new_instance đưa vào trên Version Space Classification:=proc(S,G,new_instance::list) H: tập giả thiết từ S và G h: mỗi giả thiết trong H local class,H,i,count; Tập giả thiết H từ Version Space H:=Hypotheses(S,G); count:=0; for i from 1 to nops(H) do if hx(H[i],new_instance)=1 then Đếm số giả thiết trong H phù hợp với new_instance count:=count+1; fi; od; Nếu tất cả các giả thiết trong H phù hợp với new_instance if count=nops(H) then new_instance thuộc lớp Positive class:=`Positive`; Không có giả thiết nào phù hợp với new_instance elif count=0 then new_instance thuộc lớp Negative class:=`Negative`; else Không phân được lớp cho new_instance class:=`DontKnow`; fi; RETURN (class); end: Phát sinh ra tập giả thiết H từ Version Space Hypotheses:=proc(S,G) local H; H:=GeneralThan(S[1]); H:=[op(S),op(H),op(G)]; return (H); end: Tìm những giả thiết tổng quát hơn giả thiết h GeneralThan:=proc(h) local H,temp,count,i; H:=[]; count:=0; Đếm những giá trị khác `?` trong h for i from 1 to nops(h) do if h[i]`?` then count:=count+1; fi; od; if count>2 then for i from 1 to nops(h) do if h[i]`?` then temp:=h; temp[i]:=`?`; H:=[op(H),temp]; H:=[op(H),op(GeneralThan(temp))]; fi; od; fi; RETURN (H); end: 2.3 Chạy thử trên một số tập ví dụ huấn luyện: - Training Examples 1: Sky AirTemp Humidity Wind Water Forecast EnjoySport Sunny Warm Normal Strong Warm Same Positive Sunny Warm High Strong Warm Same Positive Rainy Cold High Strong Warm Change Negative Sunny Warm High Strong Cool Change Positive Version Space: S1 = [[Sunny, Warm, Normal, Strong, Warm, Same]] G1 = [[`?`, `?`, `?`, `?`, `?`, `?`]] S2 = [[Sunny, Warm, `?`, Strong, Warm, Same]] G2 = [[`?`, `?`, `?`, `?`, `?`, `?`]] S3 = [[Sunny, Warm, `?`, Strong, Warm, Same]] G3 = [[Sunny, `?`, `?`, `?`, `?`, `?`], [`?`, Warm, `?`, `?`, `?`, `?`], [`?`, `?`, `?`, `?`, `?`, Same]] S4 = [[Sunny, Warm, `?`, Strong, `?`, `?`]] G4 = [[Sunny, `?`, `?`, `?`, `?`, `?`], [`?`, Warm, `?`, `?`, `?`, `?`]] New Instance: x:=[Sunny,Warm,Normal,Strong,Cool,Change] Kết quả phân lớp là Positive x:=[Rainy,Cold,Normal,Light,Warm,Same] Kết quả phân lớp là Negative x:=[Sunny,Warm,Normal,Light,Warm,Same] Kết quả phân lớp là Don’t Know x:=[Sunny,Cold,Normal,Strong,Warm,Same] Kết quả phân lớp là Don’t Know - Training Examples 2: Origin Make Color Decade Type Classification Japan Honda Blue 1980 Sedan Positive Japan Toyota Green 1970 Sports Negative Japan Toyota Blue 1990 Sedan Positive USA Dodge Red 1980 Sedan Negative Japan Honda White 1980 Sedan Positive Version Space: S1 = [[Japan, Honda, Blue, `1980`, Sedan]] G1 = [[`?`, `?`, `?`, `?`, `?`]] S2 = [[Japan, Honda, Blue, `1980`, Sedan]] G2 = [[`?`, Honda, `?`, `?`, `?`], [`?`, `?`, Blue, `?`, `?`], [`?`, `?`, `?`, `1980`, `?`], [`?`, `?`, `?`, `?`, Sedan]] S3 = [[Japan, `?`, Blue, `?`, Sedan]] G3 = [[`?`, `?`, Blue, `?`, `?`], [`?`, `?`, `?`, `?`, Sedan]] S4 = [[Japan, `?`, Blue, `?`, Sedan]] G4 = [[`?`, `?`, Blue, `?`, `?`], [Japan, `?`, `?`, `?`, Sedan]] S5 = [[Japan, `?`, `?`, `?`, Sedan]] G5 = [[Japan, `?`, `?`, `?`, Sedan]] New Instance: x:= [Japan,Mazda,Black,1980,Sedan] Kết quả phân lớp là Positive - Training Examples 3: Origin Make Color Decade Type Classification Japan Honda Blue 1980 Sedan Positive Japan Toyota Green 1970 Sports Negative Japan Toyota Blue 1990 Sedan Positive USA Dodge Red 1980 Sedan Negative Japan Honda White 1980 Sedan Positive Japan Mazda Black 1980 Sedan Negative Version Space: S1 = [[Japan, Honda, Blue, `1980`, Sedan]] G1 = [[`?`, `?`, `?`, `?`, `?`]] S2 = [[Japan, Honda, Blue, `1980`, Sedan]] G2 = [[`?`, Honda, `?`, `?`, `?`], [`?`, `?`, Blue, `?`, `?`], [`?`, `?`, `?`, `1980`, `?`], [`?`, `?`, `?`, `?`, Sedan]] S3 = [[Japan, `?`, Blue, `?`, Sedan]] G3 = [[`?`, `?`, Blue, `?`, `?`], [`?`, `?`, `?`, `?`, Sedan]] S4 = [[Japan, `?`, Blue, `?`, Sedan]] G4 = [[`?`, `?`, Blue, `?`, `?`], [Japan, `?`, `?`, `?`, Sedan]] S5 = [[Japan, `?`, `?`, `?`, Sedan]] G5 = [[Japan, `?`, `?`, `?`, Sedan]] S cannot be generalized. ( S = [] ) G cannot be specialized. ( G = [] ) TÀI LIỆU THAM KHẢO [1] Tom M. Mitchell, Machine Learning, The McGraw-Hill Companies, Inc., 1997. [2] Lê Thành Sách, Trí tuệ nhân tạo, ĐH Bách khoa – ĐHQG TPHCM. [3] Võ Văn Thành, Bài tập Luật phân lớp , ĐH CNTT – ĐHQG TPHCM. [4] Võ Huỳnh Trâm & Trần Ngân Bình, Học máy. [5] Howard J.Hamilton, Computer Science 831 course, Department of Computer Science, University of Regina, Canada: [6]Wikipedia – ID3 Algorithm: [7] Maplevn2008’s Blog – Blog hướng dẫn sử dụng và lập trình trên Maple.