收稿日期:2008-01-18;修回日期:2008-04-17 基金项目:国家自然科学基金资助项目(90412010,70572090);N S C F (60573166);华北电力大学博士学位教师科研基金资助项目(H 0585)
作者简介:郭庆琳(1973-),男,山东单县人,副教授,硕导,博士后,主要研究方向为自然语言处理、语义We b 、数据挖掘(q l g u o @p k u .e d u .c n );李艳梅(1983-),女,硕士研究生,主要研究方向为自然语言处理、语义We b 、数据挖掘;唐琦(1983-),男,硕士研究生,主要研究方向为自然语言处理、语义We b 、数据挖掘.
基于V S M 的文本相似度计算的研究
＊
郭庆琳
1,2
,李艳梅1,唐 琦
1
(1.华北电力大学计算机科学与技术学院,北京102206;2.北京大学计算机系,北京100871)
摘 要:文本相似度的计算作为其他文本信息处理的基础和关键,其计算准确率和效率直接影响其他文本信息
处理的结果。提出改进的D F 算法和T D -I D F 算法,一方面利用了D F 算法具有线性的时间复杂度,比较适合大规模文本处理的特点,并通过适当增加关键词的方法,弥补了其对个别有用信息错误过滤的不足;另一方面,利用特征项在特征选择阶段的权重对T D -I D F 方法进行加权处理,在不增加开销的情况下扩大了文档集的规模,还提高了相似度计算的精确度。
关键词:文本相似度;特征选择;词频—逆文档频率法;向量空间模型中图分类号:T P 391 文献标志码:A 文章编号:1001-3695(2008)11-3256-03
S i m i l a r i t y c o m p u t i n g o f d o c u m e n t s b a s e d o n V S M
G U OQ i n g -l i n 1,2,L I Y a n -m e i 1,T A N GQ i
1
(1.S c h o o l o f C o m p u t e r S c i e n c e ＆T e c h n o l o g y ,N o r t hC h i n aE l e c t r i c P o w e r U n i v e r s i t y ,B e i j i n g 102206,C h i n a ;2.D e p t .o f C o m p u t e r S c i e n c e ＆T e c h n o l o g y ,P e k i n gU n i v e r s i t y ,B e i j i n g 100871,C h i n a )
A b s t r a c t :T h e p r e c i s i o n a n d e f f i c i e n c y o f t h e c o m p u t i n g o f d o c u m e n t s s i m i l a r i t y i s t h e f o u n d a t i o n a n d k e y o f o t h e r d o c u m e n t s
p r o c e s s .T h i s p a p e r i m p r o v e dt h e D Fa n dT F -I D Fa r i t h m e t i c .I nt h i s w a y ,D F 's t i m e c o m p l e x i t y w a s l i n e a r i t y t h a t s u i t e dt h e m a s s d o c u m e n t s p r o c e s s ,a n d c o u l d m a k e u p t h e f a u l t t h a t e x c e p t i o n a l u s e f u l c h a r a c t e r s m i g h t b e d e l e t e d .A l s o ,i t d i d a m e n d o nt h e T F -I D Fa r i t h m e t i c t o i m p r o v e t h e p r e c i s i o no f d o c u m e n t s s i m i l a r i t y .K e y w o r d s :d o c u m e n t s s i m i l a r i t y ;f e a t u r es e l e c t i o n ;T F -I D F (t e r mf r e q u e n c y -i n v e r s ed o c u m e n t f r e q u e n c y );V S M(v e c t o r s p a c e m o d e l ) 随着计算机的普及和网络的飞速发展,互联网上以及各种电子文档的数量以空前的速度增长,人们获取知识的途径也发生了深刻的变化。面对如此巨大的知识海洋,如何快速查找相关信息变得非常重要。如果没有有效的组织和提取方式,普通用户查找自己想要的信息所用的时间可能比了解信息本身所花费的时间还长,这是人们无法容忍的。文本相似度是表示两个或多个文本之间匹配程度的一个度量参数,相似度大,说明文本相似程度高,反之文本相似度低。对于文本聚类、信息检索、问答系统、网页去重、文本分类等很多领域,文本相似度的有效计算问题是其进行信息处理的关键。
向量空间模型
向量空间模型(V S M )是20世纪60年代末由S a l t o n 等人提出来的,它是代数模型的一种,也是目前信息检索领域中广泛采用且效果较好的一种模型。其基本思想是:假设词与词之间是不相关的,以向量来表示文本,从而简化了文本中关键词之间的复杂关系,使得模型具备了可计算性
[1]
。在V S M 中,将文档看
成是相互独立的词条组(T 1,T 2,T 3,…,T n )构成,对于每一个词条T i ,根据其在文档中的重要程度赋予一定权值W i ,并将(T 1,T 2,T 3,…,T n
)看成是一个n 维坐标系中的坐标轴,(W 1,W 2,W 3,…,W n )为对应的坐标值。这样由(T 1,T 2,T 3,…,T n )分解得到的正交词条矢量组就构成了一个文档向量空间[2]。
特征选择
特征选择就是根据一些标准从原始特征集中选择子集的过程。特征选择的任务就是选择对相似度计算真正有贡献的特征项,被选中的特征项应能表征原始文本的主题。. 常用的特征选择算法
依据需不需要类别信息,特征选择分为有监督和无监督两类。其中有监督的特征选择方法有信息增益(i n f o r m a t i o ng a i n ,
I G )、χ2
统计(C H I )和互信息(m u t u a l i n f o r m a t i o n ,M I )等;无监
督的特征选择算法有文档频率(d o c u m e n t f r e q u e n c y ,D F )、特征增强(t e r ms t r e n g t h ,T S )、特征贡献(T C )等。.. 信息增益
一个特征的信息增益是指如果该特征在一篇文档中出现,进行类别预测所获得的信息量[3],也就是说一个特征项的信息增益就是在不考虑任何特征项的文档集的熵和考虑该特征项后的文档集的熵的差值,公式如下:
I G (t )=-∑m
i =1P (c i )l o g P (c i
)+第25卷第11期2008年11月
计算机应用研究A p p l i c a t i o n R e s e a r c h o f C o m p u t e r s
V o l .25N o .11
N o v .2008
P (t k )∑m
i =1
P (c i t k )l o gP (c i t k
)+P (t k )∑m
i =1
P (c i t k )l o gP (c i t k
)(1)
其中:P (C i )表示类别出现的概率;P (t k )为训练集中出现词条t k 的概率;P (C i t k )为文档中出现t k 时文档属于C i 的概率;P (C i t k )为文档中不出现t k 时文档属于C i 的概率。词条是否出现都将为分类提供重要的信息,根据每个特征的信息增益值进行排序,选择排在前面的一定数量作为特征,具体数目需要根据实际情况进行调整。.. χ统计
χ2
统计表示了特征项和类别之间的关系
[4]
,定义如下:
χ2(t ,c )=N×[P (t ,c )×P (t ,c )-P (t ,c )×P (t ,c )]2
/
[P (t )×P (t )×P (c )×P (c )]≈
N×(A D-B C )2
/[(A +B )×(C +D )×(A+C )×(B+D )]
(2)
其中:t 表示特征项;A 为t 和c 同时出现的次数;B 为t 出现而c 没有出现的次数;C 为c 出现而t 没有出现的次数;D 为t 和c 同时没有出现的次数;N 为所有训练文档数。进而可以得出特征项t 的平均C H I 统计和最大C H I 统计
χ2a v g (t )=∑m
i =1
P (c i )χ2
(t ,c i
)(3)χ2m a x (t )=m a x m i =1{χ2(t ,c i
)}(4)
其中:m 表示类别数。C H I 词条统计值比较了一个类别的贡献和对其余类别的贡献,以及词条和其他词条对分类的影响。C H I 值越大,特征项与类越相关,所以在特征选择时就选择C H I 统计值大的特征项。.. 互信息
令t 表示特征,c 表示类别,则t 与c 之间的互信息为
I (t ,c )=l o g (P (t ,c )/(P (t )×P (c )))
(5)
在一个包含m 个类别的集合中特征项t 的互信息值可定义为如下两种:
I a v g (t )=∑m
i =1
P (c i )I (t ,c i
)(6)I m a x (t )=m a x m i =1I (t ,c i
)(7)
其中:I a v g (t )表示t 的平均互信息;I m a x (t )表示t 的最大互信息。互信息表征了特征与类之间的相关程度,当特征的出现只依赖于某一类时,互信息大;当特征与类相互独立时,互信息为0;当特征很少在该类中出现时,互信息为负数。在特征选择时,应该选择互信息大的特征项。.. 文档频率
文档频率是训练集中含有词条t k
.的文本数和训练集文档总数的比。D F 的理念假设是稀有单词要么不含有有效信息,要么对分类产生的影响很小,或者是噪声点。该方法是最简单的特征选择方法,具有线性的时间复杂度,因而容易扩展到大的数据集合。在实际应用中效果显著[5]。.. 特征增强
这种方法根据特征项出现在一对相关文档的其中一个的条件下,也出现在另一个中的概率来计算T S 。它用一个文档训练集来得到相似度超过阈值的文档对。用d i 和d j 代表任意一对不同但相关的文档,t 代表特征,一个特征T S 定义如下:
T S (t )=P (t ∈d j t ∈d i );d i ,d j ∈D ∩s i m (d i ,d j
)>β(8)
其中:β是决定相关文档的阈值。
因为需要计算每一个文档对的相似度,所以T S 的时间复
杂度是O (N 2
),N 表示所有的文档数目。
.. 特征贡献
该方法依据特征对文档相似度的整体贡献对特征进行排
序。像D F 这样的简单方法认为特征在不同文档中具有相同的重要性,所以当特征项有高的文档频率但是在不同的类别中分布一致时,它是容易有偏差的。该方法考虑了特征项的权重。. 改进的
算法
D F 算法中,一般的做法是当特征项的D F 小于某个阈值时去掉,特征项的D F 大于某个阈值也去掉。可能会将某个在某篇文档中出现率很高但在文档集中含量不高的词认为是无用特征过滤掉。为了弥补这个缺点,需要对该算法进行改进,对于在
文档关键位置出现的词,适当增加其词频N i
,公式如下:W i =T i /T ×N i
/N (9)
其中:W i 表示特征项的权值;T i 表示出现特征项i 的文档数;T 表示总文档数;N i 表示特征项i 出现的次数;N 为总的特征项个数。这样就可以在一定程度上减小出现在较少文本且有效的词被过滤掉的概率。
文档相似度计算
计算对象相关度的常用模型主要有向量空间模型和集合运算模型等。由于后者的局限性比较大[6],最常用的是向量空间模型。. 基于
的
-
基于向量空间模型的方法中,使用较多且效果较好的方法是基于空间向量模型的T F -I D F 方法,它综合考虑了不同的词在所有文本中的出现频率和这个词对不同文本的分辨能力,被广泛用于计算文本之间的相似度。一篇文档在V S M 中被表示成一个向量,每个向量由其特征项及其权值表示,这就构成了文档向量空间。文档的相似度可用向量之间的夹角或距离来表示,其距离或夹角越小,说明文档相似度越高。
T F -I D F 方法是空间向量模型的常用方法,其公式如下:
W t ,d =T F t ,d ×I D F t
(10)
其中:W t ,d 表示该特征项在文档中的重要程度;T F t ,d 指特征项在文档d 中出现的次数。S a l t o n 将I D F t
表示成I D F t =l o n g (N /n t
)(11)
其中:N 表示文档集合中所有文档的数目;n t 表示所有文档集合中t 出现的次数,称为特征项的文档频率。I D F 反映特征项在整个文档集合中的分布情况,在一定程度上体现了该特征项的区分能力;T F 反映特征项在文档内部的分布情况。T F -I D F 算法可以排除那些高频、低区分度的词,因此T F -I D F 是一种有效的权重定义方法。. 改进的
-算法
对于一般的文本相似度计算方法,首先是利用训练集进行特征词选择,然后再根据已选择的特征对文档集进行统计,前后的工作是分离的,也就是说,前期的特征一旦被选中,在后期对文档进行词频统计时,它们的地位相同。另外,无论是D F 特征选择,还是T F -I D F 都是基于词频统计的,所以比较适用于大规模文本计算,即对于规模较大的文本集合,其效果更好。为了满足基于统计算法的这个特性,又不增加系统开销,本文提出将特征项在特征选择阶段的权重应用到要计算相似度的文档集合中。改进的T F -I D F 算法如下:
W t ,d =W t ×T F t ,d ×I D F t
(12)
·
3257·第11期
郭庆琳,等:基于V S M 的文本相似度计算的研究
其中:W t 表示特征项t 在训练集中的权重,其大小应根据具体情况进行调整。. 相似度计算
余弦计算方法是常用的计算文本相似度的方法。其公式如下:
s i m (T i ,T j )=(∑n
t =1
T i ,t ×T j ,t )/(∑n
t =1
T i ,t
×∑n
t =1
T j ,t
)(13)
其中:T i 表示文本特征向量;T i ,t 表示文本T i
的第t 个向量。 实验结果及分析
实验选用的语料为英国L a n c a s t e r 大学中文文本分类语料[7](L a n c a s t e r c o r p u s o f m a n d a r i nC h i n e s e ,L C M C )。该语料共
有500篇文本,839006个词,分为15个类别,已经用X M L 形式进行了切分和词性标注。实验对语料的新闻报道、新闻社论、新闻评论三个类别的88篇文章,147771个词进行了词频统计,选择出350个特征词。另外选出8篇文章,分别用T F -I D F 和改进的T F -I D F 计算其相似度,并与专家对其评估
的结果比较。其结果如表1和图1所示。
由图1可以看出,改进的T F -I D F 算法更接近专家评估,能较好地反映文档之间的相似度。
结束语
文本相似度的计算是其他文本信息挖掘的基础和关键,越来越受到人们的重视,其效率和准确率直接影响后期的文本处理结果。本文提出,在特征选择阶段,利用D F 算法的高效性,并对其可能造成的错误过滤进行改进;更主要的是,在相似度计算中,利用各个特征在特征提取时的权值,对T F -I D F 进行了改进,提高了其精确度。参考文献:
[1]王秀娟.文本检索中若干问题的研究[D ].北京:北京邮电大学,
2006.[2]沈斌.基于分词的中文文本相似度计算研究[D ].天津:天津财
经大学,2006.[3]Y A N GY ,P E D E R S E NJ O .Ac o m p a r a t i v e s t u d y o nf e a t u r e s e l e c t i o n
i nt e x t c a t e g o r i z a t i o n [C ]//P r o c o f t h e 14t hI n t e r n a t i o n a l C o n f e r e n c e o nM a c h i n e L e a r n i n g .S a n F r a n c i s c o :M o r g a nK a u f m a n n ,1997:412-420.[4]G A L A V O T T I L ,S E B A S T I A N I F ,S I M I M .F e a t u r e s e l e c t i o n a n d n e g a -t i v ee v i d e n c ei na u t o m a t e dt e x t c a t e g o r i z a t i o n [C ]//P r o co f K D D -2000.B o s t o n ,M A :[s .n .],2000:16-22.[5]严莉莉,张燕平.基于类信息的文本聚类中特征选择算法[J ].
计算机工程与应用,2007,43(12):144-146.[6]宋玲,马军,连莉.文档相似度综合计算[J ].计算机工程与应
用,2006,42(1):160-163.[7]T h e L a n c a s t e r c o r p u s o f m a n d a r i nC h i n e s e(L C M C )[E B /O L ].h t -t p ://w w w .l i n g .l a n c s .a c .u k /c o r p l a n g /l c m c /.
(上接第3245页) 基于元音段N A Q 特征和G M M 的情感识别
和感知实验,少数情感的识别率已经比较接近,但大部分情感的识别率还有一定的差距,这是因为只采用了N A Q 值这个一维特征。
表1 G M M 识别结果与感知实验识别结果比较
%
识别结果
a n g e r d i s g u s t
f e a r h a p p i n e s ss a d n e s s s u r p r i s e
感知实验73.376.7639086.763.3元音段特征3063.356.704040整句特征
26.7
63.3
30
3.3
16.7
3.3
结束语
本文通过实验验证了将声源时域参数N A Q 值作为情感识别的特征之一的可行性。情感识别实验结果表明,大部分以元音段的N A Q 值为特征的情感识别率比以整句N A Q 值为特征的情感识别率高,而且F -r a t i o 的实验结果也表明,以元音段的N A Q 值作为特征对情感有更强的区分力。当然本文仅用了N A Q 值一维特征,识别结果还不是很理想。作为后续工作,本文将研究N A Q 参数结合基于基频的其他特征,选择更有效的特征集进行语音情感识别,期望得到更好的识别效果。参考文献:
[1]
G O B LC ,C H A S A I D EN .T h er o l e o f v o i c eq u a l i t y i nc o m m u n i c a t i n g e m o t i o n ,m o o da n da t t i t u d e [J ].S p e e c hC o m m u n i c a t i o n ,2003,40:189-212.[2]
A L K UP ,
B
C K S T R M T ,V I L K M A NE .N o r m a l i z e da m p l i t u d e q u o -t i e n t f o rp a r a m e t e r i z a t i o no ft h eg l o t t a lf l o w[J ].J o u r n a l o f t h e A c o u s t i c a l S o c i e t yo f A me r i c a ,2002,112(2):701-710.[3]
L E H T O L ,A I R A SM ,B J R K N E R E ,e t a l .C o m p a r i s o no f t w oi n -
v e r s e f i l t e r i n g m e t h o d s i np a r a m e t e r i z a t i o no f t h eg l o t t a l c l o s i n gp h a s e c h a r a c t e r i s t i c si n d i f f e r e n tp h o n a t i o n t y p e s [J ].J o u r n a lV o i c e ,2007,21(2):138-150.[4]
A I R A SM ,A L K UP .E m o t i o n s i ns h o r t v o w e l s e g m e n t s :e f f e c t s o f t h e g l o t t a l f l o wa s r e f l e c t e db yt h en o r m a l i z e da m p l i t u d e q u o t i e n t [C ]//P r o co f T u t o r i a l a n d R e s e a r c h Wo r k s h o p ,A f f e c t i v e D i a l o g u e S y s t e m s .2004:13-24.[5]
A I R A S M ,A L K U P .E m o t i o n si n v o w e ls e g m e n t so fc o n t i n u o u s s p e e c h :a n a l y s i so ft h eg l o t t a l f l o w u s i n gt h en o r m a l i z e da m p l i t u d e q u o t i e n t [J ].P h o n e t i c a ,2006,63(1):26-46.[6]
M A R T I NO ,K O T S I AI ,M A C QB ,e t a l .T h e e N T E R F A C E '05a u d i o -v i s u a l e m o t i o n d a t a b a s e [C ]//P r o co f t h e 22n dI n t e r n a t i o n a l C o n f e -r e n c e o nD a t a E n g i n e e r i n gW o r k s h o p s .Wa s h i n g t o n :I E E E C o m p u t e r S o c i e t y ,2006:8-16.[7]
A L K UP .G l o t t a l w a v e a n a l y s i s w i t hp i t c hs y n c h r o n o u s i t e r a t i v ea d a p -t i v e i n v e r s e f i l t e r i n g [J ].S p e e c hC o m m u n i c a t i o n ,1992,11(2-3):109-118.[8]
A L K UP ,T I I T I N E NH ,N R I S T ON A A T A N E NR .Am e t h o d f o r g e n e -r a t i n gn a t u r a l -s o u n d i n gs p e e c hs t i m u l if o rc o g n i t i v eb r a i n r e s e a r c h [J ].C l i n i c a l N e u r o p h y s i o l o g y ,1999,110:1329-1333.[9]
F A N T
G .T h e v o i c es o u r c e i nc o n n e c t e ds p e e c h [J ].S p e e c hC o m -m u n i c a t i o n ,1997,22(2-3):125-139.
[10]A L K UP ,V I L K M A NE .A m p l i t u d e d o m a i nq u o t i e n t f o r c h a r a c t e r i z a -t i o n o f t h e g l o t t a l v o l u m e v e l o c i t y w a v e f o r me s t i m a t e db y i n v e r s e f i l t e -r i n g [J ].S p e e c hC o mm u n i c a t i o n ,1996,18(2):131-138.[11]蒋冬梅,赵荣椿.一种基于共振峰恢复和M e l l i m 变换的非特定人
语音特征提取方法[J ].数据采集与处理,2001,16(1):58-62.[12][E B /O L ].h t t p ://h t k .e n g .c a m .a c .u k .
·3258·计算机应用研究 第25卷
龙源期刊网 https://www.doczj.com/doc/ae6265451.html, 相似度算法在源程序比较中的应用 作者：朱利龙 来源：《电脑知识与技术》2016年第21期 摘要：在计算机程序课的教学过程中，时常需要对学生所提交的源程序进行检查，特别是源程序的重复率检查。纯人工对比不但花费时间长，而且效率低下。因此，本文提出利用文本相似度算法解决源程序对比的方法，并设计出相应的源程序比较系统，来帮助老师从繁重的工作中解脱出来。 关键词：相似度；距离编辑算法；源程序对比 中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）21-0214-01 源程序对比分析是一个复杂的过程，不仅需要考虑实用性和考虑准确性，而且还要兼顾运行效率等问题。在程序上机课的过程性考核中，很多同学提交的程序源代码之间重复率很高。本文借助计算机实现源程序的自动对比，不但可以降低劳动强度，提高工作效率，而且可以减少误判的可能性，进一步保证源程序对比结果的正确性。 1 特征提取 要获取源程序重复率，判断是否抄袭程度，可以通过计算源程序的相似率来代替。相似率越高说明源程序重复部分越多，学生抄袭的可能性越高。要计算代码的相似率，就得提取源代码的有关特征参数。 根据源程序块粒度大小不同，可以利用源程序中诸如换行符之类的分割符来分解成程序语句，分解得到的每一部分称为一个程序块。源程序块的选择将在很大程度上影响程序的效率，要比较源程序部分复制，就必须减少源程序块的长度。本文将每一个语句看成一个源程序块，即粒度大小为一条语句。于是，源程序就被分解为语句集合，源程序的相似程度便可以由语句的相似率来计算。因此，对于源程序的对比，选择程序语句作为源程序的对比粒度块是具有可行性的。 本文系统采用的是距离编辑算法，利用字符串的模式匹配实现对源程序相似度进行判断。把两篇源程序进行全文对比得出相似度；得出相似度后，根据源程序分隔符把两源程序分割成逐条语句的，然后对这些语句进行一一对比，得出语句的相似度；比较出来的超过语句的相似度的语句称为相似句，把相似句对应的原句进行红色标记；统计出相似句对应原句占原源程序的比例，在比较中可以通过红色显示相同。 2 距离编辑算法
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的权重，
计算文本相似度几种最常用的方法，并比较它们之间的性能 编者按：本文作者为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.
基于WMD距离的文本相似度算法研究 随着AI技术的迅速崛起,人工智能和随之而来的海量文本数据对自然语言处理也提出了更高的要求。文本相似度作为自然语言处理领域的一大基础任务,在搜索引擎、QA系统、机器翻译、文本分类、拼写纠错等领域有广泛的应用。 文本作为承载语义信息的一种重要方式,传统的文本表示采用向量空间模型来表达语义信息,这种方式未考虑到特征词的顺序以及上下文语义理解,造成高维稀疏以及计算效率低的问题。WMD距离算法利用word2vec中的语义信息,实现高度语义共现精确度,并能挖掘出独立词之间的语义相关性。 因此本文的研究工作基于WMD距离算法展开,在WMD距离算法的基础上充分挖掘文本语义中有价值的特征项以及结合知识词典中的语言学知识构架和句法依存关系,提出了两种改进算法。本文的主要工作有:1.本文基于WMD距离算法存在过于单一的词频权重无法有效提取文本特征及利用语义信息的问题,提出了WMD-JCS(Word Mover’s DistanceJoint Character and Sentence)算法。 该改进算法将原始的词频权重代替为使用TF-IDF系数、词语词性以及出现的物理位置作为新的文本特征项,并将这些特征项以合理的数学计算公式加入算法中;其次将训练好的词向量以无监督方式构造句子的句向量,以充分考虑语义的上下文环境;最后将筛选出的关键词的词向量和句向量参与计算改进后的距离公式。实验表明,该改进算法与WMD距离算法相比,可以有效提高文本相似度的准确度。 2.基于上述第一种改进的WMD-JCS算法,本文提出了另一种改进算法 WMD-WSA(Word Mover’s Distance-Word Sense Analysis)。由于基于深度学习的计算方法的语义可解释性差以及WMD-JCS算法存在无法融合深层语义相关性
图像相似度计算主要用于对于两幅图像之间内容的相似程度进行打分，根据分数的高低来判断图像内容的相近程度。 可以用于计算机视觉中的检测跟踪中目标位置的获取，根据已有模板在图像中找到一个与之最接近的区域。然后一直跟着。已有的一些算法比如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);
文本相似度算法 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）
第３２卷 第５期 ２０１８年５月中文信息学报JOU RNAL OF CHINESE INFORM A TION PROCESSING Vol ．３２，No ．５May ，２０１８文章编号：１００３-００７７（２０１８）０５-００９７-０８ 面向情感聚类的文本相似度计算方法研究 李欣１，李旸２，王素格２，３ （１．山西职工医学院信息中心，山西晋中０３０６１９； ２．山西大学计算机与信息技术学院，山西太原０３０００６； ３．山西大学计算智能与中文信息处理教育部重点实验室，山西太原０３０００６） 摘 要：在文本情感分析时，使用无监督的聚类方法，可以有效节省人力和数据资源，但同时也面临聚类精度不高的问题。相似性是文本聚类的主要依据，该文从文本相似度计算的角度，针对情感聚类中文本—特征向量的高维和稀疏问题，以及对评论文本潜在情感因素的表示问题，提出一种基于子空间的文本语义相似度计算方法（RESS ）。实验结果表明，基于RESS 的文本相似度计算方法，有效解决了文本向量的高维问题，更好地表达了文本间情感相似性，并获得较好的聚类结果。 关键词：文本情感聚类；文本相似度计算；文本语义子空间 中图分类号：T P ３９１ 文献标识码：A Text Similarity Calculation for Text Sentiment Clustering LI Xin １，LI Yang ２，WANG Suge ２，３（１．Information Center ，Shanxi Medical College for Continuing Education ，Jinzhong ，Shanxi ０３０６１９，China ；２．School of Computer and Information Technology ，Shanxi University ，Taiyuan ，Shanxi ０３０００６，China ； ３．Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education Shanxi University ，Taiyuan ，Shanxi ０３０００６，China ）Abstract ：In text sentiment analysis ，unsupervised clustering method is challenged by low precision ．To improve the text similarity measure lying as key to clustering ，this paper proposes a semantic subspace （RESS ）method to deal with the high dimension and sparseness of sentiment text representation issue ．It also helps to caputure the implicit expression of sentiment ．The experimental results show that RESS can effectively reduce the feature of data set and g enerat better results ．Key words ：sentiment -based text clustering ；text similarity calculation ；text semantic subspace 收稿日期：２０１７-０３-０３ 定稿日期：２０１７-０５-１２基金项目：国家自然科学基金（６１５７３２３１，６１６３２０１１，６１６７２３３１，６１４３２０１１）；山西省科技基础条件平台计划项目（２０１５０９１００１-０１０２）0 引言 随着新兴电子商务平台，微博和微信等社交媒 体的广泛使用，人们在享受互联网技术带来便利的 同时，也用文字记载了自己的心情、状态、评价和观 点。通过挖掘海量微博和评论文本等社会媒体数 据，可以获得用户对产品的情感倾向（褒扬或者贬 斥），从而指导企业的决策以及个人的消费行为 ［１-２］。有监督的机器学习方法需要大量的带标签的文本数据，而无监督的文本聚类方法可以克服这一不足［３］。目前，聚类方法在文本数据挖掘中发挥了重要作用，情感聚类的相关研究也备受关注［４］。情感聚类常面临三个困难：首先，由于聚类算法的无指导性，使聚类结果总是沿着文本最显著的特点聚簇。而文本一般是按照一定的主题进行组织，因此，情感聚类结果的准确率并不高；其次，由于用户表达的感受和观点等情感蕴含在评论中，其特征表现并不明显。从大量的特征中难以实现情感特征的有效分 万方数据
1文本相似度算法基本原理 1.1文本相似度含义 文本相似度来自于相似度概念，相似度问题是一个最基本的问题，是信息科学中绕不过去的概念，在不同的应用方向其含义有所不同，但基本的内涵表示了一个信息结构与另外一个信息结构的一致程度，从某个角度研究时特征量之间的距离大小[10]。比如，在机器翻译方面是指词这个基本单位的可替代性，在信息检索方面是指检索结果与检索内容的一致性，在自动问答方面是指搜索的结果与输入的问题的匹配程度。这充分表明文本相似度研究和应用领域十分广泛，所表达的含义也十分不同。从本文研究的角度来看，文本相似度可以描述为：有A、B两个对象，二者之间的公共区域越多、共性越大，则相似程度越高；若二者没有关联关系，则相似程度低。在文本相似度研究方面，一个层次是研究文档中以篇章、句子、词语衡量相似程度，这不同层次衡量算法也不同，研究的标准和依据也不同，算法的复杂程度也不同。从这个意义上，可以运用在新闻领域对新闻稿件进行归档，按照新闻的领域分门别类的存放在一起；也可以运用在信息检索进行信息查询，作为一个文本与另一个文本之间相似程度测量的基本方法。 1.2文本相似度计算方法分类 当前研究文本相似度都是以计算机作为计算工具，即利用计算机算法对文本进行分类，在各个领域应用十分广泛，比如包括网页文本分类、数据智能挖掘、信息识别检索、自动问答系统、论文查重分析和机器自主学习等领域，其中起最关键作用的是文本相似度计算算法，在信息检索、数据挖掘、机器翻译、文档复制检测等领域有着广泛的应用。 特别是随着智能算法、深度学习的发展，文本相似度计算方法已经逐渐不再是基于关键词匹配的传统方法，而转向深度学习，目前结合向量表示的深度学习使用较多，因此度量文本相似度从方法论和算法设计全局的角度看，一是基于关键词匹配的传统方法，如N-gram相似度；二是将文本映射到向量空间，再利用余弦相似度等方法，三是运用机器学习算法的深度学习的方法，如基于用户点击数据的深度学习语义匹配模型DSSM，基于卷积神经网络的ConvNet和LSTM 等方法。 本文研究的重点是对电子作业检查等各类电子文档对比，在对两个电子文档是否相同，相似比例为多少这一问题探究中需要比较文档的相似度，而文档的相似度又可分成段落相似度、句子相似度来进行考虑，所以课题的关键是如何定义
基于距离的计算方法 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)。
句子相似度地计算在自然语言处理具有很重要地地位,如基于实例地机器翻译( )、自 动问答技术、句子模糊匹配等.通过对术语之间地语义相似度计算,能够为术语语义识别[]、术语聚类[]、文本聚类[]、本体自动匹配[]等多项任务地开展提供重要支持.在已有地术语相似度计算方法中,基于搜索引擎地术语相似度算法以其计算简便、计算性能较高、不受特定领域语料库规模和质量制约等优点而越来越受到重视[]. 相似度计算方法总述： 《向量空间模型信息检索技术讨论》，刘斌，陈桦发表于计算机学报， 相似度()：指两个文档内容相关程度地大小，当文档以向量来表示时，可以使用向量文 档向量间地距离来衡量，一般使用内积或夹角地余弦来计算，两者夹角越小说明似度 越高.由于查询也可以在同一空间里表示为一个查询向量(见图)，可以通过相似度计算 公式计算出每个档向量与查询向量地相似度，排序这个结果后与设立地阈值进行比较. 如果大于阈值则页面与查询相关，保留该页面查询结果；如果小于则不相关，过滤此页.这样就可以控制查询结果地数量，加快查询速度.资料个人收集整理，勿做商业用途 《相似度计算方法综述》 相似度计算用于衡量对象之间地相似程度，在数据挖掘、自然语言处理中是一个基础 性计算.其中地关键技术主要是两个部分，对象地特征表示，特征集合之间地相似关系. 在信息检索、网页判重、推荐系统等，都涉及到对象之间或者对象和对象集合地相似 性地计算.而针对不同地应用场景，受限于数据规模、时空开销等地限制，相似度计算 方法地选择又会有所区别和不同.下面章节会针对不同特点地应用，进行一些常用地相 似度计算方法进行介绍.资料个人收集整理，勿做商业用途 内积表示法： 《基于语义理解地文本相似度算法》，金博，史彦君发表于大连理工大学学报， 在中文信息处理中,文本相似度地计算广泛应用于信息检索、机器翻译、自动问答系统、文本挖掘等领域,是一个非常基础而关键地问题,长期以来一直是人们研究地热点和难点.计算机对于中文地处理相对于对于西文地处理存在更大地难度,集中体现在对文本分词 地处理上.分词是中文文本相似度计算地基础和前提,采用高效地分词算法能够极大地提 高文本相似度计算结果地准确性.本文在对常用地中文分词算法分析比较地基础上,提出 了一种改进地正向最大匹配切分()算法及歧义消除策略,对分词词典地建立方式、分词 步骤及歧义字段地处理提出了新地改进方法,提高了分词地完整性和准确性.随后分析比 较了现有地文本相似度计算方法,利用基于向量空间模型地方法结合前面提出地分词算法,给出了中文文本分词及相似度计算地计算机系统实现过程,并以科技文本为例进行了 测试,对所用方法进行了验证.这一课题地研究及其成果对于中文信息处理中地多种领域 尤其是科技类文本相似度地计算比较,都将具有一定地参考价值和良好地应用前景.资料 个人收集整理，勿做商业用途
文本相似度的设计与实现 摘要：本文主要设计并实现了一个文本相似度系统，该系统主要功能计算文档之间的相似度，通过使用向量空间模型(VSM, Vector Space Model)及余弦相似度计算公式计算文档之间的相似度，数据预处理过程中加入word2vec模型进行语义扩充，从而能够匹配到更多相关文档。 1.向量空间模型 向量空间模型(VSM, Vector Space Model)由Salton等人于20世纪70年代年提出[1,2]。向量空间模型的主要思想是将文本内容的处理简化为向量空间中的向量运算，这样将空间上的相似度转化为语义上的相似度。当文档被表示为文档空间的向量时，便可通过计算向量之间的相似性来度量文档间的相似性。文本处理中最常用的相似性度量方式是余弦距离。 向量空间模型的基本思想： 给定一篇文档D=D(T1,T2,…T i,…,T n)，若T i在文档中既可以重复出现又存在先后次序，因此分析起来会较为困难。针对上述情况，暂不考虑T i的顺序，并要求T i互异，此时可将T1,T2,…T i,…,T n看作n维坐标，每一维对应相应值W i，因此D(W1,W2,…,W i,…,W n)便可以看作一个n维向量。 例如：有一篇文档D={大家好，才是真的好}，首先进行分词后转换为D={大家/好/才是/真的/好}，之后提取出公因词D={大家，好，才是，真的}，最后通过向量空间模型将文档转换为对应的向量D={1，2，1，1}。 向量空间模型只是将文档转换为方便计算的格式，若进行相似度计算，还需使用相似度计算公式进行计算。本文使用余弦相似度计算公式。 2.余弦相似度 余弦相似度计算公式广泛应用于文本数据之间的相似度计算过程中。其数学表达如下： 计算过程如下： 例如，有2个文档D1={大家好}，D2={才是真的好}，首先将D1、D2分词后，D1={大家/好}，D2={才是/真的/好}，其次提取出公因词D={大家，好，才是，真的}，然后通过向量空间模型转换成向量表达，D1={1，1，0，0}，D2={0，1，1，1}，最后进行相似度计算 Score== 3.文本相似度系统 本文主要使用向量空间模型及余弦相似度距离公式进行文本相似度计算任务，系统的基本架构如下图1所示：
向量的相似度计算常用方法 相似度的计算简介 关于相似度的计算，现有的几种基本方法都是基于向量（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中，实现了数据中心化的过程，所以皮尔森相似度值也是数据中心化后的余弦相似度。另外在新版本
几种相似度计算方法作对比 句子相似度的计算在自然语言处理具有很重要的地位,如基于实例的机器翻译(Example Based Ma-chine Translation,EBMT)、自动问答技术、句子模糊匹配等.通过对术语之间的语义相似度计算,能够为术语语义识别[1]、术语聚类[2]、文本聚类[3]、本体自动匹配[4]等多项任务的开展提供重要支持。在已有的术语相似度计算方法中,基于搜索引擎的术语相似度算法以其计算 简便、计算性能较高、不受特定领域语料库规模和质量制约等优点而越来越受到重视[1]。 相似度计算方法总述： 1 《向量空间模型信息检索技术讨论》，刘斌，陈桦发表于计算机学报，2007 相似度S(Similarity)：指两个文档内容相关程度的大小，当文档以向量来表示时，可 以使用向量文档向量间的距离来衡量，一般使用内积或夹角0的余弦来计算，两者夹角越小说明似度越高。由于查询也可以在同一空间里表示为一个查询向量(见图1)，可以通过相似度计算公式计算出每个档向量与查询向量的相似度，排序这个结果后与设立的阈值进行比较。如果大于阈值则页面与查询相关，保留该页面查询结果；如果小于则不相关，过滤此页。这 样就可以控制查询结果的数量，加快查询速度。 2 《相似度计算方法综述》 相似度计算用于衡量对象之间的相似程度，在数据挖掘、自然语言处理中是一个基础性计算。其中的关键技术主要是两个部分，对象的特征表示，特征集合之间的相似关系。在信息检索、网页判重、推荐系统等，都涉及到对象之间或者对象和对象集合的相似性的计算。而针对不同的应用场景，受限于数据规模、时空开销等的限制，相似度计算方法的选择又会有所区别和不同。下面章节会针对不同特点的应用，进行一些常用的相似度计算方法进行介绍。 内积表示法： 1 《基于语义理解的文本相似度算法》，金博，史彦君发表于大连理工大学学报，2007 在中文信息处理中,文本相似度的计算广泛应用于信息检索、机器翻译、自动问答系统、文本挖掘等领域,是一个非常基础而关键的问题,长期以来一直是人们研究的热点和难点。计算机对于中文的处理相对于对于西文的处理存在更大的难度,集中体现在对文本分词的处理上。分词是中文文本相似度计算的基础和前提,采用高效的分词算法能够极大地提高文本相似度计算结果的准确性。本文在对常用的中文分词算法分析比较的基础上,提出了一种改进的正向最大匹配切分(MM)算法及歧义消除策略,对分词词典的建立方式、分词步骤及歧义字段的处理提出了新的改进方法,提高了分词的完整性和准确性。随后分析比较了现有的文本相似度计算方法,利用基于向量空间模型的TF-IDF方法结合前面提出的分词算法,给出了中文文本分词及相似度计算的计算机系统实现过程,并以科技文本为例进行了测试,对所用方
相似度计算 在数据挖掘中经常需要用到比较两个东西的相似度。比如搜索引擎要避免非常相似的文档出现在结果的前几页，再比如很多网站上都有的“查找与你口味相似的用户”、“你可能喜欢什么什么”之类的功能。后者其实是很大的一块叫做“协同过滤”的研究领域，留待以后详谈。 首先我们定义两个集合S,T的Jaccard相似度: Sim(S,T) = |S,T的交集| / |S,T的并集|。直观上就容易感觉出这是一个很简单而且比较合理的度量，我不清楚有没有什么理论上的分析，在此省略。下面先主要说一下文档的相似度。 如果是判断两个文档是否完全相同，问题就变得很简单，只要简单地逐字符比较即可。但是在很多情况下并不是这样，比如网站文章的转载，主体内容部分是相同的，但是不同网页本身有自己的Logo、导航栏、版权声明等等，不能简单地直接逐字符比较。这里有一个叫做Shingling的方法，其实说起来很圡，就是把每相邻的k个字符作为一个元素，这样整篇文档就变成了一个集合。比如文档是"banana"，若k=2，转化以后得到集合为{"ba","an","na"}，于是又变成了前述集合相似度的问题。关于k值的设置，显然过小或过大都不合适，据说比较短的比如email之类可以设k=5，比如长的文章如论文之类可以设k=9。 当然，这是一个看上去就很粗糙的算法，这里的相似度比较只是字符意义上的，如果想进行语义上的比较就不能这么简单了（我觉得肯定有一摞摞的paper在研究这个）。不过同样可以想见的是，在实际中这个粗糙算法肯定表现得不坏，速度上更是远优于复杂的NLP方法。在实际工程中，必然糙快猛才是王道。 有一点值得注意的是，Shingling方法里的k值比较大时，可以对每个片段进行一次hash。比如k=9，我们可以把每个9字节的片段hash成一个32bit的整数。这样既节省了空间又简化了相等的判断。这样两步的方法和4-shingling占用空间相同，但是会有更好的效果。因为字符的分布不是均匀的，在4-shingling中实际上大量的4字母组合没有出现过，而如果是9-shingling再hash成4个字节就会均匀得多。 在有些情况下我们需要用压缩的方式表示集合，但是仍然希望能够（近似）计算出集合之间的相似度，此时可用下面的Minhashing方法。 首先把问题抽象一下，用矩阵的每一列表示一个集合，矩阵的行表示集合中所有可能的元素。若集合c包含元素r，则矩阵中c列r行的元素为1，否则为0。这个矩阵叫做特征矩阵，往往是很稀疏的。以下设此矩阵有R行C列。 所谓minhash是指把一个集合（即特征矩阵的一列）映射为一个0..R-1之间的值。具体方法是，以等概率随机抽取一个0..R-1的排列，依此排列查找第一次出现1的行。例如有集合S1={a,d}, S2={c}, S3 = {b,d,e}, S4 = {a,c,d}，特征矩阵即如下S1 S2 S3 S4 0a 1 0 0 1 1b 0 0 1 0 2c 0 1 0 1
词语相似度算法的分析与改进 摘要：对现有的词语相似度算法进行分析，提出一种基于知网，面向语义、可扩展的词语相似度计算方法，通过对实验结果进行分析，所提出的词语语义相似度计算方法比以前的方法更好，在计算词语相似度时，准确率更高。 关键词：词语相似度算法；义原相似度计算；概念词的相似度计算；非概念词的相似度计算 在建立主观题评分模型时，要判断句子的相似度，计算句子的相似度时，首先要处理的就是词语的相似度计算工作。目前对词语的相似度计算人们已经做了大量的研究，提出了一些较有代表性的计算方法。主要包括以下几种： 1）基于字面信息的词语相似度计算 这种算法的核心内容是：中文词语的构成句子中，一般较核心的内容都放在句子的后面。句子后面的词语在句子中所起到的作用比靠前的词语大。因此在对句子进行分析时需要给后面的字或词赋予较高的权值。 假设a和b分别代表两个词语，按照此算法，词语之间的相似度计算公式可以表示为公式1。 使用字面信息作为相似度计算的算法较简单，实现起来也方便。但该算法准确率不高，尤其是对于语义相似的词语更是难于处理。2）基于词林的词语相似度计算 对于以同义词词林作为语义分类体系进行词语相似度计算的研
究，王斌和章成志都曾作了相关探讨[1]。其核心思想是使用两个词语的语义距离来表示词语间相似度。当处理对象是一个词组或短语时，首先将其切分为义类词，并将义类词在词林的树状结构中提取出相关的语义编码，并对两个词语的语义编码进行相似度计算。基于词林的词语相似度计算较好的解决了语义相似、词形不同的词语相似度计算，但由于语义词典的完备性问题，必然会存在部分不在语义词典中的词语而无法处理。 3）基于知网的词语相似度计算 知网以概念作为描述对象，从关系层次上揭示词语的概念含义，并建立了概念关系网络，包含词语属性以及属性间关系[2]。刘群、李素建从知网的关系描述出发，研究了同一个词义所具有的多个义原间的关系，并试图计算出这些义原在计算相似度时所起到的作用，并根据这种思想提出了使用知网的语义信息来计算词语相似度的算法。 该算法在计算概念词的相似度时较准确，但在计算概念词与非概念词，非概念词与非概念词的相似度时，准确率不高。 为克服这些问题，我们采用知网作为语义资源，结合信息论中的相关理论，提出了一种面向语义的、可扩展的、多策略混合的词语相似度计算模型。 1 义原相似度计算 词语的相似度计算，最终还是要计算各词语的义源相似度。在知网中，所有词语都包含义原信息，应用知网进行相似度计算时，第
文本相似度计算系统 摘要 在中文信息处理中，文本相似度的计算广泛应用于信息检索、机器翻译、自动问答系统、文本挖掘等领域，是一个非常基础而关键的问题，长期以来一直是人们研究的热点和难点。本次毕设的设计目标就是用两种方法来实现文本相似度的计算。 本文采用传统的设计方法，第一种是余弦算法。余弦算法是一种易于理解且结果易于观察的算法。通过余弦算法可以快捷的计算出文本间相似度，并通过余弦算法的结果（0、1之间）判断出相似度的大小。由于余弦计算是在空间向量模型的基础上，所以说要想用余弦算法来完成本次系统，那么必须要将文本转化成空间向量模型。而完成空间向量模型的转换则要用到加权。在空间向量模型实现之前，必须要进行文本的去停用词处理和特征选择的处理。第二种算法是BM25算法，本文将采用最基础的循环来完成，目的是观察余弦算法中使用倒排索引效率是否提高有多大提高。 本次文本相似度计算系统的主要工作是去除停用词、文本特征选择、加权，在加权之后用余弦算法计算文本的相似度。在文本特征选择之后用BM25计算相似度。由于为了使系统的效率提高，在程序设计中应用了大量的容器知识以及内积、倒排算法。 关键词：文本相似度；余弦；BM25；容器
Text Similarity Algorithm Research Abstract In Chinese information processing，text similarity computation is widely used in the area of information retrieval，machine translation,automatic question—answering，text mining and etc．It is a very essential and important issue that people study as a hotspot and difficulty for a long time．Currently，most text similarity algorithms are based on vector space model(VSM)．However,these methods will cause problems of high dimension and sparseness．Moreover，these methods do not effectively solve natural language problems existed in text data．These natural language problems are synonym and polyseme．These problems sidturb the efficiency and accuracy of text similarity algorithms and make the performance of text similarity computation decline． This paper uses a new thought which gets semantic simirality computation into traditional text similarity computation to prove the performance of text similarity algorithms．This paper deeply discusses the existing text similarity algorithms and samentic text computation and gives a Chinese text similarity algorithm which is based on semantic similarity．There is an online information management system which is used to manage students’graduate design papers．Those papers ale used to calculate similarity by that the algorithm to validate that algorithm． This text similarity computing system's main job is to stop word removal, text feature selection, weighting, after weighting using cosine algorithm to calculate the