Artificial
Intelligence

11.1.3 EM for Soft Clustering

The EM algorithm can be used for soft clustering. Intuitively, for clustering, EM is like the k-means algorithm, but examples are probabilistically in classes, and probabilities define the distance metric. We assume here that the features are discrete.

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

When clustering, the role of the categorization is to be able to predict the values of the features. To use EM for soft clustering, we can use a naive Bayesian classifier, where the input features probabilistically depend on the class and are independent of each other given the class. The class variable has k values, which can be just {1,...,k}.

Model	Data	→	Probabilities
	X1 X2 X3 X4 t f t t f t t f f f t t ···		P(C) P(X1|C) P(X2|C) P(X3|C) P(X4|C)

Given the naive Bayesian model and the data, the EM algorithm produces the probabilities needed for the classifier, as shown in Figure 11.2. The class variable is C in this figure. The probability distribution of the class and the probabilities of the features given the class are enough to classify any new example.

To initialize the EM algorithm, augment the data with a class feature, C, and a count column. Each original tuple gets mapped into k tuples, one for each class. The counts for these tuples are assigned randomly so that they sum to 1. For example, for four features and three classes, we could have the following:

If the set of training examples contains multiple tuples with the same values on the input features, these can be grouped together in the augmented data. If there are m tuples in the set of training examples with the same assignment of values to the input features, the sum of the counts in the augmented data with those feature values is equal to m.

The EM algorithm, illustrated in Figure 11.3, maintains both the probability tables and the augmented data. In the E step, it updates the counts, and in the M step it updates the probabilities.

The algorithm is presented in Figure 11.4. In this figure, A[X₁,...,X_n,C] contains the augmented data; M_i[X_i,C] is the marginal probability, P(X_i,C), derived from A; and P_i[X_i,C] is the conditional probability P(X_i|C). It repeats two steps:

• E step: Update the augmented data based on the probability distribution. Suppose there are m copies of the tuple ⟨X₁=v₁,...,X_n=v_n⟩ in the original data. In the augmented data, the count associated with class c, stored in A[v₁,...,v_n,c], is updated to

  m ×P(C=c|X₁=v₁,...,X_n=v_n).

  Note that this step involves probabilistic inference, as shown below.

• M step: Infer the maximum-likelihood probabilities for the model from the augmented data. This is the same problem as learning probabilities from data.

The EM algorithm presented starts with made-up probabilities. It could have started with made-up counts. EM will converge to a local maximum of the likelihood of the data. The algorithm can terminate when the changes are small enough.

This algorithm returns a probabilistic model, which can be used to classify an existing or new example. The way to classify a new example, and the way to evaluate line 18, is to use the following:

P(C=c|X1=v1,...,Xn=vn)
	=	(P(C=c) ×∏i=1n P(Xi=vi|C=c))/(∑c'P(C=c') ×∏i=1n P(Xi=vi|C=c')) .

The probabilities in this equation are specified as part of the model learned.

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.

Note that, as long as k>1, EM virtually always has multiple local maxima. In particular, any permutation of the class labels of a local maximum will also be a local maximum.