How to perform K-medoids when having the distance matrix

Question

I've been trying for a long time to figure out how to perform (on paper)the K-medoids algorithm, however I'm not able to understand how to begin and iterate. for example:

I have the distance matrix between 6 points, the k,C1 and C2.

I'll be very happy if someone can show me please how to perform the K-medoids algorithm on this example? how to start and iterate?

Thanks

Answer 1

From the wikipedia page on k-medoids:

The most common realisation of k-medoid clustering is the Partitioning Around Medoids (PAM) algorithm and is as follows:

1. Initialize: randomly select k of the n data points as the medoids
2. Associate each data point to the closest medoid. ("closest" here is defined using any valid distance metric, most commonly Euclidean distance, Manhattan distance or Minkowski distance)
3. For each medoid $m$:
   1. For each non-medoid data point $o$:
      1. Swap $m$ and $o$ and compute the total cost of the configuration
4. Select the configuration with the lowest cost.
5. Repeat steps 2 to 4 until there is no change in the medoid.

There are also worked-out examples there.

Answer 2

Steps:
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.
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.
4) take the average of the minimum distances for each point wrt to its cluster representative object.
5) Select 2 new objects as representative objects and repeat steps 2-4.
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.
9) repeat until convergence.

Answer 3

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

duckvader1&2:

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]

duckvader 3:

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:

C1 (1,2,3):

• 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]

C2 (4,5,6):

• 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]

duckvader 5:

5) Select 2 new objects as representative objects and repeat steps 2-4.

iteration 2, centroids:

C1 (1,2,3,6):

• 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]

C2 (4,5): - 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.

duckvader 9:

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(
    [[0.,1.91,2.23,3.14,4.25,3.37],
    [0.,0.,2.15,1.82,2.41,2.58],
    [0.,0.,0.,3.12,3.83,4.64],
    [0.,0.,0.,0.,1.9,2.66],
    [0.,0.,0.,0.,0.,3.12],
    [0.,0.,0.,0.,0.,0.]])
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.
kmedoids_instance.process()
clusters = kmedoids_instance.get_clusters()
centers = kmedoids_instance.get_medoids()
print(clusters)
# [[1, 0, 2, 5], [3, 4]]
print(centers)
# [1, 3]

Answer 4

Would a naïve (but simple) approach be to just average the vectors (centroid) in the cluster and then find the vector in the cluster closes to this centroid?

import numpy as np
import faiss

# Using FAISS to build the vector index

vector_dimension = vectors.shape[1] # assume vectors
index = faiss.IndexFlatL2(vector_dimension)
faiss.normalize_L2(vectors)
index.add(vectors)

# find the mediod, closest to centroid?

centroid = np.array(vectors).mean(axis=0)
faiss.normalize_L2(centroid)
distances, indices = index.search(centroid, 2)

medoid = vectors[indices[0][0]]