MinHash概述及举例

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

 

评论

2 楼 小网客 2014-06-05  

orozcohsu 写道

您好，

對於您提到的 "string 转化成int" 部分，是否可以請您舉例可能有的作法?

例如:
A={中国,互联网,博客,Java,管理}

B={互联网,Java,金融,数据库,事务,源码}

這要怎麼化為 int 呢?

謝謝您


[e-mail]

那个是向量化的过程，最笨的方式就是直接取其hash值，如果进行统一编码的那么那么可以从0开始编码，如果基于hash值的话可以在hash值上面做扩展，比如采用改进的FNV_32

1 楼 orozcohsu 2014-05-26  

您好，

對於您提到的 "string 转化成int" 部分，是否可以請您舉例可能有的作法?

例如:
A={中国,互联网,博客,Java,管理}

B={互联网,Java,金融,数据库,事务,源码}

這要怎麼化為 int 呢?

謝謝您


[e-mail]