Step 2 K-medoids

figure 1.3 – clusters after step 2

select 1 of nonmedoids o′

let assume o′ = (7,3), i.e. x7.

so medoids c1(3,4) , o′(7,3)

if c1 , o′ new medoids, calculate total cost involved

by using formula in step 1

figure 2. k-medoids versus k-means. figs 2.1a-2.1f present typical example of k-means convergence local minimum. result of k-means clustering contradicts obvious cluster structure of data set. in example, k-medoids algorithm (figs 2.2a-2.2h) same initial position of medoids (fig. 2.2a) converges obvious cluster structure. small circles data points, 4 ray stars centroids (means), 9 ray stars medoids.

total cost




=
3
+
4
+
4
+
2
+
2
+
1
+
3
+
3






=
22






{\displaystyle {\begin{aligned}{\mbox{total cost}}&=3+4+4+2+2+1+3+3\\&=22\\\end{aligned}}}

so cost of swapping medoid c2 o′ is

s



=

current total cost

−

past total cost







=
22
−
20






=
2
>
0.






{\displaystyle {\begin{aligned}s&={\mbox{current total cost}}-{\mbox{past total cost}}\\&=22-20\\&=2>0.\end{aligned}}}

so moving o′ bad idea, previous choice good. try other nonmedoids , found our first choice best. configuration not change , algorithm terminates here (i.e. there no change in medoids).

it may happen data points may shift 1 cluster cluster depending upon closeness medoid.

in standard situations, k-medoids demonstrate better performance k-means. example presented in fig. 2.

the time-consuming part of k-medoids algorithm calculation of distances between objects. if quadratic preprocessing , storage applicable, distances matrix can precomputed achieve consequent speed-up. see example, authors introduce heuristic choose initial k medoids.