Bài giảng Học máy (IT 4862) - Bài 4: Các phương pháp học có giám sát - Phần 3: Học cây quyết định - Nguyễn Nhật Quang

Học Máy
(IT 4862)
ễ hậNguy n N t Quang
quangnn-fit@mail.hut.edu.vn
Trường Đại học Bách Khoa Hà Nội
Viện Công nghệ thông tin và truyền thông
Năm học 2011-2012
Nội d ô hung m n ọc:
„ Giới thiệu chung
„ Đánh giá hiệu năng hệ thống học máy
„ Các phương pháp học dựa trên xác suất 
„ Các phương pháp học có giám sát
„ Học cây quyết định (Decision tree learning) 
„ Các phương pháp học không giám sát
L ộ tᄠọc c ng c
„ Học tăng cường
2
Học Máy – IT 4862
Học cây quyết định – Giới thiệu
„ Học cây quyết định (Decision tree –DT– learning)
• Để học (xấp xỉ) một hàm mục tiêu có giá trị rời rạc (discrete- 
valued target function) – hàm phân lớp
• Hàm phân lớp được biểu diễn bởi một cây quyết định
„ Một cây quyết định có thể được biểu diễn (diễn giải) bằng một 
tập các luật IF-THEN (dễ đọc và dễ hiểu)
H â ết đị h ó thể th hiệ ả ới á dữ liệ ó„ ọc c y quy n c ực n ngay c v c c u c 
chứa nhiễu/lỗi (noisy data)
„ Là một trong các phương pháp học quy nạp (inductive 
learning) được dùng phổ biến nhất
„ Được áp dụng thành công trong rất nhiều các bài toán ứng 
d th tế
3Học Máy – IT 4862
ụng ực 
Ví dụ về DT: Những tin tức nào mà tôi quan tâm?
is present
“sport”?
is absent
“football”?
is present
“player”?
is present is absentis absent
is absent
InterestedUninterestedInterested “goal”?
is present
Interested Uninterested
• (,“sport”,,“player”,) → Interested
• (,“goal”,) → Interested
• ( “sport” ) → Uninterested, , 
4
Học Máy – IT 4862
Ví dụ về DT: Một người có chơi tennis không?
Sunny
Outlook=?
Rain
Overcast
Wind=?
Strong
Humidity=?
High WeakNormal
Yes
YesNo Yes No
• (Outlook=Overcast, Temperature=Hot, Humidity=High, 
Wind=Weak) → Yes
• (Outlook=Rain, Temperature=Mild, Humidity=High, Wind=Strong)
→ No
• (Outlook=Sunny, Temperature=Hot, Humidity=High, Wind=Strong)
→ No 
5
Học Máy – IT 4862
Biểu diễn cây quyết định (1)
„ Mỗi nút trong (internal node) biểu diễn một thuộc tính cần 
kiểm tra giá trị (an attribute to be tested) đối với các ví dụ 
„ Mỗi nhánh (branch) từ một nút sẽ tương ứng với một giá 
trị có thể của thuộc tính gắn với nút đó 
„ Mỗi nút lá (leaf node) biểu diễn một phân lớp (a
classification)
„ Một cây quyết định học được sẽ phân lớp đối với một ví 
dụ, bằng cách duyệt cây từ nút gốc đến một nút lá
→ Nhãn lớp gắn với nút lá đó sẽ được gán cho ví dụ cần phân lớp
6Học Máy – IT 4862
Biểu diễn cây quyết định (2)
„ Một cây quyết định biểu diễn một phép tuyển (disjunction) 
của các kết hợp (conjunctions) của các ràng buộc đối với 
các giá trị thuộc tính của các ví dụ
„ Mỗi đường đi (path) từ nút gốc đến một nút lá sẽ tương 
ứng với một kết hợp (conjunction) của các kiểm tra giá trị 
thuộc tính (attribute tests)
„ Cây quyết định (bản thân nó) chính là một phép tuyển 
(disjunction) của các kết hợp (conjunctions) này
„ Các ví dụ
→ Hãy xét 2 cây quyết định đã nêu ở trước
7Học Máy – IT 4862
Những tin tức nào mà tôi quan tâm?
is present
“sport”?
is absent
“football”?
is present
“player”?
is present is absentis absent
is absent
InterestedUninterestedInterested “goal”?
is present
Interested Uninterested
[(“sport” is present) ∧ (“player” is present)] ∨
[(“sport” is absent) ∧ (“football” is present)] ∨
[(“sport” is absent) ∧ (“football” is absent) ∧ (“goal” is present)] 
8
Học Máy – IT 4862
Một người có chơi tennis không?
Sunny
Outlook=?
Rain
Overcast
Wind=?
Strong
Humidity=?
High WeakNormal
Yes
YesNo Yes No
[(Outlook=Sunny) ∧ (Humidity=Normal)] ∨
(Outlook=Overcast) ∨
[(Outlook=Rain) ∧ (Wind=Weak)]
9
Học Máy – IT 4862
Giải thuật ID3 – Ý tưởng
„ Thực hiện giải thuật tìm kiếm tham lam (greedy search) đối với không
gian các cây quyết định có thể
„Xây dựng (học) một cây quyết định theo chiến lược top-down, bắt đầu
từ nút gốc
„Ở mỗi nút thuộc tính kiểm tra (test attribute) là thuộc tính có khả năng , 
phân loại tốt nhất đối với các ví dụ học gắn với nút đó
„ Tạo mới một cây con (sub-tree) của nút hiện tại cho mỗi giá trị có thể
của thuộc tính kiểm tra và tập học sẽ được tách ra (thành các tập con), 
tương ứng với cây con vừa tạo
„Mỗi thuộc tính chỉ được phép xuất hiện tối đa 1 lần đối với bất kỳ một
đ ờ đi à t âư ng n o rong c y
„Quá trình phát triển (học) cây quyết định sẽ tiếp tục cho đến khi
• Cây quyết định phân loại hoàn toàn (perfectly classifies) các ví dụ học, hoặc
10Học Máy – IT 4862
• Tất cả các thuộc tính đã được sử dụng
Giải thuật ID3
ID3_alg(Training_Set, Class_Labels, Attributes)
Tạo nút Root của cây quyết định
If tất cả các ví dụ của Training_Set thuộc cùng lớp c, Return Cây quyết định có nút Root
được gắn với (có nhãn) lớp c
If Tập thuộc tính Attributes là rỗng, Return Cây quyết định có nút Root được gắn với nhãn 
lớp ≡ Majority_Class_Label(Training Set)_
A← Thuộc tính trong tập Attributes có khả năng phân loại “tốt nhất” đối với Training_Set
Thuộc tính kiểm tra cho nút Root← A
For each Giá trị có thể v của thuộc tính A
Bổ sung một nhánh cây mới dưới nút Root, tương ứng với trường hợp: “Giá trị của A là v”
Xác định Training_Setv = {ví dụ x | x ⊆ Training_Set, xA=v}
If (Training_Setv là rỗng) Then
Tạo một nút lá với nhãn lớp Majority Class Label(T i i S t) ≡ _ _ ra n ng_ e
Gắn nút lá này vào nhánh cây mới vừa tạo
Else Gắn vào nhánh cây mới vừa tạo một cây con sinh ra bởi ID3_alg(Training_Setv, Class_Labels, {Attributes \ A})
Return Root
11Học Máy – IT 4862
Lựa chọn thuộc tính kiểm tra
„ Tại mỗi nút, chọn thuộc tính kiểm tra như thế nào?
„Chọn thuộc tính quan trọng nhất cho việc phân lớp các ví dụ học gắn 
với nút đó
„ Làm thế nào để đánh giá khả năng của một thuộc tính đối với việc
phân tách các ví dụ học theo nhãn lớp của chúng?
→ Sử dụng một đánh giá thống kê – Information Gain
„Ví dụ: Xét bài toán phân lớp có 2 lớp (c1, c2)
ể
A1=? (c1: 35, c2: 25) A2=? (c1: 35, c2: 25)
→ Thuộc tính nào, A1 hay A2, nên được chọn là thuộc tính ki m tra?
v12
v11 v13
c1: 21
: 9
c1: 5
: 5
c1: 9
: 11
v21 v22
c1: 8
: 19
c1: 27
: 6c2 c2 c2 c2 c2 
12Học Máy – IT 4862
Entropy
„Một đánh giá thường được sử dụng trong lĩnh vực Information Theory
„Để đánh giá mức độ hỗn tạp (impurity/inhomogeneity) của một tập
∑−= c ii ppSEntropy 2log.)(
„Entropy của tập S đối với việc phân lớp có c lớp
=i 1
trong đó pi là tỷ lệ các ví dụ trong tập S thuộc vào lớp i, và 0.log20=0
„Entropy của tập S đối với việc phân lớp có 2 lớp
Entropy(S) = -p1.log2p1 – p2.log2p2
„Ý nghĩa của entropy trong lĩnh vực Information Theory
→ Entropy của tập S chỉ ra số lượng bits cần thiết để mã hóa lớp của một 
phần tử được lấy ra ngẫu nhiên từ tập S
13Học Máy – IT 4862
Entropy – Ví dụ với 2 lớp
1
„ S gồm 14 ví dụ, trong đó 9 ví dụ thuộc về lớp c1
và 5 ví dụ thuộc về lớp c2
0.5
t
r
o
p
y
(
S
)
„Entropy của tập S đối với phân lớp có 2 lớp:
Entropy(S) = -(9/14).log2(9/14)-
0
0.5 1
E
n
p1
(5/14).log2(5/14) ≈ 0.94
„Entropy =0, nếu tất cả các ví dụ thuộc cùng một 
lớp (c1 hoặc c2)
„ Entropy =1, số lượng các ví dụ thuộc về lớp c1 bằng số lượng các ví 
dụ thuộc về lớp c2
„ Entropy = một giá trị trong khoảng (0,1), nếu như số lượng các ví dụ 
thuộc về lớp c1 khác với số lượng các ví dụ thuộc về lớp c2
14Học Máy – IT 4862
Information gain
„ Information Gain của một thuộc tính đối với một tập các ví dụ:
• Mức độ giảm về Entropy
ở ủ
|| S
• B i việc phân chia (partitioning) các ví dụ theo các giá trị c a thuộc tính đó
„ Information Gain của thuộc tính A đối với tập S
)(
||
)(),(
)(
v
AValuesv
v SEntropy
S
SEntropyASGain ∑
∈
−=
trong đó Values(A) là tập các giá trị có thể của thuộc tính A, và
Sv = {x | x∈S, xA=v}
„ Trong công thức trên, thành phần thứ 2 thể hiện giá trị Entropy 
sau khi tập S được phân chia bởi các giá trị của thuộc tính A 
„ Ý nghĩa của Gain(S,A): Số lượng bits giảm được (reduced) 
đối với việc mã hóa lớp của một phần tử được lấy ra ngẫu 
ế
15Học Máy – IT 4862
nhiên từ tập S, khi bi t giá trị của thuộc tính A
Tập các ví dụ học
Xét tập dữ liệu S ghi lại những ngày mà một người chơi (không chơi) tennis:
Day Outlook Temperature Humidity Wind Play Tennis
D1 Sunny Hot High Weak No
D2 Sunny Hot High Strong No
D3 Overcast Hot High Weak Yes
D4 R i Mild Hi h W k Ya n g ea es
D5 Rain Cool Normal Weak Yes
D6 Rain Cool Normal Strong No
D7 Overcast Cool Normal Strong Yes
D8 Sunny Mild High Weak No
D9 Sunny Cool Normal Weak Yes
D10 Rain Mild Normal Weak Yes
YesStrongHighMildOvercastD12
YesWeakNormalHotOvercastD13
D11 Sunny Mild Normal Strong Yes
D14 Rain Mild High Strong No
[Mitchell, 1997]
16Học Máy – IT 4862
Information Gain – Ví dụ
„Hãy tính giá trị Information Gain của thuộc tính Wind đối với tập học S
– Gain(S,Wind)?
„ Thuộc tính Wind có 2 giá trị có thể: Weak và Strong
„ S = {9 ví dụ lớp Yes và 5 ví dụ lớp No}
„ Sweak = {6 ví dụ lớp Yes và 2 ví dụ lớp No có giá trị Wind=Weak}
„ Sstrong = {3 ví dụ lớp Yes và 3 ví dụ lớp No có giá trị Wind=Strong}
∑
∈
−=
},{
)(
||
||)(),(
StrongWeakv
v
v SEntropy
S
SSEntropyWindSGain
)().14/6()().14/8()( StrongWeak SEntropySEntropySEntropy −−=
048.0)1).(14/6()81.0).(14/8(94.0 =−−=
17Học Máy – IT 4862
Học cây quyết định – Ví dụ (1)
„ Tại nút gốc, thuộc tính nào trong số {Outlook, Temperature, 
Humidity, Wind} nên được chọn là thuộc tính kiểm tra?
Có giá trị IG 
cao nhất
• Gain(S, Outlook) = ... = 0.246
• Gain(S, Temperature) = ... = 0.029
• Gain(S Humidity) = = 0 151, ... .
• Gain(S, Wind) = ... = 0.048
→Vì vậy, Outlook được chọn là thuộc tính kiểm tra cho nút gốc!
Outlook=?
OvercastSunny Rain
S={9+, 5-}
Node1
SS ={2+ 3-} SOvercast={4+, 0-} SR i ={3+ 2-}
Yes Node2
unny , a n , 
18Học Máy – IT 4862
Học cây quyết định – Ví dụ (2)
Outlook=? S={9+, 5-}
„ Tại nút Node1, thuộc tính nào
trong số {Temperature, 
idi i d} ê đ
H idit ?
OvercastSunny RainSSunny= 
{2+, 3-} Yes Node2
Hum ty, W n n n ược
chọn là thuộc tính kiểm tra?
Lưu ý! Thuộc tính Outlook bị
loại ra bởi ì nó đã đ ợc sử um y=
SOvercast=
{4+, 0-} SRain= 
{3+, 2-}
High Normal
, v ư
dụng bởi cha của nút Node1 (là
nút gốc)
• Gain(S Temperature) = =
Node3 Node4
S S
Sunny, ... 
0.57
• Gain(SSunny, Humidity) = ... = 0.97
• Gain(SSunny, Wind) = ... = 0.019
High= 
{0+, 3-}
Normal= 
{2+, 0-}
→Vì vậy, Humidity được chọn
là thuộc tính kiểm tra cho nút
19Học Máy – IT 4862
Node1!
Học cây quyết định – Chiến lược tìm kiếm (1)
„ ID3 tìm kiếm trong không gian các giả thiết (các cây 
quyết định có thể) một cây quyết định phù hợp (fits) các ví 
dụ học
„ ID3 thực hiện chiến lược tìm kiếm từ đơn giản đến phức 
tạp, bắt đầu với cây rỗng (empty tree)
„ Quá trình tìm kiếm của ID3 được điều khiển bởi độ đo 
đánh giá Information Gain
„ ID3 chỉ tìm kiếm một (chứ không phải tất cả các) cây 
quyết định phù hợp với các ví dụ học
20Học Máy – IT 4862
Học cây quyết định – Chiến lược tìm kiếm (2)
„ Trong quá trình tìm kiếm, ID3 không thực hiện quay lui 
(not backtrack) 
→Chỉ đảm bảo tìm được lời giải tối ưu cục bộ (locally optimal 
solution) – chứ không đảm bảo tìm được lời giải tối ưu tổng thể 
(globally optimal solution) 
→Một khi một thuộc tính được chọn là thuộc tính kiểm tra cho một 
nút, thì ID3 không bao giờ cân nhắc lại (backtracks to reconsider) 
l h àựa c ọn n y
„ Ở mỗi bước trong quá trình tìm kiếm, ID3 sử dụng một đánh 
giá thống kê (Information Gain) để cải thiện giả thiết hiện tại 
→Nhờ vậy, quá trình tìm kiếm (lời giải) ít bị ảnh hưởng bởi các lỗi 
(nếu có) của một số ít ví dụ học
21Học Máy – IT 4862
Ưu tiên trong học cây quyết định (1)
„Cả 2 cây quyết định dưới đây đều phù hợp với tập học đã cho
Vậy thì cây quyết định nào sẽ được ưu tiên (được học) bởi„ , 
giải thuật ID3?
O tl k ?
Sunny
Outlook=?
RainOvercast
Y
Sunny
u oo =
i
RainOvercast
Y
Weak
Wind=?
Strong
YesNo
Humidity=?
High Normal
Yes No
es W nd=?
Strong
YesNo
Temperature=?
Hot WeakMild
Yes No
es
Cool
Humidity=?
High
Yes
Normal
No
22Học Máy – IT 4862
Ưu tiên trong học cây quyết định (2)
„ Đối với một tập các ví dụ học, có thể tồn tại nhiều (hơn 1) 
cây quyết định phù hợp với các ví dụ học này
„ Cây quyết định nào (trong số đó) được chọn?
„ ID3 chọn cây quyết định phù hợp đầu tiên tìm thấy trong 
quá trình tìm kiếm của nó
→Lưu ý là trong quá trình tìm kiếm, giải thuật ID3 không bao giờ 
â hắ l i á l h t ớ đó ( ith t b kt ki )c n n c ạ c c ựa c ọn rư c w ou ac rac ng
„ Chiến lược tìm kiếm của giải thuật ID3
• Ưu tiên các cây quyết định đơn giản (ít mức độ sâu) 
• Ưu tiên các cây quyết định trong đó một thuộc tính có giá trị 
Information Gain càng lớn thì sẽ là thuộc tính kiểm tra của một nút 
à ầ út ốc ng g n n g c
23Học Máy – IT 4862
Các vấn đề trong ID3
„ Cây quyết định học được quá phù hợp (over-fit) với các ví 
dụ học 
„ Xử lý các thuộc tính có kiểu giá trị liên tục (kiểu số thực)
Cá đá h iá hù h h (tốt h I f ti G i ) đối„ c n g p ợp ơn ơn n orma on a n 
với việc xác định thuộc tính kiểm tra cho một nút
„ Xử lý các ví dụ học thiếu giá trị thuộc tính (missing value - 
attributes)
„ Xử lý các thuộc tính có chi phí (cost) khác nhau 
→ Cải tiến của giải thuật ID3 với tất cả các vấn đề nêu trên 
được giải quyết: giải thuật C4 5 .
24Học Máy – IT 4862
Over-fitting trong học cây quyết định (1)
„ Một cây quyết định phù hợp 
hoàn hảo đối với tập huấn 
ố
Sunny
Outlook=?
RainOvercast
luyện có phải là giải pháp t i 
ưu?
„ Nếu như tập huấn luyện có
Weak
Wind=?
Strong
Humidity=?
High Normal
Yes
nhiễu/lỗi?
Vd: Một ví dụ nhiễu/lỗi (Ví dụ 
YesNo Yes No
Học được một cây quyết định phức tạp hơn!
(chỉ bởi vì ví dụ nhiễu/lỗi)
thực sự mang nhãn Yes, nhưng 
bị gán nhãn nhầm là No):
(Outlook=Sunny, 
Sunny
Outlook=?
RainOvercast
Temperature=Hot, 
Humidity=Normal, 
Wind=Strong, PlayTennis=No) Weak
Wind=?
Strong
Humidity=?
High Normal
Yes
YesNo được phát 
triển tiếp!
No
25Học Máy – IT 4862
Over-fitting trong học cây quyết định (1)
Tiếp tục quá trình học cây quyết định sẽ làm giảm độ chính xác 
đối với tập thử nghiệm mặc dù tăng độ chính xác đối với tập học
[Mitchell, 1997]
26Học Máy – IT 4862
Giải quyết vấn đề over-fitting (1)
„ 2 chiến lược
ể ế•Ngừng việc học (phát tri n) cây quy t định sớm hơn, trước khi nó 
đạt tới cấu trúc cây cho phép phân loại (khớp) hoàn hảo tập huấn 
luyện
•Học (phát triển) cây đầy đủ (tương ứng với cấu trúc cây hoàn toàn 
phù hợp đối với tập huấn luyện), và sau đó thực hiện quá trình tỉa 
(to post-prune) cây
„ Chiến lược tỉa cây đầy đủ (Post-pruning over-fit trees) 
thường cho hiệu quả tốt hơn trong thực tế
→ Lý do: Chiến lược “ngừng sớm” việc học cây cần phải đánh giá 
chính xác được khi nào nên ngừng việc học (phát triển) cây – Khó 
xác định!
27Học Máy – IT 4862
Giải quyết vấn đề over-fitting (2)
„ Làm sao để chọn kích thước “phù hợp” của cây quyết 
định?
• Đánh giá hiệu năng phân loại đối với một tập tối ưu (validation set)
-Đây là phương pháp thường được sử dụng nhất
2 f f hí h d d i d l t i- . . c n : re uce -error prun ng an ru e pos -prun ng
• Áp dụng một thí nghiệm thống kê (vd: chi-square test) để đánh giá 
xem việc mở rộng (hay cắt tỉa) một nút có giúp cải thiện hiệu năng 
ố ấđ i với tập hu n luyện
• Đánh giá độ phức tạp của việc mã hóa (thể hiện) các ví dụ học và 
cây quyết định, và ngừng việc học (phát triển) cây quyết định khi 
kích thước của việc mã hóa này là tối thiểu
-Dựa trên nguyên lý Minimum Description Length (MDL)
-Cần cực tiểu hóa: size(tree) + size(misclassifications(tree))
28Học Máy – IT 4862
Reduced-error pruning
„ Mỗi nút của cây (khớp hoàn toàn) được kiểm tra để cắt tỉa
„ Một nút sẽ bị cắt tỉa nếu cây (sau khi cắt tỉa nút đó) đạt được hiệu 
ồ ầ ố ốnăng không t i hơn cây ban đ u đ i với tập t i ưu (validation set)
„ Cắt tỉa một nút bao gồm các việc:
• Loại bỏ toàn bộ cây con (sub tree) gắn với nút bị cắt tỉa - 
• Chuyển nút bị cắt tỉa thành một nút lá (nhãn phân lớp)
• Gắn với nút lá này (nút bị cắt tỉa) nhãn lớp chiếm số đông trong tập 
h ấ l ệ ắ ới út đóu n uy n g n v n 
„ Lặp lại việc cắt tỉa các nút
• Luôn lựa chọn một nút mà việc cắt tỉa nút đó tối đa hóa khả năng 
phân loại của cây quyết định đối với tập tối ưu (validation set)
• Kết thúc, khi việc cắt tỉa thêm nút làm giảm khả năng phân loại của 
cây quyết định đối với tập tối ưu (validation set) 
29Học Máy – IT 4862
Rule post-pruning
„Học (phát triển) cây quyết định hoàn toàn 
phù hợp với tập huấn luyện Outlook=?
„Chuyển biểu diễn cây quyết định học 
được thành một tập các luật tương ứng 
(tạo một luật cho mỗi đường đi từ nút
Sunny
Wind=?Humidity=?
RainOvercast
Yes 
gốc đến một nút lá)
„Rút gọn (tổng quát hóa) mỗi luật (độc lập 
với các luật khác) bằng cách loại bỏ bất
WeakStrong
YesNo
High Normal
Yes No
 , 
kỳ điều kiện nào giúp mang lại sự cải 
thiện về hiệu quả phân loại của luật đó
Sắ ế á l ật đã út th khả
IF (Outlook=Sunny) Λ
(Humidity=Normal)
„ p x p c c u r gọn eo 
năng (hiệu quả) phân loại, và sử dụng 
thứ tự này cho việc phân loại các ví dụ 
trong tương lai
THEN (PlayTennis=Yes)
30Học Máy – IT 4862
Các thuộc tính có giá trị liên tục
„Cần xác định (chuyển đổi thành) các thuộc tính có giá trị rời rạc, bằng 
cách chia khoảng giá trị liên tục thành một tập các khoảng (intervals) 
không giao nhau 
„Đối với thuộc tính (có giá trị liên tục) A, tạo một thuộc tính mới kiểu nhị 
phân Av sao cho: Av là đúng nếu A>v, và là sai nếu ngược lại
Làm thế nào để xác định giá trị ngưỡng “tốt nhất”?„ v 
→ Chọn giá trị ngưỡng v giúp sinh ra giá trị Information Gain cao nhất
„Ví dụ:
ắ ế ầ ố•S p x p các ví dụ học theo giá trị tăng d n đ i với thuộc tính Temperature
•Xác định các ví dụ học liền kề nhưng khác phân lớp
•Có 2 giá trị ngưỡng có thể: Temperature54 và Temperature85
ể• Thuộc tính mới ki u nhị phân Temperature54 được chọn, bởi vì 
Gain(S,Temperature54) > Gain(S,Temperature85)
Temperature 40 48 60 72 80 90
PlayTennis No No Yes Yes Yes No
31Học Máy – IT 4862
Các đánh giá khác cho lựa chọn thuộc tính
„ Xu hướng của đánh giá Information Gain
→Ưu tiên các thuộc tính có nhiều giá trị hơn các thuộc tính có ít giá trị
ố ấ ểVd: Thuộc tính Date có s lượng r t lớn các giá trị có th
-Thuộc tính này sẽ có giá trị Information Gain cao nhất
-Một mình thuộc tính này có thể phân loại hoàn hảo toàn bộ tập huấn luyện 
ấ ề(thuộc tính này phân chia các ví dụ học thành r t nhi u các tập con có 
kích thước rất nhỏ)
-Thuộc tính này được chọn là thuộc tính kiểm tra ở nút gốc (của cây quyết 
định chỉ có mức độ sâu bằng 1 nhưng rất rộng rất nhiều phân nhánh) , , 
„ Một đánh giá khác: Gain Ratio
→Giảm ảnh hưởng của các thuộc tính có (rất) nhiều giá trị
),(
),(),(
ASmationSplitInfor
ASGainASGainRatio =
∑ log)( vv SSASmationSplitInfor
(trong đó Values(A) là tập 
các giá trị có thể của thuộc 
∈
−=
)(
2,
AValuesv SS tính A, và Sv={x| x∈S, xA=v})
32Học Máy – IT 4862
Xử lý các thuộc tính thiếu giá trị (1)
„ Giả sử thuộc tính A là một ứng cử cho thuộc tính kiểm 
tra ở nút n 
„ Xử lý thế nào với ví dụ x không có (thiếu) giá trị đối với 
thuộc tính A (tức là: xA là không xác định)?
„ Gọi Sn là tập các ví dụ học gắn với nút n có giá trị đối với 
thuộc tính A
→Giải pháp 1: xA là giá trị phổ biến nhất đối với thuộc tính 
A trong số các ví dụ thuộc tập Sn
→Giải pháp 2: xA là giá trị phổ biến nhất đối với thuộc tính 
A trong số các ví dụ thuộc tập Sn có cùng phân lớp với x
33Học Máy – IT 4862
Xử lý các thuộc tính thiếu giá trị (2)
→Giải pháp 3:
• Tính xác suất pv đối với mỗi giá trị có thể v của thuộc tính A
• Gán phần (fraction) pv của ví dụ x đối với nhánh tương ứng của 
nút n
• Những ví dụ một phần (fractional instances) này được sử dụng để
Ví dụ:
Một th ộ tí h kiể hị hâ (0/1) A Nút
. . .
tính giá trị Information Gain
• u c n u n p n 
• Nút n bao gồm:
-Một ví dụ x (thiếu giá trị đối với A)
4 í d ó iá t ị đối ới bằ 1 à
 n
A=1 A=0
- v ụ c g r v A ng , v
- 6 ví dụ có giá trị đối với A bằng 0
p(xA=1) = 4/10 = 0.4
• 4 ví dụ có 
giá trị đối 
với A =1
• 6 ví dụ có 
giá trị đối 
với A =0
p(xA=0) = 6/10 = 0.6 • 0.4 của x • 0.6 của x
34Học Máy – IT 4862
Các thuộc tính có chi phí khác nhau
„ Trong một số bài toán học máy, các thuộc tính có thể được gắn
với các chi phí (độ quan trọng) khác nhau
• Ví dụ: Trong việc học để phân loại các bệnh y tế, BloodTest có
chi phí $150, trong khi TemperatureTest có chi phí $10
„ Xu hướng học các cây quyết định
• Sử dụng càng nhiều càng tốt các thuộc tính có chi phí thấp
• Chỉ sử dụng các thuộc tính có chi phí cao khi cần thiết (để giúp đạt
được các phân loại đáng tin cậy) 
„ Làm sao để học một cây quyết định với chi phí thấp?
→ Sử dụng các đánh giá khác IG cho việc xác định thuộc tính kiểm tra
)(
),(2
ACost
ASGain
w
ASGain
ACost )1)((
12 ),(
+
− (w (∈[0,1]) là hằng số 
xác định mức độ quan 
trọng giữa chi phí và 
I f ti G i )n orma on a n[Tan and Schlimmer, 1990] [Nunez, 1988; 1991]
35Học Máy – IT 4862
Học cây quyết định – Khi nào?
„Các ví dụ học được biểu diễn bằng các cặp (thuộc tính,giá trị)
•Phù hợp với các thuộc tính có giá trị rời rạc
•Đối với các thuộc tính có giá trị liên tục, phải rời rạc hóa
„Hàm mục tiêu có giá trị đầu ra là các giá trị rời rạc
•Ví dụ: Phân loại các ví dụ vào lớp phù hợp 
„Rất phù hợp khi hàm mục tiêu được biểu diễn ở dạng tách rời 
(disjunctive form)
„Tập huấn luyện có thể chứa nhiễu/lỗi
•Lỗi trong phân loại (nhãn lớp) của các ví dụ học
Lỗi t iá t ị th ộ tí h biể diễ á í d h• rong g r u c n u n c c v ụ ọc
„Tập huấn luyện có thể chứa các thuộc tính thiếu giá trị
•Các giá trị đối với một thuộc tính là không xác định đối với một số 
ví dụ học
36Học Máy – IT 4862
Tài liệu tham khảo
•T. M. Mitchell. Machine Learning. McGraw-Hill, 1997.
M N E i i d ti A t d I• . unez. conom c n uc on: case s u y. n 
Proceedings of the 3rd European Working Session on 
Learning, EWSL-88, pp.139-145. California: Morgan 
Kaufmann, 1988.
•M. Nunez. The use of background knowledge in decision 
tree induction. Machine Learning, 6(3): 231-250, 1991.
•M Tan and J C Schlimmer Two case studies in cost-. . . . 
sensitive concept acquisition. In Proceedings of the 8th 
National Conference on Artificial Intelligence, AAAI-90, 
pp.854-860, 1990.
37Học Máy – IT 4862