← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 1781.b

倒排算相似

理解等级:未标注

文档两两相似度直接计算是 O(n²)。倒排索引把视角转为“同一词贡献哪些文档对”,只累加共享词的贡献,利用文本向量稀疏性省掉大量零乘法。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 机器学习:分布式算法 · 查看原书依据

      有了上述计算两个文档相似性的公式,就可以在此基础上计算文档集合内任意两个文档的文本相似性。一种简单粗暴的方式是对任意两个文档根据公式24进行计算,但是其实我们可以按照公式25所示的思想对其进行优化。优化的基本思路是:对于任意两个文档来说,考虑任意单词t对于其相似性计算的影响,很明显,如果t在任意一个文档中没有出现,则其对两者相似性贡献为0,也即只有两个文档同时包含单词t,那么单词t才对这两者相似性有影响。如果从单词t的角度出发,如果能够记录哪些文档包含了单词t,并形成一个集合,那么对单词t来说,其只对集合中文档的两两相似性做出贡献。举个例子,假设单词t只出现在x、y和z三个文档,那么对于单词t来说,只需计算其对(x,y)、(x,z)以及(y,z)的相似性贡献即可。熟悉搜索引擎工作机制的读者会发现,记录包含单词t的文档集合其实就是搜索引擎的倒排索引。

    参考来源

    - 位置:《大数据日知录:架构与算法》第16章《机器学习:分布式算法》"16.4 自然语言处理:文档相似性计算"一节(源文件:_epub-src/OEBPS/text00021.html) - 结论依据:原文明确"如果t在任意一个文档中没有出现,则其对两者相似性贡献为0,也即只有两个文档同时包含单词t,那么单词t才对这两者相似性有影响……记录包含单词t的文档集合其实就是搜索引擎的倒排索引……通过累计每个单词对任意两个文档之间的相似性的贡献来最终求得整体相似性",避免了对不共享词的文档对做无效计算。 - 原始内容:如果t在任意一个文档中没有出现,则其对两者相似性贡献为0,也即只有两个文档同时包含单词t,那么单词t才对这两者相似性有影响……记录包含单词t的文档集合其实就是搜索引擎的倒排索引……上述计算流程的基本思路是通过累计每个单词对任意两个文档之间的相似性的贡献来最终求得整体相似性。