## Tags : k-means

Entries in this Tags : 2logs Showing : 1 - 2 / 2

## Apr 01, 2013

### On the symmetrical Kullback-Leibler Jeffreys centroids, and Lambert W-function

Post @ 13:41:30 | centroids, k-means

There are many ways to symmetrize the Kullback-Leibler divergence like Jeffreys one-half symmetrized KL or Jensen-Shannon divergence by taking the divergences to the mid-distribution. There is also Chernoff min-max divergence that has a nice geometric interpretation. One question that arises once we get an appropriate divergence is how to perform hard clustering a la k-means. This requires to compute a centroid. We address the problem of computing Jeffreys centroid. We end-up with a closed-form for positive histograms using Lambert W functions:

Furthermore, we prove that renormalizing this centroid gives a bound on the frequency Jeffreys centroid. We also report a simple bisection algorithm for approximating the exact frequency Jeffreys centroid. Note that we can use a variational k-means approach as described in the previous post. Further details are provided here

## Mar 27, 2009

### Batched and Incremental k-means

Post @ 17:57:16 | k-means

Since Lloyd's k-means iterative algorithm for hard clustering that stepwisely assign points to their nearest cluster and relocate these centers as centroids, there have been many generalizations, including the Bregman k-means.
This k-means is a batched k-means as points are assigned to their nearest center in a single stage. The optimization is monotone but only converge to a local minimum. To get off this potential local minimum, we can use a single swap that tries to move a point from a cluster to another one. Of course, we better choose the point and target cluster as the one that best decreases the loss function.
This incremental k-means is known and explained as the first variation by Teboulle et al.:

Clustering with Entropy-Like k-Means Algorithms


I invite you to look at the minimization of the loss function on a gene array expression dataset by combining batched and online k-means.
Frank.