<p>Apart from the works by <a href="http://www.computer.org/portal/web/csdl/doi/10.1109/FOCS.2006.75">Ostrovsky et al</a>, and the work by <a href="http://www.stanford.edu/~darthur/kMeansPlusPlus.pdf">Arthur and Vassilvitskii</a> on the behavior of k-means, there's a body of theoretical work on <a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1366265&amp;tag=1">Euclidean k-median and k-means</a> leading up to "linear" time algorithms for clustering under these formulations. What's interesting about these latter works is that they use separability as a tool in the analysis, but don't require it in the data. </p>

CC BY-SA 2.5
2010-11-15T23:57:04.733Z
2010-11-15T23:57:04.733Z
Suresh Venkat
<p>One <a href="http://portal.acm.org/citation.cfm?id=1496886">recent model</a> trying to capture such a notion is by Balcan, Blum, and Gupta '09.  They give algorithms for various clustering objectives when the data satisfies a certain assumption: namely that if the data is such that any $c$-approximation for the clustering objective is $\epsilon$-close to the optimal clustering, then they can give efficient algorithms for finding an almost-optimal clustering, even for values of $c$ for which finding the $c$-approximation is NP-Hard.  This is an assumption about the data being somehow "nice" or "separable."  Lipton has <a href="http://rjlipton.wordpress.com/2010/05/17/the-shadow-case-model-of-complexity/">a nice blog post</a> on this.</p>

<p>Another similar type of condition about data given in <a href="http://www.cs.huji.ac.il/~nati/PAPERS/stable_instance.pdf">a paper</a> by Bilu and Linial '10 is perturbation-stability.  Basically, they show that if the data is such that the optimal clustering doesn't change when the data is perturbed (by some parameter $\alpha$) for large enough values of $\alpha$, one can efficiently find the optimal clustering for the original data, even when the problem is NP-Hard in general.  This is another notion of stability or separability of the data.</p>

<p>I'm sure there is earlier work and earlier relevant notions, but these are some recent theoretical results related to your question.</p>

CC BY-SA 2.5
2010-11-15T23:47:35.293Z
2010-11-16T16:20:51.993Z
2010-11-16T16:20:51.993Z
Lev Reyzin
<p>Real world data sometimes has a natural number of clusters (trying to cluster it into a number of cluster lesser than some magic k will cause a dramatic increase the clustering cost). Today I attended a lecture by Dr. Adam Meyerson and he referred to that type of data as "separable data". </p>

<p>What are some clustering formalizations, other than K-means, that could be amenable to clustering algorithms (approximations or heuristics) that would exploit natural separability in data?</p>

<lg.learning><clustering>
Clustering formalizations other than K-means for separable data
Aleksandr Levchuk
# Clustering formalizations other than K-means for separable data

(Asked by: username_0 on 2010-11-15)

Real world data sometimes has a natural number of clusters (trying to cluster it into a number of cluster lesser than some magic k will cause a dramatic increase the clustering cost). Today I attended a lecture by Dr. Adam Meyerson and he referred to that type of data as "separable data".

What are some clustering formalizations, other than K-means, that could be amenable to clustering algorithms (approximations or heuristics) that would exploit natural separability in data?

**Tags:** lg.learning, clustering

---

## 2 answers

### Answer by username_2 on 2010-11-15. Score: 11 | Accepted answer

One [recent model](http://portal.acm.org/citation.cfm?id=1496886) trying to capture such a notion is by Balcan, Blum, and Gupta '09. They give algorithms for various clustering objectives when the data satisfies a certain assumption: namely that if the data is such that any $c$-approximation for the clustering objective is $\epsilon$-close to the optimal clustering, then they can give efficient algorithms for finding an almost-optimal clustering, even for values of $c$ for which finding the $c$-approximation is NP-Hard. This is an assumption about the data being somehow "nice" or "separable." Lipton has [a nice blog post](http://rjlipton.wordpress.com/2010/05/17/the-shadow-case-model-of-complexity/) on this.

Another similar type of condition about data given in [a paper](http://www.cs.huji.ac.il/~nati/PAPERS/stable_instance.pdf) by Bilu and Linial '10 is perturbation-stability. Basically, they show that if the data is such that the optimal clustering doesn't change when the data is perturbed (by some parameter $\alpha$) for large enough values of $\alpha$, one can efficiently find the optimal clustering for the original data, even when the problem is NP-Hard in general. This is another notion of stability or separability of the data.

I'm sure there is earlier work and earlier relevant notions, but these are some recent theoretical results related to your question.


---

### Answer by username_1 on 2010-11-15. Score: 8

Apart from the works by [Ostrovsky et al](http://www.computer.org/portal/web/csdl/doi/10.1109/FOCS.2006.75), and the work by [Arthur and Vassilvitskii](http://www.stanford.edu/~darthur/kMeansPlusPlus.pdf) on the behavior of k-means, there's a body of theoretical work on [Euclidean k-median and k-means](http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1366265&tag=1) leading up to "linear" time algorithms for clustering under these formulations. What's interesting about these latter works is that they use separability as a tool in the analysis, but don't require it in the data.


---

