intTypePromotion=3 
Array
(
    [0] => Array
        (
            [banner_id] => 140
            [banner_name] => KM1 - nhân đôi thời gian
            [banner_picture] => 964_1568020473.jpg
            [banner_picture2] => 839_1568020473.jpg
            [banner_picture3] => 620_1568020473.jpg
            [banner_picture4] => 994_1568779877.jpg
            [banner_picture5] => 
            [banner_type] => 8
            [banner_link] => https://tailieu.vn/nang-cap-tai-khoan-vip.html
            [banner_status] => 1
            [banner_priority] => 0
            [banner_lastmodify] => 2019-09-18 11:11:47
            [banner_startdate] => 2019-09-11 00:00:00
            [banner_enddate] => 2019-09-11 23:59:59
            [banner_isauto_active] => 0
            [banner_timeautoactive] => 
            [user_username] => sonpham
        )

)
 » 
 » 

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

Chia sẻ: Ngọc Hưng | Ngày: | Loại File: DOCX | Số trang:47

0
Thêm vào BST
Báo xấu
75
lượt xem 22
download

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

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Với kết cấu nội dung gồm 3 chươ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ới thiệu đến các bạn những nội dung về thuật toán Find-s, thuật toán Id3, thuật toán Candidate Elimination. Mời các bạn cùng tham khảo nội dung bài thu hoạch để có thêm tài liệu phục vụ nhu cầu học tập và nghiên cứu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

  1. 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 GV: PGS. TS. Đỗ Văn Nhơn HVTH: Huỳnh Tuấn Anh
  2. Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple 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 GV: PGS. TS. Đỗ Văn Nhơn HVTH: Huỳnh Tuấn Anh
  3. Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple Mục Lục GV: PGS. TS. Đỗ Văn Nhơn HVTH: Huỳnh Tuấn Anh
  4. Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple Chương 1: THUẬT TOÁN FIND­S 1. 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.” 1.1.  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ụ: o (Input) Các ví dụ huấn luyện:  Tập các animal cùng thuộc tính của nó. o (Output) Khái niệm được trích ra:  Bird  Cat  … 1.2.  Bài toán cụ thể ­ (Input) Tập ví dụ huấn luyện gồm 4 cá thể sau: o 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). Exampl AirTem Sky Humidity Wind Water Forecast EnjoySport e p 1 Sunny Warm Normal Strong Warm Same Positive 2 Sunny Warm High Strong Warm Same Positive 3 Rainy Cold High Strong Warm Change Negative GV: PGS. TS. Đỗ Văn Nhơn 4 HVTH: Huỳnh Tuấn Anh
  5. Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple 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” 1.3. 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à: o ­ Giả thiết tổng quát nhất: o ­ Giả thiết cụ thể nhất: o 1.4. Ký hiệu ­ Tập cá thể (set of instances) o Tập được dùng để trích khái niệm từ đó o Ký hiệu: X o 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) o Khái niệm (hàm) được học. o 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ó: o Một cá thể thuộc X. o Khái niệm đích c(X). Viết là:  GV: PGS. TS. Đỗ Văn Nhơn 5 HVTH: Huỳnh Tuấn Anh
  6. Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple ­ 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:  o Cho trước tập ví dụ huấn luyện. o Đưa ra giả thiết về sự phân loại tập cá thể: h(X) = c(X) 1.5.  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ự: o hj và hk là hai giả thiết. o 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)] o Ký hiệu: hj ≥g hk ­ Ví dụ: h2 ≥g h1 với h1 và h2 sau: o h1 =  o h2 =  2. THUẬT TOÁN FIND – S: TÌM MỘT GIẢ THUYẾT ĐẶC THÙ NHẤT 2.1. Thuật toán Find­S 1. h = giả thiết cụ thể nhất trong H. 2. Với mỗi x Є tập ví dụ huấn luyện, mà c(X) = 1 o 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 GV: PGS. TS. Đỗ Văn Nhơn 6 HVTH: Huỳnh Tuấn Anh
  7. Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple 3. Xuất ra h. 2.2.  Áp dụng thuật toán với ví dụ huấn luyện mục 1.2: ­ h   ­ Cá thể 1 (positive): o h   ­ Cá thể 2 (positive): o h   ­ Cá thể 3 (negative): h không đổi. ­ Cá thể 4 (positive): o h   ­ OUTPUT:  3. CÀI ĐẶT CHƯƠNG TRÌNH 3.1. 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: o Mục đích: kết nối Maple với Java o Cách đặt biến môi trường:  Click chuột phải vào My computer, chọn Properties. GV: PGS. TS. Đỗ Văn Nhơn 7 HVTH: Huỳnh Tuấn Anh
  8. Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple  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: o com.maplesoft.openmaple.* : import các lớp OpenMaple của Java. o 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. 3.2. Cấu trúc, chức năng các tập tin cài đặt và tập tin training examples 3.2.1. 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). 3.2.2. 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. GV: PGS. TS. Đỗ Văn Nhơn 8 HVTH: Huỳnh Tuấn Anh
  9. Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple ­ 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. 3.3. 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: o public Main() throwMapleException:  Khởi tạo Maple Engine với Java.  Đồng thời đặt Table không có Header. o 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() o void  jButton3ActionPerformed(java.awt.event.ActionEvent evt):  Sự kiện của button ReadFromFile. o 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 o 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 GV: PGS. TS. Đỗ Văn Nhơn 9 HVTH: Huỳnh Tuấn Anh
  10. Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple         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: GV: PGS. TS. Đỗ Văn Nhơn 10 HVTH: Huỳnh Tuấn Anh
  11. Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple 4. 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: o 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. o 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. 5. MỘT SỐ VÍ DỤ VÀ KẾT QUẢ CHƯƠNG TRÌNH 5.1. EnjoySport training examples: ­ TrainingExample1.txt Sunny Warm Normal Strong Warm Same Positive GV: PGS. TS. Đỗ Văn Nhơn 11 HVTH: Huỳnh Tuấn Anh
  12. Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple 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 5.2.  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: GV: PGS. TS. Đỗ Văn Nhơn 12 HVTH: Huỳnh Tuấn Anh
  13. Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple 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 5.3.  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] GV: PGS. TS. Đỗ Văn Nhơn 13 HVTH: Huỳnh Tuấn Anh
  14. Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple  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 1. MÔ TẢ CHUNG THUẬT TOÁN ID3 VÀ BÀI TOÁN 1.1. 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. GV: PGS. TS. Đỗ Văn Nhơn 14 HVTH: Huỳnh Tuấn Anh
  15. Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple 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. 1.2. 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): Humidit Day Outlook Temp Wind PlayTennis y 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ó  GV: PGS. TS. Đỗ Văn Nhơn 15 HVTH: Huỳnh Tuấn Anh
  16. Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple 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. 2. 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. 2.1. 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. GV: PGS. TS. Đỗ Văn Nhơn 16 HVTH: Huỳnh Tuấn Anh
  17. Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple 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 
  18. Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple o 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 o Ssunny={D1,D2,D8,D9,D11} o Gain(Ssunny, Humidity) = 0.97­ (3/5)0.0 – (2/5)0.0 = 0.97 o Gain(Ssunny, Wind) = 0.97 – (2/5)1.0 –(3/5)0.918 = 0.019 o 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: GV: PGS. TS. Đỗ Văn Nhơn 18 HVTH: Huỳnh Tuấn Anh
  19. Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple ­ Bước 3: Cây cho Srain o Srain={D4,D5,D6,D10,D14}  Kết quả: GV: PGS. TS. Đỗ Văn Nhơn 19 HVTH: Huỳnh Tuấn Anh
  20. Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple ­ Điều kiện dừng: o 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. 2.4. 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 o A   Thuộc tính từ Attributes tốt nhất phân loại tập cá thể. o Thuộc tính cho root là A. (root  A) o 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. 3. CÀI ĐẶT CHƯƠNG TRÌNH 3.1. Ngôn ngữ lập trình, biến môi trường, các thư viện được sử dụng GV: PGS. TS. Đỗ Văn Nhơn 20 HVTH: Huỳnh Tuấn Anh

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.03: Bộ 280+ Luận Văn Thạc Sĩ Kinh Tế
368 tài liệu
940 lượt tải
AMBIENT
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline:0933030098

Email: support@vdoc.com.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2009-2019 TaiLieu.VN. All rights reserved.

Đồng bộ tài khoản