logo标签列表

余弦相似度与汉明距离

phprelationshipsimilarity
18
为了计算两个文档之间的相似度，我创建了一个包含术语频率的特征向量。但是，在下一步中，我无法决定使用 "余弦相似度" 还是 "汉明距离"。
我的问题是：您是否有这些算法的经验？哪一个给您带来更好的结果？
此外：您能告诉我如何在 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));
}

我不想使用其他算法，我只希望获得在两者之间做决策的帮助。
也许有人可以谈谈如何改进算法。如果过滤掉停用词或常用词，是否会获得更好的结果？
希望你能帮助我。提前感谢！
4个回答
18

对于两个等长的字符串，应该考虑顺序计算汉明距离。

由于您的文档长度肯定不同，并且如果单词位置不重要，则余弦相似度更好（请注意，根据您的需求，存在更好的解决方案）。 :)

这是一个可以计算两个单词数组的余弦相似度函数：

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

非常感谢。 :) 但是Mike的解决方案（被选为答案）不是更好吗？代码更短，速度似乎和你的一样快。有什么区别？ - caw
1
Mike的函数并不是非常准确。尝试使用echo check(array('a', 'b', 'c'), array('a', 'b', 'c'));。它应该返回1（cos（0）），但他的函数返回0.33。:( - Toto
你的函数真的正确吗？对于[1, 1, 1]和[1, 1, 0]，它给出了0.71。但是http://www.miislita.com/searchito/binary-similarity-calculator.html给出了0.82？！仍然需要将相似度值除以文档长度吗？ - caw
1
这个工具是用于二进制字符串比较的。而“我的”函数则是用于“单词文档”的。结果会有所不同。 :) - Toto
好的，谢谢。我正在寻找一些比较工具，因为这次我想确保我有正确的函数；） 而且，由于长度在余弦相似度中没有作用，所以我不需要将值除以文档的长度，对吧？ - caw
9
除非我理解有误，否则我认为您的算法介于这两个算法之间。如果使用汉明距离，请使用以下内容：
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，它将减少一个文档包含“星系”而另一个文档包含“星系”的错误。无论您选择哪种方式，祝你好运！）
$counts1包含文本中所有单词作为键和它们出现次数作为值。如果您看到array_count_values()的操作，这将变得清晰明了。也许您真的误解了我的代码！？那么什么更好？我的代码（介于两种算法之间）还是余弦相似度？ - caw
是的，那么你的余弦相似度代码有效。谢谢！ :) 但是它比我的“两种算法之间的折中代码”更好吗？有什么区别？ - caw
1
这个余弦相似度函数有点奇怪。在这种情况下，结果不应该是1吗：echo check（array（'a'，'b'，'c'），array（'a'，'b'，'c'））; 而我得到的是0.333，这是与echo check（array（'a '，' b'，' c'），array（'a'，' b'））相同的结果。 - Toto
1
Toto是正确的。两个距离函数的向量范数计算是不正确的。 - outis
我写了一个小函数来计算余弦相似度（在此页面底部）。希望这能有所帮助。 :) - Toto
显示剩余11条评论
5

很抱歉忽略了你说不想使用其他算法的事实，但是，Levenshtein距离和Damerau-Levenshtein距离比汉明距离更加有用。这里有一个PHP中的D-L距离实现，如果你不喜欢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];
}
谢谢。我觉得你误解了一些事情。我不想只使用汉明距离。我想将其应用于文本的特征向量，而不是文本本身。所以我认为它比莱文斯坦距离更有用，对吧？;)但是感谢您提供的代码，我相信它对许多用户有其他用途的用处。 - caw
哎呀，我确实没能理解特征向量部分。不过没关系。 :) 既然你喜欢这段代码，我就不删回答了。希望那些踩我的人能宽容一点。 :) - chaos
是的，他们有。赞成者比反对者多。 ;) - caw
2
Levenshtein应该用来计算编辑距离。因此，它取决于需求。对于“ANNA FRED”和“FRED ANNA”，Levenshtein将给出一个较高的数字，但对于余弦相似度（针对单词），它将是100％相似的。相似还是不相似？这取决于您的需求。 - Toto
2
这是我对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;
}
1
$x（和$y）将始终为1（令牌存在）或0（令牌不存在）。在这种情况下，POW（$x，2）将始终返回$x。因此，我将其删除以节省CPU资源。 :) - Toto
你们两个的版本都正确吗，Lorenzo和Toto？它们都能工作？ - caw
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接