朝花夕拾|勿忘初心 朝花夕拾|勿忘初心

简单计算文本相似度

in 机器学习小白笔记 read (202) 2167汉字 站长Lucifaer 文章转载请注明来源!

这段时间做了些关于文本相似度的工作,发现现在对于自然语言的处理技术已经到达了一种很成熟的地步,但是在对文本相似度的识别上,尤其是对中文的文本相似度识别上还是稍显乏力。这里把学习过程中的笔记传上来,做一个记录。

0x00 概述

关于文本相似度的计算,对于不同的语言难易度是不同的。相较于中文来说,英文的文本相似度会好做很多。

计算文本相似度的几个算法大致可以分为以下几类:

  • 最长公共子串、编辑距离(基于原文本进行查找测试)
  • 分词后进行集合操作(TF-IDF)
  • 分词后对得到的词项的权重进行计算(余弦夹角算法、欧式距离、simhash)

接下来用实例代码对这几个算法进行下总结。

0x01 中文分词

在使用这几个算法时,我们注意到其对中文分词有较高的要求。我们这边来说说中文分词。

对于机器的语义识别,感兴趣的话可以看看PYTHON自然语言处理这本书。这边就不赘述原理了(我也不懂,对吧)

但是对于我们这些并不需要了解原理只求能使用的人来说,选择一个高效准确的分词库就显得非常的重要了。

对于英文的分词,nltk这个库已经做到了业界标准,就不多说了,我们重要的谈谈有什么比较好用的中文分词库。

一下是我经过测试后发现的一些较为精准的库:

  • THULAC 清华的一个高效的分词工具包,我觉得比jieba好用多了。
  • 腾讯文智 腾讯的分词确实比较好用,精准度非常高,但是缺点就是只有5w次的免费api使用次数限制。

接下来的中文分词我都是用THULAC来做的。

0x02 最长公共子串算法

这个算法本来叫Longest_common_subsequence,这个算法针对于计算英文的文本相似度,想了解详情的请点击链接查看详情。

简单的说一下原理:A组和B组最长的共同子序列(或LCS)是来自A和B的最长组,在两组之间是常见的,并且在每组中以相同的顺序排列的一组数

接下来我用一个demo来计算两串英文字符串的相似度。

比如现在有两组字符串thisisatesttesting123testing,其LCS通过算法得出的就是tsitest

在python中可以调用mlpy库来简单的实现该算法:

import string
import mlpy
a = string.ascii_letters + string.digits
text1_temp = []
text2_temp = []
temp_list = {}
i = 1
for j in a:
    temp_list.setdefault(j, i)
    i += 1

text1 = 'thisisatest'
text2 = 'testing123testing'
for i in text1:
    text1_temp.append(temp_list[i])
for i in text2:
    text2_temp.append(temp_list[i])

length, path = mlpy.lcs_std(text1_temp, text2_temp)
print(length)
print(path)

我们的所建立的映射字典是:

所得的结果是:

可以看出,我们从这两个字符串中可以得到长度为7的LCS字符串;具体的对应关系可以从两个数组中看出:第一个字符串的第一位对应第二个字符串的第一位,以此类推。

从LCS在各个字符串中的占比,可以看出两个字符串的相关性。

0x03 TF-IDF

这是一种常用于信息检索与文本挖掘的加权技术。通常用于筛选关键字。

原理请看TF-IDF原理

下面给出用python3实现的例子:

python中sckit-learn库中已经实现了该功能,直接调用即可。下面是对优酷词集与youtube词集的TF-IDF值计算,我抽取了TF-IDF值大于0.2的词进行展示:

from thulac import thulac
from sklearn.feature_extraction.text import TfidfTransformer
from sklearn.feature_extraction.text import CountVectorizer


def depart_strings(text):
    temp_list = []
    for i in text:
        temp_list.append(i[0])
    return temp_list


text1 = """优酷由古永锵在2006年6月21日创立[1]  。2006年12月21日正式上线。[2]  优酷现为阿里巴巴文化娱乐集团大优酷事业群下的视频平台。[3]  目前,优酷、土豆两大视频平台覆盖5.8亿多屏终端、日播放量11.8亿,支持PC、电视、移动三大终端,兼具版权、合制、自制、自频道、直播、VR等多种内容形态。业务覆盖会员、游戏、支付、智能硬件和艺人经纪,从内容生产、宣发、营销、衍生商业到粉丝经济,贯通文化娱乐全链路"""
text2 = """YouTube是世界上最大的视频网站,早期公司位于加利福尼亚州的圣布鲁诺。注册于2005年2月15日,由华裔美籍华人陈士骏等人创立。在比萨店和日本餐馆,让用户下载、观看及分享影片或短片。
2006年11月,Google公司以16.5亿美元收购了YouTube,并把其当做一家子公司来经营。但是对于如何通过YouTube盈利,Google一直保持非常谨慎的态度。被收购后的YouTube依然风靡全球网民,花旗银行分析师认为,以2012年整年计算,Google可能从YouTube获得24亿美元的净收入。2014年1月3日,YouTube宣布在拉斯维加斯消费电子展(CES)上演示4K高清视频流媒体服务。该服务采用谷歌的视频编解码技术VP9。网站的未注册用户仍可以直接观看视频,而注册用户则可以上传无限制数量的影片。而当影片有可能的冒犯性质的内容时,仅提供给18岁以上的注册用户观看。YouTube作为当前行业内在线视频服务提供商,YouTube的系统每天要处理上千万个视频片段,为全球成千上万的用户提供高水平的视频上传、分发、展示、浏览服务。2015年2月,央视首次把春晚推送到YouTube等境外网站。"""
corpus = []
text1_keyword = []
text2_keyword = []

depart_list = ['n']
thul = thulac(seg_only=False)
text1 = thul.cut(text1)
text2 = thul.cut(text2)
depart_text1 = depart_strings(text1)
depart_text2 = depart_strings(text2)
corpus.append(' '.join(depart_text1))
corpus.append(' '.join(depart_text2))
vectorizer = CountVectorizer()
transformer = TfidfTransformer()
tfidf = transformer.fit_transform(vectorizer.fit_transform(corpus))
word = vectorizer.get_feature_names()
weight = tfidf.toarray()
for j in range(len(word)):
    if weight[0][j] > 0.2:
        text1_keyword.append(word[j])
    if weight[1][j] > 0.2:
        text2_keyword.append(word[j])

print(text1_keyword)
print(text2_keyword)

结果:

之后就可以用接下来的余弦相似度来对两组文本进行相似度判断了。

可以说通过TF-IDf值,我们能对一大段文本进行关键词的筛选,方便之后的算法进行相似度检查。

0x04 simhash

simhash分这么几步:

  • hash:通过hash算法把每个词变成hash值,也就是将字符串转换成一串数字,这样可以提高相似度计算性能。
  • 加权:将hash后的结果按照单词的权重形成加权数字串。
  • 合并:将上面各个单词算出来的序列值累加,变成只有一个序列串。
  • 降维:将合并后的序列串变成0、1串,形成最终的simhash签名。如果每一位大于0,记为1;小于0,记为0。

想了解详情,请见simhash算法原理及实现

盗一张可以清晰说明该算法关系的图:

算出两个字符串的simhash后,我们可以通过计算两个字符串的海明距离。

simhash值的海明距离是A xor B后二进制中1的个数。计算完海明距离的数值后,我们判定A和B的相似条件是A和B的海明距离是否小于等于n。n值根据经验一般为3。

下面我们来用一段demo代码来做例子:

python中对于simhash的计算已经有现成的库了

from simhash import Simhash


text1 = '这是一段很长的文本1'
text2 = '这是一段很长的文本2'

print(Simhash(text1).distance(Simhash(text2)))

计算出两字符串的海明距离为:

由此可见,simhash对于中文文本的相似度识别并不准确,存在“相当大”的误差(当然,simhash对于大文本来说有非常好的效果,起码要在500字以上,这里说的误差是针对于小文本来说的)。

0x05 余弦相似度

余弦相似度可以简单的解释为:通过字在两段文本频度占比,通过欧几里得点积求出两个向量的夹角余弦值来度量他们之间的相似度。

举个例子。现在我们通过分词得到了两个词集为(30,40,大码,连衣裙),A短句为(30岁至40岁女装连衣裙),B短句为(大码女装连衣裙),按照词是否出现,我们将A,B两个短句定义成两个向量,出现为1,不出现为0,则A=(1,1,0,1,1),B=(0,0,1,1,1),则他们的余弦相似度为:

下面通过代码来说:

这边用在爱站上查到的p神博客的meta关键字与入链关键字举例:

from thulac import thulac


def depart_strings(text1, text2, depart_list):
    temp_list1 = []
    temp_list2 = []
    for i in text1:
        for j in depart_list:
            if i[1] == j:
                temp_list1.append(i[0])
    for i in text2:
        for j in depart_list:
            if i[1] == j:
                temp_list2.append(i[0])
    temp_list = set(temp_list1 + temp_list2)
    return temp_list


def getkeyword(text):
    keyword = []
    for i in text:
        keyword.append(i[0])
    return keyword


def confirm(text_keywords, keywords):
    result = []
    for i in keywords:
        if i in text_keywords:
            result.append(1)
        else:
            result.append(0)
    return result


def consin(text1, text2, keywords):
    denomainator = 0.0
    norm_a = 0.0
    norm_b = 0.0
    list_a = confirm(getkeyword(text1), keywords)
    list_b = confirm(getkeyword(text2), keywords)
    for a, b in zip(list_a, list_b):
        denomainator += a * b
        norm_a += a**2
        norm_b += b**2
    if norm_a == 0.0 or norm_b == 0.0:
        return None
    else:
        print("余弦相似度:")
        return denomainator / ((norm_a * norm_b) ** 0.5)


def main():
    text1 = "python/mysql/php/网络安全/信息安全/C++/漏洞挖掘/代码审计"
    text2 = "离别歌/离别歌曲/ewebeditor漏洞/离别的歌曲/socket通信/"
    depart_list = ['mq', 'n']
    thul = thulac(seg_only=False)
    text1 = thul.cut(text1)
    text2 = thul.cut(text2)
    print("text1 分词:")
    print(text1)
    print("text2 分词:")
    print(text2)
    keywords = depart_strings(text1, text2, depart_list)
    print("关键词集:")
    print(keywords)
    return consin(text1, text2, keywords)


if __name__ == '__main__':
    print(main())

结果:

0x06 总结一下

上面提到了很多种方法,我们总结下来可以分成一下几种:

  • 提取关键字要用的算法:Jaccard相似度,TF-IDf
  • 计算两文本相似度:

    • 较长的文本:先simhash,再求海明距离
    • 短文本:余弦相似度
    • 英文短文本:最长公共子串

通过以上几组算法可以初步的完成信息摘要以及文本相似度识别的功能,但是对于中文来说,以上几种算法都有着各自的限制,想要让机器理解自然语言,仍然需走很长的路。

机器学习
最后由Lucifaer修改于2017-10-30 22:42

此处评论已关闭

博客已萌萌哒运行
© 2018 由 Typecho 强力驱动.Theme by Yodu
PREVIOUS NEXT
雷姆
拉姆