Kosinusähnlichkeit vs Hamming-Abstand

Question

Um die Ähnlichkeit zwischen zwei Dokumenten zu berechnen, erstelle ich einen Merkmalsvektor, der den Begriff Frequenzen enthält. Aber dann kann ich mich für den nächsten Schritt nicht zwischen "Cosine similarity" und "Hamming distance" entscheiden.

Meine Frage: Haben Sie Erfahrung mit diesen Algorithmen? Welcher gibt dir bessere Ergebnisse?

Zusätzlich dazu: Können Sie mir sagen, wie man die Cosinus-Ähnlichkeit in PHP codiert? Für Hamming Abstand habe ich bereits den Code:

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)); 
} 

Ich möchte keinen anderen Algorithmus verwenden. Ich möchte nur Hilfe haben, um zwischen beiden zu entscheiden.

Und vielleicht kann jemand etwas sagen, wie man die Algorithmen verbessern kann. Werden Sie bessere Ergebnisse erzielen, wenn Sie die Stoppwörter oder die allgemeinen Wörter herausfiltern?

Ich hoffe, Sie können mir helfen. Danke im Voraus!

Answer 1

Eine Hamming-Distanz sollte zwischen zwei Saiten gleicher Länge und in der Reihenfolge, in der sie berücksichtigt werden, erfolgen.

Da Ihre Dokumente sicher von unterschiedlicher Länge sind und die Wörter Orte nicht zählen, ist die Kosinusähnlichkeit besser (bitte beachten Sie, dass je nach Bedarf bessere Lösungen existieren). :)

Hier eine Kosinusähnlichkeit Funktion von 2 Arrays von Wörtern ist:

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; 
} 

Es ist schnell (isset() statt in_array() ist ein Killer auf große Arrays).

Wie Sie sehen können, berücksichtigt die Ergebnisse nicht die "Größe" jedes Wortes.

Ich verwende es, um mehrfach gepostete Nachrichten von "fast" kopierten Texten zu erkennen. Es läuft gut. :)

Die beste Verbindung über Zeichenfolge Ähnlichkeit Metriken: http://www.dcs.shef.ac.uk/~sam/stringmetrics.html

Weitere interessante Lesungen:

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

Answer 2

ich ignorieren die Tatsache entschuldigen, dass Sie sagten, dass Sie keine andere Algorithmen verwenden wollte, aber ernsthaft, Levenshtein distance und Damerau-Levenshtein distance sind viel mehr freakin nützlich als Abstand Hamming. Hier ist eine D-L distance implementation in PHP, und wenn Sie nicht PHP native levenshtein() Funktion mögen, was ich denke, Sie werden nicht, weil es eine Längenbegrenzung hat, ist hier eine nicht-zeitbegrenzten Version:

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

Es sei denn, ich bin falsch, ich denke, Sie haben einen Algorithmus auf halbem Weg zwischen den beiden Algorithmen. Für Hamming-Distanz, zu verwenden:

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)); 
} 

(. Beachten Sie, dass Sie nur sind die Zugabe von 1 für jedes verglichene Element in den Token-Vektoren)

Und für Kosinusähnlichkeit, Verwendung:

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)); 
} 

(Beachten Sie, dass Sie das Produkt der Tokenzählungen zwischen den beiden Dokumenten hinzufügen.)

Der Hauptunterschied zwischen den beiden ist, dass Kosinusähnlichkeit yi wird eld ein stärkerer Indikator, wenn zwei Dokumente dasselbe Wort mehrmals in den Dokumenten haben, während Hamming Abstand ist egal, wie oft die einzelnen Token kommen.

Bearbeiten: habe gerade Ihre Frage zum Entfernen von Funktionswörtern usw. bemerkt. Ich rate Ihnen, wenn Sie Cosinusähnlichkeit verwenden möchten - da Funktionswörter ziemlich häufig vorkommen (zumindest in Englisch), könnten Sie einen Schrägstrich erzeugen Ergebnis, indem Sie sie nicht ausfiltern. Wenn Sie die Hamming-Distanz verwenden, wird der Effekt nicht ganz so groß sein, aber in manchen Fällen kann es noch bemerkbar sein. Wenn Sie Zugriff auf eine lemmatizer haben, wird es auch die Fehler reduzieren, wenn ein Dokument "Galaxien" enthält und die andere "Galaxie" enthält.

Wohin auch immer Sie gehen, viel Glück!

Answer 4

Hier mein korrigierten Code für die Funktion Cosinus Entfernung veröffentlicht von 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; 
}