Introduction

Clustering is a pivotal technique in unsupervised learning, and among various clustering methods, k-means is one of the most widely utilized due to its simplicity and effectiveness. However, while implementing the k-means algorithm, practitioners sometimes encounter negative scores, particularly when using metrics that evaluate the quality of clustering results. Understanding why this happens and interpreting these negative scores correctly requires diving deeper into the mechanics of k-means and evaluation metrics.

Understanding K-Means Clustering

K-means clustering is a partitioning method that divides a dataset into K distinct, non-overlapping subsets (clusters). It follows a simple iterative process:

1. Initialize K centroids randomly.
2. Assign each data point to the nearest centroid.
3. Update the positions of the centroids to the mean of the assigned points.
4. Repeat steps 2 and 3 until convergence or a preset number of iterations is reached.

Technical Explanation

Mathematically, given a set of data points $X = {x_1, x_2, \ldots, x_n}$, k-means aims to minimize the following objective function:

$$J = \sum_{i=1}^{K} \sum_{x \in C_i} \| x - \mu_i \|^2$$

where $C_i$ is the set of points in cluster $i$, and $\mu_i$ is the centroid of cluster $i$. The algorithm tries to minimize the intra-cluster variance while implicitly assuming spherical clusters of similar sizes.

Evaluation Metrics

Evaluating the results of k-means or any clustering method typically involves internal or external validation techniques. Internal validation relies solely on the data rather than external labels. One commonly used internal metric that can yield negative scores is the Silhouette Score.

Silhouette Score

The Silhouette Score measures how similar an object is to its own cluster compared to other clusters. It's calculated using the formula:

$$s(i) = \frac{b(i) - a(i)}{\max(a(i), b(i))}$$

where: • $a(i)$ is the average distance between the $i^{th}$ data point and all other points in the same cluster. • $b(i)$ is the average distance between the $i^{th}$ data point and all points in the nearest cluster (the one where the average distance is smallest).

The score ranges from -1 to 1: • 1 indicates clusters are well separated. • 0 indicates overlapping clusters. • Negative values suggest points are assigned to the wrong cluster.

Why Negative Scores Occur

Negative Silhouette Scores can occur due to various reasons:

1. Incorrect Number of K: The selected number of clusters (K) might not align well with the intrinsic structure of the data. Too many or too few clusters can lead to poor separation.
2. Non-Spherical Shapes: K-means assumes spherical clusters. If the data has elongated or irregular cluster shapes, overlap among clusters can occur, leading to negative scores.
3. Noise and Outliers: Presence of noise and outliers can significantly affect the placement of centroids, resulting in improper clustering.
4. Cluster Size Disparity: K-means struggles with uneven cluster sizes. Smaller clusters might be swallowed by larger ones, distorting the score.

Example

Consider a dataset with two well-separated elongated clusters and one large spherical cluster. When applying k-means with an incorrect K value, the algorithm might improperly assign points from the elongated clusters, resulting in negative Silhouette Scores.