So sánh kết quả của Football Predictions với cây quyết định ID3

Trong khi Football Predictions sử dụng mạng nơron nhằm xác định ánh xạ xấp xỉ hàm đích từ tập mẫu thì thuật toán ID3 thực hiện quy nạp để học luật cũng từ tập mẫu, và cả hai cùng có khả năng giải các lớp bài toán chung. Trong đó, ID3 đã được ứng dụng rộng rãi trong chẩn đoán bệnh đậu, dự báo thời tiết đặc biệt là giông bão, phát hiện nguyên nhân trục trặc thiết bị, đánh giá rủi ro tài chính, phân loại tìm kiếm Web, và cũng có thể áp dụng cho dự đoán bóng đá, dự đoán xu thế của thị trường chứng khoán.

Kỹ thuật quy nạp đã trở thành cổ điển và kém xa năng lực của mạng nơron, tuy nhiên ví dụ dưới đây cho thấy kết quả của chúng giống nhau rất thú vị.

Ví dụ là bài toán kinh điển chơi Tennis:

-----BEGIN DATA DEFINITION-----
OUTLOOK: Sunny Overcast Rain 
TEMPERATURE: Hot Mild Cool 
HUMIDITY: High Normal
WINDY: Weak Strong
PLAY_TENNIS: Yes No
-----END DATA DEFINITION-----

Football predictions data

Orders    OUTLOOK    TEMPERATURE    HUMIDITY    WINDY    PLAY_TENNIS
1         Sunny      Hot            High        Weak     No
2         Sunny      Hot            High        Strong   No
3         Overcast   Hot            High        Weak     Yes
4         Rain       Mild           High        Weak     Yes
5         Rain       Cool           Normal      Weak     Yes
6         Rain       Cool           Normal      Strong   No
7         Overcast   Cool           Normal      Strong   Yes
8         Sunny      Mild           High        Weak     No
9         Sunny      Cool           Normal      Weak     Yes
10        Rain       Mild           Normal      Weak     Yes
11        Sunny      Mild           Normal      Strong   Yes
12        Overcast   Mild           High        Strong   Yes
13        Overcast   Hot            Normal      Weak     Yes
14        Rain       Mild           High        Strong   No

This data is made on ...

Nguyên lý cây quyết định ID3

Trong ví dụ này chúng ta sử dụng 14 mẫu là dữ liệu của 14 ngày chơi Tennis. Các giá trị kết quả đại diện cho lớp để phân loại. Ở đây chúng ta có hai lớp Yes và No, và mỗi mẫu sẽ thuộc về một trong những lớp này. Thuật toán ID3 tìm thuộc tính quan trọng nhất của tập mẫu để tạo nút quyết định chứa thuộc tính đó và chia tập mẫu vào các nhánh theo các giá trị của thuộc tính. Đầu tiên là xử lý tập mẫu ban đầu và tạo ra nút gốc của cây. Sau đó thuật toán tiếp tục đệ quy trên mỗi tập mẫu con đối với các thuộc tính còn lại. Nếu mọi mẫu trong tập mẫu thuộc về cùng một lớp thì nút trở thành nút lá và được gắn nhãn với lớp đó. Trường hợp thiếu mẫu trong tập mẫu cho một giá trị của thuộc tính được chọn thì một nút lá được tạo và được gắn nhãn NoData (hoặc lấy lớp chung nhất trong tập mẫu để gắn nhãn cho nút lá đó với một độ may rủi nhất định). Trường hợp không còn thuộc tính để phân nhánh mà có các mẫu thuộc về các lớp khác nhau thì nút trở thành nút lá và được gắn nhãn với lớp chung nhất trong tập mẫu (với may rủi, đây là trường hợp các mẫu có kết quả trái ngược). Mỗi nút lá là một kết quả duyệt cây. Cây được duyệt từ nút gốc theo các giá trị thuộc tính.

Entropy

Entropy của tập mẫu S được kí hiệu là H(S),

entropy

trong đó, X là tập các lớp trong S và p(x) là tỉ số giữa số mẫu trong tập S thuộc lớp x và số mẫu của tập S.

Information gain

Information gain IG(S, A) là hiệu Entropy của tập mẫu S trước và sau khi chia theo thuộc tính A,

trong đó, vals(A) là tập các giá trị của thuộc tính A, S_v là tập mẫu con của S, gồm các mẫu mà thuộc tính A có giá trị là v.

Chọn thuộc tính quan trọng nhất

Thuộc tính A là thuộc tính quan trọng nhất của tập S và được chọn để phân rã tập S nếu nó chưa được sử dụng và có IG(S,A) là lớn nhất.

Dựng cây quyết định ID3

Ban đầu tập mẫu là tập S gồm tất cả 14 mẫu và chưa có thuộc tính nào được sử dụng. Các thuộc tính là OUTLOOK, TEMPERATURE, HUMIDITY và WINDY. Chúng ta có

H(S) = – p(Yes)log₂p(Yes) – p(No)log₂p(No)

= – (9/14)*log₂(9/14) – (5/14)*log₂(5/14) = 0.9402859587

Thuộc tính OUTLOOK chia tập S thành 3 tập con là S_Sunny, S_Overcast và S_Rain

H(S_Sunny) = – (2/5)*log₂(2/5) – (3/5)*log₂(3/5) = 0.9709505945

H(S_Overcast) = – (4/4)*log₂(4/4) – 0 = 0

H(S_Rain) = – (3/5)*log₂(3/5) – (2/5)*log₂(2/5) = 0.9709505945

Vậy IG(S, OUTLOOK) = 0.9402859587 – (5/14)*0.9709505945 – (4/14)*0 – (5/14)*0.9709505945

= 0.2467498198

Thuộc tính TEMPERATURE chia tập S thành 3 tập con là S_Hot, S_Mild và S_Cool

H(S_Hot) = – (2/4)*log₂(2/4) – (2/4)*log₂(2/4) = 1

H(S_Mild) = – (4/6)*log₂(4/6) – (2/6)*log₂(2/6) = 0.9182958341

H(S_Cool) = – (3/4)*log₂(3/4) – (1/4)*log₂(1/4) = 0.8112781245

Vậy IG(S, TEMPERATURE) = 0.9402859587 – (4/14)*1 – (6/14)*0.9182958341 – (4/14)*0.8112781245

= 0.0292225657

Thuộc tính HUMIDITY chia tập S thành 2 tập con là S_High và S_Normal

H(S_High) = – (3/7)*log₂(3/7) – (4/7)*log₂(4/7) = 0.985228136

H(S_Normal) = – (6/7)*log₂(6/7) – (1/7)*log₂(1/7) = 0.5916727786

Vậy IG(S, HUMIDITY) = 0.9402859587 – (7/14)*0.985228136 – (7/14)*0.5916727786

= 0.1518355014

Thuộc tính WINDY chia tập S thành 2 tập con là S_Weak và S_Strong

H(S_Weak) = – (6/8)*log₂(6/8) – (2/8)*log₂(2/8) = 0.8112781245

H(S_Strong) = – (3/6)*log₂(3/6) – (3/6)*log₂(3/6) = 1

Vậy IG(S, WINDY) = 0.9402859587 – (8/14)*0.8112781245 – (6/14)*1

= 0.0481270304

Như vậy, Information gain của tập S đối với thuộc tính OUTLOOK, IG(S, OUTLOOK) = 0.2467498198 là lớn nhất và OUTLOOK là thuộc tính quan trọng nhất, được chọn để tạo nút quyết định, trong trường hợp này là nút gốc. Tập S được chia thành 3 tập con S_Sunny, S_Overcast và S_raintheo thuộc tính OUTLOOK.

outlook

Chúng ta lần lượt xử lý các tập con S_Sunny, S_Overcast và S_rain. Các thuộc tính còn lại là TEMPERATURE, HUMIDITY và WINDY.

Xử lý tập con S_Sunny

Tại bước này tập mẫu là S_Sunny, với |S_Sunny| = 5 và chúng ta đã tính được H(S_Sunny) = 0.9709505945

Thuộc tính TEMPERATURE chia tập S_Sunny thành 3 tập con là S_Hot, S_Mild và S_Cool

H(S_Hot) = – 0 – (2/2)*log₂(2/2) = 0

H(S_Mild) = – (1/2)*log₂(1/2) – (1/2)*log₂(1/2) = 1

H(S_Cool) = – (1/1)*log₂(1/1) – 0 = 0

Vậy IG(S_Sunny, TEMPERATURE) = 0.9709505945 – (2/5)*0 – (2/5)*1 – (1/5)*0

= 0.5709505945

Thuộc tính HUMIDITY chia tập S_Sunny thành 2 tập con là S_High và S_Normal

H(S_High) = – 0 – (3/3)*log₂(3/3) = 0

H(S_Normal) = – (2/2)*log₂(2/2) – 0 = 0

Vậy IG(S_Sunny, HUMIDITY) = 0.9709505945 – (3/5)*0 – (2/5)*0

= 0.9709505945

Thuộc tính WINDY chia tập S_Sunny thành 2 tập con là S_Weak và S_Strong

H(S_Weak) = – (1/3)*log₂(1/3) – (2/3)*log₂(2/3) = 0.9182958341

H(S_Strong) = – (1/2)*log₂(1/2) – (1/2)*log₂(1/2) = 1

Vậy IG(S_Sunny, WINDY) = 0.9709505945 – (3/5)*0.9182958341 – (2/5)*1

= 0.019973094

Như vậy, Information gain của tập S_Sunny đối với thuộc tính HUMIDITY, IG(S_Sunny, HUMIDITY) = 0.9709505945 là lớn nhất và HUMIDITY là thuộc tính quan trọng nhất, được chọn để tạo nút quyết định, là nút con đầu tiên của nút gốc. Nút quyết định này sẽ có 2 nút con ứng với 2 tập con S_High và S_Normal được chia từ tập S_Sunny theo thuộc tính HUMIDITY. Tập S_High gồm các mẫu cùng một lớp No nên nút dành cho nó là một nút lá được gắn nhãn No. Tập S_Normal gồm các mẫu cùng một lớp Yes nên nút dành cho nó là một nút lá được gắn nhãn Yes. Đệ quy theo nhánh Sunny đến đây là kết thúc.

humidity

Xử lý tập con S_Overcast

Tập S_Overcast gồm các mẫu cùng một lớp Yes nên nút dành cho nó là một nút lá được gắn nhãn Yes. Đệ quy theo nhánh Overcast đến đây là kết thúc.

Xử lý tập con S_Rain

Tại bước này tập mẫu là S_Rain, với |S_Rain| = 5 và chúng ta đã tính được H(S_Rain) = 0.9709505945

Thuộc tính TEMPERATURE chia tập S_Rain thành 2 tập con là S_Mild và S_Cool

H(S_Mild) = – (2/3)*log₂(2/3) – (1/3)*log₂(1/3) = 0.9182958340

H(S_Cool) = – (1/2)*log₂(1/2) – (1/2)*log₂(1/2) = 1

Vậy IG(S_Rain, TEMPERATURE) = 0.9709505945 – (3/5)*0.9182958340 – (2/5)*1

= 0.019973094

Thuộc tính HUMIDITY chia tập S_Rain thành 2 tập con là S_High và S_Normal

H(S_High) = – (1/2)*log₂(1/2) – (1/2)*log₂(1/2) = 1

H(S_Normal) = – (2/3)*log₂(2/3) – (1/3)*log₂(1/3) = 0.9182958340

Vậy IG(S_Rain, HUMIDITY) = 0.9709505945 – (2/5)*1 – (3/5)*0.9182958340

= 0.019973094

Thuộc tính WINDY chia tập S_Rain thành 2 tập con là S_Weak và S_Strong

H(S_Weak) = – (3/3)*log₂(3/3) – 0 = 0

H(S_Strong) = – 0 – (2/2)*log₂(2/2) = 0

Vậy IG(S_Rain, WINDY) = 0.9709505945 – (3/5)*0 – (2/5)*0

= 0.9709505945

Như vậy, Information gain của tập S_Rain đối với thuộc tính WINDY, IG(S_Rain, WINDY) = 0.9709505945 là lớn nhất và WINDY là thuộc tính quan trọng nhất, được chọn để tạo nút quyết định, là nút con thứ ba của nút gốc. Nút quyết định này sẽ có 2 nút con ứng với 2 tập con S_Weak và S_Strong được chia từ tập S_Rain theo thuộc tính WINDY. Tập S_Weak gồm các mẫu cùng một lớp Yes nên nút dành cho nó là một nút lá được gắn nhãn Yes. Tập S_Strong gồm các mẫu cùng một lớp No nên nút dành cho nó là một nút lá được gắn nhãn No. Thuật toán kết thúc và cây quyết định được hoàn thành.

tennis

Cây quyết định thể hiện các luật sau:

if OUTLOOK = Sunny and HUMIDITY = High then PLAY_TENNIS = No

if OUTLOOK = Sunny and HUMIDITY = Normal then PLAY_TENNIS = Yes

if OUTLOOK = Overcast then PLAY_TENNIS = Yes

if OUTLOOK = Rain and WINDY = Weak then PLAY_TENNIS = Yes

if OUTLOOK = Rain and WINDY = Strong then PLAY_TENNIS = No

So sánh kết quả của Football Predictions với cây quyết định ID3

1. Khi OUTLOOK = Overcast

Luật của cây quyết định là

if OUTLOOK = Overcast then PLAY_TENNIS = Yes

Kết quả của Football Predictions và kết quả của cây quyết định ID3 hoàn toàn giống nhau

overcast1 overcast2 overcast3

overcast4 overcast5 overcast6

overcast7 overcast8 overcast9

overcast10 overcast11 overcast12

2. Khi OUTLOOK = Sunny và HUMIDITY = Normal

Luật của cây quyết định là

if OUTLOOK = Sunny and HUMIDITY = Normal then PLAY_TENNIS = Yes

Kết quả của Football Predictions hoàn toàn giống với kết quả của cây quyết định

sunny1-normal sunny2-normal sunny5-normal

sunny6-normal sunny9-normal sunny10-normal

3. Khi OUTLOOK = Sunny và HUMIDITY = High

Luật của cây quyết định là

if OUTLOOK = Sunny and HUMIDITY = High then PLAY_TENNIS = No

Kết quả của Football Predictions giống với kết quả của cây quyết định trong 5 trường hợp, khác nhau 1 trường hợp trong tất cả 6 trường hợp giả thiết khớp với luật này của cây quyết định

sunny3-high sunny4-high sunny7-high

sunny8-high sunny11-high sunny12-high

4. Khi OUTLOOK = Rain và WINDY = Weak

Luật của cây quyết định là

if OUTLOOK = Rain and WINDY = Weak then PLAY_TENNIS = Yes

Kết quả của Football Predictions hoàn toàn giống với kết quả của cây quyết định

rain2-weak rain4-weak rain6-weak

rain8-weak rain10-weak rain12-weak

5. Khi OUTLOOK = Rain và WINDY = Strong

Luật của cây quyết định là

if OUTLOOK = Rain and WINDY = Strong then PLAY_TENNIS = No

rain1-strong rain3-strong rain5-strong

rain7-strong rain9-strong rain11-strong

Như vậy, Football Predictions và thuật toán ID3 có kết quả giống nhau trong hầu hết tất cả 36 trường hợp của bài toán, chỉ có 2 trường hợp kết quả khác nhau. Điều đó chứng tỏ cả hai giải pháp cùng tiếp cận một chân lý. Lập luận logic trong thuật toán ID3 là dễ hiểu, nhưng kết quả học của mạng nơron trong Football Predictions thật đáng ngạc nhiên. Thuật toán ID3 hay phương pháp quy nạp nói chung có một số nhược điểm, trong đó việc chọn thuộc tính quyết định có tính phân biệt quá cao làm mất thông tin từ các thuộc tính khác trong một vài trường hợp.

Chúng ta xét thêm một ví dụ về một bài toán dự báo thời tiết

-----BEGIN DATA DEFINITION-----
TEMPERATURE: Warm Cold VeryCold 
SKY: Blue Normal Cloud 
PRESSURE: Up Stable Down 
WEATHER RESULTS: Rain Snow Sunny
-----END DATA DEFINITION-----

Football predictions data

Orders    TEMPERATURE    SKY    PRESSURE    WEATHER
1         Warm           Cloud  Down        Rain 
2         VeryCold       Cloud  Stable      Snow 
3         Warm           Cloud  Up          Sunny 
4         Warm           Normal Stable      Sunny 
5         Cold           Blue   Stable      Sunny 
6         Warm           Blue   Down        Rain 
7         Cold           Normal Stable      Snow 

This data is made on ...