Is it possible to find cluster centroids in kernel K means?

Question

Suppose ${x_1, \ldots, x_N}$ are the data points and we have to find $K$ clusters using Kernel K Means.

Let the kernel be $Ker$ (not to confuse with $K$ number of clusters)

Let $\phi$ be the implicit mapping induced by this kernel.

Now if $\phi$ were finite dimensional, there was no problem. However, assume $phi$ to be infinite dimensional, such has induced by RBF kernel

Now, everywhere I have read about kernel K means, it only says that we can do kernel K Means using

$||\phi(x_i) - \phi(x_j)||^2 = Ker(x_i, x_i) + Ker(x_j, x_j) - 2Ker(x_i, x_j) \;\; \ldots(1)$

I get this, but it is not so simple for my brain and nobody gives an explicit algorithm for kernel K means which leaves me with following doubts:

1. In what space do we initialise the K centroids? In the original space, or the space induced by $\phi$? I am guessing, we initialise in the original space only because we can't even comprehend the data points in space induced by $\phi$ Suppose we initialise randomly these $K$ centroids $\mu_1, \ldots \mu_K$ in the original space only. (Please correct me if I assuming wrong)

2. After initialisation, we have to assign every data point to one of the clusters. Suppose we want to assign $x_n$ to a cluster, this can be easily done using (1) to compute $\mu_k$ = $\text{arg min}_j\; ||\phi(x_n) - \phi(\mu_j)||^2$

3. After assigning clusters, how do I calculate the new centroids? Obviously I can't take mean in the space induced by $\phi$ as it is infinite dimensional, so what do I do now?

What is the work around this problem? I am assuming there is someway that we don't have to store the centroids at all. But I can't think of how to achieve this.

I have read Finding the cluster centers in kernel k-means clustering

However, the community wiki answer doesn't explains where $(1)$ comes from.

Answer 1

Kernel k-means is equivalent to regular k-means operating in the feature space induced by the kernel. Therefore, the centroids live in feature space which, as you mentioned, may be infinite dimensional. When formulating a learning algorithm using the kernel trick, we never need to touch feature space directly. All operations in feature space are performed implicitly using the kernel function. So, we never deal directly with the centroids in kernel k-means. Instead, we work with the cluster assignments, as I'll explain below.

K-means in feature space

Lloyd's algorithm is the standard method for (approximately) solving the k-means problem. Here's a generalization that works directly in feature space. Let $X = \{x_1, \dots, x_n\}$ be the data points and $\phi(\cdot)$ be a function that maps a point from input space into feature space.

1. Initialize $K$ clusters $C_1, \dots, C_K$, where each cluster $C_j$ is a set containing $n_j$ points, and each point is a member of exactly one cluster.

Repeat until convergence (no change in cluster membership):

2. For each cluster $C_j$, the centroid (in feature space) is:

   $$\mu_j = \frac{1}{n_j} \sum_{x \in C_j} \phi(x) \tag{1}$$

3. For each point $x_i$, find the index $a_i$ of the cluster whose centroid is nearest (in feature space).

$$a_i = \arg \min_j \ \|\phi(x_i) - \mu_j\|^2 \tag{2}$$

$$= \arg \min_j \ \langle \phi(x_i), \phi(x_i) \rangle + \langle \mu_j, \mu_j \rangle - 2 \langle \phi(x_i), \mu_j \rangle \tag{3}$$

$$= \arg \min_j \ \langle \mu_j, \mu_j \rangle - 2 \langle \phi(x_i), \mu_j \rangle \tag{4}$$

4. Update clusters. Each point becomes a member of the cluster with the nearest centroid:

$$C_j = \{x_i \mid a_i = j\}$$

Note: $\langle \cdot, \cdot \rangle$ denotes the inner product. Equation $(3)$ follows from the relationship between the norm and inner product. The first term $\langle \phi(x_i), \phi(x_i) \rangle$ doesn't depend on the cluster so we can drop it, giving equation $(4)$.

Using the kernel trick

Suppose we a have kernel function $k(\cdot, \cdot)$ that computes inner products in feature space. So $k(x, x') = \langle \phi(x), \phi(x') \rangle$. We can replace inner products in the algorithm above with kernel function evaluations, thereby operating implicitly in feature space. This is called the kernel trick.

First, combine steps 2 and 3 by substituting the definition of centroids in equation $(1)$ into the nearest centroid search in equation $(4)$:

$$\arg \min_j \ \left \langle \frac{1}{n_j} \sum_{x \in C_j} \phi(x), \frac{1}{n_j} \sum_{x' \in C_j} \phi(x') \right \rangle - 2 \left \langle \phi(x_i), \frac{1}{n_j} \sum_{x \in C_j} \phi(x) \right \rangle \tag{5}$$

Since the inner product is bilinear, we can rewrite this as:

$$\arg \min_j \ \frac{1}{n_j^2} \sum_{x \in C_j} \sum_{x' \in C_j} \langle \phi(x), \phi(x') \rangle - \frac{2}{n_j} \sum_{x \in C_j} \langle \phi(x_i), \phi(x) \rangle \tag{6}$$

Replace inner products with kernel function evaluations:

$$\arg \min_j \ \frac{1}{n_j^2} \sum_{x \in C_j} \sum_{x' \in C_j} k(x, x') - \frac{2}{n_j} \sum_{x \in C_j} k(x_i, x) \tag{7}$$

For each point $x_i$, this says how to find the cluster with the nearest centroid, without explicitly computing the centroids in feature space. It can be substituted in for steps 2 and 3 in the algorithm above.