Học Máy (IT 4862)
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
Nguyễn Nhật Quang hậ ễ
Nội dung môn học: Nội d
ô h
(cid:132) Giới thiệu chungg
(cid:132) Đánh giá hiệu năng hệ thống học máy
(cid:132) Các phương pháp học dựa trên xác suất (cid:132) Các phương pháp học dựa trên xác suất
(cid:132) Các phương pháp học có giám sát
h
khô
iá
(cid:132) Các phương pháp học không giám sát át há h Cá (cid:132) Phân cụm dựa trên tích tụ phân cấp: HAC (Hierarchical agglomerative clustering)
(cid:132) Lọc cộng tác
(cid:132) Học tăng cường (cid:132) Học tăng cường
Học Máy (IT 4862)
2
HAC (1)
(cid:132) Sinh ra một chuỗi lồng nhau của các cụm, được gọi là
dendrogramg
• Cũng được gọi là một phân loại (taxonomy)/phân cấp
[Liu, 2006]
Học Máy (IT 4862)
3
(hierarchy)/cây (tree) của các ví dụ
HAC (2)
(cid:132) Phân cụm dựa trên tích tụ phân cấp (Hierarchical
Agglomerative Clustering HAC) sẽ xây dựng dendrogram Agglomerative Clustering – HAC) sẽ xây dựng dendrogram từ mức đáy (cuối) dần lên (bottom-up)
(cid:132) Giải thuật HAC (cid:132) Giải thuật HAC
• Bắt đầu, mỗi ví dụ chính là một cụm (là một nút trong dendrogram)
• Hợp nhất 2 cụm có mức độ tương tự (gần) nhau nhất ộ g ự (g ) ụ
ợp (cid:131) Cặp gồm 2 cụm có khoảng cách nhỏ nhất trong số các cặp cụm
• Tiếp tục quá trình hợp nhất
• Giải thuật kết thúc khi tất cả các ví dụ được hợp nhất thành một
Học Máy (IT 4862)
4
cụm duy nhất (là nút gốc trong dendrogram)
HAC – Ví dụụ
(Venn diagram)
[Liu, 2006]
Học Máy (IT 4862)
5
Khoảng cách giữa 2 cụm
ụ
g
g
(cid:132) Giải thuật HAC cần định nghĩa việc tính toán khoảng cách
giữa 2 cụm giữa 2 cụm
• Trước khi hợp nhất, cần tính khoảng cách giữa mỗi cặp 2 cụm có
(cid:132) Có nhiều phương pháp để đánh giá khoảng cách giữa 2
cụm – đưa đến các biến thể khác nhau của giải thuật HAC
thể
• Liên kết đơn (Single link)
• Liên kết hoàn toàn (Complete link)
• Liên kết trung bình (Average link) • Liên kết trung bình (Average link)
• Liên kết trung tâm (Centroid link)
Học Máy (IT 4862)
6
• …
HAC – Liên kết đơn
HAC liên kết đơn (Single link):
+ +
C1 C
(cid:131) Khoảng cách giữa 2 cụm là
+
C C2
khoảng cách nhỏ nhất giữa các ví dụ (các thành viên) của các ví dụ (các thành viên) của 2 cụm đó
(cid:131) Có xu hướng sinh ra các cụm Có xu hướng sinh ra các cụm có dạng “chuỗi dài” (long chain)
[Liu, 2006]
Học Máy (IT 4862)
7
HAC – Liên kết hoàn toàn
HAC liên kết hoàn toàn (Complete link): (Complete link):
+ +
C1 C1
(cid:131) Khoảng cách giữa 2 cụm là
+
g
g
C C2
khoảng cách lớn nhất giữa các ví dụ (các thành viên) của 2 cụm đó
ỗ
(cid:131) Nhạy cảm (gặp lỗi phân cụm) đối với các ngoại lai (outliers)
h ớ
i h
á
(cid:131) Có xu hướng sinh ra các cụm Có có dạng “bụi cây” (clumps)
[Liu, 2006]
Học Máy (IT 4862)
8
HAC – Liên kết trung bình
g
(cid:132) Khoảng cách trong liên kết trung bình (Average-link) là sự thỏa hiệp giữa các khoảng cách trong liên kết hoàn toàn thỏa hiệp giữa các khoảng cách trong liên kết hoàn toàn (Complete-link) và liên kết đơn (Single-link)
• Để giảm mức độ nhạy cảm (khả năng lỗi) của phương pháp phân cụm dựa trên liên kết hoàn toàn đối với các ngoại lai (outliers) ) t ê liê kết h à t à đối ới á i ( i l tli d
• Để giảm xu hướng sinh ra các cụm có dạng “chuỗi dài” của
(cid:132) Khoảng cách giữa 2 cụm là khoảng cách trung bình của
g
g
g
ụ
g
tất cả các cặp ví dụ (mỗi ví dụ thuộc về một cụm)
Học Máy (IT 4862)
9
phương pháp phân cụm dựa trên liên kết đơn (dạng “chuỗi dài” không phù hợp với khái niệm tự nhiên của một cụm)
HAC – Liên kết trung tâmg
HAC liên kết trung tâm (Centroid link):
(cid:132) Khoảng cách giữa 2 cụm là khoảng cách giữa 2 điểm trung tâm
ể
(centroids) của 2 cụm đó
+ +
C1 C
+
C2
Học Máy (IT 4862)
10
ạp Giải thuật HAC – Độ phức tạp
ộ p
ậ
(cid:132) Tất cả các biến thể của giải thuật HAC đều có độ phức
tạp tối thiểu mức O(r ) tạp tối thiểu mức O(r2)
(cid:132) Phương pháp phân cụm HAC liên kết đơn (Single-link) có (cid:132) Phương pháp phân cụm HAC liên kết đơn (Single-link) có
độ phức tạp mức O(r2)
(cid:132) Các phương pháp phân cụm HAC liên kết hoàn toàn (cid:132) Các phương pháp phân cụm HAC liên kết hoàn toàn
(Complete-link) và liên kết trung bình (Average-link) có độ phức tạp mức O(r2logr)
(cid:132) Do độ phức tạp cao, giải thuật HAC khó có thể áp dụng được đối với các tập dữ liệu có kích thước (rất) lớn
Học Máy (IT 4862)
11
•r: Tổng số các ví dụ (kích thước của tập dữ liệu)
Các hàm khoảng cách
g
(cid:132) Một thành phần quan trọng của các phương pháp phân
cụmcụm
(cid:132) Các hàm tính khoảng cách khác nhau đối với
• Cần xác định các hàm tính độ khác biệt (dissimilarity/distance functions), hoặc các hàm tính độ tương tự (similarity functions)
(cid:131) Dữ liệu kiểu số (Numeric data) (cid:131) Dữ liệu kiểu định danh (Nominal data)
• Các kiểu dữ liệu khác nhau
Học Máy (IT 4862)
12
Các bài toán ứng dụng cụ thể • Các bài toán ứng dụng cụ thể
Hàm khoảng cách cho thuộc tính số
(cid:132) Họ các hàm khoảng cách hình học (khoảng cách
Minkowski) Minkowski)
(cid:132) Các hàm được dùng phổ biến nhất
• Khoảng cách Euclid • Khoảng cách Euclid
(cid:132) Ký hiệu d(xi, xj) là khoảng cách giữa 2 ví dụ (2 vectơ) xi (cid:132) Ký hiệu d(x x ) là khoảng cách giữa 2 ví dụ (2 vectơ) x
và xj
(cid:132) Khoảng cách Minkowski (với p là một số nguyên dương) (cid:132) Khoảng cách Minkowski (với p là một số nguyên dương)
p
p
p
d
x
)
(
x
)
(
x
p /1 ])
−
+
−
... ++
−
[( x 1 i
1 j
x i
2
j
2
x in
jn
• Khoảng cách Manhattan (khoảng cách City-block)
i xx ,(
) =j
Học Máy (IT 4862)
13
Hàm k/c cho thuộc tính nhị phân
(cid:132) Sử dụng một ma trận để biểu diễn hàm tính
khoảng cách g
• a: Tổng số thuộc tính có giá trị là 1 trong cả xi và xj • b: Tổng số các thuộc tính có giá trị là 1 trong xi và
ví dụ xj 0
1
g
g j có giá trị là 0 trong xj
i
1
a b
• c: Tổng số các thuộc tính có giá trị là 0 trong xi và
có giá trị là 1 trong xj
c d
x ụ d 0v í
• d: Tổng số các thuộc tính có giá trị là 0 trong cả xi
và xj
(cid:132) Hệ số phù hợp đơn giản (Simple matching coefficient). Tỷ lệ sai lệch giá trị của các ỷ ệ sa ệc g á ị của các coe c e t) thuộc tính giữa 2 ví dụ:
d
( (
) =)
, , i xx i
j j
cb + dcba +++
Học Máy (IT 4862)
14
Hàm k/c cho thuộc tính định danh
(cid:132) Hàm khoảng cách cũng dựa trên phương pháp đánh giá
tỷ lệ khác biệt giá trị thuộc tính giữa 2 ví dụ tỷ lệ khác biệt giá trị thuộc tính giữa 2 ví dụ
(cid:132) Với 2 ví dụ xi và xj, ký hiệu p là tổng số các thuộc tính
(trong tập dữ liệu) và q là số các thuộc tính mà giá trị là (trong tập dữ liệu), và q là số các thuộc tính mà giá trị là như nhau trong xi và xj
d
(
=)
i xx ,
j
qp − p
Học Máy (IT 4862)
15
Tài liệu tham khảo
•B. Liu. Web Data Mining: Exploring Hyperlinks,
Học Máy (IT 4862)
16
g g p Contents, and Usage Data. Springer, 2006.
