Cosseno semelhança vs distância de Hamming [fechado]

Question

Para calcular a similaridade entre dois documentos, eu criar um vetor de características contendo as freqüências prazo. Mas, em seguida, para o próximo passo, eu não posso decidir entre " Cosine semelhança " e "< a href = "http://en.wikipedia.org/wiki/Hamming_distance" rel = "noreferrer"> Hamming distância ".

A minha pergunta: Você tem experiência com esses algoritmos? Qual deles lhe dá melhores resultados?

Além disso: Você poderia me como código a semelhança Cosine dizer em PHP? Para Hamming distância, eu já tenho o código:

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

Eu não quero usar qualquer outro algoritmo. Gostaria apenas de ter ajuda para decidir entre os dois.

E talvez alguém pode dizer algo sobre a forma de melhorar os algoritmos. você obterá melhores resultados se você filtrar as palavras de parada ou palavras?

Eu espero que você possa me ajudar. Agradecemos antecipadamente!

Answer 1

A Hamming distância deve ser feito entre duas cadeias de mesmo comprimento e com a ordem tomadas em conta.

Como os documentos são certamente de comprimento diferente e se as palavras lugares não contam, cosseno semelhança é melhor (Por favor, note que, dependendo suas necessidades, existem soluções melhores). :)

Aqui é uma função cosseno semelhança de 2 conjuntos de palavras:

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

É rápido (isset() vez de in_array() é um assassino em grandes matrizes).

Como você pode ver, os resultados não leva em conta a "magnitude" de cada palavra.

Eu usá-lo para detectar mensagens de multi-lançamento "quase" textos colados contra cópia. Isso funciona bem. :)

O melhor link sobre métricas seqüência de similaridade : http://www.dcs.shef.ac.uk/~sam/stringmetrics .html

Para mais leituras interessantes:

http://www.miislita.com/information- recuperação-tutorial / cosseno-similaridade-tutorial.html http://bioinformatics.oxfordjournals.org/cgi/content/full/22 / 18/2298

Answer 2

Se não me engano, eu acho que você tem um algoritmo a meio caminho entre os dois algoritmos . Para Hamming distância, use:

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

(Note que você só está adicionando 1 para cada elemento combinado nos vetores de tokens.)

E por similaridade do cosseno, use:

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

(Note que você está adicionando o produto das contagens de token entre os dois documentos.)

A principal diferença entre os dois é que similaridade do cosseno irá produzir um indicador mais forte quando dois documentos têm a mesma palavra várias vezes nos documentos , enquanto Hamming distância não importa quantas vezes as fichas individuais vir para cima .

Editar : só notei sua consulta sobre a remoção de palavras de função etc. Eu aconselho isso se você estiver indo para usar cosseno de similaridade - como palavras funcionais são bastante freqüentes (em Inglês, pelo menos), que você pode distorcer resultado por não filtrá-los. Se você usar Hamming distância, o efeito não será tão grande, mas ainda poderia ser apreciável em alguns casos. Além disso, se você tem acesso a um lemmatizer , que irá reduzir os acidentes quando um documento contém "galáxias "e o outro contém 'galáxia', por exemplo.

Qualquer maneira você vai, boa sorte!

Answer 3

Peço desculpas por ignorar o fato de que você disse que não queria usar quaisquer outros algoritmos, mas sério, distância Levenshtein e Damerau-Levenshtein distância são muito mais freakin útil do que Hamming distância. Aqui está um DL implementação distância em PHP , e se você não como função do PHP nativo levenshtein(), que eu acho que você não vai porque tem um limite de comprimento, aqui está uma versão não-comprimento limitado:

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

Aqui meu código corrigido para Cosine Distância função postado por 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;
}