分类

TF-IDF与余弦相似性的应用(二):找出相似文章

作者: 阮一峰

日期: 2013年3月21日

上一次,我用TF-IDF算法自动提取关键词。

今天,我们再来研究另一个相关的问题。有些时候,除了找到关键词,我们还希望找到与原文章相似的其他文章。比如,"Google新闻"在主新闻下方,还提供多条相似的新闻。

为了找出相似的文章,需要用到"余弦相似性"(cosine similiarity)。下面,我举一个例子来说明,什么是"余弦相似性"。

为了简单起见,我们先从句子着手。

  句子A:我喜欢看电视,不喜欢看电影。

  句子B:我不喜欢看电视,也不喜欢看电影。

请问怎样才能计算上面两句话的相似程度?

基本思路是:如果这两句话的用词越相似,它们的内容就应该越相似。因此,可以从词频入手,计算它们的相似程度。

第一步,分词。

  句子A:我/喜欢/看/电视,不/喜欢/看/电影。

  句子B:我/不/喜欢/看/电视,也/不/喜欢/看/电影。

第二步,列出所有的词。

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

第三步,计算词频。

  句子A:我 1,喜欢 2,看 2,电视 1,电影 1,不 1,也 0。

  句子B:我 1,喜欢 2,看 2,电视 1,电影 1,不 2,也 1。

第四步,写出词频向量。

  句子A:[1, 2, 2, 1, 1, 1, 0]

  句子B:[1, 2, 2, 1, 1, 2, 1]

到这里,问题就变成了如何计算这两个向量的相似程度。

我们可以把它们想象成空间中的两条线段,都是从原点([0, 0, ...])出发,指向不同的方向。两条线段之间形成一个夹角,如果夹角为0度,意味着方向相同、线段重合;如果夹角为90度,意味着形成直角,方向完全不相似;如果夹角为180度,意味着方向正好相反。因此,我们可以通过夹角的大小,来判断向量的相似程度。夹角越小,就代表越相似。

以二维空间为例,上图的a和b是两个向量,我们要计算它们的夹角θ。余弦定理告诉我们,可以用下面的公式求得:

假定a向量是[x1, y1],b向量是[x2, y2],那么可以将余弦定理改写成下面的形式:

数学家已经证明,余弦的这种计算方法对n维向量也成立。假定A和B是两个n维向量,A是 [A1, A2, ..., An] ,B是 [B1, B2, ..., Bn] ,则A与B的夹角θ的余弦等于:

使用这个公式,我们就可以得到,句子A与句子B的夹角的余弦。

余弦值越接近1,就表明夹角越接近0度,也就是两个向量越相似,这就叫"余弦相似性"。所以,上面的句子A和句子B是很相似的,事实上它们的夹角大约为20.3度。

由此,我们就得到了"找出相似文章"的一种算法:

  (1)使用TF-IDF算法,找出两篇文章的关键词;

  (2)每篇文章各取出若干个关键词(比如20个),合并成一个集合,计算每篇文章对于这个集合中的词的词频(为了避免文章长度的差异,可以使用相对词频);

  (3)生成两篇文章各自的词频向量;

  (4)计算两个向量的余弦相似度,值越大就表示越相似。

"余弦相似度"是一种非常有用的算法,只要是计算两个向量的相似程度,都可以采用它。

下一次,我想谈谈如何在词频统计的基础上,自动生成一篇文章的摘要。

(完)

珠峰培训

简寻

留言(67条)

写的太好了,忍不住抢楼。。。

挺好的,简单易懂

之前在吴军的数学之美上看到过,不过还是阮兄的文章比较浅显和详细。

这个系列非常有意思,分词、文章相似性、文章摘要提取,通过这个,可以做一个techmeme.com了。。。。

如果上学的时候老师会讲这些东西,我会对数学感兴趣很多...

速度是硬伤啊
感觉您貌似研究了不少相似性算法啊,前面看过了您的PHASH,这次是余弦定理啊,下一次是编辑距离?

浅入深出,好文!

深入浅出体现出功力啊!

太棒了!正好最近要做这方面的东西,博主解释的太棒了!

請教一下, 如果兩個向量長度不同怎麼處理呢?

您的文章一直让我能非常清晰的明白 谢谢

高深的东西浅显的表达出来,此乃实力

刚看数学之美,你这里写的文章更美。深入浅出,博主知识渊博。以后会关注你的文章。加油!

引用passenger的发言:

請教一下, 如果兩個向量長度不同怎麼處理呢?

不同的补0呗

要是在A句子中,“也”字之前加个“但”,向量偏差不大,可是句子偏差较大。其实根本问题是:为什么得到词频数列表后,问题就成了计算向量?

引用jqian的发言:

不同的补0呗

简单的补0比较粗糙,在实际操作中通常用余弦定理的前提会是取n个最具代表行的词,例如20词/篇文章,这样以来向量长度就相等了。

引用Adrian的发言:

要是在A句子中,“也”字之前加个“但”,向量偏差不大,可是句子偏差较大。其实根本问题是:为什么得到词频数列表后,问题就成了计算向量?

举例来说:如果要比较线段的长短,那么我们只需要1个维度(长)就可以;如果是比较平面图形,那么我们需要2个维度(长,宽);同理,比较立方体,那么就需要3个维度(长,宽,高)。

每个句子都可以被视为词的组成。因此,要比较句子,就必须先分解每个句子,统计出其中包含的词语(即维度)和词语出现的频率(即维度的值)。然后综合所有的词语,构建一个统一的n维坐标系,才能进行句子的比较。(如果某个句子不包含某个词语,那么它在这个词语维度上的值计为0)。

阮兄的bolg应该不是用wordpress搭建的,php自己写的?

阮老师,能讲一讲蒙特卡罗及相关采样算法不?

说句闲话,网站排名27000了,个人博客,真不不简单啊

像这种相似性计算的算法应该有很多种吧,可以拿出来介绍介绍

相似度这个概念用的很广,匹配,推荐,聚类都会用到

2个向量比较计算好理解,N个向量计算COS真的可以表示夹角吗?

将文章相似性转为词频向量的间距 讲得好通俗,谢谢! 如果也能讲讲扭曲粘连验证码的切割与识别就好了

既然两句话可以抽象成n维空间中从同一原点出发的两个向量, 为什么不简单计算两个向量指向的端点距离或者距离的平方来给出相似性不是更简单么?

你好,请问“假定a向量是[x1, y1],b向量是[x2, y2],那么可以将余弦定理改写成下面的形式:”

这个定理是怎么被改写的,根据上面的定理cosB = (a^2 + c^2 -b^2) / (2·a·c)
我没有看到c边,他是怎么被推导为下面那个公式的呢?没想通。请求你帮我解惑一下!

太好了!!简单易懂!!感谢!!

写的太简单易懂了,必须顶一下!!!

这种方法计算的相似度每个词的权重是一样的,有没有办法把权重加入到相似度计算的过程里面?

文章中余弦相似性的英文错了,不应该是cosine similiarity,而应该是cosine similarity。

写得太通俗易懂了,正需要这方面的知识,看完豁然开朗!

引用蒙蒙的发言:

这种方法计算的相似度每个词的权重是一样的,有没有办法把权重加入到相似度计算的过程里面?

这也是我想说的,向量用tf表示,为什么不用tf-idf表示,不好吗?
idf的计算可以这样:所处理的所有文本数量作为分母
阮老师写的很赞!

请阮兄多介绍有关文本的知识。

真是大师,讲得这么明白!

看阮兄的微博,涉猎之广,真是令人赞叹

请问,如果vector只包含1或0也可以吗?

例如 vector_1 = [0,1,1], vector_2 = [0,0,1]

谢谢

真的写的很好,刚好有用,感谢!

您好,我想在论文中引用您的博客可以吗?

写的真好,即使是我这种刚接触余弦相似度概念的都能一看就明白!赞一个!

你好,在中文中,如何区分两个字如:“喜欢”是一个词,而不是把直接拆分出来进行比较呢?要怎样来判别一个词或者成语呢

写的真是太好了,浅显易懂,不得不佩服

有点明白了,谢谢分享

最后的余弦值要怎么转换为百分比的相似度呢?余弦值=0.938等同于两篇文章相似度是93.8%吗?

讲解得很细致,也很容易理解,图文并茂,很好的文章,赞一个

博主的博文非常给力,解释的太清楚了,赞一个!

我最近在研究文本挖掘,看了很多书,一个余弦相似度总是看不明白,看了你的文章,瞬间脑洞大开,大哥,我对你的佩服真是由于涛涛江水,连绵不绝,黄河泛滥,一发不可收。

这个算法,貌似没有考虑到词的顺序,
比如
“我喜欢看电影” 和 “电影喜欢看我”
按照词频来统计的话,可能会完全相同,求解答?
27304644@qq.com

写的浅显易懂,不过这类技术在实际中很不实用,因为计算太慢。余弦只是一种距离公式,应用太窄了,还有编辑距离,欧氏距离等等
在实际中,相似度计算,一般是进行1对n的近似搜索,这个n是千亿级别的。
而用余弦作逐一比对是不可能的,所以常用的法则是对每个文档都要形成能用于比对的近似指纹,而这种指纹具有检索性能。

谢谢,讲得好理解

有个问题,用IF-IDF计算时,前提是分词分好的,可分词也是个问题。。。

引用Dj的发言:

既然两句话可以抽象成n维空间中从同一原点出发的两个向量, 为什么不简单计算两个向量指向的端点距离或者距离的平方来给出相似性不是更简单么?

你这样没有考虑长度

引用passenger的发言:

請教一下, 如果兩個向量長度不同怎麼處理呢?

不存在长度不一致问题,即使真的不一致,可进行补全处理,较少的向量补全0

刚好要用到。。

通俗易懂

引用eeriee的发言:

最后的余弦值要怎么转换为百分比的相似度呢?余弦值=0.938等同于两篇文章相似度是93.8%吗?

只能说这是余弦相似度

以前听说过这个概念,没有具体的例子,现在有点形象的理解了

写的不错,对我们编辑来说很有用。。。

什麼樣的情況會是180度?

引用大力哥的发言:

有个问题,用IF-IDF计算时,前提是分词分好的,可分词也是个问题。。。

分词的工具有很多啊。百度一大堆的。直接引用就好了。像盘古等等。

引用SulaXD的发言:

什麼樣的情況會是180度?

完全不相干的文章。。如果根据分词来的话。就是把分好的词全部替换成文章里没有的。。就是180

关于向量的坐标,我能否理解为每次比较时,横坐标相同,例如:
句子A的第1个词是第1个维度,频率是1,用向量表示为[1,1],
句子B的第1个词是第1个维度,频率是1,用向量表示为[1,1], 

句子A的第6个词是第6个维度,频率是1,用向量表示为[6,1],
句子B的第6个词是第6个维度,频率是2,用向量表示为[6,2], 

句子A的第7个词是第7个维度,频率是0,用向量表示为[7,0],
句子B的第7个词是第7个维度,频率是1,用向量表示为[7,1],

发布文章时,提取他的词频,难道要取出所有文章进行构建他们的词频进行向量计算吗?这应该会严重加重发布时的操作等待时间的,
亦或是异步进行?

这里是词袋模型,不考虑词之间的顺序


引用woxiangbo的发言:

这个算法,貌似没有考虑到词的顺序,
比如
“我喜欢看电影” 和 “电影喜欢看我”
按照词频来统计的话,可能会完全相同,求解答?
27304644@qq.com

不会是180度吧,词频向量里的每个元素最小为0,所以算出来夹角最多为90度
比如, [1,0]和[0,1]两个向量


引用wjxdyx的发言:

完全不相干的文章。。如果根据分词来的话。就是把分好的词全部替换成文章里没有的。。就是180

通俗易懂 精辟精辟

有个问题:如果两篇文章分词后得到的两个关键词集合,这两个集合中元素的数量不一样,但是有交集,请问如何计算出向量呢?

刚看完走进搜索引擎,讲的差不多!

写的真不错 比看纯算法理解的快多了!

我要发表看法

«-必填

«-必填,不公开

«-我信任你,不会填写广告链接