Średnie K dla podobieństw cosinusa vs. odległość euklidesowa (LSA)

Używam ukrytej analizy semantycznej do reprezentowania zbioru dokumentów w przestrzeni o niższych wymiarach. Chcę zgrupować te dokumenty w dwie grupy za pomocą k-średnich.

Kilka lat temu zrobiłem to, używając gensim Pythona i pisząc własny algorytm k-średnich. Określiłem centroidy gromadowe na podstawie odległości euklidesowej, ale następnie zgrupowałem każdy dokument na podstawie podobieństwa cosinus do centroidu. Wydawało się, że działa całkiem dobrze.

Teraz próbuję to zrobić na znacznie większym zbiorze dokumentów. Środki K nie są zbieżne i zastanawiam się, czy to błąd w moim kodzie. Niedawno czytałem, że nie należy grupować za pomocą podobieństwa kosinusowego, ponieważ k-znaczy działa tylko na odległości euklidesowej. Chociaż, jak wspomniałem, w moim mniejszym przypadku testowym działało dobrze.

Teraz natrafiam na to na stronie Wikipedii LSA :

Dokumenty i reprezentacje wektorów terminowych można grupować za pomocą tradycyjnych algorytmów grupowania, takich jak k-średnie, stosując miary podobieństwa, takie jak cosinus.

Więc co to jest? Czy mogę użyć podobieństwa cosinusowego czy nie?

— Jeff
źródło

Ten temat rzeczywiście długo pozostaje na tej stronie. Właśnie ostatnie pytanie: stats.stackexchange.com/q/120085/3277 (zobacz dalsze linki tam). Bardzo interesujące jest to, jak zaimplementowałeś k-znaczy, który przetwarza cosinusy. Jeśli opisujesz swój algorytm w swoim pytaniu, pomoże to ludziom na nie odpowiedzieć.

— ttnphns

@ttnphns Rzeczywiście wygenerowałem centroidy gromadowe, używając odległości euklidesowej (średnia każdego wymiaru). Jednak następnie przypisałem każdy dokument do klastra na podstawie podobieństwa cosinus, a nie odległości euklidesowej.

— Jeff

I then assigned each document to a cluster based on cosine similarity- Cosinus między doktorem a centroidem? Po przypisaniu wszystkich dokumentów aktualizujesz centroidy w zwykły (euklidesowy) sposób, ponieważ znane są współrzędne dokumentów w przestrzeni. Czy tak jest

— ttnphns

Tylko jeśli suma wartości kwadratowych dla każdego dokumentu w zestawie danych jest taka sama , twoje podejście będzie działać i zawsze będzie zbieżne. Ponieważ w tym przypadku (to znaczy wszystkie tej samej długości) cosinusy między centroidami i dokumentami będą ściśle monotoniczne z euklidesowymi odległościami między centroidami i dokumentami. Będzie to jednak oznaczało, że użycie cosinusów do przypisania jest niepotrzebne, a następnie możesz użyć standardowego przypisania algorytmu k-średnich na podstawie odległości euklidesowych.

h

$h$

— ttnphns

Zaczynam myśleć, że możesz szukać k-średnich wykonanych na kuli, a nie w przestrzeni. K-kąt oznacza, że tak powiem. Przypuszczam, że jest to możliwe, ale nigdy tego nie czytałem ani nie używałem.

— ttnphns

Odpowiedzi:

Tak, możesz go użyć. Problem polega na tym, że podobieństwo cosinusa nie jest odległością, dlatego nazywa się je podobieństwem. Niemniej jednak można go przeliczyć na odległość, jak wyjaśniono tutaj .

W rzeczywistości możesz po prostu użyć dowolnej odległości. Bardzo ładnym badaniem właściwości funkcji odległości w przestrzeniach wielowymiarowych (jak to zwykle ma miejsce w przypadku wyszukiwania informacji) jest O zaskakującym zachowaniu wskaźników odległości w przestrzeni wielowymiarowej . Nie porównuje jednak euklidesa z cosinusem.

Natknąłem się na to badanie, w którym twierdzą, że w przestrzeniach o dużych wymiarach obie odległości zachowują się podobnie.

— jpmuc
źródło

Ta odpowiedź może być dobra, jeśli opisuje, w jaki sposób Yes, you can use it . (Czy pomysł na konwersję cosinusa na odległość euklidesową jest podobny do mojej odpowiedzi ?)

— ttnphns

Moje rozumienie k-średnich jest inne. Niekoniecznie ogranicza się to do odległości euklidesowej ( stat.uni-muenchen.de/~leisch/papers/Leisch-2006.pdf ). Zobacz także moje drugie odniesienie lub ten pakiet R ( cran.r-project.org/web/packages/cclust/cclust.pdf ). Miałem na myśli to naprawdę jak na stronie wikipedii. Wystarczy tylko funkcja odległości. Nazywają to „podobieństwem kątowym”.

— jpmuc

Być może (i dzięki za udostępnienie artykułu!). Ale wtedy wszystkie takie „modyfikacje” średnich k, które różnią się od średnich k tym, że definiują centroid nie jako średnią arytmetyczną w przestrzeni euklidesowej, nie powinny być nazywane środkami k.

— ttnphns

Odległość euklidesowa nie jest odpowiednia do porównywania dokumentów lub grup dokumentów. Podczas porównywania dokumentów jednym kluczowym zagadnieniem jest normalizacja według długości dokumentu. Podobieństwo cosinus osiąga tego rodzaju normalizację, ale odległość euklidesowa nie. Ponadto dokumenty są często modelowane jako wielomianowe rozkłady prawdopodobieństwa (tzw. Worek słów). Podobieństwo cosinus jest przybliżeniem do rozbieżności JS, która jest statystycznie uzasadnioną metodą podobieństwa. Jednym z kluczowych problemów z dokumentami i cosinusem jest to, że należy zastosować odpowiednią normalizację tf-idf do zliczeń. Jeśli używasz gensim do uzyskania reprezentacji LSA, gensim już to robi.

Inną przydatną obserwacją dla twojego przypadku użycia 2 klastrów jest to, że możesz uzyskać dobrą nielosową inicjalizację, ponieważ LSA to tylko SVD. Robisz to w następujący sposób:

Weź tylko pierwszy komponent każdego dokumentu (zakładając, że pierwszy komponent jest najwyższym wektorem osobliwym).
Posortuj te wartości, śledząc identyfikatory dokumentów dla każdej wartości.
klaster 1 = identyfikatory dokumentów odpowiadające najwyższym np. 1000 (lub więcej) wartościom
klaster 2 = identyfikatory dokumentów odpowiadające dolnym, np. 1000 (lub więcej) wartościom
wystarczy uśrednić wektory dla każdej grupy i znormalizować według długości wektora.
Teraz zastosuj k-średnie do tej inicjalizacji. Oznacza to po prostu iterację (1) przypisania dokumentów do najbliższego najbliższego środka masy i (2) uśrednienia i normalizacji nowych centroidów po zmianie przypisania

— Stefan Savev
źródło

Tak, ta sama aktualizacja środka ciężkości według średniej wektorowej działa.

Zobacz m = 1 przypadek w sekcji 2.2 tego dokumentu . w to wagi, a wszystkie wagi to 1 dla podstawowych algorytmów k-średnich.

W pracy wykorzystano właściwości nierówności Cauchy'ego-Schwartza do ustalenia warunku, który minimalizuje funkcję kosztu dla średniej k.

Pamiętaj również, że podobieństwo cosinus nie jest odległością wektorową. Cosinus niezadowolenie jest. (Powinno to być dobre wyszukiwane hasło.) Dlatego podczas aktualizacji partycji szukasz, arg maxw przeciwieństwie do arg min.

— Argyll
źródło