Miglior algoritmo di clustering?(semplicemente spiegato)

Question

Immaginate il seguente problema:

• Si dispone di un database contenente circa 20.000 testi in una tabella "articoli"
• Si desidera collegare quelle relative utilizza un algoritmo di clustering per visualizzare gli articoli insieme
• L'algoritmo dovrebbe fare tv di clustering (non gerarchica)
• Articoli correlati devono essere inseriti nella tabella "related"
• L'algoritmo di clustering deve decidere se due o più articoli sono legati o non si basa sui testi
• Ho voglia di codice in PHP, ma anche esempi con la pseudo-codice o in altri linguaggi di programmazione sono ok, troppo

Ho codificato una prima bozza di una funzione check() che restituisce "true" se i due input articoli correlati e "false" se non.Il resto del codice (selezione di articoli dal database, la selezione di articoli da confrontare con, l'inserimento di quelle relative) è completo, troppo.Forse si può migliorare il resto, troppo.Ma il punto principale che per me è importante è la funzione check().Così sarebbe bello se si potrebbe postare alcuni miglioramenti, o completamente diversi approcci.

APPROCCIO 1

<?php
$zeit = time();
function check($str1, $str2){
    $minprozent = 60;
    similar_text($str1, $str2, $prozent);
    $prozent = sprintf("%01.2f", $prozent);
    if ($prozent > $minprozent) {
        return TRUE;
    }
    else {
        return FALSE;
    }
}
$sql1 = "SELECT id, text FROM articles ORDER BY RAND() LIMIT 0, 20";
$sql2 = mysql_query($sql1);
while ($sql3 = mysql_fetch_assoc($sql2)) {
    $rel1 = "SELECT id, text, MATCH (text) AGAINST ('".$sql3['text']."') AS score FROM articles WHERE MATCH (text) AGAINST ('".$sql3['text']."') AND id NOT LIKE ".$sql3['id']." LIMIT 0, 20";
    $rel2 = mysql_query($rel1);
    $rel2a = mysql_num_rows($rel2);
    if ($rel2a > 0) {
        while ($rel3 = mysql_fetch_assoc($rel2)) {
            if (check($sql3['text'], $rel3['text']) == TRUE) {
                $id_a = $sql3['id'];
                $id_b = $rel3['id'];
                $rein1 = "INSERT INTO related (article1, article2) VALUES ('".$id_a."', '".$id_b."')";
                $rein2 = mysql_query($rein1);
                $rein3 = "INSERT INTO related (article1, article2) VALUES ('".$id_b."', '".$id_a."')";
                $rein4 = mysql_query($rein3);
            }
        }
    }
}
?>

APPROCCIO 2 [solo check()]

<?php
function square($number) {
    $square = pow($number, 2);
    return $square;
}
function check($text1, $text2) {
    $words_sub = text_splitter($text2); // splits the text into single words
    $words = text_splitter($text1); // splits the text into single words
    // document 1 start
    $document1 = array();
    foreach ($words as $word) {
        if (in_array($word, $words)) {
            if (isset($document1[$word])) { $document1[$word]++; } else { $document1[$word] = 1; }
        }
    }
    $rating1 = 0;
    foreach ($document1 as $temp) {
        $rating1 = $rating1+square($temp);
    }
    $rating1 = sqrt($rating1);
    // document 1 end
    // document 2 start
    $document2 = array();
    foreach ($words_sub as $word_sub) {
        if (in_array($word_sub, $words)) {
            if (isset($document2[$word_sub])) { $document2[$word_sub]++; } else { $document2[$word_sub] = 1; }
        }
    }
    $rating2 = 0;
    foreach ($document2 as $temp) {
        $rating2 = $rating2+square($temp);
    }
    $rating2 = sqrt($rating2);
    // document 2 end
    $skalarprodukt = 0;
    for ($m=0; $m<count($words)-1; $m++) {
        $skalarprodukt = $skalarprodukt+(array_shift($document1)*array_shift($document2));
    }
    if (($rating1*$rating2) == 0) { continue; }
    $kosinusmass = $skalarprodukt/($rating1*$rating2);
    if ($kosinusmass < 0.7) {
        return FALSE;
    }
    else {
        return TRUE;
    }
}
?>

Vorrei anche dire che io so che ci sono un sacco di algoritmi di clustering, ma su ogni sito c'è solo la descrizione matematica che è un po ' difficile da capire per me.Quindi, esempi di codice in (pseudo) codice sarebbe grande.

Spero che tu mi possa aiutare.Grazie in anticipo!

Answer 1

Il modo più standard che conosco per fare questo su dati di testo come voi, è quello di utilizzare la 'borsa di parole' tecnica.

Prima di tutto, creare un 'istogramma' di parole per ogni articolo.Diciamo che tra tutti i tuoi articoli, hai solo 500 uniche parole tra di loro.Quindi, questo istogramma è intenzione di essere un vettore(Array, Lista, quello che è) di dimensioni 500, i cui dati sono il numero di volte in cui ogni parola appare nell'articolo.Quindi, se il primo punto è il vettore rappresentato la parola 'chiese', e che la parola apparve 5 volte nell'articolo, vettore[0] sarebbe di 5:

for word in article.text
    article.histogram[indexLookup[word]]++

Ora, per confrontare due articoli, è abbastanza semplice.Ci basta moltiplicare i due vettori:

def check(articleA, articleB)
    rtn = 0
    for a,b in zip(articleA.histogram, articleB.histogram)
        rtn += a*b
    return rtn > threshold

(Scusa per l'utilizzo di python invece di PHP, il mio PHP è arrugginito e l'uso di zip rende più semplice)

Questa è l'idea di base.Notare il valore di soglia è semi-arbitrario;probabilmente si vorrà trovare un buon modo per normalizzare il prodotto di puntino del vostro istogrammi (questa sarà quasi necessario fattore in lunghezza articolo da qualche parte) e decidere ciò che si considera "correlati".

Inoltre, si dovrebbe mettere ogni parola nel tuo istogramma.Ti, in generale, desidera includere quelli che vengono utilizzati semi di frequente:Non sono in ogni articolo, né in un solo articolo.Questo consente di risparmiare un po ' di overhead sul tuo istogramma, e aumenta il valore del vostro rapporto.

A proposito, questa tecnica è descritta in dettaglio più qui

Answer 2

Forse il clustering è una strategia sbagliata qui?

Se si desidera visualizzare simile articoli utilizzare la ricerca di similitudine invece.

Per il testo degli articoli, questo è ben compreso.Basta inserire i vostri articoli in un testo, database di ricerca come Lucene, e usa il tuo articolo come query di ricerca.In Lucene, esiste un query chiamato MoreLikeThis che esegue esattamente questo:trovare articoli simili.

Il Clustering è lo strumento sbagliato, perché (in particolare con le vostre esigenze), ogni l'articolo deve essere messo in alcuni cluster;e i relativi elementi potrebbe essere lo stesso per ogni oggetto del cluster.Se ci sono valori anomali nel database - un caso molto probabile in quanto potrebbero rovinare il vostro clustering.Inoltre, i cluster possono essere molto grandi.Non c'è nessun vincolo di dimensione, l'algoritmo di clustering può decidere di mettere la metà del set di dati nello stesso cluster.Così hai 10000 articoli correlati per ogni articolo nel database.Con somiglianza di ricerca, è possibile trovare la top-10 di oggetti simili, per ogni documento!

Ultimo ma non meno importante:dimenticate PHP per il clustering.Non è progettato per questo, e non performante abbastanza.Ma probabilmente si può accedere a un indice di lucene da PHP abbastanza bene.

Answer 3

Credo che hai bisogno di fare alcune decisioni di progettazione sul clustering, e continuare da lì:

1. Perché il clustering testi? Vuoi visualizzare i documenti correlati insieme? Volete esplorare il vostro corpus documento tramite cluster?
2. Come risultato, vuoi piatta o gerarchica di clustering ?
3. Ora abbiamo il problema della complessità, in due dimensioni: prima, il numero e il tipo di funzioni create dal testo - le singole parole possono numero in decine di migliaia. Si consiglia di provare alcuni selezione delle funzioni - come prendere le N parole più informativi, o la N parole che appaiono le più delle volte, dopo aver ignorato fermano parole .
4. In secondo luogo, si vuole ridurre al minimo il numero di volte in cui si misura somiglianza tra i documenti. Come bubaker sottolinea correttamente, controllando somiglianza tra tutte le coppie di documenti può essere troppo. Se il clustering in un piccolo numero di cluster è sufficiente, si può considerare K- significa il clustering , che è fondamentalmente: scegliere un documenti K iniziali come centri di cluster, assegnare ogni documento al cluster più vicino, ricalcolare centri cluster trovando mezzi di documenti Vector, e iterare. Questo costa solo K * numero di documenti per ogni iterazione. Credo che ci siano anche euristiche per la riduzione del numero necessario di calcoli per il clustering gerarchico pure.

Answer 4

Che cosa significa la funzione similar_text chiamato Approccio # 1 assomigliare? Penso che quello che stai facendo riferimento alla non è di clustering, ma una somiglianza metrica. Non posso davvero migliorare l'approccio :-) istogramma del Bianco Walloun -. Un problema interessante per fare qualche lettura su

Tuttavia si implementa check(), hai avuto modo di usarlo per fare almeno 200M confronti (la metà di 20000^2). Il cut-off per articoli "correlate" può limitare quello che si memorizza nel database, ma sembra troppo arbitraria di catturare tutti raggruppamento utile di testi,

Il mio approccio sarebbe quello di modificare $prozent per restituire la "somiglianza" metrica (o rtn 20K x 20K). Scrivere il related matrice in un file e utilizzare un programma esterno per eseguire un raggruppamento per identificare i vicini più prossimi per ogni articolo, che è possibile caricare nella tabella R. Vorrei fare il clustering in php - c'è una bella per i dati di clustering in un file in esecuzione <=> da <=>.