Kernel k-means

kernel k-means algorithm

Description

This function performs kernel version of kmeans algorithm. When the linear kernel (i.e., inner product) is used, the algorithm is equivalent to standard kmeans algorithm.

Input
K: n x n a semi-definite matrix computed by a kernel function on all sample pairs
m: the number of clusters k (1 x 1) or the initial label of samples (1 x n, 1<=label(i)<=k)

reference: [1] Kernel Methods for Pattern Analysis
by John Shawe-Taylor, Nello Cristianini

sample code:
load data;
K=x'*x; % use linear kernel
label=knkmeans(K,3);
spread(x,label)

• MATLAB release: MATLAB 7.9 (2009b)

[Mathieu]

It seems that if I request N clusters, the algorithms outputs k clusters, k<=N clusters and most of the time k<<N. I was wondering if this is by construction. If yes, could provide me with an explanation ?

[Mo Chen]

This happens for standard kmeans too, which is caused by the nature of the algorithm. The reason is that when you set a very big number for k, after several iterations, some clusters might become empty.

[Mathieu]

I see, reading the code I do not manage to understand what are the principles behind the algorithm. Do you have a reference that I could get from the web or do you advise to buy the book ?

[Seyed Salim]

Mathieu, you can refer to machine learning and pattern recognition by Bishop, 2005. Alternatively this is for free: www-stat.stanford.edu/~hastie/Papers/ESLII.pdf

[Mo Chen]

Hi mathieu,
As indicated in the description, this algorithm is explained in
reference: [1] Kernel Methods for Pattern Analysis
by John Shawe-Taylor, Nello Cristianini

[John Melonakos]

The code appears broken to me:

>> load data;
K=x'*x; % use linear kernel
label=knkmeans(K,3);
scatterd(x,label)
??? Undefined function or variable 'val'.

Error in ==> knkmeans at 31
energy = sum(val)+trace(K);

[Phillip]

Hello I encountered the same problem as john luckily i had the book, I added the following code. The energy is the sum squared clustering cost function. I have been optimizing my kernel hyper-parameters to minimise this energy. Been working fairly well so thanks. Not an expert so could be wrong.

A=zeros(size(S'));
for i=1:1:size(K,1)
          A(i,label(i))=1;
end
D=diag(1./sum(A));
  energy = trace(K)-trace(sqrt(D)*A'*K*A*sqrt(D));

[Mo Chen]

Hi, Phillip,
You computation is right, only not very efficient. Check my new code

[Santiago]