文/林涛 广东省电信规划设计院有限公司 广东广州 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目标函数。