Bài giảng Khai phá dữ liệu - Chương 5: Gom cụm dữ liệu - Võ Thị Ngọc Châu

11
Chương 5: Gom cụm dữ liệu
Học kỳ 1 – 2011-2012
Khoa Khoa Học & Kỹ Thuật Máy Tính
Trường Đại Học Bách Khoa Tp. Hồ Chí Minh
Cao Học Ngành Khoa Học Máy Tính
Giáo trình điện tử
Biên soạn bởi: TS. Võ Thị Ngọc Châu
(chauvtn@cse.hcmut.edu.vn)
22
Tài liệu tham khảo
‡ [1] Jiawei Han, Micheline Kamber, “Data Mining: Concepts and 
Techniques”, Second Edition, Morgan Kaufmann Publishers, 2006.
‡ [2] David Hand, Heikki Mannila, Padhraic Smyth, “Principles of Data 
Mining”, MIT Press, 2001.
‡ [3] David L. Olson, Dursun Delen, “Advanced Data Mining 
Techniques”, Springer-Verlag, 2008.
‡ [4] Graham J. Williams, Simeon J. Simoff, “Data Mining: Theory, 
Methodology, Techniques, and Applications”, Springer-Verlag, 2006.
‡ [5] Hillol Kargupta, Jiawei Han, Philip S. Yu, Rajeev Motwani, and 
Vipin Kumar, “Next Generation of Data Mining”, Taylor & Francis 
Group, LLC, 2009.
‡ [6] Daniel T. Larose, “Data mining methods and models”, John Wiley 
& Sons, Inc, 2006.
‡ [7] Ian H.Witten, Eibe Frank, “Data mining : practical machine 
learning tools and techniques”, Second Edition, Elsevier Inc, 2005. 
‡ [8] Florent Messeglia, Pascal Poncelet & Maguelonne Teisseire, 
“Successes and new directions in data mining”, IGI Global, 2008.
‡ [9] Oded Maimon, Lior Rokach, “Data Mining and Knowledge 
Discovery Handbook”, Second Edition, Springer Science + Business
Media, LLC 2005, 2010.
33
Nội dung
‡ Chương 1: Tổng quan về khai phá dữ liệu
‡ Chương 2: Các vấn đề tiền xử lý dữ liệu
‡ Chương 3: Hồi qui dữ liệu
‡ Chương 4: Phân loại dữ liệu
‡ Chương 5: Gom cụm dữ liệu
‡ Chương 6: Luật kết hợp
‡ Chương 7: Khai phá dữ liệu và công nghệ cơ sở
dữ liệu
‡ Chương 8: Ứng dụng khai phá dữ liệu
‡ Chương 9: Các đề tài nghiên cứu trong khai phá
dữ liệu
‡ Chương 10: Ôn tập
44
Chương 5: Gom cụm dữ liệu
‡ 5.1. Tổng quan về gom cụm dữ liệu
‡ 5.2. Gom cụm dữ liệu bằng phân hoạch
‡ 5.3. Gom cụm dữ liệu bằng phân cấp
‡ 5.4. Gom cụm dữ liệu dựa trên mật độ
‡ 5.5. Gom cụm dữ liệu dựa trên mô hình
‡ 5.6. Các phương pháp gom cụm dữ liệu khác
‡ 5.7. Tóm tắt
55
Chương 5: Gom cụm dữ liệu
Phần 1
66
5.0. Tình huống 1 – Outlier detection
Người đang sử dụng 
thẻ ID = 1234 thật 
sự là chủ nhân của 
thẻ hay là một tên 
trộm?
77
5.0. Tình huống 2 - Làm sạch dữ liệu
‡ Nhận diện phần tử biên (outliers) và giảm
thiểu nhiễu (noisy data)
„ Giải pháp giảm thiểu nhiễu
‡ Phân tích cụm (cluster analysis)
88
5.0. Tình huống 3
99
5.0. Tình huống 3
10
10
5.0. Tình huống 3
11
11
5.0. Tình huống 3
12
12
5.0. Tình huống 3
13
13
5.0. Tình huống 3
14
14
5.0. Tình huống 3
15
15
5.0. Tình huống 4
Gom cụm ảnh
16
16
5.0. Tình huống 
Gom cụm
17
17
5.0. Tình huống 
‡ Hỗ trợ giai đoạn tiền xử lý dữ liệu (data 
preprocessing)
‡ Mô tả sự phân bố dữ liệu/đối tượng (data 
distribution)
‡ Nhận dạng mẫu (pattern recognition)
‡ Phân tích dữ liệu không gian (spatial data analysis)
‡ Xử lý ảnh (image processing)
‡ Phân mảnh thị trường (market segmentation)
‡ Gom cụm tài liệu ((WWW) document clustering)
‡ 
18
18
5.1. Tổng quan về gom cụm dữ liệu
‡ Gom cụm
„ Quá trình gom nhóm/cụm dữ liệu/đối tượng vào các
lớp/cụm
„ Các đối tượng trong cùng một cụm tương tự với nhau hơn
so với đối tượng ở các cụm khác.
‡ Obj1, Obj2 ở cụm C1; Obj3 ở cụm C2 Æ Obj1 tương tự Obj2 
hơn so với tương tự Obj3.
Gom cụm
19
19
5.1. Tổng quan về gom cụm dữ liệu
‡ Gom cụm
„ Quá trình gom nhóm/cụm dữ liệu/đối tượng vào các
lớp/cụm
„ Các đối tượng trong cùng một cụm tương tự với nhau hơn
so với đối tượng ở các cụm khác.
‡ Obj1, Obj2 ở cụm C1; Obj3 ở cụm C2 Æ Obj1 tương tự Obj2 
hơn so với tương tự Obj3.
Inter-cluster 
distances are 
maximized.
Intra-cluster 
distances are 
minimized.
20
20
5.1. Tổng quan về gom cụm dữ liệu
‡ Gom cụm
„ Quá trình gom nhóm/cụm dữ liệu/đối tượng vào các
lớp/cụm
„ Các đối tượng trong cùng một cụm tương tự với nhau hơn
so với đối tượng ở các cụm khác.
‡ Obj1, Obj2 ở cụm C1; Obj3 ở cụm C2 Æ Obj1 tương tự Obj2 
hơn so với tương tự Obj3.
Inter-cluster 
distances are 
maximized.
Intra-cluster 
distances are 
minimized.
High intra-
cluster/class 
similarity
Low inter-
cluster/class 
similarity
21
21
5.1. Tổng quan về gom cụm dữ liệu
‡ Vấn đề kiểu dữ liệu/đối tượng được gom cụm
„ Ma trận dữ liệu (data matrix)












npx...nfx...n1x
...............
ipx...ifx...i1x
...............
1px...1fx...11x
-n đối tượng (objects)
-p biến/thuộc tính (variables/attributes)
22
22
5.1. Tổng quan về gom cụm dữ liệu
‡ Vấn đề kiểu dữ liệu/đối tượng được gom cụm
„ Ma trận sai biệt (dissimilarity matrix)










0...)2,()1,(
:::
)2,3()
...ndnd
0dd(3,1
0d(2,1)
0
d(i, j) là khoảng cách giữa đối tượng i và j; thể hiện sự khác biệt giữa
đối tượng i và j; được tính tuỳ thuộc vào kiểu của các biến/thuộc tính.
23
23
5.1. Tổng quan về gom cụm dữ liệu
‡ Vấn đề kiểu dữ liệu/đối tượng được gom cụm
d(i, j) là khoảng cách giữa đối tượng i và j; thể hiện sự khác biệt giữa
đối tượng i và j; được tính tuỳ thuộc vào kiểu của các biến/thuộc tính.
d(i,j) ≥ 0
d(i,i) = 0
d(i,j) = d(j,i)
d(i,j) ≤ d(i,k) + d(k,j)
24
24
5.1. Tổng quan về gom cụm dữ liệu
‡ Vấn đề kiểu dữ liệu/đối tượng được gom cụm
„ Đối tượng vector (vector objects)
‡ Đối tượng i và j được biểu diễn tương ứng bởi vector x và y.
‡ Độ tương tự (similarity) giữa i và j được tính bởi độ đo
cosine:
x = (x1, , xp)
y = (y1, , yp)
s(x, y) = (x1*y1 +  + xp*yp)/((x12 +  + xp2)1/2*(y12+  + yp2)1/2)
25
25
5.1. Tổng quan về gom cụm dữ liệu
‡ Vấn đề kiểu dữ liệu/đối tượng được gom cụm
„ Interval-scaled variables/attributes
„ Binary variables/attributes
„ Categorical variables/attributes
„ Ordinal variables/attributes
„ Ratio-scaled variables/attributes
„ Variables/attributes of mixed types
26
26
5.1. Tổng quan về gom cụm dữ liệu
‡ Interval-scaled variables/attributes
.)...21
1
nffff xx(xn m +++=
|)|...|||(|1 21 fnffffff mxmxmxns −++−+−=
f
fif
if s
mx
 z
−=
Mean absolute deviation
Mean
Z-score measurement
27
27
5.1. Tổng quan về gom cụm dữ liệu
‡ Độ đo khoảng cách Minkowski
‡ Độ đo khoảng cách Manhattan
‡ Độ đo khoảng cách Euclidean
q q
pp
qq
jxixjxixjxixjid )||...|||(|),( 2211 −++−+−=
||...||||),(
2211 pp jxixjxixjxixjid −++−+−=
)||...|||(|),( 22
22
2
11 pp jxixjxixjxixjid −++−+−=
28
28
5.1. Tổng quan về gom cụm dữ liệu
‡ Binary variables/attributes
dcba
cb jid +++ +=),(
pdbcasum
dcdc
baba
sum
++
+
+
0
1
01
cba
cb jid ++ +=),(
Object i
Object j
(= a + b + c + d)
Hệ số so trùng đơn giản (nếu symmetric):
Hệ số so trùng Jaccard (nếu asymmetric):
29
29
5.1. Tổng quan về gom cụm dữ liệu
‡ Binary variables/attributes
„ Ví dụ
‡ gender: symmetric 
‡ Binary attributes còn lại: asymmetric
‡ Y, P Æ 1, N Æ 0
Name Gender Fever Cough Test-1 Test-2 Test-3 Test-4 
Jack M Y N P N N N 
Mary F Y N P N P N 
Jim M Y P N N N N 
75.0
211
21),(
67.0
111
11),(
33.0
102
10),(
=++
+=
=++
+=
=++
+=
maryjimd
jimjackd
maryjackd
30
30
5.1. Tổng quan về gom cụm dữ liệu
‡ Variables/attributes of mixed types
„ Tổng quát
‡ Nếu xif hoặc xjf bị thiếu (missing) thì
‡ f (variable/attribute): binary (nominal)
dij(f) = 0 if xif = xjf , or dij(f) = 1 otherwise
‡ f : interval-scaled (Minkowski, Manhattan, Euclidean)
‡ f : ordinal or ratio-scaled
ƒ tính ranks rif và
ƒ zif trở thành interval-scaled
)(
1
)()(
1),(
f
ij
p
f
f
ij
f
ij
p
f djid δ
δ
=
=
Σ
Σ=
1
1
−
−=
f
if
M
rzif
31
31
5.1. Tổng quan về gom cụm dữ liệu
32
32
5.1. Tổng quan về gom cụm dữ liệu
‡ Quá trình gom cụm dữ liệu
R. Xu, D. Wunsch II. Survey of Clustering Algorithms. IEEE Transactions on Neural Networks, 
16(3), May 2005, pp. 645-678.
33
33
5.1. Tổng quan về gom cụm dữ liệu
‡ Mỗi cụm nên có bao nhiêu phần tử?
‡ Các phân tử nên được gom vào bao nhiêu cụm?
‡ Bao nhiêu cụm nên được tạo ra?
Bao nhiêu cụm?
4 cụm?2 cụm?
6 cụm?
34
34
5.1. Tổng quan về gom cụm dữ liệu
‡ Các yêu cầu tiêu biểu về việc gom cụm dữ
liệu
„ Khả năng co giãn về tập dữ liệu (scalability)
„ Khả năng xử lý nhiều kiểu thuộc tính khác nhau
(different types of attributes)
„ Khả năng khám phá các cụm với hình dạng tùy
ý (clusters with arbitrary shape)
„ Tối thiểu hóa yêu cầu về tri thức miền trong việc
xác định các thông số nhập (domain knowledge 
for input parameters)
„ Khả năng xử lý dữ liệu có nhiễu (noisy data)
35
35
5.1. Tổng quan về gom cụm dữ liệu
‡ Các yêu cầu tiêu biểu về việc gom cụm dữ
liệu
„ Khả năng gom cụm tăng dần và độc lập với thứ
tự của dữ liệu nhập (incremental clustering and 
insensitivity to the order of input records)
„ Khả năng xử lý dữ liệu đa chiều (high 
dimensionality)
„ Khả năng gom cụm dựa trên ràng buộc
(constraint-based clustering)
„ Khả diễn và khả dụng (interpretability and 
usability)
36
36
5.1. Tổng quan về gom cụm dữ liệu
‡ Phân loại các phương pháp gom cụm dữ liệu tiêu biểu
„ Phân hoạch (partitioning): các phân hoạch được tạo ra và
đánh giá theo một tiêu chí nào đó.
„ Phân cấp (hierarchical): phân rã tập dữ liệu/đối tượng có thứ
tự phân cấp theo một tiêu chí nào đó.
„ Dựa trên mật độ (density-based): dựa trên connectivity and 
density functions.
„ Dựa trên lưới (grid-based): dựa trên a multiple-level 
granularity structure.
„ Dựa trên mô hình (model-based): một mô hình giả thuyết
được đưa ra cho mỗi cụm; sau đó hiệu chỉnh các thông số để
mô hình phù hợp với cụm dữ liệu/đối tượng nhất.
„ 
37
37
5.1. Tổng quan về gom cụm dữ liệu
‡ Phân loại các phương pháp gom cụm dữ
liệu tiêu biểu
Original Points Partitioning
38
38
5.1. Tổng quan về gom cụm dữ liệu
‡ Phân loại các phương pháp gom cụm dữ
liệu tiêu biểu
p4
p1
p3 
p2
p4p1 p2 p3
HierarchicalOriginal Points
p4
p1
p3
p2
39
39
5.1. Tổng quan về gom cụm dữ liệu
‡ Các phương pháp đánh giá việc gom cụm dữ liệu
„ Đánh giá ngoại (external validation)
‡ Đánh giá kết quả gom cụm dựa vào cấu trúc được chỉ định trước
cho tập dữ liệu
„ Đánh giá nội (internal validation)
‡ Đánh giá kết quả gom cụm theo số lượng các vector của chính
tập dữ liệu (ma trận gần – proximity matrix)
„ Đánh giá tương đối (relative validation)
‡ Đánh giá kết quả gom cụm bằng việc so sánh các kết quả gom
cụm khác ứng với các bộ trị thông số khác nhau
Æ Tiêu chí cho việc đánh giá và chọn kết quả gom cụm tối ưu
- Độ nén (compactness): các đối tượng trong cụm nên gần nhau.
- Độ phân tách (separation): các cụm nên xa nhau.
40
40
5.1. Tổng quan về gom cụm dữ liệu
‡ Các phương pháp đánh giá việc gom cụm dữ
liệu
„ Đánh giá ngoại (external validation)
‡ Độ đo: Rand statistic, Jaccard coefficient, Folkes and 
Mallows index, 
„ Đánh giá nội (internal validation)
‡ Độ đo: Hubert’s Γ statistic, Silhouette index, Dunn’s 
index, 
„ Đánh giá tương đối (relative validation)
41
41
5.1. Tổng quan về gom cụm dữ liệu
‡ Các phương pháp đánh giá việc gom cụm dữ liệu
„ Các độ đo đánh giá ngoại (external validation measures – contingency matrix)
J. Wu and et al. Adapting the Right Measures for K-means Clustering. KDD’09, Paris, France, July 2009.
42
42
5.2. Gom cụm dữ liệu bằng phân hoạch
‡ Đánh giá kết quả gom cụm
Contingency matrix
-Partition P: kết quả gom cụm trên n đối tượng
-Partition C: các cụm thật sự của n đối tượng
-nij = |Pi∩Cj|: số đối tượng trong Pi từ Cj
43
43
5.2. Gom cụm dữ liệu bằng phân hoạch
Kết quả gom cụm theo phương án I và II
-Partition P: kết quả gom cụm trên n (=66) đối tượng
-Partition C: các cụm thật sự của n (=66) đối tượng
-nij = |Pi∩Cj|: số đối tượng trong Pi từ Cj
‡Đánh giá kết quả gom cụm
44
44
5.2. Gom cụm dữ liệu bằng phân hoạch
‡ Đánh giá kết quả gom cụm
„ Entropy (trị nhỏ khi chất lượng gom cụm tốt)
???
)
24
0log
24
0
24
12log
24
12
24
12log
24
12(
66
24
)
23
12log
23
12
23
3log
23
3
23
8log
23
8(
66
23
)
19
12log
19
12
19
4log
19
4
19
3log
19
3(
66
19
)log(
)log()(
=
++−
++−
++−=
−=
−=
∑ ∑
∑ ∑
i
i
ij
j
i
iji
i
i
ij
j
i
ij
i
n
n
n
n
n
n
p
p
p
p
pIEntropy
???
)
24
0log
24
0
24
12log
24
12
24
12log
24
12(
66
24
)
23
12log
23
12
23
0log
23
0
23
11log
23
11(
66
23
)
19
12log
19
12
19
7log
19
7
19
0log
19
0(
66
19
)log(
)log()(
=
++−
++−
++−=
−=
−=
∑ ∑
∑ ∑
i
i
ij
j
i
iji
i
i
ij
j
i
ij
i
n
n
n
n
n
n
p
p
p
p
pIIEntropy
Æ Gom cụm theo phương án I hay phương án II tốt???
45
45
5.2. Gom cụm dữ liệu bằng phân hoạch
‡ Giải thuật k-means
46
46
5.2. Gom cụm dữ liệu bằng phân hoạch
47
47
5.2. Gom cụm dữ liệu bằng phân hoạch
-2 -1.5 -1 -0.5 0 0.5 1 1.5 2
0
0.5
1
1.5
2
2.5
3
x
y
-2 -1.5 -1 -0.5 0 0.5 1 1.5 2
0
0.5
1
1.5
2
2.5
3
x
y
Sub-optimal Clustering
-2 -1.5 -1 -0.5 0 0.5 1 1.5 2
0
0.5
1
1.5
2
2.5
3
x
y
Optimal Clustering
Original Points
48
48
5.2. Gom cụm dữ liệu bằng phân hoạch
‡ Đặc điểm của giải thuật k-means?
49
49
5.2. Gom cụm dữ liệu bằng phân hoạch
‡ Đặc điểm của giải thuật k-means
„ Bài toán tối ưu hóa
‡ Cực trị cục bộ
„ Mỗi cụm được đặc trưng hóa bởi trung tâm của
cụm (i.e. đối tượng trung bình (mean)).
‡ Không thể xác định được đối tượng trung bình???
‡ Số cụm k nên là bao nhiêu?
„ Độ phức tạp: O(nkt) 
‡ n là số đối tượng, k là số cụm, t là số lần lặp
ƒ k << n, t << n
50
50
5.2. Gom cụm dữ liệu bằng phân hoạch
‡ Đặc điểm của giải thuật k-means
„ Ảnh hưởng bởi nhiễu (các phần tử kì dị/biên)
„ Không phù hợp cho việc khai phá ra các cụm có
dạng không lồi (nonconvex) hay các cụm có kích
thước rất khác nhau
‡ Kết quả gom cụm có dạng siêu cầu (hyperspherial)
‡ Kích thước các cụm kết quả thường đồng đều (relatively 
uniform sizes)
51
51
5.2. Gom cụm dữ liệu bằng phân hoạch
‡ Đặc điểm của giải thuật k-means
„ Đánh giá kết quả gom cụm của giải thuật k-
means với hai trị k1 (phương án I) và k2 
(phương án II) khác nhau trên cùng tập dữ liệu
mẫu cho trước
‡ Entropy (trị nhỏ khi chất lượng gom cụm tốt)
ƒ Entropy (I) = ???
ƒ Entropy (II) = ???
Æ Gom cụm theo phương án I hay phương án II tốt?
52
52
5.2. Gom cụm dữ liệu bằng phân hoạch
‡ Đặc điểm của giải thuật k-means
„ Đánh giá kết quả gom cụm của giải thuật k-means 
với hai trị k1 (phương án I) và k2 (phương án II) 
khác nhau trên cùng tập dữ liệu mẫu cho trước
‡ F-measure (trị lớn khi chất lượng gom cụm tốt)
ƒ F-measure (I) = ???
ƒ F-measure (II) = ???
Æ Gom cụm theo phương án I hay phương án II tốt?
Æ Kết quả đánh giá trùng với kết quả đánh giá dựa trên độ đo
Entropy?
53
53
5.2. Gom cụm dữ liệu bằng phân hoạch
54
54
5.2. Gom cụm dữ liệu bằng phân hoạch
‡ Tính “total cost S of swapping Oj và Orandom” = 
ΣpCp/OiOrandom
55
55
5.2. Gom cụm dữ liệu bằng phân hoạch
‡ Tính “total cost S of swapping Oj và Orandom” = 
ΣpCp/OiOrandom
Cp/OiOrandom = 0 Cp/OiOrandom
= d(p,Orandom) – d(p,Oi)
Cp/OiOrandom
= d(p,Orandom) – d(p,Oj)
Cp/OiOrandom
= d(p,Oi) – d(p,Oj)
56
56
5.2. Gom cụm dữ liệu bằng phân hoạch
‡ Đặc điểm của giải thuật PAM (k-medoids)
„ ???
57
57
5.2. Gom cụm dữ liệu bằng phân hoạch
‡ Đặc điểm của giải thuật PAM (k-medoids)
„ Mỗi cụm được đại diện bởi phần tử chính giữa cụm
(centroid).
‡ Giảm thiểu sự ảnh hưởng của nhiễu  ... mới nào được thêm vào.
76
76
5.4. Gom cụm dữ liệu dựa trên mật độ
MinPts = 4
ε
C1
ε
ε
C1
77
77
5.4. Gom cụm dữ liệu dựa trên mật độ
‡ DBSCAN (Density-Based Spatial Clustering of 
Applications with Noise)
„ Đặc điểm ???
‡ Các cụm có dạng và kích thước khác nhau.
ƒ Không có giả định về phân bố của các đối tượng dữ liệu
ƒ Không yêu cầu về số cụm
ƒ Không phụ thuộc vào cách khởi động (initialization)
‡ Xử lý nhiễu (noise) và các phần tử biên (outliers)
‡ Yêu cầu trị cho thông số nhập
ƒ Yêu cầu định nghĩa của mật độ (density)
ƒ ε và MinPts
‡ Độ phức tạp
ƒ O(nlogn) Æ O(n2)
78
78
5.5. Gom cụm dữ liệu dựa trên mô hình
‡ Tối ưu hóa sự phù hợp giữa dữ liệu và mô hình toán
nào đó
„ Giả định về quá trình tạo dữ liệu
‡ Dữ liệu được tạo ra với nhiều sự phân bố xác suất khác nhau.
‡ Các phương pháp
„ Tiếp cận thống kê
‡ Mở rộng của giải thuật gom cụm dựa trên phân hoạch k-means: 
Expectation-Maximization (EM)
„ Tiếp cận học máy: gom cụm ý niệm (conceptual clustering)
„ Tiếp cận mạng neural: Self-Organizing Feature Map (SOM)
79
79
5.5. Gom cụm dữ liệu dựa trên mô hình
‡ Gom cụm Expectation-Maximization (EM)
„ Giải thuật tinh chỉnh lặp để gán các đối tượng vào các cụm
(bước kỳ vọng) và ước lượng trị thông số (bước cực đại hoá).
‡ Gom cụm ý niệm (conceptual clustering)
„ Tạo ra cách phân lớp các đối tượng chưa được gán nhãn dựa
vào các mô tả đặc trưng cho mỗi nhóm đối tượng ứng với mỗi
khái niệm (concept).
‡ Gom cụm với mạng neural
„ Biểu diễn mỗi cụm là một ví dụ tiêu biểu (exemplar).
„ Exemplar đóng vai trò của một prototype của cụm. 
„ Các đối tượng mới được phân bố vào một cụm nếu tương tự
với exemplar của cụm đó nhất dựa trên độ đo khoảng cách.
80
80
5.5. Gom cụm dữ liệu dựa trên mô hình
81
81
5.5. Gom cụm dữ liệu dựa trên mô hình
‡ Giải thuật Expectation-Maximization (EM)
„ Gán một đối tượng vào một cụm nếu tương tự
trung tâm (mean) của cụm đó nhất
‡ Dựa vào trọng số (weight) của đối tượng đối với mỗi cụm
ƒ Xác suất thành viên (probability of membership)
‡ Không có ranh giới giữa các cụm
‡ Trung tâm của mỗi cụm được tính dựa vào các độ đo có
trọng số (weighted measures).
„ Hội tụ nhanh nhưng có thể tối ưu cục bộ
82
82
5.5. Gom cụm dữ liệu dựa trên mô hình
‡ Giải thuật Expectation-Maximization (EM)
„ Input: tập n đối tượng, K (số cụm)
„ Output: trị tối ưu cho các thông số của mô hình
„ Giải thuật:
‡ 1. Khởi trị
ƒ 1.1. Chọn ngẫu nhiên K đối tượng làm trung tâm của K cụm
ƒ 1.2. Ước lượng trị ban đầu cho các thông số (nếu cần)
‡ 2. Lặp tinh chỉnh các thông số (cụm):
ƒ 2.1. Bước kỳ vọng (expectation step): gán mỗi đối tượng xi
đến cụm Ck với xác suất P(xi ∈ Ck) với k=1..K
ƒ 2.2. Bước cực đại hóa (maximization step): ước lượng trị các
thông số
ƒ 2.3. Dừng khi thỏa điều kiện định trước.
83
83
5.5. Gom cụm dữ liệu dựa trên mô hình
‡ Giải thuật Expectation-Maximization (EM)
„ Giải thuật:
‡ 1. Khởi trị
‡ 2. Lặp tinh chỉnh các thông số (cụm):
ƒ 2.1. Bước kỳ vọng (expectation step): gán mỗi đối tượng xi đến
cụm Ck với xác suất P(xi ∈ Ck)
ƒ 2.2. Bước cực đại hóa (maximization step): ước lượng trị các
thông số
(mk là trung tâm của cụm Ck, j = 1..K, k = 1..K)
84
84
5.6. Các phương pháp gom cụm dữ liệu
khác
‡ Gom cụm cứng (hard clustering)
„ Mỗi đối tượng chỉ thuộc về một
cụm.
„ Mức thành viên (degree of 
membership) của mỗi đối tượng
với một cụm hoặc là 0 hoặc là 1.
„ Ranh giới (boundary) giữa các
cụm rõ ràng.
‡ Gom cụm mờ (fuzzy clustering)
„ Mỗi đối tượng thuộc về nhiều hơn
một cụm với mức thành viên nào
đó từ 0 đến 1.
„ Ranh giới giữa các cụm không rõ
ràng (mờ - vague/fuzzy).
100 150 200 250 300
500
1000
1500
2000
2500
3000
3500
Top speed [km/h]
W
e
i
g
h
t
[
k
g
]
Sports cars
Medium market cars
Lorries
85
85
5.7. Tóm tắt
‡Gom cụm nhóm các đối tượng vào các cụm dựa 
trên sự tương tự giữa các đối tượng.
‡Độ đo đo sự tương tự tùy thuộc vào kiểu dữ
liệu/đối tượng cụ thể.
‡Các giải thuật gom cụm được phân loại thành: 
nhóm phân hoạch, nhóm phân cấp, nhóm dựa 
trên mật độ, nhóm dựa trên lưới, nhóm dựa trên 
mô hình, 
86
86
5.7. Tóm tắt
R. Xu, D. Wunsch II. Survey of Clustering 
Algorithms. IEEE Transactions on Neural 
Networks, 16(3), May 2005, pp. 645-678.
87
87
Hỏi & Đáp 
88
88
Chương 5: Gom cụm dữ liệu
Phần 2
89
89
Nội dung
‡ 5.6. Các phương pháp gom cụm dữ liệu
khác
„ 5.6.1. Fuzzy c-Means Clustering
‡ [9], part 24.4, pp. 514-516
„ 5.6.2. Self-Organizing Map (SOM)
‡ [9], part 21.3.3, pp. 433-436
Æ Tóm tắt phần 2
90
90
Fuzzy c-means clustering
‡ The most popular fuzzy clustering algorithm
„ Better than the hard K-means algorithm at 
avoiding local minima
‡ But still converge to local minima of the squared error 
criterion
„ Problem with the design of membership functions
‡ An iterative algorithm
„ find cluster centers (centroids) that minimize a 
dissimilarity (or distance) (objective) function
2
1 1
∑∑
= =
−
c
i
n
j
ij
m
ij cxu
91
91
Fuzzy c-means clustering
‡ Membership matrix = a real c x n matrix
„ n (columns): the number of clustered objects where n > 1
„ c (rows): the number of resulting clusters where 2 ≤ c < n
„ uij: degree of membership of the jth object xj belonging to 
the ith cluster ci where i ∈ {1, , c} and j ∈ {1, , n}
‡ Hard c-means clustering: uij ∈ {0, 1}
‡ Fuzzy c-means clustering: uij ∈ [0, 1]
„ Probability:
„ Possibility:
},...,1{0};,...,1{1
11
ciunju
n
j
ij
c
i
ij ∈∀>∈∀= ∑∑
==
},...,1{00
11
njcuoru
c
i
ij
c
i
ij ∈∀≤ ∑∑
==
92
92
Fuzzy c-means clustering
‡ Hard c-means clustering: objective function
‡ Fuzzy c-means clustering: objective function
„ ||.||2: squared (Euclidean) distance (dissimilarity)
„ m: weighting exponent where 1 ≤ m < +∞
‡ Control the relative weights placed on each of the distances
‡ Popular chosen value: m=2 || range: 1.5 ≤ m ≤ 3.0 ([1, 30])
‡ m Æ 1 : increasingly hard || m Æ +∞ : fuzziest
2
1
2
1 1
∑∑∑∑
= ∈= =
−=−
c
i Cp
i
c
i
n
j
ij
m
ij
i
cpcxu
2
1 1
∑∑
= =
−
c
i
n
j
ij
m
ij cxu
minimize
minimize
93
93
Fuzzy c-means clustering
‡ Fuzzy c-means clustering: objective function
„ : squared (Euclidean) distance from 
object xj to the center ci of cluster i
„ : squared error incurred by representing 
xj by the center ci weighted by (a power 
of) the membership of xj in cluster i
„ : sum of squared errors due to xj’s partial 
replacement by all centers of c clusters
„ : overall weighted sum of generalized 
errors due to replacing all objects x 
by all centers of c clusters
2
1 1
∑∑
= =
−
c
i
n
j
ij
m
ij cxuminimize
2
ij cx −
2
1 1
∑∑
= =
−
c
i
n
j
ij
m
ij cxu
2
ij
m
ij cxu −
∑
=
−
c
i
ij
m
ij cxu
1
2
(24.16)
94
94
Fuzzy c-means clustering
‡ Each degree of membership uij of object xj belonging to cluster i is 
randomly initialized in [0, 1] with the following constraints:
‡ Each degree of membership uij of object xj belonging to cluster i is 
then updated as follows:
‡ Each center ci of cluster i is updated as follows:
},...,1{0};,...,1{1
11
ciunju
n
j
ij
c
i
ij ∈∀>∈∀= ∑∑
==
∑
∑
=
== n
j
m
ij
j
n
j
m
ij
i
u
xu
c
1
1
∑
=
−




−
−
=
c
k
m
kj
ij
ij
cx
cx
u
1
)1/(2
1
(24.15)
(24.18)
(24.17)
95
95
Fuzzy c-means clustering
Fuzzy c-means algorithm (Bezdek, 1973)
[9], pp. 516
96
96
Fuzzy c-means clustering
‡ Several widely-used termination criteria
„ The number of iterations
„ The difference between the updated value of 
objective function and its previous value is small 
enough.
‡ Objective function
„ The difference between all updated degrees of 
membership uij and their previous values is small 
enough.
‡ Membership matrix
„ The difference between all updated centers ci and 
their previous values is small enough.
‡ Centers 
97
97
Fuzzy c-means clustering
‡ Notes on fuzzy c-means clustering
„ By iteratively updating the cluster centers and the 
membership grades for each data point, FCM iteratively 
moves the cluster centers to the ”right” location within a data 
set.
‡ The nearer the cluster centers, the higher the membership 
grades
‡ Possible with local minima
„ Parameter values determined in advance (experimental)
‡ c: the number of clusters 
‡ m: weighting exponent
„ Dissimilarity/Similarity measures for particular applications
„ Cluster shape
„ Data type
„ Noise
98
98
Fuzzy c-means clustering
‡ Example on fuzzy c-means 
clustering
„ The number of training 
objects: 16
„ The number of clusters: 2
„ Weighting exponent: 2
„ Threshold t: 0.01
Two resulting clusters Data Set
J. C. Bezdek, R. Ehrlich, W. Full, "FCM: the fuzzy c-means clustering algorithm", 
Computers & Geosciences 10 (2-3) (1984) 191-203.
99
99
Self-Organizing Map (SOM)
‡ Unsupervised neural network model
„ Data clustering
‡ Proposed by T. Kohonen in the early 1980s
„ Further reading: Teuvo Kohonen, “The Self-
Organizing Map,” Proceedings of the IEEE, vol. 
78, no. 9, pp. 1464-1480, September 1990.
‡ Specially good at providing visualization of high-
dimensional data in a fewer dimensional space 
(typically 1D, 2D, 3D)
„ Visualize the clusters or similarities between patterns
„ Dimensionality reduction
100
100
Self-Organizing Map (SOM)
101
101
Self-Organizing Map (SOM)
‡ Kohonen (1982) developed a neural network
based on self-organization whose key idea is 
to represent sensory signals as (low) two-
dimensional images or maps.
‡ Kohonen’s networks, often called Kohonen’s 
feature maps or selforganizing maps,
organized neighborhoods of neurons such 
that similar inputs into the model are 
topologically close.
‡ The SOM processes the input patterns and 
learns to cluster or segment the data
through adjustment of weights.
102
102
Self-Organizing Map (SOM)
‡ SOM architecture
„ A typical SOM network has two 
layers of nodes, an input layer and 
output layer (sometimes called the 
Kohonen layer).
„ Each node in the input layer is 
fully connected to nodes in the low 
(one, two, three-) dimensional 
output layer.
„ The number n of nodes in the
input layer is corresponding to the 
number of input variables (i.e. the 
length/dimensionality of an input 
vector x).
„ The number m of output nodes
depends on the specific problem 
and is determined by the user.
‡ This number of neurons in the 
rectangular array should be large 
enough to allow a sufficient 
number of clusters to form.
[9], part 21.3.3, pp. 434.
Input x
Weights w
103
103
Self-Organizing Map (SOM)
‡ SOM architecture
„ A winning neuron k: the 
neuron corresponding to 
weight wk (an nx1 vector) 
that has the minimum 
distance to the input x
randomly selected in a 
training step
„ The neighborhood Nk
around a winning neuron k: 
the collection of all nodes 
with the same radial 
distance
Fig. 21.5. A 5x5 Kohonen Layer 
with two neighborhood sizes at 
radius of 1 and 2
[9], part 21.3.3, pp. 435.
104
104
Self-Organizing Map (SOM)
‡ Self-organizing (competitive, unsupervised) 
learning
„ Neighboring cells in a neural network compete in 
their activities by means of mutual lateral 
interactions, and develop adaptively into specific 
detectors of different signal patterns.
„ The cells become specifically tuned to various 
input signal patterns or classes of patterns 
through the learning process.
„ Only one cell or local group of cells at a time 
gives the active response to the current input.
‡ winner-take-all strategy
105
105
Self-Organizing Map (SOM)
‡ SOM learning procedure
1. initialize the weights w to small random values and the 
neighborhood size large enough to cover half the nodes
2. select an input pattern x randomly from the training set 
and present it to the network
3. find the best matching or “winning” node k whose weight 
vector wk is closest to the current input vector x using the 
vector distance
4. update the weights of nodes in the neighborhood of k
using the Kohonen learning rule
5. decrease the learning rate slightly
6. repeat steps 1-5 with a number of cycles and then 
decrease the size of the neighborhood. Repeat until 
weights are stabilized.
106
106
Self-Organizing Map (SOM)
‡ The vector distance where ||.|| represents the Euclidean 
distance
‡ The Kohonen learning rule
where α is the learning rate between 0 and 1 and hik is a 
neighborhood kernel centered on the winning node and 
can take Gaussian form as
where ri and rk are positions of neurons i and k on the SOM 
grid and σ is the neighborhood radius.
)10(
)(
k
old
i
new
i
kiik
old
i
new
i
Ninnotisiifww
Ninisiifwxhww
=
−+= α
107
107
Self-Organizing Map (SOM)
‡ As the number of cycles of training (epochs)
increases, better formation of the clusters can 
be found.
‡ Eventually, the topological map is fine-tuned 
with finer distinctions of clusters within areas 
of the map.
‡ After the network has been trained, it can be 
used as a visualization tool to examine the 
data structure.
‡ Once clusters are identified, neurons in the 
map can be labeled to indicate their meaning.
„ Assignment of meaning usually requires knowledge 
on the data and specific application area.
108
108
Self-Organizing Map (SOM)
‡ Notes on SOM
„ Dimensionality (1D, 2D, 3D, ?) of the output layer
„ The size of the map (the number of neurons of 
the output layer)
‡ The number of clusters
„ Not restricted to any particular form of 
preprocessing
„ Capable of noise handling
„ Originally proposed for numeric data
‡ Extended versions for categorical data
109
109
Self-Organizing Map (SOM)
‡SOM’s Applications
„market segmentation,
„ customer targeting,
„ business failure categorization,
„ credit evaluation,
„ document retrieval,
„ group technology
„
110
110
Self-Organizing Map (SOM)
Source: Teuvo Kohonen, “The 
Self-Organizing Map,” Proceedings 
of the IEEE, vol. 78, no. 9, pp. 
1464-1480, September 1990.
111
111
Self-Organizing Map (SOM)
112
112
Self-Organizing Map (SOM)
Source: Teuvo Kohonen, “The 
Self-Organizing Map,” Proceedings 
of the IEEE, vol. 78, no. 9, pp. 
1464-1480, September 1990.
113
113
Self-Organizing Map (SOM)
‡ Example on SOM
„ The number of training vectors: 4
„ The length of each training vector/weight: 3
„ The number of clusters (output neurons): 2
„ Neighborhood size: 0
„ Learning rate:
‡ η(t) = 0.6; 1 <= t <= 4
‡ η(t) = 0.5; 5 <= t <= 8
‡ η(t) = 0.5; 9 <= t <= 12, etc.
Where t is iteration
114
114
Self-Organizing Map (SOM)
‡ Training vectors:
„ X1 = (1, 1, 0)
„ X2 = (0, 0, 0)
„ X3 = (1, 0, 0)
„ X4 = (0, 0, 1)
‡ Initial weights:
„ Neuron #1: w1 = (0.2, 0.6, 0.5)
„ Neuron #2: w2 = (0.8, 0.4, 0.7)
02134
0113
022
01
4321
X
X
X
X
XXXX
MatrixityDissimilar
Input units:
Output units: 1 2
Network Architecture
Do X1 and X3 
belong to one 
cluster?
Do X2 and X4 
belong to the 
other?
?
?
115
115
Tóm tắt phần 2
‡ Fuzzy c-means clustering
„ A fuzzy version of k-means clustering
‡Self-Organizing Map (SOM)
„ A neural network-based clustering and 
dimensionality reduction technique
„ Support for visualization
116
116
Hỏi & Đáp