untitled

K-Means

1 5 2 K-Means 7 2.1 K-Means.............................. 7 2.2 K-Means.......................... 8 2.3................... 9 3 K-Means 11 3.1.................................. 11 3.2.................................. 12 4 13 4.1 K-Means..... 13 4.2 K-Means.. 15 4.3....... 16 5 18 5.1 K-Means................ 18 5.2 LVQ K-Means.. 24 5.3 K-Means..... 28 6 34 7 34 35 35 2

1......... 8 2 3....................... 18 3 K =3 K-Means........... 19 4 K=3,m =2 K-Means...................................... 23 5............................ 23 6 K =3 LVQ..................... 24 7 K=3,m =2 LVQ K-Means...................................... 27 8 LVQ K-Means....................................... 27 9 2................... 28 10 K-Means..................... 29 11 K-Means......... 29 12................. 30 13 Km, (-1.027533,1.208392),(0.784579,-0.534775).... 31 14 Km, (-0.433101,-1.341578),(-0.314275,0.821440).... 31 15 Km, (-1.228715,-1.312461),(-3.800445,-0.485205)... 32 16 Km, (-3.217651,-2.154126),(-0.816030,-0.957352)... 32 17 Km, (2.355734,3.346941),(-3.366276,2.438362)..... 33 18 Km, (0.380646,-4.061833),(-4.050100,-0.687073).... 33 1 K-Means......... 19 2............................ 20 3 m =2 K-Means........... 20 4 m =3 K-Means........... 21 5 {R }, {R (m) } {D (m) }....................... 21 6 {ρ (m) }................................ 21 7 {d( c (m =2),p )}. 22 8 {d(r (m =2),p )}..... 22 9 LVQ................... 25 10 m =2 LVQ..................... 25 11 {R }, {R (m) } {D (m) }....................... 25 12 {ρ (m) }................................ 25 3

13 {d(r (m =2),p )}..... 26 14 Km,Km..................... 30 4

1 2 [1][2][3] K-Means [5][8][9] 1 N ( ) 2 1 N K-Means c- [4][7] K-Means (Learning Vector Quantization:LVQ)[6][11] 2 K-Means LVQ K-Means LVQ K-Means [16][17] 5

K-Means K-Means K-Means K K-Means [13][14] K-Means 2 K-Means LVQ 3 K-Means 4 K-Means LVQ 5 K-Means, K-Means,LVQ 2, K-Means 6,7 6

2 K-Means K-Means K 2 2.1 K-Means n x i =(x i1,...,x id ),i=1,...,n X K X, =1,...,K J = min { c,=1,...,k} i=1 n x i X x i c 2. (1) x i c 2 = D d=1 (x id c d ) 2 c =(c 1,..., c D ) (1) K-Means m (m1) { c (t) } x i x i X (t) α α = arg min x i c (t) 2. (2) (m2) {X (t) } c (t+1) = 1 n (t) x i X (t) x i, =1,...,K. (3) n (t) X(t) c (t+1) X (t) ( +1) ɛ c (t+1) c (t) <ɛ (m1) (m2) { c (t) } { c } (1) R R = { x x c 2 < x c i 2 for all i } (4) 7

if x R, x Class (5) { c } 1: 2.2 K-Means K-Means n X p x X q x X p X q X p X p { x} X q X q { x} c p, c q c p, c q X p N p 1, Xq N q +1 J [1] m (m 1) c (t), =1,...,K (m 2) J x i,i=1,...,n (m 2-1) x i X p N p 1 8

J p = J l = N p N p 1 x i c p 2 N l N l +1 x i c l 2, l p J q J l, for all l x i X p X q c p = c p 1 N p 1 ( x i c p ) c q = c q 1 N q +1 ( x i c q ) N p = N p 1 N q = N q +1 J J = J + J q J p X p Xp = X p { x i } X q Xq = X q { x i } x X p x X q x c p 2 = x c q 2 = x X p x c p 2 x X q x c q 2 N p N p 1 x i c p 2 N q N q +1 x i c q 2 2.3 (LVQ) K-Means t t =1, 2,... x(t) R p (t = 1, 2,...) (VQ) m R p, =1,...,K x(t) x(t) 9

m l m l (t) = arg min x(t) m (t). (6) x(t) m l (t) m l (t +1)=m l (t)+α(t)[x(t) m l (t)]. (7) α(t) α(t) =, α 2 (t) <, t =1, 2,... (8) t=1 t=1 α(t) α(t) = /t x(t) x(t) lvq (lvq1) m, =1,...,K (lvq2) t =1, 2,... (lvq2-1) m l = arg min 1 K x(t) m (t) (9) (lvq2-2) m 1 (t),...,m (t) m l (t +1) = m l (t)+α(t)[x(t) m l (t)] m (t +1) = m (t), l x(t) X l 10

3 K-Means K-Means X {R } { c } R R R R K-Means R R K-Means R 3.1 K-Means K = m (2 m M) R R m {R (m),p,p= 1,...,m}, { c (m),p,p=1,...,m} M 2 3 R D (m=1) R (m),p D (m),p = x i R (m),p = m R (m) x i R x i c 2. (10) x i c (m),p 2,m=2,...,M (11) D (m) = m p=1 D (m),p. (12) R ρ (m) =D (m) /D (m 1),m=2,...,M. (13) ρ (m) R m R m R m 1 R m 11

D (m) D (m 1) ρ (m ) = min {ρ (m), m=2,...,m} (14) m η ρ (m ) <η (15) R m R η η 3.2 R {R (m ),p,p =1,...,m } {R (m ),p } { c (m ),p,p =1,...,m } K-Means R m 1 c (m ),p R d( c (m ),p ) ˆd( c (m ),p ) = max p {d( c(m ),p ),p=1,...,m } (16) R (m ),p R p p R (m ),p d( c (m ),p ) d(r (m ),p ) = min x i R (m ),p, x j R l,l d( x i, x j ) (17) ˆd(R (m ),p ) = max p {d(r(m ),p ),p=1,...,m } (18) R (m ),p R R (m ),p ) d(r (m ),p ρ (m ) <η 12

4 SVM(Support Vector Machine)[15] H Φ :R p H H K( x, y) = Φ( x), Φ( y) H (19) Φ( x) RBF K( x, y) = exp( C x y 2 ) (20) K( x, y) = (1 + x, y ) d (21) 4.1 K-Means K-Means (1) K-Means K J = Φ( x i ) m 2 (22) =1 x i X m X m = x X Φ( x) n. (23) Φ Φ Φ( x i ) m 2 K( x i, x j ) D i = Φ( x i ) m 2 H. (24) (22) K J = D i (25) =1 x i X 13

D i = Φ( x i ) m 2 = Φ( x i ) x j X Φ( x j ), Φ( x i ) n x l X Φ( x l ) n = Φ( x i ), Φ( x i ) 2 Φ( x i ), Φ( x j ) + 1 n n 2 Φ( x j ), Φ( x l ) x j X x j, x l X = K( x i, x i ) 2 K( x i, x j )+ 1 n n 2 K( x j, x l ) x j X x j, x l X (26) Km (Km1) X K y j (j = 1,..., K) x i x i X (t) α α = arg min Φ( x i ) Φ( y j ) 2 = arg min K( x i, x i ) 2K( x i, y j )+K( y j, y j ). (27) (Km2) x i (Km2-1) x i α = arg min Φ( x i ) m 2 (28) (Km2-2) Φ( x i ) m 2 (26) 14

4.2 K-Means 4.1 n (25) Km (Km 1) X K y j (j = 1,..., K) x i (27) (Km 2) x i (Km 2-1) x i α = arg min Φ( x i ) m 2 (Km 2-2) x i (Km 2-2) J = D i (29) x i X J = K J. (30) =1 x i X p Xq X p,x q, m p, m q N p,n q Xp = X p { x i }, Xq = X q { x i }, m p = m q = N p N p 1 Φ( x i) m p 2, N q N q +1 Φ( x i) m q 2. J,J p,j q J,J p,j q J = J 15

= J p + J q + J p,q J p = x X p Φ( x) m p 2 Φ( x i ) m p 2 = Φ( x) m p + Φ( x i) m p 2 N p N x X p 1 N p 1 Φ( x i) m p 2 p = J p N p N p 1 Φ( x i) m p 2 = J p N p N p 1 D ip (31) J q = J q + N q N q +1 D iq. (32) J = J p + J q + p,q J = J p N p N p 1 D ip + J q + N q N q +1 D iq + p,q = J N p N p 1 D ip + N q N q +1 D iq (33) J 4.3 LVQ LVQ m l (t) = arg min Φ( x h ) m (t) (34) m l (t +1) = m l (t)+α(t)[φ( x h ) m l (t)] (35) m m t D i (t) = Φ( x i ) m (t) 2 (36) 16

(34) D il (t) = arg min D i (t) (37) (35) D i (t +1) = Φ( x i ) m (t +1) 2 = Φ( x i ), Φ( x i ) 2 Φ( x i ), m l (t +1) + m l (t +1), m l (t +1) (38) (35) α = α(t) D i (t +1) = Φ( x i ), Φ( x i ) 2{(1 α) Φ( x i ), m l (t) + α Φ( x i ), Φ( x h ) } + {(1 α) 2 m l (t), m l (t) +2α(1 α) Φ( x h ), m l (t) } + α 2 Φ( x h ), Φ( x h ) (39) D il (t +1) = (1 α)d il (t) α(1 α)d hl (t) + α{k( x i, x i ) 2K( x i, x h )+K( x h, x h )} (40) LVQ Klvq (Klvq1) D i,i=1,...,n, =1,...,K (Klvq2) t =1, 2,... (Klvq2-1) x i X l D il (t) = min D i (t) (Klvq2-2) D il (40) 17

5 5.1 K-Means 2 3 1 (x 1,x 2 )= (0, 0), (x 1,x 2 )=(0.1, 0.1) [10] 2 (x 1,x 2 )=(5, 0), (x 1,x 2 )=(2, 2) 3 (x 1,x 2 )=(1, 4), (x 1,x 2 )=(0.2, 0.2) (0.0861, 0.113), (4.98, 0.163), (1.10, 4.04) x 1 x 2 6 5 class1 class2 class3 centroid 4 3 2 x2 1 0-1 -2-3 -4-1 0 1 2 3 4 5 6 7 8 9 x1 2: 3 18

3 K-Means line1,line2,line3 3 R 1 line1 line3 c 1 =(1.67, 0.383), c 2 =(5.36, 0.146), c 3 =(1.55, 3.86) K-Means 3 130 17 1 6 5 4 c1 c2 c3 cluster-center line1 line2 line3 3 2 x2 1 0-1 -2-3 -4-1 0 1 2 3 4 5 6 7 8 9 x1 3: K =3 K-Means 1: K-Means R 1 23 c 1 =(1.67, 0.383) R 2 83 c 2 =(5.36, 0.146) R 3 24 c 3 =(1.55, 3.86) 19

2 K-Means D D c D p K-Means 3 2 K-Means M=3 K=m K-Means m m =2, 3 {R } K-Means 3,4 2: D D D p R 1 64.3 24.6 2.43 R 2 168.6 349.5 401.0 R 3 39.1 23.8 9.52 373.0 397.8 412.9 3: m =2 K-Means R (m=2) 1,1 10 c (m=2) 1,1 =(0.0861, 0.113) R (m=2) 1,2 13 c (m=2) 1,2 =(2.89, 0.590) R (m=2) 2,1 45 c (m=2) 2,1 =(4.72, 0.579) R (m=2) 2,2 38 c (m=2) 2,2 =(6.16, 1.05) R (m=2) 3,1 20 c (m=2) 3,1 =(1.10, 4.04) R (m=2) 3,2 4 c (m=2) 3,2 =(3.80, 2.98) 20

4: m =3 K-Means R (m=3) 1,1 10 c (m=3) 1,1 =(0.0861, 0.113) R (m=3) 1,2 2 c (m=3) 1,2 =(2.48, 1.37) R (m=3) 1,3 11 c (m=3) 1,3 =(2.96, 0.947) R (m=3) 2,1 29 c (m=3) 2,1 =(4.70, 1.10) R (m=3) 2,2 34 c (m=3) 2,2 =(5.15, 1.46) R (m=3) 2,3 20 c (m=3) 2,3 =(6.78, 0.218) R (m=3) 3,1 19 c (m=3) 3,1 =(1.05, 3.97) R (m=3) 3,2 1 c (m=3) 3,2 =(2.06, 5.21) R (m=3) 3,2 4 c (m=3) 3,2 =(3.80, 2.98) (10) (12) {R } {R (m) } {D (m) } 5 6 (13) 6 {ρ (m) } ρ (m=2) =1 ρ (m=2) =3 (15) η 0.4 m =2 R 1 R 3 2 5: {R }, {R (m) } {D (m) } D (m=1) D (m=2) D (m=3) =1 64.3 18.7 9.18 =2 269.6 172.5 110.5 =3 39.1 11.1 0.28 6: {ρ (m) } ρ (m=2) ρ (m=3) =1 0.290 0.492 =2 0.640 0.641 =3 0.283 0.781 21

7: {d( c (m =2),p )} R 1 R 2 R 3 d( c (m =2),p ) R (m =2) 1,1 3.39 1.81 d( c (m =2) 1,1 )=1.81 R (m =2) 1,2 0.688 2.36 d( c (m =2) 1,2 )=0.688 R (m =2) 3,1 2.31 3.11 d( c (m =2) 3,1 )=2.31 R (m =2) 3,2 1.18 0.434 d( c (m =2) 3,2 )=0.434 8: {d(r (m =2),p )} R 1 R 2 R 3 d(r (m ),p ) R (m =2) 1,1 3.04 3.09 d(r (m =2) 1,1 )=3.04 R (m =2) 1,2 0.366 0.882 d(r (m =2) 1,2 )=0.366 R (m =2) 3,1 1.97 2.60 d(r (m =2) 3,1 )=1.97 R (m =2) 3,2 0.882 0.628 d(r (m =2) 3,2 )=0.628 (16) {R (m =2),p, =1,p =1, 2} {R (m =2),p, =3,p =1, 2} {d( c (m =2),p )} 7 R (m =2) 1,2 R 2 R (m =2) 3,2 R 2 8 (17) R (m =2) 1,2 R 2 R (m =2) 3,2 R 2 4 K-Means R 1 line11 2 R 2 R 3 line33 2 R 2 5 22

6 5 4 3 2 c11 c12 c21 c22 c31 c32 cluster-center line1 line2 line3 line11 line33 x2 1 0-1 -2-3 -4-1 0 1 2 3 4 5 6 7 8 9 x1 4: K=3,m =2 K-Means 6 5 4 c1 c2 c3 line1 line2 line3 3 2 x2 1 0-1 -2-3 -4-1 0 1 2 3 4 5 6 7 8 9 x1 5: 23

5.2 LVQ K-Means K-Means LVQ LVQ K-Means 2 LVQ 6 9 6 130 11 LVQ LVQ LVQ [12] 6 5 "c1" "c2" "c3" "first_centroid" 4 3 2 x2 1 0-1 -2-3 -4-1 0 1 2 3 4 5 6 7 8 9 x1 6: K =3 LVQ 24

9: LVQ R 1 17 c 1 =(0.695, 0.073) R 2 89 c 2 =(5.23, 0.131) R 3 24 c 3 =(1.27, 3.97) 10: m =2 LVQ R (m=2) 1,1 10 c (m=2) 1,1 =(0.0861, 0.113) R (m=2) 1,2 7 c (m=2) 1,2 =(2.52, 0.391) R (m=2) 2,1 50 c (m=2) 2,1 =(4.54, 0.662) R (m=2) 2,2 39 c (m=2) 2,2 =(6.09, 1.03) R (m=2) 3,1 20 c (m=2) 3,1 =(1.10, 4.04) R (m=2) 3,2 4 c (m=2) 3,2 =(3.80, 2.98) 11: {R }, {R (m) } {D (m) } D (m=1) D (m=2) D (m=3) =1 35.63 7.82 5.31 =2 306.8 190.9 123.41 =3 41.17 11.07 8.64 12: {ρ (m) } ρ (m=2) ρ (m=3) =1 0.220 0.681 =2 0.627 0.653 =3 0.271 0.786 M=3 K=m LVQ K- Means m m =2 {R } K-Means 10 {R } {R (m) } {D (m) } 11 12 (13) η 0.4 {ρ (m) } m =2 R 1 R 3 2 7 25

LVQ (17) 13 R (m =2) 1,2 R 2 R (m =2) 3,2 R 2 LVQ K-Means 8 13: {d(r (m =2),p )} R 1 R 2 R 3 d(r (m ),p ) R (m =2) 1,1 2.66 3.09 d(r (m =2) 1,1 )=2.66 R (m =2) 1,2 0.333 1.82 d(r (m =2) 1,2 )=0.333 R (m =2) 3,1 1.97 2.17 d(r (m =2) 3,1 )=1.97 R (m =2) 3,2 1.82 0.628 d(r (m =2) 3,2 )=0.628 26

6 5 4 "c11" "c12" "c21" "c22" "c31" "c32" "centroid" 3 2 x2 1 0-1 -2-3 -4-1 0 1 2 3 4 5 6 7 8 9 x1 7: K=3,m =2 LVQ K-Means 6 5 "cluster1" "cluster2" "cluster3" 4 3 2 x2 1 0-1 -2-3 -4-1 0 1 2 3 4 5 6 7 8 9 x1 8: LVQ K-Means 27

5.3 K-Means 9 2 (ball) (ring) 200 K-Means 10 K-Means 11 C =0.1 RBF 5 4 "b" "r" 3 2 1 x2 0-1 -2-3 -4-5 -5-4 -3-2 -1 0 1 2 3 4 5 x1 9: 2 28

5 4 "c1" "c2" 3 2 1 x2 0-1 -2-3 -4-5 -5-4 -3-2 -1 0 1 2 3 4 5 x1 10: K-Means 5 4 "b15" "r15" 3 2 1 x2 0-1 -2-3 -4-5 -5-4 -3-2 -1 0 1 2 3 4 5 x1 11: K-Means 29

400 2 100 13-18 3 13,14 15,16 17,18 12 12: K-Means (Km) K-Means (Km ) 100 14 2 14: Km,Km method Km 0.21 13.23 Km 0.24 6.94 30

5 4 "output/b15" "output/r15" "output/init_pnt15" 3 2 1 x2 0-1 -2-3 -4-5 -5-4 -3-2 -1 0 1 2 3 4 5 x1 13: Km, (-1.027533,1.208392),(0.784579,-0.534775) 5 4 "output/b71" "output/r71" "output/init_pnt71" 3 2 1 x2 0-1 -2-3 -4-5 -5-4 -3-2 -1 0 1 2 3 4 5 x1 14: Km, (-0.433101,-1.341578),(-0.314275,0.821440) 31

5 4 "output/b27" "output/r27" "output/init_pnt27" 3 2 1 x2 0-1 -2-3 -4-5 -5-4 -3-2 -1 0 1 2 3 4 5 x1 15: Km, (-1.228715,-1.312461),(-3.800445,-0.485205) 5 4 "output/b41" "output/r41" "output/init_pnt41" 3 2 1 x2 0-1 -2-3 -4-5 -5-4 -3-2 -1 0 1 2 3 4 5 x1 16: Km, (-3.217651,-2.154126),(-0.816030,-0.957352) 32

5 4 "output/b18" "output/r18" "output/init_pnt18" 3 2 1 x2 0-1 -2-3 -4-5 -5-4 -3-2 -1 0 1 2 3 4 5 x1 17: Km, (2.355734,3.346941),(-3.366276,2.438362) 5 4 "output/b72" "output/r72" "output/init_pnt72" 3 2 1 x2 0-1 -2-3 -4-5 -5-4 -3-2 -1 0 1 2 3 4 5 x1 18: Km, (0.380646,-4.061833),(-4.050100,-0.687073) 33

6 K-Means K-Means K-Means LVQ K-Mean LVQ LVQ 7 K-Means K-Means K-Means K-Means 34

[1] Duda R.O., Hart P.E., Stor D.G., Pattern Classification (2nd Edition), John Wiley & Sons, INC., 2001. [2] Jain A.K., Dubes R.C., Algorithms for Clustering Data, Prentice-Hall, Englewood Cliffs, NJ, 1988. [3] Gordon A.D., Classification (2nd Edition), Chapman & Hall/CRC, 1999. [4] Bezde J.C., Pattern Recognition with Fuzzy Objective Function Algorithms, Plenum Press, NY, 1981. [5] MacQueen J., Some Methods for Classification and Analysis of Multivariate Observations, Proc. 5th Bereley Symp. on Math. Stat. and Prob. 1, Univ. of California Press, Bereley and Los Angeles, pp. 281-297, 1967. [6] Linde Y., Buzo A., Gray R.M., An Algorithm for Vector Quantizer Design, IEEE Trans. Commun., Vol.28, pp. 84-95, 1980. [7], :,,, 1999. [8] Tarsitano A., A Computational Study of Several Relocation Methods for K-Means Algorithm, Pattern Recognition, Vol.36, pp.2955-2966, 2003. [9] Yu J., General C-Means Clustering Model, IEEE Trans. PAMI., Vol.27, No.8, pp.1197-1211, 2005. [10] Press W.H., Flannery B.P., Teuolsy S.A., Vetterling W.T., Numerical Recipes in C, Cambridge University Press, 1988. [11] T.Kohonen, Self-Organizing Maps (2nd Edition), Springer, Berlin, 1997. [12],,, Vol.46, pp.912-918, 2005. [13] M.Girolami, Mercer ernel based clustering in feature space, IEEE Trans. on Neural Networs, Vol.13, No3, pp.780-784, 2002. 35

[14] S.Miyamoto, Y.Naayama, Algorithms of hard c-means clustering using ernel functions in support vector machines, J. of Advanced computational Intelligence and Intelligent Informatics, Vol.1.7, No.1, pp.19-24, 2003. [15] V.Vapni, Statistical Learning Theory, Wiley, New Yor, 1998. [16] F.Morii, K.Kurahashi, Clustering by the K-Means Algorithm Using a Split and Merge Procedure, Proceedings of SCIS&ISIS, SA-F2-6, pp.1767-1770, 2006. [17],, K-Means,, PRMU, vol.106, No.470, pp.67-71, 2007. 36