基于优化人工鱼群算法的混合聚类研究

田 琳，田力威，刘启文

（1.沈阳大学 信息工程学院，辽宁 沈阳110044；2.辽宁省物联网信息集成技术工程研究中心，辽宁 沈阳110044；3.大连理工大学 电子信息与电气工程学部，辽宁 大连116012）

0 引 言

混合聚类的本质是聚类，它根据不同对象之间特征的差异将数据进行模式分类，使同簇内的样本相似度较高，而不同簇中的样本相异度较大［1］，从而发现数据的分布规律与数据间的相关性。K－中心点算法是一种鲁棒性较强的划分方法，采用距离中心最近的点来代表簇，这样处理噪声数据的效果好并且不用提前定义［2］，它在知识发现、信息预测决策分析有着重大作用。但此算法易受离群点和局部最值点影响，聚类初始化参数的随机性对聚类结果起决定性作用。

文中运用的新型群智能算法—人工鱼群算法。人工鱼群算法将生物界中的群体智能用于解决优化问题，作为一种广义的邻域搜索算法，借助于启发式的搜索策略，具有快速跟踪变化能力，从而具有全局寻优的能力，由于本身具有全局收敛能力，因此初值设置为固定值或随机值都可以，参数可设置的范围较广，适应性、并行性较强。该算法具有很强的灵活性，有多种行为组合可选取，以得到较好的优化性能，这是遗传算法和粒子群算法等优化算法不具备的优点。近些年基于群智能的混合聚类方法成为热门的研究方向，融合各自算法的优势，从减小误差率、聚类准确性、以及对经验参数的选择方面都取得了很大的进展。其中应用较广的有粒子群和K 均值算法［3］混合、蚁群结合C－均值［4］算法和基于鱼群算法的聚类技术等。

近几年，基于人工鱼群的混合算法有很多，文献［5］提出了缩小搜索域的方法来加速人工鱼个体局部搜索，但这种方法只优化收敛速度，使人工鱼追尾和聚群行为受到很大局限，从而影响到算法寻优质量。文献［6］引入了K－平均值算法加快了算法迭代速度，由于人工鱼群算法在很多地方采用的是随机处理，因此算法的性能不稳定，影响了算法的实际应用。文献［7］利用模拟退火算法来改进人工鱼群算法，在该算法中通过修改人工鱼的觅食行为避免了人工鱼的退化，这种混合算法虽然克服了易陷入局部极值的缺点，但是算法收敛性时间较长，不适用于海量数据的分析。文献［8］将人工鱼群算法和基于网格和密度的聚类算法相结合，新的混合聚类算法有较好的并行性，但是最终聚类质量受到网格数目和网格大小的影响，在算法执行过程中有一定的局限性。

因此，结合K－中心点算法与人工鱼群算法的优势，本文提出了基于优化人工鱼群算法的混合聚类算法，该算法解决了初始化聚类中心敏感问题，全局优化性能稳定，文中在检测到的小数据集上进行测试，证明改进后的算法获得较好的聚类成果。

1 聚类模型

X＝（x1，x2，…xN）作为N 个样品数据，x 是数据的代表点，Ci是任意一个簇，Oi是簇Ci的中心点，（j＝1，2…，k）。

算法描述：在样本集X 中任意选取k 个对象作为k 个簇的初始中心点（O1，O2，…Oi…Ok）；将除了代表中心点的其余数据利用最临近原则分配到各个簇中；在每个簇（Ci）中，随机地选取一个非中心点Oj，计算用非中心点代替原簇中心点［9］后的总代价ΔE。如果ΔE＜0，就用非中心点Oj替换原中心点Oi；反复执行以上步骤直到k个中心点固定下来。用代价函数来评估聚类质量是否改善。该函数构成如下

式中：ΔE——绝对误差标准的改变量，E2——替换中心点后数据集中所有代表点与其同簇中中心点之间的相异度的和，E1——未替换前数据集中所有代表点与其同簇中中心点之间的相异度的和。计算ΔE＜0，则代表替换后聚类效果提高，则替换掉该中心点，否则仍用原中心点。

2 优化人工鱼群算法

2.1 基本行为描述

设人工鱼个数为N、人工鱼个体的状态F＝（f1，f2，…fn），［其中fi为欲寻优的变量］、人工鱼移动的最大步长Step、人工鱼的视野Visual、觅食最大试探次数Try＿number、拥挤度因子δ、人工鱼所在位置的食物浓度Y＝f（F）（Y 为目标函数值）。

（1）觅食行为：觅食行为作为人工鱼的基本习性之一，主要原理是鱼群通过视觉与味觉趋向于食物浓度大的区域。设置当前人工鱼状态为Fi，随机选择当前位置视野内一个状态

式中：Rand（）∈（0，1），再求优化解过程中，若Yi＜Yj，说明状态更优则向此位置方向前进一个步长

若不符合前进条件则随机选择状态Fj，重新判断，反复试探Try＿number次后，若仍无法找出更优解，则随机移动［11］一步

（2）聚群行为：鱼在游动时为确保群体的生存，会向邻近伙伴的中心聚集。Fi仍对应当前人工鱼状态，感知当前位置附近（视野内）人工鱼数目nf及其位置的中心Fc。若Yc／nf＞δYi，则说明该中心位置食物较多、拥挤度较小，则向Fc［12］进一步

若不满足则执行觅食行为。

（3）追尾行为：鱼在游动时当其中一条或几条鱼探索到食物时，其邻域范围内的鱼会尾随鱼群到达食物位置。Fi对应当前人工鱼状态，感知当前位置附近人工鱼中状态最优的Fj，若满足Yj／nf＞δYi则显示Fj位置附近的食物较多、拥挤度较小，则向Fj前进一步见式（3），判断不符合条件则执行觅食行为。

2.2 人工鱼群算法的改进

（1）在觅食行为中，Fj视野范围内随机选取的状态，当随机选的一个状态食物不满足前进条件时选择随机移动行为，随机行为的存在使得寻优难以得到很高的精度，到了收敛后期会造成人工鱼在全局极值点迂回搜索，导致无效计算。本文改进为当觅食失败时，人工鱼向公告板记录的相比之下状态较好的值前进一步

式中：Fbetter——告板记录较好的状态，相对于随机行为给出了更好的前进可能性，进而跳出局部最优，防止人工鱼在局部震荡而停滞不前。

（2）在人工鱼群算法中，参数拥挤度因子δ的引入是为了避免鱼群过度拥挤，并且δ是算法执行过程中的定值，这种全局δ固定的方式会导致全局优化解附近的人工鱼群个体之间相互排斥而不能准确的聚集到极值点，且迭代后期每次都对比是否满足拥挤度条件会增加计算成本。本文改进为定义算法执行初期拥挤度因子δ＝0.75，当Try＿number＝180时，忽略拥挤度因子即δ·nf＝1，算法初期希望限制人工鱼的规模，但在后期人工鱼基本聚集在较优状态附近，缺省δ减少计算量和算法执行时间，这样改进不仅提高算法运行效率，并且不影响算法收敛性。

（3）在求解中心点问题的人工鱼群算法中，当执行聚群行为和追尾行为失败后，每次都执行觅食行为，这样不仅增加了收敛时间，每次迭代的计算量也将增大，因此聚群行为和追尾行为可改进为：当人工鱼前进一步失败后，缺省觅食行为而是执行随机游行为，且随机游行为选择自适应步长，这样克服了人工鱼在极值点聚集而错过全局极值点的问题，优化的算法使求解质量精度更高。

3 基于优化人工鱼群算法的混合聚类算法

3.1 改进的人工鱼群算法相关定义

定义1 人工鱼自适应步长：自适应步长表示人工鱼移动的距离随着迭代次数增加而改变。自适应步长定义为

定义2 聚类评价准则：目标函数度量对象与其簇的代表对象的平均相异，表示类间数据分布的紧密程度，目标函数定义为

3.2 基于优化人工鱼群算法的混合聚类算法过程描述

（1）设置人工鱼参数的初值，利用目标函数计算当前位置的食物浓度。

（2）通过鱼群行为的执行条件和人工鱼前进准则，每条人工鱼分别执行觅食、追尾、聚群等行为，算法中的食物浓度可以参照为数据密度，对比视野范围内食物浓度选择优劣解，将其状态记录到公告板上，最终人工鱼聚集在了数据密度高的区域。

（3）每条人工鱼的状态代表一个决策变量，通过计算目标函数值来评价鱼的寻优程度，将其状态记录在公告板上，重复（2）（3），更新人工鱼的位置信息，达到最大迭代次数时算法终止，最终选择能表示初始聚类中心的解。

（4）依据公告板信息和鱼群的位置，选出K－中心点算法的输入参数，即初始中心点和聚类个数；用K－中心点算法进行聚类分析，使数据类内离散度之和达到最小，最小离散度函数：M＝minE。

基于人工鱼群算法的优化聚类算法流程如图1所示。

图1 基于人工鱼群算法的优化聚类算法流程

4 仿真实验

仿真数据包括300 个三维数据，实验运行环境为：Pentium（R）D，3.00G内存，编程环境：Matlab7.12.0（R2011a），实验参数：Step＝0.2、Visual＝100、Try＿number＝200、N＝50，δ＝0.75。

实验运用了两种混合聚类算法对300个数据进行分类，对比基于基本鱼群算法和改进的鱼群算法与K 中心点算法结合的两种混合聚类算法的实验结果。未迭代前数据分布如图2所示，经典混合聚类算法运行结果如图3所示，图4则是本文提出的改进后的混合聚类算法实验结果图。

图2 未迭代前数据分布

图3 基本人工鱼群聚类算法迭代完成的寻优

图4 改进后的人工鱼群聚类算法迭代完成的寻优

人工鱼在三维数据中寻找中心点，如图3聚集效果不清晰，部分移动到个别局部团簇附近，由图4中的寻优路线可看出优化结果可逼近到全局数据密集处，从图3和图4可以看出本文改进后的人工鱼聚类边缘更明显，聚集在更紧密的位置，得到了精确性较高的划分结果，验证了此算法的优越性。两种算法的实验结果对比见表1。

表1 两种算法的实验结果

表1说明在人工鱼个数和算法迭代次数等条件相同的情况下，文中提出的算法在迭代时间上有所减少，降低了算法执行过程中的计算量，由表1也可以看出正确率也有提高。

5 结束语

通过混合聚类方法来解决决策、预警等问题是目前研究、应用广泛的一个问题。由实验结果图对比表明，本文提出的改进后的全局人工鱼群混合聚类算法，使特性相似的数据聚集效果明显，通过改进的鱼群算法与K－中心点算法结合的数学模型，更精确地展示了样本间的差异，提高了聚类质量，获得较优的中心点与清晰地聚类划分，并且在减小算法计算量上也有所突破。作为一种基于动物自治体模型的新型现代智能算法与K－中心点算法结合的一种混合聚类算法，避开了聚类算法初值依赖性问题，克服了鱼群算法后期迭代速度慢问题，其良好的并行性可有效的应用在各种领域，但是算法的收敛速度问题还有待改善与研究。

［1］Han Jiawei，Kamber M.Data mining：Concepts and techniques［M］.2rd ed.Beijing：China Machine Press，2007：252－272 （in Chinese）.［Han Jiawei，Kamber M.数据挖掘概念与技术 ［M］.2 版.北京：机械工业出版社，2007：252－272.］

［2］XIA Ningxia，SU Yidan.An efficient k－medoids clustering algorithm ［J］.Application Research of Computers，2010，27（12）：4517－4519 （in Chinese）.［夏宁霞，苏一丹.一种高效的K－medoids 聚类算法［J］.计算机应用研究，2010，27（12）：4517－4519.］

［3］TAO Xinmin，XU Jing，YANG Libiao，et al.An improved hybrid algorithm based on particle swarm optimization and Kmeans algorithm ［J］.Journal of Electronics ＆Information Technology，2010，32 （1）：92－94 （in Chinese）. ［陶新民，徐晶，杨立标，等.一种改进的粒子群和K 均值混合聚类算法 ［J］电子与信息学报，2010，32 （1）：92－94.］

［4］WANG Xiaohua，SHEN Jie，WANG Rongbo.A new hybrid algorithm based on ant colony and clustering ［J］.Journal of Hangzhou Dianzi University，2010，30 （1）：26－27 （in Chinese）.［王小华，沈杰，王荣波.一种新的基于蚁群和凝聚的混合聚类算法 ［J］.杭州电子科技大学学报，2010，30 （1）：26－27.］

［5］FAN Yujun，WANG Dongdong，SUN Mingming.Improved artificial fish swarm algorithm ［J］.Journal of Chongqing Normal University （Natural Science Edition），2007，24 （3）：24－26 （in Chinese）.［范玉军，王冬冬，孙明明.改进的人工鱼群算法 ［J］.重庆师范大学学报 （自然科学版），2007，24（3）：24－26.］

［6］LIU Bai，ZHOU Yongquan.A hybrid clustering algorithm based on artificial fish swarm algorithm ［J］.Computer Engineering and Applications，2008，44 （18）：136－138 （in Chinese）.［刘白，周永权.一种基于人工鱼群的混合聚类算法［J］.计算机工程与应用，2008，44 （18）：136－138.］

［7］LIU Jia.Improved artificial fish swarm algorithm and its applications in function optimization ［J］.Journal of Shijiazhuang Institute of Railway Technology，2011，10 （3）：33－36 （in Chinese）.［刘佳，改进人工鱼群算法及在函数优化问题中的应用 ［J］.石家庄铁路职业技术学院学报，2011，10 （3）：33－36.］

［8］HE Dengxu，QU Liangdong.Artificial fish swarm clustering algorithm ［J］.Application Research of Computers，2009，26（10）：3666－3668 （in Chinese）.［何登旭，曲良东.人工鱼群聚类分析算法 ［J］.计算机应用研究，2009，26 （10）：3666－3668.］

［9］Xie Juanying，Jiang Shuai.A simple and fast algorithm for global k－means clustering ［C］／／Wuhan：Second International Workshop on Education Technology and Computer Science，2010：36－40.

［10］Chu Xiaoli，Zhu Ying，Shi Juntao，et al.Method of image segmentation based on fuzzy C－means clustering algorithm and artificial fish swarm algorithm ［C］／／Guilin：International Conference on Intelligent Computing and Integrated Systems，2010：254－257.

［11］Cheng Yongming，Jiang Mingyan，Yuan Dongfeng.Novel clustering algorithms based on improved artificial fish swarm algorithm ［C］／／Tianjin：Sixth International Conference on Fuzzy Systems and Knowledge Discovery，2009：141－145.

［12］JIANG Mingyan，YUAN Dongfeng.Artificial fish swarm algorithm and its applications ［M］.Beijing：Science Press，2012：43－66，110－130 （in Chinese）. ［江铭炎，袁东风.人工鱼群算法及其应用 ［M］.北京：科学出版社，2012：43－66，110－130.］