基于改進(jìn)磷蝦群算法的多目標(biāo)文本聚類(lèi)方法

菊 花

(內(nèi)蒙古師范大學(xué) 教育學(xué)院，內(nèi)蒙古 呼和浩特 010020)

0 引 言

Web網(wǎng)頁(yè)由于移動(dòng)互聯(lián)網(wǎng)的廣泛流行已經(jīng)成為文本信息的主要來(lái)源，其出現(xiàn)形式如新聞網(wǎng)站、社交媒體、數(shù)字圖書(shū)館等[1]。為了管理巨量文本信息，聚類(lèi)是有效的非監(jiān)督學(xué)習(xí)方法[2]。由于同聚類(lèi)文檔具有最大相關(guān)性和內(nèi)在聯(lián)系，這一技術(shù)可以簡(jiǎn)化用戶(hù)的文本處理過(guò)程。文本聚類(lèi)還可應(yīng)用在圖像識(shí)別、文本劃分、信息檢索、搜索引擎等[3]。此時(shí)的文檔可表示為矢量空間模型VSM，用以度量文檔矢量與聚類(lèi)質(zhì)心間的相似程度[4]。K均值聚類(lèi)是求解文本聚類(lèi)的一種快速、健壯的局部搜索算法[5]，其結(jié)構(gòu)簡(jiǎn)單、收斂速度快，該算法通過(guò)初始的聚類(lèi)質(zhì)心來(lái)尋找聚類(lèi)成員，每個(gè)文檔將根據(jù)自身與質(zhì)心的相似性選擇加入的聚類(lèi)。但算法過(guò)于依賴(lài)初始質(zhì)心選擇，容易陷入局部最優(yōu)，聚類(lèi)結(jié)果不穩(wěn)定。磷蝦群算法KH是受磷蝦的捕食行為的啟發(fā)而提出的一種新型的元啟發(fā)式算法[6]。該算法控制參數(shù)少，易于實(shí)現(xiàn)，極好的全局尋優(yōu)能力使其常用于數(shù)據(jù)聚類(lèi)領(lǐng)域。

相關(guān)研究中，文獻(xiàn)[7]利用公平克隆機(jī)制提升蜂群算法的種群多樣性和全局搜索能力，再結(jié)合K均值法進(jìn)行聚類(lèi)。文獻(xiàn)[8]將差分進(jìn)化和遺傳算子嵌入K均值聚類(lèi)，提升了聚類(lèi)相似性。文獻(xiàn)[9]以梯度搜索和混沌搜索設(shè)計(jì)蜂群算法，并以此選擇聚類(lèi)中心。文獻(xiàn)[10]融合粒子群和布谷鳥(niǎo)算法的優(yōu)勢(shì)進(jìn)行文本聚類(lèi)。文獻(xiàn)[11]提出混合粒子群算法的文本聚類(lèi)算法HPSO。文獻(xiàn)[12]和文獻(xiàn)[13]分別提出混合遺傳文本聚類(lèi)算法HGA和混合和聲搜索聚類(lèi)算法HHS。

元啟發(fā)式方法求解聚類(lèi)時(shí)可能有早熟收斂問(wèn)題，該問(wèn)題與初始解有關(guān)。單純依靠元啟發(fā)方法不能保證有限時(shí)間內(nèi)得到全局最優(yōu)。若可以改進(jìn)初始解的隨機(jī)性，并利用優(yōu)化后的全局搜索能力，則可以在聚類(lèi)準(zhǔn)確性、精確性取得均衡。K均值聚類(lèi)易受初始質(zhì)心影響，聚類(lèi)不穩(wěn)定，而傳統(tǒng)磷蝦群算法KH易陷入局部最優(yōu)，全局搜索能力弱。為此，提出基于改進(jìn)磷蝦群算法的多目標(biāo)文本聚類(lèi)算法，通過(guò)磷蝦個(gè)體的誘導(dǎo)運(yùn)動(dòng)、覓食運(yùn)動(dòng)和隨機(jī)擴(kuò)散，以及融入遺傳交叉和變異的個(gè)體更新機(jī)制，增加種群多樣性，更快得到文本文檔聚類(lèi)結(jié)果。

1 模型描述

1.1 文本文檔聚類(lèi)問(wèn)題

文本文檔集合D可劃分為K個(gè)聚類(lèi)，D可表示為如式(1)的文本矢量形式

D=d1,d2,…,di,…,dn

(1)

式中：di為文檔i，n為文檔總數(shù)。文檔可表示為矢量d1=w11,w12,…,w1j,…,w1t， 其中，d1表示長(zhǎng)度為t的文檔1，wij表示文檔i中詞條j的權(quán)重，計(jì)算方法如下

wij=TFIDF(i,j)=tf(i,j)×logn/df(j)

(2)

式中：tf(i,j) 為詞條j在文檔i中的出現(xiàn)頻率，df(j) 為含有j的文檔數(shù)。

聚類(lèi)即就是將D劃分為K個(gè)聚類(lèi)，Ck為聚類(lèi)k的質(zhì)心，可表示為一個(gè)詞條權(quán)重矢量Ck=c1,c2,…,cj,…,ct，Ck表示第k個(gè)聚類(lèi)質(zhì)心，c1表示聚類(lèi)質(zhì)心k位置1上的權(quán)重值，t表示聚類(lèi)質(zhì)心的長(zhǎng)度。

算法利用余弦相似度計(jì)算每個(gè)文檔與聚類(lèi)質(zhì)心間的相似性分值，計(jì)算公式如下

(3)

歐氏距離可用于計(jì)算每個(gè)文檔與聚類(lèi)質(zhì)心間的距離，該距離則可以度量?jī)烧唛g的非相似性，計(jì)算方式如下

(4)

可以看到，歐氏距離取值在(0,1)之間，這不同于余弦相似度的度量方式。若文檔與質(zhì)心距離接近0，則表明該文檔與該質(zhì)心具有較大相似性；若距離接近于1，則表明該文檔與質(zhì)心具有不相似性。式(4)為文檔d4與C2的歐氏距離。

1.2 多目標(biāo)文本聚類(lèi)

根據(jù)式(3)和式(4)可知，余弦相似度衡量相似性，歐氏距離度量距離。本文算法聯(lián)立兩種度量方式作為目標(biāo)函數(shù)進(jìn)行聚類(lèi)決策，即盡可能選擇離質(zhì)心近且相似度高的質(zhì)心。因此，聚類(lèi)目標(biāo)函數(shù)為

multi-obj=cosine(d1,C2)×[1-dis(d1,C2)]

(5)

2 K均值聚類(lèi)算法

K均值聚類(lèi)算法目標(biāo)是通過(guò)初選的聚類(lèi)質(zhì)心，將高維度文本集合D中的文檔劃分為K個(gè)固有聚類(lèi)子集。算法通過(guò)所設(shè)定的目標(biāo)函數(shù)將每個(gè)文檔劃分至相似性最大的質(zhì)心中。該算法通過(guò)聚類(lèi)數(shù)K、初始質(zhì)心及余弦相似度進(jìn)行聚類(lèi)劃分，并通過(guò)質(zhì)心迭代更新，得到最優(yōu)聚類(lèi)解。算法以矩陣A(n×K)表示可能的聚類(lèi)解集，n代表所有文檔數(shù)量，K代表聚類(lèi)數(shù)量，每個(gè)文檔可表示為式(1)所示的詞條矢量權(quán)重，t表示唯一文本特征(詞條)數(shù)量。算法的目標(biāo)就是尋找最優(yōu)的n×K矩陣，具體過(guò)程如算法1所示。

算法1：K均值聚類(lèi)算法

(1)input:Dis a set of text documents,Kis the number of clusters

(2)output: assignDtoK

(3) termination criteria

(4) randomly chooseKdocuments as clusters centroids

(5) initialize matrixA(n*K) as zero

(6)foralldinDdo

(7) letj=argmaxk∈(1,2,…,K)based onmulti-obj(di,Ck)

(8) allocatedito the cluster numberj,A[i][j]=1

(9)endfor

(10) update the clusters centroids

3 融合遺傳算子的改進(jìn)磷蝦群算法

磷蝦君算法KH是一種新型的元啟發(fā)式算法，模擬了蝦個(gè)體的捕食行為，可用于求解全局優(yōu)化問(wèn)題。尋優(yōu)過(guò)程中，磷蝦的位置更新通過(guò)3種運(yùn)動(dòng)構(gòu)成：誘導(dǎo)運(yùn)動(dòng)、覓食運(yùn)動(dòng)和隨機(jī)擴(kuò)散。每個(gè)磷蝦的位置代表目標(biāo)函數(shù)的一個(gè)可行解，每只磷蝦通過(guò)覓食過(guò)程中位置的不斷更新來(lái)尋找最優(yōu)解。

3.1 位置更新

磷蝦個(gè)體i從迭代I至迭代I+ΔI發(fā)生的位置更新如下

xi(I+ΔI)=xi(I)+ΔIdxi/ds

(6)

式中：xi(I+ΔI) 表示磷蝦個(gè)體i的下一更新位置，xi(I)表示迭代I時(shí)磷蝦個(gè)體的位置，ΔI表示間隔常量。磷蝦個(gè)體的位置決策利用拉格朗日模型進(jìn)行表示，將其描述為

dxi/ds=Fi+Ni+Di

(7)

式中：Ni代表誘導(dǎo)運(yùn)動(dòng)分量，F(xiàn)i代表覓食運(yùn)動(dòng)分量，Di代表隨機(jī)擴(kuò)散分量。

(1)誘導(dǎo)運(yùn)動(dòng)

每個(gè)磷蝦個(gè)體的鄰居誘導(dǎo)運(yùn)動(dòng)可計(jì)算為

Ni,new=Nmaxai+wnNi,old

(8)

式中：Nmax表示最大誘導(dǎo)步長(zhǎng)，wn表示慣性權(quán)重，取值(0,1)之間，Ni,old表示磷蝦個(gè)體i的先前誘導(dǎo)運(yùn)動(dòng)，ai表示誘導(dǎo)方向，計(jì)算為

ai=ai,local+ai,target

(9)

式中：ai,local表示磷蝦個(gè)體i受鄰居的誘導(dǎo)方向，ai,target表示磷蝦個(gè)體i受當(dāng)前全局最優(yōu)個(gè)體的誘導(dǎo)方向，且

(10)

其中

(11)

K′i,j=Ki-Kj/Kworst-Kbest

(12)

其中，Kworst和Kbest分別表示特定位置上磷蝦個(gè)體的目標(biāo)函數(shù)值最差值和最優(yōu)值，Ki表示個(gè)體i的目標(biāo)函數(shù)值，Kj表示其鄰居j的目標(biāo)函數(shù)值，x表示相關(guān)個(gè)體，ε為極小正值，xi表示當(dāng)前個(gè)體位置，xj表示鄰居j位置，NN表示磷蝦個(gè)體總量，即代表總的文檔數(shù)n

ai,target=CbestK′i,bestx′i,best

(13)

Cbest=2(rand+I/Imax)

(14)

其中，Cbest表示磷蝦個(gè)體的相關(guān)系數(shù)，ai,target代表的系數(shù)有助于算法達(dá)到全局最優(yōu)解，rand是(0,1)間的隨機(jī)數(shù)，I代表KH算法的當(dāng)前迭代，Imax為最大迭代。

(2)覓食運(yùn)動(dòng)

覓食運(yùn)動(dòng)分量Fi與當(dāng)前估算的食物源位置和前一次覓食活動(dòng)及位置相關(guān)，可表示為

Fi=Vfβi+wfFi,old

(15)

βi=βi,food+βi,best

(16)

式中：βi,food表示個(gè)體受食物源誘導(dǎo)的方向，βi,best表示個(gè)體受自身歷史最優(yōu)個(gè)體誘導(dǎo)的方向。

(3)隨機(jī)擴(kuò)散

隨機(jī)擴(kuò)散分量表示磷蝦個(gè)體的隨機(jī)搜索行為，可表示為

Di=Dmax(1-I/Imax)δ

(17)

式中：Dmax表示最大的隨機(jī)擴(kuò)散速度，I表示當(dāng)前迭代數(shù)，Imax表示最大迭代數(shù)，δ表示隨機(jī)擴(kuò)散方向，取值范圍為[-1,1]。

3.2 融入遺傳算子的位置更新

由磷蝦個(gè)體的位置更新方式可知，磷蝦個(gè)體運(yùn)動(dòng)由其鄰居、種群最優(yōu)個(gè)體、食物源位置以及自身位置等多個(gè)因素共同決定，因此，傳統(tǒng)KH算法的局部開(kāi)發(fā)能力較優(yōu)，但其全局搜索能力不足，在處理多峰優(yōu)化問(wèn)題過(guò)程中可能陷入局部最優(yōu)解。此外，KH算法在每次迭代中均需要多個(gè)因素共同決策個(gè)體的運(yùn)動(dòng)，其搜索全局最優(yōu)解的速度較慢，無(wú)法快速收斂。

為解決該問(wèn)題，引入遺傳算子增強(qiáng)傳統(tǒng)KH算法的全局搜索能力。首先，通過(guò)交叉算子交換所選個(gè)體的相應(yīng)位置信息，交叉算子由交叉概率pc控制，定義pc=0.2×Ki,best。 磷蝦個(gè)體i的位置j發(fā)生交叉的更新方式為

(18)

變異算子可以通過(guò)所選個(gè)體的位置信息突變方式增加解的多樣性，以便搜索全局最優(yōu)解。變異算子由變異概率pm控制，將其定義為pm=0.05/Ki,best。 磷蝦個(gè)體i的位置j發(fā)生變異的更新方式為

由此可見(jiàn)，智能加工技術(shù)研究的內(nèi)容極其廣泛，但要真正實(shí)現(xiàn)整體加工過(guò)程的優(yōu)化控制，機(jī)床、刀具以及工件的狀態(tài)監(jiān)測(cè)是基礎(chǔ)[13-14]，需要通過(guò)監(jiān)測(cè)為過(guò)程優(yōu)化提供源信息。其中，機(jī)床的狀態(tài)監(jiān)測(cè)通常通過(guò)內(nèi)置傳感器來(lái)實(shí)現(xiàn)，而刀具和工件狀態(tài)的監(jiān)測(cè)，機(jī)器視覺(jué)技術(shù)可以發(fā)揮重要作用。

(19)

4 基于改進(jìn)磷蝦群算法的文本聚類(lèi)模型

本節(jié)描述基于改進(jìn)磷蝦群算法的文本文檔聚類(lèi)模型，目標(biāo)是尋找最優(yōu)文本聚類(lèi)，提升聚類(lèi)準(zhǔn)確度，加快算法尋優(yōu)。

4.1 磷蝦個(gè)體位置表示

利用一個(gè)代表磷蝦的解集S進(jìn)行文本文檔聚類(lèi)，每個(gè)解可表示為一個(gè)長(zhǎng)度為n的矢量，n代表所有文檔數(shù)量，每個(gè)文檔則代有KH算法中一個(gè)磷蝦的行為。每個(gè)決策變量(即磷蝦個(gè)體)屬于一個(gè)聚類(lèi)質(zhì)心 [1,2,…,K]， 每個(gè)解由K個(gè)質(zhì)心集合構(gòu)成，單個(gè)質(zhì)心Ck=c1,c2,…,cj,…,ct，Ck表示第k個(gè)聚類(lèi)質(zhì)心。圖1是解的一種表示方式，該解表明8個(gè)文檔被劃分為3個(gè)聚類(lèi)，文檔d1屬于聚類(lèi)c3，文檔d5屬于聚類(lèi)c2，而聚類(lèi)c3包含文檔d1、d2和d7這3個(gè)文檔。

圖1 解的表示方法

4.2 磷蝦群記憶庫(kù)KHM

KHM通過(guò)區(qū)間 [1,…,K] 內(nèi)搜索空間的隨機(jī)值進(jìn)行初始化。KHM的每個(gè)矢量代表一個(gè)可行解，對(duì)應(yīng)聚類(lèi)質(zhì)心K中的一個(gè)序號(hào)。KHM大小S×n由可行解數(shù)量和文檔數(shù)量決定。將KHM定義為

(20)

4.3 聚類(lèi)質(zhì)心更新

質(zhì)心更新是文本聚類(lèi)的主要步驟，決定了文檔所屬聚類(lèi)。聚類(lèi)質(zhì)心Ck的計(jì)算方式為

(21)

式中：nk為聚類(lèi)k的文檔量，Ck為聚類(lèi)k的質(zhì)心。式(21)表明：聚類(lèi)內(nèi)所有文檔的矢量權(quán)重和與文檔數(shù)量之比為聚類(lèi)質(zhì)心。

4.4 適應(yīng)度函數(shù)

定義平均相似文檔質(zhì)心ASDC為適應(yīng)度函數(shù)，該函數(shù)可考慮為一個(gè)外部度量方式，其值則是根據(jù)內(nèi)部度量(余弦相似度和歐氏距離)計(jì)算。結(jié)合式(5)定義的聚類(lèi)目標(biāo)函數(shù)，適應(yīng)度函數(shù)利用目標(biāo)函數(shù)在K個(gè)聚類(lèi)上的均值結(jié)果進(jìn)行定義

(22)

式中：ni表示聚類(lèi)i中的所有文檔數(shù)量，multi-obj(Ci,dij) 表示文檔j與質(zhì)心i間的相似度，dij表示聚類(lèi)i中的文檔j。

4.5 基于改進(jìn)磷蝦群算法的文本聚類(lèi)算法MHKHA

圖2是融合K均值的混合多目標(biāo)改進(jìn)磷蝦群算法的文本聚類(lèi)算法MHKHA的執(zhí)行流程。算法以多目標(biāo)K均值聚類(lèi)結(jié)果作為改進(jìn)磷蝦群算法的初始種群，即初始聚類(lèi)解，填充至磷蝦群記憶庫(kù)KHM中。同時(shí)多目標(biāo)K均值聚類(lèi)以式(5)融合余弦相似度和歐氏距離的目標(biāo)進(jìn)行度量。在對(duì)磷蝦群相關(guān)參數(shù)配置后，進(jìn)行迭代終止判斷，若未滿(mǎn)足終止條件，則進(jìn)行磷蝦個(gè)體運(yùn)動(dòng)計(jì)算，包括誘導(dǎo)運(yùn)動(dòng)、覓食運(yùn)動(dòng)和隨機(jī)擴(kuò)散，從而進(jìn)行磷蝦群位置更新。再引入遺傳交叉和變異機(jī)制，提升種群多樣性，再以最優(yōu)個(gè)體替換最差個(gè)體，完成一次文本聚類(lèi)迭代過(guò)程。算法2是MHKHA的完整偽代碼。

圖2 MHKHA算法的執(zhí)行流程

算法2： MHKHA算法偽代碼

(1) initialization ofK-mean parametersK,KImax//初始化K均值聚類(lèi)參數(shù)

(2) initialization of KH parameters:Imax,S//初始化磷蝦群參數(shù)

(3)forl=1 toSdo//在KHM上遍歷

(4) randomly selectKdocuments as the initial cluster centroid//隨機(jī)選擇聚類(lèi)質(zhì)心

(5)forKI=1 toKImaxdo//K均值聚類(lèi)迭代

(6) initialize matrixAas zero//初始聚類(lèi)矩陣初始化

(7)forj=1 tondo//遍歷文檔集合

(8)j=argmaxk∈(1,2,…,K)on basis ofmulti-obj(dj,Ck)//根據(jù)目標(biāo)函數(shù)尋找聚類(lèi)質(zhì)心

(9) assigndito clusterj,i.e.A[i][j]=1//分配文檔至聚類(lèi)， 更新矩陣元素

(10) update the clusters centroids//更新聚類(lèi)質(zhì)心

(11)endfor

(12)endfor

(13) convert matrixAas a matrix of solutions KHM//將K均值聚類(lèi)解A轉(zhuǎn)換為KHM

(14)S(l)=A, note that eachK-means generation is one solution for KH memory//K均值每一次迭代的聚類(lèi)解作為KHM的一種可行解

(15)endfor

(16) initialization of KHM usingS,which is theK-means results//初始化KHM

(17)fori=1 toSdo//遍歷所有可行解

(18)forj=1 tondo//遍歷所有文檔

(19) computing the clusters centroids//計(jì)算聚類(lèi)質(zhì)心

(20) compute fitness function of each krill by usingASDC//根據(jù)ASDC計(jì)算磷蝦個(gè)體適應(yīng)度

(21)endfor

(22)endfor

(23) sort the krills and findxbest,where best from [1,2,…,S]//對(duì)所有可行解進(jìn)行排序， 尋找最優(yōu)解

(24)whileI=Imaxdo//改進(jìn)磷蝦群算法迭代

(25)fori=1 toSdo

(26) perform the three motion calculations//磷蝦3種運(yùn)動(dòng)模式

(27)xi(I+dI)=xi(I)+ΔI(dxi/ds)//個(gè)體位置更新

(28) compute the clusters centroids//計(jì)算聚類(lèi)質(zhì)心

(29) evaluate each krill usingASDC//根據(jù)ASDC評(píng)估磷蝦個(gè)體

(30)endfor

(31)fori=1 toSdo

(32) apply KH operators to KHM//更新KHM

(33) genetic crossover//遺傳交叉

(34) genetic mutation//遺傳變異

(35)endfor

(36) replace the worst krill with the best krill//個(gè)體替換

(37) sort the krills and findxbest//重新排序磷蝦群， 尋找最優(yōu)個(gè)體

(38)I=I+1//迭代更新

(39)endwhile

(40)returnxbest//迭代完成后， 返回最優(yōu)解

5 實(shí)驗(yàn)分析

5.1 評(píng)估指標(biāo)

本節(jié)對(duì)所提出的算法進(jìn)行仿真對(duì)比分析，實(shí)驗(yàn)利用Matlab進(jìn)行。文本聚類(lèi)領(lǐng)域內(nèi)聚類(lèi)質(zhì)量的評(píng)估指標(biāo)主要有準(zhǔn)確率、精確度、召回率和F度量值，以上指標(biāo)可用于評(píng)估文檔聚類(lèi)和度量每個(gè)聚類(lèi)中實(shí)際分割與文檔分類(lèi)標(biāo)簽的一致性。

精確度：精確度表示所有實(shí)際相關(guān)文檔與所有聚類(lèi)中文檔總量的比值，該比值可以根據(jù)實(shí)際給定的分類(lèi)標(biāo)簽針對(duì)每個(gè)聚類(lèi)進(jìn)行計(jì)算，計(jì)算方式為

P(i,j)=nij/nj

(23)

式中：P(i,j) 表示聚類(lèi)j中分類(lèi)i的精確度，nij表示聚類(lèi)j中分類(lèi)i的實(shí)際成員數(shù)量，nj為聚類(lèi)j中的所有成員數(shù)量。

召回率：召回率表示實(shí)際相關(guān)文檔與所有聚類(lèi)文檔的比值，計(jì)算方式為

R(i,j)=nij/ni

(24)

式中：R(i,j) 為聚類(lèi)j中分類(lèi)i的召回率，ni為分類(lèi)i的實(shí)際成員量。

F度量：F度量根據(jù)聚類(lèi)精確度和召回率計(jì)算，期望最佳的文本聚類(lèi)結(jié)果，其F度量值將越接近于1，聚類(lèi)j中分類(lèi)i的F度量計(jì)算方式為

(25)

所有聚類(lèi)的F度量計(jì)算方式為

(26)

式中：n表示集合D中的文檔總量。

準(zhǔn)確率：聚類(lèi)準(zhǔn)確率用于計(jì)算實(shí)際劃分至每個(gè)聚類(lèi)中的文本文檔的比例，計(jì)算方式為

(27)

式中：K表示文本總聚類(lèi)數(shù)。

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

利用9個(gè)擁有不同特征的文本數(shù)據(jù)集測(cè)試聚類(lèi)算法的可行性，這些文本聚類(lèi)基準(zhǔn)數(shù)據(jù)集可從網(wǎng)站http://sites.labic.icmc.usp.br/text_collections/下載，并通過(guò)詞條提取表征為數(shù)值形式進(jìn)行實(shí)驗(yàn)。表1給出了數(shù)據(jù)集的詳細(xì)屬性。數(shù)據(jù)集DS1來(lái)源于CSTR，包括4個(gè)分類(lèi)的關(guān)于技術(shù)報(bào)告的299個(gè)文檔。數(shù)據(jù)集DS2來(lái)源于SyskrillWebert，包括4個(gè)分類(lèi)的關(guān)于Web網(wǎng)頁(yè)的333個(gè)文檔。數(shù)據(jù)集DS3來(lái)源于Trace，包括6個(gè)分類(lèi)的關(guān)于tr32的204個(gè)文檔。數(shù)據(jù)集DS4來(lái)源于Trace，包括9個(gè)分類(lèi)的關(guān)于tr32的313個(gè)文檔。數(shù)據(jù)集DS5 Trace，包括9個(gè)分類(lèi)的關(guān)于tr11的414個(gè)文檔。數(shù)據(jù)集DS6來(lái)源于Trace，包括10個(gè)分類(lèi)的關(guān)于tr41的878個(gè)文檔。數(shù)據(jù)集DS7來(lái)源于OHSUMED，包括10個(gè)分類(lèi)的關(guān)于MIDLINE的913個(gè)文檔。數(shù)據(jù)集DS8來(lái)源于classic4，包括4個(gè)分類(lèi)的關(guān)于MIDLINE的2000個(gè)文檔，4個(gè)分類(lèi)分別為CACM、CRAN、CISI、MED，每個(gè)分類(lèi)500個(gè)文檔。數(shù)據(jù)集DS9來(lái)源于20 NEWSGRUP，包括20個(gè)分類(lèi)的關(guān)于新聞的18 828個(gè)文檔。

表1 數(shù)據(jù)集

與本文設(shè)計(jì)的相關(guān)KH算法一共有6種，表2是不同KH算法版本的詳細(xì)說(shuō)明。KHA1和KHA2是利用基本KH算法進(jìn)行文本聚類(lèi)，不使用K均值結(jié)果作為初始解，區(qū)別在于是否融入遺傳交叉和變異。HKHA1、HKHA2和HKHA3均是融入K均值的混合KH算法，但僅僅是以余弦相似度單目標(biāo)進(jìn)行聚類(lèi)衡量，同時(shí)區(qū)別在于是融入遺傳交叉和變異。MHKHA則是融入K均值的混合多目標(biāo)算法，以K均值聚類(lèi)作為初始解，以余弦相似度和歐氏距離進(jìn)行多目標(biāo)聚類(lèi)優(yōu)化，再融入遺傳交叉和變異。不同版本的KH算法還將與3種混合文本聚類(lèi)算法進(jìn)行比較，分別選取混合和聲搜索文本聚類(lèi)算法HHS[13]、混合遺傳文本聚類(lèi)算法HGA[12]和混合粒子群優(yōu)化文本聚類(lèi)算法HPSO[11]進(jìn)行性能對(duì)比。實(shí)驗(yàn)結(jié)果均是20次實(shí)驗(yàn)結(jié)果的均值，聚類(lèi)過(guò)程中設(shè)置1000次最大迭代，可以使算法進(jìn)行充分的全局最優(yōu)搜索，K均值聚類(lèi)過(guò)程設(shè)置100次最大迭代，可以使其收斂在局部搜索最優(yōu)解上。

表2 不同版本的KH算法

5.3 改進(jìn)磷蝦群算法的參數(shù)確定

該部分實(shí)驗(yàn)用于確定MHKHA算法中相關(guān)參數(shù)最優(yōu)值。表3是20個(gè)收斂實(shí)驗(yàn)場(chǎng)景的詳細(xì)參數(shù)配置。實(shí)驗(yàn)主要研究4個(gè)參數(shù)的取值問(wèn)題，包括KHM大小S、最大覓食速度Vf、最大隨機(jī)擴(kuò)散速度Dmax和最大誘導(dǎo)步長(zhǎng)Nmax。所有實(shí)驗(yàn)場(chǎng)景最大迭代數(shù)Imax=1000，在所有9個(gè)數(shù)據(jù)集上對(duì)每個(gè)收斂實(shí)驗(yàn)場(chǎng)景進(jìn)行實(shí)驗(yàn)分析，以確定4個(gè)參數(shù)最優(yōu)值。表3將收斂場(chǎng)景劃分為4組，每一組確定3個(gè)參數(shù)不同，改變一個(gè)參數(shù)來(lái)確定最優(yōu)值。如：對(duì)于場(chǎng)景6～場(chǎng)景10，S、Dmax和Nmax是固定相同取值，Vf改變?nèi)≈怠５谝唤M場(chǎng)景以5個(gè)不同取值S=1020304050檢測(cè)磷蝦群記憶庫(kù)KHM大小(存儲(chǔ)初始解)的最優(yōu)值，第二組場(chǎng)景以5個(gè)不同最大覓食速度Vf=0.005/0.010/0.030/0.040/0.070檢測(cè)Vf最優(yōu)值。剩余3組場(chǎng)景依此類(lèi)推。最后一列數(shù)據(jù)是在相應(yīng)場(chǎng)景下得到的最優(yōu)值組數(shù)，最后一行則是相應(yīng)參數(shù)最優(yōu)取值。4個(gè)參數(shù)的組合取值是參考有關(guān)磷蝦群算法研究文獻(xiàn)所作的取值。

場(chǎng)景1～場(chǎng)景5用于決定KHM大小的最優(yōu)值，第2組場(chǎng)景在所有數(shù)據(jù)集中的36個(gè)評(píng)估指標(biāo)中得到了24個(gè)最優(yōu)值，因此，選定S=20，后續(xù)實(shí)驗(yàn)也以該值進(jìn)行實(shí)驗(yàn)分析。場(chǎng)景6～場(chǎng)景10用于決定最大覓食速度Vf的最優(yōu)值，第8組場(chǎng)景在所有數(shù)據(jù)集的36個(gè)評(píng)估指標(biāo)中得到了19個(gè)最優(yōu)

表3 磷蝦群算法的執(zhí)行場(chǎng)景和最佳參數(shù)取值

值，因此，選定Vf=0.030，后續(xù)實(shí)驗(yàn)也以該值進(jìn)行實(shí)驗(yàn)分析。場(chǎng)景11～場(chǎng)景15用于決定最大隨機(jī)擴(kuò)散速度Dmax的最優(yōu)值，第14組場(chǎng)景在所有數(shù)據(jù)集的36個(gè)評(píng)估指標(biāo)中得到了25個(gè)最優(yōu)值，因此，選定Dmax=0.008，后續(xù)實(shí)驗(yàn)也以該值進(jìn)行實(shí)驗(yàn)分析。場(chǎng)景16～場(chǎng)景20用于決定最大誘導(dǎo)步長(zhǎng)Nmax的最優(yōu)值，第20組場(chǎng)景在所有數(shù)據(jù)集的36個(gè)評(píng)估指標(biāo)中得到了27個(gè)最優(yōu)值，因此，選定Nmax=0.100，后續(xù)實(shí)驗(yàn)也以該值進(jìn)行實(shí)驗(yàn)分析。

5.4 算法對(duì)比結(jié)果分析

表4給出在9個(gè)基準(zhǔn)數(shù)據(jù)集上測(cè)試的4個(gè)評(píng)估指標(biāo)結(jié)果，共測(cè)試10種算法。最優(yōu)結(jié)果以粗體表示。準(zhǔn)確率方面，MHKHA在9個(gè)數(shù)據(jù)集中的7個(gè)數(shù)據(jù)集得到了最優(yōu)結(jié)果；精確度方面，MHKHA在9個(gè)數(shù)據(jù)集測(cè)試中的8個(gè)數(shù)據(jù)集得到了最優(yōu)結(jié)果；在召回率和F度量指標(biāo)上，MHKHA在所有數(shù)據(jù)集上均得到了最優(yōu)結(jié)果。綜合所有指標(biāo)可知，MHKHA獲得了最多的最優(yōu)值，可見(jiàn)，融入遺傳算子的混合多目標(biāo)磷蝦群算法MHKHA可以有效提升文本聚類(lèi)效果。

表4 聚類(lèi)性能對(duì)比結(jié)果

5.5 統(tǒng)計(jì)分析

本節(jié)根據(jù)F度量值執(zhí)行弗里德曼氏測(cè)試評(píng)估算法性能，結(jié)果見(jiàn)表5，給出的是算法在不同數(shù)據(jù)集中的測(cè)試排序。本文的MHKHA算法在所有數(shù)據(jù)集中改進(jìn)文本文檔聚類(lèi)的排序最高，緊接著是HKHA1、HKHA3、HKHA2、HPSO、HHS、HGA、KHA2、HKA1和K-mean++算法。MHKHA算法利用多目標(biāo)優(yōu)化的K均值聚類(lèi)結(jié)果作為算法的初始解，可以有效增強(qiáng)KH算法的局部開(kāi)發(fā)能力；而融入遺傳算法后的KH算法又可以提升算法的全局搜索能力，最終得到最佳的聚類(lèi)效果。

進(jìn)一步對(duì)算法進(jìn)行t測(cè)試，測(cè)試結(jié)果見(jiàn)表6、表7，利用α<0.05的t測(cè)試評(píng)估性能。表6總結(jié)了KHA1和HKHA1

表5 基于F度量的弗里德曼氏測(cè)試分析

表6 KHA1和HKHA1在α<0.05時(shí)的t測(cè)試結(jié)果

表7 HKHA1和MHKHA在α<0.05時(shí)的t測(cè)試結(jié)果

的t測(cè)試結(jié)果，可以看到，9個(gè)數(shù)據(jù)集中有7個(gè)改進(jìn)較多，結(jié)果很可觀。同時(shí)，HKHA1的t測(cè)試結(jié)果要優(yōu)于HKA1，可見(jiàn)，改善磷蝦群的初始種群結(jié)構(gòu)是行之有效的。表7總結(jié)了HKHA1和MHKHA的t測(cè)試結(jié)果，可以看到，9個(gè)數(shù)據(jù)集中有6個(gè)改進(jìn)較多，同時(shí)，MHKHA的t測(cè)試結(jié)果要優(yōu)于HKHA1，可見(jiàn)，融入多目標(biāo)和遺傳算子在磷蝦群算法中可以有效增強(qiáng)個(gè)體尋優(yōu)能力，在避免局部最優(yōu)的同時(shí)，快速收斂至全局最優(yōu)解處。

5.6 收斂分析

本節(jié)觀察幾種文本聚類(lèi)算法的收斂行為，收斂速度可以反映算法尋找最優(yōu)解(準(zhǔn)確聚類(lèi))的速度。圖3是算法的收斂行為表現(xiàn)。可以看到，MHKHA算法隨著迭代的進(jìn)行，基本上到后期在所有數(shù)據(jù)集測(cè)試下均可以得到最大的適應(yīng)度均值，說(shuō)明算法可以有效避免陷入局部最優(yōu)，獲得全局最優(yōu)解，這與其它幾種混合KH算法(HKHA1、HKHA2、HKHA3)不同，說(shuō)明MHKHA算法所采用的混合多目標(biāo)機(jī)制和遺傳算子對(duì)于有效提升聚類(lèi)效率，以及個(gè)體尋優(yōu)方面是有效可行的。此外，HKHA2和HKHA3的收斂性?xún)?yōu)于HKHA1、HGA、HHS和HPSO，說(shuō)明在融入K均值作為種群初始結(jié)構(gòu)后，對(duì)磷蝦群個(gè)體更新融入遺傳算子的思路是有效可行的，可以有效增加種群多樣性，增加獲得全局最優(yōu)的概率。

圖3 算法收斂狀況

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

為了提高文本聚類(lèi)的準(zhǔn)確率，提升聚類(lèi)效率，提出一種融合改進(jìn)磷蝦群算法與K均值的文本聚類(lèi)算法。算法結(jié)合K均值聚類(lèi)的局部快速尋優(yōu)能力和改進(jìn)磷蝦群算法的全局搜索能力，以K均值聚類(lèi)解作為磷蝦群算法的初始種群，引入遺傳交叉和變異算子改善磷蝦個(gè)體多樣性，提升全局搜索能力；通過(guò)磷蝦種群的誘導(dǎo)運(yùn)動(dòng)、覓食運(yùn)動(dòng)和隨機(jī)擴(kuò)散機(jī)制作個(gè)體位置更新，引入余弦相似度和歐氏距離的多目標(biāo)結(jié)構(gòu)適應(yīng)度函數(shù)評(píng)估磷蝦位置優(yōu)劣，搜索全局最優(yōu)解。結(jié)果表明，該算法在聚類(lèi)指標(biāo)上表現(xiàn)更優(yōu)。