[转][转]文本相似度算法

标签: | 发表时间:2013-12-11 02:31 | 作者:heiyeshuwu
出处:http://blog.csdn.net/heiyeshuwu


来源: http://www.cnblogs.com/liangxiaxu/archive/2012/05/05/2484972.html


文本相似度算法

1.信息检索中的重要发明TF-IDF

1.1TF

Term frequency即关键词词频,是指一篇文章中关键词出现的频率,比如在一篇M个词的文章中有N个该关键词,则

clip_image002(公式1.1-1)

为该关键词在这篇文章中的词频。

1.2IDF

Inverse document frequency指逆向文本频率,是用于衡量关键词权重的指数,由公式

clip_image004(公式1.2-1)

计算而得,其中D为文章总数,Dw为关键词出现过的文章数。

2.基于空间向量的余弦算法

2.1算法步骤

预处理→文本特征项选择→加权→生成向量空间模型后计算余弦。

2.2步骤简介

2.2.1预处理

预处理主要是进行中文分词和去停用词,分词的开源代码有:ICTCLAS。

然后按照停用词表中的词语将语料中对文本内容识别意义不大但出现频率很高的词、符号、标点及乱码等去掉。如“这,的,和,会,为”等词几乎出现在任何一篇中文文本中,但是它们对这个文本所表达的意思几乎没有任何贡献。使用停用词列表来剔除停用词的过程很简单,就是一个查询过程:对每一个词条,看其是否位于停用词列表中,如果是则将其从词条串中删除。

clip_image006

图2.2.1-1中文文本相似度算法预处理流程

2.2.2文本特征项选择与加权

过滤掉常用副词、助词等频度高的词之后,根据剩下词的频度确定若干关键词。频度计算参照TF公式。

加权是针对每个关键词对文本特征的体现效果大小不同而设置的机制,权值计算参照IDF公式。

2.2.3向量空间模型VSM及余弦计算

向量空间模型的基本思想是把文档简化为以特征项(关键词)的权重为分量的N维向量表示。

这个模型假设词与词间不相关(这个前提造成这个模型无法进行语义相关的判断,向量空间模型的缺点在于关键词之间的线性无关的假说前提),用向量来表示文本,从而简化了文本中的关键词之间的复杂关系,文档用十分简单的向量表示,使得模型具备了可计算性。

在向量空间模型中,文本泛指各种机器可读的记录。

用D(Document)表示文本,特征项(Term,用t表示)指出现在文档D中且能够代表该文档内容的基本语言单位,主要是由词或者短语构成,文本可以用特征项集表示为D(T1,T2,…,Tn),其中Tk是特征项,要求满足1<=k<=N。

下面是向量空间模型(特指权值向量空间)的解释。

假设一篇文档中有a、b、c、d四个特征项,那么这篇文档就可以表示为

D(a,b,c,d)

对于其它要与之比较的文本,也将遵从这个特征项顺序。对含有n个特征项的文本而言,通常会给每个特征项赋予一定的权重表示其重要程度,即

D=D(T1,W1;T2,W2;…,Tn,Wn)

简记为

D=D(W1,W2,…,Wn)

我们把它叫做文本D的权值向量表示,其中Wk是Tk的权重,1<=k<=N。

在上面那个例子中,假设a、b、c、d的权重分别为30,20,20,10,那么该文本的向量表示为

D(30,20,20,10)

在向量空间模型中,两个文本D1和D2之间的内容相关度Sim(D1,D2)常用向量之间夹角的余弦值表示,公式为:

clip_image008

其中,W1k、W2k分别表示文本D1和D2第K个特征项的权值,1<=k<=N。

下面是利用模型进行余弦计算的示例。

在自动归类中,我们可以利用类似的方法来计算待归类文档和某类目的相关度。

假设文本D1的特征项为a,b,c,d,权值分别为30,20,20,10,类目C1的特征项为a,c,d,e,权值分别为40,30,20,10,则D1的向量表示为

D1(30,20,20,10,0)

C1的向量表示为

C1(40,0,30,20,10)

则根据上式计算出来的文本D1与类目C1相关度是0.86。

那么0.86具体是怎么推导出来的呢?

在数学当中,n维向量是

V{v1,v2,v3,...,vn}

模为

|v|=sqrt(v1*v1+v2*v2+…+vn*vn)

两个向量的点积

m*n=n1*m1+n2*m2+......+nn*mn

相似度

sim=(m*n)/(|m|*|n|)

它的物理意义就是两个向量的空间夹角的余弦数值。

下面是代入公式的过程:

d1*c1=30*40+20*0+20*30+10*20+0*10=2000

|d1|=sqrt(30*30+20*20+20*20+10*10+0*0)=sqrt(1800)

|c1|=sqrt(40*40+0*0+30*30+20*20+10*10)=sqrt(3000)

sim=d1*c1/(|d1|*|c1|)=2000/sqrt(1800*3000)=0.86066

完毕。

2.3算法实现

开源代码:Text-Similarity-0.08

简介:PERL脚本、自定义去停用词表、无语义识别功能、不适于中文。

局限:仅适用于英文、无语义相似判别功能

编译安装:

(1)进入代码主目录里的/bin

修改text_similarity.pl

将第一行改为#!/usr/bin/perl

(2)退回代码主目录,分别执行

perl Makefile.PL

make

make test

make install

(3)重新进入主目录/bin进行测试

clip_image010

图2.3-1代码效果

可以看见语句“.......this is one”与“????this is two”的匹配度是0.66;

“.......this is one”与“.......this is two”的匹配度仍然是0.66;

“.......this is one”与“…….this is one”的匹配度是1;

“.......this is one”与“..()()this is one”的匹配度是1。

说明匹配的算法去停用字功能存在。

2.4缺陷

这类算法没有很好地解决文本数据中存在的自然语言问题,即同义词和多义词。这样对于搜索的精度产生很大的影响。

2.5算法变体

clip_image012

图2.5-1算法变体(红)

3.改进算法

3.1隐形语义引标

隐性语义标引(LSI)利用矩阵理论中的“奇异值分解(SVD)”技术,将词频矩阵转化为奇异矩阵:首先从全部的文档集中生成一个文档矩阵,该矩阵的每个分量为整数值,代表某个特定的文档矩阵出现在某个特定文档中次数。然后将该矩阵进行奇异值分解,较小的奇异值被剔除。结果奇异向量以及奇异值矩阵用于将文档向量和查询向量映射到一个子空间中,在该空间中,来自文档矩阵的语义关系被保留。最后,可以通过标准化的内积计算来计算向量之间的夹角余弦相似度,进而根据计算结果比较文本间的相似度。LSI引入的唯一变化就是剔除小的奇异值,因为与小的奇异值相关联的特征实际上在计算相似度时并不相关,将它们包括进来将降低相关性判断的精确度。保留下来的特征是那些对文档向量在m维空间中的位置大有影响的特征。剔除小的奇异值将文档特征空间变为文档概念空间。概念向量之问使用内积的夹角余弦相似度计算比原来基于原文本向量的相似度计算更可靠,这也是使用LSI方法的主要原因所在。LSI的缺点在于它的效果依赖于上下文信息,过于稀疏的语料不能很好的体现其潜在的语义。

3.2基于语义相似度的文本相似度算法

用向量空间模型(VSM)来表示文本在该领域内普遍受到认可,是因为其在知识表示方法上的巨大优势。在该模型中,文本内容被形式化为多维空间中的一个点,通过向量的形式给出,把对文本内容的处理简化为向量空间中向量的运算,使问题的复杂性大为降低。但是它很大的不足之处在于只考虑了词在上下文中的统计特性,假定关键词之间线性无关,而没有考虑词本身的语义信息,因此具有一定的局限性。

结合语义相似度计算后的算法流程如下所示:

clip_image014

图3.2-1基于向量空间的语义相似度算法流程图

其中,语义相关度计算获得相似度矩阵的方向有两个:基于知网HowNet或者基于WordNet。

4.其它算法涉及的相似度衡量方式

4.1基于拼音相似度的汉语模糊搜索算法

不同于传统的以关键词匹配为核心的匹配技术,这里提出基于拼音相似度的编辑距离来衡量汉字字符串之间的相似度。

论文提出三种编辑距离:基于汉字的编辑距离、基于拼音的编辑距离,以及基于拼音改良的编辑距离。

4.2最长公共子序列

(1)将两个字符串分别以行和列组成矩阵。

(2)计算每个节点行列字符是否相同,如相同则为1。

(3)通过找出值为1的最长对角线即可得到最长公共子串。

为进一步提升该算法,我们可以将字符相同节点的值加上左上角(d[i-1,j-1])的值,这样即可获得最大公共子串的长度。如此一来只需以行号和最大值为条件即可截取最大子串。

4.3最小编辑距离算法

(1)狭义编辑距离

设A、B为两个字符串,狭义的编辑距离定义为把A转换成B需要的最少删除(删除A中一个字符)、插入(在A中插入一个字符)和替换(把A中的某个字符替换成另一个字符)的次数,用ED(A,B)来表示。直观来说,两个串互相转换需要经过的步骤越多,差异越大。

(2)步骤

1.对两部分文本进行处理,将所有的非文本字符替换为分段标记“#”

2.较长文本作为基准文本,遍历分段之后的短文本,发现长文本包含短文本子句后在长本文中移除,未发现匹配的字句累加长度。

3.比较剩余文本长度与两段文本长度和,其比值为不匹配比率。

5.总结

衡量文本相似度的几种手段:

(1)最长公共子串(基于词条空间)

(2)最长公共子序列(基于权值空间、词条空间)

(3)最少编辑距离法(基于词条空间)

(4)汉明距离(基于权值空间)

(5)余弦值(基于权值空间)



作者:heiyeshuwu 发表于2013-12-10 18:31:21 原文链接
阅读:36 评论:0 查看评论

相关 [文本 相似 算法] 推荐:

[转][转]文本相似度算法

- - heiyeluren的blog(黑夜路人的开源世界)
来源: http://www.cnblogs.com/liangxiaxu/archive/2012/05/05/2484972.html. 1.信息检索中的重要发明TF-IDF. Term frequency即关键词词频,是指一篇文章中关键词出现的频率,比如在一篇M个词的文章中有N个该关键词,则.

[转][转] 文本相似性算法Simhash原理及实践

- - heiyeluren的blog(黑夜路人的开源世界)
simhash(局部敏感哈希)的原理. simhash广泛的用于搜索领域中,也许在面试时你会经常遇到这样的问题,如果对抓取的网页进行排重,如何对搜索结果进行排重等等. jaccard相似度也是一种相似 算法,它的计算方式比较直观,就是sim(x,y)= (x∩y) / (x∪y),例如:.      若  S={a, d}, T={a, c, d} .

字符串相似算法-Jaro-Winkler Distance

- - 开源软件 - ITeye博客
Jaro-Winkler Distance 算法. 这是一种计算两个字符串之间相似度的方法,想必都听过Edit Distance,Jaro-inkler Distance 是Jaro Distance的一个扩展,而Jaro Distance(Jaro 1989;1995)据说是用来判定健康记录上两个名字是否相同,也有说是是用于人口普查,具体干什么就不管了,让我们先来看一下Jaro Distance的定义.

[记录]字符串相似度算法(编辑距离算法 Levenshtein Distance)

- - xilo's blog
在搞验证码识别的时候需要比较字符代码的相似度用到“编辑距离算法”,关于原理和C#实现做个记录. 编辑距离,又称Levenshtein距离(也叫做Edit Distance),是指两个字串之间,由一个转成另一个所需的最少编辑操作次数,如果它们的距离越大,说明它们越是不同. 许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符.

相似图片搜索的三种哈希算法

- - CSDN博客推荐文章
想必大家都用google或baidu的识图功能,上面就是我搜索冠希哥一幅图片的结果,达到图片比较目的且利用信息指纹比较有三种算法,这些算法都很易懂,下面分别介绍一下:. 一、平均哈希算法(aHash). 此算法是基于比较灰度图每个像素与平均值来实现的,最适用于缩略图,放大图搜索. 1.缩放图片:为了保留结构去掉细节,去除大小、横纵比的差异,把图片统一缩放到8*8,共64个像素的图片.

从相似度算法谈起 - Effective similarity search in PostgreSQL

- - 云栖社区-精彩推荐
标签 PostgreSQL , 数组 , 相似度 背景 相似度分析是一个非常普遍的需求,例如根据用户提供的线索,从一堆文本数据、图片数据、视频数据中筛选一段与用户的描述相近的. 我之前写过一系列的文章来介绍,文本、图片相似度搜索的技术和使用场景. 《PostgreSQL 在视频、图片去重,图像搜.

海量数据相似度计算之simhash短文本查找

- - ITeye博客
在前一篇文章 《 海量数据相似度计算之simhash和海明距离》 介绍了simhash的原理,大家应该感觉到了算法的魅力. 但是随着业务的增长 simhash的数据也会暴增,如果一天100w,10天就1000w了. 我们如果插入一条数据就要去比较1000w次的simhash,计算量还是蛮大,普通PC 比较1000w次海明距离需要 300ms ,和5000w数据比较需要1.8 s.

文本相似度计算-google的simHash汉明距离

- - 行业应用 - ITeye博客
       针对文本相似性计算,很多开发朋友首先想到的应该是使用向量空间模型VSM(Vector Space Model). 使用VSM计算相似度,先对文本进行分词,然后建立文本向量,把相似度的计算转换成某种特征向量距离的计算,比如余弦角、欧式距离、Jaccard相似系数等. 这种方法存在很大一个问题:需要对文本两两进行相似度比较,无法扩展到海量文本的处理.

java 两字符串相似度计算算法 (转)Levenshtein Distance编辑距离算法

- - 开源软件 - ITeye博客
Levenshtein distance最先是由俄国科学家Vladimir Levenshtein在1965年发明,用他的名字命名. 不会拼读,可以叫它edit distance(编辑距离). 原理很简单,就是返回将第一个字符串转换(删除、插入、替换)成第二个字符串的编辑次数. 次数越少,意味着字符串相似度越高 .

文本比较算法--LD算法(C++实现)

- - CSDN博客推荐文章
在日常应用中,文本比较是一个比较常见的问题. 文本比较算法也是一个老生常谈的话题.   文本比较的核心就是比较两个给定的文本(可以是字节流等)之间的差异. 目前,主流的比较文本之间的差异主要有两大类. 一类是基于编辑距离 (Edit Distance)的,例如LD算法. 一类是基于最长公共子串的(Longest Common Subsequence),例如Needleman/Wunsch算法等.