基于精細簇的K－Means文本聚類

侯榮濤，路 郁，王 琴，周 彬

（1.南京信息工程大學 計算機與軟件學院，江蘇 南京210044；2.南京信息工程大學 電子與信息工程學院，江蘇 南京210044）

0 引 言

聚類技術是數據挖掘的關鍵手段，其中K－Means算法是最經典的聚類算法之一，其簡單快速且易于實現的特點使它成為數據挖掘中最常用的算法。

綜上所述，文本挖掘應用所要求的是無監督的文本聚類方法，要求方法能夠穩定地獲得高精度聚類結果，傳統的聚類方法還需要進一步地改進才能良好地應用于文本數據挖掘中。因此，本文引入了精細簇的概念來進行文本數據進行聚類，以滿足應用所需的高精度和高穩定性的需求。

1 K－Means算法研究及改進

1.1 K－Means算法研究

K－Means算法的基本思想是劃分與迭代，具體做法是在歐幾里德多維空間里把包含N 個數據對象的數據集合劃分為K 個劃分其中每個劃分分別代表一個聚類的簇，根據某種具有區分能力的相似度度量，通過反復地迭代變換使對象劃分至正確的類中，直到類的歸屬停止變動或達到收斂條件為止。K－Means算法開始于一系列隨即的初始類中心，根據相似度度量函數，將所有的對象分配到與其最接近的中心所屬的類別，產生一個新的劃分。各類中的對象因被劃分而發生更替，每一輪劃分后都會產生一系列新的類中心，這些類中心即為包含在簇內所有對象的均值

其中，Nk為第k個簇的樣本數目，ck為其簇中心。這種中心調整的方式使得K－Means朝著類內離散度減小的方向發展，并根據新的類中心繼續劃分，這個聚類過程重復迭代進行，直到聚類結果不再變化或者觸發了預先設定的終止條件為止。

K－Means的主要優勢在于算法簡潔、易于理解及實現等優點外，對于稀疏矩陣的處理有著良好的性能。然而，算法執行前需要人工指定聚類數目K。對于未知的數據集，在聚類前是無法預知數據集中真實的類分布，確定K 值的過程需要用戶的實踐經驗，并且存在這很大的不確定性。其次，由于初始中心點是隨機生成的，算法容易陷入局部最優解并且聚類結果差別很大。最后，K－Means算法存在只能發現凸狀簇的限制。由于K－Means是通過多個中心組成的超平面來劃分各類，因此這些類呈現凸型。實際應用中，類不一定規則地呈現凸型，對于這些不規則的形狀的類，K－Means將無法獲得最優的劃分。如圖1 所示，圖中空心圓點為數據集分布，黑色實心圓點為通過K－Means迭代收斂時的簇中心。根據數據對象分配到與其最近中心所屬類中的原則，劃分結果可由兩個簇中心平分線 （圖中以虛線）隔開，由于數據集中簇的非凸型，部分數據點被歸到錯誤的類中，使得數據集無法得到最佳的劃分結果。

1.2 K－Means算法改進

由于數據集中真實類別數目K 無法預知，隨機的初始中心缺乏根據，加大了K－Means算法陷入局部最優的可能性，且增多了迭代次數。聚類所得的凸型簇也使得不規則形狀簇中的對象無法被劃分到正確的類中。針對這些缺點，本文提出了精細簇聚類概念，將真實的簇劃分得更加精細，并通過合并這些精細簇以獲得更高的聚類精度。采用精細簇進行K－Means聚類的過程如圖2所示。將K 值增加至4，經過K－Means聚類后，簇中心如圖2 （a）所示，由這些中心所組成的平分線將數據集劃分的更加精細，如圖2 （b）所示。若能將圖2 （b）中左側兩個精細簇合并為一個簇，并將右側兩個簇合并為一個簇，數據集將獲得更加精準的劃分，如圖2 （c）所示。

圖1 形狀不規則簇的聚類結果

圖2 精細簇K－Means聚類過程

精細簇的引入將一定程度上克服K－Means算法只能識別凸型結構簇的缺點從而更加準確地聚類，而其中最關鍵的是如何獲得和合并精細簇，即需要獲得子簇與其父簇的層次結構。文本引入了基于密度的OPTICS聚類進行預處理，該算法不顯式地產生聚類結果，而是基于其核心距離和可達距離的概念掃描數據集來獲得一個指示數據集對象分布的可達圖。可達圖反映了數據集內部結構，從可達圖的提取凹槽區域可獲得的聚類結果簇。圖3為OPTICS對文本數據集聚類分析生成的可達圖，從圖3 中可以看出，由于算法始終往密度高的區域發展，使得密度稀疏區域的對象被調整到可達圖凹槽區后緩慢上揚的尾部，這些部分無法得到正確的歸類。特別是在實際文本聚類應用中，文本簇通常并非緊湊分布，導致可達圖中緩慢上揚區域變得十分寬，這部分區域中的對象無法正確歸類。

在三維豎井模型中，使用MIDAS/GTS NX提供的實體單元來模擬地質圍巖，使用板單元來模擬混凝土襯砌，使用植入式桁架來模擬錨桿。巖體本構模型為彈塑性模型，采用莫爾-庫侖理論[2-4]。巖體及材料的物理力學參數如表1所示。

圖3 OPTICS聚類結果

雖然OPTICS具有自動識別簇類數量的優勢，但是單純地使用OPTICS文本聚類將無法得到文本對象的完全分類。然而可達圖能夠反映數據集的整體密度結構，如圖3左側區域的數據集經過OPTICS聚類后的得到了右側區域所示的可達圖，其中C1包含了子簇a和b，C2包含了子簇c和d。這樣的層次結構在進行精細簇K－Means聚類時能有效指導初始中心的選取以及精細簇的合并。因此，有效利用OPTICS可達圖所包含的簇層次結構，可為K－Means算法提供初始化依據，結合K－Means算法的全局劃分方案，將得到更好的聚類性能。

2 精細簇K－Means文本聚類

2.1 數據模型構建

本文采取中科院計算技術研究所研制的基于多層隱馬模型的漢語詞法分析系統ICTCLAS 進行分詞。ICTCLAS能夠有效地識別中文詞及未登錄詞，并能夠標注各個詞條的詞性。從語言學角度分析，不同類別的文本中漢字的分布是有規律的并且這種規律是相對穩定的。已有大量的實驗表明，僅僅基于單字詞的文本分類能夠取得高于八成的分類準確率，事實說明只使用單字詞進行聚類是實際有效的。目前分詞系統對雙字詞的識別并非完全符合語義，分詞結果也容易造成歧義。因此，本文采取單字詞進行聚類分析。

首先需要對文本數據進行分詞、去停用詞等操作，然后統計詞頻。由于單純的文檔詞頻無法正確表達該詞對文本的重要性，有些詞條出現頻率高卻對文本無實際意義，它們通常廣泛地遍布于整個數據集的文本中；有些詞匯對文本具有重要意義，然而由于文本篇幅較短從而導致了該詞頻低，以至于該詞的權值較低，這些情況顯然是不符合常規邏輯的。為此，文本采取TF－IDF公式根據詞頻矩陣計算詞權，如式 （1）所示

為了保證數據的一致性，采用式 （2）進行歸一化

圖4為建立數據模型的流程。

2.2 層次樹構建

圖4 建立數據模型流程

在數據模型構建完成的基礎上，本文采用文本間的余弦相似度衡量兩個文本對象間的相似程度。根據余弦相似度的性質可知，兩個對象的相似度程度越高，余弦相似度值越大。由于聚類算法按照對象間的相異度進行，即將相距小的對象聚為一類。為了符合這種特性，修改余弦公式為如式 （3）所示，以表示文本對象間的距離

利用OPTICS算法對數據集進行初步聚類，得到反映數據集內部結構的可達圖。目前已有方法能夠根據可達圖中根據陡峭下降及陡峭上升區域獲取所有可能的簇。然而常規的簇提取算法提取了所有滿足條件的簇，但是不包含簇之間的所屬關系，其中每一個簇由其邊界確定，如C＝［s，e］代表第s至e之間的數據點為簇中的對象。然而簇之間的包含關系能夠通過可達圖中凹槽的邊界來構造，這種簇包含結構即為層次樹，樹結構如圖5所示。文本對傳統的簇提取算法進行改進，采取先提取后構造的形式進行層次樹的構建。

圖5 層次樹的結構

輸入：可達圖列表Point；

輸出：層次樹CHT；

算法中陡降 （升）點 （區域）的過程以及簇的匹配過程與常規提取算法類似，這里不予贅述。其中CHT.Create（）為層次樹的創建，該過程主要過程為：根據小簇必然是包含在大簇中的性質，將ClassSet中的簇根據各自大小（即簇結束與起始位置之差）進行排序，然后將簇Class按照從大到小的順序插入層次樹合適的位置，這樣做的好處是避免了層次樹在構建的時候反復調整節點位置所帶來的時間消耗，簇節點插入算法CHTAdd描述為：

輸入：Class：即將插入的簇節點；CHTNode：層次樹節點；

2.3 基于層次樹的K－Means聚類

計算層次樹中所有葉子節點所代表的簇的中心并標記及所屬的簇id，將這些中心作為K－Means算法的輸入。同時標記葉節點中所有的數據對象簇id為葉節點的id。葉子節點代表的簇是數據集中提煉出的高密度區域，簇中的對象排列緊密，且在聚類完成后基本不發生分裂。若忽略對象間的關系，K－Means迭代時會獨立地考察每個對象，影響算法應用的效率性。基于高密度簇中對象相似關系的基礎上，文本提出了結構化對象的概念，將高密度簇中相似的對象作為一個結構體，以結構體的中心代表高密度簇中的所有對象。

引入結構化概念后，結構化對象在聚類前被標記了簇id。在K－Means算法重新劃分對象所屬的類別時，只需將不屬于葉節點的對象歸類，以便減少K－Means算法聚類過程中的計算量。結構化K－Means算法步驟如下：

步驟1 輸入數據對象集合，輸入層次樹葉節點所代表的簇中心作為算法初始中心；

步驟2 While（收未達到斂條件）do

（1）對于每一個不屬于葉節點的數據對象，根據其與各個中心的相似度，將對象分派到最相似的中心所屬的類別；

（2）根據每個類別中所有對象，計算均值代表簇中心；

End

步驟3 輸出K 個聚類簇的集合，將簇id相同的簇進行合并。

算法中根據初始中心點開始迭代，迭代過程中采用與OPTICS相同的距離公式來衡量文本對象之間距離，并采用質心作為簇的中心，收斂條件為平方誤差準則，如式（4）所示

式中：x——數據集中的文本對象，mi——簇的均值，Ci——簇，k——簇的數量。迭代過程中平方誤差E 不斷變小，當E 不再變化時，迭代結束，所有的文本對象被劃分到精細簇中，合并具有相同類標記的精細簇。至此，整個數據集的聚類結束。基于精細簇的K－Means聚類算法流程如圖6所示。

3 實驗及結果分析

檢驗聚類結果好壞的評價方式有查準率，查全率以及FMeasure。假設文檔類別為K，其中聚類C 主題為T，C 中主題類別為T 的對象數目為CT，主題類別不為T的數目為CF，其它類中主題為T的數目為COT，變量與類的對應見表1。

圖6 精細簇聚類過程

表1 變量名與類的關系

（1）查準率有時也稱準確率，是所有文本對象分類后，其所屬的類別與實際類別一致的數量與各類中對象總數的比值，如式 （5）所示

（2）查全率也稱召回率，是聚類C中與主題相關的文檔數目與人工分類相應主題所有文檔數目比率，如式（6）所示

（3）F－Measure是以查準率與查全率為基礎的綜合概念，對于第i個類的F－Measure值定義如式 （7）所示

為了測試聚類效果，文本采用搜狗實驗室分類制作的語料庫進行實驗，分別選取類汽車、財經、IT、健康4 個類，每個類別任意抽取其中的200 篇文檔，共800 篇文檔進行聚類。經過多次實驗，確定OPTICS 參數選取MinPts＝18 和ε ＝20。文本與傳統K－Means 以及文獻［12］中基于密度的算法 （這里記為DK－Means）進行了對比，為了保持一致性，算法中同時采用了余弦相似度及平方誤差收斂準則，并且設定傳統K－Means算法的K 為4。實驗中，一共隨機進行了10次實驗，經統計，分類準確率如圖7所示。

圖7 聚類準確率對比

從實驗結果可以看出，傳統K－Means算法中即使給定準確的聚類數K，也會由于初始種子的隨機選取，導致查準率不穩定 （浮動范圍0.7064～0.8953），浮動較大。DKMeans算法由于缺乏細化及合并的過程，準確率低于本文算法。由于本文方法將OPTICS算法與K－Means算法結合，為K－Means算法自動確定了初始類數K，并且提供了高質量的初始聚類中心，使得聚類結果相對穩定 （浮動范圍0.9114～0.9207），精細簇聚類概念的引入在提高聚類準確率方面也起到了一定的作用。每次實驗計算所得的查全率與F－Measure值呈現與查準率相同的起伏趨勢，各項數據統計結果如表2所示。由實驗結果可知，本文算法平均性能較傳統K－Means以及DK－Means算法均有提升。

表2 本文算法與傳統K－Means聚類質量對比

由于結構化概念的引入，減少了K－Means算法的計算量，使得算法時間相應減少，本文分別對不同量級的數據進行了實驗，與未經過結構化處理的K－Means算法進行比較，經過統計，結果如圖8所示，從圖中可以看出，結構化概念的引入有效地減少了K－Means算法的時間消耗。

圖8 算法時間消耗對比

4 結束語

本文針對K－Means算法的缺陷，提出了采用基于OP－TICS層次樹來優化K－Means算法初始中心的思想。在優化算法的基礎上，描述了文本數據挖掘中的文本預處理、數據模型構建、以及聚類分析的細節。聚類過程中，雖然表示文本數據集的數據矩陣進行了一定程度的降維，然而特征維數仍然較高，影響了聚類性能。下一步工作將深入研究降維技術，并進一步優化算法，實現在保證聚類質量的基礎上降低算法時間消耗。

［1］ZHANG Wenming，WU Jiang，YUAN Xiaojiao.K－Means text clustering algorithm based on density and nearest neighbor［J］.Journal of Computer Applications，2010，30 （7）：1933－1935 （in Chinese）.［張文明，吳江，袁小蛟.基于密度和最近鄰的K－Means文本聚類算法 ［J］.計算機應用，2010，30（7）：1933－1935.］

［2］HUANG Zhenhua，XIANG Yang，ZHANG Bo.An efficient method for K－Means clustering ［J］.PR＆AI，2010，23 （4）：516－521 （in Chinese）. ［黃震華，向陽，張波，一種進行KMeans聚類的有效方法 ［J］.模式識別與人工智能，2010，23（4）：516－521.］

［3］Jiang Dongyang，Zheng Wei，Lin Xiaoqing.Research on selection of initial center points based on improved K－Means algorithm ［C］／／2nd International Conference on Computer Science and Network Technology，2012：1146－1149.

［4］Yao Mingyu，Pi Dechang，Cong Xiangxiang.Chinese text clustering algorithm based K－Means［C］／／Proceedings of International Conference on Services Science，Management and Engineering，2010：9－12.

［5］CAI Yue，YUAN Jinsheng.Text clustering based on improved DBSCAN algorithm ［J］.Computer Engineering，2011，37（12）：50－52 （in Chinese）. ［蔡岳，袁津生.基于改進DBSCAN 算法的文本聚類 ［J］.計算機工程，2011，37 （12）：50－52.］

［6］ZHOU Weiben，SHI Yuexiang.Optimization algorithm of KMeans clustering center of selection based on density ［J］.Application Research of Computers，2012，29 （5）：1726－1728（in Chinese）.［周煒奔，石躍祥.基于密度的K－Means聚類中心選取的優化算法 ［J］.計算機應用研究，2012，29 （5）：1726－1728.］

［7］XU Qin，LUO Bin.K－Means clustering algorithm combined with mean－shift and minimum spanning tree ［J］.Computer Engineering，2013，39 （12）：204－210 （in Chinese）.［徐沁，羅斌.結合mean－shift與MST 的K－Means聚類算法 ［J］.計算機工程，2013，39 （12）：204－210.］

［8］Zhang Junhao，Ha Minghu，WU Jing.Implementation of rough fuzzy K－Means clustering algorithm in matlab ［C］／／International Conference on Machine Learning and Cybernetics，2010：2084－2087.

［9］Chandrasekhar Am，Raghuveer K.Intrusion detection technique by using K－Means，fuzzy neural network and SVM classifiers［C］／／International Conference onComputer Communication and Informatics，2013：1－7.

［10］Verma Vicky Kumar，Khanna Nitin.Indian language identification using K－Means clustering and support vector machine（SVM） ［C］／／Students Conference on Engineering and Systems，2013：1－5.

［11］Gan Zhigang，Xiao Nanfeng.A new ensemble learning algorithm based on improved K－Means for training neural network ensembles［C］／／Second International Symposium on Intelligent Information Technology and Security Informatics，2009：8－11.

［12］FU Desheng，ZHOU Chen.Improved K－Means algorithm and its implementation based on density ［J］.Journal of Computer Applications，2011，31 （2）：432－434 （in Chinese）. ［傅德勝，周辰.基于密度的K－均值算法 ［J］.計算機應用，2011，31 （2）：432－434.］