Introduction to ID3 algorithm - Thuật toán quy nạp cây ID3 (ID3 algorithm)
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
2p 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 Ssunny = {D1, D2, D8, D9, D11}
Tiếp tục tính toán Gain theo nhánh này:
§ Gain(Ssunny, Humidity) = 0.970
§ Gain(Ssunny, Temperature) = 0.570
§ Gain(Ssunny, 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: errortrain(h)
§ Trong toàn bộ dữ liệu D (entire distribution D of data): errorD(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
§ errortrain(h) < errortrain(h’)
§ errorD(h) > errorD(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).
Tuy nhiên gây ảnh hưởng lớn đến hệ số hồi quy của mô hình do sẽ có tác động kéo đường hồi quy theo hướng của nó. Trong trường hợp này A là điểm ảnh hưởng (influence point).
Trong một số trường hợp có thể nhận thấy một lượng nhỏ dữ liệu nhưng gây ảnh hưởng không cân xứng (disproportionate influence - nhóm nhỏ nhưng ảnh hưởng lớn hơn so với tỷ lệ dữ liệu) lên các hệ số và thuộc tính của mô hình.
Trong một vài trường hợp cực đoan (extreme case), các dự đoán về tham số (parameter estimates) có thể phụ thuộc vào một tập rất nhỏ dữ liệu gây ảnh hưởng hơn là phần lớn data còn lại.
Thông thường mô hình hồi quy thường mong muốn sẽ đại diện được cho toàn bộ dữ liệu. Nếu các điểm ảnh hưởng là xấu (không hợp lý hoặc do lỗi) thì các điểm này cần được loại bỏ khỏi phân tích.
Nếu các điểm này có ý nghĩa, và kiểm soát các thông số chính của mô hình, cần phải biết các điểm này để giải thích ảnh hưởng của chúng cũng như hiểu rõ để sử dụng hiệu quả kết quả của mô hình hồi quy.
