聚类是将数据集中的样本划分为若干个通常不相交的子集, 每个子集称为“族”, 同一族中的对象具有较高的相似度, 不同族中的对象差别较大. 聚类分析已成为数据挖掘领域的研究热点问题, K均值算法(K-means)是一种经典的聚类算法, 因其受初始聚类中心的影响容易陷入局部最优等缺陷而限制了其应用范围. 许多学者提出一系列智能聚类算法, 如蜜蜂交配优化聚类算法^[1]、萤火虫聚类算法^[2]、差分进化聚类算法^[3]、布谷鸟聚类算法^[4]、弹性网络聚类算法^[5]、花朵授粉聚类算法^[6]、蝙蝠聚类算法^[7]、灰狼与郊狼混合优化算法^[8]、自适应细菌觅食聚类优化算法^[9]、拓展差异度的高维数据聚类算法^[10]、无人仓系统订单分批问题及K-max 聚类算法^[11]等. 各种改进算法均取得了一定成效, 但对于一些复杂问题仍存在精度不高和收敛速度慢等问题.

蝴蝶优化算法^[12](Butterfly Optimization Algorithm, BOA)是2018年Sankalap Arora提出一种新的全局优化算法, 其灵感来自于蝴蝶的觅食行为. 该行为由蝴蝶的合作向食物来源位置移动, 蝴蝶接收并感知空气中的气味以确定食物来源或交配伙伴的潜在方向, 但其本质不同于文献[13, 14]. 由于提出时间短, 国外可参考的文献很少, 国内暂无相关论文报道. 蝴蝶优化算法与其他群智能算法一样, 也存在收敛速度和易陷入局部最优等缺陷, 因此本文尝试提出了一种改进蝴蝶优化算法(Improved Butterfly Optimization Algorithm, IBOA), 首先描述了蝴蝶优化算法的特点及实施步骤, 重新定义蝴蝶优化算法的局部迭代公式, 再将遗传算法的轮盘赌选择、交叉操作和变异操作融入蝴蝶优化算法中, 通过标准的数据集测试验证IBOA算法的有效性.

1 基本的蝴蝶优化算法

蝴蝶优化算法是模拟蝴蝶的觅食行为, 该思想的条件假设如下:

1) 所有的蝴蝶都应该散发出某种香味, 使蝴蝶能够互相吸引.

2) 每只蝴蝶都会随机移动, 或朝着散发出更多香味的最佳蝴蝶移动.

3) 蝴蝶的刺激强度受目标函数值的影响或决定.

当蝴蝶能感觉到其他任何蝴蝶的香味时并朝它移动, 在该算法中, 该阶段称为全局搜索. 在另一种情况下, 当蝴蝶不能感觉周围的香味时, 然后它会随机移动这个阶段称为局部搜索. 利用转换概率 控制全局和局部搜索过程, 其迭代公式为:

$ f = {c^t}{I^a} $

(1)

${x_i^{t + 1} = x_i^t + \left( {{r^2} \times {g^*} - x_i^t} \right) \times {f_i}}$

(2)

${x_i^{t + 1} = x_i^t + \left( {{r^2} \times x_j^t - x_k^t} \right) \times {f_i}}$

(3)

${{{{c}}^{{{t + 1}}}} = {{{c}}^{{t}}} + \left( {{{b}}/{{{c}}^{{t}}} \times Ngen} \right)}$

(4)

式(1)中的 $f$ 是香味感知量, $c$ 是感觉形式, $I$ 是刺激强度, $a$ 是香味, 通常 $a$ 和 $c$ 的取值范围为[0, 1]之间; 式(2)中的 $x_i^{t + 1}$ 表示第 $i$ 只蝴蝶在第 $t + 1$ 代的位置, $r \in [0,1]$ 的随机数, ${g^ * }$ 表示全局最优解, ${f_i}$ 表示第 $i$ 只蝴蝶的香味感知量; 式(3)中的 $x_i^t$ , $x_j^t$ , $x_k^t$ 分别表示第 $i,j,k$ 只蝴蝶在第 $t$ 代的位置; 式(4)中的 $b$ 为常数, ${{{c}}^{{t}}}$ , 表示第 $t$ 代的值, Ngen为最大迭代次数.

基于上述描述, 蝴蝶优化算法的实施步骤如下:

Step 1. 初始化种群规模 $n$ 及转换概率 $p$ 等参数.

Step 2. 利用式(5)计算每只蝴蝶的适应度值, 并求出当前最优值f_min和最优解Best.

Step 3. 利用式(1)计算香味感知量, 如果rand<p, 则利用式(2)计算 $x_i^t$ , 否则利用式(3)计算 $x_i^t$ .

Step 4. 利用式(5)重新计算每只蝴蝶的适应度值F_new, if F_new<f_min, 则替换之前的最优值和最优解.

Step 5. 利用式(4)更新 $c$ .

Step 6. 判断是否达到最大迭代次数, 如果是输出最优值和最优解, 否则跳至Step 3.

2 改进的蝴蝶优化算法

由于基本的BOA算法聚类效果差, 本文对其进行改进, 提出一种改进的蝴蝶优化聚类算法. 重新定义蝴蝶的局部搜索方式, 同时结合轮盘赌选择、交叉操作和变异操作, 提高算法的寻优能力, 使聚类效果稳定.

2.1 编码方法

采用实数编码, 一只蝴蝶的位置表示一组聚类中心, 假设有 $m$ 个聚类中心, 数据集的属性有 $d$ 个, 则每只蝴蝶的维数为 $nd = d \times m$ . 则第 $t$ 代蝴蝶 $i$ 的位置编码为 ${x_i}(t) = [{c_1}(t),{c_2}(t), \cdots, {c_m}(t),]$ , 其中 ${c_j}(t)$ 表示第 $t$ 代蝴蝶的第 $j$ 个聚类中心, $j = 1,2, \cdots ,m$ .

2.2 评价函数

本文采用如下的聚类准则作为适应度值:

$f({x_i}(t)) = \min \sum\limits_{i = 1}^{{n_c}} {\sum\limits_{j = 1}^m {||{y_i} - {c_j}(t)||} } $

(5)

其中, ${n_c}$ 为聚类样本数, ${y_i}$ 为第 $i$ 个样本, $f({x_i}(t))$ 表示所有数据到聚类中心的最小值, 值越小表示聚类效果越好.

2.3 重新定义迭代公式

鉴于基本的蝴蝶优化算法局部寻优能力较差, 故结合精英策略将式(3)重新定义如下:

$x_i^{t + 1} = x_i^t + r \times (x_j^t - x_k^t) + r \times ({g^ * } - x_i^t)$

(6)

式(6)中 ${g^ * }$ 为全局最优解即为精英, 其他蝴蝶在精英附近进行搜索, 因此能提高算法的精度.

为了提高聚类效果和鲁棒性, 融合遗传算法相关操作.

2.4 轮盘赌选择

1) 计算每只蝴蝶的适应度值Fitness;

2) 计算每只蝴蝶被遗传到下一代的概率p;

3) 计算每只蝴蝶的累加概率q;

4) 在蝴蝶种群中对每一个体产生一个随机数 $r \in [0,1]$ , 执行temp=find(r<q), $x_i^{t + 1} = $ $x_i^t(temp(1),:)$ .

2.5 交叉操作

1) 在蝴蝶种群中随机选择两个父类 $x_{j + 1}^t$ , $x_{j }^t$ , 设置交叉概率p_c;

2) 若r<pc, 随机产生一个交叉点point; $temp = x_j^t$ ;

3) $x_j^t(:,po{{int}} + 1:nd) = x_{j + 1}^t(:,po{{int}} + 1:nd)$ $x_{j + 1}^t(:, po{{int}} + 1:nd) = temp$ .

2.6 变异操作

设 ${x_i} = ({x_{i1}},{x_{i2}}, \cdots ,{x_{id}},{x_{id + 1}}, \cdots ,{x_{ie}}, \cdots ,{x_{in}})$ , 随机选取两个位置 ${x_{id}}$ 和 ${x_{ie}}$ , 将两个位置之间的元素进行逆转操作, 变换后的位置为 ${x'_i} = $ $({x_{i1}},{x_{i2}}, \cdots ,{x_{ie}}, {x_{ie - 1}}, \cdots , {x_{id}}, \cdots ,{x_{in}})$ .

2.7 IBOA实施步骤

IBOA算法求解聚类问题的步骤:

Step 1. 初始化种群规模、转换概率、迭代次数N_iter和交叉概率p_c等参数.

Step 2. 计算每只蝴蝶的适应度值, 并求出当前最优值f_min和最优解Best.

Step 3. 利用式(1)计算香味感知量, 如果rand<p, 则利用式(2)计算, 否则利用式(6)计算.

Step 4. 重新计算每只蝴蝶的适应度值F_new, if F_new<f_min, 则替换之前的最优值和最优解.

Step 5. 执行轮盘赌选择、交叉操作和变异操作. 重新计算每只蝴蝶的适应度值F_new, if F_new<f_min, 则替换之前的最优值和最优解.

Step 6. 利用式(4)更新.

Step 7. 判断是否达到最大迭代次数, 如果是输出最优值和最优解, 否则跳至Step 3.

3 实验分析 3.1 实验环境与参数设置

为了测试IBOA算法的正确性与有效性, 选取6个基准测试函数来验证算法, 包括1个人工数据集和5个从UCI ( http://archive.ics.uci.edu/ml/index.php)数据库中选取了Iris、Wine、Glass、Cancer、Cintraceptive Method Choice (简称CMC) 5组实验数据, 所有的实例均运行在处理器为Celeron(R)双核CPU T3100, 1.90 GHz、内存为4G的PC上, 以Matlab R2010a编写代码. 参数设置为: 种群规模 ＝50、转换概率 ＝0.1、c的初值为0.01, 迭代次数N_iter＝200和交叉概率pc＝0.85. 在问题规模一致的情形下, 这些算法的复杂度是相同的.

3.2 测试实例结果比较

(1)人工数据集1 (set_data=250, d=3, K=5): 为了展示IBOA的求解过程, 分别计算第10代、第50代的求解结果如图1和图2中. 并将算法独立运行20次的结果于表1中, Best表示最优解, Average表示平均解, Worst表示最差解, Std表示标准差.表1中其他算法与数据来源于文献[7], 从表1中的计算结果可知IBOA的求解精度及鲁棒性均优于其他算法.

(2)UCI数据集: 将算法独立运行20次, 与近几年多种算法比较如表2–表7所示, 其中表2–表6中的K-means、GA、ACO、PSO、HBMO、IDE算法数据来源于文献[3]且迭代次数为500时的计算结果, IBA算法数据来源于文献[7], IGSO算法数据来源于文献[2], BPFPA算法数据来源于文献[6]; 表7中K-means、PSO、ABC、BA和IBA算法数据来源于文献[7]. 从表2可知, IBOA算法求解效果与IBA、BPFPA相当, 但比其余8种算法效果较好; 从表3可知, IBOA算法与BPFPA求解效果相当, 但比其余7种算法效果优越许多; 文中的“－”表示未有相关数据. 从表4可知, IBOA的求结果在迭代次数为200时优于IDE和其他算法; 从表5可知, IBOA算法的精度和方差均优于其他算法; 从表6可知, IBOA算法的求解效果差于IDE, 与IBA、BPFPA效果相当, 但优于其他算法; 从表7可知, IBOA算法的求解效果与IBA、BPFPA相当, 但优于其他算法. 另外, 图3展示了IBOA算法和BOA算法在Survival数据集的最优解收敛曲线图, 从图3易知, IBOA算法的求解速度和精度较BOA算法高.IBOA求解Iris、Survival、CMC数据集的聚类效果图如图4–图6所示.

4 结论

本文将精英策略的思想重新定义蝴蝶优化算法的局部搜索迭代公式且遗传算法相结合提出了一种改进的蝴蝶优化聚类算法, 通过求解1个人工数据集和5个UCI数据库中不同规模的数据, 统计分析结果表明IBOA算法能够避免陷入局部最优, 具有较快的收敛速度和较强的鲁棒性, 能够有效解决聚类问题且与其他聚类算法相比具有一定优势.