(sec:ml:cluster:k-means)= # K-Means Clustering An initial version of the k-means algorithm was originally developed by Lloyd in 1957 but was published for the first time in 1982 {cite}`lloyd1982least`. Given a set of $n$ data points in $\RR^m$, the objective is to select $k$ centroids so as to minimize the sum of squared distances between each point and its closest centroid. In general the problem is NP-hard but a local search method to this problem as described in {prf:ref}`alg:ml:cluster:k_means` is generally quite successful in finding reasonable solutions. See {cite}`macqueen1967some, duda2012pattern, hartigan1975clustering` for a detailed treatment of the algorithm. ## Basic Algorithm K-means clustering algorithm is a hard clustering algorithm as it assigns each data point to exactly one cluster. ````{prf:algorithm} Basic k-means clustering algorithm :label: alg:ml:cluster:k_means 1. Select $k$ points as initial centroids. 1. Repeat 1. Segmentation: Form $k$ clusters by assigning all points to the nearest centroid. 2. Estimation: Recompute the centroid for each cluster. 5. Until the segmentation has stopped improving. ```` 1. The input to an algorithm is an unlabeled dataset $$ \bX = \{ \bx_1, \bx_2, \dots, \bx_n \} $$ where each data point belongs to the ambient feature space $\RR^m$. 1. Our goal is to partition the dataset into $k$ different clusters. 1. The clustering is denoted by $$ \CCC = \{C_1, \dots, C_k \} $$ where $C_j$ is the list of indices of data points belonging to the $j$-th cluster. 1. The clustering can be conveniently represented in the form of a label array $L$ consisting of $n$ entries each of which can take a value from $\{ 1, \dots, k \}$. 1. In other words, if $L[i] = j$, then the data point $\bx_i$ belongs to the $j$-th cluster ($i \in C_j$). 1. Each cluster $C_j$ is represented by a centroid (or a mean vector) $\mu_j$. 1. The algorithm consists of two major steps: 1. Segmentation 1. Estimation 1. The goal of segmentation step is to partition the data points into clusters according to the nearest cluster centroids. 1. The goal of estimation step is to compute the new centroid for each cluster based on the current clustering. $$ \mu_j = \frac{1}{n} \sum_{i \in C_j} \bx_i. $$ 1. We start with an initial set of centroids for each cluster. 1. One way to pick the initial centroids is to pick $k$ points randomly from the dataset. 1. In each iteration, we segment the data points into individual clusters by assigning a data point to the cluster corresponding to the nearest centroid. 1. Then, we estimate the new centroid for each cluster. 1. We return a labels array $L$ which maps each point to corresponding cluster. We note that the basic structure of the k-means is not really an algorithm. It is more like a template of the algorithm. For a concrete implementation of the k-means algorithm, there are many aspects that need to be carefully selected. - Initialization of the centroids - Number of clusters - Choice of the distance metric - Criterion for evaluation of the quality of the clustering - Stopping criterion ### Example ````{prf:example} A k-means example :label: ex-ml-cl-kmeans-1 We show a simple simulation of k-means algorithm. - The data consists of randomly generated points organized in 4 clusters. - The algorithm is seeded with random points at the beginning. - After each iteration, the centroids are moved to a new location based on the current members of the cluster. - The animation below shows how the centroids are moving and cluster memberships are changing. ```{figure} images/kmeans/kmeans.gif This animation shows how the centroids move from one iteration to the next. The centroids have been initialized randomly in the first iteration. ``` The figure below shows the clusters and centroids of all the six iterations in a grid. You can open this figure in a different tab to see its enlarged version. ```{figure} images/kmeans/grid.png ``` We have 4 centroids randomly initialized at iteration 1. Let us call them as - A near $(-5, -8)$ (centroid of yellow cluster) - B near $(1.5, -1)$ (centroid of blue cluster) - C near $(6, 2.5)$ (centroid of the green cluster) - D near $(8.5, 6)$ (centroid of the purple cluster) Look at centroid A over time - It starts from the location $(-5, -8)$. - More than half of the points from the eventual blue cluster are still belonging to the yellow cluster in the first iteration. - As the centroid starts moving towards its eventual location near $(-9, -8.5)$, extra points from the yellow cluster are dropped. Next look at the journey of centroid B. - In the beginning it contains about 70% points of the cluster around origin and only about 20% points of the cluster around $(1.5, -7.5)$. - But it is enough to start pulling the centroid downward. - As the centroid C starts moving left & down, the points around origin start becoming green. - Since centroid A is also moving left, the points around $(1.5, -7.5)$ start turning blue. Centroid D doesn't really move much. - Initially it is in competition with centroid C for some of its points around its boundary. - However as C starts moving to its final destination, all the points around D turn purple. - Since not many points had to change cluster membership here, hence their centroid location didn't shift much over these iterations. We also note that after iteration 5, there is no further change in cluster memberships. Hence the centroids stop moving. ```` ### Stopping Criterion As we noticed that in the previous example that centroids converge fast during the initial iterations and then they start moving very slowly. Once the segmentation stops changing, then the centroids will also stop moving. When the cluster boundaries are not clear, it is often good enough to stop the algorithm when relatively very few points are changing clusters. ### Evaluation ````{div} A simple measure for the evaluation of the k-means algorithm is the within-cluster-scatter given by $$ S = \sum_{j=1}^k \sum_{i \in C_j} (\bx_i - \mu_j)^T (\bx_i - \mu_j) = \sum_{j=1}^k \sum_{i \in C_j} \| \bx_i - \mu_j \|_2^2. $$ ```` As can be seen from the formula, this is essentially the sum of squared errors w.r.t. the corresponding cluster centroids. ### Convergence It can be shown that the scatter is monotonically decreasing over the k-means iterations. 1. One can easily see that there are only at most $k^n$ possible clusterings. 1. Each partition has a different value of scatter. 1. Since the scatter is monotonically decreasing, hence no configuration is repeated twice. 1. Since the number of possible clusterings is finite, hence the algorithm must terminate eventually. ### Number of Clusters The algorithm requires that the user provide the desired number of clusters $k$ as an input to the algorithm. It doesn't discover the the number of clusters automatically. We can also see that one straight-forward way to decrease the within cluster scatter is to increase the number of clusters. In fact, when $k=n$, then the optimal within cluster scanner will be $0$. However, a lower scatter may provide a clustering which will not be very useful. This begs the question how do we select the number of clusters? Here are a few choices: - Run the algorithm on the data with different values of $k$ and then choose a clustering by inspecting the results. - Use another clustering method like EM. - Use some domain specific prior knowledge to decide the number of clusters. ### Initialization There are a few options for selection of initial centroids: 1. Randomly chosen data points from the data set. 1. Random points in the feature space $\RR^m$. 1. Create a random partition of $\bX$ into $k$ clusters and take the centroid of each partition. 1. Identify regions of space which are dense (in terms of number of data points per unit volume) and then select points from those regions as centroids. 1. Uniformly spaced points in the feature space. Later, we will discuss a specific algorithm called k-means++ which carefully selects the initial centroids. k-means algorithm doesn't provide a globally optimal clustering for a given number of clusters. It does converge to a locally optimal solution based on the initial selection of the centroids. One way to address this is to run the k-means algorithm multiple times with different initializations. At the end, we select the clustering with the smallest scatter. ## Scale and Correlation One way to address the issue of scale variation in features and correlation among features is using the Mahalanobis distance for distance calculations. To do this, in the estimation step we shall calculate the covariance matrix for each cluster separately. ````{prf:algorithm} k-means clustering with Mahalanobis distance :label: alg-ml-cl-k-means-mahalanobis Inputs: * The data set $\bX = \{ \bx_s\}_{s=1}^n \subset \RR^m$ * Number of clusters : $k$ Outputs: * Clusters: $\{\bX_j^{(i)} \}_{j=1}^k$ * Cluster labels array: $L[1:n]$ Initialization: 1. $i \leftarrow 0$. # Iteration counter 1. For each cluster $j \in \{1, \dots, k\}$: 1. Initialize $\mu_j^{(0)}$ and $\Sigma_j^{(0)}$ suitably. 1. Set $\bX_j^{(0)}$ to empty set. Algorithm: 1. If the segmentation has stopped changing: break. 1. Segmentation: for each data point $\bx_s \in \bX$: 1. Find the nearest centroid via Mahalanobis distance. $$ L(s) \leftarrow l \leftarrow \underset{j=1,\dots, k}{\text{arg min}} \| \bx_s - \mu_j^{(i)} \|^2_{\Sigma_j^{(i)}}. $$ Use the centroid number as the label for the point. 1. Assign $\bx_s$ to the cluster $\bX_l^{(i+1)}$. 1. Estimation: for each cluster $j \in \{1, \dots, k\}$: 1. Compute new mean/centroid for the cluster: $$ \mu_j^{(i+1)} \leftarrow \text{mean}(\bX_j^{(i+1)}). $$ 1. Compute the covariance matrix for the cluster: $$ \Sigma_j^{(i+1)} \leftarrow \text{cov}(\bX_j^{(i+1)}). $$ 1. $i \leftarrow i+1$. # Increase iteration counter 1. Go to step 1. ```` A *within-cluster-scatter* can be defined as $$ w(L) = \frac{1}{n} \sum_{j=1}^k \sum_{L(s) = j} \| y_s - \mu_j \|^2_{\Sigma_j}. $$ This represents the average (squared) distance of each point to the respective cluster mean. The $k$-means algorithm reduces the scatter in each iteration. it is guaranteed to converge to a local minimum.