Jakie są standardowe sposoby obliczania odległości między dokumentami?


34

Kiedy mówię „dokument”, mam na myśli strony internetowe, takie jak artykuły z Wikipedii i wiadomości. Wolę odpowiedzi podające albo waniliowe leksykalne wskaźniki odległości, albo najnowocześniejsze semantyczne mierniki odległości, z silniejszą preferencją dla tych ostatnich.

Odpowiedzi:


48

Istnieje wiele różnych sposobów radzenia sobie z tym, w zależności od tego, ile dokładnie informacji semantycznych chcesz zachować i jak łatwo tokenizować dokumenty (dokumenty html byłyby prawdopodobnie dość trudne do tokenizacji, ale możesz zrobić coś z tagami i kontekstem .)

Niektóre z nich zostały wspomniane przez ffriend, a wektory akapitowe od user1133029 są naprawdę solidne, ale właśnie pomyślałem, że zagłębię się w plusy i minusy różnych podejść.

  • Odległość kosinusowa - wypróbowana prawdziwa odległość kosinusowa jest prawdopodobnie najczęściej stosowaną miarą odległości używaną ogólnie w wielu domenach. To powiedziawszy, jest bardzo mało informacji w odległości cosinusów, które mogą być faktycznie odwzorowane z powrotem na wszystko semantyczne, co wydaje się nie idealne w tej sytuacji.
  • Levenshtein Distance - Znany również jako edit distance, jest zwykle używany tylko na poziomie pojedynczego tokena (słowa, bigramy itp.). Zasadniczo nie poleciłbym tej metryki, ponieważ nie tylko odrzuca ona informacje semantyczne, ale również ma tendencję do traktowania bardzo różnych zmian słów bardzo podobnie, ale jest to niezwykle powszechna metryka dla tego rodzaju rzeczy
  • LSA - jest częścią dużego arsenału technik, jeśli chodzi o ocenę podobieństwa dokumentów o nazwie topic modeling. LSA niedawno wyszła z mody i z mojego doświadczenia wynika, że ​​nie jest to najsilniejsze podejście do modelowania tematów, ale jest stosunkowo łatwe do wdrożenia i ma kilka implementacji typu open source
  • LDA - Jest to również technika stosowana topic modeling, ale różni się od LSAtego, że faktycznie uczy wewnętrznych reprezentacji, które wydają się być bardziej płynne i intuicyjne. Ogólnie rzecz biorąc, wyniki, które otrzymujesz, LDAsą lepsze do modelowania podobieństwa dokumentów niż LSA, ale nie są tak dobre do nauki, jak silnie rozróżniać tematy.
  • Pachinko Allocation - To naprawdę fajne rozszerzenie na szczycie LDA. Ogólnie rzecz biorąc, jest to tylko znacznie ulepszona wersja LDA, z jedynym mankamentem w tym, że szkolenie zajmuje trochę więcej czasu, a implementacje typu open source są nieco trudniejsze do zdobycia
  • word2vec - Google pracuje nad szeregiem technik inteligentnego sprowadzania słów i dokumentów do bardziej rozsądnych wektorów niż rzadkie wektory uzyskane za pomocą takich technik, jak Count Vectorizersi TF-IDF. Word2vec jest świetny, ponieważ ma wiele implementacji typu open source. Po uzyskaniu wektora można na nim zastosować dowolną inną metrykę podobieństwa (np. Odległość cosinusowa) ze znacznie większą skutecznością.
  • doc2vec - Znany również jako paragraph vectors, jest to najnowszy i największy z serii artykułów Google, analizujących gęstą reprezentację wektorową dokumentów. gensimBiblioteki w python ma implementacja word2vecże jest na tyle prosta, że można go całkiem rozsądnie być użyta do budowy doc2vec, ale upewnij się, aby zachować licencję na uwadze, jeśli chcesz iść tą drogą

Mam nadzieję, że to pomoże, daj mi znać, jeśli masz jakieś pytania.


6

Istnieje wiele semantycznych miar odległości, z których każda ma swoje zalety i wady. Oto tylko kilka z nich:

  • odległość cosinus , iloczyn wewnętrzny między wektorami cech dokumentu;
  • LSA , inny model wektorowy, ale wykorzystujący SVD do usuwania szumów z oryginalnej matrycy dokumentów-terminów;
  • Oparty na WordNet , zweryfikowany przez człowieka, choć trudny do rozszerzenia.

Zacznij od najprostszego podejścia, a następnie przejdź dalej w oparciu o problemy dotyczące konkretnego przypadku.


1
Zauważ, że robiąc LSA, zwykle używasz odległości cosinus na rzutach LSA oryginalnego zestawu danych. Aby wyjaśnic.
Simon

6

Empirycznie stwierdziłem, że LSA za każdym razem znacznie przewyższa LDA i na każdym zestawie danych, w którym go wypróbowałem. Rozmawiałem z innymi ludźmi, którzy powiedzieli to samo. Został również wykorzystany do wygrania wielu konkursów SemEval w celu pomiaru podobieństwa semantycznego między dokumentami, często w połączeniu z miarą opartą na słowie, więc nie powiedziałbym, że wychodzi z mody lub zdecydowanie jest gorszy od LDA, co jest lepsze za modelowanie tematów, a nie semantyczne podobieństwo w moim doświadczeniu, w przeciwieństwie do tego, co stwierdzili niektórzy respondenci.

Jeśli używasz gensim (biblioteka python), ma on LSA, LDA i word2vec, więc możesz łatwo porównać 3. doc2vec to fajny pomysł, ale nie skaluje się zbyt dobrze i prawdopodobnie będziesz musiał go zaimplementować tak jak ja nieświadomy żadnych implementacji typu open source. Nie skaluje się dobrze, ponieważ dla każdego dokumentu należy zbudować nowy i oddzielny model przy użyciu SGD, algorytmu powolnego uczenia maszynowego. Ale prawdopodobnie da Ci najdokładniejsze wyniki. LSA i LDA również nie skalują się dobrze (jednak word2vec robi to), ogólnie LDA skaluje się gorzej. Implementacje Gensim są jednak bardzo szybkie, ponieważ wykorzystuje iteracyjne SVD.

Jeszcze jedna uwaga, jeśli użyjesz word2vec, nadal będziesz musiał określić sposób komponowania wektorów z dokumentów, ponieważ daje to inny wektor na słowo. Najprostszym sposobem na to jest normalizacja każdego wektora i wzięcie średniej ze wszystkich wektorów słów w dokumencie lub przyjęcie średniej ważonej przez ważenie idf każdego słowa. Nie jest to tak proste, jak użycie słowa „word2vec”, trzeba będzie zrobić coś więcej, aby obliczyć podobieństwo dokumentu.

Osobiście wybrałbym LSA, ponieważ widziałem, jak działa dobrze empirycznie, a biblioteka gensim skaluje się bardzo dobrze. Jednak nie ma bezpłatnego lunchu, więc najlepiej wypróbuj każdą metodę i sprawdź, która z nich jest lepsza dla Twoich danych.


Jak dokładnie użyłeś LSA? Warto zauważyć, że LDA jest w rzeczywistości dość cienkim opakowaniem wokół LSA (to pLSA z dirichletem wcześniej), który wykazano empirycznie, że znacznie zwiększa uogólnienie. Prawie na pewno zobaczysz lepsze trafności z LSA, ale ogólnie jest to wynikiem nadmiernego dopasowania, co jest bardzo znaczącym problemem z LSA. Co dokładnie rozumiesz przez skalowanie tutaj? doc2vec tak naprawdę nie wymaga nowego modelu dla każdego dokumentu, a do obliczeń nie ma zauważalnej różnicy między LSA i LDA, ponieważ oba są bardzo skalowalne.
Slater Victoroff,

Nie zaobserwowałem nadmiernego dopasowania do LSA i, jak powiedziałem, spotkałem wiele innych osób, które widziały lepsze wyniki niż LDA. Widziałem także LSA używany w wielu zwycięskich pracach w konkursach półrocznych, nigdy nie widziałem LDA używanego w zwycięskim konkursie. To konferencja akademicka służąca porównywaniu podobieństwa semantycznego między dokumentami, więc zakładam, że wiedzą, co robią. Doc2vec, jeśli masz na myśli implementację wektora akapitu Mikołowa, wykonuje SGD na każdym dokumencie osobno. To jest bardzo wolne.
Simon

@SlaterVictoroff Myślę, że to przesadzanie z twierdzeniem, że to za dużo. Wiadomo, że LDA jest słaba w przypadku wyszukiwania / wyszukiwania informacji i rekomendacji, empirycznie wykazano, że LSA działa znacznie lepiej i to odpowiada mojemu własnemu doświadczeniu, ponieważ lubię weryfikować te ustalenia na podstawie własnych danych. Wersje Doc2Vec wykonują spadek gradientu na dokument, zależy to od algorytmu używanego w Doc2Vec, ponieważ ogólnie odnosi się to do wielu różnych algorytmów.
Simon

3

Najnowocześniejsze wydają się być „wektory akapitowe” wprowadzone w ostatnim artykule: http://cs.stanford.edu/~quocle/paragraph_vector.pdf . Odległość cosinus / euklidesowa między wektorami akapitowymi prawdopodobnie działałaby lepiej niż jakiekolwiek inne podejście. Prawdopodobnie nie jest to jeszcze możliwe ze względu na brak implementacji open source.

Kolejną najlepszą rzeczą jest odległość cosinus między wektorami LSA lub odległość cosinus między surowymi wektorami BOW. Czasami lepiej jest wybrać różne schematy ważenia, takie jak TF-IDF.


Zwróć uwagę na moje komentarze poniżej dotyczące skalowalności wektora akapitu. Ta technika wygląda bardzo obiecująco, ale jest trudna do wdrożenia i nie skaluje się wcale, ponieważ robisz osobny SGD dla każdego dokumentu, co jest bardzo kosztowne, jeśli dobrze pamiętam papier
Simon

1

Przydatne jest posiadanie w pakiecie narzędzi rodziny algorytmów mieszających wrażliwych na lokalizację . Ta rodzina wcale nie jest semantyczna. Właściwie uważa się, że tekst jest sekwencją bitów. Uważam, że jest to przydatne w brudnych zestawach danych, gdy ten sam tekst pojawia się wiele razy z niewielkimi różnicami.

Możesz użyć ssdeep (który jest oparty na skrócie Nilsimsa ) do identyfikacji takich dokumentów. Ssdeep został pierwotnie zaplanowany dla domeny spamu. Spamerzy często dokonują niewielkich zmian w wiadomości (dodają spację), aby zapobiec wykryciu przez dokładny podpis (np. Md5 ).

Ponieważ wiele wersji prawie tego samego dokumentu w tym samym zbiorze danych spowoduje spustoszenie w metodach statystycznych, które zostaną na nim zastosowane, przeprowadzenie takiego czyszczenia może być bardzo korzystne.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.