王鳳領(lǐng)

（賀州學(xué)院， 廣西 賀州542899）

0 引 言

差分進(jìn)化算法是Storn.R 和Price.K 在1995 年提出的基于種群進(jìn)化的啟發(fā)式算法，是隨機(jī)并行全局搜索算法。 它具有記憶個(gè)體最優(yōu)解和在群體中共享信息的特點(diǎn)，即通過群體中個(gè)體之間的合作和競(jìng)爭(zhēng)來解決優(yōu)化問題。 差分進(jìn)化算法具有易于理解、簡(jiǎn)單高效、易于使用、魯棒性好、收斂速度快、全局搜索能力強(qiáng)等優(yōu)點(diǎn)。 目前，差分進(jìn)化算法已成功應(yīng)用于許多研究領(lǐng)域，并取得了較好的效果。

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

差分進(jìn)化算法作為優(yōu)化算法的一種，具有變異、交叉和選擇操作。 差分進(jìn)化算法還具有控制參數(shù)少、收斂速度快、原理簡(jiǎn)單、全局優(yōu)化能力突出等優(yōu)點(diǎn)，其獨(dú)特的差分變異操作可以保證種群的多樣性，并能使種群向更好的方向發(fā)展。

1.1 差分進(jìn)化算法的特點(diǎn)

（1）通用性。 無需問題的先驗(yàn)信息。 可用實(shí)數(shù)編碼問題的可行解，并且不依賴于問題的信息。

（2）易于實(shí)現(xiàn)，結(jié)構(gòu)簡(jiǎn)單。

（3）控制較少的參數(shù)。

（4）局部搜索和全局搜索協(xié)同搜索。

（5）具有記憶能力，能夠記住群體搜索過程中個(gè)體的最優(yōu)解。

（6）易于與其他算法相結(jié)合，構(gòu)建性能更好的混合算法。

1.2 差分進(jìn)化算法的步驟和過程

1.2.1 步驟

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

第一步 完成種群初始化，設(shè)置群體大小N，縮放因子F∈［0，2］，交叉概率CR∈［0，1］，進(jìn)化代數(shù)t ＝0， 隨 機(jī) 生 成 初 始 種 群X（0）＝｛X1（0），X2（0），...，XN（0）｝，其中，任一個(gè)體Xi（0） 包含D個(gè) 分 量 的 向 量， 即Xi（0）＝｛Xi1（0），Xi2（0），...，XiD（0）｝；

第二步 計(jì)算出每個(gè)體的適應(yīng)度值f（Xi（t）），評(píng)價(jià)種群中的每個(gè)個(gè)體；

第三步 根據(jù)式（1）完成種群個(gè)體Xi（t） 變異操作，得到變異個(gè)體Vi（t）；

第四步 根據(jù)式（2）完成交叉操作，得到中間測(cè)試個(gè)體Ui（t），Ui（t） 是由D 維分量組成，即Ui（t）＝（ui1（t），ui2（t），...，uiD（t））。

第五步 對(duì)于最小化求解問題，適應(yīng)度函數(shù)值小的個(gè)體進(jìn)入下一代種群中繼續(xù)進(jìn)化。 在選擇操作過程中，采取貪心策略，進(jìn)行最佳選擇，通過比較當(dāng)前進(jìn)化個(gè)體Xi（t） 與相對(duì)應(yīng)中間試驗(yàn)個(gè)體的適應(yīng)度值。 選擇方式按照公式（3）進(jìn)行

第六步 檢驗(yàn)種群X（t +1） 中的個(gè)體，如果終止算法滿足條件，則輸出；否則t ＝t +1， 轉(zhuǎn)到步驟二。

1.2.2 算法流程

根據(jù)差分進(jìn)化算法的描述，獲得差分進(jìn)化算法的如圖1 所示的流程圖。

圖1 差分進(jìn)化算法的流程圖Fig. 1 Flow chart of differential evolution algorithm

2 k-means 聚類算法

2.1 k-means 聚類算法概述

k-means 是Hartigan 提出的一種基于劃分的聚類方法，是一種基于距離劃分的聚類算法。 距離作為相似性評(píng)價(jià)標(biāo)準(zhǔn)。 當(dāng)兩物體間的距離較近時(shí)，它們之間的距離就較小，其相似度較高。

2.2 k-means 算法的缺點(diǎn)

（1）容易陷入局部最優(yōu)解；

（2）易受孤立點(diǎn)的影響；

（3）算法對(duì)初始中心選擇具有隨機(jī)性。

2.3 k-means 聚類算法步驟

k-means 聚類算法就是將n個(gè)數(shù)據(jù)樣本對(duì)象分割成k個(gè)類別，把聚類個(gè)數(shù)k作為輸入?yún)?shù)，使不同的類別間數(shù)據(jù)點(diǎn)的相似性盡可能小，每個(gè)類別內(nèi)的數(shù)據(jù)點(diǎn)相似性盡可能大［1］。

設(shè)有n個(gè)數(shù)據(jù)樣本∈Rd為待聚類數(shù)據(jù)集，d 維向量xjT。 尋找一個(gè)包含k個(gè)聚類中心的集合C ＝c1，(c2，…，ck)T，并最小化目標(biāo)函數(shù)，公式（4）：

其中，Si是第i個(gè)類別中樣本集，ci是Si內(nèi)所有樣本xj的聚類中心點(diǎn)，d（xj，ci） 為樣本數(shù)據(jù)xj與聚類中心ci之間的歐氏距離，其定義如公式（5）：

其中，ci為第i個(gè)類的中心位置，i ＝1，2，...，k，xj代表屬于類ci中的樣本數(shù)據(jù)，ni是類ci中樣本數(shù)據(jù)的個(gè)數(shù)。

如圖2 所示，k-means 聚類算法的流程圖。

圖2 k-means 聚類算法流程圖Fig. 2 Flow chart of K-means clustering algorithm

步驟1 每個(gè)數(shù)據(jù)樣本為一個(gè)初始聚類中心，隨機(jī)選取k個(gè)樣本數(shù)據(jù)，初始聚類中心的集合為C ＝(c1，c2，…，ck)T。步驟2 根據(jù)歐氏距離公式（7）， 從每個(gè)數(shù)據(jù)樣本到每個(gè)聚類中心的距離計(jì)算每個(gè)剩余樣本數(shù)據(jù)，并劃分為距離最小的類別。

步驟3 公式（8），重新進(jìn)行計(jì)算k個(gè)聚類中心的值。

步驟4 若目標(biāo)函數(shù)公式（9）最小或保持不變，則迭代結(jié)束。

3 基于差分進(jìn)化的加權(quán)k-means 算法

k-means 算法對(duì)初始聚類中心的選擇很敏感，為了解決異常點(diǎn)使聚類結(jié)果不穩(wěn)定問題，采用差分進(jìn)化算法選擇最佳數(shù)據(jù)點(diǎn)，并確定初始聚類中心。給每個(gè)樣本賦予一個(gè)權(quán)重值根據(jù)每個(gè)樣本的重要性，得到加權(quán)歐氏距離，增加數(shù)據(jù)屬性間的區(qū)分度，來減少異常點(diǎn)等造成的不利影響［2］。

3.1 基于差分進(jìn)化的初始聚類中心選擇

隨機(jī)從數(shù)據(jù)樣本中選擇一組數(shù)據(jù)作為初始聚類中心，構(gòu)建初始種群進(jìn)行編碼。 對(duì)差分進(jìn)化算法變異、交叉和選擇操作，推導(dǎo)得到最佳個(gè)體。 通過對(duì)最佳個(gè)體進(jìn)行解碼，從而得到k-means 聚類的最佳初始聚類中心［3］。

基于差分進(jìn)化的初始聚類中心選擇流程如圖3所示。

算法的具體步驟：

（1）初始化群體。 假設(shè)樣本數(shù)據(jù)為d維，種群的每個(gè)個(gè)體是k×d ＝D維向量。 從樣本數(shù)據(jù)中隨機(jī)選取k個(gè)樣本作為一組聚類中心，進(jìn)行重復(fù)執(zhí)行Np次，構(gòu)造初始種群通過實(shí)數(shù)編碼［4］。 每個(gè)個(gè)體包含一組k個(gè)聚類中心，Np為種群規(guī)模，代表Np個(gè)個(gè)體，在初始化種群時(shí)，取進(jìn)化代數(shù)g ＝0，編碼方式如式（10）所示：

其中j ＝1，2，…，Np，Xj（0） 表示初始種群的第j個(gè)個(gè)體，Xji(i ＝1，2，…，k) 表示第j個(gè)體的第i個(gè)聚類中心。

（2）變異操作。 一個(gè)聚類中心相當(dāng)于一個(gè)基因位置，變異操作是根據(jù)個(gè)體的基因位置進(jìn)行的，從當(dāng)前種群Xj(g) 中隨機(jī)選取3 個(gè)個(gè)體，即Xa(g) ，Xb(g) ，Xc(g) ，且a≠b≠c≠j，變異個(gè)體νj(g')＝(νj1(g′) ，νj2(g′) ，…，νjD(g′)) ，且g′ ＝g +1，種群中的每個(gè)個(gè)體的基因位如公式（11）所示：

其中，i ＝1，2，…，k，a∈［0，1］ 為縮放系數(shù)。

圖3 基于差異進(jìn)化的初始聚類選擇Fig. 3 Initial cluster selection based on differential evolution

（3）交叉操作。 當(dāng)前個(gè)體Xj(g) 和變異個(gè)體νji(g +1) 進(jìn)行交叉操作來獲得中間個(gè)體Mj(g +1)＝（mj1(g +1) ，mj2(g +1) ，…，mjk（g +1）），中間個(gè)體的第i分量如下公式（12）：

其中CR為交叉概率，且CR∈［0，1］，γ為［1，k］之間隨機(jī)產(chǎn)生的一個(gè)整數(shù)，β為0～1 間滿足均勻分布且隨機(jī)產(chǎn)生的一個(gè)數(shù)。

（4）選擇操作。 采用貪婪算法選擇進(jìn)入下一代群體的個(gè)體，比較當(dāng)前進(jìn)化個(gè)體Xj(g) 與其對(duì)應(yīng)的中間試驗(yàn)個(gè)體Mj(g +1) 的適度值，公式（13）。

（5） 算 法 終 止 判 斷。 進(jìn) 行 檢 驗(yàn) 種 群X(g +1) 中的個(gè)體，若滿足算法終止條件，輸出最佳個(gè)體，否則返回到第二步繼續(xù)操作，一直到輸出最佳個(gè)體為止。

3.2 加權(quán)歐幾里德距離

k-means 聚類分析中，每個(gè)樣本數(shù)據(jù)對(duì)聚類結(jié)果的影響程度不同，雖然差分進(jìn)化算法可以為k-means算法選擇更合適的初始聚類中心，由于異常點(diǎn)的存在，聚類結(jié)果仍會(huì)受到很大影響，k-means聚類算法沒有考慮到每個(gè)樣本對(duì)聚類結(jié)果的影響［5］。 為了解決這一問題，本文提出了一種加權(quán)的歐氏距離，根據(jù)每個(gè)樣本的重要性給每個(gè)參與聚類的樣本賦予一個(gè)權(quán)重值，從而減少異常點(diǎn)等因素對(duì)聚類結(jié)果的影響［6］。

定義權(quán)值ω ＝［ω1，ω2，…，ωn］T∈Rn×d，d 維向量：ωj＝［ωj1，ωj2，…，ωjd］T。 對(duì)公式（7）引入權(quán)值ω來加以區(qū)分對(duì)每個(gè)樣本數(shù)據(jù)與聚類中心之間的關(guān)系，改進(jìn)后為公式（14）

xjl為第j個(gè)樣本的第l個(gè)分量，為樣本數(shù)據(jù)集中每個(gè)數(shù)據(jù)對(duì)象的第l個(gè)分量之和的平均值，ω是一個(gè)反映樣本數(shù)據(jù)整體分布特性的權(quán)值。

為了保持形式與k-means 算法的歐氏距離公式一致，對(duì)公式（15）經(jīng)過變換以獲得公式（17）：

3.3 基于差分進(jìn)化的加權(quán)k-means 算法的步驟

該算法需要確定聚類數(shù)k， 在基于差分進(jìn)化選擇初始聚類中心之前，選擇固定參數(shù)：種群規(guī)模Np∈［5D，10D］，縮放因子α∈［0.5，1］，交叉概率Cp∈［0.8，1］。

基于差分進(jìn)化的加權(quán)k-means 算法流程如圖4所示。

圖4 基于差分進(jìn)化的加權(quán)k-means 算法流程圖Fig. 4 Flow chart of weighted k -means algorithm based on differential evolution

算法的步驟描述：

步驟1 輸入n個(gè)樣本的數(shù)據(jù)、聚類個(gè)數(shù)k和控制參數(shù)Np、α、Cp。

步驟2 釆用基于差分進(jìn)化的初始聚類中心的選擇算法來進(jìn)行選取初始聚類中心。

步驟3 根據(jù)改進(jìn)的歐氏距離公式（17），計(jì)算每個(gè)數(shù)據(jù)樣本到各聚類中心的距離，將每樣本劃分到最小距離的類別當(dāng)中。

步驟4 根據(jù)公式（8），重新計(jì)算k個(gè)聚類中心的值。

步驟5 若滿足改進(jìn)的目標(biāo)函數(shù)公式（15）最小或保持不變，迭代結(jié)束；否則，返回步驟3 繼續(xù)執(zhí)行。

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

在UCI 實(shí)驗(yàn)本文選擇4 個(gè)數(shù)據(jù)集。 其中，數(shù)據(jù)集名稱、類別數(shù)目、樣本總數(shù)和屬性維數(shù)見表1。 為了說明本文提出的算法的有效性，首先利用機(jī)器學(xué)習(xí)領(lǐng)域的數(shù)據(jù)集對(duì)四組實(shí)驗(yàn)數(shù)據(jù)進(jìn)行了分析和比較［7-8］。 實(shí)驗(yàn)結(jié)果表明，樣本數(shù)據(jù)集中包含的每個(gè)數(shù)據(jù)的屬性維數(shù)、樣本總數(shù)和類別數(shù)都相等。 與Uk-means算法、k-means 算法的聚類結(jié)果比較，算法迭代次數(shù)、聚類精度和收斂時(shí)間的比較結(jié)果見表2～表4。

表1 四組UCI 數(shù)據(jù)集Tab. 1 Four sets of UCI data sets

表2 3 種方法的迭代次數(shù)Tab. 2 Iterations of three methods

表3 3 種方法的聚類精度Tab. 3 Clustering accuracy of three methods

表4 3 種方法的收斂時(shí)間Tab. 4 Convergence time of three methods

在保證更好聚類精度的前提下，對(duì)于這四組不同的數(shù)據(jù)集，該算法收斂速度提高得更明顯。 從表2～表4 的實(shí)驗(yàn)仿真結(jié)果可以看出，該算法對(duì)四組UCI 數(shù)據(jù)集進(jìn)行聚類，能夠獲得較好的聚類結(jié)果。算法對(duì)目標(biāo)函數(shù)的歐氏距離判別公式增加了權(quán)值，使得一些異常點(diǎn)與聚類中心間的歐氏距離增加，算法的每次迭代更接近真實(shí)數(shù)據(jù)的劃分，分布不明顯且難以分類的數(shù)據(jù)更有利于聚類，提高了聚類精度，減少了算法的迭代次數(shù)，加快了收斂速度。

5 結(jié)束語

本文提出了一種基于差分進(jìn)化的加權(quán)k-means算法，并進(jìn)行了實(shí)驗(yàn)仿真和結(jié)果分析。 采用差分進(jìn)化算法優(yōu)先選擇初始聚類中心，在保證聚類中心選擇多樣性的前提下，使初始聚類中心的選擇更接近最終聚類中心；根據(jù)每個(gè)樣本參與聚類的重要性，給出每個(gè)樣本通過權(quán)值得到加權(quán)歐氏距離，增加了數(shù)據(jù)屬性間的差異，降低了異常點(diǎn)對(duì)聚類結(jié)果的影響。同與其他算法比較，該算法選擇的初始聚類中心更接近最終的聚類中心，保證聚類精度的同時(shí)提高了計(jì)算效率。