精华内容
下载资源
问答
  • Minihash && LSH

    2020-01-26 22:47:00
    有空补自己的理解和思考 参考文献 https://www.jianshu.com/p/535c537a5766

    有空补自己的理解和思考

    LSH

    参考文献
    https://blog.csdn.net/icvpr/article/details/12342159

    下面为摘抄

    LSH的基本思想是:将原始数据空间中的两个相邻数据点通过相同的映射或投影变换(projection)后,这两个数据点在新的数据空间中仍然相邻的概率很大,而不相邻的数据点被映射到同一个桶的概率很小。也就是说,如果我们对原始数据进行一些hash映射后,我们希望原先相邻的两个数据能够被hash到相同的桶内,具有相同的桶号。对原始数据集合中所有的数据都进行hash映射后,我们就得到了一个hash table,这些原始数据集被分散到了hash table的桶内,每个桶会落入一些原始数据,属于同一个桶内的数据就有很大可能是相邻的,当然也存在不相邻的数据被hash到了同一个桶内。因此,如果我们能够找到这样一些hash functions,使得经过它们的哈希映射变换后,原始空间中相邻的数据落入相同的桶内的话,那么我们在该数据集合中进行近邻查找就变得容易了,我们只需要将查询数据进行哈希映射得到其桶号,然后取出该桶号对应桶内的所有数据,再进行线性匹配即可查找到与查询数据相邻的数据。换句话说,我们通过hash function映射变换操作,将原始数据集合分成了多个子集合,而每个子集合中的数据间是相邻的且该子集合中的元素个数较小,因此将一个在超大集合内查找相邻元素的问题转化为了在一个很小的集合内查找相邻元素的问题,显然计算量下降了很多。

    在这里插入图片描述

    其他参考文献

    https://www.jianshu.com/p/535c537a5766

    展开全文
  • MinHash() m2 = MinHash() #对两个句子进行MiniHash操作 for d in sentense_1: m1.update(d.encode('utf8')) for d in sentense_2: m2.update(d.encode('utf8')) #打印MiniHash后,两个句子的相似度 print("使用...

    什么是最近邻查找?

    在推荐系统中,主要分为召回跟排序两个阶段。

    • 召回阶段,基于用户画像及场景数据从海量的视频库(百万级别)中将相关度最高的资源检索出来,作为候选集,召回阶段可以通过“粗糙”的方式召回候选item。
    • 排序阶段,基于更加精细的特征对候选集(百级别)进行排序,最终呈现给用户的是很少的一部分数据。在这个ranking阶段,采用更精细的特征计算user-item之间的排序score,作为最终输出推荐结果的依据。

    随着机器学习的发展,越来越多问题转移到deep learning上面解决,而系统实际部署在基于Tensorflow的Google Brain上,模型有接近10亿级参数,训练样本千亿级别。
    所以,如此之大数量级的数据量,如果要通过常规方法,计算item两两之间的相似度,那么计算量级要到(n^2)级别,实在是太久了。针对这一现象,聪明的人类提出了NN的方法:
    在这里插入图片描述

    • NN,Nearest Neighbor Search,最近邻查找问题。
    • KNN,K-Nearest Neighbor,k最近邻,查找离目标数据最近的前k个数据项。
    • ANN,Approximate Nearest Neighbor,近似最近邻检索,在牺牲可接受范围内的精度的情况下提高检索效率。
    • ANN,Approximate Nearest Neighbor,近似最近邻检索,在牺牲可接受范围内的精度的情况下提高检索效率。
    • LSH,局部敏感哈希是ANN的一种。

    什么是Hash?

    目前主流的索引技术有:

    • 基于树的索引技术(二叉树,B-Tree,B+Tree)
    • 基于哈希的索引技术
    • 基于词的倒排索引

    海量数据的检索方式,Hash是重要的索引技术。所谓hash,简而言之,就是将原始数据通过一个函数(hash)映射到新的数值。比如自定义一个hash 2 x + 1 2x+1 2x+1,原始数据有[2,4,6,8],通过hash可以映射到[5,9,13,17]。

    针对海量且高维的数据如何进行查找:

    • 如果数据是低维 and 小数据 => 通过线性的方式查找。
    • 数据不仅海量,而且高维 => 需要降维,采用索引方式查找

    LSH,Locality-Sensitive Hashing,局部敏感哈希

    • 需要查找与某个数据1个或多个相似的数据。
    • 最近邻查找方法(ANN,Approximate Nearest Neighbor)
      在这里插入图片描述
    • 对于传统的HashTable用于检索数据,无法将相似的数据放到同一个Bucket中,比如h=x mod w
    • LSH将相邻的数据,通过映射后依然保持相邻的关系,即保持局部的敏感度Locality-Sensitive。
    • 通过Hash Function,每个Bucket会落入一些原始数据,属于同一个桶内的数据有很大可能是相邻的(也存在不相邻的数据被hash到了同一个桶内)。
    • 将原始数据集合分成了多个子集合(即每个bucket),每个子集合中的数据大概率是相邻的,而且子集合中的元素个数较少。
    • 方便进行近邻查找 => 在一个很小的集合里查找相邻元素

    上面提到即使是相邻的元素,也有可能分到不同的bucket,下面举个栗子~:
    $$
    Hash(127) = 127%8 = 7;
    Hash(123) = 123%8 = 3;
    Hash(1023) = 1023%8 = 7;

    $$
    从上面的例子可以看出通过hash把127和1023分到了同一个桶7,而与127更加相邻的123却分到了桶3。所以LSH一定程度上会丢失精度,但是精度换时间,这种买卖的交易是值得的。

    MiniHash算法

    在计算文本相似度中,有:

    • k-shingle,也称为k-gram,文档中任意长度为k的字符串。将每篇文档可以表示成文档中出现一次或者多次的k-shingle的集合
    • 比如document=“abcdabd”,当2-shingle组成的集合为 {ab,bc,cd,da,bd}
    • 如果两个文档相似,那么他们会有很多的shingles也是相同的
    • 文本越长,K取值越大。K的经验值参考,短文本K=5,长文本K=10
      在这里插入图片描述
      由上图所示,假设我们有四篇文档(4列),每篇文档的shingles如果出现则表示为1,否则为0。
      有了这个输入矩阵input_metrix,我们可以通过Jaccard方法计算文本的相似度:
      SIM ⁡ ( C i , C j ) = ∣ C i ∩ C j ∣ ∣ C i ∪ C j ∣ \operatorname{SIM}\left(C_{i}, C_{j}\right)=\frac{\left|C_{i} \cap C_{j}\right|}{\left|C_{i} \cup C_{j}\right|} SIM(Ci,Cj)=CiCjCiCj
      上式分子为两个文档之间交集,分母为两个文档的并集。拿上图举个例子,我们取文档1和文档2(列1和列2),他们之间的交集为2(即两列都为1的行数),并集为5(总共出现的nunique)。看到这里可能有人会提问为啥两列都为0的情况不计算?如果两列都为0,就表示这两篇文章都没有这个shingles,计不计算其实意义都不大。

    有了Jaccard相似度,但是面对海量数据,高维 => 矩阵非常大的时候,我们的目标是需要找到一个Hash函数,将原来的Jaccard相似度计算,等同于降维后的相似度矩阵计算(Input Matrix => Signature Matrix)。

    • 如果原来文档的Jaccard相似度高,那么它们的hash值相同的概率高。
    • 如果原来文档的Jaccard相似度低,那么它们的hash值不相同的概率高。

    针对这个hash函数,聪明的人类提出了MiniHash。MiniHash需要准备两个东西:

    • Input Metrix
    • 随机置换表

    下面上图:
    在这里插入图片描述
    上图中红黄蓝表示随机置换的顺序表,而右边的是输入矩阵Input Metrix。
    假设我们取蓝色的置换顺序表,那么我们通过置换可以得到以下的Metrix(如下图所示)。可以看到原本的第3行(0101)置换到了第1行,原本的第7行(1010)置换到了第3行。
    在这里插入图片描述

    同样的,我们根据红色,黄色置换表,也可以得到不一样的Metrix。如下图所示的黄色置换表得到的Metrix。
    在这里插入图片描述
    有了三个置换的得到的Metrix后,重点来了。==对于每个metrix,我们取出每列首个为1的行数。==拿蓝色置换得到的矩阵为例(如下图),第1列首个1的行数为2,第2列首个1的行数为1,第3列为2,第4列为1,所以最终可以得到(2121)这个hash后的数值。
    在这里插入图片描述
    如此类推,由黄色+红色+蓝色的置换+hash后,可以得到以下的Signature Metrix。
    在这里插入图片描述
    有了MiniHash得到的Signature Metrix,我们就可以计算Jaccard相似度了。如下图所示,第1行为原输入矩阵的Jaccard相似度,第2行为通过MiniHash降维后得到的Signature Metrix的Jaccard相似度。可以看出降维前后的相似度差距不是很大,但是两者之间的计算时间+空间量级得到了大大压缩。精度换时间,何乐而不为~
    在这里插入图片描述

    MiniHash总结

    • 先将原矩阵Input Metrix分别经过n次随机置换(n取决于降维后的维度大小)。
    • 每次置换后,采用MinHash得到Signature Metrix。
    • 使用Sig矩阵相似度用来近似估计原始矩阵Input Matrix的Jaccard相似度。

    MiniHash+LSH

    当数据量非常大的时候,计算量随之也会成倍的增加。我们利用LSH+MiniHash的算法,将可能相似的用户以较大概率分到同一个桶内,这样每一个用户的“相似用户候选集”就会少很多,大大降低计算复杂度。其中主要的思想就是:

    • 在MiniHash降维的基础上,将得到的Signature向量分成多段(band)。

    • 将Signiture矩阵分成b组(即b个bands),每组由r行组成。(如下图所示)
      在这里插入图片描述

    • 对每一组进行hash,各个组设置不同的桶空间。只要两列有一组的MinHash相同,那么这两列就会hash到同一个桶而成为候选相似项.(如下图所示)
      在这里插入图片描述
      对于以上分组,我们假设对于某行,两列MinHash的值相同的概率为s(两列的相似度),有:

    • 在某个band,值都相等的概率是 S r S^r Sr

    • 在某个band,值不相同的概率是 1 − S r 1-S^r 1Sr

    • 两个文档存在b个band,这b个band都不相同的概率是 ( 1 − S r ) b (1-S^r)^{b} (1Sr)b

    • b个band里,至少有一个相同的概率是 1 − ( 1 − S r ) b 1-(1-S^r)^{b} 1(1Sr)b,即两列成为候选相似对的概率是 1 − ( 1 − S r ) b 1-(1-S^r)^{b} 1(1Sr)b

    以上我们将其称之为And Then Or方法,先要求每个band的所有对应元素必须都相同,再要求多个band中至少有一个相同。符合这两条,才能发生hash碰撞。下面我们举个例子用以理解:假设两列MinHash的值相同的概率s=0.8,20个band,每个band 5行,即b=20, r=5。有

    • 在某个band,值都相等的概率: 0. 8 5 = 0.328 0.8^5 = 0.328 0.85=0.328
    • 在某个band,值不相同的概率: 1 − 0. 8 5 = 0.672 1- 0.8^5 = 0.672 10.85=0.672
    • b个band都不相同的概率: 0.67 2 2 0 = 0.00035 0.672^20 = 0.00035 0.67220=0.00035
    • b个band里,至少有一个相同的概率: 1 − 0.67 2 2 0 = 0.9996 1- 0.672^20 = 0.9996 10.67220=0.9996
    • 相应地,保持b和r不变,我们也可以调节不同的s,有:
      在这里插入图片描述
      从上图可以看出,当我们的s超过某个阈值后,两个用户成为candidate用户的概率会迅速增加并接近于1。这个阈值,也就是概率变化最陡的地方,近似为 t = ( 1 b ) 1 r t=\left(\frac{1}{b}\right)^{\frac{1}{r}} t=(b1)r1
      在这里插入图片描述
      那么实际使用的过程中,我们需要确定以下几点:
    • Smin,相似用户的阈值定义(近邻定义)
    • Signature向量的长度,降到k维embedding,即随机置换表的个数。

    而针对b和r的取值,我们需要考虑:

    • 如果想要尽可能少的出现false negative,需要选择b和r使得概率变化最陡的地方小于Smin(比如s在0.5以上才属于相似用户,选择b和r使得S曲线的最陡处小于0.5)。
      在这里插入图片描述
    • 如果想要保证计算速度较快,并且尽可能少出现false positive,那么最好选择b和r使得概率变化最陡的地方较大(比如b=20,r=6)这样,s较小的两个用户就很难成为candidate用户,但同时也会有一些“潜在”的相似用户不会被划分到同一个桶内。
      在这里插入图片描述

    对于LSH的一般定义:
    Locality-Sensitive Hashing是满足一定条件的Hash函数簇
    d 1 d_1 d1< d 2 d_2 d2是定义在距离测定d下的两个距离值,如果一个函数族的每一个函数f满足:

    • 如果d(x,y)<= d 1 d_1 d1,则f(x)=f(y)的概率至少为 p 1 p_1 p1,即P(f(x)=f(y)) >= p 1 p_1 p1
    • 如果d(x,y)>= d 2 d_2 d2,则f(x)=f(y)的概率至多为 p 2 p_2 p2,即p(f(x)=f(y)) <= p 2 p_2 p2
      那么称F为( d 1 d_1 d1, d 2 d_2 d2, p 1 p_1 p1, p 2 p_2 p2)-sensitive的函数族。
    • Jaccard相似性对应的LSH为MinHash,是( d 1 d_1 d1, d 2 d_2 d2, 1 − d 1 1-d_1 1d1, 1 − d 2 1-d_2 1d2)-sensitive.

    LSH算法工具

    part1
    首先我们看一下用MiniHash前后,jaccard相似度的对比。话不多说,先上代码:

    from datasketch import MinHash
    import jieba
    
    #创建两个句子
    sentense_1 = '今天我和朋友去打球,他说我打得很好。'
    sentense_2 = '昨天我和朋友去打球,他说我打得没他好。'
    
    #文本清洗,去标点符号,分词。
    def clean(x):
        symbol = ',。'
        for i in symbol:
            x = x.replace(i,'')
        res = jieba.lcut(x)
        return res
    sentense_1 = clean(sentense_1)
    sentense_2 = clean(sentense_2)
    #查看一下清洗后的样式
    sentense_1,sentense_2
    

    在这里插入图片描述

    #开始调用MiniHash方法
    m1 = MinHash()
    m2 = MinHash()
    
    #对两个句子进行MiniHash操作
    for d in sentense_1:
        m1.update(d.encode('utf8'))
    for d in sentense_2:
        m2.update(d.encode('utf8'))
    #打印MiniHash后,两个句子的相似度    
    print("使用MinHash预估的Jaccard相似度", m1.jaccard(m2))
    
    #
    s1 = set(sentense_1)
    s2 = set(sentense_2)
    actual_jaccard = float(len(s1.intersection(s2)))/float(len(s1.union(s2)))
    print("未使用MinHash预估的Jaccard相似度实际值", actual_jaccard)
    

    在这里插入图片描述

    从上图结果可以看出,用了MiniHash的结果未必比没用的差(当然这可能存在偶然性)。这里只是想表明,计算相似度里面,MiniHash的效果跟原数据的差不多,但是时间跟计算复杂度上能压缩很多倍!

    在datasketch中的MinHash(),有一些可调参数:

    • num_perm参数,Hash置换函数设定个数,默认为128,如果需要提高精度,可以提高该数值,比如设置num_perm=256
    • update函数,内容Hash化m1.update(content)
    • merge函数,Hash合并,比如m1.merge(m2)

    part2
    了解了MiniHash的简单使用,再讲讲MiniHash+LSH的结合体。话不多说,线上代码:

    from datasketch import MinHash,MinHashLSH
    import jieba
    
    sentense_1 = '今天我和朋友去打球,他说我打得很好。'
    sentense_2 = '昨天我和朋友去打球,他说我打得没他好。'
    test = '昨天我和朋友没去打球,他说我打得太好'
    
    def clean(x):
        symbol = ',。'
        for i in symbol:
            x = x.replace(i,'')
        res = jieba.lcut(x)
        return res
    sentense_1 = clean(sentense_1)
    sentense_2 = clean(sentense_2)
    test = clean(test)
    
    sentense_1,sentense_2,test
    

    在这里插入图片描述

    m1 = MinHash()
    m2 = MinHash()
    m3 = MinHash()
    
    for d in sentense_1:
        m1.update(d.encode('utf8'))
    for d in sentense_2:
        m2.update(d.encode('utf8'))
    for d in test:
        m3.update(d.encode('utf8'))
    
    lsh = MinHashLSH(threshold=0.5, num_perm=128)
    lsh.insert("m1", m1)
    lsh.insert("m2", m2)
    result = lsh.query(m3)
    print("近似的邻居(Jaccard相似度>0.5)", result)
    

    在这里插入图片描述
    由上图可以得到与test相似度最高的sentense_1

    part3
    除了MiniHash+LSH,还可以用MinHashLSHForest,针对新闻中某句话Query进行TOP-K相似度输出。话不多说,先上代码(数据集链接):

    from datasketch import MinHash, MinHashLSH, MinHashLSHForest
    from sklearn.feature_extraction.text import TfidfVectorizer
    import jieba.posseg as pseg
    import re
    
    # 读取文件
    f = open('./sentences.txt', 'r', encoding='UTF-8')
    text = f.read()
    
    # 以句号,叹号,问号作为分隔,去掉\n换行符号
    sentences = re.split('[。!?]', text.replace('\n', ''))
    
    # 最后一行如果为空,则删除
    if sentences[len(sentences)-1] == '':
        sentences.pop()
    #查看简单清洗效果
    sentences
    

    在这里插入图片描述

    # 将文本进行分词
    def get_item_str(item_text):
        item_str = "" 
        item=(pseg.cut(item_text)) 
        for i in list(item):
            #去掉停用词
            if i.word not in list(stop):  
                item_str += i.word
                #tfidf_vectorizer.fit_transform的输入需要空格分隔的单词
                item_str += " "
        return item_str
    
    # 对文本创建MinHash
    def get_minhash(item_str):
        temp = MinHash()
        for d in item_str:
            temp.update(d.encode('utf8'))
        return temp
    
    # 设置停用词
    stop = [line.strip().decode('utf-8') for line in open('stopword.txt').readlines()]
    # 得到分词后的documents
    documents = []
    for item_text in sentences:
        # 将item_text进行分词
        item_str = get_item_str(item_text)
        documents.append(item_str)
        
    # 创建LSH Forest及MinHash对象
    minhash_list = []
    forest = MinHashLSHForest()
    for i in range(len(documents)):
        #得到train_documents[i]的MinHash
        temp = get_minhash(documents[i])
        minhash_list.append(temp)
        forest.add(i, temp)
    # index所有key,以便可以进行检索
    forest.index()
    
    query = '00:01:36,2019天猫双11总成交额超100亿元'
    # 将query的内容进行分词
    item_str = get_item_str(query)
    # 得到query的MinHash
    minhash_query = get_minhash(item_str)
    
    # 查询forest中与m1相似的Top-K个邻居,此处K取3
    result = forest.query(minhash_query, 3)
    for i in range(len(result)):
        print(result[i], minhash_query.jaccard(minhash_list[result[i]]), documents[result[i]].replace(' ', ''))
    print("Top 3 邻居", result)
    

    在这里插入图片描述

    MinHashLSHForest流程总结

    • 对新闻中的句子进行检索
    • 使用MinHashLSHForest,针对某句话Query进行TOP-K相似度输出
    • Step1、分词
    • Step2、创建MinHash
    • Step3、使用MinHashLSHForest进行Index
    • Step4、使用MinHashLSHForest进行Query,查询Top-K相似句子

    走过路过的朋友们,记得点个关注或者点赞哦,谢谢,我是阿民,会努力保持更新!!!谢谢!!

    展开全文
  • MinHash和SimHash

    2017-11-13 17:07:38
    MinHash: 用文档里所有词最小的K个哈希值做特征集合,表征这篇文档;文档之间的相似度在这个集合上用Jaccard距离;适合海量文档,所有文档只做一遍预处理,两两之间的词集合大大减小; ... 跟SimHash一样,...

    MinHash:  用文档里所有词最小的K个哈希值做特征集合,表征这篇文档;文档之间的相似度在这个集合上用Jaccard距离;适合海量文档,所有文档只做一遍预处理,两两之间的词集合大大减小;


    原文链接:https://my.oschina.net/pathenon/blog/65210

    1.概述


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

    2.Jaccard index

        在介绍MinHash之前,我们先介绍下Jaccard index。

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

        

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

    3.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)k  ∪  Min(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是怎么回事了。但是,MinHash的好处到底在哪里呢?计算两篇文档的相似度,就直接统计相同的词数和总的
    次数,然后就Jaccard index不就可以了吗? 对,如果仅仅对两篇文档计算相似度而言,MinHash没有什么优势,反而把问题复杂化了。但是如果有海量的文档需要求相似度,比如在推荐系统
    中计算物品的相似度,如果两两计算相似度,计算量过于庞大。下面我们看看MinHash是怎么解决问题的。

          比如  元素集合{a,b,c,d,e},其中s1={a,d},s2={c},s3={b,d,e},s4={a,c,d}     那么这四个集合的矩阵表示为:   
            
        如果要对某一个集合做MinHash,则可以从上面矩阵的任意一个行排列中选取一个,然后MinHash值是排列中第一个1的行号。
        例如,对上述矩阵,我们选取排列  beadc,那么对应的矩阵为
               
        那么,  h(S1) = a,同样可以得到h(S2) = c, h(S3) = b, h(S4) = a。
            如果只对其中一个行排列做MinHash,不用说,计算相似度当然是不可靠的。因此,我们要选择多个行排列来计算MinHash,最后根据Jaccard index公式  来计算相似度。但是求排列本身的复杂度比较高,特别是针对很大的矩阵来说。因此,我们可以设计一个随机哈希函数去模拟排列,能够把行号0~n随机映射到0~n上。比如  H(0)=100,H(1)=3...。当然,冲突是不可避免的,冲突后可以二次散列。并且如果选取的随机哈希函数够均匀,并且当n较大时,冲突发生的概率还是比较低的。

        说到这里,只是讨论了用MinHash对海量文档求相似度的具体过程,但是它到底是怎么减少复杂度的呢?
        比如有n个文档,每个文档的维度为m,我们可以选取其中k个排列求MinHash,由于每个对每个排列而言,MinHash把一篇文档映射成一个整数,所以对k个排列计算MinHash就得到k个整数。那么所求的MinHash矩阵为n*k维,而原矩阵为n*m维。n>>m时,计算量就降了下来。
        

    4.参考文献
               (2)   http://fuliang.iteye.com/blog/1025638

    ------------------------------------------------------------------------------------------------------------------------------------------------------------


    SimHash: 海量文本去重(允许一定的噪声);文档里权重最大的前N个词进行Hash编码,1正0负乘以词的权重,N个词的向量按位相加,再反编码(正1负0),得到该文档的编码;两篇文档的距离用编码的海明距离,小于Bar(例如3)则认为二者相似;


    simhash是google用来处理海量文本去重的算法。 google出品,你懂的。 simhash最牛逼的一点就是将一个文档,最后转换成一个64位的字节,暂且称之为特征字,然后判断重复只需要判断他们的特征字的距离是不是<n(根据经验这个n一般取值为3),就可以判断两个文档是否相似。

    原理

    simhash值的生成图解如下:

    simhash原理图

    大概花三分钟看懂这个图就差不多怎么实现这个simhash算法了。特别简单。谷歌出品嘛,简单实用。

    算法过程大概如下:

    1. 将Doc进行关键词抽取(其中包括分词和计算权重),抽取出n个(关键词,权重)对, 即图中的(feature, weight)们。 记为 feature_weight_pairs = [fw1, fw2 ... fwn],其中 fwn = (feature_n, weight_n)
    2. hash_weight_pairs = [ (hash(feature), weight) for feature, weight in feature_weight_pairs ] 生成图中的(hash,weight)们, 此时假设hash生成的位数bits_count = 6(如图);
    3. 然后对 hash_weight_pairs 进行位的纵向累加,如果该位是1,则+weight,如果是0,则-weight,最后生成bits_count个数字,如图所示是[13, 108, -22, -5, -32, 55], 这里产生的值和hash函数所用的算法相关。
    4. [13,108,-22,-5,-32,55] -> 110001这个就很简单啦,正1负0。

    到此,如何从一个doc到一个simhash值的过程已经讲明白了。 但是还有一个重要的部分没讲,

    simhash值的海明距离计算

    二进制串A 和 二进制串B 的海明距离 就是 A xor B 后二进制中1的个数。

    举例如下:

    A = 100111;
    B = 101010;
    hamming_distance(A, B) = count_1(A xor B) = count_1(001101) = 3;
    

    当我们算出所有doc的simhash值之后,需要计算doc A和doc B之间是否相似的条件是:

    A和B的海明距离是否小于等于n,这个n值根据经验一般取值为3,

    simhash本质上是局部敏感性的hash,和md5之类的不一样。 正因为它的局部敏感性,所以我们可以使用海明距离来衡量simhash值的相似度。

    高效计算二进制序列中1的个数

    /* src/Simhasher.hpp */
    bool isEqual(uint64_t lhs, uint64_t rhs, unsigned short n = 3)
    {
        unsigned short cnt = 0;
        lhs ^= rhs;
        while(lhs && cnt <= n)
        {
            lhs &= lhs - 1;
            cnt++;
        }
        if(cnt <= n)
        {
            return true;
        }
        return false;
    }
    

    由上式这个函数来计算的话,时间复杂度是 O(n); 这里的n默认取值为3。由此可见还是蛮高效的。

    simhash实现的工程项目

    我自己写的simhash

    主要是针对中文文档,也就是此项目进行simhash之前同时还进行了分词和关键词的抽取。

    对比其他算法

    百度的去重算法

    百度的去重算法最简单,就是直接找出此文章的最长的n句话,做一遍hash签名。n一般取3。 工程实现巨简单,据说准确率和召回率都能到达80%以上。

    shingle算法

    shingle原理略复杂,不细说。 shingle算法我认为过于学院派,对于工程实现不够友好,速度太慢,基本上无法处理海量数据。

    其他算法

    具体看微博上的讨论

    参考


    展开全文
  • 问题引入 在风控领域常会面临一种场景:随着安全策略的打击,部分已经显露的账号/用户会被稽核、处置,要么被动地被封停,要么被坏人干脆舍弃掉。...但有一点是较难隐藏的:上下游的关系链。因此,可以尝试通过关系...

    问题引入

    在风控领域常会面临一种场景:随着安全策略的打击,部分已经显露的账号/用户会被稽核、处置,要么被动地被封停,要么被坏人干脆舍弃掉。坏人会重新注册新的账号进行活跃。而这些新老账号之间很可能没有直接的交易关系,甚至连登陆设备也不同,就较难发现其关联性。但有一点是较难隐藏的:上下游的关系链。因此,可以尝试通过关系网络结构上的相似性来量化两个账号之间的关联度,从而对于风险用户关联分析起到一个补充作用。

    可用下图来辅助说明,x的交易流入方集合为{a,b,c,d}, y的交易流入方集合为{b,c,d},一个很自然的想法就是用Jaccard相似度来计算两个集合之间的相似度,也即:

    常用解法

    • 暴力计算

    比较容易想到的就是该表与自己做JOIN,求出交集。然后再分别计算一个节点入度数,用 x的节点入度数 + y的节点入度 - 交集节点数 得到并集的大小,那么交集大小/并集大小就得到了结果。但是以蚂蚁的数据体量而言,动辄N亿的关系对,这个计算几乎是不可行的。

    • 借鉴倒排索引

    在使用表的JOIN操作时,默认是不知道哪两个节点有交集的,所以会进行暴力的两两配对计算。这里可以借鉴自然语言处理中的倒排索引方法,将每个流入节点node看作一个词,得到一个索引表, 该表中的账号就有共同的流入节点,它们两两之间的交集统计值就可以+1,遍历所有的流入节点,就汇总出了两两节点之间的交集数量。

    • Minhash

    前面的方法都是实打实地计算,但有时候一种“足够好”的近似求解结果也是可以接受的,尤其是工程上有较大的效率提升时。Minhash就常用于近似求解Jaccard相似度。现在Spark中也有现成的包可以用,使用成本就比较可控了。

    实践代码

    Spark官方文档中有一段样例代码可以参考:https://spark.apache.org/docs/3.0.0/ml-features.html#minhash-for-jaccard-distance,但DEMO距离落地的成品还是有开发成本的,需要我们把数据预处理成人家指定的格式,即是说,把节点集合的向量,变成0,1 值的向量。这里有点类似于文本处理中的bag of word方法,沿着这个思路去找到spark中的CountVectorizer类,但默认是统计的频数,通过指定.setBinary(true) 实现0-1值的转换。

    基于阿里的ODPS平台,完整版本的代码如下:

    import com.aliyun.odps.TableSchema
    import com.aliyun.odps.data.Record
    import org.apache.spark.sql.functions.col
    import org.apache.spark.sql.{DataFrame, Row, SparkSession}
    import org.apache.spark.ml.feature.{CountVectorizer, CountVectorizerModel, MinHashLSH, MinHashLSHModel}
    import org.apache.spark.ml.linalg.{ SparseVector}
    import org.apache.spark.odps.OdpsOps
    import org.apache.spark.rdd.RDD
    
    
    object minhashJaccardCal {
      def main(args:Array[String]) = {
        val spark = SparkSession.builder().enableOdpsSupport().enableHiveSupport().appName("minhashJaccardCal").getOrCreate()
        //输入参数
        val inputProject = args(0)
        val inputTable = args(1)
        val outputProject = args(2)
        val outputTable = args(3)
        val usage = s"""
        Usage: <inputProject> <inputTable> <outputProject> <outputTable>
      """
        if(args.length < 4){
          println("参数错误")
          sys.error(usage)
          sys.exit(-1)
        }
    
        try{
          val odpsOps = new OdpsOps(spark.sparkContext)
          val pair: RDD[(String, String)] = odpsOps.readTable(inputProject,inputTable, (r: Record, _: TableSchema) => (r.getString(0),r.getString(1)) ,100)
          //-----------------------------------------------------------------------------
          //计算流入节点的重合度,用MINHASH的方法来近似计算,总共分成两步
          //1. 数据预处理成bag of word形式的0-1向量,且用sparse向量来表示
          //2. 调用org.apache.spark.ml.feature.MinHashLSH 来近似计算jaccard距离
          //下面执行第1步
          val inputNodeVector: RDD[(String, List[String])] = pair.map(_.swap).combineByKey(
            (v : String) => List(v),
            (c : List[String], v : String) => v :: c,
            (c1 : List[String], c2 : List[String]) => c1 ::: c2
          ).repartition(100)
    
          val inputNodeVectorDF = spark.createDataFrame(inputNodeVector).toDF("node","neighbors")
          val cvModel: CountVectorizerModel = new CountVectorizer().setInputCol("neighbors").setOutputCol("features").setBinary(true).fit(inputNodeVectorDF)
          val inputNodeVectorDFSparse: DataFrame = cvModel.transform(inputNodeVectorDF).select("node","features")
    
          val inputNodeVectorDFSparseFilter = spark.createDataFrame(inputNodeVectorDFSparse.rdd.map(row => (row.getAs[String]("node") ,row.getAs[SparseVector]("features"))).map(x => (x._1,x._2,x._2.numNonzeros)).filter(x => x._3 >= 1).map(x => (x._1,x._2))).toDF("node","features")
    
          //下面执行第2步
          val mh = new MinHashLSH().setNumHashTables(100).setInputCol("features").setOutputCol("hashes")
          val model: MinHashLSHModel = mh.fit(inputNodeVectorDFSparseFilter)
          val inputNodeDistance: DataFrame =  model.approxSimilarityJoin(inputNodeVectorDFSparseFilter, inputNodeVectorDFSparseFilter, 0.7, "JaccardDistance").select(col("datasetA.node").alias("node1"),col("datasetB.node").alias("node2"),col("JaccardDistance"))
          val inputNodeOverlapRatio =  inputNodeDistance.rdd.map(x => {
              val node1 = x.getString(0)
              val node2 = x.getString(1)
              val overlapRatio = 1 - x.getDouble(2)
              if(node1 < node2) ((node1, node2),overlapRatio) else ((node2, node1),overlapRatio)
          }).filter(x => x._1._1 != x._1._2)
    
          //-----------------------------------------------------------------------------
          //计算流出节点的重合度, 思路与上相同
          val outputNodeVector: RDD[(String, List[String])] = pair.combineByKey(
            (v : String) => List(v),
            (c : List[String], v : String) => v :: c,
            (c1 : List[String], c2 : List[String]) => c1 ::: c2
          )
          val outputNodeVectorDF = spark.createDataFrame(outputNodeVector).toDF("node","neighbors")
    
          val cvModelOutput: CountVectorizerModel = new CountVectorizer().setInputCol("neighbors").setOutputCol("features").setBinary(true).fit(outputNodeVectorDF)
          val outputNodeVectorDFSparse: DataFrame = cvModelOutput.transform(outputNodeVectorDF).select("node","features")
          val outputNodeVectorDFSparseFilter: DataFrame = spark.createDataFrame(outputNodeVectorDFSparse.rdd.map(row => (row.getAs[String]("node") ,row.getAs[SparseVector]("features"))).map(x => (x._1,x._2,x._2.numNonzeros)).filter(x => x._3 >= 1).map(x => (x._1,x._2))).toDF("node","features")
    
    
          //下面执行第2步
          val mh2 = new MinHashLSH().setNumHashTables(100).setInputCol("features").setOutputCol("hashes")
          val outputModel: MinHashLSHModel = mh2.fit(outputNodeVectorDFSparseFilter)
          val outputNodeOverlapRatio =  outputModel.approxSimilarityJoin(outputNodeVectorDFSparseFilter, outputNodeVectorDFSparseFilter, 0.7, "JaccardDistance").select(col("datasetA.node").alias("node1"),col("datasetB.node").alias("node2"),col("JaccardDistance")).rdd.map(x => {
            val node1 = x.getString(0)
            val node2 = x.getString(1)
            val overlapRatio = 1 - x.getDouble(2)
            if(node1 < node2) ((node1, node2),overlapRatio) else ((node2, node1),overlapRatio)
          }).filter(x => x._1._1 != x._1._2)
    
          //-----------------------------------------------------------------------------
          //合并到一起
          val jaccardValuePair: RDD[(String, String, Double, Double)] = inputNodeOverlapRatio.fullOuterJoin(outputNodeOverlapRatio,100).map{case ((x,y),(inValue, outValue)) =>
            (x,y,inValue.getOrElse(0.0),outValue.getOrElse(0.0))
          }.filter(x => x._1 != x._2).distinct(100)
          //      写入结果表
          val saveTransfer = (v:Tuple4[String, String, Double, Double] , record:Record, schema: TableSchema) => {
            record.set("srcid", v._1)
            record.set("tarid", v._2)
            record.set("invalue", v._3)
            record.set("outvalue", v._4)
          }
          odpsOps.saveToTable(outputProject,outputTable,jaccardValuePair,saveTransfer,isOverWrite = true)
        }catch {
          case ex: Exception => {
            throw ex
          }
        } finally {
          spark.stop()
        }
      }
    }
    

     

    展开全文
  • Python的datasketch库中的MinHashLSH

    千次阅读 2020-01-19 20:02:24
    1、简介 在工作中需要对海量数据进行相似性查找,即对微博全量用户进行关注相似度计算,计算得到每个用户关注相似度最高的TOP-N个用户,首先想到的是利用简单的协同过滤,先定义相似性度量(cos,Pearson,Jaccard...
  • 【文本相似性计算】minHash和LSH算法

    万次阅读 2018-09-25 14:27:06
    minHash和LSH算法 原理 ... Jaccard相似度 判断两个集合是否相等,一般使用称之为Jaccard相似度的算法(后面用Jac(S1,S2)来表示集合S1和S2的Jaccard相似度)。举个列子,集合X = {a,b,c},Y = {b,c,d}。...
  • MinHash (最小哈希)

    万次阅读 2014-12-09 19:41:18
    minhash是判断文档相似的一种方法。这里结合一个具体的示例来简单过一下: 一、全集 {a,b,c,d,e},S1={a,d}, S2={c}, S3={b,d,e}, S4={a,c,d}。...具体含义:比如 S1,S2,S3,S4分别是4个文档,a,b,c,d,e可以是...
  • 一、hash:key所对应的值为键值对。 hset key k v 创建hash类型的键值对 hget key k 获取k所对应的value hmset/hmget 同时设置/获取多个hash键值对。 hgetall key 获取所有的kv ...hkeys/hvals key 获取所有的key/...
  • JAVA基础之HashMap源码(JDK 1.8)

    千次阅读 2016-05-19 15:27:06
    JAVA的hashMap源码的get方法、hash函数、resize方法以及key的hashCode方法和equals的重写
  • MinHash与SimHash

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

    千次阅读 2014-08-24 11:03:53
    问题背景 给出N个集合,找到相似的集合对,如何实现呢?直观的方法是比较任意两个集合。那么可以十分精确的找到每一对相似的集合,但是时间复杂度是O(n2)。当N比较小时,比如K级,此算法可以在接受的时间范围内完成...
  • Map: Vector featureVector = features.get(); if (featureVector.size() < minVectorSize) { return; } // Initialize the MinHash values to highest for (int i = ...
  • 聚类之MinHash

    2012-12-20 12:39:00
    最小哈希法 最小哈希原理介绍 MinHash是基于Jaccard Index相似度(海量数据不可行)的算法,一种降维的方法A,B 两个集合:A = {s1, s3, s6, s8, s9} B = {s3, s4, s7, s8, s10} MinHash的基本原理:在A∪B这个...
  • Map:   Vector featureVector = features.get();  if (featureVector.size() &lt; minVectorSize) { return; } // Initialize the MinHash values to highest for (int i = 0;... numH...
  • 文本去重之MinHash算法

    万次阅读 2012-08-06 14:58:04
    1.概述  跟SimHash一样,MinHash也是LSH的一种,可以用来快速估算两个集合的相似度。MinHash由Andrei Broder提出,最初用于在搜索引擎中检测重复网页。它也可以应用于大规模聚类问题。...
  • The minihash method allows us to compute the Jaccard index using approximation to avoid computing similarities between nonsimilar malware samples below some predefined similarity threshold so that we...
  • minihash使用的是LSH算法,背后使用的距离公式应该是jaccard距离。这一块还不是很确定,后续会在好好研究下补充进来。 docsim求解: import gensim import jieba import re # 训练样本 from gensim import ...
  • (三):minihash: 原文链接: http://my.oschina.net/pathenon/blog/65210  转自wiki:http://en.wikipedia.org/wiki/Locality_sensitive_hashing  传统的hash算法只负责将原始内容尽量均匀随机地映射为一个...
  • Lookalike(一):Lookalike技术调研

    千次阅读 2018-09-12 17:52:34
    为了解决这个问题,论文中使用了MiniHash+LSH 1 来简化计算,进而构建一张全局图。另外在构建全局图时,论文使用的相似度计算公式为 s i m ( f i , f j ) = f ′ i A f j ∥ f i ∥ ∥ f j ∥ s i m ( f i , f ...
  • miniHash m i n i H a s h 值,并用同样的方法计算出 A A A 的 m i n i H a s h miniHash m i n i H a s h 值,然后逐个比较该值与 S S S 中的 n n n 个集合的杰卡德相似度,返回阈值大于 0.5 0.5 0 . 5 的集合。 ...
  • 搜索引擎中抓取的网页是海量的,海量文本的去重算法也出现了很多,比如minihash, simhash等等。 在工程实践中,对simhash使用了很长一段时间,有些缺点,一是算法比较复杂、效率较差;二是准确率一般。 网上也...
  • 搜索引擎中抓取的网页是海量的,海量文本的去重算法也出现了很多,比如minihash, simhash等等。 在工程实践中,对simhash使用了很长一段时间,有些缺点,一是算法比较复杂、效率较差;二是准确率一般。 网上也流传着...

空空如也

空空如也

1 2
收藏数 34
精华内容 13
关键字:

minihash