聚类分析作为数学挖掘领域的重要研究方向之一，通过获得样本数据的分布状况，分析每一类样本数据的特征并作进一步的分类。著名学者Ruspini^[1]在1969年首先提出了模糊划分的概念，将模糊集理论引入到聚类分析中。在模糊聚类分析方法中，应用最广泛的是由Dunn^[2]提出并由Bezdek^[3]推广的模糊C均值(Fuzzy C-Means, FCM)，依据样本间的相似度而得到数据的划分。研究学者在FCM的基础上引入核函数，将非线性不可分数据变换到到高维空间中的可分数据集, 提出了一种基于划分的核模糊C均值聚类(Kernel-based Fuzzy C-Means, KFCM)算法。通过最小化目标函数得到各样本点与其各聚类中心的隶属度, 一定程度上克服了对样本数据内在形状分布的依赖，解决了FCM不能发现非凸聚类结构问题。由于思路简单、收敛速度等优点，KFCM目前在模式识别、图像处理^[4-5]、医学诊断^[6]、生物信息学^[7]、人口统计^[8]等相关领域广泛应用。但该算法仍然存在对初始聚类中心敏感、聚类精度较低、在迭代时易陷入局部最优等问题，吸引了大量专家学者的探索与改进。文献[9]通过最小化簇内的分散和同时最大化属性权重的熵来改进目标函数，提高聚类的准确性。文献[10]利用改进的自适应遗传算法优化模糊核聚类算法，避免传统核模糊聚类容易陷入局部最优问题。文献[11]提出了增量核模糊聚类，通过优化初始聚类中心，为每个数据块提高聚类结果的质量。

群体智能在全局优化领域中占有优势地位，Karaboga通过仿效蜜蜂觅食行为来解决数值优化问题，提出了人工蜂群(Artificial Bee Colony, ABC)算法。人工蜂群算法具有易于实现、构架简单，以及鲁棒性强等优点，备受众多学者的关注，在标准ABC算法上作出了延伸与改进。文献[12]引入了两个新的搜索方程，在雇佣蜂和跟随蜂阶段中产生候选解，在每一次迭代过程中被分配更多的资源，提高算法的收敛速度和开采能力。文献[13]融合差分进化(Differential Evolution, DE)算法与人工蜂群算法，利用差分进化算法的鲁棒性强和进化速度快的特点，提高算法的收敛性以及改进其开采能力。文献[14]在侦查蜂更新阶段引入广义反向学习策略，从而提高算法的全局收敛性。

鉴于此，将人工蜂群优化算法引入到核模糊聚类中，达到快速收敛、优化聚类精度的目的。本文提出一种基于改进人工蜂群的核模糊聚类的算法。该算法在人工蜂群算法的雇佣蜂阶段，利用每次迭代所产生的当前维度最优解，根据离最优解的距离动态来改变人工蜂群的搜索距离，并构造新的适应度函数平衡类内和类间距离。通过3组Benchmark测试函数和6组经典UCI(University of California-Irvine)的实验数据集的仿真实验，验证了提出的改进人工蜂群算法在函数优化问题上的优势，同时解决了核模糊聚类对于初始中心敏感和容易陷入局部最优的问题，提高聚类精度和鲁棒性。

1 基本算法 1.1 核模糊C均值算法

核模糊C均值算法通过最小化目标函数将含有n个样本点的向量x_j(j=1, 2, …, n)划分到c个类别中。v_i(i=1, 2, …, c)表示第i个聚类的中心，u_ij(i=1, 2, …, c; j=1, 2, …, n)表示第j个样本属于第i类的隶属度。

KFCM步骤:

1) 设置聚类数目c，模糊度m的值，目标函数允许最小误差ε，最大迭代次数T。

2) 初始化c个聚类中心，在n个样本点中随机选取c个数据进行聚类中心初始化。

3) 直至目标函数|J(t)-J(t-1)| < ε结束聚类。

① 聚类目标函数：

$ J=\sum\limits_{i=1}^{n}{\sum\limits_{j=1}^{c}{{{\left( {{u}_{ij}} \right)}^{m}}}{{\left\| \varphi \left( {{\mathit{\boldsymbol{x}}}_{\mathit{j}}} \right)-\varphi \left( {{\mathit{\boldsymbol{v}}}_{\mathit{j}}} \right) \right\|}^{2}}} $

(1)

原始输入数据通过非线性映射函数φ(x)映射到高维特征空间中再进行聚类，核函数采用高斯函数。

$ {\rm{||}}\varphi ({\mathit{\boldsymbol{x}}_j}) - \varphi ({\mathit{\boldsymbol{v}}_j})|{|^2} = K({\mathit{\boldsymbol{x}}_j}, {\mathit{\boldsymbol{x}}_j}) - 2K({\mathit{\boldsymbol{x}}_j}, {\mathit{\boldsymbol{v}}_j}) + K({\mathit{\boldsymbol{v}}_j}, {\mathit{\boldsymbol{v}}_j}) $

(2)

对于高斯函数，当K(x, x)=1时，式(1) 可表示为：

$ J = \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^c {{{\left( {{u_{ij}}} \right)}^m}\left( {1 - K\left( {{\mathit{\boldsymbol{x}}_j}, {\mathit{\boldsymbol{v}}_j}} \right)} \right)} } $

(3)

② 聚类中心

$ {\mathit{\boldsymbol{v}}_j} = \left( {\sum\limits_{i = 1}^n {v_{ij}^mK\left( {{\mathit{\boldsymbol{x}}_j}, {\mathit{\boldsymbol{v}}_j}} \right){\mathit{\boldsymbol{x}}_j}} } \right)/\left( {\sum\limits_{i = 1}^n {v_{ij}^mK\left( {{\mathit{\boldsymbol{x}}_j}, {\mathit{\boldsymbol{v}}_j}} \right)} } \right) $

(4)

③ 隶属度

$ {u_{ij}} = \frac{{1 - K{{\left( {{\mathit{\boldsymbol{x}}_j}, {\mathit{\boldsymbol{v}}_j}} \right)}^{ - 1/\left( {m - 1} \right)}}}}{{\sum\limits_{k = 1}^c {{{\left( {1 - K\left( {{\mathit{\boldsymbol{x}}_j}, {\mathit{\boldsymbol{v}}_j}} \right)} \right)}^{ - 1/\left( {m - 1} \right)}}} }} $

(5)

隶属度满足约束条件$\sum\limits_{j = 1}^c {{u_{ij}} = 1} $且u_ij∈[0,1]。

1.2 人工蜂群算法

在人工蜂群算法中，首先引入蜜源，代表优化问题的各种可行解，用可行解的质量即适应度函数值来衡量蜜源。再引入三种不同类型的蜂：雇佣蜂、跟随蜂、侦查蜂。雇佣蜂负责寻找蜜源并记忆蜜源的花蜜量，通过“摇摆舞”与跟随蜂共享蜜源信息。跟随蜂根据传回的信息以一定的概率选择蜜源。雇佣蜂找到的蜜源质量未有改善时，放弃现有的蜜源，会转变成侦查蜂继续寻找新的食物来源。通过3种蜂群之间相互协作，从而找到优化问题的全局最优解。

1.2.1 初始化阶段

在ABC算法中，首先根据式(6) 在搜索空间内随机初始化生成SN个蜜源，D是待优化问题的维数。设置最大迭代次数maxcycle，蜂群终止循环次数limit。

$ {x_{ij}} = x_j^{{\rm{max}}} + {\rm{rand}}(0, 1)*(x_j^{{\rm{max}}} - x_j^{{\rm{min}}}) $

(6)

其中:在第n次迭代时蜜源i的位置表示为x_iⁿ=[x_i1ⁿ, x_i2ⁿ, …, x_iDⁿ]，n表示当前的迭代次数，x_j^max、x_j^min为对应的第j维向量的上下界。

1.2.2 雇佣蜂阶段

每一个雇佣蜂都到达目标点后，根据式(7) 在蜜源邻域内进行搜索，生成一个新蜜源。

$ {z_{ij}} = {x_{ij}} + {\varphi _{ij}}({x_{ij}} - {x_{kj}}) $

(7)

其中，k∈{1, 2, …, SN}，j∈{1, 2, …, D}是随机选择的下标，且k不等于j，φ_ij为[-1,1]的随机数，它控制了邻域的搜索范围。在产生新的候选蜜源之后，计算其适应度，利用贪婪选择原则，将新位置的适应度与记忆中最优解进行比较：如新蜜源的适应度大于原蜜源，则替换；否则，保持原位置不变。

1.2.3 跟随蜂阶段

跟随蜂根据雇佣蜂分享的蜜源信息，通过适应度值衡量蜜源优劣，用适应度度值计算跟随蜂选择蜜源的概率。

$ {p_i} = fi{t_i}/\left( {\sum\limits_{n = 1}^{SN} {fi{t_n}} } \right) $

(8)

其中: fit_i表示第i个蜜源的适应度的值，对应的P_i是指第i个蜜源被选择的概率，并基于轮盘赌原则选择雇佣蜂，P_i越大说明相应的蜜源越好，被跟随蜂选中的概率越大。

1.2.4 侦查蜂阶段

若蜜源经过limit次迭代循环后，蜜源质量仍没有提高，该处的雇佣蜂转变成侦查蜂，其拥有的蜜源也会被放弃。侦查蜂按式(6) 重新随机搜索一个新蜜源。

2 基于改进的人工蜂群的核模糊聚类算法 2.1 改进局部搜索策略

在标准的ABC算法中，平衡局部搜索和全局搜索的关键是更新种群的步长。文献[15]为了提高雇佣蜂的效率，通过最优值更新蜜源，提高了收敛速度，提出了新的搜索方式(9):

$ {z_{ij}} = {x_{ij}} + {\varphi _{ij}}{f_b}\left( {{x_{ij}} - {x_{bj}}} \right) $

(9)

其中：z_ij是新蜜源; f_b是第j维最优蜜源的适应度值，x_ij在所选维度j中蜜源的位置i，x_bj是第j维度中最优的蜜源。φ_ij为[-1,1]的随机数。蜂群在迭代寻优过程中只向最优解靠近，所有个体都聚集在该个体附近，并在小范围内随机寻找，忽略了控制人工蜂群的距离，容易陷入局部极值点且算法不稳定。搜索能力和开发能力对于群智能算法很重要。文中提出的改进人工蜂群算法，在迭代过程中动态改变与当前全局最优值差值的变化率w，通过增大减小权值φ_ij来调节当前变化态势。

$ w = \left( {{f_b} - {f_i}} \right)/{f_b} $

(10)

$ {\varphi _{ij}} = \left\{ {\begin{array}{*{20}{c}} {0.2 + w, }&{w \leqslant 0.3}\\ {0.5 + w, }&{0.3 < w \leqslant 0.6}\\ {0.6 + w, }&{w > 0.6} \end{array}} \right. $

(11)

其中:w为第j维与最优适应度差值的变化率，f_b为第j维的最优适应度的值，f_i为第i个蜜源的适应度的值。当蜂群第i个蜜源的适应度f_i与最优适应度f_b差值较大时，说明蜂群正往新的领域扩展，增大权值φ_ij能够提高全局搜索能力；反之，当f_i与最优适应度差值较小时，减小权值φ_ij能够加快收敛速度。实现对其附近解空间的搜索，增大了算法的搜索空间范围和开发能力，保持了种群多样性，避免算法因追求最优解产生早熟现象。动态改变权值策略契合蜂群当前变化态势，平衡了全局搜索与局部开采能力。

2.2 构造适应度函数

原始核模糊聚类算法的目标函数如式(1)，其衡量聚类总体质量的标准是最小化最大类内距离。聚类分析的核心思想是将数据划分到不同的类别，同一类中的样本对象相似度最大，而不同类间的样本对象相异度最大。而原始目标函数只考虑到同一类样本对象之间的距离，忽略了聚类质量是由类内距离和类间距离共同评价的。基于此，本文提出一种新的目标函数作为IABC-KFCM的适应度函数，能够有效平衡类内紧密程度和类间离散程度，充分挖掘数据之间的冗余。

设不同簇之间聚类中心的距离为：

$ {D_i} = \sum\limits_{i, j = 1}^c {\left. {\left| {{d_i} - {d_j}} \right.} \right|} $

(12)

改进的目标函数为：

$ {E_i} = {J_i}/{D_i} $

(13)

其中：D_i表示第i类间距离之和，定义了类之间的耦合性，J_i是由式(3) 得。在改进的目标函数中：J_i越小，表示类内距离达到越小，满足类内紧密的要求；D_i越大，表示类间距离越大，满足类间远离的要求，则E_i越小，达到最佳聚类状态。构造新的适应度函数为式(14)。

$ fi{t_i} = 1/\left( {1{\rm{ + }}{E_i}} \right) $

(14)

其中: fit_i表示第i个蜜源的适应度的值，E_i越小，fit_i越大，聚类效果越好。本文提出的适应度函数以样本与异类和同类近邻样本耦合度度量蜜源的优劣程度，旨在搜索类内相似度高、类间差异大的目标函数，提高聚类效果。

2.3 基于改进人工蜂群的核模糊聚类算法基本步骤

基于改进人工蜂群的核模糊聚类算法的主要思想：改进人工蜂群算法中每个蜜源代表优化问题的可行解，每个蜜源即由一组聚类中心组成。交替执行改进人工蜂群算法和核模糊聚类，对聚类中心进行优化，最后求得最优解。

第1步  随机产生有SN个蜜源的初始蜂群，设置最大迭代次数maxcycle，蜂群终止循环次数limit，聚类个数c，模糊指数m，允许最小误差ε。

第2步  对每个蜜源进行一次核模糊聚类，根据式(14) 计算每个蜜源的适应度，按照适应度值排序，前50%作为雇佣蜂，后50%作为跟随蜂，进入迭代阶段，直到达到maxcycle迭代次数。

第3步  雇佣蜂根据式(9) 进行邻域搜索工作，产生新的蜜源，计算其适应度值并评价，通过贪婪原则选择新旧蜜源。

第4步  跟随蜂根据轮盘赌的原则选择雇佣蜂，同时根据式(9) 在其邻域内搜索。将得到的蜜源作为聚类中心，再进行一次核模糊聚类，用划分后形成的新聚类中心更新蜂群。

第5步  如果蜜源x_i进行limit次迭代后，位置不变，则丢弃当前解，相应的雇佣蜂转变成侦查蜂，按照式(6) 在搜索空间内产生新解替代当前解。

第6步  记录迄今为止最优蜜源，判断是否满足循环终止条件：若是，循环结束，输出最后结果；若否，转至第2步。

3 实验仿真与分析

仿真环境采用CPU为Inter Core i3-2350, 内存4GB的计算机，操作系统是Window 7, 开发软件为Matlab 2015a。

3.1 改进ABC算法性能测试

为了验证改进人工蜂群(Improved Artificial Bee Colony, IABC)算法的寻优性能，选取3个经典的Benchmark函数Sphere、Rosenbrock和Ackley作为测试集，测试函数的数学表达式及搜索空间范围如表 1所示，测试函数的理论最优值均为0。其中Sphere和Rosenbrock是高维单峰值函数，Sphere用来测试算法的收敛速度和准确定位能力，Rosenbrock是非凸、病态函数，全局最优解位于抛物线形状的谷底处。Ackley是高维复杂多峰值函数，拥有多个局部极值点，用来检验算法的全局寻优能力。

对IABC算法和ABC算法、文献[16]算法进行对比仿真实验，对比实验效果并分析。文献[16]算法是将中心解引入到跟随蜂的局部搜索策略的改进人工蜂群算法。

对所有的测试函数，设IABC算法、标准ABC算法和文献[16]的蜂群规模为100，每个函数独立运行100次，对40维的Sphere、Rosenbrock、Ackley每次独立实验的最大迭代次数为3000，limit值为100，即在同一蜜源迭代搜索超过100次则雇佣蜂变为侦查蜂。采用适应度值评价算法的性能，得出各个标准测试函数对两种算法的适应度值对比曲线如图 1所示。

由图 1中可以看出，在固定的迭代次数下，IABC算法对于40维的Sphere函数和Rosenbrock函数虽然在最大迭代次数内没有达到最优值，但仿真精度都优于ABC算法和文献[16]，收敛曲线都以更快的速率下降。尤其是Ackley函数在153代时快速地收敛到函数的最优值，明显优于ABC算法。ABC算法在高维单峰以及多峰函数中都出现收敛速度缓慢的情况。文献[16]算法相对ABC算法收敛速度有所提升，在全局寻优上稍显薄弱。IABC算法具有更好的全局寻优能力和更快的全局收敛速度，IABC算法在各标准测试函数上都优于ABC算法和文献[16]，且算法性能稳定，证明IABC具有较好的鲁棒性。

3.2 基于IABC算法的核模糊聚类性能测试

为了测试基于IABC算法的核模糊聚类(KFCM based on Improved ABC, IABC-KFCM)对数值型数据的有效性，采用UCI(http://archive.ics.uci.edu)实验数据集Iris、Wine、Balance-scale、Vote、Heart、Australia作为测试样本。数据集的基本特征如表 2所示。

选取KFCM、基于人工蜂群算法的核模糊聚类(KFCM based on ABC, ABC-KFCM)、IABC-KFCM算法、基于改进的人工蜂群的广义模糊聚类^[17](The Generalized Fuzzy Clustering algorithm based on Improved ABC, IABC-GFCM)进行对比实验。IABC-GFCM改进雇佣蜂和跟随蜂的搜索方式，引入混沌映射对种群进行个体变异，对目标函数、隶属度和聚类中心的模糊指数独立赋值，进而优化模糊聚类。选用聚类正确率作为评价指标，即正确聚类样本数与样本总数所得的比值。对于每个聚类运行100次，取聚类的平均正确率，其实验结果如表 3所示。设置实验参数为：IABC-GFCM的模糊指数为m₁=2，m₂=3，m₃=2，其余算法的模糊指数取均为2，允许最小误差ε=0.000 1。

由表 3可知：传统的核模糊聚类容易受到初始聚类中心的影响，聚类效果差；在基于人工蜂群的核模糊聚类和IABC-GFCM算法中，聚类精度都有所提高；本文提出的基于IABC算法的核模糊聚类算法，由于引入了人工蜂群中的蜜蜂的智能搜索行为，防止早熟收敛，使得聚类精度高于以上几种算法。对于Iris数据集中第二类和第三类存在交迭部分，IABC-KFCM仍保持最优聚类精度；对于Wine数据集IABC-KFCM稍劣于IABC-GFCM算法；但对于其他高维的数据集，聚类效果也在不同程度上得到提升。由此可见，在聚类的准确性以及鲁棒性方面IABC-KFCM更好。

4 结语

本文先介绍了核模糊聚类算法，并指出算法的局限性：对聚类的初始化敏感和易陷入局部最优。针对这两个问题，本文提出一种人工蜂群和核模糊聚类相结合的算法，该算法首先将与迭代的当前维度最优解差值作为改变权值的参考依据，引导雇佣蜂的搜索趋势，在适应度函数中引入类内距离和类间距离比值，从而改变蜂群的适应度函数并与核模糊聚类相结合，在聚类时使得类内紧密度和类间离散度均达到最优化。UCI数据集实验表明，本文提出的算法在优化效率和优化性能上更加稳定。需要指出的是，Wine数据集上的结果稍劣于IABC-GFCM算法，此外，算法引入与最优解的差值的过程中增加了时间复杂度，因此后续的研究工作主要针对上述两方面以及将IABC-KFCM算法应用到图像分割和图像检索等领域。