Kosinusähnlichkeit vs Hamming-Distanz [geschlossen]

Question

, um die Ähnlichkeit zwischen zwei Dokumenten zu berechnen, erstelle ich einen Merkmalsvektor den Begriff Frequenzen enthält. Aber dann, für den nächsten Schritt, kann ich nicht entscheiden zwischen „ Kosinusähnlichkeit “ und „< a href = "http://en.wikipedia.org/wiki/Hamming_distance" rel = "noreferrer"> Hamming-Distanz “.

Meine Frage: Haben Sie Erfahrung mit diesen Algorithmen haben? Welche gibt Ihnen bessere Ergebnisse?

Zusätzlich zu, dass: Können Sie mir sagen, wie die Cosinus Ähnlichkeit in PHP codieren? Für Hamming-Distanz, 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 will keinen anderen Algorithmus verwenden. Ich möchte nur Hilfe haben zwischen den beiden zu entscheiden.

Und vielleicht kann jemand etwas sagen, wie die Algorithmen zu verbessern. Werden Sie bessere Ergebnisse, wenn Sie die Stoppwörter oder gemeinsame Wörter herauszufiltern?

Ich hoffe, dass Sie mir helfen können. Vielen Dank im Voraus!

Answer 1

Ein Hamming-Abstand sollte zwischen zwei Saiten von gleicher Länge und mit der Bestellung berücksichtigt erfolgen.

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

Hier ist eine Kosinusähnlichkeit Funktion von 2 Arrays von Worten:

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, hat die Ergebnisse nicht berücksichtigen, die „Größe“ eines jeden Wortes.

Ich benutze es mehr geposteten Nachrichten von „fast“ Kopie kleisterte Texte zu erfassen. Es funktioniert gut. :)

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

Für weitere interessante Lesungen:

http://www.miislita.com/information- Retrieval-tutorial / Cosinus-ähnlichkeits tutorial.html http://bioinformatics.oxfordjournals.org/cgi/content/full/22 / 18/2298

Answer 2

Wenn ich nicht irre, ich glaube, Sie einen Algorithmus haben auf halber Strecke zwischen den beiden Algorithmen . Für Hamming-Distanz 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 hinzufügen nur 1 für jedes verglichene Element in den Token-Vektoren).

Für Kosinusähnlichkeit, zu verwenden:

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 zwischen den beiden Dokumenten das Produkt der Tokenzählungen sind hinzufügen.)

Der Hauptunterschied zwischen den beiden ist, dass Kosinusähnlichkeit eine stärkere Indikator ergeben, wenn zwei Dokumente das gleiche Wort mehrere Male in den Dokumenten , während Hamming-Distanz nicht, wie oft ist es egal die einzelnen Token kommen .

Bearbeiten : habe gerade bemerkt, Ihre Frage über Funktionsworte zu entfernen usw. ich dies tun beraten, wenn Sie Kosinusähnlichkeit verwenden werden - als Funktionsworte recht häufig sind (in englischer Sprache, zumindest), Sie könnten ein Ergebnis skew durch Filtern sie nicht aus. Wenn Sie Hamming-Distanz verwenden, wird der Effekt nicht ganz so groß sein, aber es könnte noch in einigen Fällen beträchtlich sein. Auch, wenn Sie haben Zugriff auf ein Lemmatizer , wird es die Fehlschüsse reduzieren, wenn ein Dokument enthält „Galaxien "und das andere enthält‚Galaxie‘, zum Beispiel.

Welchen Weg Sie gehen, viel Glück!

Answer 3

Ich entschuldige mich die Tatsache zu ignorieren, dass Sie sagten, dass Sie keine andere Algorithmen verwenden wollten, aber ernsthaft, Levenshtein Abstand und Damerau-Levenshtein Abstand sind viel mehr freakin nützlich als Abstand Hamming. Hier ist eine DL Abstand Implementierung in PHP , und wenn Sie dies nicht tun wie native levenshtein() Funktion von PHP, die ich denke, Sie werden nicht, weil es eine Längenbegrenzung hat, ist hier eine nicht längenbegrenzte 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 4

Hier mein korrigierten Code für Cosinus Entfernung Funktion von Toto geschrieben

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