收稿日期:2005212226 基金项目:浙江省自然科学基金项目(Y 105118)资助. 作者简介:黄德才,男,1958年生,教授,博士生导师,主要研究方向为人工智能、图像处理、数据挖掘、计算机应用技术等.戚华春,男,1979年生,硕士研究生,主要研究方向为网络应用、数据挖掘和遗传算法等;钱 能,男,1961年生,教授,主要研究方向为网络应用、数据挖掘等.
基于主题相似度模型的TS -PageRank 算法
黄德才,戚华春,钱 能
(浙江工业大学信息工程学院,浙江杭州310014)E 2m ail :hdc @zjut .edu .cn
摘 要:PageR ank 算法是著名搜索引擎Google 的核心算法,但存在主题漂移的问题,致使搜索结果中存在过多与查询主题无关的网页.在分析PageR ank 算法及其有关改进算法的基础上,提出了基于虚拟文档的主题相似度模型和基于主题相似度模型的T S 2PageR ank 算法框架.只要选择不同的相似度计算模型,就可以得到不同的T S 2PageR ank 算法,形成一个网页排序算法簇.理论分析和数值仿真实验表明,该算法在不需要额外文本信息,也不增加算法时空复杂度的情况下,就能极大地减少主题漂移现象,从而提高查询效率和质量.
关键词:链接分析;主题相似度;PageR ank 算法
中图分类号:T P 18 文献标识码:A 文章编号:100021220(2007)0320510205
TS -PageRank A lgor ith m Ba sed on the M odel of Top i c Si m ilar ity
HUAN G D e 2cai ,Q I H ua 2chun ,Q I A N N eng
(Colleg e of Inf or m ation E ng ineering ,Z hej iang U niversity of T echnolog y ,H ang zhou 310014,China )
Abstract :T he PageR ank algorithm is a key algorithm used in famous search engine Google ,but there exists a bad p roble m of top ic 2drift ,w h ich results in too m any w eb pages w ithout any correlati on w ith the user’s search top ic in the list of w eb pages searched by the algorithm .A fter analysing the PageR ank algorithm and its modified algorithm ,a si m ilarity model based on virtual file vector and si m ilar degree of cosine ,and put for w ard a T S 2PageR ank algorithm fram e .W e can get m any different T S 2PageR ank algorithm s and for m a set of T S 2PageR ank algorithm ,if w e use different si m ilarity model in the fram e .T he analysis of theory and num erical si m ulati on illustrate that the T S 2PageR ank algorithm can avoid the p roble m of top ic 2drift and i m p rove the quanlity of w eb search effectively w ithout adding any other extra text infor m ati on or increasing the degree of ti m e and s pace comp lexity .Key words :hyperlink analysis ;top ic si m ilarity ;pagerank algorithm
1 引 言
互联网的规模已经发展到包含大约80亿张网页和560亿个超链接[1].虽然互联网络的发展已经超出了一般人的想象,几乎包容了整个人类历史所积累的全部知识,而且还在以每天超过100万张网页的速度增长,但如何快速地在互联网的海量信息中检索出有效信息却成为当前互联网应用中的瓶颈问题.自从以斯坦福大学Sergey B rin 和L aw rence Page 提出的PageR ank [2]算法为核心所开发的搜索引擎Google 在商业应用中获得极大成功之后,引发了人们研究网络结构分析算法的极大兴趣,越来越多的学者开始致力于这方面的研究工作.
目前对网络的组织结构和链接关系进行挖掘的算法主要有2类[1]:
(1)PageR ank 算法:该算法提取网页的链接信息,进行离线计算,得出网页的PageR ank 值,并进行排序,以发现网络中最主要的页面.
(2)H IT S 算法:该算法将网页分为锚页(H ub )和权威页(A uthority ),并通过这两种页面相互增强,进行迭代,以最终
的权威页值为依据对结果进行排序.
上述两类算法各有优缺点,其中的PageR ank 算法因为是著名商用搜索引擎Google 的核心算法而备受瞩目.但深入地研究表明,PageR ank 算法也存在一些明显的缺陷,许多学者又提出了一些改进算法[1].比如,PageR ank 算法偏重旧网页,即越旧的网页越靠前.因此,宋聚平[3],戚华春[4]等分别提出了具有时间反馈的改进算法.又比如,PageR ank 算法存在主题漂移(Top ic 2drift )问题.因为PageR ank 算法仅仅对网页的链接结构进行分析,无法区分网页中的超链接与该网页的主题是否相关,这样就容易导致在最后的推荐结果中出现大量与查询主题无关但却又具有很高PageR ank 值的无效网页,即所谓的主题漂移(Top ic 2drift )现象.针对PageR ank 算法存在的这个问题,一些学者也提出了相应的改进算法.其中斯坦福大学的T aher H aveli w ala [5]提出了一种主题敏感(Top ic 2sensitive )的PageR ank 改进算法(简称TH 2PageR ank
小型微型计算机系统Journal of Ch inese Computer Syste m s 2007年3月第3期V ol 128N o .32007
算法),华盛顿大学的M atthe w R ichards on 和Pedro
Dom inggos [6]提出了一个结合链接分析和文本内容的PageR ank 改进算法(简称M P 2PageR ank 算法).这两种算法都需要利用查询主题以外的信息来提高对网页的辨识能力,以减少主题漂移现象的发生.但仍然存在一些缺陷,比如,
TH 2PageR ank 算法由于需要利用查询q 的上下文才能有效
地进行主题分类判断,而在缺少上下文时,算法就很难抑制主
题漂移现象的发生.而M P 2PageR ank 算法,不仅需要文本内容支撑,且时间复杂性和空间复杂性都比PageR ank 算法扩大了N 倍(N 为搜索引擎涵盖的网页数),这对于涉及数以亿计网页的互连网络,M P 2PageR ank 算法对空间和时间的需求都难于满足实际应用的需要.因此,本文在对网络链接结构进行进一步分析的基础上,提出了基于虚拟文档的主题相似度模型和一个基于主题相似度模型的PageR ank 算法框架(简称T S 2PageR ank 算法).只要选择不同的相似度计算模型,我们就可以得到各种不同的T S 2PageR ank 算法,形成一个算法簇.理论分析和数值仿真实验表明,该算法在不需要额外文本信息,也不增加算法时空复杂度的情况下,就能极大地减少主题漂移现象.
2 已有改进算法及问题分析
2.1 TH -PageRank 算法
众所周知,有些页面在某些领域被认为是重要的,而在其它领域却可能是次要的,甚至是不重要的.所以,TH 2PageR ank 算法首先根据Open D irectory P roject (OD P )[7]提出的16个基本分类标准对网页进行分类,并针对每个网页的OD P 分类,给出一个主题敏感值A ,然后把这个主题敏感值A 引入算法,离线计算出网页在OD P 分类下的P ag eR ank 值.这样,每个网页根据不同的OD P 分类都对应存在一个
P ag eR ank 值
.算法的形式化表示如下:PR j (p )=(12Α)×A j +Α×∑n
i =1
PR j (T i )
C (T i )
(j =1,2,…,16)(1)公式(1)中的p 为当前网页,PR j (p )表示当前网页p 在OD P 分类c j 下的PageR ank 值;T i (i =1,2,…,n )为指向当前网页p 的其他网页;Α为衰减系数且Α∈(0,1),一般取Α=0.85;C (T i )为网页T i 的链出链接数.主题敏感值A j =1 F j ,F j 是当前网页p 在某个OD P 分类c j 的链出网页集合.在用户查询时,算法可以根据用户的输入及查询的上下文,利用下面的计算公式(2)计算出每个网页p 最终的
PageR ank 值,并返回推荐结果.
PR (p )=∑16
j =1
q j ?PR j (p )
(2)
公式(2)中的q j 是当前查询p 属于OD P 分类c j 的可能性大小.
该算法在知道查询p 的上下文时,可以有效地避免一些明显的主题漂移现象,比如在查询“美洲虎”时,如果有上下文的指引,算法可以明确的区分用户现在查询的是美洲虎汽车,或者是美洲虎橄榄球队,或者是美洲虎产品,或者是哺乳动物美洲虎这些主题中的某个主题.
2.2 M P -PageRank 算法
M atthe w R ichards on 等考虑到用户从一个网页跳到另一
个网页是受到当前网页内容和当前主题影响的.所以,他们把这种影响引入PageR ank 算法而得到M P 2PageR ank ,其计算形式为:
PR q (j )=(12Α
)p ’q (j )+Α∑i ∈B
j
PR q (i )h q (i ,j )(3)
这里h q (i ,j )指在查询主题q 下从网页i 跳转到j 的可能性.p ’
q
(j )表示在网页中没有链出链接时,跳转到j 的可能性.而PR q (j )就是在查询q 下的网页j 的PageR ank 值.对于h q
(i ,j )和p ’
q (j ),M atthe w 采用一个查询q 和网页j 的相关函数R q (j )分别计算:
p ’
q (j )=R q (j )∑k ∈W
R q (k ) h q (i ,j )=
R q (j )∑k ∈F i
R q (k )
其中,W 是整个网络的网页集合,F i 是网页i 的链出网
页集合.相关函数R q (j )原则上可以是任意的,但一般取在网页j 的文本中查询q 的关键字出现的次数.2.3 问题分析
从上面介绍的两个算法可知,它们都通过利用上下文或网页的文本信息来提高对网页的辨识能力,并减少主题漂移现象的发生.然而,以上算法也存在对额外信息—上下文或网页文本信息的严重依赖性.比如,TH 2PageR ank 算法需要利用查询p 的上下文才能有效地进行主题分类判断,在缺少上下文的时候,算法默认把查询p 本身当成上下文,这就很难确定查询p 的具体分类,此时算法就无法抑制主题漂移现象的发生.况且有的时候,用户也很难对自己需要查询的主题提供有效的上下文描述.所以,TH 2PageR ank 算法很难用于实际系统.对于M P 2PageR ank 算法,由文献[6]知,若PageR ank 算法的空间需求是S ,则M P 2PageR ank 算法的空间需求是N ?S ;若PageR ank 算法的计算时间需求是O (S ),则M P 2PageR ank 算法的时间需求为N ?O (S ),其中N 为搜索引擎涵盖的网页数.由于互联网上的网页数以亿计,因此M P 2PageR ank 算法对空间和时间的需求都难于满足合实际应用的需要.
3 TS -PageRank 算法
我们知道,PageR ank 算法的形式化描述为:
PR (p )=(12Α)+Α×∑n
i =1PR (T i )
C (T i
)
(4)在公式(4)中,PR (p )表示当前网页p 的PageR ank 值,T i
(i =1,2,…,n )为指向网页p 的其他网页;Α为衰减系数且Α∈(0,1),C (T i )为网页T i 的链出链接数.注意到公式(4)在计算PR (p )时依赖于其链出网页T i 的PR (T i )值.因此,在实际计算的时候,先给每个网页一个初始的PageR ank 值,比如1,然后通过简单的迭代算法计算出每个网页p 的PR (p )值.
通过对公式(4)进行考察和分析可以发现,出现主题漂移现象的主要原因是:PageR ank 算法在传递网页的PageR ank 值时,采用了平均传递的策略,使得主题不相关的网页获得了本不该得到的PageR ank 值,导致PageR ank 值的分布出现偏
1
153期 黄德才等:基于主题相似度模型的T S 2PageR ank 算法
差.因此,新算法T S 2PageR ank 的核心思想为:根据链接到网页的主题相关性的高低来传递PageR ank 值,而不采用平均传递策略.为了算法不增加额外信息需求而直接通过网页间的链接关系来得到网页间的主题相关性,本文利用虚拟文档向量[8]来表示一个网页,并通过两个网页的虚拟文档向量的余弦相似度来描述它们的主题相关性.然后,把这个相关性引入T S 2PageR ank 算法,以此实现针对链接到的网页主题相关性的高低来传递PageR ank 值.3.1 虚拟文档向量模型
网页的链入链接是网络上的其它人对该网页的认可,所以一般的虚拟文档向量模型采用网页的链入链接来代表网页的主题特征,是一个N 维向量.但由于该虚拟文档向量仅仅体现了其它人对该网页的认可,也是存在偏差的.
受到J .K leinberg [9]提出的H IT S (H yperlink 2Induced Top ic Search )算法的启发,好的锚页指向许多好的权威页;同时,好的权威页是由许多好的锚页指向的.本文考虑到网页链出链接是网页作者对该网页主题的理解,这些链出的链接必定指向那些作者认为与自己主题相关的网页,所以可以把网页链出链接作为一个简单的锚页来看.因此,本文将传统的虚拟文档向量推广成2N 维向量,该向量混合了网页的链入链接和链出链接,体现了网络上其他人对该网页的认可及作者对该网页主题理解,其具体描述如下:
先对搜索引擎所涵盖的网页进行编号:1,2,…,N .对于任意网页p ,在向量V 的前N 维中,第i 个分量为1当且仅当有网页i 指向网页p ,否则为0;在向量V 的后N 维中,第N +i 个分量为1当且仅当有网页p 指向网页i ,否则为0.这里假设网页i 有指向自身的链接时,该向量的分量i 为0.3.2 TS -PageRank 算法描述
由于每个网页所链接到的网页数目和被链接到的数目毕竟是有限的,所以我们在实际生成虚拟文档向量时,采用这样的表示方法:令v p =[i 1,i 2,…,i k ,o 1,o 2,…,o m ],其中i 1,i 2,…,i k 是网页p 的实际链入网页的编号;o 1,o 2,…,o m 是网页p 的实际链出网页的编号,这样虽然增加了一定的计算量,但可以大大减少算法的空间复杂性.
余弦相似度(Cosine Si m ilarity )是传统文件分类中最常被用来度量文件间距离的基本方法,本文利用余弦相似度来计算两个网页的主题相关性.假设有网页p 和q ,它们的虚拟文档向量为v p 和v q ,则它们的主题相关性表示式为:
si m (v p ,v q )=
v p ?v q
v p ‖v q
我们将这个si m (v p ,v q )称为虚拟文档相似度模型.显然,
si m (v p ,v q )是介于0
～1之间的实数,且越接近1,两个网页p ,q 的主题越相关;反之亦然
.这样,我们可将PageR ank 算法(4)修正为:
PR (p )=(12Α)+Α×∑k i =1
PR (T i
)×si m (v p ,v T i )∑m
j =1
si m (v T i ,v j )
(5)公式(5)中的PR (p )表示当前网页p 的PageR ank 值;T i
(i =1,2,3,…,k )表示所有指向p 的网页;j =(1,2,3,…,m )表示网页T i 的链出网页.
对于公式(5)的一个特别情形,即∑m
j =1
si m (v T i ,v j )=0时,
表示网页T i 和它的所有链出网页间都没有任何相关性.此时,为防止PageR ank 值不可计算,我们可以令∑m
j =1si m (v T i ,v j )
=
1N
,N 是搜索引擎涵盖的网页数.
同公式(4)一样,公式(5)在计算PR (p )时依赖于其链出网页T i 的PR (T i )值.因此,在实际计算时,若我们令
s ij =
si m (i ,j )∑m
k =1
si m (j ,k ) (i ,j =1,2,…,N )
可得到矩阵S =(s ij ),则只要给出所有网页的PageR ank 值初始向量PR 0,网页的PageR ank 值向量就可以由以下迭代公式计算:
PR m +1=Α
?S ×PR m +(12Α) m =1,2,3,…由于‖S ‖1=1,因此这个迭代过程是收敛的.
注意到公式(5)包含的si m (v p ,v q )是两个网页p ,q 的主题相似度,且没有对si m (v p ,v q )的计算公式有任何的限制.因此,公式(5)本质上是一个基于主题相似度模型的PageR ank 算法框架.只要给出不同的主题相似度模型公式si m (v p ,v q ),我们就可以得到不同的基于主题相似度的一个T S 2PageR ank 算法簇.比如,我们将[1]中应用于H IT S 算法的基于关联规则的相似度模型应到公式(5)中,就得到一个基于泛主题相似度的T S 2PageR ank 算法.
为方便第4节的实验比较分析,下面简单介绍一下[1]中应用于H IT S 算法的基于关联规则的相似度模型(简称泛主题相似度).该模型把寻找网页间具有共同引用的问题看作是在关联规则挖掘中的频繁项集(frequent ite m set )的生成过程.其中,把基础集合中的所有网页看作一个项目集合(ite m set )),一个网页的所有链入链接或链出链接看作一个事务,使用关联规则发现算法而得到的频繁项集则对应于那些有共同链出或链入的网页集合.
对于给定的某个频繁项集I ,其关联规则度量的相似度定义为:
Ε(I )=
∑k
t =1
Λt K
(6)
其中,Λt 为频繁项集I 中第t 个关联规则的置信度,k 为频繁
项集I 中包含的基本关联规则数.
由于计算得到的频繁项集不是唯一的,因此,将所有包含此网页对的关联规则置信度之和作为该网页间的相似度度量值,可形式化表示为:
si m (i ,j )=∑(I i ,j ∈I )Ε(I )
(7)
4 实验验证分析
为验证算法的正确性和有效性,本文建立了一个实验系统,专门对新浪网站的娱乐版块进行了网页爬取.由于该娱乐版块集中了目前的娱乐新闻及娱乐明星的介绍,这些明星新闻和明星人物互相联系、形成网络,能够较好的模拟互联网的
215 小 型 微 型 计 算 机 系 统 2007年
网络结构.
本文任意选取一个主题,为便于介绍和比较搜索结果,我们先选择“刘德华”为查询主题,并采用类似于文献[6]中的用户满意度分类方法,即对于查询得到的网页,如果其主题是用户最需要的主题,则该网页的满意度为2;如果其主题是用户需要的相关主题,则该网页的满意度为1;如果该网页的主题偏离了查询主题,则该网页的满意度为0.为客观起见,实验系统首先在包含10万多张网页的超链接数据库中获得全部有关“刘德华”这个主题的网页,然后按照上述方法确定每个网页的主题满意值.由于本实验系统选择的新浪网娱乐版块的网页是由人工分类形成的,并且查询的关键字含义简单,所以按以上的用户满意度定义方法得出的每个网页的主题满意程度值是可以信赖的
.
接着,分别用PageR ank 算法和本文提出的分别采用泛主题相似度模型和虚拟文档相似度模型的T S 2P ag eR ank 算法进行计算,获得各自的PageR ank 值分布,然后用关键字查询获得推荐结果并进行比较.其搜索结果的比较见图12图3.
图1 用户满意度为0的网页分布图F ig .
1 T he num bers of user needless pages
图1是用户满意度为0的网页分布情况,图2是符合要求的网页分布情况(包括满意度为1和2的网页);图3是满
图2 符合用户查询要求的网页分布F ig .2 T he num ber of user need pages
意度为2的网页分布情况.图中的“系列1”代表的是采用虚拟文档相似度模型的T S
2PageR ank 算法的搜索结果,“系列2”是采用泛主题相似度模型的T S 2PageR ank 算法的搜索结果,“系列3”则是PageR ank 算法的搜索结果.横坐标表示搜
索算法返回的PageR ank 值排在前面的n 张网页,纵坐标表示在这n 张网页中符合要求的网页数目.
图3 用户满意度为2的网页分布
F ig .3 T he num ber of s pecial pages of user need 根据北京大学的网络与分布式系统研究室对北大天网系统的研究发现[10]:用户一般对搜索引擎推荐结果的前面5页表达出浓厚的兴趣,其中用户在第1页的点击数占总点击数的47%,在前面5页的点击数占到了总点击数的75%以上(表1).
表1 点击前5页的用户比例
T able 1 P ropoti on of user clicked the first 5pages 页号
12345用户翻页的比例(%)
47.0
12.1
7.4
5.0
3.7
这表明用户很少浏览排名靠后的内容,一般就看前面几页的内容而已.所以,搜索算法应该使那些与用户查询主题相关的网页尽量排在前面,而T S 2PageR ank 算法就实现了这个目标.这也是我们在实验结果比较中将查询结果集的最大值选定为100的原因.
由图1和图2可见,以本文提出的T S 2PageR ank 算法为网页排序算法得到的查询结果用户满意度比PageR ank 算法好得多,因为它比PageR ank 算法获得了更多的有效网页,就更好地满足了用户的查询需求.
由图2中可以发现,采用2种不同相似度的T S 2PageR ank 算法虽然返回的符合用户查询要求的网页数量都达到80%以上,且相差不大,但从其图3可以发现,真正令用户满意的网页分布情况却不一样.明显的,采用虚拟文档相似度模型的T S 2PageR ank 算法比采用泛主题相似度模型的T S 2PageR ank 算法效果好.同时,采用虚拟文档相似度模型的T S 2PageR ank 算法也没有显著增加算法的时间复杂度.所以,
采用虚拟文档相似度模型的T S 2PageR ank 算法有较好的搜
索效果.
此外,实验系统还对其它主题作过类似的测试,获得的结果大致相同.
5 结 论
我们知道,一个好的网页排序算法应该使那些与用户查
3
153期 黄德才等:基于主题相似度模型的T S 2PageR ank 算法
询主题密切相关的网页尽量排在前面,而经典的PageR ank 算法则存在主题漂移现象,致使大量与用户查询主题无关的网页排在了查询结果的前面.在分析PageR ank算法及其有关改进算法的基础上,本文提出的基于主题相似度的T S2 PageR ank算法框架,可以通过选择不同的相似度计算模型而得到各种不同的T S2PageR ank算法,从而形成一个算法簇.数值仿真实验还表明,该算法在不需要额外文本信息,也不增加算法时空复杂度的情况下,就能极大地减少主题漂移现象,并使用户满意的有效网页能更多地排在搜索结果集的靠前位置,易于用户获得所需要的信息,从而提高查询质量.
References:
[1]W ang X iao2yu,Zhou A o2ying.L inkage analysis for the world w ide
w eb and its app licati on:a survey[J].Journal of Softw are,2003,14
(10):176821780.
[2]Page L,B rin S,M otw ani R,etal.The pagerank citati on ranking:
bringing order to the W EB[EB OL].January1998,http: https://www.doczj.com/doc/d117712447.html, ～backub PageRanksub.p s.
[3]Song Ju2p ing,W ang Yong2cheng,Yin Zhong2hang.I mp roved
pageRank algorithm for ordering w eb pages[J].Journal of
Shanghai J iaotong U niversity,2003,37(3):3972400.
[4]Q i H ua2chun,H uang D e2cai,Zheng Yue2feng.A n i m p roved
pageRank algorithm w ith ti m e feedbacking[J].Journal of
Zhejiang U niversity of Technol ogy,2005,33(3):2722275.
[5]Taher H.H aveli w ala.Top ic2sensitive pageRank[C].P roceedings of
the11th Internati onal Conference on W orld W ide W EB,
Honolulu,H a w aii,A C M P ress,2002.[6]R ichards on M,Dom ingos P.The intelligent surfer:p robabilistic
com binati on of link and content infor m ati on in PageRank[J].
A dvances in N eural Infor m ati on P rocessing Syste m s,2002,14,
144121448.
[7]The open directory p roject:W eb directory for over2.5m illi on urls
[EB OL].http: https://www.doczj.com/doc/d117712447.html,
[8]E ric J Gl over,Kostas T si outsi ouliklis,Steve L a w rence,etal.U sing
w eb structure for classifying and describing w eb pages[C].
P roceedings of the11th internati onal conference on W orld W ide W eb,Honolulu,H a w aii,A C M P ress,2002.
[9]Kleinberg J.A uthoritative s ources in a hyperlinked environm ent
[C].P roceedings of the9th A C M2S I AM Symposium on D iscrete
A lgorithm s.N e w O rleans:A C M P ress,1997.
[10]W ang J ian2yong,Shan Song2w ei,L ei M ing,etal.W eb search
engine:characteristics of user behavi ors and their i m p licati on[J].
Science in China(Series E),2001,31(4):3722384.
附中文参考文献:
[1]王晓宇,周傲英.万维网的链接结构分析及其应用综述[J].北
京:软件学报,2003,14(10):176821780.
[3]宋聚平,王永成,尹中航,等.对网页PageRank算法的改进[J].
上海:交通大学学报,2003,37(3):3972400.
[4]戚华春,黄德才,郑月锋.具有时间反馈的PageRank改进算法
[J].浙江工业大学学报,2005,33(3):2722275.
[10]王建勇,单松巍,雷 鸣,等.海量w eb搜索引擎系统中用户行为
的分布特征及其启示[J].中国科学(E辑),2001,31(4):3722 384.
415 小 型 微 型 计 算 机 系 统 2007年
图像相似度计算主要用于对于两幅图像之间内容的相似程度进行打分，根据分数的高低来判断图像内容的相近程度。 可以用于计算机视觉中的检测跟踪中目标位置的获取，根据已有模板在图像中找到一个与之最接近的区域。然后一直跟着。已有的一些算法比如BlobTracking，Meanshift，Camshift，粒子滤波等等也都是需要这方面的理论去支撑。 还有一方面就是基于图像内容的图像检索，也就是通常说的以图检图。比如给你某一个人在海量的图像数据库中罗列出与之最匹配的一些图像，当然这项技术可能也会这样做，将图像抽象为几个特征值，比如Trace变换，图像哈希或者Sift特征向量等等，来根据数据库中存得这些特征匹配再返回相应的图像来提高效率。 下面就一些自己看到过的算法进行一些算法原理和效果上的介绍。 (1)直方图匹配。 比如有图像A和图像B，分别计算两幅图像的直方图，HistA，HistB，然后计算两个直方图的归一化相关系数（巴氏距离，直方图相交距离）等等。 这种思想是基于简单的数学上的向量之间的差异来进行图像相似程度的度量，这种方法是目前用的比较多的一种方法，第一，直方图能够很好的归一化，比如通常的256个bin条的。那么两幅分辨率不同的图像可以直接通过计算直方图来计算相似度很方便。而且计算量比较小。 这种方法的缺点: 1、直方图反映的是图像像素灰度值的概率分布，比如灰度值为200的像素有多少个，但是对于这些像素原来的位置在直方图中并没有体现，所以图像的骨架，也就是图像内部到底存在什么样的物体，形状是什么，每一块的灰度分布式什么样的这些在直方图信息中是被省略掉得。那么造成的一个问题就是，比如一个上黑下白的图像和上白下黑的图像其直方图分布是一模一样的，其相似度为100%。 2、两幅图像之间的距离度量，采用的是巴氏距离或者归一化相关系数，这种用分析数学向量的方法去分析图像本身就是一个很不好的办法。 3、就信息量的道理来说，采用一个数值来判断两幅图像的相似程度本身就是一个信息压缩的过程，那么两个256个元素的向量（假定直方图有256个bin条）的距离用一个数值表示那么肯定就会存在不准确性。 下面是一个基于直方图距离的图像相似度计算的Matlab Demo和实验结果. %计算图像直方图距离 %巴氏系数计算法 M=imread('1.jpg'); N=imread('2.jpg'); I=rgb2gray(M); J=rgb2gray(N); [Count1,x]=imhist(I); [Count2,x]=imhist(J); Sum1=sum(Count1);Sum2=sum(Count2); Sumup = sqrt(Count1.*Count2); SumDown = sqrt(Sum1*Sum2); Sumup = sum(Sumup); figure(1); subplot(2,2,1);imshow(I); subplot(2,2,2);imshow(J);
龙源期刊网 https://www.doczj.com/doc/d117712447.html, 相似度算法在源程序比较中的应用 作者：朱利龙 来源：《电脑知识与技术》2016年第21期 摘要：在计算机程序课的教学过程中，时常需要对学生所提交的源程序进行检查，特别是源程序的重复率检查。纯人工对比不但花费时间长，而且效率低下。因此，本文提出利用文本相似度算法解决源程序对比的方法，并设计出相应的源程序比较系统，来帮助老师从繁重的工作中解脱出来。 关键词：相似度；距离编辑算法；源程序对比 中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）21-0214-01 源程序对比分析是一个复杂的过程，不仅需要考虑实用性和考虑准确性，而且还要兼顾运行效率等问题。在程序上机课的过程性考核中，很多同学提交的程序源代码之间重复率很高。本文借助计算机实现源程序的自动对比，不但可以降低劳动强度，提高工作效率，而且可以减少误判的可能性，进一步保证源程序对比结果的正确性。 1 特征提取 要获取源程序重复率，判断是否抄袭程度，可以通过计算源程序的相似率来代替。相似率越高说明源程序重复部分越多，学生抄袭的可能性越高。要计算代码的相似率，就得提取源代码的有关特征参数。 根据源程序块粒度大小不同，可以利用源程序中诸如换行符之类的分割符来分解成程序语句，分解得到的每一部分称为一个程序块。源程序块的选择将在很大程度上影响程序的效率，要比较源程序部分复制，就必须减少源程序块的长度。本文将每一个语句看成一个源程序块，即粒度大小为一条语句。于是，源程序就被分解为语句集合，源程序的相似程度便可以由语句的相似率来计算。因此，对于源程序的对比，选择程序语句作为源程序的对比粒度块是具有可行性的。 本文系统采用的是距离编辑算法，利用字符串的模式匹配实现对源程序相似度进行判断。把两篇源程序进行全文对比得出相似度；得出相似度后，根据源程序分隔符把两源程序分割成逐条语句的，然后对这些语句进行一一对比，得出语句的相似度；比较出来的超过语句的相似度的语句称为相似句，把相似句对应的原句进行红色标记；统计出相似句对应原句占原源程序的比例，在比较中可以通过红色显示相同。 2 距离编辑算法
重要值的计算方法 以综合数值表示植物物种在群落中的相对重要值。 重要值=相对多度+相对频度+相对显著度 或，重要值=（相对多度+相对频度+相对显著度)/3 补充： 针对乔木而言：重要值=（相对密度【即相对多度】+相对频度+相对显著度【即相对优势度】）/3 针对灌草而言：重要值=（相对密度【即相对多度】+相对频度+相对盖度【即相对优势度】）/3 注： 频度：是指一个种在所作的全部样方中出现的频率.相对频度指某种在全部样方中的频度与所有种频度和之比。 相对频度=(该种的频度/所有种的频度总和)×100% 显著度【优势度】：指样方内某种植物的胸高断面积除以样地面积。 相对显著度【相对优势度】=(样方中该种个体胸面积和/样方中全部个体胸面积总和)×100% 密度（D）=某样方内某种植物的个体数/样方面积 相对密度（RD）=（某种植物的密度/全部植物的总密度）×100 =（某种植物的个体数/全部植物的个体数）×100 盖度（cover degree，或coverage）指的是植物地上部分垂直投影面积占样地面积的百分比，即投影盖度。后来又出现了“基盖度”的概念，即植物基部的覆盖面积。对于草原群落，常以离地面1英寸（2.54cm）高度的断面计算；对森林群落，则以树木胸高（1.3m处）断面积计算。基盖度也称真盖度。乔木的基盖度特称为显著度（dominant）。盖度可分为种盖度（分盖度）、层盖度（种组盖度）、总盖度（群落盖度）。林业上常用郁闭度来表示林木层的盖度。通常，分盖度或层盖度之和大于总盖度。群落中某一物种的分盖度占所有分盖度之和的百分比，即相对盖度。某一物种的盖度占盖度最大物种的盖度的百分比称为盖度比（cover ratio）。
一、计算过程： 1、根据输入一个地址，生成一个地址每个字的数组： T1={w1,w2,w3..wn}; 比如：有两个地址广东省梅州市江南彬芳大道金利来步街xx号和广东省梅州市梅江区彬芳大道金利来步行街xx号，会生成 T1={广,东,省,梅,州,市,江,南,彬,芳,大,道,金,利,来,步,街,xx,号}; T2={广,东,省,梅,州,市,梅,江,区,彬,芳,大,道,金,利,来,步,行,街,xx,号}; 2、这两个地址的并集，对出现多次的字只保留一次 比如：T={广,东,省,州,市,梅,江,南,区,彬,芳,大,道,金,利,来,步,行,街,xx,号}; 3、求出每个t中每个词在t1和t2中出现的次数得到m和n m={m1,m2,m3..mn}; n={n1,n2,n3.nn}; 比如:t1和t2可以得到两个出现次数的数组 m={1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1}; n={1,1,1,1,1,2,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1}; 4、计算相似度 Sim=m1*n1+m2*n2+..mn*nn/sqrt(m1*m1+m2*m2+..mn*mn)* sqrt(n1*n1+n2*n2+..nn*nn) 二、计算原理： 假如这两个数组是只有｛x1,y1｝和{x2,y2}的数组，这两个数组可以在平面直角坐标系中用两个由原点出发的向量来表示，我们可以通过向量的夹角的大小来判断向量的相似度，夹角越小，相似度越高。计算向量的夹角，我们可以使用余弦定理，余弦定理用坐标表示的公式： 余弦的这种计算方法不止对于2维向量成立，对n维向量也成立，n维向量表示为： 所以我们可以使用这个公式得出余弦的值，值越接近1，夹角越小，两个向量越相似，这种计算方式叫做余弦相似性。
图像相似度计算 图像相似度计算主要用于对于两幅图像之间内容的相似程度进行打分，根据分数的高低来判断图像内容的相近程度。 可以用于计算机视觉中的检测跟踪中目标位置的获取，根据已有模板在图像中找到一个与之最接近的区域。然后一直跟着。已有的一些算法比如BlobTracking，Meanshift，Camshift，粒子滤波等等也都是需要这方面的理论去支撑。 还有一方面就是基于图像内容的图像检索，也就是通常说的以图检图。比如给你某一个人在海量的图像数据库中罗列出与之最匹配的一些图像，当然这项技术可能也会这样做，将图像抽象为几个特征值，比如Trace变换，图像哈希或者Sift特征向量等等，来根据数据库中存得这些特征匹配再返回相应的图像来提高效率。 下面就一些自己看到过的算法进行一些算法原理和效果上的介绍。 (1)直方图匹配。 比如有图像A和图像B，分别计算两幅图像的直方图，HistA，HistB，然后计算两个直方图的归一化相关系数（巴氏距离，直方图相交距离）等等。 这种思想是基于简单的数学上的向量之间的差异来进行图像相似程度的度量，这种方法是目前用的比较多的一种方法，第一，直方图能够很好的归一化，比如通常的256个bin条的。那么两幅分辨率不同的图像可以直接通过计算直方图来计算相似度很方便。而且计算量比较小。 这种方法的缺点: 1、直方图反映的是图像像素灰度值的概率分布，比如灰度值为200的像素有多少个，但是对于这些像素原来的位置在直方图中并没有体现，所以图像的骨架，也就是图像内部到底存在什么样的物体，形状是什么，每一块的灰度分布式什么样的这些在直方图信息中是被省略掉得。那么造成的一个问题就是，比如一个上黑下白的图像和上白下黑的图像其直方图分布是一模一样的，其相似度为100%。 2、两幅图像之间的距离度量，采用的是巴氏距离或者归一化相关系数，这种用分析数学向量的方法去分析图像本身就是一个很不好的办法。 3、就信息量的道理来说，采用一个数值来判断两幅图像的相似程度本身就是一个信息压缩的过程，那么两个256个元素的向量（假定直方图有256个bin条）的距离用一个数值表示那么肯定就会存在不准确性。 下面是一个基于直方图距离的图像相似度计算的Matlab Demo和实验结果.
计算文本相似度几种最常用的方法，并比较它们之间的性能 编者按：本文作者为Yves Peirsman，是NLP领域的专家。在这篇博文中，作者比较了各种计算句子相似度的方法，并了解它们是如何操作的。词嵌入（word embeddings）已经在自然语言处理领域广泛使用，它可以让我们轻易地计算两个词语之间的语义相似性，或者找出与目标词语最相似的词语。然而，人们关注更多的是两个句子或者短文之间的相似度。如果你对代码感兴趣，文中附有讲解细节的Jupyter Notebook地址。以下是论智的编译。 许多NLP应用需要计算两段短文之间的相似性。例如，搜索引擎需要建模，估计一份文本与提问问题之间的关联度，其中涉及到的并不只是看文字是否有重叠。与之相似的，类似Quora之类的问答网站也有这项需求，他们需要判断某一问题是否之前已出现过。要判断这类的文本相似性，首先要对两个短文本进行embedding，然后计算二者之间的余弦相似度（cosine similarity）。尽管word2vec和GloVe等词嵌入已经成为寻找单词间语义相似度的标准方法，但是对于句子嵌入应如何被计算仍存在不同的声音。接下来，我们将回顾一下几种最常用的方法，并比较它们之间的性能。 数据 我们将在两个被广泛使用的数据集上测试所有相似度计算方法，同时还与人类的判断作对比。两个数据集分别是： STS基准收集了2012年至2017年国际语义评测SemEval中所有的英语数据 SICK数据库包含了10000对英语句子，其中的标签说明了它们之间的语义关联和逻辑关系 下面的表格是STS数据集中的几个例子。可以看到，两句话之间的语义关系通常非常微小。例如第四个例子： A man is playing a harp. A man is playing a keyboard.
1.信息检索中的重要发明TF-IDF 1.1TF Term frequency即关键词词频，是指一篇文章中关键词出现的频率，比如在一篇M个词的文章中有N个该关键词，则 （公式1.1-1） 为该关键词在这篇文章中的词频。 1.2IDF Inverse document frequency指逆向文本频率，是用于衡量关键词权重的指数，由公式 （公式1.2-1） 计算而得，其中D为文章总数，Dw为关键词出现过的文章数。2.基于空间向量的余弦算法 2.1算法步骤 预处理→文本特征项选择→加权→生成向量空间模型后计算余弦。 2.2步骤简介 2.2.1预处理 预处理主要是进行中文分词和去停用词，分词的开源代码有：ICTCLAS。 然后按照停用词表中的词语将语料中对文本内容识别意义不大但出
现频率很高的词、符号、标点及乱码等去掉。如“这，的，和，会，为”等词几乎出现在任何一篇中文文本中，但是它们对这个文本所表达的意思几乎没有任何贡献。使用停用词列表来剔除停用词的过程很简单，就是一个查询过程：对每一个词条，看其是否位于停用词列表中，如果是则将其从词条串中删除。 图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. 欧氏距离(Euclidean Distance) 欧氏距离是最易于理解的一种距离计算方法，源自欧氏空间中两点间的距离公式。 (1)二维平面上两点a(x1,y1)与b(x2,y2)间的欧氏距离： (2)三维空间两点a(x1,y1,z1)与b(x2,y2,z2)间的欧氏距离： (3)两个n维向量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的欧氏距离： 也可以用表示成向量运算的形式： (4)Matlab计算欧氏距离 Matlab计算距离主要使用pdist函数。若X是一个M×N的矩阵，则pdist(X)将X矩阵M行的每一行作为一个N维向量，然后计算这M个向量两两间的距离。例子：计算向量(0,0)、(1,0)、(0,2)两两间的欧式距离 X = [0 0 ; 1 0 ; 0 2] D = pdist(X,'euclidean') 结果： D = 1.0000 2.0000 2.2361 2. 曼哈顿距离(Manhattan Distance) 从名字就可以猜出这种距离的计算方法了。想象你在曼哈顿要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除
非你能穿越大楼。实际驾驶距离就是这个“曼哈顿距离”。而这也是曼哈顿距离名称的来源，曼哈顿距离也称为城市街区距离(City Block distance)。 (1)二维平面两点a(x1,y1)与b(x2,y2)间的曼哈顿距离 (2)两个n维向量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的曼哈顿距离 (3) Matlab计算曼哈顿距离 例子：计算向量(0,0)、(1,0)、(0,2)两两间的曼哈顿距离 X = [0 0 ; 1 0 ; 0 2] D = pdist(X, 'cityblock') 结果： D = 1 2 3 5. 标准化欧氏距离 (Standardized Euclidean distance ) (1)标准欧氏距离的定义 标准化欧氏距离是针对简单欧氏距离的缺点而作的一种改进方案。标准欧氏距离的思路：既然数据各维分量的分布不一样，好吧！那我先将各个分量都“标准化”到均值、方差相等吧。均值和方差标准化到多少呢？这里先复习点统计学知识吧，假设样本集X的均值(mean)为m，标准差(standard deviation)为s，那么X的“标准化变量”表示为： 而且标准化变量的数学期望为0，方差为1。因此样本集的标准化过程(standardization)用公式描述就是： 标准化后的值= ( 标准化前的值－分量的均值) /分量的标准差 经过简单的推导就可以得到两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的标准化欧氏距离的公式： 如果将方差的倒数看成是一个权重，这个公式可以看成是一种加权欧氏距离(Weighted Euclidean distance)。
句子相似度地计算在自然语言处理具有很重要地地位,如基于实例地机器翻译( )、自 动问答技术、句子模糊匹配等.通过对术语之间地语义相似度计算,能够为术语语义识别[]、术语聚类[]、文本聚类[]、本体自动匹配[]等多项任务地开展提供重要支持.在已有地术语相似度计算方法中,基于搜索引擎地术语相似度算法以其计算简便、计算性能较高、不受特定领域语料库规模和质量制约等优点而越来越受到重视[]. 相似度计算方法总述： 《向量空间模型信息检索技术讨论》，刘斌，陈桦发表于计算机学报， 相似度()：指两个文档内容相关程度地大小，当文档以向量来表示时，可以使用向量文 档向量间地距离来衡量，一般使用内积或夹角地余弦来计算，两者夹角越小说明似度 越高.由于查询也可以在同一空间里表示为一个查询向量(见图)，可以通过相似度计算 公式计算出每个档向量与查询向量地相似度，排序这个结果后与设立地阈值进行比较. 如果大于阈值则页面与查询相关，保留该页面查询结果；如果小于则不相关，过滤此页.这样就可以控制查询结果地数量，加快查询速度.资料个人收集整理，勿做商业用途 《相似度计算方法综述》 相似度计算用于衡量对象之间地相似程度，在数据挖掘、自然语言处理中是一个基础 性计算.其中地关键技术主要是两个部分，对象地特征表示，特征集合之间地相似关系. 在信息检索、网页判重、推荐系统等，都涉及到对象之间或者对象和对象集合地相似 性地计算.而针对不同地应用场景，受限于数据规模、时空开销等地限制，相似度计算 方法地选择又会有所区别和不同.下面章节会针对不同特点地应用，进行一些常用地相 似度计算方法进行介绍.资料个人收集整理，勿做商业用途 内积表示法： 《基于语义理解地文本相似度算法》，金博，史彦君发表于大连理工大学学报， 在中文信息处理中,文本相似度地计算广泛应用于信息检索、机器翻译、自动问答系统、文本挖掘等领域,是一个非常基础而关键地问题,长期以来一直是人们研究地热点和难点.计算机对于中文地处理相对于对于西文地处理存在更大地难度,集中体现在对文本分词 地处理上.分词是中文文本相似度计算地基础和前提,采用高效地分词算法能够极大地提 高文本相似度计算结果地准确性.本文在对常用地中文分词算法分析比较地基础上,提出 了一种改进地正向最大匹配切分()算法及歧义消除策略,对分词词典地建立方式、分词 步骤及歧义字段地处理提出了新地改进方法,提高了分词地完整性和准确性.随后分析比 较了现有地文本相似度计算方法,利用基于向量空间模型地方法结合前面提出地分词算法,给出了中文文本分词及相似度计算地计算机系统实现过程,并以科技文本为例进行了 测试,对所用方法进行了验证.这一课题地研究及其成果对于中文信息处理中地多种领域 尤其是科技类文本相似度地计算比较,都将具有一定地参考价值和良好地应用前景.资料 个人收集整理，勿做商业用途
词语相似度算法的分析与改进 摘要：对现有的词语相似度算法进行分析，提出一种基于知网，面向语义、可扩展的词语相似度计算方法，通过对实验结果进行分析，所提出的词语语义相似度计算方法比以前的方法更好，在计算词语相似度时，准确率更高。 关键词：词语相似度算法；义原相似度计算；概念词的相似度计算；非概念词的相似度计算 在建立主观题评分模型时，要判断句子的相似度，计算句子的相似度时，首先要处理的就是词语的相似度计算工作。目前对词语的相似度计算人们已经做了大量的研究，提出了一些较有代表性的计算方法。主要包括以下几种： 1）基于字面信息的词语相似度计算 这种算法的核心内容是：中文词语的构成句子中，一般较核心的内容都放在句子的后面。句子后面的词语在句子中所起到的作用比靠前的词语大。因此在对句子进行分析时需要给后面的字或词赋予较高的权值。 假设a和b分别代表两个词语，按照此算法，词语之间的相似度计算公式可以表示为公式1。 使用字面信息作为相似度计算的算法较简单，实现起来也方便。但该算法准确率不高，尤其是对于语义相似的词语更是难于处理。2）基于词林的词语相似度计算 对于以同义词词林作为语义分类体系进行词语相似度计算的研
究，王斌和章成志都曾作了相关探讨[1]。其核心思想是使用两个词语的语义距离来表示词语间相似度。当处理对象是一个词组或短语时，首先将其切分为义类词，并将义类词在词林的树状结构中提取出相关的语义编码，并对两个词语的语义编码进行相似度计算。基于词林的词语相似度计算较好的解决了语义相似、词形不同的词语相似度计算，但由于语义词典的完备性问题，必然会存在部分不在语义词典中的词语而无法处理。 3）基于知网的词语相似度计算 知网以概念作为描述对象，从关系层次上揭示词语的概念含义，并建立了概念关系网络，包含词语属性以及属性间关系[2]。刘群、李素建从知网的关系描述出发，研究了同一个词义所具有的多个义原间的关系，并试图计算出这些义原在计算相似度时所起到的作用，并根据这种思想提出了使用知网的语义信息来计算词语相似度的算法。 该算法在计算概念词的相似度时较准确，但在计算概念词与非概念词，非概念词与非概念词的相似度时，准确率不高。 为克服这些问题，我们采用知网作为语义资源，结合信息论中的相关理论，提出了一种面向语义的、可扩展的、多策略混合的词语相似度计算模型。 1 义原相似度计算 词语的相似度计算，最终还是要计算各词语的义源相似度。在知网中，所有词语都包含义原信息，应用知网进行相似度计算时，第
大规模句子相似度计算方法* 黄河燕1陈肇雄1张孝飞1张克亮1，2 （1中国科学院计算机语言信息工程研究中心北京100083 2 南京理工大学南京210094） Email: heyan.huang@https://www.doczj.com/doc/d117712447.html, xiaofei_ustc@https://www.doczj.com/doc/d117712447.html, 摘要：如何根据源语言文本从大规模语料库中找出其最相近的翻译实例，即句子相似度计算，是基于实例翻译方法的关键问题之一。本文提出一种多层次句子相似度计算方法：首先基于句子的词表层特征和信息熵从大规模语料库中选择出少量候选实例，然后针对这些候选实例进行泛化匹配，从而计算出相似句子。在多策略机器翻译系统IHSMTS中的实验表明，当语料规模为20万英汉句对时，系统提取相似句子的召回率达96%，准确率达90%，充分说明了本文算法的有效性。 关键词：句子相似度；基于实例的机器翻译；多策略机器翻译；泛化匹配 中图法分类号：TP391 Approach of Large-Scale Sentence Similarity Computation HUANG He-yan CHEN Zhao-xiong ZHANG Xiao-fei (Research Center of Computer & Language Information Engineering, CAS Beijing 100083) Email: heyan.huang@https://www.doczj.com/doc/d117712447.html, xiaofei_ustc@https://www.doczj.com/doc/d117712447.html, Abstract: The retrieval of the similar translation examples corresponding to the SL sentence from the large-scale corpora, or the computation of sentence similarity, is one of the key problems of EBMT. A new multi-layer sentence similarity computation approach is proposed in this paper. First, a few candidate translation examples are selected form a large-scale corpus on the basis of the surface features and entropies of the given words. Second, the degree of generalization match between the input sentence and each of those candidate translation examples is computed respectively. Finally, the sentence similarity is computed according to the outcomes of the previous two steps. Experimental results from tests on IHSMTS show that this approach has a recall rate of 96% and a precision rate of 90% when applied to a corpus of 200,000 English-Chinese sentence pairs. Key words: sentence similarity; example-based machine translation; hybrid-strategy machine translation; generalization matching 1 引言 基于实例的机器翻译EBMT（Example-based machine translation）的基本思路是：预先 *基金项目：国家自然科学基金资助项目（60502048，60272088）；国家863计划基金资助项目（2002AA117010-02）。 作者简介：黄河燕（1963-），女，研究员，博士生导师，主要研究方向为自然语言处理与机器翻译、大型智能应用系统；陈肇雄（1961-），男，研究员，博士生导师，主要研究方向为自然语言处理、大型智能应用系统；张孝飞（1970-），男，副研究员，博士，主要研究方向为自然语言处理、机器翻译、信息检索。张克亮（1964-），男，副教授，博士后，主要研究方向为计算语言学、机器翻译。
词语相似度计算方法分析 崔韬世麦范金 桂林理工大学广西 541004 摘要：词语相似度计算是自然语言处理、智能检索、文档聚类、文档分类、自动应答、词义排歧和机器翻译等很多领域的基础研究课题。词语相似度计算在理论研究和实际应用中具有重要意义。本文对词语相似度进行总结，分别阐述了基于大规模语料库的词语相似度计算方法和基于本体的词语相似度计算方法，重点对后者进行详细分析。最后对两类方法进行简单对比，指出各自优缺点。 关键词：词语相似度；语料库；本体 0 引言 词语相似度计算研究的是用什么样的方法来计算或比较两个词语的相似性。词语相似度计算在自然语言处理、智能检索、文本聚类、文本分类、自动应答、词义排歧和机器翻译等领域都有广泛的应用，它是一个基础研究课题，正在为越来越多的研究人员所关注。笔者对词语相似度计算的应用背景、研究成果进行了归纳和总结，包括每种策略的基本思想、依赖的工具和主要的方法等，以供自然语言处理、智能检索、文本聚类、文本分类、数据挖掘、信息提取、自动应答、词义排歧和机器翻译等领域的研究人员参考和应用。词语相似度计算的应用主要有以下几点： (1) 在基于实例的机器翻译中，词语相似度主要用于衡量文本中词语的可替换程度。 (2) 在信息检索中，相似度更多的是反映文本与用户查询在意义上的符合程度。 (3) 在多文档文摘系统中，相似度可以反映出局部主题信息的拟合程度。 (4) 在自动应答系统领域，相似度的计算主要体现在计算用户问句和领域文本内容的相似度上。 (5) 在文本分类研究中，相似度可以反映文本与给定的分类体系中某类别的相关程度。 (6) 相似度计算是文本聚类的基础，通过相似度计算，把文档集合按照文档间的相似度大小分成更小的文本簇。1 基于语料库的词语相似度计算方法 基于统计方法计算词语相似度通常是利用词语的相关性来计算词语的相似度。其理论假设凡是语义相近的词，它们的上下文也应该相似。因此统计的方法对于两个词的相似度算建立在计算它们的相关词向量相似度基础上。首先要选择一组特征词，然后计算这一组特征词与每一个词的相关性(一般用这组词在实际的大规模语料中在该词的上下文中出现的频率来度量)，于是，对于每一个词都可以得到一个相关性的特征词向量，然后计算这些向量之间的相似度，一般用向量夹角余弦的计算结果作为这两个词的相似度。 Lee利用相关熵，Brown采用平均互信息来计算词语之间的相似度。李涓子(1999)利用这种思想来实现语义的自动排歧；鲁松(2001)研究了如何利用词语的相关性来计算词语的相似度。PBrownetc采用平均互信息来计算词语之间的相似度。基于统计的定量分析方法能够对词汇间的语义相似性进行比较精确和有效的度量。基于大规模语料库进行的获取受制于所采用的语料库，难以避免数据稀疏问题，由于汉语的一词多义现象，统计的方法得到的结果中含有的噪声是相当大的，常常会出现明显的错误。 2 基于本体库的词语相似度计算方法 2.1 常用本体库 关于Ontology的定义有许多，目前获得较多认同的是R.Studer的解释：“Ontology是对概念体系的明确的、形式
向量的相似度计算常用方法 相似度的计算简介 关于相似度的计算，现有的几种基本方法都是基于向量（Vector）的，其实也就是计算两个向量的距离，距离越近相似度越大。在推荐的场景中，在用户-物品偏好的二维矩阵中，我们可以将一个用户对所有物品的偏好作为一个向量来计算用户之间的相似度，或者将所有用户对某个物品的偏好作为一个向量来计算物品之间的相似度。下面我们详细介绍几种常用的相似度计算方法。 共8种。每人选择一个。第9题为选做。 编写程序实现（这是第一个小练习，希望大家自己动手，java实现）。计算两个向量的相似性： 向量1（0.15, 0.45, 0.l68, 0.563, 0.2543, 0.3465, 0.6598, 0.5402, 0.002） 向量2（0.81, 0.34, 0.l66, 0.356, 0.283, 0.655, 0.4398, 0.4302, 0.05402） 1、皮尔逊相关系数（Pearson Correlation Coefficient） 皮尔逊相关系数一般用于计算两个定距变量间联系的紧密程度，它的取值在[-1，+1] 之间。 s x , s y 是 x 和 y 的样品标准偏差。 类名：PearsonCorrelationSimilarity 原理：用来反映两个变量线性相关程度的统计量 范围：[-1,1]，绝对值越大，说明相关性越强，负相关对于推荐的意义小。 说明：1、不考虑重叠的数量；2、如果只有一项重叠，无法计算相似性（计算过程被除数有n-1）；3、如果重叠的值都相等，也无法计算相似性（标准差为0，做除数）。
该相似度并不是最好的选择，也不是最坏的选择，只是因为其容易理解，在早期研究中经常被提起。使用Pearson线性相关系数必须假设数据是成对地从正态分布中取得的，并且数据至少在逻辑范畴内必须是等间距的数据。Mahout中，为皮尔森相关计算提供了一个扩展，通过增加一个枚举类型（Weighting）的参数来使得重叠数也成为计算相似度的影响因子。 2、欧几里德距离（Euclid ean Distance） 最初用于计算欧几里德空间中两个点的距离，假设 x，y 是 n 维空间的两个点，它们之间的欧几里德距离是： 可以看出，当 n=2 时，欧几里德距离就是平面上两个点的距离。当用欧几里德距离表示相似度，一般采用以下公式进行转换：距离越小，相似度越大。 类名：EuclideanDistanceSimilarity 原理：利用欧式距离d定义的相似度s，s=1 / (1+d)。 范围：[0,1]，值越大，说明d越小，也就是距离越近，则相似度越大。 说明：同皮尔森相似度一样，该相似度也没有考虑重叠数对结果的影响，同样地，Mahout通过增加一个枚举类型（Weighting）的参数来使得重叠数也成为计算相似度的影响因子。 3、Cosine 相似度（Cosine Similarity） Cosine 相似度被广泛应用于计算文档数据的相似度： 类名： UncenteredCosineSimilarity 原理：多维空间两点与所设定的点形成夹角的余弦值。 范围：[-1,1]，值越大，说明夹角越大，两点相距就越远，相似度就越小。 说明：在数学表达中，如果对两个项的属性进行了数据中心化，计算出来的余弦相似度和皮尔森相似度是一样的，在mahout中，实现了数据中心化的过程，所以皮尔森相似度值也是数据中心化后的余弦相似度。另外在新版本
—52— 协同过滤算法中的相似度优化方法 徐 翔，王煦法 (中国科学技术大学计算机科学与技术系，合肥 230027) 摘 要：在协同过滤推荐系统中，通过对稀疏评分矩阵进行填充，可以提高对用户相似度的度量效果和系统的推荐精度。不同填充方法对相似度计算结果的影响存在较大差异。为解决该问题，针对3类填充方法构建的评分数据集，以最近邻算法进行推荐，分析传统相似度和基于云模型的相似度经2种方法优化后的度量效果，分别为各填充方法选取最有效的相似度优化方案。 关键词：协同过滤；最近邻；相似度；云模型 Optimization Method of Similarity Degree in Collaborative Filter Algorithm XU Xiang, WANG Xu-fa (Department of Computer Science and Technology, University of Science and Technology of China, Hefei 230027) 【Abstract 】In collaborative filter recommendation systems, the performance of user similarity measuring can be improved by filling the sparse marking matrix. Different filling method has different effect on similarity calculation result. To resolve this problem, this paper makes recommendation by using nearest neighbor algorithm on marking sets constructed by three kinds of filling methods separately, analyzes the measure performance optimized by two methods of traditional similarity measures and the similarity based on cloud model, and selects the most effective similarity measure optimization scheme for each filling method. 【Key words 】collaborative filter; nearest neighbor; similarity degree; cloud model 计 算 机 工 程 Computer Engineering 第36卷 第6期 Vol.36 No.6 2010年3月 March 2010 ·软件技术与数据库· 文章编号：1000—3428(2010)06—0052—03 文献标识码：A 中图分类号：TP391 1 概述 协同过滤是用于减少信息过载的常用技术，已成为个性化推荐系统的主要工具。最近邻协同过滤算法[1]是当前最成功的推荐技术之一。但随着推荐系统规模的扩大，用户评分数据出现极端稀疏性，导致该算法的推荐质量降低。 为解决数据稀疏性问题，一些学者提出了新的相似度计算模型，如文献[2]提出基于云模型的相似度计算方法。一些学者则采用对稀疏的用户-项矩阵进行填充的技术来提高相似度度量效果。最简单的填充办法是将用户对未评分项目的评分设为一个固定的缺省值，如设定为用户的平均评分，实验表明该方法可以有效提高协同过滤算法的推荐精度，因此，被许多简单推荐系统采用。另一种填充方法的处理过程如下：(1)采用预测评分的方式先估算出未评分项目的评分，将用 户-项矩阵填充完整；(2)在得到的稠密矩阵上计算用户间的相似度，以最近邻算法进行推荐。例如，文献[3]提出一种基于项目评分预测的协同过滤推荐技术，通过估计用户评分来填充用户-项矩阵，减小数据稀疏性对计算结果的影响。文献[4]通过奇异值分解(Singular Value Decomposition, SVD)算法估计未评分项目的评分，并在稠密矩阵上计算用户间的相关相似度，采用最近邻算法求取实际未评分项目的预测值。 选取合适的相似度方法对提高推荐精度具有重要作用，因此，本文在3类填充后的评分数据集下对现有相似度度量方法进行了优化分析。 2 现有相似度度量方法 本文主要研究4种相似度：余弦相似度[2](Cos)，修正的余弦相似度[2](ACos)，相关相似度[2](Pearson)和基于云模型的相似度(Yun)。前3种相似度是传统相似度度量方法得到的，下文简要介绍基于云模型的相似度。云模型表达的概念的整体特性可以用期望Ex 、熵En 、超熵He 3个特征来表示，记为C (Ex , En , He )，称为云的向量。在云模型中，云由多个云滴组成，每个用户的所有评分集合被视为一朵“云”，每个评分被视为一个“云滴”，可以通过逆向云算法[2]实现每朵云从定量值到云的特征向量的转换，2朵云之间的相似度可以由云的特征向量的夹角余弦来表示。 基于云模型的相似度度量算法描述如下： 输入 用户i 的评分集合P i =(x 1,x 2,…,x N )，用户j 的评分集合P j =(y 1,y 2,…,y M )，其中，N , M 分别为用户i 和用户j 评分过的项目个数。 输出 用户i 和用户j 的相似度YSim (i , j ) (1)计算用户i 的评分矢量的样本均值1 1N i i X x N ==∑，一阶样本绝对中心矩 1 1N i i x X N =?∑和样本方差221 1()1N i i S x X N ==?∑?。Ex i 的估计值为?Ex X =，He i 的估计值为1 1??N i i He x Ex N ==?∑，En i 的估计值为?En =，则用户i 的云向量为i =C (,,)i i i Ex En He ，用户j 的云向量为j =C (,,)j j j Ex En He 。 (2)对任意2个用户i 和j 的相似度可以由C i 和C j 之间的余弦夹角来表示，即 作者简介：徐 翔(1984－)，男，硕士研究生，主研方向：电子商务个性化理论与方法；王煦法，教授、博士生导师 收稿日期：2009-10-25 E-mail ：xuustc@https://www.doczj.com/doc/d117712447.html,
2012.12 52 本体相似度计算方法研究 张路 长江大学工程技术学院 湖北 434020 摘要：MD3模型是一种系统的跨本体概念间相似度的计算方法，这种方法无需建立一个集成的共享本体。本文在MD3 模型的基础上，充分利用本体对概念的描述信息，重点讨论了跨本体概念间非层次关系相似度的计算，把MD3 模型扩展到 EMD3 模型，使得概念间相似度的计算理论上更全面、更精确。 关键词：本体；元数据模型；语义相似度；MD3模型 0 引言 本体映射算法以两个本体作为输入，然后为这两个本体的各个元素(概念、属性或者关系) 建立相应的语义关系。相似性提取是本体映射的一个重要步骤，它主要是进行概念相似度的计算，提高语义相似度计算精度成为提高语义信息检索质量的关键之一。语义相似度一般是指计算本体概念间的相似度，多数方法所考虑的概念是基于一个本体的，跨本体 概念间的方法比较少。MD3模型是一种典型的计算跨本体概念间相似度的方法。 1 MD3模型 Triple Matching-Distance Model(MD3)模型是一种跨本体概念间相似度计算框架。计算实体类a 和b 之间的相似度通过计算同义词集、特征属性和语义邻居之间的加权和，公式如下： Sim(a,b)=wS synsets (a,b)+uS features (a, b)+vS neighborhoods (a,b) 其中w, u, v 表示了各组成部分的重要性。特征属性细化为组成部分、功能以及其他属性。概念a 和b 的语义邻居及其特征属性(即概念的部分、功能及其他属性)也通过同义词集合描述，每一个相似度的计算都通过Tversky 公式： (,)(,)(1(,))A B S a b A B a b A B a b B A αα=+-+-- 其中A, B 分别表示概念a 和b 的描述集合，A-B 表示属于A 但不属于B 的术语集(B-A 相反)。参数(,)a b α由概念a 和b 和在各自层次结构中的深度确定。 2 EMD3模型 MD3模型的不足在于没有考虑对象实例对概念的影响，同 时其语义邻居只考虑语义关系中层次之间的相似度，没有考虑非层次之间的相似度。本文在MD3模型的基础上，参考了其概念名称相似度、特征属性，对本体的结构以及概念描述两方面做了扩充，重点讨论了跨本体概念间非层次关系的相似度的比较和实例对概念相似度的影响，把MD3模型扩展到Extension of Triple Mapping Distance model (EMD3)模型。 2.1 概念属性的相似度 属性有属性名称、属性数据类型、属性实例数据等要素，因此判断两个属性是否相似主要从这三个要素来考虑。属性名称、属性类型本身是文本类型，是字符串，因此可以采用字符串相似度计算方法进行判定。例如用Humming distance 来比较两字符串。设两字符串s 和t ，则它们之间的相似度可由下式给出： min(,) 1 (,)1[( ())]/max(,)s t i Sim s t f i s t s t ==-+-∑ 其中：若s[i]=t[i],则f(i)=0;否则f(i)=1。由于每个概念的实例对该概念的每个属性都分配了一个相应的值，对于其他类型的数据，可以采用下面介绍的方法进行计算。 设概念A 的属性为a i ，概念B 的属性为b j ，两个属性之间的相似度的计算公式为： Sim(a i ，b j )= w 1s 1(a i ，b j )+ w 2s 2(a i ，b j )+ w 3s 3(a i ，b j ) 其中w i 是权重，代表属性名称、数据类型、属性实例数据对属性相似度计算的重要程度，且和为1。设概念A,B 之间总共计算出m 个sim(a i ，b j )，并设置相应的权值k l ，则概念之间基于属性的相似度为： 1 1 (,)/(,)m m l i j l l l k Sim a b k Sim A B ==∑∑ =