KhoaKhoa KhoaKhoa HọcHọc & & KỹKỹ Thuật Thuật MáyMáy TínhTính
TrTrưườngờng ĐĐạiại HọcHọc BáchBách KhoaKhoa TpTp. . HồHồ ChíChí MinhMinh
ChChươươngng 5: 5: GomGom cụmcụm dữdữ liệuliệu
CaoCao HọcHọc Ngành
Ngành KhoaKhoa HọcHọc MáyMáy TínhTính
GiáoGiáo trình
trình đđiệniện tửtử
BiênBiên soạnsoạn bởibởi: TS.
: TS. VõVõ ThịThị NgọcNgọc ChâuChâu
chauvtn@cse.hcmut.edu.vn)) ((chauvtn@cse.hcmut.edu.vn
1
Học kỳ 1 – 2011-2012
1
Tài liệu tham khảo
(cid:135) [1] Jiawei Han, Micheline Kamber, “Data Mining: Concepts and
Techniques”, Second Edition, Morgan Kaufmann Publishers, 2006. (cid:135) [2] David Hand, Heikki Mannila, Padhraic Smyth, “Principles of Data
(cid:135) [3] David L. Olson, Dursun Delen, “Advanced Data Mining
Mining”, MIT Press, 2001.
(cid:135) [4] Graham J. Williams, Simeon J. Simoff, “Data Mining: Theory,
Techniques”, Springer-Verlag, 2008.
(cid:135) [5] Hillol Kargupta, Jiawei Han, Philip S. Yu, Rajeev Motwani, and Vipin Kumar, “Next Generation of Data Mining”, Taylor & Francis Group, LLC, 2009.
(cid:135) [6] Daniel T. Larose, “Data mining methods and models”, John Wiley
Methodology, Techniques, and Applications”, Springer-Verlag, 2006.
(cid:135) [7] Ian H.Witten, Eibe Frank, “Data mining : practical machine
& Sons, Inc, 2006.
(cid:135) [8] Florent Messeglia, Pascal Poncelet & Maguelonne Teisseire,
learning tools and techniques”, Second Edition, Elsevier Inc, 2005.
(cid:135) [9] Oded Maimon, Lior Rokach, “Data Mining and Knowledge
2
“Successes and new directions in data mining”, IGI Global, 2008.
2
Discovery Handbook”, Second Edition, Springer Science + Business Media, LLC 2005, 2010.
Nội dung
(cid:135) Chương 1: Tổng quan về khai phá dữ liệu
(cid:135) Chương 2: Các vấn đề tiền xử lý dữ liệu
(cid:135) Chương 3: Hồi qui dữ liệu (cid:135) Chương 4: Phân loại dữ liệu
(cid:135) Chương 5: Gom cụm dữ liệu
(cid:135) Chương 6: Luật kết hợp
(cid:135) Chương 7: Khai phá dữ liệu và công nghệ cơ sở
dữ liệu
(cid:135) Chương 8: Ứng dụng khai phá dữ liệu
(cid:135) Chương 9: Các đề tài nghiên cứu trong khai phá
dữ liệu
3
3
(cid:135) Chương 10: Ôn tập
Chương 5: Gom cụm dữ liệu
(cid:135) 5.1. Tổng quan về gom cụm dữ liệu
(cid:135) 5.2. Gom cụm dữ liệu bằng phân hoạch
(cid:135) 5.3. Gom cụm dữ liệu bằng phân cấp
(cid:135) 5.4. Gom cụm dữ liệu dựa trên mật độ
(cid:135) 5.5. Gom cụm dữ liệu dựa trên mô hình
(cid:135) 5.6. Các phương pháp gom cụm dữ liệu khác
(cid:135) 5.7. Tóm tắt
4
4
ChChươươngng 5: 5: GomGom cụmcụm dữdữ liệuliệu
Phần 1
5
5
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?
6
6
5.0. Tình huống 2 - Làm sạch dữ liệu
(cid:135) Nhận diện phần tử biên (outliers) và giảm
thiểu nhiễu (noisy data)
(cid:135) Phân tích cụm (cluster analysis)
7
7
(cid:132) Giải pháp giảm thiểu nhiễu
5.0. Tình huống 3
8
8
5.0. Tình huống 3
9
9
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 4
http://kdd.ics.uci.edu/databases/CorelFeatures/CorelFeatures.data.html
Gom cụm ảnh
15
15
5.0. Tình huống …
16
16
Gom cụm
5.0. Tình huống …
preprocessing)
(cid:135) Hỗ trợ giai đoạn tiền xử lý dữ liệu (data
distribution)
(cid:135) Mô tả sự phân bố dữ liệu/đối tượng (data
(cid:135) Nhận dạng mẫu (pattern recognition)
(cid:135) Phân tích dữ liệu không gian (spatial data analysis)
(cid:135) Xử lý ảnh (image processing)
(cid:135) Phân mảnh thị trường (market segmentation)
(cid:135) Gom cụm tài liệu ((WWW) document clustering)
17
17
(cid:135) …
5.1. Tổng quan về gom cụm dữ liệu
(cid:132) Quá trình gom nhóm/cụm dữ liệu/đối tượng vào các
lớp/cụm
(cid:132) 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.
(cid:135) Obj1, Obj2 ở cụm C1; Obj3 ở cụm C2 (cid:198)Obj1 tương tự Obj2
(cid:135) Gom cụm
hơn so với tương tự Obj3.
18
18
Gom cụm
5.1. Tổng quan về gom cụm dữ liệu
(cid:132) Quá trình gom nhóm/cụm dữ liệu/đối tượng vào các
lớp/cụm
(cid:132) 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.
(cid:135) Obj1, Obj2 ở cụm C1; Obj3 ở cụm C2 (cid:198)Obj1 tương tự Obj2
(cid:135) Gom cụm
Intra-cluster distances are minimized.
Inter-cluster distances are maximized.
19
19
hơn so với tương tự Obj3.
5.1. Tổng quan về gom cụm dữ liệu
(cid:132) Quá trình gom nhóm/cụm dữ liệu/đối tượng vào các
lớp/cụm
(cid:132) 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.
(cid:135) Obj1, Obj2 ở cụm C1; Obj3 ở cụm C2 (cid:198)Obj1 tương tự Obj2
(cid:135) Gom cụm
hơn so với tương tự Obj3.
Intra-cluster distances are minimized.
Inter-cluster distances are maximized.
Low inter-- Low inter cluster/class cluster/class similarity similarity
20
20
High intra-- High intra cluster/class cluster/class similarity similarity
5.1. Tổng quan về gom cụm dữ liệu
(cid:135) Vấn đề kiểu dữ liệu/đối tượng được gom cụm
(cid:132) Ma trận dữ liệu (data matrix)
...
...
... ...
... ...
...
...
...
...
11x ... i1x ... n1x
1fx ... ifx ... nfx
1px ... ipx ... npx
-n đối tượng (objects)
21
21
-p biến/thuộc tính (variables/attributes)
5.1. Tổng quan về gom cụm dữ liệu
(cid:135) Vấn đề kiểu dữ liệu/đối tượng được gom cụm
(cid:132) Ma trận sai biệt (dissimilarity matrix)
0 d(2,1) d(3,1 )
0 )2,3(
d
0
: nd )1,(
: nd )2,(
: ...
...
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
22
22
đố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.
5.1. Tổng quan về gom cụm dữ liệu
(cid:135) 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)
23
23
d(i,j) ≤ d(i,k) + d(k,j)
5.1. Tổng quan về gom cụm dữ liệu
(cid:135) Vấn đề kiểu dữ liệu/đối tượng được gom cụm
(cid:135) Đối tượng i và j được biểu diễn tương ứng bởi vector x và y.
(cid:135) Độ tương tự (similarity) giữa i và j được tính bởi độ đo
cosine:
(cid:132) Đối tượng vector (vector objects)
x = (x1, …, xp)
y = (y1, …, yp)
24
24
s(x, y) = (x1*y1 + … + xp*yp)/((x12 + … + xp2)1/2*(y12+ … + yp2)1/2)
5.1. Tổng quan về gom cụm dữ liệu
(cid:135) Vấn đề kiểu dữ liệu/đối tượng được gom cụm
(cid:132) Interval-scaled variables/attributes
(cid:132) Binary variables/attributes
(cid:132) Categorical variables/attributes
(cid:132) Ordinal variables/attributes
(cid:132) Ratio-scaled variables/attributes
25
25
(cid:132) Variables/attributes of mixed types
5.1. Tổng quan về gom cụm dữ liệu
(cid:135) Interval-scaled variables/attributes
Mean absolute deviation
s
|
|
m
|
|
|)
=
−
+
−
... ++
f
1
f
f
x 2
f
f
mx − nf
f
(|1 mxn
1
.)
... ++
+
Mean
1
x 2
f
f
f
x nf
(xn m =
f
Z-score measurement
=
z if
mx − if s
f
26
26
5.1. Tổng quan về gom cụm dữ liệu
q
q
q
),( jid
(|
x
|
|
x
|
|
x
q )|
=
−
+
−
... ++
−
2
2
p
p
x i 1
j 1
x i
j
x i
j
(cid:135) Độ đo khoảng cách Minkowski
|
|
|
|
|
jid
x
x
x
|),( =
−
+
−
... ++
−
2
2
p
p
x i 1
j 1
x i
j
x i
j
(cid:135) Độ đo khoảng cách Manhattan
2
2
(|
|
|
|
|
2 )|
),( jid
x
x
x
=
−
+
−
... ++
−
2
2
p
p
x i 1
j 1
x i
j
x i
j
27
27
(cid:135) Độ đo khoảng cách Euclidean
5.1. Tổng quan về gom cụm dữ liệu
(cid:135) Binary variables/attributes
1
Object j 0 b
1 a
0
d
c
Object i
sum ba + dc + p
sum
dbca
+
+
(= a + b + c + d)
j
id ,(
=)
b b
c c
a
d
+ +++
Hệ số so trùng đơn giản (nếu symmetric):
j
id ,(
=)
c
a
b c + b ++
28
28
Hệ số so trùng Jaccard (nếu asymmetric):
5.1. Tổng quan về gom cụm dữ liệu
(cid:132) Ví dụ
N P N
Y Y Y
N N N
N N P
N N N
Name Gender Fever Cough Test-1 Test-2 Test-3 Test-4 P Jack M P Mary F N Jim M
(cid:135) gender: symmetric (cid:135) Binary attributes còn lại: asymmetric (cid:135) Y, P (cid:198) 1, N (cid:198) 0
(cid:135) Binary variables/attributes
d
jack
mary
(
,
)
33.0
=
=
1
1 +
d
jack
jim
(
,
)
67.0
=
=
1
1
d
jim
mary
75.0
(
,
)
=
=
0 + + 1 + 1
2
1
+ 0 1 + 2 +
2 1 + 1 +
29
29
5.1. Tổng quan về gom cụm dữ liệu
(cid:135) Variables/attributes of mixed types
f
)
f
)
Σ
),( jid
=
( ij )
p ( d δ f 1 ij = p ( f Σ δ f 1 ij
=
(cid:135) Nếu xif hoặc xjf bị thiếu (missing) thì (cid:135) f (variable/attribute): binary (nominal)
(f) = 1 otherwise
dij
(f) = 0 if xif = xjf , or dij
(cid:135) f : interval-scaled (Minkowski, Manhattan, Euclidean)
1
−
if
=
zif
1
−
(cid:135) f : ordinal or ratio-scaled r M
f
30
(cid:131) tính ranks rif và (cid:131) zif trở thành interval-scaled
30
(cid:132) Tổng quát
5.1. Tổng quan về gom cụm dữ liệu
31
31
5.1. Tổng quan về gom cụm dữ liệu
(cid:135) 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.
32
32
5.1. Tổng quan về gom cụm dữ liệu
(cid:135) Mỗi cụm nên có bao nhiêu phần tử?
(cid:135) Các phân tử nên được gom vào bao nhiêu cụm?
(cid:135) Bao nhiêu cụm nên được tạo ra?
33
Bao nhiêu cụm? 6 cụm?
33
2 cụm? 4 cụm?
5.1. Tổng quan về gom cụm dữ liệu
(cid:135) Các yêu cầu tiêu biểu về việc gom cụm dữ
liệu
(cid:132) Khả năng co giãn về tập dữ liệu (scalability)
(different types of attributes)
(cid:132) Khả năng xử lý nhiều kiểu thuộc tính khác nhau
ý (clusters with arbitrary shape)
(cid:132) Khả năng khám phá các cụm với hình dạng tùy
(cid:132) 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)
34
34
(cid:132) Khả năng xử lý dữ liệu có nhiễu (noisy data)
5.1. Tổng quan về gom cụm dữ liệu
(cid:135) Các yêu cầu tiêu biểu về việc gom cụm dữ
liệu
(cid:132) 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)
dimensionality)
(cid:132) Khả năng xử lý dữ liệu đa chiều (high
(constraint-based clustering)
(cid:132) Khả năng gom cụm dựa trên ràng buộc
usability)
35
35
(cid:132) Khả diễn và khả dụng (interpretability and
5.1. Tổng quan về gom cụm dữ liệu
(cid:132) 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 đó.
(cid:132) 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 đó.
(cid:132) Dựa trên mật độ (density-based): dựa trên connectivity and
density functions.
(cid:132) Dựa trên lưới (grid-based): dựa trên a multiple-level
granularity structure.
(cid:132) 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.
(cid:132) …
36
36
(cid:135) Phân loại các phương pháp gom cụm dữ liệu tiêu biểu
5.1. Tổng quan về gom cụm dữ liệu
(cid:135) Phân loại các phương pháp gom cụm dữ
liệu tiêu biểu
37
37
Original Points Partitioning
5.1. Tổng quan về gom cụm dữ liệu
(cid:135) Phân loại các phương pháp gom cụm dữ
liệu tiêu biểu
p1
p1
p3
p4
p3
p4
p2
p2
p1 p2
p3
p4
38
38
Hierarchical Original Points
5.1. Tổng quan về gom cụm dữ liệu
(cid:132) Đánh giá ngoại (external validation)
(cid:135) Đánh giá kết quả gom cụm dựa vào cấu trúc được chỉ định trước
(cid:135) Các phương pháp đánh giá việc gom cụm dữ liệu
(cid:132) Đánh giá nội (internal validation)
(cid:135) Đánh giá kết quả gom cụm theo số lượng các vector của chính
cho tập dữ liệu
(cid:132) Đánh giá tương đối (relative validation)
(cid:135) Đánh giá kết quả gom cụm bằng việc so sánh các kết quả gom
tập dữ liệu (ma trận gần – proximity matrix)
(cid:198) 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.
39
39
cụm khác ứng với các bộ trị thông số khác nhau
5.1. Tổng quan về gom cụm dữ liệu
(cid:135) Các phương pháp đánh giá việc gom cụm dữ
liệu
(cid:135) Độ đo: Rand statistic, Jaccard coefficient, Folkes and
Mallows index, …
(cid:132) Đánh giá ngoại (external validation)
(cid:135) Độ đo: Hubert’s Γ statistic, Silhouette index, Dunn’s
index, …
(cid:132) Đánh giá nội (internal validation)
40
40
(cid:132) Đánh giá tương đối (relative validation)
5.1. Tổng quan về gom cụm dữ liệu
(cid:132) Các độ đo đánh giá ngoại (external validation measures – contingency matrix)
41
J. Wu and et al. Adapting the Right Measures for K-means Clustering. KDD’09, Paris, France, July 2009.
41
(cid:135) Các phương pháp đánh giá việc gom cụm dữ liệu
5.2. Gom cụm dữ liệu bằng phân hoạch
(cid:135) Đánh giá kết quả gom cụm
Contingency matrix
-Partition P: kết quả gom cụm trên n đối tượng
42
42
-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
5.2. Gom cụm dữ liệu bằng phân hoạch
(cid:135) Đánh giá kết quả gom cụm
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
43
43
-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
5.2. Gom cụm dữ liệu bằng phân hoạch
(cid:132) Entropy (trị nhỏ khi chất lượng gom cụm tốt)
log
)
Entropy
)( I
−=
i
j
∑ ∑ ( p i
(
)
log
)
Entropy
II
−=
i
j
∑ ∑ ( p i
p ij p i
p ij p i
p ij p i
p ij p i
)
log
−=
i
j
)
log
−=
i
j
n ∑ ∑ i ( n
n ij n i
n ∑ ∑ i ( n
n ij n i
(
log
log
log
)
+
−=
+
(
log
log
log
)
−=
+
+
19 66
19 66
0 19
n ij n i 0 19
(
log
log
log
)
−
+
+
(
log
log
log
)
+
−
+
(
log
log
log
)
−
+
+
(
log
log
log
)
+
−
+
3 19 8 23 12 24
n ij n i 3 19 8 23 12 24
4 19 3 23 12 24
4 19 3 23 12 24
12 19 12 23 0 24
12 19 12 23 0 24
11 23 12 24
11 23 12 24
7 19 0 23 12 24
7 19 0 23 12 24
12 19 12 23 0 24
12 19 12 23 0 24
23 66 24 66 ???
=
23 66 24 66 ???
=
(cid:135) Đánh giá kết quả gom cụm
44
44
(cid:198) Gom cụm theo phương án I hay phương án II tốt???
5.2. Gom cụm dữ liệu bằng phân hoạch
45
45
(cid:135) Giải thuật k-means
5.2. Gom cụm dữ liệu bằng phân hoạch
46
46
5.2. Gom cụm dữ liệu bằng phân hoạch
3
2.5
2
1.5
y
1
0.5
0
-2
-1.5
-1
-0.5
0.5
1
1.5
2
0 x
3
3
2.5
2.5
2
2
1.5
1.5
y
y
1
1
0.5
0.5
0
0
-2
-1.5
-1
-0.5
0.5
1
1.5
2
-2
-1.5
-1
-0.5
0.5
1
1.5
2
0 x
0 x
Original Points
47
47
Optimal Clustering Sub-optimal Clustering
5.2. Gom cụm dữ liệu bằng phân hoạch
(cid:135) Đặc điểm của giải thuật k-means?
48
48
5.2. Gom cụm dữ liệu bằng phân hoạch
(cid:135) Đặc điểm của giải thuật k-means
(cid:135) Cực trị cục bộ
(cid:132) Bài toán tối ưu hóa
cụm (i.e. đối tượng trung bình (mean)).
(cid:135) Không thể xác định được đối tượng trung bình???
(cid:135) Số cụm k nên là bao nhiêu?
(cid:132) Mỗi cụm được đặc trưng hóa bởi trung tâm của
(cid:135) n là số đối tượng, k là số cụm, t là số lần lặp
(cid:132) Độ phức tạp: O(nkt)
49
49
(cid:131) k << n, t << n
5.2. Gom cụm dữ liệu bằng phân hoạch
(cid:135) Đặc điểm của giải thuật k-means
(cid:132) Ảnh hưởng bởi nhiễu (các phần tử kì dị/biên)
dạng không lồi (nonconvex) hay các cụm có kích thước rất khác nhau
(cid:135) Kết quả gom cụm có dạng siêu cầu (hyperspherial)
(cid:135) Kích thước các cụm kết quả thường đồng đều (relatively
uniform sizes)
50
50
(cid:132) Không phù hợp cho việc khai phá ra các cụm có
5.2. Gom cụm dữ liệu bằng phân hoạch
(cid:135) Đặc điểm của giải thuật k-means
(cid:135) Entropy (trị nhỏ khi chất lượng gom cụm tốt)
(cid:132) Đá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
(cid:131) Entropy (I) = ???
(cid:131) Entropy (II) = ???
51
51
(cid:198) Gom cụm theo phương án I hay phương án II tốt?
5.2. Gom cụm dữ liệu bằng phân hoạch
(cid:135) Đặc điểm của giải thuật k-means
(cid:135) F-measure (trị lớn khi chất lượng gom cụm tốt)
(cid:132) Đá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
(cid:131) F-measure (I) = ???
(cid:131) F-measure (II) = ???
(cid:198) Gom cụm theo phương án I hay phương án II tốt?
(cid:198) Kết quả đánh giá trùng với kết quả đánh giá dựa trên độ đo
52
52
Entropy?
5.2. Gom cụm dữ liệu bằng phân hoạch
53
53
5.2. Gom cụm dữ liệu bằng phân hoạch
ΣpCp/OiOrandom
54
54
(cid:135) Tính “total cost S of swapping Oj và Orandom” =
5.2. Gom cụm dữ liệu bằng phân hoạch
ΣpCp/OiOrandom
= 0
Cp/OiOrandom
Cp/OiOrandom = d(p,Orandom) – d(p,Oi)
Cp/OiOrandom = d(p,Orandom) – d(p,Oj)
Cp/OiOrandom = d(p,Oi) – d(p,Oj)
55
55
(cid:135) Tính “total cost S of swapping Oj và Orandom” =
5.2. Gom cụm dữ liệu bằng phân hoạch
(cid:135) Đặc điểm của giải thuật PAM (k-medoids)
56
56
(cid:132) ???
5.2. Gom cụm dữ liệu bằng phân hoạch
(cid:135) Đặc điểm của giải thuật PAM (k-medoids)
(centroid).
(cid:135) Giảm thiểu sự ảnh hưởng của nhiễu (phần tử biên/kì
dị/cực trị).
(cid:135) Số cụm k cần được xác định trước.
(cid:132) Mỗi cụm được đại diện bởi phần tử chính giữa cụm
(cid:135) Giải thuật bị ảnh hưởng bởi kích thước tập dữ liệu.
57
57
(cid:132) Độ phức tạp cho mỗi vòng lặp O(k(n-k)2)
5.3. Gom cụm dữ liệu bằng phân cấp
(cid:135) Gom cụm dữ liệu bằng phân cấp
(hierarchical clustering): nhóm các đối tượng vào cây phân cấp của các cụm
(cid:132) Agglomerative: bottom-up (trộn các cụm)
(cid:198) Không yêu cầu thông số nhập k (số cụm)
(cid:198) Yêu cầu điều kiện dừng
(cid:198) Không thể quay lui ở mỗi bước trộn/phân
tách
58
58
(cid:132) Divisive: top-down (phân tách các cụm)
5.3. Gom cụm dữ liệu bằng phân cấp
(cid:135) An agglomerative hierarchical clustering method: AGNES
(Agglomerative NESting) (cid:198) bottom-up
(cid:135) A divisive hierarchical clustering method: DIANA (Divisive
ANAlysis) (cid:198) top-down
59
59
5.3. Gom cụm dữ liệu bằng phân cấp
(cid:135) An agglomerative hierarchical clustering method: AGNES
(Agglomerative NESting)
(cid:132) Khởi đầu, mỗi đối tượng tạo thành một cụm.
(cid:132) Các cụm sau đó được trộn lại theo một tiêu chí nào đó.
(cid:135) Cách tiếp cận single-linkage: cụm C1 và C2 được trộn lại nếu
(cid:132) Quá trình trộn các cụm được lặp lại đến khi tất cả các đối
tượng tạo thành một cụm duy nhất.
(cid:135) A divisive hierarchical clustering method: DIANA (Divisive
ANAlysis)
(cid:132) Khởi đầu, tất cả các đối tượng tạo thành một cụm duy nhất.
(cid:132) Một cụm được phân tách theo một tiêu chí nào đó đến khi
mỗi cụm chỉ có một đối tượng.
(cid:135) Khoảng cách lớn nhất giữa các đối tượng cận nhau nhất.
60
60
khoảng cách giữa 2 đối tượng từ C1 và C2 là ngắn nhất.
5.3. Gom cụm dữ liệu bằng phân cấp
4
4
3
3
2
2
1
1
1
2
3
4
1
2
3
4
Single-linkage Complete-linkage
61
61
Tiêu chí trộn các cụm: single-linkage và complete-linkage
5.3. Gom cụm dữ liệu bằng phân cấp
bởi cấu trúc cây (dendrogram).
62
62
(cid:135) Quá trình gom cụm bằng phân cấp được biểu diễn
5.3. Gom cụm dữ liệu bằng phân cấp
bởi cấu trúc cây (dendrogram).
3 cụm có độ tương tự kết hợp nhỏ nhất 0.5
(cid:135) Quá trình gom cụm bằng phân cấp được biểu diễn
63
63
0.5
5.3. Gom cụm dữ liệu bằng phân cấp
p, p’: các đối tượng
|p-p’|: khoảng cách giữa p và p’
64
mi, mj: đối tượng trung bình của Ci, Cj, tương ứng ni, nj: số lượng đối tượng của Ci, Cj, tương ứng
64
(cid:135) Các độ đo dùng đo khoảng cách giữa các cụm Ci và Cj
5.3. Gom cụm dữ liệu bằng phân cấp
(cid:135) Một số giải thuật gom cụm dữ liệu bằng
phân cấp
Clustering using Hierarchies): phân hoạch các đối tượng dùng cấu trúc cây theo độ co giãn của phân giải (scale of resolution)
(cid:132) BIRCH (Balanced Iterative Reducing and
dành cho các thuộc tính rời rạc (categorical/discrete attributes), trộn các cụm dựa vào sự kết nối lẫn nhau giữa các cụm
(cid:132) ROCK (Robust Clustering using linKs): gom cụm
tự giữa các cặp cụm
65
65
(cid:132) Chameleon: mô hình động để xác định sự tương
5.3. Gom cụm dữ liệu bằng phân cấp
(cid:135) Một số vấn đề với gom cụm dữ liệu bằng
phân cấp
(cid:132) Chọn điểm trộn/phân tách phù hợp
(cid:135) Mỗi quyết định trộn/phân tách yêu cầu kiểm tra/đánh
giá nhiều đối tượng/cụm.
(cid:198) Tích hợp gom cụm dữ liệu bằng phân cấp với
các kỹ thuật gom cụm khác
(cid:198) Gom cụm nhiều giai đoạn (multiple-phase clustering)
66
66
(cid:132) Khả năng co giãn (scalability)
5.4. Gom cụm dữ liệu dựa trên mật độ
(cid:135) Gom cụm dữ liệu dựa trên mật độ
gồm các đối tượng.
(cid:135) Các đối tượng trong vùng thưa hơn được xem là nhiễu.
(cid:132) Mỗi cụm là một vùng dày đặc (dense region)
(cid:135) Giải thuật
(cid:132) Mỗi cụm có dạng tùy ý.
Applications with Noise)
(cid:132) DBSCAN (Density-Based Spatial Clustering of
Clustering Structure)
(cid:132) OPTICS (Ordering Points To Identify the
67
67
(cid:132) DENCLUE (DENsity-based CLUstEring)
5.4. Gom cụm dữ liệu dựa trên mật độ
(cid:135) DBSCAN (Density-Based Spatial Clustering
of Applications with Noise)
(cid:135) OPTICS (Ordering Points To Identify the
Clustering Structure)
(cid:132) Phân tích các điểm kết nối nhau dựa vào mật độ
gom cụm dựa vào mật độ của tập dữ liệu
(cid:135) DENCLUE (DENsity-based CLUstEring)
(cid:132) Tạo ra thứ tự các điểm dữ liệu tùy vào cấu trúc
68
68
(cid:132) Gom cụm dựa vào các hàm phân bố mật độ
5.4. Gom cụm dữ liệu dựa trên mật độ
(cid:135) Các khái niệm dùng trong gom cụm dữ liệu
dựa trên mật độ
tượng, gọi là ε-neighborhood.
(cid:132) ε: bán kính của vùng láng giềng của một đối
trong ε-neighborhood của một đối tượng.
(cid:135) Nếu đối tượng có ε-neighborhood với MinPts thì đối tượng này được gọi là đối tượng lõi (core object).
(cid:132) MinPts: số lượng đối tượng ít nhất được yêu cầu
εε
εε
p: core object (MinPts = 3) q: không là core object
p
q
69
69
5.4. Gom cụm dữ liệu dựa trên mật độ
(cid:135) Các khái niệm dùng trong gom cụm dữ liệu
dựa trên mật độ
(cid:132) Directly density-reachable (khả năng đạt được trực tiếp): q có thể đạt được trực tiếp từ p nếu q trong vùng láng giềng ε-neighborhood của p và p phải là core object.
εε
εε
p: directly density-reachable đối với q? q: directly density-reachable đối với p?
p
q
p: directly density-reachable đối với q? X q: directly density-reachable đối với p? √
70
70
5.4. Gom cụm dữ liệu dựa trên mật độ
(cid:135) Các khái niệm dùng trong gom cụm dữ liệu
dựa trên mật độ
(cid:135) Cho trước tập đối tượng D, ε và MinPts
(cid:132) Density-reachable (khả năng đạt được):
(cid:135) q density-reachable từ p nếu ∃ chuỗi các đối tượng p1, ..., pn ∈ D với p1 = p và pn = q sao cho pi+1 directly density-reachable từ pi theo các thông số ε và MinPts, 1 ≤ i ≤ n.
(cid:135) Bao đóng truyền (transitive closure) của directly density-
reachable
(cid:135) Quan hệ bất đối xứng (asymmetric relation)
q
p2
p
MinPts = 5
71
71
5.4. Gom cụm dữ liệu dựa trên mật độ
(cid:135) Các khái niệm dùng trong gom cụm dữ liệu
dựa trên mật độ
(cid:135) Cho trước tập các đối tượng D, ε và MinPts
(cid:135) p, q ∈ D
(cid:132) Density-connected (nối kết dựa trên mật độ):
(cid:135) q density-connected với p nếu ∃ o ∈ D sao cho cả q và p đều density-reachable từ o theo các thông số ε và MinPts.
(cid:135) Quan hệ đối xứng
p
p
q
o
q
o
72
72
5.4. Gom cụm dữ liệu dựa trên mật độ
(cid:135) Các khái niệm dùng trong gom cụm dữ liệu
dựa trên mật độ
MinPts = 3
73
73
5.4. Gom cụm dữ liệu dựa trên mật độ
Border Outlier
gom cụm dữ liệu dựa trên mật độ
(cid:132) Cụm dựa trên mật độ (density
based cluster): tập tất cả các đối tượng được nối kết với nhau dựa trên mật độ.
(cid:135) Đối tượng thuộc về cụm có thể là
(cid:135) Các khái niệm dùng trong
core object.
(cid:131) Nếu đối tượng đó không là core object thì gọi là đối tượng ranh giới (border object).
ε= 1cm
(cid:135) Đối tượng không thuộc về cụm
Core
MinPts = 5
74
74
nào được xem là nhiễu (noise/outlier).
5.4. Gom cụm dữ liệu dựa trên mật độ
(cid:135) DBSCAN (Density-Based Spatial Clustering of
Applications with Noise)
(cid:132) Input: tập đối tượng D, ε, MinPts
(cid:132) Output: density-based clusters (và noise/outliers)
(cid:135) 1. Xác định ε–neighborhood của mỗi đối tượng p ∈ D.
(cid:135) 2. If p là core object, tạo được một cluster.
(cid:135) 3. Từ bất kì core object p, tìm tất cả các đối tượng
(cid:132) Giải thuật
density-reachable và đưa các đối tượng này (hoặc các cluster) vào cùng cluster ứng với p.
(cid:131) 3.1. Các cluster đạt được (density-reachable cluster) có thể
được trộn lại với nhau.
75
75
(cid:131) 3.2. Dừng khi không có đối tượng mới nào được thêm vào.
5.4. Gom cụm dữ liệu dựa trên mật độ
ε
ε
ε
C1
76
C1
MinPts = 4
76
5.4. Gom cụm dữ liệu dựa trên mật độ
Applications with Noise)
(cid:132) Đặc điểm ???
(cid:135) Các cụm có dạng và kích thước khác nhau.
(cid:131) Không có giả định về phân bố của các đối tượng dữ liệu
(cid:131) Không yêu cầu về số cụm
(cid:131) Không phụ thuộc vào cách khởi động (initialization)
(cid:135) Xử lý nhiễu (noise) và các phần tử biên (outliers)
(cid:135) Yêu cầu trị cho thông số nhập
(cid:131) Yêu cầu định nghĩa của mật độ (density)
(cid:131) ε và MinPts
(cid:135) Độ phức tạp
(cid:131) O(nlogn) (cid:198) O(n2)
77
77
(cid:135) DBSCAN (Density-Based Spatial Clustering of
5.5. Gom cụm dữ liệu dựa trên mô hình
nào đó
(cid:132) Giả định về quá trình tạo dữ liệu
(cid:135) Dữ liệu được tạo ra với nhiều sự phân bố xác suất khác nhau.
(cid:135) Tối ưu hóa sự phù hợp giữa dữ liệu và mô hình toán
(cid:132) Tiếp cận thống kê
(cid:135) Mở rộng của giải thuật gom cụm dựa trên phân hoạch k-means:
(cid:135) Các phương pháp
(cid:132) Tiếp cận học máy: gom cụm ý niệm (conceptual clustering)
(cid:132) Tiếp cận mạng neural: Self-Organizing Feature Map (SOM)
78
78
Expectation-Maximization (EM)
5.5. Gom cụm dữ liệu dựa trên mô hình
(cid:132) 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á).
(cid:135) Gom cụm Expectation-Maximization (EM)
(cid:132) 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).
(cid:135) Gom cụm ý niệm (conceptual clustering)
(cid:132) Biểu diễn mỗi cụm là một ví dụ tiêu biểu (exemplar).
(cid:132) Exemplar đóng vai trò của một prototype của cụm.
(cid:132) 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.
79
79
(cid:135) Gom cụm với mạng neural
5.5. Gom cụm dữ liệu dựa trên mô hình
80
80
5.5. Gom cụm dữ liệu dựa trên mô hình
(cid:135) Giải thuật Expectation-Maximization (EM)
trung tâm (mean) của cụm đó nhất
(cid:135) Dựa vào trọng số (weight) của đối tượng đối với mỗi cụm
(cid:132) Gán một đối tượng vào một cụm nếu tương tự
(cid:135) Không có ranh giới giữa các cụm
(cid:135) 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).
(cid:131) Xác suất thành viên (probability of membership)
81
81
(cid:132) Hội tụ nhanh nhưng có thể tối ưu cục bộ
5.5. Gom cụm dữ liệu dựa trên mô hình
(cid:135) Giải thuật Expectation-Maximization (EM)
(cid:132) Input: tập n đối tượng, K (số cụm)
(cid:132) Output: trị tối ưu cho các thông số của mô hình
(cid:135) 1. Khởi trị
(cid:132) Giải thuật:
(cid:131) 1.1. Chọn ngẫu nhiên K đối tượng làm trung tâm của K cụm
(cid:135) 2. Lặp tinh chỉnh các thông số (cụm):
(cid:131) 1.2. Ước lượng trị ban đầu cho các thông số (nếu cần)
(cid:131) 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
(cid:131) 2.2. Bước cực đại hóa (maximization step): ước lượng trị các
82
thông số
82
(cid:131) 2.3. Dừng khi thỏa điều kiện định trước.
5.5. Gom cụm dữ liệu dựa trên mô hình
(cid:132) Giải thuật:
(cid:135) 1. Khởi trị
(cid:135) 2. Lặp tinh chỉnh các thông số (cụm):
(cid:131) 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)
(cid:131) 2.2. Bước cực đại hóa (maximization step): ước lượng trị các
thông số
83
(mk là trung tâm của cụm Ck, j = 1..K, k = 1..K)
83
(cid:135) Giải thuật Expectation-Maximization (EM)
5.6. Các phương pháp gom cụm dữ liệu khác
3500
(cid:135) Gom cụm cứng (hard clustering)
Lorries
3000
2500
(cid:132) Mỗi đối tượng chỉ thuộc về một
Sports cars
i
2000
] g k [ t h g e W
1500
Medium market cars
(cid:132) Mức thành viên (degree of
1000
cụm.
500
100
150
250
300
200 Top speed [km/h]
(cid:132) Ranh giới (boundary) giữa các
membership) của mỗi đối tượng với một cụm hoặc là 0 hoặc là 1.
(cid:135) Gom cụm mờ (fuzzy clustering)
(cid:132) 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.
(cid:132) Ranh giới giữa các cụm không rõ
cụm rõ ràng.
84
84
ràng (mờ - vague/fuzzy).
5.7. Tóm tắt
(cid:135) 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.
(cid:135) Độ đo đo sự tương tự tùy thuộc vào kiểu dữ
liệu/đối tượng cụ thể.
(cid:135) 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, …
85
85
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.
86
86
HỏiHỏi & & ĐĐápáp ……
87
87
ChChươươngng 5: 5: GomGom cụmcụm dữdữ liệuliệu
Phần 2
88
88
Nội dung
(cid:135) 5.6. Các phương pháp gom cụm dữ liệu
khác
(cid:135) [9], part 24.4, pp. 514-516
(cid:132) 5.6.1. Fuzzy c-Means Clustering
(cid:135) [9], part 21.3.3, pp. 433-436
(cid:198) Tóm tắt phần 2
89
89
(cid:132) 5.6.2. Self-Organizing Map (SOM)
Fuzzy c-means clustering
(cid:135) The most popular fuzzy clustering algorithm
avoiding local minima
(cid:135) But still converge to local minima of the squared error
criterion
(cid:132) Better than the hard K-means algorithm at
(cid:135) An iterative algorithm
(cid:132) Problem with the design of membership functions
2
c
n
−
m xu ij
j
c i
(cid:132) find cluster centers (centroids) that minimize a dissimilarity (or distance) (objective) function
∑∑
i
j
1 =
1 =
90
90
Fuzzy c-means clustering
(cid:132) n (columns): the number of clustered objects where n > 1
(cid:132) c (rows): the number of resulting clusters where 2 ≤ c < n
(cid:132) uij: degree of membership of the jth object xj belonging to
the ith cluster ci where i ∈ {1, …, c} and j ∈ {1, …, n}
(cid:135) Membership matrix = a real c x n matrix
(cid:135) Hard c-means clustering: uij ∈ {0, 1}
c
n
(cid:132) Probability:
u
1
j
,...,1{
n };
0
i
,...,1{
c }
u
∈∀=
∈∀>
ij
ij
∑
∑
i
j
1 =
1 =
c
c
u
u
0
or
0
c
j
,...,1{
n }
>
<
∈∀≤
(cid:132) Possibility:
ij
ij
∑
∑
i
i
1 =
1 =
91
91
(cid:135) Fuzzy c-means clustering: uij ∈ [0, 1]
Fuzzy c-means clustering
2
2
c
c
n
−
=
cp − i
m xu ij
j
c i
∑∑
∑ ∑
(cid:135) Hard c-means clustering: objective function
i
i
j
1 =
1 =
1 =
Cp ∈
i
minimize minimize
2
c
n
−
m xu ij
j
c i
(cid:135) Fuzzy c-means clustering: objective function
minimize minimize
∑∑
i
j
1 =
1 =
(cid:132) ||.||2: squared (Euclidean) distance (dissimilarity)
(cid:132) m: weighting exponent where 1 ≤ m < +∞
(cid:135) Control the relative weights placed on each of the distances
(cid:135) Popular chosen value: m=2 || range: 1.5 ≤ m ≤ 3.0 ([1, 30])
(cid:135) m (cid:198) 1 : increasingly hard || m (cid:198) +∞ : fuzziest
92
92
Fuzzy c-means clustering
2
n
c
(24.16)
−
m xu ij
j
c i
(cid:135) Fuzzy c-means clustering: objective function
minimize minimize
∑∑
i
j
1 =
1 =
2
(cid:132)
x − j
c i
2
(cid:132)
−
m xu ij
j
c i
c
2
−
(cid:132)
m xu ij
j
c i
∑
: 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
2
i 1 = c
n
(cid:132)
−
m xu ij
j
c i
∑∑
i
j
1 =
1 =
: overall weighted sum of generalized errors due to replacing all objects x by all centers of c clusters
93
93
Fuzzy c-means clustering
(cid:135) Each degree of membership uuijij of object xj belonging to cluster i is
c
n
(24.15)
u
u
1
j
,...,1{
n };
0
i
,...,1{
c }
∈∀=
∈∀>
ij
ij
∑
∑
i
j
1 =
1 =
randomly initialized in [0, 1] randomly initialized constraints: [0, 1] with the following constraints
(cid:135) Each degree of membership uuijij of object xj belonging to cluster i is 1
(24.18)
u
=
ij
/(2
m
)1 −
c
x
−
j
c i
∑
c
x
−
k
1 =
k
j
updated as follows:
(cid:135) Each center ccii of cluster i is updated
n
m xu ij
j
(24.17)
j
c i
1 n
u
m ij
∑ == ∑
94
j
1 =
94
updated as follows: then updated
Fuzzy c-means clustering
Fuzzy c-means algorithm (Bezdek, 1973)
95
[9], pp. 516
95
Fuzzy c-means clustering
(cid:135) Several widely-used termination criteria
number of iterations (cid:132) The number of iterations
objective function and its previous value is small enough.
Objective function (cid:135)(cid:135) Objective function
(cid:132) The difference between the updated value of
membership uuijij and their previous values is small enough.
Membership matrix (cid:135)(cid:135) Membership matrix
(cid:132) The difference between all updated degrees of
their previous values is small enough.
Centers (cid:135)(cid:135) Centers
96
96
(cid:132) The difference between all updated centers ccii and
Fuzzy c-means clustering
(cid:132) 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.
(cid:135) The nearer the cluster centers, the higher the membership
(cid:135) Notes on fuzzy c-means clustering
(cid:135) Possible with local minima
(cid:132) Parameter values determined in advance (experimental)
(cid:135) c: the number of clusters
(cid:135) m: weighting exponent
(cid:132) Dissimilarity/Similarity measures for particular applications
(cid:132) Cluster shape
(cid:132) Data type
(cid:132) Noise
97
97
grades
Fuzzy c-means clustering
clustering
(cid:132) The number of training
objects: 16
(cid:132) The number of clusters: 2
(cid:132) Weighting exponent: 2
(cid:132) Threshold t: 0.01
Data Set
Two resulting clusters
98
J. C. Bezdek, R. Ehrlich, W. Full, "FCM: the fuzzy c-means clustering algorithm", Computers & Geosciences 10 (2-3) (1984) 191-203.
98
(cid:135) Example on fuzzy c-means
Self-Organizing Map (SOM)
(cid:135) Unsupervised neural network model
(cid:135) Proposed by T. Kohonen in the early 1980s
(cid:132) Data clustering
Organizing Map,” Proceedings of the IEEE, vol. 78, no. 9, pp. 1464-1480, September 1990.
(cid:132) Further reading: Teuvo Kohonen, “The Self-
(cid:132) Visualize the clusters or similarities between patterns
(cid:132) Dimensionality reduction
99
99
(cid:135) Specially good at providing visualization of high- dimensional data in a fewer dimensional space (typically 1D, 2D, 3D)
Self-Organizing Map (SOM)
100
100
Self-Organizing Map (SOM)
neural network (cid:135) Kohonen (1982) developed a neural network organization whose key idea is
(low) twotwo--
based on selfself--organization to represent sensory signals as (low) images or maps. dimensional images or maps dimensional
(cid:135) Kohonen’s networks, often called Kohonen’s
feature maps or selforganizing maps, organized neighborhoods of neurons such the model are similar inputs into the model are that similar inputs into topologically close. topologically close
(cid:135) The SOM processes the input patterns and
learns to cluster or segment through adjustment of
the data cluster or segment the data weights. adjustment of weights
101
101
Self-Organizing Map (SOM)
(cid:135) SOM architecture
(cid:132) A typical SOM network has two layers of nodes, an input layer input layer and output layer (sometimes called the output layer Kohonen layer).
(cid:132) Each node in the input layer is
fully connected to nodes in the low fully connected (one, two, three-) dimensional output layer.
Weights w Weights w
Input x Input x
(cid:132) The number of nodes in the number nn of nodes in the input layer is corresponding to the input layer number of input variables (i.e. the length/dimensionality of an input vector xx).
(cid:132) The number
output nodes number mm ofof output nodes
(cid:135) This number of neurons in the
[9], part 21.3.3, pp. 434.
rectangular array should be large enough to allow a sufficient number of clusters to form.
102
102
depends on the specific problem and is determined by the user.
Self-Organizing Map (SOM)
(cid:135) SOM architecture
(cid:132) A winning neuron kk: the neuron corresponding to weight wwkk (an nnx1 vector) that has the minimum distance to the input xx randomly selected in a training step
Fig. 21.5. A 5x5 Kohonen Layer with two neighborhood sizes at radius of 1 and 2
[9], part 21.3.3, pp. 435.
around a winning neuron kk: the collection of all nodes with the same radial distance
103
103
(cid:132) The neighborhood NNkk
Self-Organizing Map (SOM)
(cid:135) Self-organizing (competitive, unsupervised)
learning
their activities by means of mutual lateral interactions, and develop adaptively into specific detectors of different signal patterns.
(cid:132) Neighboring cells in a neural network compete in
(cid:132) The cells become specifically tuned to various input signal patterns or classes of patterns through the learning process.
gives the active response to the current input.
(cid:135)(cid:135) winner
winner--take
all strategy take--all strategy
104
104
(cid:132) Only one cell or local group of cells at a time
Self-Organizing Map (SOM)
1. initialize the weights ww to small random values and the neighborhood size large enough to cover half the nodes
2. select an input pattern xx randomly from the training set
and present it to the network
3. find the best matching or “winning” node kk whose weight vector wwkk is closest to the current input vector xx using the vector distance
4. update the weights of nodes in the neighborhood of kk
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.
105
105
(cid:135) SOM learning procedure
Self-Organizing Map (SOM)
(cid:135) The vector distance where ||.|| represents the Euclidean
distance
Nin
is
if
)
(
i
+
=
−
k
Nin
)10(
not
i
=
(cid:135) The Kohonen learning rule new w α i new w i
old w i old w i
k
wxh ik i if is 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
106
grid and σ is the neighborhood radius.
106
Self-Organizing Map (SOM)
(cid:135) As the number of cycles of training (epochs)
increases, better formation of the clusters can be found.
(cid:135) Eventually, the topological map is fine-tuned
with finer distinctions of clusters within areas of the map.
(cid:135) After the network has been trained, it can be used as a visualization tool to examine the data structure.
(cid:135) Once clusters are identified, neurons in the
map can be labeled to indicate their meaning. (cid:132) Assignment of meaning usually requires knowledge
107
on the data and specific application area.
107
Self-Organizing Map (SOM)
(cid:135) Notes on SOM
(cid:132) Dimensionality (1D, 2D, 3D, ?) of the output layer
the output layer)
(cid:135) The number of clusters
(cid:132) The size of the map (the number of neurons of
preprocessing
(cid:132) Not restricted to any particular form of
(cid:132) Capable of noise handling
(cid:135) Extended versions for categorical data
108
108
(cid:132) Originally proposed for numeric data
Self-Organizing Map (SOM)
(cid:135) SOM’s Applications
(cid:132) market segmentation,
(cid:132) customer targeting,
(cid:132) business failure categorization,
(cid:132) credit evaluation,
(cid:132) document retrieval,
(cid:132) group technology
(cid:132) …
109
109
Self-Organizing Map (SOM)
Source: Teuvo Kohonen, “The
Self-Organizing Map,” Proceedings
of the IEEE, vol. 78, no. 9, pp.
1464-1480, September 1990.
110
110
Self-Organizing Map (SOM)
111
111
Self-Organizing Map (SOM)
Source: Teuvo Kohonen, “The
Self-Organizing Map,” Proceedings
of the IEEE, vol. 78, no. 9, pp.
112
1464-1480, September 1990.
112
Self-Organizing Map (SOM)
(cid:135) Example on SOM
(cid:132) The number of training vectors: 4
(cid:132) The length of each training vector/weight: 3
(cid:132) The number of clusters (output neurons): 2
(cid:132) Neighborhood size: 0
(cid:135) η(t) = 0.6; 1 <= t <= 4
(cid:135) η(t) = 0.5; 5 <= t <= 8
(cid:135) η(t) = 0.5; 9 <= t <= 12, etc.
Where t is iteration
113
113
(cid:132) Learning rate:
Self-Organizing Map (SOM)
Dissimilar
ity
Matrix
X
X
X
X
1
2
3
4
(cid:132) X1 = (1, 1, 0)
(cid:132) X2 = (0, 0, 0)
X X
1 2
0
0 2
(cid:132) X3 = (1, 0, 0)
(cid:132) X4 = (0, 0, 1)
X X
3 4
1 1
1 3
0 2
0
(cid:135) Training vectors:
(cid:135) Initial weights:
??
(cid:132) Neuron #1: w1 = (0.2, 0.6, 0.5)
(cid:132) Neuron #2: w2 = (0.8, 0.4, 0.7)
Network Architecture Network Architecture
??
Do X1 and X3 belong to one cluster?
114
Input units:
Do X2 and X4 belong to the other?
114
1 2 Output units:
Tóm tắt phần 2
(cid:135) Fuzzy c-means clustering
(cid:132) A fuzzy version of k-means clustering
(cid:135) Self-Organizing Map (SOM)
(cid:132) A neural network-based clustering and
dimensionality reduction technique
(cid:132) Support for visualization
115
115
HỏiHỏi & & ĐĐápáp ……
116
116
