聚类算法综述

JournalofComputerApplicationsISSN1001-90812019-07-10计算机应用,2019,39(7):1869-1882CODENJYIIDU文章编号：1001-9081(2019)07-1869-14DOI：10.11772/j.issn.1001-9081.2019010174聚类算法综述章永来，周耀鉴*(中北大学软件学院，太原030051)(*通信作者电子邮箱[e-mail])摘要：大数据时代，聚类这种无监督学习算法的地位尤为突出。近年来，对聚类算法的研究取得了长足的进步。首先，总结了聚类分析的全过程、相似性度量、聚类算法的新分类及其结果的评价等内容，将聚类算法重新划分为大数据聚类与小数据聚类两个大类，并特别对大数据聚类作了较为系统的分析与总结。齐匕外，概述并分析了各类聚类算法的研究进展及其应用概况,并结合研究课题讨论了算法的发展趋势。关键词:聚类；相似性度量；大数据聚类；小数据聚类;聚类评价中图分类号：TP301；TP18文献标志码:AReviewofclusteringalgorithmsZHANGYonglai,ZHOUYaojian*(SoftwareSchool,NorthUniversityofChina,TaiyuanShanxi030051,China)Abstract：Clusteringisveryimportantasanunsupervisedlearningalgorithmintheageo£bigdata.Recently,considerableprogresshasbeenmadeintheanalysisofclusteringalgorithm.Firstly,thewholeprocessofclustering,similaritymeasurement,newclassificationofclusteringalgorithmsandevaluationontheirresultsweresummarized.Clusteringalgorithmsweredividedintotwocategories:bigdataclusteringandsmalldataclustering,andthesystematicanalysisandsummaryofbigdataclusteringwerecarriedoutparticularly.Moreover,theresearchprogressandapplicationo£variousclusteringalgorithmsweresummarizedandanalyzed,andthedevelopmenttrendo£clusteringalgorithmswasdiscussedincombinationwiththeresearchtopics.Keywords：clustering;similaritymeasurement;bigdataclustering;smalldataclustering;clusteringevaluation0引言把具有相似特性的实物放到一起是人类最原始的活动之—O这也是聚类的最初目的。早在1984年,Aldenderfer等⑴就已经提出了聚类分析的四大功能:一是数据分类的进一步扩展;二是对实体归类的概念性探索;三是通过数据探索而生成假说;四是一种基于实际数据集归类假说的测试方式。在很多情况下，样本数据集并没有分类，即每一个数据样本都没有分类标签。一般而言，聚类指将没有分类标签的数据集，分为若干个簇的过程，是一种无监督的分类方法⑵。实际上，很难对聚类下一个明确的定义。2001年,Everitt等⑶甚至指出提出聚类的正式定义不仅困难而且也没有必要，因为聚类分析本身是一种建立在主观判断基础上的相对行之有效的方法[4'5]o尽管如此,聚类分析还是表达了一般认为的“类内的相似性与类间的排他性”的目标。Hansen等同也已经作了数学上的阐述。给定一个数据样本集：c=iXj=(号1,巧2,…，喰)eR}(1)这里，兀表示一个向量，称为样本点或者样本;兀w表示一个变量，通常称为属性、特征、变量或维等。划分聚类将数据集分为K个簇，需满足：(C=!C1;C2,-,CJ；KWNC&0；i=1,2,…,K(2)IK=xi=l-c,nC,=0;i,j=1,2,…,Kj而层次聚类是将数据集构建成一种树状的结构,即：H={H^H,，-,Hq\-QWNCieH“,CjHt-mI(3)CiCCjorC；Cj=0；m,l=1,2,i承j聚类分析是伴随着统计学、计算机学与人工智能等领域科学的发展而逐步发展起来的,为此,这些领域若有较大的研究进展，必然促进聚类分析算法的快速发展。比如机器学习领域的人工神经网络与支持向量机的发展就促生了基于神经网络的聚类方法与核聚类方法。目前,基于人工神经网络的深度学习(如:AlphaG。围棋系统)也必将推动聚类分析方法的进一步发展。到目前为止，聚类研究及其应用领域已经非常广泛，因此，本文主要以聚类分析算法为主要分析对象，兼论聚类分析的全过程。关于聚类分析,《数据挖掘概念与技术(第二版)》一书中已经有了经典的论述。然而，聚类算法又有了长足的发展与收稿日期：2019-01-23；修回日期=2019-04-09；录用日期：2019-04-10。基金项目：国家自然科学基金资助项目(6160051296)。作者简介：章永来(1978—),男，浙江诸暨人，助理教授，博士，主要研究方向：大数据分析与处理、医疗大数据、海洋大数据；周耀鉴(1987—),男，湖北武穴人，助理教授,博士,主要研究方向:大数据分析与处理、海洋大数据、水下机器人。1870计算机应用第39卷进步。本文首先简要介绍了聚类分析的主要过程，然后分析并总结了样本点之间的相似性度量方法，提出了聚类算法的新分类方式，并总结与分析了各种聚类算法，还对如何评价聚类结果作了过程分析。最后，依靠课题组承担的医疗与海洋大数据的聚类分析研究—山，展望了聚类算法的发展趋势,作为本文的结语。1聚类分析过程聚类分析是一个较为严密的数据分析过程。聚类分析的全过程如图1所示，从聚类对象数据源开始到得到聚类结果的知识存档为止，其中主要包括四个部分研究内容，即特征选择或变换、聚类算法选择或设计、聚类结果评价与聚类结果物理解析等。数据源（特征选择卜或变换r4聚类算法力选择或设计知识存档聚类结果卜物理解析卜4聚类结丿果评价图1聚类分析过程Fig.1Clusteringanalysisprocess1.1特征选择或变换一般情况下，样本数据是杂乱无章的（特别是大数据时代），聚类分析首先需要进行数据集的特征选择或变换。实际上，特征选择与特征变换是降维技术的两大分类。特征选择指的是从数据样本集的所有特征（或称属性）中选择更有利于达到某种目标的若干属性,即原始属性集的一个子集，同时也达到了降低维度的目的;而特征变换则是指通过某种变换将原始输入空间的属性映射到一个新的特征空间,然后在特征空间中根据规则选择某些较为重要的变换后的特征。由于特征选择并不改变其原有属性，所以结果只是一个原始属性的优化特征子集，保留了原属性的物理意义，方便用户理解;而特征变换的结果失去了原始特征的物理意义，但能够提取其隐含的特征信息，移除原特征集属性之间的相关性与冗余性。特征选择或变换在聚类分析过程中占据极其重要的地位，结果的优劣将直接影响最后的聚类效果，应该引起足够的重视。有时,特征选择或变换后得到的有效模式（或称子集）的作用甚至超过聚类算法本身的效用。1.2聚类算法选择或设计依据特征选择或变换后的数据集特性,选择或设计聚类算法,是聚类分析的第二部分研究内容。如果样本集数据都是数值型数据，在选择或者设计聚类算法时需要注意量纲不同的问题。一般情况下，样本集数据不一定都是数值型数据,因此，聚类算法需要有处理非数值型数据的能力。各个样本点之间的相似性度量是聚类算法中的首要问题。相似性度量与经常提到的样本间“距离”有着相同的意义，但是，它们的取值却正好相反，即相似性度量值越大,“距离”越近。同样,相似性度量也是聚类分析全过程中的关键问题之一,将在后文进行详细的介绍与分析。1.3聚类结果评价与物理解析聚类簇只能依靠聚类结束准则函数得到陀」，需要特别指出的是，这种准则函数一般由人为设定的终止条件实现,而这些终止条件并没有统一的标准。由此可见聚类分析是一个主观的归类过程，所以在聚类簇生成以后,必须对聚类结果进行综合评价。聚类分析的本来目标是得到特定数据集中隐含的数据结构。更何况，对于同样一个数据集，不同的聚类算法一般会得到不同的聚类簇。然而，对聚类结果作了评价之后，仍然不能改变聚类分析是“通过数据探索而生成假说”的实质,因此，最后需要对聚类结果作物理上的解析。在聚类结果评价后一段较长的时间内，需要对一种或者几种聚类结果假说，总结出实际的物理意义。聚类簇的物理解析应该与具有实际工作经验的专家作深入的探讨与分析。最后才可以将探讨的结果加入到知识库，作为进一步研究的依据。可见，聚类物理解析并不属于学术研究的范畴，而是一个长期的验证过程。2相似性度量聚类分析是将数据集的相似性样本归为若干类的方法,因此，如何度量样本之间的相似性是聚类算法的关键问题。假设样本间的相似性满足对称性、非负性和反身性，则称样本间的相似性具有可度量性（Metric）。另外，需要注意的是，三角不等式的半度量（SemiMetric）和超度量（UltraMetric）这两种非可度量方式不在本文的探讨范围内。数据集的特征一般分为三种:连续性变量（或称定量型变量）、离散性变量（或称定性型变量）和混合变量。相应的，有三种相似性度量方法。2.1连续性变量的相似性度量1）欧氏距离（EuclideanDistance）o这是一种最常用的样本间距离度量方法，计算公式如下：D（Xi,X］）=J^（xa-X］l-）2（4）V2=1其中:Q表示样本之间的距离；兀与Xj表示一个向量，或称为样本点或者样本;2是样本特征的维数;兔与知表示一个变量,或称为属性;d表示样本的总维数，即样本特征的总数量（以下同）。欧氏距离是一种二范数形式，具有在特征空间中转化和旋转的不变性，一般趋向于构建球形聚类簇。然而,属性值相差较大或线性变换都会使相关性产生形变0为了解决这个问题,需要标准化处理目标数据集,使每一个属性对距离的贡献率相同，这也是消除特征之间量纲差异的常规方式。在进行数据分析之前，需要对样本集在均值与方差上作标准化处理〔切。标准化计算公式如下：xa=（如:-叫）/S［（5）其中:m为均值;S为方差；*表示特征的原值（以下同）。另外，为了去掉不同属性值间在量纲上的差别，需要对样本集作正则化处理。例如在［0,1］区间内的正则化公式为：_州；-min（州；）,,Xu-/~rrL（~rvmax（陶）-min（%.z）2）切比雪夫距离（ChebyshevDistance）o在二维空间中，切比雪夫距离的典型应用是解决国际象棋中的国王从一个格子走到另一个格子最少需要几步的问题。这种距离在模糊C-Means方法〔”加中得到了有效应用。切比雪夫距离的公式可以表示为：第7期章永来等:聚类算法综述18710(&,禺)=111严(扁—切|)(刀此公式的另外一种表示形式为：D(X、,Xj)=11m(xxl-(8)3)曼哈顿距离(ManhattanDistance)。在城市中生活，只能沿着街道从一个地方到另一个地方,为此，人们将生活中熟悉的城市街区距离(CityBlockDistance)形象地称为曼哈顿距离。该距离的计算公式为：=X\Xxl-Xjl\(9)2=1曼哈顿距离在基于自适应谐振理论(AdaptiveResonanceTheory,ART)的同步聚类(SynchronizationClustering,SYC)中有较好的应用;但是，需要注意的是这种距离不再符合在特征空间中转化和旋转的不变性。4