基于Spark的聚类算法优化与实现

赵玉明 舒红平 魏培阳 刘魁

摘要： 在数据挖掘中，针对聚类过程中数据存在的稀疏性问题，如果仍用传统的欧氏距离作为聚类指标，聚类的质量和效率将会受到一定的影响。受到信息论中KL散度的启发，文中提出一种基于Spark开源数据框架下利用KL散度的相似性度量方法，对目前使用的聚类算法进行优化。首先，通过预聚类，对数据的整体分布进行分析;然后，借助KL散度作为聚类的距离指标，充分利用数据集中元素提供的信息来度量不同数据集的相互关系，指导数据的聚类，在一定程度上改善了数据分布稀疏性的问题。整个过程基于Spark分布式数据处理框架，充分利用集群的能力对数据进行处理，提升数据处理的准确度和算法的时间效率;同时利用KL散度作为数据聚类距离指标，以充分考虑数据内部蕴藏的信息，使得聚类的质量得到了提升。最后通过一个实验来验证所提算法的有效性。

关键词： 聚类算法优化; Spark; 數据分布分析; 数据聚类; 聚类分析; 数据处理

中图分类号： TN911?34; TP301.6                 文献标识码： A                     文章编号： 1004?373X（2020）08?0052?04

Optimization and implementation of clustering algorithm based on Spark

ZHAO Yuming1，2， SHU Hongping1，2， WEI Peiyang1，2， LIU Kui1，2

（1. College of Software Engineering， Chengdu University of Information Technology， Chengdu 610225， China;

2. Key Laboratory of Software Automatic Generation and Intelligent Information Service， Chengdu University of Information Technology， Chengdu 610225， China）

Abstract： In the data mining， if the traditional Euclidean distance is still used as the clustering index to deal with the data sparseness in the clustering process， the clustering quality and efficiency would be affected to a certain extent. On the basis of the inspiration of KL divergence in information theory， a similarity measure method using KL divergence and based on Spark open source data framework is proposed to optimize the clustering algorithm used at present. The entire distribution of data is analyzed by pre?clustering.  By taking the KL divergence as the distance index of clustering， the information provided by elements in data sets is fully utilized to measure the mutual relationship of different data sets and guide the data′s clustering， by which the sparseness of data distribution is improved to a certain extent. The whole process is based on Spark distributed data processing framework， by which the data is processed by making full use of the cluster ability to improve the accuracy of data processing and the time efficiency of the algorithm. KL divergence is used as the distance index of data clustering， so that the information hided in the data is fully considered， which may make the clustering quality improved. An experiment was carried out to verify the effectiveness of the proposed algorithm.

Keywords： clustering algorithm optimization; Spark; data distribution analysis; data clustering; clustering analysis; data processing

0  引  言

作为知识库发现的一个步骤，数据挖掘可以帮助人们从大型数据库中提取模式、关联、变化、异常、及有意义的结构[1]。聚类主要源于很多学科领域，包括：数学、计算机科学、统计学、生物学和经济学[2]等。

传统的聚类算法大致可以分为划分聚类、层次聚类、密度聚类等。近年来，量子聚类、谱聚类、粒度聚类等也流行起来。

在划分的聚类方法中，通过构造一个迭代过程来优化目标函数，当优化到目标函数的最小值或极小值的时候，就可以得到一系列不相交的子集，这时每一个子集就是一个聚类[3]。其中，K?means聚类算法就是典型的代表，而在此过程中会遇到如下的三个问题：

1） 如果数据维度非常高，并且呈现出相当大的稀疏性。传统的K?means聚类算法，更多考虑共同项之间的距离，忽略非共同项之间可能蕴藏的信息。尤其在数据分布呈现极度稀疏性的时候，缺乏考虑数据上下文之间的关系，无法达到准确的聚类效果[4]。

2） 在使用K?means进行聚类时，无法很好地衡量出不同数据集中数据的依赖性以及分布不均衡特点。同时缺乏从数据的整体分布进行聚类，导致聚类的质量产生严重的影响[5]。

3） 基于划分的聚类方法，而对于极不规则、大小相差很大的数据集表现的非常不理想。尤其初始聚类中心和聚类数目直接影响了聚类的准确率。同时，数据的并发处理效率很低，无法满足目前大数据处理的要求[6]。

在信息论中，KL散度[5]用来衡量一个分布来拟合另一个分布时候产生的信息损耗。使用KL散度可以将统计学中的概率分布引入进来，充分考虑数据整体的分布特性以及数据集中不同数据提供的信息。Spark作为新兴的、应用范围最为广泛的大数据处理开源框架引起了广泛的关注[7]。相比于Hadoop，Spark在设计之初就是基于内存而设计，这样的分布式框架可以将中间数据处理结果存放在内存中，每次迭代处理数据的时候不需要重复读取HDFS数据，降低了I/O负荷;同时基于Spark的聚类算法设计基于Spark DAG的任务调度执行机制，要优于Hadoop MapReduce的迭代执行机制[8]。

基于以上分析，在面对稀疏数据集的聚类过程中，提出基于Spark的开源大数据处理框架，利用KL散度作为聚类指标，对数据进行聚类。通过这样的方式，提高了聚类的准确度和算法的执行效率。

1  相关工作

1.1  KL散度的引入及数据特征分析

相对熵又称互熵，交叉熵，鉴别信息。Kullback熵，Kullback?Leible散度（即KL散度）等。设P（x）和Q（x）是X取值的两个概率概率分布，则P对Q的相对熵为：

相对熵突出的特点是非对称性，也就是[D（PQ）]和[DQP]是不相等的，但是表示的都是P和Q之间的距离，在本文的算法设计中采取两者的平均值作为两个簇或者类之间的距离。

以下介绍数据分布，在聚类过程中，假设要聚类的数据为：X={X1，X2，…，Xn-1，Xn}。X是n个Rx（x=1，2，…，m-1，m）空间的数据。其基本的分布见表1。

设N是数据集的个数，M是每个数据的最大空间维度，V表示非零数据的个数，K表示此数据集的稀疏度，则：

通常认为K值小于5%的时候，可以将这类数据集归纳为稀疏性数据。

1.2  Spark框架和算法流程

Apache Spark[9]是加州大学伯克利分校的AMPLabs开发的开源分布式轻量级通用计算框架。整个聚类过程基于Spark框架，在设计上，首先，利用Spark分布式开源框架，将几台PC机连接起来，形成主从式的控制结构。主节点对从节点进行任务调度、分发和容错，从节点实现并行计算，此结构被证明是一个拥有高可靠、高并发、高性能计算能力的分布式结构。然后，利用普通机上的HDFS存储系统对数据进行存储。最后利用KL散度作为数据聚类的距离指标，完善对数据聚类的质量控制。针对以上分析，本文提出基于Spark的算法执行流程，如图1所示。

2  基于Spark的聚类算法（KL?Cluster）

2.1  数据预聚类

首先，扫描整体数据，对稀疏数据集上的数据进行预聚类。预聚类是完成对整体数据所属类别的确定过程，可以在整体上分析数据分布情况。

文献[1]提供了一种基于层次思想的计算方法，即COPS。本文在数据的预聚类阶段采用此种方法，对数据的整体分布进行分析。通过预聚类形成的Q（C）曲线，可以直观地看到每个数据分布的依赖性、噪声影响以及边界模糊等情况。完整的设计过程可以参看文献[1]。

2.2  基于KL散度的聚类过程

在聚类过程中，主要分为根据概率矩阵的形成过程、距离矩阵的形成过程以及循环迭代过程。

2.2.1  概率矩阵的形成过程

通过预聚类过程，离散数据集上的数据分为k（k=1，2，…，k-1，k）类。然后循环统计簇中数据在k类数据上分频率分布，这样就会形成一个n×k的概率矩阵。形成的概率矩阵如下：

2.2.2  距离矩阵的形成过程

根据以上的概率矩阵，分别计算矩阵中任意一行和其他一行之间的KL距离，形成整体数据集上的KL矩阵。在KL散度介绍中也谈到了KL具有非对称性，这里采用任意两行相互计算距离的平均值作为实际的KL值[10]。剩下的部分都用0来填充，最后形成上三角概率矩阵如下：

通过形成的KL矩阵，将距离矩阵中小于一定精度的值所代表的两行数据合并[11]。通过以上过程完成对数据集的一次合并，形成新的数据集。对合并后形成的数据集，按照上面的过程形成新的概率矩阵和距离矩阵，再次完成数据的合并。通过不断重复，直到KL矩陣无法达到合并数据的精度后，完成所有数据集的聚类。

3  实验与分析

3.1  数据选择

为了验证本算法的有效性，并且本算法主要针对的是离散性数据集。一方面，引用公开数据集MovieLens中最新的数据，ML?Lastest?Small和Yahoo Music作为数据集;另一方面，在The  Movie  DB中下载数据，然后将数据清洗、整理，得到179位观众对国内外将近180部电影评分的数据集，这里简称为MVD，来验证算法的有效性。数据基本情况见表2。

3.2  过程分析

3.2.1  算法评价指标

在算法准确率和效率上，使用本文提供的算法和Spark MLlib中的K?means算法、高斯混合聚类算法进行对比。在同样使用Spark框架下对比出不同算法的准确率和时间效率。

3.2.2  预聚类分析

首先对每个数据集上的数据集进行预聚类，根据文献[1]的方法，得到的实验结果如图2～图4所示。

通过预聚类可以发现，聚类数目从最优变化到变到两边次优的时候，聚类质量发生大幅度下降。在图2和图3中，可以明显看到有两个基本重合的簇，数据存在一定的关联性。图4中，在达到最佳的聚类数10之前，曲线的变化很小，说明数据由于密度分布不均匀、边界模糊的情况，尤其是在聚类数目达到8的时候，Q（C）曲线出现了一定的上升趋势。

3.2.3  实验结果对比分析

本算法与K?means以及高斯混合聚类运行时间的对比见表3。

从以上的实验结果可以看出，同样是基于Spark的KL?Cluster算法相比于Spark MLlib中提供的K?means和K?Prototypes，聚类的准确度上有了明显的提高。而运行时间在某种程度上增加，时间差距在0.08～0.67 s之间。原因是在预聚类中占用了一段时间，虽然牺牲了一定的时间效率，但是不影響整个算法的执行时间效率。但是针对稀疏性的数据集上的聚类质量得到大幅度的提高。

4  结  语

聚类算法是机器学习算法中经常使用的一类算法，传统的K?means算法并不能很好地处理数据稀疏性问题，在聚类的质量上产生严重的误差。为了解决此问题，本文提出了一种基于Spark的聚类算法。整个执行过程是基于Spark的分布式数据处理框架，首先通过预聚类综合考虑了数据的分布情况，对将整体的数据进行聚类，划分类别;然后根据的数据分布情况构建概率矩阵，计算KL矩阵;最后通过KL矩阵得到数据聚类。通过这样的迭代过程完成聚类。通过这种方式可以减少引言中提到的三个问题，提升对稀疏数据集中聚类质量和效率，同时基于Spark的分布式处理框架提升了数据处理的并行度。

参考文献

[1] 陈黎飞，姜青山，王声瑞.基于层次划分的最佳聚类数确定方法[J].软件学报，2008，19（1）：62?72.

[2] 无恒，李文杰，蒋旻.引入信息熵的CURE聚类算法[J].计算机应用研究，2017，34（8）：2303?2305.

[3] 陈新泉，周灵晶，刘耀中.聚类算法综述[J].集成技术，2017，6（3）：41?49.

[4] LI Jundong， CHENG Kewei， WANG Suhang， et al. Feature selection： a data perspective [J]. ACM computing surveys， 2018， 50（6）： 194.

[5] 杨琪.基于深度学习的聚类关键技术研究[D].成都：西南交通大学，2016.

[6] 王卫卫，李小平，冯象初，等.稀疏子空间聚类综述[J].自动化学报，2015，41（8）：1373?1384.

[7] MENG X R， BRANDLEY J， YAVUZ B， et al. MLlib： machine learning in apache spark [J]. Journal of machine learning research， 2016， 17（1）： 1235?1241.

[8] ZAHARIA M， CHOWDHURY M， FRANKLIN M J， et al. Spark： cluster computing with working sets [J]. Hot cloud， 2010（6）： 1?6.

[9] SALLOUM S， DAUTOV R， CHEN X J， et al. Big data analytics on apache spark [J]. International journal of data science and analytics， 2016， 1（3/4）： 145?164.

[10] 李斌，王劲松，黄玮.一种大数据环境下的新聚类算法[J].计算机科学，2015，42（12）：247?250.

[11] 张文，姜祎盼，张思光，等.基于经验分布和K散度的协同过滤推荐质量评价研究[J].计算机应用研究，2018，36（9）：17?24.

[12] 何玉林，黄哲学.大规模数据集聚类算法的研究进展[J].深圳大学学报（理学版），2019，36（1）：4?17.

[13] 许明杰，蔚承建，沈航.基于Spark的并行K?means算法研究[J].微电子学与计算机，2018，35（5）：95?98.

[14] 徐健锐，詹永照.基于Spark的改进K?means快速聚类算法[J].江苏大学学报（自然科学版），2018，39（3）：316?323.

[15] XIE M， HU J K， GUO S， et al. Distributed segment?based anomaly detection with Kullback?Leibler divergence in wireless sensor networks [J]. IEEE transactions on information forensics & security， 2017， 12（1）： 101?110.

[16] WILSON R C， HANCOCK E R， PEKALSKA E， et al. Spherical and hyperbolic embeddings of data [J]. IEEE transactions on pattern analysis and machine intelligence， 2014， 36（11）： 2255?2269.

[17] AHN H S， YU W. Environmental adaptive RSSI based indoor localization [J]. IEEE transactions on automation science and engineering， 2009， 6（4）： 626?633.

[18] 陆一潇，潘常春，白杰，等.基于对称KL散度的符号大数据动态聚类算法[C]//第八届中国卫星导航学术年会论文集.上海：Springer，2017：89?94.

[19] SOLTANOLKOTABI M， CAND′ES E J. A geometric analysis of subspace clustering with outliers [J]. The annals of statistics， 2012， 40（4）： 2195?2238.

[20] 杨杰，燕雪峰，张德平.考虑KL散度的多源软件缺陷预测方法[J].小型微型计算机系统，2017，38（11）：2494?2498.

[21] 王永，邓江洲.基于KL散度的用户相似性协同过滤算法[J].北京邮电大学学报，2017，40（2）：110?114.

[22] AL?KAHTANI M S， KARIM L. An efficient distributed algorithm for big data processing [J]. Arabian journal for science & engineering， 2017（42）： 3149?3157.

[23] GOU Jie， MA Zitang. Parallel CSA?FCM clustering algorithm based on Mapreduce [J]. Computer engineering and applications， 2016， 52（1）： 66?70.

[24] PATEL V M， VAN NGUYEN H， VIDAL R. Latent space sparse subspace clustering [C]// Proceedings of 2013 IEEE International Conference on Computer Vision. Sydney： IEEE， 2013： 225?232.

[25] FAHAD A， ALSHATRI N， TARI Z， et al. A survey of clustering algorithms for big data： taxonomy and empirical analysis [J]. IEEE transactions on emerging topics in computing， 2014， 2（3）： 267?279.

[26] ZALIK K R. An efficient k?means clustering algorithm [J]. Pattern recognition letters， 2008， 29（9）： 1385?1391.

[27] ZHAO Q， MENG D Y， XU Z B， et al. Robust principal component analysis with complex noise [C]// Proceedings of 31st International Conference on Machine Learning. Beijing： IEEE， 2014： 55?63.

[28] VILLALBA L J G， OROZCO A L S， CORRIPIO J R. Smartphone image clustering [J]. Expert systems with applications， 2015， 42（4）： 1927?1940.

[29] LU C Y， FENG J S， LIN Z C， et al. Correlation adaptive subspace segmentation by Trace Lasso [C]// Proceedings of 2013 IEEE International Conference on Computer Vision. Sydney： IEEE， 2013： 1345?1352.