K Medoid

• In K-Means, the centroid is the arithmetic mean of the cluster. The mean is very sensitive to outliers.
• Not interpretable; centroid is the mean of cluster data points and may not be an actual data point, hence not representative.

⭐️Medoid is a specific data point from a dataset that acts as the ‘center’ or most representative member of its cluster.

👉It is defined as the object within a cluster whose average dissimilarity (distance) to all other members in that same cluster is the smallest.

💡Selects actual data points from the dataset as cluster representatives, called medoids (most centrally located).

👉a.k.a Partitioning Around Medoids(PAM).

Steps:

1. Initialization: Select ‘k’ data points from the dataset as the initial medoids using K-Means++ algorithm.
2. Assignment: Calculate the distance (e.g., Euclidean or Manhattan) from each non-medoid point to all medoids and assign each point to the cluster of its nearest medoid.
3. Update (Swap):

• For each cluster, swap current medoid with a non-medoid point from the same cluster.
• For each swap, calculate the total cost 💰(sum of distances from medoid).
• Pick the medoid with minimum cost 💰.

4. Repeat🔁: Repeat the assignment and update steps until (convergence), i.e, medoids no longer change or a maximum number of iterations is reached.

Note: Kind of brute-force algorithm, computationally expensive for large dataset.