# Clustering formalizations other than K-means for separable data

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.