Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
One recent model 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 on this.
Another similar type of condition about data given in a paper 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.
Apart from the works by Ostrovsky et al, and the work by Arthur and Vassilvitskii on the behavior of k-means, there's a body of theoretical work on Euclidean k-median and k-means 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.
