聚类算法

聚类算法什么是聚类聚类就是按照某个特定标准(如距离准则)把一个数据集分割成不同的类或簇，使得同一个簇内的数据对象的相似性尽可能大，同时不在同一个簇中的数据对象的差异性也尽可能地大。即聚类后同一类的数据尽可能聚集到一起，不同数据尽量分离。简单地说，聚类就是把相似的东西分到一组。聚类和分类的区别同分类不同，对于一个分类器，通常需要你告诉它“这个东西被分为某某类”这样一些例子，理想情况下，一个分类器会从它得到的训练集中进行“学习”，从而具备对未知数据进行分类的能力，这种提供训练数据的过程通常叫做监督学习。而在聚类的时候，我们并不关心某一类是什么，我们需要实现的目标只是把相似的东西聚到一起，一个聚类算法通常只需要知道如何计算相似度就可以开始工作了，因此，聚类通常并不需要使用训练数据进行学习，这在机器学习中被称作无监督学习。聚类的现状及应用聚类技术正在蓬勃发展，对此有贡献的研究领域包括数据挖掘、统计学、机器学习、空间数据库技术、生物学以及市场营销等。各种聚类方法也被不断提出和改进，而不同的方法适合于不同类型的数据，因此对各种聚类方法、聚类效果的比较成为值得研究的课题。聚类分析是一种重要的人类行为，早在孩提时代，一个人就通过不断改进下意识中的聚类模式来学会如何区分猫狗、动物植物。目前在许多领域都得到了广泛的研究和成功的应用，如用于模式识别、数据分析、图像处理、市场研究、客户分割、Web文档分类等。聚类算法选择与分类目前，有大量的聚类算法。而对于具体应用，聚类算法的选择取决于数据的类型、聚类的目的。如果聚类分析被用作描述或探查的工具，可以对同样的数据尝试多种算法，以发现数据可能揭示的结果。主要的聚类算法可以划分为如下几类：划分方法、层次方法、基于密度的方法、基于网格的方法以及基于模型的方法。几种聚类算法介绍划分聚类算法（K-means聚类算法）层次聚类算法（AGNES、DIANA）密度聚类算法（DBSCAN）K-means聚类算法k-means是划分方法中较经典的聚类算法之一。由于该算法的效率高，所以在对大规模数据进行聚类时被广泛应用。目前，许多算法均围绕着该算法进行扩展和改进。k-means算法以k为参数，把n个对象分成k个簇，使簇内具有较高的相似度，而簇间的相似度较低。假设我们提取到原始数据的集合为D(x1,x2,…,xn)，并且每个xi为d维的向量，K-means聚类的目的就是，在给定分类组数k（k≤n）值的条件下，将原始数据分成k类，S={S1,S2,…,Sk}，在数值模型上，即对以下表达式求最小值：这里μi表示分类Si的平均值。k-means聚类算法计算机实现步骤1、从D中随机取k个元素，作为k个簇的各自的中心。2、分别计算剩下的元素到k个簇中心的相异度，将这些元素分别划归到相异度最低的簇。3、根据聚类结果，重新计算k个簇各自的中心，计算方法是取簇中所有元素各自维度的算术平均数。4、将D中全部元素按照新的中心重新聚类。5、重复第4步，直到聚类结果不再变化。6、将结果输出。k-means聚类算法示例对于一个数据集合D，假设K=3，首先3个中心点被随机初始化，所有的数据点都还没有进行聚类，默认全部都标记为红色，如下图所示：k-means聚类算法示例然后进入第一次迭代：按照初始的中心点位置为每个数据点着上颜色，重新计算3个中心点，结果如下图所示：k-means聚类算法示例可以看到，由于初始的中心点是随机选的，这样得出来的结果并不是很好，接下来是下一次迭代的结果：k-means聚类算法示例可以看到大致形状已经出来了。再经过两次迭代之后，基本上就收敛了，最终结果如下：k-means聚类算法示例但k-means并不是万能的，虽然许多时候都能收敛到一个比较好的结果，但是也有运气不好的时候会收敛到一个让人不满意的局部最优解，例如选用下面这几个初始中心点：k-means聚类算法示例最终会收敛到这样的结果：k-means聚类算法优缺点优点：1.算法快速、简单。2.对大数据集有较高的效率并且是可伸缩性的。3.时间复杂度近于线性，而且适合挖掘大规模数据集。缺点：1.K-means算法中K是事先给定的，这个K值的选定是非常难以估计，很多时候，事先并不知道数据集应该分成多少个类别才最合适。2.K-means算法中，需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果。3.不适合于发现非凸面形状的簇或者大小差别很大的簇。而且，它对于“躁声”和孤立点数据是敏感的。层次聚类当采用划分聚类方法（如k-means）K值选取十分困难时，我们不妨考虑可以考虑层次聚类。层次聚类是另一种主要的聚类方法，它具有一些十分必要的特性使得它成为广泛应用的聚类方法。它生成一系列嵌套的聚类树来完成聚类。单点聚类处在树的最底层，在树的顶层有一个根节点聚类。根节点聚类覆盖了全部的所有数据点。可根据其聚类方式划分为：凝聚（自下而上）聚类和分裂（自上而下）聚类。层次凝聚的代表是AGNES算法。层次分裂的代表是DIANA算法。AGNES算法AGNES(AGglomerativeNESting)算法最初将每个对象作为一个簇，然后这些簇根据某些准则被一步步地合并。两个簇间的相似度由这两个不同簇中距离最近的数据点对的相似度来确定。聚类的合并过程反复进行直到所有的对象最终满足簇数目。AGNES（自底向上凝聚算法）计算机编程实现：输入：包含n个对象的数据库，终止条件簇的数目k。输出：k个簇，达到终止条件规定簇数目。(1)将每个对象当成一个初始簇；(2)REPEAT(3)根据两个簇中最近的数据点找到最近的两个簇；(4)合并两个簇，生成新的簇的集合；(5)UNTIL达到定义的簇的数目；判断两个类之间相似度的方法1.SingleLinkage：又叫做nearest-neighbor，就是取两个类中距离最近的两个样本的距离作为这两个集合的距离，也就是说，最近两个样本之间的距离越小，这两个类之间的相似度就越大。容易造成一种叫做Chaining的效果，两个cluster明明从“大局”上离得比较远，但是由于其中个别的点距离比较近就被合并了，并且这样合并之后Chaining效应会进一步扩大，最后会得到比较松散的cluster。2.CompleteLinkage：这个则完全是SingleLinkage的反面极端，取两个集合中距离最远的两个点的距离作为两个集合的距离。其效果也是刚好相反的，限制非常大，两个cluster即使已经很接近了，但是只要有不配合的点存在，就顽固到底，老死不相合并，也是不太好的办法。这两种相似度的定义方法的共同问题就是指考虑了某个有特点的数据，而没有考虑类内数据的整体特点3.Average-linkage：这种方法就是把两个集合中的点两两的距离全部放在一起求一个平均值，相对也能得到合适一点的结果。average-linkage的一个变种就是取两两距离的中值，与取均值相比更加能够解除个别偏离样本对结果的干扰。层次聚类AGNES算法示例第1步：根据初始簇计算每个簇之间的距离，随机找出距离最小的两个簇，进行合并，最小距离为1，合并后1，2点合并为一个簇。第2步：，对上一次合并后的簇计算簇间距离，找出距离最近的两个簇进行合并，合并后3，4点成为一簇。第3步：重复第2步的工作，5，6点成为一簇。第4步：重复第2步的工作，7，8点成为一簇。第5步：合并{1，2}，{3，4}成为一个包含四个点的簇。第6步：合并{5，6}，{7，8}，由于合并后的簇的数目已经达到了用户输入的终止条件程序结束。步骤最近的簇距离最近的两个簇合并后的新簇11{1}，{2}{1，2}，{3}，{4}，{5}，{6}，{7}，{8}21{3}，{4}{1，2}，{3，4}，{5}，{6}，{7}，{8}31{5}，{6}{1，2}，{3，4}，{5，6}，{7}，{8}41{7}，{8}{1，2}，{3，4}，{5，6}，{7，8}51{1，2}，{3，4}{1，2，3，4}，{5，6}，{7，8}61{5，6}，{7，8}{1，2，3，4}，{5，6，7，8}结束序号属性1属性2111212321422534635744845层次聚类算法优缺点及改进算法•优点：适用于任意形状和任意属性的数据集，灵活控制不同层次的聚类粒度，强聚类能力。•缺点：大大延长了算法的执行时间，不能回溯处理。层次聚类方法尽管简单，但经常会遇到合并或分裂点的选择的困难。改进层次方法的聚类质量的一个有希望的方向是将层次聚类和其他聚类技术进行集成，形成多阶段聚类。下面介绍两个改进的层次聚类方法BIRTH和CURE。BIRCH聚类算法BIRCH（利用层次方法的平衡迭代归约和聚类）是一个综合的层次聚类方法，它用聚类特征和聚类特征树（CF）来概括聚类描述。该算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。CF树是一个具有两个参数分支因子B和阂值T的高度平衡树，存储了层次聚类的聚类特征。分支因子定义了每个非叶节点孩子的最大数目，而阈值给出了存储在树的叶子节点中的子聚类的最大直径。BIRCH聚类算法BIRCH算法的工作过程包括两个阶段：–阶段一：BIRCH扫描数据库，建立一个初始存放于内存的CF树，它可以被看作数据的多层压缩，试图保留数据内在的聚类结构。随着对象的插入，CF树被动态地构造，不要求所有的数据读入内存，而可在外存上逐个读入数据项。因此，BIRTH方法对增量或动态聚类也非常有效。–阶段二：BIRCH采用某个聚类算法对CF树的叶结点进行聚类。在这个阶段可以执行任何聚类算法，例如典型的划分方法。BIRCH算法试图利用可用的资源来生成最好的聚类结果。通过一次扫描就可以进行较好的聚类，故该算法的计算复杂度是O(n)，n是对象的数目。CURE聚类算法很多聚类算法只擅长处理球形或相似大小的聚类，另外有些聚类算法对孤立点比较敏感。CURE算法解决了上述两方面的问题，选择基于质心和基于代表对象方法之间的中间策略，即选择空间中固定数目的具有代表性的点，而不是用单个中心或对象来代表一个簇。该算法首先把每个数据点看成一簇，然后再以一个特定的收缩因子向簇中心“收缩”它们，即合并两个距离最近的代表点的簇。CURE聚类算法•CURE算法采用随机取样和划分两种方法的组合，具体步骤如下：–从源数据集中抽取一个随机样本。–为了加速聚类，把样本划分成p份，每份大小相等。–对每个划分局部地聚类。–根据局部聚类结果，对随机取样进行孤立点剔除。主要有两种措施：如果一个簇增长得太慢，就去掉它。在聚类结束的时候，非常小的类被剔除。–对上一步中产生的局部的簇进一步聚类。落在每个新形成的簇中的代表点根据用户定义的一个收缩因子收缩或向簇中心移动。这些点代表和捕捉到了簇的形状。–用相应的簇标签来标记数据。•由于它回避了用所有点或单个质心来表示一个簇的传统方法，将一个簇用多个代表点来表示，使CURE可以适应非球形的几何形状。另外，收缩因子降底了噪音对聚类的影响，从而使CURE对孤立点的处理更加健壮，而且能识别非球形和大小变化比较大的簇。CURE的复杂度是O(n)，n是对象的数目，所以该算法适合大型数据的聚类。密度聚类算法•密度聚类方法的指导思想是，只要一个区域中的点的密度大于某个域值，就把它加到与之相近的聚类中去。这类算法能克服基于距离的算法只能发现“类圆形”的聚类的缺点，可发现任意形状的聚类，且对噪声数据不敏感。但计算密度单元的计算复杂度大，需要建立空间索引来降低计算量，且对数据维数的伸缩性较差。这类方法需要扫描整个数据库，每个数据对象都可能引起一次查询，因此当数据量大时会造成频繁的I/O操作。代表算法有：DBSCAN、OPTICS、DENCLUE算法等。•DBSCAN（Density-BasedSpatialClusteringofApplicationswithNoise）一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有