Referring to @duckvader, I tried to put this into practice, no guarantees! It is just an idea, I have not looked up anything for this.
I did not calculate averages to get the new centroids because with just 2 clusters and few points, it could be seen directly which one is best. I also did not consider the costs of swapping that @duckvader mentions, I assume that costs of swapping are simply the difference in costs when a cluster is changed, and that can be seen with a short glimpse anyway when we only have k=2. Costs of swapping are also not mentioned by @Bitwise, but only the total costs, as I am calculating here. Costs of swapping are probably a concept for larger samples where calculating the cost changes is easier than calculating the whole costs again
1) Assume one point from each cluster as a representative object of that cluster.
2) Find distance(Manhattan or Euclidean) of each object from these 2. You have been given these distances so skip this step.
for initial_kmedoids k=2 the clusters are already given with distances
iteration 1, given clusters:
- C1 X(1,2,3) = [1.91, 2.23, 2.15]
- C2 X(4,5,6) = [1.9, 2.66, 3.12]
3) select the points with minimum distance for each cluster wrt to
selected objects, i.e. create 2 new clusters with objects having least
distance to the above 2 points.
iteration 1, centroids:
- 1 to 2,3: [1.91, 2.23]
- 2 to 1,3: [1.91, 2.15] <-- min(avg(D)), X2 is centroid of C1
- 3 to 1,2: [2.23, 2.15]
- 4 to 5,6: [1.9, 2.66] <-- min(avg(D)), X4 is centroid of C2
- 5 to 4,6: [1.9, 3.12]
- 6 to 4,5: [2.66, 3.12]
duckvader 4 (though I do not take the average but just compare here):
4) take the average of the minimum distances for each point wrt to its
cluster representative object.
--> we only have two clusters, no avg needed to find the best. If we had many clusters, we needed the avg of the min distance approach in order to get the best clusters for the centroids quickly.
iteration 2, clusters:
Now find the new Cluster points of the new centroid that minimize D from the centroid.
Always just take the smaller C1 or C2 of the available Xn distance comparison.
- X2 to all others X(1 to 6): 1.91, 0, 2.15, 1.82, 2.41, 2.58
X4 to all others X(1 to 6): 3.14, 1.82, 3.12, 0, 1.9, 2.66
C1 (1,2,3,6) = [1.91, 2.15, 1.82, 2.58]
- C2 (4,5) = [1.82, 1.9]
5) Select 2 new objects as representative objects and repeat steps 2-4.
iteration 2, centroids:
- 1 to 2,3,6: [1.91, 2.23, 3.37]
- 2 to 1,3,6: [1.91, 2.15, 2.58] <-- min(avg(D)), X2 stays centroid of C1
- 3 to 1,2,6: [2.23, 2.15, 4.64]
- 6 to 1,2,3: [3.37, 2.58, 4.64]
- 4 to 5: [1.9] <-- mind(avg(D)), X4 stays centroid of C2 (X5 also possible)
duckvader 6-8 (we do not have swapping costs here, this is thus not needed):
6) calculate swapping cost. subtract old avg from new avg. New-old.
7) If swapping cost is negative then then new mediods are the new objects and go to step 5.
8) if cost is more than 0, discard points and select new points in step 5 keeping original points.
--> Again, we do not have many clusters and no swapping costs that might be needed then. With just 2 clusters, we can directly see which clustering minimizes the distances.
9) repeat until convergence.
iteration 3, clusters:
new clustering has the same stucture as iteration 2, iteration end
Result: C1 X(1,2,3,6) with X2 as centroid, C2 X(4,5) with X4 as centroid
I have checked this in a script, it gives me the same results.
from pyclustering.cluster.kmedoids import kmedoids
import numpy as np
dm = np.array(
dm = dm + np.transpose(dm)
k = 2
# choose medoid 2 and 4 in your C1 and C2 because min(D) in their cluster
initial_medoids = [1,3]
kmedoids_instance = kmedoids(dm, initial_medoids, data_type = 'distance_matrix')
# Run cluster analysis and obtain results.
clusters = kmedoids_instance.get_clusters()
centers = kmedoids_instance.get_medoids()
# [[1, 0, 2, 5], [3, 4]]
# [1, 3]