Khai phá dữ liệu - Chương 5: Gom cụm dữ liệu

ng 5

ươ

Gom c m d li u

ữ ệ

ụ

Data Clustering

1 Gi Gi

i thi u i thi u

ớ ớ

ệ ệ

• S bùng n thông tin hi n nay do tác đ ng c a các ệ ủ ự ộ

siêu ph ổ . ng ti n và WWW ệ

ươ ệ ố ấ ệ

ụ ự ờ ể ố

ộ

ườ ộ

• Các h th ng truy v n thông tin d a trên vi c phân nhóm, gom c m (clustering) ra đ i đ làm tăng t c đ tìm ki m thông tin. ế • Do s bi n đ ng th ự ế ậ

ng xuyên c a thông tin nên i không th duy ng t các nhóm, ể c m (cluster) trong m t môi tr ườ ụ ộ

ủ các thu t toán clustering đang t n t ồ ạ trì t ố nh thư ế.

ấ ề ặ ể ậ

ng xuyên clustering l ệ ả ậ

01/18/13

www.lhu.edu.vn

• V n đ đ t ra là làm th nào đ c p nh t các ậ ế c c p ậ ượ ỗ i toàn ạ 2 cluster trong h th ng m i khi thông tin đ ố nh t thay vì ph i th ườ b d li u? ộ ữ ệ

Gi Gi

i thi u i thi u

ớ ớ

ệ ệ

Gom c m (clustering) là quá trình nhóm t p ậ ng thành các c m (cluster) có các đ i ố ụ

ng gi ng nhau.

ụ đ i t ố ượ t ượ

ố

ụ

ạ

ượ

ộ

Cho CSDL D={t1,t2,…,tn} và s nguyên k, gom c m là bài toán xác đ nh ánh x f: ị c gán vào m t Dg{1,…,k} sao cho m i ti đ ỗ c m (l p) Kj, 1 <= j <= k . ụ

ớ

ụ

ớ

Không gi ng bài toán phân l p, các c m c.

không đ

c bi

t tr ế ướ

ố ượ

3

01/18/13

www.lhu.edu.vn

Gi Gi

i thi u i thi u

ớ ớ

ệ ệ

D a trên kho ng cách

ự

ả

4 Gi Gi

i thi u i thi u

ớ ớ

ệ ệ

ể

ng ụ Cách bi u di n các c m ễ – Phân chia b ng ằ ranh ườ

1 2 3

các đ i ớ gi

0.5 0.2 0.3

…

ố ầ

– Các kh i c u – Theo xác su tấ – Hình cây – …

5 M đ u ở ầ

ụ

ọ c gán nhãn.

ượ

ủ

ữ

ạ

ọ ụ ụ

ẫ ộ

ươ

ự

ệ

Gom c m d li u là hình th c h c không giám sát, ữ ệ ứ trong đó các m u h c ch a đ ư ẫ M c đích c a gom c m d li u là tìm nh ng m u đ i ụ ữ ệ nhau (theo m t tiêu ng t di n hoăc gom c m t chu n nào đó) thành các c m ụ

ẩ

ị

ự

Đ nh nghĩa: ộ ậ

ậ

ng t

m t t p d li u m u, các ph n t t ươ

Gom c m là quá trình xây d ng m t t p h p t ợ ừ ộ ậ trong t p đã gom c m ụ ữ ệ ầ ử c. nhau v m t vài thu c tính ch n tr ướ

ụ ẫ ề

ự

ộ

ọ

ộ

6 What Is Clustering?

Group data into clusters

– Similar to one another within the same cluster – Dissimilar to the objects in other clusters – Unsupervised learning: no predefined classes

Outliers

Cluster 1

Cluster 2

7 Application Examples

A stand-alone tool: explore data distribution A preprocessing step for other algorithms Pattern recognition, spatial data analysis,

image processing, market research, WWW, … – Cluster documents – Cluster web log data to discover groups of

similar access patterns

8 Th nào là PP gom c m t

t?

ụ

ế

ố

ng t ng t ộ ươ ộ ươ cao trong cùng c m (intra-class) ụ th p gi a các c m (inter-class) ụ

ự ự ấ ệ

• Có đ t • Có đ t • Kh năng phát hi n m u n (hidden patterns) ả • Có kh năng làm vi c hi u qu v i m u l n ệ ữ ẫ ẩ ệ ẫ ớ ả ớ

ả (scalability)

• Kh năng làm vi c v i nhi u lo i d li u khác ớ ạ ữ ệ ề ệ

ả nhau

• ….

9 Ma tr n d li u (Data Matrix)

ữ ệ

ậ

ể

ụ

• Dùng đ mô hình hóa bài toán gom c m • Ma tr n bi u di n không gian d li u g m ồ

ữ ệ

ễ

ộ

• Ma tr n bi u di n m i quan h đ i t

ậ n đ i t ố ượ ậ

ể ng theo p thu c tính ể

ố

ệ ố ượ  

ễ theo thu c tính: ộ

ø Ø

x 11 

x 1 f 

ng x 1 p 

œ Œ

 

œ Œ

x 1 i 



x if 

x ip 



œ Œ



œ Œ

x 1 n

œ Œ ß º

10 Ma tr n phân bi

t (Dissimilarity Matrix)

ậ

ệ

Bi u di n kho ng cách gi a 2 đi m (đ i ố

ữ

ễ

ể

ả

ữ ệ

ồ

ng) trong không gian d li u g m n đ i ố ng theo p thu c tính

ộ

ể t ượ t ượ

ø Ø

œ Œ

d d

œ Œ

0 (2,1) (3,1) 

0 (3,2) 

0 

œ Œ



nd (

,1)

nd (

,2)

œ Œ ß º

11 3. Đ đo kho ng cách

ộ

ả

Distances are normally used measures Minkowski distance: a generalization

+ |

jid ),(

q (

x i

x i 1

x i

++ x ... | j 1 If q = 2, d is Euclidean distance If q = 1, d is Manhattan distance Weighed distance

- - -

jid ),(

++ ...

q q ()|

j 1

xpw | i

xw | i 1 1

xw | i 2

- - -

12 Properties of Minkowski Distance

Nonnegative: d(i,j) ‡ The distance of an object to itself is 0

– d(i,i) = 0

Symmetric: d(i,j) = d(j,i) Triangular inequality

– d(i,j) £

d(i,k) + d(k,j)

13

Các ph

ươ

ng pháp phân c m (Categories of ụ Clustering Approaches )

ng thành k c m:

ụ

ố ượ

ố ượ ng thu c v 1 c m duy nh t ấ ụ ề c ướ

Thu t toán phân ho ch (Partitioning algorithms)

ạ

ng và t o m t c m ch a nó. ộ ụ

ứ

ỗ ố ượ ầ

ụ

ộ

i b

c 2 cho đ n khi còn 1 c m duy nh t là toàn b không gian

Thu t toán phân c p (Hierarchy algorithms) ấ

ụ

ế

ấ

ộ

1 c m duy nh t là toàn b không gian

ộ

t có ph n t

ụ ộ

ụ

ệ

ậ

ấ

ầ ử

ể

ớ

ị

ng thu c 1 c m ho c đ t đi u

ấ ỗ ố ượ

ế

ộ

– Tách: • Xu t phát t ừ ấ • Ch n c m có đ phân bi ọ ặ c 2 cho đ n khi m i đ i t ủ ố ụ

ấ t cao nh t (ma tr n phân bi ệ l n nh t ho c giá tr trung bình l n nh t) đ tách đôi ấ ớ • L p l i b ụ ặ ạ ướ ụ ừ ệ

ạ ki n d ng (đ s c m ho c kho ng cách gi a các c m đ nh ) ỏ ả

ặ ủ

ữ

ặ

ạ ậ Phân ho ch c s d li u D có n đ i t ạ ơ ở ữ ệ – M i c m có ít nh t 1 đ i t ấ ỗ ụ – M i đ i t ộ ỗ ố ượ – K là sô 1c m cho tr ụ ậ – G p: ộ • Xu t phát m i đ i t ấ • N u 2 cum g n nhau thì g p thành 1 c m ế • L p l ặ ạ ướ

ề 14

Các ph

ng pháp phân c m (ti p)

ươ

ụ

ế

ng pháp d a trên m t đ (Density-

• Ph

ậ ộ

ươ

• Ph

ng pháp d a trên l

i (Grid-based

ự based methods) ự

ướ

• Ph

ng pháp d a trên mô hình (Model-

ự

ươ methods) ươ based)

15 4 Thu t toán K-means

ậ

ố ượ

ụ

ng thành k c m ồ

• Phân ho ch n đ i t ạ • Thu t toán K-means g m 4 b ướ ọ

ậ ọ đ uầ

– Ch n ng u nhiên k đi m làm tr ng tâm ban ể ẫ

i) t ng đi m vào c m có tr ng ạ ừ ặ ụ ể ọ

– Gán (ho c gán l ầ tâm g n đi m đang xét. ể

ế ụ

ừ ả ệ ậ

– N u không có phép gán nào thì d ng (các c m đã n đ nh và thu t toán không c i thi n thêm đ

ừ ụ

– Tính tr ng tâm cho t ng c m – Quay l c 2. ị ổ c n a) ữ ượ ọ i b ạ ướ

16

K-Means: Example

Update the cluster means

reassign

Assign each objects to most similar center

K=2

Arbitrarily choose K object as initial cluster center

Update the cluster means

17

Example

ể

ụ

Cho t p đi m: ậ X1={1,3} = {x11,, x12} X2={1.5,3.2} = {x21,, x22} X3={1.3,2.8} = {x31,, x32} X4={3,1} = {x41,, x42} Dùng K-mean phân c m v i k=2 ớ B c 1: Kh i t o ma tr n phân ho ch U (2 rows and ở ạ ậ ạ

ij) 1<=i<=2; 1<=j<=4

ướ 4 columns) B c 2: U=(m ướ

18

Cho n=0 (s l n l p) t o U

ố ầ ặ

ạ

U0= C1

Every column has 1 bit number 1

B c 3: Tính các vector tr ng tâm

ướ

ọ

Do có 2 c m C1, C2 do đó có 2 vector tr ng t m

ụ

ậ

ọ

19

Vector v1 for cluster C1:

x 11

*11

*14

v 11

x m

m m

x 31 m 14

+ 21 + 12 +

*11

*14

v 12

m m

x 32 m 14

+ 22 + 12 +

m *12 *13 + + 11 m 13 + 3*03.1*05.0*01*1 +++ 0001 + x 12 m x *12 *13 + + 11 m m 13 + 1*08.2*02.3*03*1 +++ 0001

v )3,1(1

20

Vector v2 for cluster C2:

x 11

*21

*24

+ +

x m

x 31 m 24

21 22 +

93.1

*21

*24

+ +

x m

x 32 m 24

22 22 +

33.2

m m *22 + 21 m m + 3*13.1*15.1*11*0 +++ 1110 x 12 m m *22 + 21 m m + 1*18.2*12.3*13*0 +++ 1110

*23 + 23 8.5 3 *23 + 23 7 3

v )33.2.93.1(1

21

Computing the Euclide distance for all points to clustering:

vxd

)1,1(

x 11(

v )11

x 12(

v )12

- -

)11(

)33(

vxd

)2,1(

x 11(

)21

x 12(

)22

- -

)93.11(

)33.23(

14.1

G p x1 vào c m C1 vì d(x1,v1) < d(x1,v2)

ụ

ộ

ng t

ươ

: ự

d(x2,v1)=0.54 < 0.97 = d(x2,v2) g p x2 vào C1

ộ

d(x3,v1)=0.36 < 0.78 = d(x3,v2) g p ộ x3 vào C1

22

d(x4,v1)=2.83 > 1.70 = d(x4,v2) g pộ x4 vào C1

x1 x2 x3 x4

ạ

Tăng n lên 1 Ma tr n phân ho ch U s ẽ ậ là:

C2 0

U0= C1 1

L p l ặ ạ

i cho đ n khi ế Không có phép gán nào thì d ng, n u ừ ế c 3 i b sai quay l ạ ướ

23

2) Fuzzy C-means

ậ

ạ

ậ

ạ

ờ

ứ

ậ ụ ẽ ị

ộ ậ

ự

ể

)

(

)

)( j Cxd i

Thu t toán K-means phân ho ch t p d ữ li u thành các c m là các t p rõ. ụ ệ Phân ho ch m xem các c m là các ờ t p m và 2 đi m d li u s có m c đ i ộ ữ ệ ể ậ thu c v m t c m v i giá tr trong [0,1]. ớ ề ộ ụ Thu t toán Fuzzy C-means c c ti u hàm m c tiêu: ụ n

= 1

(cid:229) (cid:229)

24

2) Fuzzy C-means

ự

ể

Thu t toán Fuzzy C-means c c ti u hàm ậ m c tiêu:

ụ

=

J

(m

)

(

,

)

)( j Cxd i

Trong đó:

ộ

ủ

ộ

ụ

hàng i c t j c a ma tr n thành ậ ộ ủ j vào c m j

– m>1 là tham s m hóa (m đi u ch nh đ ộ ỉ ng ng, ươ ứ

ụ

(cid:229) (cid:229)

25

ộ ề ủ ườ

– μij là ph n t ầ ử viên U, bi u di n đ thu c c a x ễ ể (có Cj là tr ng tâm) ọ ề ố ờ thu c v c a 1 đi m vào c m t ể ng ch n m=2) thông th ọ

Thu t toán Fuzzy C-means

ậ

ữ ệ

ể

i i=1,n. C n ầ

ồ ụ

ạ

ậ

Không gian d li u g m n đi m x phân ho ch thành c c m (2<= c

ướ

ồ ố ờ

1. Chon tham s m hóa m>1

nxc v i 0<= ớ

2. Kh i t o ma tr n thành viên U ậ ở ạ μij <=1

sao cho

(

)

x i

== 1 i n

(cid:229) (cid:229)

= 1 ủ

j j c a cum j (j=1..c)

(

)

3. Tính tr ng tâm C ọ

= 1

(cid:229)

26

Thu t toán Fuzzy C-means(ti p)

ế

ậ

4. C p nh t ma tr n kho ng cách D ậ ậ ậ

nxc theo đ ộ ij là kho ng cách ả

ả ọ ả

đo kho ng cách đã ch n (d xừ i đ n Cế t

ậ -

= (cid:229) c

ø Ø ậ N u dế ậ ij >0 thì - 5. C p nh t ma tr n thành viên U: 2 m (cid:246) (cid:230) œ Œ (cid:247) (cid:231) (cid:247) (cid:231) œ Œ ł Ł œ Œ ß º

ij=0 thì xij trùng v i tr ng tâm

ớ ọ

27

c tr c ế ướ

i l p l i t ớ ướ c 3. b c l Ng i, n u d ế ượ ạ μij =1 Cj c a c m j, ủ ụ 6. N u U thay đ i là đ nh so v i b ủ ỏ ổ c l ượ ạ ặ ạ ừ ướ thì d ng, ng ừ

Example

ể

ạ

ờ

(0), s m=2 và tiêu chu n h i t ộ ụ

ầ ẩ

Cho t p đi m: ậ X1={1,3} = {x11,, x12} X2={1.5,3.2} = {x21,, x22} X3={1.3,2.8} = {x31,, x32} X4={3,1} = {x41,, x42} Dùng Fuzzy C-mean phân c m ụ v i k=2 ớ Phân ho ch m ban đ u U gi ả ử e =0.01. Phân ho ch m ban đ u là: ờ

ạ

ầ

(

)

U0= 1 0 0 1 0 1 0 1

ắ

v ij

== 1 k n

Tính tr ng tâm ban đ u b ng ầ công th c sau v i m=2

ọ ứ

ớ

(

)

(cid:229)

28

= 1

a. V i c m 1(c=1)

ớ ụ

Vector v1 cho c m 1ụ

2 1

x 1

2 4

v 1

x m

* +

x 3 m

2 3 2 3 +

j 2 4 x

x 1

2 j 2 2 2 2 1 x x *1 3 2 +++ 0111 + + x 3

x 1

26.1

v 11

3.15.11 3

0.3

v 12

2 3 + 8.32.33 3

29

b. V i c m 2(c=2)

ớ ụ

Vector v1 cho c m 1ụ = v

x 2

0

2 1

0 =

=

j 4 +++ v

1 0 ,3

v

=

}1,3{ ả

ừ

ế

ể

ọ

ủ

ế

ể

ừ ả

ọ

ỏ

ả ụ ng vào c m

v Ti p theo tính kho ng cách t ng đi m đ n tr ng ế tâm c a nó. Tính kho ng cách t ng đi m đ n các c m C1,C2 và ch n c m có kho ng cách nh nh t ụ ấ đ đ a đ i t ể ư

ố ượ

ụ

30

b. V i c m 2(c=2) (ti p)

ớ ụ

ế

)26.11(

)33(

26.0

d 11

- -

)26.15.1(

)32.3(

31.0

d 12

- -

)26.13.1(

)38.2(

20.0

d 13

- -

)26.13(

)31(

65.2

d 14

)31(

)13(

82.2

- -

)35.1(

)12.3(

66.2

- -

)33.1(

)18.2(

47.2

- -

)33(

)11(

0.0

31

V i đ đo kho ng cách, c p nh t U

ớ ộ

ả

ậ

(

)1.6

( r ik

d d

= 1

r )( ik )( r jk

- ø Ø (cid:246) (cid:230) (cid:247) (cid:231) œ Œ (cid:229) (cid:247) (cid:231) œ Œ ł Ł ß º

2 +(cid:247)

991.0

+(cid:247)

26.0 36.0

26.0 82.2

= 1

d 11

- - - ø Ø ø Ø ø Ø (cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) (cid:247) (cid:231) œ Œ (cid:247) (cid:231) (cid:247) (cid:231) œ Œ (cid:247) (cid:231) (cid:231) œ Œ (cid:229) (cid:247) (cid:231) (cid:231) (cid:247) (cid:231) œ Œ ł Ł ł Ł œ Œ œ Œ ł Ł ł Ł ł Ł ß º ß º ß º

968.0

+(cid:247)

31.0 66.2

d 12

- - ø Ø ø Ø (cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) (cid:247) (cid:231) (cid:247) (cid:231) œ Œ (cid:247) (cid:231) œ Œ (cid:247) (cid:231) (cid:231) ł Ł œ Œ œ Œ ł Ł ł Ł ß º ß º