Introduction to Centroid-based Clustering

Study Notes

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.

Description

Explore the fundamentals of centroid-based clustering algorithms, focusing on their methodology and applications. Learn about popular techniques like K-means and K-medoids, and how these algorithms partition data points into clusters based on distance from centroids. This quiz will test your understanding of the key steps involved in the K-means clustering process.