面向高维数据的人工蜂群优化密度峰值聚类

叶丽珠,郑冬花,隋 栋,吴 迪

(1.广州商学院 信息技术与工程学院,广东 广州 511363;2.马来西亚管理与科学大学 研究生院,雪兰莪 莎阿南 40100; 3.北京建筑大学 电气与信息工程学院,北京 102406;4.哈尔滨工程大学 计算机科学与技术学院,黑龙江 哈尔滨 150001)

大数据分析给多个领域发展带来了新的机遇,通过大数据技术可实现对各种复杂数据的潜在价值挖掘。聚类技术作为大规模数据统计分析的常用方法[1],能够有效挖掘海量异构多维数据之间的关系,完成非标签的数据分类,为复杂异构数据的各种模型分析提供数据支持。通过聚类,将数据进行有效归类整理,提高数据的可用性。复杂高维数据聚类由于待聚类样本数据结构复杂,且呈现样本特征分布稀疏与特征冗余明显等特点[2],完成低失真聚类的难度大幅提升,因此针对高维数据的聚类需要采取更精准的聚类算法。

当前,关于高维数据聚类的研究成果较多,武森等人[3]从样本特征扩展的角度去降低高维样本的聚类复杂度,解决了高维样本的聚类问题,但聚类效果仍有待加强。向志华等人[4]采用贪心选择算法提取高维样本的关键特征,并采用特征加权方法对高维特征进行重要排序,以达到降维作用,降低高维数据复杂度,但是聚类效率受到了影响。本文采用改进密度峰值聚类(Density peaks clustering,DPC)算法用于数据聚类,为了提高DPC应对高维数据样本聚类的适应度,采用人工蜂群(Artificial bee colony,ABC)算法对DPC的距离阈值进行优化改进,最后采用改进的DPC算法解决复杂高维数据聚类的问题。

1 DPC

设N个样本集X的类别总数为k,其数学表示为C={C1,C2,…,Ck},其中k≤N,且X=C1∪C2…∪Ck,Ci∩Cj=∅(i≠j)。

点xi和点xj距离值[5]

(1)

式中:n为维数。

xi在所有样本点中的密度[6]

(2)

式中:rc为距离阈值,χ(x)核函数一般为

(3)

在实际密度计算时,为了考虑核函数连续可导,常引入高斯函数代替,则式(2)变为[7]

(4)

xi的最小距离δi为距离xi最近且密度值比xi大的点的距离[8]

(5)

根据计算的ρi和δi生成决策图,两者中值较大的点成为候选中心点。为了找出ρi和δi均较大的点,采用求积方式[9]

γi=ρi·δi

(6)

然后选择ρi、δi和γi均较大的点作为簇中心点,具体过程见图1。

图1 决策图生成过程示意图

图1中样本初始分布为3个类别,选择ρi、δi和γi均较大的点作为簇中心,生成以2、13和30为候选簇中心的点。确定中心点,接着按照各样本点至簇中心的距离判定聚类类别。

2 改进的DPC

2.1 ABC算法

ABC算法主要根据蜜源的搜寻路径来寻找最优解,现对ABC算法进行数学描述,设蜜源为i,引领探测蜂在第d维的初始随机位置为Xid,其位置具体为[10]

Xid=Ld+rand(0,1)(Ud-Ld)

(7)

式中:Ud与Ld分别为蜜源在第d维搜索的边界上下限范围,d∈{1,2,…,D},D表示总维度。

探测蜂在Xid处展开蜜源搜索,新蜜源为Vid,其搜索方式为[11]

Vid=Xid+φ(Xid-Xjd)

(8)

式中:j≠i,φ取值范围为[1,1],Xjd为搜索范围内第d维除了Xid外的任意位置。

当探测蜂探测到新蜜源时,会将新旧蜜源进行质量对比,对比方式为计算两者的适应度值,新蜜源Vi=[Vi1Vi2…Vid]的适应度fi的计算方法为[12]

(9)

若Vi的适应度值优于Xi,则用新蜜源替换原蜜源。探测蜂将蜜源数据传达至跟随蜂,而跟随蜂选择其偏好的蜜源概率pi为[13]

(10)

式中:SP为总蜜源数。

探测蜂搜索蜜源的策略为:当迭代次数trial达到最大次数Itr max时,则重新跳转至式(7),否则继续寻找最优蜜源。

(11)

2.2 基于ABC的DPC

在DPC算法实现过程中,rc的选择非常重要,rc既决定了DPC的聚类精度,也影响着DPC的执行效率。DPC由于受rc的影响大,对样本点分布密度不均衡的处理效果差,因此本文采取ABC算法对DPC进行改进。

采用ABC对DPC进行优化后,ABC-DPC不用再进行DPC的rc参数选择,而是通过蜜源搜索获得最优rc参数值。在获得了待聚类的样本之后,计算各样本点两两之间的距离,并整理成矩阵集合。然后计算各样本点的密度值及距离值,选择两者较大的样本点作为样本聚类的中心点,然后计算剩余节点相对各中心点的距离值,选择较近的中心点所属类别作为各剩余节点的类别。具体的ABC-DPC聚类流程如图2所示。

图2 基于ABC-DPC的聚类流程图

3 实例仿真

为了验证ABC-DPC算法的聚类性能,进行实例仿真。仿真数据来源为某大型电商平台,选取了4类不同商品(手机、电脑显示器、键盘和鼠标)作为聚类样本集,见表1。首先对不同维度的样本聚类仿真, 生成DPC的决策图并分析其性能;然后分别采用DPC和ABC-DPC进行聚类操作,分析ABC对DPC的优化程度。

表1 在线购物平台样本集参数表

3.1 不同样本量的决策图性能仿真

在DPC聚类过程中,核心内容是获得准确率有效的决策图,通过决策图来选择合适的聚类类别中心点,然后根据样本点离各中心点的距离获得样本类别。从表1的4种数据集中分别选择1 000个样本进行ABC-DPC聚类,其中ABC-DPC算法针对4个数据集求解的决策图如图3所示。

由图3可知,通过选择不同的数据维度,得到了4幅ABC-DPC聚类决策图。当数据维度为26时,样本点大部分分布在δ<1的范围内,ρ轴的样本点分布范围比较广;当数据维度增加至34时,相比于维度为26时,1<δ<2的样本点在增多;而当维度增加至47时,δ>1的点相比于维度34时增加不多,但ρ值更大的样本点攀升明显;样本数据维度为56时,相比于前3个样本维度,样本点处于δ>2且ρ>50处的点数增加明显,根据DPC算法的中心点选择策略,候选中心点数目增加,因此选择合适中心点的难度在提升。

图3 决策图

由图3可知,从整体上来看,当样本数据维度增加时,局部密度ρ最大值增大,这是因为样本数据维度增加,聚类中心阈值范围内的节点数增多,因此密度值会增大。对于4个不同维度的数据集进行ABC-DPC聚类准确率仿真,统计结果如表2所示。

表2 ABC-DPC的聚类准确率表

从表2可知,当样本维度从26提升至56时,平均聚类准确率降低了1.097%,这可能是因为维度增加,在进行ABC的距离阈值优化时,难度提升而造成优化效果下降,促使DPC聚类效果微降。降低效果较小,表明ABC-DPC聚类在高维数据聚类时优势明显,聚类准确率不随着维度的大幅提升而明显下降。

3.2 ABC的DPC改进性能

为了验证ABC对DPC聚类算法的改进性能,分别采用DPC和ABC-DPC算法对4个样本集进行聚类仿真,并求解2种算法的聚类准确率。从图4可知,经过ABC优化后,ABC-DPC的聚类准确率明显高于DPC算法。ABC-DPC收敛时4种样本集聚类的平均准确率约为0.95,而DPC算法在数据集1和2的聚类准确率约为0.8,在数据集3和4的聚类准确率约为0.7,这表明DPC算法在处理高维数据聚类时效果较差。从图4中可观察到,随着样本维度增加,DPC和ABC-DPC算法的聚类准确率差值明显扩大,这说明引进了ABC对DPC进行优化之后,对高维数据的聚类效果提升明显。

图4 DPC和ABC-DPC的聚类准确率曲线图

从聚类时间方面来看,稳定时DPC算法的聚类时间和ABC-DPC算法的聚类时间相差较小,这是因为加入了ABC优化之后,距离阈值的优化需要消耗更多的时间。但是,从图4中结果可得两者差距并不大,这主要是因为引入了ABC优化后,DPC算法能够获得更优的距离阈值。在相同聚类准确率阈值条件下,虽然ABC优化需要消耗时间,但ABC-DPC达到收敛时能够节省迭代次数,降低聚类模型复杂度。

3.3 不同算法的聚类性能

为了验证不同算法的大数据聚类性能,分别采用常用聚类算法模糊聚类[14]、决策树[15]、卷积神经网络(Convolutional neural network,CNN)[16]、非参数密度峰值聚类[17]和ABC-DPC算法对样本进行仿真,样本来自于公开的UCI(University of California,Irvine)数据集,具体如表3所示。对表3的5类样本集进行聚类仿真,其性能结果如表4和表5所示。

表3 UCI仿真集参数表

从表4可知,5种算法对于UCI数据集4个类别样本的聚类性能差异明显。对于聚类准确率,在4个数据集上,均表现出ABC-DPC算法聚类准确率最高,非参数密度峰值聚类算法次之,模糊聚类算法最差的特点。横向对比,在seeds集上4种算法表现出了最高聚类准确率,在Gisette集上4种算法表现出了最低聚类准确率,在seeds集上ABC-DPC算法聚类准确率达到了0.867 5。

从表5得,对于聚类准确率的标准差性能,ABC-DPC和非参数密度峰值聚类算法性能较好,两者收敛时的标准差明显优于模糊聚类和决策树算法,其中ABC-DPC算法在seeds集上获得了最优标准差0.251 3。

表4 5种算法的聚类准确率表

表5 5种算法的聚类准确率标准差表

4 结束语

采用ABC-DPC算法应用于高维数据聚类,能够获得较高的聚类准确率。通过合理设置ABC算法的探测蜂蜜源搜索范围,优化DPC算法的核心参数值ρ和δ,选择两者中值较大的点作为聚类中心点进行聚类,与常用高维数据聚类算法对比,ABC-DPC算法能够获得更高的聚类准确率性能,且聚类效率高,在高维聚类方面适用度高。