somiglianza cosine vs distanza di Hamming

Question

Per calcolare la somiglianza tra due documenti, creo un vettore di funzionalità contenente il termine frequenze. Ma poi, per il prossimo passo, non riesco a decidere tra "Cosine similarity" e "Hamming distance".

La mia domanda: hai esperienza con questi algoritmi? Quale ti dà risultati migliori?

In aggiunta a ciò: Potrebbe dirmi come codificare la similarità del coseno in PHP? Per distanza di Hamming, ho già il codice:

function check ($terms1, $terms2) { 
    $counts1 = array_count_values($terms1); 
    $totalScore = 0; 
    foreach ($terms2 as $term) { 
     if (isset($counts1[$term])) $totalScore += $counts1[$term]; 
    } 
    return $totalScore * 500/(count($terms1) * count($terms2)); 
} 

Non voglio usare qualsiasi altro algoritmo. Mi piacerebbe solo avere un aiuto per decidere tra entrambi.

E forse qualcuno può dire qualcosa su come migliorare gli algoritmi. Otterrete risultati migliori se filtrate le parole di arresto o le parole comuni?

Spero che tu possa aiutarmi. Grazie in anticipo!

Answer 1

A distanza di Hamming dovrebbe essere fatto tra due stringhe di uguale lunghezza e con l'ordine preso in considerazione.

Dato che i tuoi documenti sono sicuramente di lunghezza diversa e se i posti delle parole non contano, la somiglianza del coseno è migliore (tieni presente che a seconda delle tue esigenze esistono soluzioni migliori). :)

Ecco una funzione coseno di similitudine di 2 array di parole:

function cosineSimilarity($tokensA, $tokensB) 
{ 
    $a = $b = $c = 0; 
    $uniqueTokensA = $uniqueTokensB = array(); 

    $uniqueMergedTokens = array_unique(array_merge($tokensA, $tokensB)); 

    foreach ($tokensA as $token) $uniqueTokensA[$token] = 0; 
    foreach ($tokensB as $token) $uniqueTokensB[$token] = 0; 

    foreach ($uniqueMergedTokens as $token) { 
     $x = isset($uniqueTokensA[$token]) ? 1 : 0; 
     $y = isset($uniqueTokensB[$token]) ? 1 : 0; 
     $a += $x * $y; 
     $b += $x; 
     $c += $y; 
    } 
    return $b * $c != 0 ? $a/sqrt($b * $c) : 0; 
} 

'veloce (isset() anziché in_array() è un killer su grandi array).

Come potete vedere, i risultati non tengono conto della "magnitudine" di ciascuna parola.

Lo uso per rilevare messaggi multi-postato di "quasi" testi copiati. Funziona bene. :)

Il miglior collegamento su metriche di similarità stringa: http://www.dcs.shef.ac.uk/~sam/stringmetrics.html

Per letture più interessanti:

http://www.miislita.com/information-retrieval-tutorial/cosine-similarity-tutorial.html http://bioinformatics.oxfordjournals.org/cgi/content/full/22/18/2298

Answer 2

Mi scuso per aver ignorato il fatto che hai detto che non volevi utilizzare altri algoritmi, ma seriamente, Levenshtein distance e Damerau-Levenshtein distance sono molto più utili della distanza di Hamming. Ecco un D-L distance implementation in PHP, e se non ti piace levenshtein() funzione nativa di PHP, che penso che non lo farò perché ha un limite di lunghezza, ecco una versione non lunghezza limitata:

function levenshtein_distance($text1, $text2) { 
    $len1 = strlen($text1); 
    $len2 = strlen($text2); 
    for($i = 0; $i <= $len1; $i++) 
     $distance[$i][0] = $i; 
    for($j = 0; $j <= $len2; $j++) 
     $distance[0][$j] = $j; 
    for($i = 1; $i <= $len1; $i++) 
     for($j = 1; $j <= $len2; $j++) 
      $distance[$i][$j] = min($distance[$i - 1][$j] + 1, $distance[$i][$j - 1] + 1, $distance[$i - 1][$j - 1] + ($text1[$i - 1] != $text2[$j - 1])); 
    return $distance[$len1][$len2]; 
} 

Answer 3

A meno che io sono errato, penso che tu abbia un algoritmo a metà strada tra i due algoritmi. Per distanza di Hamming, uso:

function check ($terms1, $terms2) { 
    $counts1 = array_count_values($terms1); 
    $totalScore = 0; 
    foreach ($terms2 as $term) { 
     if (isset($counts1[$term])) $totalScore += 1; 
    } 
    return $totalScore * 500/(count($terms1) * count($terms2)); 
} 

(. Si noti che si sta solo aggiungendo 1 per ogni elemento abbinati nei vettori gettone)

E per coseno di similitudine, uso:

function check ($terms1, $terms2) { 
    $counts1 = array_count_values($terms1); 
    $counts2 = array_count_values($terms2); 
    $totalScore = 0; 
    foreach ($terms2 as $term) { 
     if (isset($counts1[$term])) $totalScore += $counts1[$term] * $counts2[$term]; 
    } 
    return $totalScore/(count($terms1) * count($terms2)); 
} 

(Si noti che si sta aggiungendo il prodotto dei conteggi di token tra i due documenti.)

La differenza principale tra i due è che la somiglianza del coseno sarà quella Un indicatore più forte quando due documenti hanno la stessa parola più volte nei documenti, mentre nella distanza di Hamming non interessa la frequenza con cui vengono visualizzati i token individuali.

: ho appena notato la tua domanda sulla rimozione delle parole di funzione ecc. Ti consiglio se usi la somiglianza del coseno - dato che le parole di funzione sono abbastanza frequenti (in inglese, almeno), potresti distorcere un risultato non filtrandoli. Se usi la distanza di Hamming, l'effetto non sarà altrettanto grande, ma potrebbe comunque essere apprezzabile in alcuni casi. Inoltre, se si ha accesso a un lemmatizer, ridurrà le mancanze quando un documento contiene "galassie" e l'altro contiene "galassia", per esempio.

In qualsiasi modo, buona fortuna!

Answer 4

Ecco il mio codice corretto per la funzione coseno Distanza postato da Toto

function cosineSimilarity($tokensA, $tokensB) 
{ 
    $a = $b = $c = 0; 
    $uniqueTokensA = $uniqueTokensB = array(); 

    $uniqueMergedTokens = array_unique(array_merge($tokensA, $tokensB)); 

    foreach ($tokensA as $token) $uniqueTokensA[$token] = 0; 
    foreach ($tokensB as $token) $uniqueTokensB[$token] = 0; 

    foreach ($uniqueMergedTokens as $token) { 
     $x = isset($uniqueTokensA[$token]) ? 1 : 0; 
     $y = isset($uniqueTokensB[$token]) ? 1 : 0; 
     $a += $x * $y; 
     $b += pow($x,2); 
     $c += pow($y,2); 
    } 
    return $b * $c != 0 ? $a/sqrt($b * $c) : 0; 
}