文本相似度算法小结

分词 + 杰卡德系数

首先是最简单粗暴的算法。为了对比两个东西的相似度,我们很容易就想到可以看他们之间有多少相似的内容,又有多少不同的内容,再进一步可以想到集合的交并集概念。

因此引入了杰卡德系数这一概念,这是一个非常简单的想法。

假设有两个集合A,B;如果我们想要知道这两个集合的相似度究竟有多少,我们可以进行如下的计算:

这个结果称为杰卡德相似系数,越大表明两个集合的相似度越高。

1 - J(A,B)则被称为杰卡德距离,越大表明两个集合的相似度越小。

有了这个公式,我们只需要将文本抽象成集合就行了,方法就是分词:英文的分词可以直接用空格来分割,中文的话可以考虑jieba分词,效果比较有保证。

这个算法的计算效率最高、最快。不过因为公式太简单,能涵盖到的维度太少,所以在需要比较高准度的场合并不适用。当然如果要判断的文本不存在语义等复杂问题要考虑,量又比较大的话,还是个非常不错的选择。

TF-IDF + 余弦相似性

参考文章:阮一峰:TF-IDF与余弦相似性的应用

提取关键词

这个算法比较简单,也很好理解,效果也相对不错。首先我们要尝试从文本中提取出关键词,也就是最能描述文章主题的关键词。

最直观的想法是统计词频(TF):统计每个词在文本中出现的次数,出现的越频繁,那么就越可能是这个文章的关键词。

但这样还不够,因为有些实际无用的词出现的频率会很高,比如“的”、“是”、“在”这样的单词,我们称之为停用词,应该过滤掉。

但即便过滤掉后,还要考虑剩下的词中,有的词会是很常见的词,有的词会是很少见的词。一般来说,如果很少见的词在文本中出现的次数很多,那么它比起常见的词,成为文本关键词的可能性要更大。

引入逆文档频率(IDF)的概念:可以理解IDF是每一个词重要性的权重,一个词越少见,它的权重就越大(因为更有可能符合主题),反之,一个词越常见,它的IDF就越小。

于是,我们可以使用TF*IDF这个乘积来描述某个词对文章的“重要性”。

具体的数学定义如下:

  • 计算TF(两种参考算法):
- 词频TF = 某个词在文章中出现的次数/文章的总词数
- 词频TF = 某个词在文章中出现的次数/文章中出现的最多的词出现的次数
  • 计算IDF:
首先需要有一个语料库,来模拟语言的使用环境。
- IDF = log(语料库的文档总数/包含该词的文档数+1)

余弦相似度

现在我们有了两个文本,也分别使用TF-IDF提取出了他们的关键词,那么要如何判定它们是否相似呢?

首先第一步是将关键词抽象成向量,这一点很重要,举个例子

句子1:

我/喜欢/看/电视,不/喜欢/看/电影。

句子2:

我/不/喜欢/看/电视,也/不/喜欢/看/电影。

提取关键词后,我们可以计算每个句子中,每个关键词的词频:

句子1:

我 1,喜欢 2,看 2,电视 1,电影 1,不 1,也 0。

句子2:

我 1,喜欢 2,看 2,电视 1,电影 1,不 2,也 1。

因此句子1对应的向量就是[1, 2, 2, 1, 1, 1, 0],句子2对应的向量就是[1, 2, 2, 1, 1, 2, 1]

于是,计算两个文本相似度的问题,变成了计算两个向量相似度的问题。

有了向量,我们就可以使用数学知识来解决问题了,我们可以把向量想象成多维空间里的两条直线(好吧,这有点抽象,需要一些数学知识来理解),那么两个向量的相似度可以量化称为这两条直线的“夹角”,夹角越小,说明它们越接近,也就是越相似。

计算夹角的方式有很多,最常用的就是余弦定理了,在多维空间中也一样适用。

多维空间向量的余弦公式如下:

用图来直观的理解就是:

(图片引用自阮一峰博客)

因此我们根据余弦公式计算出的角度大小,就能近似的判断两个文本的内容相似程度。

值得一提的是,空间向量+余弦相似度这个算法也被广泛地应用于推荐系统中(据说网易云的推荐就是基于这个算法),这里也展开一下对应的思路。

基于相似度的推荐算法,其实就是根据已有的用户行为数据去推断一个新的用户可能做出的下一个行为。具体的举个例子,比如网易云的电台推荐。

我们把每首歌都做上编号,那么我们听歌的历史可以做成一个编号的序列,其实也就是一个向量。接下来我们可以去搜索已有的所有用户的听歌序列里(也是向量)和这个向量夹角最小,也就是最相似的那一个。那么这个已有的序列里的下一首,很可能就是我们想听的下一首。

这么说可能有点抽象,不如做一个简单的数据来看看。假设曲库中有10首歌,编号为0~9,现在我的听歌序列(向量)为[0,2,4,7],系统想要为我推荐下一首歌曲时,就会在系统已有的用户播放序列里搜索,比如它找到了一个跟我口味很像(历史播放向量跟我夹角最小的那个)的家伙,他的听歌序列为[0,2,3,7,5],那么系统为我推荐的下一首歌,很可能就是编号为5的这首歌。

当然,实际的推荐系统远比这个复杂的多,不过核心的思路却是没有变化的。

词袋模型和LSI模型

参考文章:python文本相似度计算

当然,将一个文本向量化的方式有很多,TF-IDF只是其中的一种。

下面再给出两种比较常见的向量化手段:

  1. 词袋模型

在NLP里比较常用的手段(如word2vec)。核心想法是把一篇文章想象成词的组合,没有顺序和语义之分,文章就是一个装满了词的袋子。

根据语料集,把所有的词都提取出来,编上序号,假设我们的语料集里有100个词,那么每个文章就是一个100维的向量:每个位置上的数字表示对应编号的词在该文章中出现的次数。

举个例子,语料集为

John likes to watch movies. Mary likes too.
John also likes to watch football games.

从这两句话中构建出的词集合(字典)即为:

{"John": 1, "likes": 2,"to": 3, "watch": 4, "movies": 5,"also": 6, "football": 7, "games": 8,"Mary": 9, "too": 10}

那么上述两个句子,用词袋模型向量化之后就是

[1, 2, 1, 1, 1, 0, 0, 0, 1, 1]
[1, 1, 1, 1, 0, 1, 1, 1, 0, 0]

2. LSI模型

TF-IDF模型基本已经能够胜任绝大多数的文本分析任务了,但是存在一个问题:实际的文本,用TF-IDF表示的维度太高,不易于计算,因此引入了LSI的概念,从语义和文本的潜在主题来分析。

LSI是概率主题模型的一种,基于统计学和概率论方法实现,类似的模型有LDA等,具体的理论学术性太强,需要专门的数学证明来说明,这里只展开一下核心思想:

每篇文本中有多个概率分布不同的主题,每个主题中都包含所有已知词,但是这些词在不同主题中的概率分布不同,LSI通过奇异值分解的方法,计算文本中的各个主题的概率分布。这样做的好处是,我们的向量从词的维度下降到文本的主题的维度,维度更少,计算更快。

其他

简要的提一下其他的相似度/距离公式和算法,在某些场景下也会是不错的选择。

1. 欧式距离

就是计算欧式几何坐标系中两个点的距离(当然也需要向量化),距离越大说明相似度越低:

2. 汉明距离

这个在计算图片相似度的时候会用到(可见本博客相关文章),汉明距离只是简单的计算两个序列中,有多少位是不一样的,一般用于哈希的对比。

3. 编辑距离

编辑距离,又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。例如,kitten与sitting之间的编辑距离为3。可用于DNA分析、语音辨识、抄袭判重等相关领域。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏新智元

Hinton 谷歌大脑最新研究:1370 亿参数超大规模神经网络

【新智元导读】谷歌大脑研究员昨天往 arXiv 上传了被 ICLR'17 接收的一篇论文,作者包括深度学习教父 Geoffrey Hinton 和谷歌技术大牛 ...

356130
来自专栏量子位

无监督学习才不是“不要你管”

无监督学习是机器学习算法里非常扑朔迷离的一个类别,负责解决这些“没有真实值 (no-ground-truth) ”的数据。

10420
来自专栏AI研习社

博客 | 论文解读:对端到端语音识别网络的两种全新探索

雷锋网 AI 科技评论按:语音识别技术历史悠久,早在上世纪 50 年代,贝尔研究所就研究出了可以识别十个英文数字的简单系统。从上世纪 70 年代起,传统的基于统...

16930
来自专栏大数据挖掘DT机器学习

搭建LSTM(深度学习模型)做文本情感分类的代码

传统的文本情感分类思路简单易懂,而且稳定性也比较强,然而存在着两个难以克服的局限性: 一、精度问题,传统思路差强人意,当然一般的应用已经足够了,但是要进一步提高...

73180
来自专栏机器人网

深度学习知识框架--概率图模型

在实际应用中,变量之间往往存在很多的独立性假设或近似独立,随机变量与随机变量之间存在极少数的关联。PGM根据变量之间的独立性假设,为我们提供了解决这类问题...

12920
来自专栏大数据文摘

暑期追剧学AI | 十分钟搞定机器学习中的数学思维(二)

16020
来自专栏大数据挖掘DT机器学习

大白话解析模拟退火算法

一. 爬山算法 ( Hill Climbing ) 介绍模拟退火前,先介绍爬山算法。爬山算法是一种简单的贪心搜索算法,该算法每次从当前解的临近...

47890
来自专栏新智元

【一文读懂Bengio研究组最新论文】图谱注意力网络GAT,以图谱做输入做深度学习

作者:邓侃 编辑:闻菲 【新智元导读】Yoshua Bengio 团队日前提出了一种名叫图谱注意力网络(Graph Attention Network,GAT)...

60870
来自专栏新智元

深度学习盛会 ICLR-17 最佳论文出炉!机器自主编程 NPI 再称雄

1 新智元编译 来源:iclr.cc、openreview.net 编译:闻菲、张易、刘小芹 【新智元导读】深度学习盛会 ICLR 2017 日程及最佳论文...

441130
来自专栏专知

基于信息理论的机器学习-中科院自动化所胡包钢研究员教程分享03(附pdf下载)

【导读】专知于11月24日推出胡老师的基于信息理论的机器学习报告系列教程,大家反响热烈,胡老师PPT内容非常翔实精彩,是学习机器学习信息理论不可多得的好教程,今...

36670

扫码关注云+社区

领取腾讯云代金券