李法軍

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

?

基于圖論聚類和PageeRRaannkk的領(lǐng)域后控詞表自動(dòng)構(gòu)建研究

李法軍

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

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

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

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

1　基于圖論聚類和PageRank原理進(jìn)行領(lǐng)域后控詞表自動(dòng)構(gòu)建的總體思路

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

2　基于圖論聚類和PageRank原理進(jìn)行領(lǐng)域后控詞表自動(dòng)構(gòu)建的原型構(gòu)建

2.1后控詞表結(jié)構(gòu)及初始內(nèi)容的建立

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

2.2規(guī)范化語(yǔ)料庫(kù)的建立

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

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

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

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

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

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

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

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

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

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

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

2.4詞匯的自動(dòng)定位

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

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

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

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

3　實(shí)驗(yàn)結(jié)果

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

表1　規(guī)范化文獻(xiàn)元數(shù)據(jù)格式以及自動(dòng)抽取詞匯結(jié)果示例

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

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

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

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

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

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

4　結(jié)語(yǔ)

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

考察該方法由構(gòu)建圖書館情報(bào)檔案領(lǐng)域后控詞表推廣到構(gòu)建其他領(lǐng)域以及跨領(lǐng)域后控詞表的適用性。本文僅從一個(gè)領(lǐng)域?qū)@一方法進(jìn)行了實(shí)驗(yàn)驗(yàn)證，下一步還需要收集其他領(lǐng)域文獻(xiàn)作為實(shí)驗(yàn)數(shù)據(jù)進(jìn)行相應(yīng)領(lǐng)域后控詞表的自動(dòng)構(gòu)建，驗(yàn)證該方法的通用性，進(jìn)而驗(yàn)證構(gòu)建跨領(lǐng)域后控詞表的可行性。

參考文獻(xiàn)：

［1］張琪玉.論后控詞表［J］.圖書館情報(bào)工作，1994（1）:1-4.

［2］劉穎.計(jì)算機(jī)語(yǔ)言學(xué)［M］.北京：清華大學(xué)出版社，2002.

［3］陸勇，侯漢清.基于PageRank算法的漢語(yǔ)同義詞自動(dòng)識(shí)別［J］.西華大學(xué)學(xué)報(bào):自然科學(xué)，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］王軍.詞表的自動(dòng)豐富——從元數(shù)據(jù)中提取關(guān)鍵詞及其定位［J］.中文信息學(xué)報(bào)，2005（6）:36-43.

［7］朱偉麗，韓宇，肖曉旦，陳先來(lái).醫(yī)學(xué)關(guān)鍵詞與敘詞對(duì)照表自動(dòng)構(gòu)建研究［J］，現(xiàn)代圖書情報(bào)技術(shù)，2006（8）:51-54.

［8］章成志，蘇蘭芳，蘇新寧.基于多語(yǔ)境的相關(guān)詞自動(dòng)提取系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)［J］.現(xiàn)代圖書情報(bào)技術(shù)，2006（9）.

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

［10］崔光照，曹玲芝，勛才，延峰.基于密度的最小生成樹聚類算法研究［J］.計(jì)算機(jī)工程與應(yīng)用，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

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

基金項(xiàng)目：國(guó)家社會(huì)科學(xué)基金青年項(xiàng)目（13CTQ046）。

收稿日期：2015-10-8

［中圖分類號(hào)］TP391.1

［文獻(xiàn)標(biāo)識(shí)碼］A

文章編號(hào)：1671-0037（2015）11-77-4