Kernel K-means and Spectral Clustering

The objective in K-means can be written as follows:

(11.1)

where we wish to minimize over the assignment variablesz__i(which can take valuesz__i= 1,..,K, for all data-casesi, and over the cluster meansµk, k= 1..K. It is not hard to show that the following iterations achieve that,

z__i= argmin||x__i−µ__k||2(11.2)

k

(11.3)

where_C__k_is the set of data-cases assigned to cluster k.

Now, let’s assume we have defined many features,φ(x__i)and wish to do clustering in feature space. The objective is similar to before,

(11.4)

We will now introduce aN×K_assignment matrix,_Z__nk, each column of which represents a data-case and contains exactly one1at rowk_if it is assigned to cluster_k.As a result we havePkZnk= 1andN__k= PnZnk. Also define