差分進化算法在極大熵聚類優化中的應用

文/林濤 廣東省電信規劃設計院有限公司 廣東廣州 510630

極大熵聚類算法(Maximum Entropy Clust ering，MEC)[1]是經典的模糊聚類方法，主要利用熵模型和最大熵定理設計目標函數。文獻[2]嚴格證明了MEC算法能夠收斂到目標函數的局部極小值，但未必能收斂到全局最優點上。

差分進化算法(Differential Evolution，DE)是一種智能優化方法，通過變異、交叉、選擇等處理和種群更替，最終在可行域中搜索出最優解。DE算法具有較強的全局搜索能力，常用于解決實際中的復雜優化問題。

本文借助DE算法的全局搜索能力，處理MEC算法目標函數的優化問題，提出一種基于差分進化的極大熵聚類算法，使其具有更好的聚類性能。

1、極大熵聚類算法

2、差分進化算法

DE算法是一種通過實數編碼，能在連續空間內進行策略搜索，實現全局尋優的優化方法，主要通過個體優勝劣汰和種群多樣性，驅使算法向全局最優解搜索。DE算法包括種群初始化、變異、交叉、選擇等步驟，具體如下：

（1）種群初始化：

DE算法首先要在可行域內隨機生成初始種群，個體以D維實數向量Xi,g表示，其中i表示第i個個體，，NP表示種群規模，表示進化代數。具體可按下式(4)隨機生成。

其中rand (0,1) 表示在[0,1]區間內生成隨機數。

(2)變異:

對于各個體 Xi,g，需要生成對應的變異向量 Di,g。能使算法具有較強全局搜索能力的 DE/rand/1 變異算子具體如下所示:

其中 Xr,g、Xr,g、Xr,g分別為從第 g 代種群中隨機選擇的三個個體，且縮放因子，通常

(3)交叉:

目標個體 Xi,g與變異向量Di,g經過交叉處理，得到試驗個體 Si,g，使算法能夠在不同區域中搜索。試驗個體按式(6)生成。

(4)選擇:

假設需要最小化函數f，算法需要從試驗個體 Si,g與目標個體 Xi,g中選擇一個進入下一代種群當中，通常基于貪婪策略，具體為。

3、基于差分進化的極大熵聚類算法

研究表明，若V 和U 滿足式(2)與式(3)，則它們必為式(1)的嚴格局部極小 值點，但由于 MEC 是迭代算法，其結果未必能收斂到目標函數全局最優點上。本 文針對其目標函數優化問題進行研究，利用 DE 算法的全局搜索能力，解決式(1) 的優化問題。

本文具體研究的優化問題為:

主要是有約束的優化問題，由于聚類中心主要分布在數據樣本內部，因此聚類中 心應滿足約束條件:

其中 Xk表示數據集X第k維數據。由于隸屬度和聚類中心都是實數值向量，需 要對個體向量進行編碼設計，本文采用基于聚類中心的編碼方式，具體如下:

其中i =1,2,...,NP。本文采用DE/rand/1變異算子和貪婪選擇策略，直接以式(1)作為適應值函數，結合隸屬度更新公式(3)，提出基于差分進化的極大熵聚類算 法。

基于差分進化的極大熵聚類算法流程:

輸出:種群中最優個體聚類中心與隸屬度矩陣。

setp1:令g=0;

step2:根據約束條件式(9)，通過式(4)隨機生成初始種群;

step3:對于種群中個體Vi,g，利用式(5)進行變異操作，得到變異向量Di,g;

step4:根據變異向量Di,g，利用式(6)進行交叉操作，得到試驗個體Si,g;

step5:對于種群中目標個體Vi,g與試驗個體Si,g，利用式(3)分別計算出對應的隸屬度矩陣UVi,g和USi,g，并代入目標函數式(1)計算適應值;

step6:根據所得到的適應值，利用式(7)進行選擇操作，并置 g=g+1;

4、實驗及結果分析

本文在 Iris、Wine、Seed、Breast 數據集上進行算法性能實驗，利用 RI、 NMI 指標評估聚類性能，以 MEC 作為對比算法，檢驗本文算法性能。各數據集的 具體實驗結果見表 1 和表 2。

?

結果表明，相比于MEC算法，本文算法在各數據集上，RI指標和NMI指標都略有提升，這說明DE算法應用到MEC算法上能夠有效提高優化處理，改善聚類效果。

結語：

本文針對MEC算法易陷入局部最優問題，利用DE算法對其目標函數進行有效優化，設計出一種基于差分進化的極大熵聚類算法。經過數據實驗檢驗，表明DE算法在一定程度上能更好地優化MEC目標函數。