基于信息熵與動態聚類的文本特征選擇方法

唐立力

TANG Lili

重慶工商大學 融智學院，重慶400033

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

1 引言

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

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

2 相關基礎知識

2.1 相關定義

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

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

定義2同一類別的數據對象的質心點[8]定義為：

其中|Ti|是Ti中數據對象的個數。

定義3同屬于Tj組的ni個數據對象ai(i=1,2,…,n1)的標準差[8]σ定義為：

2.2 K-means算法

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

輸入：簇的個數K與包含n個對象的數據集合。

輸出：K個簇，使得準則函數值滿足條件。

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

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

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

步驟4重復步驟步驟2 與步驟3 直至算法收斂。

步驟5結束，得到K個結果簇。

2.3 關聯規則與Apriori算法

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

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

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

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

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

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

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

步驟1構造屬性值矩陣：

其中，n表示樣本數據個數，m為每個數據對象的維數。

步驟2計算第j維屬性對應的第i個數據對象的屬性值比重。需要對數據進行標準化處理，即將數據壓縮到區間[0，1]上，其過程如式（5）[13]所示：

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

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

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

其中，qj為差異性系數。對于給定的j，當Hj越小時，qj越大，屬性就越重要。

步驟5第j維的屬性權值[14]的計算：

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

其中，ωj是第j 維屬性的權值。相當于使權值對應的屬性值進行了適當的放大或縮小，使權值大的屬性聚類作用更大，權值小的屬性聚類作用更小。

步驟7采用標準差作為標準測度函數，由定義3 求得賦權類別目標價值函數為：

其中，σi表示第i 類的賦權標準差，|Tj|是Tj所含數據對象的個數。由公式可知，σi的值越小，類內數據對象相似度越大，數據對象越密集，其所在類的質心越能夠體現分類決策面。

4 基于信息熵的K-means動態聚類算法

4.1 K-means動態聚類

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

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

4.2 基于信息熵的K-means動態聚類算法描述

結合基于信息熵的賦權方法與K-means 的動態聚類對數據集合進行聚類處理，算法流程如圖1 所示。

算法步驟描述如下：

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

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

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

步驟2使用熵值法計算數據對象各個屬性的權值。

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

圖1 基于信息熵的K-means動態聚類流程圖

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

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

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

步驟7計算每個類的質心點。

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

步驟9判斷數據樣本集是否為空，如果為空，結束算法。如果不為空，遍歷中心點個數N，當N＜K時，轉向步驟6，當N=K值時，繼續下一步。

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

步驟11結束，數據樣本為空集，得到K個結果簇。

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

本文根據科技文獻的結構特點提出四層挖掘模式，將K-means 聚類分析方法應用于該模式的前三層，將Apriori方法應用于第四層，逐層實現特征選擇。科技文獻特征提取的流程圖，如圖2 所示。

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

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

5.1 獲取前三級特征詞

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

圖3 漢語自動分詞系統

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

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

5.2 獲取四級特征詞

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

步驟1掃描文獻語料庫（C）中的數據信息，產生頻繁的1-項集。

步驟2由頻繁1-項集經過兩兩結合生成頻繁的2-項集。

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

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

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

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

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

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

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

6 仿真實驗及結果分析

6.1 仿真實驗

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

表1 前三級特征詞數量表

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

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

6.2 實驗結果及分析

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

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

表2 文獻語料庫（C）

表3 各特征選擇方法實驗對比結果

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

7 結束語

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

[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].計算機工程與應用，2014，50（15）：25-29.

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