結合權重因子與特征向量改進的文本聚類算法

董躍華，郭士串

（江西理工大學 信息工程學院，江西 贛州341000）

0 引 言

文本聚類屬于聚類分析范疇，是一種挖掘潛在、隱藏信息的方法［1］，但因其非結構化的數據類型和向量空間模型表示后的高維性，使其自身具有特殊性。

通常文本聚類包括兩個步驟：第一文本預處理，使文本數據可以通過計算機處理；第二聚類算法選擇，針對文本數據的特點進行聚類。長期以來，人們都很熱衷于對文本預處理的研究，如有研究者提出一種特征項自動分解的思想［2］提高了文本特征項的選擇精度；還有通過類間偏斜度、類內離散度和權重調整因子的配合使用［3］修改了傳統的文本預處理方法，提高了文本聚類的精度。在文本聚類算法方面，K－均值因其高效和簡單已被廣泛應用，但其具有過分依賴初始中心點選取和聚類結果，易陷入局部最優等缺點。目前，很多研究者利用遺傳算法的全局優化能力結合K－均值算法對聚類進行優化［4－8］。遺傳算法獲得最優解的方法就是模擬自然進化的過程，其通過部分結構可反映應用空間較大的區域，具有一定的健壯性，可避免局部最優，同時還便于實時處理。所以，兩種算法相結合能更好改善聚類效果。

本文首先通過特征詞權重因子和特征向量改進了文本預處理方法，并根據新的文本編碼特點結合遺傳控制因子對遺傳K－均值聚類算法進行算子控制。實驗結果表明，本文提出的文本聚類方法提高了文本特征詞分類精度并改進了文本聚類效果。

1 文本預處理方案設計

在文本聚類之前，必須要對文本進行預處理，主要包括文本的特征選取和文本編碼，經過預處理后能提高文本聚類的效率和準確率。通常文本聚類可描述為：對文本集合D＝｛d1，d2，…，dn｝進行聚類，而最終的聚類效果是要得到一個簇的集合C＝ ｛c1，c2，…，ck｝，∪ki＝1Ci＝D ，其中對每一個di（di∈D），-Cj（Cj∈C），di∈Cj，并且還要使得聚類準則函數Q（C）收斂，其中n為文本的總個數，k是需要的聚類個數，且Cj∩Cl＝φ，j≠l。

1.1 特征詞權重計算方法

在文 本 聚 類 中 文 本 通 過 VSM （vector space model，VSM）表示，每個文本為一條向量。向量內容為通過TFIDF度量求出的文本中每個特征詞t的權重，用來表示特征詞t在該文本中的重要性。則文本可表示為

其中特征詞tk的權重為wk，1≤k≤n。

但是傳統的TF－IDF只考慮詞語頻率TF和詞語倒排文檔頻率IDF，在文本集中，通過該方法計算的特征詞權重集合能很好的表示一個文本，但此權重在體現文本間的差異性時有明顯的局限性。為了解決這一缺點本文提出一種改進方法，在考慮到TF和IDF的情況下，加入特征詞權重因子對特征詞權重進行加權處理。特征詞權重因子（WF）的作用是通過特征詞權重提高不同類文本間的區分度，增強同類文本間的相似度，WF的表達式如下

其中w′it為特征詞t在除i文本外在文本集其它文本中的權重，w＊為此權重集合中的非零最小值，w＊∈w′it。由式（2）可以看出通過WF的控制更好體現同一特征詞在不同文本中的不同重要性，從而加強文本間的差異性。修改后的度量公式命名WF－TF－IDF，做歸一化處理后為

式中：wit為特征詞t在文本di中的權重，t＝1……n，N為文本集合中的文本總個數，nt為出現特征詞t的文本個數。

1.2 文本編碼方案

預處理過程中通過WF－TF－IDF對文本特征詞權重計算結束后，文本的編碼方案也是非常重要的環節。但是在傳統的VSM編碼方案中，并沒有考慮特征詞在文本中的位置，而是簡單的要求特征詞不重復，不考慮在文本中的先后順序。但是一個特征詞出現在文本中的不同部分在表示文本時也有不同的貢獻度，比如，同一特征詞出現在文本的標題和正文兩個部分中，在其表示文本時貢獻度就有所不同，所以在對文本編碼時應該把特征詞出現在文本中的位置考慮在內。

于是本文將傳統通過VSM中一個向量表示文本的模式，修改成文本由標題向量dv1、第一段向量dv2、最后一段向量dv3、其它段向量dv4這4個特征向量構成，每個特征向量均包含對應的特征詞和權重，由于每個特征向量代表文本的不同位置，因此，對于不同位置的特征向量通過位置權重Lm進行加權處理，修改后的文本表示應為

式中：dvm——文本的特征向量，Lm＝ ｛0.4，0.3，0.2，0.1｝為位置權重信息，m為特征向量個數，1≤m≤4。

因VSM是實數域的求解問題，并且二進制編碼計算量大，所以本文將采用浮點數編碼，能加快求解速度。通過以上描述，以chromi＝ （c1，c2，…，ck）（1≤i≤p，p表示種群的大小，本文設p為偶數）表示染色體。給定一個文本集包括N個文本，對每個文本根據自身的結構生成各自的特征向量。從特征向量中提取的各自特征詞，對其不同的特征詞構造VSM。通過此過程，每個文本d被認為由向量空間中的，個特征向量組成。如果某個特征詞不存在對應的特征向量中，那么在VSM中其對應元素值設為0；否則根據本文提出的基于WF加權的TF－IDF權重計算方法求得該特征詞在文本中的權重。其染色體中的cj（1≤j≤k）則是由特征向量構成并與VSM長度相同，表示聚類結果中第j個中心向量。由于對特征向量權值進行了歸一化處理，所以進行編碼時向量cj中的元素都是0和1之間的實數。

1.3 相似度的設計

1.3.1 改進的余弦夾角度量

在整個聚類過程中，文本彼此間的相似性計算尤為重要，其評價準則對最終聚類效果有直接的影響。目前對于同一特征空間的兩個對象進行相似性評價有了很多方法。但是對象的數據類型有所不同有的數據是連續型，有的則是分類型，不是所有的評價標準都適用。文本聚類屬于對連續型數據進行處理，目前常用的文本間相似性計算方法有Pearson相關、Jaccard系數［9］以及歐幾里德距離等。但在VSM中文本通過向量表示，故文本間的相似性可以通過向量之間的距離表示。因為本文在文本預處理中，采用了基于WF的加權策略和特征向量方法，故在文本相似度計算時采余弦相似度度量最優。又由于本文對文本編碼方案做了修改，所以本文結合式 （4）對余弦相似度計算做了修改，其表達式如下

式中：dI、dJ——文本，m為文本特征向量個數。分子和分母分別表示兩個特征向量的內積和模的乘積。由于文本向量在進行內積運算時對沒有此特征詞時做補零處理，且每個特征向量還包含位置權重信息，所以通過式 （5）能更好體現出文本間的差異度。

1.3.2 遺傳控制因子 （GCF）

通過研究遺傳算法控制算子的方法和新的文本編碼的特點，本文提出一種遺傳控制因子 （GCF）。GCF在遺傳算法中的作用是如何將優質的個體引入下一代，還表示該個體各聚類中心向量間的相似度。如果GCF較小說明此個體聚類中心點彼此間相似度較小，此個體為優質個體；如果GCF較大說明此個體聚類中心點彼此間相似度較大，此個體為劣質個體。GCF主要的設計步驟如下：

（1）計 算 均 值向量VA ＝ ｛VA1，……，VAm｝，其 中VAi表示染色體p第i維的平均向量，m為特征向量的個數。

（3）染色體p的GCF計算公式為

式中：μ∈ （0，1］為隨機數；CI、CJ 為染色體p 的中心向量。

1.4 適應度函數設計

由于采用Sim度量文本間的相似度，故Sim值的大小和文本間的相似度成正比。首先由1.2節的編碼方案，對生成的染色體隨機的產生k個中心向量，再根據Sim求出每個中心向量和各個文本間的相似度，并將各文本放入與之相似度最接近的中心點所在的類中。由此可見，一個中心點與離它越近的對象的相似度越大，否則相似度越小，那么其適應度值就應該越大。所以本文設計的適應度函數f為

1.5 收斂準則函數設計

根據本文重構的余弦相似度計算公式，所設計的新的遺傳K－均值算法的收斂準則函數為

式中：q（cj）——第j類中內部文本與聚類中心的相似度

式 （9）的目標函數是基于本文設計的Sim相似度的。

2 用于文本聚類的遺傳K－均值算法

為了克服算子操作的低效性，本文將使用GCF對傳統的遺傳K－均值算法進行算子操作控制，使其能更好的和特征向量方法相結合。本文將此算法稱為GGKM。在GGKM算法遺傳算子交叉和變異時，GCF的作用如下：

在遺傳算子交叉操作時，交叉后新個體的GCF大于原個體的GCF，則說明交叉失敗保留原來的個體，否則保留新個體。在算子變異操作時，如果進行一次變異后得到的新個體的GCF大于原來個體的GCF，則說明沒有得到優質的新個體，說明變異操作失敗需重新進行一次變異，如果進行了Gmax（最大變異次數）次變異后還沒有得到小于原來個體的GCF，則說明原來個體為優質個體并保留下來，否則將得到的新個體引入下一代。

2.1 通過GCF控制遺傳算子

2.1.1 選擇算子

為了保證基因中最優個體一定被選中，并且讓個體被選中的概率都與其自身的適應度值有關。所以，文本使用最優保持策略和輪盤賭注選擇方法對算子進行選擇操作。實現的步驟如下：

還有，最優保持策略的目的是保證當前算子操作階段出現的最優個體不會在下一步的進化操作中被直接破壞。設Iw為當前種群中適應度最低個體，Ib為當前種群中適應度最高個體，I′b為種群中總的最好個體，具體偽代碼如下：

2.1.2 交叉算子

本文在進行遺傳算子交叉操作時，采用了自適應可變概率，并在操作時采用單點交叉算子。假設兩個配對個體為c1＝g1，g2，…，gk和c1＝h1，h2，…hk。實現交叉操作的步驟如下：

（1）設favg為當前種群的平均適應度，fmax為當前種群的最大適應度，設f1為c1和c2兩者中適應度較大的個體，則本文使用的可變交叉概率Pt為［10］

由式 （10）可以看出，當平均適應度大于個體適應度時，說明個體不是優質個體，必須進行交叉操作；而當交叉個體的適應度值比較大時，其交叉概率成反比。

（2）生成一個隨機數R1∈ ［0，1）。

（3）if （R1＜Pt）

｛

（4）產生一個隨機整數r并且小于中心點個數k，使其作為交叉操作的交叉點，并將r位到k位之間的對象隨機互換。即當i＝r＋1，…，k時，每次均生成一個隨機數μ其取值為0或1，則有gi＝μgi＋（1－μ）hi和hi＝ （1－μ）gi＋μhi。

（5）用GCF進行個體控制。

｝

2.1.3 變異算子

在進行變異操作時，其概率類似于交叉操作也采用可變控制。確定變異概率大小的公式［10］如下

式中：λ∈ （0，1］，一般為0.1。由式 （11）可以觀察出，種群中個體適應度的值和變異概率成反比。通過式 （11）求得變異概率后，遺傳算法變異算子操作步驟如下：首先確定一個范圍 ［－R，R］，計算公式為

設Ni為個體N在第i位的值，而nimin和nimax為文本集中第i位上的最小值和最大值，設ni為種群進行變異操作后第i位的值，μ為隨機數且μ∈ ［－R，R］，其計算公式如下

實現偽代碼為：

用式 （12）、式 （13）進行變異運算；

2.2 算法終止條件

在改進后的文本聚類算法中，采用的終止條件如下：

（1）固定最大迭代次數Itemum。當算法執行了Itemum次遺傳進化后停止。

（2）根據算法自身的收斂程度。比如在文本聚類過程中準則函數值連續多代無明顯變化，則說明函數值趨向收斂此時算法停止。

2.3 算法步驟及流程圖

輸入：文本集D（文本數為N，維數為m），遺傳種群大小p，交叉概率pt，變異概率pm，聚類個數k，終止條件。

輸出：聚類結果。

GGKM算法具體步驟如下：

步驟1 進行文本預處理；

步驟2 通過WF－TF－IDF算法對特征詞權重進行計算；

步驟3 對文本進行編碼，通過文本自身的特征向量結合VSM表示文本；

步驟4 初始化種群，通過K－均值和Sim隨機產生p個染色體，種群可以表表示為p＝ （chrom1，chrom2，……，chromp）；

步驟5 通過重構的適應度函數f求的每個個體的適應度函數值；

步驟6 計算遺傳控制因子GCF并進行選擇、交叉、變異控制。選擇采用最優保持策略和輪盤賭注選擇；交叉和變異操作通過每個個體的GCF和自適應可變概率控制，確保優質個體被引至下一代；

步驟7 產生了新一代的遺傳種群，通過算法終止條件判斷是否終止，是則進入步驟8；否則轉步驟5；

步驟8 輸出聚類結果。

改進后的文本聚類流程如圖1所示，首先通過特征詞權重因子 （WF）修改了傳統的權重計算公式，得出的特征詞權重值能更好的體現特征詞在文本中的價值。再利用特征向量的概念和VSM對文本進行編碼，重新編碼后的文本由自身特征向量組成，每個特征向量表示文本的不同位置。再此基礎上利用式 （5）進行相似度計算，能更好的提高同類文本的相似度，增加不同類文本的差異度。最后，根據本文的文本編碼方案特點結合遺傳算法操作算子的思想，提出一種遺傳控制因子 （GCF）。通過GCF對遺傳K－均值算法的算子操作進行控制，使交叉和變異效率更高，從而得到較理想的聚類效果。

3 實驗及結果分析

本文實驗采用的原始數據來自于中文自然語言處理開放平臺網站的新聞樣本。其中訓練樣本和測試樣本共有2516個。樣本有12個類別，分別為財經、體育、教育等，采用信息增益和基于文檔統計并取1000個特征詞，數據集稱為Chs2516。實驗的硬件環境為Intel Core i3 2.4GH，內存2G，操作系統是32位 Windows7，仿真軟件為Matlab 2012b。

圖1 改進后的文本聚類流程

3.1 實驗評價標準

文本預處理階段首先在支持向量機算法下進行特征詞分類實驗，通過WF加權的TF－IDF方法對特征詞權重進行計算，每次實驗結束都會計算出此次特征詞分類的查全率（Pe）和查準率 （Pr），對每20次結果求Pe和Pr平均值，而Pe和Pr是F1－measure的重要參數，對特征詞分類精度的評估有很重要的影響。評估指標F1－measure在文本聚類有效性評價中的使用非常頻繁，在各種文獻檢索系統中都有運用［11］。其表達式如下

在文本聚類效果方面，采用Huang提出的聚類精度度量來衡量文本聚類結果的準確性，其公式為

式中：ai——對象出現在類Ci和其相應標記類中的總和。并把終止條件設為：Gmax為200，Itemum為800，當Itemum大于800或函數Q（）收斂時，算法結束。

3.2 實驗結果分析

在文本特征詞提取階段采用支持向量機算法，將傳統的 TF－IDF算法、BOR－TFIDF算法［12］、SI－TFIDF算法與WF－TF－IDF改進算法進行比較。每種算法運行100次。表1和圖2分別表示4種算法對同一類特征詞的測試結果和實驗效果圖。通過表1的數據可以看出，通過WF加權的WF－TF－IDF算法和其它3種算法相比在特征詞分類效果方面具有較高的準確率。圖2表現出了4種算法對不同類特征詞的分類效果，其中TF－IDF和BOR－TFIDF算法的分類精度比較低，SI－TFIDF優于前2種算法，而 WF－TF－IDF算法在傳統算法優點的基礎上，結合權重因子WF對特征詞權重進行加權處理使得分類精確度最高。

表1 基于支持向量機的測試結果

在文本聚類階段，將傳統K－均值聚類算法、改進的混合聚類算法［13］與改進算法GGKM進行比較。表2對應3種聚類算法對數據集Chs2516進行聚類后的聚類精度 （表中的順序號為100次實驗中隨機挑選的8組），從表2中可以看出GGKM算法相比其它兩種算法有更高的聚類精度且聚類精度波動幅度相對較小，這都說明GGKM算法的聚類結果更加的準確和穩定。圖3為3種算法的平均聚類精度對比，更加直觀的顯示GGKM算法的聚類效果更優。

圖2 基于支持向量機的實驗效果比較

表2 文本聚類精度值

圖3 文本數據集聚類精度對比

綜上所述，本文提出的以WF加權的WF－TF－IDF特征詞權重計算方法，在繼承了傳統算法優勢的同時，并根據特征詞在表示文本時對文本的重要性進行權重的加權和降權處理，以體現特征詞對區分文本的貢獻度。從而更好的變現了同一特征詞在不同文本中的不同重要性，確保了文本分類效果的穩定。而結合了特征向量思想和遺傳控制因子的遺傳K－均值聚類算法GGKM，相比其它兩種文本聚類算法，能更好的適應文本提出的文本編碼方案，從以上實驗數據可以看出，本文改進的文本聚類算法，不但對特征詞的權重計算和特征詞分類做出了改進，還使得文本聚類精度得到提高，聚類效果不易受到干擾。

4 結束語

首先通過研究傳統特征詞權重計算的缺陷，從加強一個特征詞在不用文本中重要性的角度出發，結合權重因子WF的方法，提出了改進算法 WF－TF－IDF。并對文本編碼做了修改，使用特征向量的思想修改了相似度計算公式，使文本之間的差異度更加明顯。還針對改進的文本預處理方案，提出通過遺傳控制因子改進遺傳K－均值文本聚類算法。實驗結果表明，本文提出的結合權重因子與特征向量改進的文本聚類方法較之其它改進方法，具有更好的特征提取和文本聚類效果。

［1］LIN Li.Application research of text clustering based on noumenon ［D］.Tianjin：Tianjin University，2011 （in Chinese）.［林利.基于本體的文本聚類的應用研究 ［D］.天津：天津大學，2011.］

［2］YU Yonghong，BAI Wenyang.Text clustering based on automatic partition of feature item weight ［J］.Computer Engineering，2011，37 （11）：25－27 （in Chinese）. ［余永紅，柏文陽.基于特征項權重自動分解的文本聚類 ［J］.計算機工程，2011，37 （11）：25－27.］

［3］ZHANG Yu，ZHANG Dexian.Improved feature weight algorithm ［J］.Computer Engineering，2011，37 （5）：210－212（in Chinese）. ［張瑜，張德賢.一種改進的特征權重算法［J］.計算機工程，2011，37 （5）：210－212.］

［4］Roy D K，Sharma L K.Genetic k－Means clustering algorithm for mixed numeric and categorical data sets ［J］.International Journal of Artificial Intelligence ＆ Applications，2010，1 （2）：23－28.

［5］Laszlo M，Mukherjee S.A genetic algorithm that exchanges neighboring centers for k－means clustering ［J］.Pattern Recognition Letters，2007，28 （16）：2359－2366.

［6］Chang D X，Zhang X D，Zheng C W.A genetic algorithm with gene rearrangement for K－means clustering ［J］.Pattern Recognition，2009，42 （7）：1210－1222.

［7］Hwang C，Chang T.Genetic k－means collaborative filtering for multi－criteria recommendation ［J］.Journal of Computational Information Systems，2012，8 （1）：293－303.

［8］ Martis R J，Chakraborty C.Arrhythmia disease diagnosis using neural network，SVM，and genetic algorithm－optimized k－means clustering ［J］.Journal of Mechanics in Medicine and Biology，2011，11 （4）：897－915.

［9］Shameem M U S，Ferdous R.An efficient k－means algorithm integrated with Jaccard distance measure for document clustering［C］／／First Asian Himalayas International Conference on Internet.IEEE，2009：1－6.

［10］Chavent M，Lechevallier Y，Briant O.DIVCLUS－T：A monothetic divisive hierarchical clustering method ［J］.Computational Statistics ＆Data Analysis，2007，52 （2）：687－701.

［11］Agarwal A，Xie B，Vovsha I，et al.Sentiment analysis of twitter data ［C］／／Proceedings of the Workshop on Languages in Social Media.Association for Computational Linguis－tics，2011：30－38.

［12］SHEN Zhibin，BAI Qingyuan.Improvement of feature weighting algorithm in text classification ［J］.Journal of Nanjing Normal University （Engineering and Technology Edition），2009，8 （4）：95－98 （in Chinese）.［沈志斌，白清源.文本分類中特征權重算法的改進 ［J］.南京師范大學學報 （工程技術版），2009，8 （4）：95－98.］

［13］LAI Yuxia，LIU Jianping，YANG Guoxing.K－means clustering analysis based on genetic algorithm ［J］.Computer Engineering，2008，34 （20）：200－202 （in Chinese）. ［賴玉霞，劉建平，楊國興.基于遺傳算法的K均值聚類分析 ［J］.計算機工程，2008，34 （ 20）：200－202.］