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?
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 jestOdpowiedzi:
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.
źródło
Yes, you can use it
. (Czy pomysł na konwersję cosinusa na odległość euklidesową jest podobny do mojej odpowiedzi ?)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:
ź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 max
w przeciwieństwie doarg min
.źródło