14.2 K-Means Clustering

The K-Means Algorithm

K-Means is one of the most popular and straightforward clustering algorithms. It's a centroid-based algorithm that aims to partition \(n\) observations into \(k\) clusters in which each observation belongs to the cluster with the nearest mean (cluster centroid).

The algorithm works iteratively to assign each data point to one of \(k\) groups based on the features that are provided. The data points are clustered based on feature similarity.

The Algorithm Steps

The K-Means algorithm follows these steps:

1. Initialization: Randomly select \(k\) data points from the dataset to serve as the initial centroids.
2. Assignment Step: For each data point, calculate the distance to each of the \(k\) centroids. Assign the data point to the cluster corresponding to the nearest centroid. The most common distance metric used is the Euclidean distance.
3. Update Step: Recalculate the centroids of the newly formed clusters. The new centroid is the mean of all data points assigned to that cluster.
4. Repeat: Repeat the assignment and update steps until the centroids no longer move significantly, or until a maximum number of iterations is reached.

The objective function for K-Means is to minimize the within-cluster sum of squares (WCSS), also known as inertia:

\( \text{WCSS} = \sum_{i=1}^{k} \sum_{x \in C_i} \|x - \mu_i\|^2 \)

where \(\mu_i\) is the centroid of cluster \(C_i\).

Challenges with K-Means

• Choosing k: The number of clusters, \(k\), must be specified beforehand. The "Elbow Method" is a common technique used to find the optimal value of \(k\).
• Initialization Sensitivity: The initial placement of centroids can affect the final clustering result. Running the algorithm multiple times with different random initializations (known as k-means++) can help mitigate this.
• Cluster Shape: K-Means assumes that clusters are spherical and evenly sized, which may not be true for all datasets.