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

1.廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣州 510006

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

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

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

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

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

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

1 背景

1.1 文本聚類相關(guān)基礎(chǔ)

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

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

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

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

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

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

1.3 差分進(jìn)化算法

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

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

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

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

若交叉操作得到的個(gè)體不差于原來(lái)的個(gè)體，則替換原個(gè)體作為新一代的個(gè)體，否則新一代的個(gè)體仍為原個(gè)體。

2 IDEPSO聚類算法

2.1 問(wèn)題定義與評(píng)價(jià)函數(shù)

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

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

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

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

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

（1）假設(shè)以xj的聚類中心排列順序?yàn)榛鶞?zhǔn)對(duì)xi進(jìn)行調(diào)整，計(jì)算xi與xj各聚類中心之間的相似度矩陣M。

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

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

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

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

下面給出調(diào)整前xi與xj各聚類中心之間的位置（圖1（a））與相似度矩陣M（表1）的例子。圖中顏色相同的聚類中心表示在同一維度?？梢钥闯鲇捎诰垲愔行呐帕械碾S機(jī)性，相近的聚類中心并沒(méi)有獲得相同的標(biāo)號(hào)，在相似度矩陣上則體現(xiàn)在每一列的最大值不在對(duì)角線上。相似度值越大體現(xiàn)兩個(gè)聚類中心位置越靠近。因此，通過(guò)調(diào)整聚類的排列，使得位置接近的聚類中心獲得相同的聚類排列號(hào)。

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)設(shè)計(jì)與數(shù)據(jù)分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3.3 收斂速度分析

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

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

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

圖4 給出了不同算法在數(shù)據(jù)集上測(cè)試的平均用時(shí)?？梢钥闯鯠EPSO 和IDEPSO 算法的用時(shí)介于PSO和DE算法之間，GQPSO算法的用時(shí)最長(zhǎng)，DE算法的用時(shí)最短。

圖4 不同算法在4個(gè)數(shù)據(jù)集上的平均運(yùn)行時(shí)間對(duì)比

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

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