孙 晶,张东站

(厦门大学信息科学与技术学院,福建厦门361005)

基于逆概念频率的词语相似度计算

孙 晶,张东站*

(厦门大学信息科学与技术学院,福建厦门361005)

词语相似性度量在服务选择、自然语言处理、文献检索等领域具有重要的作用,目前通用的词语相似度计算方法是利用《知网》对词的概念解释得出词语之间相似度.对《知网》结构进行分析,认为利用《知网》计算词的相似度的方法中概念的4项基本结构的权重应该动态产生,并提出区分度作为衡量4项基本结构的动态权重.在分析现有研究基础上,借鉴逆文档频率(IDF)权重计算思想,认为义原的区分度与义原在所有概念的相应位置中出现次数成反比,提出了一种基于义原出现频次的义原权重计算方法:逆概念频率(inverse concept frequency,ICF).通过分析概念的组织结构,计算第一基本义原结构、其他基本义原结构、关系义原结构、关系符号结构中各义原的ICF权重,将4个基本结构中的最大义原ICF权重作为基本结构的ICF权重.利用动态ICF值逼近基本结构的区分度,进而计算词语相似度.通过对真实数据的实验对比可以看出ICF算法能有效提高计算词语相似度的准确率.相比较传统算法平均前160个词准确率从30.74%提高到72.28%,平均召回率从15.87%提高到49.64%.

知网;词语相似度;逆概念频率;义原权重

现阶段以互联网带动的信息技术的不断发展和普及,如何从海量的信息资源中挖掘出有价值的信息成为信息用户的关注点.信息资源形态迥异,使得采用传统的以字符串匹配为基础的信息检索系统逐渐被淘汰,取而代之的是以计算词语之间的语义相似度为核心的概念模型匹配的信息检索,因此提高词语相似度的计算精度显得尤为重要.

词语是文章最基本的组成单位,词语之间的关系也因为人们的思考逻辑而变得复杂.词语相似度计算研究的是计算两个词语相似度的方法,是研究句子相似度的基础.词语相似性度量在服务选择、自然语言理解、文献检索等领域具有重要的作用.可见词语相似度研究有广阔的应用前景和重大研究价值.

现今对词语相似度计算主要分为两类,一种是基于本体的计算方法,根据概念层次结构组织形式及概念之间的上下位与同位关系来计算词语的相似度.另外一种是基于统计的方法,利用大规模语料库,研究上下文环境中各个词语之间出现的某种规律,总结出计算词语相似度的方法.

基于统计的计算方法:基于这样一个假设,语义相近的词,其上下文也应该相似.从大规模语料库中统计出被比较词汇的相关上下文词汇,组成集合、向量化并计算向量夹角余弦值,同时使用词的上下文信息的概率分布作为参考值,进而计算词语的语义相似度.

在中文方面,文献[1]利用词相关性知识计算词语相似度.

基于本体的计算方法:基于这样一个假设,两个词语具有一定的语义相似性,当且仅当其在概念结构层次网络图中存在一条通路.本体能够准确描述概念含义和概念之间的内在关联[2],并根据语义距离来计算词语相似度,已经成为词语相似度研究的基础,当前基于本体的语义相似度计算方法已经取得了丰硕的成果,本文研究的也是基于本体的计算方法.在英文研究中文献[3-4]对基于本体的多种计算方法进行了比较.目前中文词语相似度计算都较多地采用了《知网》,《知网》采用的是一种多维的知识表示形式,内容与结构较同义词词林更加丰富,文献[5]研究了利用义原特征结构的分类,计算不同义原的相似度来综合求解词的相似度.而文献[6]改进了义原的计算方式,文献[7]提出基于信息论的计算方法,文献[8]提出知识库描述语言对概念的描述具有线性关系,文献[9]提出位置相关的权重分配策略等.在这些研究中,都未考虑到同类义原中不同义原含有的区分度不同,不同义原的计算时应动态分配权重.本文利用逆概念频率动态地为不同义原定义权重,并根据动态的权重计算词的相似度.实验结果表明,该算法比固定义原权重的方法表现要优异.

1 词语相似度计算方法

1.1 相关理论

《知网》[10](英文名称How Net)是著名机器翻译专家董振东先生创建的一个网状的有机知识系统,它描述概念与概念之间的关系以及概念的属性与属性之间的关系,含有关系层次丰富而多样化的词汇语义知识.

在《知网》结构中有两个主要的概念是“概念”和“义原”,“概念”是用“义原”这种“知识表示语言”来描述的,“义原”是《知网》中不可分割的最小基本单位.一个词用一个或多个概念描述,一个概念用一组义原描述,词的相似度计算最终可以归结到义原的相似度计算.本文采用《知网》系统分析词的结构特征.

定义1 w为一个词,W为词的集合,即w∈W.

定义2 词语相似度Sim(w1,w2).给定两个词语w1和w2,词语相似度取值为一个0到1之间的实数,两者相同为1,完全无关为0[5].

定义3 语义距离Dis(w1,w2).给定两个词语w1和w2,以概念间结构层次关系组织的语义词典为基础,两个概念结构在给定的树状概念层次体系中存在的一条由上下位关系和同位关系构成的路径,把这条路径的长度称作语义距离,取值为正整数.

词语相似度和语义距离之间存在着反比关系[5],对于两个词语w1和w2,Dis(w1,w2)越大,则Sim(w1,w2)越小,反之亦成立.

定义4 c为《知网》中的一个概念,C为所有概念的集合,即c∈C.

定义5 B(ci)=w,ci∈C为概念ci用于表示词w.

定义6 F(w)为w对应的概念集合.给定一个词语w,在《知网》中被表示成一个或多个概念,称为词w的概念向量表示,表示为F(w)={c1,c2,…,ci,…,cn| ci∈C,B(ci)=w,1≤i≤n},有F(w)⊂C.

1.2 计算方法

1.2.1 词语相似度计算

对于两个词语w1和w2,文献[5]给出w1和w2的相似度定义为各个概念相似度的最大值,即

上述公式把词语相似度计算转换为概念相似度计算,而在《知网》中概念是由义原或极个别具体词组成的,因此计算词语的相似度最终可以转换为计算义原的相似度.

1.2.2 义原相似度计算

在《知网》中义原是从所有汉语词中提炼出可以用来描述其他词汇的不可再分的基本意义单元,义原根据上下位关系构成了一个树状义原层次体系,故可通过计算在义原树中的语义距离计算义原相似度,文献[5]假设两个义原在这个层次体系中的路径距离为d,得到这两个义原之间的相似度:

其中,p1和p2表示两个义原,d是p1、p2在义原层次体系结构中的路径长度,α是可调节参数.α的含义是当相似度为0.5时的词语距离值.

1.2.3 概念相似度计算

定义7 y为《知网》中的一个义原,Y为所有义原的集合,即y∈Y.

在《知网》中,一个概念ci是用一组义原描述式组合,其中义原描述式由义原与对应的符号构成.

基本义原描述式:用“基本义原”,或者“(具体词)”进行描述;

关系义原描述式:用“关系义原=基本义原”或者“关系义原=(具体词)”或者“(关系义原=具体词)”来描述;

符号义原描述式:用“关系符号基本义原”或者“关系符号(具体词)”加以描述;

定义8 P(ci)={y1,y2,…,yi,…,yn|yi∈Y,1≤i≤n}为概念ci对应的基本义原集合.

定义9 P1(ci)为概念ci的第一基本义原描述式中的基本义原集合,第一基本义原描述式即在概念ci出现的第一个基本义原描述式.有0≤|P1(ci)|≤1,且P1(ci)⊆P(ci).

定义10 P2(ci)为概念ci的其他基本义原描述式中的基本义原集合,除第一基本义原描述式外的基本义原描述式称为概念ci的其他基本义原描述式,有 P2(ci)⊆P(ci).

定义11 P3(ci)为概念ci的关系义原描述式中的基本义原集合,有P3(ci)⊆P(ci).

定义12 P4(ci)为概念ci的符号义原描述式中的基本义原集合,有P4(ci)⊆P(ci).综上有P(ci)= P1(ci)∪P2(ci)∪P3(ci)∪P4(ci)

文献[5]提出了一种计算实词概念相似度的方法,利用上述4个基本特征计算2个概念ci,cj的相似度:

1)第一基本义原描述式,这一部分的相似度记Sim1(y1,y2)(y1∈P1(ci),y2∈P1(cj)),计算方法见式(2);

2)其他基本义原描述式,这一部分的相似度记为Sim2(y1,y2),计算方法如下:

(i)列出P2(ci)和P2(cj)中的所有可能的配对情况,分别计算相似度,取相似度最大的一组,记录下来并从P2(ci)和P2(cj)中删除这组的2个元素.

(ii)重复执行(i),直至P2(ci)和P2(cj)为空.

(iii)计算(ii)中得到的相似度的算术平均值.

3)关系义原描述式,这一部分的相似度记为Sim3(y1,y2),计算方法是将关系义原相同的描述式分为一组,并计算其相似度,最后取所有组的算术平均值.

4)关系符号描述式,这一部分的相似度记为Sim4(y1,y2),计算方法是将关系符号相同的分为一组,其值是对应的两个集合,按2)中计算方法计算这2个集合的相似度,最后取各个特征的相似度的算术平均值.

又因为主要部分的相似度值对于次要部分的相似度值起到制约作用,所以如果主要部分相似度比较低,那么次要部分的相似度对于整体相似度所起到的作用也要降低.

于是两个概念语义表达式的整体相似度记为:

其中,βi(1≤i≤4)是可调节参数,且有β1+β2+β3+β4 =1,β1≥β2≥β3≥β4.后者反映了Sim1到Sim4对于总体相似度所起到的作用依次递减.

2 基于逆概念频率(inverse concept frequency,ICF)的词语相似度计算

定义13 基本义原区分度.I(ci,yj)(yj∈P(ci))为基本义原yj在概念ci中的区分度,即概念ci区分于其他所有概念的因素中,yj义原在P(ci)中所占的权重.

定义14 基本特征区分度.I(ci,Pj(ci))(1≤j≤4)为基本特征j(j为正整数,1对应第一基本义原描述式,2对应其他基本义原描述式,3对应关系义原描述式,4对应关系符号描述式)在概念ci中的区分度.有I(ci,Pj(ci))=max{I(ci,yk)(yk∈Pj(ci))}.

从区分度的定义可以得出,利用Pj(ci)(1≤j≤4)对应的4个基本特征计算2个概念相似度时, Simj(y1,y2)(1≤j≤4)所占的权重βj与I(ci,Pj(ci))越接近计算的结果越理想,即|βj-I(ci,Pj(ci))|的值应该越小越好.

对于不同的概念ci,I(ci,Pj(ci))(1≤j≤4)的值是不定的.而传统的义原权重计算方法计算不同概念对的相似度时采用固定的义原权重,这必然导致|βj-I(ci,Pj(ci))|的结果是波动的.这种波动是会影响到词的相似度计算.

2.1 ICF

本文借鉴TF-IDF权重计算方法[11],提出使用ICF计算义原在概念中的权重,ICF权重计算方法是一种统计方法,其主要思想是使用义原出现在概念的频率来权衡该义原区分概念的能力,义原的重要性随着它在概念库中出现的频率成正比下降.

定义15 ICF是一个义原区分度的普遍性的度量.对于某一义原pi的ICF,可以由《知网》概念的总数目除以该义原pi出现在Pj(ci)(ci∈C,1≤j≤4)上的概念总数目,再将得到的商取对数得到.

其中pi为《知网》中的某个义原,j为义原位置信息,C为《知网》概念集合.

定义16 ICF_C(ci,yj)(yj∈P(ci))为基本义原yj在概念ci中的ICF权重.对于一个概念ci而言,其基本义原的ICF权重就是该义原在《知网》中的ICF权重,故有

ICF_C(ci,yj)=ICF(yj,k)(对于k,有yj∈

Pk(ci)).

定义17 ICF_C(ci,Pj(ci))=max{ICF_C(ci, yk)(yk∈Pj(ci))}为各个基本特征概念ci中的ICF权重.

2.2 概念相似度的计算

不同于文献[5]中使用固定权值计算相似度,使用ICF计算特征结构权值进而计算整体相似度,需要消除主要部分相似度值对于次要部分相似度值的牵制作用,4类特征结构的相似度对于总体的相似度所起到的作用决定于ICF,并不存在递减关系.于是,本文采用以下公式(4)计算两个概念语义表达式的整体相似度:

其中,βi(1≤i≤4)是据ICF计算得出的权重参数,且有β1+β2+β3+β4=1.

2.3 基于ICF的词语相似度计算

对于概念c∈C,∀ci∈C(i=1,2,…,|C|),使用式(4)计算概念c和ci的相似度Word_Simi(c,ci).假设c有n(0＜n≤4)个特征结构p11,p12,…,p1n,ci有m(0＜m≤4)个特征结构p21,p22,…,p2m.

算法:基于ICF的词语相似度计算算法

输入:词语W

输出:按与词语W相似度从高到低排列的《知网》词集

方法:

1)对于在义原树中的每一个义原yi,分别计算基本义原yi出现在第一义原、其他基本义原、关系义原、关系符号位置上的次数.

2)对于在《知网》中的每一个概念ci(i≥1),再对于在概念ci中的每一个特征结构Pj,依据定义17计算Pj的ICF值并作归一化处理,记作ICFPj.

3)对于在《知网》中的每一个概念ci,计算概念ci和概念c的相似度.

4)依据公式1)和第3)步的结果计算W和《知网》中所有词语的相似度.

5)按相似度从高到低排序,最终得到有序结果集.

证明算法有效性时,本文提出一种假设,假设概念集合C中的元素ci对应的I(ci,Pj(ci))(1≤j≤4)是不相同的,且存在一个值α(0＜α≤1)使得对于两个不同的概念ci和cj,有I(ci,Pk(ci))-I(cj,Pk(cj))≥α(∀1≤k≤4).这样假设是符合人们对词语的直觉的.

证明 在概念个数|C|较多的情况下基于ICF的词语相似度计算比固定权重算法改进了概念的相似度计算.

对于概念的4个基本结构的权重βj(1≤j≤4),即|βj-I(ci,Pj(ci))|的值应该越小越好.现将βj固定为4个常数αj(1≤j≤4),基于上述假设,对于概念ci使得|αj-I(ci,Pj(ci))|≥α/2.

根据上式说明存在一个正整数N,当|C|≥N时有|βj-I(ci,Pj(ci))|＜α/2,这就说明了在|C|足够大的前提下,基于ICF的词语相似度计算比固定权重算法改进了概念的相似度计算.

例1 给定词语C=“军事”,在《知网》中,C的概念解释为affairs|事务,military|军,令Ci=“军管会”, Ci的概念解释为institution|机构,military|军.按2.3节的计算方法,经过归一化处理后C的ICF=[0.229 6,0.7,0.01,0.05],C和Ci的基本义原、其他基本义原、关系义原、关系符号相似度数组为[0.231 6,1,1, 1],因此Sim(C,Ci)=0.823 6.使用文献[5]的算法,并结合文献[6]对义原相似度计算的改进,得出Sim (C,Ci)=0.231 6.因此,可以看出,本文在某些区域方面极大地提升了相似度计算的精度.

2.4 多义词处理

中文词汇中,存在着一词多义的现象,在《知网》中体现为一个词语对应多个概念.对于一词多义的词语其根据上下文来判断具体的释义,《知网》的构建已经提出了处理一词多义的方法[10].

在《知网》的概念属性集中存在E_C属性,该属性解释为例子属性.例子属性用途在于为消除歧义提供可靠的帮助.这里试以“打”的两个义项为例,一个义项是“buy|买”,另一个是“weave|辫编”.

W_C=打,

G_C=V,

E_C=～酱油,～张票,～饭,去～瓶酒,醋～来了,

DEF=buy|买,

W_C=打,

E_C=～毛衣,～毛裤,～双毛袜子,～草鞋,～一条围巾,～麻绳,～条辫子,

G_E=V,

DEF=weave|辫编.

设要判定的歧义语境是“我女儿给我打的那副手套哪去了”.我们通过对“手套”与“酱油”等的语义距离的计算以及跟“毛衣”等的语义距离的计算的比较,将会得到一个正确的歧义判定结果.

文献[9]则取两个词对应的概念对中概念相似度的最大值作为两个词的相似度.与文献[10]相比,则没有考虑上下文对词义的影响,本文认为文献[10]中的消除歧义的方法充分利用上下文对词义的影响,而一词多义的产生也是由于上下文的不同而产生.故本文认为使用文献[10]的方法来消除歧义更为合适.

由于《知网》还未完善概念中E_C属性,且在现有的《知网》中概念的E_C属性值还未公布.故本文无法对一词多义的处理结果进行实验分析.

3 实验结果及分析

3.1 实验结果

本文使用Visual Studio 2008在Window操作系统上实现了基于ICF的义原权重计算,采用式(1)计算词语相似度,基于义原在义原层次树中的深度和密度[5]计算义原相似度.

实验选取了部分具有代表性的词汇,采用6个分类词“财经”、“教育”、“美食”、“政治”、“军事”、“体育”作为实验对象,对《知网》中的词汇进行相似度计算,并按相似度从高到低排序.由于与分类词相关的词语总数数量相差甚远,常用的准确率、召回率对不同的分类词无法选取统一的标准,故我们使用图表和准确率、召回率结合的形式描述实验结果.图1中,每个分类词使用5～6个点作为阶段性结果统计点,其中,点(x,y)表示在实验结果的词集中,排名前x词集的准确率或召回率.

实验将本文算法(方法1)、文献[6]算法(方法2)和文献[5]算法(方法3)3种算法比较,从图1可以看出本文算法在部分中心词汇取得了不错的扩展效果.

3.2 实验结果分析

本文基于ICF权重计算方法是基于这样的一个假设:对区分概念最有意义的义原应该是那些在其他概念的相应义原位置中出现次数少的义原,它们区分概念的能力较大.这种假设是符合人们平时的认知的.应用ICF完成对义原权重的调整,取代了传统实验中义原固定权重,避免计算时权重与实际区分度产生波动.从实验结果可以看出,利用ICF完成对义原权重的调整抑制了这种波动的产生.

但ICF只是对义原实际区分度的一种假设,本质上是一种试图抑制噪声的加权,并且单纯地认为概念频率小的义原就越重要,概念频率大的义原就越无用,显然这不是完全正确的.比如概念“美食”的义原是“食品”“好”“良”,“食品”在第一基本义原结构中出现次数是364,“好”在其他基本义原结构中出现次数是263,概念“美食”在计算义原权重时更趋向于“好”而非“食品”,这导致对“美食”进行词的扩展时,很多和“好”相关的词具有较高的相似度,导致局部实验结果不够理想.文献[6]中的算法在“美食”概念上表现得较为不理想,是由于它忽略了第一义原和其他义原的区别,从《知网》的结构上来看,这样在计算词的相似度的时候会导致对褒贬义的词较为敏感,从实验结果可以看出,其排序较前的词都是具有义原“好”、“良”等相近意思的词.

4 结 论

图1 准确率和召回率Fig.1 Accuracy rate and recall rate

基于《知网》进行词的扩展,充分利用概念描述结构,考虑义原代表所在概念的信息量,根据义原的ICF赋予义原权重.在词的相似度计算实验中,采用将概念的4个义原基本结构权重分别与4个义原基本结构相似度相乘,得到概念与概念的相似度,最后采用文献[5]中公式(1)得到相似度从高到低排列的词集.实验结果证明,与分类词相似的词集整体上得到了不错的效果.某些分类词的扩展效果有待改善,原因在于,基于ICF计算义原权重算法对概念解释的依赖性过大,随着时代的进步和汉语的演化,《知网》中某些词语的义原解释和现实生活中人们所理解的含义有偏差.在今后的研究工作中,重点在于如何提高基于ICF计算义原权重算法的鲁棒性,使算法适用于更多的词汇,并把该项研究成果应用于文本分类等领域.

[1] 鲁松.自然语言处理中词相关性知识无导获取和均衡分类器构建[D].北京:中国科学院研究生院计算技术研究所,2001.

[2] Rodríguez M A,Egenhofer M J.Determining semantic similarity among entity classes from different ontologies [J].Knowledge and Data Engineering,IEEE Transactions,2003,15(2):442-456.

[3] Budanitsky A,Hirst G.Semantic distance in Word Net:an experimental,application-oriented evaluation of five measures[C]∥Workshop on Word Net and Other Lexical Resources.Pennsylvania:The Pennsylvania State University,2001:1-6.

[4] Lee W N,Shah N,Sundlass K,et al.Comparison of ontology-based semantic-similarity measures[C]∥AMIA Annual Symposium Proceedings.Bethesda MD,USA:American Medical Informatics Association,2008:384-388.

[5] 刘群,李素建.基于知网的词汇语义相似度计算[J].中文计算语言学,2002,7(2):59-76.

[6] 江敏,肖诗斌,王弘蔚,等.一种改进的基于《知网》的词语语义相似度计算[J].中文信息学报,2008,22(5):84-89.

[7] 刘青磊,顾小丰.基于《知网》的词语相似度算法研究[J].中文信息学报,2010,24(6):31-36.

[8] 王小林,王义.改进的基于知网的词语相似度算法[J].计算机应用,2011,31(11):3075-3077.

[9] 朱征宇,孙俊华.改进的基于《知网》的词汇语义相似度计算[J].计算机应用,2013,8:2276-2279,2288.

[10] 董振东,董强.知网[DB/OL].[1999-06-01].http:∥www.keenage.com/.

[11] 刘赫,刘大有,裴志利,等.一种基于特征重要度的文本分类特征加权方法[J].计算机研究与发展,2009,10: 1693-1703.

Word Similarity Computing Based on Inverse Concept Frequencies

SUN Jing,ZHANG Dong-zhan*
(School of Information Science and Engineering,Xiamen University,Xiamen 361005,China)

The word similarity computation plays an important role in service selection,natural language processing,and literature retrieval.Current researches of word similarity are generally based on How Net.By analyzing the structure of How Net,we present an idea that the weight of four basic structures of the concept should be dynamically generated during computing the similarity between two words and a method of calculating the weight of primitive based on the frequency.We compute the ICF of each basic primitive in the first basic primitive,other basic primitives,relation primitive and mark primitive through concept structure analyzing,and take the maximum ICF as the ICF of the basic structure.Then we compute the word similarity by using dynamic ICF obtained as the weight of four basic structures.Experimental results show that the accuracy of word similarity calculation is effectively improved.The average accuracy of former 160 words rises from 30.74%to 72.28%,and the recall rises from 15.87%to 49.64%.

How Net;word similarity;inverse concept frequency;primitive weight

10.6043/j.issn.0438-0479.2015.02.018

TP 391.1

A

0438-0479(2015)02-0257-06

2014-04-29 录用日期:2014-08-25

国家自然科学基金(61303004);福建省自然科学基金(2013J05099)

*通信作者:zdz@xmu.edu.cn

孙晶,张东站.基于逆概念频率的词语相似度计算[J].厦门大学学报:自然科学版,2015,54(2):257-262.

:Sun Jing,Zhang Dongzhan.Word similarity computing based on inverse concept frequencies[J].Journal of Xiamen University:Natural Science,2015,54(2):257-262.(in Chinese)