Introduction to Centroid-based Clustering

Introduction to Centroid-based Clustering

• Centroid-based clustering algorithms partition data points into clusters based on their proximity to the centroid (mean) of each cluster.
• These methods iteratively refine cluster assignments and centroids until convergence or a predefined stopping criterion is met.
• Popular examples include K-means and K-medoids algorithms.

K-means Clustering

• Aims to partition n observations into k clusters, with each observation assigned to the cluster with the nearest mean (centroid).
• The algorithm iteratively updates cluster assignments and centroids using Euclidean distance.
• Key Steps:
  • Randomly initialize k centroids.
  • Assign each data point to the cluster with the nearest centroid.
  • Recalculate the centroids of each cluster based on the mean of the data points assigned to that cluster.
  • Repeat steps 2 and 3 until centroids no longer change significantly (convergence).
• Strengths:
  • Relatively simple implementation and computationally efficient.
  • Effective for large datasets.
• Weaknesses:
  • Sensitive to initial centroid placement. Different initializations can lead to different clusterings.
  • Assumes spherical clusters (data points form roughly spherical clusters) and equal variance in clusters.
  • Sensitive to outliers. Noise and outlier data points can significantly impact results.
  • The number of clusters (k) needs to be specified beforehand.

K-medoids Clustering (PAM)

• A variation of k-means using medoids (data points within a cluster) instead of means as cluster representatives.
• The medoid is the data point within a cluster with the smallest sum of distances to all other points in that cluster.
• Key difference from K-means:
  • Uses the medoid as the cluster representative, making it less sensitive to outliers than k-means.
• Strengths:
  • More robust to outliers compared to k-means.
  • More robust to data without a typical Gaussian-like structure, which k-means assumes.
• Weaknesses:
  • Computationally more expensive than k-means for large datasets and large k.
  • Still requires specifying the number of clusters (k).

Choosing the optimal number of clusters (k)

• Determining an optimal k is vital for effective clustering.
• Methods used include:
  • Elbow method: Plot within-cluster sum of squares (WCSS) against the number of clusters. The "elbow" in the plot often suggests a good k value.
  • Silhouette analysis: Measures similarity of a data point to its own cluster versus other clusters. A high average silhouette score indicates good clustering.
  • Gap statistic: Compares within-cluster sum of squares to a reference distribution. A significant gap suggests a good k in the graph.
• These methods should be used in conjunction with domain knowledge and the specific problem.

Applications of Centroid-based Clustering

• Customer segmentation in marketing.
• Image segmentation in computer vision.
• Anomaly detection.
• Document clustering.
• Gene expression analysis.
• Social network analysis.