基于果蝇算法优化的粗糙C均值聚类算法.pdf

第 卷 第 期 年 月南昌工程学院学报 收稿日期：基金项目：江西省教育厅科学技术研究项目（）；国家自然科学基金资助项目（）作者简介：周浩岩（），男，硕士生，通信作者：叶军（），男，教授，硕士，文章编号：（）基于果蝇算法优化的粗糙 均值聚类算法周浩岩，叶军，谢立，卢岚，李兆彬（南昌工程学院 信息工程学院，江西 南昌 ；江西省水信息协同感知与智能处理重点实验室，江西 南昌 ）摘要：粗糙 均值聚类算法采用随机选取质心的方法，会导致聚类算法过早陷入局部最优；簇心更新中采用固定权值降低了聚类精度。针对此类问题，结合果蝇和粗糙 均值聚类两种算法，提出一种改进算法。该算法从三个方面进行了改进：一是为克服传统果蝇算法中固定飞行半径带来的影响，给出一种自适应寻优步长策略的果蝇优化算法，提高果蝇优化算法的搜索精度；二是构造对应味道浓度值的目标函数，利用目标函数值引导果蝇进行位置更新，把最优味道浓度值的果蝇位置作为新的聚类中心进行次迭代；三是设计了一种动态调整簇心更新中上下近似权重和阈值的方案。最后通过 标准数据集对算法进行比对分析，实验结果证明了改进后算法的可行性和有效性。关键词：粗糙 均值；果蝇算法；适应度函数；权重因子；飞行策略中图分类号：文献标志码：，（；，）：，：；聚类算法是一种经典的数据挖掘算法。聚类是指将数据有效划为若干个簇，使每个簇内的数据相似性较大，簇间数据相似性较小，从而找出数据中分布的规律。均值聚类算法是一种无监督学习的聚类分析算法，具有计算速度快、可伸缩性强、易实现的特点，被广泛应用于文本分析、图像识别和人脸识别等诸多领域 。但 均值算法在处理类簇边界交叠严重、无法确定归属对象的数据时，精度有所降低，聚类效果差。为此，等 利用粗糙集在处理不确定数据上的优势，引入上、下近似两个算子，提出了一种粗糙 均值聚类算法。该算法将确定归属关系的对象划分至下近似集，将无法确定归属关系的对象划分至上近似集，后期通过迭代将上近似集中的对象不断划分至下近似集，较好地解决了边界交叠区样本归属的问题。但该算法延用了经典 均值聚类算法中随机初始质心的做法，以及在迭代过程中，人为给定上近似与边界域权重，易导致聚类结果稳定性与精度下降问题。为此许多学者提出了改进方法。文献 提出了一种自适应参数的粗糙 均值聚类算法，优化了粗糙聚类效果、降低了对噪声的敏感程度。文献 针对 均值聚类算法中均值计算的特点，提出了基于密度加权粗糙 均值聚类算法。该算法在类均值计算中赋予每个对象不同权重值，有效降低了迭代次数，减小了孤立点对聚类的影响，提高了聚类精确度。文献 采用基于近邻密度的选取方法确定初始聚类中心。文献 提出了一种对维度加权的欧氏距离来计算样本权重方法，可自动获取聚类中心以及聚类数目。文献 提出了三支聚类的思想，引入距离阈值 ，有效地将离群点单独形成新的类簇，一定程度上解决了人工干预聚类个数对 均值聚类算法稳定性的影响。群智能算法是一种仿生的寻优搜索算法，近年来，众多学者将群智能算法引入到粗糙 均值聚类算法中，解决粗糙聚类算法盲目初始簇心带来的聚类结果不稳定、精度下降等问题。例如文献 通过改进的遗传算法动态地划分 均值的聚类数目，并且根据最大和最小距离原则初始化聚类中心。文献 结合粒子群算法对粗糙聚类算法进行优化，通过引入随机粒子和动态学习因子来避免聚类结果陷入局部最优的情况，提升算法全局搜索能力与准确率。文献 将蚁群优化算法与粗糙 均值的聚类算法相结合，有效改善了原算法随机选取初始簇心带来聚类结果不稳定的问题，提高聚类算法的准确率。文献 将改进的鱼群算法引入到粗糙聚类中，结合粒计算理论，依据粒密度和最大最小距离乘积法初始化聚类中心，该方法提高了全局搜索能力和聚类精度。文献 结合人工蜂群算法，将每次迭代蜂群得到的最优蜂源（适应度函数值）作为初始聚类中心，同时动态地调整下近似与边界域权重，提高算法的稳定性和聚类效果。上述结合群智能优化算法改进的粗糙 均值聚类算法虽然取得了较好的效果，但是还有改进空间，尤其是在减少迭代次数和降低时间复杂度方面改进空间较大。本文借鉴其他群智能优化方法，引入果蝇优化算法对粗糙 均值算法随机初始簇心问题进行改进。果蝇优化算法（）是潘教授受果蝇觅食启发提出的群智能优化算法，是一种模拟果蝇搜索寻优行为进行全局搜索的算法 。该算法具有操作简单、参数少、全局寻优能力强、鲁棒性较好以及算法复杂度低等优点，尤其是在求解多维背包问题、函数优化 、调度问题以及数学极值方面很有优势。不依赖于求解问题的具体信息，并且适合与其他算法混合使用，容易得到性能更出众的混合算法 ，本文在文献 基础上将双策略协同果蝇优化算法引入粗糙聚类算法中，对搜索步长进行了改进，提出新的步长搜索策略，提高算法稳定性和聚类精度，进一步减少了算法的迭代次数，降低了时间复杂度。相关知识 果蝇算法及其改进算法标准的果蝇算法引入了味道浓度判定值和味道浓度函数，根据味道浓度引导果蝇移动，该算法主要步骤如下：初始化阶段，果蝇的规模 、最大可以达到的迭代次数、以及果蝇的初始位置（，）；：搜寻阶段，赋予果蝇个体搜索方向和距离 ；（）：根据勾股定理计算出果蝇个体与原点之间的距离，味道浓度判定值 与 互为倒数；槡 （）：将味道浓度判定值代入适应度函数中得出味道浓度 （），找出浓度值最高的果蝇并记录其位置（，）；，()（）：果蝇种群向具有最优味道浓度的果蝇个体靠拢；()()（）：迭代阶段，重复搜寻阶段，直到迭代次数达到 。由于果蝇算法中的飞行方向与飞行距离都是随机的，会导致寻优结果非常不稳定，容易陷入局部最优，带来早熟的问题。许多研究者提出了改进算法。例如，马兵等 引入差分进化算法中的差分演化策略对果蝇算法进行优化，对果蝇种群进行变异、交叉、选择操作，增加了果蝇优化算法的多样性。郑晓龙等 将 的全局搜索能力与模拟退火算法概率突跳机制进行结合，增加算法的鲁棒性。本文借鉴这些改进算法的研究成果，提出自适应调整寻优步长的果蝇优化算法。粗糙 均值聚类及其改进算法 等 将粗糙集中上下近似的概念引入到了 均值聚类算法中，从该算法定义可知，一个南昌工程学院学报 年数据样本最多只能属于一个类的下近似；若一个数据样本属于某个类的下近似则必将属于该类的上近似；若某个数据样本不属于任何类的下近似，则该样本至少属于两个或两个以上簇的上近似。算法的质心迭代如式（）所示：，（），（）式（）中和分别表示类 的上、下近似；，为下近似权重，为上近似权重；表示集合中数据对象的个数。针对粗糙 均值聚类算法存在的不足，许多研究者提出了改进算法。修正了簇心的迭代公式，当仅有下近似或上近似的情况时，权值设置为，用相对距离代替聚类算法中的绝对距离，有效减少了离群点的影响，中心迭代如式（）所示：，()，()，()（）但是，的改进方法依然采用人为设置权重和阈值的方法，没有考虑随着迭代次数的变化下近似和边界区域不同对质心更新造成的影响。文献 提出了一种加权距离自适应的粗糙 均值聚类算法，定义的密度函数如式（）所示：()，（）式中 为邻域有效半径，数据对象 对应的权重值定义为，（）式中 为边界域，簇心的更新如式（）所示：，（）该算法在处理高维数据集时具有较高的时间复杂度，且聚类精度较低。文献 针对数据对象分布差异性的问题，考虑到不同类簇中下近似和上近似分布的差异性，提出了一种空间距离自适应权重的粗糙 均值聚类算法，其簇心更新如式（）所示：（，）（，()），（）式中：（，）为下近似到簇心的平均距离；（，）为边界域到簇心的平均距离，有效地改善了不同簇间下近似和边界域权重分配的问题，提高了聚类算法的准确性。改进的粗糙 均值聚类算法 改进的果蝇步长搜索策略传统的果蝇算法，受固定步长的限制容易陷入局部最优，文献 提出基于 分布的步长更新策略，其步长更新公式如下：（，）（，）（）（）（），（）（，）（），（）式中：为第一自由度，为第二自由度，两者均为人为给定值。该公式虽然可以有效地改善果蝇算法过早收敛的缺点，但计算量比较大，在处理一些高维数据的时候，时间复杂度较高。为减少计算工作量并防止果蝇算法过早收敛，提出一种基于标准正态分布的步长更新策略，公式如下：，（），（）式中：为初始步长；为初始果蝇位置。其运行轨迹如图 所示。从运行轨迹可以看出，前期较大步长可以扩大搜索的范围，后期缩减步长能够避免在最优解附近震荡，找到全局最优解。运算比较简单，不仅可以降低计算工作量，而且能有效地提升果蝇算法的寻优能力。动态调整下近似和边界权重方法粗糙 均值聚类算法中，上下近似的权值均为人为给定的固定值。分析可知，采用定值的方式，无法合理动态地反映两个集合对质心造成的影响。事第 期周浩岩，等：基于果蝇算法优化的粗糙 均值聚类算法图 果蝇步长更新轨迹实上，搜索质心是一个动态迭代的过程，质心的权重会随着下近似与边界集合中数据空间分布变化而改变。文献 使用下近似与边界域中数据对象个数比值的方式来动态调整上近似及边界域权重，但是仅考虑数据对象个数对上近似和边界域的影响，忽视了数据对象分布的差异性；文献 中提出了空间距离自适应的方法来处理权重的问题，其考虑了空间样本分布的差异性，对下近似及边界域的权重进行了调整，但该算法忽视了类簇间规模不均衡的影响。文献 考虑到边界样本位于交叉类簇不均衡的情况，采用式（）将边界域中数据对象对簇规模的影响进行度量。，（）式中：表示第 个类中上近似样本的个数；表示数据样本 目前所在的交叉类簇。显然，式（）有效改善了文献 没有考虑边界样本处于交叉类簇不均衡的情况，提高了聚类精度。该公式也存在不足，经过分析可知，式（）在如图 所示簇中样本分布密度差异小的情况下处理效果比较好，聚类精度较高。在图 中，黑色的方形表示原本应该归属于 类的数据样本，圆形表示原本应该归属于类的数据样本。图 类簇均衡示例但式（）对图 所示在样本密度差异大的情况下将失去已有的调和作用，得到的聚类效果较差。因此，对该式进行了修正，定义如下：图 类簇不均衡示例，（）式中：表示第 个簇 中上近似中样本点 距质心的距离与边界样本点 到簇心 距离的比值，称为边界样本 对于 的归属度；表示簇 中数据的个数。式（）既考虑了式（）中的样本数量，又反映了样本处于交叉类簇不均衡的情况，真实地体现了样本对象对簇规模的影响。的值越大，说明该边界样本点对于该簇的归属度越大。对于不考虑类簇规模不均衡的情况下，边界区样本对于簇 的隶属度函数为 ，（）表示边界域样本距簇心 的距离。结合图（）（），考虑到各类簇规模不均衡的情况，对边界域中的样本对象隶属度函数进行了修改，如下式（）所示：，（）式中：为边界样本 对于 簇的隶属度；为边界样本 对于 的归属度。如图（）（），值越大说明样本的隶属度越大，边界样本对该簇心的作用越大。因此，综合式（）（），新的簇心更新公式为 ，（）显然，式（）不仅考虑了交叉类簇不均衡的情况，而且考虑了样本空间密度差异大的情况，合理地反映了各样本对簇心的作用。构建目标函数果蝇向最优解位置靠拢是由目标函数引导进行南昌工程学院学报 年的，因此，目标函数直接决定着果蝇的搜索方向、解的优劣以及迭代次数等 。在果蝇优化算法中，味道浓度和视觉是引导果蝇相互移动的两个主要因素，本文将每类中的点距离各自聚类中心的距离之和作为适应度函数，如式（）（）所示，并将适应度函数值对应果蝇味道浓度值。从式（）（）可以看出，适应度越小说明样本点距离簇心越近，果蝇味道浓度就越浓。构造的适应度函数如下：（），（，），（）（，），（）式中 表示簇中样本距离簇心的距离之和。改进的自适应阈值阈值在粗糙 均值聚类算法中对计算样本分配到上、下近似有着重要的影响，算法迭代的前期，较大的阈值可以更好地解决样本归属关系不确定的问题，随着迭代次数增加阈值不断地减小，较大的阈值可以高效地确定样本的归属关系 。随着阈值的减小，更多的样本被划入到簇的下近似集中。传统的粗糙 均值聚类算法采用固定的阈值，在算法迭代的过程中影响很小，文献 中采用一种动态改变域值的方法：（），（）式中 为迭代次数。在进行实验仿真时发现，若将初始阈值 设置为 ，采用式（）动态调整阈值时，算法迭代到第二次的时候，阈值 就减小到了负值而导致实验无法继续。为了避免这种情况，本文算法对式（）进行了修正，采用式（）作为阈值的更新公式，阈值的轨迹如图 所示。（），()，（）图 阈值轨迹从图 所示的阈值轨迹可以看出，在聚类初期，数据对象的归属关系不明确，阈值 较大，使得数据对象大多划入上近似集。随着迭代次数的不断增加，数据对象的归属关系变得明朗，越来越多的数据对象划入类的下近似集，阈值 持续变小。因此，式（）得到的阈值轨迹与粗糙 均值聚类算法迭代过程数据对象变化情况完全一致。算法实现流程基于以上改进，提出了一种基于果蝇算法改进的粗糙 均值聚类算法（），该算法首先从初始的果蝇个体中随机选取 个果蝇个体作为聚类的中心，并进行粗糙 均值聚类，然后计算每个果蝇个体的浓度值并且找出最大的 个作为新的聚类中心，不断循环直到达到最大迭代次数，具体流程如图 所示：图 算法流程图 算法的时间复杂度分析本文提出的算法首先对样本进行粗糙 均值聚类，需要将每个样本数据划分到上下近似集中，即计算出每个样本与 个聚类中心的距离，时间复杂度为 （），其中 为样本的个数。在计算果蝇的味道浓度值时，个果蝇需要对浓度进行计算，因此所花费的时间复杂度为 （），计算浓度后更新果蝇的位置需要的时间复杂度为 （），相比于样本数据 的规模，果蝇种群的规模 要小很多。算法的时间复杂度为 （），时间复杂度相比于结合蚁群算法改进的粗糙 均值聚类算法 的 （）和结合人工蜂群算法 改进的粗糙 均值聚类算法 的 （）优势明显一些，显然，本文算法减少了时间复杂度。实验结果与分析为了证明本文算法的有效性，将经典粗糙 均值聚类算法（算法 ）、遗传算法改进的粗糙 均第 期周浩岩，等：基于果蝇算法优化的粗糙 均值聚类算法值聚类算法（算法 ）、蚁群算法改进的粗糙 均值聚类算法（算法 ）以及本文算法即果蝇算法优化的粗糙 均值聚类算法（算法）进行比较。实验采用表所示的个 数据集对算法的聚类效果进行测试。仿真软件环境为 操作系统，编译软件 ，环境为 ，硬件为 ，内存。表 数据集的基本信息数据集类别数据维数样本个数 本文算法实验参数设置为：最大迭代次数 ，种群的规模 ，初始步长 ，初始阈值为 。数据预处理为了避免不同分量对应差异较大，首先对样本数据进行了归一化处理 ，将数据进行等比例缩放，使数据位于（，）之间，使其各个特征做出的结果贡献度相同。本文采用的是用对数函数对数据进行转换：找到每个维度的最大值以及各个测试数据对应维度的值 ，通过对数函数归一化映射到（，）区间中 的值。具体公式为 ()()，（）评价指标性能测试包括类内、类间距离、准确率、迭代次数 、指数（）等 个指标，其中 指数公式为 ，（）具体计算步骤如下，其中定义 为 ，（），（）式中：，为衡量相似度的值；，是簇 与簇 质心间的距离。计算的是类内数据到簇心的平均距离，代表了簇类 中各样本数据的分散程度。计算公式分别为 ()，（），()，（）式中：代表簇类 中第 个数据点；是簇 的质心；是簇类 中数据的个数；指标指的是任意两簇的类内样本到类中心平均距离之和除以两类中心点之间的距离，的取值越小说明类内距离越小，同时类间间距越大，聚类效果越好。结果比较实验得到的 个算法在 个数据集的类内、类间距离、准确率、迭代次数分别如表 所示。类内距离和类间距离反映了类内之间的紧凑程度和类与类之间的相异程度。一般情况下，类内距离越小，表示同一簇内样本对象分布更紧凑，对象间相似度高；类间距离越大，表示不同簇内样本对象分布离散，对象的相似度低。从表 结果可以看出，本文算法得到的 个数据集的类内距离比其他 个算法的都要略小，得到的类间距比其他三个算法得到的稍大些，说明了本文算法的聚类精度更高。准确率方面，在 、和 个数据集上略高于算法和算法；在高维数据集 、大数据集 以及 数据集上，本文算法也优势明显。在迭代次数方面，由于果蝇算法在寻找最优聚类中心方面具有很强的能力，本文算法在 、以及 个数据集上的迭代次数明显要少，在 、和 个数据集上也略少于其他 个算法，证明了本文算法减少了迭代次数。在 比较上，实验得到的 个算法在 个数据集上的 指数（）分布如图 所示。图 指数南昌工程学院学报 年表 算法性能比较数据集性能指标算法 算法 算法 算法 类内距离 类间距离 准确率 迭代次数 类内距离 类间距离 准确率 迭代次数 类内距离 类间距离 准确率 迭代次数 类内距离 类间距离 准确率 迭代次数 类内距离 类间距离 准确率 迭代次数 类内距离 类间距离 准确率 迭代次数 类内距离 类间距离 准确率 迭代次数 能较好地反映聚类效果，从式（）可知，的值越小说明得到的聚类效果越好。从上述图分析可知，本文算法在 数据集上的 高于算法 和略高于算法 ，稍低于算法 ，说明本算法在该数据集上聚类效果稍逊色于算法 和算法 ，好过算法 。在 、和 个数据集上 值比其他 个算法小许多；在高维数据集 上也是明显比算法和算法 小，略小于算法 ，体现了本文算法在这 个数据集上的聚类效果要好于其他 个算法，在高维数据集 和大数据集 、上也取得了较好的效果。结论针对 均值聚类及其改进算法存在的局限性，本文所做的工作主要包括 个方面：（）对果蝇算法的搜索步长进行了改进，给出了一种基于正态分布的自动步长搜索策略。该策略一是加大了前期步长，可以扩大搜索的范围；二是缩小了后期步长，能够有效避免在最优解附近震荡，找到全局最优解。新的搜索策略提升了果蝇算法的寻优能力。（）给出了一种动态调整公式中上、下近似权重和阈值的方法，该方法不仅考虑了交叉类簇不均衡的情况，而且考虑了样本空间密度差异大的情况，合理反映了各样本对象对簇心所起的作用。（）构造了一种对应味道浓度值的目标函数，以目标函数值引导果蝇进行位置更新，将最优味道浓度值的果蝇位置作为算法聚类中心进行聚类迭代。改善了随机选择初始聚类中心带来的不稳定性问题，并且减少了算法的迭代次数。实验证明了本文算法的有效性和可行性。该算法也存在不足：一是实验仿真是在事先知道 值的条件下进行的，在已知类别数 的数据集上实验取得了较好的聚类效果，但在未知类别数 的数据集上效果不稳定；二是动态调整上下近似权重的方法增加了算法每次迭代的运算量。后期的研究工作将主要集中于改进上述不足。第 期周浩岩，等：基于果蝇算法优化的粗糙 均值聚类算法参考文献：，（）：吴烨，钟志农，熊伟，等 一种高效的属性图聚类方法 计算机学报，（）：，（）：，：周涛 具有自适应参数的粗糙 聚类算法 计算机工程与应用，（）：郑超，苗夺谦，王睿智 基于密度加权的粗糙 均值聚类改进算法 计算机科学，（）：，（）：王子龙，李进，宋亚飞 基于距离和权重改进的 算法 计算机工程与应用，（）：解滨，董新玉，梁皓伟 基于三支动态阈值 聚类的入侵检测算法 郑州大学学报（理学版），（）：洪亮亮，罗可 改进的基于遗传算法的粗糙聚类方法 计算机工程与应用，（）：张丹丹，罗可 一种结合粒子群和粗糙集的聚类算法 小型微型计算机系统，（）：刘洋，王慧琴，张小红 结合蚁群算法的改进粗糙 均值聚类算法 数据采集与处理，（）：陈济舟，罗可 基于粒计算与粗糙集的人工鱼群聚类算法 计算机工程与应用，（）：叶廷宇，叶军，王晖，等 结合人工蜂群优化的粗糙 聚类算法 计算机科学与探索，（）：，：张清勇，钱浩，雷德明 求解多维背包问题的二级协作果蝇优化算法 控制与决策，（）：王林，吕盛祥，曾宇容 果蝇优化算法研究综述 控制与决策，（）：石建平，刘国平，李培生，等 双策略协同进化果蝇优化算法及其应用 计算机集成制造系统，（）：马兵，王瑞峰 计及需求响应的主动配电系统优化调度研究 郑州大学学报（理学版），（）：郑晓龙，王凌，王圣尧 求解置换流水线调度问题的混合离散果蝇算法 控制理论与应用，（）：，：段文影，李向军，邱桃荣，等 一种具有自适应参数的基于密度加权的粗糙 均值算法 南昌大学学报（理科版），（）：王慧研，张腾飞，马福民 基于空间距离自适应权重度量的粗糙 算法 计算机科学，（）：覃承友，谢晓兰，王悦悦，等 基于仿生优化算法的聚类改进算法 桂林理工大学学报，（）：张腾飞，李中文，马福民，等 基于类簇规模不均衡度量的粗糙模糊 聚类算法 信息与控制，（）：张淑清，要俊波，张立国，等 基于改进深度稀疏自编码器及 的电力负荷预测 仪器仪表学报，（）：马福民，逯瑞强，张腾飞 基于局部密度自适应度量的粗糙 聚类算法 计算机工程与科学，（）：李沛武，张永芳，黄逸翠，等 基于双重密度和簇间近邻度的密度峰值聚类算法 南昌工程学院学报，（）：，（）：许文涛，唐明，张桓玮，等 基于 聚类点信息再分配的干旱危险性评价 南昌工程学院学报，（）：，（）：，：，：，（）：南昌工程学院学报 年