精华内容
下载资源
问答
  • MinHash

    2014-10-08 10:24:54
    MinHash[1] 也是LSH的一种,可以用来快速估算两个集合的相似度。MinHash由Andrei Broder提出,最初用于在搜索引擎中检测重复网页。它也可以应用于大规模聚类问题。
     
    

    传统的hash算法只负责将原始内容尽量均匀随机地映射为一个签名值,原理上相当于伪随机数产生算法。传统hash算法产生的两个签名,如果相等,说明原始内容在一定概率下是相等的;如果不相等,除了说明原始内容不相等外,不再提供任何信息,因为即使原始内容只相差一个字节,所产生的签名也很可能差别极大。从这个意义上来说,要设计一个hash算法,对相似的内容产生的签名也相近,是更为艰难的任务,因为它的签名值除了提供原始内容是否相等的信息外,还能额外提供不相等的原始内容的差异程度的信息。

    MinHash 也是LSH的一种,可以用来快速估算两个集合的相似度。MinHash由AndreiBroder提出,最初用于在搜索引擎中检测重复网页。它也可以应用于大规模聚类问题。

    Jaccardindex

    Jaccard index 是用来计算相似性,也就是距离的一种度量标准。假如有集合A、B,那么

    J(A,B)=(A intersection B)/(Aunion B)

    也就是说,集合A,B的Jaccard系数等于A,B中共同拥有的元素数与A,B总共拥有的元素数的比例。很显然,Jaccard系数值区间为[0,1]。

    MinHash

    先定义几个符号术语:

    h(x): 把x映射成一个整数的哈希函数。

    hmin(S):集合S中的元素经过h(x)哈希后,具有最小哈希值的元素。

    那么对集合A、B,hmin(A) = hmin(B)成立的条件是A B 中具有最小哈希值的元素也在 ∩B中。这里

    有一个假设,h(x)是一个良好的哈希函数,它具有很好的均匀性,能够把不同元素映射成不同的整数。

    所以有,Pr[hmin(A) = hmin(B)] = J(A,B),即集合A和B的相似度为集合A、B经过hash后最小哈希值相等的概率。

    有了上面的结论,我们便可以根据MinHash来计算两个集合的相似度了。一般有两种方法:

    第一种:使用多个hash函数

    为了计算集合A、B具有最小哈希值的概率,我们可以选择一定数量的hash函数,比如K个。然后用这K个hash函数分别对集合A、B求哈希值,对

    每个集合都得到K个最小值。比如Min(A)k={a1,a2,...,ak},Min(B)k={b1,b2,...,bk}。

    那么,集合A、B的相似度为|Min(A)k ∩ Min(B)k| /|Min(A)kMin(B)k|,即Min(A)k和Min(B)k中相同元素个数与总的元素个数的比例。

    第二种:使用单个hash函数

    第一种方法有一个很明显的缺陷,那就是计算复杂度高。使用单个hash函数是怎么解决这个问题的呢?请看:

    前面我们定义过 hmin(S)为集合S中具有最小哈希值的一个元素,那么我们也可以定义hmink(S)为集合S中具有最小哈希值的K个元素。这样一来,

    我们就只需要对每个集合求一次哈希,然后取最小的K个元素。计算两个集合A、B的相似度,就是集合A中最小的K个元素与集合B中最小的K个元素的交集个数与并集个数的比例。

     


    展开全文
  • minhash

    2014-09-10 11:23:00
    minhash是一种基于jaccard index 相似度的算法。属于LSH(Location Sensitive Hash)家族中的一员。  jaccard index :有两个集合A={a , b , c , d , e } ,B={a , e , f , g},根据jaccard index 来计算两个集合的...

     

      minhash是一种基于jaccard index 相似度的算法。属于LSH(Location Sensitive Hash)家族中的一员。

      jaccard index :有两个集合A={a , b , c , d , e } ,B={a , e , f , g},根据jaccard index 来计算两个集合的相似度Jaccard(A,B)=|A∩B| / |AUB|=2/7≈0.2857

      当集合较大或者集合数量过多时,直接计算集合交集与并集过于耗时,因此提出了minhash方法。

      minhash:

    A∩B={a , e}   AUB = {a , b , c , d , e , f , g} , 这里,我们假如要从AUB中随机挑选一个元素,毫无疑问这个元素属于A∩B的概率也为2/7,即与A,B的jaccard相似度相等,这里,我们假设自己有A , B集合中有很多数据,我们不方便直接计算A∩B , 但是我们可以从A中随机抽取部分(可以按比例)数据记作AA,从B中也随机抽取部分(可以按比例)数据 记作BB,则从AAUBB中随机抽取一个元素,这个元素落在AA∩BB中的概率 等 AA∩BB / AAUBB = A∩B / AUB,而这就是minhash降维的基本原理。(minhash算法中,不是随机抽取的)

             在minhash算法中我们是采用hash函数来随机抽取原A、B集合的子集的。(这里说的随机不是真正意义上的随机,hash函数实际上是对全集U中的元素进行了映射,U中的每个元素在同一个hash函数下被映射成不同的数字,其实是对U集元素的一个排列),下面具体讲下minhash算法

             算法:

    1. 使用多个hash functions 时

        最简单的minhash方案就是使用k个hash函数,这里k为正整数。依次取每个hash函数对集合中的所有函数进行hash运算,取每个hash函数对应的最小值。这样我们对每个集合都取到了k个值,这k个值就的集合就是原集合的minhash , 相似度估计为两个集合的minhash的交集除以k。

      2. 使用单个hash function

        a)      使用单个hash functions 时,只是使用一个hash function 对集合进行hash,取前k个最小的值组成minhash,其余与使用多个hash functions 一样。

      3. 在处理大数据中的方法

        a)      矩阵:其实当我们使用一个hash function 对集合进行hash时,其时就是对集合进行排列,而取最小的一个值,我们可以理解为排列为升序,而我们取的是列顶元素。根据这个原理我们可以简化处理大数据中的一些运算,具体方法这里不做细解。

        b)     分布式:mahout中集成了minhash算法,算法采用了多个hash functions,但不同的是mahout minhash中引入了一个group的方法,这个group方法通过指定的整数,把生成的minhash截成若干个字符串,这样就可以把这些个字符串当成原始集合的hash指纹,这里group的值越大(小于等于k),相似度阈值越高。具体细节  这里也不赘述。

        c)      合并相同指纹时的算法:在使用分布式时,由于算法通过group算法生成的是一系列的短指纹(把原来的minhash信息指纹截取了),判定是只有两个短指纹完全相等,两个集合才相等。这是个两两比较的问题,直接计算时间复杂度过高,可以用并查集算法解决。至于并查集算法 ,这里也不做赘述。

     

    注:本文只是对minhash的简单使用笔记,以防以后忘记,写的很水,如有写错的地方,欢迎指点。

     

    展开全文
  • MinHash库 概述 该库提供了用于b位MinHash算法的工具。 问题/问题 请提出。 (日本论坛在。) 安装 玛文 将以下依赖项放入pom.xml中: < groupId>org.codelibs < artifactId>minhash < version>0.2.0 参考 ...
  • minhash实验.zip

    2020-06-30 18:37:11
    实时大数据分析minhash算法 报告,源代码和数据集 采用Minhash技术两个文本数据集Amazon News和Google Report的Jaccard相似度,给出两个集合中每条记录在另一个集合中相似度最高的记录,作为匹配结果输出。
  • MinHash.java

    2019-06-20 16:22:06
    java实现的MinHash算法,用于大批量的文本检测重复度。
  • MinHash算法

    2021-05-16 23:27:44
    当这两个集合里的元素数量异常大(特征空间维数很大),同时又有很多个集合需要判断两两间的相似度时,传统方法会变得十分耗时,最小哈希(minHash)可以用来解决该问题。 Jaccard相似度 首先看看Jaccard相似度。...

     在数据挖掘中,一个最基本的问题就是比较两个集合的相似度。通常通过遍历这两个集合中的所有元素,统计这两个集合中相同元素的个数,来表示集合的相似度;这一步也可以看成特征向量间相似度的计算(欧氏距离,余弦相似度)。当这两个集合里的元素数量异常大(特征空间维数很大),同时又有很多个集合需要判断两两间的相似度时,传统方法会变得十分耗时,最小哈希(minHash)可以用来解决该问题。

    Jaccard相似度

    首先看看Jaccard相似度。假设有两个集合A,B,则

           Jaccard(A, B)= \frac{\left | A\cap B \right |}{\left | A\cup B \right |}

    最小哈希(minHash)

    一个很大的集合进行哈希处理的过程其实是由很多小的哈希过程组成。而这些最小的哈希过程就被称为是最小哈希。最小哈希的具体内容就是把一个集合映射到一个编号上。

    比如对于集合U={a,b,c,d,e},S1:{a,d},S2:{c},S3:{b,d,e},S4:{a,c,d},用一个矩阵形式来表示他们:

    那么,对他进行一次最小哈希就是在经过随机的行排列之后,对于每个集合,从上到下取第一个数值为1的那一行的行号。

    比如对上面的矩阵进行随机行排列后变成:

    那么每个集合的minhash结果就应该是h(S1)=2,h(S2)=4,h(S3)=0,h(S4)=2。

     在经过随机行打乱后,两个集合的最小哈希值相等的概率等于这两个集合的Jaccard相似度,证明如下:

           现仅考虑集合S1和S2,那么这两列所在的行有下面3种类型:
           1、S1和S2的值都为1,记为X
           2、只有一个值为1,另一个值为0,记为Y
           3、S1和S2的值都为0,记为Z

           S1和S2交集的元素个数为x,并集的元素个数为x+y,所以sim(S1,S2) = Jaccard(S1,S2) = x/(x+y)。接下来计算h(S1)=h(S2)的概率,经过随机行打乱后,从上往下扫描,在碰到Y行之前碰到X行的概率为x/(x+y),即h(S1)=h(S2)的概率为x/(x+y)。

    这就是minhash的基本方法。

    最小哈希签名

    其实得到上面的签名矩阵之后,我们就可以用签名矩阵中列与列之间的相似度来计算集合间的Jaccard相似度了;但是这样会带来一个问题,就是当一个特征矩阵很大时(假设有上亿行),那么对其进行行打乱是非常耗时,更要命的是还要进行多次行打乱。              

    为了解决这个问题,可以通过一些随机哈希函数来模拟行打乱的效果。就是再用一个哈希函数,将行号进行哈希变换。比如当n=5时,对0,1,2,3,4这5个数,可以用h(x)=(3x+1)的方法进行映射,得到1,4,2,0,3。当然,随便找的h(x)=ax+b这种哈希函数显然可能会冲突,不过只要n和a互素,那么生成的一定是一个排列,这一点用同余类的知识很好证明。

    以(x+1)mod5,(3x+1)mod5为例,处理过程如下:

     s1s2s3s4h1(x+1mod5)h2(3x+1mod5)
    0100111
    1001024
    2010132
    3101140
    4001003

     我们用h1、h2两个hash函数产生了两个行号顺序,那么接下来就是关键步骤了:

    初始化都是inf:

    \s1s2s3s4
    h1infinf0inf
    h2infinfinfinf

    比如求文档s1的值。遍历s1相应的单词,从第0行到第4行:

    1. 第0行为1,看一下h1计算出来的行号为1<inf,赋值h1为1(就是行号)。继续遍历
    2. 第1行为0,不关心,跳过
    3. 第2行为0,不关心。跳过
    4. 第3行为1, 看一下h1计算出来的行号为4。4大于此时h1的值,h1的值不变。假设小于h1此时的值,将值付给h1
    5. 第4行为0。不关心,跳过

    遍历完了之后此时h1的值就是1,能够看到。我们事实上在做的就是遍历矩阵中的值,对0的不关心。跳过。对1的。看一下hash函数产生的行号,找到行号最小的值作为h1输出的值。同理,h2也一样,最后得到例如以下的签名矩阵矩阵

    \s1s2s3s4
    h11301
    h21200

    这个时候就能够计算相似度了:

    • sim(s1,s2)=0
    • sim(s1,s4)=0.5
    • sim(s3,s4)=0.5

    局部敏感哈希算法(LSH)

    通过上面的方法处理过后,一篇文档可以用一个很小的签名矩阵来表示,将文档进行了压缩,比如使用了30个hash函数。那么就将一篇文档压缩成了30位表示,节省下很多内存空间;但是,还有一个问题没有解决,那就是如果有很多篇文档,那么如果要找出相似度很高的文档,其中一种办法就是先计算出所有文档的签名矩阵,然后依次两两比较签名矩阵的两两;这样做的缺点是当文档数量很多时,要比较的次数会非常大。那么我们可不可以只比较那些相似度可能会很高的文档,而直接忽略过那些相似度很低的文档。

    首先,我们可以通过上面的方法得到一个签名矩阵,然后把这个矩阵划分成b个行条(band),每个行条由r行组成。对于每个行条,存在一个哈希函数能够将行条中的每r个整数组成的列向量(行条中的每一列)映射到某个桶中。可以对所有行条使用相同的哈希函数,但是对于每个行条我们都使用一个独立的桶数组,因此即便是不同行条中的相同列向量,也不会被哈希到同一个桶中。这样,只要两个集合在某个行条中有落在相同桶的两列,这两个集合就被认为可能相似度比较高,作为后续计算的候选对;下面直接看一个例子:

    例如,现在有一个12行签名矩阵,把这个矩阵分为4个行条,每个行条有3行;为了方便,这里只写出行条1的内容。

     

    可以看出,行条1中第2列和第4列的内容都为[0,2,1],所以这两列会落在行条1下的相同桶中,因此不论在剩下的3个行条中这两列是否有落在相同桶中,这两个集合都会成为候选对。在行条1中不相等的两列还有另外的3次机会成为候选对,因为他们只需在剩下的3个行条中有一次相等即可。
    对于S2,我们仅需要寻找那些桶相同的集合来计算相似度,例如:

    我们仅需要计算sim(S2, S3),sim(S2, S4),sim(S2, S5),因为这些集合出现过与S2桶相同的情况。

    两者的应用

    1.谷歌新闻推荐论文中使用到了Min hash。这里涉及推荐,使用用户看过的所有的新闻集合表示用户。这里每个用户可以用一个取值0/1的向量表示(每个维度代表新闻,取值代表是否看过该新闻)。这里选用的方法是Min Hash。文章将Min Hash看作是聚类算法,因为哈希后的不同桶可以看做不同的簇。

    具体算法是对用户看过的新闻集合进行随机排列,第一个新闻的序号就是最小哈希的结果。但是由于新闻集合太大,显示的随机排列是不可取的。文章里面用哈希的方法模拟随机排列的过程,将每个新闻哈希到0到N,取哈希结果最小的那篇新闻的序号即可。

    2.谷歌网页去重论文中使用到了Sim hash。这里用一个高维向量表示表示一个网页。这里每维度的值是一个实数(不是binary)故选用SimHash。使用SimHash将高维向量降维成64位0/1的指纹。之后文章提出了如何找出指纹库中与给定指纹相差最多3位的所有指纹,查询效率关于时间和空间的权衡,非常有意思。


    参考:

    1. https://www.cnblogs.com/mengfanrong/p/5058919.html
    2. https://www.cnblogs.com/sddai/p/6110704.html
    3. https://blog.mythsman.com/post/5d2b376225601931a5f8d706/
    4. https://blog.csdn.net/dm_ustc/article/details/45626907
    展开全文
  • 最近实现了一把MinHashMinHashLSH算法,发现实现的细节还是挺难的,所以我把datasketch的源代码改了一下,去除了很多冗余的代码,保留了算法的实现主要细节部分。 MinHash算法: import hashlib import numpy ...

    最近实现了一把MinHash和MinHashLSH算法,发现实现的细节还是挺难的,所以我把datasketch的源代码改了一下,去除了很多冗余的代码,保留了算法的实现主要细节部分。

    MinHash算法:

    import hashlib
    import numpy as np
    
    def sha1_hash32(data):
        return struct.unpack('<I', hashlib.sha1(data).digest()[:4])[0]
    _mersenne_prime = (1 << 61) - 1
    _max_hash = (1 << 32) - 1
    _hash_range = (1 << 32)
    
    
    class MinHash(object):
    
        def __init__(self, d=128, seed=1,
                hashfunc=sha1_hash32,
                hashvalues=None, permutations=None):
            if hashvalues is not None:
                d = len(hashvalues)
            self.seed = seed
            # Check the hash function.
            if not callable(hashfunc):
                raise ValueError("The hashfunc must be a callable.")
            self.hashfunc = hashfunc
        
            # Initialize hash values
            if hashvalues is not None:
                self.hashvalues = self._parse_hashvalues(hashvalues)
            else:
                self.hashvalues = self._init_hashvalues(d)
            if permutations is not None:
                self.permutations = permutations
            else:
                generator = np.random.RandomState(self.seed)
                self.permutations = np.array([(generator.randint(1, _mersenne_prime, dtype=np.uint64),
                                               generator.randint(0, _mersenne_prime, dtype=np.uint64))
                                              for _ in range(d)], dtype=np.uint64).T
            if len(self) != len(self.permutations[0]):
                raise ValueError("Numbers of hash values and permutations mismatch")
    
        def _init_hashvalues(self, d):
            return np.ones(d, dtype=np.uint64)*_max_hash
    
        def _parse_hashvalues(self, hashvalues):
            return np.array(hashvalues, dtype=np.uint64)
    
        def add(self, b):
    
            hv = self.hashfunc(b)
            a, b = self.permutations
            phv = np.bitwise_and((a * hv + b) % _mersenne_prime, np.uint64(_max_hash))
            self.hashvalues = np.minimum(phv, self.hashvalues)
    
        def jaccard(self, other):
    
            if other.seed != self.seed:
                raise ValueError("different seeds")
            if len(self) != len(other):
                raise ValueError("different numbers of permutation functions")
            return np.float(np.count_nonzero(self.hashvalues==other.hashvalues)) /  np.float(len(self))
    
    
        def __len__(self):
            return len(self.hashvalues)
    
        def __eq__(self, other):
            return type(self) is type(other) and  self.seed == other.seed and np.array_equal(self.hashvalues, other.hashvalues)

    然后是MinhashLSH

     

    class DictListStorage():
        
        def __getitem__(self, key):
            return self.get(key)
    
        def __delitem__(self, key):
            return self.remove(key)
    
        def __len__(self):
            return self.size()
    
        def __iter__(self):
            for key in self.keys():
                yield key
                
        def __init__(self, config,name):
            self._dict = defaultdict(list)
    
        def keys(self):
            return self._dict.keys()
    
        def get(self, key):
            return self._dict.get(key, [])
    
        def insert(self, key, *vals, **kwargs):
            self._dict[key].extend(vals)
    
        def size(self):
            return len(self._dict)
    
        def itemcounts(self, **kwargs):
            return {k: len(v) for k, v in self._dict.items()}
    
        def has_key(self, key):
            return key in self._dict
    class DictSetStorage():
        def __init__(self, config,name):
            self._dict = defaultdict(set)
    
        def get(self, key):
            return self._dict.get(key, set())
    
        def insert(self, key, *vals, **kwargs):
            self._dict[key].update(vals)
    def _random_name(length):
        return ''.join(random.choice(string.ascii_lowercase)
                       for _ in range(length)).encode('utf8')
    
    def _false_positive_probability(threshold, b, r):
        _probability = lambda s : 1 - (1 - s**float(r))**float(b)
        a, err = integrate(_probability, 0.0, threshold)
        return a
    
    def _false_negative_probability(threshold, b, r):
        _probability = lambda s : 1 - (1 - (1 - s**float(r))**float(b))
        a, err = integrate(_probability, threshold, 1.0)
        return a
    
    def _optimal_param(threshold, num_perm, false_positive_weight,
            false_negative_weight):
        min_error = float("inf")
        opt = (0, 0)
        for b in range(1, num_perm+1):
            max_r = int(num_perm / b)
            for r in range(1, max_r+1):
                fp = _false_positive_probability(threshold, b, r)
                fn = _false_negative_probability(threshold, b, r)
                error = fp*false_positive_weight + fn*false_negative_weight
                if error < min_error:
                    min_error = error
                    opt = (b, r,fp,fn)
        return opt
    class MinHashLSH(object):
    
        def __init__(self, threshold=0.9, d=128, weights=(0.5, 0.5),
                     params=None, storage_config=None):
            if storage_config is None:
                storage_config = {'type': 'dict'}  
    
            if sum(weights) != 1.0:
                raise ValueError("Weights must sum to 1.0")
            self.h = d
            if params is not None:
                self.b, self.r = params
                if self.b * self.r > d:
                    raise ValueError("The product of b and r in params is "
                            "{} * {} = {} -- it must be less than d {}. ".format(self.b, self.r, self.b*self.r, d))
            else:
                false_positive_weight, false_negative_weight = weights
                self.b, self.r ,self.fp,self.fn= _optimal_param(threshold, d,false_positive_weight, false_negative_weight)
                print('the best parameter b={},r={},fp={},fn={}'.format(self.b,self.r,self.fp,self.fn))
    
            basename = storage_config.get('basename', _random_name(11))
            self.hashtables=[]
            self.hashranges=[]
            for i in range(self.b):
                name=b''.join([basename, b'_bucket_', struct.pack('>H', i)])
                item=DictSetStorage(storage_config, name=name)
                self.hashtables.append(item)
    
                self.hashranges.append((i*self.r, (i+1)*self.r))
    
            self.keys = DictListStorage(storage_config, name=b''.join([basename, b'_keys']))
    
    
    
        def insert(self, key, minhash):
            self._insert(key, minhash, buffer=False)
    
    
        def _insert(self, key, minhash, buffer=False):
            if  key in self.keys:
                raise ValueError("key already exists")
            Hs=[]
            for start, end in self.hashranges:
                Hs.append(self._H(minhash.hashvalues[start:end]))
    
            self.keys.insert(key, *Hs, buffer=buffer)
            
            for H, hashtable in zip(Hs, self.hashtables):
                hashtable.insert(H, key, buffer=buffer)
    
        def query(self, minhash):
            candidates = set()
            for (start, end), hashtable in zip(self.hashranges, self.hashtables):
                H = self._H(minhash.hashvalues[start:end])
                for key in hashtable.get(H):
                    candidates.add(key)
         
            return list(candidates)
    
        
        def _H(self,hs):
            return bytes(hs.byteswap().data)

    这是实现的全过程了,哪天我能够把这些东西自己手动实现出来,我应该就很牛了,哈哈,现在还在学习模仿阶段。

    参考文献

    [1]. datasketch. https://github.com/ekzhu/datasketch

    展开全文
  • minhash算法

    2019-05-08 12:53:00
    minhash算法 大数据量计算相似度的时候,我们使用minhash(最小哈希)进行降维,使用LSH算法进行近似查询。 相似性的度量: 使用雅卡尔系数,交集数量除以并集数量。 以文档为例,组成成分为单词。我们将单词量化为...
  • minhashLSH

    2019-11-28 19:49:37
    minhashLSH 1 问题场景 假设我们要找海量用户中哪些是行为相似的—— 用户A: id: 1001 name: 用户A data: “07:00 吃早餐,09:00 工作,12:00 吃午饭,13:00 打王者,18:00 吃晚饭,22:00 睡觉” mat: ...
  • MinHash,加权MinHash 提卡阈值 MinHash,加权MinHash Jaccard Top-K 最小哈希 遏制阈值 datasketch必须与Python 2.7或更高版本以及NumPy 1.11或更高版本一起使用。 Scipy是可选的,但有了它,LSH初始化可以更快...
  • datasketch, MinHash,LSH,LSH林,加权 MinHash,HyperLogLog,HyperLogLog datasketch: 大数据看起来很小 datasketch提供了可以以快速地处理和搜索大量数据 super的概率数据结构,而且精度很少。这里软件包包含...
  • LSH minhash Signature

    2020-06-24 15:04:48
    准备些写得时候,发现大佬们已经总结的很棒很完善了,瞬间不知道改写什么,、 贴个链接吧 minhash1 minhash2 minhash3
  • datasketch, MinHash,LSH,LSH林,加权 MinHash,HyperLogLog,HyperLogLog+ + datasketch: 大数据看起来很小 datasketch提供了可以以快速地处理和搜索大量数据 super的概率数据结构,而且精度很少。这里软件包包含...
  • MinHash 和 LSH 的 Java 实现,用于查找通过 Jaccard 相似度衡量的接近重复的文档。 MinHash 的实现,用于逼近文本文档中的 Jaccard 相似度。 还包括 LSH 的实现,这是一种快速查找近似最近邻的方法。
  • Minhash介绍

    千次阅读 2014-07-23 00:58:41
    1. minhash是用来降维的。用在两个事物相似度比较的场景。 2. 比较两个事物的相似度,通常是抽出事物的特征,然后两个事物的特征进行比较。例如s1(1,3,5),s2(2,3,5),交集/并集,算分。 3. 但如果事物...
  • MinHash 和LSH

    2020-05-29 07:18:59
    Min Hash 实现 ...from scipy.spatial.distance import cosine from random import randint ...# specify the length of each minhash vector N = 128 max_val = (2**32)-1 # create N tuples that will serve as
  • MinHash 原理

    千次阅读 2013-11-13 09:48:08
    MinHash是基于Jaccard Index相似度(海量数据不可行)的算法,一种降维的方法A,B 两个集合:A = {s1, s3, s6, s8, s9} B = {s3, s4, s7, s8, s10}MinHash的基本原理:在A∪B这个大的随机域里,选中的元素落在A∩B这...
  • MinHash和SimHash

    2017-11-13 17:07:38
    MinHash: 用文档里所有词最小的K个哈希值做特征集合,表征这篇文档;文档之间的相似度在这个集合上用Jaccard距离;适合海量文档,所有文档只做一遍预处理,两两之间的词集合大大减小; 原文链接:...
  • minhash技术的Java实现,以查找集合之间的相似性。 根据上的代码进行的修改
  • MinHash与SimHash

    千次阅读 多人点赞 2015-05-10 22:23:46
    这篇文字主要写MinHash和SimHash的区别,不涉及MinHash和SimHash的详细介绍,具体资料在最后参考资料里给出。 一、相同点 提到哈希我们想到很多应用,最常见的话就是用于提高查询效率,还可用于加密方面。本篇文章要...
  • minHash vs LSH

    2018-01-15 14:21:30
    http://blog.csdn.net/liujan511536/article/details/47729721?readlog ...(simHash、minHash、LSH、海量数据相似度、Redis百亿级Key存储、 Sentinel+ShardedJedis) http://www.07net01.

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 906
精华内容 362
关键字:

minhash