基于特征矩陣優(yōu)化與數(shù)據(jù)降維的文本聚類算法

陳 瑋，盧佳偉

（上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院，上海200093）

引 言

文本文檔作為互聯(lián)網(wǎng)輿情信息的主要載體，一直是數(shù)據(jù)信息時(shí)代的研究重點(diǎn)，能否監(jiān)控并處理好這些文本信息是實(shí)現(xiàn)社會(huì)和諧發(fā)展的重要前提。伴隨著自然語(yǔ)言處理技術(shù)的不斷發(fā)展，各類文本信息處理的技術(shù)愈發(fā)完善，對(duì)輿情信息的處理也越來(lái)越高效，其中文本聚類是文本挖掘、機(jī)器學(xué)習(xí)和模式識(shí)別領(lǐng)域最具代表性的技術(shù)之一。作為一種無(wú)監(jiān)督學(xué)習(xí)的方法，文本聚類在數(shù)據(jù)分析處理上承擔(dān)著重要的角色，通過(guò)將大型的文本文檔分解為具有各類特征代表的文檔子集，從而實(shí)現(xiàn)對(duì)文檔的管理與監(jiān)控［1］。

在文本數(shù)據(jù)處理的過(guò)程中，向量空間模型（Vector space model，VSM）是一種被廣泛采用的模型，模型內(nèi)每一個(gè)詞都被認(rèn)定為文檔的一個(gè)特征從而映射到向量空間中［2］。文本文檔一般會(huì)形成一個(gè)高維度的向量空間模型，每一個(gè)維度依次對(duì)應(yīng)一個(gè)權(quán)重值，初始文本文檔通常包含高維信息和噪聲信息特征，后者以其非相關(guān)性、冗雜性和分布散亂性的特點(diǎn)成為聚類工作中一個(gè)處理難點(diǎn)［3］。特征選擇的主要目的是確定文本中最具代表性和高辨識(shí)度的特征。傳統(tǒng)文本特征的選擇處理有3種方法：基于文檔頻率（Document frequency，DF）的特征選擇、基于詞頻（Term frequency，TF）的特征選擇和基于文檔頻率和逆詞頻（Term frequency inverse document frequency，TF?IDF）的混合特征選擇，這些方法主要依靠詞頻統(tǒng)計(jì)來(lái)完成矩陣特征的提取［4］。文獻(xiàn)［5］通過(guò)確定詞對(duì)文本密集度的貢獻(xiàn)來(lái)評(píng)定該詞的價(jià)值，從而找出不損失文本有效信息的最小特征詞語(yǔ)集，創(chuàng)造出更為合理的權(quán)重計(jì)算方案。文獻(xiàn)［6］提出一種多標(biāo)記的屬性約簡(jiǎn)特征選擇方法，將粗糙集應(yīng)用于多標(biāo)記數(shù)據(jù)的特征選擇中，定義了一種領(lǐng)域粗糙集的下近似和依賴度計(jì)算方法。上述方法都通過(guò)引入其他屬性對(duì)矩陣做出相應(yīng)調(diào)整，從而產(chǎn)生更為明顯的特征子集，但往往忽略了特征矩陣內(nèi)在的影響。本文提出一種自適應(yīng)的特征矩陣，依靠自身的詞頻率分布來(lái)產(chǎn)生特征權(quán)重計(jì)算方案，在改進(jìn)傳統(tǒng)的TF?IDF算法的同時(shí)，使得生成的特征矩陣具有更好的分布性。

文本矩陣空間的高維性仍然是一個(gè)終極挑戰(zhàn)，文本文檔集合一般包含成百上千個(gè)文本特性，文本集群因此變得非常復(fù)雜。一般來(lái)說(shuō)，文本聚類性能受到文本文檔維數(shù)的影響，盡管高維的數(shù)據(jù)包含的信息很多，但是往往會(huì)降低文本集群的準(zhǔn)確性，通常需要采用一定的降維手段對(duì)其進(jìn)行處理，最終實(shí)現(xiàn)聚類性能的優(yōu)化［7］。從技術(shù)上講，有效的降維應(yīng)該做到消除無(wú)用的文本特性，即不必要的、不協(xié)調(diào)的和嘈雜的文本特征等等，保存內(nèi)在信息，從而顯著降低文本特征空間的維數(shù)，常用的降維方法為主成分分析法（Principal component analysis，PCA）［8］，但是當(dāng)數(shù)據(jù)維度十分龐大時(shí)，此時(shí)PCA降維后生成的矩陣非常不準(zhǔn)確。文獻(xiàn)［9］將高維數(shù)據(jù)泛化為新的距離表達(dá)式，并且結(jié)合信息熵構(gòu)造出新的特征評(píng)價(jià)函數(shù)，評(píng)價(jià)每一個(gè)維度的信息量來(lái)消除冗余特征后再聚類，這樣最大限度地保留了數(shù)據(jù)信息，同時(shí)完成了降維處理。文獻(xiàn)［10］在此基礎(chǔ)上結(jié)合PCA降維算法，將PCA算法中映射到低維空間的方差最大化標(biāo)準(zhǔn)改進(jìn)為一種基于特征度量的信息熵標(biāo)準(zhǔn)，使得降維后的數(shù)據(jù)具有更好的分布特性。本文在此兩者基礎(chǔ)上提出一種基于聯(lián)合熵特征度量的標(biāo)準(zhǔn)，即對(duì)所有特征計(jì)算同時(shí)發(fā)生時(shí)的信息熵，進(jìn)一步保留重要的矩陣信息，從而使得降維后的數(shù)據(jù)具有更好的完整性。

1 特征矩陣優(yōu)化

隨著文檔的復(fù)雜性與其內(nèi)容的多變性的增加，文本向量化后形成的矩陣變得越來(lái)越稀疏，并且特征項(xiàng)愈發(fā)不明顯。因此，本文提出一種新的加權(quán)方案ALFW（Adaptive length frequency weight）來(lái)獲得一個(gè)加權(quán)特征項(xiàng)得分，并通過(guò)這個(gè)權(quán)值來(lái)有效地區(qū)分信息性和非信息性文本特征，以此來(lái)提高文本特征選擇的效果。TF?IDF是目前的一個(gè)標(biāo)準(zhǔn)權(quán)重方案，著重體現(xiàn)了詞頻對(duì)特征矩陣的影響［11］，具體如式（1～3）所示。

式中：d j表示一個(gè)文本，nij代表某詞在文本d j中的出現(xiàn)次數(shù)，文本d j中每種詞條的出現(xiàn)總數(shù)使用表示，|D|代表所有文本的總數(shù)，|{j：ti∈d j}|表示包含詞語(yǔ)ti的文本數(shù)目。

新提出權(quán)重方案ALFW的主要目的是在此基礎(chǔ)上合理地突出特征項(xiàng)以及優(yōu)化非信息特征對(duì)矩陣的影響。ALFW的建立主要依靠以下3個(gè)因素：首先引入si變量削弱了逆詞頻對(duì)整個(gè)文檔的影響，其次，考慮到一篇文檔中并沒(méi)有考慮其所有特征項(xiàng)頻率對(duì)權(quán)重方案的影響，因此si變量的添加也對(duì)選擇數(shù)量較少的信息特征起到了幫助；最后maxtf(i)是一個(gè)主要的因素，它對(duì)分配一個(gè)良好的詞頻權(quán)重分?jǐn)?shù)起著至關(guān)重要的作用。ALFW的引入使得文本特征選擇技術(shù)更加容易地找到新的信息特征子集，這也將最終提高文本聚類算法的性能。

式中：maxtf(i)表示文檔i中最大的特征頻率值，si表示文檔i中的特征項(xiàng)被選擇次數(shù)不為0的特征數(shù)之和，df(j)代表包含特征j的文檔數(shù)。

表1為特征頻率分布矩陣，表示10個(gè)特征項(xiàng)在8篇文檔中的分布情況，表2和表3分別給出了在TF?IDF算法和ALFW算法下生成的特征矩陣，對(duì)比矩陣進(jìn)一步說(shuō)明了ALFW與經(jīng)典方案（TF?IDF）進(jìn)行比較時(shí)的優(yōu)勢(shì)，此示例是在8個(gè)帶有10個(gè)特征權(quán)重的文檔上完成的。從表2，3中可以明顯看出，與經(jīng)典的權(quán)重方案（TF?IDF）相比，本文提出的ALFW權(quán)重方案更有效地區(qū)分了文檔的特征。表2中對(duì)于文檔2中的第10個(gè)特征，TF?IDF給出的權(quán)重顯然過(guò)大（2.709），而經(jīng)過(guò)ALFW權(quán)重方案處理后得到了一個(gè)合適的權(quán)重（0.043）（見(jiàn)表3）。同時(shí)，可以看到表2中的2，3，4特征項(xiàng)在各個(gè)文檔中都表示出相同的權(quán)重，這說(shuō)明文檔級(jí)別的特性沒(méi)有體現(xiàn)出來(lái)，而ALFW在這3個(gè)特征項(xiàng)中均給予了不同的權(quán)重值，使得矩陣的特征區(qū)分更加明顯。

表1 特征頻率矩陣Table 1 Fr equency of char acter istic matr ix

表2 TF?IDF矩陣Table 2 TF?IDF matrix

表3 ALFW矩陣Table 3 ALFW matrix

2 基于聯(lián)合熵標(biāo)準(zhǔn)的PCA降維處理

傳統(tǒng)的PCA算法在處理稀疏的高維數(shù)據(jù)時(shí)，結(jié)果往往不太理想，文獻(xiàn)［12］提出對(duì)傳統(tǒng)PCA算法進(jìn)行改進(jìn)，提出一種利用信息熵對(duì)數(shù)據(jù)進(jìn)行特征篩選，再采用PCA進(jìn)行降維處理的算法。本文在此基礎(chǔ)上提出一種基于聯(lián)合熵標(biāo)準(zhǔn)的PCA降維算法（United entropy PCA，UE?PCA）。信息熵的定義如式（5）所示，信息熵是一個(gè)隨機(jī)變量H(X)所有可能情況的自信息量的期望。信息熵表征了隨機(jī)變量所有情況下的平均不確定度，有

信息熵推廣到多維領(lǐng)域即為聯(lián)合熵，具體公式如式（6）所示。采用聯(lián)合熵的好處在于在降維時(shí)不再單一的關(guān)注自身隨機(jī)變量包含的信息，可以與其他變量聯(lián)合產(chǎn)生新的信息量，從而使得特征信息更加完整地保存，反映出原高維稀疏矩陣數(shù)據(jù)的更為真實(shí)的分布情況，更好地服務(wù)于文本聚類算法，即

同時(shí)引入文獻(xiàn)［10］中的屬性空間概念，屬性空間與數(shù)據(jù)空間的區(qū)別在于屬性空間中的點(diǎn)是抽象空間具象化，即屬性成為了空間中的點(diǎn)［10］。給出一個(gè)維度為p的高維數(shù)據(jù)集合D={x1j，x2j，…，x ij，…，x nj}(0

將上述屬性空間與聯(lián)合熵進(jìn)行組合，則形成屬性空間聯(lián)合熵（United entropy，UE）。屬性空間聯(lián)合熵的定義如下。

給定一個(gè)屬性空間T={t1i，t2i，…，tji}（0

結(jié)合特征值得到UE?VAR（United entropy?variance）標(biāo)準(zhǔn)，有

式中：UE T為選取的屬性特征集合的屬性空間聯(lián)合熵，var為集合中每個(gè)特征屬性對(duì)應(yīng)的特征值的和，用這個(gè)特征值的和代替方差也可反映出數(shù)據(jù)的波動(dòng)情況。λ1和λ2為經(jīng)驗(yàn)參數(shù)，根據(jù)方差和聯(lián)合熵的比例來(lái)調(diào)節(jié)之后選擇0.7作為兩個(gè)參數(shù)的值。

基于以上分析，本文提出UE?PCA算法的具體步驟如下。

算法：UE?PCA

輸入：初始數(shù)據(jù)集D

輸出：降維后數(shù)據(jù)集W

begin

輸入數(shù)據(jù)集D=M n*p（矩陣M包含n個(gè)p維的數(shù)據(jù)）=(x()1，x()2，…，x(m))

去中心化處理

計(jì)算協(xié)方差矩陣Dcov

求特征值λ與特征向量，并確定降維后的維度r值

3 實(shí)驗(yàn)仿真及分析

實(shí)驗(yàn)仿真的流程如圖1所示。首先對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理，包括去停用詞、分詞、此行過(guò)濾等步驟，隨后采用VSM向量空間表示并使用ALFW權(quán)重方案來(lái)建立特征矩陣，再由基于聯(lián)合熵標(biāo)準(zhǔn)的PCA算法降維處理后運(yùn)用K?means算法進(jìn)行最終的聚類驗(yàn)證。

圖1 算法流程圖Fig.1 Algorithm flowchart

3.1 評(píng)價(jià)標(biāo)準(zhǔn)

K?means是一種迭代求解的聚類分析算法，通過(guò)隨機(jī)選取k個(gè)對(duì)象作為初始聚類中心，隨后計(jì)算每個(gè)對(duì)象與其他子類聚類中心的距離，將每個(gè)對(duì)象分配給距離它最近的聚類中心。此時(shí)，聚類中心與中心的其他被分配點(diǎn)就成為一個(gè)類簇。對(duì)象的每次更新，聚類中心也會(huì)隨著當(dāng)前聚類情況而被重新計(jì)算，直到收斂到某個(gè)值或達(dá)成某個(gè)終止條件［13］。K?means算法以其簡(jiǎn)捷性、高效性而被廣泛運(yùn)用于聚類領(lǐng)域，在處理大數(shù)據(jù)集時(shí)，該算法可以保證良好的伸縮性和高效性，因此，本文選用其作為聚類數(shù)的判定手段，采用輪廓系數(shù)作為聚類效果的驗(yàn)證方法。

輪廓系數(shù)是一種聚類效果的評(píng)價(jià)方式，通過(guò)結(jié)合內(nèi)聚度和分離度來(lái)完成評(píng)估［14］。其計(jì)算公式為

式中：a(i)表示樣本i到同簇其他樣本的平均距離，也稱之為內(nèi)聚度，內(nèi)聚度越小代表類聚合的效果越好；b(i)表示樣本i到其他簇的簇的所有樣本的平均距離，即分離度，分離度越大表明類簇之間的劃分越明顯。s(i)的取值范圍為（-1，1），聚類的最終效果由此評(píng)判，值越接近1表示聚類效果越好。

3.2 數(shù)據(jù)集

本文數(shù)據(jù)集選自THUCNews文本數(shù)據(jù)集。THUCNews是根據(jù)新浪新聞RSS訂閱頻道2005—2011年間的歷史數(shù)據(jù)篩選過(guò)濾生成，包含74萬(wàn)篇新聞文檔（2.19 GB），均為UTF?8純文本格式，該數(shù)據(jù)集分為體育、財(cái)經(jīng)、房產(chǎn)、家居、教育、科技、時(shí)尚、時(shí)政、游戲和娛樂(lè)10個(gè)類別。本文從其中隨機(jī)選擇10 000篇，每類1 000篇作為實(shí)驗(yàn)測(cè)試數(shù)據(jù)集。在仿真實(shí)驗(yàn)之前，需要對(duì)文本文檔作預(yù)處理，即停用詞過(guò)濾和分詞操作，相應(yīng)地使用jieba分詞工具和中文停用詞表完成。

除此之外，本文另外爬取2018年10～12月的網(wǎng)絡(luò)新聞數(shù)據(jù)共計(jì)403篇短文進(jìn)行輿情聚類實(shí)驗(yàn)，詳細(xì)的數(shù)據(jù)集信息如表4所示。

表4 數(shù)據(jù)集信息Table 4 Data set

3.3 實(shí)驗(yàn)結(jié)果分析

本文實(shí)驗(yàn)選擇4種算法模型進(jìn)行對(duì)比，分別為PCA降維算法+TFIDF算法+K?means聚類算法的傳統(tǒng)組合算法、PCA降維算法+ALFW特征矩陣+K?means聚類算法的組合、文獻(xiàn)［10］提出的算法以及本文算法（K?means+UE?PCA+ALFW）。

圖2 大樣本數(shù)據(jù)集算法輪廓系數(shù)對(duì)比圖Fig.2 Comparison of silhouette coeffi?cient of large sample data set algo?rithm

表5 大樣本輪廓系數(shù)對(duì)比表Table 5 Silhouette coefficient comparison table of big data set

從圖2可以看出隨著類簇?cái)?shù)的增加，輪廓系數(shù)曲線逐漸上升，當(dāng)達(dá)到區(qū)間［8，10］時(shí)，各個(gè)算法呈現(xiàn)的輪廓系數(shù)曲線都開(kāi)始逐步下降，說(shuō)明此時(shí)聚類時(shí)的內(nèi)聚度與分離度之間達(dá)到一個(gè)平衡的狀態(tài)，也是聚類最佳的狀態(tài)，超過(guò)這個(gè)區(qū)間之后，輪廓系數(shù)評(píng)價(jià)值大幅下降。從表5可以看出采用傳統(tǒng)的K?means+PCA+TF?IDF組合算法模型、K?means+PCA+ALFW組合算法模型、文獻(xiàn)［10］算法和本文算法分別在類簇?cái)?shù)為9、10、11、10時(shí)達(dá)到最佳聚類狀態(tài)，而實(shí)際上的標(biāo)準(zhǔn)類簇?cái)?shù)為10，從而可知本文算法正確完成了聚類。觀察4種模型算法在類簇?cái)?shù)為10時(shí)的輪廓系數(shù)得分，本文算法也取得了最佳的0.673得分。同時(shí)對(duì)比K?means+PCA+TF?IDF組合算法模型和K?means+PCA+ALFW組合算法模型，可以看出后者取得了更好的效果，這也進(jìn)一步驗(yàn)證了ALFW矩陣對(duì)聚類結(jié)果優(yōu)化的有效性。

此外，本文在自主爬取的5類小樣本數(shù)據(jù)也進(jìn)行了仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表6和圖3所示。同樣地，本文算法依舊取得了最佳的輪廓系數(shù)評(píng)價(jià)（0.724），在小樣本中更加體現(xiàn)出了算法的優(yōu)劣性。

表6 小樣本輪廓系數(shù)對(duì)比表Table 6 Silhouette coefficient comparison table of small data set

圖3 小樣本數(shù)據(jù)集算法輪廓系數(shù)對(duì)比圖Fig.3 Comparison of silhouette coeffi?cient of small sample data set al?gorithm

4 結(jié)束語(yǔ)

本文針對(duì)傳統(tǒng)的TF?IDF特征權(quán)重矩陣做出改進(jìn)，提出一種基于ALFW特征權(quán)重方案的特征矩陣，使得矩陣的特征項(xiàng)具有更好的分布性，對(duì)后續(xù)聚類算法的性能進(jìn)行了提升。高維數(shù)據(jù)的稀疏性通常會(huì)嚴(yán)重干擾到聚類算法的效果，因此，本文提出一種基于聯(lián)合熵標(biāo)準(zhǔn)的PCA降維算法，使得特征信息在完整保存下來(lái)的同時(shí)，過(guò)濾掉大量上下文無(wú)關(guān)特征信息，更好地反映出原高維數(shù)據(jù)特征矩陣的真實(shí)性?；谏鲜鰞身?xiàng)改進(jìn)，本文提出的基于特征矩陣優(yōu)化與數(shù)據(jù)降維算法（K?means+UE?PCA+ALFW）最終在4種算法的評(píng)估中取得最佳效果。