用于文本聚類的新型差分進化粒子群算法

胡曉敏，王明豐 ，張首榮，李 敏，2

1.廣東工業(yè)大學 計算機學院，廣州 510006

2.廣東工業(yè)大學 信息工程學院，廣州 510006

聚類是一種無監(jiān)督的機器學習任務，其目的是將數(shù)據(jù)集按照某種結(jié)構(gòu)或者相似度進行分組，劃分為若干數(shù)目的簇集，同時盡可能保證同一聚集內(nèi)的數(shù)據(jù)樣本盡量相似，而使屬于不同類別的樣本具有明顯差別。隨著文本資源的急劇遞增，信息檢索[1]、主題分析數(shù)據(jù)[2]和社交網(wǎng)絡[3]等領域?qū)ξ谋就诰蚺c分析的迫切需求，文本聚類也越來越得到重視[4]。

K-均值（K-means）算法是最早用于聚類的無監(jiān)督算法，該算法實現(xiàn)簡單，收斂速度快，但也存在對聚類中心初始值十分敏感，并且容易陷入局部最優(yōu)解的缺點。而文本作為一種特殊的非結(jié)構(gòu)化的數(shù)據(jù)，具有維度高、特征稀疏和數(shù)據(jù)關聯(lián)性低的特點，該算法應用于文本聚類時，其缺點則會明顯凸現(xiàn)出來，最終造成聚類效果差、早熟收斂的結(jié)果[5]。

為了提高文本聚類的性能表現(xiàn)，很多學者利用基于元啟發(fā)式的群體智能進化算法來改善聚類中心的更新方式。例如文獻[6]提出一種特征選擇方法用于粒子群優(yōu)化（Particle Swarm Optimization，PSO）中提高文本聚類的性能。文獻[7]提出基于自適應慣性權(quán)重函數(shù)的PSO與K-means結(jié)合的聚類算法，并在醫(yī)學電子病歷數(shù)據(jù)上取得較高的聚類準確率與執(zhí)行效率。文獻[8]提出利用隨機樣本的中位值來初始化聚類中心，并且劃分子種群進行更新，然后再合并動態(tài)差分進化（Differential Evolution，DE）算法用于聚類。由于單一的進化算法無法在穩(wěn)定性、收斂速度、搜索能力等方面都具備良好表現(xiàn)，嘗試利用混合算法進行聚類成為一種可行的方案。文獻[9]提出利用全局優(yōu)化能力較好的遺傳算法（Genetic Algorithm，GA）進行聚類，隨后從最優(yōu)個體劃分各樣本簇集中隨機選擇的樣本作為個體聚類中心的初始值，再用量子PSO算法進行聚類的混合遺傳量子粒子群（Genetic Quantum PSO，GQPSO）算法。文獻[10]提出將種群中的個體按照適應度值進行排序，并且劃分為兩個子種群，隨后在兩個子種群中分別采用PSO 和GA 算法進行更新的遺傳改進粒子群（Genetically Improved PSO，GAI-PSO）算法。

上述算法在初始聚類中心優(yōu)化、更新方式、全局優(yōu)化能力等方面進行改善，取得了一定成果。但在場景更普遍、維度更高的文本聚類方面鮮有應用，并且忽視了個體間各維度聚類中心排列的一致性問題，即聚類中心排列順序完全隨機的兩個個體在同一維度上的聚類中心可能屬于間隔較遠的簇集，該現(xiàn)象在一定程度上會影響個體更新效率與學習效果。

因此本文提出一種自適應調(diào)整聚類中心排列順序的方法用于改善種群個體學習效率，并首先利用多樣性更好的DE算法進行初步聚類，然后當算法收斂停滯后，再利用PSO 算法進行更穩(wěn)定的局部搜索。該混合聚類算法IDEPSO充分發(fā)揮了各算法在不同時期的優(yōu)勢，并提高了個體間的學習效率，有效避免了算法搜索的盲目性。通過在文本數(shù)據(jù)集上進行測試，驗證了此算法是一種穩(wěn)定高效的算法。

1 背景

1.1 文本聚類相關基礎

在進行聚類之前，文本形式的非結(jié)構(gòu)化的數(shù)據(jù)需要轉(zhuǎn)換為計算機程序容易處理的格式。向量空間模型（Vector Space Model，VSM）是一種常用并且效果良好的轉(zhuǎn)換模型[11]。在VSM 模型中，每個文本可表示為其包含的關鍵詞組成的向量，向量的維度為整個文本數(shù)據(jù)集不同關鍵詞的總數(shù)，每一維度的權(quán)重采用tf-idf計算，該權(quán)重綜合考慮了每個關鍵詞在其所在文檔中出現(xiàn)的頻率tf和在整個文本數(shù)據(jù)集中的分布情況idf這兩個因素的共同作用。

文本數(shù)據(jù)集轉(zhuǎn)換為tf-idf向量矩陣后，具有維度高、特征稀疏、空間結(jié)構(gòu)復雜的特點，因此一般采用向量夾角余弦值來表示文本之間的相似程度。文本向量之間的夾角越小，余弦值越大，則文本之間的相似度越高。對于文本向量di和dj，其相似程度的計算公式如下：

1.2 粒子群優(yōu)化算法

粒子群優(yōu)化（PSO）算法[12]是一種基于群體智能理論的進化算法，其基本思想為：隨機初始化一定數(shù)目的種群，其中每個個體代表待解決問題的一個潛在候選解，通過評價函數(shù)來衡量這個解的質(zhì)量，然后個體通過自身的飛行行為和整個種群的飛行經(jīng)驗來更新速度，再結(jié)合速度調(diào)整飛行位置，最終朝解空間中的最優(yōu)位置逐步逼近，直至最優(yōu)解收斂穩(wěn)定。PSO算法在第t次迭代對個體xi的速度和位置的更新公式如下：

其中，w為慣性權(quán)重；c1和c2為加速因子；i=1,2,…,N,N代表種群規(guī)模；j=1,2,…,D,D為個體的維度；pbesti代表個體i自身找到的最優(yōu)解；gbest為全局最優(yōu)解；r1和r2為[0，1]間的隨機數(shù)。

PSO 是一種實現(xiàn)方式和參數(shù)設置簡單且快速高效的算法。但在優(yōu)化目標過于復雜且有多個局部最優(yōu)解，或搜索空間維度高、規(guī)模大時，隨著時間的推移，種群中個體之間的差異逐漸縮小，種群個體在固定區(qū)間波動，最終使得算法陷入局部最優(yōu)解并無法跳出[13-15]。經(jīng)過多年的發(fā)展，在PSO 應用于數(shù)據(jù)挖掘的過程中，目前已有許多成熟的改善PSO 算法缺陷的方法。例如文獻[16]采用一種社團劃分的方法減少初始化過程中的冗余信息來提高初始化種群的質(zhì)量；文獻[17]在種群更新過程中加入混沌搜索和動態(tài)因子增加總?cè)旱亩鄻有裕欢墨I[18]則提出一種基于混合互信息和粒子群算法的自適應突變策略擾動種群，避免其陷入局部最優(yōu)解的方法。

1.3 差分進化算法

差分進化（DE）算法[19]是一種多樣性較好的進化算法，它通過隨機選擇種群中的個體構(gòu)造差分向量，然后基于某個個體或自身歷史最優(yōu)個體作為目標向量進行交叉融合構(gòu)造后代，最后根據(jù)適應度值選擇是否更好來更新個體產(chǎn)生新的種群。

DE算法通過向量變異、交叉、選擇三個步驟產(chǎn)生新的個體。對于標準DE 算法，種群中的每個個體都是通過以下公式進行變異操作：

其中，i=1,2,…,N;r1,r2,r3∈{1,2,…,N}為互不相同且不同于i的隨機數(shù)；γ為變異因子，控制差分向量的比重。然后根據(jù)以下公式對變異后的個體進行交叉操作得到臨時個體

其中，i=1,2,…,N,j=1,2,…,D,jrand∈{1,2,…,D}為隨機數(shù)，randij為[0，1]間的隨機數(shù)，Cr為[0，1]間的交叉概率。最后通過競爭選擇策略產(chǎn)生新種群中的個體：

若交叉操作得到的個體不差于原來的個體，則替換原個體作為新一代的個體，否則新一代的個體仍為原個體。

2 IDEPSO聚類算法

2.1 問題定義與評價函數(shù)

進化算法采用基于劃分的方式進行聚類時，種群每個個體表示一種劃分方案。若文本數(shù)據(jù)集需要劃分為K個類別，則每個個體xi包含K個聚類中心向量，可表示為xi=[mi1,mi2,…,mik,…,miK]，其中mik表示第i個個體的第k個聚類中心向量。算法的優(yōu)化目標為使各個簇集的相似度總和盡可能大，各簇集的相似度為該簇集包含的全部樣本到其聚類中心向量的相似度總和，因此個體i的評價函數(shù)的計算方式為：

其中，d為該個體第k個簇集所包含的每一個文本向量樣本。F越大表示聚類效果越好。

2.2 自適應調(diào)整聚類中心排列順序

由于種群個體的聚類中心排列順序完全隨機，包含K個聚類中心，共有K!種排列方式。當個體間進行諸如pbesti-xi，gbest-xi這類交叉操作時，會出現(xiàn)不同簇集上差別較大的聚類中心出現(xiàn)在同一維度上的情形。例如有兩個個體xi={a1,b1,c1},xj={b2,c2,a1}（字母相同表示聚類中心相似度最高）屬于同一簇集，但這兩組聚類中心向量的排列完全錯開。在速度更新過程中，它們進行向量加減操作時，將無法為個體提供有效的搜索經(jīng)驗，從而影響個體間的學習效果，甚至誤導個體朝著脫離最優(yōu)解的方向搜索。

鑒于上述情形，本文提出一種基于個體間聚類中心向量相似度矩陣的自適應調(diào)整聚類中心向量排列順序的方法。該方法基于相似度大小的雙向選擇與淘汰策略，盡可能將相似度最高的兩個聚類中心向量排列在同一維度。以個體xi和xj為例，自適應調(diào)整聚類中心向量排列順序的方法的步驟如下：

（1）假設以xj的聚類中心排列順序為基準對xi進行調(diào)整，計算xi與xj各聚類中心之間的相似度矩陣M。

（2）分別統(tǒng)計M各行、列上相似度最大值的索引列表Lij和Lji，分別表示xi與xj期望與對方的聚類中心形成對應關系的列表。

（3）若Lij存在重復值t，則存在對應關系沖突，即xi存在兩個及以上的聚類中心都對應于xj中同一個聚類中心此時由xj(t)從Lji中選擇與自身最近的聚類中心xi(s)構(gòu)建對應關系，確定的對應關系組合為(xi(s),xj(t))。

（4）將M第s行第t列除M[s][t]以外的其他相似度值都重置為最小值，防止其他聚類中心繼續(xù)選擇與它們組成對應關系組合。

（5）重復（2）～（4）直到Lij中不存在重復的值，即xi不存在兩個及以上的聚類中心對應于xj中的同一個聚類中心，最后按照Lij調(diào)整xi中各聚類中心排列順序。

下面給出調(diào)整前xi與xj各聚類中心之間的位置（圖1（a））與相似度矩陣M（表1）的例子。圖中顏色相同的聚類中心表示在同一維度。可以看出由于聚類中心排列的隨機性，相近的聚類中心并沒有獲得相同的標號，在相似度矩陣上則體現(xiàn)在每一列的最大值不在對角線上。相似度值越大體現(xiàn)兩個聚類中心位置越靠近。因此，通過調(diào)整聚類的排列，使得位置接近的聚類中心獲得相同的聚類排列號。

圖1 K=3 時兩個個體聚類中心調(diào)整前后示意圖

表1 聚類中心調(diào)整前后的相似度矩陣M

當以xj各個聚類中心排列為基準，根據(jù)表1調(diào)整前xi與xj各聚類中心相似度矩陣列表M可知，各行各列的最大值索引列表分別為Lij=[3,1,1]和Lji=[2,3,1]。這說明xi(2)、xi(3)均期望與xj(1)配對，此時產(chǎn)生沖突，從表1調(diào)整前的相似度列表或Lji可以看出xj(1)與xi(2)相似度最大，因此選擇與xi(2)配對。由于xi(3)競爭失敗，開始選擇與xj其他聚類中心xj(2)配對，Lij調(diào)整為[3,1,2]（該過程在實際情況下可能會根據(jù)Lij產(chǎn)生沖突的次數(shù)反復進行）。最終Lij不存在沖突后，按照Lij調(diào)整xi各聚類中心的排列順序為{xi(2),xi(3),xi(1)},與xj的相似度矩陣列表如表1調(diào)整后的表格所示，聚類中心分布情況如圖1（b）所示。可見xi個體原來的聚類中心排列由（1，2，3）調(diào)整為（2，3，1）。可以看出調(diào)整后兩個個體基本上在同一維度上的兩個聚類中心相似度最大。調(diào)整后再進行個體間的交叉操作能使產(chǎn)生的差分向量更具有引導性。

2.3 算法實現(xiàn)流程

PSO是一種高效穩(wěn)定的進化算法，但在搜索空間龐大的文本聚類過程中，隨著迭代次數(shù)增加，種群容易陷入局部最優(yōu)解。因此可以采用多樣性更好的DE算法進行初步搜索，當算法在找到較理想的最優(yōu)解并收斂停滯后，再利用PSO 進一步完善最優(yōu)解的位置，盡可能優(yōu)化出更理想的最優(yōu)解。同時在種群迭代過程中，始終利用自適應調(diào)整聚類中心排列順序的操作，提高種群的學習效率與收斂速度。該混合算法IDEPSO的實現(xiàn)步驟如下：

（1）構(gòu)造數(shù)量為N的種群，對于種群中的每個個體xi(i=2,3,…,N)，從數(shù)據(jù)集中隨機選取K個樣本對應的文檔向量作為其初始值(mi1,mi2,…,mik,…,miK)。種群迭代次數(shù)t初始化為0。

（2）計算種群每個個體xi各聚類中心mik(i=1,2,…,N;k=1,2,…,K)與數(shù)據(jù)集中所有文本的相似度大小，然后樣本歸類至與其相似度最大的聚類中心所在簇集。

（3）計算每個個體的適應度值，設置每個個體xi的歷史最優(yōu)個體pbesti為當前個體，計算種群當前全局最優(yōu)個體gbest。

（4）自適應調(diào)整參與種群更新的個體間聚類中心的排列順序并采用標準DE 算法對種群進行更新，利用每個個體表示的一組聚類中心向量對所有樣本進行劃分，計算劃分后每個簇集的聚類中心與適應度值，更新個體向量、種群的最優(yōu)個體gbest。種群迭代次數(shù)t加1。重復該過程，直到gbest連續(xù)T代穩(wěn)定不變。

（5）自適應調(diào)整參與更新的個體間聚類中心的排列順序并采用標準PSO算法對種群進行更新，利用每個個體表示的一組聚類中心向量對所有樣本進行劃分，計算劃分后每個簇集的聚類中心與適應度值，更新個體向量、每個個體xi的歷史最優(yōu)個體pbesti和種群當前全局最優(yōu)個體gbest。種群迭代次數(shù)t加1。

（6）若步驟（5）找到更優(yōu)個體則更新gbest，返回步驟（4）；否則重復執(zhí)行步驟（5）。當?shù)螖?shù)t達到預設的最大迭代次數(shù)時，算法停止并輸出最優(yōu)個體的適應度值、聚類中心和樣本劃分的類別集合。

3 實驗設計與數(shù)據(jù)分析

3.1 數(shù)據(jù)集與參數(shù)設置

本文實驗部分選取文本挖掘領域通用的Reuters-21578 標準語料庫（http：//kdd.ics.uci.edu/databases/）和CMU 小組收集的 WebKb4 語料庫（http：//www.cs.cmu.edu/～TextLearning/datasets.html）作為實驗測試數(shù)據(jù)集。這些測試數(shù)據(jù)集的具體信息如表2 所示。其中算法測試的聚類數(shù)量K的值為表中的主題數(shù)。

表2 測試數(shù)據(jù)集

本實驗比較未添加聚類中心排列調(diào)整的DEPSO算法和添加了該操作的IDEPSO 算法，與傳統(tǒng)PSO、DE、GQPSO[9]、GAI-PSO[10]算法在4 個文本數(shù)據(jù)集上的聚類結(jié)果。本文算法采用的參數(shù)設置均為標準PSO 和DE算法的推薦取值[20-21]，對比算法的參數(shù)按文獻給出的取值設置如下：w=0.9,c1=c2=1.495,γ=2.0,Cr=0.7 。所有算法的默認種群規(guī)模為20，種群的最大迭代次數(shù)為150。為了減少初始種群的隨機性對算法比較的影響，實驗中對于同一次獨立測試，各個算法采用相同的隨機初始種群。所有算法獨立運行20次。

3.2 聚類評價標準

聚類算法的聚類效果的評價標準可分為內(nèi)部評價和外部評價。內(nèi)部評價指標采用所有文本到距離它最近的聚類中心的余弦相似度的總和F（適應度函數(shù)），該評價指標能有效評估聚類的緊密程度。外部評價指標采用 ARI（Adjusted Rand Index）和 FMI（Fowlkes-Mallows Index）。

ARI是在蘭德系數(shù)基礎上考慮樣本隨機劃分的情況下的聚類評價模型，其計算方式為：

其中，RI為蘭德系數(shù)，ARI取值范圍為[-1,1]，值越大則預測樣本分布與實際情況吻合程度越高。

FMI是比較樣本的預測類別和真實類別的一個有效指標，F(xiàn)MI定義為預測精度與召回率的幾何平均值。

其中，TP表示真陽性，即預測標簽和真實標簽相同的樣本數(shù)量；FP為假陽性，即預測標簽中類別不相同而在真實標簽中相同的樣本數(shù)量；FN為假陰性，即在預測標簽中類別相同而在真實標簽中不同的樣本數(shù)量。FMI的上限值為1，值越大表示與樣本真實標簽越匹配，F(xiàn)MI沒有對簇的結(jié)構(gòu)做出假設，非常適合用來比較聚類算法的性能。

3.3 實驗結(jié)果與分析

3.3.1 種群規(guī)模對算法性能的影響分析

本文測試了種群規(guī)模N為10、20 和30 時DEPSO算法和IDEPSO 算法在最大函數(shù)評價次數(shù)為3 000 時的目標函數(shù)F的平均值，如表3 所示。這里采用最大函數(shù)評價次數(shù)是為了使種群規(guī)模不一致時算法的計算量相對均衡，這個計算量與種群規(guī)模為20 時最大迭代次數(shù)為150 代是相同的。從表中的數(shù)據(jù)可以看出，種群規(guī)模為30 時得到的平均值結(jié)果最優(yōu)，規(guī)模為10 時結(jié)果最差。

表3 DEPSO和IDEPSO算法在不同種群規(guī)模下F 平均值

圖2 給出了這兩個算法在不同種群規(guī)模時算法基于函數(shù)評價次數(shù)的平均迭代收斂曲線。種群規(guī)模越小，算法初始找到最優(yōu)解的速度越快，但更容易陷入局部最優(yōu)解而收斂停滯，最后得到的最優(yōu)解質(zhì)量較差。種群規(guī)模越大，初始收斂速度越慢，但隨著迭代進行，容易跳出局部最優(yōu)找到更好的解。另一方面，可以看出IDEPSO算法的收斂速度比DEPSO 算法快，可見調(diào)整聚類中心編號的方法提高了算法的優(yōu)化速度。

3.3.2 內(nèi)外部指標分析

表4給出了各算法聚類后的內(nèi)部評價指標，即評價函數(shù)F的平均值。從結(jié)果來看，結(jié)合了差分進化與粒子群優(yōu)化的DEPSO 算法在4個數(shù)據(jù)集上進行聚類后所得F值的平均值都比其他算法表現(xiàn)更好。說明在DE算法收斂停滯后再利用PSO算法進行改善，能找到更好的最優(yōu)解。添加了聚類中心排列調(diào)整的IDEPSO 算法獲得了最優(yōu)平均解。因此整體而言IDEPSO 算法在內(nèi)部指標上具有較明顯的優(yōu)化能力，特別是在大數(shù)據(jù)集中，聚類中心排列調(diào)整的操作起到良好的效果。

表4 各聚類算法在數(shù)據(jù)集上F 平均值

圖2 不同種群規(guī)模下DEPSO和IDEPSO算法的平均收斂曲線

表5和表6分別給出了各算法在數(shù)據(jù)集上聚類后外部指標ARI和FMI的平均值。所有算法的結(jié)果與IDEPSO算法的結(jié)果進行W 檢驗，可以看出IDEPSO算法在外部指標上與PSO和GQPSO算法都有統(tǒng)計學的顯著性區(qū)別，可以看出IDEPSO算法的結(jié)果更優(yōu)。IDEPSO算法在外部指標上與其他算法的結(jié)果沒有統(tǒng)計學差別。鑒于所有算法的優(yōu)化都是基于F進行的，外部指標的結(jié)果反映聚類的結(jié)果是近似的。

表5 各聚類算法在數(shù)據(jù)集上ARI 平均值

表6 各聚類算法在數(shù)據(jù)集上FMI 平均值

3.3.3 收斂速度分析

圖3 給出了各算法在數(shù)據(jù)集上適應度值F的平均收斂曲線。從圖中可以看出，PSO算法在四種數(shù)據(jù)集上的收斂曲線均十分陡峭，在短時間內(nèi)就收斂至較差的適應度值，收斂速度最快，這印證了PSO 算法在高維度的聚類問題上容易收斂早熟，陷入局部最優(yōu)解。GQPSO算法、GAI-PSO 算法的收斂速度也較快，最后取得最優(yōu)解F比 PSO 算法稍好。DE、DEPSO 和 IDEPSO 這三個算法的F收斂曲線較接近，取得的平均適應度值F也最好，這說明DE 算法其多樣性更好的優(yōu)勢適合高維度的文本聚類。但對比DEPSO算法與DE算法的收斂曲線，PSO算法在DE算法已取得的最優(yōu)解的基礎上做局部搜索，仍具有進一步的優(yōu)化空間，這在樣本數(shù)量更多、維度更高的DS4數(shù)據(jù)集上體現(xiàn)得更為明顯。

而對比IDEPSO與DEPSO算法的收斂曲線，最終收斂穩(wěn)定的最優(yōu)解F值提高之外，其收斂速度比DEPSO算法更快，即在取得較理想的最優(yōu)解的同時，所需的迭代次數(shù)和運行時間卻更少，這較好體現(xiàn)了自適應調(diào)整聚類中心排列順序的操作能提高種群的更新效率。因此對比各算法的收斂曲線圖，證明了本文提出的新型差分進化粒子群算法更好地發(fā)揮了各算法的特點，將全局優(yōu)化能力與局部優(yōu)化能力充分運用在不同時期，并通過調(diào)整種群更新過程所參與的個體間的聚類中心的排列順序，提高了算法的運行效率。

圖3 不同算法在4個測試集上F 的平均收斂曲線

圖4 給出了不同算法在數(shù)據(jù)集上測試的平均用時。可以看出DEPSO 和IDEPSO 算法的用時介于PSO和DE算法之間，GQPSO算法的用時最長，DE算法的用時最短。

圖4 不同算法在4個數(shù)據(jù)集上的平均運行時間對比

4 結(jié)束語

鑒于K-means 算法對初始聚類中心敏感但收斂速度快，PSO算法穩(wěn)定可靠但在高維度搜索空間后期容易陷入局部最優(yōu)以及DE 算法多樣性較好的特點，本文提出一種混合DE和PSO的文本聚類算法，同時提出一種自適應調(diào)整聚類中心排列順序的方法，用于改善個體的學習效率。該算法充分發(fā)揮不同算法在不同時期的優(yōu)化能力和適用性，降低了初始聚類中心的影響，提高了個體學習效率，同時避免了陷入局部最優(yōu)解。通過實驗測試分析，這種新型聚類算法IDEPSO可有效解決大規(guī)模的文本聚類問題。本文參數(shù)設置、評價函數(shù)以及聚類中心初始化方式的設計只是依據(jù)通用的方案，因此在這些方面可做進一步研究，以創(chuàng)造出更有效的解決方案。