nlp - 查找相似/相关文本算法

Question

我在 stackoverflow 和 Google 中搜索了很多，但没有找到最好的答案。实际上，我打算开发一个新闻阅读器系统，从网络上爬取和收集新闻（使用爬虫），然后，我想在网站中找到相似或相关的新闻（为了防止在网站上显示重复的新闻）

我认为最好的活生生的例子是谷歌新闻，它从网络上收集新闻，然后分类并找到相关的新闻和文章。这就是我想做的。

这样做的最佳算法是什么？

Answer 1

一个相对简单的解决方案是为每个文档计算一个 tf-idf 向量 (en.wikipedia.org/wiki/Tf*idf)，然后使用这些向量之间的余弦距离 (en.wikipedia.org/wiki/Cosine_similarity) 作为估计文章之间的语义距离。

这可能会比 Levenstein 距离更好地捕捉语义关系，并且计算速度要快得多。

Answer 2

这是一个：http ://en.wikipedia.org/wiki/Levenshtein_distance

public static SqlInt32 ComputeLevenstheinDistance(SqlString firstString, SqlString secondString)
{
    int n = firstString.Value.Length;
    int m = secondString.Value.Length;
    int[,] d = new int[n + 1,m + 1];

    // Step 1
    if (n == 0)
    {
        return m;
    }

    if (m == 0)
    {
        return n;
    }

    // Step 2
    for (int i = 0; i <= n; d[i, 0] = i++)
    {
    }

    for (int j = 0; j <= m; d[0, j] = j++)
    {
    }

    // Step 3
    for (int i = 1; i <= n; i++)
    {
        //Step 4
        for (int j = 1; j <= m; j++)
        {
            // Step 5
            int cost = (secondString.Value[j - 1] == firstString.Value[i - 1]) ? 0 : 1;

            // Step 6
            d[i, j] = Math.Min(Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1), d[i - 1, j - 1] + cost);
        }
    }
    // Step 7
    return d[n, m];
}

这对于手头的任务很方便：http ://code.google.com/p/boilerpipe/

另外，如果您需要减少要分析的单词数，请尝试以下操作：http: //ots.codeplex.com/

我发现 OTS 在情感分析中非常有用，我可以将句子的数量减少到一个小的常用短语和/或单词列表中，并据此计算整体情绪。这同样适用于相似性。