A Comprehensive Guide to Centroid-Based Clustering with Python Examples

What is Clustering?

Clustering is a type of unsupervised machine learning that involves grouping data points together based on their inherent similarity or closeness. The goal is to partition a dataset such that data points within the same cluster are more similar to each other than to points in other clusters. Clustering is considered unsupervised learning because the input data is unlabeled – the algorithm has to discover the underlying structure on its own without any pre-defined class labels to learn from.

Clustering has a wide variety of real-world applications across many different domains. For example:

• Customer segmentation in marketing to group customers with similar behaviors or preferences
• Anomaly detection in cybersecurity to identify unusual network traffic or user activity
• Medical imaging analysis to distinguish different types of cells, tissues, or tumors
• Document clustering to automatically organize large collections of text by topic
• Social network analysis to find communities of densely connected individuals

There are many different types of clustering algorithms that take different approaches. In this article, we‘ll focus specifically on centroid-based clustering methods.

Centroid-Based Clustering Methods

Centroid-based clustering refers to a family of algorithms that represent each cluster by a single mean vector called its centroid. The centroid can be thought of as the "center of mass" or average position of all the points in the cluster. The goal is to partition the data such that the total squared distance between points and their closest centroid is minimized. This is an optimization problem that is challenging to solve exactly, so approximation methods are used.

The two most well-known centroid-based clustering algorithms are:

1. K-means
2. K-medoids (also known as Partitioning Around Medoids or PAM)

Let‘s examine each of these in more detail.

K-Means Clustering

K-means is perhaps the most widely used and well-known clustering algorithm. It‘s fast, simple, and easy to understand. The key steps are:

1. Specify the desired number of clusters k
2. Initialize k centroids (e.g. by choosing k data points at random)
3. Repeat until convergence:
   • Assign each point to the cluster whose centroid it is closest to
   • Recompute the centroid of each cluster as the mean of its assigned points

The algorithm typically converges when the cluster assignments no longer change between iterations. Here‘s what this looks like in Python using the scikit-learn library:

from sklearn.cluster import KMeans

# Assume X is our input data matrix 
kmeans = KMeans(n_clusters=3, random_state=0).fit(X)

# Get the cluster labels for each point
labels = kmeans.labels_

# Get the final centroid locations
centroids = kmeans.cluster_centers_

One issue with k-means is that it‘s sensitive to the initial placement of the centroids. A bad random initialization can lead to poor results. One workaround is to run the algorithm multiple times with different random initializations and keep the best result. Another approach is to use a smarter initialization strategy like k-means++, which spreads out the initial centroids to avoid placing them too close together. This is easy to enable in scikit-learn:

kmeans = KMeans(n_clusters=3, init=‘k-means++‘, random_state=0).fit(X)  

K-Medoids Clustering

K-medoids is a variant of k-means that is more robust to noise and outliers. Instead of using the mean point as the cluster center, k-medoids chooses an actual data point (called the medoid) to represent each cluster. The medoid is defined as the point that minimizes the total dissimilarity to all other points in the cluster.

The steps are very similar to k-means, but in the update step, rather than taking the mean, we find the point that minimizes the total dissimilarity:

1. Specify the desired number of clusters k
2. Initialize k medoids (e.g. by choosing k data points at random)
3. Repeat until convergence:
   • Assign each point to the cluster whose medoid it is closest to
   • For each cluster, find the point that minimizes total dissimilarity within the cluster and make it the new medoid

Here‘s an example of using k-medoids clustering with the pyclustering library in Python:

from pyclustering.cluster.kmedoids import kmedoids

# Assume X is a list of points 
initial_medoids = [1, 10, 50]  # Indices of initial medoids
kmedoids_instance = kmedoids(X, initial_medoids)
kmedoids_instance.process()

clusters = kmedoids_instance.get_clusters()
medoids = kmedoids_instance.get_medoids()

K-medoids can be preferable to k-means when the data contains a significant amount of noise or outliers, since a medoid is less influenced by extreme values than a mean. It‘s also useful when the centroid is not a meaningful or interpretable quantity, e.g. when clustering text documents, where taking the "average" of a set of documents doesn‘t have a clear meaning.

Determining the Optimal Number of Clusters

One challenge with centroid-based clustering is that you need to specify the number of clusters k in advance. But in most real-world applications, we don‘t know the "true" number of clusters in the data. So how can we choose k?

There are a few common heuristics:

• Elbow method: Plot the clustering objective (e.g. total squared distance from centroids) versus k. Choose the k where the objective starts to flatten out and form an "elbow".
• Silhouette analysis: Measures how well each point fits into its assigned cluster versus the next closest cluster. Maximize the average silhouette coefficient.
• Gap statistic: Compares the clustering objective to its expected value under a reference null distribution. Maximize the gap between the observed and expected objectives.

Here‘s an example of the elbow method in Python:

from sklearn.cluster import KMeans

sse = []
for k in range(1, 11):
    kmeans = KMeans(n_clusters=k, init=‘k-means++‘, random_state=0)
    kmeans.fit(X)
    sse.append(kmeans.inertia_)

plt.plot(range(1, 11), sse)
plt.title(‘Elbow Method‘)
plt.xlabel(‘Number of clusters‘)
plt.ylabel(‘SSE‘)
plt.show()

This plots the sum of squared errors (SSE) for k ranging from 1 to 10. The point where the SSE starts to level off (the "elbow") indicates a good choice for k.

Advantages and Limitations

Centroid-based clustering methods like k-means and k-medoids have several advantages:

• Fast and scalable to large datasets
• Easy to implement and interpret results
• Guaranteed to converge to a local optimum
• Tend to produce clusters of similar size and spherical shape

However, they also have some key limitations:

• Require specifying k in advance
• Sensitive to initialization and may converge to suboptimal solutions
• Assume clusters are spherical with equal variance
• Struggle with clusters of varying sizes and densities
• Not suitable for discovering clusters with non-convex shapes

So while centroid-based methods are a good choice for many applications, it‘s important to understand their strengths and weaknesses. Alternative clustering approaches like density-based clustering or hierarchical clustering may be preferable in some situations.

Tips and Best Practices

Here are a few tips to get the best results from centroid-based clustering:

• Scale your data so that all features have similar ranges. K-means and k-medoids rely on distance calculations that can be thrown off by features on very different scales.
• Try multiple initializations to avoid getting stuck in suboptimal local minima. Set different random seeds and keep the best result.
• Visualize the clustering results if possible, especially in lower dimensions. Scatter plots with color-coded clusters can help assess the quality of the clustering.
• Experiment with different values of k and use a quantitative method like the elbow method or silhouette analysis to justify your choice.
• Remove significant outliers before clustering, as they can pull centroids away from the main clusters and distort the results.
• Be careful not to overinterpret the results, especially if the data does not have a clear clustered structure. Not all datasets contain meaningful clusters!

Conclusion

Centroid-based clustering is a powerful family of unsupervised learning methods for discovering groups of similar data points. K-means and k-medoids are two popular algorithms that are fast, simple, and widely applicable. However, they have some key assumptions and limitations to be aware of.

When used properly on suitable datasets with careful initialization, interpretation, and validation, centroid-based clustering can uncover valuable insights in domains ranging from customer segmentation to document clustering to anomaly detection. The techniques covered in this article should give you a solid foundation for applying centroid-based clustering to your own machine learning projects.

I hope you found this guide comprehensive and helpful for understanding centroid-based clustering! Let me know if you have any other questions.