基于角度—相似度转换模型的义原相似度计算

，

(浙江工业大学 计算机科学与技术学院，浙江 杭州 310023)

基于角度—相似度转换模型的义原相似度计算

黄洪，屠肖龙

(浙江工业大学 计算机科学与技术学院，浙江 杭州 310023)

义原的相似度是基于《知网》计算词语、句子相似度的基础.最早的义原相似度计算方法是刘群等提出的根据义原距离转换为义原相似度的方法，之后许多研究者在计算公式中引入了其他影响相似度计算的因素.这些因素本质上都可以由父节点深度、父节点到第一个义原的深度和父节点到第二个义原的深度等三个基本因素组成.将这三个因素作为基本变量,分析变量对义原相似度的影响方式并构建角度—相似度转换模型，实现了根据义原角度转换为义原相似度的方法.最后，通过实验分析比较新方法与同类方法在区分度、正区分度和距离误差上的优势，验证了其合理性.

义原相似度；角度—相似度转换模型；知网

相似度计算是人工智能和自然语言处理领域的一个研究重点，词语相似度普遍应用于信息抽取、文本聚类[1]、词义排歧、机器翻译和自动问答等领域[2-3].在计算词语相似度时通常有两种经典的方法；第一种是统计分析的方法，该方两个词语的相似度[4-5].另一种是基于词语分类体系的方法，该方法需要依赖于某种知识库，目前英文世界知识库研究较多的是Wordnet，中文世界研究较多的是《知网》[6]和《同义词词林》.

《知网》是由我国著名的机器翻译专家董振东老师耗费十多年时间建立的一个知识库.它能够以概念的形式来描述汉语的词以及词所对应的英文，并且对概念具有的属性及概念相互间的关系做了详细的描述.《知网》中有两个主要的概念：“概念”和“义原”.其中，“概念”表示词语语义，一个概念只能表示某个词语的一种语义，但是一个词语可能由一个或者两个及以上的概念组成.“概念”用一种特定的“知识表示语言”来描述，这种“知识表示语言”又是由“义原”作为基本描述语言来表示.“义原”是《知网》用于描述“概念”的最小的意义单位.《知网》中一共确定了一千五百多个义原，分为：Event|事件、Entity|实体、Attribute|属性、AValue|属性值、Quantity|数量、QValue|数量值、SecondaryFeatlure|第二特征、Syntax|语法、EventRole|动态角色和EventFeatures|动态属性等10个大类.此外义原与义原之间又存在各种不同的关系，在《知网》里面总共定义了义原之间的8种关系，关系之间组合在一起构成了一个复杂的关系网络.其中义原间的上下位关系是最主要的一种关系，所有的义原依照上下位关系可以组成一个树状的义原层次体系结构，绝大多数学者根据该层次结构[7]来计算义原的相似度.

1 义原相似度计算方法

刘群[8]等首先给出了根据知网义原树计算义原相似度的方法，该方法首先计算义原之间的距离，然后将义原之间的距离转换为义原间的相似度.之后又出现了许多改进的公式：如李峰[9]等对义原深度的考虑，夏天[10]等对义原重合度的考虑以及江敏[11]等对义原深度差的考虑.几种典型的改进算法如下：

夏天等结合相异度、重合度和义原深度对义原相似度的影响，从信息论的角度给出了义原间相似度的计算式为

式中：spd(P1,P2)为义原P1，P2公共父节点的深度；depth(P)为义原P的深度.

李峰等在计算过程中引入了节点深度对义原相似度的影响，给出的计算式为

sim(P1,P2)=

式中：sim(P1，P2)为两个义原之间的相似度；α为常数，代表相似度为0.5时义原之间的距离；distance(P1，P2)为义原之间的距离；min(depth(P1)，depth(P2))为两个义原深度的较小值.

江敏等的义原相似度计算方法中考虑了义原深度差对义原相似度的影响，认为距离相同的两个义原之间的层次差越大，相似度越小，最终给出义原相似度计算式为

式中：sim(P1，P2)为两个义原之间的相似度；α为常数；|depth(P1)-depth(P2)|为两个义原之间的层次差；depth(P)为义原P的深度.

分析这些因素后发现深度和深度差是两个复杂因素，而复杂因素是基本因素综合作用的体现，其对相似度的影响可以转化为基本因素对相似度的影响.因此可以利用模型的方法来综合各个因素对相似度计算的影响，剖析各个因素的几何意义，最后从基本因素出发计算义原相似度.

2 基于角度—相似度转换模型的义原相似度计算方法

2.1 问题分析

假设点O为树根，点P1，P2分别是两个需要计算相似度的义原，P3是P1，P2的公共父节点中最深的节点.总结之前影响义原相似度的因素包括：义原P1和P2之间的距离、义原P1和P2之间的深度差、公共父节点P3的深度、义原P1的深度以及义原P2的深度等.这些影响因素被归结到三个基本因素上：因素一，节点P3的深度；因素二，P3到P2的深度；因素三，P3到P1的深度.基于义原树结构的相似度计算有如下几个特点：

1)P1和P2之间的距离越大，相似度越小；当距离趋于非常大时，相似度趋于0.

2) 义原P1和P2的公共父节点P3深度越大，P1和P2的相似度越大；当深度趋于非常大时，相似度趋于1.

2.2 模型构建

义原在知网中以树形结构组织在一起，在计算义原之间的相似度时，主要有4个关键的点：树根节点、最深公共父节点以及两个义原节点.为了简化模型结构首先摘除其他节点，形成“丫”字形结构，模型的构建过程如下：

确立直角坐标系，在直角坐标系的x轴上确定节点P3，原点O到P3的长度为根节点到最深公共父节点的节点数；给定一个固定的β角，令P3为β的顶点，x轴平分β角，P3P1是β角的一条边，长度为义原P3到义原P1的节点数(不包括P3)，P3P2是β角的另一条边，长度为义原P3到义原P2的节点数(不包括P3)；连接O，P2形成边OP2，连接O，P3形成边OP3，两条边之组成一个夹角α，如图1所示.

图1 义原相似度的角度—相似度转换计算模型Fig.1 Angle similarity transformation model of sememe similarity

该模型中O点对应的是义原树树根，P1，P2分别是两个需要计算相似度的义原，P3是P1，P2的公共父节点中最深的节点.角P2OP1为α，角P2P3P1为β.

定义1OP3长度为从根节点O到节点P3经过的所有节点数目(包括节点O和P3)，记为spd(P1,P2).

定义2P3P2，P3P1长度分别为从节点P3到节点P2，P1经过的所有节点数目，不包括节点P3，分别记为dis(P3,P2)，dis(P3,P1).

α角随着义原P1，P2距离的增大而增大，表示两个义原的相异部分.但随着距离的无限增加，α角只会无限接近β角但不会大于β角，因此相似度计算式可形式化为

(1)

式中α/β为两个义原的相异程度，通过1-α/β就可以得到它们的相似程度.

2.3 模型检验

分析并比较影响相似度的因素与影响模型计算的因素，建立因素之间对应的关系，检验模型的合理性.

2.3.1 父节点深度

如果义原树中的spd(P1,P2)(父节点P3的深度)越长，则从根节点定位到P3节点需要走过的节点数越多，包含的信息也越详细，因此义原P1和义原P2的公共信息量[12]也越多，根据Dekang Lin的信息论义原相似度计算方法，义原相似度就会变大，反之则会变小.

在spd(P1,P2)减小，dis(P3,P2)和dis(P3,P1)不变化的情况下，α便会增大(图2)，根据式(1)，sim(P1,P2)就会减小.

图2 父节点深度降低Fig.2 Reduce the depth of super point

在spd(P1,P2)增大，dis(P3,P2)和dis(P3,P1)不变化的情况下，α便会减小(图3)，根据式(1)，sim(P1,P2)就会增大.

图3 父节点深度增长Fig.3 Increase the depth of super point

2.3.2dis(P3,P2)和dis(P3,P1)

在spd(P1,P2)不变的情况下，dis(P3,P2)和dis(P3,P1)增长意味着定位到P1，P2需要走过更多的节点，完整描述P1，P2需要更多的信息量，根据Dekang Lin[13]信息论公式，分母增大意味着相似度的下降.

在dis(P3,P2)和dis(P3,P1)增长，spd(P1,P2)不变化的情况下，α便会增大(图4)，根据式(1)，sim(P1,P2)就会减小.

图4 义原深度增长Fig.4 Increase the depth of sememe

在dis(P3,P2)和dis(P3,P1)减小，spd(P1,P2)不变化的情况下，α便会减小(图5)，根据式(1)，sim(P1,P2)就会增大.

图5 义原深度降低Fig.5 Reduce the depth of sememe

2.3.3 深度差

深度差是指两个义原深度之间的差，通常情况下，深度差越大，义原之间的差异越大.但在基于义原树的3个基本因素(spd(P1,P2)为P1,P2公共父节点P3的深度;dis(P3,P1)为P3,P1之间的长度;dis(P3,P2)为P3,P2之间的长度)中并不包含深度差这个因素，因为它是一个综合性的因素.当义原之间的深度差改变时，必然会导致depth(P1)或者depth(P2)改变，对应于基本因素dis(P3,P2)和dis(P3,P1)也会变化，因此，不将深度差作为一个基本因素.如图6所示，depth(P2)改变引起深度差的改变.

图6 义原深度差改变Fig.6 Change of depth difference between two sememes

2.4 计算公式

基于以上模型得出计算式为

(2)

(3)

α=ω+θ

(4)

(5)

式中：ω为α被横轴截的上半部分角；θ为下半部分角；β为一个人为测定的值，经过人工试验的测试，当β取π/2时能够较好的符合主观感受.

2.5 义原直系情况下模型及计算公式

当P3与P2或P1中的某一个重合时，即义原P1，P2之间是直系关系，不符合图1建立的模型，无法使用以上公式计算.

直系情况下，两个义原之间是父子关系，两者之间没有形成夹角(图7)，义原P1是义原P2的父节点，两者之间的深度差就是义原之间的相异距离(父节点到子节点的距离)，而两个义原之间的公共部分就是重合距离(原点到父节点的距离)，这比较符合夏天等从信息论的角度计算义原相似度的思想，因此选择夏天等的义原相似度计算方法作为直系情况下的补充.

图7 直系关系的义原模型图Fig.7 The model of direct relation sememe

3 实验分析

根据以上方法，实现了一种新的对知网义原相似度的计算方法，同时与其他学者的计算结果在多个维度上进行了比较，包括区分度、均方差和正区分度.表1为各个方法的计算结果.

表1 不同方法的义原相似度计算结果Table 1 The calculation results of different sememe similarity means

刘群等首次给出了义原距离转化为义原相似度的方法，对义原相似度计算有重要意义，但计算结果有不足的地方.从表1中可以发现：计算结果比较粗糙，结果的区分度比较低，比如“生物”与“无生物”“牲畜”与“禽”“兽”与“人”等相似度一样，10项测试数据中有7项得到的结果相同.

江敏等在计算过程中考虑了义原间深度差的影响，更加全面.分析表2,3中的数据认为其能够很好地区分不同词语对的相似度，不足的是计算结果总体上略微偏高.新方法的结果基本都处于夏天方法、刘群方法的计算结果和江敏方法的计算结果之间，比较折中、合理，更符合主观判断.

定义3区分度为算法对结果的区分能力，是可区分的结果对数与测试对总数的比值.

表2 各个相似度计算方法的区分度表Table 2 Every sememe similarity mean’s discriminative

从表2可以看出新方法的计算结果能够在区分度上有较好的效果.

表3 各个方法与主观判断之间的比较Table 3 The comparison of subjective result and mean’s calculation result

距离误差公式为

式中：M为待计算结果；I为主观结果.各个方法的结果与调研结果之间的距离误差如表4所示.

表4各个方法与主观之间的距离误差

Table4Distanceerrorbetweensubjectiveresultandmean’scalculationresult

刘群方法夏天方法李峰方法江敏方法新方法0．170．230．220．300．23

由表4可知：刘群方法最优，新方法与夏天方法和李峰方法的方法不相上下，江敏方法的计算结果略有偏高.

定义4正区分表示计算结果中结果的大小关系与对应的主观判断结果中结果的大小关系相同的区分.

正区分在实际应用中可能会很有用.因为有时候用户并不需要得到相似度的准确值，只需要知道相似度计算结果之间的大小关系就足够了.比如当用户输入一个关键词查询时，用户不需要知道呈现在他面前的结果和他输入的关键词之间的相似度值，他看到的只是一系列结果根据相似度大小关系的排序，只有根据用户浏览的顺序按相似度从高到低对结果进行排序，用户才能较快地找到自己的答案，因此正确的相似度大小排序也很重要，正区分数越多，排序越准确.区分度代表了算法区分不同结果的能力，而正区分度则体现了算法能够正确区分结果大小的能力.

各个计算结果相对于主观的正区分数计算步骤如下：

步骤1将主观判断结果按从小到大的顺序排列，第十项“物质”和“饮品”相似度最小排在第一个，“牲畜”和“禽”相似度最大，排在末尾,按行号排完序的结果(标记为序列S)为

主观排序S:10-9-1-3-5-6-8-7-4-2

步骤2对各个方法也按从小到大的顺序排列,无法区分的放在小括号中并用斜杠隔开(括号中用‘/’隔开的项表示指定方法无法区分的项，以下同)，各个计算结果的排序结果为

1) 9-10-7-(1/2/3/4/5/6/8)，为刘群方法.

2) 9-10-7-1-3-(4/5/6/8)-2，为夏天方法.

3) 9-10-7-1-(3/4)-(5/6/8)-2，为李峰方法.

4) 9-10-7-4-1-3-(5/6/8)-2，为江敏方法.

5) 9-10-7-1-3-4-(5/6/8)-2，为新方法.

当对所有方法排完序后，方法的计算结果与主观结果之间的相对逆序就是两个序列之间大小关系不同的数据对对数.比如在主观排序中10号排在9号之前，因此10号的相似度要小于9号的相似度.而在1)刘群方法计算结果排序当中10号排在9号之后，10号的相似度要大于9号.因此，9号与10号就是在刘群方法的计算结果与主观结果之间大小关系不同的一对数据，找出所有这样的数据对，去减所有可能的数据对对数，就可以得到两个结果序列之间大小关系相同的数据对对数，也就是正区分数.为了便于寻找这种数据对，再进行第三步处理.

步骤3对每一个方法，按从左到右的顺序写出每一位在主观结果排序S中的位置号，组成新的序列并记为S-方法序号，比如1)中的第一位是9,而9在S中排在第二位，所以新的序列第一位是2；1)中的第二位10位列S中的第一位，因此新序列的第二位是1；1)中的第三位7位列S中的第八位，因此新序列的第三位是8；1)中的项(1/2/3/4/5/6/8)对应在S中的(3/10/4/9/5/6/7)，最后组成的新序列S-1)：2-1-8-(3/10/4/9/5/6/7).所有的新序列如下：

S-1):2-1-8-(3/10/4/9/5/6/7)

S-2):2-1-8-3-4-(5/6/7/9)-10

S-3):2-1-8-3-(4/9)-(5/6/7)-10

S-4):2-1-8-9-3-4-(5/6/7)-10

S-5):2-1-8-3-4-9-(5/6/7)-10

步骤4对每一个新的序列，计算数大小关系与下标大小关系相同的数据对对数(若两个数据对中包含相同的数，则视为同一对，计入一次；若数据对中的两个数无法区分，不计入).比如S-1)序列中对数据2和1进行比较：数的大小关系是2大于1，下标关系是数2的下标小于数1的下标，两者相反，代表计算方法得出的相似度大小关系与主观的不相同，不是正区分.最后各个方法的正区分计算结果如下：

S-1):18对

S-2):33对

S-3):32对

S-4):31对

S-5):33对

从正确区分数看：新方法计算结果的正确区分略好于其他几种计算结果(表5).

经过观察发现：夏天方法、李峰方法以及新方法计算结果的正区分之所以比江敏方法的计算结果要高，是因为江敏方法的计算结果与主观之间的结果偏差更大.比如在计算“生物”与“无生物”的相似度以及“动物”与“牲畜”的相似度时，江敏方法的计算结果显示前者的相似度为0.865，而后者才0.827，即“生物”与“无生物”的相似度比“动物”与“牲畜”相似度还要高.但实际上，“动物”与“牲畜”应该比“生物”与“无生物”更相似，因为“动物”和“牲畜”都是动物而且也都是生物，两者存在很多动物以及生物的共同特性，相似的地方很多；但是“生物”与“无生物”是两种截然不同的东西，很难找出两者有何相似的地方.因此相比于后者，“动物”与“牲畜”之间相似的地方更多更相似，相似度也应该更高.在主观结果中可以看到，“生物”和“无生物”之间的相似度为0.458，“动物”和“牲畜”之间的相似度为0.696，很好的证明了这一点.同时，在夏天方法、李峰方法以及新方法的计算结果中，也都符合“动物”与“牲畜”之间的相似程度比“生物”与“无生物”之间的相似程度更高这一结论，因此夏天方法、李峰方法以及新方法的计算结果在区分度上比江敏方法的计算结果有更好的表现.

通过以上对各个方法的区分度、正区分度和距离误差的结果分析，排序后获得表5.

表5 所有义原相似度计算方法的各指标排名Table 5 The ranking criteria of the sememe similarity computing method

从表5可以看到：刘群方法在均方差上最接近人的主观判断，但是在区分度和正区分度上与主观符合比较一般.新的方法在区分度和正区分度上较为符合人的主观判断，均方差上与其他方法比较也有不错表现，具有更好的合理性.

为了进一步验证方法的有效性，在《知网》义原中另外抽取了十对词语进行实验分析，并对不同的方法在各个指标上进行了排序，实验结果如表6所示.

表6 实验二中不同方法的义原相似度计算结果Table 6 The calculation results of different sememe similarity means in the second experiment

从表7可以看出：与其他同类方法相比，新方法的优势在于其区分度和正区分度最高，在实际应用中表现出来的是对结果的排序更准确.其次，在距离误差上，新方法同夏天方法、李峰方法有相同程度的距离误差，且要好于江敏方法.虽然新方法的距离误差稍差于刘群方法，但由于刘群方法的区分度和正区分度最低，与新方法相差较多，因此新方法总体上要优于其他同类方法，证明了新方法更有合理性和有效性.

表7 所有义原相似度计算方法的各指标排名Table 7 The ranking criteria of the sememe similarity computing method in the second experiment

4 结 论

《知网》是一个集合了丰富的世界知识的体系，在自然语言处理领域有广泛的应用.义原是《知网》描述概念最小单位，是基于知网进行词汇语义相似度计算、文本相似度计算等学术研究的基础.新的方法通过“角度—相似度”模型模拟义原距离的变化对相似度的影响，并提取出三个最基本的义原相似度影响因素,这些因素通过数学模型组合在一起形成相似度的计算方法.最后通过主观判断和三个评价指标解释了方法的有效性和合理性.除了义原距离对相似度的影响之外，义原的区域密度也是一个影响相似度的因素.通常来说，义原所处的区域密度越大，则对义原的描述越细致，包含的信息量越多.而根据Dekang Lin的信息论方法，词语的信息量是计算词语间相似度的基础，因此，如何将密度因素和信息量融合到新方法中需要在今后的研究中继续努力.

[1] 张科.基于《知网》义原空间的文本相似度计算研究与实现[D].重庆：重庆大学,2013.

[2] 崔淑洁.句子相似度算法研究及其在中文问答系统中的应用[D].杭州：浙江工业大学，2014.

[3] 王方红,黄文彪.孪生支持向量机的特征选择研究[J].浙江工业大学学报,2016,02:146-149.

[4] 王小林,杨林,王东.基于知网的新词语相似度算法研究[J].情报科学,2015(2):67-71.

[5] 黄洪,丰旭.涉及地名的句子相似度计算方法的改进[J].浙江工业大学学报,2015,43(6):624-629.

[6] 董振东,董强.知网和汉语研究[J].当代语言学,2001(1):33-44.

[7] 袁晓峰.《知网》义原相似度计算的研究[J].辽宁大学学报(自然科学版),2011(4):358-361.

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

[9] 李峰,李芳.中文词语语义相似度计算——基于《知网》2000[J].中文信息学报,2007,21(3):99-105.

[10] 夏天.汉语词语语义相似度计算研究[J].计算机工程,2007,33(6):191-194.

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

[12] 魏韡,向阳.基于2008版《知网》的词语相似度计算方法[J].计算机工程,2015(9):215-219.

[13] LIN Dekang．An information-theoretic definition of similarity semantic distance in Wordnet[C]//Proceedings of the Fifteenth International Conference on Machine Learning Ec．San Francisco：Morgan Kaufmann Publishers，1998:296-304.

Thecalculationofsememesimilaritybasedonangle-similaritytransformationmodel

HUANG Hong, TU Xiaolong

(College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China)

Sememe similarity is the basis for computing similarity of words and sentences in the “Hownet”. The earliest sememe similarity calculation method was proposed by Liu Qu. In this method, the sememe distance was transformed into sememe similarity. After that, many researchers have introduced other factors that influence similarity calculations in the calculation formula. These factors essentially consists of three preliminary parts: depth of common father point, distance between the father point and the first sememe, and distance between the father point and the second sememe. Taking these three factors as basic variables, the effect of these factors on sememe similarity was analyzed and an angle-similarity transformation model was constructed to transform sememe angle into sememe similarity. Finally, the experiments analyzed the advantages on distinction, positive distinction and distance error between new methods and similar methods. and verified its rationality.

sememe similarity; angle-similarity transformation model; Hownet

2017-02-17

黄 洪(1964—)，男，江西丰城人，教授，研究方向为软件开发、智能电子商务和自然语言处理等，E-mail：huanghong@zjut.edu.cn.

TP391

A

1006-4303(2017)06-0597-07

(责任编辑：陈石平)