24

很常见的情况，我敢打赌。你有一个博客或新闻网站，你有很多文章或博客或任何你称之为的东西，你想在每一个的底部推荐其他似乎相关的东西。

让我们假设每个项目的元数据很少。也就是说，没有标签、类别。视为一大块文本，包括标题和作者姓名。

你如何去寻找可能相关的文件？

我对实际的算法很感兴趣，而不是现成的解决方案，尽管我可以看看用 ruby​​ 或 python 实现的东西，或者依赖 mysql 或 pgsql。

编辑：目前的答案很好，但我想看到更多。也许是一两件事的一些非常简单的示例代码。

4

5 回答 5

38

这是一个相当大的话题——除了人们在这里提出的答案之外，我建议跟踪几个信息检索课程的教学大纲，并查看分配给他们的教科书和论文。也就是说，这是我自己研究生时代的简要概述：

最简单的方法称为词袋。每个文档都被简化为一个稀疏向量{word: wordcount}对，您可以在代表您的文档集的向量集上扔一个 NaiveBayes（或其他一些）分类器，或者计算每个袋子和每个其他袋子之间的相似度分数（这称为k-最近邻分类）。KNN 查找速度很快，但得分矩阵需要 O(n^2) 存储；但是，对于博客来说，n 并不是很大。对于大型报纸大小的东西，KNN 很快变得不切实际，因此动态分类算法有时会更好。在这种情况下，您可以考虑使用排名支持向量机。SVM 很简洁，因为它们不会限制您使用线性相似性度量，并且仍然非常快。

词干提取是词袋技术的常见预处理步骤；这涉及在计算词袋之前将形态相关的词（例如“cat”和“cats”、“Bob”和“Bob's”或“similar”和“similarly”）减少到它们的根。有很多不同的词干算法。维基百科页面有几个实现的链接。

如果词袋相似度不够好，您可以将其抽象为 N-gram 袋相似度，在其中创建表示基于词对或词组的文档的向量。（您可以使用 4 元组甚至更大的元组，但实际上这并没有多大帮助。）这具有产生更大向量的缺点，因此分类将花费更多工作，但您获得的匹配会更接近在句法上。OTOH，您可能不需要这个语义相似性；它更适合剽窃检测之类的东西。也可以使用分块或将文档简化为轻量级解析树（树有分类算法），但这对于作者身份问题（“给定一个未知来源的文档，

也许对您的用例更有用的是概念挖掘，它涉及将单词映射到概念（使用诸如WordNet之类的同义词库），然后根据所用概念之间的相似性对文档进行分类。这通常比基于词的相似性分类更有效，因为从词到概念的映射是简化的，但预处理步骤可能相当耗时。

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

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

于 2009-08-10T13:25:43.590 回答
4

这是一个典型的文档分类案例，在机器学习的每一类中都有研究。如果你喜欢统计学、数学和计算机科学，我建议你看看无监督的方法，如kmeans++、贝叶斯方法和LDA。特别是，贝叶斯方法非常适合您要查找的内容，它们唯一的问题是速度很慢（但除非您运行一个非常大的站点，否则应该不会打扰您）。

在更实用且理论较少的方法上，我建议您查看this和this 其他出色的代码示例。

于 2009-12-06T05:06:11.207 回答
4

您应该阅读《编程集体智能：构建智能 Web 2.0 应用程序》（ISBN 0596529325）一书！

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

请参阅聚类分析/分区聚类。

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

预处理：

  1. 存储每篇文章的平面单词列表（不要删除重复的单词）。
  2. “交叉连接”文章：计算文章 A 中与文章 B 中相同单词匹配的单词数。你现在有一个矩阵int word_matches[narticles][narticles]（你不应该这样存储它，A->B 的相似性与 B->A 相同，所以稀疏矩阵几乎节省了一半的空间）。
  3. 将 word_matches 计数标准化为 0..1 范围！（找到最大计数，然后除以任何计数） - 你应该在那里存储浮点数，而不是整数；）

查找类似文章：

  1. 从 word_matches 中选择匹配度最高的 X 篇文章
于 2009-12-11T01:47:29.080 回答
3

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 论文：)

于 2009-12-06T11:59:33.390 回答
1

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

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

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

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

因此，要查看相关文章，我只需列出前n 个 NextPage实体，按计数器列降序排列。

于 2009-12-05T23:22:16.183 回答