K Means Clustering Algorithm with R: A Beginner‘s Guide

Clustering is a fundamental task in unsupervised machine learning that aims to partition a set of data points into groups or "clusters" such that points within the same cluster are more similar to each other than points in different clusters. The K-means algorithm is one of the oldest and most widely used methods for clustering, known for its simplicity and efficiency.

In this guide, we‘ll dive deep into the K-means algorithm from a machine learning expert‘s perspective. We‘ll explore the mathematical formulation of K-means, techniques for selecting the number of clusters, best practices for implementation, and advanced topics that arise in real-world applications.

The K-Means Algorithm

The goal of K-means is to partition a set of $n$ data points ${x_1, …, x_n}$ into $k$ clusters ${C_1, …, C_k}$ so as to minimize the within-cluster sum of squares (WCSS):

$$\min_{C_1, …, Ck} \sum{i=1}^k \sum_{x \in C_i} ||x – \mu_i||^2$$

where $\mu_i$ is the centroid (mean) of cluster $C_i$. In other words, K-means aims to find clusters such that points within each cluster are as close as possible to the cluster centroid.

The standard algorithm for solving this optimization problem is an iterative refinement procedure known as Lloyd‘s algorithm:

1. Initialize cluster centroids ${\mu_1, …, \mu_k}$, either randomly or using a heuristic like K-means++
2. Repeat until convergence:
   • Assignment step: Assign each point to the nearest centroid
   • Update step: Recompute centroids as the mean of points in each cluster

This algorithm is guaranteed to converge to a local optimum, but not necessarily the global optimum. The result can be sensitive to the initial centroid positions, so it‘s common to run K-means multiple times with different initializations and choose the clustering with the lowest WCSS.

Choosing the Number of Clusters

One of the key hyperparameters in K-means is $k$, the number of clusters to form. The optimal $k$ depends on the data and the goals of the analysis, and is not always obvious.

A common heuristic is the "elbow method", which plots the WCSS as a function of $k$ and looks for an elbow point where the decrease in WCSS begins to level off. However, this method can be ambiguous if there is no clear elbow.

More principled methods for selecting $k$ include:

• Gap statistic: Compares the WCSS to the expected WCSS under a null reference distribution (e.g. uniform points) and chooses the smallest $k$ such that the observed WCSS falls below the reference curve (Tibshirani et al., 2001).

• Silhouette method: Measures how well each point fits into its assigned cluster versus the next nearest cluster. Calculates the average silhouette width for different values of $k$ and chooses the $k$ that maximizes this metric (Kaufman & Rousseeuw, 1990).

• Information criteria: Treats selecting $k$ as a model selection problem and chooses the $k$ that minimizes criteria like AIC or BIC, which balance model fit with complexity.

There is no universally optimal method for selecting $k$, and it‘s often informative to compare results from multiple methods. Domain knowledge can also guide the choice of $k$ based on the expected or desired number of clusters.

Implementing K-Means in R

To demonstrate K-means in action, let‘s walk through a case study using the wine recognition dataset from the UCI Machine Learning Repository. This dataset contains 13 chemical measurements on 178 Italian wines grown in the same region but derived from three different cultivars.

First, we‘ll load the data and do some basic exploratory analysis:

wine <- read.table("wine.data", sep=",")

# Check dimensions
dim(wine)
#> [1] 178  14

# Look at first few rows
head(wine)
#>   V1  V2   V3   V4   V5   V6   V7   V8   V9  V10  V11  V12  V13 V14
#> 1  1 14.23 1.71 2.43 15.6 127 2.80 3.06 0.28 2.29 5.64 1.04 3.92 1065
#> 2  1 13.20 1.78 2.14 11.2 100 2.65 2.76 0.26 1.28 4.38 1.05 3.40 1050
#> 3  1 13.16 2.36 2.67 18.6 101 2.80 3.24 0.30 2.81 5.68 1.03 3.17 1185
#> 4  1 14.37 1.95 2.50 16.8 113 3.85 3.49 0.24 2.18 7.80 0.86 3.45 1480
#> 5  1 13.24 2.59 2.87 21.0 118 2.80 2.69 0.39 1.82 4.32 1.04 2.93  735
#> 6  1 14.20 1.76 2.45 15.2 112 3.27 3.39 0.34 1.97 6.75 1.05 2.85 1450

# Summary statistics
summary(wine)
#>        V1          V2             V3             V4             V5       
#>  Min.   :1   Min.   :11.03   Min.   :0.74   Min.   :1.36   Min.   : 10.60  
#>  1st Qu.:1   1st Qu.:12.36   1st Qu.:1.60   1st Qu.:2.21   1st Qu.: 17.20  
#>  Median :2   Median :13.05   Median :1.87   Median :2.36   Median : 19.50  
#>  Mean   :2   Mean   :13.00   Mean   :2.34   Mean   :2.37   Mean   : 19.49  
#>  3rd Qu.:3   3rd Qu.:13.68   3rd Qu.:3.08   3rd Qu.:2.56   3rd Qu.: 21.50  
#>  Max.   :3   Max.   :14.83   Max.   :5.80   Max.   :3.23   Max.   :289.00  
#>  ...

The dataset has 178 rows and 14 columns, with the first column indicating the wine cultivar (1, 2, or 3). The other columns contain various chemical measurements.

Before applying K-means, we‘ll standardize the features to have zero mean and unit variance, since K-means is sensitive to scaling. We‘ll also exclude the cultivar label.

wine_std <- scale(wine[,-1])

Now let‘s use the gap statistic to estimate the optimal number of clusters:

library(cluster)

gap_stat <- clusGap(wine_std, FUN = kmeans, nstart = 25, K.max = 10, B = 50)
print(gap_stat, method = "Tibs2001SEmax")
#> Clustering Gap statistic ["clusGap"] from call:
#> clusGap(x = wine_std, FUNcluster = kmeans, K.max = 10, B = 50,      nstart = 25)
#> B=50 simulated reference sets, k = 1..10; spaceH0="scaledPCA"
#>  -->  according to the 1st choice method "Tibs2001SEmax", the optimal number of clusters 
#> is 3

The gap statistic selects $k=3$ clusters, which aligns with the true number of cultivars. Let‘s run K-means with $k=3$ and look at the cluster sizes:

set.seed(123)
km <- kmeans(wine_std, centers = 3, nstart = 25)
km$size
#> [1] 62 65 51

The algorithm finds three clusters with roughly balanced sizes. We can evaluate the quality of the clustering using metrics like the average silhouette width:

library(cluster)
sil_width <- silhouette(km$cluster, dist(wine_std))
mean(sil_width[,3])
#> [1] 0.7224416

The average silhouette width is 0.72, indicating that samples are generally well matched to their assigned clusters.

Finally, let‘s visualize the clustering in the space of the first two principal components:

library(ggplot2)
pca <- prcomp(wine_std)
df <- data.frame(pca$x[,1:2], cluster = factor(km$cluster))

ggplot(df, aes(x = PC1, y = PC2, color = cluster)) +
  geom_point(size = 2) +
  labs(x = "PC1", y = "PC2", title = "K-Means Clustering of Wine Data (k = 3)")

The plot shows that the three clusters are well separated in PC space, especially along the first component. This suggests that the chemical measurements contain strong signal for distinguishing the three cultivars.

Of course, this is just a simple example – in practice, K-means is often applied to much larger and higher-dimensional datasets. The time complexity of Lloyd‘s algorithm is $O(n k d i)$ for $n$ points, $k$ clusters, $d$ features, and $i$ iterations. This scales linearly with the number of points and features, making K-means relatively efficient even for big data.

Advanced Topics and Extensions

While the standard K-means algorithm is simple and effective, there are many ways it can be extended and adapted to different problem settings. Some key considerations in practice include:

• Initialization: The initial centroid positions can have a major impact on the final clustering. More sophisticated initialization methods like K-means++ (Arthur & Vassilvitskii, 2007) can improve speed and consistency by spreading out the initial centroids.

• Distance metric: K-means is typically used with Euclidean distance, but other metrics may be more appropriate for specific data types (e.g. cosine distance for text). The choice of distance metric can have a big effect on the clustering results.

• High-dimensional data: In high dimensions, Euclidean distance can become less informative due to the "curse of dimensionality". Techniques like subspace clustering (Agrawal et al., 2005) or projection pursuit (Friedman & Tukey, 1974) can help identify clusters that only exist in particular subspaces of the feature space.

• Categorical data: K-means assumes continuous features, but many datasets contain categorical or mixed data types. Variants like K-modes (Huang, 1998) or K-prototypes (Huang, 1997) modify the centroid representation and distance metric to handle categorical features.

• Streaming data: For massive or streaming datasets that don‘t fit in memory, online variants of K-means (e.g. Sculley, 2010) can incrementally update clusters as new data arrives, using a subset or "mini-batch" of points at each step.

Conclusion

K-means is a powerful yet intuitive algorithm for partitional clustering that has stood the test of time in machine learning and data mining. While easy to implement, doing K-means well in practice requires careful consideration of issues like initialization, feature scaling, and model selection.

By understanding the mathematical formulation of K-means and the practical tradeoffs involved in its use, data scientists can apply this algorithm effectively to uncover meaningful groups and structure in all sorts of real-world datasets. With its simplicity and scalability, K-means will undoubtedly remain a go-to tool in the unsupervised learning toolkit for years to come.

References

• Tibshirani, R., Walther, G., & Hastie, T. (2001). Estimating the number of clusters in a data set via the gap statistic. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 63(2), 411-423.

• Kaufman, L. and Rousseeuw, P.J. (1990), Finding Groups in Data: An Introduction to Cluster Analysis. Wiley, New York.

• Arthur, D., & Vassilvitskii, S. (2007). K-means++: The advantages of careful seeding. Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, 1027-1035.

• Agrawal, R., Gehrke, J., Gunopulos, D., & Raghavan, P. (2005). Automatic subspace clustering of high dimensional data. Data Mining and Knowledge Discovery, 11(1), 5-33.

• Friedman, J. H., & Tukey, J. W. (1974). A projection pursuit algorithm for exploratory data analysis. IEEE Transactions on Computers, C-23(9), 881-890.

• Huang, Z. (1997). A fast clustering algorithm to cluster very large categorical data sets in data mining. Research Issues on Data Mining and Knowledge Discovery, 1-8.

• Huang, Z. (1998). Extensions to the k-means algorithm for clustering large data sets with categorical values. Data mining and knowledge discovery, 2(3), 283-304.

• Sculley, D. (2010). Web-scale k-means clustering. Proceedings of the 19th International Conference on World Wide Web, 1177-1178.