基于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]。……