Cosa sono là fuori gli algoritmi provati e veri per suggerire che articoli correlati sono là fuori?

Question

Situazione abbastanza comune, scommetterei. Hai un blog o un sito di notizie e hai molti articoli o blag o qualunque cosa li chiami e vuoi, in fondo a ciascuno, suggerire ad altri che sembrano essere correlati.

Supponiamo che pochissimi metadati su ogni articolo. Cioè, nessun tag, categorie. Tratta come una grande chiazza di testo, incluso il titolo e il nome dell'autore.

Come si fa a trovare i documenti forse correlati?

Sono piuttosto interessato all'algoritmo effettivo, non alle soluzioni pronte, anche se stavo bene a dare un'occhiata a qualcosa implementato in Ruby o Python, o fare affidamento su MySQL o PGSQL.

modificare: La risposta attuale è abbastanza buona ma mi piacerebbe vedere di più. Forse qualche codice di esempio davvero nudo per una cosa o due.

Answer 1

Questo è un argomento piuttosto grande - oltre alle risposte che le persone vengono qui, consiglio di rintracciare i sillabi per un paio di lezioni di recupero delle informazioni e di controllare i libri di testo e gli articoli assegnati per loro. Detto questo, ecco una breve panoramica dei miei giorni di scuola di laurea:

L'approccio più semplice è chiamato a sacchetto di parole. Ogni documento è ridotto a un vettore scarso di {word: wordcount} coppie, e puoi lanciare un classificatore NaiveBayes (o qualche altro) sul set di vettori che rappresenta il tuo set di documenti o calcolare i punteggi di somiglianza tra ogni borsa e ogni altra borsa (questo si chiama classificazione K-Neare-Neigh-Neighbour). KNN è veloce per la ricerca, ma richiede una memoria O (n^2) per la matrice del punteggio; Tuttavia, per un blog, N non è molto grande. Per qualcosa delle dimensioni di un grande giornale, KNN diventa rapidamente poco pratico, quindi un algoritmo di classificazione al volo è talvolta migliore. In tal caso, potresti considerare un Macchina vettoriale di supporto di classificazione. Gli SVM sono puliti perché non ti limitano a misure di somiglianza lineari e sono ancora abbastanza veloci.

Derivante è un passo di preelaborazione comune per le tecniche di borsa; Ciò comporta una riduzione delle parole morfologicamente correlate, come "gatto" e "gatti", "Bob" e "Bob's", o "simili" e "allo stesso modo", fino alle loro radici prima di calcolare la borsa delle parole. Ci sono un mucchio di diversi algoritmi di causa in circolazione; La pagina Wikipedia ha collegamenti a diverse implementazioni.

Se la somiglianza di borse-words non è abbastanza buona, puoi astrarre una somiglianza di livello per sacchetti di n-n-grammi, in cui si crea il vettore che rappresenta un documento basato su coppie o triple di parole. (Puoi usare 4 tuple o anche tuple più grandi, ma in pratica questo non aiuta molto.) Questo ha lo svantaggio di produrre vettori molto più grandi e la classificazione richiederà di conseguenza più lavoro, ma le partite che ottieni saranno molto più vicine sintatticamente. Otoh, probabilmente non ne hai bisogno per la somiglianza semantica; È meglio per cose come il rilevamento del plagio. Chunking, o ridurre un documento fino a alberi di analisi leggeri, può anche essere usato (ci sono algoritmi di classificazione per gli alberi), ma questo è più utile per cose come il problema della paternità ("dato un documento di origine sconosciuta, chi l'ha scritto?") .

Forse più utile per il tuo caso d'uso è il concept mining, che prevede la mappatura delle parole ai concetti (usando un thesaurus come Wordnet), quindi classificando i documenti basati sulla somiglianza tra i concetti utilizzati. Questo spesso finisce per essere più efficiente della classificazione di somiglianza basata su parole, poiché la mappatura dalle parole ai concetti è riduttiva, ma la fase di preelaborazione può richiedere molto tempo.

Finalmente c'è Analisi del discorso, che prevede documenti di analisi per la loro struttura semantica; Puoi eseguire classificatori di somiglianza sugli alberi del discorso nello stesso modo in cui è possibile su documenti di tagliato.

Praticamente tutti implicano la generazione di metadati dal testo non strutturato; Fare paragoni diretti tra blocchi grezzi di testo è intrattabile, quindi le persone preevano prima i documenti nei metadati.

Answer 2

Questo è un caso tipico di Classificazione del documento che è studiato in ogni classe di apprendimento automatico. Se ti piacciono le statistiche, la matematica e l'informatica, ti consiglio di dare un'occhiata ai metodi non supervisionati come kmeans ++, Metodi bayesiani e LDA. In particolare, i metodi bayesiani lo sono piuttosto buono A quello che stai cercando, il loro unico problema è essere lento (ma a meno che tu non esegui un sito molto grande, non dovrebbe disturbarti molto).

Su un approccio più pratico e meno teorico, ti consiglio di dare un'occhiata a questo e questo altro Grandi esempi di codice.

Answer 3

Dovresti leggere il libro "Programming Collective Intelligence: Building Smart Web 2.0 Applications" (ISBN 0596529325)!

Per qualche metodo e codice: prima chiediti, se vuoi trovare somiglianze dirette in base alle corrispondenze di parole o se si desidera mostrare articoli simili che potrebbero non essere direttamente relativi a quello attuale, ma appartengono allo stesso cluster di articoli.

Vedere Analisi del cluster / clustering partizionale.

Un metodo molto semplice (ma teorico e lento) per trovare diretto Le somiglianze sarebbero:

Preprocess:

1. Memorizza l'elenco di parole piane per articolo (non rimuovere le parole duplicate).
2. "Cross join" The Articoli: Conta il numero di parole nell'articolo A che corrispondono alle stesse parole nell'articolo B. Ora hai una matrice int word_matches[narticles][narticles] (Non dovresti archiviarlo in questo modo, la somiglianza di A-> B è uguale a B-> A, quindi una matrice sparsa risparmia quasi la metà dello spazio).
3. Normalizzare il numero di word_matches per l'intervallo 0..1! (Trova il conteggio massimo, quindi dividi qualsiasi conteggio con questo): dovresti archiviare i galleggianti lì, non int;)

Trova articoli simili:

1. Seleziona gli articoli X con corrispondenze più alte da word_matches

Answer 4

Un piccolo motore di ricerca sul modello vettoriale a Ruby. L'idea di base è che due documenti sono correlati se contengono le stesse parole. Quindi contiamo la presenza di parole in ciascun documento e quindi calcoliamo il coseno tra questi vettori (ogni Termini ha un indice fisso, se sembra che esiste un 1 a quell'indice, se non uno zero). Il coseno sarà 1.0 se due documenti hanno tutti i termini comuni e 0,0 se non hanno termini comuni. Puoi tradurlo direttamente su % valori.

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

la definizione di Array#cosine è lasciato come un esercizio al lettore (dovrebbe affrontare i valori di zero e diverse lunghezze, ma bene per questo abbiamo ottenuto Array#zip Giusto?)

A proposito, i documenti di esempio sono prelevati dal documento SVD da Deerwester etal :)

Answer 5

Qualche tempo fa ho implementato qualcosa di simile. Forse questa idea è ora obsoleta, ma spero che possa aiutare.

Ho eseguito un sito Web ASP 3.0 per la programmazione delle attività comuni e ho iniziato da questo principio: l'utente ha un dubbio e rimarrà sul sito Web per quanto tempo/lei può trovare contenuti interessanti su tale argomento.

Quando un utente è arrivato, ho iniziato un ASP 3.0 Session oggetto e registrato tutta la navigazione dell'utente, proprio come un elenco collegato. In Session.OnEnd Evento, prendo il primo link, cerca il prossimo link e increto una colonna di contatore come:

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

Quindi, per controllare gli articoli correlati ho dovuto solo elencare la parte superiore n NextPage entità, ordinate per banco colonna discendente.