Tell me more ×
Cross Validated is a question and answer site for statisticians, data analysts, data miners and data visualization experts. It's 100% free, no registration required.
up vote 2 down vote favorite

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) ?

share|improve this question
Which "many methods" did you see that in? Any references? – Anony-Mousse Jun 28 '12 at 17:31
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. – TenaliRaman Jun 28 '12 at 21:45
@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 ? – shn Jun 28 '12 at 22:30
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. – TenaliRaman Jun 29 '12 at 2:16
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}$. – TenaliRaman Jun 29 '12 at 2:47
show 3 more comments

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.