CHƯƠNG 2: MỘT SỐ KỸ THUẬT PHÂN LỚP
2.4. Phân lớp dựa trên câu quyết định (Decision Tree)
2.4.1. Khái niệm cây quyết định
Cây quyết định (Decision Tree) là một cây phân cấp có cấu trúc đƣợc dung để phân lớp các đối tƣợng dựa vào dãy các luật (series of rules).
Các thuộc tính của đối tƣợng (ngoại trừ thuộc tính phân lớp – Category attribute) có thể thuộc các kiểu dữ liệu khác nhau (Binary, Nominal, ordinal, quantitative values) trong khi đó thuộc tính phân lớp phải có kiểu dữ liệu là Binary hoặc Ordinal.
Việc xây dựng cây quyết định đƣợc tiến hành một cách đệ qui, lần lƣợt từ nút gốc xuống tới tận nút lá. Tại mỗi nút hiện hành đang xét, nếu kiểm tra thấy thỏa điều kiện dừng: thuật toán sẽ tạo nút lá. Nút này đƣợc gán một giá trị của nhãn lớp tùy điều kiện dừng đƣợc thỏa. Ngƣợc lại, thuật toán tiến hành chọn điểm chia tốt nhất theo một tiêu chí cho trước, phân chia dữ liệu hiện hành theo điều kiện chia này. Lưu ý dữ liệu hiện hành không phải hoàn toàn là tập dữ liệu ngay khi bắt đầu thuật toán, có thể là tập dữ liệu đã được phân chia theo điều kiện chia của nút liền trước đó (nút cha).
2.4.1.1. Giải thuật qui nạp cây quyết định (ID3):
Giải thuật quy nạp cây quyết định (gọi tắt là ID3) là một giải thuật học đơn giản nhƣng tỏ ra thành công trong nhiều lĩnh vực. ID3 là một giải thuật 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 (concept) ở dạng các cây quyết định (decision tree). 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 giải thuật ID3 là học cây quyết định từ một tập các ví dụ rèn luyện (training example) hay còn gọi là dữ liệu rèn luyện (training data). Hay nói khác hơn, giải thuật 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 rèn luyện, và hy vọng là phân loại đúng cho cả các ví dụ chưa gặp trong tương lai.
Giải thuật cơ bản (giải thuật tham lam) được chia thành các bước như sau:
1. Cây được xây dựng đệ qui từ trên xuống dưới (top-down) và theo cách thức chia để trị (divide-conquer).
2. Ở thời điểm bắt đầu , tất cả những ví dụ huấn luyện ở gốc.
3. Thuộc tính đƣợc phân loại ( nếu là giá trị liên tục chúng đƣợc rời rạc hóa).
4. Những ví dụ huấn luyện đƣợc phân chia đệ qui dựa trên thuộc tính mà nó chọn lựa.
5. Kiểm tra những thuộc tính đƣợc chọn dựa trên nền tảng của heristic hoặc của một định lƣợng thống kê.
Điều kiện để dừng việc phân chia:
1. Tất cả những mẫu huấn luyện đối với một node cho trước thuộc về cùng một lớp.
2. Không còn thuộc tính còn lại nào để phân chia tiếp.
3. Không còn mẫu nào còn lại.
2.4.1.2. Độ lợi thông tin (Information Gain) trong cây quyết định:
Độ lợi thông tin là đại lƣợng đƣợc sử dụng để chọn lựa thuộc tính với độ lợi thông tin lớn nhất. Giả sử có hai lớp, P và N. Cho tập hợp của những ví dụ S chứa p phần tử của lớp P và n phần tử của lớp N. Khối lƣợng của thông tin, cần để quyết định nếu những mẫu tùy ý trong S thuộc về P hoặc N đƣợc định nghĩa nhƣ là :
I(p,n) = -[p/(p+n)]log 2 [p/(p+n)] – [n/(p+n)]log 2 [n/(p+n)]
Giả sử rằng sử dụng thuộc tính A một tập hợp S đƣợc phân hoạch thành những tập hợp {S1,S2,..,Sv}. Nếu Si chứa những mẫu của P và ni mẫu của Ni entropy
hoặc thông tin mong đợi cần để phân loại những đối tƣợng trong cây con Si là :
E( A) [( v pi ni ) /( p n)]I ( pi, ni ) i
1
Thông tin nhận đƣợc ở nhánh A là: Gain(A) = I(p,n)-E(A) 2.4.1.3. Nội dung giải thuật học cây quyết định cơ bản ID3:
ID3 là một giải thuật học cây quyết định đƣợc phát triển bởi Ross Quinlan (1983). Ý tưởng cơ bản của giải thuật ID3 là để xây dựng cây quyết định bằng việc sử dụng một cách tìm kiếm từ trên xuống trên những tập hợp cho trước để kiểm tra mỗi thuộc tính tại mỗi nút của cây. Để chọn ra thuộc tính mà hữu ích nhất cho sự phân loại trên những tập hợp cho trước, chúng ta sẽ đƣa ra một hệ số độ lợi thong tin.
Để tìm ra một cách tối ƣu để phân loại một tập hợp thông tin, vấn đề đặt ra là chúng ta cần phải làm tối thiểu hóa (chẳng hạn, tối thiểu chiều cao của cây). Nhƣ vậy chúng ta cần một số chức năng mà có thể đánh giá trường hợp nào cho ra một sự phân chia cân bằng nhất. Hệ số độ lợi thông tin sẽ là hàm nhƣ vậy.
ID3 ( Learning Sets S, Attributes Sets A, Attributesvalues V) Return Decision Tree.
Begin Đầu tiên nạp các tập học dữ liệu, tạo nút gốc cho cây quyết định 'rootNode', thêm learning set S vào trong nút gốc nhƣ là tập con của nó.
For rootNode, đầu tiên chúng ta tính Entropy(rootNode.subset) If
Entropy(rootNode.subset)==0, thenrootNode.subset bao gồm records tất cả với cùng giá trị cho cùng giá trị thuộc tính xác định, trả về một nút lá với decision attribute:attribute value; If Entropy(rootNode.subset)!=0,then
Tính độ lợi thông tin (information gain) cho mỗi thuộc tính trái (chƣa đƣợcsử dụng để phân chia), tìm thuộc tính A với Maximum(Gain(S,A)). Tạo những nút con của rootNode này và thêm vào rootNode trong cây quyết định.
For mỗi con của rootNode, áp dụng ID3(S,A,V) một cách đệ qui cho đến khi đạt đƣợc node mà có entropy=0 hay đạt đƣợc nút lá.
End ID3. Ví dụ :
Để mô tả hoạt động của ID3 chúng ta sử dụng ví dụ “Play Tennis”. Sự mô tả tƣợng trƣng thuộc tính nhƣ sau:
Attribute Possible Values: Outlook sunny, overcast, rain Temperature hot, mild, cood Humidity high, normal Windy true, false
Decision n(negative), p(positive) Tập Leaning set cho ví dụ chơi tennis:
Outlook Temperatur e
Humidity Windy Decision
sunny hot high false n
sunny hot high True n
overcast hot high false p
rain mild high false p
rain cool normal false p
rain cool normal false n
overcast cool normal True p
sunny mild high false p
sunny mild normal True p
rain mild normal false p
sunny mild normal True p
overcast mild high True p
overcast hot normal false p
rain mild high True n
Giải thuật ID3 thực hiện nhƣ sau :
1. Tạo nút gốc( rootNode), chứa đựng toàn bộ learning set nhƣ là những tập hợp con của chúng (subset) sau đó tính :
Entropy(rootNode.subset)= -(9/14)log 2 ( 9/14 ) – ( 5/14)log 2 (5/14)= 0.940 2. Tính toán thông tin nhận đƣợc cho mỗi thuộc tính :
Gain(S,Windy)= Entropy(S)-(8/14)Entropy(S false) – (6/14)Entropy(S true) = 0.048
Gain(S,Humidity) = 0.151 Gain(S,Temperature) = 0.029
Gain(S,Outlook) = 0.246
3. Chọn lựa những thuộc tính với thông tin nhận đƣợc tối đa, đó chính là sự phân chia theo thuộc tính “outlook”.
4. Áp dụng ID3 cho mỗi nút con của nút gốc này, cho đến khi đạt đến nút lá hoặc nút có entropy = 0.
2.4.1.4. Những thiếu sót của giải thuật ID3:
Trường hợp thiếu sót thứ nhất :
Một thiếu sót quan trọng của ID3 là không gian phân chia hợp lệ tại một node là cạn kiệt. Một sự phân chia là sự phân hoạch của mỗi trường hợp của không gian mà kết quả đạt đƣợc từ việc thử nghiệm tại một node quyết định ID3 và con cháu của nó cho phép sự kiểm tra tại tại một thuộc tính đơn và nhánh trong kết quả cho ra từ sự kiểm tra này.
Trường hợp thiếu sót thứ hai:
Một thiếu sót mà ID3 mắc phải là nó dựa vào rất nhiều vào số lƣợng của những tập hợp dữ liệu đƣa vào. Quản lý sự tạp nhiễu của tập dữ liệu vào là vô cùng quan trọng khi chúng ta ứng dụng giải thuật học cây quyết định vào thế giới thực. Cho ví dụ, khi có sự lẫn tạp trong tập dữ liệu đƣa vào hoặc khi số lƣợng ví dụ đƣa vào là quá nhỏ để tạo ra một ví dụ điển hình của hàm mục tiêu đúng. ID3 có thể dẫn đến việc tạo quyết định sai.
Có rất nhiều những mở rộng từ giải thuật ID3 cơ bản đã phát triển để áp dụng những luật học cây quyết định vào thế giới thực, nhƣ là những post-pruning tree, quản lý những thuộc tính giá trị thực, liên quan đến việc thiếu những thuộc tính, sử dụng những tiêu chuẩn chọn lựa thuộc tính khác hơn thu thập thông tin.
2.4.1.5. Mở rộng qui nạp cây quyết định cơ bản:
Việc mở rộng qui nạp cây quyết định đƣợc áp dụng cho những thuộc tính giá trị liên tục: Định nghĩa một cách uyển chuyển những thuộc tính giá trị bị rời rạc mà sự phân chia giá trị thuộc tính thành một tập rời rạc của những khoảng.
Mở rộng qui nạp cây quyết định cũng đƣợc áp dụng cho những giá trị thuộc tính thiếu sót bằng cách: Gán những giá trị thiếu sót bằng giá trị thông thường nhất của thuộc tính hoặc gán khả năng có thể với mỗi giá trị có thể.
Việc mở rộng qui nạp cây quyết định cũng đƣợc áp dụng cho xây dựng thuộc tính: Tạo những thuộc tính dựa trên những cái đã tồn tại mà chúng thể hiện thƣa thớt. Điều này sẽ giúp thu giảm việc phân mảnh, sự lặp lại và việc tạo bản sao.
2.4.1.6. Giải thuật mở rộng C4.5
C4.5 là sự mở rộng của giải thuật ID3 trên một số khía cạnh sau:
Trong việc xây dựng cây quyết định, chúng có thể liên hệ với tập huấn luyện mà có những bảng ghi với những giá trị thuộc tính không đƣợc biết đến bởi việc đánh giá việc thu thập thông tin hoặc là tỉ số thu thập thông tin, cho những thuộc tính bằng việc xem xét chỉ những bảng ghi mà ở đó thuộc tính đƣợc định nghĩa.
Trong việc sử dụng cây quyết định, chúng ta có thể phân loại những bảng ghi mà có những giá trị thuộc tính không biết bằng việc ƣớc lƣợng những kết quả có khả năng xãy ra. Trong ví dụ chơi đánh gôn của chúng
ta, nếu chúng ta đƣợc đƣa một bảng ghi mới mà outlook là sunny và humidity chƣa cho biết, chúng ta sẽ xử lý nhƣ sau:
Chúng ta di chuyển từ nút gốc Outlook đến nút Humidity theo cung đƣợc đánh nhãn là sunny. Ở điểm đó từ lúc chúng ta không biết giá trị của Humidity chúng ta để ý rằng nếu humidity là ở 75 có 2 bảng ghi, và nếu humidity là lớn hơn
75 có 3 bảng ghi trong đó có 1 bảng ghi không hoạt động. Nhƣ vậy điều đó có thể đƣa ra nhƣ câu trả lời cho bảng ghi khả năng (0.4,06) cho chơi gôn hoặc không chơi gôn.
Chúng ta có thể liên hệ đến những giá trị liên tục. Giả sử rằng thuộc tính Ci có tầm giá trị thuộc tính liên tục. Chúng ta sẽ xem xét những giá trị này trong tập học. Cho rằng chúng đƣợc xắp sếp thứ tự tăng dần A1, A2,..,Am sau đó với mỗi giá
trị Ai với i=1,2,..,m. Chúng ta chia những bảng ghi thành những cái có giá trị từ Ci trở lên và bao gồm cả Aj và những cái có những giá trị lớn hơn Aj. Với những lần phân hoạch này chúng ta tính lại giá trị thu thập và tỉ số thu thập và chọn ra phân hoạch có tỉ số thu thập thông tin nhận đƣợc tối đa.
Trong ví dụ về chơi Golf của chúng ta, đối với humidity T là tập huấn luyện chúng ta sẽ xác định thông tin cho mỗi lần phân chia và tìm đƣợc sự phân chia tốt nhất tại 75. Phạm vi của thuộc tính này trở thành {<=75,>75}.
Chú ý rằng phương pháp này liên quan đến một con số quan trọng của việc tính toán.
2.4.1.7. Thu giảm cây quyết định và những tập luật suy dẫn
Việc xây dựng cây quyết định nhờ vào tập huấn luyện bởi vì cách chúng xây dựng liên quan nghiêm ngặt đến hầu hết các bảng ghi trong tập
huấn luyện. Trong thực tế, để làm nhƣ vậy nó có thể là điều hoàn toàn phức tạp. Với những đường đi dài và không đều.
Việc thu giảm cây quyết định đƣợc thực hiện bằng việc thay thế những cây con thành những nút lá. Sự thay thế này sẽ đƣợc thực hiện tại nơi mà luật quyết định đƣợc thiết lập nếu tần suất lỗi gây ra trong cây con là lớn hơn trong một nút lá.
Cho ví dụ với cây đơn giản nhƣ sau:
\
Trong cây quyết định trên ta nhận thấy cây quyết định có chứa 2 bảng ghi; bảng ghi thứ nhất là màu đỏ huấn luyện thành công và bảng ghi thứ hai là màu xanh huấn luyện không thành công và sau đó trong thực hiện kiểm thử chúng ta tìm thấy
3 màu đỏ không thành công và một màu xanh thành công, chúng ta có thể xem xét việc thay thế cây con này bằng việc thay thế bằng một node đơn không thành công. Sau việc thay thế này chúng ta sẽ còn lại 2 lỗi thay vì 5 lỗi.
Winston chỉ ra rằng làm thế nào để sử dụng Fisher's exact test để xác định nếu thuộc tính phân loại là thực sự phụ thuộc vào một thuộc tính không xác định.
Nếu điều này không xảy ra thì thuộc tính không xác định không cần phải xuất hiện trong đường đi hiện tại của cây quyết định.
Quinlan và Breiman đề nghị những heuristic phức tạp hơn cho việc
Đỏ xanh
Màu
Thành công
Không thành công
thu giảm cây quyết định. Một điều dễ dàng làm là có thể dẫn ra một luật từ một cây quyết định: viết ra một luật từ mỗi đường trong cây quyết định đi từ gốc đến lá. Vế trái của luật đƣợc xây dựng dễ dàng từ nhãn của những nút và nhãn của những cung.
Những luật rút ra có thể đƣợc rút gọn nhƣ sau:
Gọi LHS là LHS của luật Cho LHS’ nhận đƣợc bằng cách thu giảm một số điều kiện của LHS. Chúng ta có thể chắc chắn thay thế LHS bằng LHS’ trong luật này nếu tập con của training set thỏa mãn LHS và LHS’ là tương đương.
Một luật có thể đƣợc thu giảm bằng cách sử dụng siêu nhận thức, ví dụ nhƣ “không có luật khác có thể áp dụng ”.
2.4.1.8. Giải thuật mở rộng See5/C5.0:
“See5 là một dạng nghệ thuật của hệ thống xây dựng sự phân loại trong dạng thức của những cây quyết định và tập luật .”
See5 đã đƣợc thiết kế và hoạt động trên cơ sở dữ liệu lớn và sự kết hợp đổi mới như là boosting. Kết quả tạo ra bởi See5 và C5.0 là tương tự nhau. Hoạt động trước đây trên Windows95/98/NT của C5.0 là phần hoạt động của nó trên Unix . See 5 và C5.0 là những công cụ khai khái dữ liệu phức tạp cho những mẫu khai phá dữ liệu mà phát họa ra những loại tập hợp chúng thành những đối tƣợng phân loại và sử dụng chúng để tiên đoán.
Đặc điểm chính của C5.0 là:
C5.0 đƣợc thiết kế để phân tích những cơ sở dữ lịêu quan trọng chứa đựng hàng ngàn đến hàng trăm ngàn những bảng ghi và hàng chục đến hàng trăm số liệu và hoặc tên trường.
Để tối đa khả năng giải thích, đối tƣợng phân loại của See5.0/C5.0 đƣợc diễn tả nhƣ là cây quyết định hoặc tập của những luật if – then. Dạng thức của nó dễ hiểu hơn so với mạng nơron.
C5.0 dễ dàng sử dụng do đó không đƣợc gọi là kiến thức cao cấp của thống kê và máy học .
2.4.1.9. So sánh giữa giải thuật see/c5.0 với C4.5:
C5.0 trong hệ thống Unix và bản sao của nó See5 trong Windows là những phiên bản cao cấp hơn C4.5 trên nhiều khía cạnh quan trọng.
Chúng ta sẽ thử so sánh C5.0 và C4.5 trên cùng hệ thống Unix.
+ Về những tập luật (Ruleset):
Cả C5.0 và C4.5 cung cấp sự lựa chọn cho những dạng thức của phân loại – cây quyết định hoặc là những tập luật (ruleset). Trong nhiều ứng dụng thì tập luật (ruleset) đƣợc ƣu tiên sử dụng hơn vì chúng đơn giản và dễ hiểu hơn cây quyết định. Nhưng những phương pháp để tìm ra luật trong C4.5 là chậm và chiếm nhiều bộ nhớ. C5.0 thể hiện sự hoàn thiện trong vấn đề tạo ra tập luật và sự cải tiến này là gây ấn tƣợng mạnh mẽ.
+ Cây quyết định:
Với cùng những tập dữ liệu (dataset) thì C4.5 và C5.0 sản sinh ra những luật với sự chính xác về dự đoán là nhƣ nhau. Sự khác nhau chính yếu là kích cỡ của cây và thời gian tính toán. Cây của C5.0 là nhỏ hơn và nhanh hơn ở một số yếu tố.
+ Sự nâng lên (Boosting):
Dựa trên sự nguyên cứu của Freund và Schapire, đây là sự phát triển mới đầy hấp dẫn mà nó không có sự tương tự nào trong C4.5. Boosting là một kỹ thuật để tạo và kết hợp nhiều những đối tƣợng phân loại để cải thiện tính chính xác dự đoán.
C5.0 hỗ trợ Booting với một số những dữ liệu số thử nghiệm. Thông thường, C5.0 sẽ mất thời gian lâu hơn để tạo ra những đối tượng phân loại (classifier). Nhƣng những kết quả có thể phân tích định lƣợng sự tính toán cộng thêm. Boosting luôn cố gắng để đạt đƣợc đỉnh cao nhất của sự