论文部分内容阅读
〔摘 要〕同义词自动识别在信息检索、知识挖掘等方面起着重要作用,一直以来都是业界的关注焦点。本文结合网上词典链接分析方法和共现分析方法来自动提取同义词,分别通过分析页面的后向链接信息、重定向页面和对网页内容利用共现分析方法来识别同义词,和传统的同义词识别方法比较有更好的覆盖率和准确性。
〔关键词〕同义词识别;链接挖掘;共现分析;相似度
〔中图分类号〕TP393 〔文献标识码〕C 〔文章编号〕1008-0821(2009)08-0125-03
Automatic Recognition of Chinese Synonyms Using
Link Structure and Co-occurrence AnalysisHuang Fang1 Liu Youhua1,2 Zhang Kezhuang1 Li Yin2
(1.Department of Information Management,Nanjing University,Nanjing 210093,China;
2.School of Management and Engineering,Nanjing University,Nanjing 210093,China)
〔Abstract〕Automatic Recognition of Synonyms plays an important role in aspects such as information retrieval and knowledge mining,and has always been a focus in these fields.This paper combined link structure analysis of web dictionary and co-occurrence analysis to detect synonyms.It was realized by analyzing backward link and redirect page information,and meanwhile by co-occurrence analysis of theweb page contents.The result showed that this method has better coverage and precision.
〔Key words〕synonym recognition;link mining;co-occurrence analysis;similarity
目前,自动识别中文同义词的方法主要有以下几种:(1)基于字面相似度和词素相似度的算法;(2)基于《同义词词林》[1]、《知网》语义体系的同义词识别[2];(3)基于信息检索的同义词识别算法[3]。其中,第一种方法依据字面的相似度,然而很多同义词字面并不相似,并且字面相似的词也并不一定是同义词;基于词典语义体系的方法解决了字面相似性不足的问题,但它要基于专门的词典,而像《同义词词林》、《知网》等词典本身词汇覆盖率不够,并且还存在新词未收录的问题;而基于信息检索的识别算法则依赖于搜索引擎的性能。随着互联网和web挖掘技术的发展,通过分析网上词典链接来获取同义词也逐渐成为同义词识别一个研究方向。文献[4]利用HITS算法分析wikipedia的链接和分类得到同义词和相关词,取得比较好的效果;文献[5]把词典中存在的词汇之间的解释和被解释关系看成是一种语义上的链接关系,并引用pagerank算法来计算词汇间的语义相似度。
本文结合链接分析和共现分析的方法进行同义词的自动提取,通过分析网上词典的链接结构,并对其页面内容利用共现分析方法,两者相结合获取同义词,不仅扩大了同义词识别的覆盖率,而且还可以提高识别的准确性。
1 对基于链接结构识别方法的改进
1.1 几个相关的术语
1.1.1 网上词典
网上词典的一个重要特征是其对链接的应用,对词汇概念的解释由链接的方式给出,且概念之间相互链接,相互存在链接的概念通常比没有链接的概念具有更大的相关性或者相似性;另一个特征是它的扩展性,它的词汇收录量是不断增长的,可以及时收录新词。
1.1.2 前向、后向链接
某个概念的前向链接是指由此概念链出的超链接,后向链接是指链向此概念的超链接。前向链接和后向链接都是分析网页链接结构和网页内容的重要信息。
1.1.3 链接文本[6]
链接文本是指网上词典页面的一部分,它们链接到目标页面。这里分析的链接文本是出现在主题文章的链接文本。这样的链接文本通常和它所链接到的目标概念有很强的关联。
1.1.4 重定向页面
有的网上词典支持在重定向页面,当一个概念有不同的表达方式,比如电脑又可称为电子计算机,则在搜索时重定向到另一个页面,如搜索“电脑”即重定向到“电子计算机”这个页面。重定向页通常和目标页面概念有很强的联系,它们很有可能是同义词、缩写、或是极常见错拼的词,利用重定向页面信息可以直接提取出同义词。
1.2 概念相似度计算
由上文所述,我们可以用有向图G={V,E}来表示网上词典的内容和结构。一般页面内容由一个概念和它的释义组成,这里,V表示页面集合,E表示链接集合。任意两个概念vi和vj的相关性强度可以由从vi到vj的链接数和链接路径的长度来衡量。从vi到vj的链接数越多、链接路径越短,则它们之间的相关性越大[7]。用P={p1,p2,…pn}来表示所有vi到vj的路径,vi和vj的链接关系用链接频率(link frequency)来表示,其计算方法为:
lf(vi,vj)=∑nk=11d(pk)
其中d(pk)代表vi到vj第k条路径的长度。
在信息检索向量模型中,有词频(tf因子)和逆文献频率(idf因子)这两个概念[8],在此基础上有著名的词语加权方案即tf-idf方案。同样,我们利用链接频率lf、逆后向链接频率ibf、lf-ibf加权方案来表示两个概念之间的相关性程度。这里的逆后向链接频率ibf表明,如果某个概念指向很多其他的概念,说明此概念比较宽泛,不能认为它与某个其他概念有很强的相关性,ibf可用下式计算获得:
ibf(vi)=logNlf(vi)
其中,N是网上词典概念总数量,lf(vi)是vi的链出数量。
这时用lf-ibf加权方案来表示两个概念之间的相似性:
lf-ibf(vi,vj)=lf(vi,vj)×ibf(vi)
上式表明,从vi到vj的路径越多,且vi指向的概念越少,则lf-ibf值越大,不难看出,用此来衡量vi和vj的相似性程度比单纯的lf值更加合理,综合得vi和vj的相似性:
sim1(vi,vj)=∑nk=11d(pk)×logNlf(vi)
1.3 利用后向链接和重定向页面信息提取同义词
链接分析方法利用网上词典网页后向链接中的链接文本和重定向页面来提取同义词。第一步,利用后向链接信息识别同义词,为了简化计算过程,在本算法中,后向链接指定为直接指向某个概念的链接,即上述中的d(pk)取统一的一个常值。后向链接获取同义词算法:
其中,B(vj)是vj的后向链接集合,vk∈B(vj),n是vj的后向链接数量,vi是链接文本,它属于网上词典中的一个概念,wij即为概念vi和vj的相似度sim1(vi,vj),即:
sim1(vi,vj)=wij(0≤wij<1)
第二步,利用重定向页面链接信息来识别同义词,将某个概念与它的重定向页面相似度的值取为所有得到的概念间相似度的最大值MAX(sim1)。这样,加大了同义词识别的广度。
2 结合共现分析方法进行同义词识别
2.1共现分析法词汇相似度计算
基于词汇共现分析的方法的前提是如果两个词经常一起出现在同一文献或一定的窗口单元中,则认为两个词在意义上是相互关联的。该方法又称为基于分布的词汇相似度方法,利用词汇的同现信息,对词汇之间的相关性进行度量和量化。
这里,借鉴文献[9]中的方法,对文档集M中的每篇文档,提取出K个词汇,用下式来计算两个词汇之间的关联权值:
wgt(vik,vjk)=2×NS(vik∩vjkNS(vik)+NS(vjk)×ln(1.72+NSk)
其中,NSk表示文档k中全部句子数,NS(vik)、NS(vjk)分别表示文档k中出现词汇vi的句子数和出现词汇vj的句子数,NS(vik∩vjk)表示文档k中同时出现词汇vi和词汇vj的句子数。Ln(1.72+NSk)用来修正在长文档中的词汇对的关联权值,使得不同长度文档得到的权值处在相似的范围值内。设定一个阈值(这里设为1),达到阈值的权值被累加,最后得到词汇vi和词汇vj的相似度:
sim2(vi,vj)=∑nk=1wgt(vik,vjk)
2.2 结合链接分析和共现方法
利用上述链接结构分析方法和共现分析方法计算概念间相似度后,将两者结合,得到概念之间最后的相似度为:
sim(vi,vj)=βsim1(vi,vj)+(1-β)sim2(vi,vj)
其中,sim1(vi,vj)为利用链接结构分析方法得到概念间的相似度,sim2(vi,vj)为用共现分析法得到的相似度,sim0(vi,vj)为最终得到的相似度,β和1-β(0<β<1)分别是两种方法得到的相似度的权值。这里,将两种方法相结合,不仅进一步增大了同义词识别的广度,更重要是提高了同义词识别的准确性。
2.3 实验结果及分析
本文利用维基百科(Wikipedia)中文版来进行同义词的识别。维基百科是一个由大量用户创造并具有高覆盖度的在线百科全书。这里选择中文维基百科分类中的信息技术这个大类,分别利用页面链接数据和页面文本数据分析识别同义词,在结果中随机抽取20个概念,得到它们同义词识别的平均准确率,即对每个概念,经过人工判断,计算识别出的正确的同义词所占的比例,最后计算这20个数值的平均值。结果如表1,部分推荐的同义词或相关词见表2。
试验结果表明,结合两种方法识别同义词比单独利用链接结构分析方法和共现分析方法可达到更高的准确率。另外,和利用《同义词词林》等语义体系识别方法相比,本文的方法可以识别更多新词,如表2中博客以及它的同义词网志、网志空间都不能利用前者识别出来。表1 不同方法同义词识别比较
识别方法链接结构分析共现分析两种方法结合准确率68.4%33.7%76.2%表2 同义词识别例子
目标概念同义词、相关词本体论语义网微软微软公司、操作系统、比尔盖茨、Microsoft Windows互联网因特网、万维网、上网、网络博客网志、网志空间
3 结 论
利用链接结构分析的方法提取同义词,减去了复杂的自然语言处理过程,使得识别过程比较简便,利用网上词典,也可以解决以往利用《同义词词林》、《知网》等语义体系时存在的缺乏新词的问题。将网上词典连接结构分析方法和共现分析方法相结合不仅可以提高同义词识别的准确率,也增大了识别的广度。在网上词典中,概念通常还被归类存放,我们将在进一步的工作中利用分类信息等识别概念之间更具体的关系,比如同位、父子关系等。
参考文献
[1]曹晶.同义词挖掘及其在概念信息检索系统中的应用研究[D].长春:东北师范大学,2006,(5):25-30.
[2]朱毅华.智能搜索引擎中的同义词识别算法研究[D].南京:南京农业大学,2001,(6):32-39.
[3]刘华梅,侯汉清.基于情报检索的汉语同义词识别初探[J].情报理论与实践,2005,(4):373-382.
[4]Andrew A.Krizhanovsky.Synonym search in Wikipedia:Synarcher[EB].http:∥www.citebase.org/abstract?id=oai:arXiv.org:cs/0606097,2005,2008-10-21.
[5]陆勇.面向信息检索的汉语同义词自动识别[D].南京:南京农业大学,2005,(6):27-35.
[6]Kotaro Nakayama.Wikipedia Mining for Triple Extraction Enhanced by Co-reference Resolution[EB].http:∥ftp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-405/paper6.pdf,2008-10-21.
[7]Nakayama,K.,Hara,T.,Nishio,S.A thesaurus construction method from largescale web dictionaries.Proceedings of IEEE International Conference on AdvancedInformation Networking and Applications,2007:932-939.
[8]Ricardo Baeza2Yates.现代信息检索[M].王知津,译.北京:机械工业出版社,2006.5:19-23.
[9]Yuen2Hsien Tseng,Fast Co-occurrence Thesaurus Construction for Chinese News[A].Proceedings of 2001 IEEE International Conference on Systems,Man,and Cybernetics[C],Volume 2,2001,(10):853-858.
〔关键词〕同义词识别;链接挖掘;共现分析;相似度
〔中图分类号〕TP393 〔文献标识码〕C 〔文章编号〕1008-0821(2009)08-0125-03
Automatic Recognition of Chinese Synonyms Using
Link Structure and Co-occurrence AnalysisHuang Fang1 Liu Youhua1,2 Zhang Kezhuang1 Li Yin2
(1.Department of Information Management,Nanjing University,Nanjing 210093,China;
2.School of Management and Engineering,Nanjing University,Nanjing 210093,China)
〔Abstract〕Automatic Recognition of Synonyms plays an important role in aspects such as information retrieval and knowledge mining,and has always been a focus in these fields.This paper combined link structure analysis of web dictionary and co-occurrence analysis to detect synonyms.It was realized by analyzing backward link and redirect page information,and meanwhile by co-occurrence analysis of theweb page contents.The result showed that this method has better coverage and precision.
〔Key words〕synonym recognition;link mining;co-occurrence analysis;similarity
目前,自动识别中文同义词的方法主要有以下几种:(1)基于字面相似度和词素相似度的算法;(2)基于《同义词词林》[1]、《知网》语义体系的同义词识别[2];(3)基于信息检索的同义词识别算法[3]。其中,第一种方法依据字面的相似度,然而很多同义词字面并不相似,并且字面相似的词也并不一定是同义词;基于词典语义体系的方法解决了字面相似性不足的问题,但它要基于专门的词典,而像《同义词词林》、《知网》等词典本身词汇覆盖率不够,并且还存在新词未收录的问题;而基于信息检索的识别算法则依赖于搜索引擎的性能。随着互联网和web挖掘技术的发展,通过分析网上词典链接来获取同义词也逐渐成为同义词识别一个研究方向。文献[4]利用HITS算法分析wikipedia的链接和分类得到同义词和相关词,取得比较好的效果;文献[5]把词典中存在的词汇之间的解释和被解释关系看成是一种语义上的链接关系,并引用pagerank算法来计算词汇间的语义相似度。
本文结合链接分析和共现分析的方法进行同义词的自动提取,通过分析网上词典的链接结构,并对其页面内容利用共现分析方法,两者相结合获取同义词,不仅扩大了同义词识别的覆盖率,而且还可以提高识别的准确性。
1 对基于链接结构识别方法的改进
1.1 几个相关的术语
1.1.1 网上词典
网上词典的一个重要特征是其对链接的应用,对词汇概念的解释由链接的方式给出,且概念之间相互链接,相互存在链接的概念通常比没有链接的概念具有更大的相关性或者相似性;另一个特征是它的扩展性,它的词汇收录量是不断增长的,可以及时收录新词。
1.1.2 前向、后向链接
某个概念的前向链接是指由此概念链出的超链接,后向链接是指链向此概念的超链接。前向链接和后向链接都是分析网页链接结构和网页内容的重要信息。
1.1.3 链接文本[6]
链接文本是指网上词典页面的一部分,它们链接到目标页面。这里分析的链接文本是出现在主题文章的链接文本。这样的链接文本通常和它所链接到的目标概念有很强的关联。
1.1.4 重定向页面
有的网上词典支持在重定向页面,当一个概念有不同的表达方式,比如电脑又可称为电子计算机,则在搜索时重定向到另一个页面,如搜索“电脑”即重定向到“电子计算机”这个页面。重定向页通常和目标页面概念有很强的联系,它们很有可能是同义词、缩写、或是极常见错拼的词,利用重定向页面信息可以直接提取出同义词。
1.2 概念相似度计算
由上文所述,我们可以用有向图G={V,E}来表示网上词典的内容和结构。一般页面内容由一个概念和它的释义组成,这里,V表示页面集合,E表示链接集合。任意两个概念vi和vj的相关性强度可以由从vi到vj的链接数和链接路径的长度来衡量。从vi到vj的链接数越多、链接路径越短,则它们之间的相关性越大[7]。用P={p1,p2,…pn}来表示所有vi到vj的路径,vi和vj的链接关系用链接频率(link frequency)来表示,其计算方法为:
lf(vi,vj)=∑nk=11d(pk)
其中d(pk)代表vi到vj第k条路径的长度。
在信息检索向量模型中,有词频(tf因子)和逆文献频率(idf因子)这两个概念[8],在此基础上有著名的词语加权方案即tf-idf方案。同样,我们利用链接频率lf、逆后向链接频率ibf、lf-ibf加权方案来表示两个概念之间的相关性程度。这里的逆后向链接频率ibf表明,如果某个概念指向很多其他的概念,说明此概念比较宽泛,不能认为它与某个其他概念有很强的相关性,ibf可用下式计算获得:
ibf(vi)=logNlf(vi)
其中,N是网上词典概念总数量,lf(vi)是vi的链出数量。
这时用lf-ibf加权方案来表示两个概念之间的相似性:
lf-ibf(vi,vj)=lf(vi,vj)×ibf(vi)
上式表明,从vi到vj的路径越多,且vi指向的概念越少,则lf-ibf值越大,不难看出,用此来衡量vi和vj的相似性程度比单纯的lf值更加合理,综合得vi和vj的相似性:
sim1(vi,vj)=∑nk=11d(pk)×logNlf(vi)
1.3 利用后向链接和重定向页面信息提取同义词
链接分析方法利用网上词典网页后向链接中的链接文本和重定向页面来提取同义词。第一步,利用后向链接信息识别同义词,为了简化计算过程,在本算法中,后向链接指定为直接指向某个概念的链接,即上述中的d(pk)取统一的一个常值。后向链接获取同义词算法:
其中,B(vj)是vj的后向链接集合,vk∈B(vj),n是vj的后向链接数量,vi是链接文本,它属于网上词典中的一个概念,wij即为概念vi和vj的相似度sim1(vi,vj),即:
sim1(vi,vj)=wij(0≤wij<1)
第二步,利用重定向页面链接信息来识别同义词,将某个概念与它的重定向页面相似度的值取为所有得到的概念间相似度的最大值MAX(sim1)。这样,加大了同义词识别的广度。
2 结合共现分析方法进行同义词识别
2.1共现分析法词汇相似度计算
基于词汇共现分析的方法的前提是如果两个词经常一起出现在同一文献或一定的窗口单元中,则认为两个词在意义上是相互关联的。该方法又称为基于分布的词汇相似度方法,利用词汇的同现信息,对词汇之间的相关性进行度量和量化。
这里,借鉴文献[9]中的方法,对文档集M中的每篇文档,提取出K个词汇,用下式来计算两个词汇之间的关联权值:
wgt(vik,vjk)=2×NS(vik∩vjkNS(vik)+NS(vjk)×ln(1.72+NSk)
其中,NSk表示文档k中全部句子数,NS(vik)、NS(vjk)分别表示文档k中出现词汇vi的句子数和出现词汇vj的句子数,NS(vik∩vjk)表示文档k中同时出现词汇vi和词汇vj的句子数。Ln(1.72+NSk)用来修正在长文档中的词汇对的关联权值,使得不同长度文档得到的权值处在相似的范围值内。设定一个阈值(这里设为1),达到阈值的权值被累加,最后得到词汇vi和词汇vj的相似度:
sim2(vi,vj)=∑nk=1wgt(vik,vjk)
2.2 结合链接分析和共现方法
利用上述链接结构分析方法和共现分析方法计算概念间相似度后,将两者结合,得到概念之间最后的相似度为:
sim(vi,vj)=βsim1(vi,vj)+(1-β)sim2(vi,vj)
其中,sim1(vi,vj)为利用链接结构分析方法得到概念间的相似度,sim2(vi,vj)为用共现分析法得到的相似度,sim0(vi,vj)为最终得到的相似度,β和1-β(0<β<1)分别是两种方法得到的相似度的权值。这里,将两种方法相结合,不仅进一步增大了同义词识别的广度,更重要是提高了同义词识别的准确性。
2.3 实验结果及分析
本文利用维基百科(Wikipedia)中文版来进行同义词的识别。维基百科是一个由大量用户创造并具有高覆盖度的在线百科全书。这里选择中文维基百科分类中的信息技术这个大类,分别利用页面链接数据和页面文本数据分析识别同义词,在结果中随机抽取20个概念,得到它们同义词识别的平均准确率,即对每个概念,经过人工判断,计算识别出的正确的同义词所占的比例,最后计算这20个数值的平均值。结果如表1,部分推荐的同义词或相关词见表2。
试验结果表明,结合两种方法识别同义词比单独利用链接结构分析方法和共现分析方法可达到更高的准确率。另外,和利用《同义词词林》等语义体系识别方法相比,本文的方法可以识别更多新词,如表2中博客以及它的同义词网志、网志空间都不能利用前者识别出来。表1 不同方法同义词识别比较
识别方法链接结构分析共现分析两种方法结合准确率68.4%33.7%76.2%表2 同义词识别例子
目标概念同义词、相关词本体论语义网微软微软公司、操作系统、比尔盖茨、Microsoft Windows互联网因特网、万维网、上网、网络博客网志、网志空间
3 结 论
利用链接结构分析的方法提取同义词,减去了复杂的自然语言处理过程,使得识别过程比较简便,利用网上词典,也可以解决以往利用《同义词词林》、《知网》等语义体系时存在的缺乏新词的问题。将网上词典连接结构分析方法和共现分析方法相结合不仅可以提高同义词识别的准确率,也增大了识别的广度。在网上词典中,概念通常还被归类存放,我们将在进一步的工作中利用分类信息等识别概念之间更具体的关系,比如同位、父子关系等。
参考文献
[1]曹晶.同义词挖掘及其在概念信息检索系统中的应用研究[D].长春:东北师范大学,2006,(5):25-30.
[2]朱毅华.智能搜索引擎中的同义词识别算法研究[D].南京:南京农业大学,2001,(6):32-39.
[3]刘华梅,侯汉清.基于情报检索的汉语同义词识别初探[J].情报理论与实践,2005,(4):373-382.
[4]Andrew A.Krizhanovsky.Synonym search in Wikipedia:Synarcher[EB].http:∥www.citebase.org/abstract?id=oai:arXiv.org:cs/0606097,2005,2008-10-21.
[5]陆勇.面向信息检索的汉语同义词自动识别[D].南京:南京农业大学,2005,(6):27-35.
[6]Kotaro Nakayama.Wikipedia Mining for Triple Extraction Enhanced by Co-reference Resolution[EB].http:∥ftp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-405/paper6.pdf,2008-10-21.
[7]Nakayama,K.,Hara,T.,Nishio,S.A thesaurus construction method from largescale web dictionaries.Proceedings of IEEE International Conference on AdvancedInformation Networking and Applications,2007:932-939.
[8]Ricardo Baeza2Yates.现代信息检索[M].王知津,译.北京:机械工业出版社,2006.5:19-23.
[9]Yuen2Hsien Tseng,Fast Co-occurrence Thesaurus Construction for Chinese News[A].Proceedings of 2001 IEEE International Conference on Systems,Man,and Cybernetics[C],Volume 2,2001,(10):853-858.