ABSTRACT

Artificial Fish Swarm (AFS) is a stochastic search optimization algorithm with a fast convergence speed, and it is widely used in different areas due to its tolerance for descriptions and mechanism model of questions. In this paper, we propose a new clustering algorithm called Artificial Fish Swarm Mixed Clustering (AFSMC) by performing a combination of AFS and similarity based K-means. And we further propose a relative entropy based optimization method for AFSMC. Finally, we evaluate our proposal by conducting classification on the real data of large scale water pump, which is a new thought for analyzing the potential correlations among the different pumps. The experimental results show that our proposal outperforms the existing clustering approaches.

Keywords:Artificial Fish Swarm Algorithm, Relative Entropy, Mixed Clustering, Large Water Pump

基于人工鱼群混合聚类的大型水泵分类研究

单丽^1*，杨栋梁²，姚磊²，于文文¹，段长余¹

¹合肥恒大江海泵业股份有限公司，大型潜水电泵装备安徽省重点实验室，安徽 合肥

²合肥三益江海智能科技有限公司，安徽 合肥

收稿日期：2016年12月8日；录用日期：2016年12月21日；发布日期：2016年12月29日

摘 要

人工鱼群是一种随机搜索优化算法，具有较快的收敛速度，对问题的机理模型与描述无严格要求，具有广泛的应用范围。本文在该算法的基础上，结合传统的K-means聚类方法，提出了一种新的人工鱼群混合聚类算法(AFSMC)，并给出相对熵混合聚类优化方法。文中将几种算法应用于大型水泵数据的分类，算例分析表明，基于相对熵的AFSMC算法在准确率与时间效益上都具有较明显的优越性。

关键词 :人工鱼群算法，相对熵，混合聚类，大型水泵

1. 引言

大型水泵是一种重要的防水、治水设备，是水利、矿山等部门安全生产的重要保障。目前对于大型水泵的物联网建设及实时运行数据管理，主要是从使用方的角度，即是基于某一泵站若干台设备进行的，实现实时监控、智能预警、报警等功能 [1] [2] [3] 。而从大型水泵制造商的角度，若能建立动态数据库，掌握其所有水泵产品在全生命周期的运行状态，则一方面可以通过实时监控提升服务质量，另一方面还能利用大数据分析促进产品技术革新升级，具有重要的战略意义。而对多种产品规格，多种数据来源，海量规模的大型水泵数据进行大数据研究，一个关键任务就是对大型水泵数据准确、快速的聚类分析。

K-means算法是一种经典的聚类分析算法 [4] [5] [6] ，该算法的最大优势在于简洁和快速，但主要不足之处在于聚类结果极大依赖聚类中心的选取，聚类过程易陷入局部最优等。而与之相对的，源于对鱼群行为特点的研究 [7] [8] ，由李晓磊等 [9] [10] 提出并得到了大量后续的关注与改进 [11] [12] [13] 的人工鱼群算法(AFS)则具有良好的克服局部极值、获取全局极值的能力，不受初始化的随机性影响，且对搜索空间具有一定自适应能力。刘白等 [11] 根据K-means算法与AFS算法的相关特点，发展了一种混合聚类算法，即先使用AFS算法做初始化优化，然后再进入主体的K-means算法流程，取得了一定的优化效果。

本文以AFS为主体，融合了K-means算法，提出了一种新的人工鱼群混合聚类算法(AFSMC)。并根据大型水泵数据特点，采用相对熵作为距离度量，对该算法做新一步的优化。利用合肥恒大江海泵业股份有限公司的真实数据，构建仿真实验对几种聚类方法进行验证，算例分析表明，采用相对熵度量的AFSMC兼具聚类的准确性和快速性，在大型水泵数据的聚类分析上具有很好的应用前景。

2. 人工鱼群混合聚类算法

2.1. K-means聚类算法

K-means是一种常用的聚类分析算法 [4] [5] [6] ，是一种基于划分的方法，需要预先指定聚类数目和聚类中心，它能够使聚类域中的所有样品到聚类中心距离的平方和最小。算法基本思想是：以空间中k个点为中心进行聚类，对最靠近他们的对象归类，通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果。假设要把样本集分为k个类别，算法描述如表1所示。

该算法的最大优势在于简洁和快速。算法的关键在于初始中心的选择和距离公式。一般K-means聚类算法选择欧氏距离作为最常见的距离度量，衡量的是多维空间中各个点之间的绝对距离。

表1. K-means聚类算法

2.2. 人工鱼群算法

人工鱼群算法 [9] [10] (AFS)是根据鱼类的活动特点提出的一种基于动物行为的自治体寻优模式。在水域中，鱼生存数目最多的地方一般就是该水域中富含营养物质最多的地方，依据这一特点模仿鱼群觅食、聚群、追尾等行为，这些行为在不同的条件下会相互转换。鱼类通过对行为的评价，选择一种当前最优的行为进行执行，到达食物浓度最高的位置，从而实现全局最优。

采用面向对象技术重构人工鱼模型，将人工鱼封装成变量和函数两部分。表2、表3分别给出人工鱼模型中变量部分和函数部分定义。

人工鱼基本行为描述

① 随机行为Rand()

是作为人工鱼在觅食行为Prey()中的缺省行为，是在解空间中随机寻找大于自身状态的行为。

② 觅食行为Prey()

通过视觉或味觉来感知水中的食物量或浓度进而来选择趋向。设人工鱼i当前状态为，在其感知范围内随机选择一个状态：

(1)

若Y_i < Y_try，则向该方向前进一步：

(2)

反之，再重新随机选择状态，判断是否满足前进条件，反复尝试Try_number次后，若仍不满足前进条件，则随机移动一步：

(3)

③ 聚群行为Swarm()

鱼在游动过程中为保证群体的生存和躲避危害，会自然的聚集成群。在算法中对该行为中的人工鱼有如下规定：一是尽量向邻近伙伴的中心移动；二是避免过分拥挤。设人工鱼当前状态为，探索当前邻域内(d_ij < Visual)的伙伴数目n_f及中心位置X_c。若，表明伙伴中心有较多食物且不太拥挤，则朝伙伴的中心位置方向前进一步：

(4)

否则，执行觅食行为。

④ 追尾行为Follow()

追尾行为是一种向邻近的有着最高适应度的人工鱼追逐的行为，在寻优算法中可以理解为是向附近

表2. 人工鱼参数

表3. 人工鱼函数

的最优伙伴前进的过程。设人工鱼当前状态为，探索当前邻域内(d_ij < Visual)的伙伴中Y_j为最大值的伙伴X_j。若，表明伙伴X_j的状态具有较高的食物浓度且周围不太拥挤，则朝X_j的方向前进一步：

(5)

否则，执行觅食行为。

2.3. 改进的人工鱼群混合聚类算法

由K-means模型给出分类模型结构，AFS算法将给出的模型在解空间中循环迭代到最优，由此消除K-means初始化随机性的影响，发挥AFS全局寻优特性。一条鱼代表一个K-means分类模型，若干鱼组成一个鱼群，在所有训练实例域空间中，每个鱼都各自按照一定的原则寻找最优值，循环修正自己的K-means模型，并将最优值对应的模型记录在公告板，直到达到迭代次数以后，公告板上模型即为最后的分类最优模型。算法流程如图1所示。

每条鱼中包含的参数除了基本AFS算法参数以外，还有K-means聚类模型，是一个具有n个属性的实例，将其分为k类的描述。将此模型编码，如下：

(6)

图1. 人工鱼群混合聚类算法(AFSMC)流程图

人工鱼按照一定规则在解空间中游动，比较执行觅食、聚群、追尾等行为。为使得鱼群能够最大范围覆盖到最优解，鱼群需要保持一个合适的密度，即人工鱼之间要保持相应的距离。每条人工鱼以自己状态为中心，搜索视野范围内的人工鱼并与其进行交互。与K-means聚类算法类似，可以选择欧氏距离作为距离度量，衡量各人工鱼之间的绝对距离。为了消除量纲选择造成的绝对数值的差异，使用相对熵 [14] [15] 描述人工鱼之间距离。

计算两条人工鱼的相对熵距离，假设p，q代表两条不同状态的人工鱼，每条鱼的k分类模型编码为，其中k为分类数，n为数据维度；中第分量结构为：

(7)

则可计算两条鱼的概率分布

(8)

进一步可计算得两条鱼之间的相对熵：

(9)

相对熵越大，两条人工鱼的状态模型差异越大；反之，差异越小。

用欧式距离或相对熵距离法判别视野范围Visual的其他人工鱼，在Visual范围内计算人工鱼基本行为，评估并执行最优的人工鱼基本行为，得到此人工鱼最新的参数模型，将实例在参数模型下按照余弦相似度 [14] 分类，并计算其离差平方和 [16] 作为当前食物浓度，并将其与公告板上比较，更新公告板；继续迭代执行以上过程，达到迭代次数以后结束算法。

3. 混合聚类算法在大型水泵中的应用

3.1. 实验设置

1) 对大型水泵数据进行清理和集成，经过分析后选择其中5种不同类型水泵作为实验数据，汇总后数据集共包括6个属性，最后一个属性标记其真实类别；

2) 算法参数设置，人工鱼群的个体数Total = 15，迭代次数iterate_times = 2，尝试次数Try_number = 30，聚类中心个数K = 5，人工鱼群移动的最大步长，相对熵距离：Step = 60、视野范围Visual = 200，欧式距离：Step = 10、视野范围Visual = 2500，拥挤度因子，随机初始化为同一个值。

3.2. 实验结果与分析

分别实现基本的K-means算法，基于欧氏距离的AFSMC算法和基于相对熵的AFSMC算法，应用于大型水泵数据集。

三种算法得出的聚类中心结果分别如表4、表5和表6所示。对比发现，三种算法给出的聚类中心大致吻合，证明了算法及仿真的可靠性。将聚类分析结果与水泵真实类型相比较，三种聚类方法的准确率分别为：K-means算法0.80；基于欧式距离AFSMC模型0.91；基于相对熵AFSMC模型0.96。证明三种算法均具有一定的有效性，且本文提出的基于相对熵AFSMC算法具有更高的准确率，并且其准确性也高于文献 [11] 中的相关结果。对两种不同距离度量的AFSMC算法进行比较，其收敛曲线如图2所示。可以看出，基于相对熵的AFSMC算法比基于欧式距离的AFSMC算法迭代收敛更快，其收敛精度也更高。

表4. K-means算法聚类中心结果

表5. 基于欧式距离AFSMC聚类中心结果

表6. 基于相对熵AFSMC聚类中心结果

图2. 两种人工鱼群混合算法(AFSMC)的收敛曲线对比

4. 总结

本文结合人工鱼群算法(AFS)和K-means聚类分析算法，提出一种新的人工鱼群混合聚类算法(AFSMC)，并给出利用相对熵作为距离度量的优化方法。将几种聚类算法应用于真实的大型水泵数据集，算例结果表明：

1) 几种算法在大型水泵的聚类分析上均具有相当的有效性；

2) AFSMC在准确率上较传统的K-means聚类方法有明显的提高；

3) 利用相对熵优化的AFSMC比采用欧式距离的AFSMC具有更高的准确率和收敛速度。

致谢

本项目为“安徽省自然科学基金资助项目，项目编号1408085MKL82”，在此表示感谢。

文章引用

单 丽,杨栋梁,姚 磊,于文文,段长余. 基于人工鱼群混合聚类的大型水泵分类研究
Research of Large-Scale Water Pump Classification Based on Artificial Fish Swarm Mixed Clustering[J]. 计算机科学与应用, 2016, 06(12): 794-801. http://dx.doi.org/10.12677/CSA.2016.612095

参考文献 (References)