基于圖論聚類和PageeRRaannkk的領域后控詞表自動構建研究

李法軍

（鄭州大學第三附屬醫(yī)院，河南　鄭州　45500000000）

?

基于圖論聚類和PageeRRaannkk的領域后控詞表自動構建研究

李法軍

（鄭州大學第三附屬醫(yī)院，河南鄭州45500000000）

［摘要］本文提出了一種基于圖論聚類算法和PageRank原理的領域后控詞表自動構建方法，并以圖書館情報檔案領域部分文獻為實驗數(shù)據(jù)，驗證了運用該方法自動構建領域后控詞表的可行性。

［關鍵詞］后控詞表；圖論聚類；詞匯同現(xiàn)網(wǎng)絡；PageRank

“后控制檢索”是指“用自然語言標引，但通過控制詞表檢索”的模式，其所使用的詞表稱為“后控詞表”［1］，后控詞表是自然語言檢索中提高檢索效率的有效方式之一。后控詞表是在自然語言的基礎上編制的，自然語言自由活躍、變化快，所以后控詞表相應的具有詞匯量大、增加速度快、更新及時等特點，是不斷增長的敘詞表。最初編制后控詞表都是由領域專家手工完成的，這樣編制的后控詞表凝聚了領域內高級專家的智慧，因此，無論從選詞的數(shù)量、選詞的質量以及詞匯之間的關系方面來說都比較精確可靠。但是，顯而易見，手工編制詞表需要花費大量的人力、智力，構建速度慢，尤其是不易于維護和更新。當詞表被集成到信息檢索系統(tǒng)或移植到Web環(huán)境時，它的不適應性就完全突顯出來了。單純依靠手工維護和更新詞表跟不上領域知識的快速發(fā)展，適應不了網(wǎng)絡時代信息的迅速增長和快速更新。因此，根據(jù)特定領域文獻本身的主題，有針對性地自動及時地構建領域后控詞表的方法是非常值得研究的課題。本文試圖運用圖論聚類和PageRank原理進行領域后控詞表的自動構建，為領域后控詞表的自動構建研究提供新的思路，并改善構建效果。由于是新方法的初步研究，本文的研究范圍僅限于中文領域后控詞表的自動構建。

1　基于圖論聚類和PageRank原理進行領域后控詞表自動構建的總體思路

首先，從敘詞表中抽取某一領域的敘詞建立后控詞表結構及初始內容，然后，建立大規(guī)模規(guī)范化語料庫，從語料庫中抽取出領域詞匯，建立同現(xiàn)詞匯網(wǎng)絡，利用PageRank公式計算詞匯網(wǎng)絡中每一個詞匯的重要度指數(shù)，結合圖論聚類算法得到的詞匯網(wǎng)絡聚類簇，選擇詞表中正式詞的入口詞添加到后控詞表中，總體思路如圖1。

2　基于圖論聚類和PageRank原理進行領域后控詞表自動構建的原型構建

2.1后控詞表結構及初始內容的建立

以敘詞表《管理科學主題詞表》為基礎建立后控詞表。該詞表是我國第一部涉及管理科學領域的專業(yè)性主題詞表，詞表元數(shù)據(jù)包括：id、范疇號、正式詞、英文、關系、入口詞。本文選擇其中范疇號為0530的圖書、情報、檔案類的敘詞作為后控詞表的初始內容，共有450條記錄，其中290多個是正式詞。

2.2規(guī)范化語料庫的建立

選擇中國知網(wǎng)（www.cnki.net）圖書、情報與檔案領域期刊文獻作為原始文檔來構建圖書情報檔案專業(yè)的領域語料庫。網(wǎng)站收錄了該領域78種期刊，不同期刊可能在出版格式上有所不同，但是，科技文獻的元數(shù)據(jù)格式是統(tǒng)一的。由于文獻的代表性詞匯通常集中在篇名、摘要以及關鍵詞中，所以建立包括篇名、文獻摘要、關鍵詞串、發(fā)表日期以及所屬專題等字段的數(shù)據(jù)表作為領域語料庫。抽取文獻300篇，利用應用程序將這些文獻逐篇讀取到元數(shù)據(jù)格式規(guī)范的語料庫中，得到規(guī)范化語料庫。

2.3領域詞匯的自動抽取及同現(xiàn)詞匯網(wǎng)絡的建立

由于關鍵詞串有明顯的間隔符號，所以，只要根據(jù)這些間隔符號抽取即可。對篇名和文獻摘要中詞匯的自動抽取主要有以下過程：

2.3.1停用詞過濾?？萍嘉墨I的篇名和摘要有其固有的文法和結構?？萍嘉墨I篇名常用的語言格式有：“基于……的研究/分析/實現(xiàn)/應用”“一種……”“……的……分析”等。文獻摘要是對文獻全文的概括，語言一般非常精煉，常見的句式有：“針對……的問題”“提出了一種……的方法”“采用……的技術”“構建……的系統(tǒng)”等。針對如上特點，結合出現(xiàn)頻率高的泛指詞、無意義的虛詞，以及一些動詞、某些中性的名詞以及量詞建立停用詞表（停用詞表具體詞匯包括：的、了、是、一種、基于、研究、分析、實現(xiàn)、應用、可以、開發(fā)、我們、提出、針對、采用、構建、技術、方法、系統(tǒng)、介紹、探討、問題、能夠、與、本文），使用該詞表從文本中刪除不需要的詞匯。

2.3.2自動分詞。從文檔中自動提取詞匯是一個研究的熱點和難點，也是自動構建詞表的一個難點。從漢語文檔中自動抽詞較英文更為困難，這是由于中文詞匯組合成句進而成篇時不像英文那樣用空格作為詞匯的間隔符。目前，常用的分詞方法基本上分為基于規(guī)則的方法、基于統(tǒng)計的方法以及兩者的結合。本文使用統(tǒng)計分詞方法中常用的Viterbi算法［2］進行自動分詞。

2.3.3分詞結果過濾。由于漢語中的詞匯絕大多數(shù)是由兩個或兩個以上的單漢字構成，而用來表示概念的單漢字詞匯較少，所以，首先去除分詞結果中的單漢字。然后在文獻的正文中搜索兩個漢字或兩個漢字以上的詞匯以及英文單詞，記錄詞匯在文獻正文中出現(xiàn)的次數(shù)，如果出現(xiàn)次數(shù)低于設定的閾值，說明該詞匯在文獻中提及較少，不能作為代表文獻主題的詞匯，將其過濾掉。將最后得到的詞匯分別讀取到詞匯數(shù)據(jù)表中，詞匯數(shù)據(jù)表元數(shù)據(jù)包括：詞匯編號、詞匯、所在文獻、出現(xiàn)次數(shù)。

2.3.4建立同現(xiàn)詞匯網(wǎng)絡。把收集到的詞匯按照同現(xiàn)頻率構造成同現(xiàn)關系網(wǎng)絡，其作用：一是為圖論聚類提供基礎，二是雖然同現(xiàn)詞匯網(wǎng)絡不包含詞匯間各種具體的語義關系，但可部分體現(xiàn)出詞匯的關聯(lián)。步驟如下：

Step1.把經過停用詞過濾、自動分詞和分詞結果過濾所得的詞匯作為同現(xiàn)詞匯網(wǎng)絡中的結點。

Step2.應用窗口機制選擇一定數(shù)量的詞匯建立詞匯網(wǎng)絡，該窗口可以是一篇文章、某個時間段內的所有領域文獻、某一個專題的文獻等，詞匯結點如果處于同一個窗口就將兩個同現(xiàn)的詞匯結點用同現(xiàn)邊連接起來，得到詞匯網(wǎng)絡。

Step3.確定詞匯結點之間同現(xiàn)邊（wi，wj）的權值dij。

其中，P（wi∩wj）表示詞匯結點wi和wj同時出現(xiàn)的頻率，P（wi）表示詞匯結點wi出現(xiàn)的頻率。

2.4詞匯的自動定位

2.4.1 PageRank算法。針對某個詞匯可能在窗口中出現(xiàn)次數(shù)較多，但對于整個領域來講并不十分重要的現(xiàn)象，需要計算每一個詞匯在領域中的重要度，借用Google搜索引擎網(wǎng)頁排序PageRank算法［3］為每個詞匯結點分配一個重要度指數(shù)。由于詞匯同現(xiàn)網(wǎng)絡是無向圖，結點的PageRank值的計算公式為：

其中d為取值范圍為0-1的阻尼因子，一般為0.85；weight（Eij）表示結點Vi和Vj之間邊的權值；C（Vi）表示與結點Vi相連的結點集合；D（Vj）為結點Vj的度。

2.4.2圖論聚類算法。圖論聚類方法的算法思想是首先得到圖的最小生成樹，然后按照一定的規(guī)則刪除其中不需要的某些邊，得到連通分支數(shù)大于1的非連通圖，每一個連通分支為一個聚類。本文應用Prim算法得到詞匯網(wǎng)絡的最小生成樹，然后查找所有已經存在于后控詞表之中的正式詞，把這些正式詞作為聚類簇的中心詞，詞匯網(wǎng)絡中正式詞的數(shù)量即為聚類簇的數(shù)量。然后按照設定的百分比閾值選擇出與中心詞相關程度最大的一些詞匯作為中心詞的一級相關詞，其余未被選中的詞匯結點和中心詞之間的邊從最小生成樹中刪除，然后再以一級相關詞作為中心按照百分比閾值選擇出中心詞的第二級相關詞，再刪除一些邊，對于同時和不同的中心詞相關程度均較大的結點作為聚類簇相交的結點，同時存在于不同的聚類簇中。從而得到以正式詞為中心的輻射狀聚類簇。

2.4.3詞匯的定位。以每一個詞匯的PageRank值和詞匯與中心詞同現(xiàn)頻率的乘積為依據(jù)，選擇出乘積最大的詞匯作為正式詞的入口詞添加到后控詞表中。

3　實驗結果

規(guī)范化后的文獻元數(shù)據(jù)格式以及經過停用詞過濾、自動分詞和分詞結果過濾的結果示例，如表1。

表1　規(guī)范化文獻元數(shù)據(jù)格式以及自動抽取詞匯結果示例

表2　3個窗口時聚類簇中詞匯的PageRank值及PageRank（wi）*P（wi，w中心詞）

以文獻作為窗口，首先選擇3個窗口的詞匯，建立同現(xiàn)詞匯網(wǎng)絡作為圖論聚類的初始數(shù)據(jù)，設定百分比閾值為60%，根據(jù)圖論聚類后得到的結果可以作為正式詞的備選詞匯。例如，“分類”的入口詞的詞匯是以“分類”為中心的聚類中的所有詞匯，計算這些詞匯的PageRank值。比較同一個聚類簇中的詞匯PageRank（wi）*P（wi，w中心詞）值，選擇數(shù)值最大的詞匯作為入口詞添加到后控詞表中。

據(jù)表2所示，“分類”聚類簇中選擇“分類體系”作為入口詞，“圖書館”聚類簇中選擇“rss”作為入口詞，將這兩個詞添加到后控詞表中，并把它們之間的關系確定為同現(xiàn)關系。

將窗口數(shù)增至6個時，詞匯網(wǎng)絡、聚類結果、PageRank值及PageRank（wi）*P（wi，w中心詞），如表3所示。

據(jù)表3所示，“分類”聚類簇中選擇“XML”作為入口詞，“圖書館”聚類簇中選擇“數(shù)字圖書館”作為入口詞。

表3　6個窗口時的聚類簇中詞匯的PageRank值及PageRank（wi）*P（wi，w中心詞）

4　結語

通過實驗驗證結果達到穩(wěn)定所需的語料規(guī)模和窗口數(shù)量。詞匯網(wǎng)絡圖中的詞匯結點要達到相當規(guī)模才能使結果比較穩(wěn)定，但是，本文實驗的語料庫還未達到所需數(shù)量，因此結果并不穩(wěn)定，需要擴大語料庫的規(guī)模。雖然詞匯網(wǎng)絡規(guī)模越大得到的結果越穩(wěn)定，但是，詞匯網(wǎng)絡規(guī)模的增加意味著算法運行的空間和時間耗費增加，所以，還要通過實驗得到合適的語料規(guī)模和窗口數(shù)量，使之既能夠得到穩(wěn)定的結果，又不浪費空間和時間資源。

考察該方法由構建圖書館情報檔案領域后控詞表推廣到構建其他領域以及跨領域后控詞表的適用性。本文僅從一個領域對這一方法進行了實驗驗證，下一步還需要收集其他領域文獻作為實驗數(shù)據(jù)進行相應領域后控詞表的自動構建，驗證該方法的通用性，進而驗證構建跨領域后控詞表的可行性。

參考文獻：

［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］王軍.詞表的自動豐富——從元數(shù)據(jù)中提取關鍵詞及其定位［J］.中文信息學報，2005（6）:36-43.

［7］朱偉麗，韓宇，肖曉旦，陳先來.醫(yī)學關鍵詞與敘詞對照表自動構建研究［J］，現(xiàn)代圖書情報技術，2006（8）:51-54.

［8］章成志，蘇蘭芳，蘇新寧.基于多語境的相關詞自動提取系統(tǒng)的設計與實現(xiàn)［J］.現(xiàn)代圖書情報技術，2006（9）.

［9］屈婉玲，耿素云，張立昂.離散數(shù)學［M］.北京:清華大學出版社，2004.

［10］崔光照，曹玲芝，勛才，延峰.基于密度的最小生成樹聚類算法研究［J］.計算機工程與應用，2006（5）:156-158、164.

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

作者簡介：李法軍（1976-），男，碩士，館員，研究方向：電子文件管理，電子病案管理。

基金項目：國家社會科學基金青年項目（13CTQ046）。

收稿日期：2015-10-8

［中圖分類號］TP391.1

［文獻標識碼］A

文章編號：1671-0037（2015）11-77-4