Introduction to ID3 algorithm - Thuật toán quy nạp cây ID3

Introduction to ID3 algorithm - Thuật toán quy nạp cây ID3 (ID3 algorithm)

http://www.cise.ufl.edu/~ddd/cap6635/Fall-97/Short-papers/2.htm

Note: một số thứ căn bản trong ML

Introduction

ID3 (Iterative Dichotomiser 3 do J. Ross Quinlan phát triển tại University of Sydney và giới thiệu năm 1986) biểu diễn các khái niệm (concept) ở dạng các cây quyết định (decision tree)

§  Input: 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ó.

§  Output: 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.

Tập huấn luyện gọi là training set bao gồm nhiều records. Mỗi record là một  tập hợp các thuộc tính (attributes). Mục tiêu là cho dữ liệu của các đối tượng cùng lớp (cùng thuộc tính lớp) của nó, xác định lớp của các đối tượng chưa biết (previously unseen) từ các thuộc tính của những đối tượng này.

Biểu diễn cây quyết định (decision tree representation)

§  Các node không phải node lá (non-leaf node) gọi là node quyết định (decision node).

§  Mỗi node là một kiểm định/một kiểm tra (a test on an attribute) trên một thuộc tính (là thuộc tính ordinal hay nomimal), mỗi giá trị của thuộc tính tương ứng với một nhánh của cây. Tức đối tượng nào đi qua node quyết định sẽ di chuyển về nhánh tương ứng.

§  Mỗi node có thể có nhiều node con (mỗi node con cho một test value).

§  Các node lá (leaf node) được gán nhãn (labeled) bởi một nhãn lớp (class label) hay là một phân lớp/loại (a classification).

§  Cây quyết định thể hiện các giả thuyết phân biệt (disjunctive hypotheses).

§  Mỗi đường dẫn tới node lá (leaf node) thể hiện một luật kết hợp (conjuctive term).

ID3 dựa trên thuật toán CLS (Concept Learning System). CLS dựa trên training set C:

§  Bước 1: nếu tất cả các instances trong C là tích cực (positive) à tạo node YES và dừng lại. Nếu tất cả tiêu cực (negative) tạo node NO và dừng lại. Nếu không chọn một tính năng F (feature), với mỗi giá trị v1, v2, …, vn và tạo ra một node quyết định

§  Bước 2: phân hoạch (partition) training set C thành các subset C1, C2, …, Cn theo các giá trị của V

§  Bước 3: áp dụng thuật toán đệ quy cho Ci

Lưu ý: người/trình huấn luyện (trainer) hay chuyên gia (expert) quyết định tính năng nào được chọn.

ID3 cải tiến CLS bằng cách thêm lựa chọn tính năng/thuộc tính (feature selection) bằng heuristic (sẽ trình bày sau). ID3 sẽ tìm trong các thuộc tính của training set thuộc tính nào có khả năng phân tách tốt nhất các ví dụ trong training set.

Nếu có thuộc tính có thể phân loại hoàn toàn training set thì ID3 sẽ dừng lại. Nếu không có thuộc tính như vậy nó sẽ hoạt động đệ quy trên n subset đã phân hoạch (partitioned subsets) để tìm thuộc tính “tốt nhất” tiếp theo. Thuật toán này sử dụng greedy search (tìm kiếm tham lam) tức luôn chọn cái tốt nhất và không bao giờ xem xét lại lựa chọn đã thực hiện.

Vì không có khả năng quay lui trong khi tìm kiếm nên nó có thể gặp phải những hạn chế giống như giải thuật leo núi, đó là hội tụ về cực tiểu địa phương. Trong quá trình tìm kiếm, giải thuật ID3 có xu hướng chọn cây quyết định ngắn hơn là những cây quyết định dài. Đây là tính chất thiên lệch quy nạp của ID3. Cây quyết định sẽ không thay đổi cho đến khi thực hiện lại việc xây dựng cây quyết định với training set mới.

Dữ liệu train của bài toán kinh điển “Có đi chơi tennis/golf hay không?” như sau (dữ liệu sample của Weka weather.arff).

§  Quang cảnh outlook {sunny, overcast, rainy}

§  Nhiệt độ temperature real (số thực)

§  Độ ẩm humidity real (số thực)

§  Gió windy {TRUE, FALSE} (binary)

§  Chơi tennis play {yes, no} (class labeled)

Outlook	Temperature	Humidity	Windy	Play
sunny	85	85	FALSE	no
sunny	80	90	TRUE	no
overcast	83	86	FALSE	yes
rainy	70	96	FALSE	yes
rainy	68	80	FALSE	yes
rainy	65	70	TRUE	no
overcast	64	65	TRUE	yes
sunny	72	95	FALSE	no
sunny	69	70	FALSE	yes
rainy	75	80	FALSE	yes
sunny	75	70	TRUE	yes
overcast	72	90	TRUE	yes
overcast	81	75	FALSE	yes
rainy	71	91	TRUE	no

Sau khi transform data thành nominal (hay dùng weather.nominal.arff):

§  Nhiệt độ temperature {hot, mild, cool}

§  Độ ẩm humidity {high, normal}

Dữ liệu như sau

Day	Outlook	Temperature	Humidity	Windy	Play
D1	sunny	hot	high	FALSE	no
D2	sunny	hot	high	TRUE	no
D3	overcast	hot	high	FALSE	yes
D4	rainy	mild	high	FALSE	yes
D5	rainy	cool	normal	FALSE	yes
D6	rainy	cool	normal	TRUE	no
D7	overcast	cool	normal	TRUE	yes
D8	sunny	mild	high	FALSE	no
D9	sunny	cool	normal	FALSE	yes
D10	rainy	mild	normal	FALSE	yes
D11	sunny	mild	normal	TRUE	yes
D12	overcast	mild	high	TRUE	yes
D13	overcast	hot	normal	FALSE	yes
D14	rainy	mild	high	TRUE	no

Trong quá trình xây dựng cây quyết định việc xác định đâu là node root (node gốc) thường thực hiện bằng cách dùng entropy.

Performance evaluation

Đánh giá cây ID3 thực hiện theo cách thông thường như hold-out (test split) sử dụng validation set với tỷ lệ khoảng 2/3.

Attribute Selection

Làm thế nào để ID3 quyết định thuộc tính nào là tốt nhất? Trong trường hợp này một thuộc tính thống kê (statistical property) được sử dụng, gọi là độ tăng thông tin hay độ lợi thông tin (information gain). Độ lợi này đo lường thuộc tính được chọn phân tách training set thành các lớp mục tiêu (targeted classes) tốt như thế nào? Attribute với IG cao nhất (thông tin hữu ích nhất cho phân loại) sẽ được chọn. Đầu tiên là tìm hiểu khái niệm entropy từ lý thuyết thông tin, entropy đo lường lượng thông tin trong một thuộc tính hay để đ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 đó tập hợp này có độ pha trộn là thấp nhất.

Khi một tập hợp là thuần nhất thì có thể biết chắc chắn về giá trị phân loại của một đối tượng (instance) thuộc tập hợp này, hay lượng thông tin có được về tập hợp đó là cao nhất. Khi một tập hợp có độ pha trộn cao nhất, nghĩa là số lượng các đối tượng có cùng giá trị phân loại cho mỗi loại là tương đương nhau, thì khi đó khó có thể đoán chính xá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.

Khái niệm entropy của một tập hợp S được định nghĩa trong Lý thuyết thông tin được giới thiệu bởi Claude E. Shannon là số lượng mong đợi các bit 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 hợp S (xem thêm entropy thông tin). Trong trường hợp tối ưu, giá trị mã hóa có độ dài ngắn nhất (ít bit nhất). Giá trị mã hóa có độ dài tối ưu là –log₂p bits cho thông điệp có xác suất là p.

Một số ví dụ:

§  Entropy(S) = 0 khi tất cả các đối tượng của S chỉ cùng 1 loại hay S thuần nhất (perfectly classified)

§  Entropy(S) = 1 khi S có độ pha trộn cao nhất (totally random)

§  0 < Entropy(S) < 1 khi S có số lượng các đối tượng thuộc các phân loại không bằng nhau

Tổng quát hơn một tập hợp S bao gồm c phân loại thì công thức tính entropy của S

${\rm{Entropy}}\left( {\rm{S}} \right) = \mathop \sum \limits_{i = 1}^c  - p\left( I \right){\log _2}p\left( I \right)$

Trong đó p(I) là tỷ lệ S thuộc lớp I.

Ví dụ cụ thể S là tập hợp có 14 đối tượng với 9 YES và 5 NO

Khi đó:

${\rm{Entropy}}\left( {\rm{S}} \right) =  - \left( {9/14} \right){\log _2}\left( {9/14} \right) - \left( {5/14} \right){\log _2}\left( {5/14} \right) = 0.940$

Tiếp theo là việc tính toán Gain(S, A) gọi là độ lợi thông tin thu được, đơ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.

${\rm{Gain}}\left( {{\rm{S}},{\rm{\;A}}} \right){\rm{\;}} = {\rm{\;Entropy}}\left( {\rm{S}} \right){\rm{\;}} - {\rm{\;}}\mathop \sum \limits_{v\; \in \;values\left( A \right)} \frac{{\left| {{S_v}} \right|}}{{\left| {\rm{S}} \right|}}{\rm{Entropy}}\left( {{S_v}} \right)$

Trong đó

§  values(A) tập hợp các giá trị có thể có của A

§  $S_v$ tập con subset của S mang giá trị v

§  $\left| {{S_v}} \right|$ số lượng phần tử của $S_v$

§  $\left| {{S}} \right|$ số lượng phần tử của S

Ví dụ tập S là tập hợp có 14 đối tượng, A là thuộc tính gió strong hay weak tương ứng TRUE/FALSE. Phân loại của S là 9 YES và 5 NO. Với attribute wind = weak có 8 trường hợp và wind = strong có 6 trường hợp. Với wind = weak 8 trường hợp bao gồm 6 YES và 2 NO. Với wind = strong 6 trường hợp bao gồm 3 YES và 3 NO (totally random entropy = 1)

${\rm{Gain}}\left( {{\rm{S}},{\rm{\;Wind}}} \right){\rm{\;}} = {\rm{\;Entropy}}\left( {\rm{S}} \right){\rm{\;}} - \left( {8/14} \right)Entropy\left( {{S_{weak}}} \right) - \left( {6/14} \right)Entropy\left( {{S_{strong}}} \right)$

$= 0.940{\rm{\;}} - {\rm{\;}}\left( {8/14} \right)0.811{\rm{\;}} - {\rm{\;}}\left( {6/14} \right)1.00 = 0.048$

${\rm{Entropy}}\left( {{S_{weak}}} \right) =  - \left( {6/8} \right){\log _2}\left( {6/8} \right) - \left( {2/8} \right){\log _2}\left( {2/8} \right) = 0.811$

${\rm{Entropy}}\left( {{S_{strong}}} \right) =  - \left( {3/6} \right){\log _2}\left( {3/6} \right) - \left( {3/6} \right){\log _2}\left( {3/6} \right) = 1$

Ví dụ ID3

Theo data ví dụ các độ đo như sau:

§  Gain(S, Outlook) = 0.246

§  Gain(S, Temperature) = 0.029

§  Gain(S, Humidity) = 0.151

§  Gain(S, Wind) = 0.048 (đã tính toán ở ví dụ trên)

Outlook có gain cao nhất nên sẽ được chọn làm root node. Bây giờ ví dụ theo nhánh sunny sẽ có 5 trường hợp S_sunny = {D1, D2, D8, D9, D11}

Tiếp tục tính toán Gain theo nhánh này:

§  Gain(S_sunny, Humidity) = 0.970

§  Gain(S_sunny, Temperature) = 0.570

§  Gain(S_sunny, Wind) = 0.019

Theo đó humidity có gain cao nhất, sau bước này thì humidity có thể dùng để phân lớp hoàn toàn (classified perfectly) nên không cần xét thêm thuộc tính nào.

Day	Outlook	Temperature	Humidity	Windy	Play
D1	sunny	hot	high	FALSE	no
D2	sunny	hot	high	TRUE	no
D8	sunny	mild	high	FALSE	no
D9	sunny	cool	normal	FALSE	yes
D11	sunny	mild	normal	TRUE	yes

ID3 tree cuối cùng như sau

Các ID3 tree có thể biểu diễn các luật (rule) dưới dạng phát biểu như sau:

§  IF outlook = sunny AND humidity = high THEN play = no

§  IF outlook = rain AND humidity = high THEN play = no

§  IF outlook = rain AND wind = strong THEN play = yes

§  IF outlook = overcast THEN play = yes

§  IF outlook = rain AND wind = weak THEN play = yes

ID3 thông thường được cài đặt sẵn trong các ứng dụng như Weka, R. ID3 được dùng trong các trường hợp như chẩn đoán y tế, đánh giá rủi ro tín dụng … và được đánh giá là có hiệu quả.

Kết quả chạy với Weka

=== Run information ===

Scheme:weka.classifiers.trees.Id3

Relation:     weather.symbolic

Instances:    14

Attributes:   5

              outlook

              temperature

              humidity

              windy

              play

Test mode:split 66.0% train, remainder test

=== Classifier model (full training set) ===

Id3

outlook = sunny

|  humidity = high: no

|  humidity = normal: yes

outlook = overcast: yes

outlook = rainy

|  windy = TRUE: no

|  windy = FALSE: yes

Time taken to build model: 0 seconds

=== Evaluation on test split ===

=== Summary ===

Correctly Classified Instances           3               60      %

Incorrectly Classified Instances         2               40      %

Kappa statistic                          0    

Mean absolute error                      0.4  

Root mean squared error                  0.6325

Relative absolute error                 84.6154 %

Root relative squared error            128.7453 %

Total Number of Instances                5    

=== Detailed Accuracy By Class ===

               TP Rate   FP Rate   Precision   Recall  F-Measure   ROC Area  Class

                 1         1          0.6       1         0.75       0.5      yes

                 0         0          0         0         0          0.5      no

Weighted Avg.    0.6       0.6        0.36      0.6       0.45       0.5 

=== Confusion Matrix ===

 a b   <-- as="" classified="" o:p="">

 3 0 | a = yes

 2 0 | b = no

Các vấn đề

Vấn đề overfitting? Xem xét sai số của giả thuyết h (error of hypothesis h) như sau:

§  Trong training data: error_train(h)

§  Trong toàn bộ dữ liệu D (entire distribution D of data): error_D(h)

Giả thuyết h ∉ H gọi là overfit training data nếu tồn tại một giả thuyết khác h’ ∉ H thỏa mãn

§  error_train(h) < error_train(h’)

§  error_D(h) > error_D(h’)

Có nghĩa overfitting là do bị ảnh hưởng quá nhiều vào dữ liệu rèn luyện mà không cho kết quả tốt trên dữ liệu thật sự. Ví dụ overfitting có thể thực hiện bằng cách thêm 1 record #D15 như sau sunny-hot-normal-strong-play=No

Nhiều giải pháp được đưa ra như cắt tỉa lại cây quyết định (prunning tree) sau khi học, hoặc cắt tỉa các luật sau khi chuyển cây về dạng luật. Một vấn đề nữa là thuộc tính có giá trị liên tục. Để giải quyết các vấn đề này một số thế hệ sau của ID3 đã ra đời. Nổi bật trong số đó có thể kể như C4.5 (Quinlan, 1996) (J48 trong Weka).