一種基于知識粒度的關(guān)鍵詞提取方法

楊淑棉,劉劍

(1. 齊魯工業(yè)大學(xué)(山東省科學(xué)院)，山東省計算中心(國家超級計算濟南中心)，山東省計算機網(wǎng)絡(luò)重點實驗室，山東 濟南 250014; 2. 濟南高新區(qū)齊魯軟件園發(fā)展中心，山東 濟南 250101)

互聯(lián)網(wǎng)的出現(xiàn)使得網(wǎng)上的信息呈爆炸式增長，人們越來越難以查找到有用的信息，網(wǎng)上日益豐富的信息資源靠人工處理和分類更是不太可能，因此如何方便、快捷、準確地獲取所需信息，對各類文本自動處理并進行自動分類成為一個迫切需要解決的問題。關(guān)鍵詞是從報告、論文中選取出來用以表示全文主題的詞語，高度概括了文本的主要內(nèi)容與主題，使不同的讀者很容易判斷文本是否是自己需要的內(nèi)容。關(guān)鍵詞自動提取技術(shù)是文本分類中的一個重點，國內(nèi)外專家對其做了大量的研究，并在提高獲取準確率方面提出了很多的方法，但是關(guān)鍵詞的獲取準確率和效率仍然不高，仍存在許多需要解決的問題。目前，最經(jīng)典的關(guān)鍵詞提取算法是利用詞的統(tǒng)計信息，主要判斷詞的權(quán)重，并設(shè)定閾值，選出權(quán)重較大的、超過一定閾值的詞作為最終的關(guān)鍵詞?，F(xiàn)有中文分詞和詞頻統(tǒng)計相結(jié)合的方法、詞庫匹配法、基于N-gram頻率統(tǒng)計的方法需要依賴于語料庫的規(guī)模和數(shù)量以及詞典和專門的分詞技術(shù)[1]等，漢語詞匯量的編制和維護也是一件很煩瑣的事情，并且使用訓(xùn)練語料庫導(dǎo)致工作量迅猛增加，代價相對高昂，因而局限性大[2]。

信息粒是對現(xiàn)實的抽象，由一系列元素組成，元素之間滿足某種程度上的相似性和不可分辨關(guān)系。本文從信息粒分類的角度對知識進行研究，目前關(guān)于粒度計算已出現(xiàn)在很多領(lǐng)域，如粗集理論、區(qū)間分析、機器學(xué)習(xí)聚類分析等。國內(nèi)外學(xué)者已提出了粒度計算的一些重要模型，這些模型表明粒度計算與粗糙集理論有密切的聯(lián)系。羅燕等[3]提出了基于詞頻統(tǒng)計的文本關(guān)鍵詞提取方法；廖洪建[4]提出一種基于知識粒度的決策系統(tǒng)屬性約簡算法；陳玉明等[5]提出基于相對知識粒度的決策表約簡；景運革等[6]提出基于知識粒度的增量約簡算法； Yao[7]提出利用信息粒度，給出了粗糙集逼近。從現(xiàn)有的成果看，知識粒度已經(jīng)被廣泛應(yīng)用于不完備屬性約簡領(lǐng)域，是粗糙集理論中有效進行屬性約簡的一個重要方法。但是現(xiàn)有的方法由于計算知識粒度浪費了大量的時間，算法效率有待于提高。本文用粗糙集中的等價關(guān)系來刻劃粒，通過計算知識粒的屬性重要度作為一種啟發(fā)式信息，使用Tabu局部搜索算法，提出一種關(guān)鍵詞獲取方法，此方法大大降低了算法的時間復(fù)雜度，提高了算法的效率，而且克服了張雪英[8]提出的基于GF/GL權(quán)重法的局限。

1 信息粒度的相關(guān)概念

1.1 知識粒概念

知識粒的定義：設(shè)S=(U,R)是一個信息系統(tǒng)，其中U是對象的非空有限集，稱為論域，R是屬性的有限集，U/IND(R)={[x]R|x∈U}表示不可分辨關(guān)系IND(R)在U上導(dǎo)出的劃分，也稱為R的劃分或信息粒度，其中[x]R={y∈U|(x,y)∈IND(R)}記為R的等價類或R知識粒。

定理1[9]：設(shè)S=(U,R)是一個信息系統(tǒng)，P?R，若U/IND(R)

定理2：設(shè)S=(U,R)是一個信息系統(tǒng)，P?R，則U/IND(R)=U/IND(P)的充要條件是gk(R)=gk(P)。

約束1：關(guān)鍵詞長度是不確定的，存在一定范圍限制。為盡可能減少系統(tǒng)的計算時間，中英文粒度的最大抽取長度分別是15和5。英文的每個單詞都被看作是一個漢字[4]。

1.2 知識粒重要度的計算(kgImp)

利用知識粒度，可以分析信息系統(tǒng)中每一個屬性的重要性，主要方法：信息系統(tǒng)S=(U,R)中，設(shè)r∈R是一屬性，用從R中去掉r后引起的知識粒度變化的大小來衡量r對于R的重要度，變化越大，認為r對于R越重要。這里主要計算粒的重要度來衡量詞在文獻中的重要程度，重要度用Imp來表示，知識粒度用gk來表示。

知識粒重要度計算：設(shè)S=(U,R)是一個信息系統(tǒng)，屬性r在R中的重要度表示為ImpR-r(r)=gk(R-{r})-gk(R)，特別地，當(dāng)R={r}時,ImpR-r(r)=Imp?(r)=gk(?)-gk(r)=1-gk(r),其中U/IND(?)={U}，gk(?)=1。由以上公式可以知道：U/IND(?)={U}

性質(zhì)1：屬性r∈R在R中是必要的等價條件是當(dāng)且僅當(dāng)ImpR-r(r)>0。

性質(zhì)2：0?ImpR-r(r)?1-1/U。

屬性重要度值：設(shè)S=(U,R)是一個信息系統(tǒng)，P?R是屬性集，任意屬性a∈R-P對于R的重要度為ImpR(a)=Impp∪a-{a}(a)=gk(p)-gk(p∪{a})，由定義知：

性質(zhì)3：屬性a∈R在R中的必要條件必滿足ImpR(a)>0。

基于以上知識粒度的概念和知識粒的重要性，本文提出了一種新的關(guān)鍵詞的獲取方法。

2 文本預(yù)處理方法

大規(guī)模文本分類和文本信息檢索之前最基本前提是收集數(shù)據(jù)，收集數(shù)據(jù)的方法一般是使用別人做好的語料庫和自己用爬蟲爬取需要的語料數(shù)據(jù)，本實驗使用現(xiàn)有的語料庫。另一個環(huán)節(jié)是文本的預(yù)處理，目標是將文本轉(zhuǎn)變成結(jié)構(gòu)化的數(shù)據(jù)形式，一般使用向量空間模型、語義網(wǎng)絡(luò)、框架模型等來表示文本。本文采用一種基于粒度重要性的文本表示方法，使用決策信息表和粒表示文本，首先我們需要對文本進行預(yù)處理，主要包括：

(1)建立停用詞表，包括缺乏檢索意義的詞、頻繁出現(xiàn)在文本中但分詞不正確、語義不明確的詞等。(2)文本預(yù)處理：對文本進行掃描，把標點、數(shù)字、非漢字字符、助詞、連詞、感嘆詞等都用空格替代；把缺乏檢索意義的詞比如就是、很、非常等用空格替代；把語義不明確的詞用空格替代。(3)用二元語法(2-gram)抽取任意長度的詞，按照李秀紅等[10]的方法提取所有滿足限制條件的字符串。(4)詞的表示：使用信息決策表知識表達系統(tǒng)表示以上生成的任意長度的字符串。(5)根據(jù)知識粒定義的概念、原理和所提供的性質(zhì)，計算每一個屬性的重要度值，根據(jù)重要度值的大小，獲取文獻的關(guān)鍵詞。流程如圖1所示。

圖1 文本關(guān)鍵詞獲取方法流程Fig.1 Keyword acquisition process of text documents

3 關(guān)鍵詞提取算法

3.1 算法思想

知識粒度度量了知識的粗細程度，利用知識粒度的概念、原理、性質(zhì)，當(dāng)一些屬性增加到?jīng)Q策表后，可以使原有的決策表的知識粒度發(fā)生變化，我們利用了決策表中任一屬性的增加對知識粒變化的大小來衡量屬性的重要程度，可計算出信息系統(tǒng)中每一個屬性的重要度值，并以重要度值的大小確定此屬性對文本的重要程度，用此種思路來提取文本中的關(guān)鍵詞。首先，根據(jù)知識粒的定義，計算決策系統(tǒng)中所有屬性核的大小Core，然后增加任一屬性之后對屬性內(nèi)核影響程度，計算出屬性重要度值，由知識重要度(KgImp)的計算公式ImpR-r(r)=gk(R-{r})-gk(R)，根據(jù)性質(zhì)1、性質(zhì)2和性質(zhì)3，可以從信息決策系統(tǒng)中提取文本文獻中的關(guān)鍵詞，增加屬性后，對于核的重要度值變化越大，說明屬性a對于內(nèi)核Core(R)越重要,最后根據(jù)求出的重要度值的大小，進行排序，取重要度值大的作為要提取的關(guān)鍵詞。

3.2 算法描述

依據(jù)上述知識粒度、原理及性質(zhì)，基于知識粒度重要性的關(guān)鍵詞提取算法具體描述如下：

輸入：信息系統(tǒng)S=(U,P),其中，P是文本文獻預(yù)處理之后得到的詞條。

輸出：文獻所提取的最小的屬性約簡。

步驟1：輸入預(yù)處理之后的所有詞條P，建立信息決策系統(tǒng)列表Gklist。

步驟2：計算列表Gklist屬性的核Core(P)，/*組成核的所有屬性記為P*/。

步驟3: 判斷屬性核Core(P)是否為空。

如果Core(P)為空，轉(zhuǎn)步驟6

否則，轉(zhuǎn)步驟4 /*核為空說明這組文獻是特殊文獻，如新聞稿，需要單獨處理論域中的每一個對象，根據(jù)權(quán)重提取關(guān)鍵詞*/。

步驟4：計算列表Gklist中任一a∈R-P，此步使用基于Tabu算法，搜索空間的a，計算這一屬性對核core(P)的重要度值ImpP(a)，重要度值大于0的詞組成關(guān)鍵詞集合

步驟5：根據(jù)步驟4計算出來的ImpP(a)的值給所有大于0的詞條排序，取重要度值大的作為要提取的關(guān)鍵詞。

1）做好頂層設(shè)計，助推實驗室管理制度體系化。設(shè)立由單位領(lǐng)導(dǎo)及各相關(guān)部門負責(zé)人組成的實驗室安全管理委員會，按專業(yè)類別下設(shè)實驗室安全專家咨詢組，例如：化學(xué)、生物、輻射、環(huán)境保護、特種設(shè)備、職業(yè)健康等安全專家咨詢組；為委員會評價和審核各項管理制度、安全手冊、規(guī)范及細則等提供專業(yè)性意見或建議，促進實驗室管理制度體系化發(fā)展。

步驟6：根據(jù)統(tǒng)計方法，從單篇文獻中提取關(guān)鍵詞，首要考慮關(guān)鍵詞的詞性、位置、詞頻、詞跨度等因素計算詞條的權(quán)重，選取權(quán)重大的為提取的關(guān)鍵詞。

由算法可知，先增減哪個字符串計算的屬性重要度值是不一樣的，因此下一步的問題是解決怎樣克服增減字符串順序引起的重要度值不同的問題。

4 實驗驗證

給定一個信息決策系統(tǒng)[11]IS=(U,A,V,f)，其中U={X1,X2,X3,X4,X5,X6}，A={a,b,c,d}如表1所示。

表1 信息系統(tǒng)

4.1 計算屬性的知識粒度和屬性重要度

由于論域U中任何一個對象都是不同的，對象在論域U上劃分是最細的，則有R的知識粒度達到最小值，即：

gk(A-{A})=14/36; gk(B-{B})=12/36; gk(C-{C})=12/36;

根據(jù)單屬性知識粒度和在A屬性集上的知識粒度差值計算單屬性的重要度值，按降序排序，獲取關(guān)鍵詞，分別為：

同樣的道理：

Imp(b)=18/36-1/6=12/36>0;

Imp(c)=12/36-1/6=6/36>0。

排序之后，單屬性遞減序列為b,a,c，取前幾位作為文本集的關(guān)鍵詞，此實驗只是驗證所有屬性的核不為空的情況，特使用了文獻[11]中數(shù)據(jù)進行驗證，此結(jié)果和文獻[11]中結(jié)果是一致的。不過一般情況下，最小約簡并不是唯一的，本文只是找出不完備信息系統(tǒng)中的一個約簡方法。

4.2 算法效率驗證

選用決策表1和UCI 機器學(xué)習(xí)數(shù)據(jù)庫中的4個決策表在Inter(R) Core i5-2500 3.3GHZ CPU，4G 內(nèi)存，Windows7 機器上進行實驗，數(shù)據(jù)庫采用MySql 5.1，與王玨等[12]和劉少輝等[13]的兩種算法進行對比，這兩種算法簡稱為算法1、算法2，本文中的算法簡稱算法3。實驗結(jié)果如表2所示。從表2三種算法效率比較可知，當(dāng)決策表實例數(shù)小于100時，算法3 與算法1、算法2在約簡后執(zhí)行時間上無明顯區(qū)別。當(dāng)決策表的實例數(shù)大于300時，算法1比算法2和3的效率低很多，后兩種算法在實例數(shù)較大時則比較接近，從而我們確認，后兩種算法更適用于大型的數(shù)據(jù)分析。單純的執(zhí)行時間上看，算法2又比算法3效率低一些。從表2約簡前后屬性個數(shù)比較可知，約簡前，算法2 的中間結(jié)果含有較多的無用屬性，仍需大量的工作才能得到理想的約簡結(jié)果，最后算法3中使用Tabu算法和屬性重要度的這一啟發(fā)式策略，算法3 的約簡前后的中間結(jié)果明顯優(yōu)于算法2，免除了大量的重復(fù)工作，進一步驗證了Tabu算法與引入屬性重要度這一啟發(fā)式策略的有效性及正確性。

表2 算法效率比較

5 結(jié)論

本文利用粗糙集中的等價關(guān)系刻劃知識粒度，將粒計算理論中的知識粒度概念應(yīng)用于文本處理中，闡述了知識粒度的概念、原理、性質(zhì)，給出了屬性重要度的計算方法，并利用知識粒的屬性重要性為啟發(fā)式信息給出了信息決策系統(tǒng)的約簡算法，最后提出了一種新的關(guān)鍵詞獲取方法。該方法充分利用了粒計算理論處理不確定數(shù)據(jù)方面的優(yōu)勢，并在此基礎(chǔ)上使用了Tabu局部搜索算法，去除可省屬性并減少了可搜索空間，提高了提取效率。本文在關(guān)鍵詞提取方面作了探索性的工作，經(jīng)實例驗證，此算法是有效的，能提取出等價類的最小關(guān)鍵詞集合。下一步計劃根據(jù)此算法提取出的關(guān)鍵詞集合獲取文本分類規(guī)則，從而對大文本數(shù)據(jù)集進行快速有效的分類。