一種基于改進差分進化的K-均值聚類算法研究?

王鳳領 梁海英 張 波

（賀州學院數(shù)學與計算機學院 賀州 542899）

1 引言

差分進化算法（DE）是由Storn.R和Price.K提出的一種基于群體進化的啟發(fā)式算法，該算法從原始種群開始，通過變異、交叉和選擇操作來生成新種群，是一種隨機的并行全局搜索算法，具有記憶個體最優(yōu)解和種群內信息共享的特點，即通過種群內個體間的合作與競爭來實現(xiàn)對優(yōu)化問題的求解。差分進化算法具有簡單高效、收斂速度快、魯棒性好等優(yōu)點。如劉明廣通過引入遷徙操作而提出一種改進差分進化算法，吳亮紅提出的基于群體適應度二次變異的自適應方差的差分進化算法。

K-means算法是由Mac（lueen）提出的經(jīng)典聚類分析算法。它具有算法簡單，收斂快的優(yōu)點，但算法的聚類結果容易受到初始聚類中心的影響，易于陷入局部最優(yōu)。近年來，許多學者利用各種常用的智能優(yōu)化算法來改進K-means算法，并取得了一些成果?；诓町愡M化的K-means算法的改進優(yōu)于基于傳統(tǒng)遺傳算法和微粒群優(yōu)化算法。但傳統(tǒng)的差分進化算法也會造成全局尋優(yōu)能力下降，基于傳統(tǒng)差分進化的K均值改進算法的性能受到全局優(yōu)化能力的影響。本文提出基于改進的差分進化的K均值聚類算法。結合改進的差分進化算法和K均值，實驗結果表明，該算法具有更好的全局優(yōu)化能力和更快的收斂性。

2 差分進化算法

2.1 研究現(xiàn)狀

2013年，Liang Bai等提出一種快速全局K-means算法，有效提高算法的聚類速度。在2014年，Aristidis Likas和Grigorios Tzortzis提出一種基于權重的K-means算法。2015年，Li Ma等提出了一種改進的K-mean算法。近幾年，國內外許多研究人員將K-means和DE算法組合，取得一些成果。2015年Wan-li Xiang等使用動態(tài)攪亂差分進化算法進行聚類。2008年Swagatam Das等提出了基于差分進化的自動聚類算法（ACDE）。喬艷霞等提出一種基于K-means的改進差分進化聚類算法，將差分進化算法用于K-means聚類。劉莉莉等改進自適應調整的控制參數(shù)、將差分進化算法用選擇結構的多模式進化方案，并將其與K-means聚類算法相結合，有效地解決初始聚類中心的優(yōu)化問題。高平，毛力等提出了一種基于改進差分進化的K-means聚類算法，通過Logistic變尺度混濁搜索，增強差分進化算法的全局尋優(yōu)能力［1］。

2.2 差分進化算法的關鍵操作

差分進化算法（DE）是一種典型的實數(shù)編碼的進化算法，采用變異、雜交、選擇等關鍵性操作從上一代種群到下一代種群的進化，以實現(xiàn)群體優(yōu)化，下面將分析差分進化算法中涉及的幾個操作［2］。

1）種群初始化

定義N×D的矩陣X用于存放當前種群的數(shù)據(jù)，其中，D為種群中個體的維數(shù)，N為種群的規(guī)模，隨機產(chǎn)生N×D個服從均勻分布規(guī)律并滿足特定約束條件的數(shù)據(jù)，放入矩陣X中，構成初始種群X(0)={X1(0)，X2(0)…XN(0)}。

2）變異操作

令種群大小為N，當前進化個體Xi(t)(i=1，2，…，N)表示，t為當前進化個數(shù)。隨機選擇三個不同的個體，從當前進化群體中，并滿足條件 r1，r2，r3∈{1，2，…，N}，r1≠r2≠r3≠i，個體Xr2(t)和 Xr3(t)差值(Xr2(t)-Xr3(t))被看作個體Xr1(t)的擾動因子［2］。將因子和個體 Xi(t)相加以獲得當前突變，突變操作的演變的對應個體Vi(t)，如式（1）所示:

其中F為控制擾動因子的縮放系數(shù)。群體中個體由D個分量組成，那么變體個體Vi(t)也由D個分量組成，即Vi(t)=vr1(t)，vr2(t)，…，viD(t))。

3）交叉操作

生成隨機整數(shù)r4，且 r4∈{1，2，…，N}，離散變異個體Vi(t)與當前進化個體Xi(t)交叉以獲得中間測試個體Ui(t)，其將與 Xi(t)選擇操作競爭，并且Ui(t)由D組分組成，即Ui(t)=(ui1(t)，ui2(t)，…，uiD(t))。其中第j個分量如式（2）所示:

r4是｛1，2，…，D｝中的隨機整數(shù)，randj（0，1）表示服從（0，1）上均勻分布的隨機數(shù)，并且r4可以保證在突變個體Vi(t)中存在至少一個維度分量，測試個體Ui(t)，確保突變操作的作用力。CR是交叉概率，并且CR∈［0，1］，CR概率越小，中間試驗個體Ui(t)對當前進化個體Xi(t)的相似性越大。這可以幫助確保群體的多樣性和算法的全局優(yōu)化［3］。

4）選擇操作

在最小化問題的情況下，適應度值越小越好［4］。如果Ui(t)的適應度值小于的適應度值，中間實驗Ui(t)將替代新個體 Xi(t+1)中的當前個體Xi(t)。否則，當前進化的個體 Xi(t)將直接到下一代。如果個體適合度值由 f(Xi(t))表示，則選擇操作可以式（3）表示如下:

5）參數(shù)設定

差分進化算法的主要控制參數(shù)有縮放系數(shù)、交叉概率CR以及F種群規(guī)模N。對差分進化算法的性能有著重要影響，尤其是縮放系數(shù)和交叉概率，在某種程度上決定算法的收斂速度和全局搜索能力［4］。

2.3 差分進化算法的步驟和流程

1）步驟

種群中的每個體都是求解問題的可行解，種群規(guī)模為N，個體的適應度表示為 f(Xi(t))函數(shù)，其中Xi(t)表示第t代種群的第i個個體，F(xiàn)是縮放系數(shù)，t是進化代數(shù)。CR表示交叉概率。養(yǎng)分進化算法的步驟描述為

步驟1:完成種群初始化，設群體大小N，縮放因子F∈［0，2］，交叉概率 CR∈［0，1］，進化代數(shù)t=0，隨機生成初始種群 X(0)={X1(0)，X2(0)，…，XN(0)}，其中，對任一個體 Xi(0)都含D個分量的向量，即 Xi(0)={Xi1(0)，Xi2(0)，…，XiD(0)}；

步驟2:計算出每個體的適應度值 f(Xi(t))，對種群中的每個體進行評價；

步驟3:對種群個體 Xi(t)按式（1）完成變異操作，將得到變異個體Vi(t)；

步驟5:對于最小化求解問題，具有小適應度函數(shù)值的個體進入下一代種群中繼續(xù)進化。采取貪心策略，在選擇操作過程中，擇優(yōu)選取，比較當前進化個體Xi(t)與相對應中間試驗個體的適應度值。選擇方式按式 Xi(t+1)進行；

步驟6:對種群X(t+1)中的個體進行檢驗，如果終止算法滿足條件，則輸出；否則t=t+1，轉到步驟2。

2）算法流程

根據(jù)上述差分進化算法的描述，得到差分進化算法的流程圖［5］，如圖1所示。

圖1 差分進化算法的流程圖

3 基于差分進化算法的K-均值聚類

差分進化算法是基于選擇、交叉、變異操作的全局優(yōu)化算法，差分算法用于操作對多個個體組成的群體，該群體中的個體經(jīng)過優(yōu)化，逐漸接近最優(yōu)解，可通過K-均值聚類算法避免容易陷入局部最優(yōu)解的缺陷，提高算法收斂速度和算法的穩(wěn)定性［6］。

3.1 基于差分進化的K-均值聚類算法描述

首先需要對從數(shù)據(jù)集中隨機選擇的聚類中心進行編碼，構建初始種群，然后進行差分進化算法的選擇、交叉、變異等，以獲得最佳個體，最后，最佳個體解碼，獲得最佳初始聚類中心并進行聚類［7］。其步驟如下。

輸入:包含n個數(shù)據(jù)對象的數(shù)據(jù)集X、聚類數(shù)目K、縮放系數(shù)F、種群大小N、交叉概率CR。

輸出:輸出最佳聚類結果。

步驟1編碼:使用實數(shù)編碼從數(shù)據(jù)集中隨機選擇聚類中心，對與可行解對應的編碼進行編碼；每個個體由K個聚類中心向量串組成，因為樣本向量維數(shù)d，所以每個個體應該是K×d維向量［8］。具體編碼如下:

其中，Xi(t)為第t代種群的第i個個體，表示第i個個體的第j個聚類中心，迭代次數(shù)t的初始值為0。

步驟2種群初始化:從數(shù)據(jù)集K數(shù)據(jù)樣本中隨機選取個體作為初始種群，重復N次操作，構建初始種群。

步驟3評價種群中每一個體；計算個體Xi(t)的適應度值 f(Xi(t))。

步驟4變異操作:從種群中隨機選擇三個個體Xa，j(t)，Xb，j(t)，Xc，j(t)，并且 a≠b≠c≠i，并按如下式進行計算得到變異個體Vi(t)，Vi(t)為縮放系數(shù)。

步驟5交叉操作:種群中的個體Xi(t)和變異個體Vi(t)進行交叉操作，并按如下式進行計算得到中間試驗個體Ui(t):

其中，rand（0，1）是在（0，1）上均勻分布的隨機數(shù)，rand（i）是［1，K］上的隨機數(shù)。 CR是交叉概率，CR∈［0，1］。

步驟6選擇操作:在中間試驗個體Ui(t)和當前進化個體Xi(t)之間，采用貪心算法計算和比較適應度值，確定個體的最小適合度值，即最佳個體進入下一代種群。

步驟7檢驗種群X（t+1）中的個體，若滿足終止條件，則輸出最佳個體并終止算法；否則，迭代次數(shù)t將增加1，并返回步驟2繼續(xù)。

步驟8對輸出的最佳個體進行解碼，得到相應的最優(yōu)聚類中心集，并將種群中的所有數(shù)據(jù)對象劃分為相應的簇中，根據(jù)最近鄰原則。

步驟9輸出聚類結果。

3.2 基于差分進化的K-均值聚類算法流程

差分進化算法是具有強大的全局搜索能力的進化算法，應用于優(yōu)化K-均值聚類算法的初始中心，有效克服K-均值聚類算法對初始中心值選擇敏感缺陷，大大提高初始聚類中心的質量［9］。根據(jù)基于差分進化的K-均值聚類算法的描述，得到基于差分進化的K-均值聚類算法的流程圖，如圖2所示。

圖2 基于差分進化的K-均值聚類算法的流程圖

4 改進差分進化的K-均值聚類算法

通過將差分進化算法引入到K-均值聚類算法，可優(yōu)化初始聚類中心的選擇過程，簡便易行，提高聚類質量和收斂速度。交叉和突變操作確保種群進化的多樣性和算法的全局搜索能力［10］。然而，隨著差分進化代數(shù)的增加，種群的多樣性將會變小，過早收斂到局部最小點，或者算法停滯不前［11］。因此，需要加強算法的局部搜索能力，特別是后期進化算法收斂速度。在本文中，提出一種改進的方案來提高算法的局部搜索能力［12］。

4.1 改進方案

1）加強局部搜索能力

與標準差分進化算法相比，全局優(yōu)化能力并沒有減弱，而且可以同時增強算法的局部搜索能力［13］。改進方案的基本思想是記錄在算法變異操作中和個體Xi(t)對應的兩個隨機個體之間的差，即 Xr2(t)-Xr3(t)，記為 Hi(t)，即 Hi(t)=Xr2(t)-Xr3(t)，在選擇操作之后獲到的個體Xi(t+1)為中心，Hi(t)為半徑，并在此范圍內繼續(xù)搜索，產(chǎn)生新個體與 Xi(t+1)的適應度值，如果在此范圍內搜索新產(chǎn)生的個體適應度值優(yōu)于Xi(t+1)，用個體(t+1)替代 Xi(t+1)將成為新的Xi(t+1)，從而加強原差分進化算法的局部搜索功能［14］。

2）采用動態(tài)縮放系數(shù)

差分進化算法中設置控制參數(shù)對算法的性能有重要的影響。在本文中，采用開口向上拋物線方式取值縮放系數(shù)F，F(xiàn)的值如式（6）:

其中，F(xiàn)min為最小縮放系數(shù)，且Fmin=0.4，F(xiàn)max為最大縮放系數(shù)，且Fmax=0.9。t為當前進化的代數(shù)，TMAX為算法設定的最大進化代數(shù)。

3）采用動態(tài)交叉概率

在本文中，采取隨進化代數(shù)線性增加的交叉概率取值策略，交叉概率CR對差分進化算法的收斂速度有直接和重要的影響，方法如式（7）:

其中，CRmax為最大交叉概率，CRmax=0.9，CRmin為最小交叉概率，CRmin=0.3，t為當前進化代數(shù)，TMAX為算法設定的最大進化代數(shù)。

4.2 算法描述

根據(jù)上述改進方案，改進了標準差分進化算法，并將改進的差分進化算法應用于K-均值聚類算法中初始聚類中心的優(yōu)化。對于一組聚類中心（c1，c2，…，cK），在K-均值聚類算法中，相應的類內距離定義為式（8）:

其中，mi為簇wi的中心，x是簇wi中的數(shù)據(jù)樣本，通過計算簇wi中所有數(shù)據(jù)樣本的均值來獲得，本文中的適應度函數(shù)采用式（9）:

算法描述如下:

輸入:含有n個數(shù)據(jù)對象的數(shù)據(jù)集X、聚類數(shù)目K、種群規(guī)模N。

輸出:輸出最佳聚類結果。

步驟1:用于對聚類中心進行編碼以完成種群初始化:對于使用實際編碼從數(shù)據(jù)中心對數(shù)據(jù)集進行隨機選擇，進化代數(shù)t=0，一組K個聚類中心對應于一個個體，因為聚類中心代表聚類，種群N的大小，表明初始種群代表N種聚類，單個體由K個基因位向量串組成，基因位代表聚類中心，編碼如式（4）。

假設每個聚類中心的向量維數(shù)為d，數(shù)據(jù)樣本的維數(shù)為d維，種群中的每個個體為K×d維向量。從數(shù)據(jù)集K數(shù)據(jù)樣本中隨機選擇K個體的初始種群，重復N次操作，以構建初始種群。

步驟2:個體評價，計算每個個體的適應度值f(Xi(t))。

步驟3:變異操作，根據(jù)個體基因位進行變異，個體 Xi(t)按式 vij(t)=xaj(t)+F(xbj(t)-xcj(t))(j=1，2，…，K)計算得到變異個體Vi(t)，記錄兩個隨機個體 的 差 值 Hi(t)=Xb(t)-Xc(t) ，Hi(t)=(hi1(t)，hi2(t)，…，hiK(t))為縮放系數(shù)，按照公式 F=(Fmax-Fmin)執(zhí)行動態(tài)遞減策略取值。

步驟4:交叉操作，按照式 uij(t)=計算得到中間試驗個體Ui(t)，Ui(t)是由K維分量組成的，即Ui(t)=(ui1(t)，ui2(t)，…，uiK(t))。其中，CR為交叉概率，CR進行取值策略。隨著進化代數(shù)的增加，CR的值線性增加。

步驟5:選擇操作，中間試驗個體Ui(t)和當前進化個體Xi(t)之間，哪個個體進入下一代種群中使用貪心選擇策略來決定。擇優(yōu)選取當前進化個體Xi(t)與其對應中間試驗個體Ui(t)的適應度值。對于最小化求解問題，具有較小適應度值的個體可能繼續(xù)進化成下一代種群。按式進行選擇。

步驟6:檢驗下一代種群中的個體，若滿足終止條件，則輸出最佳個體并終止算法；否則，迭代次數(shù)增加1，返回繼續(xù)步驟2操作。

步驟7:對輸出的最佳個體進行解碼以獲得相應的最優(yōu)聚類中心集，并根據(jù)最近鄰原則將種群中的所有數(shù)據(jù)對象劃分為相應的簇。

步驟8:輸出聚類結果。

4.3 算法流程

改進的差分進化算法的重要特征是添加二次選擇和二次變異操作以增強局部搜索能力。同時，交叉概率和縮放因子不是固定值，是采用動態(tài)變化值策略［15］。

基于上述改進差分進化的K-均值聚類算法的描述，得到改進差分進化的K-均值聚類算法流程圖，如圖3所示。

圖3 基于改進差分進化的K-均值聚類算法流程圖

4.4 實驗結果及分析

采用UCI數(shù)據(jù)庫中的三個數(shù)據(jù)集:IRIS數(shù)據(jù)集，Glass數(shù)據(jù)集和Vowel數(shù)據(jù)集被用作測試數(shù)據(jù)集。三個數(shù)據(jù)集用于測試K-均值聚類算法，基于差分進化算法的K-均值聚類算法和提出的基于改進差分進化的K-均值聚類算法的聚類效果。

表1 測試數(shù)據(jù)集特征描述

在基于差分進化K-均值聚類算法的仿真實驗中，種群大小N占相應數(shù)據(jù)集維數(shù)D的10倍，最大迭代次數(shù)T設置為1800。交叉概率CR為0.5?？s放系數(shù)為0.6。在基于改進差分進化的K均值聚類算法的仿真實驗中，種群大小N也取相應數(shù)據(jù)集的維數(shù)D的10倍，最大迭代次數(shù)T也被設置為1800，交叉概率CR和縮放系數(shù)F按公式自適應取值。K-均值聚類算法、基于差分進化的K-均值聚類算法和基于改進差分進化的K-均值聚類算法這三個測試數(shù)據(jù)集用于進行35次仿真實驗。結果如表2所示。

表2 IRIS數(shù)據(jù)集上的實驗結果

對于Glass數(shù)據(jù)集，其實驗結果如表3所示。

表3 Glass數(shù)據(jù)集上的實驗結果

對Vowel數(shù)據(jù)集，實驗結果如表4所示。

表4 在Vowel數(shù)據(jù)集上的實驗結果

通過上述實驗結果，我們可以發(fā)現(xiàn)隨機選擇初始聚類中心的K-均值聚類算法的聚類結果波動范圍較大，穩(wěn)定性差。因此，實驗數(shù)據(jù)驗證了基于差分進化和改進算法的K-均值聚類算法大大提高了聚類結果的穩(wěn)定性和有效性，并且聚類質量得到了顯著提高。從結果分析可以看出，提出的算法的聚類結果和質量優(yōu)于基于標準差分進化的K均值聚類算法。改進算法的收斂速度比基于差分進化聚類算法的K-均值聚類算法的收斂速度快。

5 結語

針對基于差分進化的K均值聚類算法的缺陷，提出基于改進差分進化的K均值聚類算法，介紹改進算法的改進方案，步驟和具體流程。并對K-均值聚類算法、基于差分進化的K-均值聚類算法和改進算法進行仿真實驗。結果表明，該算法具有收斂快的優(yōu)點，不僅具有差分進化算法的全局優(yōu)化能力，而且具有K-均值聚類算法的優(yōu)點，搜索速度快，結果穩(wěn)定。