Hamming mesafesi vs kosinüs benzerliği

5 Cevap php

Iki belge arasındaki benzerliği hesaplamak için, ben terim frekansları içeren bir özellik vektörü oluşturmak. Ama sonra, bir sonraki adım için, ben "Cosine similarity" arasında karar veremiyorum ve "Hamming distance".

Benim soru: Eğer bu algoritmaları ile deneyiminiz var mı? Hangisi daha iyi sonuç verir?

Buna ek olarak: nasıl PHP kosinüs benzerliği kodlamak için bana söyleyebilir misiniz? Hamming mesafesi için, ben zaten kod var:

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

Ben başka bir algoritma kullanmak istemiyorum. Ben sadece her iki arasında karar yardım istiyorum.

Ve belki birisi algoritmalar geliştirmek için nasıl bir şey söyleyebiliriz. Eğer stop sözcükleri ya da ortak kelimeleri filtrelemek eğer daha iyi sonuçlar alırsınız?

Bana yardımcı olur umarım. Şimdiden teşekkürler!

5 Cevap

Bir Hamming uzaklığı eşit uzunlukta iki dizeleri arasındaki ve dikkate alınan sipariş ile yapılmalıdır.

Belgelerinizi farklı uzunlukta kesinlikle vardır ve kelimeler yerleri saymazsak, kosinüs benzerliği daha iyi olduğu gibi (sizin ihtiyaçlarınıza bağlı olarak, daha iyi çözümler var lütfen unutmayın). :)

Burada kelimelerin 2 diziler bir kosinüs benzerlik fonksiyon:

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

Bu (isset() yerine in_array() büyük diziler üzerinde bir katil) hızlı.

Gördüğünüz gibi, sonuçlar dikkate her kelimenin "büyüklüğünü" almaz.

"Neredeyse" kopyalanıp yapıştırılmış metinlerin çok nakledilen mesajları algılamak için kullanabilirsiniz. Bu iyi çalışıyor. :)

The best link about string similarity metrics: http://www.dcs.shef.ac.uk/~sam/stringmetrics.html

Diğer bir ilginç okuma için:

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

Yanılmıyorsam, ben bir algoritma halfway between the two algorithms var düşünüyorum. Hamming mesafesi için, kullanın:

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

(Sadece belirteç vektörleri her eşleşen öğe için 1 ekliyoruz unutmayın.)

Ve kosinüs benzerliği için, kullanın:

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

(Eğer iki belge arasındaki belirteç sayımların ürününü ekliyoruz unutmayın.)

İkisi arasındaki temel fark cosine similarity will yield a stronger indicator when two documents have the same word multiple times in the documents iken Hamming distance doesn't care how often the individual tokens come up.

Edit: sadece kosinüs benzerliği kullanmak için gidiyoruz eğer ben bu tavsiye edersiniz vb fonksiyon kelimeleri kaldırarak hakkında sorgu fark - işlevsel sözcükler (en azından İngilizce) oldukça sık olarak, bir çarpıklık olabilir onları filtreleyerek değil tarafından sonuçlanabilir. Eğer Hamming mesafe kullanırsanız, etkisi oldukça büyük olmayacak, ama yine de bazı durumlarda kayda değer olabilir. Bir belge "galaksiler" içerir ve diğer örneği için, "galaksi" içerir Ayrıca, bir erişiminiz varsa lemmatizer, bu isabetsizlik azaltacaktır.

Gittiğiniz yol hangisi olursa olsun, iyi şanslar!

Ben size başka algoritmalar kullanmak istiyorum, ama ciddi, Levenshtein distance ve Damerau-Levenshtein distance yolu daha fazla acayip olan mesafe Hamming daha 'yararlı olmadığını söyledi gerçeğini görmezden için özür dileriz. İşte D-L distance implementation in PHP, ve bir uzunluk limiti vardır çünkü ben değil olacağını düşünüyorum PHP'nin native levenshtein() function, beğenmezseniz, burada olmayan bir uzunluğu kısıtlı versiyonu :

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

İşte Kosinüs Uzaklık fonksiyonu benim düzeltilmiş kod Toto tarafından yayınlanmıştır

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

Hamming mesafesi programa daha kolay olsa da, yerine Levenstein mesafeyi kullanın ...

Ayrıca farklı uzunluk dizeleri karşılaştırmak için izin verir

etiketler