Clustering ogromnej przestrzeni wektorowej

Question

Przeprowadzam kilka testów skupiających dużą liczbę bardzo dużych rzadkich wektorów reprezentujących częstotliwościowo-odwrotne częstotliwości dokumentów różnych dokumentów hipertekstowych. Jaki algorytm zaproponujesz do grupowania tych danych, biorąc pod uwagę proporcje zbioru danych? Wymiar wektorów będzie> 3 · 10 , a liczba wektorów może wynosić około 10 . Przyjrzałem się algorytmom dbscan i optyki. Liczba klastrów nie jest znana. A indeks przestrzenny o tak dużej wymiarowości wydaje się skomplikowany.

Answer 1

Osiągnąłem prawie tak dobre wyniki z prostym skupiskiem K, jak prawie wszystkim, i jest zdecydowanie szybsze niż większość alternatyw. Osiągnąłem również dobre wyniki w przypadku aglomeracji parami, ale jest to trochę wolniej. W przypadku K-średnich musisz zacząć od pewnej szacowanej liczby klastrów, ale możesz dostosować ją algorytmicznie w miarę upływu czasu. Jeśli znajdziesz dwa klastry ze środkami, które są zbyt blisko siebie, zmniejszasz liczbę klastrów. Jeśli znajdziesz klastry o zbyt dużym zakresie odmian, wypróbuj więcej klastrów. Stwierdziłem, że sqrt (N) jest rozsądnym punktem wyjścia - ale zwykle zaczynam od więcej niż 10^7 dokumentów niż 10^9. W przypadku 10^9 może to nieco zmniejszyć.

Jeśli jednak było to zależne ode mnie, to bardzo ciężko by mi było zacząć od zredukowania wymiarów za pomocą czegoś takiego jak Landmark MDS, , a następnie podczas łączenia w klastry.

Answer 2

Drzewa decyzyjne są popularne do wydajnej pracy w przestrzeniach wielowymiarowych. Sprawdź listę Clustering Via Decision Tree Construction.

Ponadto, Randomized Forests są wyjątkowo wydajnymi uczniami i OpenCV implementation exists, jeśli chcesz się z nimi bawić.

Answer 3

Słyszałem, że semantic hashing osiąga doskonałe wyniki. Jednak głębokie sieci przekonań są dość trudne do wdrożenia. Możesz spróbować min haszowania (to jest podejście probabilistyczne) lub locality sensistive hashing for euclidean spaces.

Generalnie, klastrowanie w tak dużych przestrzeniach wymiarowych jest trudne z powodu klątwy wymiarów i faktu, że większość przedmiotów ma do siebie podobne odległości. Standardowe podejścia, takie jak K-średnie, mogą zadziałać, jeśli wcześniej zmniejszysz wymiarowość za pomocą SOM lub PCA.

Answer 4

Gdy grupowanie danych zawsze będę próbować przynajmniej te dwa algorytmy w następującej kolejności:

1. K oznacza: spróbuj szczypanie wyniki w jak największym stopniu. Jeśli potrafisz sprawić, by K-Means działał dla ciebie i zapewniał przyzwoite wyniki, prawie na pewno nie zrobisz tego lepiej, gdy będzie jakikolwiek inny algorytm.

2. Maksymalizacja oczekiwań: algorytm K-średnich został opracowany jako tania i dobra alternatywa dla algorytmu EM. Algorytm EM jest trudniejszy do zrozumienia i droższy do obliczenia, ale wyniki EM są doskonałe. Możesz dowiedzieć się więcej o EM http://en.wikipedia.org/wiki/Expectation-maximization_algorithm. Jest to implementacja OpenCV EM: http://opencv.willowgarage.com/documentation/expectation-maximization.html

Jeżeli wyniki żadna z tych dwóch są zadowalające, chciałbym zacząć szukać gdzie indziej, ale nie dopóki nie próbowałem obu.