Сходство косинуса с расстоянием Хэмминга [закрыто]
-
09-09-2019 - |
Вопрос
Чтобы вычислить сходство между двумя документами, я создаю вектор признаков, содержащий термин frequencies (частоты).Но затем, для следующего шага, я не могу выбрать между "Косинусное сходство" и "Расстояние Хэмминга".
Мой вопрос:Есть ли у вас опыт работы с этими алгоритмами?Какой из них дает вам лучшие результаты?
В дополнение к этому:Не могли бы вы рассказать мне, как закодировать косинусное подобие в 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));
}
(Обратите внимание, что вы добавляете произведение количества токенов между двумя документами.)
Главное различие между ними заключается в том, что косинусное сходство даст более сильный показатель, если в двух документах несколько раз встречается одно и то же слово, в то время как Расстояние Хэмминга не имеет значения, как часто выпадают отдельные жетоны.
Редактировать:просто заметил ваш запрос об удалении функциональных слов и т.д.Я советую это, если вы собираетесь использовать косинусное подобие - поскольку функциональные слова встречаются довольно часто (по крайней мере, в английском языке), вы можете исказить результат, не отфильтровав их.Если вы используете расстояние Хэмминга, эффект будет не таким сильным, но в некоторых случаях он все еще может быть заметен.Кроме того, если у вас есть доступ к лемматизатор, это уменьшит количество пропусков, например, когда один документ содержит "галактики", а другой - "galaxy".
Каким бы путем вы ни пошли, удачи!
Я приношу извинения за игнорирование того факта, что вы сказали, что не хотите использовать какие-либо другие алгоритмы, но серьезно, Расстояние Левенштейна и Расстояние Дамерау-Левенштейн гораздо более чертовски полезны, чем дистанция Хэмминга.Вот такой Реализация расстояния D-L в 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];
}
Вот мой исправленный код для функции косинусного расстояния, опубликованный 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;
}