余弦相似度与汉明距离

Question

为了计算两个文档之间的相似性,我创建了一个包含术语频率的特征向量.但是,对于下一步,我不能在" 余弦相似度 "和" 汉明距离 " 之间做出决定.

我的问题:您对这些算法有经验吗？哪一个给你更好的结果？

除此之外:你能告诉我如何在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));
}

我不想使用任何其他算法.我只想帮助两者之间做出决定.

也许有人可以说一些如何改进算法.如果你过滤掉停用词或常用词,你会得到更好的结果吗？

我希望你能帮助我.提前致谢!

Answer 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

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

(请注意,您要在两个文档之间添加令牌计数的产品.)

两者之间的主要区别在于,当两个文档在文档中多次具有相同的单词时,余弦相似性将产生更强的指示,而汉明距离并不关心单个令牌出现的频率.

编辑:刚刚注意到你关于删除功能词等的查询.如果你要使用余弦相似性,我建议你这样做 - 因为功能词是非常频繁的(至少在英语中),你可能会因为没有过滤它们而扭曲结果.如果使用汉明距离,效果将不会那么大,但在某些情况下仍然可以理解.此外,如果您可以访问一个词形变换器,那么当一个文档包含"星系"而另一个文档包含"星系"时,它将减少未命中.

无论你走哪条路,祝你好运!

Answer 3

我为忽略你说你不想使用任何其他算法的事实而道歉,但严重的是,Levenshtein距离和Damerau-Levenshtein距离比汉明距离更有用.这是PHP中的DL距离实现,如果你不喜欢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];
}