大数据聚类算法研究

郭雯雯 邵全义

摘 要：随着大数据时代的来临，数据量不断地增加，对大数据环境下的数据进行有效的聚类已经成为现阶段的一个研究热点。文章围绕这一课题，从介绍大数据环境下的特点以及对算法的处理要求开始，对面向大数据的聚类算法的划分进行简单的介绍，指出其中的问题，并对大数据下的有效聚类算法的划分进行展望，希望能够借此加深对于聚类算法的理解。

关键词：大数据；聚类算法；划分

1 大数据下聚类算法的含义

大数据是指以多元形式，由许多来源搜集而组成的庞大数据组。电子商务网站、社交网站以及网页浏览记录等都可以成为大数据的数据来源。同时，大数据又是指在现有的技术条件下无法在规定的时间内对数据进行传输、存储、计算和应用等的数据集合。大数据的数据体量巨大，数据的类型繁多，价值密度较低，处理速度较快，其核心的价值在于对海量的数据进行存储和分析，具有成本低、效率高等优势。随着信息化技术的不断发展，大数据已经成为当代炙手可热的一个话题，各个行业都在对大数据下的聚类算法的应用进行研究。大数据是信息化社会的一个产物，像是一块蕴含着能量的煤矿，利用大数据的优势，可以为大量消费者提供产品或服务的企业提供进行精准营销的技术，促进企业的转型和升级。

采用聚类算法对大数据进行处理解决抽样数据处理上的局限性，通过聚类，可以对大数据集进行随机分块，每一块又是原数据集的一个可以保证抽样能够独立进行的样本集合，在足够小的范围之内保证处理结果的可靠性。

在物联网技术的不断发展下，聚类作为数据挖掘的一个重要的手段，在无先验知识的前提下揭示数据之间的内在联系，将某些具有共同属性的数据聚成一个簇，减小簇间的相似性，扩大簇内数据之间的相似性，是数据挖掘以及机器等学习领域的重要研究课题，属于无监督模式识别的一种。大数据环境的发展，使得在数据处理上的要求不断增加，面对每天所存在的几百维乃至上万维的数据，传统的聚类算法不能够很好地与这些任务要求进行匹配，导致处理效率低下、效果差等情况的出现，迫切需要定义新的聚类算法，提高算法的稳定性和保证聚类效果的准确性。

2 大数据下的聚类算法划分

现阶段大数据聚类算法的具体的划分方式如图1所示。

2.1 单机聚类算法

单机聚类算法由传统聚类算法、基于抽样的聚类以及基于降维的聚类3个部分组成[1]。

2.1.1 传统聚类算法

传统聚类算法包含以下几种算法[1]。

（1）分區聚类算法。该类型的划分是基于点的相似性，在单个分区中根据彼此之间的分离距离来进行划分，但是由于其需要用户预先定义一个不具有确定性的参数K。现今具有代表性的分区算法主要有CLARANS，PAN和K-Means等。

（2）分层聚类算法。它就是指将数据按照不同的层次来进行划分，划分的依据是根据数据自底向上或自顶向下来进行的，划分后的每种结果就代表了一种层次分类树。现阶段的代表性算法有ROCK，CURE和BIRCH等。

（3）基于密度的聚类算法。这种聚类划分方法能够有效地过滤噪音，以一种任意的方式来发现不同密度的区域，以此来达到处理数据的目的。

（4）基于网格的聚类。这种聚类算法主要由3个步骤组成：①将空间划分为矩形方格；②将方格按照密度的高低进行筛选，选取密度低的方格；③对高密度的方格按照相邻的结合方式进行归类形成簇，这样便可以降低复杂度，代表性的算法就有STING，CRIDCLUS以及CLICK等。

（5）基于模型的聚类。它可以解决测量划分的不确定的问题，但是基于多元概率分布的规律进行处理不可避免地使得其在数据处理时的速度较慢。

2.1.2 基于抽样的聚类算法

基于抽样的聚类算法只需要在数据集的一个样本上应用聚类算法就能够推广到整个数据集，重点关注较小的数据，有效减少聚类的时间和节省空间，提高数据处理的经济效益。主要是根据以下的公式来推测其样本的大小。

其中，f是抽取到指定数据的比例，（0≤f≤1）；n为数据规则；ni为簇Ci的规模。

抽样聚类主要有以下3种聚类算法。

（1）基于随机选择的聚类算法（Clustering Algorithm based on Randomized Search，CLARANS）。它是由CLARA演变过来的，继承了CLARA在处理规模数据上的优势，有效地节约运行的时间和降低算法的复杂性，其主要目的就是通过一个整体的图来挖掘出其局部的最优处理方式，在动态处理上具有明显的优势。

（2）利用层次方法的平衡迭代规约和聚类（Balanced Iterative Reducing and Clustering Using Hierarchies，BTRCH）。它可以利用其自身的数据结构，对所有存在的数据点进行筛选之后存放到内存中去，提高数据的处理效率。在这个算法中有两个重要的步骤，首先是它需要对数据点进行扫描并在内存中建立一棵树；其次就是运用聚类算法对所建立好的树的各个叶子节点进行处理。

（3）针对大型数据库的高效的聚类算法（Clustering Using Representatives，CURE）。前述所讲的算法一般都采取单个的数据点来表示一个聚类，这种模式只适用球形聚类，在实际中会出现各种不同类型的聚类，而CURE便能够很好地解决这类问题，利用一组分散的数据点来表示这个聚类，把每一个数据点都看成一个独立的聚类，并依次对相邻的聚类进行合并，以最短的距离为基础，在每个阶段利用堆和K-D树来分别记录和表示每个聚点间的距离以及每个聚类的所有代表点。同样的，CURE也可以使用抽样技术来提高计算的速度，利用分区的方式，对每个分区进行局部的分层聚类直到达到预设的聚类数的临界值或者两个需要合并的聚类之间距离的某个阈值。如此再重复几次，使得没有被抽中的数据点也可以被分配到就近的聚类中，通过常数因子来缩小代表点和聚类之间的中心距离。

2.1.3 基于降维的聚类算法

变量的数量和实例的数量是测量数据大小的两个主要的维度，由于其在分析数据时很可能由于自身数值的大小而产生问题，因此在应用聚类算法时必须要对其进行一个预先的处理，以降低失误发生的可能性。降维的目的是基于一个事先定义的标准来消除无关和冗余的信息，缩小样本空间，避免出现高维度情况下较为复杂的局面。

2.2 多机聚类

多机聚类是区别于单机聚类的一种聚类模式，其又可以分为并行聚类和基于MapReduce的聚类[2]。

并行聚类是指对数据进行划分并将其分布在不同的机器上从而提高单个机器聚类的速度，并依此来达到增加扩展性的目的，从而保证在合理的时间内获取合理的结果。

MapReduce是一种将任务分布在大量的服务器上执行的任务分区机制。Map是指将一个任务分解为更小的任务到不同服务器上执行的一个阶段；Reduce则是将这些阶段所得出的結果进行执行合并的阶段。MapReduce可以利用改进的K-means算法来消除其在迭代上的依赖，提高数据处理的效能；同时，借助于改进后的最大期望（Expectation Maximization，EM）算法，它可以减少计算机时间和内存的开销，有效提高数据处理的效能。

3 结语

目前聚类的方法有很多，其的划分方式也多种多样。随着大数据时代的不断发展，越来越多的聚类方法逐渐被提了出来。本文对现有的大数据环境下的聚类算法的不同处理方式进行了划分，虽然每种聚类算法都有适用的领域，但是也同时存在着需要改进的地方，本文只是指出了其中的一些问题，希望能够在接下来的研究中不断地发展聚类算法，为未来大数据环境的发展提供更多可靠高效的聚类算法。例如，可以采用面向大数据的快速自动聚类算法，适应大数据环境下的高维数据自动聚类，达到降低聚类维度的目的，达到平衡性和提高它的速度；采用简单的粒子编码方式，与FRE-PSO算法相结合的模式来自动聚类等，使得聚类的效果最大化。

[参考文献]

[1]李斌，王劲松，黄玮.一种大数据环境下的新聚类算法[J].计算机科学，2015（12）：247-250.

[2]周丽华，黄成泉，王林.一种自动模糊聚类的算法[J].统计与决策，2014（20）：16-19.