I think this is the most easily understood topic in Kernel K Means Clustering. But assuming that I am not an expert in Machine Learning, can someone tell me how does someone calculate Kernel K means clustering centres?
From what I know, we take mean of all points in a cluster for normal k means. But in case of Kernel K means, we need to take mean of all points in feature space (which can be of infinite dimension). Certainly, for each kernel, its feature map is not known. How can someone then calculate kernel k means centres of clusters?
Best Answer
I think I found an answer. All you need to do in Kernel K means is to compute $$ C^{(t+1)}(i) = argmin_k \{K(x_i,x_i) -\frac{2}{N_k}{\Sigma_{l\epsilon C^{t}_k}}K(x_i,x_l) +\frac{1}{N_k^2} {\Sigma_{{l,{l`}}\epsilon C^{t}_k} }K(x_l,x_{l`})\} ...(1) $$
So this is the only operation that needs to be done. One need not to know each cluster center in high dimensional space. Just compute $(1)$ again and again till the algorithm converges.
Algorithm:
Step 1: Assign Random Cluster to points (Known as clsuter map $ C(i):= \{k: i\rightarrow k\}$ i.e point $i$ is assigned to cluster $k$
Step 2: For each point perform $(1)$ above and assign new $C(i)$.
Just to be more clear at this step:
$\rightarrow$After running this step for $(t-1)^{th} iteration $, you get a new $C^{(t)}(i)$ which will be used in (1) again to calculate $C^{(t+1)}(i)$
$\rightarrow$ So each iteration assigns new $C(i)$.Hence, $C^{(t)}(i)$ keeps on changing ( which is representative of cluster means).
Step 3: Repeat 2 above till the point assignments do not change or any of your error metric is stable. (I am not sure about the error metric that should be used)
New Point:
Each new point will be classified according to $(1)$ above.