云计算中基于群体智能算法的大数据聚类挖掘

唐新宇,张新政,赵月爱

(1.广东工商职业学院 计算机应用技术系， 广东 肇庆 526040；2.广东工业大学 自动化学院， 广州 510090； 3.太原师范学院 计算机系， 山西 晋中 030619)

随着计算机性能和网络带宽的不断提高，云计算技术逐渐得到推广和普及，与云计算相辅相成的物联网技术也得到越来越多的关注[1-3]。与此同时，是随之产生的爆发式的数据，如何利用数据挖掘技术对海量的数据进行分析和处理成为备受关注的热点。网上社交、人工智能和电子商务等各个行业对数据挖掘有较大的需求。数据挖掘作为一种新型的计算机科学技术，在社会需求的推动下得到了快速的发展。研究人员通常构建若干个模型和数据分析工具来提取数据间的隐藏关联，并采用适当的规则或算法采集感兴趣的信息[4]。

目前，面向云计算的数据挖掘工具中最常用的是聚类分析技术，其目标是把某一数据集分解为若干类，并满足以下条件：① 处于相同类中的数据具有较高的相似性；② 处于不同类中的数据具有较小的相似性或没有相似性[5]。现阶段，聚类分析一般被划分为2种类型：基本的聚类分析和模糊聚类分析。相比基本的聚类分析，模糊聚类分析在处理真实社会中的数据(较高的复杂性和多样性)时表现出更好的适应性和鲁棒性。因此，文献[6]提出了基于动态时间规整距离的时间序列数据模糊聚类方法。文献[7]提出了基于模糊聚类的RBF神经网络训练方法，有效提升了模型的预测准确率。文献[8]采用聚类分析法评价4个蓝莓品种的感官品质、营养品质、加工品质等指标，从而筛选出品质较佳的蓝莓品种。但是，模糊聚类分析存在容易陷入局部极值等问题。

群智能优化算法作为一种人工模仿动物群体生活习性的仿生技术，在数据挖掘方面具有较大的应用前景。例如，粒子群优化算法作为群智优化的重要方法之一，能够模拟简单群落中个体以及个体之间的互动行为来搜索全局最优解。利用这个特性，文献[9]提出了基于模糊聚类分析的云计算负载平衡策略，将粒子群优化算法与模糊C均值聚类算法融合得到了PSO-FCM算法，有效提高了模糊C均值聚类算法的正确率。

在文献[9]提出的融合思路基础上，本文提出了一种基于群体智能算法大数据聚类挖掘算法。首先对聚类算法中的模糊C-均值聚类算法进行了分析，然后将亚启发式群智能优化技术中的混合蛙跳算法与模糊C-均值聚类相结合，以便在调整参数少的条件下优化全局搜索能力。仿真实验结果显示，相比其他聚类挖掘算法，提出的算法能够有效解决局部陷阱问题，从而具有较好的聚类效果、准确率和收敛速度，同时算法的稳定性较高。

1 聚类分析

云计算环境下聚类分析的目标为数据的划分，以便将具有较高相似性的数据划分到相同的组中，并将具有较小相似性或没有相似性的数据划分到相同的组中。

1.1 聚类分析的相关概念

通过上述介绍可以看出，聚类分析的本质是一种多维样本分类问题。为了进行样本分类，需要确定数据样本间的相似程度，并且不需要参数，如属性、数量等。为此引入“距离”的概念。设X={x1,x2,…,xp}和Y={y1,y2,…,yp}为2个维度为p的样本数据，则绝对距离的计算方法如式(1)所示[10-11]。

(1)

此外，还有契比雪夫距离、马氏距离和欧式距离等计算方法。第i个样本和第j个样本间的相似系数可以由式(2)得到。

(2)

第i个指标与第j个指标间的相关系数可以由式(3)得到。

(3)

1.2 模糊聚类分析

模糊聚类方法通常用来解决一些不精确和不确定性的问题，例如天气预报。模糊聚类分析的数据模型中，原始数据矩阵的定义如下：

(4)

为了对所有对象m的特征进行划分以便对数据集合进行分组，定义数据对象的表达式如式(5)所示。

U={x1,x2,…,xn}

(5)

其中：xi={xi1,xi2,…,xim},i=1,2,…,n。

模糊聚类分析算法大致可以分为4种[12-14]：谱系聚类法、基于等价关系的聚类方法、图论聚类方法和基于目标函数的聚类方法。由于基于目标函数的模糊聚类方法采用传统的非线性规划原理来处理数据挖掘问题，因此实现起来较为简单，得到了大多数研究机构和科研人员的关注。模糊C-均值聚类算法属于基于目标函数的方法，在大数据量时表现出优秀的性能。因此， 本文的研究对象为模糊C-均值聚类算法。

2 模糊C-均值聚类算法

模糊C-均值聚类算法采用了硬聚类的思想。设X={x1,x2,…,xn}⊂Rs表示一个数据集，xj={xl1,xj2,…,xjk,…,xjn}⊂Rs表示第j个数据样本的s个特征向量，xjk表示第j个数据样本在维度k上的特征值。将数据集X进行分组成为C个子集Y={X1,X2,…,XC},C∈[2,n)。如果Y符合式(6)的要求，那么Y可以视为硬C分组[12]。

(6)

设样本xj属于子集Xi的隶属度为uij，那么可以用隶属矩阵U=[μij]C×n来表示硬C分组，其中μij∈{0,1}。因此， 数据集X的硬C分组可以用式(7)来表示。

∀k;

(7)

因此， 模糊C分组可以用式(8)来表示。

(8)

对于数据集X={x1,x2,…,xk,…,xn}⊂Rs来说，n是数据集X中元素的数量，s是样本xk中属性值的个数。c个聚类中心组成1个矩阵V={v1,v2,…,vi,…,vc}S×C,其中vi={vi1,vi2,…,vis}为第i个聚类中心的元素，c为聚类的类别数，则模糊C-均值聚类算法的目标函数为

(9)

约束条件为：

(10)

第j个样本数据xj到第i个聚类中心vi的欧氏距离为：

dij=||xj-vi||

(11)

第i个聚类中心vi和隶属度uij的计算方法分别如式(12)(13)所示。

(12)

(13)

3 混合蛙跳算法与模糊C-均值聚类算法的融合

3.1 混合蛙跳算法

混合蛙跳算法能够在解决局部搜索问题的时候同时考虑全局信息[15]。在有限空间中，混合蛙跳算法通过模拟青蛙种群的跳动觅食行为来解决组合优化问题。该算法所需的调整参数较少且全局搜索能力较强，混合蛙跳算法示意图如图1所示。

图1 混合蛙跳算法示意图

混合蛙跳算法的流程为：① 算法各参数初始化；② 子种群的划分；③ 组内局部搜索进化；④ 子种群混合。在局部搜索的每一次迭代步骤中，只需要更新一次子种群中最差解，具体方式为：

Di=rand()·(xb-xw),

i=1,2,…,m

(14)

xw=xw+Di,-Dmax≤Di≤Dmax,

i=1,2,…,m

(15)

其中: rand()表示1个大于0且小于1的随机数；Di表示青蛙每次跳动的距离；Dmax表示青蛙每次跳动的最大距离；xb表示各个子种群中适应度值最优解；xw表示各个子种群中适应度值最差解。

3.2 算法融合思想和步骤

如上所述，模糊C-均值聚类算法使用目标函数优化到最小值的方法来求解。但是这样的方式容易使最终解陷入局部极小值点，且收敛速度慢。作为一种群体智能算法，混合蛙跳具有较强的全局搜索特性。因此，本文将混合蛙跳算法和模糊C-均值聚类算法进行结合，来提高聚类效果和优化精度。

基于混合蛙跳的模糊C-均值聚类算法步骤如下：

步骤1 初始化：初始化青蛙种群的数量N，聚类数目c，并设置随机的隶属度原始矩阵，视为初始的聚类划分，根据式(12)计算各类的聚类中心，作为初始混合蛙跳算法中青蛙映射编码。

步骤2 行为选择：根据式(16)计算模拟执行青蛙群体行为后所得的每只青蛙的适应度函数值，并对青蛙按降序进行排列和分组。

(16)

其中：q是一个随机数，其取值范围为[0,1]；Jm表示模糊C-均值聚类的目标函数(式(9))。

步骤3 在每个子种群中进行局部搜索并更新子种群中最差个体直至达到局部搜索最大迭代次数。

步骤4 将子种群混合并及时更新种群最优解。

步骤5 重复步骤2～5，直到达到最大给定迭代次数，此时全局最优解就是初始聚类中心。调用模糊C-均值聚类算法，获得最终的聚类矩阵分组。最后采用最大隶属度规则，对数据集中所有的样本进行属类别标注。

融合算法流程如图2所示。

图2 融合算法的流程

4 仿真实验结果

4.1 实验数据集

为了验证本文提出的融合算法的有效性和先进性，用典型Iris数据集和3组人工数据集 Dataset1对传统模糊C-均值聚类算法[14]、混合蛙跳算法[15]、PSO-FCM算法[9]和本文算法进行了仿真实验。4组实验数据集的各项参数如表1所示。

表1 4组实验数据集的各项参数

4.2 聚类效果分析

在本文实验过程中，设置最大迭代次数为500，子种群个数为5，子聚类数目为3，种群规模为30，模糊指数m=2，群内迭代次数为5。将4种算法分别重复执行40次，并计算每个指标的平均值。4种算法在不同数据集上的实验结果见表2～5。聚类结果的有效性用分类正确率来评估，分类正确率的计算方法如式(17)所示。

(17)

其中：M表示样本聚类正确数；N表示数据集中所含数据对象的总个数。

表2 Iris 数据集上的实验结果

表3 Dataset1数据集上的实验结果

表4 Dataset2数据集上的实验结果

表5 Dataset3数据集上的实验结果

从表2～5可以看出：由于对初始值的敏感度较大，模糊C-均值聚类算法聚类效果比较差；混合蛙跳算法虽然鲁棒性和收敛速度较好且克服了局部极值问题，但是应对大数据聚类划分问题时精度较低；PSO-FCM 算法将粒子群优化算法与模糊C-均值聚类算法结合，利用群智优化算法的优点较好地提高了局部搜索能力，优化了聚类效果，从而得到了较高的准确性。本文提出的融合算法利用混合蛙跳算法最优解来调整模糊C-均值聚类中的聚类中心值，并合理选取适应度函数，提高了全局搜索能力和搜索精度，获得了较好的聚类效果，与PSO-FCM算法的效果相近。

4.3 收敛速度比较

图3～5是对Dataset1、Dataset2和Dataset3分别应用传统模糊C-均值聚类算法[14]、混合蛙跳算法[15]、PSO-FCM算法[9]和本文算法得到的收敛速率对比结果。

图3 Dataset1 数据集上的测试结果

图4 Dataset2 数据集上的测试结果

图5 Dataset3 数据集上的测试结果

由图3～5可知，模糊C-均值聚类算法和混合蛙跳算法的收敛速度较慢；PSO-FCM 算法收敛速率有所提升。由于融合算法所需的调整参数较少，因此能更准确、更快速地得到聚类中心，鲁棒性强，收敛速度较快。

相比其他几种算法，本文提出的融合算法在聚类效果、精确度、收敛速率、鲁棒性上均表现最优。

5 结束语

本文提出了一种基于群体智能算法的大数据聚类挖掘算法。首先对聚类算法中的模糊C-均值聚类算法进行了分析，然后将亚启发式群智能优化技术中的混合蛙跳算法与模糊C-均值聚类相结合，以便在调整参数少的条件下优化全局搜索能力。仿真实验结果显示，相比其他聚类挖掘算法，提出的算法能够有效解决局部陷阱问题，从而具有较好的聚类效果、准确率和收敛速度，同时算法的稳定性较高。