How do I cluster with KL-divergence?

Question

I want to cluster my data with KL-divergence as my metric.

In K-means:

1. Choose the number of clusters.

2. Initialize each cluster's mean at random.

3. Assign each data point to a cluster c with minimal distance value.

4. Update each cluster's mean to that of the data points assigned to it.

In the Euclidean case it's easy to update the mean, just by averaging each vector.

However, if I'd like to use KL-divergence as my metric, how do I update my mean?

Answer 1

Clustering with KL-divergence may not be the best idea, because KLD is missing an important property of metrics: symmetry. Obtained clusters could then be quite hard to interpret. If you want to go ahead with KLD, you could use as distance the average of KLD's i.e.

d(x,y) = KLD(x,y)/2 + KLD(y,x)/2