Formalisations de clustering autres que K-means pour les données séparables

Les données du monde réel ont parfois un nombre naturel de clusters (essayer de les regrouper en un nombre de clusters inférieur à certains k magiques entraînera une augmentation spectaculaire du coût de clustering). Aujourd'hui, j'ai assisté à une conférence du Dr Adam Meyerson et il a qualifié ce type de données de "données séparables".

Quelles sont les formalisations de clustering, autres que K-means, qui pourraient se prêter à des algorithmes de clustering (approximations ou heuristiques) qui exploiteraient la séparabilité naturelle des données?

Un modèle récent essayant de saisir une telle notion est celui de Balcan, Blum et Gupta '09. Ils donnent des algorithmes pour différents objectifs de clustering lorsque les données satisfont à une certaine hypothèse: à savoir que si les données sont telles que toute approximation pour l'objectif de clustering est ϵ- proche du clustering optimal, alors ils peuvent donner des algorithmes efficaces pour trouver un presque - regroupement optimal, même pour les valeurs de c pour lesquelles trouver la c- approximation est NP-difficile. Il s'agit d'une hypothèse selon laquelle les données sont en quelque sorte "agréables" ou "séparables". Lipton a un joli blog à ce sujet.$c$$\epsilon$$c$$c$

$\alpha$$\alpha$

Je suis sûr qu'il y a des travaux antérieurs et des notions pertinentes antérieures, mais ce sont des résultats théoriques récents liés à votre question.

Outre les travaux d' Ostrovsky et al , et les travaux d' Arthur et Vassilvitskii sur le comportement des k-moyennes, il existe un corpus de travaux théoriques sur la médiane k et les k-moyens euclidiens menant à des algorithmes de temps "linéaires" pour le regroupement sous ces formulations. Ce qui est intéressant à propos de ces derniers travaux, c'est qu'ils utilisent la séparabilité comme outil dans l'analyse, mais ne l'exigent pas dans les données.