Coseno similitud vs distancia de Hamming [cerrada]

Question

Para calcular la similitud entre dos documentos, se crea un vector de características que contiene las frecuencias plazo. Pero entonces, para el siguiente paso, no puedo decidir entre " coseno similitud" y "< a href = "http://en.wikipedia.org/wiki/Hamming_distance" rel = "noreferrer"> distancia de Hamming ".

Mi pregunta: ¿Tiene experiencia con estos algoritmos? Cuál le da mejores resultados?

Además de eso: ¿Podría decirme cómo codificar la similitud del coseno en PHP? Para la distancia de Hamming, ya tengo el 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));
}

No quiero usar cualquier otro algoritmo. Sólo me gustaría tener ayuda para decidir entre ambos.

Y tal vez alguien puede decir algo sobre cómo mejorar los algoritmos. Va a obtener mejores resultados si filtra las palabras de parada o palabras comunes?

Espero que me puedan ayudar. Gracias de antemano!

Answer 1

A distancia de Hamming debe hacerse entre dos cadenas de igual longitud y con el fin de tener en cuenta.

A medida que sus documentos son sin duda de diferente longitud y si las palabras lugares no cuentan, similitud del coseno es mejor (tenga en cuenta que dependiendo de sus necesidades, existen mejores soluciones). :)

Esta es una función coseno similitud de 2 conjuntos de palabras:

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 rápido (isset() en lugar de in_array() es un asesino en grandes matrices).

Como se puede ver, los resultados no tiene en cuenta la "magnitud" de cada palabra.

Lo uso para detectar mensajes multi-publicado de textos "casi" copiar-pegar. Funciona bien. :)

La mejor enlace acerca de las métricas de similitud de cadenas : http://www.dcs.shef.ac.uk/~sam/stringmetrics .html

Para más lecturas interesantes:

http://www.miislita.com/information- recuperación-tutorial / coseno-similitud-tutorial.html http://bioinformatics.oxfordjournals.org/cgi/content/full/22 / 18/2298

Answer 2

Si no me equivoco, creo que tienes un algoritmo a medio camino entre los dos algoritmos . Para Hamming distancia, utilice:

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

(Tenga en cuenta que sólo se va a añadir 1 para cada elemento coincidente en los vectores de fichas.)

Y por similitud del coseno, utilice:

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

(Tenga en cuenta que va a añadir el producto de los recuentos de fichas entre los dos documentos.)

La principal diferencia entre los dos es que similitud del coseno producirá un indicador más fuerte cuando dos documentos tienen la misma palabra varias veces en los documentos , mientras que distancia de Hamming no le importa con qué frecuencia las fichas individuales vienen .

Editar : solo se dio cuenta de su pregunta sobre la eliminación de las palabras de función, etc. Yo aconsejo esto si usted va a utilizar similitud del coseno - como las palabras de función son bastante frecuentes (en Inglés, por lo menos), usted puede sesgar el resultado al no filtrar hacia fuera. Si utiliza la distancia de Hamming, el efecto no será tan grande, pero todavía podría ser apreciable en algunos casos. Además, si usted tiene acceso a una lematizador , se reducirá del área cuando un documento contiene galaxias" "y el otro contiene "Galaxy", por ejemplo.

Como quiera que se vaya, buena suerte!

Answer 3

Me disculpo por ignorar el hecho de que usted ha dicho que usted no desea utilizar cualquier otro tipo de algoritmos, pero en serio, Levenshtein distancia y Damerau-distancia Levenshtein son mucho más pasada útil que la distancia de Hamming. He aquí una DL aplicación distancia en PHP , y si no lo hace al igual que la función de PHP nativo levenshtein(), que creo que no va porque tiene un límite de longitud, aquí está una versión no-longitud limitada:

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

Aquí mi código corregido para la función coseno Distancia Publicado 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;
}