algorytm grupowania dla danych niewymiarowych

12

Mam zestaw danych zawierający tysiące punktów i sposób pomiaru odległości między dowolnymi dwoma punktami, ale punkty danych nie mają wymiarów. Chcę algorytmu, aby znaleźć centra klastrów w tym zestawie danych. Wyobrażam sobie, że ponieważ dane nie mają wymiarów, centrum klastrów może składać się z kilku punktów danych i tolerancji, a członkostwo w klastrze może być określone przez średnią odległość punktu danych do każdego punktu danych w centrum klastra.

proszę wybacz mi, jeśli to pytanie ma dobrze znane rozwiązanie, niewiele wiem o tego rodzaju problemach! moje (bardzo ograniczone) badania ujawniły tylko algorytmy grupowania danych wymiarowych, ale z góry przepraszam, jeśli coś przeoczyłem.

Dziękuję Ci!

machine-learning lg.learning clustering

— puszka farby
źródło

Dlaczego niewymiarowość czyni ten problem wyjątkowym?

— Raphael

1

Niektóre algorytmy, które widziałem dla grupowania (tak naprawdę tylko średnie k), wymagają generowania losowych punktów danych jako zarodków, co nie jest możliwe w przypadku danych bezwymiarowych. Tak więc szczególnym wymogiem jest, aby centra klastra były reprezentowane przez zbiór istniejących punktów danych (być może ważonych).

— paintcan

15

Jeśli funkcja odległości jest metryką, możesz zastosować grupowanie centrum (w którym maksymalny promień kulki jest zminimalizowany) lub -klastry medialne (co minimalizuje sumę odległości do centrów gromady). Grupowanie centre jest łatwe: wystarczy wybrać najdalsze punkty, a otrzymasz 2-przybliżenie poprzez nierówność trójkąta (jest to stary wynik z powodu Gonzaleza). $k$ $k$ $k$ $k$

W przypadku klastrów medialnych było dużo pracy, zbyt wiele do przejrzenia tutaj. Michael Shindler z UCLA ma fajną ankietę na temat głównych pomysłów. $k$

Oba te problemy są na ogół trudne dla NP i trudno je zbliżyć do dowolnego czynnika. Zauważ, że jeśli porzucisz warunek bycia metryką, sytuacja stanie się znacznie gorsza pod względem zbliżalności.

Innym, bardziej heurystycznym podejściem, które może być odpowiednie dla twojej aplikacji, jest zastosowanie techniki takiej jak MDS (skalowanie wielowymiarowe) w celu osadzenia macierzy odległości w przestrzeni euklidesowej, a następnie użycie jednej z wielu różnych metod euklidesowych (lub nawet średnich) ). Jeśli masz pewność, że twoja funkcja odległości jest miarą, możesz wykonać nieco bardziej inteligentne osadzenie w przestrzeni euklidesowej i uzyskać sprawdzalną (choć słabą) gwarancję jakości swojej odpowiedzi. $k$

Ostatecznie, podobnie jak w przypadku większości problemów związanych z klastrowaniem, ostateczny wybór zależy od aplikacji, wielkości danych i tak dalej.

— Suresh Venkat
źródło

3

Dziękujemy za szybki i przejrzysty przegląd. Ustalenie, czy odpowiedziałeś na moje pytanie, zajmie mi przynajmniej kilka dni. Wygląda na to, że muszę się wiele nauczyć, zanim wystarczająco zrozumiem mój problem :)

— paintcan

5

Istnieje również klaster korelacji , który jako informacje wejściowe dla każdej pary elementów wskazuje, czy należą one do tego samego klastra, czy do innych klastrów.

— Warren Schudy
źródło

tak, to kolejny dobry przykład. I oczywiście Warren jest w tym ekspertem! Nie wiem jednak, czy dane wejściowe OP były +/-, czy można je przekonwertować za pomocą progów. jeśli tak, to z pewnością jest to opłacalna opcja.

— Suresh Venkat

5

Jeśli szukasz dobrej wydajności empirycznej, algorytm propagacji powinowactwa zwykle działa lepiej niż mediany k. Kod jest dostępny w kilku językach, a publikacje opisujące algorytm bardziej szczegółowo znajdują się tutaj: http://www.psi.toronto.edu/index.php?q=affinity%20propagation

Celem, który próbuje zmaksymalizować, jest:

\sum_{ja} s (ja, {do}_{ja})

$\sum_{i} s(i, c_i)$

gdzie jest miarą podobieństwa określono między parami punktów (np ujemnej odległości) i daje klaster należy. Istnieje jeden dodatkowy parametr podany w który kontroluje, czy wolisz duże czy małe klastry. $s$ $c_i \in \mathbf{c}$ $i$ $s(i, i)$

— dan_x
źródło

5

Twoje pytanie wydaje się sugerować, że szukasz algorytmu z przyzwoitym czasem obliczeniowym. Biorąc pod uwagę rozmiar twoich wierzchołków (lub punktów), stworzyłbyś ważoną reprezentację graficzną twoich danych i używałeś algorytmu klastrowania Markowa (MCL) do grupowania wykresu.

http://www.micans.org/mcl/

MCL opiera się na losowych spacerach przez ważone i nieważone wykresy w celu znalezienia gęstych podrozdziałów. Jest w stanie obsługiwać duże wykresy i był używany w wielu dobrze znanych, dobrze używanych programach bioinformatycznych (takich jak BLAST). -Boucher

— Christina Boucher
źródło

1

Rozważ algorytm k-najbliższego sąsiada .

— Raphael
źródło

Raphael, algorytm k-NN nie jest tak naprawdę algorytmem grupowania, prawda? chyba że wielokrotnie wyciągasz k sąsiadów węzła?

— Suresh Venkat

Rysujemy krawędź między węzłami, które znajdują się w zestawach najbliższych węzłów. Na wynikowym wykresie kliki (prawie kliki) powinny być pewnego rodzaju klastrami. Uznałem, że skoro budujemy wykres, identyfikacja tych klik nie powinna być zbyt trudna, ale nie do końca to przemyślałem.

k

$k$

— Raphael