Khoa Công Nghệ Thông Tin
Trường Đại Học Cần Thơ
Đỗ Thanh Nghị

Cần Thơ
02-12-2008
Phương pháp học cây quyết đị
nh
Decision Tree
Nội dung

Giới thiệu về cây quyết định

Giải thuật học của cây quyết định

Kết luận và hướng phát triển
2
Nội dung

Giới thiệu về cây quyết định

Giải thuật học của cây quyết định

Kết luận và hướng phát triển
3
Cây quyết định

lớp các giải thuật học

kết quả sinh ra dễ dịch (if … then …)


Nội dung

Giới thiệu về cây quyết định

Giải thuật học của cây quyết định

Kết luận và hướng phát triển
6
Giải thuật học cây quyết định
7

Giới thiệu về cây quyết định

Giải thuật học cây quyết định

kết luận và hướng phát triển

1 nút trong : test trên 1 thuộc tính (biến)

1 nhánh : trình bày cho dữ liệu thỏa mãn test, ví dụ :
age < 25.

nút lá : lớp (nhãn)

ở mỗi nút, 1 thuộc tính được chọn để phân hoạch dữ
liệu học sao cho tách rời các lớp tốt nhất có thể

dữ liệu mới đến được phân loại theo đường dẫn từ
gốc đến nút lá
8


Giải thuật học cây quyết định

kết luận và hướng phát triển
Cây quyết định cho tập dữ liệu weather,
dựa trên các thuộc tính (
Outlook, Temp, Humidity, Windy
)
overcast
high normal
false
true
sunny
rain
No No
Yes Yes
Yes
Outlook
Humidity
Windy
10

Giới thiệu về cây quyết định

Giải thuật học cây quyết định

kết luận và hướng phát triển
Giải thuật cây quyết định

xây dựng cây Top-down


Giới thiệu về cây quyết định

Giải thuật học cây quyết định

kết luận và hướng phát triển
Chọn thuộc tính phân hoạch ?
13

Giới thiệu về cây quyết định

Giải thuật học cây quyết định

kết luận và hướng phát triển
Chọn thuộc tính phân hoạch ?

thuộc tính nào tốt ?

cho ra kết quả là cây nhỏ nhất

heuristics: chọn thuộc tính sinh ra các nút “purest” (thuần
khiết)

độ lợi thông tin

tăng với giá trị trung bình thuần khiết của các tập con của
dữ liệu mà thuộc tính sinh ra

chọn thuộc tính có độ lợi thông tin lớn nhất
14

)
,
,
,
entropy(
2
2
1
1
2
1





15

Giới thiệu về cây quyết định

Giải thuật học cây quyết định

kết luận và hướng phát triển
Born: 30 April 1916
Died: 23 February 2001
“Father of
information theory”
*Claude Shannon
16


Yesfalsenormalcoolrain
Yesfalsehighmildrain
Yesfalsehighhotovercast
Notruehighhotsunny
Nofalsehighhotsunny
Play?WindyHumidityTemperatureOutlook
17

Giới thiệu về cây quyết định

Giải thuật học cây quyết định

kết luận và hướng phát triển
Ví dụ : thuộc tính outlook

“Outlook” = “Sunny”:

“Outlook” = “Overcast”:

“Outlook” = “Rainy”:

thông tin của thuộc tính outlook:
bits

971
.
0
)
5
/

1
log(
1
0)
entropy(1,
)
info([4,0]





bits

971
.
0
)
5
/
2
log(
5
/
2
)
5
/
3
log(

971
.
0
)
14
/
5
(
[3,2])
[4,0],
,
info([3,2]






bits

693
.
0

18

Giới thiệu về cây quyết định

Giải thuật học cây quyết định


bits 985.0)7/4log(7/4)7/3log(7/37,4/7)entropy(3/)info([3,4]





bits 592.0)7/1log(7/1)7/6log(7/67,1/7)entropy(6/)info([6,1]





592.0)14/7(985.0)14/7([6,1]),info([3,4]




bits 788.0

0.1520.788-0.940[6,1]),info([3,4]-)info([9,5]


20

Giới thiệu về cây quyết định

Giải thuật học cây quyết định

kết luận và hướng phát triển
Độ lợi thông tin


bits

048
.
0
)
Windy"
gain("

21

Giới thiệu về cây quyết định

Giải thuật học cây quyết định

kết luận và hướng phát triển
Tiếp tục phân hoạch dữ liệu
bits

571
.
0
)
e"
Temperatur
gain("

bits


Giới thiệu về cây quyết định

Giải thuật học cây quyết định

kết luận và hướng phát triển
Tính chất của độ đo thuần khiết

3 tính chất

khi 1 nút là thuần khiết thì độ đo nên bằng 0

khi độ hỗn loạn là maximal thì độ đo thuần khiết phải
maximal

độ đo phải có tính chất multistage

entropy là hàm thỏa mãn các tính chất trên!
,4])
measure([3
(7/9)
,7])
measure([2
,3,4])
measure([2



24

Giới thiệu về cây quyết định

9
/
3
log(
9
/
3
)
9
/
2
log(
9
/
2
])
4
,
3
,
2
([
info








thuộc tính có nhiều giá trị phân nhánh

tập con thường có tính thuần khiết nếu có nhiều giá trị

độ lợi thông tin : thường là những thuộc tính có nhiều giá
trị phân nhánh

điều này thường dẫn đến overfitting