基于图论聚类和PageRank的领域后控词表自动构建研究

打开文本图片集

[摘 要] 本文提出了一种基于图论聚类算法和PageRank原理的领域后控词表自动构建方法，并以图书馆情报档案领域部分文献为实验数据，验证了运用该方法自动构建领域后控词表的可行性。

[关键词] 后控词表;图论聚类;词汇同现网络;PageRank

[中图分类号] TP391.1    [文献标识码] A   文章编号：1671-0037（2015）11-77-4

Study on the Automatic Construction of DomainPost-Controlled Vocabulary Basedon Graph Clustering and PageRank

Li Fajun

（The Third Affiliated Hospital of Zhengzhou University， Zhengzhou Henan 450000）

Abstract：This paper put forward an automatic construction method of domain Post-Controlled Vocabulary（PCV）based on graph clustering and PageRank principles.Some literatures about library science，informatics and archaistic are used as experiment datato prove the feasibility of automatic construction of domain PCV through this method.

Keywords：Post-Controlled Vocabulary;Graph clustering;Concurrence vocabulary network;PageRank

“后控制检索”是指“用自然语言标引，但通过控制词表检索”的模式，其所使用的词表称为“后控词表”[1]，后控词表是自然语言检索中提高检索效率的有效方式之一。后控词表是在自然语言的基础上编制的，自然语言自由活跃、变化快，所以后控词表相应的具有词汇量大、增加速度快、更新及时等特点，是不断增长的叙词表。最初编制后控词表都是由领域专家手工完成的，这样编制的后控词表凝聚了领域内高级专家的智慧，因此，无论从选词的数量、选词的质量以及词汇之间的关系方面来说都比较精确可靠。但是，显而易见，手工编制词表需要花费大量的人力、智力，构建速度慢，尤其是不易于维护和更新。当词表被集成到信息检索系统或移植到Web环境时，它的不适应性就完全突显出来了。单纯依靠手工维护和更新词表跟不上领域知识的快速发展，适应不了网络时代信息的迅速增长和快速更新。因此，根据特定领域文献本身的主题，有针对性地自动及时地构建领域后控词表的方法是非常值得研究的课题。本文试图运用图论聚类和PageRank原理进行领域后控词表的自动构建，为领域后控词表的自动构建研究提供新的思路，并改善构建效果。由于是新方法的初步研究，本文的研究范围仅限于中文领域后控词表的自动构建。

1 基于图论聚类和PageRank原理进行领域后控词表自动构建的总体思路

首先，从叙词表中抽取某一领域的叙词建立后控词表结构及初始内容，然后，建立大规模规范化语料库，从语料库中抽取出领域词汇，建立同现词汇网络，利用PageRank公式计算词汇网络中每一个词汇的重要度指数，结合图论聚类算法得到的词汇网络聚类簇，选择词表中正式词的入口词添加到后控词表中，总体思路如图1。

2 基于图论聚类和PageRank原理进行领域后控词表自动构建的原型构建

2.1 后控词表结构及初始内容的建立

以叙词表《管理科学主题词表》为基础建立后控词表。该词表是我国第一部涉及管理科学领域的专业性主题词表，词表元数据包括：id、范畴号、正式词、英文、关系、入口词。本文选择其中范畴号为0530的图书、情报、档案类的叙词作为后控词表的初始内容，共有450条记录，其中290多个是正式词。

2.2 规范化语料库的建立

选择中国知网（）图书、情报与档案领域期刊文献作为原始文档来构建图书情报档案专业的领域语料库。网站收录了该领域78种期刊，不同期刊可能在出版格式上有所不同，但是，科技文献的元数据格式是统一的。由于文献的代表性词汇通常集中在篇名、摘要以及关键词中，所以建立包括篇名、文献摘要、关键词串、发表日期以及所属专题等字段的数据表作为领域语料库。抽取文献300篇，利用应用程序将这些文献逐篇读取到元数据格式规范的语料库中，得到规范化语料库。

2.3 领域词汇的自动抽取及同现词汇网络的建立

由于关键词串有明显的间隔符号，所以，只要根据这些间隔符号抽取即可。对篇名和文献摘要中词汇的自动抽取主要有以下过程：

2.3.1 停用词过滤。科技文献的篇名和摘要有其固有的文法和结构。科技文献篇名常用的语言格式有：“基于……的研究/分析/实现/应用”“一种……”“……的……分析”等。文献摘要是对文献全文的概括，语言一般非常精炼，常见的句式有：“针对……的问题”“提出了一种……的方法”“采用……的技术”“构建……的系统”等。针对如上特点，结合出现频率高的泛指词、无意义的虚词，以及一些动词、某些中性的名词以及量词建立停用词表（停用词表具体词汇包括：的、了、是、一种、基于、研究、分析、实现、应用、可以、开发、我们、提出、针对、采用、构建、技术、方法、系统、介绍、探讨、问题、能够、与、本文），使用该词表从文本中删除不需要的词汇。

2.3.2 自动分词。从文档中自动提取词汇是一个研究的热点和难点，也是自动构建词表的一个难点。从汉语文档中自动抽词较英文更为困难，这是由于中文词汇组合成句进而成篇时不像英文那样用空格作为词汇的间隔符。目前，常用的分词方法基本上分为基于规则的方法、基于统计的方法以及两者的结合。本文使用统计分词方法中常用的Viterbi算法[2]进行自动分词。

2.3.3 分词结果过滤。由于汉语中的词汇绝大多数是由两个或两个以上的单汉字构成，而用来表示概念的单汉字词汇较少，所以，首先去除分词结果中的单汉字。然后在文献的正文中搜索两个汉字或两个汉字以上的词汇以及英文单词，记录词汇在文献正文中出现的次数，如果出现次数低于设定的阈值，说明该词汇在文献中提及较少，不能作为代表文献主题的词汇，将其过滤掉。将最后得到的词汇分别读取到词汇数据表中，词汇数据表元数据包括：词汇编号、词汇、所在文献、出现次数。

2.3.4 建立同现词汇网络。把收集到的词汇按照同现频率构造成同现关系网络，其作用：一是为图论聚类提供基础，二是虽然同现词汇网络不包含词汇间各种具体的语义关系，但可部分体现出词汇的关联。步骤如下：

Step1.把经过停用词过滤、自动分词和分词结果过滤所得的词汇作为同现词汇网络中的结点。

Step2.应用窗口机制选择一定数量的词汇建立词汇网络，该窗口可以是一篇文章、某个时间段内的所有领域文献、某一个专题的文献等，词汇结点如果处于同一个窗口就将两个同现的词汇结点用同现边连接起来，得到词汇网络。

Step3.确定词汇结点之间同现边（wi，wj）的权值dij。

dij=[    1    ][P（wi∩wj）]=[     1     ][P（wi）×P（wj）]

其中，P（wi∩wj）表示词汇结点wi和wj同时出现的频率，P（wi）表示词汇结点wi出现的频率。

2.4 词汇的自动定位

2.4.1 PageRank算法。针对某个词汇可能在窗口中出现次数较多，但对于整个领域来讲并不十分重要的现象，需要计算每一个词汇在领域中的重要度，借用Google搜索引擎网页排序PageRank算法[3]为每个词汇结点分配一个重要度指数。由于词汇同现网络是无向图，结点 的PageRank值的计算公式为：

PageRank（Vi）=（1-d）+d×[∑][j∈C（Vi）]

[weight（Eij）×PageRank（Vj）]["D（Vj）|]

其中d为取值范围为0-1的阻尼因子，一般为0.85;weight（Eij）表示结点Vi和Vj之间边的权值;C（Vi）表示与结点Vi相连的结点集合;D（Vj）为结点Vj的度。

2.4.2 图论聚类算法。图论聚类方法的算法思想是首先得到图的最小生成树，然后按照一定的规则删除其中不需要的某些边，得到连通分支数大于1的非连通图，每一个连通分支为一个聚类。本文应用Prim算法得到词汇网络的最小生成树，然后查找所有已经存在于后控词表之中的正式词，把这些正式词作为聚类簇的中心词，词汇网络中正式词的数量即为聚类簇的数量。然后按照设定的百分比阈值选择出与中心词相关程度最大的一些词汇作为中心词的一级相关词，其余未被选中的词汇结点和中心词之间的边从最小生成树中删除，然后再以一级相关词作为中心按照百分比阈值选择出中心词的第二级相关词，再删除一些边，对于同时和不同的中心词相关程度均较大的结点作为聚类簇相交的结点，同时存在于不同的聚类簇中。从而得到以正式词为中心的辐射状聚类簇。

2.4.3 词汇的定位。以每一个词汇的PageRank值和词汇与中心词同现频率的乘积为依据，选择出乘积最大的词汇作为正式词的入口词添加到后控词表中。

3 实验结果

规范化后的文献元数据格式以及经过停用词过滤、自动分词和分词结果过滤的结果示例，如表1。

以文献作为窗口，首先选择3个窗口的词汇，建立同现词汇网络作为图论聚类的初始数据，设定百分比阈值为60%，根据图论聚类后得到的结果可以作为正式词的备选词汇。例如，“分类”的入口词的词汇是以“分类”为中心的聚类中的所有词汇，计算这些词汇的PageRank值。比较同一个聚类簇中的词汇PageRank（wi）*P（wi，w中心词）值，选择数值最大的词汇作为入口词添加到后控词表中。

据表2所示，“分类”聚类簇中选择“分类体系”作为入口词，“图书馆”聚类簇中选择“rss”作为入口词，将这两个词添加到后控词表中，并把它们之间的关系确定为同现关系。

将窗口数增至6个时，词汇网络、聚类结果、PageRank值及PageRank（wi）*P（wi，w中心词），如表3所示。

据表3所示，“分类”聚类簇中选择“XML”作为入口词，“图书馆”聚类簇中选择“数字图书馆”作为入口词。

4 结语

通过实验验证结果达到稳定所需的语料规模和窗口数量。词汇网络图中的词汇结点要达到相当规模才能使结果比较稳定，但是，本文实验的语料库还未达到所需数量，因此结果并不稳定，需要扩大语料库的规模。虽然词汇网络规模越大得到的结果越稳定，但是，词汇网络规模的增加意味着算法运行的空间和时间耗费增加，所以，还要通过实验得到合适的语料规模和窗口数量，使之既能够得到稳定的结果，又不浪费空间和时间资源。

考察该方法由构建图书馆情报档案领域后控词表推广到构建其他领域以及跨领域后控词表的适用性。本文仅从一个领域对这一方法进行了实验验证，下一步还需要收集其他领域文献作为实验数据进行相应领域后控词表的自动构建，验证该方法的通用性，进而验证构建跨领域后控词表的可行性。

参考文献：

[1] 张琪玉.论后控词表[J].图书馆情报工作，1994（1）：1-4.

[2] 刘颖.计算机语言学[M].北京：清华大学出版社，2002.

[3] 陆勇，侯汉清.基于PageRank算法的汉语同义词自动识别[J].西华大学学报：自然科学，2008（3）.

[4] Young C. Park， Key-Sun Choi. Automatic thesaurus construction using Bayesian networks. Information Processing & Management，1996（5）：543-553.

[5] Kotaro Nakayama，Takahiro Hara， Shojiro Nishio. Wikipedia Mining for an Association Web Thesaurus Construction. Lecture Notes in Computer Science，2007.

[6] 王军.词表的自动丰富——从元数据中提取关键词及其定位[J].中文信息学报，2005（6）：36-43.

[7] 朱伟丽，韩宇，肖晓旦，陈先来.医学关键词与叙词对照表自动构建研究[J]，现代图书情报技术，2006（8）：51-54.

[8] 章成志，苏兰芳，苏新宁.基于多语境的相关词自动提取系统的设计与实现[J].现代图书情报技术，2006（9）.

[9] 屈婉玲，耿素云，张立昂.离散数学[M].北京：清华大学出版社，2004.

[10] 崔光照，曹玲芝，勋才，延峰.基于密度的最小生成树聚类算法研究[J].计算机工程与应用，2006（5）：156-158、164.

推荐访问： 词表 构建 领域 研究 图论

---