Czy istnieją jakieś algorytmy klastrowania oparte na braku odległości?

14

Wydaje się, że w przypadku średnich K i innych powiązanych algorytmów grupowanie opiera się na obliczaniu odległości między punktami. Czy jest taki, który działa bez niego?

machine-learning clustering data-mining k-means użytkownik154510
źródło

2

Dokładnie, co miałbyś na myśli przez „grupowanie” bez jakiegoś sposobu na oszacowanie podobieństwa lub „bliskości” punktów?

whuber

2

@ Odpowiedź Tima poniżej jest bardzo dobra. Możesz rozważyć wznowienie głosowania i / lub zaakceptowanie go, jeśli pomogło ci to; to dobry sposób na powiedzenie „dzięki”. Rozszerzając swój pomysł, istnieje utajona analiza klas , która stosuje podobne podejście do danych kategorycznych. Nieparametryczne podejście do FMM można zastosować na podstawie wysokości szacunków gęstości jądra na wielu odmianach. Zobacz Klastrowanie za pomocą szacowania gęstości nieparametrycznej: Pakiet R pdfCluster ( pdf ), aby uzyskać więcej.

gung - Przywróć Monikę

25

Jednym z przykładów takiej metody są modele mieszanki skończonej (np. Tutaj lub tutaj ) stosowane do grupowania. W FMM rozważyć rozmieszczenie ( ) o zmiennej w postaci mieszaniny rozkładów ( ): $f$ $X$ $K$ $f_1,...,f_k$

f (x, ϑ) = \sum_{k = 1}^{K} π_{k} f_{k} (x, ϑ_{k})

$f(x, \vartheta) = \sum^K_{k=1} \pi_k f_k(x, \vartheta_k)$

gdzie jest wektorem parametrów i jest stosunek -tym rozkładu mieszaniny i jest parametrem (lub parametry) od dystrybucji. $\vartheta$ $\vartheta = (\pi', \vartheta_1', ..., \vartheta_k')'$ $\pi_k$ $k$ $\vartheta_k$ $f_k$

Szczególnym przypadkiem danych dyskretnych jest analiza ukrytych klas (np. Tutaj ) zdefiniowana jako:

P (x, k) = P (k) P (x | k)

$P(x, k) = P(k) P(x|k)$

gdzie jest prawdopodobieństwo obserwowania utajony klasy (czyli ), jest prawdopodobieństwo obserwację wartość i jest prawdopodobieństwo będących w klasie . $P(k)$ $k$ $\pi_k$ $P(x)$ $x$ $P(x|k)$ $x$ $k$

Zazwyczaj zarówno dla FMM, jak i LCA stosuje się algorytm EM , ale możliwe jest również podejście bayesowskie, ale nieco bardziej wymagające ze względu na problemy, takie jak identyfikacja modelu i zmiana etykiety (np . Blog Xi'ana ).

Zatem nie ma miary odległości, a raczej model statystyczny określający strukturę (rozkład) danych. Z tego powodu inną nazwą tej metody jest „klastrowanie oparte na modelu”.

Sprawdź dwie książki na temat FMM:

McLachlan, G. i Peel, D. (2000). Modele z skończoną mieszaniną. John Wiley & Sons.
Frühwirth-Schnatter, S. (2006). Modele z mieszanką skończoną i Markowa. Skoczek.

Jednym z najbardziej popularnych pakietów klastrów, które wykorzystuje się FMM mclust(sprawdź tutaj lub tutaj ), które jest realizowane w R . Możliwe są jednak bardziej skomplikowane FMM, sprawdź na przykład flexmixpakiet i jego dokumentację . Dla LCA istnieje pakiet R poLCA .

Tim
źródło

Czy masz dobre pojęcie o różnych przypadkach użycia?

shadowtalker

Na przykład: „kiedy powinienem tego użyć zamiast, powiedzmy, partycjonowania wokół medoidów?” W każdym razie bardzo fajna odpowiedź

shadowtalker,

1

@caveman zauważa, że to tylko konwencja notacyjna. To wektor wektorów, to wszystko.

Tim

1

k

$k$

f_{1}, . . ., f_{k}

$f_1,...,f_k$

1

k

$k$

7

$\sim$

Istnieje wiele podejść do klastrowania opartych na siatce . Nie obliczają odległości, ponieważ często daje to kwadratowy czas działania. Zamiast tego dzielą dane i agregują je w komórki siatki. Ale intuicja stojąca za takimi podejściami jest zwykle bardzo ściśle związana z odległościami.

Istnieje wiele algorytmów grupowania dla danych kategorycznych, takich jak COOLCAT i STUCCO. Odległości nie są łatwe w użyciu z takimi danymi (kodowanie na gorąco to hack i nie daje szczególnie znaczących odległości). Ale nie słyszałem o nikim, kto używałby tych algorytmów ...

Istnieją metody grupowania wykresów. Ale albo ograniczają się do klasycznych problemów graficznych, takich jak wyszukiwanie kliki lub bliski kliki i kolorowanie wykresów, lub są ściśle powiązane z grupowaniem na podstawie odległości (jeśli masz wykres ważony).

Klastrowanie oparte na gęstości, takie jak DBSCAN, ma inną nazwę i nie koncentruje się na minimalizowaniu odległości; ale „gęstość” jest zwykle określana w odniesieniu do odległości, więc technicznie algorytmy te są oparte na odległości lub na siatce.

Zasadniczą częścią pomijanego pytania jest to, jakie są twoje dane ?

Ma ZAKOŃCZENIE - Anony-Mus
źródło

1

+1: Doceniam to, że pokazujesz, w jaki sposób dowolny algorytm grupowania wykorzystuje ukryte (być może) uogólnione poczucie „odległości” lub „podobieństwa” i że robisz to, oferując przegląd wielu takich algorytmów.

whuber

Myślę, że przez „oparty na odległości” miał na myśli wskaźniki podobieństwa, które obejmowałyby wariancję.

en1

1

Dlaczego wariancja miałaby być podobieństwem? Jest to związane z kwadratową odległością euklidesową; ale nie równoważne arbitralnej odległości s .

Ma ZAKOŃCZENIE - Anony-Mousse

2

Oprócz poprzednich miłych odpowiedzi sugerowałbym rozważenie modeli mieszania Dirichleta i hierarchicznych modeli procesów Dirichleta opartych na Bayesian . Aby uzyskać raczej kompleksowy i ogólny przegląd podejść i metod określania optymalnej liczby klastrów , zobacz tę doskonałą odpowiedź na StackOverflow : /programming//a/15376462/2872891 .

Aleksandr Blekh
źródło

2

Podejście czysto dyskryminujące to „uregulowana maksymalizacja informacji” według Gomesa i in . Nie ma w tym żadnego pojęcia o podobieństwie / odległości.

Chodzi o regresję logistyczną podobną do modelu, która umieszcza punkty w pojemnikach. Ale zamiast trenować go, aby zmaksymalizować pewną formę logarytmu prawdopodobieństwa etykiet klas, funkcją celu jest ta, która umieszcza punkty w różnych klastrach.

$\lambda$

Rozszerzenie na metody jądra lub sieci neuronowe dla klastrowania nieliniowego jest proste.

bayerj
źródło

Czy istnieją jakieś algorytmy klastrowania oparte na braku odległości?

Odpowiedzi: