Косинус сходство против расстояния Хэмминга

Чтобы вычислить сходство между двумя документами, я создаю вектор признаков, содержащий термины частот. Но затем, для следующего шага, я не могу решить между "" сходство с косинусом" и " Расстояние Хэмминга.

Мой вопрос: У вас есть опыт работы с этими алгоритмами? Какой из них дает вам лучшие результаты?

В дополнение к этому: Не могли бы вы рассказать мне, как закодировать сходство косинусов в PHP? Для расстояния Хэмминга у меня уже есть код:

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

Я не хочу использовать какой-либо другой алгоритм. Мне хотелось бы только помочь решить между ними.

И, может быть, кто-то может что-то сказать о том, как улучшить алгоритмы. Получите ли вы лучшие результаты, если отфильтровать слова остановки или общие слова?

Надеюсь, ты поможешь мне. Спасибо заранее!

Ответ 1

Расстояние Хэмминга должно быть выполнено между двумя строками равной длины и с учетом порядка.

Поскольку ваши документы, разумеется, имеют разную длину, и если слова не учитываются, лучше понимать сходство с косинусом (обратите внимание, что в зависимости от ваших потребностей существуют лучшие решения).:)

Вот функция подобия косинуса из 2 массивов слов:

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

Быстро (isset() вместо in_array() является убийцей на больших массивах).

Как вы можете видеть, результаты не учитывают "величину" каждого слова.

Я использую его для обнаружения сообщений с несколькими сообщениями "почти" скопированных текстов. Это работает хорошо.:)

Лучшая ссылка о показателях сходства строк: http://www.dcs.shef.ac.uk/~sam/stringmetrics.html

Для дальнейших интересных показаний:

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

Ответ 2

Если я ошибаюсь, думаю, у вас есть алгоритм на полпути между двумя алгоритмами. Для расстояния Хэмминга используйте:

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

(Обратите внимание, что вы добавляете только 1 для каждого согласованного элемента в векторах токена.)

И для сходства с косинусом используйте:

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

(Обратите внимание, что вы добавляете продукт из числа токенов между двумя документами.)

Основное различие между ними заключается в том, что сходство с косинусом даст более сильный индикатор, если два документа имеют одно и то же слово несколько раз в документах, а Расстояние Хэмминга не волнует, как часто индивидуальные жетоны появляются.

Изменить: просто заметил ваш запрос об удалении функциональных слов и т.д. Я рекомендую это, если вы собираетесь использовать сходство с косинусом - поскольку функциональные слова довольно часты (по крайней мере, на английском языке) вы можете перекосить результат, не отфильтровывая их. Если вы используете расстояние Хэмминга, эффект будет не таким большим, но в некоторых случаях он может быть заметным. Кроме того, если у вас есть доступ к lemmatizer, это уменьшит промахи, когда один документ содержит "галактики", а другой содержит "галактику", для экземпляр.

Каким бы способом вы ни отправились, удачи!

Ответ 3

Я прошу прощения за игнорирование того факта, что вы сказали, что не хотите использовать какие-либо другие алгоритмы, но серьезно, расстояние Левенштейна и Расстояние Дамерау-Левенштейна намного более полезно, чем расстояние Хэмминга. Здесь DL distance implementation в PHP, и если вам не нравится PHP-функция levenshtein(), которая, я думаю, вы не будете, потому что он имеет ограничение длины, здесь версия, не ограниченная по длине:

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

Ответ 4

Здесь мой исправленный код функции Cosine Distance, отправленный 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;
}