“1+X”(中级)08-聚类分析

聚类分析课程目录8.1.聚类分析概述

8.1.1.聚类分析的定义

8.1.2.聚类分析提出的背景

8.1.3.聚类分析的原理8.1.4.聚类分析的应用场景

8.1.5.聚类算法的分类8.2.基于划分的聚类8.3.基于层次的聚类8.4.基于密度的聚类8.5.基于网格的聚类8.6.k-均值聚类分析实验8.7.本章小结8.8.本章习题聚类分析的定义聚类分析是一组将研究对象分为相对同质的群组的统计分析技术。聚类分析对具有共同趋势或结构的数据进行分组，将数据项分组成多个簇（类），簇之间的数据差别尽可能大，簇内的数据差别尽可能小，即“最小化”簇内的相似性，最大化簇间的相似性。它主要解决的是把一群对象划分成若干个组的问题。划分的依据是聚类问题的核心。所谓“物以类聚，人以群分”，故得名聚类。聚类分析的定义课程目录8.1.聚类分析概述

8.1.1.聚类分析的定义

8.1.2.聚类分析提出的背景

8.1.3.聚类分析的原理8.1.4.聚类分析的应用场景

8.1.5.聚类算法的分类8.2.基于划分的聚类8.3.基于层次的聚类8.4.基于密度的聚类8.5.基于网格的聚类8.6.k-均值聚类分析实验8.7.本章小结8.8.本章习题聚类分析提出的背景聚类是在预先不知道分类的情况下，根据信息相似度原则进行信息聚类的一种方法。聚类的目的是将大量的数据通过“属于同类别的对象之间的差别尽可能的小，而不同类别上的对象的差别尽可能的大”的原则进行分类。因此，聚类的意义就在于将观察到的内容组织成类分层结构，把类似的事物组织在一起。通过聚类分析，人们能够识别密集的和稀疏的区域因而发现全局的分布模式以及数据属性之间的有趣的关系。聚类分析的过程示意课程目录8.1.聚类分析概述

8.1.1.聚类分析的定义

8.1.2.聚类分析提出的背景

8.1.3.聚类分析的原理8.1.4.聚类分析的应用场景

8.1.5.聚类算法的分类8.2.基于划分的聚类8.3.基于层次的聚类8.4.基于密度的聚类8.5.基于网格的聚类8.6.k-均值聚类分析实验8.7.本章小结8.8.本章习题聚类分析的原理聚类分析是将样品或变量按照它们在性质上的亲疏程度进行分类的数据分析方法。它是典型的无监督分析方法，也就是没有关于样品或变量的分类标签，分类需要依据样品或者变量的亲疏程度进行。聚类分析的原理描述样品或变量亲疏程度的两个途径个体间差异度个体间相似度把每个样品或变量看成是多维空间上的一个点，在多维坐标中，定义点与点、类和类之间的距离，用点与点间距离来描述样品或变量之间的亲疏程度。计算样品或变量的简单相关系数或者等级相关系数，用相似系数来描述样品或变量之间的亲疏程度。课程目录8.1.聚类分析概述

8.1.1.聚类分析的定义

8.1.2.聚类分析提出的背景

8.1.3.聚类分析的原理8.1.4.聚类分析的应用场景

8.1.5.聚类算法的分类8.2.基于划分的聚类8.3.基于层次的聚类8.4.基于密度的聚类8.5.基于网格的聚类8.6.k-均值聚类分析实验8.7.本章小结8.8.本章习题聚类分析的应用场景商业方面用来将用户根据其性质分类，从而发现不同的客户群，并且通过购买模式刻画不同的客户群特征。计算生物学领域用来对动植物和对基因进行分类，从而获得更加准确的生物分类。保险领域根据住宅类型、价值、地理位置来鉴定一个城市的房产分组。电子商务发现具有相似浏览行为的客户，并分析客户的共同特征，可以更好地帮助电子商务的用户了解自己的客户，向客户提供更合适的服务。聚类分析在不同领域有着广泛应用。课程目录8.1.聚类分析概述

8.1.1.聚类分析的定义

8.1.2.聚类分析提出的背景

8.1.3.聚类分析的原理8.1.4.聚类分析的应用场景

8.1.5.聚类算法的分类8.2.基于划分的聚类8.3.基于层次的聚类8.4.基于密度的聚类8.5.基于网格的聚类8.6.k-均值聚类分析实验8.7.本章小结8.8.本章习题聚类算法的分类基于划分的聚类基于层次的聚类基于密度的聚类基于网格的聚类基于模型的聚类对给定的数据集合，事先指定划分为k个类别。典型算法：k-均值法和k-中心点算法等。对给定的数据集合进行层次分解，不需要预先给定聚类数，但要给定终止条件，包括凝聚法和分裂法。典型算法：CURE、Chameleon、BIRCH、Agglomerative。只要某簇邻近区域的密度超过设定的阈值，则扩大簇的范围，继续聚类。这类算法可以获得任意形状的簇。典型算法：DBSCAN、OPTICS和DENCLUE等。首先将问题空间量化为有限数目的单元，形成一个空间网格结构，随后聚类在这些网格之间进行。典型算法：STING、WareCluster和CLIQUE等。为每个簇假定一个模型，寻找数据对模型的最佳拟合。基于的假设是：数据是根据潜在的概率分布生成的。典型算法：COBWEB和神经网络算法等。课程目录8.1.聚类分析概述8.2.基于划分的聚类

8.2.1.k-均值算法

8.2.2.k-medoids算法8.2.3.k-prototype算法8.3.基于层次的聚类8.4.基于密度的聚类8.5.基于网格的聚类8.6.k-均值聚类分析实验8.7.本章小结8.8.本章习题k-均值算法概述K均值聚类（Kmeans）算法是无监督聚类算法中的代表，该算法的主要作用是将相似的样本自动归到一个类别中。所谓的无监督算法，就是输入样本没有对应的输出或标签。K均值聚类算法十分简单易懂而且非常有效，但是合理的确定K值和K个初始类簇中心点对于聚类效果的好坏有很大的影响。k-均值算法适用场景K-means算法是集简单和经典于一身的基于距离的聚类算法采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为类簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。k-均值算法原理及步骤第一步第二步第三步第四步设定K值，即确定聚类数；确定各类中心；计算每个记录到类中心的距离，并将该记录归到最近的类中；然后重新计算K类的中心点，更新原类族的中心；重复第二、三步，迭代到收敛标准停止。指定聚类数目K确定K个数据中心，每个点分到距离最近的类中，重新计算K个类的中心，然后要么结束，要么重算所有点到新中心的距离聚类。其结束准则包括迭代次数超过指定或者新的中心点距离上一次中心点的偏移量小于指定值。k-均值算法原理及步骤第一步设定K值，即确定聚类数；确定各类中心；第一步，确定聚类个数、确定聚类中心、确定距离计算公式:观察法枚举法其他技术手段指定聚类数目K确定K个数据中心，每个点分到距离最近的类中，重新计算K个类的中心，然后要么结束，要么重算所有点到新中心的距离聚类。其结束准则包括迭代次数超过指定或者新的中心点距离上一次中心点的偏移量小于指定值。k-均值算法原理及步骤第一步设定K值，即确定聚类数；确定各类中心；第一步，确定聚类个数、确定聚类中心、确定距离计算公式:观察法枚举法其他技术手段指定聚类数目K确定K个数据中心，每个点分到距离最近的类中，重新计算K个类的中心，然后要么结束，要么重算所有点到新中心的距离聚类。其结束准则包括迭代次数超过指定或者新的中心点距离上一次中心点的偏移量小于指定值。k-均值算法原理及步骤第二步计算每个记录到类中心的距离，并将该记录归到最近的类中；第二步，计算每个点到中心的距离,归类指定聚类数目K确定K个数据中心，每个点分到距离最近的类中，重新计算K个类的中心，然后要么结束，要么重算所有点到新中心的距离聚类。其结束准则包括迭代次数超过指定或者新的中心点距离上一次中心点的偏移量小于指定值。k-均值算法原理及步骤第三步然后重新计算K类的中心点，更新原类族的中心；第三步，计算每个点到中心的距离,归类指定聚类数目K确定K个数据中心，每个点分到距离最近的类中，重新计算K个类的中心，然后要么结束，要么重算所有点到新中心的距离聚类。其结束准则包括迭代次数超过指定或者新的中心点距离上一次中心点的偏移量小于指定值。第四步重复第二、三步，迭代到收敛标准停止。重复第二步，将各样本点重新归类划分；重复第三步，根据新分类重新计算类中心；直到聚类中心不发生变化（达到收敛标准）或循环次数到达设置数值，迭代停止k-均值算法原理及步骤指定聚类数目K确定K个数据中心，每个点分到距离最近的类中，重新计算K个类的中心，然后要么结束，要么重算所有点到新中心的距离聚类。其结束准则包括迭代次数超过指定或者新的中心点距离上一次中心点的偏移量小于指定值。k-均值算法伪代码创建k个点作为初始的质心点（随机选择）当任意一个点的簇分配结果发生改变时

对数据集中的每一个数据点

对每一个质心

计算质心与数据点的距离

将数据点分配到距离最近的簇

对每一个簇，计算簇中所有点的均值，并将均值作为质心k-均值算法伪代码k-均值算法python实现python实现的k-均值算法核心代码机器学习PAI中对应的组件机器学习PAI中对应的组件为K均值聚类组件k-均值算法的特点小结指定聚类数目K确定K个数据中心，每个点分到距离最近的类中，重新计算K个类的中心，然后要么结束，要么重算所有点到新中心的距离聚类。其结束准则包括迭代次数超过指定或者新的中心点距离上一次中心点的偏移量小于指定值。原理简单、容易理解、容易实现聚类结果容易解释聚类结果相对较好k值选择不同，聚类结果相差较大初始聚类中心不同，聚类结果可能不同只能发现球状簇，非球状聚类效果差对于离群点和孤立点敏感样本点较多，计算量偏大优点缺点课程目录8.1.聚类分析概述8.2.基于划分的聚类

8.2.1.k-均值算法

8.2.2.k-medoids算法

8.2.3.k-prototype算法8.3.基于层次的聚类8.4.基于密度的聚类8.5.基于网格的聚类8.6.k-均值聚类分析实验8.7.本章小结8.8.本章习题k-medoids算法概述medoids算法是对k-means算法的一种改进算法。由于对k-means算法对于异常值十分敏感，因此具有极大值的对象可能会产生严重扭曲的数据分布。所以我们可以使用k-medoids算法，它是集群中位于最中心的对象，而不是将集群中的平均值作为参考点。因此，分区的方法仍然可以基于最小化每个对象与其参考点之间的不相似程度之和的原理来进行。这构成了k-medoids方法的基础。k-medoids算法与k-均值算法的差异及比较k-均值算法（即k-means）与k-medoids之间的差异就是可以理解为对于数据样本的平均值和中位数之间的差异。原因：k-均值算法对于数据样本的要求太高，要求所有数据样本处在一个欧式空间中，对于有很多噪声的数据就会造成极大的误差。但对于非数值型数据样本，不能够计算平均值等实数型变量。取值范围可以是连续空间中的任意值取值只能是数据样本范围中的样本k-均值算法k-medoids算法PKk-medoids算法原理及步骤不采用簇中对象的平均值作为参照点，可以选用簇中位置最中心的对象，即medoid。这样划分方法仍然是基于最小化所有对象与其参照点之间的相异度之和的原则来执行的。随机选择K个对象作为初始的代表对象；指派每个剩余的对象给离它最近的代表对象所代表的簇；随意地选择一个非代表对象；计算用代替的总代价ＳStep1Step2Step3Step4如果，则用替换，形成新的k个代表对象的集合。直到不发生变化。Step5迭代循环课程目录8.1.聚类分析概述8.2.基于划分的聚类

8.2.1.k-均值算法

8.2.2.k-medoids算法8.2.3.k-prototype算法8.3.基于层次的聚类8.4.基于密度的聚类8.5.基于网格的聚类8.6.k-均值聚类分析实验8.7.本章小结8.8.本章习题k-prototype算法概述K-prototype是处理混合属性聚类的典型算法，它继承了Kmean算法和Kmode算法的思想，并且加入了描述数据簇的原型和混合属性数据之间的相异度计算公式。K-prototype算法是设定了一个目标函数，类似于kmean的SSE（误差平方和），不断迭代，直到目标函数值不变。K-prototype算法提出了混合属性簇的原型，我们可以理解原型就是数值属性聚类的质心。混合属性中存在数值属性和分类属性，其原型的定义是数值属性原型用属性中所有属性取值值的均值，分类属性原型是分类属性中选取属性值取值频率最高的属性。合起来就是原型。k-prototype算法步骤K-prototype的算法步骤是：从数据集中随机选取k个对象作为初始的k个簇的原型；遍历数据集中的每一个数据，计算数据与k个簇的相异度。然后将该数据分配到相异度最小的对应的簇中，每次分配完毕后，更新簇的原型；然后计算目标函数，然后对比目标函数值是否改变，循环直到目标函数值不在变化为止。课程目录8.1.聚类分析概述8.2.基于划分的聚类8.3.基于层次的聚类8.3.1.BIRCH聚类

8.3.2.CURE算法8.4.基于密度的聚类8.5.基于网格的聚类8.6.k-均值聚类分析实验8.7.本章小结8.8.本章习题BIRCH算法基本概念BIRCH的全称是：利用层次方法的平衡迭代规约和聚类（BalancedIterativeReducingandClusteringUsingHierarchies）BIRCH算法比较适合于数据量大，类别数K也比较多的情况。它运行速度很快，只需要单遍扫描数据集就能进行聚类BIRCH算法利用了一个树结构来帮助我们快速的聚类，这个数结构类似于平衡B+树，一般将它称之为聚类特征树(ClusteringFeatureTree，简称CFTree)。CFCFCF12B…RootNodeCFCFCF12B…Non-leafNodeLeafNodeCF1CF2…CFLLeafNodeCF1CF2…CFLLeafNodeCF1CF2…CFLBIRCH算法原理在聚类特征树中，一个聚类特征CF是这样定义的：每一个CF是一个三元组，可以用（N，LS，SS）表示。其中N代表了这个CF中拥有的样本点的数量；LS代表了这个CF中拥有的样本点各特征维度的和向量，SS代表了这个CF中拥有的样本点各特征维度的平方和。1.从根节点向下寻找和新样本距离最近的叶子节点和叶子节点里最近的CF节点；2.如果新样本加入后，这个CF节点对应的超球体半径仍然满足小于阈值T，则更新路径上所有的CF三元组，插入结束。否则转入3；3.如果当前叶子节点的CF节点个数小于阈值L，则创建一个新的CF节点，放入新样本，将新的CF节点放入这个叶子节点，更新路径上所有的CF三元组，插入结束。否则转入4；4.将当前叶子节点划分为两个新叶子节点，选择旧叶子节点中所有CF元组里超球体距离最远的两个CF元组，作为两个新叶子节点的第一个CF节点。将其他元组和新样本元组按照距离远近原则放入对应的叶子节点。依次向上检查父节点是否也要分裂，如果需要按和叶子节点分裂方式相同。聚类特征树CFTree的插入流程BIRCH算法流程及步骤BIRCH算法的主要过程就是建立CFTree的过程。除了建立CFTree来聚类，还有一些可选的算法步骤。整个BIRCH算法流程如下：第１步第２步（可选）第３步（可选）第４步（可选）将所有的样本依次读入，在内存中建立一颗CFTree将第一步建立的CFTree进行筛选，去除一些异常CF节点，这些节点一般里面的样本点很少。对于一些超球体距离非常近的元组进行合并。利用其它的一些聚类算法比如K-Means对所有的CF元组进行聚类，得到一颗比较好的CFTree。利用第3步生成的CFTree的所有CF节点的质心，作为初始质心点，对所有的样本点按距离远近进行聚类。BIRCH算法的关键就是步骤1，也就是CFTree的生成，其他步骤都是为了优化最后的聚类结果。BIRCH算法python实现Python实现算法示例：BIRCH聚类算法特点小结123123主要优点主要缺点节约内存，所有的样本都在磁盘上，CFTree仅仅存了CF节点和对应的指针。聚类速度快，只需要一遍扫描训练集就可以建立CFTree，CFTree的增删改都很快。可以识别噪音点，还可以对数据集进行初步分类的预处理由于CFTree对每个节点的CF个数有限制，导致聚类的结果可能和真实的类别分布不同。对高维特征的数据聚类效果不好。此时可以选择MiniBatchK-Means如果数据集的分布簇不是类似于超球体，或者说不是凸的，则聚类效果不好。课程目录8.1.聚类分析概述8.2.基于划分的聚类8.3.基于层次的聚类8.3.1.BIRCH聚类

8.3.2.CURE算法8.4.基于密度的聚类8.5.基于网格的聚类8.6.k-均值聚类分析实验8.7.本章小结8.8.本章习题CURE算法概述CURE对孤立点的处理更加健壮，而且能够识别非球形和大小变化比较大的类。针对大型数据库，CURE采用随机取样和划分两种方法组合：一个随机样本首先被划分，每个划分被部分聚类。绝大多数聚类算法或者擅长处理球形和相似大小的聚类，或者在存在孤立点时变得比较脆弱。CURE采用了一种新颖的层次聚类算法，该算法选择基于质心和基于代表对象方法之间的中间策略。它不同于单个质心或对象来代表一个类，而是选择数据空间中固定数目的具有代表性的点。CURE算法原理及步骤123456从源数据对象中抽取一个随机样本S。将样本S分割为一组划分。对每个划分局部的聚类。通过随机取样剔除孤立点。如果一个类增长太慢，就去掉它。对局部的类进行聚类。落在每个新形成的类中的代表点根据用户定义的一个收缩因子收缩或向类中心移动。这些点代表和捕捉到了类的形状。用相应的类标签来标记数据。CURE算法伪代码Procedurecluster(S,k)Begin1.T:=build_kd_tree(S)2.Q:=build_heap(S)3:whilesize(Q)>kdo{u:=extract_min(Q)v:=u.closet()Delete(Q,v)w:=merge(u,v)delete_rep(T,u);delete_rep(T,v);insert_rep(T,w)w.closet:=xforeachx∈Qdo{ifdist(w,x)<dist(w,w.closet)w.closet:=x

ifx.closetiseitheruorv{ifdist(x,x.closet)<dist(x,w)

x.closet:=closet_cluster(T,x,dist(x,w))16.else17.x.closet:=w;18.

relocate(Q,x)19.}20.elseifdist(x,x.close)>dist(x,w){21.x.closet:=w;22.relocate(Q,x)23.}24.}25.Insert(Q,w)26.}end课程目录8.1.聚类分析概述8.2.基于划分的聚类8.3.基于层次的聚类8.4.基于密度的聚类8.4.1.DBSCAN算法

8.4.2.OPTICS算法8.4.3.DENCLUE算法8.5.基于网格的聚类8.6.k-均值聚类分析实验8.7.本章小结8.8.本章习题DBSCAN算法概述DBSCAN，英文全写为Density-basedspatialclusteringofapplicationswithnoise，是一种基于数据密度的无监督聚类算法。在聚类空间中的一定区域内，用给定的半径阈值和数量阈值，筛选出核心点及核心点的领域点，通过密度可达、密度相连的定义，实现数据点的聚类。该算法将具有足够密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点的最大集合。DBSCAN算法原理及步骤DBScan需要两个参数：扫描半径(eps)和最小包含点数(minPts)，实现伪码如下：检测样本集中尚未检查过的样本p，如果p未被处理(归为某个簇或者标记为噪声)，则检查其邻域，若包含的样本数不小于minPts，建立新簇C，将其中的所有点加入候选集N；对候选集N中所有尚未被处理的样本q，检查其邻域，若至少包含minPts个样本，则将这些样本加入N；如果q未归入任何一个簇，则将q加入C；重复上步骤，继续检查N中未处理的样本，当前候选集N为空；重复上三步骤，直到所有样本都归入了某个簇或标记为噪声。DBSCAN算法python实现Python实现算法示例：机器学习PAI中对应的组件机器学习PAI中对应的组件为DBSCAN算法组件DBSCAN算法特点小结基于密度的聚类DBSCAN（Density-BasedSpatialClusteringofApplicationswithNoise，具有噪声的基于密度的聚类方法）是一种基于密度的空间聚类算法。该算法将具有足够密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点的最大集合。优点：不需要提前设定K值大小；对噪声不敏感；可以发现任意形状的簇类相对K-Means，聚类结果无偏倚缺点:对两个参数的设置敏感，即圈的半径eps、阈值MinPtsDBSCAN使用固定的参数识别聚类样本集越大，收敛时间越长,计算量越大课程目录8.1.聚类分析概述8.2.基于划分的聚类8.3.基于层次的聚类8.4.基于密度的聚类8.4.1.DBSCAN算法

8.4.2.OPTICS算法8.4.3.DENCLUE算法8.5.基于网格的聚类8.6.k-均值聚类分析实验8.7.本章小结8.8.本章习题OPTICS算法概述OPTICS：OrderingPointstoidentifytheclusteringstructure，点排序识别聚类结构对于真实的、高维的数据集合而言，参数的设置通常是依靠经验，难以确定。绝大多数算法对参数值是非常敏感的，设置的细微不同可能导致差别很大的聚类结果。OPTICS算法通过对象排序识别聚类结构。－OPTICS没有显式地产生一个数据集合簇，它为自动和交互的聚类分析计算一个簇排序。－这个次序代表了数据的基于密度的聚类结构。OPTICS算法提出的背景在前面介绍的DBSCAN算法中，有两个初始参数E（邻域半径）和minPts(E邻域最小点数)需要用户手动设置输入，并且聚类的类簇结果对这两个参数的取值非常敏感，不同的取值将产生不同的聚类结果，其实这也是大多数其他需要初始化参数聚类算法的弊端。为了克服DBSCAN算法这一缺点，提出了OPTICS算法。OPTICS并不显示的产生结果类簇，而是为聚类分析生成一个增广的簇排序（比如，以可达距离为纵轴，样本点输出次序为横轴的坐标图），这个排序代表了各样本点基于密度的聚类结构。它包含的信息等价于从一个广泛的参数设置所获得的基于密度的聚类，换句话说，从这个排序中可以得到基于任何参数E和minPts的DBSCAN算法的聚类结果。

OPTICS算法原理及步骤创建两个队列，有序队列和结果队列。（有序队列用来存储核心对象及其该核心对象的直接可达对象，并按可达距离升序排列；结果队列用来存储样本点的输出次序）；如果所有样本集D中所有点都处理完毕，则算法结束。否则，选择一个未处理（即不在结果队列中）且为核心对象的样本点，找到其所有直接密度可达样本点，如过该样本点不存在于结果队列中，则将其放入有序队列中，并按可达距离排序；OPTICS算法原理及步骤如果有序队列为空，则跳至步骤2，否则，从有序队列中取出第一个样本点（即可达距离最小的样本点）进行拓展，并将取出的样本点保存至结果队列中，如果它不存在结果队列当中的话。3.1

判断该拓展点是否是核心对象，如果不是，回到步骤3，否则找到该拓展点所有的直接密度可达点；3.2

判断该直接密度可达样本点是否已经存在结果队列，是则不处理，否则下一步；3.3

如果有序队列中已经存在该直接密度可达点，如果此时新的可达距离小于旧的可达距离，则用新可达距离取代旧可达距离，有序队列重新排序；3.4

如果有序队列中不存在该直接密度可达样本点，则插入该点，并对有序队列重新排序；算法结束，输出结果队列中的有序样本点。OPTICS算法python实现Python实现算法示例：课程目录8.1.聚类分析概述8.2.基于划分的聚类8.3.基于层次的聚类8.4.基于密度的聚类8.4.1.DBSCAN算法

8.4.2.OPTICS算法8.4.3.DENCLUE算法8.5.基于网格的聚类8.6.k-均值聚类分析实验8.7.本章小结8.8.本章习题DENCLUE算法DENCLUE算法：密度分布函数的聚类DENCLUE是对k-means聚类算法的一个推广：－DENCLUE算法得到的是全局最优划分。DENCLUE主要基于：－每个数据点的影响可以用一个数学函数来形式化地模拟，它描述了一个数据点在领域内的影响，被称为影响函数；－数据空间的整体密度可以被模型化为所有数据点的影响函数的总和；－然后聚类可以通过确定密度吸引点来得到，这里的密度吸引点是全局密度函数的局部最大。课程目录8.1.聚类分析概述8.2.基于划分的聚类8.3.基于层次的聚类8.4.基于密度的聚类8.5.基于网格的聚类

8.5.1.STING算法

8.5.2.CLIQUE算法8.6.k-均值聚类分析实验8.7.本章小结8.8.本章习题STING算法概述STING算法是一种基于网格聚类的算法基于网格聚类的算法核心思想是将数据空间划分为一个个网格，将数据按照一定的规则映射到网格单元中，然后计算每个单元的密度。根据预先设定的阈值判断出每个网格单元是否为高密度单元，由临近的高密度单元组成一个类。常见算法有STING、wave-cluster、clique。不同算法本质上只是划分网格的方法不同而已:STING：基于网格多分辨率，将空间划分为方形单元，对应不同分辨率CLIQUE：结合网格和密度聚类的思想，子空间聚类处理大规模高维度数据WaveCluster：用小波分析使簇的边界变得更加清晰说明：

网格聚类算法一般和基于密度的算法结合使用具体实施步骤如下：（1）从一个层次开始（2）对于这一个层次的每个单元格，我们计算查询相关的属性值。（3）从计算的属性值以及约束条件下，我们将每一个单元格标记成相关或者不想关。(不相关的单元格不再考虑，下一个较低层的处理就只检查剩余的相关单元)（4）如果这一层是底层，那么转（6），否则转（5）（5）我们由层次结构转到下一层，依照步骤2进行（6）查询结果得到满足，转到步骤8，否则（7）（7）恢复数据到相关的单元格进一步处理以得到满意的结果，转到步骤（8）（8）停止；

STING是一个基于网格的多分辨率聚类技术，它将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。关于每个网格单元属性的统计信息（例如平均值，最大值，和最小值）被预先计算和存储。这些统计变量可以方便下面描述的查询处理使用。STING算法原理及步骤STING算法特点小结基于网格聚类优点：1、聚类速度快。

缺点：1、对参数敏感2、无法处理不规则分布的数据3、会产生维度灾难4、算法精度不高基于网格的聚类方法采用空间驱动的方法，把嵌入空间划分成独立于输入对象分布的单元。基于网格的聚类方法使用一种多分辨率的网络数据结构。它将对象空间量化成有限数目的单元，这些网格形成了网格结构，所有的聚类结构都在该结构上进行。这种方法的主要优点是处理速度快，其处理时间独立于数据对象数，而仅依赖于量化空间中的每一维的单元数。课程目录8.1.聚类分析概述8.2.基于划分的聚类8.3.基于层次的聚类8.4.基于密度的聚类8.5.基于网格的聚类

8.5.1.STING算法

8.5.2.CLIQUE算法8.6.k-均值聚类分析实验8.7.本章小结8.8.本章习题CLIQUE算法概述

CLIQUE算法是基于网格的空间聚类算法，但它同时也非常好的结合了基于密度的聚类算法，因此既能够发现任意形状的簇，又可以像基于网格的算法一样处理较大的多维数据。算法需要两个参数：一个是网格的步长，第二个是密度的阈值。网格步长确定了空间的划分，而密度阈值用来定义密集网格。

CLIQUE算法原理首先扫描所有网格。当发现第一个密集网格时，便以该网格开始扩展，扩展原则是若一个网格与已知密集区域内的网格邻接并且其自身也是密集的，则将该网格加入到该密集区域中，直到不再有这样的网格被发现为止。（密集网格合并）算法再继续扫描网格并重复上述过程，知道所有网格被遍历。以自动地发现最高维的子空间，高密度聚类存在于这些子空间中，