标签：MinHash

MinHash原理与应用

这篇讲的是MinHash算法，一种基于Jaccard相似度的高效降维技术，专门用于处理大数据集的相似度计算问题。作者从Jaccard Index的定义出发，解释了直接计算集合交集和并集在海量数据下计算资源消耗过大，几乎不可行。MinHash的核心原理是通过随机哈希函数将集合元素映射为哈希值，并取最小哈希值作为签名，因为两个集合的最小哈希值相等的概率正好等于它们的Jaccard相似度，从而将高维数据降维为固定长度的签名向量。 文章进一步展示了MinHash的实际应用，比如在Mahout中用于聚类，以及在一个推荐系统案例中：针对几十万优质用户推荐给几千万普通用户，先用MinHash按相同哈希值个数排序筛选出备选集，再计算余弦相似度取TOPN。这种方法虽然在计算量上仍非最优，但在可接受时间范围内，效果接近两两计算余弦相似度的最优解，尤其适合集合量级差异较大的场景，如大规模用户推荐。