基于编辑距离结合词性的词相似度算法
基于编辑距离结合词性的词相似度算法
梅筱，刘海鹏
（北京邮电大学智能科学与技术研究中心，北京 100876）
摘要：现有的词语相似度算法大多依赖于外部知识（知网、同义词词林等），导致其只能解决外部知识以内的词语，或者单纯依赖词语本身的某一种特性，准确率不足。本文提出了一种在最小编辑距离的基础上结合词性的相似度算法，打破了外部知识的局限性，并提高了单纯依赖最小编辑距离计算相似度的准确率。
关键词：模式识别与智能系统；词共现；最小编辑距离；词性；相似度
中图分类号：H08
Word similarity algorithm based on Edit Distance and the
Parts of Speech
Mei Xiao, LIU Haipeng
(Intelligence Science and Technology Research Center of Beijing University of Posts and
Telecommunications, Beijing 100876)
Abstract: The current word similarity algorithms are dependent on external knowledge (Hownet, TongYiCi CiLin, etc.), leading to only words within external knowledge can be resolved, or rely solely on one feature of words, the accuracy is insufficient. This paper presents a similarity algorithm based on minimum edit distance in combination of parts of speech, it breaks the limitation of external knowledge, and increased the accuracy of which relies solely on minimum edit distance.
Key words: Pattern Recognition & Intelligent Systems; word co-occurrence; minimum edit distance; parts of speech; similarity
0引言
认知科学的研究表明，人类在语言习得过程中，其他认知通道(如视觉)的信息具有重要的辅助作用。母亲在开始教孩子说话时总会借助一些身边的玩具，比如一个皮球，在重复地和孩子说“球”等简单的指代性话语时，也让孩子通过眼睛、耳朵、手等感觉器官进行看、听、摸等感知活动，帮助孩子获得对“球”这个词的理解。而视觉信息对语言习得的帮助尤其大，最近有认知科学的研究表明，人们在提取物体语义知识时都会同时激活该物体的视觉表象[1]。
目前，越来越多的应用需要将感知数据翻译为自然语言[2]。视频游戏中自动的体育解说员，将空间关系和虚拟运动员的动态映射成语言。汽车的自动导航系统在地图导向和地理位置数据的基础上说出正确的前进方向。另外，随着机器人工业的发展，未来的家用机器人在新的环境需要对新的物体进行识别[3]。它可以问主人几个简单的问题，根据主人的回答来排除多余的可选项，最终进行确认分类。受到人类在日常交谈中肢体语言作为辅助的视觉信息可以帮助语言上的交流的启发，通过计算机视觉捕捉人眼的移动和方向以及识别人类的动作来对一些模糊的和省略的语言内容构建完整的上下文。
在前面提到的国外学者已经构建的系统中，都不同程度的具有学习能力。机器的学习可以分为个体学习和社会学习两种方式[4]。个体学习是通过大量的训练材料，机器自动习得
作者简介：梅筱（1987—），男，硕士研究生，自然语言处理. E-mail: meixiaoyao@https://www.sodocs.net/doc/3d1083366.html,
所需的知识。社会学习是通过人机交互，在人和机器的交流中，使得机器习得所需的知识。本文中的系统采用的是个体学习的方式，也就是给出训练材料，机器自动学习所需的知识。在本文的系统中训练材料是机器自动生成的视频特征和对这些视频的描述词汇，而后机器通过学习掌握描述新的视频的能力。
于是，在这种个体学习的方式中，对于模型的训练即视频视觉特征及其描述词汇的对齐就成为了关键，而对齐系统的重中之重就是如何处理语料中没有出现过的词（新词）。本文的考虑是首先找出训练语料中的基础词，再计算新词与基础词之间相似度，从而对词进行分类，实现词与特征的对齐。
1知识介绍及文章安排
词语相关度反映了两个词语互相关联的程度,即词语之间的组合特点, 它可以用这两个词语在同一个语境中共现的可能性来衡量。词语相关度可以应用于信息检索、句法消歧、文本分类、文本聚类等领域。
目前, 词语相关度的计算主要是基于语义词典的方法。如Hownet[5][6]、同义词词林[7]等知识源提供的分类体系来计算词语在语义上的相关程度。许云等人基于语义相似度计算以及知网的语义信息, 提出了语义相关度的计算方法, 即利用知网义原纵向与横向关系及实例信息来计算不同词性的词语之间的语义相关度。但是知网中只有部分义原具有解释义原, 并且标注的实例信息十分有限, 因此算法存在很大的局限性[8] 。
为了解决外部知识不能解决的词语，本文提出了最小编辑距离结合词性的算法，由于此算法是从词语本身的特性出来，不借助外部知识，所以就打破了外部知识的局限性。而且加入了词性这一维度。实验表明，本文提出的算法比单纯依靠最小编辑距离有着更高的准确性。
本文是这样安排的。第二章陈述了训练的模型和数据的准备工作；第三章提出了基于最小编辑距离结合词性的相似度算法；第四章将给出对比实验和实验结果并对其进行分析，第五部分对全文进行了总结。
2训练模型和数据准备
2.1训练模型
视频视觉特征及其描述词汇的对齐系统结构如下图1：
图1对齐系统流程图
Fig.1 the flow chart of alignment
首先要为系统准备用于学习的视频和语言。系统采用的是计算机生成的视频，视频采用
纯白色背景，每个视频中仅包含一个运动主体（小球）。小球的运动是规则的匀速直线运动，方向包括向上、向下、向左和向右。系统中学习的语言是视频所对应的人工标注，本文采用了开放的不限定维度的语言对视频进行了人工标注。本问中的对其系统主要学习三个范畴，运动方向、运动位置和运动方向。具体的习得过程是，首先通过计算词汇的词频以及同视觉特征的共现概率来得到基础词以及它们与视频特征的对应关系；然后通过最小编辑距离和词性计算新词与基础词的相似度，从而分类；最后实现视频特征与词汇的对齐。
2.2数据准备
实验数据的准备工作遵循两个通道的信息独立进行。准备工作的内容包括视频场景文件和语言描述文件的制作，以及对这两类粗语料的预处理，为后期的对齐系统提高的训练语料。
视频语料是对人类学习语言时看到的视觉场景的仿真。选取适合位移类动词描述的运动场景，即小球的直线位移事件。根据直线位移事件发生时的不同状态，选取了4个可变参数，来确定某次直线位移发生时的状态，4个参数及其取值如下表1：
表1视觉特征参数
Tab.1 the Parameters of Video features
可变参数参数取值说明
方向1，2，3，4 上左右下四个方向
速度 12，24，48 三种速度，12代表走0.1
用0.5秒
起始位置均匀分布于全屏屏幕面积1x1
终止位置均匀分布于全屏屏幕面积1x1
语言标注语料类似于人类看到场景时听到的教学语言，在此即对位移事件的语言描述。原则是无语言限制，维度开放的自然语言。经过切分、词性标注等预处理之后最终形成的1080句训练语料格式如下：
0074/v 1 0 2 8 2 24 缓缓/d 向右/v
0075/v 1 0 2 10 2 24 缓缓/d 左端/v 右端/wj
0076/wkz 1 8 2 10 2 48 右侧/f 右端/wj
0077/wkz 1 6 2 8 2 48 向右/qd
0078/wj 1 6 2 10 2 48 缓缓/d 向右/v 尽头/f
0079/wd 1 4 2 6 2 48 缓缓/d 向右/v
0080/v 1 4 2 8 2 48 慢慢/d 从左向右/v
0081/v 1 4 2 10 2 48 慢慢/d 从左向右/v 尽头/f
0082/wd 1 2 2 4 2 48 慢慢/d 从左向右/v ……
3词共现和词相似度
本文基于上述的训练语料，将视觉的特征与描述词汇相对齐。首先通过词共现得到语料中的基础词；然后我们再定义一个计算词相似度的一个算法，通过相似度的计算，将词语分类，最终实现对齐。
3.1词共现
共现，顾名思义就是共同出现。我们这里通过计算共现概率来得到基础词。设特征集R
和词集X ，{}12,R ,......n r r r =，{}12,,......m X x x x =。i r （1<=i<=n）在文档中出现的次数为i a ，j x （1<=j<=m）出现的次数为j b ，i r 和j x 在同一行中共同出现的次数为ij c 。 定义i r 和j x 的共现概率如式1所示： ()1(1)ij ij i ij j ij c p a c b c =?+?+ 1
其中，为了防止分母为0，在每个分式中加上了1,，对于概率的比较是没有影响的。 通过公式1，我们可以计算出词j x 同特征集R 中每一个特征的共现概率1j p 、2j p 、……、nj p ，从而得到最大的ij p 以及对应的特征i r 。再对词集X 的每一个词进行计算，就可以得到每一个词的p 以及对应的特征r 。
在得到每个词的出现次数a 和贡献概率p ，我们就可以选择a 和p 较大的作为我们的分类基础词。
下图是针对本训练语料得到的基础词。
运动方向类： 从左向右 向右 从右向左 向下 向上
运动位置类： 从中 左边 右下方 在下 偏下 上部
运动速度类： 快速 缓缓 很快 快
3.2最小编辑距离结合词性的词相似度算法
得到基础词之后，我们就可以计算新词与基础词之间的相似度了，从而进行分类。
3.2.1最小编辑距离算法
最小编辑距离((Minimum Edit Distance: MED) 由Levenshtein 于1966年在文献[9]中提出, 通过编辑距离计算源字符串S 与目标字符串T 相似度。编辑距离是指由S 变化到T 所需要的最小编辑操作的数量, Levenshtein 所提出的编辑操作是指对字符串的某一个位置的字符进行删除、插入、替换的操作。基于编辑距离算法进行动态编程,其算法的时间复杂度为O (mn ), 空间复杂度为O(mn), 如果编辑顺序不需要保存的话, 空间复杂度为O(min(m, n) ), m, n 分别表示源字符串S （1s ……m s ）和目标字符串T （1t ……n t ）的长度。编辑距离D (S, T ) 的计算方法如下所述。首先假设(,)D i j =D ( s1 …si, t1… tj ),表示从S 到T 的编辑距离, 那么(m + 1) *( n + 1) 阶矩阵(,)D i j 可通过式2计算得到：
(1,)cos (,)min (1,1)cos (,1)cos D i j ins t D i j D i j sub t D i j del t ?+???=??+????+??
2
式(2)包含删除、插入、替换三种操作。cos ins t ?表示进行插入操作的编辑常量，在本文中设为1, cos sub t ?表示进行替换操作的编辑常量，在本文中设为2, cos del t ?表示进行删除操作的编辑常量，在本文中设为1。该算法是从两个字符串的左边开始比较, 记录已经比较过的编辑距离, 然后进一步得到下一个字符位置时的编辑距离。矩阵(,)D i j 逐行逐列计算获取[10], 最终(,)D m n 表示D (S, T )的值, 即S 和T 的编辑距离。编辑距离越大, 相似度越小。
3.2.2基于最小编辑距离结合词性的词相似度
由于单纯依靠最小编辑距离得到的结果准确率不高，所以本文提出了一种最小编辑距离结合词性的改进算法。设S,T 为两个词语，他们的相似度通过式3计算得到 (,)P S T =αSim （文字串）+βSim （词性） 3
Sim （文字串）采用最小编辑距离的方法（D (S, T )），Sim （词性）表示如果S 和T 的词性相同，则为1；若不同，则为0。得到的(,)P S T 如式4所示
(,)P S T =α/（D (S, T )+1）+βSim （词性） 4
其中：
1、 α+β=1
2、 (,)P S T [0,1]∈
3、 当D (S, T )=0且Sim （词性）=1，即词语S 和T 的最小编辑距离为0,词性相同时，(,)P S T =1,表示S 和T 的相似度最大。
4、 D （S,T ）越大，Sim （词性）=0，即词语S 和T 的最小编辑距离越大,词性不同时，(,)P S T 越小,表示S 和T 的相似度越小。
得到式4后，我们要确定参数α和β的值，本文使用了400句训练语料作为发展集，来训练参数。得到的结果如下图2
Fig.2 errors-α value curve
由此，我们得到了当参数α=0.6时，词语分类的错误数最少，效果最佳。那么β=1-0.6=0.4。所以，本文采用的最小编辑距离结合词性的词相似度算法通过式5得到 (,)P S T =0.6/（D (S, T )+1）+0.4Sim （词性） 5
4 实验结果及分析
4.1对比实验
本文进行了3组实验，来验证提出的算法确有改进。实验一是通过最小编辑距离结合词性计算(,)P S T 的最大值来进行分类；实验二是单纯依靠最小编辑距离来计算词相似度进行分类；实验三是通过最小编辑距离结合词性来计算每个词同三类基础词相似度的平均进行分类。正确率、召回率、F 值的计算公式如下:
正确率P=正确分类的词语个数/此类中词语总数
召回率R=本当属于此类但被错分为其他类的词语/此类中词语总数
F值 = p*R*2/(p+R)
得到的结果如表2所示。
表2 结果对比表
Tab.2 the results of Comparison
实验一实验二实验三
方向类0.825 0.782 0.395
方位类0.834 0.803 0.829
速度类0.951 0.96 0.951
total 0.869 0.836 0.709
表中的total表示三类综合之后的F值
F值的对比图如图3所示
图3F值对比图
Fig.3 the comparison of F value
由上图可知，实验一即本文提出的算法的效果最佳。较之实验二（单纯依靠最小编辑距离）的算法，F值提高了3.3%。
4.2结果分析
依据本算法进行的实验一的最终详细结果如下
运动方向类：准确率 99.6% 召回率 70.5%
运动方位类：准确率 71.6% 召回率 99.7%
运动速度类：准确率 99.8% 召回率 90.6%
F值 = 86.9%
由于本文提出的算法是依靠词本身的特性来计算相似度，并不依赖于外部的知识，所以可以解决所有的词语，打破了外部知识的局限性。
从结果分析可以看出，运动方位类的准确率不高。这是因为本文采用的是基础上下文的自动词性标注系统，不是人工的标注词性。由于词性的标注考虑到了上下文，所以同一个词在不同行中标注的词性并不相同，这样就影响到了最后分类的结果，在方位类上尤为突出。
虽然有着相同词不同词性的负面影响，但是本算法还是在单纯依靠最小编辑距离的算法
的基础上F值从83.6%提高到了86.9%。说明的本文定义的最小编辑距离结合词性的算法对词相似度计算的性能有着很大的提高。
5结论
本文提出了一种在最小编辑距离的基础上结合词性的相似度算法，通过计算词语同基础词之间的相似度来进行分类，最终实现特征与词汇的对齐。经过试验证明，词算法打破了外部知识的局限性，并且较之单纯依赖最小编辑距离计算相似度的算法有着更好的性能。[参考文献] (References)
[1]Jerome A. Feldman等，Miniature Language Acquisition: A touchstone for cognitive science, FELDMAN,
LAKOFF, STOLCKE & WEBER, 1990.
[2]Deb K. Roy. Learning Visually-Grounded Words and Syntax for a Scene Description Task. Computer
Speech and Language. 2002年.
[3]Deb Roy等, Learning Audio-Visual Associations using Mutual Information, in International Conference on
Computer Vision, Workshop on Integrating Speech and Image Understanding, 1999.
[4]Luc Steels and Frederic Kaplan, AIBO’s first words. The social learning of language and meaning, in: H.
Gouzoules(Ed), Evolution of Communications, vol. 4, No. 1, 2001.
[5]刘群,李素建.基于知网的词汇语义相似度计算[EB/OL].https://www.sodocs.net/doc/3d1083366.html,, 2002
[6]葛斌.基于知网的词汇语义相似度计算方法研究.计算机应用研究.2010年9月
[7]梅家驹,竺一鸣，高蕴琦等编.同义词词林.上海：上海辞书出版社，1983.
[8]许云, 樊效忠, 张锋. 基于知网的语义相关度计算[ J] . 北京理工
[9]LEVENSHTEIN V L. Binary codes capable of correcting deletions, insertions and reversals[ J ]. Doklady
Akadem iiNauk SSSR, 1966, 163( 4): 707 - 710.
[10] 赵作鹏，一种改进的编辑距离算法及其在数据处理中的应用，计算机应用，2009年2月