融合集群度與距離均衡優(yōu)化的K-均值聚類算法

王日宏，崔興梅

(青島理工大學(xué) 計算機工程學(xué)院，山東 青島 266033)(*通信作者電子郵箱rihongw@126.com)

0 引言

隨著信息時代的發(fā)展，現(xiàn)有的技術(shù)手段無法實時滿足海量文本數(shù)據(jù)的要求，出現(xiàn)了一種“知識匱乏”困局。聚類作為數(shù)據(jù)挖掘的一個重要技術(shù)方法，目前已成為一大研究熱點。聚類分析不同于其他挖掘方法，它的優(yōu)勢主要體現(xiàn)在可以直接根據(jù)文本信息的自然分布狀態(tài)而挖掘出有用的信息[1]。按照特定方法，實現(xiàn)聚類后同類數(shù)據(jù)之間的相似性大，不同類間的相似性小。

K-均值聚類(K-means clustering)算法作為一種比較典型的聚類分析算法而備受關(guān)注，并廣泛應(yīng)用于文本聚類分析[2-3]、客戶細分[4]、交通管理[5]等實際應(yīng)用領(lǐng)域。文本聚類分析的目標則是通過衡量文本相似度，進而將雜亂的文本集分成幾個特定要求的類，實現(xiàn)同一類文本數(shù)據(jù)間的相似性大，不同類間的文本相似性小。然而傳統(tǒng)的K-均值算法具有初始簇中心選擇敏感、易受孤立點影響、易陷入局部極值、聚類結(jié)果不穩(wěn)定等缺點，致使聚類效果不佳，無法取得理想實驗效果。針對傳統(tǒng)K-均值算法存在的缺點，各種K-means改進算法紛紛涌現(xiàn)，主要從獲得最佳聚類中心與最好聚類數(shù)目這兩方面進行優(yōu)化[6-9]。樊寧[4]通過動態(tài)調(diào)整聚類數(shù)k的值，并采用密度半徑來優(yōu)化初始聚類中心選擇，但其客戶分類準確率有待提高。黃韜等[10]通過對原數(shù)據(jù)集多次采樣，并進行k個質(zhì)心的聚類運算，達到優(yōu)化選取初始聚類中心的目的，但存在參數(shù)點的選取對聚類影響不明確的不足。翟東海等[11]基于最遠樣本選取策略，采用最大距離法優(yōu)化選擇初始簇點并應(yīng)用于文本聚類，效果雖有所改善，卻未考慮選取初始簇中心的代表性。周愛武等[12]針對簇中心與孤立點的問題，采用距離和方法改進聚類算法，降低孤立點的影響程度，聚類效果顯著改善，而在查找孤立點時，會增加時間消耗。王春龍等[13]針對聚類結(jié)果不穩(wěn)的缺陷，基于隱含狄利克雷分布的優(yōu)化選取對文本集影響最大的主題，實驗減少了迭代次數(shù)，聚類效果明顯，但無法適應(yīng)高精度文本聚類的要求。安計勇等[14]引入置信半徑，并基于權(quán)重距離且采用輪廓系數(shù)優(yōu)化聚類效果，最終取得較好聚類質(zhì)量，但算法總耗時有所增加。李武等[15]提出基于數(shù)據(jù)空間分布選取初始簇中心，按照差異度的大小優(yōu)化選擇，提高聚類穩(wěn)定性與收斂性，而改進算法時間復(fù)雜度不太理想。張素潔等[16]引入誤差平方和來選取聚類數(shù)K值，并基于密集區(qū)域且簇中心相距較遠選擇初始策略，實驗聚類準確率較高，但未考慮各簇中心點總的度量距離。

為了降低K-均值算法受初始簇中心選擇的影響程度，使文本聚類呈現(xiàn)較穩(wěn)定的狀態(tài)，本文基于“集群度”優(yōu)化選擇思想，并且在初始聚類中心選擇過程中，同時遵循已選擇的所有簇中心距離總和最小原則，提出一種融合集群度與距離均衡優(yōu)化選擇的K-均值聚類(K-Means clustering based on Clustering degree and Distance equalization optimization,K-MCD)算法。針對K-均值算法對初始聚類中心選擇的隨機性與敏感性，在此通過基于“集群度”思想并融合所有簇中心的距離總和的均衡度量選取策略，優(yōu)化初始聚類中心，來改善文本聚類效果。通過選取文本數(shù)據(jù)集對本文中的改進算法進行驗證，從算法精確度與穩(wěn)定性方面進行實驗驗證，仿真結(jié)果表明，K-MCD算法可取得較好的實驗效果，且穩(wěn)定性好。

1 K-均值聚類算法及文本表示

K-均值聚類算法作為一種典型的基于距離的聚類算法，用相似度標準來衡量聚類的效果，樣本距離之間的大小程度決定了是否能歸屬同一類別，使得聚類后，樣本之間的聚類距離總和最小，進而得到最佳的效果。K-均值算法先隨機選取初始簇中心，然后分類樣本數(shù)據(jù)對象，并計算聚類相似度大小，不斷更新迭代進行，達到最大類間及最小類內(nèi)相似度聚類效果。K-均值算法在隨機選擇初始簇中心時，可能會影響算法整體的聚類穩(wěn)定性，文本聚類效果不理想。本文主要針對傳統(tǒng)K-均值算法初始簇中心選擇的敏感問題，改進并提出K-MCD算法，并運用于文本聚類研究。

1.1 文本向量化表示

文本無法直接被計算機識別并處理，要想將文本按照指定要求劃分為多個簇，實現(xiàn)文本聚類，通常運用向量空間模型(Vector Space Model, VSM)方法[17-18]，即將文本進行向量化處理，轉(zhuǎn)換成計算機能夠識別的形式，再計算出文本的相似度，方可進行文本聚類分析。

VSM方法便是把指定的文本表示成特定向量的形式，而文本是由特征詞體現(xiàn)出來的，并將其作為文本的表示單位。文本向量的維數(shù)與文本特征詞在其中的權(quán)重大小相互對應(yīng)。即文本集X={x1,x2,…,xn}，向量xi的向量空間形式是{w(t1,xi),w(t2,xi),…,w(tj,xi),…,w(tm,xi)}，其中，m是文本特征值的總數(shù)目，w(tj,xi)表示含義是第tj個特征詞在文本xi中的權(quán)重大小。對于特征詞的權(quán)重值的計算方法，通常選用TF-IDF(Term Frequency-Inverse Document Frequency)策略[19-20]。公式如下所示：

(1)

1.2 文本相似度計算

文本相似度作為統(tǒng)計文本之間相似程度的一個重要指標，想要進行文本聚類分析，必須構(gòu)造出一種恰當(dāng)?shù)亩攘哭k法，能把文本相似程度轉(zhuǎn)變成文本之間的距離來實現(xiàn)。由文獻可知，常見的轉(zhuǎn)換方法有3種，即距離函數(shù)法、余弦法與內(nèi)積法。本文選取距離函數(shù)的方法來衡量文本的相似程度，其中，距離采用常用的歐氏度量辦法，并且遵循文本相似度與文本距離成反比的原則，即隨著文本相似程度越大，文本之間的距離就會越小，取得的文本聚類效果便越好。度量公式如下所示：

(2)

其中，w(tk,xi)與w(tk,xj)分別表示tk個文本特征在xi與xj的特征權(quán)重值。

2 K-均值初始聚類中心改進算法——K-MCD

2.1 改進算法思想及相關(guān)定義

由于K-均值算法容易受到初始簇中心選擇的影響：一方面，算法的波動性可能會造成文本聚類效果不好，存在容易陷入局部解的缺點；另一方面，算法表現(xiàn)出總的迭代次數(shù)增加，系統(tǒng)開銷相對增大，效率低下，同時也會導(dǎo)致聚類結(jié)果的不穩(wěn)定性。在此，需要對初始簇中心的選取進行改進，尋找最佳聚類效果，本文主要基于以下兩點改進算法策略：

1)基于“集群度”思想?？傮w來講，想要取得較好的文本聚類效果，需要遵循集群度的策略辦法，即選取的各個簇中心能夠體現(xiàn)文本集的匯集程度，既能保證初始聚類中心的代表性，又能確保不會過度集中。相似度較大的文本更大概率地被分到同一個簇中，反之，相似度較小的文本更大概率地被分到不同的簇集中。

2)基于簇中心點間的度量總和優(yōu)化選擇策略。在優(yōu)化選擇初始簇中心的過程中，需要尋找一個劃分的尺度，即基于初步篩選出的對象最終確定出各個簇中心，確保簇中心的分散度，使得文本總的相似度最大(文本相距度最小)。本文提出一種基于距離總和均衡優(yōu)化選擇的度量辦法，既保證按照策略1)中“集群度”辦法選取簇中心的集中代表性，又能確保文本聚類整體相似度的最優(yōu)化與穩(wěn)定性。

對于文本集X={x1,x2,…,xn}，本文給定幾個相關(guān)定義形式。

(3)

其中：d(xi,xj)表示文本xi與xj之間的度量距離，n是文本集中的文本對象的總數(shù)目。

定義2 文本聚類評價函數(shù)E：

(4)

其中：c1,c2,…,ck為k個簇中心，d2(xp,cj)為簇Cj中任意文本對象xp與相應(yīng)聚類中心cj之間的度量距離的平方和。

定義3 文本聚類適應(yīng)度函數(shù)f(x)：

(5)

其中：λ為任意常數(shù)；k為簇的總數(shù)目；d2(xp,cj)為簇Cj中任意文本對象xp與相應(yīng)聚類中心cj之間的度量距離的平方和。

2.2 K-MCD算法

2.2.1 基于“集群度”初步篩選初始聚類中心

由于K-means算法對初始簇中心選取具有較大的敏感性，簇中心選取的不同，聚類結(jié)果可能會有比較大的差異性，如果選取不當(dāng)，甚至還會造成一些錯誤情況的發(fā)生。為了文本聚類的準確與穩(wěn)定性，在此基于“集群度”初步篩選初始聚類中心集合D。

關(guān)于“集群度”的定義方式，給定如下形式。

以二維隨機文本數(shù)據(jù)分布圖為例，如圖1所示，選取其中的一個樣本點作為代表簇中心，并且以distr作為覆蓋區(qū)域的長度，計算落在覆蓋區(qū)域圓內(nèi)的相應(yīng)文本數(shù)據(jù)點的數(shù)目，該數(shù)目便是此文本對象的集群度值。通過此種選擇方式便得到相應(yīng)對象點的集群度值，并依次選擇l(k≤l≤n)個作為最初的文本聚類中心點。操作步驟如下：

圖1 二維文本數(shù)據(jù)分布

步驟1 初始覆蓋域長度distr的確定。隨機選取k個數(shù)據(jù)點，記錄并連續(xù)取三次，按定義1計算這些數(shù)據(jù)點兩兩之間的平均距離并取均值，得到：

且d(xi,xj)表示文本xi與xj之間的度量距離，在此把計算的距離作為distr的值。

步驟2 計算并選取l個初始文本對象。按照“集群度”思想，選取l個初始文本對象，并依次按值的大小由高到低的順序排列為m1,m2,…,ml(k≤l≤n)，并存于集合M中，且|ml|表示集群度值。選取集群度值最大的m1定義成第一個簇中心點p1，并加入集合D內(nèi)，同時計算得到m1和m2的文本度量距離d(m1,m2)。

步驟3 如果d(m1,m2)≥distr，那么選取集群度值次大的文本對象m2成為第二個簇中心點p2加入集合D中；否則繼續(xù)判斷下一個文本對象。

The weight matrix is determined by the path of packet forwarding, while the congestion distribution plays a prominent role in the LNoC. Even though congestion-aware schemes produce extra LR, they are able to alleviate uneven congestion for NoC to reduce the LNoC.

步驟4 依次判斷下面的文本對象。判斷m3與前兩個簇中心點之間的度量距離，如果max[d(m3,m1),d(m3,m2)]≥distr，即可選擇m3作為第三個簇中心p3；否則舍棄，繼續(xù)判斷。對于下面的點依次進行判斷，并選取得到l個初始文本簇中心，得到集合D={p1,p2,…,pl}。

按此“集群度”方法初步篩選出l(k≤l≤n)個初始文本簇中心，優(yōu)化選取初始簇中心的集合，一方面，體現(xiàn)文本集的匯集程度，從密集區(qū)域選擇簇中心，加大同一簇內(nèi)的優(yōu)化效果；另一方面，又考慮到初始簇中心點的分散性，體現(xiàn)出文本集類間相似度小?；凇凹憾取钡倪x擇能初步改善K-均值算法不易受初始文本簇中心選擇的影響，但此辦法中未涉及算法整體的文本聚類效果。為更好地應(yīng)用于文本聚類，必須綜合考慮文本綜合相似度量。下文將對該算法作出進一步的改進策略。

2.2.2 融合距離總合均衡優(yōu)化選取初始聚類中心

根據(jù)上文基于“集群度”策略優(yōu)化初始聚類中心，篩選得到包含l個初始文本簇中心的集合D。在此基礎(chǔ)上，綜合考慮文本簇中心的距離總和的度量選擇，進一步優(yōu)化確定k個初始簇中心點，確保聚類問題整體的效果與算法的穩(wěn)定性。

下面選取4個簇數(shù)目為例，如圖2所示。融合“集群度”與距離總和均衡優(yōu)化選取的辦法，最終確定k個初始簇中心，過程如下：

圖2 初始簇中心選擇

步驟1 按“集群度”方法初步篩選出l個初始文本聚類中心，并將其保存在文本對象D集合中，且D={p1,p2,…,pl}。

步驟2 選取第一個初始文本簇中心對象。按“集群度”思想選取的l個初始文本對象集合D={p1,p2,…,pl}，選取集群度值最大的p1定義成第一個簇中心點(如圖2中的c1)，并從集合D中刪除，同時計算得到p1和p2的文本度量距離d(p1,p2)。

步驟3 選取第二個初始文本簇中心點。對于集合D中任意文本對象pi，假如存在對象p2，滿足u*d(p1,p2)+(1-u)*|p2|≥u*d(p1,pi)+(1-u)*|pi|(i=3,4,…,l)，其中，|pi|表示文本對象pi的集群度值，u為權(quán)衡調(diào)節(jié)因子(取任意常數(shù))，那么選取度量值(以融合集群度值與距離總和均衡選擇為標準)最大的對象p2作為第二個聚類中心(如圖2中的c2)，并將p2從集合D中刪除。

步驟4 依次判斷下面的文本聚類中心點。對于集合D中剩余的任意文本對象pi，假如存在對象p3，滿足{u*d(p1,p3)+(1-u)*|p3|}+{u*d(p2,p3)+(1-u)*|p3|}≥{u*d(p1,pi)+(1-u)*|pi|}+{u*d(p2,pi)+(1-u)*|pi|}(i=4,5,…,l)，即可選擇p3作為第三個簇中心c3，并將p3從集合D中刪除；否則繼續(xù)判斷。對于下面的文本對象點按同樣的方式依次進行判斷選擇，最終得到k個初始文本簇中心，即c1,c2,…,ck。

按照以上所述選取初始文本簇中心點的方法，既能保證簇中心的文本密集域的代表性，又能權(quán)衡簇中心的分散度(用文本待初始聚類點間的度量總和衡量)，綜合考慮文本初始聚類效果的最大優(yōu)化度。K-均值算法初始聚類中心點的改進，優(yōu)化選擇相對比較密集區(qū)域且具有一定分散性的初始聚類點，為進一步應(yīng)用于文本聚類分析提供最佳初始條件。

2.2.3 優(yōu)化選取初始簇中心算法流程

優(yōu)化選取k個初始聚類中心算法的流程，如圖3所示。

圖3 優(yōu)化選取初始簇中心流程

2.3 K-MCD算法進行文本聚類

K-MCD算法進行文本聚類過程如下：

Input:文本集X={x1,x2,…,xn}，聚類數(shù)目k，最大迭代次數(shù)T。

Output:劃分的k個類別的簇。

步驟1 按照2.2.2節(jié)中優(yōu)化選取初始簇中心的方法，得到k個初始文本簇中心，即：c1,c2,…,ck。

步驟2 對其他的文本對象，按照式(2)中文本相似度量方法，計算該文本xp到簇中心cj的距離為:

步驟3 分配各文本對象到相距最近的簇中心所代表的簇Cj中。

步驟4 修正各簇中心，根據(jù)式(6)優(yōu)化選取最佳文本簇中心。文本聚類評價函數(shù)采用2.1節(jié)中的式(4)計算，文本適應(yīng)度函數(shù)采用式(5)計算：

(6)

其中：Cj是第j個簇；cj與xp分別表示聚類中心點與簇內(nèi)任意文本對象；cj′為該簇內(nèi)其他待判斷的聚類中心點。

步驟5 判斷算法終止條件。如果算法達到最大迭代次數(shù)T或者執(zhí)行修正操作后的簇中心幾乎保持不變，此時用適應(yīng)度函數(shù)的變化來衡量，即|ft+1(x)-ft(x)|≤e(ft+1(x)與ft(x)分別為第t+1次與t次的文本適應(yīng)度函數(shù)值，e為趨向于無限小的數(shù)值)，則算法結(jié)束；否則繼續(xù)執(zhí)行步驟2，直到滿足條件為止。

K-MCD算法文本聚類流程如圖4所示。

圖4 文本聚類流程

3 文本數(shù)據(jù)集仿真實驗

3.1 實驗1——算法精確性測試

為驗證K-MCD算法文本聚類效果，本實驗分別采用傳統(tǒng)的K-均值算法、文獻[11]改進算法、文獻[18]改進算法、K-MCD算法進行實驗分析比較。其中，文獻[11]基于最大樣本距離的策略選取初始簇中心，重新構(gòu)造文本測度函數(shù)并應(yīng)用于文本聚類，在選取初始簇中心時未考慮樣本點的密集程度，可進一步優(yōu)化算法；文獻[18]通過動態(tài)調(diào)整慣性權(quán)重w及云變異策略改進粒子群算法，提高文本聚類全局搜索能力，而控制w參數(shù)的選擇有些局限，聚類穩(wěn)定性有待于提高。從騰訊網(wǎng)上選取測試文本數(shù)據(jù)集，每組數(shù)據(jù)集分別關(guān)于時尚、新聞、娛樂等幾大類別主題，實驗中使用的文本數(shù)據(jù)集如表1所示。

表1 實驗中使用的文本數(shù)據(jù)集

本實驗采用大多數(shù)聚類分析所用的F-measure的衡量方法，其中涵蓋了查全率(Recall)和查準率(Precision)兩個衡量方面。由類別i和j歸屬的類別主題，Recall衡量文本聚類分析覆蓋的完備度，定義形式如式(7)所示：

Recall(i,j)=Nij/Nj

(7)

Precision則是衡量文本聚類分析查找的精確度，定義形式如下：

Precision(i,j)=Nij/Ni

(8)

其中：Nij表示類別主題j在類別i的文本數(shù)目；Ni為分類i的文本總數(shù)目，Nj為類別主題j的總數(shù)目。且類別i的聚類結(jié)果用如下形式進行定義，如式(9)所示：

(9)

文本聚類結(jié)果是用類別i的加權(quán)平均值來衡量。如式(10)：

(10)

其中|i|指的是文本分類的數(shù)目。

為了更能證明文本實驗數(shù)據(jù)的有效性，對給定的數(shù)據(jù)集分別測試10次，取這10次的平均值作為最終的F-measure測量值，并記錄在表2中。

表2 各算法的F-measure實驗結(jié)果

為了便于直觀分析傳統(tǒng)的K-均值算法、文獻[11]改進算法、文獻[18]改進算法、K-MCD算法的文本準確度聚類效果，把實驗結(jié)果匯總成算法的F-measure值柱狀分布圖形式，如圖5所示。

圖5 各算法的F-measure柱狀圖

由圖5可知，從整體柱狀分布情況可以看出，在各類文本數(shù)據(jù)集上，本文提出的K-MCD算法的聚類精確度要高于其他3種算法，且相比傳統(tǒng)的K-均值算法來說，F(xiàn)-measure值提高的幅度較明顯，K-MCD算法在4個文本集上的F-measure值分別提高了18.6、17.5、24.3與24.6個百分點，取得較好的聚類精確度，且在文本集D4上的效果最明顯。對比文獻[11]與文獻[18]中的改進算法，K-MCD算法都在文本集D2上的F-measure值增長幅度最大，分別提高了9與6.6個百分點，其次便是在文本集D4上，K-MCD算法的F-measure值分別提高了6.9與6.4個百分點。

從圖中可以看出，對于不同的文本數(shù)據(jù)集，文本采用的K-MCD算法中的精確度也都有不同程度的提高。文本集D1從K-均值算法中的聚類精確值0.518提高到了0.704，約提高了18.6個百分點，效果明顯，而且相比文獻[11]以及文獻[18]提到的改進算法，F(xiàn)-measure值相應(yīng)地都提高了2.9%與3.1%；同樣在文本集D2上呈現(xiàn)出良好的聚類準確性；對于文本集D3，K-MCD算法與文獻[11]與文獻[18]提到的算法的聚類精確度比較，聚類準確性效果不是很顯著，尤其在對比文獻[18]中的算法僅增加了0.9個百分點，但相比K-均值算法有較大的改善效果，增長了超過20個百分點。其中，本文中的K-MCD算法中的F-measure值在D1、D3、D4三個數(shù)據(jù)集上面超過了0.7，并且在文本集D4上達到0.778的最大精確度值?？偟膩碚f，本文中的K-MCD算法聚類準確性改進效果明顯。

3.2 實驗2——算法穩(wěn)定性測試

本實驗采用的文本數(shù)據(jù)集是從中文分類語料庫(http://www.sogou.com/labs/)中選取的1 500篇測試文檔，包括關(guān)于教育、軍事、體育等共5類，每類300篇。分別采用傳統(tǒng)的K-均值算法、文獻[4]改進算法、文獻[11]改進算法、K-MCD算法進行實驗分析比較。其中，文獻[4]采用有效指數(shù)法調(diào)整聚類數(shù)，并結(jié)合自適應(yīng)密度半徑優(yōu)化初始簇中心選擇，提高聚類速度，但算法改進需要更切合實際客戶需求；文獻[11]算法思想同實驗1所述。每種算法運行50次，對該文本集測試多次，分別記錄適應(yīng)度函數(shù)值f(x)、算法收斂時的最大迭代次數(shù)及進化代數(shù)方差三者的最小值、最大值及其平均值的數(shù)據(jù)情況(測試得到的大小均值分別用fmin、fmax、fave以及min、max、ave表示)，且式(5)中λ取值為100，各算法實驗情況如表3所示。

表3 各算法的實驗測試結(jié)果

由表3可知，本文提出的K-MCD算法聚類穩(wěn)定效果明顯，穩(wěn)定性較好。在平均進化代數(shù)方差方面，K-MCD算法比K-均值算法降低了36.99個百分點,相比文獻[4]與文獻[11]中提到的算法，也分別降低了8.28個百分點與4.22個百分點。文本相似度越大，評價函數(shù)之間的度量距離越小，文本的適應(yīng)度函數(shù)值會越大，算法的聚類效果便越好。K-MCD算法的適應(yīng)度平均值為7.201 1，明顯高于傳統(tǒng)的K-均值算法中的6.581 7，且相對于文獻[4]和文獻[11]中的改進算法，K-MCD算法平均適應(yīng)度值分別增加9.93個百分點與12.3個百分點的良好改善效果。文獻[11]中的改進算法相比文獻[4]提到的算法來講，雖然平均適應(yīng)值略小，不過平均進化代數(shù)方差小，穩(wěn)定性更好，整體效果比較好。從算法整體的最大迭代次數(shù)上來看，K-均值算法平均30次達到穩(wěn)定收斂，本文中的改進算法可在22次內(nèi)達到最大收斂效果，并且K-MCD算法的波動范圍相對較小，能降低K-均值算法本身受初始簇中心選取的影響，穩(wěn)定性能提高。

同時，根據(jù)K-均值算法、文獻[4]中的改進算法、文獻[11]中的改進算法及K-MCD算法在此文本數(shù)據(jù)集上平均適應(yīng)度值隨迭代次數(shù)的走勢變化，繪制各算法的收斂圖，如圖6所示。

由圖6可知，從圖像的整體走勢來看，本文提出的K-MCD算法相比傳統(tǒng)K-均值算法有比較明顯的聚類收斂性，在算法迭代初期，改進初始簇中心策略的引入可以較大程度地提高算法快速收斂的能力，雖然比文獻[4]、文獻[11]中提到的改進算法迭代初期沒有較大程度的改善，不過在算法迭代5次之內(nèi)，K-MCD算法有較快尋找最優(yōu)解的趨勢，能有效避開局部最優(yōu)區(qū)域。文獻[11]中的改進算法相比文獻[4]中的算法來講，雖然平均適應(yīng)值略小，不過在迭代10～20次內(nèi)能較快地趨于最優(yōu)解的尋找，穩(wěn)定性能更好，并且從圖中可以看到，相對于K-均值算法適應(yīng)度值緩慢增長來說，本文中的K-MCD算法文本聚類優(yōu)化效果比較明顯，且K-MCD、文獻[4]及文獻[11]中提到的這3種算法的平均適應(yīng)度值達到7以上。在算法迭代后期，K-均值算法需要迭代30次才能達到最終收斂，K-MCD算法能在有限的迭代次數(shù)22次內(nèi)趨于穩(wěn)定狀態(tài)，文本聚類穩(wěn)定性能比較好。

圖6 各算法在文本集上的收斂圖

4 結(jié)語

K-均值算法前期容易受到初始簇中心波動性的影響，在文本聚類中可能會導(dǎo)致聚類效果不精確與不穩(wěn)定。本文基于集群度思想，篩選出具備代表性且匯集度較好的對象，進一步融合距離優(yōu)化策略，從中確定出初始簇中心點，能克服K-均值算法前期簇中心選擇敏感性的缺點，避開局部解區(qū)域，減少迭代次數(shù)，并趨于穩(wěn)定收斂狀態(tài)。對文本數(shù)據(jù)集進行向量化表示，將文本相似度轉(zhuǎn)化為文本距離度量法，基于改進的K-MCD算法，重新優(yōu)化選擇初始文本簇中心，從精確性與穩(wěn)定性兩個方面進行本文數(shù)據(jù)集的驗證。仿真實驗證明了本文提出的K-MCD算法有較好的文本聚類效果與收斂性。對于文本聚類的向量轉(zhuǎn)化及K-均值算法中待分類數(shù)目的判斷有待于進一步研究。

References)

[1] 彭京,楊冬青,唐世渭,等.一種基于語義內(nèi)積空間模型的文本聚類算法[J].計算機學(xué)報,2007,30(8):1354-1363.(PENG J, YANG D Q, TANG S W, et al. A novel text clustering algorithm based on inner product space model of semantic [J]. Chinese Journal of Computers, 2007, 30(8): 1354-1363.)

[2] MAHDAVI M, ABOLHASSANI H. HarmonyK-means algorithm for document clustering [J]. Data Mining & Knowledge Discovery, 2009, 18(3): 370-391.

[3] 王永貴,林琳,劉憲國.結(jié)合雙粒子群和K-means的混合文本聚類算法[J].計算機應(yīng)用研究,2014,31(2):364-368.(WANG Y G, LIN L, LIU X G. Hybrid text clustering algorithm based on dual particle swarm optimization andK-means algorithm [J]. Application Research of Computers, 2014, 31(2): 364-368.)

[4] 樊寧.K均值聚類算法在銀行客戶細分中的研究[J].計算機仿真,2011,28(3):369-372.(FAN N. Simulation study on commercial bank customer segmentation onK-means clustering algorithm [J]. Computer Simulation, 2011, 28(3): 369-372.)

[5] 高曼,韓勇,陳戈,等.基于K-means聚類算法的公交行程速度計算模型[J].計算機科學(xué),2016,43(S1):422-424.(GAO M, HAN Y, CHEN G, et al. Computational model of average travel speed based onK-means algorithms [J]. Computer Science, 2016, 43(S1): 422-424.)

[6] LOUHICHI S, GZARA M, ABDALLAH H B. A density based algorithm for discovering clusters with varied density [C]// Proceedings of the 2014 World Congress on Computer Applications and Information Systems. Piscataway, NJ: IEEE, 2014: 1-6.

[7] YEDLA M, PATHAKOTA S R, SRINIVASA T M. EnhancingK-means clustering algorithm with improved initial center [J]. International Journal of Computer Science & Information Technologies, 2010, 1(2): 121-125.

[8] 程艷云,周鵬.動態(tài)分配聚類中心的改進K均值聚類算法[J].計算機技術(shù)與發(fā)展,2017,27(2):33-36.(CHENG Y Y, ZHOU P. ImprovedK-means clustering algorithm for dynamic allocation cluster center [J]. Computer Technology and Development, 2017, 27(2): 33-36.)

[9] 于海濤,李梓,姚念民.K-means聚類算法優(yōu)化方法的研究[J].小型微型計算機系統(tǒng),2012,33(10):2273-2277.(YU H T, LI Z, YAO N M. Research on optimization method forK-means clustering algorithm [J]. Journal of Chinese Computer Systems, 2012, 33(10): 2273-2277.)

[10] 黃韜,劉勝輝,譚艷娜.基于K-means聚類算法的研究[J].計算機技術(shù)與發(fā)展,2011,21(7):54-57.(HUANG T, LIU S H, TAN Y N. Research of clustering algorithm based onK-means [J]. Computer Technology and Development, 2011, 21(7): 54-57.)

[11] 翟東海,魚江,高飛,等.最大距離法選取初始簇中心的K-means文本聚類算法的研究[J].計算機應(yīng)用研究,2014,31(3):713-715.(ZHAI D H, YU J, GAO F, et al.K-means text clustering algorithm based on initial cluster centers selection according to maximum distance [J]. Application Research of Computers, 2014, 31(3): 713-715.)

[12] 周愛武,于亞飛.K-means聚類算法的研究[J].計算機技術(shù)與發(fā)展,2011,21(2):62-65.(ZHOU AW, YU Y F. The Research about clustering algorithm ofK-means [J]. Computer Technology and Development, 2011, 21(2): 62-65.)

[13] 王春龍,張敬旭.基于LDA的改進K-means算法在文本聚類中的應(yīng)用[J].計算機應(yīng)用,2014,34(1):249-254.(WANG C L, ZHANG J X. ImprovedK-means algorithm based on latent Dirichlet allocation for text clustering [J]. Journal of Computer Applications, 2014, 34(1): 249-254.)

[14] 安計勇,高貴閣,史志強,等.一種改進的K均值文本聚類算法[J].傳感器與微系統(tǒng),2015,34(5):130-133.(AN J Y, GAO G G, SHI Z Q, et al. An improvedK-means text clustering algorithm [J]. Transducer and Microsystem Technologies, 2015, 34(5): 130-133.)

[15] 李武,趙嬌燕,嚴太山.基于平均差異度優(yōu)選初始聚類中心的改進K-均值聚類算法[J].控制與決策,2017,32(4):759-762.(LIU W, ZHAO J Y, YAN T S. ImprovedK-means clustering algorithm optimizing initial clustering centers based on average difference degree [J]. Control and Decision, 2017, 32(4): 759-762.)

[16] 張素潔,趙懷慈.最優(yōu)聚類個數(shù)和初始聚類中心點選取算法研究[J].計算機應(yīng)用研究,2017,34(6):1-5.(ZHANG S J, ZHAO H C. Algorithm research of optimal cluster number and initial cluster center [J]. Application Research of Computers, 2017, 34(6): 1-5.)

[17] SALTON G, WONG A, YANG C S. A vector space model for automatic indexing [J]. Communications of the ACM, 1975, 18(11): 613-620.

[18] 王永貴,林琳,劉憲國.基于改進粒子群優(yōu)化的文本聚類算法研究[J].計算機工程,2014,40(11):172-177.(WANG Y G, LIN L, LIU X G. Research on text clustering algorithm based on improved particle swarm optimization [J]. Computer Engineering, 2014, 40(11): 172-177.)

[19] SALTON G, BUCKLEY C. Term-weighting approaches in automatic text retrieval [J]. Information Processing & Management, 1988, 24(5): 513-523.

[20] 黃承慧,印鑒,侯昉.一種結(jié)合詞項語義信息和TF-IDF方法的文本相似度量方法[J].計算機學(xué)報,2011,34(5):856-864.(HUANG C H, YIN J, HOU F. A text similarity measurement combining word semantic information with TF-IDF method [J]. Chinese Journal of Computers, 2011, 34(5): 856-864.)

This work is partially supported by the National Natural Science Foundation of China (61502262), the Shandong Graduate Education Innovation Program (SDYY16023).

WANGRihong, born in 1964, M. S., professor. His research interests include intelligent information processing, data mining.

CUIXingmei, born in 1990, M. S. candidate. Her research interests include intelligent information processing.