3
$\begingroup$

As we know that K-Means is a powerful clustering, however it often stuck with local minimum problem because of bad initialization . One of the solution is K-Harmonic means that use Harmonic Average as the performance function instead of minimum distance btw the data and cluster's centroid. I am curious that why using harmonic function makes less sensitive to init centroids than ordinary K-Means.

$\endgroup$
  • $\begingroup$ Did you run any experiments that support this assertion? And what about zero distances on real data? $\endgroup$ – Anony-Mousse Oct 4 '17 at 5:54
5
$\begingroup$

Harmonic mean is less sensitive to outliers.

Say that you have 3 numbers: 1 1 and 30001

Their arithmetic mean (average) is 10001 and their harmonic mean is 2 that is much closer to the majority of the points.

So in a way, using an harmonic mean is more forgiving.

A Bayesian look at the harmonic mean

Assuming that the closer a point is, the more likely it is to be in a cluster.

One can choose to model the distribution of distances from an origin point, as an Gamma-Exponential model with a priors $\alpha=m$ and $\beta=\frac{m}{\mu_0}$ where $\mu_0$ is the initial mean and $m$ is the strength of the prior.

And given observations of $\{d_1,d_2,\dots,d_n\}$, the updated model's mean is: $$\mu'=\frac{m+n}{\frac{m}{\mu_0}+\frac{1}{d_1}+\frac{1}{d_2}+\dots+\frac{1}{d_n}}$$ We got our beloved harmonic mean.

You could argue that the harmonic mean in k-means context is an assumption on the distribution of distances.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.