K-means Clustering

The earlier chapters used parametric models for regression and classification. Most of them took the form $\mathbf w^T \phi(\mathbf x)$, and none was very complex, despite the sometimes heavy math. Clustering is a common problem in which the data have no labels $y$. Most of the treatment here is from Bishop, Section 9.1 (Bishop, n.d.); the equivalent section in Tan’s book is Section 7.2. Suppose we have a data set $D=\{ \mathbf x_1,...,\mathbf x_m\}$ consisting of $m$ observations of a random n-dimensional Euclidean variable $\mathbf x$. Our goal is to partition the data set into some number $K$ of clusters, where we shall suppose for the moment that the value of $K$ is given. Intuitively, we might think of a cluster as comprising a group of data points whose inter-point distances are small compared with the distances to points outside of the cluster. This is shown in the figure below. We can formalize this notion by first introducing a set of n-dimensional vectors $\mathbf \mu_k$ where $k =\{1,...,K\}$, in which $\mathbf \mu_k$ is a prototype associated with the kth cluster. We can think of the $\mathbf \mu_k$ as representing the centers of the clusters. Our goal is then to find both an assignment of data points to clusters and a set of prototypes. As before, we need a loss function. It is the sum of the squares of the distances of each data point to the prototype $\mathbf \mu_k$ of the cluster it is assigned to: $L = \sum_{i=1}^m \sum_{k=1}^K r_{ik} ||\mathbf x_i - \mathbf \mu_k||^2$ The variable $r_{ik}$ is a binary indicator. It adds the squared Euclidean distance between the point $\mathbf x_i$ and the candidate cluster prototype if the point is assigned to that cluster, and adds 0.0 to the loss if it is not. For two cluster prototypes, as in the example above, $r_k \in \{(1 0), (0 1)\}$. This is the one-hot encoding of the cluster: “cluster 1” is coded as $(1 0)$ and “cluster 2” as $(0 1)$. The k-means algorithm is iterative. After the $\mathbf \mu_k$ are initialized to random locations, each iteration includes two steps.

​

Assignment step

We go over each data point $\mathbf x_i$ and we assign it to the closest cluster center for this iteration. Iteration 1, Step 1: assignment of data points to cluster centers The assignment is $r_{ik} = \begin{cases}1, & \text{if } k = \arg \min_j ||\mathbf x_i - \mathbf \mu_j||^2\\ 0, & \text{otherwise. } \end{cases}$

​

Update step

In the second step we move each cluster center to the average of the data points assigned to that cluster: $\mathbf \mu_k = \frac{\sum_i r_{ik} \mathbf x_i}{\sum_i r_{ik}}$ Iteration 1, Step 2: moving the cluster centers to the mean of the data points assigned to each cluster The figures below show the second iteration. Iteration 2, Step 1: assignment of data points to cluster centers Iteration 2, Step 2: moving the cluster centers to the mean of the data points assigned to each cluster The loss drops quickly and levels off after the third iteration: The loss after each assignment step (blue circles) and each update step (red circles), as k-means converges Each of the two steps can only lower the loss $L$ or leave it unchanged, so the algorithm always converges. The minimum it reaches can be a local one, and which minimum it reaches depends on the initial prototypes.

​

Outliers

The loss uses the squared Euclidean distance. A single point far from every cluster is still assigned to one of them, and because its squared distance is large, it pulls that cluster’s mean toward it. Bishop notes that this makes the cluster means nonrobust to outliers (Section 9.1). The next section, the EM algorithm, replaces the hard indicator $r_{ik}$ with a probability that point $\mathbf x_i$ belongs to cluster $k$, and shows that k-means is a limiting case of EM for a mixture of Gaussians. The robust estimation chapter then returns to the problem of points that fit no part of the model. Key references: (Bishop, n.d.)

​

References

• Bishop (n.d.). Pattern Recognition and Machine Learning.

---