MinHash概述及举例

标签: minhash | 发表时间:2013-04-28 16:29 | 作者:
出处:http://www.iteye.com

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

 



已有 0 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [minhash] 推荐:

MinHash原理与应用

- - 淘宝网综合业务平台团队博客
MinHash首先它是一种基于. Jaccard Index 相似度的算法,也是一种 LSH的降维的方法,应用于大数据集的相似度检索、推荐系统. 下边按我的理解介绍下MinHash. 根据Jaccard Index公式,A,B的相似度 S(A,B) = |A ∩B|/|A∪ B| = 2/8 = 0.25, 用图表示如下:.

MinHash概述及举例

- - ITeye博客
MinHash可用于聚类,计算向量相似等,两个向量相似计算,通过minhash降维从而把计算量维持在一个常数级别,他是基于Jaccard Index 相似度的算法,也是一种LSH的降维的方法. A={中国,互联网,博客,Java,管理}. B={互联网,Java,金融,数据库,事务,源码}. S(A,B)=|A∩B|/|A∪B|=2/9,当为1的时候为极其相似可以认为是相同,因此MinHash也用于文本去重.