吳雅琴，王曉東

(內(nèi)蒙古醫(yī)科大學(xué) 計(jì)算機(jī)信息學(xué)院， 呼和浩特 010110)

近年來，隨著計(jì)算機(jī)和互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，人們在工作和生活中產(chǎn)生了各種形式的數(shù)據(jù)，如文本、圖像、音頻、視頻等，這些數(shù)據(jù)的存儲量正變得越來越大。如何準(zhǔn)確和有效地從這些海量數(shù)據(jù)中抽取出隱藏的、有價值的信息成為計(jì)算機(jī)科學(xué)領(lǐng)域中的研究熱點(diǎn)，由此數(shù)據(jù)挖掘技術(shù)應(yīng)運(yùn)而生[1-2]。數(shù)據(jù)挖掘又稱知識發(fā)現(xiàn)，即“從數(shù)據(jù)中挖掘知識”，可以看作信息技術(shù)自然進(jìn)化的結(jié)果。聚類分析作為大數(shù)據(jù)挖掘中最為重要的方法之一，已經(jīng)得到了人們越來越多的關(guān)注[3]。其中，K-Means無監(jiān)督聚類算法是現(xiàn)有聚類算法中最為典型的劃分算法。目前，K-Means聚類算法在情報檢索、機(jī)器學(xué)習(xí)、專家系統(tǒng)(依靠過去的經(jīng)驗(yàn)法則)和模式識別等領(lǐng)域得到了廣泛應(yīng)用[4]。

K-Means聚類算法作為聚類分析中廣泛應(yīng)用的一種經(jīng)典算法，具有算法結(jié)構(gòu)簡單、運(yùn)行效率高且適用范圍大等優(yōu)點(diǎn)。文獻(xiàn)[5]將基于K-Means聚類算法的自動圖譜識別應(yīng)用于電纜監(jiān)測，其能夠?qū)?nèi)部放電、沿面放電和干擾信號做出準(zhǔn)確的判斷。文獻(xiàn)[6]提出了一種K-means聚類算法，并將其應(yīng)用于大數(shù)據(jù)圖像檢索，獲得了較高的檢索準(zhǔn)確率。但是，K-Means聚類算法對初始參數(shù)設(shè)置有較大的依賴性，此外，其聚類結(jié)果的魯棒性較低且易陷入局部最優(yōu)解。因此，許多文獻(xiàn)對K-Means聚類算法進(jìn)行了改進(jìn)和優(yōu)化[7-10]。這些方法在一定程度上克服了K-Means聚類算法的缺陷，但仍需繼續(xù)優(yōu)化和完善。

為了解決上述問題，提高K-Means聚類算法的聚類穩(wěn)定度和速度，本文提出了一種改進(jìn)的混合差分進(jìn)化算法，并將混合差分進(jìn)化算法引入K-Means聚類中。通過個體適值函數(shù)把種群視為2個子種群的混合體，按照不同的變異策略和參數(shù)對2個子種群分別進(jìn)行動態(tài)更新，提高了獲取全局最優(yōu)的概率。該算法較好地解決了K-Means聚類算法容易陷入局部最優(yōu)陷阱的問題。實(shí)驗(yàn)結(jié)果表明：相比K-Means聚類算法、基于差分進(jìn)化的K-均值聚類算法，本文方法較好地提高了聚類的有效性和穩(wěn)定性。

1 K-Means聚類算法基本原理

1.1 算法基本思想

作為一種基于距離的聚類劃分算法，K-Means聚類算法具有結(jié)構(gòu)簡單、運(yùn)行效率高且適用范圍大等優(yōu)點(diǎn)[4]。K-Means聚類算法一般通過如式(1)所示的目標(biāo)函數(shù)來實(shí)現(xiàn)優(yōu)化。

(1)

可以看出，式(1)所示的目標(biāo)函數(shù)是一個誤差平方和計(jì)算過程。其中：E為聚類準(zhǔn)則函數(shù)；K為聚類的總數(shù)；Cj,j=1,2,…,K為聚類中的簇；x為簇Cj中的一個聚類目標(biāo)；mj為簇Cj的平均大小。通常來說，E值越小則聚類效果越好。反之，E值越大則聚類質(zhì)量越差。

1.2 K-Means聚類算法的基本流程

K-Means聚類算法的輸入?yún)?shù)為數(shù)值K和數(shù)據(jù)集X中聚類目標(biāo)的數(shù)量n，輸出為使聚類準(zhǔn)則函數(shù)E達(dá)到最小的K個聚類。K-Means聚類算法的基本流程如圖1所示。

1.3 K-Means聚類算法存在的問題分析

K-Means聚類算法的主要缺點(diǎn)分為3個方面[3]：① 初始參數(shù)依賴性較高，且算法容易產(chǎn)生局部最優(yōu)解；② 容易受噪聲數(shù)據(jù)和離群數(shù)據(jù)點(diǎn)的干擾；③K-Means聚類算法作為一種基于歐式距離的硬聚類算法，僅對球形狀簇表現(xiàn)出較好的聚類性能。④ 對聚類數(shù)目K的值較為敏感。針對上述缺點(diǎn)中的局部最優(yōu)解陷阱問題，本文引入差分進(jìn)化算法，并與K-Means聚類算法進(jìn)行結(jié)合。

圖1 K-Means聚類算法流程

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

差分進(jìn)化算法是一種基于群體智能的新型啟發(fā)式算法，能夠通過演化技術(shù)計(jì)算種群中個體間的差異信息，并按照適應(yīng)值的結(jié)果擇優(yōu)選擇符合要求的下一代種群，從而完成種群的進(jìn)化[11]。差分進(jìn)化算法是一種具有良好穩(wěn)健性和全局搜索能力的全局優(yōu)化算法[12]。

設(shè)X為初始種群，N為種群的大小，Xi(t)(t=1,2,…,N)為當(dāng)前種群中進(jìn)化個體，t為進(jìn)化過程的迭代次數(shù)。種群中個體變異操作的過程如式(2)所示。

Vi(t)=(vi1(t),vi2(t),…,viD(t))=

Xp1(t)+F(Xp2(t)-Xp3(t))

(2)

其中：Xp1(t)、Xp2(t)、Xp3(t)是從當(dāng)前進(jìn)化種群中隨機(jī)選擇的3個不同個體；F是縮放權(quán)值。經(jīng)驗(yàn)表明：F=0.6時效果較好；D為種群中個體的維度，即變異個體Vi(t)由D個分量構(gòu)成。

當(dāng)前種群中的進(jìn)化個體Xi(t)與Vi(t)進(jìn)行交叉操作，生成競爭個體Ui(t)=(ui1(t),ui2(t),…,uiD(t))(由D個分量構(gòu)成)。競爭個體Ui(t)中j-th分量的計(jì)算方法如式(3)所示。

(3)

其中：z是一個隨機(jī)整數(shù)，且z∈{1,2,…,D}；CR∈[0,1]，為交叉概率，經(jīng)驗(yàn)表明，CR取值在0.3～0.9較為適宜。

通過適應(yīng)度值對比競爭個體和當(dāng)前種群中的進(jìn)化個體，并按照式(4)方法在上述兩者中進(jìn)行擇優(yōu)選擇更新種群[13]。

(4)

3 混合差分進(jìn)化K-Means聚類算法

在種群的迭代進(jìn)化過程中，根據(jù)貪婪選擇策略，傳統(tǒng)的差分進(jìn)化算法會以較大的概率阻止適應(yīng)度較差的個體進(jìn)入下一代種群。這種情況會造成迭代末期時種群個體之間的差異較小，多樣性較低，容易導(dǎo)致種群中大多數(shù)個體都集中在一個局部極值點(diǎn)附近。這種情況下，無論如何進(jìn)行變異、交叉和選擇，進(jìn)化后的種群都與上一代種群十分類似，無法產(chǎn)生新的個體。針對該情況，本文通過個體適值函數(shù)把種群視為2個子種群的混合體，并按照不同的變異策略和參數(shù)對2個子種群分別進(jìn)行動態(tài)更新，提高了獲取全局最優(yōu)的概率。

3.1 混合差分進(jìn)化算法

首先按照參數(shù)δ對種群進(jìn)行劃分，前δ%個個體為子種群X′，其余個體為子種群X″。在每次迭代進(jìn)化的最后，根據(jù)式(5)更新參數(shù)δ。

δ=δmin+rand·(δmax-δmin)

(5)

按照不同的變異策略和參數(shù)對2個子種群分別進(jìn)行動態(tài)更新。對于子種群X′中個體Xi(t)，采用的變異策略如式(6)所示。

Vi(t)=Xi(t)+Fi(t)·(Xp1(t)-Xp2(t))+

Fi(t)·(Xp3(t)-Xp4(t))

(6)

其中：Fi(t)為個體Xi(t)相應(yīng)的縮放權(quán)值；Xp1(t)、Xp2(t)、Xp3(t)、Xp4(t)是從當(dāng)前進(jìn)化種群中隨機(jī)選擇出來的4個不同個體。

對于子種群X″中個體Xi(t)，采用的變異策略如式(7)所示。

Vi(t)=Xi(t)+Fi(t)·(Xδbest-Xi(t))+

Fi(t)·(Xp5(t)-Xp6(t))

(7)

其中：Xδbest為從子種群X′中隨機(jī)選擇的個體；Xp5(t)、Xp6(t)是從當(dāng)前進(jìn)化種群中隨機(jī)選擇出來的2個不同個體。

對于子種群X′和X″中的個體Xi(t)，若通過Fi(t)生成的后代能夠進(jìn)入下一代，則記錄到集合SF中，下一代個體Xi(t+1)對應(yīng)的縮放權(quán)值可以按照式(8)產(chǎn)生，否則按照式(9)產(chǎn)生。

(8)

(9)

其中：fiti為當(dāng)前個體的適應(yīng)度值，fitb為當(dāng)前種群中個體的最佳適應(yīng)度值，fitw為當(dāng)前種群中個體的最差適應(yīng)度值；meanA(SF)為集合SF中所有對象的算術(shù)平均值。

按照以上縮放權(quán)值的動態(tài)更新方法，能夠充分考慮所產(chǎn)生后代存活情況。這種按照不同的變異策略和縮放權(quán)參數(shù)對2個子種群分別進(jìn)行動態(tài)更新的方法可有效提高獲取全局最優(yōu)的概率。

3.2 基于混合差分進(jìn)化的 K-Means聚類算法

基于混合差分進(jìn)化的K-Means聚類算法流程如圖2所示。

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

為了驗(yàn)證提出的混合差分進(jìn)化的K-Means聚類算法的性能，將本文算法與另外2種典型聚類算法(K-Means聚類算法和基于差分進(jìn)化的K-均值聚類算法)進(jìn)行對比，以驗(yàn)證本文算法的聚類性能。仿真環(huán)境為 Matlab 7.0，實(shí)驗(yàn)平臺為Windows 10 64位操作系統(tǒng)，CPU為i5-4570處理器，4 GB內(nèi)存。實(shí)驗(yàn)使用的數(shù)據(jù)集是UCI 數(shù)據(jù)庫中的3個數(shù)據(jù)集，如表1所示。實(shí)驗(yàn)參數(shù)設(shè)置如表2所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集參數(shù)

圖2 基于混合差分進(jìn)化的 K-Means聚類算法流程

參數(shù)數(shù)值種群規(guī)模40λmax0.4λmin0.2初始縮放權(quán)重 Fi(0)0.6CR0.2D20The maximum number of iterations2 000

IRIS、Glass和Vowel數(shù)據(jù)集，實(shí)驗(yàn)結(jié)果見表3～5。圖3為20維的收斂特性。

通過表3～5可以看出，在最小類內(nèi)距離和最大類內(nèi)距離結(jié)果方面，相比其他兩種算法，本文算法的數(shù)值結(jié)果均為最小。這表明本文方法的最大類內(nèi)距離和最小類內(nèi)距離之間的差值都有較大的減少。此外，本文方法具有最小的平均類內(nèi)距離，說明聚類結(jié)果波動范圍較小，穩(wěn)定性較高。

表3 IRIS數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果

表4 Glass數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果

表5 Vowel數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果

圖3 收斂特性比較

在算法平均收斂代數(shù)方面，相比基于差分進(jìn)化的K-均值聚類算法，本文算法的收斂速度有所提升，這是因?yàn)椴捎昧穗p種群混合策略。圖3的曲線結(jié)果也驗(yàn)證了本文算法的收斂優(yōu)勢，表明其具有良好的尋優(yōu)能力。

上述實(shí)驗(yàn)結(jié)果驗(yàn)證了本文算法的可行性和高效性。相比其他兩種算法，本文算法能以較快的速度獲得全局最優(yōu)值，并具有更好的魯棒性。

5 結(jié)束語

本文提出了一種改進(jìn)的混合差分進(jìn)化算法，并將混合差分進(jìn)化算法引入K-Means聚類中。通過個體適值函數(shù)把種群視為2個子種群的混合體，并按照不同的變異策略和參數(shù)對2個子種群分別進(jìn)行動態(tài)更新，提高了獲取全局最優(yōu)的概率。該算法較好地解決了K-Means聚類算法容易陷入局部最優(yōu)陷阱的問題。實(shí)驗(yàn)結(jié)果表明：相比K-Means聚類算法、基于差分進(jìn)化的K-均值聚類算法，本文方法能有效提高聚類質(zhì)量和收斂速度。