Jakie są wypróbowane i prawdziwe algorytmy sugerowania powiązanych artykułów?

Question

Bardzo typowa sytuacja, chciałbym się założyć. Masz bloga lub serwis informacyjny i masz mnóstwo artykułów lub blagów lub cokolwiek je nazwiesz i chcesz, na dole każdego sugerować inne, które wydają się być powiązane.

Przyjmijmy bardzo mało metadanych dotyczących każdej pozycji. To znaczy, brak tagów, kategorii. Traktuj jak jedną dużą kroplę tekstu, w tym tytuł i nazwisko autora.

W jaki sposób można znaleźć możliwie powiązane dokumenty?

Jestem raczej zainteresowany aktualnym algorytmem, a nie gotowymi rozwiązaniami, chociaż byłbym w porządku, patrząc na coś zaimplementowanego w Ruby lub Pythonie, lub polegając na mysql lub pgsql.

edycja: aktualna odpowiedź jest całkiem dobra, ale chciałbym zobaczyć więcej. Może jakiś naprawdę dobry przykład kodu.

Answer 1

To bardzo duży temat - oprócz odpowiedzi, które ludzie wymieniają tutaj, polecam wyśledzenie sylabusów dla kilku klas pobierania informacji i sprawdzenie podręczników i dokumentów przeznaczonych dla nich. To powiedziawszy, oto krótki przegląd z moich własnych dni szkolnych:

Najprostsze podejście nazywa się bag of words. Każdy dokument jest zredukowany do rzadkiego wektora par {word: wordcount} i możesz rzucić klasyfikator NaiveBayes (lub inny) na zestaw wektorów, który reprezentuje twój zestaw dokumentów, lub oblicz wyniki podobieństwa między każdą torbą i każdą inną torbą (to jest nazywana klasyfikacją k-najbliższego sąsiada). KNN jest szybki do wyszukiwania, ale wymaga macierzy wyników O (n^2); jednak na blogu n nie jest zbyt duży. Dla czegoś wielkości dużej gazety, KNN szybko staje się niepraktyczny, więc czasami algorytm klasyfikacji w locie jest lepszy. W takim przypadku możesz wziąć pod uwagę ranking support vector machine. Maszyny SVM są zgrabne, ponieważ nie ograniczają cię do podobieństwa liniowego i wciąż są dość szybkie.

Stemming jest częstym krokiem preprocesyjnym dla technik work-of-words; polega to na zmniejszaniu morfologicznie powiązanych słów, takich jak "kot" i "koty", "Bob" i "Bob", lub "podobnie" i "podobnie", aż do ich korzeni przed obliczeniem worka słów. Istnieje wiele różnych algorytmów rozstrzygania; strona Wikipedii zawiera linki do kilku implementacji.

Jeśli podobieństwo w woreczku słów nie jest wystarczająco dobre, można je zrównać do podobieństwa w woreczku N-gramów, w którym tworzy się wektor reprezentujący dokument oparty na parach lub potrójnych słowach . (Możesz użyć 4-tek, a nawet większych krotek, ale w praktyce to niewiele pomoże). Ma to tę wadę, że generuje dużo większe wektory, a klasyfikacja będzie wymagała więcej pracy, ale dopasowania, które otrzymasz, będą znacznie bliższe składniowo. OTOH, prawdopodobnie nie potrzebujesz tego dla semantycznego podobieństwa; to jest lepsze dla rzeczy takich jak wykrywanie plagiatu. Można również zastosować redukcję dokumentu do lekkich parse drzew (istnieją algorytmy klasyfikacji drzew), ale jest to bardziej użyteczne w przypadku problemów takich jak problem autorstwa ("dany dokument o nieznanym pochodzeniu, kto go napisał?").).

Być może bardziej przydatny w przypadku użycia jest eksploracja koncepcji, która obejmuje odwzorowywanie słów na pojęcia (przy użyciu tezaurusa, takiego jak WordNet), a następnie klasyfikowanie dokumentów na podstawie podobieństwa między używanymi pojęciami. Często kończy się to bardziej wydajną niż opartą na słowie klasyfikacją podobieństwa, ponieważ odwzorowywanie słów do pojęć ma charakter redukcyjny, ale etap przetwarzania wstępnego może być dość czasochłonny.

Wreszcie jest discourse parsing, który obejmuje analizowanie dokumentów dla ich struktury semantycznej; możesz uruchamiać klasyfikatory podobieństwa na drzewach dyskursu w taki sam sposób, jak w przypadku porcji dokumentów.

Obejmują one generowanie metadanych z nieustrukturyzowanego tekstu; wykonywanie bezpośrednich porównań między surowymi blokami tekstu jest trudne, więc ludzie najpierw przetwarzają dokumenty w metadane.

Answer 2

Jakiś czas temu zaimplementowałem coś podobnego. Być może ten pomysł jest już nieaktualny, ale mam nadzieję, że może pomóc.

Uruchomiłem stronę ASP 3.0 do programowania typowych zadań i zacząłem od tej zasady: użytkownik ma wątpliwości i pozostanie na stronie internetowej, dopóki może znaleźć interesujące treści na ten temat.

Po pojawieniu się użytkownika uruchomiłem obiekt ASP 3.0 Session i nagrałem całą nawigację użytkownika, podobnie jak połączoną listę. Na Session.OnEnd razie biorę pierwszy link, szukać następnego linku i zwiększany kolumnę licznik jak:

<Article Title="Cookie problem A"> 
    <NextPage Title="Cookie problem B" Count="5" /> 
    <NextPage Title="Cookie problem C" Count="2" /> 
</Article> 

Tak więc, aby sprawdzić związanych artykuły miałem tylko do listy top nNextPage podmioty, zamówione przez licznik kolumny malejąco .

Answer 3

Jest to typowy przypadek Document Classification, który jest badany w każdej klasie uczenia maszynowego. Jeśli lubisz statystyki, matematykę i informatykę, polecam zapoznać się z metodami bez nadzoru, takimi jak kmeans++, Bayesian methods i LDA. W szczególności metody Bayesa to: pretty good, czego szukasz, ich jedynym problemem jest powolność (ale jeśli nie prowadzisz bardzo dużej witryny, to nie powinno ci to zbytnio przeszkadzać).

Korzystając z bardziej praktycznego i mniej teoretycznego podejścia, polecam zapoznać się z przykładami wspaniałych kodów, przedstawiającymi this i this other.

Answer 4

Mała wyszukiwarka modelu przestrzeni kosmicznej w Ruby. Podstawową ideą jest to, że dwa dokumenty są powiązane, jeśli zawierają te same słowa. Liczymy więc występowanie słów w każdym dokumencie, a następnie obliczamy cosinus pomiędzy tymi wektorami (każde wyrażenie ma ustalony indeks, jeśli wydaje się, że jest 1 w tym indeksie, jeśli nie jest zero). Cosine będzie miała wartość 1,0, jeśli dwa dokumenty mają wszystkie terminy wspólne, a 0.0, jeśli nie mają wspólnych terminów. Możesz bezpośrednio przetłumaczyć to na% wartości.

terms = Hash.new{|h,k|h[k]=h.size} 
docs = DATA.collect { |line| 
    name = line.match(/^\d+/) 
    words = line.downcase.scan(/[a-z]+/) 
    vector = [] 
    words.each { |word| vector[terms[word]] = 1 } 
    {:name=>name,:vector=>vector} 
} 
current = docs.first # or any other 
docs.sort_by { |doc| 
    # assume we have defined cosine on arrays 
    doc[:vector].cosine(current[:vector]) 
} 
related = docs[1..5].collect{|doc|doc[:name]} 

puts related 

__END__ 
0 Human machine interface for Lab ABC computer applications 
1 A survey of user opinion of computer system response time 
2 The EPS user interface management system 
3 System and human system engineering testing of EPS 
4 Relation of user-perceived response time to error measurement 
5 The generation of random, binary, unordered trees 
6 The intersection graph of paths in trees 
7 Graph minors IV: Widths of trees and well-quasi-ordering 
8 Graph minors: A survey 

definicja Array#cosine pozostawiamy jako ćwiczenie dla czytelnika (powinien poradzić sobie z wartościami zerowymi i różnych długościach, ale dobrze, że mamy Array#zip prawda?)

BTW, przykładowe dokumenty są brane z artykułu SVD autorstwa Deerwester'a i innych :)

Answer 5

Powinieneś przeczytać książkę "Programowanie kolektywnej inteligencji: tworzenie inteligentnych aplikacji Web 2.0" (ISBN 0596529325)!

Dla pewnej metody i kodu: Najpierw zadaj sobie pytanie, czy chcesz znaleźć bezpośrednie podobieństwa na podstawie dopasowań słów, czy chcesz wyświetlić podobne artykuły, które nie mają bezpośredniego związku z bieżącym, ale należą do tego samego klastra artykułów.

Zobacz Cluster analysis/Partitional clustering.

Bardzo prosty (ale teoretyczna i powolny) metoda na znalezienie bezpośrednie podobieństwa byłoby:

Preprocesuj:

1. Store płaską listę słów za artykuł (nie usunąć duplikaty słów).
2. "Łączenie krzyżowe" artykułów: zliczanie słów w artykule A, które pasują do tego samego słowa w artykule B. Macie teraz macierz int word_matches[narticles][narticles] (nie należy tego przechowywać tak, podobieństwo A-> B jest takie samo jak B -> A, więc rzadka macierz oszczędza prawie połowę miejsca).
3. Normalizacja wartości parametru word_matches ma wartość 0..1! (Znalezienie max liczbę, a następnie podzielić dowolną liczbę od tego) - należy przechowywać pływaków tam nie ints;)

Znajdź podobne artykuły:

1. wybrać artykuły xz najwyższych meczów z word_matches