聚类分析及其应用

—聚类分析及其应用摘要数据挖掘是信息产业界热门的研究方向，通过数据挖掘技术能够揭露大量数据背后隐藏的一些有价值的信息，并且利用这些信息促进社会各方面的发展。大数据时代的来临，为数据处理技术获得充分的发展奠定坚实的基础，这不仅促进了科学理论的研究，而且也使得实践应用领域的发展更好地造福人类的生活。聚类分析是数据挖掘的核心技术，它是一种无监督的机器学习方式，即事先不给出一个分类标准，而是直接利用样本数据，自动进行分类。随着数据挖掘的大热，聚类分析自然而然地成为人们争相研究的对象，不论是对其算法的改进，还是对其有效性评价方法的改良，都是在这个时代中人们探讨的热门话题。通过仔细并且认真地研读相关的文献，初步掌握聚类分析的基本内容，进而一一完善每个要点，使本文成为一篇具有可参考性的综述性文章。首先，本文阐述了聚类分析的基本思想及主要步骤。简单来说，聚类的中心思想就是“物以类聚”，通过度量数据间的距离，将关系亲密的放在同一个类当中，而关系疏远的则放在不同的类中。其次，根据聚类的主要步骤，分别详细地阐述了数据的变换方法、相似性的度量、常用的聚类算法以及聚类的有效性评价等四个部分。其中数据的变换方法包括中心化变换、标准化变换、极差标准化变换、极差正规化变换等；相似性的度量包含距离和相似系数；常用的聚类算法有系统聚类法、K-均值聚类法、有序样品聚类法、DBSCAN算法；有效性评价则分为外部评价、内部评价、相对评价。针对以上每个部分，本文均有细致阐述。另外，本文还介绍了关于类的定义及特征，以完善读者对聚类概念的理解。最后，结合实例说明聚类分析在实际生活中的应用价值，并力证本文的研究价值。关键词：聚类分析算法有效性评价AbstractDataminingisahotresearchdirectioninInformationIndustry.Dataminingtechnologycanrevealsomevaluableinformationhiddenbehindalargeamountofdata,andwecanusethisinformationtopromotethedevelopmentofallaspectsofsociety.Theadventoftheeraofbigdatahaslaidasolidfoundationforthefulldevelopmentofdataprocessingtechnology,whichnotonlypromotestheresearchofscientifictheory,butalsomakesthedevelopmentofpracticalapplicationfieldbetterbenefithumanlife.Clusteranalysisisthecoretechnologyofdatamining.Itisanunsupervisedmachinelearningmethod.Itdoesnotgiveastandardclassificationinadvance,butusessampledatadirectlytoautomaticallyclassify.Withthepopularityofdatamining,clusteringanalysisnaturallybecomestheobjectofstudy.Whetheritistheimprovementofitsalgorithmortheimprovementofitseffectivenessevaluationmethod,itisahottopicinthisera.Bycarefullystudyingtherelevantliterature,wecangraspthebasiccontentofclusteringanalysis,andthenimproveeachpointonebyone,sothatthispapercanbecomeacomprehensivearticlewithreference.Firstly,thispaperexpoundsthebasicideaandmainstepsofclusteranalysis.Simplyput,thecentralideaofclusteringis"objectsclusteredbyclusters".Bymeasuringthedistancebetweendata,closeobjectsareplacedinthesameclass,whilealienatedobjectsareplacedindifferentclasses.Secondly,accordingtothemainstepsofclustering,thetransformationmethodofdata,similaritymeasurement,commonlyusedclusteringalgorithmsandtheevaluationofclusteringeffectivenessareelaboratedindetail.Datatransformationmethodsincludecentralizationtransformation,standardizationtransformation,rangestandardizationtransformationandrangenormalizationtransformation;similaritymeasurementincludesdistanceandsimilaritycoefficient;commonlyusedclusteringalgorithmsaresystemclustering,K-meansclustering,orderedsampleclustering,DBSCANalgorithm;effectiveevaluationisdividedintoexternalevaluation,internalevaluationandrelativeevaluation.Inviewofeachpartabove,thisarticlehaselaboratedindetail.Inaddition,thispaperalsointroducesthedefinitionandcharacteristicsofclassesinordertoimprovethereaders'understandingoftheconceptofclustering.Finally,anexampleisgiventoillustratetheapplicationvalueofclusteringanalysisinreallife,andtoprovetheresearchvalueofthispaper.KeyWords:Clusteranalysis;Algorithm;Effectiveevaluation目录TOC\o"1-2"\h\z\u摘要 IAbstract II1.绪论 11.1选题背景及意义 11.2国内外研究状况 22.聚类分析的基础概念 42.1基本思想和主要步骤 42.2数据的变换方法 52.3相似性的度量 62.4类的定义及特征 93.常用聚类算法 103.1系统聚类法 113.2K-均值聚类法 113.3有序样品的聚类分析法 123.4DBSCAN算法 144.聚类有效性评价 164.1外部评价法 164.2内部评价法 174.3相对评价法 185实例分析 185.1系统聚类法的有效性评价 195.2K-均值聚类法的有效性评价 226.总结 24参考文献 26致谢 27聚类分析及其应用1.绪论1.1选题背景及意义近年来，随着经济和信息科学技术的不断发展，数据库的应用在规模、范围和深度等方面呈现出急剧膨胀的状态，社会各方面的数据量持续上升。然而，在这些大数据的背后，隐藏着许多人们未知但有用的信息，获取这些有用的信息能够有效地促进社会经济和科学理论的进一步发展。例如，在人口学研究中，通过构造人口生育分类模式、人口死亡分类状况，以此来研究人口生育和死亡规律。因此，数据挖掘成为了信息产业界热门的研究方向，它是实现大数据转换成有用知识信息的重要途径。所谓数据挖掘，就是通过分析每个数据，从大量无序的数据中自动搜索隐藏于其中有着特殊关系性的信息过程。聚类分析是数据挖掘中最为重要的获取信息的方式，通过运用聚类分析的手段，能够发掘数据中存在的内在关系和隐含信息，并且在此基础之上以预测事物未来的发展趋势。聚类分析也叫群分析，是一种将研究对象分为相对同质的群的多元统计分析技术。聚类与分类有所不同，分类是对当前所研究的问题已知它的类别数目及各类的特征，我们的目的是:要将另一些未知类别的个体正确地归属于其中某一类。而聚类则是事先不知道研究的问题应该分为几类，更不知道观测到的个体的具体分类情况，我们的目的是:通过对观测数据所进行的分析处理，选定一种度量个体间相似程度的统计量，确定类别的数目，建立一种分类方法，并按相似程度对观测对象进行合理的分类。在大数据的背景下，聚类算法的研究成为了热门话题。聚类分析为研究者提供了多样的聚类算法，根据数据类型、聚类目的和实际应用，大体可以分为五类:基于层次的聚类方法、基于划分的聚类方法、基于密度的聚类方法、基于网格的聚类方法、基于模型的聚类方法等。聚类算法的选择取决于数据的类型(R型或Q型)和聚类的目的，不同算法下聚类的结果不同，聚类结果的好坏依赖于不同的算法，为了使分类更好地进行下去，相关研究人员在前人的基础上不断地改进聚类分析算法，为实践应用奠定良好的理论基础。聚类算法是聚类分析过程中的重点内容，通过应用各类聚类算法，我们可以针对给定的数据集实现分类最优化问题。然而，由于聚类过程是一个无监督的学习过程，整个过程中没有示例或预设分类来表明数据集中某种期望关系的有效性，大多数的聚类分析方法都是依赖于猜测，具有极大的不确定性并且缺乏说服力。因此，寻求合理客观的聚类评价方法是聚类分析中至关重要又极其困难的问题。常用的聚类评价方法有三种；外部评价法、内部评价法和相对评价法。聚类分析作为数据处理技术广泛应用于社会、生物、经济等多个领域，与人们的生活息息相关。比如，研究我国31个省市自治区的区域科技创新能力或物价状况；对动植物分类和基因分类，从而获取对某个种群固有结构的认识；根据人均国民收入、人均工农业产值、人均消费水平等多种指标，分析世界上所有国家的经济发展状况；发现不同的客户群，并且通过购买模式描绘不同的客户群的特征等等。聚类分析不仅可以单独作为数据挖掘算法对数据展开研究，并且可以和其他的算法理论相结合，在不同的条件下进行相应的数据处理和分析。聚类可以单独用于文本数据的处理中，常用的有K-均值算法；聚类与遗传算法遗传算法：指模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型遗传算法：指模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型。模糊集理论：指用到了模糊集合的基本概念或连续隶属度函数的理论。聚类分析的历史还很短，其方法也较为粗糙，理论上还不完善，正处于发展阶段，但由于能够解决实际生活中的很多问题，所以深受人们的重视。1.2国内外研究状况从历史背景来看，聚类分析起源于分类学，狭义的分类学特指生物分类学，其任务既要识别动植物的种类、鉴定其学名，又要描述物种与物种之间的亲缘关系和分类系统，再进一步研究物种起源、分布中心、演化过程和演化趋势。在早期植物分类学中，主要依据植物的外部形态和内部解剖特征进行分类，后来把孢粉形态、地域分布和古生物学等方面的内容结合进去，有助于进一步对种类的鉴定和植物演化关系的探讨。管宇：《实用多元统计分析》，杭州：浙江大学出版社，2011年版，第159页。随着科学的发展和生产技术的进步，有时单纯地凭借经验和专业理论知识是不可以确切分类的，需要定性分析和定量分析相结合起来进行分类，数学工具逐渐被引进分类学中，形成了数值分类学。随着多元统计分析的发展，从数值分类学中逐渐分离出了聚类分析。1.2.1国外研究状况1967年，JamesMacQueen正式提出了K-Means聚类算法。由于K-Means聚类算法在获得一个局部最优值时会停止运算，且只能发现聚类结果是凸形的数据集，也只对数值型数据有效。1986年，Rousseeuw和Kaufman分别提出了CLARA算法和PAM算法。1998年，Huang则给出了一种适合于分类属性数据的K-Modes算法。1977年，Laird、Dempster和Rubin基于模型思想提出了EM聚类算法，即期望最大算法。1984年，Edelsbrunner和Day对凝聚层次聚类算法进行了早期综述。1995年，Kaufman和Rousseeuw提出了分裂层次DANA聚类算法。1996年，Lwny、Zhang和Ramakrishnan在借助CF树的基础上进行层次聚类,提出了BRCH聚类算法。1998年，基于密度的思想，Xu、Sander、Kriegel和Ester提出了DBSCAN聚类算法。1999年，为了降低聚类算法对参数的依赖程度，Sander、Ankerst、Kriegel和Breunig提出了一种簇排序的方法——OPTICS算法，该算法大大地提高基于密度的聚类算法的性能。1997年，Muntz、Yang和Wang基于网格的思想提出了多分辨率方法——STNG算法。1998年，Chatterjee、Zhang和Sheikholeslami则提出了一种通过小波变换来替换原特征空间的多分辨率的聚类算法——WaveCluster算法。1.2.2国内研究状况我国数据挖掘发展起步较晚,这样导致我国对聚类分析算法的研究较少。2005年，高惠璇提出了关于类的定义，此前我们知道聚类分析的目的是对样本进行分类，但并未给出过类的定义。2006年，根据加权的思想，叶海军在模糊测度聚类方法的基础上，提出了加权模糊聚类的方法，其权值依赖于统计特性。2008年，李莹通过聚类结果的信息提取，以获得样本中最本质的信息，并基于最小描述长度原理作出相应聚类评价。同年，杨燕、靳蕃、KAMELMohamed等人对聚类的有效性评价的方法进行归纳总结，主要分为外部评价、内部评价和相对评价。2010年，根据放射信息传播聚类算法和SAGE数据的Poisson统计特征，唐东明提出了一种自适应的聚类分析算法，并给出了一个聚类结果校验测度，以该测度为代价函数可以对聚类的结果进行优化。2014年，陈新泉为克服K-均值聚类算法对初始化过于敏感的缺点，提出了K-中心点轮换法。此外，为在聚类质量和时间复杂度之间取得良好的均衡，提出了一种基于近似类抽样的组合聚类算法。针对FCM算法的改进，将K-均值聚类算法与特征权重优化相结合，推导出FCM聚类算法与特征权重优化相结合的优化迭代公式。2015年，董琦璠利用WAND算法在倒排索引结构中查询与中心点相似的一定数量的样本，这样大大地降低了K-均值算法的时间复杂程度。2017年，王建培提出了一种代表类与类之间分离程度的对偶中心测度，并在此基础之上，提出一个全新的聚类结果有效性指标对划分式聚类算法进行评价。2.聚类分析的基础概念聚类分析也叫群分析，是一种将研究对象分为相对同质的群(类)的多元统计分析技术。我们想要彻底地了解聚类分析，首先要将聚类分析的一些基本概念弄清楚，比如聚类的基本思想、主要步骤、相似性的度量等等。2.1基本思想和主要步骤常言道:“物以类聚”，即是将具有相同性质的事物放在一起，这就是聚类分析的核心思想。那么，如何去衡量事物两者是否可以归为一类，即聚类的方法和聚类的标准。具体来说，我们认为所研究的样品或指标之间有着不同程度的亲疏关系（相似程度）：首先，通过定义能够度量样品或指标间亲疏关系的统计量，以这些统计量作为划分类别的依据；其次，按照相似性的大小，将相似性较大的样品或指标归为一类；最后，将关系密切的聚到一个小的分类单位，关系疏远的聚到一个大的分类单位，直到所有的样品或指标都被聚类完毕，把不同的类型全部划分出来，形成一个由小到大的分类系统。李静萍，谢邦昌李静萍，谢邦昌：《多元统计分析方法与应用》，北京:中国人民大学出版社，2008年版，第51页。在大数据时代，聚类分析是一种极为重要的多元统计分析方法，其主要步骤如下：（1）处理数据：在获取大量相关数据后，如若要从数据中挖掘出任何信息，就必须先对数据进行预先的处理，借助数据更好更准确地反映隐藏在其背后的本质。其中包括选择数量、类型和特征的标度，以及移除孤立点。首先，选择数量、类型和特征的标度依赖于特征抽取和特征选择，特征抽取是把一个输入的特征转换为另一个崭新的显著特征，特征选择则是在所有数据特征中提取重要的特征，这些常常被人们用来获得适合的特征集以避免高维数据带来的麻烦；其次，由于孤立点是不依赖于一般数据模型或行为的数据，则孤立点时常会导致聚类产生偏差，影响聚类的最终结果，故此我们在进行聚类前必须将其消除，以便获得更加精准的聚类结果。（2）定义距离函数：我们秉承“物以类聚”的理念，通过定义度量数据间亲疏关系的距离函数，以此作为划分类别的根据，然后按照相似性的大小，将相似性较大的数据归为一类。由于特征的标度和特征的类型具有多样性，距离函数的选择一定要考虑多方面的因素，它经常依赖于实际应用。例如，在特征空间，通过定义距离度量来衡量不同对象的相似性，许多距离度量应用在不同的领域，一些常见的距离度量，如SMC和PMC，常常被用作衡量不同数据之间的相似性。（3）聚类：将数据分配到相异的类当中，这是聚类分析的重要步骤。同一批数据在不同的聚类方法下，得到的聚类结果是不同的。基于层次的方法和基于划分的方法是聚类分析的两个主要的方法，其中层次方法是对给定的数据集进行层次式的分解，直到达到某个标准为止，而划分方法是基于某个标准产生的一个嵌套的划分方式，它可以衡量一个类的分离性或者不同类之间的相似性，以此用来分裂类或合并类。另外，聚类分析方法还包括基于密度的方法、基于网格的方法、基于模型的方法等。（4）评价：聚类结果的有效性评价是聚类分析的另一个重要的阶段。从本质上来说，聚类结果的好坏取决于类内距离和类间距离，我们希望同一个类中的数据点之间的距离越小越好，而类与类之间的距离越大越好，这样就可以将数据集清楚且准确地进行划分。聚类的有效性评价的方法大致可分为内部度量、外部度量和相对度量。2.2数据的变换方法针对不同的变量，通常来说都有不同的取值范围、不同的量纲、不同的数量级单位。为了使不同取值范围和不同量纲的数据可以放在一起进行比较，则对数据的变换处理是必不可少的，常用的数据变换方法高惠璇高惠璇：《应用多元统计分析》，北京:北京大学出版社，2005年版，第219页。（1）中心化变换xSS数据经过变换，所有变量的均值都为0，且协方差阵不变。（2）标准化变换x数据经过变换，所有变量的均值都为0，标准差为1，并且进行标准化变换后的数据与变量的量纲无关，则达到消除量纲的目的。（3）极差标准化变换x数据经过变换，所变量的均值都为0，极差为1，且数学符号，在计算分析中可以降低误差产生的概率；同时，进行极标准化变换后的数据也是没有量纲的量。（4）极差正规化变换x数据经过变换，0≤xij此外，数据变换的方法还有对数变换、平方根变换、立方根变换等等。它们最重要的作用是将非线性数据结构变换为线性数据结构，以便适用于相应统计方法的需要。2.3相似性的度量聚类分析进行分类的对象包括样品和变量，根据聚类对象的不同分为Q型聚类和R型聚类，对样品进行分类处理的成为Q型聚类，而对变量进行分类处理的称为R型聚类。简单来说，Q型聚类的方法即是对样品进行聚类时采用距离作为衡量亲疏关系的指标，同时R型聚类方法就是对变量进行聚类时借助相似系数作为相似性的度量。2.3.1距离 我们在度量样品间的亲疏程度时，常用距离作为度量指标。获取的每个样品中有p个变量，它们分别从不同方面描述该样品的性质，从而形成一个p维的向量。如果我们把n个样品看成p维空间中的n个点，那么两个样品间的亲疏程度直接可用维空间中对应两点的距离来度量即可。设Xi=(xi1,xi2,…,xip)'高惠璇：《应用多元统计分析》，北京：北京大学出版社，2005年版，第221页。（1）闵氏（Minkowski）距离dijq=当q=1时，dij当q=2时，dij当q=∞时，dij在各指标大小相近和没有其他辅助信息时，闵氏距离因相对简单而常常被选用。但在解决多元数据分析问题时，闵氏距离系列就会出现缺陷，其不足之处主要表现在两个方面：第一，它没有考虑到变量之间的相关性，只是要求分量方差相等且不相关，这对多元数据的处理效果不好；第二，与各变量的量纲有关，由于各变量的量纲不同，会呈现出各变量相差较大的情况，导致“大数吃小数”的现象，即样品间的距离大小主要与所谓的大数有关。（2）兰氏（Canberra）距离d兰氏距离是由Lance和Williams最早提出来的，故称为兰氏距离。该距离在使用的过程当中，要求所有数据均大于零(xij闵氏距离和兰氏距离均是在假设变量间相互独立的情况下讨论的，即在正交空间中讨论两个样品之间的距离。然而，在实际问题中，变量之间往往有着一定程度的相关性，为了消除变量间的相关性，我们可以使用马氏距离。（3）马氏（Mahalanobis）距离设Xi与Xj为变量，μ表示其均指向量，d马氏距离是由印度统计学家马哈拉诺比斯于1936年引入的，故称为马氏距离。显然，与其他各种距离相比，马氏距离最大的优势在于考虑了变量之间的相关性。那么，马氏距离既不受变量之间量纲的影响，又排除了变量相关性的干扰。除此之外，如果我们将原始数据进行线性变换的处理，结果马氏距离不变。尽管如此，在聚类处理前，如果所有的数据都进行均值和协方差的计算来求马氏距离，最后的效果并不是很好。由于马氏距离在实际情况当中也不是理想的距离，故我们引入了斜交空间距离。（4）斜交空间距离d其中，rkl表示Xk和X我们知道变量与变量之间存在着一定程度的相关性，如果用正交空间距离来度量两个样品间的距离，必会导致聚类的谱系结构发生变形，而斜交空间距离则可以使谱系结构不发生形变。2.3.2相似系数从几何意义上来说，多元数据中变量可以看作多维空间中的一个向量，用有向线段来表示。在进行多元数据分析时，我们不仅关注数据的大小问题，而且更加在意变量的方向。那么，我们可以通过这些向量的方向趋同性来考察变量间的相似程度，从而引入相似系数朱建平：《应用多元统计分析》，北京：科学出版社，2016年版，第76页。朱建平：《应用多元统计分析》，北京：科学出版社，2016年版，第76页。（1）夹角余弦cos其中，两个变量Xi与Xj是p维空间的两个向量，且∣cos（2）相关系数r其中，变量Xi与Xj是|cij夹角余弦和相关系数作为度量变量相似程度的两种工具，可以把它们统一记为cij。当|cij|=0时，Xi与Xj正交，说明两者不相关；当|cij|=1时，Xi与Xj平行，说明两者完全相似；当|cij|接近0时，说明变量在实际问题中，我们经常把变量的相似性度量转换为距离，即dij=1−cij，其中dij表示变量之间的距离大小，这样可以简便计算。如果dij较小，2.4类的定义及特征 聚类分析研究的是对样品或变量的分类问题，那么又何为类？在现实生活中，在不同的领域，关于类的定义都有所不同，我们要给出一个既统一又严格的定义谈何容易。2.4.1类的定义 在1977年，Rao给出了三种关于类的定义高惠璇高惠璇：《应用多元统计分析》，北京:北京大学出版社，2005年版，第238页。定义1：设阈值T是给定的正数，若集合G中任两个元素的距离dijd则称G对于阈值T组成一个类。定义2：设阈值T是给定的正数，如果集合G中每个数学符号都满足：1其中n是集合G中元素的个数，则称G对于阈值T组成一个类。定义3：设T和H(H>T)是两个给定的正数，如果集合G中两两元素距离的平均满足：1其中n是集合G中元素的个数，则称G对于阈值T，H组成一个类。类似的还可以给出以下两种定义。定义4：设T是给定的正数，若对集合G中任一个一定存在，使得这两个元素距离dijd则称G对于阈值T组成一个类。定义5：设阈值T是给定的正数，将集合G任意分为两类：G1和G2，这两类之间的距离D(则称G对于阈值T组成一个类。2.4.2类的特征设类G包含的样品记为X1,X2,⋯,Xn（1）均值：X（2）样本离差阵AG及样本协方差阵SAS（3）类的直径：用DG表示类G的直径，DD3.常用聚类算法现在，聚类算法根据数据类型的不同、聚类目的的差异以及实际问题的应用，大致可以分为五个大类：基于划分的聚类算法、基于层次的聚类算法、基于密度的聚类算法、基于网格的聚类算法、基于模型的聚类算法。然而，由于分类方法的角度存在多样性，我们并不能只用一种方法便把所有聚类算法完全区分开。下面介绍几种常见且具体的聚类算法。3.1系统聚类法在目前的实际应用当中，系统聚类法是较为常见的聚类分析算法，其基本思想是：利用确定的某种度量样品或变量间亲疏程度的工具，将关系密切的样品或变量首先聚成一个类，关系疏远的样品或变量后聚成类，按照这个原则把聚类一直进行下去，最终使得每个样品或变量都能够聚到适当的类中。根据系统聚类法的基本思想，我们可以知道系统聚类法相应的基本步骤：（1）将n个样品看成n个类，即每一个样品是一个类，此时样品间的距离与类间距离是等价的；（2）利用确定的距离计算公式，分别计算类与类之间的距离，并将距离最近的也就是关系最密切的两类聚成一个新类，其他的各自为一类，共有n-1类；（3）继续借助距离公式计算类间距离，按照最短距离原则进行并类，直到n个样品或变量聚成一类；（4）根据分类过程，把整个分类系统绘制成一张聚类谱系图。我们在使用系统聚类法时，不仅需要计算出各个样品或变量之间的距离，而且还要不断地计算类与类之间的距离，如此便会导致计算量过大。当样本容量很大时，这样占据的计算机容量相应变大，并且在聚类的过程中，需要将每类样品或变量和其他样品或变量的距离一一比较，再决定如何聚类，则会消耗更多的时间用来计算。在计算机内存和计算时间的约束下，系统聚类法在实际应用中存在着一定的缺陷。3.2K-均值聚类法K-均值聚类法是一种快速聚类法，由MacQueen于1967年提出。基于计算机算法中的迭代思想，给出K-均值法的基本思想：事先确定聚为k类，并给出k个初始点，然后将其他样品或变量逐个输入，继而改变凝聚点，不断地进行迭代，直到得到合理的分类为止。具体的步骤如下：（1）选择k个初始凝聚点和确定初始分类，设定迭代终止条件，比如最大迭代次数；（2）依据数据间亲疏关系的程度，把数据对象划分到距离最近的凝聚点，使之聚为一类；（3）经过聚类后，重新计算新的凝聚点，继续将各个数据对象进行归类；（4）循环执行第二个和第三个步骤，直到满足第一步中设定的终止条件。不论是系统聚类法还是K-均值聚类法，聚类的准则都是数据对象间的亲疏程度。但是，系统聚类对不同的类数得出不同的聚类结果，而由于事先确定聚类数目，导致K-均值聚类法聚类结果的唯一性。在实践经验的积累过程中，我们可以更加好地去确定聚类的数目。甚至有时候可以借助系统聚类法，为K-均值聚类法确定类数提供参考。与系统聚类法相比，K-均值聚类法对计算机的性能要求不太高，并且得到的最终结果较为简单易懂。然而，K-均值聚类法也存在两个明显的缺点：一是聚类前K值的确定，如果K值设定过小，可能会导致聚类结果中有效信息的遗失，而K值设定过大，则会使聚类结果复杂难懂；二是初始凝聚点的选取对K-均值聚类法影响较大，如果初始凝聚点的选择导致分类严重偏离全局最优分类，那么就会出现局部最优解的现象。当聚类数目K值越大时，缺点二也会越明显，只能通过多次聚类来削减影响，从而得到较好的聚类结果。3.3有序样品的聚类分析法 由于系统聚类法和K-均值聚类法中各个样品是相互独立的，那么，各样品分类时的地位是可互换的、等价的。但是，在某些实际问题中，样品分类必须按照一定的次序进行。比如，在地质勘探中，需要通过岩心了解地层结构，要求对地层的不同结构进行分类，则样品次序不能打乱；又比如，对动植物按年龄段进行分类，年龄的顺序是不能改变的，否则就没有实际意义。有序样品聚类法又称最优分割法，该聚类算法的思想与系统聚类法的基本思想恰好相反：先将所有样品看成一类，再划分为两类、三类等等，直到把所有样品分成n类，即一个样品属于一类。具体聚类步骤如下：定义类的直径(其中XDD定义分类的损失函数。L(3)求最优分类法的递推公式。LL(4)最优解的求法。例：为了了解90年代以来我国夏季奥运会获得金牌的变化情况，借助1992年-2016年的运动员金牌获得数量进行分析。数据如下：年份1992199620002004200820122016数量16162832483826解：(1)计算直径{Di表3.1直径DiJ12345620396724204138.69857043242241286787.34563.2227130.67507798.87597.34315.2264242.6772(2)计算最小分类损失函数{L[pk表3.2最小分类损失函数{kN2345630(3)48(3)0(4)5204(5)8(5)0(5)6226.67(4)58(5)8(6)0(6)7315.2(3)226.67(7)58(7)8(7)0(7)(3)分类个数k的确定图3.1k与L[p(n,k)]以表2最后一行的最小损失函数L[p(n,k)](4)求最优分类取K=4，查表3.2最后一行得Lpn,k=58(7)，说明最小损失函数值为58，最优分割点在第七个元素处，即D4=7。继续查表，取n=6,k=3得Lpn,k聚类结果表明，90年代以来，我国夏季奥运会金牌获得数量经历了四个时期。前期属于较为平稳的低潮期，2000~2004年处于获得金牌数量的上升期，2008~2012年进入获得金牌数的高峰期，而2016年开始步入金牌获得数的下降期。3.4DBSCAN算法DBSCAN算法是基于密度的聚类算法当中较为典型的一种算法，这种密度聚类算法常常通过样本点分布的密切程度来决定聚类的结果。观察某个类别中的样本点，我们会发现它们之间的关系极其密切，换言之，在该类别中任意一个样本点的附近必定有同一类的其他样本点存在。DBSCAN算法把密度相连的点的最大集合看作是类，利用该算法能够对密度过高的区域划分成类。基本思想就是：若一个区域中点的密度大于某个阈值，就将其放入邻近的类中。具体算法步骤如下：（1）任选一个未被访问的点开始，标记好距离在其eps（扫描半径）内的所有附近点；（2）如果附近点数大于或等于minPts（最小包含点数），则当前点与其附近点形成一类，并且出发点称为核心点；同样的方法处理类内其他未被访问的点，以扩充类的范围；（3）如果附近点数小于minPts,则该点被记为非核心点；（4）直到所有点都归为某个类当中或记为噪声点。DBSCAN算法既可以适用于凸数据集，也可以适用于非凸数据集。而K-均值法一般只适用于凸数据集。因此，相比之下，DBSCAN算法不仅可以发现任意形状的类，而且不需要提前知道类的数目。此外，该算法能够识别出噪声点。然而，针对数据集变化的密度和高维数据，DBSCAN算法存在一定的局限性。同样，在进行聚类时，如果类间距差值很大，或是输入参数（eps/minPts）不当，便容易使得聚类效果较差。例：运用DBSCAN算法，将以下二维数据进行聚类。其中，选取A点为初始访问点，eps=3,minPts=3。ABCDEFGHIJKX145983752410：为了更加直观的观察数据特征，我们在二维平面进行描点作图，将以上数据转换成平面上的点：图3.2样本数据散点图(1)根据题意，选取点A为初始访问点，扫描其附近点B、F、I，分别计算这三点与点A的距离，AB=，AI=,AF=。AI与AF均小于扫描半径(eps)3，故将点A、F、I先聚为第一类D1。同时(2)同理，选取B作为新的初始点，计算距离BF=，BI=，两者均小于3,故将B放入D1。此时，得到第一类D(3)继续选取点C作为新初始访问点，得到第二类D2(4)继续选取点D为新的初始点，判断点D为非核心点。(5)继续选取点E为新的初始访问点，得到第三类D3(6)继续处理点F~点K，至此所有点都处理完毕。最终将样本数据聚为三类：D1={A、B、F、I}、D2={C、H、J}、4.聚类有效性评价聚类分析过程中存在两大问题，一是给定的数据集分类最优化问题，二是针对数据集的聚类结果如何进行评价。上文提及的聚类算法能够解决第一个问题，第二个问题需要通过聚类的有效性评价来解决。由于聚类过程是一个无监督的学习过程，整个过程中没有示例或预设分类来表明数据集中某种期望关系的有效性，大多数的聚类分析方法都是依赖于猜测，具有极大的不确定性并且缺乏说服力。因此，寻求合理客观的聚类评价方法是聚类分析中至关重要又极其困难的问题。常用的聚类评价方法有三种；外部评价法、内部评价法和相对评价法。4.1外部评价法针对外部评价法，我们已知每个数据的分类情况和类的个数，通过利用数据外的信息来度量聚类结构与外部结构的匹配程度，不考虑分类结果是否符合某种期望，而是直接考虑实际类编号和预测的类编号的相符程度。下面简单介绍Jaccard系数和Rand指数。简单来说，我们将聚类结构和给定的类结构进行对比，Jaccard系数和Rand指数就是度量两者的相近程度的指标。设数据集的一个聚类结构为C={C1,⋯,Cn}，数据集已知的划分为D={D1,⋯,Dm},可通过比较C和D来评价聚类的质量。针对数据集中任一对点，设a为该对点既属于C中同一类，又属于D中同一类的数目；b为该对点属于C中同一类，但不属于D中同一类的数目；J=a/(a+b+c)R=(a+d)/(a+b+c+d)当划分完全一致时即n=m时，存在最大值。此外，Jaccard系数和Rand指数取值为[0,1]。4.2内部评价法相比外部评价法而言，内部评价法只利用数据集中的数据信息来评价聚类质量。下面介绍两种主要的内部评价指标：（1）CPCC准则就系统聚类算法而言，可以用Cophenetic矩阵表示生成的层次图，矩阵中的元素表示数据xi和xj首次在同一类中出现的邻近层，由此定义Cophenetic相关系数来度量P1CPCC=其中，dij和cij分别是矩阵P1和P2中的元素(i,j)；μ1和μ2分别是矩阵P1和P2的均值；M=N(N−1)/2；N为数据集中点的个数(2)轮廓系数（SIL）在实际分类未知的情况下，用轮廓系数(SilhouetteCoefficient)对聚类算法进行评价较为适宜。SIL指标如下：S=就单个样本而言，d表示与其距离最近其他类别样本的平均距离，l则表示与同类中其他样本之间的平均距离。轮廓系数取值范围是[−1,1],若不同类别间的距离越大且同类样本间距离越小，则轮廓系数越大，聚类效果就越好。4.3相对评价法外部和内部评价法均基于统计测试，其计算量比较大，当数据类型较大时，使用效率会有所下降。相对评价法是在确定聚类算法的基础上，采用预定义的评价标准，针对该算法不同的参数设置进行算法测试，最终选择最优的参数设置和聚类模式。（1）SD有效性指数已知数据集X的方差为σ，聚类后第i类的方差为σi，用c表示聚类的数目Scat用Dmax和Dmin分别表示聚类中心间的最大距离和最小距离，DDis(c)=(最终得到SD有效性指数SD其中，cmax是输入的最大聚类数目（2）DB指数（DBI）DBI=(1/k)其中，μi和μj均为各自类内的平均距离，d5实例分析为了检验不同聚类方法下聚类结果的优劣，本文将借助MATLAB软件进行一些实例分析。我们选用某年我国10个地区农民支出情况的抽样调查数据，每个地区调查了反映每个人平均生活消费支出情况的六个经济指标。下面将分别使用系统聚类法和K-均值聚类法对这些地区进行聚类分析，并进行聚类的有效性评价。数据信息如下：地区食品衣着燃料住房交通和通信娱乐教育文化北京190.3343.779.7360.5449.019.04天津135.236.410.4744.1636.493.94河北95.2122.839.322.4422.812.8山西104.7825.116.49.8918．173.25辽宁145.6832.8317.7927.2939.093.47上海221.1138.6412.53115.6550.825.89江苏144.9829.1211.6742.627.35.74浙江169.9232.7512.7247.1234.355福建144.9221．2616.9619.5221.756.73江西140.5421.517.6419.1915.974.945.1系统聚类法的有效性评价根据实例分析要求，在MATLAB软件的运行环境下，采用系统聚类的算法对指定样本进行聚类并在此基础上借助Cophenetic相关系数（CPCC准则）来评价该种聚类方法下聚类结果的优劣。5.1.1系统聚类的MATLAB程序设计在MATLAB中实现系统聚类算法主要依靠pdist、linkage、cluster等函数来实现，而利用cophenet函数进行聚类效果的评价：(1)Y=pdist(X,’metric’)pdist函数主要用来计算样品间的距离，而常见的距离指标有euclidean、canberra、mahalanobis等，但默认使用euclidean。(2)Z=linkage（Y,’method’）在系统聚类法下，度量类与类之间的距离主要通过linkage函数来实现，同样度量的方式也有许多种：single、complete、average等。(3)T=cluster(Z,’cutoff’)其中，用cluster函数对样品进行聚类，而cutoff表示聚类的临界值，即按照要求决定将样品聚为几类。因此，系统聚类的MATLAB程序设计如下：表5.1系统聚类的MATLAB程序设计代码注释X=xlsread运用xls函数从Excel中导入数据X=zscore(X)对数据进行标准化Y=pdist(X,’euclidean’)运用欧氏距离度量样品间的距离，生成相似矩阵Z=linkage(Y,’single’)运用最短距离法计算类间距离，创建系统聚类表dendrogram(Z)输出聚类的谱系图T=cluster(Z,2)将目标样品聚为2类C=cophenet(Z,Y)运用cophenet函数评价聚类的效果5.1.2基于MATLAB的系统聚类分析结果(1)相似矩阵表5.2样品间的距离北京天津河北山西辽宁上海江苏浙江福建江西北京03.42905.54785.49184.28122.77443.43103.01674.63935.2792天津3.429002.52622.73192.07153.68071.58391.33553.30803.2918河北5.54782.526201.03983.19415.77352.41123.05183.18102.7888山西5.49182.73191.039803.75236.01272.59273.27843.53173.2454辽宁4.28122.07153.19413.752304.16962.31241.83612.69852.5126上海2.77443.68075.77356.01274.169603.87803.07755.10625.4225江苏3.43101.58392.41122.59272.31243.878001.11371.98582.2286浙江3.01671.33553.05183.27841.83613.07751.113702.55572.7160福建4.63933.30803.18103.53172.69855.10621.98582.555701.0799江西5.27923.29182.78883.24542.51265.42252.22862.71601.07990观察各样品间的距离，我们发现北京与上海的距离相对更小，那么两者间的差异越小，可以聚为一类。此外，它们与其他样品间的距离较大，则关系疏远。(2)聚类表和谱系图表5.3聚类表类别距离类别距离341.039812151.98589101.079911162.4112781.1137162.77442131.335517183.01675141.8361———图5.1谱系图按照系统聚类的思想，首先将每一个样品看成一类，再将距离近的类聚为一个新类。由于第3类与第4类的距离最近，则第一个聚成新类，即第11类。以此类推，直至所有类聚完。由聚类表和谱系图可知，将样品分为两类较好。(3)聚类结果表5.4cluster函数的聚类结果类别第一类第二类样品序号2、3、4、5、7、8、9、101、6根据以上信息，可以看出运用系统聚类算法将样品分为两类比较适合，其中北京和上海为一类，其他地区为另一类。这个聚类结果显示我国农民平均生活消费支出有地区性的差异，北京和上海地区消费水平要更高。(4)聚类结果的评价CPCC=0.8360由于Cophenetic相关系数为0.8360，接近于1，则说明该数据样本在系统聚类法下的聚类效果较好。5.2K-均值聚类法的有效性评价前面已经介绍了系统聚类法在MATLAB中的实现，现在采用K-均值聚类的算法在MATLAB中进行聚类，并利用轮廓系数（SIL指标）来评价该种聚类方法下聚类结果的有效性。5.2.1K-均值聚类的MATLAB程序设计在MATLAB中实现K-均值聚类算法主要利用kmeans函数来实现，并利用silhouette函数对聚类效果进行评价：[Idx,C,sumD,D]=kmeans(X,k,’dist’,’metric’,’rep’,n)Kmeans函数是指对样品进行K-均值聚类。此外，k表示聚类的数目，metric则表示选取的距离测度,n为重复聚类的次数。由此，K-均值聚类的MATLAB程序设计如下：表5.5K-均值聚类的MATLAB程序设计代码注释X=xlsread运用xls函数从Excel中导入数据X=zscore(X)对数据进行标准化[Idx,C,sumD,D]=kmeans(X,2，’dist’,’sqEuclidean’,’rep’,4)运用平方欧氏距离作为距离测度，将目标样品聚成2类，且聚类重复次数为4[S,H]=silhouette(X,Idx)运用silhouette函数评价聚类的效果5.2.2基于MATLAB的K-均值聚类分析结果(1)聚类结果表5.6kmeans函数聚类的结果类别第一类第二类样品序号2、3、4、5、7、8、9、101、6在K-均值聚类法下，同样将样品聚为两类，一类是北京和上海，另一类是其他地区，这与系统聚类的结果相同。(2)样品与质心的距离表5.7样品与质心的距离地区与第一类质心的距离与第二类质心的距离北京17.18301.9244天津2.547710.7282河北3.357830.1314山西4.909231.2318辽宁3.382615.9327上海19.57251.9244江苏0.839511.4810浙江2.06737.3611福建3.578921.8739江西3.142926.7124以北京市为例，其与第一类的质心距离为17.1830，与第二类质心的距离为1.9277，故将其划为第二类较为适宜。由此，我们可知将北京和上海聚类第二类，其他地区聚类第一类。(3)轮廓系数与轮廓图表5.8轮廓系数表地区轮廓系数（SIL）地区轮廓系数（SIL）北京0.6182上海0.6587天津0.5009江苏0.6745河北0.7741浙江0.3790山西0.7281福建0.6851辽宁0.5929江西0.7557图5.2轮廓图同时，我们可以利用轮廓系数来判断分类是否合理，轮廓系数越接近1则聚类的有效性越高，故在K-均值聚类法下，聚类结果亦较为优质。综上所述，针对本文选取的样本，采用系统聚类算法和K-均值聚类算法得出的聚类结果是一致的，且利用CPCC准则和SIL指标分别对其聚类结果进行有效性评价，均表明聚类效果良好。6.总结随着大数据领域的蓬勃发展，聚类分析的研究深受学者们的喜爱，从而使得聚类分析的理论和应用迅速发展。本文作为一篇综述性的文章，以聚类问题基本思想和主要步骤作为切入点，详细地阐述了聚类分析过程中各部分的理论内容，为读者了解聚类分析提供系统的知识板块。此外，本文通过实例分析，有力的证明了聚类分析在实际生活中的应用性，进一步体现了本文的研究价值。聚类分析的过程中存在聚类算法和聚类的有效性评价两个重点问题，针对不同的数据特征和聚类目标，可以选择不同的聚类算法。然而，即是是使用同一种聚类算法，在评价聚类结果的优劣的过程中，我们可以使用多种聚类的评价指标