基于差分進化的加權k-means 算法研究

王鳳領

（賀州學院， 廣西 賀州542899）

0 引 言

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

1 差分進化算法

差分進化算法作為優化算法的一種，具有變異、交叉和選擇操作。 差分進化算法還具有控制參數少、收斂速度快、原理簡單、全局優化能力突出等優點，其獨特的差分變異操作可以保證種群的多樣性，并能使種群向更好的方向發展。

1.1 差分進化算法的特點

（1）通用性。 無需問題的先驗信息。 可用實數編碼問題的可行解，并且不依賴于問題的信息。

（2）易于實現，結構簡單。

（3）控制較少的參數。

（4）局部搜索和全局搜索協同搜索。

（5）具有記憶能力，能夠記住群體搜索過程中個體的最優解。

（6）易于與其他算法相結合，構建性能更好的混合算法。

1.2 差分進化算法的步驟和過程

1.2.1 步驟

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

第一步 完成種群初始化，設置群體大小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）｝；

第二步 計算出每個體的適應度值f（Xi（t）），評價種群中的每個個體；

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

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

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

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

1.2.2 算法流程

根據差分進化算法的描述，獲得差分進化算法的如圖1 所示的流程圖。

圖1 差分進化算法的流程圖Fig. 1 Flow chart of differential evolution algorithm

2 k-means 聚類算法

2.1 k-means 聚類算法概述

k-means 是Hartigan 提出的一種基于劃分的聚類方法，是一種基于距離劃分的聚類算法。 距離作為相似性評價標準。 當兩物體間的距離較近時，它們之間的距離就較小，其相似度較高。

2.2 k-means 算法的缺點

（1）容易陷入局部最優解；

（2）易受孤立點的影響；

（3）算法對初始中心選擇具有隨機性。

2.3 k-means 聚類算法步驟

k-means 聚類算法就是將n個數據樣本對象分割成k個類別，把聚類個數k作為輸入參數，使不同的類別間數據點的相似性盡可能小，每個類別內的數據點相似性盡可能大［1］。

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

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

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

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

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

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

步驟3 公式（8），重新進行計算k個聚類中心的值。

步驟4 若目標函數公式（9）最小或保持不變，則迭代結束。

3 基于差分進化的加權k-means 算法

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

3.1 基于差分進化的初始聚類中心選擇

隨機從數據樣本中選擇一組數據作為初始聚類中心，構建初始種群進行編碼。 對差分進化算法變異、交叉和選擇操作，推導得到最佳個體。 通過對最佳個體進行解碼，從而得到k-means 聚類的最佳初始聚類中心［3］。

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

算法的具體步驟：

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

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

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

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

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

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

其中CR為交叉概率，且CR∈［0，1］，γ為［1，k］之間隨機產生的一個整數，β為0～1 間滿足均勻分布且隨機產生的一個數。

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

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

3.2 加權歐幾里德距離

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

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

xjl為第j個樣本的第l個分量，為樣本數據集中每個數據對象的第l個分量之和的平均值，ω是一個反映樣本數據整體分布特性的權值。

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

3.3 基于差分進化的加權k-means 算法的步驟

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

基于差分進化的加權k-means 算法流程如圖4所示。

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

算法的步驟描述：

步驟1 輸入n個樣本的數據、聚類個數k和控制參數Np、α、Cp。

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

步驟3 根據改進的歐氏距離公式（17），計算每個數據樣本到各聚類中心的距離，將每樣本劃分到最小距離的類別當中。

步驟4 根據公式（8），重新計算k個聚類中心的值。

步驟5 若滿足改進的目標函數公式（15）最小或保持不變，迭代結束；否則，返回步驟3 繼續執行。

4 實驗仿真與結果分析

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

表1 四組UCI 數據集Tab. 1 Four sets of UCI data sets

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

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

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

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

5 結束語

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