王日宏，崔興梅

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

0 引言

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

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

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

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

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

1.1 文本向量化表示

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

VSM方法便是把指定的文本表示成特定向量的形式，而文本是由特征詞體現(xiàn)出來的，并將其作為文本的表示單位。文本向量的維數(shù)與文本特征詞在其中的權(quán)重大小相互對(duì)應(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個(gè)特征詞在文本xi中的權(quán)重大小。對(duì)于特征詞的權(quán)重值的計(jì)算方法，通常選用TF-IDF(Term Frequency-Inverse Document Frequency)策略[19-20]。公式如下所示：

(1)

1.2 文本相似度計(jì)算

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

(2)

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

2 K-均值初始聚類中心改進(jìn)算法——K-MCD

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

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

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

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

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

(3)

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

定義2 文本聚類評(píng)價(jià)函數(shù)E：

(4)

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

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

(5)

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

2.2 K-MCD算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 初始簇中心選擇

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

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

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

步驟4 依次判斷下面的文本聚類中心點(diǎn)。對(duì)于集合D中剩余的任意文本對(duì)象pi，假如存在對(duì)象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作為第三個(gè)簇中心c3，并將p3從集合D中刪除；否則繼續(xù)判斷。對(duì)于下面的文本對(duì)象點(diǎn)按同樣的方式依次進(jìn)行判斷選擇，最終得到k個(gè)初始文本簇中心，即c1,c2,…,ck。

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

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

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

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

2.3 K-MCD算法進(jìn)行文本聚類

K-MCD算法進(jìn)行文本聚類過程如下：

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

Output:劃分的k個(gè)類別的簇。

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

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

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

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

(6)

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

步驟5 判斷算法終止條件。如果算法達(dá)到最大迭代次數(shù)T或者執(zhí)行修正操作后的簇中心幾乎保持不變，此時(shí)用適應(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ù)集仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)1——算法精確性測(cè)試

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

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

本實(shí)驗(yàn)采用大多數(shù)聚類分析所用的F-measure的衡量方法，其中涵蓋了查全率(Recall)和查準(zhǔn)率(Precision)兩個(gè)衡量方面。由類別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é)果用如下形式進(jìn)行定義，如式(9)所示：

(9)

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

(10)

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

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

表2 各算法的F-measure實(shí)驗(yàn)結(jié)果

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

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

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

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

3.2 實(shí)驗(yàn)2——算法穩(wěn)定性測(cè)試

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

表3 各算法的實(shí)驗(yàn)測(cè)試結(jié)果

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

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

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

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

4 結(jié)語(yǔ)

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

References)

[1] 彭京,楊冬青,唐世渭,等.一種基于語(yǔ)義內(nèi)積空間模型的文本聚類算法[J].計(jì)算機(jī)學(xué)報(bào),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] 王永貴,林琳,劉憲國(guó).結(jié)合雙粒子群和K-means的混合文本聚類算法[J].計(jì)算機(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均值聚類算法在銀行客戶細(xì)分中的研究[J].計(jì)算機(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ì)算模型[J].計(jì)算機(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] 程艷云,周鵬.動(dòng)態(tài)分配聚類中心的改進(jìn)K均值聚類算法[J].計(jì)算機(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].小型微型計(jì)算機(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].計(jì)算機(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].計(jì)算機(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].計(jì)算機(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的改進(jìn)K-means算法在文本聚類中的應(yīng)用[J].計(jì)算機(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] 安計(jì)勇,高貴閣,史志強(qiáng),等.一種改進(jìn)的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án)太山.基于平均差異度優(yōu)選初始聚類中心的改進(jìn)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)聚類個(gè)數(shù)和初始聚類中心點(diǎn)選取算法研究[J].計(jì)算機(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] 王永貴,林琳,劉憲國(guó).基于改進(jìn)粒子群優(yōu)化的文本聚類算法研究[J].計(jì)算機(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é)合詞項(xiàng)語(yǔ)義信息和TF-IDF方法的文本相似度量方法[J].計(jì)算機(jī)學(xué)報(bào),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.