基于Spark的动态聚类算法研究

针对数据流的聚类算法，近年来取得了有效的进展，出现了许多卓有成效的算法。随着信息采集技术的进步，需要处理的数据量越来越大，需要研究针对数据流的并行聚类算法。本文基于串行的数据流聚类算法D-Stream作出并行化改进，用通用的大数据处理框架Spark设计了一个基于分布式架构运行的动态数据聚类算法PDStream。实验结果表明，该算法具有更高的效率和良好的扩展性，能够实现分布式架构下的流数据动态聚类。

当今社会信息化的发展，在生物工程、新能源、企业医疗等新领域出现了海量的数据。由于这些数据持续不断产生，随着时间动态无限增长，近似呈现一种“流”的形态，因此此类数据被称为流数据。针对流数据进行数据挖掘是当前的热门课题。聚类作为数据挖掘领域的一个重要分支，一直以来倍受关注并得到了学者们广泛、深入的研究。它作为一种无监督的学习方式，在数据挖掘过程中能根据数据间的相似性将待处理对象划分为一个或若干个簇，在网络入侵检测、挖掘潜在客户和分析市场情况等方面具有重要应用。

针对流数据的聚类分析因其诸多特点变得相对困难，主要体现在三个方面：1) 低时空复杂度。数据流源源不断地产生且高速到达，它的海量、无限性要求算法不能够存储全部数据，每个数据项的处理也不能花费过长时间，算法在线处理速度应尽量和数据流的流速相匹配。2) 增量的处理新数据。由于流数据数量巨大，数据量未知，因此近乎不可能重复计算原有数据，算法必须能够在已有结果基础上增量处理新的数据。3) 正确、快速的处理离群点。数据流具有不断演化的特性，随着时间的推移数据流可能会不断地改变趋势，算法应能够清晰、快速地识别离群点，且对离群点做出正确的处理。

近年来， 已经有许多优秀的流数据聚类算法诞生， 他们有各自的处理要求和特点。

CluStream [1]算法是一个基于层次的流数据聚类算法，它首次将数据流的处理框架分为在线层和离线层，并引入聚类特征向量来表示聚簇，且采用预先定义的距离阈值来衡量数据项是否属于已知类。DenStream [2]是一个基于密度的流数据聚类算法，该算法将满足一定密度阈值的数据点划分为一个簇，且能够发现球状簇，但该算法对输入参数敏感，参数的变化将严重影响聚类结果，且聚类过程中需要对每个数据对象进行邻域检查，因而计算时间复杂度较大。D-Stream [3]是一个基于网格密度的算法，它将空间划分成一个个离散的网格，将进入系统中的数据映射到对应的网格中，然后操纵这些网格的信息，并将密度较大的相邻网格合并为一个聚簇。DENGRIS-Stream [4]同样是一个基于网格密度的流数据聚类算法，但是它额外加入了滑动窗口，使得聚簇结果消除了历史数据的影响。ExCC [5]是一个针对混合属性设计的算法，属性中包含数字和非数字，它对相邻网格的概念进行了重新定义，使得它适应非数字属性，并且依据数据流速的不同来决定消除历史数据的规模。

FlockStream [6]是一个基于密度的算法， 它基于群体智能[7]， 给每个输入数据指定一个代理，代理在一个提前定义好的虚拟空间中移动，当两个代理相遇则将他们合并为一个聚簇，该算法合并了在线层和离线层，在任何时间都可能生成新的聚簇。以上这些流聚类算法有各自适用的环境，在实际运用中需要针对业务的特点合理进行选择。