K-Means Clustering

What Is K-Means Clustering?

K-means clustering is an unsupervised machine learning algorithm for clustering.

In supervised learning, the data has input features and labels. Here, the data isn't labeled. We need to group similar data together, so that the data reveals its own structure.

Before clustering, we just have raw data without any labels. After clustering, the data is organized into groups of similar points.

K-means is a hard clustering algorithm:

• In hard clustering, each data point belongs to only one cluster.
• In soft clustering, one data point can belong to multiple clusters with different probabilities.

Clusters in One and Two Dimensions

Suppose we have the ages of a few people, plotted in one dimension: 18, 19, 20, 27, 31, 38, and 40.

If $K$, the number of clusters, is 3, we can see three natural groups: 18 to 20, 27 and 31, and 38 and 40. If $K$ is 4, we get four clusters instead.

Now suppose we have two features, age and weight, with age on the x-axis and weight on the y-axis. Just by looking at the plot, we can see which points form a cluster. If we want more or fewer clusters, we can group the points differently.

But how can a machine find these clusters?

How K-Means Works

K-means starts by placing $K$ cluster centers, called centroids, at random positions. Then it alternates between two steps.

One-Dimensional Example

Using the age data with $K = 3$, we randomly place three centroids.

1. Assign the points. For each point, we find the nearest centroid and assign the point to that cluster.
2. Move the centroids. After the assignment, the centroids are no longer at the center of their points, so we recalculate each centroid as the mean position of its cluster.

We repeat these steps again and again to get the correct clusters.

Two-Dimensional Example

The same process works in two dimensions, again with $K = 3$. We randomly place three centroids, then assign each data point to its nearest centroid.

After this first step, the clustering isn't finished. Some points are assigned to a cluster they clearly don't belong to, because the centroids started in random positions.

So we move each centroid to the center of its points, and then assign the points again.

The points have moved between clusters, so the centroids are off-center again, and we recalculate them.

We repeat this process until the clusters stabilize.

Distance Metric

At each step, we calculate the distance from a data point to the centroid of every cluster. K-means usually uses Euclidean distance, which measures how close a point is to a centroid.

If each point has $d$ features, the distance between a point $x$ and a centroid $c$ is:

Euclidean distance suits k-means for several reasons:

• The centroid is the mean of the points, which works naturally with Euclidean geometry.
• It produces spherical clusters.
• It is fast and computationally efficient.
• It is differentiable, which enables optimization.

The Algorithm

Here are the steps of k-means clustering:

1. Choose $K$, the number of clusters.
2. Initialize the centroids.
3. Assign each point to its closest centroid.
4. Recalculate the centroids.
5. Repeat steps 3 and 4 until convergence.

Let's write this more formally.

We have a dataset of $n$ points, $x_1, x_2, \dots, x_n$, with no labels. We choose $K$, which gives us clusters $C_1, C_2, \dots, C_K$. These clusters start empty. We initialize the centroids $\mu_1, \mu_2, \dots, \mu_K$ randomly.

Until convergence, we repeat the following.

Assignment. For each point $x_i$, we find the closest centroid:

So $f(x_i)$ is the closest cluster to $x_i$, and $\mu_{f(x_i)}$ is the centroid closest to $x_i$.

Update. For each cluster $j$, we collect all the points whose closest cluster is $j$:

We then recompute the centroid by adding up the points in the cluster and dividing by the number of points in it, $|C_j|$:

What K-Means Optimizes

In practice, k-means minimizes the squared Euclidean distance, known as the within-cluster sum of squares (WCSS). This is also called the sum of squared errors (SSE).

For each cluster, we take the squared distance from each point to the cluster's centroid and add them up. Then we add up these sums over all the clusters:

Here, $x$ is a data point in cluster $k$, and $\mu_k$ is the centroid of that cluster.

For example, if the WCSS is 89.5 for cluster 1 and 115.6 for cluster 2, the total WCSS is 205.1.

A lower WCSS means tighter clusters. When we minimize it, the data points within each cluster end up closer to their centroid.

When to Stop

K-means keeps assigning points and recalculating centroids, so when should it stop? Machine learning libraries stop when any of these happens:

• The centroids stop changing position.
• The cluster assignments stabilize.
• The improvement in WCSS falls below some tolerance $\epsilon$.
• A predefined maximum number of iterations is reached, such as 100 or 200.

Choosing K With the Elbow Method

The well-known way to choose the number of clusters is the elbow method:

1. Run k-means with different values of $K$.
2. Plot the WCSS for each one, with the number of clusters on the x-axis and the WCSS on the y-axis.
3. Look for the bend in the curve, called the elbow point. The value of $K$ at that point is the optimal $K$.

For example, if the curve bends at 3, we would choose $K = 3$.

Here is why it works. With just one cluster, all the points are assigned to it, so the squared distances and the WCSS are at their maximum.

As we increase the number of clusters, the WCSS drops rapidly until the elbow point. After that, it changes much more slowly, so adding more clusters doesn't help much.

Advantages

• It is simple and fast.
• It works well on large datasets.
• It is easy to implement and understand.

Limitations

• We need to choose K. This is an extra overhead.
• It is sensitive to outliers. A few stray points can stop the clustering from working properly.
• It works based on spherical clusters. The clusters are centered around the centroids, so k-means might not work properly if the clusters aren't spherical.
• Random initialization may affect the results. Different starting centroids can give different clusters.

Applications

Despite these limitations, k-means has many real-world applications:

• Customer segmentation in marketing
• Image compression, where similar pixels are clustered together
• Anomaly detection
• Document clustering

Summary

The key ideas are:

• K-means is an unsupervised, hard clustering algorithm that groups unlabeled data into $K$ clusters.
• It alternates between assigning points to the nearest centroid and recalculating the centroids.
• It usually uses Euclidean distance, and it minimizes the WCSS.
• It stops when the centroids or assignments stabilize, the improvement in WCSS is small, or the iteration limit is reached.
• The elbow method helps us choose $K$.