The k-means algorithm is used for hard clustering. The training examples, $E$, and the number of clusters, $k$, are given as input. It requires the value of each feature to be a (real) number, so that differences in values make sense.

The algorithm constructs $k$ clusters, a prediction of a value for each feature for each cluster, and an assignment of examples to clusters.

Suppose the input features, $X_1,\mathrm{\dots },X_n$, are observed for each example. Let $X_j(e)$ be the value of input feature $X_j$ for example $e$. Associate a cluster with each integer $c\in \{1,\mathrm{\dots },k\}$.

The $k$-means algorithm constructs

• •

  a function $cluster:E\to \{1,\mathrm{\dots },k\}$ that maps each example to a cluster (if $cluster(e)=c$, example $e$ is said to be in cluster $c$)

• •

  a function $prediction(j,c)$ that returns the predicted value of each element of cluster $c$ on feature $X_j$.

Example $e$ is thus predicted to have value $prediction(j,cluster(e))$ for feature $X_j$.

The aim is to find the functions $cluster$ and $prediction$ that minimize the sum of squared loss:

To minimize the squared loss, the prediction of a cluster should be the mean of the prediction of the examples in the cluster; see Figure 7.5. Finding an optimal clustering is NP-hard. When there are only a few examples, it is possible to enumerate the assignments of examples to clusters. For more than a few examples, there are too many partitions of the examples into $k$ clusters for exhaustive search to be feasible.

The $k$-means algorithm iteratively improves the squared loss. Initially, it randomly assigns the examples to clusters. Then it carries out the following two steps:

• •

  For each cluster $c$ and feature $X_j$, make $prediction(j,c)$ be the mean value of $X_j(e)$ for each example $e$ in cluster $c$:

  $$\frac{{\displaystyle \sum _{e:cluster(e)=c}}{X}_j(e)}{\left|\{e:cluster(e)=c\}\right|}$$

  where the denominator is the number of examples in cluster $c$.

• •

  Reassign each example to a cluster: assign each example $e$ to a cluster $c$ that minimizes

  $$\sum _{j=1}^n{\left(prediction(j,c)-X_j(e)\right)}^2.$$

These two steps are repeated until the second step does not change the assignment of any example.

An algorithm that implements $k$-means is shown in Figure 10.4. It constructs sufficient statistics to compute the mean of each cluster for each feature, namely

• •

  $cc[c]$ is the number of examples in cluster $c$

• •

  $fs[j,c]$ is the sum of the value for $X_j(e)$ for examples in cluster $c$.

These are sufficient statistics because they contain all of the information from the data necessary to compute $cluster(e)$ and $prediction(j,c)$. The current values of $fs$ and $cc$ are used to determine the next values (in $fs\mathrm{\_}new$ and $cc\mathrm{\_}new$).

The random initialization could be assigning each example to a cluster at random, selecting $k$ points at random to be representative of the clusters, or assigning some, but not all, of the examples to construct the initial sufficient statistics. The latter two methods may be more useful if the dataset is large, as they avoid a pass through the whole dataset for initialization.

An assignment of examples to clusters is stable if an iteration of $k$-means does not change the assignment. Stability requires that $argmin$ in the definition of $cluster$ gives a consistent value for each example in cases where more than one cluster is minimal. This algorithm has reached a stable assignment when each example is assigned to the same cluster in one iteration as in the previous iteration. When this happens, $fs$ and $cluster\mathrm{\_}count$ do not change, and so the Boolean variable $stable$ becomes $true$.

This algorithm will eventually converge to a stable local minimum. This is easy to see because the sum-of-squares error keeps reducing and there are only a finite number of reassignments. This algorithm often converges in a few iterations.

Some stable assignments may be better, in terms of sum-of-squares error, than other stable assignments. To find the best assignment, it is often useful to try multiple starting configurations, using a random restart and selecting a stable assignment with the lowest sum-of-squares error. Note that any permutation of the labels of a stable assignment is also a stable assignment, so there are invariably multiple local and global minima.

One problem with the $k$-means algorithm is that it is sensitive to the relative scale of the dimensions. For example, if one feature is $height$ in centimeters, another feature is $age$, and another is a binary ($\{0,1\}$) feature, the different values need to be scaled so that they can be compared. How they are scaled relative to each other affects the clusters found. It is common to scale the dimensions to between 0 and 1 or with a mean of 0 and a variance of 1, but this assumes that all dimensions are relevant and independent of each other.

Finding an appropriate number of clusters is a classic problem in trading off model complexity and fit to data. One solution is to use the Bayesian information criteria (BIC) score, similar to its use in decision trees where the number of clusters is used instead of the number of leaves. While it is possible to construct $k+1$ clusters from $k$ clusters, the optimal division into three clusters, for example, may be quite different from the optimal division into two clusters.

A hidden variable or latent variable is a probabilistic variable that is not observed in a dataset. A Bayes classifier can be the basis for unsupervised learning by making the class a hidden variable.

The expectation maximization (EM) algorithm can be used to learn probabilistic models with hidden variables. Combined with a naive Bayes classifier, it does soft clustering, similar to the $k$-means algorithm, but where examples are probabilistically in clusters.

As in the $k$-means algorithm, the training examples and the number of clusters, $k$, are given as input.

Given the data, a naive Bayes model is constructed where there is a variable for each feature in the data and a hidden variable for the class. The class variable is the only parent of the other features. This is shown in Figure 10.6. The class variable has domain $\{1,2,\mathrm{\dots },k\}$, where $k$ is the number of classes. The probabilities needed for this model are the probability of the class $C$ and the probability of each feature given $C$. The aim of the EM algorithm is to learn probabilities that best fit the data.

The EM algorithm conceptually augments the data with a class feature, $C$, and a count column. Each original example gets mapped into $k$ augmented examples, one for each class. The counts for these examples are assigned so that they sum to 1.

For four features and three classes, the example is mapped into the three tuples, shown in the table on the left of Figure 10.7. EM works by iteratively determining the count from the model, and the model from the count.

The EM algorithm repeats the following two steps:

• •

  E step. Update the augmented counts based on the probability distribution. For each example in the original data, the count associated with in the augmented data is updated to

  $$P(C=c\mid X_1=v_1,\mathrm{\dots },X_n=v_n).$$

  This step involves probabilistic inference. If multiple examples have the same values for the input features, they can be treated together, with the probabilities multiplied by the number of examples. This is an expectation step because it computes the expected values.

• •

  M step. Infer the probabilities for the model from the augmented data. Because the augmented data has values associated with all the variables, this is the same problem as learning probabilities from data in a naive Bayes classifier. This is a maximization step because it computes the maximum likelihood estimate or the maximum a posteriori probability (MAP) estimate of the probability.

The EM algorithm starts with random probabilities or random counts. EM will converge to a local maximum of the likelihood of the data.

This algorithm returns a probabilistic model, which is used to classify an existing or new example. An example is classified using

The algorithm does not need to store the augmented data, but can maintain a set of sufficient statistics, which is enough information to compute the required probabilities. Assuming categorical features, sufficient statistics for this algorithm are

• •

  $cc$, the class count, a $k$-valued array such that $cc[c]$ is the sum of the counts of the examples in the augmented data with $class=c$

• •

  $fc$, the feature count, a three-dimensional array; for $i$ from 1 to $n$, for each value $v$ in $domain(X_i)$, and for each class $c$, $fc[i,v,c]$ is the sum of the counts of the augmented examples $t$ with $X_i(t)=v$ and $class(t)=c$.

In each iteration, it sweeps through the data once to compute the sufficient statistics. The sufficient statistics from the previous iteration are used to infer the new sufficient statistics for the next iteration.

The probabilities required of the model can be computed from $cc$ and $fc$:

where $\left|E\right|$ is the number of examples in the original dataset (which is the same as the sum of the counts in the augmented dataset).

The algorithm of Figure 10.8 computes the sufficient statistics. Evaluating $P(C=c\mid X_1=v_1,\mathrm{\dots },X_n=v_n)$ in line 17 relies on the counts in $cc$ and $fc$. This algorithm has glossed over how to initialize the counts. One way is for $P(C\mid X_1=v_1,\mathrm{\dots },X_n=v_n)$ to return a random distribution for the first iteration, so the counts come from the data. Alternatively, the counts can be assigned randomly before seeing any data. See Exercise 10.7.

The algorithm will eventually converge when $cc$ and $fc$ do not change significantly in an iteration. The threshold for the approximately equal in line 21 can be tuned to trade off learning time and accuracy. An alternative is to run the algorithms for a fixed number of iterations.

Notice the similarity with the $k$-means algorithm. The E step (probabilistically) assigns examples to classes, and the M step determines what the classes predict.

As long as $k>1$, EM, like $k$-means, virtually always has multiple local and global maxima. In particular, any permutation of the class labels will give the same probabilities. To try to find a global maximum, multiple restarts can be tried, and a model with the lowest log-likelihood returned.