如果有N个集合，求它们之间两两的相似度就需要N*(N-1)/2次计算，当N很大时这个代价仍然承受不起。于是我们需要一种方法能够不遍历所有可 能的元素对就找出相似度较大的那些（大于某个给定的阈值t），这就是所谓Locality-Sensitive Hashing。第三章的后半部分基本全是围绕这一话题展开的。 这里又要出现一个比较神奇的方法了：由上篇文章所述，对每一列c（即每个集合）我们都计算出了n行minhash值，我们把这n个值均分成b组，每 组包含相邻的r=n/b行。对于每一列，把其每组的r个数都算一个hash值出来，把此列的编号...

本文作者Roba。 无意中发现这本貌似不错的书 Mining of Massive Datasets，随便记一下学到的东西。因为对数据挖掘没什么研究，理解肯定很肤浅，请过往大牛指教。下面内容来自此书第三章的前面部分。 在数据挖掘中经常需要用到比较两个东西的相似度。比如搜索引擎要避免非常相似的文档出现在结果的前几页，再比如很多网站上都有的“查找与你口味相似的用户”、“你可能喜欢什么什么”之类的功能。后者其实是很大的一块叫做“协同过滤”的研究领域，留待以后详谈。 首先我们定义两个集合S,T的Jaccard相似度: Sim(S,T) = |S...