4.3 基于MinHash的相似性算法

MinHash也称为最小哈希式独立排列局部性敏感哈希，是一种非常快速的对两个不同集合进行相似性分析的方法。该算法起初主要用于在搜索引擎中的重复网页检查，现在也应用于解决大规模聚类问题。

4.3.1 与Jaccard相似性关系

采用MinHash可以减小过程中的计算复杂度。其基本原理为有两个集合A、B，在集合A与集合B的并集中，选取的元素同时也在集合A和集合B中的概率等于Jaccard的相似度。

4.3.2 计算网页文本相似性过程

整个计算流程依然基于Jaccard相似系数，不同的是引入了哈希函数的机制。

对于集合A和集合B，选取出计算过程中哈希值最小的元素，在集合A和集合B中最小哈希值相等的概率即为集合A和集合B的相似度。通过两个哈希方法之后，转换为求新集合的Jaccard相似度。

MinHash实质也是一种降维技术，降维后的数据计算复杂度会减小很多。