dQA 4.49 dQB 3.69 dQC 5.10 d QD 4.4
dQE 5.22 dQF 0.89 dQG 0.45 dQH 1.26 dQI 1 dQJ 0.63
Step 2 again.
So,we classify A,B,C,D,E as a cluster and F,G,H,I,J as another cluster.
10
Example
cluster 1
E
C
D
P(1.6,4.8)
A
B
cente(rxi ,yj)
ij
M A,B,C,D ,E(1.6,4.8)
new center
NF,G ,H,I,J(4.8,1.6)
F
cluster 2 I
G
H
Q(4.8,1.6)
J
P , Q as the centre and K=2.
A dAA 0
< dBA 1
B
dAB 1
>
dBB 0
C dAC 1
< dBC 1.41
> D dAD 1.41
dBD 1
> E dAE 2.24
dBE 2
> F dAF 3.61
dBF 2.83
> G dAG 4.47 > H dAH 5.39
> I dAI 4.24
J d AJ 5
Step 3 again.
The new centers of
the two clusters are
equal to the original
P(1.6,4.8)
and
Q(4.8,1.6)
11
Final
E CD
A
B
cluster 1
cluster 2
F
G
H
I
J
Clustering finished !
The new centers of the two clusters are (1,4.5) and (3.75,2.875)
7
Example
E
C
D
α(1,4.5)
A
B
β(3.75,2.875)
F
G
H
I
J
< A dA 0.5 < B dB 1.12 < C dC 0.5 < D dD 1.12
k-means算法的简单示例
3
Algorithm Procedure
1. Randomly select K points from complete samples as the initial center.(That's what k means in K-means)
2. Each point in the dataset is assigned to the closed cluster,based upon the Euclidean distance between each point and each cluster center.
< E dE 1.8 > F dF 3.91
> G dG 4.72 > H dH 5.59
> I dI 4.61 > J dJ 5.32
d A 2.97 d B 2.08 dC 3.48 dD 2.75
d E 3.58 d F 0.91
dG 1.53 d H 2.41
d I 1.89 d J 2.25
9
Example
E
C
D
P(1.6,4.8)
A
B
F
G
H
Q(4.8,1.6)
I
J
A dPA 1
<
< B dPB 0.89
< C dPC 0.63 < D dPD 0.45
< E dPE 1.26 > F dPF 3.69
> G dPG 4.40 > H dPH 5.22
> I dPI 4.49 > J dPJ 5.10
cluster 1
cluster 2
F
G
H
I
J
cente(rxi ,yj)
ij
A,C(1 21,4 25)(1,4.5)
new center
B,D ,E,F,G ,H ,I,J(3.7,2 5.87 )
Randomly choose A,B as the centre ae
E
C
D
A
B
F
G
H
I
J
How to cluster A,B...H,J into two clusters?
5
Example
E
CD
d AC
d BC
A(1,4) B(2,4)
F
G
H
I
J
Randomly choose A,B as the centre and K=2.
Step 1 and 2.
12
Disadvantages
one of the main
disadvantages to k-means is
α , β as the centre and K=2.
Step 2 again.
So,we classify A,B,C,D,E as a cluster and F,G,H,I,J as another cluster.
8
Example
E
C
D
α(1,4.5)
A
B
cluster 1
β(3.75,2.875)
>
dBG 3.61 dBH 4.47
dBI 3.61 dBJ 4.24
d AB means distance A→B
So,we classify A,C as a cluster and B,E,D,F,G,H,I and J as another cluster.
6
Example
E CD A(1,4) B(2,4)
F
G
H
I
J
cluster 2
α , β as the centre and K=2.
Step 3 again.
cente(rxi ,yj)
ij
PA,B,C,D,E(1.6,4.8)
new center
Q F,G,H,I,J(4.8,1.6)
The new centers of the two clusters are P(1.6,4.8) and Q(4.8,1.6)
3. Each cluster's center is recomputed as the average of the points in that cluster.
4. Iterate step 2 or more until the new center of cluster equals to the original center of cluster or less than a specified threshold,then clustering finished.