融合化學(xué)反應(yīng)優(yōu)化與K均值的文本數(shù)據(jù)聚類

王 琛，董永權(quán)

(1.江蘇建筑職業(yè)技術(shù)學(xué)院 信電工程學(xué)院，江蘇 徐州 221116； 2.江蘇師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221116)

0 引 言

作為一種非監(jiān)督學(xué)習(xí)技術(shù)，文本聚類[1]的目的是根據(jù)距離或相似性將文本文檔集合劃分為若干聚類，使得相同聚類內(nèi)的文檔具有最相近的文本特征，而不同聚類內(nèi)的文檔體現(xiàn)不同特征，它可以簡化文本處理過程，將具有固有特征的文檔聚類成集[2]。在沒有文檔分類標(biāo)簽的先驗(yàn)知識前提下，文本聚類需要管理非標(biāo)簽的文本文檔集合。

K均值算法是一種最為簡單快速的文本聚類算法[3]，算法試圖為每個(gè)文檔尋找距離最短或相似性最高的質(zhì)心，并通過質(zhì)心的不斷更新得到穩(wěn)定聚類。但是，該算法過多依賴于初始質(zhì)心選取，是一種局部最優(yōu)搜索算法。為了進(jìn)一步得到準(zhǔn)確度更高的文本聚類結(jié)果，提出了一種融合化學(xué)反應(yīng)算法與K均值算法的文本聚類算法，結(jié)合K均值算法的局部快速開發(fā)尋優(yōu)能力和化學(xué)反應(yīng)算法的全局勘探能力，以K均值得到的聚類解集合作為化學(xué)反應(yīng)算法的初始分子結(jié)構(gòu)群，通過4種化學(xué)反應(yīng)操作，增加種群分子結(jié)構(gòu)的多樣性，在擴(kuò)展搜索空間的基礎(chǔ)上得到最優(yōu)文本聚類。

1 相關(guān)研究

相關(guān)研究中，文獻(xiàn)[4]針對傳統(tǒng)K均值聚類在初始質(zhì)心選取上的隨機(jī)性，為樣本點(diǎn)引入局部密度指標(biāo)，并根據(jù)局部密度分布，選擇密度峰值點(diǎn)作為初始質(zhì)心，得到了更高聚類準(zhǔn)確度。文獻(xiàn)[5]針對特征詞稀疏性，提出結(jié)合語義的K均值聚類算法。算法以詞集表示短文本，解決了短文本特征詞的稀疏問題，還克服了對初始質(zhì)心的敏感性。文獻(xiàn)[6]提出增強(qiáng)蜂群優(yōu)化與K均值的文本聚類算法。首先引入克隆操作提高全局搜索能力，提高樣本多樣性并增強(qiáng)蜂群搜索能力；再通過克隆操作增強(qiáng)世代間的信息交流，提高聚類質(zhì)量。元啟發(fā)式算法也常用于數(shù)據(jù)聚類分析。文獻(xiàn)[7]利用遺傳算法和差分進(jìn)化對K均值聚類做了改進(jìn)。文獻(xiàn)[8]利用智能蜂群算法選擇聚類中心并創(chuàng)建文檔聚類，建立了梯度搜索和混沌搜索兩種局部搜索增強(qiáng)蜂群開發(fā)能力，在收斂速度和聚類質(zhì)量上具備優(yōu)勢。文獻(xiàn)[9]結(jié)合粒子群和布谷鳥算法進(jìn)行聚類分析，將粒子群生成的聚類解作為布谷鳥算法的輸入，融合兩者優(yōu)勢，在F度量指標(biāo)上有著優(yōu)異表現(xiàn)。文獻(xiàn)[10]提出基于粒子群算法的文本聚類算法，文獻(xiàn)[11]提出基于遺傳算法的文本聚類算法。元啟發(fā)式算法在解決聚類問題時(shí)可能面臨早熟或收斂過快問題，這會降低種群全局搜索能力。早熟收斂問題一般與初始解的質(zhì)量相關(guān)，若初始解質(zhì)量較優(yōu)，元啟發(fā)式算法的全局尋優(yōu)也較易實(shí)現(xiàn)。因此，純粹的元啟發(fā)式求解方式并不一定能夠在有限時(shí)間內(nèi)得到全局最優(yōu)解。若可以改進(jìn)初始解集的隨機(jī)選擇特征，在此基礎(chǔ)上利用更高效的全局搜索能力，定會在聚類解的求解速度、準(zhǔn)確性、精確性等指標(biāo)上取得均衡的優(yōu)化效果。基于此考慮，結(jié)合K均值算法的局部快速開發(fā)尋優(yōu)能力和化學(xué)反應(yīng)算法的全局勘探能力，以K均值得到的聚類解集合作為化學(xué)反應(yīng)算法的初始分子結(jié)構(gòu)群，通過4種簡單的化學(xué)反應(yīng)操作，增加種群分子結(jié)構(gòu)的多樣性，更快速得到不同特征的文本文檔聚類結(jié)果。

2 模 型

2.1 文本聚類模型

文本聚類即是將一個(gè)文本文檔集合D劃分為K個(gè)聚類，D表示文本文檔集合D=d1,d2,…,di,…,dn，di表示集合D中的文檔i，n表示集合D中所有文本文檔數(shù)量。每個(gè)文檔i可表示為矢量di=wi,1,wi,2,…,wi,j,…,wi,t，di即為集合D中的第i個(gè)文檔，文檔長度為t(詞條數(shù)量)，wi,j表示文檔i中詞條j的權(quán)重值，利用詞頻逆文本頻率指數(shù)TF-IDF計(jì)算為

(1)

其中，TF(i,j) 為文檔i中詞條j的頻率，n為集合D內(nèi)的文檔數(shù)量，DF(j) 為包括詞條j的文檔數(shù)量，IDF(i,j) 則為文檔頻率倒數(shù)。

利用矢量空間模型VSM[12]，文檔集合D可表示為

(2)

文本聚類算法的目標(biāo)是將文本文檔劃分為K個(gè)聚類，每個(gè)聚類擁有一個(gè)質(zhì)心，表示為C=C1,C2,…,CK， 質(zhì)心Ck可表示為詞條權(quán)重矢量，即Ck=c1,c2,…,ct，c1為質(zhì)心Ck的位置1上的取值，t為聚類質(zhì)心長度。文本聚類算法應(yīng)當(dāng)先計(jì)算各個(gè)文檔與各個(gè)聚類質(zhì)心的距離，并將文檔劃分至距離最小的聚類質(zhì)心。

2.2 聚類質(zhì)量度量方式

文本文檔聚類的目的是將相似文檔劃分至同一聚類中，不相似文檔則劃分在不同聚類中。余弦相似度是度量一個(gè)文檔與聚類質(zhì)心相似度的一種標(biāo)準(zhǔn)度量方式，可計(jì)算為

(3)

上式表示文檔di與聚類質(zhì)心Ck的余弦相似度。wi,j表示文檔i中詞條j的權(quán)重值，wk,j表示聚類質(zhì)心Ck所代表的文檔k中詞條j的權(quán)重值?？梢钥闯觯粑臋ndi與聚類質(zhì)心Ck具有相似性，則余弦值接近于1；若文檔di與聚類質(zhì)心Ck不具有相似性，則余弦值接近于0。

歐氏距離是計(jì)算歐氏空間內(nèi)文檔與聚類質(zhì)心的距離(相似性)的另一種計(jì)算方法。文檔di與聚類質(zhì)心Ck的歐氏距離計(jì)算為

(4)

可以看到，歐氏距離取值空間在0至1之間。若文檔與聚類質(zhì)心間的歐氏距離接近于0，則表明該文檔與該聚類質(zhì)心具有較大相似性，可劃分至相應(yīng)聚類中；若文檔與聚類質(zhì)心間的歐氏距離接近于1，則表明該文檔與該聚類質(zhì)心相距較遠(yuǎn)。

聚類質(zhì)心Ck的計(jì)算方式為

(5)

其中，di表示文檔i，nk表示聚類k中文檔的數(shù)量，Ck為聚類k的質(zhì)心，di∈Ck表明屬于聚類k的所有文檔。該式表明聚類內(nèi)所有文檔的矢量權(quán)重之和除以聚類內(nèi)的文檔數(shù)量即為該聚類的質(zhì)心。

2.3 聚類目標(biāo)函數(shù)

由于余弦相似度可以度量文檔與質(zhì)心間的相似性，歐氏距離可以度量文檔與質(zhì)心間的距離，本文將相似性和距離均考慮在聚類標(biāo)準(zhǔn)的目標(biāo)函數(shù)中。在為文檔選擇相應(yīng)聚類質(zhì)心時(shí)，應(yīng)該盡可能選擇相似度高且距離最近的聚類質(zhì)心，因此，聚類目標(biāo)函數(shù)可設(shè)置為同步優(yōu)化的雙目標(biāo)形式

obj(di,Ck)=Cos(di,Ck)+(1-Dis(di,Ck))

(6)

其中，Cos(di,Ck) 表示式(3)計(jì)算的余弦相似度，Dis(di,Ck) 表示式(4)計(jì)算的歐氏距離。由公式可知，聚類時(shí)目標(biāo)函數(shù)應(yīng)該最大化，即余弦相似度越大，歐氏距離越小，目標(biāo)函數(shù)值越大。

2.4 K均值文本聚類

K均值聚類是數(shù)據(jù)聚類領(lǐng)域最簡單有效的聚類算法，該算法可以通過聚類數(shù)K、初始聚類質(zhì)心以及余弦相似度將文檔劃分至相似質(zhì)心內(nèi)，并通過若干次的質(zhì)心迭代更新，直到滿足終止條件，得到最終的聚類解。算法僅利用式(3)計(jì)算文檔與質(zhì)心間的相似度，并以一個(gè)矩陣A[K][n] 代表最終的文檔聚類解，其中，K表示聚類數(shù)量，n表示文檔集合中的文檔數(shù)量，矩陣元素A[k][i] 定義為

(7)

上式表明，若文檔di劃分至質(zhì)心Ck，則元素A[k][i]=1； 否則，A[k][i]=0。K均值文本聚類的目標(biāo)即是尋找最優(yōu)的矩陣A[K][n]。 算法執(zhí)行過程如下：

算法1：K均值文本聚類過程

(1)輸入： 文本文檔集合D和聚類數(shù)量K

(2)輸出： 以矩陣A[K][n]定義的聚類解

(3)randomly selectKdocuments as clusters centroidC=(C1,C2,…,CK)//隨機(jī)選擇K個(gè)文檔作為初始聚類質(zhì)心

(4)initialize all elements as zeros in matrixA[K][n]//初始化聚類解矩陣

(5)foreach documentdiinDdo

(6)k=argmaxk∈{1 to K}based onCos(di,Ck)//尋找余弦相似度最大的目標(biāo)聚類質(zhì)心

(7) allocatedito the clusterCkandA[k][i]=1//分配文檔至聚類并更新矩陣元素

(8)endfor

(9)update the clusters centroid using Eq.(5)//更新聚類質(zhì)心

(10)iftermination condition is not satisfied, return step 4; otherwise, return clustering solution and end

由于K均值算法在聚類過程中受初始質(zhì)心選取的影響較大，所以較易于收斂在局部最優(yōu)解上，尤其在文檔特征相差較大時(shí)，無法找到接近最優(yōu)的聚類解。因此，為了避免早熟，在已有K均值聚類較強(qiáng)的局部開發(fā)能力基礎(chǔ)上，還需要進(jìn)一步加強(qiáng)全局勘探過程。

3 融合化學(xué)反應(yīng)優(yōu)化和K均值的文本聚類

在若干次迭代的K均值文本聚類的結(jié)果上，本文進(jìn)一步引入化學(xué)反應(yīng)優(yōu)化算法對文本聚類結(jié)果進(jìn)行優(yōu)化，尋找文本聚類結(jié)果的全局最優(yōu)解?；瘜W(xué)反應(yīng)優(yōu)化算法CRO模擬實(shí)現(xiàn)了封閉容器中分子所發(fā)生的一系列化學(xué)反應(yīng)及相互作用的過程，通過不斷迭代尋找分子結(jié)構(gòu)的穩(wěn)定狀態(tài)[13]。每一次化學(xué)反應(yīng)均會使環(huán)境中生成新的分子結(jié)構(gòu)，且每一個(gè)分子擁有唯一的結(jié)構(gòu)。

3.1 化學(xué)分子結(jié)構(gòu)的聚類解編碼及解碼

將一個(gè)分子結(jié)構(gòu)編碼為一種可能的文本聚類解，每個(gè)分子由兩個(gè)原子集構(gòu)成，一個(gè)原子集代表分子的元素位置，表示文檔序列，另一個(gè)原子集代表元素取值，表示對應(yīng)文檔所屬的聚類質(zhì)心。兩個(gè)原子集均可表示為長度為n的矢量，n為文檔總數(shù)。若文檔劃分為K個(gè)聚類，則元素取值代表的聚類質(zhì)心原子的變量范圍為 [1,2,…,K]。 圖1所示為一種可能的分子結(jié)構(gòu)，該分子結(jié)構(gòu)表明總共有8個(gè)文檔劃分為3個(gè)文本聚類，即n=8，K=3。具體的分子結(jié)構(gòu)解碼信息為：聚類C2擁有3個(gè)文檔，文檔d1、d3和d6劃分至聚類C2中；聚類C1擁有3個(gè)文檔，文檔d2、d5和d8劃分至聚類C1中；聚類C3擁有兩個(gè)文檔，文檔d3和d7劃分至聚類C3中。

圖1 化學(xué)分子結(jié)構(gòu)編碼

3.2 新聚類解的生成

化學(xué)反應(yīng)優(yōu)化算法CRO中，分子一共會經(jīng)歷4種化學(xué)反應(yīng)操作：單分子碰撞、單分子分解、分子間碰撞和分子間合成。單分子碰撞與分子間碰撞對原分子結(jié)構(gòu)的影響較小，主要用于在鄰域空間內(nèi)搜索局部更優(yōu)解，屬于局部開發(fā)過程；單分子分解和分子間合成對原分子結(jié)構(gòu)的影響較大，可以較大改變原分子結(jié)構(gòu)，主要用于開辟更大的搜索空間，屬于全局勘探過程。

(1)單分子碰撞

單分子碰撞是單個(gè)分子的化學(xué)反應(yīng)行為，即：一個(gè)原分子Φ與封閉容器內(nèi)壁會發(fā)生碰撞，生成一個(gè)新的分子結(jié)構(gòu)Φ’，兩個(gè)分子在原子結(jié)構(gòu)上擁有不同的特征。具體碰撞實(shí)施過程如下：首先，從表示元素位置的原子中隨機(jī)選擇一個(gè)位置，即隨機(jī)選擇一個(gè)文檔；然后，將其對應(yīng)的元素取值在[1,K]間做隨機(jī)改變，生成一個(gè)新的分子結(jié)構(gòu)，即：單分子碰撞會隨機(jī)改變一個(gè)文檔所屬聚類。如圖2所示的單分子碰撞示例中，隨機(jī)選擇的文檔為x=d3，原本屬于文本聚類C2，經(jīng)過碰撞后，d3劃分至聚類C1中，其它分子結(jié)構(gòu)保持不變，即其它文檔所屬聚類不變。得到新分子結(jié)構(gòu)后，算法解碼出分子結(jié)構(gòu)對應(yīng)的文本聚類解，并計(jì)算聚類解的適應(yīng)度。若適應(yīng)度優(yōu)于原分子，則保留新分子在候選聚類解中；否則，丟棄新分子。

圖2 單分子碰撞

(2)單分子分解

與單分子碰撞相似，單分子分解也是分子自身的化學(xué)反應(yīng)過程，但會生成兩個(gè)新的分子結(jié)構(gòu)Φ1’和Φ2’。具體分解過程如下：將原分子結(jié)構(gòu)Φ劃分為奇數(shù)號文檔和偶數(shù)號文檔，奇數(shù)號文檔及其所屬聚類結(jié)構(gòu)保留至新分子Φ1’中，Φ1’中偶數(shù)號文檔所屬聚類則在[1,K]內(nèi)隨機(jī)生成；偶數(shù)號文檔及其所屬聚類結(jié)構(gòu)保留至新分子Φ2’中，Φ2’中奇數(shù)號文檔所屬聚類則在[1,K]內(nèi)隨機(jī)生成。如圖3所示的單分子分解示例中，新分子結(jié)構(gòu)Φ1’中文檔d1、d3、d5和d7所屬聚類與原分子Φ保持一致，文檔d2、d4、d6和d8所屬聚類隨機(jī)生成；新分子結(jié)構(gòu)Φ2’中文檔d2、d4、d6和d8所屬聚類與原分子Φ保持一致，文檔d1、d3、d5和d7所屬聚類則隨機(jī)生成。得到新分子結(jié)構(gòu)后，算法解碼出分子結(jié)構(gòu)對應(yīng)的文本聚類解，并計(jì)算聚類解的適應(yīng)度。若適應(yīng)度優(yōu)于原分子，則保留新分子在候選聚類解中；否則，丟棄新分子。

圖3 單分子分解

(3)分子間碰撞

分子間碰撞可以通過兩個(gè)原分子結(jié)構(gòu)Φ1和Φ2生成兩個(gè)新的分子結(jié)構(gòu)Φ1’和Φ2’，屬于多分子間的化學(xué)反應(yīng)行為。具體碰撞過程如下：在兩個(gè)原分子結(jié)構(gòu)Φ1和Φ2上隨機(jī)選擇兩個(gè)位置x和y，將Φ1中位置x和y間的文檔所屬聚類保留至新分子結(jié)構(gòu)Φ1’中，其余位置上文檔的所屬聚類與Φ2保持一致，得到新分子結(jié)構(gòu)Φ1’；將Φ2中位置x和y間的文檔所屬聚類保留至新分子結(jié)構(gòu)Φ2’中，其余位置上文檔的所屬聚類與Φ1保持一致，得到新分子結(jié)構(gòu)Φ2’。如圖4所示的分子間碰撞示例中，新分子結(jié)構(gòu)Φ1’中文檔d3、d4、d5和d6所屬聚類原分子Φ1一致，文檔d1、d2、d7和d8所屬聚類原分子Φ2一致；新分子結(jié)構(gòu)Φ2’中文檔d3、d4、d5和d6所屬聚類原分子Φ2一致，文檔d1、d2、d7和d8所屬聚類原分子Φ1一致。得到新的分子結(jié)構(gòu)后，算法解碼出分子結(jié)構(gòu)對應(yīng)的文本聚類解，并計(jì)算聚類解的適應(yīng)度。若適應(yīng)度優(yōu)于原分子，則保留新分子在候選聚類解中；否則，丟棄新分子。

圖4 分子間碰撞

(4)分子間合成

分子間合成可以通過兩個(gè)原分子結(jié)構(gòu)Φ1和Φ2生成一個(gè)新的分子結(jié)構(gòu)Φ’，屬于多分子間的化學(xué)反應(yīng)行為。具體合成過程如下：在兩個(gè)原分子結(jié)構(gòu)Φ1和Φ2上隨機(jī)選擇一個(gè)位置x，保留Φ1中位置x左側(cè)文檔所屬聚類信息至新分子結(jié)構(gòu)Φ’的左側(cè)位置，保留Φ2中位置x右側(cè)文檔所屬聚類信息至新分子結(jié)構(gòu)Φ’的右側(cè)位置，得到一個(gè)新分子結(jié)構(gòu)Φ’。如圖5所示的分子間合成示例中，隨機(jī)位置x=4，則新分子Φ’中文檔d1、d2、d3和d4所屬聚類原分子Φ1一致，新分子Φ’中文檔d5、d6、d7和d8所屬聚類原分子Φ2一致。得到新分子結(jié)構(gòu)后，算法解碼出分子結(jié)構(gòu)對應(yīng)的文本聚類解，并計(jì)算聚類解的適應(yīng)度。若適應(yīng)度優(yōu)于原分子，則保留新分子在候選聚類解中；否則，丟棄新分子。

圖5 分子間合成

3.3 分子質(zhì)量評估適應(yīng)度

適應(yīng)度函數(shù)用于評估分子結(jié)構(gòu)代表的聚類解質(zhì)量。本文利用平均文檔相似質(zhì)心計(jì)算聚類解適應(yīng)度，基于式(6)的目標(biāo)函數(shù)，適應(yīng)度函數(shù)綜合利用了目標(biāo)函數(shù)取值在K個(gè)聚類上的均值結(jié)果，具體為

(8)

其中，nk表示聚類k中的文檔數(shù)量。

3.4 算法過程

結(jié)合K均值和化學(xué)反應(yīng)優(yōu)化算法CRO，本文設(shè)計(jì)了一種文本聚類算法，算法命名為KMCRO。KMCRO算法將K均值聚類生成的結(jié)果作為化學(xué)反應(yīng)算法CRO的初始輸入，將K均值聚類優(yōu)秀的局部開發(fā)能力和化學(xué)反應(yīng)算法強(qiáng)大的全局勘探能力有效結(jié)合，有效避免陷入局部最優(yōu)，防止聚類早熟收斂。算法2是KMCRO算法的執(zhí)行過程。該算法分為兩個(gè)階段，第一階段執(zhí)行K均值聚類算法，即步驟(3)～步驟(16)。該階段在若干次迭代基礎(chǔ)上尋找局部的最優(yōu)聚類，由于僅是局部最優(yōu)解，迭代次數(shù)可以設(shè)置較小，以較快的時(shí)間獲得最優(yōu)解。第二階段執(zhí)行化學(xué)反應(yīng)算法，即步驟(17)～步驟(30)，K均值聚類生成的解集合將作為化學(xué)反應(yīng)算法的初始輸入。該階段在已有K均值聚類的局部最優(yōu)解的基礎(chǔ)上進(jìn)一步做全局勘探，因此其迭代次數(shù)要長于K均值階段，以便最終獲得全局最優(yōu)解。融合K均值和化學(xué)反應(yīng)算法的文本聚類算法KMCRO可以在局部開發(fā)能力和全局勘探能力間做出有效均衡，并最終獲得更準(zhǔn)確的文本聚類解。

算法2： KMCRO算法

(1)輸入： 文本文檔集合D、 文檔數(shù)量n、 聚類數(shù)量K、K均值聚類迭代次數(shù)KImax、 化學(xué)反應(yīng)過程迭代次數(shù)CImax

(2)輸出： 最優(yōu)聚類解

(3)initialize randomly a solution setCRMwithSclustering solution

(4)fors=1 toSdo

(5) randomly selectKdocuments as clusters centroidC=(C1,C2,…,CK)

(6)forI=1 toKImaxdo

(7) initialize all elements as zeros in matrixA[K][n]

(8)foreach documentdiinDdo

(9)k=argmaxk∈{1 to K}based onCos(di,Ck)

(10) allocatedito the clusterCkand setA[k][i]=1

(11) update the clusters centroid using Eq.(5)

(12)endfor

(13)endfor

(14) transfer matrixA[K][n] into encoded solutions of CRO

(15) generate newCRMwith solutions produced byK-means clustering

(16)endfor

(17)forI=1 toCImaxdo

(18) select randomly solutionΦfromCRM

(19)call單分子碰撞

(20) compute fitness of new molecule and reserve the better molecule toCRM

(21) select randomly solutionΦfromCRM

(22)call單分子分解

(23) compute fitness of new molecule and reserve the better molecule toCRM

(24) select randomly solutionΦ1andΦ2fromCRM

(25)call分子間碰撞

(26) compute fitness of new molecule and reserve the better molecule toCRM

(27) select randomly solutionΦ1andΦ2fromCRM

(28)call分子間合成

(29) compute fitness of new molecule and reserve the better molecule toCRM

(30)endfor

(31)returnthe molecule with best fitness inCRMand encode clustering solution

算法詳細(xì)說明：步驟(1)和步驟(2)為算法的輸入輸出，步驟(3)隨機(jī)初始化一個(gè)規(guī)模為S的聚類解集CRM，針對每一個(gè)CRM中的解，執(zhí)行K均值聚類算法對其更新，具體地，步驟(5)隨機(jī)選擇K個(gè)質(zhì)心，步驟(7)對K均值的聚類解矩陣初始為0，步驟(8)～步驟(10)為每個(gè)文檔尋找至質(zhì)心相似度最大的質(zhì)心進(jìn)行聚類，步驟(11)更新質(zhì)心，步驟(14)將K均值矩陣聚類解轉(zhuǎn)換為化學(xué)反應(yīng)算法中使用的分子結(jié)構(gòu)編碼，并在步驟(15)中以所有生成的聚類解得到新的解集合CRM，化學(xué)反應(yīng)算法在現(xiàn)有CRM基礎(chǔ)上做進(jìn)一步聚類搜索。步驟(18)～步驟(20)執(zhí)行化學(xué)反應(yīng)中的單分子碰撞，步驟(21)～步驟(23)執(zhí)行化學(xué)反應(yīng)中的單分子分解，步驟(24)～步驟(26)執(zhí)行化學(xué)反應(yīng)中的分子間碰撞，步驟(27)～步驟(29)執(zhí)行化學(xué)反應(yīng)中的分子間合成，最終，步驟(31)輸出當(dāng)前CRM中適應(yīng)度最高的分子結(jié)構(gòu)并解碼出文本聚類解作為KMCRO算法的最終解。

圖6所示是文本文檔完整聚類分析流程圖。流程分為3個(gè)階段，第一階段是對文本信息進(jìn)行預(yù)處理，包括對詞語進(jìn)行分割、移除文檔中的終止詞、提取文檔詞干并計(jì)算詞條權(quán)重值；利用詞頻逆文本頻率指數(shù)TF-IDF計(jì)算得到全部詞條權(quán)重后，即可將文檔信息表征為矢量空間模型VSM，基于VSM對文檔進(jìn)行聚類分析。第二階段是利用K均值算法實(shí)現(xiàn)文本聚類，經(jīng)過KImax次迭代后，將K均值算法生成的聚類解集轉(zhuǎn)換為化學(xué)反應(yīng)優(yōu)化算法的分子結(jié)構(gòu)。第三階段將K均值聚類結(jié)果作為化學(xué)反應(yīng)優(yōu)化的初始分子結(jié)構(gòu)群，經(jīng)歷CImax次迭代過程的單分子碰撞、單分子分解、分子間碰撞和分子間合成4種化學(xué)反應(yīng)操作后，最后輸出適應(yīng)度最優(yōu)的分子結(jié)構(gòu)并解碼為最終的文本文檔聚類解。

圖6 文本文檔完整聚類分析流程

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

4.1 測試文本

利用Matlab實(shí)現(xiàn)融合化學(xué)反應(yīng)算法與K均值的文本聚類算法KMCRO，觀察在給定測試文本數(shù)據(jù)集合中融入化學(xué)反應(yīng)機(jī)制后聚類效果的變化。利用表1所示的6種基準(zhǔn)文本數(shù)據(jù)集測試算法性能，該數(shù)據(jù)集是美國加州大學(xué)計(jì)算智能實(shí)驗(yàn)室 LABIC提供的文本聚類標(biāo)準(zhǔn)數(shù)據(jù)集(http://sites.labic.icmc.usp.br/text_collections/)，是經(jīng)過詞條提煉后得到的數(shù)值抽象形式。數(shù)據(jù)集DS1為技術(shù)報(bào)告文摘，包含理論、人工智能、機(jī)器人和系統(tǒng)4類話題；數(shù)據(jù)集DS2來自Web頁面，包含山羊、生物醫(yī)學(xué)、綿羊和樂隊(duì)4類話題；數(shù)據(jù)集DS3、DS4、DS5和DS6均來自TREC，涉及的話題數(shù)分別為6、8、9、10。同時(shí)，測試數(shù)據(jù)集還給出了其包含的文檔數(shù)量和詞條數(shù)量。選擇常規(guī)K均值文本聚類算法、基于粒子群算法的文本聚類算法PSOTC[10]和基于遺傳算法的文本聚類算法GATC[11]進(jìn)行對比分析。

表1 測試文檔數(shù)據(jù)集

4.2 評估指標(biāo)

引入4種常用文本聚類評估指標(biāo)對算法的聚類效果進(jìn)行評估，包括：準(zhǔn)確率(Accuracy,A)、精確率(Precision,P)、召回率(Recall,R)和F度量(F-meansure,F)。除此之外，通過計(jì)算迭代過程中聚類解的適度度值描述算法的收斂情況，來評估文本聚類算法的計(jì)算速度。

(1)精確率P

精確率P表示所有相關(guān)文檔與所有聚類中文檔總量的比例，計(jì)算方式為

P(i,j)=ni,j/nj

(9)

其中，P(i,j) 表示聚類j中分類i的精確值，ni,j表示聚類j中分類i的實(shí)際成員數(shù)量，nj為聚類j中的所有成員數(shù)量。

(2)召回率R

召回率R表示相關(guān)文檔的實(shí)際數(shù)量與所有聚類文檔間的比例，該指標(biāo)需要根據(jù)給定的分類標(biāo)簽對每個(gè)聚類進(jìn)行計(jì)算，計(jì)算方式為

R(i,j)=ni,j/ni

(10)

其中，R(i,j) 表示聚類j中分類i的召回值，ni表示分類i中的實(shí)際成員數(shù)量。

(3)F度量F

F度量根據(jù)聚類精確率P和召回率R進(jìn)行計(jì)算。最佳的文本聚類效果是F度量值盡量接近于1。聚類j中分類i的F度量計(jì)算為

(11)

所有聚類的F度量計(jì)算為

(12)

其中，n表示文檔集合D中的文檔總量。

(4)準(zhǔn)確率A

準(zhǔn)確率用于計(jì)算分配至每個(gè)聚類的真實(shí)文本文檔所占的比例，計(jì)算為

(13)

其中，K表示總聚類數(shù)量，P(i,j) 表示聚類j中分類i的精確值。

(5)適應(yīng)度

即式(7)定義的聚類解的適應(yīng)度值，可用于描述算法的收斂速度。

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

表2所示是4種算法在6種測試數(shù)據(jù)集合中得到的聚類精確率、準(zhǔn)確率、召回率和F度量指標(biāo)上的性能表現(xiàn)，加粗?jǐn)?shù)值為該指標(biāo)上的最優(yōu)值。從整體上可以看到，本文算法在絕大多數(shù)測試文本數(shù)據(jù)中均可以得到最佳的性能指標(biāo)值，在數(shù)據(jù)集DS1、DS5和DS6上算法的4個(gè)指標(biāo)均是最優(yōu)的。DS2和DS3中的精確率和DS4中的準(zhǔn)確率稍有差異，但不足以影響算法的整體性能，這可能是源于第一階段中初始質(zhì)心選擇的影響。在6個(gè)文本測試數(shù)據(jù)集中穩(wěn)定的表現(xiàn)表明，本文算法結(jié)合K均值算法的局部快速開發(fā)尋優(yōu)能力和化學(xué)反應(yīng)算法的全局勘探能力進(jìn)行文檔聚類是有效可行的。

表2 聚類指標(biāo)表現(xiàn)

圖7是6種基準(zhǔn)文本數(shù)據(jù)集測試得到的4種算法的適應(yīng)度變遷情況。最終的穩(wěn)定聚類適應(yīng)度值是經(jīng)過迭代進(jìn)化得到的最優(yōu)聚類解的適應(yīng)度值。從不同類型的文本數(shù)據(jù)集的測試結(jié)果看，K均值聚類算法在多數(shù)情況下收斂較快，但其得到的適應(yīng)度值最小，這是由于該算法基本是一種局部尋優(yōu)算法，其最終的聚類解對于初始聚類質(zhì)心的選擇較為依賴，而隨機(jī)式的初始質(zhì)心選擇也加大了算法的不穩(wěn)定性。兩種元啟發(fā)式對比算法通過種群進(jìn)化機(jī)制對聚類解空間做了進(jìn)一步擴(kuò)展，加大了得到全局最優(yōu)解的概率，但其隨機(jī)化的粒子初始位置以及遺傳個(gè)體的隨機(jī)性依然沒有根本解決進(jìn)化個(gè)體可能出現(xiàn)的早熟問題。本文算法結(jié)合K均值算法的局部快速開發(fā)尋優(yōu)能力和化學(xué)反應(yīng)算法的全局勘探能力，以K均值得到的聚類解集合作為化學(xué)反應(yīng)算法的初始分子結(jié)構(gòu)群，通過4種化學(xué)反應(yīng)操作，增加種群分子的多樣性，在擴(kuò)展搜索空間的基礎(chǔ)上得到最優(yōu)文本聚類結(jié)果，因此，其得到的適度值是最高的。同時(shí)，綜合6種測試數(shù)據(jù)集合的結(jié)果來看，本文算法具有很好的適應(yīng)性，面對不同類型不同話題分布的文本集，基本上都可以得到最佳的聚類適應(yīng)度，說明聚類效果上相似性和距離度量均做到了最優(yōu)。

圖7 適應(yīng)度值

圖8觀察本文算法在利用不同的聚類質(zhì)量標(biāo)準(zhǔn)時(shí)的性能，即單獨(dú)利用余弦相似度度量、單獨(dú)利用歐氏距離度量以及混合雙目標(biāo)度量時(shí)的表現(xiàn)，選擇聚類準(zhǔn)確率A和F度量值進(jìn)行評估。左側(cè)縱坐標(biāo)為聚類準(zhǔn)確率指標(biāo)，右側(cè)縱坐標(biāo)表示聚類F度量指標(biāo)，橫坐標(biāo)上的柱狀圖對應(yīng)左側(cè)縱坐標(biāo)，橫坐標(biāo)上的折線圖對應(yīng)右側(cè)縱坐標(biāo)?？梢钥吹?，同步融合余弦相似度和歐氏距離在適應(yīng)度函數(shù)中得到的聚類效果在所有測試文本數(shù)據(jù)集中均產(chǎn)生了比單目標(biāo)度量更好的效果。此外，單獨(dú)以余弦相似度或歐氏距離作為聚類標(biāo)準(zhǔn)時(shí)的效果相差并大，從準(zhǔn)確率和F度量看，余弦相似度得到的聚類效果略好一些。

圖8 聚類目標(biāo)度量方式

5 結(jié)束語

提出一種融合化學(xué)反應(yīng)算法和K均值算法的文本文檔聚類算法。算法首先利用K均值算法快速獲得文本聚類局部最優(yōu)解集合，再以該解集合作為化學(xué)反應(yīng)機(jī)制的初始輸入，在此侯選聚類解集合上進(jìn)行4種分子化學(xué)反應(yīng)，結(jié)合K均值的局部快速開發(fā)尋優(yōu)能力和化學(xué)反應(yīng)算法的全局勘探能力，得到文本聚類最優(yōu)解。經(jīng)過6種數(shù)據(jù)集的聚類測試，結(jié)果表明，該算法可以比基準(zhǔn)算法獲得性能更好的聚類結(jié)果，且適應(yīng)度更優(yōu)，聚類準(zhǔn)確度更高。