Andere Cluster-Formalisierungen als K-Mittel für trennbare Daten

Daten aus der realen Welt haben manchmal eine natürliche Anzahl von Clustern (der Versuch, sie in eine Anzahl von Clustern zu gruppieren, die kleiner als ein magisches k ist, führt zu einem dramatischen Anstieg der Clusterkosten). Heute habe ich einen Vortrag von Dr. Adam Meyerson besucht und er hat diese Art von Daten als "trennbare Daten" bezeichnet.

Was sind andere Cluster-Formalisierungen als K-Mittel, die für Cluster-Algorithmen (Approximationen oder Heuristiken) geeignet sein könnten, die die natürliche Trennbarkeit von Daten ausnutzen würden?

Ein aktuelles Modell, das versucht, eine solche Vorstellung zu erfassen, stammt von Balcan, Blum und Gupta '09. Sie geben Algorithmen für verschiedene Clustering-Ziele an, wenn die Daten eine bestimmte Annahme erfüllen : Wenn die Daten so sind, dass eine Annäherung für das Clustering-Ziel ϵ- nahe an der optimalen Clustering liegt, können sie effiziente Algorithmen zum Auffinden einer nahezu liefern -optimale Clusterbildung, selbst für Werte von c, für die das Finden der c- Approximation NP-schwer ist. Dies ist eine Annahme darüber, dass die Daten irgendwie "nett" oder "trennbar" sind. Lipton hat einen schönen Blog-Beitrag dazu.$c$$\epsilon$$c$$c$

$\alpha$$\alpha$

Ich bin sicher, dass es frühere Arbeiten und frühere relevante Begriffe gibt, aber dies sind einige neuere theoretische Ergebnisse, die sich auf Ihre Frage beziehen.

Neben den Arbeiten von Ostrovsky et al . Und den Arbeiten von Arthur und Vassilvitskii zum Verhalten von k-Mitteln gibt es eine Reihe theoretischer Arbeiten zum euklidischen k-Median und zu k-Mitteln , die zu "linearen" Zeitalgorithmen für die Clusterbildung führen diese Formulierungen. Das Interessante an diesen letzteren Arbeiten ist, dass sie die Trennbarkeit als Werkzeug für die Analyse verwenden, diese jedoch nicht in den Daten benötigen.