基于 Wikipedia 的短文本语义相关度计算方法

基于 Wikipedia 的短文本语义相关度计算方法
王荣波1 谌志群1 周建政2 李 治2 高 飞1 1 ( 杭州电子科技大学认知与智能计算研究所 浙江 杭州 310018) 2 ( 天格科技( 杭州) 有限公司 浙江 杭州 310005)
收稿日期: 2013 － 06 － 04。教育部人文社会科学研究青年基金项目
( 12YJCZH201) ; 杭州市科技发展计划重大科技创新专项( 20122511A18) 。
王荣波，副教授，主研领域: 中文信息处理。谌志群，副教授。周建政，工程师。李治，工程师。高飞，硕士生。 摘 要 语义相关度计算是自然语言处理领域的研究热点。现有的以文本相似度计算代替文本相关度计算的方法存在不足之处。提出从语形相似性和组元相关性两个方面来综合度量短文本之间的语义相关性，并提出 2 个以 Wikipedia 作为外部知识库的短文本相关度计算算法: 最大词语关联法和动态组块法。在一个网络短文本测试集上对算法进行测评。实验结果表明，该算法与典型相似度计算算法比较，在正确率方面提高了 20% 以上。
关键词 短文本 Wikipedia 相关度计算 自然语言处理
中图分类号 TP391 文献标识码 A DOI: 10． 3969 /j． issn． 1000-386x． 2015． 01． 021 SHOＲT TEXTS SEMANTIC ＲELEVANCE COMPUTATION METHOD BASED ON WIKIPEDIA Wang Ｒongbo1 Chen Zhiqun1 Zhou Jianzheng2 Li Zhi2 Gao Fei1 1 ( Institute of Cognitive and Intelligent Computing，Hangzhou Dianzi University，Hangzhou 310018，Zhejiang，China) 2 ( Tiange Technology( Hangzhou) Limited Company，Hangzhou 310005，Zhejiang，China) Abstract Semantic relevance computation is the research focus in natural language processing field． Existing approach has the deficiency， which replaces the texts relevance computation with texts similarity computation． In this paper，we present to measure the semantic relevance between short texts comprehensively from two aspects of morphological similarity and group elements relevance，and present two computation algorithms for short texts relevance using Wikipedia as the external knowledge base: the maximum words correlation ( MWC) algorithm and the dynamic chunking ( DC) algorithm． The algorithm has been texted and assessed on a network short texts test set． Experimental results show that compared with typical similarity computation algorithm，this algorithm improves the accuracy rate up to 20% and higher． Keywords Short texts Wikipedia Ｒelevance computation Natural language processing
0 引 言
互联网应用的快速发展与变革导致短文本大量出现［1］，如即时聊天记录、新闻和 BBS 标题、新闻跟帖、博客评论等，近几年微博成为另一个海量的短文本信息源。短文本之间的相关度计算是很多互联网应用的关键技术。目前在文本相似度计算 ( 包括短文本相似度计算) 方面已有不少研究成果，并在诸多领域得到应用［2，3］。文本相关度的概念与文本相似度的概念有联系也有区别［4］。“相关”强调的是文本内容的“关联性”，而“相 似”强调的是语义 方 面 的“相 像 性”。例 如，词 语“iPhone”和 “iPad”之间更多的是具有相关性而非相似性，“餐桌”和“书桌”之间更多的是相似而非相关。又如，两个短文本“电脑走进了农村孩子的课堂，张老师第一次使用 PPT 做公开课”和“乡村中小学计算机教育条件有待改善”均与农村地区教育中的电脑普及与使用相关，它们之间具有强烈的相关性，而语义相似度较小。互联网上的很多应用都需要文本相关度计算技术，如信息推荐系统中需要根据用户的偏好自动发现关联信息［5］; 网络舆情分析系统中需要分析热点话题之间的相关性及其演化规律［6］; 而在自动聊天系统中需要对海量的聊天记录进行归类与关联挖掘以改进自动聊天的效果［1］。
网络上出现的短文本作为文本的一种，具有几个显著的特点［7］，其中最重要的是单条短文本的长度一般都非常短( 如每条微博限 140 字、新闻和 BBS 标题最多也就几十个字) ，因此样本特征非常稀疏，很难准确抽取有效的语言特征，也就难以充分挖掘与利用特征之间的关联性。短文本的特征稀疏性，使得现有的文本相关度计算算法难以取得良好的效果［8］。本文首先综述了现有的文本相关度计算技术，并介绍了基于Wikipedia 的语义相关度计算研究现状，然后提出以 Wikipedia 作为外部知识库，实现网络短文本之间的相关度计算，并具体提出了最大词语关联法和动态组块法两个短文本相关度计算算法，最后在一个网络短文本测试集上对本文算法进行了评测。
1．1 文本相关度计算研究
目前的自然语言相关度计算研究主要集中在词汇层面［4］，文本之间的相关度研究由于其在网络信息处理中的重要作用近年来也逐渐成为研究热点。主流技术分为两类: 基于词语共现的方法［8，9］和基于外部知识库的方法［10，11］。词语共现模型是经典的自然语言处理模型，其基本思想是如果两个文本包含较多的共同词语那么它们是语义相关的或相似的。贾西平等［9］ 提出了一个以词语共现模型为基础的概率文档相关模型，通过概率推理和合理近似，把求解文档之间的相关性转化为计算 LDA主题向量之间的相似性。赵玉茗等［10］提出以知网为知识库，提取文档中存在语义关联的词语链及其权重作为文档的形式化表达，并在此基础上进行文档之间的相关度计算。朱鲲鹏等［11］通过词频统计和基于知网的词语概念相似度计算模型来计算网页文档间的主题相关度。在短文本相关度研究方面，何海江［8］提出一种扩展向量空间模型的相关度向量空间模型( cVSM) ，并把它应用于博客和 BBS 评论文本的相关度计算领域。综合以上研究，发现现有的文本相关度计算方法基本都是借鉴文本相似度的计算方法。相似性度量虽然能够在一定程度上反映相关性度量。但是，在强调考察文本之间的关联程度而非相似程度的很多互联网应用当中，这类方法往往不能取得良好的应用效果，而短文本由于其特征稀疏性，效果更差。因此，迫切需要研究新的文本相关度( 特别是针对网络短文本的相关度) 计算方法。
1．2 基于 Wikipedia 的语义相关度计算研究
本文提出引入 Wikipedia 作为外部知识库，在计算词语之间相关度的基础上来计算短文本之间的语义相关度。Wikipedia是目前世界上规模最大、覆盖面最广的在线百科知识库［12］，近年来很多研究者把它应用到自然语言处理中，取得了很好的效果［13］。Strube 等［14］最早利用 Wikipedia 作为语义知识库来对词语相关度进行计算，并与基于 WordNet 的方法作了对比，发现它在相关度计算中的优势体现在它的覆盖面比较广。Gabrilovich 等［15］提出一种基于 Wikipedia 解释文档来实现文档特征向量语义扩展的方法，可以实现对词语或者更长文本的相关度计算。 Hassan 等［16］改进了文献［15］中提出的方法，首先从 Wikipedia中抽取重要概念以及概念的解释文档，然后基于概念范围之间的距离来衡量词语语义相关度。在短文本相关度计算方面， Banerjee 等［17］首先收集 Wikipedia 解释文档，并利用开源文本检索工具 Lucene 建立文档索引，然后将短文本进行预处理得到两个单词序列，针对每个词语通过检索系统获取检索文档来进行词语语义扩展进而计算词语相关度。在国内，针对中文文本也有类似的研究。李赟［18］根据ikipedia 中文版的分类层次以及文档链接体系构建了分类图和文档图，通过概念之间的路径信息进行了概念之间的相关度计算。刘军等［19］利用 Wikipedia 的分类层次进行倒排索引，通过余弦相似度来计算两个词语的语义相关度。我们在这方面也做了一定工作，在借鉴向量空间模型和谷歌相似度计算方法基础上，提出构建 Wikipedia 分类图和相关语义向量来实现汉语词语相关度的计算［20］。该方法也是本文提出的短文本相关度计算方法的基础。
2 短文本语义相关度计算方法
2．1 方法描述
从原理上来说，要度量两个短文本之间的相关性，需要对短文本进行深层的语义分析，在获取短文本深层语义的基础上来计算短文本之间的语义相关度。但是目前自然语言语义分析的技术水平还难以满足要求。我们认为，在目前的技术条件下，引入文本浅层分析技术，从语形相似性和组元相关性两个方面来综合度量两个短文本之间的语义相关性是合理、可行的。所谓语形相似性是指两个短文本在结构上、在词语构成上的共同之处。组元相关性指两个短文本包含的组成单元( 如词语和组块) 在语义方面的相关性。基于以上分析，本文引入常见的词形词序法［21］度量短文本之间的语形相似性。同时由于现有大部分研究将文本相似度作为文本相关度，而词形词序法是有代表性的文本相似度计算方法，因此本文将词形词序法作为一种传统的文本相关度计算方法，与本文方法进行实验比较。本文提出的两种方法以我们已有的基于 Wikipedia 的词语相关度计算方法［20］为基础，通过计算短文本之间的组元相关度( 词语相关度和组块相关度) ，并综合语形相似度和组元相关度来计算短文本之间的相关度。具体来说，语形相似度计算结合词语相关度计算构成最大词语关联法，语形相似度计算结合组块相关度计算得到动态组块法。
2．2 词形词序法
词形词序法是一种衡量句子相似度的常见方法［21］。短文本一般只包含 1 ～ 2 句子，甚至只包含几个词语，我们引入词形词序法来计算短文本之间的语形相似度。设 sameWC( A，B) 为短文本 A 和 B 中相同词语的个数，当同一词语在 A 和 B 中出现的次数不同时，以出现次数少的计数，则短文本 A 和 B 的词形相似度可由式( 1) 计算:

可以证明，0≤WordSim( A，B) ≤1。 设 OnceWS( A，B) 表示 A 和 B 中都出现且只出现一次的词语集合。Pfirst( A，B) 表示 OnceWS( A，B) 的词语在 A 中的位置序号构成的向量。Psecond( A，B) 表示 Pfirst( A，B) 中的分量按对应词语在 B 中的词序排列生成的向量。ＲevOrd( A，B) 表示Psecond( A，B) 各相邻分量的逆序数。则 A 和 B 的词序相似度可由式( 2) 计算:

易证，0≤OrdSim( A，B) ≤1。综合考察词形相似度和词序相似度，短文本 A 和 B 的语形相似度可由式( 3) 计算:
Simword ( A，B) = λ1 × WordSim( A，B) + λ2 × OrdSim( A，B) ( 3)其中 λ1和 λ2为常数，并且满足 λ1 + λ2 = 1，因此 0≤Simword ( A， B) ≤1。由于词形相似度起主要作用，词序相似度起次要作用，因此一般有 λ1 ＞ λ2。
2．3 最大词语关联法
两个短文本包含的词语( 特别是名词) 之间的语义相关性是这两个短文本之间相关性的重要反映。设 A 和 B 是两个待84 计算机应用与软件 2015 年比较的短文本，经过分词和词性过滤后，得到两个短文本的特征词向量 A' = { a1，a2，…，am } 和 B' = { b1，b2，…，bn } ，不失一般性， 可令 n≥m。构建两个短文本的词语特征相关矩阵，见式( 4) :

其中 sij表示词语 ai和 bj之间的语义相关度值，0≤sij≤1，由我们 已有的基于 Wikipedia 的词语相关度计算方法计算得到［20］。矩 阵 S 第 i 行中的最大值是短文本 A 中词语 ai与短文本 B 中词语 相关度最大的词语的相关度值。取 S 中每一行具有最大值的元 素，构成短文本 A 和 B 的最大词语关联序列:

然后，由式( 6) 计算 A 和 B 之间的词语相关度:

其中，wi和 wxi 分别是 ai和 bxi 在短文本 A 和 B 中的权重，权重可 用其频度表示。综合语形相似度 Simword和词语相关度 Simsem可 最终计算短文本 A 和 B 之间的相关度，见式( 7) :

其中 λ3和 λ4为常数，分别为语形相似度和词语相关度的权重系 数，满足 λ3 + λ4 = 1。

2．4 动态组块法

最大词语关联法中的最小语言单位是词语，由词语相关度 结合语形相似度来度量两个短文本之间的相关度。该方法没有 考察短文本内部的语义结构，没有考察构成短文本的词语之间 的语义关联性。为此，我们进一步引入组块分析［22］的思想，提 出短文本动态组块的概念，并在组块获取基础上计算短文本之 间的组块相关性。组块是一种符合一定语法功能的语法结构， 一般由句子中连续的词语序列构成［22］。本文将短文本中相关 度较高的词语聚集在一起，并称之为动态组块。动态组块可以 看作是构成短文本的语义单位。短文本 A 的动态组块获取步骤 如下:
Step 1 对 A 进行分词和词性过滤，获得其特征词向量 A' = { a1，a2，…，am } ，令组块集合 Chunk( A) 为空，即 Chunk( A) = { } ;
Step 2 取 A'中元素 ai，如果 Chunk( A) 为空，将( ai ) 作为 一个组块加入 Chunk( A) 中，否则计算 ai与 Chunk( A) 每一组块 中词语的平均相关度;
Step3 如果 ai与 cj ( cj ∈Chunk( A) ) 的平均相关度( 记为 rij ～ ) 最大，且rij ～ ≥θ( θ 为阈值) ，则将 ai加入 cj，否则将( ai ) 作为 一个组块加入 Chunk( A) 中;
Step4 反复执行 Step 2 和 Step 3，直到 A'为空。
设短文本 A 和 B 的动态组块集合分别为:

类似式( 4) ，可构建 A 和 B 的组块特征相关矩阵，其中第 i 行第 j 列元素表示的是 CAi和 CBj两个组块之间的相关度。两个 组块之间 的 相 关 度，定义为组块包含词语之间相关度的均 值，设:

则组块 CAi和 CBj的相关度定义为:

其中，Sim( ai，bj) 为词语 ai和 bj之间的语义相关度值。有了组块 特征相关矩阵，可类似式( 5) 获取 A 和 B 的最大组块关联序列， 类似式( 6) 计算 A 和 B 之间的组块相关度，类似式( 7) 计算 A 和 B 之间的短文本相关度。
3 实验与分析
3．1 Wikipedia 数据与测试集
Wikipedia 作为百科知识库，主要包含词语( 概念) 解释文档 及文档之间的链接信息和概念的分类数据。为处理“多词一 义”现象和“一词多义”现象，还设置了重定向页面和消歧义页 面。Wikipedia 提供的资源结构见图 1 所示。

图 1 Wikipedia 资源结构
从 http: / /dumps． wikimedia． org /zhwiki /latest /下 载 Wikipe- dia 中文版 XML 形式的数据集，并进行了简繁体转换和数据清 洗，提取了词语( 概念) 集合及其解释文档集合，提取了树状的 分类结构。将以上信息以二维表形式保存到数据库表中以供实 验之用。为推动科研资源共享，以上整理好的信息已经以 SQL 文件形式上传到数据堂( www． datatang． com) 网站，供同行自由 下载。
目前还没有专门针对短文本相关度计算的公共测试集。从 网络上收集整理了部分新闻标题、论坛标题作为短文本语料，按 照语义相关性通过人工分类，把语料分为 10 类: 环境、计算机、 交通、教育、经济、军事、体育、医药、艺术、政治。每类 50 篇，总 计 500 篇。
3．2 实验配置与实验结果
实现了 3 个算法: 词形词序法、最大词语关联法、动态组块 法。已有的文本相关度计算方法一般都是借鉴文本相似度计算 方法，而词形词序法是有代表性的相似度计算方法，我们将该方 法与本文提出的最大词语关联法、动态组块法作性能比较。参 数设置是经验性的，选取实验结果较好的一组参数: λ1 = 0． 85、 λ2 = 0． 15、λ3 = 0． 65、λ4 = 0． 35、θ = 0． 5。为验证算法性能，从每 类的 50 篇短文本中随机抽取 3 篇，共抽取 3 × 10 = 30 篇，每类 剩下 47 篇，共 47 × 10 = 470 篇。对于每一抽取的短文本，采用 本文算法计算其与每类剩下的 47 篇短文本之间的平均相关度， 第 1 期 王荣波等: 基于 Wikipedia 的短文本语义相关度计算方法 85 如果该短文本与它自身所在类的短文本的平均相关度最高，那 么说明算法是有效的，作为正例，否则作为反例。以上实验重复 进行 10 组，以正确率作为衡量算法性能的指标。3 个算法的详 细实验结果见表 1 所示，实验结果的比较见图 2 所示。 表 1 实验结果 词形词序法 最大词语关联法 动态组块法



图 2 实验比较
以上实验结果表明，词形词序法根据短文本包含的词语及 词语出现的次序来度量两个短文本之间的相似度，并将相似度 作为短文本之间的相关性测度，效果较差，只取得 47% 的平均 准确率，实验效果很不理想。究其原因一方面是因为选取的特 征过于简单，仅局限于简单表层特征; 另一方面是因为以相似度 代替相关度，而无视两个概念之间的区别。最大词语关联法和 动态组块法将 Wikipedia 作为外部知识库，以词语之间的相关度 计算为基础，计算短文本之间的组元相关性，并结合语形相似度 来度量短文本之间的语义相关性，均取得了 70% 以上的平均准 确率。之所以取得较好效果是因为一方面计算层面不再局限于 语形层面，而是通过引入容量大、覆盖面广的外部知识库来对词 语进行语义扩展，进而计算词语之间和短文本之间在语义层面 的相关性。其中动态组块法引入文本浅层分析思想，在动态组 块提取和动态组块相关度计算基础上来计算短文本之间的相关 度，取得了优于最大词语关联法的实验效果。不过由于需要进 行额外的动态组块提取和相关度计算，动态组块法的时间复杂 度较高。在应用系统研发过程中可根据实际需要选取合适 算法。
4 结 语
文本语义相关度计算是自然语言处理中的重要课题，短文 本语义相关度计算技术在网络信息泛滥的今天具有重大研究价 值。在互联网信息检索与个性化推荐、网络舆情分析与跟踪、网 络自动问答与聊天机器人等互联网应用领域，都需要高效的短 文本相关度计算算法。本文在分析现有的以文本相似度计算代 替文本相关度计算存在的不足，并在考察短文本语言特点的基 础上，引入 Wikipedia 百科知识库，提出短文本相关度计算的最 大词语关联法和动态组块法，实验结果表明了方法的可行性和 有效性。网络短文本一般都是由网络用户发布的，而网络用户 一般又相互关联、相互作用，构成各类社会网络。引入社会网络 分析方法考察短文本的生产主体以及他们之间的相互联系和相 互作用，以进一步改进短文本相关度计算的效果是今后的研究 方向。
参 考 文 献
［1］ 龚才春． 短文本语言计算的关键技术研究［D］． 北京: 中国科学院计算技术研究所，2008．
［2］ Martins A，Figueiredo M，Aguiar P． Kernels and similarity measures for text classification［C］/ /Proceedings of ConfTele’2007，New York， USA，2007: 1-4． ［3］ 闫瑞，曹先彬，李凯． 面向短文本的动态组合分类算法［J］． 电子
学报，2009，37 ( 5) : 1019-1024．
［4］ 刘宏哲，须德． 基于本体的语义相似度和相关度计算研究综述［J］． 计算机科学，2012，39( 2) : 8-13．
［5］ Yize Li，Jiazhong Nie，Yi Zhang，et al． Contextual recommendation based on text mining［C］/ /Proceedings of the 23rd International Con- ference on Computational Linguistics， Beijing， August 2010: 692-700．
［6］ Waltinger U，Mehler A． Social Semantics and Its Evaluation by Means of Semantic Ｒelatedness and Open Topic Models［C］/ /Proceedings of International Joint Conferences on Web Intelligence and Intelligent A- gent Technologies，Milan，Italy，15-18 Sept． 2009 : 42-49．
［7］ 胡佳妮，郭军，邓伟洪，等． 基于短文本的独立语义特征抽取算法［J］． 通信学报，2007，28( 12) : 121-124．
［8］ 何海江． 一种适应短文本的相关测度及其应用［J］． 计算机工程， 2009，35( 6) : 88-90，96． ［9］ 贾西平，彭宏，郑启伦，等． 一种基于主题的概率文档相关模型［J］． 计算机科学，2008，35( 10) : 178-180，218．
［10］ 赵玉茗，徐志明，王晓龙，等． 基于词汇集聚的文档相关性计算［J］． 电子与信息学报，2008，30( 10) : 2512-2515．
［11］ 朱鲲鹏，魏芳． 基于文档相关度计算的网页预测模型［J］． 计算机应用与软件，2012，29( 2) : 109-112，189．
［12］ Wikipedia［EB /OL］． http: / /www． wikipedia． org．
［13］ Olena Medelyan，David Milne，Catherine Legg，et al． Mining meaning from Wikipedia［J］． International Journal of Human-Computer Stud- ies，2009，67( 9) : 716-754．
［14］ Strube M，Ponzetto S． WikiＲelate Computing Semantic Ｒelatedness U- sing Wikipedia［C］/ /Proceedings of the 21st National Conference on Artificial Intelligence，Boston，2006: 1419-1424．
［15］ Gabrilovich G，Markovitch S． Computing Semantic Ｒelatedness using Wikipedia-based Explict Semantic Analysis［C］/ /Proceedings of the 20th International Joint Conference on Artificial Intelligence，2007: 1606-1611．
［16］ Samer Hassan，Ｒada Mihalcea． Semantic Ｒelateness Using Salient Se- mantic Analysis［C］/ /Proceedings of the 25th AAAI Conference on Artificial Intelligence，2011: 884-889． 92 计算机应用与软件 2015 年
［17］ Somnath Banerjee，Krishnan Ｒamanathan，Ajay Gupta． Clustering Short Texts using Wikipedia［C］/ /Proceedings of the 30th annual internation- al ACM SIGIＲ conference on research and development in information retrieval，2007: 787-788．
［18］ 李赟． 基于中文维基百科的语义知识挖掘相关研究［D］． 北京:北京邮电大学，2009．
［19］ 刘军，姚天昉． 基于 Wikipedia 的语义相关度计算［J］． 计算机工程，2010，36( 19) : 42-46．
［20］ 谌志群，高飞，曾智军． 基于中文维基百科的词语相关度计算［J］． 情报学报，2012，31( 12) : 1265-1270．
［21］ 吕学强，任飞亮，黄志丹，等． 句子相似模型和最相似句子查找算法［J］． 东北大学学报: 自然科学版，2003，24( 6) : 531-534．
［22］ 李素建，刘群，杨志峰． 基于最大熵模型的组块分析［J］． 计算机学报，2003，26( 12) : 1722-1777．<br

---

收稿日期: 2013 － 06 － 04。教育部人文社会科学研究青年基金项目 12YJCZH201) ; 杭州市科技发展计划重大科技创新专项( 20122511A18) 。王荣波，副教授，主研领域: 中文信息处理。谌志群，副教授。周建政，工程师。李治，工程师。高飞，硕士生。