Formalizações de cluster que não sejam meios K para dados separáveis

Os dados do mundo real às vezes têm um número natural de clusters (tentar agrupá-los em um número menor de clusters do que um k mágico causará um aumento dramático no custo de cluster). Hoje assisti a uma palestra do Dr. Adam Meyerson e ele se referiu a esse tipo de dados como "dados separáveis".

Quais são algumas formalizações de cluster, que não sejam meios K, que podem ser passíveis de algoritmos de cluster (aproximações ou heurísticas) que explorariam a separabilidade natural dos dados?

Um modelo recente que tenta capturar essa noção é de Balcan, Blum e Gupta '09. Eles dão algoritmos para vários objectivos de agrupamento quando os satisfaz dados uma certa suposição: a saber, que se os dados é tal que qualquer -approximation para o objetivo de agrupamento é ε -próximo ao ideal clustering, então eles podem dar algoritmos eficientes para encontrar uma quase agrupamento ótimo, mesmo para valores de c para os quais a aproximação c é NP-Hard. Esta é uma suposição de que os dados são de alguma forma "agradáveis" ou "separáveis". Lipton tem um bom post sobre isso.$c$$\epsilon$$c$$c$

$\alpha$$\alpha$

Tenho certeza de que existem trabalhos anteriores e noções relevantes anteriores, mas esses são alguns resultados teóricos recentes relacionados à sua pergunta.

Além dos trabalhos de Ostrovsky et al . E do trabalho de Arthur e Vassilvitskii sobre o comportamento de k-means, há um corpo de trabalho teórico sobre k-mediana euclidiana e k-meios que levam a algoritmos de tempo "lineares" para agrupar sob estas formulações. O interessante desses últimos trabalhos é que eles usam a separabilidade como uma ferramenta na análise, mas não exigem isso nos dados.