大规模数据集聚类算法的研究进展

A review on clustering algorithms for large-scale data sets

聚类是机器学习领域的一个重要研究方向,在过去几十年间,针对不同类型中小规模数据集聚类算法的研究取得了很大的进展,许多行之有效的算法先后问世.然而,这些算法在处理大规模数据集时,计算复杂度较高,处理高维数据的能力较弱,难以获得令人满意的效果.随着大数据时代的到来,数据的采集和存储变得相对容易和便捷,但数据量也与日俱增,因此,针对各种实际应用的聚类问题应运而生,使得专门针对大规模数据集的聚类算法研究成为当前机器学习领域的重要任务之一.本文以大规模数据集的可计算性为切入点,对目前串行和并行计算环境下专门用于处理大规模数据集的聚类算法进行综述和分析,重点评述了串行计算环境下基于样例选择、增量学习、特征子集和特征转换的聚类算法以及并行计算环境下基于MapReduce、Spark和Storm框架的聚类算法,给出了有关未来大规模数据集聚类算法设计思路与应用前景的思考和讨论,包括基于数据并行和训练过程自动化的聚类算法设计策略及关于社交网络大数据聚类算法的若干理解.

Clustering is an important research branch of machine learning.In the past decades,many well-known clustering algorithms have been designed to handle the clustering problems of small-scale and medium-scale data sets.Although these algorithms have obtained the good clustering performances,they are usually inefficient when dealing with the clustering tasks of large-scale data sets due to the high computation complexity and weak capability of handling the high-dimensional data.In the age of big data,the collection and storage of data become easier and more convenient.The clustering technologies are desperately needed to satisfy the requirements of real applications which generate a great deal of large-scale data sets.Thus,the clustering for large-scale data sets becomes an important research direction in the field of machine learning.In this paper,the current clustering algorithms are reviewed and analyzed for large-scale data sets under both the sequential clustering algorithms based on instance selection,incremental learning,feature subset and feature transformation and the parallel clustering algorithms based on MapReduce,Spark and Storm computational frameworks,respectively.Unlike the existing literature reviews,we focus on the computability of large-scale data sets.Meanwhile,we provide some new thoughts for the designs and applications of clustering algorithms for large-scale data sets,including the design strategies of clustering algorithms based on data parallelization,automation of training process,and some understandings of clustering algorithms for large-scale data in social networks.