基于分布式计算的AP聚类并行化方法研究与应用

摘要

聚类是一种基于数据对象的特征对数据集进行聚合的数据挖掘方法，主要目的是聚集相似的数据对象。随着传统互联网及移动互联网的飞速发展，企业和用户产生的数据呈爆炸式增长，面对海量数据时传统的聚类挖掘计算极为耗时，不能有效地满足数据挖掘的时效性需求。因此，为了应对海量数据的处理，算法优化与并行化研究成为热点。
　　AP聚类算法是近几年提出的一种新型的方法，目前已被广泛研究与应用。与K-Means等算法相比，AP聚类不需要预设聚类中心，它把每个数据对象都视为潜在的聚类中心，通过数据对象间相互传递消息自动产生聚类中心。但这种聚类算法的时空复杂度较高，随着数据量的增大，整个计算耗时也迅速增大。为了使AP聚类算法能有效应用于海量数据分析，本文即主要研究并实现AP聚类算法的并行化方法，使聚类算法可在云计算集群环境下自动高效地并行化执行。
　　Hadoop是一种开源的分布式计算框架，基于Google的MapReduce并行化思想将并行化的底层实现细节作了封装，使得开发人员只需关注并行的策略方法。针对Hadoop在处理迭代式算法的不足，Berkeley提出了Spark分布式内存计算框架，通过将数据转化为RDD进行缓存有效提升了迭代式算法的执行性能。本文在分析两种计算平台的特点基础上，首先设计实现了并行的AP聚类算法，并分析了并行算法的性能以及两种平台下并行算法执行的性能差异；再通过KDD99的入侵检测海量数据集的测试实验，表明在两个计算平台下并行AP聚类算法都具有良好的加速比和扩展性，且经由Spark内存计算框架的优化，AP聚类算法的执行可获得更高的效率，更适合海量数据的聚类分析应用。
　　本文最后设计开发了一个基于云计算的聚类分析应用服务平台，即在后台将AP并行聚类等算法的实现无缝集成封装到Hadoop和Spark平台，对外则提供简单易用的Restful服务接口，同时提供可供本地调用的云聚类服务SDK，使开发者可直接调用并行化的聚类算法，有效屏蔽云计算底层实现细节，便于一般开发人员快速应用聚类云计算服务。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪 论

1.1 研究背景及意义

1.2 国内外研究现状

1.3 本文的主要工作

1.4 论文组织结构

第2章 相关理论知识和关键技术

2.1 聚类分析

2.2 分布式计算平台Hadoop

2.3 内存计算平台Spark

2.4 Web服务和Restful接口

2.5 本章小结

第3章 基于Hadoop的AP聚类并行化方法设计与实现

3.1 AP聚类的性能瓶颈

3.2 MapReduce并行化基本方法

3.3 并行化AP聚类设计思想

3.4 并行化AP聚类实现问题

3.5 基于MapReduce框架的并行AP聚类设计与实现

3.6 实验验证及结果分析

3.7 本章小结

第4章 基于Spark的AP聚类的并行化方法设计与实现

4.1 传统MapReduce计算模式到Spark的转换

4.2 Spark环境下并行AP聚类设计与实现

4.3 Hadoop与Spark并行AP聚类实验性能比较

4.4 两种环境下并行方法的比较与分析

4.5 本章小结

第5章 基于云的聚类分析服务平台

5.1 服务平台总体架构

5.2 服务平台各层实现

5.3 服务平台测试

5.4 本章小结

第6章 结论与展望

6.1 结论

6.2 工作展望

参考文献

致谢

攻读学位期间参加的科研项目和成果