当前位置: 首页>大数据>正文

如何判断两篇文章相似性

这个仍然是极客时间上,关于《索引技术核心20讲》的一篇笔记同时结合自己的理解加了点料,这个专栏虽然只有20讲,但是真不错,老师解答问题还是很积极,回答字数经常比问题字数多。有兴趣的朋友可以到我星球(在公众号的其他菜单中)扫码购买,然后加我微信返利。

一 前言

如果我们接到如题的需求,让我们来判断两篇文章是否相似,那么怎么判断?文章相似判断的场景还是不少的,比如我们判断论文排重,像知网的收费的查重服务,说到知网,第一次听说的时候问了下说的人,被故意告知是知乎网,鄙视下:)。 扯远了,文章另外一个相似性判断应用场景是在搜索引擎中,搜索引擎搜索的时候,是要找和查询关键词相关的文章,如果返回的第一页每篇文章都相似性很高,也是不好的,是要有些区分度的。

大家可以先思考下。

二 一般思路空间向量法

看上去这个问题并不是太好解决,一个文章有这么多词语,每个词语的重要性又不相同,在计算机中如何表示一篇文章,又如何来求两个文章的相似性。 我来想的话,我想到了以前判断两个句子的相似性的算法,文章不就是可以看做很多句子嘛,所以两者的算法应该一致的。判断两个句子的相似度算法大概思路是这样子的:

  1. 把文章或句子进行分词,分成一个个词语。
  2. 计算词语的TF-IDF值,公式:TF-IDF = TF*IDF
    TF-IDF可以很好标示词在文章中的重要性,通过考虑IDF降低常见词的结果值。通过Log下,将IDF的值的范围缩小。


    如何判断两篇文章相似性,第1张
    词频TF

    如何判断两篇文章相似性,第2张
    IDF值
  3. 将所有单词组成一个空间向量,如下:


    如何判断两篇文章相似性,第3张
    文章转成空间向量
  4. 这样通过上述步骤将文章转成为空间向量了,两篇文章的相似性就是判断两个向量的空间距离,
    如果距离近,说明文章比较相似,空间向量的距离可以通过计算两个向量的余弦距离来判断:


    如何判断两篇文章相似性,第4张
    二维点的余弦距离

说明:

  1. 上图两个点,一个是(x1,y1)和(x2,y2)两个点的余弦距离用黄色线段表示。
  2. 两个点的距离可以通过a和b的夹角的余弦值来表示,值越大,距离越小。
    如下:


    如何判断两篇文章相似性,第5张
    图片来自互联网

三 Python计算余弦距离判断相似

上述文章说起来比较复杂,用python代码实现如下:

# -*- coding: utf-8 -*-

from sklearn.feature_extraction.text import TfidfVectorizer
import math

'''
 计算余弦距离
'''
def  cal_cos(list_one,list_two):
    sum = 0
    sq1 = 0
    sq2 = 0
    for i in range(len(list_one)):
        sum += list_one[i]*list_two[i]
        sq1 += pow(list_one[i], 2)
        sq2 += pow(list_two[i], 2)
    try:
        result = round(float(sum) / (math.sqrt(sq1) * math.sqrt(sq2)), 2)
    except ZeroDivisionError:
        result = 0.0
    return result

if __name__ == '__main__':
    tfidf_vec = TfidfVectorizer()
    docs = ['this is the bays document', 'this is the second second document', 'and the third one', 'is this the document']
    tfidf_matrix = tfidf_vec.fit_transform(docs)

    allarray = tfidf_matrix.toarray()
    for  i in range(len(docs)):
        r = cal_cos(allarray[0],allarray[i])
        print(u'第'+str(i)+u'个和第0个的相关度为:'+str(r))

三 局部Hash函数来计算文章的相似性

以上内容只是我按照以前的思路来计算文章的相似性,不过可以想下,如果文章很多,比如千万级别,而且文章的词语也非常多,向量的维度就很大,计算起来工作量就很大。有没有什么好一点的算法。

我们将文章转成TF-IDF的向量后,可以把一篇篇文章用N维空间中的一个点来表示,那么文章的相似性就是空间中的点的距离,是不是有点类似于我们求附近的人,同样是搜索空间中临近点的距离。我们在计算附近距离的时候,是把整个空间分为N多个区间,并对这些区间进行编码,编码前缀相同的空间内的人或点肯定是具有一定相似性的。

那么难点就转成了如何对向量进行编码,相近的点空间编码具有相同的前缀。是不是像哈希函数,通过对空间N维向量的转化,转成一维的地区编码。普通的哈希函数,如果改变一个词语,整个哈希函数结果有很大的偏差,这和我们的要求的函数不同,我们想要的是一个对相似的文档转成的哈希值也相似,这个函数有个名字叫局部性敏感哈希函数。

这样的哈希函数怎么得到那,有个简单的办法,将刚才的文章映射成N维空间的点之后,任意在空间中划条线,线上编码为0,下编码为1(对N维空间实际上采用超平面来划分,超平面是计算点向量和超平面的余弦值通过值为1还是0来进行编码,其实原理类似)。如此在整个向量空间,画N条线或超平面之后,每个文档都转成了一串0和1组成的编码串。

文档转成编码串后,如果编码串中只有几位,比如3位不相同,其他的位都相同,那么我们可以认为这两个文档是相似的,这个不同比特差异位数称为海明距离,比如以下两个字符串:

10000000 和 01000000

的海明距离为2,有两位不同。

四 SimHash算法

上面说我们可以通过海明距离来判断文章的相似性,但是注意到我们编码的时候才用0和1编码,只能表示词语在文中或者不在文中,我们知道文章中的词语权重是不相同的,这样计算的话就丢失了权重这个重要的因素,怎么解决那?谷歌提供了一个方案就是SimHash算法,简单且有效。

4.1 SimHash函数计算步骤

SimHash作用的对象是文章中的单词,而不是整个文章;且用普通哈希函数替换了超平面。
具体步骤如下:

  1. 找一个将单词映射到64位整数的哈希函数。
  2. 使用哈希函数对文章中的每个关键词都生成一个64位的整数,并且将哈希位中值为0的都转成-1。
  3. 用刚才的关键词编码乘关键词的权重,这里面权重可以用TF-IDF值。如果关键词编码为:<1,-1,1,-1> 权重为3的话,那么转换得到的关键词编码为:<3,-3,3,-3>。
  4. 文章中的所有关键词按照上述方法计算后,然后按位对应相加,举个例子两个关键词的编码分别为:<3,-3,3,-3>和编码<5,5,-5,-5> 和为<8,2,-2,-8>
  5. 我们将最终编码中大于0的都转成1,小于0的转成0,结果为:<1,1,0,0>

通过这种构造方法,我们保留了关键词的权重,这为我们相似性的准确判断打下了基础。

4.2 如何判断相似性

按照上文中计算SimHash函数后,我们每个文章都得到了一个64位的编码,那么如何判断文章的相似性那,最简单的想法是我们先以每位的值为key,文章的ID的列表作为值,做成一个倒排索引。
每位有2个值,64位,所以一共有128个key,值为一个个docId组成的Postlist。假如我们得到一个文章的编码后,比如<1,1,0,0>,按照每一位作为key去倒排索引中查找所有的Postlist,然后比对两个文档中的其他位数是否相同,如果差异的位数小于我们规定的海明距离,则说明两个文档相似。

如何判断两篇文章相似性,第6张
倒排索引

但是这样的话,有个缺点,就是我们每次按位的值去倒排索引里面,只有一位是肯定相同的,其他位是否相同需要比较,这样文档数目比较多,效率比较低。有什么好办法那?有个抽屉原理可以用下,原理很简单,如果3个苹果放进四个抽屉中,那么肯定有一个抽屉为空的。刚开始看到原理还是在《算法之美》里面讲哈希函数的时候,用来证明哈希函数是肯定有冲突的。那在这里怎么用那?

我们以海明距离为3为例,即差异3位以及以下位数的编码认为是相似的,我们将64位编码分为4组,每组16位,由于我们规定了差异只能3位以及以下,那么四组中,肯定有一组是相同的,如果没有一组相同的,那么4组就是4位不同,这样就不满足海明距离了。

所以我们可以以一组16位作为一个key建立一个个倒排索引。在比较相似性的时候,将要查询文档的64位编码拆分成4个16位为一组,共4组,然后以每组16位作为key,去倒排索引中查找,查找16位都相同的文档列表,得到四组文档列表。依次和要查询文档的64位编码进行比对,满足海明距离为3的就是相似问题。

这种分组方法建立倒排索引的时候也有缺点,就是如果海明距离从3改成4,这样整个倒排索引都要重新建。对于这种情况,我们可以按照不同的位数建立多个倒排索引,然后根据海明距离来选择合适的倒排索引来进行比对。

好了,就聊到这里吧,下次有机会自己实现下。

五 诗词赏析

溪上遇雨二首
[唐] [崔道融] )

回塘雨脚如缫丝,野禽不起沈鱼飞。
耕蓑钓笠取未暇,秋田有望从淋漓。

坐看黑云衔猛雨,喷洒前山此独晴。
忽惊云雨在头上,却是山前晚照明。


https://www.xamrdz.com/bigdata/7dx1874191.html

相关文章: