Formalizacje grupowania inne niż K-średnie dla oddzielnych danych

Dane ze świata rzeczywistego czasami mają naturalną liczbę klastrów (próba klastrowania ich w liczbę klastrów mniejszą niż jakaś magiczna k spowoduje drastyczny wzrost kosztu klastrowania). Dzisiaj uczestniczyłem w wykładzie dr Adama Meyersona, który nazwał tego typu danymi „danymi możliwymi do oddzielenia”.

Jakie są inne formalizacje klastrowania, inne niż K-średnie, które mogą być podatne na algorytmy klastrowania (aproksymacje lub heurystyka), które wykorzystywałyby naturalną separowalność w danych?

Jednym z ostatnich modeli próbujących uchwycić takie pojęcie jest Balcan, Blum i Gupta '09. Podają algorytmy dla różnych celów klastrowania, gdy dane spełniają pewne założenia: mianowicie, że jeśli dane są takie, że jakiekolwiek przybliżenie dla celu klastrowania jest ϵ -bliskie do optymalnego grupowania, wówczas mogą podać wydajne algorytmy do znalezienia prawie -optymalne grupowanie, nawet dla wartości c, dla których znalezienie przybliżenia c jest NP-twarde. Jest to założenie, że dane są w jakiś sposób „ładne” lub „możliwe do rozdzielenia”. Lipton ma fajny post na ten temat.$c$$\epsilon$$c$$c$

$\alpha$$\alpha$

Jestem pewien, że istnieje wcześniejsza praca i wcześniejsze odpowiednie pojęcia, ale są to niektóre teoretyczne wyniki związane z twoim pytaniem.

Oprócz prac Ostrovsky'ego i in. Oraz pracy Arthura i Vassilvitskiego na temat zachowania k-średnich, istnieje cała część teoretycznych prac nad euklidesową k-medianą i k-średnich prowadzących do „liniowych” algorytmów czasowych dla grupowania te formulacje. Ciekawe w tych ostatnich pracach jest to, że używają one separacji jako narzędzia w analizie, ale nie wymagają tego w danych.