有哪些经过验证的算法可以用于推荐相关文章？

Question

这种情况很常见。假设你有一个博客或新闻网站，有许多文章或博客或其他你称之为的内容，你想在每篇文章底部建议看起来相关的其他文章。

让我们假设每个项目都没有太多元数据。也就是说，没有标签、分类。将其视为一个大文本块，包括标题和作者名。

如何找到可能相关的文档呢？

我对实际算法非常感兴趣，而不是现成的解决方案，虽然我愿意查看用ruby或python实现的某些东西，或者依赖于mysql或pgsql。

编辑：目前的答案非常好，但我想看到更多。也许有一两个例子的真正基本代码。

- kch

---

我发现自己成为了一个糟糕的标记者。欢迎进行标记编辑。 - kch

请查看contest.github.com，那里有大量开源解决方案可供参考。 - Bob Aman

这里是完整的 Ruby 示例。 - akuhn

Answer 1

这是一个相当大的话题 - 除了人们在此提出的答案外，我建议跟踪一些信息检索课程的教学大纲，并查看为它们分配的教材和论文。话虽如此，以下是我自己研究生阶段的简要概述：

最简单的方法称为词袋。每个文档都被减少为一个稀疏向量{word: wordcount}对，您可以将NaiveBayes（或其他）分类器投向表示文档集合的向量集合，或者计算每个包与每个其他包之间的相似性得分（这称为k-nearest-neighbour分类）。KNN用于查找很快，但需要O(n^2)存储得分矩阵;然而，对于博客来说，n不是很大。对于像大报纸那样的东西，KNN很快变得不切实际，因此，即时分类算法有时更好。在这种情况下，您可以考虑使用排名支持向量机。SVM非常有用，因为它们不会限制您的线性相似度度量，并且仍然非常快。 Stemming是词袋技术的常见预处理步骤；这涉及到在计算词袋之前将形态上相关的单词，例如“cat”和“cats”，“Bob”和“Bob's”或“similar”和“similarly”缩小到它们的根。有许多不同的词干提取算法；维基百科页面链接到几个实现。

如果词袋相似度不够好，您可以将其抽象化到N元词袋相似度层面，其中您可以基于单词对或三元组创建表示文档的向量。 （您可以使用4元组甚至更大的元组，但在实践中，这并没有多大帮助。）这样做的缺点是会产生更大的向量，分类工作也会相应增加，但您得到的匹配结果将在句法上更接近。 另一方面，您可能不需要这种语义相似性； 它更适用于检测抄袭之类的东西。Chunking或将文档简化为轻量级解析树也可以使用（有树的分类算法），但这对于作者问题（“给定一个未知来源的文档，谁写了它？”）更有用。

也许对于您的用例来说，概念挖掘更有用，它涉及将单词映射到概念（使用像WordNet这样的词典），然后基于所使用的概念之间的相似性对文档进行分类。 由于从单词到概念的映射是还原的，因此这通常比基于单词的相似性分类更有效，但预处理步骤可能需要相当长的时间。

最后，有discourse parsing，它涉及解析文档的语义结构； 您可以在话语树上运行相似性分类器，就像在分块文档上一样。

这些几乎都涉及从非结构化文本生成元数据； 直接比较原始文本块是不可行的，因此人们首先将文档预处理为元数据。

- Meredith L. Patterson

---

这方面有哪些 C++ 库可用？此外，这些信息是否仍然相对最新？ - sinθ

Answer 2

你应该阅读《Programming Collective Intelligence: Building Smart Web 2.0 Applications》这本书（ISBN 0596529325）！

对于一些方法和代码：首先要问自己，您是想基于单词匹配找到直接相似性，还是想展示可能与当前文章没有直接关系，但属于同一篇文章群集的类似文章。

请参见 聚类分析/划分聚类。

一个非常简单（但理论上较慢）的查找直接相似性的方法是：

预处理：

1. 每篇文章存储平面单词列表（不要删除重复单词）。 2. “交叉联接”文章：计算文章A中与文章B相同的单词数。现在您有一个矩阵 int word_matches[narticles][narticles]（您不应该像那样存储它，A->B的相似度与B->A相同，因此稀疏矩阵可以节省将近一半的空间）。 3. 将word_matches计数归一化为0..1范围！ （找到最大计数，然后将任何计数除以此）-您应该在那里存储浮点数，而不是整数;)

查找相似文章：

1. 从单词匹配中选择与X最匹配的文章

- Frunsi

Answer 3

这是机器学习课程中研究的文档分类典型案例。如果你喜欢统计学、数学和计算机科学，我建议你看一下无监督方法，如kmeans++、贝叶斯方法和LDA。特别是贝叶斯方法非常擅长你所寻找的内容，唯一的问题是速度较慢（但除非你运行一个非常大的站点，否则这不应该对你产生太大的影响）。

从更实际和少一些理论的角度出发，我建议您查看这个和另一个优秀的代码示例。

- Davide

---

实际上，我认为这比“文档分类”的正常定义要困难得多。原因是什么？你试图打中一个移动的目标！你的类别是由你所阅读的文本所定义的，而不是由预定义的类别（如“垃圾邮件”、“代码”或“英语”）所定义的。 - San Jacinto

Answer 4

一个用Ruby实现的小型向量空间模型搜索引擎。基本思想是如果两个文档包含相同的单词，则它们相关。因此，我们计算每个文档中单词的出现次数，然后计算这些向量之间的余弦值（每个术语都有一个固定的索引，如果出现则在该索引处为1，否则为零）。如果两个文档具有所有术语共同点，则余弦值为1.0，如果它们没有共同点，则余弦值为0.0。您可以直接将其转换为％值。

terms = Hash.new{|h,k|h[k]=h.size}
docs = DATA.collect { |line| 
  name = line.match(/^\d+/)
  words = line.downcase.scan(/[a-z]+/)
  vector = [] 
  words.each { |word| vector[terms[word]] = 1 }
  {:name=>name,:vector=>vector}
}
current = docs.first # or any other
docs.sort_by { |doc| 
  # assume we have defined cosine on arrays
  doc[:vector].cosine(current[:vector]) 
}
related = docs[1..5].collect{|doc|doc[:name]}

puts related

__END__
0 Human machine interface for Lab ABC computer applications
1 A survey of user opinion of computer system response time
2 The EPS user interface management system
3 System and human system engineering testing of EPS
4 Relation of user-perceived response time to error measurement
5 The generation of random, binary, unordered trees
6 The intersection graph of paths in trees
7 Graph minors IV: Widths of trees and well-quasi-ordering
8 Graph minors: A survey

Array#cosine的定义留给读者自己练习（应该要处理nil值和不同长度，但这个问题可以用Array#zip来解决，对吧？）

顺便说一句，这些示例文档来自Deerwester等人的SVD论文 :)

- akuhn

Answer 5

前段时间我实现了类似的东西。也许这个想法现在已经过时了，但我希望它能有所帮助。

我运行了一个ASP 3.0网站，用于编程常见任务，并从以下原则开始：用户有疑问，只要他/她能在该主题上找到有趣的内容，就会停留在网站上。

当用户到达时，我启动了一个ASP 3.0 Session对象，并记录了所有用户导航，就像一个链接列表。在Session.OnEnd事件中，我获取第一个链接，查找下一个链接并增加计数器列，例如：

<Article Title="Cookie problem A">
    <NextPage Title="Cookie problem B" Count="5" />
    <NextPage Title="Cookie problem C" Count="2" />
</Article>

所以，为了检查相关文章，我只需要列出前 n 个按计数器列降序排列的 NextPage 实体。

- Rubens Farias