php - Similitud coseno vs distancia de Hamming

relationship similarity

Question

Para calcular la similitud entre dos documentos, creo un vector de características que contiene el término frecuencias. Pero entonces, para el siguiente paso, no puedo decidir entre " Similitud de coseno " y " Distancia de Hamming ".

Mi pregunta: ¿Tienes experiencia con estos algoritmos? ¿Cuál te 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 ningún otro algoritmo. Solo me gustaría tener ayuda para decidir entre los dos.

Y tal vez alguien pueda decir algo sobre cómo mejorar los algoritmos. ¿Obtendrá mejores resultados si filtra las palabras vacías o las palabras comunes?

Espero que puedas ayudarme. ¡Gracias por adelantado!

Answer 1

A menos que me equivoque, creo que tienes un algoritmo a medio camino entre los dos algoritmos . Para la distancia de Hamming, 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));
}

(Tenga en cuenta que solo está agregando 1 por cada elemento coincidente en los vectores de token).

Y para la similitud de coseno, usar:

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 está agregando el producto del conteo de fichas entre los dos documentos).

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

Edición : acabo de notar su consulta sobre la eliminación de palabras funcionales, etc. Recomiendo esto si va a utilizar la similitud de coseno, ya que las palabras funcionales son bastante frecuentes (al menos en inglés), puede distorsionar un resultado al no filtrarlas . Si utiliza la distancia de Hamming, el efecto no será tan grande, pero en algunos casos podría ser apreciable. Además, si tiene acceso a un lemmatizer , reducirá las fallas cuando un documento contiene "galaxias" y el otro contiene "galaxia", por ejemplo.

Como sea que vayas, ¡buena suerte!

Answer 2

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

Answer 3

Me disculpo por ignorar el hecho de que usted dijo que no quería usar ningún otro algoritmo, pero en serio, la distancia de Levenshtein y la distancia de Damerau-Levenshtein son mucho más útiles que la distancia de Hamming. Aquí hay una implementación de DL a distancia en PHP , y si no te gusta la función levenshtein() nativa de PHP, que creo que no lo harás porque tiene un límite de longitud, aquí hay una versión sin límite de longitud:

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

Se debe realizar una distancia de Hamming entre dos cadenas de igual longitud y con el orden tomado en cuenta.

Como sus documentos son ciertamente de diferente longitud y si las palabras lugares no cuentan, la similitud de coseno es mejor (tenga en cuenta que dependiendo de sus necesidades, existen mejores soluciones). :)

Aquí hay una función de similitud de coseno de 2 matrices 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() lugar de in_array() es un asesino en arreglos grandes).

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

Lo uso para detectar mensajes de publicación múltiple de textos "casi" copiados. Funciona bien. :)

El mejor enlace sobre 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-retrieval-tutorial/cosine-similarity-tutorial.html http://bioinformatics.oxfordjournals.org/cgi/content/full/22/18/2298