ươ ươ
ữ ệ ữ ệ
ụ ụ
Ch Ch
ng 5: Gom c m d li u ng 5: Gom c m d li u
ữ ệ
Khai phá d li u
(Data mining)
1
ộ
N i dung
ữ ệ
ụ
ổ
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 ắ
2
ố
5.0. Tình hu ng 1 – Outlier detection
ử ụ
ủ
ủ
ộ
ộ
ườ i đang s d ng Ng ậ ự ẻ th ID = 1234 th t s ẻ là ch nhân c a th hay là m t tên tr m?
3
ữ ệ
ạ
ố
5.0. Tình hu ng 2 Làm s ch d li u
ể
ả
biên (outliers) và gi m thi u
ậ ễ
Nh n di n ph n t ầ ử ệ nhi u (noisy data)
ả
ễ
ể
ả
i pháp gi m thi u nhi u
ụ
Phân tích c m (cluster analysis)
4
Gi
ố
5.0. Tình hu ng 3
5
ố
5.0. Tình hu ng 3
6
ố
5.0. Tình hu ng 3
7
ố
5.0. Tình hu ng 3
8
ố
5.0. Tình hu ng 3
9
ố
5.0. Tình hu ng 3
10
ố
5.0. Tình hu ng 3
11
ố
5.0. Tình hu ng 4
http://kdd.ics.uci.edu/databases/CorelFeatures/CorelFeatures.data.html
Gom c mụ nhả
12
5.0. Tình hu ng …ố
13
Gom c mụ
5.0. Tình hu ng …ố
ỗ ợ
ữ ệ
ử
ề
ạ
ả ự
ố ữ ệ
ố ượ
H tr giai đo n ti n x lý d li u (data preprocessing)
s phân b d li u/đ i t
ng (data distribution)
ậ
ạ
ẫ
Mô t
ữ ệ
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)
ng (market segmentation)
ụ
ệ
Phân m nh th tr
Gom c m tài li u ((WWW) document clustering)
14
…
ữ ệ
ụ
ổ
ề 5.1. T ng quan v gom c m d li u
ữ ệ
ố ượ
ụ
ụ
ớ
Quá trình gom nhóm/c m d li u/đ i t
ng vào các l p/c m
ộ ụ
ươ
ự ớ
ơ
ng t
ớ v i nhau h n so v i
Các đ i t ố ượ đ i t
ố ượ ở ng
ng trong cùng m t c m t ụ các c m khác.
Gom c mụ
ở ụ ươ ự ơ c m C2 Obj1 t ng t Obj2 h n so
ở ụ Obj1, Obj2 c m C1; Obj3 ự ớ ươ v i t Obj3. ng t
15
Gom c mụ
ữ ệ
ụ
ổ
ề 5.1. T ng quan v gom c m d li u
ữ ệ
ố ượ
ụ
ụ
ớ
Quá trình gom nhóm/c m d li u/đ i t
ng vào các l p/c m
ộ ụ
ươ
ự ớ
ơ
ng t
ớ v i nhau h n so v i
Các đ i t ố ượ đ i t
ố ượ ở ng
ng trong cùng m t c m t ụ các c m khác.
Gom c mụ
ở ụ ươ ự ơ c m C2 Obj1 t ng t Obj2 h n so
Intracluster distances are minimized.
Intercluster distances are maximized.
16
ở ụ Obj1, Obj2 c m C1; Obj3 ự ớ ươ v i t Obj3. ng t
ữ ệ
ụ
ổ
ề 5.1. T ng quan v gom c m d li u
ữ ệ
ố ượ
ụ
ụ
ớ
Quá trình gom nhóm/c m d li u/đ i t
ng vào các l p/c m
ộ ụ
ươ
ự ớ
ơ
ng t
ớ v i nhau h n so v i
Các đ i t ố ượ đ i t
ố ượ ở ng
ng trong cùng m t c m t ụ các c m khác.
Gom c mụ
ở ụ ươ ự ơ c m C2 Obj1 t ng t Obj2 h n so
ở ụ Obj1, Obj2 c m C1; Obj3 ự ớ ươ v i t Obj3. ng t
Intracluster distances are minimized.
Intercluster distances are maximized.
Low inter Low inter cluster/class cluster/class similarity similarity
17
High intra High intra cluster/class cluster/class similarity similarity
ữ ệ
ụ
ổ
ề 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)
...
...
(cid:0) (cid:0)
(cid:0) (cid:0)
(cid:0) (cid:0)
... ...
... ...
(cid:0) (cid:0)
(cid:0) (cid:0)
(cid:0) (cid:0)
... ...
... ...
(cid:0) (cid:0)
11x ... i1x ... n1x
1fx ... ifx ... nfx
1px ... ipx ... npx
(cid:0) (cid:0) (cid:0) (cid:0)
ố ượ n đ i t ng (objects)
18
ế ộ p bi n/thu c tính (variables/attributes)
ữ ệ
ụ
ổ
ề 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
ệ
t (dissimilarity matrix)
Ma tr n sai bi ậ
(cid:0) (cid:0)
0 d(2,1)
0
(cid:0) (cid:0)
(cid:0) (cid:0)
d
0
d(3,1 )
(cid:0) (cid:0)
:
(cid:0) (cid:0)
(cid:0) (cid:0)
: nd
)2,3( : nd
...
)1,(
)2,(
...
0
(cid:0) (cid:0) (cid:0) (cid: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
19
ượ ủ ế ể ộ ộ ỳ 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
ề ể
ữ ệ
ố ượ
ấ
ượ
ụ
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) (cid:0) 0
d(i,i) = 0
d(i,j) = d(j,i)
20
d(i,j) (cid:0) d(i,k) + d(k,j)
ữ ệ
ụ
ổ
ề 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
ố ượ
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:
Đ i t
x = (x1, …, xp)
y = (y1, …, yp)
21
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
ề ể
ữ ệ
ố ượ
ấ
ượ
ụ
V n đ ki u d li u/đ i t
ng đ
c gom c m
Intervalscaled variables/attributes
Binary variables/attributes
Categorical variables/attributes
Ordinal variables/attributes
Ratioscaled variables/attributes
22
Variables/attributes of mixed types
ữ ệ
ụ
ổ
ề 5.1. T ng quan v gom c m d li u
Intervalscaled variables/attributes
Mean absolute deviation
s
m
|
|
|
...
|
|)
f
f
f
f
f
mx nf
f
1
x 2
(|1 mxn
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
1
...
.)
Mean
f
f
f
x nf
1
x 2
(xn m
(cid:0) (cid:0) (cid:0) (cid:0)
f
(cid:0)
Zscore measurement
z if
mx if s
f
23
(cid:0)
ữ ệ
ụ
ổ
ề 5.1. T ng quan v gom c m d li u
ả
ộ
q
q
Đ đo kho ng cách Minkowski
q
x
x
x
jid ),(
(|
|
|
|
...
|
q )|
p
p
2
2
x i 1
j 1
x i
j
x i
j
ả
ộ
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
Đ đo kho ng cách Manhattan
jid
x
x
x
|),(
|
|
|
...
|
|
p
p
2
2
x i 1
j 1
x i
j
x i
j
ả
ộ
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
2
2
Đ đo kho ng cách Euclidean
x
x
x
jid ),(
(|
|
|
|
...
|
2 )|
p
p
2
2
x i 1
j 1
x i
j
x i
j
24
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
ữ ệ
ụ
ổ
ề 5.1. T ng quan v gom c m d li u
Binary variables/attributes Object j 0 b
1 a
sum ba
1
(cid:0)
dc
c
d
Object i
(cid:0)
0 sum
dbca
p
(= a + b + c + d)
(cid:0) (cid:0)
(cid:0)),( jid
cb dcba
(cid:0) ệ ố ế ả ơ H s so trùng đ n gi n (n u symmetric): (cid:0) (cid:0) (cid:0)
(cid:0)),( jid
cb cba
25
(cid:0) ệ ố ế H s so trùng Jaccard (n u asymmetric): (cid:0) (cid:0)
ữ ệ
ụ
ổ
ề 5.1. T ng quan v gom c m d li u
Ví dụ
Name Gender Fever Cough Test1 Test2 Test3 Test4 P Jack M P Mary F N Jim M
N P N
Y Y Y
N N P
N N N
N N N
ạ
i: asymmetric
gender: symmetric Binary attributes còn l Y, P 1, N 0
Binary variables/attributes
d
jack
mary
(
,
)
33.0
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
d
jack
jim
(
,
)
67.0
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
jimd
mary
(
,
)
75.0
10 102 11 111 21 211
26
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
ữ ệ
ụ
ổ
ề 5.1. T ng quan v gom c m d li u
Variables/attributes of mixed types
ổ
f
f
)
)
T ng quát
p f
jid ),(
( ij )
(cid:0) (cid:0) (cid:0)
(cid:0) 1 p f
d f ( ij
( ij (cid:0) 1
(cid:0) (cid:0)
N u xế
if ho c xặ
jf b thi u (missing) thì
f (variable/attribute): binary (nominal)
(f) = 1 otherwise
dij
(f) = 0 if xif = xjf , or dij
f : intervalscaled (Minkowski, Manhattan, Euclidean)
ế ị
1
if
1
f
r M
f : ordinal or ratioscaled zif tính ranks rif và
27
ở
zif tr thành intervalscaled
(cid:0) (cid:0) (cid:0)
ữ ệ
ụ
ổ
ề 5.1. T ng quan v gom c m d li u
28
ữ ệ
ụ
ổ
ề 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. 645678.
29
ữ ệ
ụ
ổ
ề 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 ?
nên đ
c gom vào bao nhiêu c m?
ụ
ượ ạ
Các phân t
c t o ra?
Bao nhiêu c m nên đ
30
Bao nhiêu c m?ụ 6 c m?ụ
2 c m?ụ 4 c m?ụ
ữ ệ
ụ
ổ
ề 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) ề ậ
(different types of attributes)
ụ
ả
ạ
ớ
Kh năng x lý nhi u ki u thu c tính khác nhau ể
(clusters with arbitrary shape)
ể
ứ
ề
ề
ệ
ầ
ố ị
ậ
ố
Kh năng khám phá các c m v i hình d ng tùy ý
ữ ệ
ử
ễ
ả
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)
31
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
ề ệ
ữ ệ
ụ
ể
ầ
Các yêu c u tiêu bi u v vi c gom c m d li u
ứ ự ủ
ộ ậ
ụ
ớ
ả ữ ệ
ậ
ầ c a d li u nh p (incremental clustering and insensitivity to the order of input records)
ữ ệ
ử
ề
ả
Kh năng gom c m tăng d n và đ c l p v i th t
ự
ả
ộ
Kh năng x lý d li u đa chi u (high dimensionality)
ụ based clustering)
ả ễ
ả ụ
Kh năng gom c m d a trên ràng bu c (constraint
32
Kh di n và kh d ng (interpretability and usability)
ữ ệ
ụ
ổ
ề 5.1. T ng quan v gom c m d li u
ạ
ươ
ữ ệ
ụ
ể
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 đ (densitybased): d a trên connectivity and density
functions.
ướ
ự
ự
i (gridbased): d a trên a multiplelevel granularity
D a trên l structure.
ự
ộ
ế ượ
D a trên mô hình (modelbased): 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.
…
33
Phân lo i các ph
ữ ệ
ụ
ổ
ề 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ể
34
Original Points Partitioning
ữ ệ
ụ
ổ
ề 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ể
p1
p1
p3
p4
p3
p4
p2
p2
p1 p2
p3
p4
35
Hierarchical Original Points
ữ ệ
ụ
ổ
ề 5.1. T ng quan v gom c m d li u
ươ
ữ ệ
ụ
ệ ng pháp đánh giá vi c gom c m d li u
ạ
Đánh giá ngo i (external validation)
Các ph
Đánh giá k t qu gom c m d a vào c u trúc đ
ụ ự ế ấ ả ượ ỉ ướ ị c ch đ nh tr c cho
ộ
Đánh giá n i (internal validation)
ữ ệ ậ t p d li u
ụ ố ượ ậ ữ ủ ng các vector c a chính t p d
ươ
ố
Đánh giá t
ng đ i (relative validation)
ế ậ ầ ả Đánh giá k t qu gom c m theo s l ệ li u (ma tr n g n – proximity matrix)
Đánh giá k t qu gom c m b ng vi c so sánh các k t qu gom c m
ụ ụ ế ệ ằ ả ả
ụ
ệ
ế
ả
ọ
ố ư
Tiêu chí cho vi c đánh giá và ch n k t qu gom c m t
i u
ứ ố ế ớ ộ ị khác ng v i các b tr thông s khác nhau
Đ 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.
36
ụ ộ
ữ ệ
ụ
ổ
ề 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
ạ
ộ
Đ đo: Rand statistic, Jaccard coefficient, Folkes and Mallows
index, …
ộ
Đánh giá ngo i (external validation)
ộ
Đ đo: Hubert
’s (cid:0)
statistic, Silhouette index, Dunn’s index, …
ươ
ố
Đánh giá n i (internal validation)
ng đ i (relative validation)
37
Đánh giá t
ữ ệ
ụ
ổ
ề 5.1. T ng quan v gom c m d li u
ươ
ữ ệ
ụ
ệ 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)
38
J. Wu and et al. Adapting the Right Measures for Kmeans Clustering. KDD’09, Paris, France, July 2009.
Các ph
ữ ệ
ụ
ằ
ạ
5.2. Gom c m d li u b ng phân ho ch
ụ
ả
Đánh giá k t qu gom c m ế
Contingency matrix
ả ế ụ ố ượ ng
ậ ự ủ ố ượ ng
39
i t
ố ố ượ ng trong P Partition P: k t qu gom c m trên n đ i t Partition C: các c m th t s c a n đ i t Cừ j ụ (cid:0) Cj|: s đ i t nij = |Pi
ữ ệ
ụ
ằ
ạ
5.2. Gom c m d li u b ng phân ho ch
ụ
ế
ả
Đánh giá k t qu gom c m
ụ ế ả ươ K t qu gom c m theo ph ng án I và II
ố ượ ụ ế ả ng
ậ ự ủ ố ượ Partition P: k t qu gom c m trên n (=66) đ i t Partition C: các c m th t s c a n (=66) đ i t ng
40
i t
ố ố ượ ng trong P ụ (cid:0) Cj|: s đ i t nij = |Pi Cừ j
ữ ệ
ụ
ằ
ạ
5.2. Gom c m d li u b ng phân ho ch
ụ
ế
ả
ấ ượ
ỏ
ụ
ố
Entropy (tr nh khi ch t l ị
ng gom c m t
t)
Đánh giá k t qu gom c m
Entropy
I )(
log
)
(
p i
j
i
Entropy
II
(
)
log
)
(
p i
j
i
p ij p i
p ij p i
p ij p i
p ij p i
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
(
log
)
i
j
(
log
)
j
i
n i n
n ij n i
n i n
n ij n i
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
log
log
)
log
log
log
)
log
19 66
n ij n i 0 19
19 66
0 ( 19
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
log
(
log
log
)
log
(
log
log
)
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
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
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
23 66 24 66 ???
23 66 24 66 ???
(cid:0) (cid:0)
41
ươ ươ ố 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
ả
ậ
i thu t kmeans
42
Gi
ữ ệ
ụ
ằ
ạ
5.2. Gom c m d li u b ng phân ho ch
43
ữ ệ
ụ
ằ
ạ
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
44
Optimal Clustering Sub-optimal Clustering
ữ ệ
ụ
ằ
ạ
5.2. Gom c m d li u b ng phân ho ch
ủ
ặ
ả
ậ
Đ c đi m c a gi ể
i thu t kmeans?
45
ữ ệ
ụ
ằ
ạ
5.2. Gom c m d li u b ng phân ho ch
ủ
ặ
ả
ậ
Đ c đi m c a gi ể
i thu t kmeans
ố ư
i u hóa
ị ụ
ự
ộ
C c tr c c b
ặ
ở
ủ
ụ
c đ c tr ng hóa b i trung tâm c a c m
Bài toán 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?
ộ
M i c m đ ỗ ụ ố ượ (i.e. đ i t
ố ố ượ
ố ầ ặ
ố ụ
n là s đ i t
ng, k là s c m, t là s l n l p
Đ ph c t p: O(nkt) ứ ạ
46
k << n, t << n
ữ ệ
ụ
ằ
ạ
5.2. Gom c m d li u b ng phân ho ch
ủ
ặ
ả
ậ
Đ c đi m c a gi ể
i thu t kmeans
ưở
ầ ử
ễ
ở
ng b i nhi u (các ph n t
ị kì d /biên)
ụ
ệ
ợ
ụ
ồ
nh h Ả
không l 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)
47
Không phù h p cho vi c khai phá ra các c m có d ng ạ ướ ấ c r t i (nonconvex) hay các c m có kích th
ữ ệ
ụ
ằ
ạ
5.2. Gom c m d li u b ng phân ho ch
ủ
ặ
ả
ậ
Đ c đi m c a gi ể
i thu t kmeans
ủ
ậ
ươ
ớ i thu t kmeans v i ng án II) khác nhau
u cho tr
ả ươ c
ế ị hai tr k1 (ph ậ trên cùng t p d li u m
ấ ượ
ỏ
ụ
ố
ị Entropy (tr nh khi ch t l
ng gom c m t
t)
Đánh giá k t qu gom c m c a gi ả ụ ng án I) và k2 (ph ữ ệ ướ ẫ
Entropy (I) = ???
Entropy (II) = ???
48
ươ ươ ố 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
ủ
ặ
ả
ậ
Đ c đi m c a gi ể
i thu t kmeans
ụ
ả
ậ
ớ
i thu t kmeans v i hai
ị
ng án II) khác nhau trên
ậ
ế ươ ng án I) và k2 (ph tr k1 (ph ẫ ữ ệ cùng t p d li u m u cho tr
ủ ươ ướ c
ị ớ
ấ ượ
ụ
ố
Fmeasure (tr l n khi ch t l
ng gom c m t
t)
Đánh giá k t qu gom c m c a gi ả
Fmeasure (I) = ???
Fmeasure (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
49
ả Entropy?
ữ ệ
ụ
ằ
ạ
5.2. Gom c m d li u b ng phân ho ch
50
ữ ệ
ụ
ằ
ạ
5.2. Gom c m d li u b ng phân ho ch
51
Tính “total cost S of swapping Oj và Orandom” = ΣpCp/OiOrandom
ữ ệ
ụ
ằ
ạ
5.2. Gom c m d li u b ng phân ho ch
= 0
Cp/OiOrandom
Cp/OiOrandom
Cp/OiOrandom
Cp/OiOrandom
= d(p,Oi) – d(p,Orandom)
= d(p,Oj) – d(p,Orandom)
= d(p,Oj) – d(p,Oi)
52
Tính “total cost S of swapping Oj và Orandom” = ΣpCp/OiOrandom
ữ ệ
ụ
ằ
ạ
5.2. Gom c m d li u b ng phân ho ch
ủ
ặ
ả
ậ
Đ c đi m c a gi ể
i thu t PAM (kmedoids)
53
???
ữ ệ
ụ
ằ
ạ
5.2. Gom c m d li u b ng phân ho ch
ủ
ặ
ả
ậ
Đ c đi m c a gi ể
i thu t PAM (kmedoids)
ượ
ầ ử
ệ
ạ
ở
ụ
c đ i di n b i ph n t
ữ chính gi a c m
ự ả
ả
ưở
ầ ử
ủ
ị ự
ị
ể Gi m thi u s nh h
ễ ng c a nhi u (ph n t
biên/kì d /c c tr ).
ố ụ
ầ
ượ
ị
ướ
S c m k c n đ
c xác đ nh tr
c.
ứ ạ
ặ
ộ
ỗ
M i c m đ ỗ ụ (centroid).
2)
ả
ưở
ở
ướ ậ
ữ ệ
Gi
ậ ị ả i thu t b nh h
ng b i kích th
c t p d li u.
54
Đ ph c t p cho m i vòng l p O(k(nk)
ụ
ằ
ấ
ữ ệ 5.3. Gom c m d li u b ng phân c p
ấ
ụ
ằ
Gom c m d li u b ng phân c p (hierarchical
ố ượ
ấ
ng vào cây phân c p
ụ
ữ ệ clustering): nhóm các đ i t ủ c a các c m
ụ
ộ
Agglomerative: bottomup (tr n các c m)
ố ụ
ậ
ầ
ố
Không yêu c u thông s nh p k (s c m)
ừ
ệ
ầ
Yêu c u đi u ki n d ng ề
ộ
Không th quay lui ể
ở ỗ ướ m i b
c tr n/phân tách
55
Divisive: topdown (phân tách các c m)ụ
ụ
ằ
ấ
ữ ệ 5.3. Gom c m d li u b ng phân c p
An agglomerative hierarchical clustering method: AGNES
(Agglomerative NESting) bottomup
A divisive hierarchical clustering method: DIANA (Divisive ANAlysis)
topdown
56
ụ
ằ
ấ
ữ ệ 5.3. Gom c m d li u b ng phân c p
An agglomerative hierarchical clustering method: AGNES
(Agglomerative NESting)
ỗ ố ượ
ở ầ
ộ ụ
ạ
Kh i đ u, m i đ i t
ng t o thành m t c m.
ụ
ượ
ộ ạ
ộ
Các c m sau đó đ
c tr n l
i theo m t tiêu chí nào đó.
ụ ậ ộ ạ ế ả c tr n l i n u kho ng
Cách ti p c n singlelinkage: c m C1 và C2 đ ng t
ụ
ượ ặ ạ ế
ấ ả
ố ượ
c l p l
i đ n khi t
t c các đ i t
ạ ng t o
Quá trình tr n các c m đ ộ ấ ộ ụ thành m t c m duy nh t.
A divisive hierarchical clustering method: DIANA (Divisive ANAlysis)
ấ ả
ố ượ
ộ ụ
ạ
ấ
ở ầ Kh i đ u, t
t c các đ i t
ng t o thành m t c m duy nh t.
ượ
ỗ ụ
ế
ộ
c phân tách theo m t tiêu chí nào đó đ n khi m i c m
M t c m đ ộ ụ ỉ
ộ ố ượ
ch có m t đ i t
ng.
ố ượ ừ ắ ượ ấ C1 và C2 là ng n nh t. ế ữ cách gi a 2 đ i t
Kho ng cách l n nh t gi a các đ i t
57
ố ượ ữ ấ ả ớ ậ ấ ng c n nhau 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
Singlelinkage Completelinkage
58
ụ ộ Tiêu chí tr n các c m: singlelinkage và completelinkage
ụ
ằ
ấ
ữ ệ 5.3. Gom c m d li u b ng phân c p
ằ
ấ
ượ
ể
ễ
ở
c bi u di n b i
ấ c u trúc cây (dendrogram).
59
Quá trình gom c m b ng phân c p đ ụ
ụ
ằ
ấ
ữ ệ 5.3. Gom c m d li u b ng phân c p
ấ
ằ
ượ
ể
ễ
ở
c bi u di n b i
ấ c u trúc cây (dendrogram).
ụ
ự ế
ng t
k t
ợ
ộ ươ 3 c m có đ t ấ ỏ h p nh nh t 0.5
Quá trình gom c m b ng phân c p đ ụ
60
0.5
ụ
ằ
ấ
ữ ệ 5.3. Gom c m d li u b ng phân c p
ữ
ụ
ộ
ả Các đ đo dùng đo kho ng cách gi a các c m C
i và Cj
ố ượ
p, p’: các đ i t
ng
’
ữ
ả
|pp’|: kho ng cách gi a p và p
ố ượ
ủ
ươ
ng trung bình c a C
ứ ng ng
mi, mj: đ i t
i, Cj, t
61
ố ượ
ố ượ
ươ
ng đ i t
ủ ng c a C
ứ ng ng
ni, nj: s l
i, Cj, t
ụ
ằ
ấ
ữ ệ 5.3. Gom c m d li u b ng phân c p
ộ ố ả
ữ ệ
ụ
ậ
ằ
M t s gi
i thu t gom c m d li u b ng phân
c pấ
ạ
ố ượ ả
ủ
using Hierarchies): phân ho ch các đ i t ộ ấ c u trúc cây theo đ co giãn c a phân gi resolution)
BIRCH (Balanced Iterative Reducing and Clustering ng dùng i (scale of
ộ
ờ ạ ụ
ụ
ữ
ụ 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
ự ươ
ể
ộ
ị
ROCK (Robust Clustering using linKs): gom c m dành
ng t
ự
ụ
ữ
ặ
gi a các c p c m
62
Chameleon: mô hình đ ng đ xác đ nh s t
ụ
ằ
ấ
ữ ệ 5.3. Gom c m d li u b ng phân c p
ộ ố ấ
ề ớ
ữ ệ
ụ
ằ
M t s v n đ v i gom c m d li u b ng phân
c pấ
ể
ọ
ộ
ợ
ả
Ch n đi m tr n/phân tách phù h p
ể
ầ
ỗ
M i quy t đ nh tr n/phân tách yêu c u ki m tra/đánh giá
ế ị ố ượ
ề
ộ ụ ng/c m.
nhi u đ i t
ữ ệ
ụ
ằ
ấ
ợ
ớ
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
ụ
ề
Gom c m nhi u giai đo n (multiplephase clustering) ạ
63
Kh năng co giãn (scalability)
ậ ộ
ụ
ự
ữ ệ 5.4. Gom c m d li u d a trên m t đ
ữ ệ
ậ ộ
ự
ụ
Gom c m d li u d a trên m t đ
ặ
ồ
ộ
ỗ ụ ố ượ
đ i t
ng.
ố ượ
ư
ơ
ượ
ễ
Các đ i t
ng trong vùng th a h n đ
c xem là nhi u.
ỗ ụ
ạ
M i c m là m t vùng dày đ c (dense region) g m các
ả
Gi
ậ i thu t
M i c m có d ng tùy ý.
Applications with Noise)
DBSCAN (DensityBased Spatial Clustering of
Structure)
OPTICS (Ordering Points To Identify the Clustering
64
DENCLUE (DENsitybased CLUstEring)
ậ ộ
ụ
ự
ữ ệ 5.4. Gom c m d li u d a trên m t đ
DBSCAN (DensityBased Spatial Clustering of
Applications with Noise)
ậ ộ
ự
ể
OPTICS (Ordering Points To Identify the
Clustering Structure)
ữ ệ
ứ ự
ể
ấ
Phân tích các đi m k t n i nhau d a vào m t đ ế ố
các đi m d li u tùy vào c u trúc gom ữ ệ
ậ ộ ủ ậ
ự
ạ ụ c m d a vào m t đ c a t p d li u
DENCLUE (DENsitybased CLUstEring)
ố ậ ộ
ự
ụ
T o ra th t
65
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 đ
ữ ệ
ự
ụ
Các khái ni m dùng trong gom c m d li u d a
ệ trên m t đậ ộ
là εneighborhood.
ε: bán kính của vùng láng giềng của một đối tượng, gọi
εneighborhood của một đối tượng.
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).
εε
εε
p: core object (MinPts = 3) q: không là core object
p
q
66
MinPts: số lượng đối tượng ít nhất được yêu cầu trong
ậ ộ
ụ
ự
ữ ệ 5.4. Gom c m d li u d a trên m t đ
ữ ệ
ự
ụ
Các khái ni m dùng trong gom c m d li u d a
ệ trên m t đậ ộ
ạ ượ
ự c tr c
ể ạ ượ
ự
q có th đ t đ
ả c tr c ti p t
ế ừ p n u ế q trong vùng ả
εneighborhood c a ủ p và p ph i là core
ti p): ế láng gi ng ề object.
εε
εε
p: directly densityreachable đ i v i q: directly densityreachable đ i v i
ố ớ q? ố ớ p?
p
q
p: directly densityreachable đ i v i q: directly densityreachable đ i v i
ố ớ q? X ố ớ p? (cid:0)
67
Directly densityreachable (kh năng đ t đ
ậ ộ
ụ
ự
ữ ệ 5.4. Gom c m d li u d a trên m t đ
ữ ệ
ự
ụ
Các khái ni m dùng trong gom c m d li u d a
ệ trên m t đậ ộ
ả
ạ ượ
c):
ướ ậ
ng
ỗ
ố ượ
chu i các đ i t
ng
Cho tr c t p đ i t q densityreachable từ p nếu (cid:0)
ừ
Densityreachable (kh năng đ t đ ố ượ D, ε và MinPts
p1, ..., pn (cid:0) D v i ớ p1 = p và pn = q sao cho pi+1 directly densityreachable t pi theo các thông s ố ε và MinPts, 1 ≤ i ≤ n.
ủ
ề
Bao đóng truy n (transitive closure) c a directly density
reachable
ệ ấ ố ứ
Quan h b t đ i x ng (asymmetric relation)
q
p2
p
MinPts = 5
68
ậ ộ
ụ
ự
ữ ệ 5.4. Gom c m d li u d a trên m t đ
ữ ệ
ự
ụ
Các khái ni m dùng trong gom c m d li u d a
ệ trên m t đậ ộ
ố ế ự
ậ ộ
c t
ướ ập các đối tượng D, ε và MinPts
D
o (cid:0)
Cho tr p, q (cid:0) q densityconnected v i ớ p n u ế (cid:0)
D sao cho c ả q và p đ u ề
Densityconnected (n i k t d a trên m t đ ):
densityreachable t
ừ o theo các thông s ố ε và MinPts.
ệ ố ứ
Quan h đ i x ng
p
p
q
o
q
o
69
ậ ộ
ụ
ự
ữ ệ 5.4. Gom c m d li u d a trên m t đ
ữ ệ
ự
ụ
Các khái ni m dùng trong gom c m d li u d a
ệ trên m t đậ ộ
MinPts = 3
70
ậ ộ
ụ
ự
ữ ệ 5.4. Gom c m d li u d a trên m t đ
ệ
ậ ộ
ữ ệ
Border Outlier
ậ ộ
ụ
C m d a trên m t đ (density based
ậ ấ ả
ng
ố ượ ự
ố ế ớ
ậ
t c các đ i t c n i k t v i nhau d a trên m t
ự cluster): t p t ượ đ đ .ộ
Các khái ni m dùng trong gom ự ụ c m d li u d a trên m t đ
Đ i t
ố ượ ể ộ ề ụ ng thu c v c m có th là
ố ượ
N u đ i t ế
ng đó không là core object
ọ
ố ượ
ớ
ng ranh gi
i (border
core object.
thì g i là đ i t object).
Core
ề ụ ộ ng không thu c v c m nào
ε = 1cm
MinPts = 5
71
ễ ố ượ Đ i t ượ đ c xem là nhi u (noise/outlier).
ậ ộ
ụ
ự
ữ ệ 5.4. Gom c m d li u d a trên m t đ
DBSCAN (DensityBased Spatial Clustering of
Applications with Noise)
ậ
ng
ố ượ D, ε, MinPts
Input: t p đ i t
Output: densitybased clusters (và noise/outliers)
ị
ỗ ố ượ
ủ
1. Xác đ nh
ε–neighborhood c a m i đ i t
ng
p (cid:0)
D.
2. If p là core object, tạo được một cluster.
ừ ấ
ố ượ
3. T b t kì core object
t c các đ i t
ng
Giải thuật
density
p, tìm t ố ượ
ặ
ấ ả ng này (ho c các cluster) v
ào cùng
reachable và đ a các đ i t ứ cluster ng v i
ư ớ p.
ạ ượ c (densityreachable cluster) c ó thể được
72
3.1. Các cluster đ t đ trộn lại với nhau.
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 đ
(cid:0)
C1
(cid:0)
(cid:0)
73
C1
MinPts = 4
ậ ộ
ụ
ự
ữ ệ 5.4. Gom c m d li u d a trên m t đ
with Noise)
ể
ặ
Đ c đi m ???
DBSCAN (DensityBased Spatial Clustering of Applications
Các c m có d ng và kích th
ả ị
ố ủ
ố ượ
ề
ữ ệ
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)
ụ ạ ướ c khác nhau.
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)
74
ứ ạ ộ
ữ ệ
ụ
ự
5.5. Gom c m d li u d a trên mô hình
ữ ệ
ố ư
ữ
ự
ợ
ả ị
ữ ệ
ề
ạ
Gi
đ nh v quá trình t o d li u
T i u hóa s phù h p gi a d li u và mô hình toán nào đó
ươ
ượ ạ ự ề ấ ố ớ ữ ệ D li u đ c t o ra v i nhi u s phân b xác su t khác nhau.
ng pháp
ế
ố
Ti p c n th ng kê ậ
Các ph
M r ng c a gi
ở ộ ủ ậ ự ạ i thu t gom c m d a trên phân ho ch kmeans:
ụ
ệ
ế
ậ
ọ
Ti p c n h c máy: gom c m ý ni m (conceptual clustering)
ế
ạ
ậ
Ti p c n m ng neural: SelfOrganizing Feature Map (SOM)
75
ụ ả ExpectationMaximization (EM)
ữ ệ
ụ
ự
5.5. Gom c m d li u d a trên mô hình
ụ
ụ
ướ
ỳ c k
Gi ả ọ
ố ướ
ậ v ng) và
ố ượ ặ ng vào các c m (b i thu t tinh ch nh l p đ gán các đ i t ạ ự ị c c c đ i hoá).
ể ỉ ướ ượ c l ng tr thông s (b
ụ
ệ
Gom c m ExpectationMaximization (EM)
ố ượ
ượ
ự
ớ
c gán nhãn d a vào các
T o ra cách phân l p các đ i t ư
ng ch a đ ứ ố ượ
ệ
ỗ
ớ
đ c tr ng cho m i nhóm đ i t
ư ỗ ng ng v i m i khái ni m
ạ ả ặ mô t (concept).
ụ
ạ
Gom c m ý ni m (conceptual clustering)
ỗ ụ
ụ
ễ
ể
ể
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 t
v i
c phân b vào m t c m n u t ộ
ố ượ ng m i đ ụ ủ
ả
ế ươ ấ ự exemplar c a c m đó nh t d a trên đ đo kho ng cách.
76
Gom c m v i m ng neural ớ
ữ ệ
ụ
ự
5.5. Gom c m d li u d a trên mô hình
77
ữ ệ
ụ
ự
5.5. Gom c m d li u d a trên mô hình
ả
ậ
Gi
i thu t ExpectationMaximization (EM)
ế ươ
ự
ộ ụ 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
Gán m t đ i t ụ
ớ
ụ
ữ
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).
ộ ụ
ể ố ư
ụ
ộ
ấ Xác su t thành viên (probability of membership)
ư nhanh nh ng có th t
i u c c b
78
H i t
ữ ệ
ụ
ự
5.5. Gom c m d li u d a trên mô hình
ả
ậ
Gi
i thu t ExpectationMaximization (EM)
ố ượ
ng,
Input: t p n đ i t ậ
ố ụ K (s c m)
ị ố ư
ố ủ
i u cho các thông s c a mô hình
ả
ậ
Output: tr t
i thu t:
1. Kh i trở ị
Gi
ọ ẫ ố ượ ng làm trung tâm c a K đ i t ủ K c mụ
ố ụ
ặ
ỉ
2. L p tinh ch nh các thông s (c m):
ố ế ầ ầ ị 1.1. Ch n ng u nhiên 1.2. Ướ ượ c l ng tr ban đ u cho các thông s (n u c n)
i đ n c m
ỗ ố ượ ướ ụ ế 2.1. B c k v ng (expectation step): gán m i đ i t ng x
ỳ ọ ấ ớ K Ck v i xác su t P(x ớ Ck) v i k=1..
i (cid:0) 2.2. B c c c đ i hóa (maximization step):
ướ ự ạ ị ướ ượ c l ng tr các thông
79
số
ừ ệ ề ị ướ 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
ả
ậ
i thu t ExpectationMaximization (EM)
ả
ậ
Gi
i thu t:
1. Kh i trở ị
Gi
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 x
ụ i đ n c m C
k
ấ
ỳ ọ ướ ớ v i xác su t P(x
i (cid:0)
Ck)
ướ
ự
ạ
ị
ố
2.2. B c c c đ i hóa (maximization step):
ướ ượ c l
ng tr các thông s
80
ụ
ủ
(mk là trung tâm c a c m C
k, j = 1..K, k = 1..K)
ố ụ ặ ỉ
ươ
ữ ệ
5.6. Các ph
ụ ng pháp gom c m d li u khác
3500
ụ
ứ
Gom c m c ng (hard clustering)
Lorries
3000
]
2500
M i đ i t
g k [ t
Sports cars
i
2000
ỗ ố ượ ề ộ ụ ộ ỉ ng ch thu c v m t c m.
h g e W
1500
Medium market cars
ứ
ớ ng v i
M c thành viên (degree of ỗ ố ượ ủ membership) c a m i đ i t ặ m t c m ho c là 0 ho c là 1.
1000
500
100
150
250
300
ộ ụ ặ
200 Top speed [km/h]
Ranh gi ràng.
ụ
Gom c m m (fuzzy clustering) ờ
ớ ụ ữ i (boundary) gi a các c m rõ
M i đ i t
ề ơ
ứ
Ranh gi
ộ m t c m v i m c thành viên nào đó ừ t ỗ ố ượ ề ng thu c v nhi u h n ớ ộ ụ ế 0 đ n 1.
ụ i gi a các c m không rõ
81
ớ ờ ữ ràng (m vague/fuzzy).
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, …
82
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. 645678.
83
ỏ
ỏH i & Đáp … H i & Đáp …
84
