Usually online clustering methods (based on kmeans or not) define a distance threshold value. If a new data-point $x$ is far enough from the nearest center $c$ (i.e. the distance from $x$ to $c$ is greater than the threshold), then just give this $x$ its own new cluster.

I saw that many methods theoretically define this sort of threshold as "the mean distance of all data-points to the center of their distribution". That is, let $\bar{x}$ be the center-of-mass of all data-points, the threshold is defined as the mean distance of all data-points to $\bar{x}$.

Question: Why is the threshold defined like that ? Does this make any sense ? What is the idea behind setting the threshold to this value (mean of distances to the center-of-mass) ?

  • $\begingroup$ Which "many methods" did you see that in? Any references? $\endgroup$ – Anony-Mousse Jun 28 '12 at 17:31
  • $\begingroup$ Same question as Anony-Mousse, which methods describe that? According to what you describe, the threshold is the radius of a ball the encloses all data points. Now, that's a very large ball and I would be surprised if you can re-cluster even the existing points using that threshold. $\endgroup$ – TenaliRaman Jun 28 '12 at 21:45
  • $\begingroup$ @TenaliRaman I'll try to find some references where I saw that later, and update my post. So if you think that this is a large threshold (it is in fact the the case), which thresholds can be more convenient for such a situation ? $\endgroup$ – shn Jun 28 '12 at 22:30
  • $\begingroup$ I would be tempted to use something along the lines of $max_i(max_{x \in C_i}(distance(x, c_i)))$ where $c_i$ is the center of cluster $C_i$. P.S.This recent paper in ICML 2012 discusses k-means like algorithm inspired by DPMM (but simple enough like k-means) that can perform just as well as DPMM and enjoys the scalability of k-means. Might be of interest to you. $\endgroup$ – TenaliRaman Jun 29 '12 at 2:16
  • $\begingroup$ My earlier threshold might be a bit too conservative. A slightly bolder threshold could be $\frac{min_{i,j:i \neq j}d(c_i, c_j)}{2}$. $\endgroup$ – TenaliRaman Jun 29 '12 at 2:47

Your Answer

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

Browse other questions tagged or ask your own question.