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

4 回答 4

17

应在两个长度相等的字符串之间进行汉明距离，并考虑顺序。

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

这是 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

于 2009-08-17T20:39:33.627 回答
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，例如，当一个文档包含“galaxies”而另一个文档包含“galaxy”时，它将减少未命中。

无论你走哪条路，祝你好运！

于 2009-06-03T16:44:39.997 回答
5

我很抱歉忽略了你说你不想使用任何其他算法的事实，但说真的，Levenshtein 距离和Damerau-Levenshtein 距离比 Hamming 距离更有用。这是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];
}
于 2009-06-03T16:37:56.293 回答
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;
}
于 2010-08-07T02:03:22.047 回答