Чтобы вычислить сходство между двумя документами, я создаю вектор признаков, содержащий термин «частоты». Но затем, для следующего шага, я не могу решить между « сходством Косина » и « расстоянием Хэмминга ».
Мой вопрос: Есть ли у вас опыт работы с этими алгоритмами? Какой из них дает вам лучшие результаты?
В дополнение к этому: Не могли бы вы рассказать мне, как закодировать сходство косинусов в 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)); } Я не хочу использовать какой-либо другой алгоритм. Мне хотелось бы только помочь решить, между тем и другим.
И, может быть, кто-то может что-то сказать о том, как улучшить алгоритмы. Получите ли вы лучшие результаты, если отфильтровать слова остановки или общие слова?
Я надеюсь, что вы можете мне помочь. Заранее спасибо!
Расстояние Хэмминга должно быть выполнено между двумя строками равной длины и с учетом порядка.
Поскольку ваши документы, разумеется, имеют разную длину, и если слова не учитываются, косинус-сходство лучше (обратите внимание, что в зависимости от ваших потребностей существуют лучшие решения). 🙂
Вот функция подобия косинуса из 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
Если я не ошибаюсь, я думаю, что у вас есть алгоритм на полпути между двумя алгоритмами . Для расстояния Хэмминга используйте:
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 , это уменьшит промахи, когда один документ содержит «галактики», а другой, например, содержит «галактику».
Каким бы способом вы ни отправились, удачи!
Я прошу прощения за игнорирование того факта, что вы сказали, что не хотите использовать какие-либо другие алгоритмы, но серьезно, расстояние Левенштейна и расстояние Дамерау-Левенштейна намного более полезны, чем расстояние Хэмминга. Вот реализация DL-расстояния в PHP , и если вам не нравится функция родного levenshtein() PHP, которая, я думаю, вы не будете, потому что она имеет ограничение по длине, вот версия, ограниченная длиной:
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]; }
Здесь мой исправленный код для функции 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; }