Bài giảng Học máy - Bài 5: Cây phân loại và hồi quy - Nguyễn Thanh Tùng

Cây phân loại và hồi quy
Bài giảng có sử dụng hình vẽ trong cuốn sách “An Introduction to Statistical Learning with Applications in R” với sự
cho phép của tác giả, có sử dụng slides các khóa học CME250 của ĐH Stanford và IOM530 của ĐH Southern California
Nguyễn Thanh Tùng
Khoa Công nghệ thông tin – Đại học Thủy Lợi
tungnt@tlu.edu.vn
CSE 445: Học máy | Học kỳ 1, 2016-2017 1
Website môn học: https://sites.google.com/a/wru.vn/cse445fall2016
Các giải thuật Học máy
Cluster 
Analysis
Dimensionality 
Reduction
Classification Regression
KNN
Supervised Unsupervised
Yes No
Do you have 
labeled data?
Do you want to group the data?
Yes No
What do you want to predict?
Category Quantity
PCA
Logistic 
Regression
LASSO
ICA
Linear 
Regression K--means
Hierarchical 
Clustering NMF SOM
CSE 445: Học máy | Học kỳ 1, 2016-2017 2
Các giải thuật Học máy
Cluster 
Analysis
Dimensionality 
Reduction
Classification Regression
KNN
Supervised Unsupervised
Yes No
Do you have 
labeled data?
Do you want to group the data?
Yes No
What do you want to predict?
Category Quantity
PCA
Logistic 
Regression
CART LASSO
ICA
Linear 
Regression K--means
Hierarchical 
Clustering NMF SOM
CSE 445: Học máy | Học kỳ 1, 2016-2017 3
Cây quyết định
(Decision tree)
CSE 445: Học máy | Học kỳ 1, 2016-2017 4
• 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ọc cây quyết định có thể thực hiện ngay cả với các dữ liệu có chứa
nhiễu/lỗi (noisy data)
• Được áp dụng thành công trong rất nhiều các bài toán ứng dụng 
thực tế
Cây quyết định là gì?
nguồn: Nguyễn Nhật Quang-Học máy
CSE 445: Học máy | Học kỳ 1, 2016-2017 5
Ví dụ về DT: Những tin tức nào mà tôi quan tâm?
is present
“sport”?
is absent
“football”?“player”?
is present is absentis absent
is absent
is present
InterestedUninterestedInterested “goal”?
is present
Interested Uninterested
→ Interested
→ Interested
→ Uninterested
• (,“sport”,,“player”,)
• (,“goal”,)
• (,“sport”,)
Cây quyết định là gì?
CSE 445: Học máy | Học kỳ 1, 2016-2017 6
nguồn: Nguyễn Nhật Quang-Học máy
Ví dụ về DT: Một người có chơi tennis không?
Sunny
Outlook=?
Rain
Overcast
True
Humidity=?
High
Windy=?
FalseNormal
Yes
YesNo Yes No
• (Outlook=Overcast, Temperature=Hot, Humidity=High, Windy=False)
→ Yes
• (Outlook=Rain, Temperature=Mild, Humidity=High, Windy=True)
→ No
• (Outlook=Sunny, Temperature=Hot, Humidity=High, Windy=True)
→ No
Cây quyết định là gì?
CSE 445: Học máy | Học kỳ 1, 2016-2017 7
Cây quyết định là gì?
Hastie, Trevor, et al. The elements of statistical learning. Vol. 2. No. 1. New York: Springer, 2009.
CSE 445: Học máy | Học kỳ 1, 2016-2017 8
Cây quyết định là gì?
Hastie, Trevor, et al. The elements of statistical learning. Vol. 2. No. 1. New York: Springer, 2009.
CSE 445: Học máy | Học kỳ 1, 2016-2017 9
ĐÚNG SAI
Hastie, Trevor, et al. The elements of statistical learning. Vol. 2. No. 1. New York: Springer, 2009.
CSE 445: Học máy | Học kỳ 1, 2016-2017 10
Cây quyết định là gì?
Dữ liệu đầu vào của cây quyết định
CSE 445: Học máy | Học kỳ 1, 2016-2017 11
Biểu diễn cây quyết định
12
• Mỗi nút trong (internal node) biểu diễn một biến cần kiểm tra giá 
trị (a variable to be tested) đối với các mẫu
• Mỗi nhánh (branch) từ một nút sẽ tương ứng với một giá trị có 
thể của biến 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 mẫu, 
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 mẫu cần phân lớp
CSE 445: Học máy | Học kỳ 1, 2016-2017
Minh họa cây quyết định
Children
Realincom
e
Save_act
Married
Mortgage Mortgage
Save_act
Yes
No
Yes
Yes
Yes
No No
No
YES
NO
 0
YESNO
YES
YES
NO
NONO YES
 14996.4
CSE 445: Học máy | Học kỳ 1, 2016-2017 13
Tập luật từ cây quyết định
Rule #1
if children =< 0
and married == YES
and mortgage == YES
and save_act == NO
then -> YES (9.0, 0.889)
Rule #2
if children =< 0
and married == NO
and mortgage == NO
then -> YES (29.0, 0.931)
Rule #3
if children =< 0
and married == NO
and mortgage == YES
and save_act == NO
then -> YES (3.0, 1.0)
Rule #4
if children > 0
and realincome > 14996.4
then -> YES (85.0, 0.953)
CSE 445: Học máy | Học kỳ 1, 2016-2017 14
Tập luật từ cây quyết định
Rule #1
if children =< 0
and married == YES
and mortgage == NO
then -> NO (59.0, 0.898)
Rule #2
if children =< 0
and married == YES
and mortgage == YES
and save_act == YES
then -> NO (16.0, 0.875
Rule #3
if children =< 0
and married == NO
and mortgage == YES
and save_act == YES
then -> NO (12.0, 1.0)
Rule #4
if children > 0
and realincome =< 14996.4
then -> NO (87.0, 0.908)
CSE 445: Học máy | Học kỳ 1, 2016-2017 15
16
• 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 mẫu
• 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ị
biến (variable tests)
• Cây quyết định (bản thân nó) chính là một phép tuyển của 
các kết hợp này
Biểu diễn cây quyết định
CSE 445: Học máy | Học kỳ 1, 2016-2017
Tập dữ liệu Weather
[Mitchell,
1997]
Xét tập dữ liệu Weather ghi lại những ngày mà một người chơi (không chơi) tennis:
Day Outlook Temperature Humidity Windy Play Tennis
D1 Sunny Hot High FALSE No
D2 Sunny Hot High TRUE No
D3 Overcast Hot High FALSE Yes
D4 Rain Mild High FALSE Yes
D5 Rain Cool Normal FALSE Yes
D6 Rain Cool Normal TRUE No
D7 Overcast Cool Normal TRUE Yes
D8 Sunny Mild High FALSE No
D9 Sunny Cool Normal FALSE Yes
D10 Rain Mild Normal FALSE Yes
D11 Sunny Mild Normal TRUE Yes
D12 Overcast Mild High TRUE Yes
D13 Overcast Hot Normal FALSE Yes
D14 Rain Mild High TRUE No
CSE 445: Học máy | Học kỳ 1, 2016-2017 17
Mô hình cây QĐ có (không) chơi tennis
overcast
high normal FALSETRUE
sunny
rainy
no noyes yes
yes
Outlook
Humidity
Windy
CSE 445: Học máy | Học kỳ 1, 2016-2017 18
[(Outlook=Sunny) ∧
(Outlook=Overcast)
(Humidity=Normal)] ∨
∨
[(Outlook=Rain) ∧ (Windy=False)]
Xây dựng cây QĐ thế nào?
Phương pháp dựng cây theo Top-down
Ban đầu, tất cả các mẫu trong tập huấn luyện đều đặt tại nút gốc.
Tách các mẫu theo đệ quy bằng cách chọn 1 thuộc tính trong mỗi
lần tách cho đến khi gặp điều kiện dừng.
Phương pháp tỉa cây theo Bottom-up
Ban đầu dựng cây lớn nhất có thể
Chuyển phần cây con hoặc nhánh từ phần đáy của cây lên nhằm
cải thiện tính chính xác khi dự đoán mẫu mới
CSE 445: Học máy | Học kỳ 1, 2016-2017 19
• 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, biến kiểm tra (test variable) là biến có khả năng phân loại tốt nhất đối 
với các mẫu 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 biến kiểm 
tra, và tập huấn luyện 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 biến chỉ được phép xuất hiện tối đa 1 lần đối với bất kỳ một đường đi nào trong
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 mẫu, hoặc tất cả các thuộc tính đã được 
sử dụng
Giải thuật ID3
CSE 445: Học máy | Học kỳ 1, 2016-2017 20
Lựa chọn biến kiểm tra
• Tại mỗi nút, chọn biến kiểm tra như thế nào?
• Chọn biến quan trọng nhất cho việc phân lớp 
các mẫu gắn với nút đó
• Làm thế nào để đánh giá khả năng của một
biến đối với việc phân tách các mẫu theo 
nhãn lớp của chúng?
→ Sử dụng một đánh giá thống kê –
Information Gain
Với một số cây quyết định khác:
• Information gain ratio (C4.5)
• Gini index (CART)
overcast
high normal FALSETRUE
sunny
rainy
no noyes yes
yes
Outlook
Humidity
Windy
CSE 445: Học máy | Học kỳ 1, 2016-2017 21
Entropy
• Một đánh giá thường được sử dụng trong lĩnh vực lý thuyết thông tin 
(Information Theory)
• Để đánh giá mức độ hỗn tạp (impurity/inhomogeneity) của một tập
• Entropy của tập S đối với việc phân lớp có c lớp
c
Entropy(S ) =∑− pi .log2 pi
i=1
trong đó pi là tỷ lệ các mẫu 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
CSE 445: Học máy | Học kỳ 1, 2016-2017 22
Nguyễn Nhật Quang-Học máy
Entropy – Ví dụ với 2 lớp
• S gồm 14 mẫu, trong đó 9 mẫu thuộc về lớp c1
và 5 mẫu thuộc về lớp c2
• Entropy của tập S đối với phân lớp có 2 lớp:
Entropy(S) = 
-(9/14).log2 (9/14)-(5/14).log2(5/14) ≈0.94
1
0.5
0
1
E
n
t
r
o
p
y
(
S
)
0.5
p1
• Entropy =0, nếu tất cả các mẫu thuộc cùng một lớp (c1
hoặc c2)
• Entropy =1, số lượng các mẫu thuộc về lớp c1 bằng số 
lượng các mẫu thuộc về lớp c2
• Entropy = một giá trị trong khoảng (0,1), nếu như số 
lượng các mẫu thuộc về lớp c1 khác với số lượng các mẫu
thuộc về lớp c2
23
Nguyễn Nhật Quang-Học máy
CSE 445: Học máy | Học kỳ 1, 2016-2017
Information gain
■ Information Gain của một biến đối với một tập các mẫu:
•Mức độ giảm về Entropy
•Bởi việc phân tách (partitioning) các mẫu theo các giá trị của biến đó
■ Information Gain của biến A đối với tập S
v
| Sv |Entropy(S )| S |∑v∈Values(A)Gain(S, A) = Entropy(S) −
trong đó Values(A) là tập các giá trị có thể của biến 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 biến 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 nhiên từ tập S, khi biết giá trị 
của biến A
24
Nguyễn Nhật Quang-Học máy
CSE 445: Học máy | Học kỳ 1, 2016-2017
Weather-Tìm các khả năng tách
CSE 445: Học máy | Học kỳ 1, 2016-2017 25
Hãy tính giá trị Information Gain của biến Windy đối với tập học S
– Gain(S,Windy)?
Biến Windy có 2 giá trị có thể: False và True
S = {9 mẫu lớp Yes và 5 mẫu lớp No}
SFalse = {6 mẫu lớp Yes và 2 mẫu lớp No có giá trị Windy=False}
STrue = {3 mẫu lớp Yes và 3 mẫu lớp No có giá trị Windy=True}
∑
v∈{False,True}
Entropy(Sv)| S |
| Sv |Gain(S,Windy ) = Entropy(S ) −
= Entropy(S ) − (8 /14).Entropy(SFalse ) − (6 /14).Entropy(STrue )
= 0.94 − (8 /14).(0.81) − (6 /14).(1) = 0.048 bits
Biến Windy
Entropy(S) = -(9/14).log2 (9/14)-(5/14).log2(5/14) ≈ 0.94
CSE 445: Học máy | Học kỳ 1, 2016-2017 26
Biến Outlook
witten&eibe CSE 445: Học máy | Học kỳ 1, 2016-2017 27
Entropy của mỗi tập con bị tách do biến Outlook
• “Outlook” = “Sunny”
• “Outlook” = “Overcast”
• “Outlook” = “Rainy”
• Thông tin kỳ vọng của biến Outlook:
bits 971.0)5/3log(5/3)5/2log(5/25,3/5)entropy(2/)info([2,3] =−−==
bits 0)0log(0)1log(10)entropy(1,)info([4,0] =−−==
bits 971.0)5/2log(5/2)5/3log(5/35,2/5)entropy(3/)info([3,2] =−−==
Chú ý: log(0) 
không xác định, 
tuy nhiên ta tính
quy ước 0*log(0) 
là 0
bits 693.0971.0)14/5(0)14/4(971.0)14/5([3,2])[4,0],,info([3,2] =×+×+×=
CSE 445: Học máy | Học kỳ 1, 2016-2017 28
Tính Information Gain
• Information gain=(thông tin trước khi tách) – (thông tin sau khi
tách)
• Tương tự, ta tính được Information gain cho các biến trong tập
dữ liệu weather:
• Vậy Outlook là biến được chọn để kiểm tra cho nút gốc vì có
Information Gain cao nhất
0.693-0.940[3,2])[4,0],,info([2,3]-)info([9,5]Outlook) Gain(S, ==
bits 247.0=
bits 247.0Outlook) Gain(S, =
bits 029.0e)Temperatur Gain(S, =
bits 152.0Humidity) Gain(S, =
bits 048.0Windy)Gain(S, =
CSE 445: Học máy | Học kỳ 1, 2016-2017 29
→Outlook được chọn là biến kiểm tra tại nút gốc!
Outlook=?
OvercastSunny Rain
S={9+, 5-}
Yes
SOvercast={4+, 0-}
Node1
SSunny={2+, 3-}
Node2
SRain={3+, 2-}
Tính Information Gain
30CSE 445: Học máy | Học kỳ 1, 2016-2017
Outlook=? S={9+, 5-}
Overcast
Sunny
RainSSunny=
{2+, 3-}
Humidity=? Yes
SOvercast=
{4+, 0-}
Node2
SRain=
{3+, 2-}
High
Node3
SHigh=
{0+, 3-}
Normal
Node4
SNormal=
{2+, 0-}
■Tại nút Node1, biến nào trong số 
{Temperature, Humidity, Windy} nên
được chọn là biến kiểm tra?
Lưu ý! Biến Outlook bị loại ra, bởi vì nó đã được 
sử dụng bởi cha của nút Node1(là nút gốc)
•Gain(SSunny, Temperature) =...= 0.57
•Gain(SSunny, Humidity) = ... = 0.97
•Gain(SSunny, Windy) = ... = 0.019
→Vì vậy, Humidity được chọn là biến
kiểm tra cho nút Node1!
Tiếp tục tách nút
31CSE 445: Học máy | Học kỳ 1, 2016-2017
Điều kiện dừng
• Lượng dữ liệu của 1 nút được gán hầu hết vào 1 lớp
vd: >90%
• Số lượng mẫu trong tập con tại nút nhỏ hơn 1 giá trị
cho trước – ngưỡng (threshold)
• Giảm được Information gain
• Các biến đều đã được kiểm tra
CSE 445: Học máy | Học kỳ 1, 2016-2017 32
Cây quyết định dựng được
CSE 445: Học máy | Học kỳ 1, 2016-2017 33
• Cây quyết định học được quá phù hợp 
(over-fit) với các mẫu
• Xử lý các biến có kiểu giá trị liên tục 
(kiểu số thực)
Vấn đề trong ID3
CSE 445: Học máy | Học kỳ 1, 2016-2017 34
Sunny
Outlook=?
RainOvercast
False
Windy=?
True
YesHumidity=?
High Normal
No Yes No Yes
Học được một cây quyết định phức tạp hơn! 
(chỉ bởi vì mẫu nhiễu/lỗi)
• Một cây quyết định phù hợp hoàn hảo 
đối với tập huấn luyện có phải là giải 
pháp tối ưu?
• Nếu như tập huấn luyện có 
nhiễu/lỗi?
Vd: Một mẫu nhiễu/lỗi (Mẫu thực sự mang 
nhãn Yes, nhưng bị gán nhãn nhầm là No):
(Outlook=Sunny, Temperature=Hot, 
Humidity=Normal, Windy=True,
PlayTennis=No)
Sunny
Outlook=?
RainOvercast
False
Windy=?
True
Humidity=?
High Normal
Yes
No được phát
triển tiếp!
No Yes
Over-fitting trong học cây quyết định
CSE 445: Học máy | Học kỳ 1, 2016-2017 35
Nguyễn Nhật Quang-Học máy
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 huấn luyện
[Mitchell, 1997]
Over-fitting trong học cây quyết định
CSE 445: Học máy | Học kỳ 1, 2016-2017 36
• Hai 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àntoà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!
Giải quyết vấn đề over-fitting
CSE 445: Học máy | Học kỳ 1, 2016-2017 37
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 v “tốt nhất”?
→ 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 mẫu theo giá trị tăng dần đối với thuộc tính Temperature
• Xác định các mẫu 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
CSE 445: Học máy | Học kỳ 1, 2016-2017 38
Cây phân loại và hồi quy
Classification and Regression Trees
(CART)
CSE 445: Học máy | Học kỳ 1, 2016-2017 39
Xây dựng cây CART thế nào?
Có 2 dạng:
1.Hồi quy
2.Phân loại (lớp)
CSE 445: Học máy | Học kỳ 1, 2016-2017 40
Mô hình liên tục từng đoạn(piecewise)
• Dự đoán liên tục trong mỗi vùng
Hastie, Trevor, et al. The elements of statistical learning. Vol. 2. No. 1. New York: Springer, 2009.
CSE 445: Học máy | Học kỳ 1, 2016-2017 41
Mô hình liên tục từng đoạn
Hastie, Trevor, et al. The elements of statistical learning. Vol. 2. No. 1. New York: Springer, 2009.
CSE 445: Học máy | Học kỳ 1, 2016-2017 42
Minh họa cây CART
1 TYPE OFHOME
1.House
5 EDUCATION
1. Grade 8 or less
8 HOW LONG HAVE YOU LIVED IN THE SAN 
FRAN./OAKLAND/SAN JOSE AREA?
2. Condominium
3. Apartment
4. Mobile Home
5. Other
2. Grades 9 to11
3. Graduated high school
4. 1 to 3 years of college
5. College graduate
1. Less than one year
2. One to three years
3. Four to sixyears
4. Seven to tenyears
6. GradStudy 5. More than tenyears
2 SEX
3
1. Male
2. Female
MARITALSTATUS
6 OCCUPATION
1. Professional/Managerial
2. SalesWorker
3. FactoryWorker/Laborer/Driver
9 DUAL INCOMES (IFMARRIED)
1. NotMarried
2. Yes
3. No
1.Married 4. Clerical/Service Worker
2. Living together, notmarried
3. Divorced orseparated
4. Widowed
5. Single, nevermarried
5. Homemaker
6. Student, HS orCollege
7. Military
8. Retired
10 PERSONS IN YOUR HOUSEHOLD
1. One
2. Two
3. Three
9. Unemployed 4.Four
4 AGE
1. 14 thru17 7 ANNUAL INCOME OF HOUSEHOLD (PERSONAL INCOMEIF
5. Five
6. Six
2. 18 thru24
3. 25 thru34
SINGLE
1. Less than $10,000
7. Seven
8. Eight
4. 35 thru44 2. $10,000 to$14,999 9. Nine or more
3. $15,000 to$19,999
4. $20,000 to$24,999
5. $25,000 to$29,999
CSE 445: Học máy | Học kỳ 1, 2016-2017 43
Hồi quy
Minh họa cây CART
own_rent_family=1,3
persons_in_house>=2.5
income>=2.5
persons_under_18>=0.5
job=1,2,3,4,5,6,8,9
1.241
1.446
job=1,2,3,4,5,6,8,9
1.843 3.8
persons_in_house>=3.5
1.908 2.461
2.651
residence_time>=2.
2.421 3.8
CSE 445: Học máy | Học kỳ 1, 2016-2017 44
Minh họa cây CART
Phân lớp
CSE 445: Học máy | Học kỳ 1, 2016-2017 45
Cây hồi quy
CSE 445: Học máy | Học kỳ 1, 2016-2017 46
Giá trị dự đoán lưu tại lá của cây hồi quy. Nó được tính bằng
giá trị trung bình của tất cả các mẫu (bản ghi) tại lá đó.
Cây hồi quy
• Giả sử ta có 2 vùng R1 và R2 với
• Với các giá trị của X mà ta sẽ có giá trị
dự đoán là 10, ngược lại ta có kết quả dự
đoán là 20. 
20ˆ,10ˆ 21 == YY
1RX ∈
2RX ∈
CSE 445: Học máy | Học kỳ 1, 2016-2017 47
Cây hồi quy
• Cho 2 biến đầu vào
và 5 vùng
• Tùy theo từng vùng
của giá trị mới X ta 
sẽ có dự đoán 1 
trong 5 giá trị cho Y.
22
12
9
34
23
CSE 445: Học máy | Học kỳ 1, 2016-2017 48
Tách các biến X
Ta tạo ra các phân
vùng bằng cách
tách lặp đi lặp lại
một trong các biến
X thành hai vùng
CSE 445: Học máy | Học kỳ 1, 2016-2017 49
Tách các biến X
1. Đầu tiên tách
trên X1=t1
CSE 445: Học máy | Học kỳ 1, 2016-2017 50
Tách các biến X
1. Đầu tiên tách
trên X1=t1
2. Nếu X1<t1, 
tách trên X2=t2
CSE 445: Học máy | Học kỳ 1, 2016-2017 51
Tách các biến X
1. Đầu tiên tách
trên X1=t1
2. Nếu X1<t1, 
tách trên X2=t2
3. Nếu X1>t1, 
tách trên X1=t3
CSE 445: Học máy | Học kỳ 1, 2016-2017 52
Tách các biến X
1. Đầu tiên tách
trên X1=t1
2. Nếu X1<t1, 
tách trên X2=t2
3. Nếu X1>t1, 
tách trên X1=t3
4. Nếu X1>t3, 
tách X2=t4
CSE 445: Học máy | Học kỳ 1, 2016-2017 53
Tách các biến X
• Khi ta tạo các vùng theo
phương pháp này, ta có thể
biểu diễn chúng dùng cấu trúc
cây.
• Phương pháp này dễ diễn giải
mô hình dự đoán, dễ diễn giải
kết quả
CSE 445: Học máy | Học kỳ 1, 2016-2017 54
Giải thuật tham lam: hồi quy
CSE 445: Học máy | Học kỳ 1, 2016-2017 55
• Tìm thuộc tính tách và điểm
tách mà nó cực tiểu lỗi dự đoán
Cây phân lớp
CSE 445: Học máy | Học kỳ 1, 2016-2017 56
Giải thuật tham lam: phân lớp
• Nhiều độ đo cho lỗi dự đoán (độ
hỗn tạp của nút-node impurity)
Hastie, Trevor, et al. The elements of statistical learning. Vol. 2. No. 1. New York: Springer, 2009.
CSE 445: Học máy | Học kỳ 1, 2016-2017 57
Giải thuật tham lam: phân lớp
• Nhiều độ đo cho lỗi dự đoán (độ
hỗn tạp của nút-node impurity)
Hastie, Trevor, et al. The elements of statistical learning. Vol. 2. No. 1. New York: Springer, 2009.
CSE 445: Học máy | Học kỳ 1, 2016-2017 58
Độ hỗn tạp của nút khi phân lớp
Hastie, Trevor, et al. The elements of statistical learning. Vol. 2. No. 1. New York: Springer, 2009.
CSE 445: Học máy | Học kỳ 1, 2016-2017 59
Classification node impurity
Ưu điểm của CART
• Dễ xử lý dữ liệu thiếu (surrogate splits)
• Mạnh trong xử lý dữ liệu chứa thông tin rác
(non-informative data)
• Cho phép tự động lựa chọn thuộc tính (variable
selection)
• Dễ giải thích, lý tưởng để giải thích “tại sao” đối với
người ra quyết định
• Xử lý được tính tương tác cao giữa các thuộc tính
CSE 445: Học máy | Học kỳ 1, 2016-2017 60
Ưu điểm của CART
Dễ giải thích, lý tưởng để lý giải “tại
sao” cho người ra quyết định
CSE 445: Học máy | Học kỳ 1, 2016-2017 61
Ưu điểm của CART
Xử lý được tính tương tác cao giữa các thuộc tính
Y = β0 + β1 x1 + β2 x2 
Y = β0 + β1 x1 + β2 x2 + θ1 x1 x2 + θ2 x1 x3 + θ3 x2 x3 + λ1 x1 x2 x3 
Y = 3.5 if ((1<marital_status<6) AND (1<job<9)) AND (age<1.5) OR 
CSE 445: Học máy | Học kỳ 1, 2016-2017 62
Nhược điểm của CART
• Cây không ổn định (Instability of trees)
• Thiếu tính trơn (Lack of smoothness)
• Khó nắm bắt độ cộng tính (Hard to capture
additivity)
CSE 445: Học máy | Học kỳ 1, 2016-2017 63
Nhược điểm của CART
Cây không ổn định
CSE 445: Học máy | Học kỳ 1, 2016-2017 64
Nhược điểm của CART
Thiếu tính trơn (Smoothness)
CSE 445: Học máy | Học kỳ 1, 2016-2017 65
Nhược điểm của CART
Khó nắm bắt độ cộng tính (additivity)
Y = c1 I ( X1 < t1 ) + c2 I ( X2 < t2 ) + e
Hastie, Trevor, et al. Introduction 
to statistical learning.
CSE 445: Học máy | Học kỳ 1, 2016-2017 66
Nhược điểm của CART
1. Cây không ổn định
Giải pháp -- Random Forests
2. Thiếu tính trơn
Giải pháp -- MARS
3. Khó nắm bắt độ cộng tính (additivity)
Giải pháp – MART or MARS
CSE 445: Học máy | Học kỳ 1, 2016-2017 67
MART – “Multiple Additive Regression Trees”
MARS – “Multivariate Adaptive Regression Splines”
Câu hỏi?
CSE 445: Học máy | Học kỳ 1, 2016-2017 68