MinHash原理与应用
- - 淘宝网综合业务平台团队博客MinHash首先它是一种基于. Jaccard Index 相似度的算法,也是一种 LSH的降维的方法,应用于大数据集的相似度检索、推荐系统. 下边按我的理解介绍下MinHash. 根据Jaccard Index公式,A,B的相似度 S(A,B) = |A ∩B|/|A∪ B| = 2/8 = 0.25, 用图表示如下:.
MinHash可用于聚类,计算向量相似等,两个向量相似计算,通过minhash降维从而把计算量维持在一个常数级别,他是基于Jaccard Index 相似度的算法,也是一种LSH的降维的方法。
举例描述:
A={中国,互联网,博客,Java,管理}
B={互联网,Java,金融,数据库,事务,源码}
那么A和B的相似值为:
S(A,B)=|A∩B|/|A∪B|=2/9,当为1的时候为极其相似可以认为是相同,因此MinHash也用于文本去重。
我们发现直接基于向量进行距离计算需要做如下操作:
1.string 转化成int,同时设置值
2.计算距离
3.如果集合足够大,那么这个向量维度就很大
如果直接基于集合进行合集并集运算那么也依赖于集合的基
我们可以通过minhash来把维度降低到常数级别记做N,是一种LSH的降维的方法不一定精确。
原理:
假如,我们随机从两个集合中各挑选一个元素s(A)、s(B),刚好这两个无素相同的概率 其实等同于,在A∪B这个大的随机域里,选中的元素落在A∩B这个区域的概率,这个概率就是S(A,B)
minhash的算法流程如下:
1.找N个随机hash函数;
2.对集合的每个元素进行hash,每次hash之后取集合元素hash值的最小值,这样就得到N个数值;
3.集合A和集合B的N个数值进行比较是否相等,相等累计记做n
4.S(A,B)=n/N