基于信息熵與動態(tài)聚類的文本特征選擇方法

唐立力

TANG Lili

重慶工商大學(xué) 融智學(xué)院，重慶400033

Rongzhi College of Chongqing Technology and Business University,Chongqing 400033,China

1 引言

文本特征向量的高維性是文本分類的瓶頸，特征選擇是文本特征向量降維的一種方式，它是實現(xiàn)文本高效分類的前提，是文本自動分類的一個重要環(huán)節(jié)，特征選擇算法的性能將直接影響分類系統(tǒng)的最終效果。目前，用于文本特征選擇的方法主要有以下幾種：互信息（Mutual Information，MI）[1]、信息增益方法（Information Gain，IG）[2]、x2 統(tǒng)計量方法（CHI）[3]、文檔頻方法（Document Frequency，DF）[4]等。雖然這些主流方法獲得了較好的特征詞提取效果，但是用于科技文獻的特征詞提取卻有許多不足，例如：互信息（MI）的不足在于它對臨界特征的概率比較敏感，當(dāng)兩個特征的條件概率相等時，p(f)（這里p(f)指的是特征f在全部文檔中出現(xiàn)的概率）較小的詞（也即稀有詞）比p(f)大的詞（也即普通詞）的互信息分值要高，因此，對于概率相差太大的兩特征來說，它們的互信息值不具有可比性[5]。信息增益方法（IG）的不足在于它不但考慮了特征出現(xiàn)的情況，而且還考慮了特征未出現(xiàn)兩種情況，即使某個特征不在文本中出現(xiàn)也可能對判斷文本類別有所貢獻。但實驗證明，這種貢獻十分微小，尤其是在樣本分布和特征分布失衡的情況下，某些類別中出現(xiàn)的特征詞在全部特征詞的比例很小，較大比例的特征詞在這些類別中是不存在的，也就是此時的信息增益中特征不出現(xiàn)的部分占絕大優(yōu)勢，這將導(dǎo)致信息增益的效果大大降低[6]。x2 統(tǒng)計量方法（CHI）主要缺點在于它對低頻詞的測量不一定準(zhǔn)確[7]。文檔頻方法（DF）的不足在于它僅考慮特征詞在文檔中出現(xiàn)與否，忽視了在文檔中出現(xiàn)的次數(shù)。這樣就產(chǎn)生了一個問題：如果特征詞a 和b 的文檔頻相同，那么該方法認(rèn)為這兩個特征詞的貢獻是相同的，而忽略了它們在文檔中出現(xiàn)的次數(shù)。但是，通常情況是文檔中僅出現(xiàn)次數(shù)較少的詞是噪聲詞，這樣就導(dǎo)致該方法所選擇的特征不具代表性[7]。

眾所周知，科技文獻主要由標(biāo)題、摘要，關(guān)鍵字，正文等組成，其中最能代表文章主題的是標(biāo)題和關(guān)鍵字，其次是摘要部分，再次是正文的引言和總結(jié)部分，最后是正文的其他部分。在這種情況下，對科技文獻進行分層提取相應(yīng)特征詞就顯得更加合情合理。為了更加精準(zhǔn)地提取特征詞，組建了四層挖掘模式，逐層對科技文獻進行特征選擇。首先對K-means 算法進行改進，然后結(jié)合改進后的K-means 算法和Apriori 算法提出一種新的文本特征選擇方法，對科技文獻進行分類處理。

2 相關(guān)基礎(chǔ)知識

2.1 相關(guān)定義

假設(shè)A={ai|ai∈Rm,i=1,2,…,n}為給定的數(shù)據(jù)集，c(T1),c(T2),…,c(Tk)分別是k個聚類中心，Ti(i=1,2,…,k)代表k個類別。有如下定義：

定義1設(shè)向量ai=(ai1,ai2,…,aim) 和向量aj=(aj1,aj2,…,ajm)分別代表兩個數(shù)據(jù)對象，那么它們之間的歐式距離[8]定義為：

定義2同一類別的數(shù)據(jù)對象的質(zhì)心點[8]定義為：

其中|Ti|是Ti中數(shù)據(jù)對象的個數(shù)。

定義3同屬于Tj組的ni個數(shù)據(jù)對象ai(i=1,2,…,n1)的標(biāo)準(zhǔn)差[8]σ定義為：

2.2 K-means算法

K-means 算法是一種基于樣本間相似性度量的間接聚類方法，也被稱為K-均值算法[9]。算法的主要思想是通過迭代的過程把數(shù)據(jù)集劃分為不同的類別，使得評價聚類性能的準(zhǔn)則函數(shù)達(dá)到最優(yōu)。算法描述如下：

輸入：簇的個數(shù)K與包含n個對象的數(shù)據(jù)集合。

輸出：K個簇，使得準(zhǔn)則函數(shù)值滿足條件。

步驟1為每個聚類確定一個初始聚類中心點。

步驟2將數(shù)據(jù)集中的數(shù)據(jù)按照歐氏距離原則分配到最鄰近簇。

步驟3使用每個簇中的樣本數(shù)據(jù)均值作為新的聚類中心。

步驟4重復(fù)步驟步驟2 與步驟3 直至算法收斂。

步驟5結(jié)束，得到K個結(jié)果簇。

2.3 關(guān)聯(lián)規(guī)則與Apriori算法

Apriori 算法是一種逐層迭代挖掘關(guān)聯(lián)規(guī)則的頻繁項集算法，其核心思想是通過候選集生成和情節(jié)的向下封閉檢測兩個階段來尋找數(shù)據(jù)項之間的關(guān)聯(lián)關(guān)系[10]。首先找出頻繁1-項集的集合。通過頻繁1-項集來尋找頻繁2-項集，…，通過(k-1)項集尋找k項集合，直至找到最大頻繁項集合。Apriori 算法使用如下性質(zhì)來找到K維最大頻繁項集：

性質(zhì)1XK是K維頻繁項集，若所有K-1 維頻繁項集集合XK-1 中包含XK的K-1 維子項集的個數(shù)小于K，那么XK不可能為K維最大頻繁項集。

K的值每增加1 就需要掃描一次數(shù)據(jù)庫，為了提高頻繁項集的搜索效率，Apriori算法使用下述性質(zhì)用于壓縮搜索空間：

性質(zhì)2若K維數(shù)據(jù)項集XK中有一(k-1)維子集不是頻繁項集，那么X不是頻繁項集。

3 確定K-means算法的初始聚類中心點

傳統(tǒng)的K-means 算法是隨機選擇初始聚類中心點，可能造成在同一類別的樣本被強行當(dāng)做兩個類別的初始聚類中心點，使結(jié)果簇只能收斂于局部最優(yōu)解。因此，為了選出更為合理的初始聚類中心，需要對初始聚類中心進行預(yù)處理，基本思想[11]為：首先把數(shù)據(jù)集平均分成k1(k1＞k)個子集，在每個子集中隨機選出某一數(shù)據(jù)對象，然后把這k1個數(shù)據(jù)對象當(dāng)做聚類種子中心進行初聚類，計算每個類別的賦權(quán)類別價值函數(shù)σi，按照從小到大的順序進行排列，最后把前k個類對應(yīng)的質(zhì)心作為初始聚類的中心點。

通過熵值法[12]確定屬性權(quán)重值的方式選出初始中心點。

步驟1構(gòu)造屬性值矩陣：

其中，n表示樣本數(shù)據(jù)個數(shù)，m為每個數(shù)據(jù)對象的維數(shù)。

步驟2計算第j維屬性對應(yīng)的第i個數(shù)據(jù)對象的屬性值比重。需要對數(shù)據(jù)進行標(biāo)準(zhǔn)化處理，即將數(shù)據(jù)壓縮到區(qū)間[0，1]上，其過程如式（5）[13]所示：

其中，Mij表示屬性值比重，xij代表屬性值，i=1,2,…,n，j=1,2,…,m。

步驟3計算第j維屬性的熵值：

步驟4計算第j維屬性的差異性系數(shù)：

其中，qj為差異性系數(shù)。對于給定的j，當(dāng)Hj越小時，qj越大，屬性就越重要。

步驟5第j維的屬性權(quán)值[14]的計算：

步驟6使用歐式距離計算數(shù)據(jù)對象之間的相似性，根據(jù)定義1 可得賦權(quán)后的歐式距離為：

其中，ωj是第j 維屬性的權(quán)值。相當(dāng)于使權(quán)值對應(yīng)的屬性值進行了適當(dāng)?shù)姆糯蠡蚩s小，使權(quán)值大的屬性聚類作用更大，權(quán)值小的屬性聚類作用更小。

步驟7采用標(biāo)準(zhǔn)差作為標(biāo)準(zhǔn)測度函數(shù)，由定義3 求得賦權(quán)類別目標(biāo)價值函數(shù)為：

其中，σi表示第i 類的賦權(quán)標(biāo)準(zhǔn)差，|Tj|是Tj所含數(shù)據(jù)對象的個數(shù)。由公式可知，σi的值越小，類內(nèi)數(shù)據(jù)對象相似度越大，數(shù)據(jù)對象越密集，其所在類的質(zhì)心越能夠體現(xiàn)分類決策面。

4 基于信息熵的K-means動態(tài)聚類算法

4.1 K-means動態(tài)聚類

在樣本數(shù)據(jù)聚類的過程中，不僅需要計算每個聚類對象與他們中心對象的距離，還需要重新計算中心對象發(fā)生變化的聚類的均值，且計算是在一次次迭代中重復(fù)的完成，當(dāng)數(shù)據(jù)樣本較多時，過大的計算量會嚴(yán)重影響算法的性能。其次，由于K-means 聚類是個動態(tài)變化的過程，聚類的過程中將產(chǎn)生一些冗余信息，會對聚類產(chǎn)生一些不必要的干擾。針對K-means 算法的以上缺陷，提出兩點優(yōu)化原則：（1）減少聚類過程中的迭代次數(shù)。（2）減少聚類過程中的數(shù)據(jù)量。K-means 動態(tài)聚類算法的基本思想：由于K-means 算法是通過迭代的過程把數(shù)據(jù)集劃分為不同的類別，現(xiàn)為中心點的該變量設(shè)定一個值β1，在迭代的過程中，當(dāng)中心點的改變量小于β1時，將整個簇加入到已選數(shù)據(jù)集，并將其從樣本集中刪除，使得原始樣本數(shù)據(jù)集中只保留未被正確識別的樣本。由定義2 求得中心點的改變量計算公式為：

其中，r為算法迭代次數(shù)，Tr,i表示第r次迭代的第i個類別。當(dāng)βr≤β1時，滿足條件，對其他樣本進行篩選，直到所有樣本數(shù)據(jù)都被正確識別。

4.2 基于信息熵的K-means動態(tài)聚類算法描述

結(jié)合基于信息熵的賦權(quán)方法與K-means 的動態(tài)聚類對數(shù)據(jù)集合進行聚類處理，算法流程如圖1 所示。

算法步驟描述如下：

輸入：數(shù)據(jù)對象集A，聚類種子初始中心點個數(shù)k1。

輸出：K個結(jié)果簇，使每個聚類中心點的改變量小于設(shè)定的值，直至數(shù)據(jù)對象集合為?。

步驟1依據(jù)經(jīng)驗規(guī)律確定聚類數(shù)K值在2 到之間，其中N為數(shù)據(jù)空間中的所有數(shù)據(jù)點的個數(shù)。通過在區(qū)間逐個選取K值，并利用聚類有效性函數(shù)來評價聚類的效果。最終得到最優(yōu)的K值。

步驟2使用熵值法計算數(shù)據(jù)對象各個屬性的權(quán)值。

步驟3將數(shù)據(jù)集平均分成k1(k1＞k)個子集，從各個子集中隨機選出一個數(shù)據(jù)對象，并將其作為聚類種子中心。

圖1 基于信息熵的K-means動態(tài)聚類流程圖

步驟4掃描數(shù)據(jù)集合，根據(jù)其與各聚類種子中心的相似度（賦權(quán)后的歐式距離），將其歸于與其最相似的簇中。

步驟5計算k1個聚類的σi(i=1,2,…,k1)，并按照σi值遞增順序排序，選前k個σi值對對應(yīng)的質(zhì)心作為初始聚類中心。

步驟6將樣本集中的樣本按照歐式距離原則分配到最鄰近的簇中。

步驟7計算每個類的質(zhì)心點。

步驟8判斷聚類中心點的改變量是否滿足設(shè)定的條件，如果滿足，將其加入到已選特征集，同時將它從數(shù)據(jù)樣本集中刪除。

步驟9判斷數(shù)據(jù)樣本集是否為空，如果為空，結(jié)束算法。如果不為空，遍歷中心點個數(shù)N，當(dāng)N＜K時，轉(zhuǎn)向步驟6，當(dāng)N=K值時，繼續(xù)下一步。

步驟10更新中心點。計算每個聚類中心點的改變量大于設(shè)定值的簇的質(zhì)心，并將其作為新的聚類中心，然后轉(zhuǎn)向步驟6。

步驟11結(jié)束，數(shù)據(jù)樣本為空集，得到K個結(jié)果簇。

5 結(jié)合K-means和Apriori算法的四層挖掘模式

本文根據(jù)科技文獻的結(jié)構(gòu)特點提出四層挖掘模式，將K-means 聚類分析方法應(yīng)用于該模式的前三層，將Apriori方法應(yīng)用于第四層，逐層實現(xiàn)特征選擇?？萍嘉墨I特征提取的流程圖，如圖2 所示。

圖2 科技文獻特征選擇流程圖

其基本思想：首先將挖掘過程分為如下四層，標(biāo)題與關(guān)鍵字為第一層，摘要為第二層，文獻引言與總結(jié)部分為第三層，正文的其他部分為第四層；然后將第一層的一級特征詞的個數(shù)來確定K值，通過熵值法確定屬性權(quán)重值的方式選出初始中心點，將樣本集中的樣本按照歐式距離原則分配到最鄰近的簇中；其次計算每個簇的平均值，并用該平均值代表相應(yīng)的簇，中心點若有改變，重復(fù)該步驟，直到算法收斂，得到K個結(jié)果簇；在每個簇中選擇一個或多個代表詞作為二級特征詞，并根據(jù)二級特征詞的數(shù)量來確定第三層K值。步驟相同，待算法收斂時得到三級特征詞。正文部分屬于四層挖掘模式中的第四層，由于該部分?jǐn)?shù)據(jù)量大，且所含有效信息量較少[14]，本文采用Apriori算法對其進頻繁項集的挖掘。將提取出的頻繁項集和三級特征詞進行比較，消除重復(fù)詞，最終得出特征詞集。

5.1 獲取前三級特征詞

對科技文獻標(biāo)題、關(guān)鍵字用漢語分詞系統(tǒng)進行切分，經(jīng)去停用詞處理，得出一級特征詞，作為第二層正文的引言和總結(jié)部分聚類算法的中心點。例如文獻標(biāo)題為：基于潛在語義分析的微博主題挖掘模型研究，關(guān)鍵字為：微博、短文本、主題挖掘、LDA 模型、增量聚類，得到的切分效果如圖3 所示。

圖3 漢語自動分詞系統(tǒng)

對文獻的摘要部分用上文提到的漢語分詞系統(tǒng)進行分詞處理，經(jīng)過去停用詞處理得到得到文獻語料庫（A）。采用基于信息熵的K-means 動態(tài)聚類算法對其進行特征選擇，然后對每個簇選擇一個或多個代表詞作為二級特征詞，并將其作為下一層聚類的初始中心點。

引言主要介紹該文獻主題的應(yīng)用背景，目前所取得的一些成果、所處的一個階段及存在的不足之處，段尾是對該文獻的總結(jié)和展望。用漢語分詞系統(tǒng)對段首和段尾文本進行切分，切分出的單詞經(jīng)過去停用詞處理后，形成文獻語料庫（B）。三級特征詞提取過程同二級特征詞提取過程類似。

5.2 獲取四級特征詞

用相同的方法對正文部分?jǐn)?shù)據(jù)處理得到文獻語料庫（C），由于科技文獻的正文部分?jǐn)?shù)據(jù)量較大，特征詞的密度相對較小。適合采用挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的方法進行頻繁項的抽取。

步驟1掃描文獻語料庫（C）中的數(shù)據(jù)信息，產(chǎn)生頻繁的1-項集。

步驟2由頻繁1-項集經(jīng)過兩兩結(jié)合生成頻繁的2-項集。

步驟3通過頻繁(k-1)-項集產(chǎn)生k-項集候選集。

如果在兩個頻繁的(k-1)-項集只有最后一個元素不同，其他都相同，那么這兩個(k-1)-項集項集可以“連接”為一個k-項集；如果不能連接，將其舍棄。

步驟4從候選集中剔除非頻繁項集。

如果候選集中某個k-項集的子項集不在頻繁的(k-1)-項集中，將其刪除。

步驟5掃描文獻語料庫（C），計算候選項集的支持度，將其與最小支持度比較，從而得到K維頻繁項集。直至生成最大項集；否則轉(zhuǎn)向步驟3。

步驟6將挖掘出的頻繁項經(jīng)過頻率過濾和名詞剪枝，得到評價對象集，作為四級特征詞。

將提取出的頻繁項集和三級特征詞進行比較，消除重復(fù)詞，最終得出特征詞集。

6 仿真實驗及結(jié)果分析

6.1 仿真實驗

在中國知網(wǎng)上搜集1 320 篇屬于計算機行業(yè)的科技文獻，660 篇作為實驗數(shù)據(jù)的訓(xùn)練集，其余作為測試集。其中160 篇主題為“離散化”的文獻，440 篇主題為“綠色網(wǎng)絡(luò)”的文獻，720 篇主題為“特征選擇”的文獻，對660篇訓(xùn)練集均采用以上的方法對其進行特征選擇。前三級特征詞的數(shù)量如表1 所示。

表1 前三級特征詞數(shù)量表

本文以80篇主題為“離散化”的科技文獻作為Apriori算法的實驗數(shù)據(jù)。設(shè)最小支持度為40%，文獻語料庫（C）如表2 所示。

80 篇主題為“離散化”的文獻，經(jīng)過Apriori 算法處理，最終得到39 450 維最大頻繁項集52 組，將52 組數(shù)據(jù)全部組合得到39 608 個特征詞。

6.2 實驗結(jié)果及分析

在實驗中，論文采用空間向量模型（VSM）進行文本表示，經(jīng)過KNN（這里設(shè)定K=20）文本分類算法的訓(xùn)練，形成文本分類器，以此作為實驗測試的工具。

為了驗證本文所提方法的性能，實驗以查全率、查準(zhǔn)率和F值(F=(2×Recall×Precision)/(Recall+Precision)×100%，其中Recall=正確分類的文本數(shù)/應(yīng)有文本數(shù)，Precision= 正確分類的文本數(shù)/實際分類的文本數(shù)）為性能指標(biāo)，使用2012年劉海燕提出的IACA 方法[15]與之做對比，該算法是對主流特征選擇方法—互信息（MI）的改進，采用K-means 算法的基本思想聚類特征，并從中選出類相關(guān)度最大的特征，從而去除不相關(guān)和冗余特征。該算法比較適合處理高維數(shù)據(jù)集，能夠較好地降維，并且達(dá)到不錯的效果。另外，還選擇了兩種主流特征選擇方法：信息增益方法（IG）和x2 統(tǒng)計量方法（CHI）進行對比實驗，表3 為具體實驗結(jié)果。

表2 文獻語料庫（C）

表3 各特征選擇方法實驗對比結(jié)果

從表3可以看出，本文方法都優(yōu)于其他三種特征選擇方法，其優(yōu)劣順序依次為本文方法、IG 方法、CHI 方法和ICAC 方法。經(jīng)分析原因如下：本文方法利用K-means和Apriori 算法進行逐層全面考查待選特征詞，能夠較好地選擇出代表性的特征詞；IG 方法對樣本分布情況極其敏感，如果在樣本分布不均勻的情況下使用該方法，那么它所選擇的特征集代表性就較差，不過本文所選實驗數(shù)據(jù)集分布比較均勻；雖然ICAC 方法是MI方法的一種改進方法，但是它在選擇特征時也僅僅考查了待查特征存在的情況，而CHI 方法不但考查了特征存在的情況而且還考查了特征不存在的情況，因此CHI 方法要優(yōu)于ICAC 方法。

7 結(jié)束語

提出一種針對科技文獻分類的特征詞選擇方法，四層挖掘模式的思想結(jié)合改進后的K-means 動態(tài)聚類算法，解決了K-means 聚類算法不能自動確定K值的問題；選出質(zhì)量較高的初始聚類中心點；通過為算法的終止條件設(shè)定標(biāo)準(zhǔn)值，減少了算法迭代次數(shù)以及學(xué)習(xí)時間；通過刪除由信息動態(tài)變化而產(chǎn)生的冗余信息，減少了動態(tài)聚類過程中的干擾。但該方法也受到一定因素的影響，如K-means 算法對孤立點數(shù)據(jù)很敏感，孤立點會使聚類中心偏離從而影響聚類結(jié)果；Apriori算法在每次計算項集的支持度時，都對文獻語料庫中的所有數(shù)據(jù)進行掃描比較，若是一個大型的文獻語料庫，這種掃描比較會使得計算機系統(tǒng)的I/O 開銷大大增加，而其代價是隨著文獻語料庫記錄的增加呈現(xiàn)出幾何級數(shù)的增加。這些都是今后研究中應(yīng)進一步考慮的問題。

[1] Lee J，Kim D W.Mutual information-based multi-label feature selection using interaction information[J].Expert Systems with Applications，2015，42（4）：2013-2025.

[2] Fan Baojie，Cong Yang，Du Yingkui.Discriminative multitask objects tracking with active feature selection and drift correction[J].Pattern Recognition，2014，47（12）：3828-3840.

[3] Wu Xiaodong.Online feature selection with streaming features[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2013，35（5）：1178-1192.

[4] Seeja K R.Feature selection based on closed frequent itemset mining：A case study on SAGE data classification[J].Nurocomputing，2015，151（3）：1027-1032.

[5] Dernoncourt D.Analysis of feature selection stability on high dimension and small sample data[J].Computational Statistics and Data Analysis，2014，71（3）：681-693.

[6] Tabakhi S.An unsupervised feature selection algorithm based on ant colony optimization[J].Engineering Applications of Artificial intelligence，2014，32（2）：112-123.

[7] Abdullah S.An exponential Monte-Carlo algorithm for feature selection problems[J].Computers and Industrial Engineering，2014，67（1）：160-167.

[8] Boutsidis C，Zouzias A.Randomized dimensionality reduction for κ-means clustering[J].IEEE Transactions on Information Theory，2015，61（2）：1045-1062.

[9] Sun Jiangyan.An improved k-means clustering algorithm for the community discovery[J].Journal of Software Engineering，2015，9（2）：242-253.

[10] Xiang Yaguang.Apriori algorithm for economic data mining in sports industry[J].Computer Modelling and New Technologies，2014，18（12）：451-455.

[11] Bavdekar Vinay A，Shah Sirish L.Computing point estimates from a non-Gaussian posterior distribution using a probabilistic k-means clustering approach[J].Journal of Process Control，2014，24（2）：487-497.

[12] Lin Chuenhorng，Chen Chunchieh，Lee Hsinlun.FastKmeans algorithm based on a level histogram for image retrieval[J].Expert Systems with Applications，2014，41（7）：3276-3283.

[13] Zhao Jinguo.A novel method for K-means clustering algorithm[J].Computer Modelling and New Technologies，2014，18（11）：182-188.

[14] 潘果.基于正則化互信息改進輸入特征選擇的分類算法[J].計算機工程與應(yīng)用，2014，50（15）：25-29.

[15] 劉海燕，王超，牛軍鈺.基于條件互信息的特征選擇改進算法[J].計算機工程，2012，14（38）：36-42.