楊淑棉,劉劍

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

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

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

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

1.1 知識(shí)粒概念

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

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

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

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

1.2 知識(shí)粒重要度的計(jì)算(kgImp)

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

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

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

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

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

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

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

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

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

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

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

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

3.1 算法思想

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

3.2 算法描述

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

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

輸出：文獻(xiàn)所提取的最小的屬性約簡(jiǎn)。

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)驗(yàn)證

給定一個(gè)信息決策系統(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 計(jì)算屬性的知識(shí)粒度和屬性重要度

由于論域U中任何一個(gè)對(duì)象都是不同的，對(duì)象在論域U上劃分是最細(xì)的，則有R的知識(shí)粒度達(dá)到最小值，即：

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

根據(jù)單屬性知識(shí)粒度和在A屬性集上的知識(shí)粒度差值計(jì)算單屬性的重要度值，按降序排序，獲取關(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)鍵詞，此實(shí)驗(yàn)只是驗(yàn)證所有屬性的核不為空的情況，特使用了文獻(xiàn)[11]中數(shù)據(jù)進(jìn)行驗(yàn)證，此結(jié)果和文獻(xiàn)[11]中結(jié)果是一致的。不過(guò)一般情況下，最小約簡(jiǎn)并不是唯一的，本文只是找出不完備信息系統(tǒng)中的一個(gè)約簡(jiǎn)方法。

4.2 算法效率驗(yàn)證

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

表2 算法效率比較

5 結(jié)論

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