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

王鳳領 梁海英 張 波

（賀州學院數學與計算機學院 賀州 542899）

1 引言

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

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

2 差分進化算法

2.1 研究現狀

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

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

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

1）種群初始化

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

2）變異操作

令種群大小為N，當前進化個體Xi(t)(i=1，2，…，N)表示，t為當前進化個數。隨機選擇三個不同的個體，從當前進化群體中，并滿足條件 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為控制擾動因子的縮放系數。群體中個體由D個分量組成，那么變體個體Vi(t)也由D個分量組成，即Vi(t)=vr1(t)，vr2(t)，…，viD(t))。

3）交叉操作

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

4）選擇操作

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

5）參數設定

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

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

1）步驟

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

步驟1:完成種群初始化，設群體大小N，縮放因子F∈［0，2］，交叉概率 CR∈［0，1］，進化代數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:對于最小化求解問題，具有小適應度函數值的個體進入下一代種群中繼續進化。采取貪心策略，在選擇操作過程中，擇優選取，比較當前進化個體Xi(t)與相對應中間試驗個體的適應度值。選擇方式按式 Xi(t+1)進行；

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

2）算法流程

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

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

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

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

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

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

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

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

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

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

步驟2種群初始化:從數據集K數據樣本中隨機選取個體作為初始種群，重復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)為縮放系數。

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

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

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

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

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

步驟9輸出聚類結果。

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

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

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

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

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

4.1 改進方案

1）加強局部搜索能力

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

2）采用動態縮放系數

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

其中，Fmin為最小縮放系數，且Fmin=0.4，Fmax為最大縮放系數，且Fmax=0.9。t為當前進化的代數，TMAX為算法設定的最大進化代數。

3）采用動態交叉概率

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

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

4.2 算法描述

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

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

算法描述如下:

輸入:含有n個數據對象的數據集X、聚類數目K、種群規模N。

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

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

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

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

步驟3:變異操作，根據個體基因位進行變異，個體 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))為縮放系數，按照公式 F=(Fmax-Fmin)執行動態遞減策略取值。

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

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

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

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

步驟8:輸出聚類結果。

4.3 算法流程

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

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

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

4.4 實驗結果及分析

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

表1 測試數據集特征描述

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

表2 IRIS數據集上的實驗結果

對于Glass數據集，其實驗結果如表3所示。

表3 Glass數據集上的實驗結果

對Vowel數據集，實驗結果如表4所示。

表4 在Vowel數據集上的實驗結果

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

5 結語

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