【作者】 刘健；

【导师】 陈东明； 王刚；

【作者基本信息】 东北大学 ， 软件工程（专业学位）， 2013， 硕士

【摘要】 随着互联网的广泛应用,各行各业需要分析处理的数据量飞速增长,甚至达到海量数据的水平。传统的聚类分析算法往往由于物理机器内存不足或效率低而不能满足处理大数据网络数据的需求。分布式计算的出现,为解决以上问题提供了有效途径。但对结构化网络还没有高效的分布式算法进行有效处理。此外分布式k-means聚类算法初始中心点选取的主观性使得聚类结果不稳定,聚类时间长,而改进的分布式k-means聚类算法初始中心点选取的过程比较复杂,时间和空间复杂度比较高。针对以上问题,本文分析了聚类算法方面的国内外研究现状,对SCAN算法、Clique算法及分布式k-means算法的基本原理及优缺点进行研究,并对Hadoop平台的分布式文件系统和分布式框架的特性和运行机制进行深入研究。本文根据Hadoop平台的工作原理,提出两种分布式聚类算法：(1)结构化分布式聚类算法,结合SCAN算法思想,采用MRC理论设计有限MapReduce轮数,控制混洗排序所需时间,利用Map内合并技术对网络流量进行控制,控制内存开销；(2)基于密度的分布式聚类算法,结合分布式k-means算法和Clique算法,利用分布式CLIQUE算法自动快速地确定聚类个数,选取全局初始聚类中心点,利用格密度除去噪声点,。利用模拟生成结构化网络和空间网络在Hadoop集群中进行实验,实验结果表明结构化分布式聚类算法具有良好的加速比与扩展性,基于密度的分布式算法在划分效果和效率方面优于分布式k-means算法,算法对含噪声数据的数据集处理效果更好,具有聚类稳定、准确率高与效率高的特点。更多还原

【Abstract】 With the wide application of Internet, the amount of data needed by every walk of life to deal and analyze grow rapidly, and even reaching mass data. Due to physical machines out of memory or low efficiency, the traditional clustering analysis algorithms often cannot meet the needs of processing large data network. The emergence of distributed computing provides an effective way to solve the above problems. But there is no efficient distributed algorithm for structured network. The subjectivity of the initial center selection of distributed k-means clustering algorithm makes the clustering result unstable. The process of initial center selection of improved distributed k-means clustering algorithm is complicated, and its time and space complexity is high.According to above problem, this thesis analyzes clustering algorithm on the research status at home and abroad, studies the basic principle, the advantages and disadvantages of SCAN algorithm, Clique algorithm and distributed k-means algorithm, as well as the characteristics and operation mechanism of distributed file system and distributed framework on Hadoop platform. This thesis put forward two kinds of distributed clustering algorithm: one is a structured distributed clustering algorithm, which combines SCAN algorithm, uses MRC theory to design limited MapReduce round number, utilizes the Map merging technology to control the network traffic; another is a algorithm based on density, which combines distributed k-means algorithm and Clique algorithm, uses distributed Clique algorithm to automatically and quickly determine the clustering number, select the global initial clustering center, and deal well for data set containing noise data.Structured and space networks generated by simulation experiment in the Hadoop cluster is utilized to do experiments. Experimental results show that structured distributed clustering algorithm has good performance, availability and scalability. Experimental results show that the distributed algorithm based on density in classification effect and the efficiency is better than that of distributed k-means algorithm.更多还原