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 2: Học dựa trên các láng giềng gần nhất - 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 dựa trên các láng giềng gần nhất (Nearest 
neighbors learning)
„ Các phương pháp học không giám sát
„ Lọc cộng tác
„ Học tăng cường
2
Học Máy – IT 4862
Học dựa trên các láng giềng gần nhất
„ Một số tên gọi khác của phương pháp học dựa trên các láng
giềng gần nhất (Nearest neighbors learning)
• Instance-based learning
• Lazy learning
• Memory-based learning 
„ Ý tưởng của phương pháp học dựa trên các láng giềng gần nhất
• Với một tập các ví dụ học
─ (Đơn giản là) lưu lại các ví dụ học
─ Chưa xây dựng một mô hình (mô tả) rõ ràng và tổng quát của
hàm mục tiêu cần học
• Đối với một ví dụ cần phân loại/dự đoán
─ Xét quan hệ giữa ví dụ đó với các ví dụ học để gán giá trị của
3Học Máy – IT 4862
hàm mục tiêu (một nhãn lớp, hoặc một giá trị thực)
Học dựa trên các láng giềng gần nhất
„ Biểu diễn đầu vào của bài toán
• Mỗi ví dụ x được biểu diễn là một vectơ n chiều trong không gian 
các vectơ X∈Rn
• x = (x1,x2,,xn), trong đó xi (∈R) là một số thực
C ể ả ể„ ó th áp dụng được với c 2 ki u bài toán học
• Bài toán phân lớp (classification)
─ Hàm mục tiêu có giá trị rời rạc (a discrete-valued target function)
─ Đầu ra của hệ thống là một trong số các giá trị rời rạc đã xác định 
trước (một trong các nhãn lớp)
• Bài toán dự đoán/hồi quy (prediction/regression) 
─ Hàm mục tiêu có giá trị liên tục (a continuous-valued target function)
─ Đầu ra của hệ thống là một giá trị số thực
4Học Máy – IT 4862
Ví dụ bài toán phân lớp
Lớp c1 Lớp c2
„ Xét 1 láng giềng gần
Ví dụ cần 
phân lớp z
nhất
→Gán z vào lớp c2
„ Xét 3 láng giềng gần
nhất
→Gán z vào lớp c1
„ Xét 5 láng giềng gần
nhất
→Gán z vào lớp c1
5Học Máy – IT 4862
Giải thuật phân lớp k-NN
„ Mỗi ví dụ học x được biểu diễn bởi 2 thành phần:
• Mô tả của ví dụ: x=(x1,x2,,xn), trong đó xi∈R
• Nhãn lớp : c (∈C, với C là tập các nhãn lớp được xác định trước)
„ Giai đoạn học
• Đơn giản là lưu lại các ví dụ học trong tập học: D = {x}
„ Giai đoạn phân lớp: Để phân lớp cho một ví dụ (mới) z
• Với mỗi ví dụ học x∈D, tính khoảng cách giữa x và z
• Xác định tập NB(z) – các láng giềng gần nhất của z
→Gồm k ví dụ học trong D gần nhất với z tính theo một hàm 
khoảng cách d
• Phân z vào lớp chiếm số đông (the majority class) trong số các lớp 
ủ á í d h t NB( )
6Học Máy – IT 4862
c a c c v ụ ọc rong z
Giải thuật dự đoán k-NN
„ Mỗi ví dụ học x được biểu diễn bởi 2 thành phần:
• Mô tả của ví dụ: x=(x1,x2,,xn), trong đó xi∈R
• Giá trị đầu ra mong muốn: yx∈R (là một số thực)
„ Giai đoạn học
• Đơn giản là lưu lại các ví dụ học trong tập học D
„ Giai đoạn dự đoán: Để dự đoán giá trị đầu ra cho ví dụ z
• Đối với mỗi ví dụ học x∈D, tính khoảng cách giữa x và z
• Xác định tập NB(z) – các láng giềng gần nhất của z
→ Gồm k ví dụ học trong D gần nhất với z tính theo một hàm khoảng
∑= )(1 NB xz yy
cách d
• Dự đoán giá trị đầu ra đối với z:
7Machine Learning: Algorithms and Applications
∈ zxk
Họ Máy – IT 4862
Một hay nhiều láng giềng gần nhất?
„ Việc phân lớp (hay dự đoán) chỉ dựa trên duy nhất một láng 
giềng gần nhất (là ví dụ học gần nhất với ví dụ cần phân 
lớp/dự đoán) thường không chính xác
• Nếu ví dụ học này là một ví dụ bất thường, không điển hình (an 
outlier) – rất khác so với các ví dụ khác
• Nếu ví dụ học này có nhãn lớp (giá trị đầu ra) sai – do lỗi trong 
quá trình thu thập (xây dựng) tập dữ liệu
ề ầ ấ„ Thường xét k (>1) các ví dụ học (các láng gi ng) g n nh t với 
ví dụ cần phân lớp/dự đoán
Đối với bài toán phân lớp có 2 lớp k thường được chọn là„ , 
một số lẻ, để tránh cân bằng về tỷ lệ các ví dụ giữa 2 lớp
• Ví dụ: k= 3, 5, 7,
8Học Máy – IT 4862
Hàm tính khoảng cách (1)
„ Hàm tính khoảng cách d
• Đóng vai trò rất quan trọng trong phương pháp học dựa trên các 
láng giềng gần nhất
• Thường được xác định trước, và không thay đổi trong suốt quá 
trình học và phân loại/dự đoán 
„ Lựa chọn hàm khoảng cách d
Cá hà kh ả á h hì h h Dà h h á bài t á ó á• c m o ng c c n ọc: n c o c c o n c c c 
thuộc tính đầu vào là kiểu số thực (xi∈R)
• Hàm khoảng cách Hamming: Dành cho các bài toán có các 
ầ ể ( { })thuộc tính đ u vào là ki u nhị phân xi∈ 0,1
• Hàm tính độ tương tự Cosine: Dành cho các bài toán phân lớp 
văn bản (xi là giá trị trọng số TF/IDF của từ khóa thứ i)
9Học Máy – IT 4862
Hàm tính khoảng cách (2)
„ Các hàm tính khoảng cách hình học (Geometry distance 
functions)
∑
=
−=
n
i
ii zxzxd
1
),(
n
• Hàm Minkowski (p-norm):
( )∑
=
−=
i
ii zxzxd
1
2),(
pn
p
/1
⎟⎞⎜⎛∑
• Hàm Manhattan (p=1):
i
ii zxzxd
1
),( ⎠⎝ −= =
pn
pd
/1
li)( ⎟⎞⎜⎛∑
• Hàm Euclid (p=2):
Hàm Chebyshev (p=∞):
iii
zx −= max
i
iip
zxzx
1
m, ⎠⎝ −= =∞→
•
10Học Máy – IT 4862
Hàm tính khoảng cách (3)
∑= n ii zxDifferencezxd ),(),(
„ Hàm khoảng cách 
Hamming
=i 1
⎩⎨
⎧
=
≠=
)(,0
)(,1
),(
baif
baif
baDifference
• Đối với các thuộc tính đầu
vào là kiểu nhị phân ({0,1})
∑n
• Ví dụ: x=(0,1,0,1,1)
∑∑
===
nn
i
ii
zx
zx
zx
zxzxd
22
1.),(
„ Hàm tính độ tương tự
Cosine
ố ầ == i
i
i
i
11
• Đ i với đ u vào là một vectơ
các giá trị trọng số (TF/IDF) 
của các từ khóa
11Học Máy – IT 4862
Chuẩn hóa miền giá trị thuộc tính
( )∑
=
−=
n
i
ii zxzxd
1
2),(„ Hàm tính khoảng cách Euclid:
„ Giả sử mỗi ví dụ được biểu diễn bởi 3 thuộc tính: Age, Income (cho
mỗi tháng), và Height (đo theo mét)
• x = (Age=20, Income=12000, Height=1.68)
• z = (Age=40, Income=1300, Height=1.75)
„ Khoảng cách giữa x và z
• d(x z) = [(20-40)2 + (12000-1300)2 + (1 68-1 75)2]1/2, . .
• Giá trị khoảng cách bị quyết định chủ yếu bởi giá trị khoảng cách (sự khác
biệt) giữa 2 ví dụ đối với thuộc tính Income
→Vì: Thuộc tính Income có miền giá trị rất lớn so với các thuộc tính khác 
„ Cần phải chuẩn hóa miền giá trị (đưa về cùng một khoảng giá trị)
• Khoảng giá trị [0,1] thường được sử dụng
Đối ới ỗi th ộ tí h i / l(f )
12Học Máy – IT 4862
• v m u c n : xi = xi max_va i
Trọng số của các thuộc tính
( )∑
=
−=
n
i
ii zxzxd
1
2),(„ Hàm khoảng cách Euclid:
• Tất cả các thuộc tính có cùng (như nhau) ảnh hưởng đối với giá trị
khoảng cách
„ Các thuộc tính khác nhau có thể (nên) có mức độ ảnh hưởng
n
khác nhau đối với giá trị khoảng cách
„ Cần phải tích hợp (đưa vào) các giá trị trọng số của các thuộc tính
trong hàm tính khoảng cách ( )∑
=
−=
i
iii zxwzxd
1
2),(•wi là trọng số của thuộc tính i:
„ Làm sao để xác định các giá trị trọng số của các thuộc tính?
• Dựa trên các tri thức cụ thể của bài toán (vd: được chỉ định bởi các
chuyên gia trong lĩnh vực của bài toán đang xét)
• Bằng một quá trình tối ưu hóa các giá trị trọng số (vd: sử dụng một tập
ể ố ố
13Học Máy – IT 4862
học đ học một bộ các giá trị trọng s t i ưu)
Khoảng cách của các láng giềng (1)
Ví d ầ
„ Xét tập NB(z) – gồm k ví dụ học gần 
nhất với ví dụ cần phân lớp/dự đoán z ụ c n 
phân loại z
• Mỗi ví dụ (láng giềng gần nhất) này có 
khoảng cách khác nhau đến z
ề ả ở• Các láng gi ng này có nh hư ng như 
nhau đối với việc phân lớp/dự đoáncho 
z? → KHÔNG!
„ Cần gán các mức độ ảnh hưởng (đóng 
góp) của mỗi láng giềng gần nhất tùy 
theo khoảng cách của nó đến z 
• Mức độ ảnh hưởng cao hơn cho các 
láng giềng gần hơn!
14Học Máy – IT 4862
Khoảng cách của các láng giềng (2)
„ Gọi v là hàm xác định trọng số theo khoảng cách
• Đối với một giá trị d(x,z) – khoảng cách giữa x và z
tỷ lệ hị h ới
∑
∈∈
=
)(
))(,().,(maxarg)(
zNBx
j
Cc
xccIdenticalzxvzc
j
⎧
•v(x,z) ng c v d(x,z)
„ Đối với bài toán phân lớp:
⎩⎨ ≠
==
)(,0
)(,1
),(
baif
baif
baIdentical
∑ )().,( xfzxv
∑
∈
∈=
)(
)(
),(
)(
zNBx
zNBx
zxv
zf„ Đối với bài toán dự đoán (hồi quy):
)(
1),(
zxd
zxv += α 2)]([
1),(
zxd
zxv += α
2
2),(
),( σ
zxd
ezxv
−=
„ Lựa chọn một hàm xác định trọng số theo khoảng cách:
, ,
15Học Máy – IT 4862
Lazy learning vs. Eager learning
„ Lazy learning. Việc đánh giá hàm mục tiêu (target function) 
được hoãn lại cho đến khi xét ví dụ cần phân loại/dự đoán
• Đánh giá (xấp xỉ) hàm mục tiêu một cách cục bộ (locally) và riêng rẽ
(diferrently) cho mỗi ví dụ cần phân loại/dự đoán (tại thời điểm phân
loại/dự đoán của hệ thống)
Tí h t á hiề lầ á ấ ỉ bộ ủ hà tiê• n o n n u n c c x p x cục c a m mục u
• Thường mất thời gian lâu hơn để đưa ra kết luận (phân lớp/dự đoán), và
cần nhiều không gian nhớ hơn
• Ví dụ: Nearest neighbor learner Locally weighted regression , 
„ Eager learning. Việc đánh giá hàm mục tiêu được hoàn thành
trước khi xét đến bất kỳ ví dụ cần phân loại/dự đoán
• Đánh giá (xấp xỉ) hàm mục tiêu một cách tổng thể (globally) đối với toàn
bộ không gian các ví dự (tại thời điểm học của hệ thống)
• Tính toán một xấp xỉ duy nhất (ở mức tổng thể) của hàm mục tiêu
16Học Máy – IT 4862
• Ví dụ: Linear regression, Support vector machines, Neural networks, ...
k-NN – Khi nào?
„ Các ví dụ được biểu diễn trong không gian vectơ Rn
„ Số lượng các thuộc tính (để biểu diễn ví dụ) là không nhiều
„ Một tập học có kích thước lớn
„ Các ưu điểm
Chi hí thấ h á t ì h h ấ l ệ ( hỉ iệ l l i á í d h )• p p c o qu r n u n uy n c v c ưu ạ c c v ụ ọc
• Hoạt động tốt với các bài toán phân loại gồm nhiều lớp
→ Không cần phải học n bộ phân loại cho n lớp
• Phương pháp học k-NN (k >>1) có khả năng xử lý nhiễu cao
→ Phân loại/dự đoán được thực hiện dựa trên k láng giềng gần nhất
„ Các nhược điểm 
• Phải lựa chọn hàm tính khoảng cách (sự khác biệt) thích hợp với bài toán
• Chi phí tính toán (thời gian, bộ nhớ) cao tại thời điểm phân loại/dự đoán
• Có thể cho kết quả kém/sai với các thuộc tính không liên quan 
17Học Máy – IT 4862