algorytm grupowania dla danych niewymiarowych

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!

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.

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.

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:

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)$

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

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