计算机研究 -基于云计算平台Hadoop的聚类研究.pdf

Abstract

II

Abstract

With the rapid development of Internet technology, sizes of dataset are growing

dramatically. A typical dataset might involve Terabytes or even Petabytes of data. How to

extract meaningful and helpful information quickly and efficiently from vast amounts of

data is a new challenge for data mining. Hadoop is an open source cloud computing

platform, which provides the users the powerful capacities of data collection, storage and

computing. Clustering analysis is an important field of data mining. Research of clustering

system (HDFS) and its programming framework (MapReduce). We also gain an insight

into the basic ideas of different kinds of clustering methods and make an in-depth analysis

of some classical algorithms. Our main purpose of this part is to obtain solid knowledge for

designing and implementing clustering algorithms based on Hadoop.

(2) We propose bigClustering which can be easily parallelized in MapReduce and done

in quite a few MapReduce rounds while many existing clustering algorithms failed to be

effectively migrated to the cloud computing platform. Based on the ideas of micro-cluster,

bigKClustering divides the dataset into many groups and constructs one micro-cluster,

which will be treated as a single point, corresponding to each group. All the micro-clusters

that are closed enough will be connected and put into the same group by the equivalence

final clustering process. It selects a small number of samples which can well represent the

whole original dataset, using particular sampling technology. According to the distribution

characteristics of these samples, it filters the original dataset. The data left after filtering

Abstract

III

and the samples are clustering by an existing algorithm in a single node. Experiments show

that SnIClustering runs very fast, obtains relatively good clustering results and scales well.

IV

摘 要 ............................................................................................................................... I

Abstract ............................................................................................................................ II

目录 ................................................................................................................................IV

第一章 绪论 ..................................................................................................................... 1

§1.1 研究背景和意义 .................................................................................................1

§1.2 研究现状............................................................................................................2

§2.2 Hadoop 架构 .......................................................................................................9

§2.3 本章小结.......................................................................................................... 17

第三章 聚类研究概述 .................................................................................................... 18

§3.1 基本概念.......................................................................................................... 18

§3.2 相关度量.......................................................................................................... 19

第四章 基于微簇和等价关系的聚类算法 ..................................................................... 30

§4.1 问题提出.......................................................................................................... 30

§4.2 相关工作.......................................................................................................... 30

V

§4.3 bigKClustering 算法......................................................................................... 32

§4.4 实验评估.......................................................................................................... 35

§4.5 本章小结.......................................................................................................... 38

第五章 MapReduce 框架上基于采样和过滤的聚类算法 ............................................. 39

§5.1 问题提出.......................................................................................................... 39

§5.2 相关工作.......................................................................................................... 39

§5.3 SnIClustering 算法 ........................................................................................... 41

§6.1 全文总结.......................................................................................................... 47

§6.2 工作展望.......................................................................................................... 48

参考文献 ......................................................................................................................... 49

致 谢............................................................................................................................... 54

攻读硕士期间发表的论文及参与的科研项目 ............................................................... 55