第24卷第7期 计算机技术与发展 COMPUTER TECHNOLOGY AND DEVEL0PMENT Vo1.24 No.7 2014年7月 July 20l4 使用网络搜索引擎计算汉语词汇的语义相似度 高国强,黄吕威,陈丰钰 (武汉纺织大学传媒学院,湖北武汉430073) 摘要:汉字词语的语义相似度计算是中文信息处理中的一个关键问题。文中利用网络搜索引擎提供的信息来计算汉语 词对的语义相似性。首先通过程序访问搜索引擎,获取汉字词汇的搜索结果数,并依此实现了相似度计算模型WebPMI; 然后描述了根据查询返回的文本片段进行语义相关性分析的模型CODC;最后,结合这个两个模型,给出了文中算法的伪 代码。实验结果显示,文中的算法较好地利用了互联息,实现了一种较新的汉语词汇语义相似度计算方法,接近于利 用词典提供的信息计算相似度的传统算法。 关键词:相似度;搜索引擎;词典 中图分类号:TP301.6 文献标识码:A 文章编号:1673—629X(2014)07—0084—04 doi:10.3969/j.issn.1673—629X.2014.07.021 Calculation of Chinese Words Semantic Similarity Using Network Search Engines GAO Guo—qiang,HUANG Lii-wei,CHEN Feng-yu (School of Media and Communication,Wuhan Textile University,Wuhan 430073,China) A ̄trad:Similarity computation of Chinese words is a key problem in Chinese information processing.It measures semantic siilarimty between Chinese words using the information returned by web search engines.First.implement a model named WebPM1 which computes similarity using page counts,and then,describe another model named CODC which analyzes semantic siilamri ̄using text snippets.Final- ly,present the algorithm based on the two models.Experimental results show that hist algorithm ontperforms all the existing web-based semantic siilmarity measures for Chinese,and is close to the traditional semantic siilmarity measures using lexicon. Key words:similarity;search engines;lexicon 0 引 言 词汇间语义相似度的研究一直是信息检索和自然 语言处理的核心部分,对于汉语来说尤其如此。词汇 之间的语义相似度在时间和领域范围内是经常变动 了使用网络搜索引擎来计算汉语词汇之间的相似度。 虽然精度不如基于词典的算法,但是可以避免复杂的 词法分析,也避免了维护不断出现的新词汇的代价。 对于精度要求不是很高的应用该算法具有一定价值, 而且随着互联网的不断扩展,这种算法的精度将不断 的。比如说,在互联网上“苹果”经常是“苹果电脑”的 意思,然而在大部分词典中苹果是没有这种意思的。 一提高。网络搜索引擎对互联网上的海量信息提供了一 个有效的访问接口,比如说其提供的搜索结果数和文 个用户在互联网上搜索“苹果”可能就是找苹果电 脑,而不是找一种水果。目前的汉语词汇语义相似度 本片段就是很有价值的信息。一个查询的搜索结果数 是包含这个查询的页面个数。查询“P AND Q”的搜索 算法|1 大部分使用词典来计算相似度,然而新的词 汇是不断增加的,而且领域不同词汇间的相似度也有 结果数可以被用来作为考虑词P和Q存在相关性的全 局度量标准,比如查询“老师AND教授”在百度中的 搜索结果数是88 000 000,然而“工人AND教授”的仅 很大区别。因此手工维护词典来保证完整性是非常困 难的,即使可行,代价也是高昂的。 文中结合已有的两种相似度计算机制 I5 ,提出 收稿日期:2013—09—28 修回Et期:2013—12-30 有7 350 000。查询“老师AND教授”的搜索结果数是 网络出版时间:2014—04—24 基金项目:湖北省自然科学基金(2013cFB3l0);湖北教育科研项目(B2013205);湖北省高等学校2013年省级大学生创新创业训练计划项目 (2013CXZD027);2013年武汉纺织大学大学生创新创业训练计划项目(2013CXXLO08,2013CXXLO09) 作者简介:高国强(1971一),男,湖南常德人,讲师,CCF高级会员,研究方向为数据挖掘、信息检索。 网络出版地址:http://www.cnki.net/kems/detail/61.1450.TP.20140424.0830.074.html 第7期 高国强等:使用网络搜索引擎计算汉语词汇的语义相似度 .85. 查询“工人AND教授”的12倍,这说明前者比后者语 义上更加相关。 尽管使用搜索结果数可以指示词汇间存在语义相 关性,但是仅仅使用结果数来测量语义相似度存在一 些缺点。比如说可能存在大量不相关词对同时出现的 网页,这将导致该方法变得不可信。搜索引擎返回的 片段也是一种有效度量信息,比如查询“教授”的前 100个最高排序结果的片段中,“老师”这个词出现的 次数比“工人”多,这说明了“教授”和“老师”更加相 关。某个词对同时出现的网页中可能有很多页面是它 们不相关的网页,使用这种方式可以抵消不相关网页 对统计结果的干扰。比如含片段“我的计算机坏了, 而且又忘了买苹果”的网页,这个网页就不能表明“计 算机”和“苹果”之间有相关性,这两个词汇只是偶然 出现在一个网页中的,如果把这种网页作为度量参数 的话就会对统计结果产生偏差。搜索引擎返回的前 100个最高排序结果的网页与查询是最相关的,比如 查询“计算机”返回的前100个页面应该都是和“计算 机”相关的信息,前面例子的那个页面一般不会出现 在前100个中。由此可见前100个页面的文本片段是 非常有价值的信息,比如查询“计算机”的前100个页 面片段中含有大量“苹果”词汇,说明两者之间的确有 相关性。当然片段度量标准和搜索引擎效率以及网络 信息容量有很大关系,这是文中提出算法的基础。就 目前而言,网络的容量已经达到了一个可以用来作为 度量标准的级别,而且网络是在不断发展的;搜索引擎 技术也已经比较成熟,对于中文搜索,“百度”是可以 信赖的工具。 1 相关工作 语义相似度测量在许多与网络相关的应用中扮演 着非常重要的角色,比如在查询扩展 中,一个用户的 查询通过同义词被修正以提高搜索的准确性。在查询 中发现合适替代词的一个方法是通过语义相似度计算 来比较用户以前的查询,如果以前的查询与目前的查 询语义相关,就建议用户或搜索引擎修正查询语句。 文献[7]利用相似度对网络连接数据的属性特征进行 选择,抽取其关键特征,并降低属性的冗余度,以优化 朴素贝叶斯的分类性能。实验结果表明,他们的方法 能降低分类数据的维数,提高分类的准确率。现有的 相似度算法 大部分集中在利用词典提供的信息 进行度量,给定一个词典,一个计算两个词之间相似度 的直接方法是发现连接词典中两个词的最短路径长 度。对于汉语词汇来说,尤其如此,不过也更为复杂。 文献[10]利用HowNet作为词典库,在考虑义原 距离和义原深度的条件下,进行词语相似度计算,可以 获得与人们的主观判断更接近的结果。刘群等提出的 基于《知网》的词汇语义相似度计算… 也是利用词典 信息进行计算的例子,为了计算用知识描述语言表达 的两个概念的语义表达式之间的相似度,他们采用了 “整体的相似度等于部分相似度加权平均”的做法。 首先将一个整体分解成部分,再将两个整体的各个部 分进行组合配对,通过计算每个组合对的相似度的加 权平均得到整体的相似度。夏天¨ 在汉语词语语义 相似度计算研究中提出的算法也是利用了《知网》提 供的信息。他提出了一种基于知网、面向语义、可扩展 的相似度计算新方法,该方法从信息论的角度出发,定 义了知网义原间的相似度计算公式,通过对未登录词 进行概念切分和语义自动生成,解决了未登录词无法 参与语义计算的难题,实现了任意词语在语义层面上 的相似度计算。针对同义词词林的实验结果表明,该 方法的准确率比现有方法高出近15个百分点。虽然 文献[13]分析多种相似度计算方法,但也都是基于词 典的算法。 最近,一些研究正关注于利用网络信息来测量语 义相似度。Danushka等 提出了利用网络搜索引擎 测量词对间的相似度。对于两个词P和Q,根据查询 P、Q、P AND Q的搜索结果数按四种不同计算公式计 算归一相似值,并作为一个四维向量保存。然后获取 查询P AND Q的排序前100个搜索结果的片段,对这 些片段进行语义分析,提取词P和Q之间的语义模式, 比如P is p、P and Q are等等,并对这些模式按出现频 率排序。最后对片段中出现的模式选择前200个形成 一个向量并与前面的搜索结果数向量合并为一个向量 F,再利用SVM(支持向量机)对向量F进行处理得出 词对问的归一相似度。这种方法有较高的相关性,接 近于利用词典的算法,但是模式提取算法非常复杂,而 且要利用大量同义和反义词对进行参考模式库生成。 同时,生成参考模式库时,参考词对数规模和选取词对 的标准都是启发式的,这是该算法实用性的一个问题。 对于汉语词汇尤其如此,首先是提取模式复杂,因为汉 语间没有空格,要提取就要使用分词处理,这将导致准 确率下降。再者就是如何选择汉语词对及规模生成参 考模式库,这都是非常复杂的问题,也导致了如果利用 此种方式处理汉语词汇将使算法不实用。陈信希 等 提出了一种利用网络搜索计算词汇相关性的相 关性双重检测算法(CODC)。对词P和Q,首先使用搜 索引擎分别获得查询P、Q的搜索结果数和前100个搜 索结果的返回片段,然后对P的片段统计出现词p的 次数,对Q的片段统计出现词P的次数,然后将这些数 据输入一个设计好的模型得出归一的相似度。CODC 算法在利用网络信息进行相似度计算的算法中有较高 ・86・ 计算机技术与发展 第24卷 的相关性,但它的缺点是,很多词对不能统计相似度。 尤其对语义相差较大或者网络信息覆盖较弱的词对, 对这些情况CODC算法会出错而给出一个为零的相 似度,这是因为P的片段中可能根本就不会出现词 p。对于CODC算法的简洁性,文中的算法进行了采 用,但对于其不足的地方文中进行了改进。 2相似度计算方法 文中提出的算法,对于给定的一组汉语词对,利用 了网络搜索引擎提供的搜索结果数和前100个搜索结 果片段这两种信息,并分别处理后集成在一起形成归 一的相似度。在2.1节,描述了一种使用搜索结果数 计算相似度分值的模型。在2.2节,文中首先分别获 取查询结果片段中另外一个词出现的次数,然后利用 了CODC算法 提供的模型计算出归一的相似度。 在2.3节,给出了文中的相似度算法伪代码,该算法首 先利用2.I节的方法,然后利用2.2节的方法,并在综 合两种方法的基础上给出一个最终的词对相似度。 2.1基于搜索结果数的相似度模型 查询“P AND Q”的搜索结果数能够作为两个词 P和Q的近似相关度,但是仅仅考虑查询“P AND Q” 的搜索结果数来计算语义相似度是不准确的。例如, 在百度中搜索“大学AND讲师”返回搜索结果数是 1 170 000条,而搜索“大学AND苹果”却有5 720 000 条。虽然相比于“苹果”,“讲师”这个词在语义上与 “大学”更相近,但是查询“大学AND苹果”在百度中 的搜索结果数却远远大于查询“大学AND讲师”的结 果数。所以在进行相似度计算时,不仅要考虑查询“P AND Q”的搜索结果数,而且还要考虑查询P、Q的搜 索结果数。 文中扩展了现有的比较流行的相关性计算方法: 逐点共有信息(PMI)算法,通过使用搜索结果数修改 PMI为WebPMI算法来计算语义相似度。这里定义 (P)表示使用搜索引擎查询P的搜索结果数,P n Q 表示联合查询“P AND q”。WebPMI算法关于词P和 Q的相似度为WebPMI(P,Q),定义在式(1)中。 WebPMI(P,Q)= 0 H(P n Q)≤c l0 丽 丽, )o、 therwise (1)一 式中,Ⅳ是搜索引擎已索引文档数。对于Ⅳ值的 给定直接影响结果的准确性,尽管估计一个搜索引擎 索引文档数量是一个有趣的任务,但这超过了文中的 范围。在式(1)中文中根据百度的报告给定N=2× 10 。c是一个门限值,如果查询PnQ的搜索结果数 小于门限值,就不使用计算模型,直接给一个结果为0 的相似度。这是因为两个词可能纯粹偶然地出现在一 个页面上,为了避免这种干扰,文中实验给定C=10。 2.2使用片段信息计算相似度 文本片段是和搜索结果数一起由搜索引擎返回 的,片段提供了一个词和另外的词相关的信息。比如 查询“老师”的返回片段为“【讲师简介】林老师著名 实战派全面预算管理与成本控制实务操作专家”,这 个片段中有很多词汇,比如“讲师”、“著名”、“专家” 等等。可以说“讲师”可能和“老师”有一定关联,如果 考虑查询“老师”的大量片段,而且“讲师”在这些片段 中不断出现,就可以把这种统计结果作为相关的一种 度量。为了利用片段提供的这种信息,文中根据 CODC算法定义词P和Q的语义相似度为CODC(P, Q),定义在式(2)中。 CODC(P,Q)= f0 _厂(p@Q)=0 ilog【 × 】“ e e 式中 厂(P@Q)表示百度中搜索查询Q的前100 个返回片段中出现词P的次数。n是式(2)的一个常 量,根据经验在实验中设置为0.15。如果,(P@Q)或 者 Q@P)等于0,那么CODC(P,Q)将等于0,这是 一种极端情况,也表明词P和Q之间没有关联。如果 ,(P@Q)等于H(Q)且,(Q@P)等于日(P), CODC(P,Q)将等于1,表明词P和Q之间有非常强的 关联,最极端的情况就是同一个词,此 ̄lCf(P@P)肯定 等于 (P),从而就有CODC(P,P)等于1。虽然从理 论上分析,式(2)能计算所有词对的相似度,但是实验 的结果却显示,利用网络信息作为数据源时,式(2)对 于语义关联不强的词对结果几乎都为零。这可能和网 络信息的容量以及搜索引擎的效率有关,比如词对 “工人”和“技术”,因为查询“工人”的前100个结果的 片段中没有出现“技术”,所以CODC(工人,技术)等 于零。直观上看这样的度量是不准确的,为了修正这 种偏差,文中的算法结合了2.1节和2.2节两种方法, 将在2.3中给出描述。 2.3计算相似度算法 对于语义相关性比较强的词对,CODC模型的相 关度要比WebPMI模型的高,但是对于语义相关性较 弱的词对,CODC模型不能度量。文中的算法采用两 种模型,对于给定的词对(P,Q),首先判断,(P@Q) 或厂(Q@P)是否等于零,如果等于零算法使用WebP- MI模型计算相似度,否则使用CODC模型计算相似 度。相似度算法伪代码描述如下。 第7期 高国强等:使用网络搜索引擎计算汉语词汇的语义相似度 ・87・ 算法:GetSim(P,Q)。 D—GetSnippets(P)ifQ not inDthen Sier=WebPMI(P,Q) else Sim:cooc(P,O) ... end if return(Sier) 其中函数GetSnippets(P)是从搜索引擎获得查 询P的前100个搜索结果的片段,并存放在数据集D 中。因为 P@Q)或厂(Q@P)等于零,都有CODC(P, 口)=0,所以算法中可以随便取一个查询的片段进行 分析,这里取的是查询P的片段。Sim是相似度变量, 根据片段分析结果采用不同的计算模型,最后返回相 似度Sim。 3实验 词语相似度计算的结果评价,最好是放到实际的 系统中(比如基于实例的机器翻译系统),观察不同的 相似度计算方法对实际系统的性能的影响。但这需要 一个完整的应用程序,在条件不具备的情况下,文中采 用了模拟几个不同算法,然后进行比较的方法。为了 获取搜索引擎的结果,文中利用perl脚本调用文本浏 览器w3m来访问百度,然后通过程序分析返回结果, 从中获取搜索结果数以及片段。对于片段内容,开发 了一组程序进行内容挖掘。 文中另外选取了三个相似度算法,一个是刘群等 提出的算法,被称之为《知网》算法,这是基于词典模 拟的算法;另一个是Sahami 等提出的利用搜索引擎 计算相似度的算法,被称之为Sahami算法;还有一个 也是基于搜索引擎的算法,叫做Web Overlap,它仅仅 使用了搜索结果数。在对比实验中文中的算法被称为 Proposed Algorithm。根据词义相关性的强弱分别选择 了一些词对进行测试,实验结果如表1所示。 由表1可以看出《知网》算法效果最好,相关度达 到了0.834,接近于人工识别的程度。在非词典的算 法中,文中提出的算法效果最好,达到了一个0.713的 相关度。虽然与人工识别的0.9相关度还有一定距 离,但是和利用词典的算法差距已经不是太大。文中 的算法简单实用,不需要维护词典,而且随着互联网的 发展,其精度将越来越高。 4结束语 文中提出了一种利用互联息计算汉语词汇语 义相似度的算法,该算法的特点是不需要维护词典或 者其他的信息库,算法简单实用。使用网络搜索引擎 表1语义相似度实验结果 — —— _— —丽 ~ 一 Overlap Algorithm 算法 束缚一微笑0.036 0.090 0.000 公鸡一航海0・021 0・197 0.017 中午一绳索 。・。60 。・。82 。・oI 玻璃一魔术0・408 0.143 0.180 和尚一奴隶 0.067 0.095 0.375 海出一毒林0 ,n n,dR n n 作为访问互联息的接口是一种新颖的尝试,通过 文中的算法可以看出这种尝试是成功的。文中利用搜 索引擎返回的搜索结果数和文本片段,给出了两个相 似度计算模型。实验结果表明文中的算法接近于利用 词典的算法,具有一定实用价值。未来进一步要做的 是如果提高效率,毕竟对于有的应用文中的算法精度 是不够的,以后可能的重点在分析文本片段上面。 参考文献: [1]孙昌年,郑诚,夏青松.基于LDA的中文文本相似度计 算[J].计算机技术与发展,2013,23(1):217—220. [2]杨方颖,蒋正翔,张姗姗.基于本体结构的语义相似度计算 [J].计算机技术与发展,2013,23(7):52—56. [3]王桐,王磊,吴吉义,等.WordNet中的综合概念语义 相似度计算方法[J].北京邮电大学学报,2013,36(2):98 —101. [4]Bollegala D,Matsuo Y,Ishizuka M.Measuring semantic simi— larity between words using web search engines[C]//Proceed— ings of the 16th international conference on World Wide Web. Banff,Alberta,Canada:[S.n.],2007:757—766。 (下转第91页)