基于菌群优化的K均值聚类算法研究

郭 婧,耿海军,吴 勇

(1.晋中职业技术学院 电子信息系,山西 晋中 030600;2.山西大学 自动化与软件学院,山西 太原 030013)

伴随着物联网技术的发展,互联网应用正朝着精细化的方向发展。通过对连入网络的数据进行深入挖掘分析,可以获得潜在价值数据,为互联网创新应用提供技术支持。但是万物互联的发展必然引起互联网数据的规模化增长,从海量数据中获取价值数据的难度提升,数据挖掘的方法显得尤为重要[1]。聚类作为数据挖掘算法的一种,能够通过抽象方法将多维数据特征进行有效计算,分析数据之间的相似属性和差异特性[2],从而将海量的看似无关无序的数据进行有效归类,为数据的多样化应用提供了有效保证。

数据聚类挖掘有2个方面的特点:一方面是待聚类的数据量大,对聚类算法的效率有一定要求;另一方面是待聚类的数据维度高,聚类运算复杂度高。因此数据聚类挖掘算法应着重解决这2个方面的问题。基于K均值(K-means)聚类的数据挖掘在处理多维数据样本时存在聚类精度低的缺点,这是因为传统K均值聚类存在局部寻优陷阱和全局寻优不理想的问题。当前,研究人员尝试使用群体智能算法来解决上述问题。刘云恒[3]对云计算环境的数据挖掘算法展开了研究,主要研究了多种群体智能算法在数据挖掘中的适用性,分析了不同智能算法在数据挖掘中的优劣,并阐述了群体智能算法在数据挖掘中的应用价值。Karimi等人[4]分析了遗传算法在数据挖掘中的应用情况,通过聚类分析有效解决了云计算环境的服务质量(Quality of services,QoS)问题。尹芳等人[5]针对K均值聚类在数据聚类中的不足进行了有效改进,采用动态分配聚类中心点的方法解决了K均值聚类效率对初始中心点依赖程度高的问题。但是,基于群体智能算法的数据挖掘大多存在局部过拟合和全局寻优的能力不够理想的问题,准确度和稳定性有待进一步提高。

菌群优化算法作为一种新型仿生智能优化算法,具有比传统优化算法更快的收敛速度和更强的鲁棒性。因此,本文采用K均值聚类来完成数据挖掘,建模简单,复杂度低,并且引入菌群算法对其进行优化,以便进一步提高其聚类性能。通过将菌群算法和K均值聚类相结合的方法,来解决传统数据聚类挖掘不稳定的问题,从而最终获得较高的聚类准确率。

1 基于K均值聚类的数据挖掘原理

K均值聚类的核心思想是根据待聚类点至中心点的距离来判断待聚类点的类别[6]。K均值聚类的复杂度和效率取决于待聚类点的维度。一般而言,聚类的准确率和效率随着待聚类样本的维度增加而降低。因此,聚类在数据挖掘中的应用遇到了困难。在数据挖掘中,待挖掘的数据一般都是高维数据,而且样本容量大,因此多维数据的聚类精度问题和聚类时间问题都是数据挖掘急需解决的关键问题。

除了待聚类的维度外,K均值聚类算法初始中心点的选择也很重要,它影响着聚类的效率。在样本类别相似判别时,设定所属类别距离阈值,然后计算待聚类点和所有中心点距离来划分该聚类点的类别。具体数学描述为:设第i个中心点xi,待聚类的点与xi的距离为[7]

(1)

设中心点xi包含n个属性,表示方法为[xi1xi2xi3…xin],和待聚类点xj[xj1xj2xj3…xjn]的距离为

(2)

根据式(2)可以计算所有待聚类的样本点至中心点的距离集,根据距离dij来判定xi与xj是否同类。然后根据距离集建立聚类目标函数,求解式(3)的最小值[8]

(3)

将式(3)进一步展开得[9]

(4)

最后得到目标函数为

(5)

2 菌群优化算法分析

(6)

式中:Pmax和Pmin分别表示菌群边界上下限。

第i个细菌的第j次趋化、k次复制、l次驱散的行为之后,其位置Pi(j,k,l)变化为Pi(j+1,k,l),方法为[10]

(7)

式中:C(i)为步长,Δ(i)表示细菌运动的方向向量。

在趋化运动过程中,其适应度函数J(Pi)为[11]

(8)

式中:dattract和wattract为引力深度和宽度,hrepellant和wrepellant为斥力深度和宽度。

从第j至(j+1)次趋化后的适应度更新方法为[12]

Ji(j+1,k,l)=Ji(j,k,l)+J(Pi)

(9)

经过复制后

(10)

式中:Nc表示趋化总次数。对适应度值较低的个体按一定概率驱散,重新求解所有个体适应度,继续重复复制和趋化操作。

3 基于菌群优化的K均值聚类算法

根据数据样本建立K均值聚类模型。根据参与聚类各节点和各自中心点的距离值建立适应度函数。初始化菌群算法,通过菌群算法优化各节点至中心点距离,获得稳定的样本所属类别,其具体流程如图1所示。

图1 基于菌群优化的K均值聚类的数据挖掘流程图

在实际操作时,可以根据需要调节驱散和趋化的次数。驱散次数过少,可能获得局部最优解;而趋化次数过少,不利于快速搜索到聚类适应度最优值;但是两者次数过大,会导致聚类效率过低。因此,在实际操作中,应当合理设置驱散和趋化次数。

4 实例仿真

为了验证基于菌群优化的K均值聚类在数据挖掘中的性能,分别对实验数据集和UCI(University of California,Irvine)数据集进行实例仿真。选择的实验数据集为某在线学习平台,该平台主要面向初、高中阶段的英语教学领域,其运行时间已经长达6 a,共积累了12万注册用户的各种数据信息,日平均活跃用户数达到4 000人,课程种类十分丰富。

根据学习者的学习习惯进行聚类并推荐关联类别的学习资源,根据学习者反馈验证聚类准确率。选择常用UCI 5种数据集进行聚类准确率仿真,并验证菌群优化对K均值聚类的性能提升程度。最后采用常用聚类算法和本文算法对UCI 5种数据集分别进行实例仿真,验证不同聚类算法的聚类性能。

菌群算法主要参数dattract=0.1,wattract=0.2,hrepellant=0.1,wrepellant=10,驱散次数l=20,趋化总次数Nc=200。菌群算法主要参数是参照菌群算法的相关文献,多次实验的经验结果。

4.1 基于实验数据集的聚类性能

半年时间内每个月从在线学习平台抽取3 000个数据样本,构建6个数据集,其样本量共计18 000个,训练和测试比例为3∶1。根据用户在平台上的学习习惯,选择属性重要度排名前6名的属性进行聚类。4 500个测试样本的聚类结果如表1所示。

表1 测试样本的用户聚类准确率表

从表1可得,4 500个测试样本被划分成6个类别,其聚类准确率最低值为92.518%,最高值为95.613%,标准差性能差距不大。对比发现,A和F类的聚类准确率高于B、C、D和E类,这与属性值差异有较大关系。当属性差异较小时,容易出现聚类误差,造成聚类准确率降低的情况。

为了验证菌群优化对聚类准确率的影响,分别采用K均值和基于菌群优化的K均值聚类算法对6个不同数据集进行聚类仿真。表2为2种算法的聚类准确率性能表。

表2 2种算法的聚类准确率性能表 %

从表2得,对于6种不同数据集,引入菌群算法对K均值聚类进行优化后,聚类准确率得到明显提升,所有数据集的平均聚类准确率都高于92%,数据集6获得了最高的平均聚类准确率95.538%。

4.2 基于菌群优化的K均值聚类算法处理UCI数据集

为了进一步验证基于菌群优化的K均值聚类算法在UCI数据集挖掘中的性能,对常用UCI数据集进行聚类仿真,UCI数据集结构如表3所示。

表3 UCI仿真数据集结构表

4.2.1 聚类准确率

对表3的数据集按照3∶1进行训练和测试样本数分配,分别采用K均值和基于菌群优化的K均值算法进行聚类准确率仿真。表4为菌群算法的聚类优化性能对比表。

表4 2种算法的聚类优化性能对比表

由表4对比得到,经过了菌群算法优化后,K均值聚类的性能得到了较大改善。K均值的聚类准确率最高为82.301%,标准差最优值为1.927×10-6;经过了菌群算法优化后,聚类准确率最高为85.465%,标准差最优值为1.252×10-6。其中Iris数据集的聚类准确率提升了7.043%,提升幅度最大,提升幅度最小的Seeds数据集为3.844%,其他3类数据集的准确率提升均保持在6%以上。相比于准确率,标准差的提升幅度更加明显,这表明经过菌群优化后,对UCI 5种数据集的聚类稳定性提升效果大幅改善。

4.2.2 聚类时间

分别从表3的5种数据集中各选取1 000个数据样本,构成UCI混合数据集。对混合数据集分别进行K均值和基于菌群优化的K均值聚类仿真,聚类准确率设定阈值为70%,聚类时间仿真结果如图2所示。

图2 2种算法的优化时间图

从图2得,当聚类达到稳定时,本文算法的聚类标准差性能明显优于K均值聚类算法。而且本文算法对5 000个混合样本完成聚类消耗的时间更短,大约需要70 s,而K均值聚类算法大约需要93 s。而且在运行时间为[20,25]的时间段内,K均值聚类算法有一段时间的标准差未发生变化,收敛性能较差。

4.3 不同聚类算法的聚类性能

下文对常用聚类算法进行聚类性能比较,分别采用层次聚类[13]、DBSCAN(Density based spatial clustering of applications with noise)[14]、粒子群优化(Particle swarm optimization,PSO)K均值聚类算法[15]和基于菌群优化的K均值聚类算法对表3中的Iris和Seeds样本进行仿真,结果如图3所示。

图3 聚类准确率图

从图3可以看出,对于Iris和Seeds数据集,基于菌群优化的K均值聚类准确率最高,层次聚类次之。从聚类效率方面来看,本文算法低于层次聚类排在第2位。对比图3(a)、(b)发现,4种算法在Seeds数据集上的聚类性能明显优于Iris数据集,这可能是因为Iris样本包含22个属性,远大于Seeds数据集的13个属性,属性过多导致聚类运算复杂度提升而造成了聚类精度不高。而对比聚类效率,Seeds数据集优于Iris数据集,这主要是在因为参与聚类的样本数量上Iris数据集要远大于Seeds数据集,且Iris属性个数偏多。

5 结束语

本文提出了一种基于菌群优化的K均值聚类的数据挖掘方法。该方法采用菌群算法优化K均值聚类中各节点至中心点距离,通过合理设置菌群的趋化和驱散次数,优化引力和斥力参数,不断提高数据聚类的适应度,从而获得最佳且稳定的样本所属分类判别。后续研究将进一步优化菌群算法参数,或者引入并行运算机制,提高算法的聚类效率,增强基于菌群优化的K均值聚类算法在大规模数据挖掘中的适用性。