一種基于知識粒度的關鍵詞提取方法

楊淑棉,劉劍

(1. 齊魯工業大學(山東省科學院)，山東省計算中心(國家超級計算濟南中心)，山東省計算機網絡重點實驗室，山東 濟南 250014; 2. 濟南高新區齊魯軟件園發展中心，山東 濟南 250101)

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

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

1 信息粒度的相關概念

1.1 知識粒概念

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

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

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

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

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

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

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

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

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

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

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

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

2 文本預處理方法

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

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

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

3 關鍵詞提取算法

3.1 算法思想

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

3.2 算法描述

依據上述知識粒度、原理及性質，基于知識粒度重要性的關鍵詞提取算法具體描述如下：

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

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

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

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

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

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

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

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

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

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

步驟6：根據統計方法，從單篇文獻中提取關鍵詞，首要考慮關鍵詞的詞性、位置、詞頻、詞跨度等因素計算詞條的權重，選取權重大的為提取的關鍵詞。

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

4 實驗驗證

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

表1 信息系統

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

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

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

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

同樣的道理：

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

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

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

4.2 算法效率驗證

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

表2 算法效率比較

5 結論

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