数据挖掘 课件 第六章 聚类分析

聚类分析Contents聚类分析介绍01层次聚类02密度聚类03谱聚类04聚类分析介绍什么是聚类？(cluster)聚类分析介绍什么是聚类？(cluster)聚类就是针对大量数据或者样品根据数据本身的特性研究数据分类规则及方法（无监督方式），并遵循这个分类方法实现“同类相同、异类相异”。聚类分析介绍什么是聚类分析？

(clusteranalysis)把“对象”分成不同的类别这些类不是事先给定的，而是直接根据数据的特征确定的把相似的东西放在一起，从而使得类别内部的“差异”尽可能小，而类别之间的“差异”尽可能大聚类分析就是按照对象之间的“相似”程度把对象进行分类聚类分析介绍什么是聚类分析？(两种分类方式)聚类分析的“对象”可以是所观察的多个样本，也可以是针对每个样本测得的多个变量按照变量对所观察的样本进行分类称为Q型聚类按照多项经济指标(变量)对不同的地区(样本)进行分类按照样本对多个变量进行分类，则称为R型聚类按照不同地区的样本数据对多个经济变量进行分类两种聚类没有什么本质区别，实际中人们更感兴趣的通常是根据变量对样本进行分类(Q型聚类)聚类分析介绍什么是聚类分析？(按什么分类)按对象的“相似”程度分类根据样本的观测数据测度变量之间的相似性程度可以使用夹角余弦、Pearson相关系数等工具，也称为相似系数变量间的相似系数越大，说明它们越相近根据变量来测度样本之间的相似程度则使用“距离”把离得比较近的归为一类，而离得比较远的放在不同的类聚类分析介绍相似性的度量

(样本点间距离的计算方法)在对样本进行分类时，度量样本之间的相似性使用点间距离点间距离的计算方法主要有欧氏距离(Euclideandistance)平方欧氏距离(SquaredEuclideandistance)曼哈顿距离(Blockdistance)切比雪夫距离(Chebychevdistance)马氏距离(Minkovskidistance)最常用的是平方欧氏距离聚类分析介绍保险业土地使用市场营销城市规划帮市场分析人员从客户基本库中发现不同的客户群，从而可以对不同的客户群采用不同营销策略在地球监测数据库中，发现相同的土地使用区域发现汽车保险中索赔率较高的客户群根据房子的类型、价值和地理位置对其进行分组地震研究将观测到的震中点沿板块断裂带进行聚类最终可以得出地震高危区聚类分析的实际应用聚类分析介绍聚类分析的算法分类根据处理复杂分布的，高维的或者混合属性的大规模数据方法进行大致分类基于网格(Grid-Based)STING算法、CLIQUE算法等图论谱聚类基于划分（Partitioning）K-均值聚类，K-中心聚类等基于层次(Hierarchical)BIRCH算法、CURE算法、CHAMELEON算法等基于密度(Density-Based)DBSCAN算法、OPTICS算法、DENCLUE算法等基于模型(Model-Based)统计学的COBWEB聚类和神经网络的SOM聚类模糊理论相关领域结合的聚类技术FCM聚类自然计算相关领域结合的聚类技术遗传聚类、克隆选择聚类Contents聚类分析介绍01层次聚类02密度聚类03谱聚类04层次聚类层次的聚类方法将数据对象组成一棵聚类的树根据层次分解是自底向上,还是自顶向下形成,层次的聚类方法可以进一步分为凝聚的(agglomerative)和分裂的(divisive)层次聚类

纯粹的层次聚类方法的聚类质量受限于如下特点：一旦一个合并或分裂被执行，就不能修正最近的研究集中于凝聚层次聚类和迭代重定位方法的集成

使用距离矩阵作为聚类标准.该方法不需要输入聚类数目k,但需要终止条件层次聚类凝聚的(agglomerative)和分裂的(divisive)层次聚类图示Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0agglomerative(AGNES)divisive(DIANA)层次聚类四个广泛采用的簇间距离度量方法

最小距离：dmin(Ci,Cj)=min

p∈Ci,p’∈Cj

|p-p’|

最大距离：dmax(Ci,Cj)=max

p∈Ci,p’∈Cj|p-p’|

平均值的距离：dmean(Ci,Cj)=|mi-mj|

平均距离(簇的直径D)：davg(Ci,Cj)=∑p∈Ci∑p’∈Cj|p-p’|

/ninj其中,|p-p’|是两个对象p和p’之间的距离

mi是簇Ci

的平均值，ni是簇Ci中对象的数目

层次聚类簇与簇之间邻近度的定义:每个簇中的点数不一定相等，如何计算两个不同簇之间的邻近度呢？常用的有三种方法：单链（MIN准则），全链（MAX准则），组平均技术。单链（MIN）定义簇的邻近度为不同簇的两个最近的点之间的邻近度。层次聚类全链（MAX）定义簇的邻近度为不同簇中两个最远的点之间的邻近度作为簇的邻近度。组平均是一种基于图的方法。它定义簇邻近度为取自不同簇的所有点对邻近度的平均值（平均长度）。层次聚类基于划分的聚类方法构造n个对象数据库D的划分,将其划分成k个聚类启发式方法:k-平均值(k-

means)和k-中心点(k-

medoids)算法k-平均值(MacQueen’67):每个簇用该簇中对象的平均值来表示k-中心点或PAM(Partitionaroundmedoids)(Kaufman&Rousseeuw’87):每个簇用接近聚类中心的一个对象来表示这些启发式算法适合发现中小规模数据库中的球状聚类对于大规模数据库和处理任意形状的聚类,这些算法需要进一步扩展层次聚类——K-means聚类算法描述为中心向量c1,c2,…,ck初始化k个种子分组:将样本分配给距离其最近的中心向量由这些样本构造不相交（non-overlapping

）的聚类确定中心:用各个聚类的中心向量作为新的中心重复分组和确定中心的步骤，直至算法收敛层次聚类——K-means聚类算法的具体过程从数据集中任意选取k个赋给初始的聚类中心c1,c2,…,ck；对数据集中的每个样本点xi，计算其与各个聚类中心cj的欧氏距离并获取其类别标号：

按下式重新计算k个聚类中心；重复步骤2和步骤3，直到达到最大迭代次数、聚类目标函数达到最优值或者两次迭代得到的目标函数变化小于给定的

为止。层次聚类——K-means聚类例012345678910012345678910012345678910012345678910K=2任意选择

K个对象作为初始聚类中心将每个对象赋给最类似的中心更新簇的平均值重新赋值更新簇的平均值重新赋值层次聚类——K-means聚类Matlab程序实现function[M,j,e]=kmeans(X,K,Max_Its)[N,D]=size(X);I=randperm(N);M=X(I(1:K),:);Mo=M;forn=1:Max_Itsfork=1:KDist(:,k)=sum((X-repmat(M(k,:),N,1)).^2,2)';end

[i,j]=min(Dist,[],2);fork=1:Kifsize(find(j==k))>0

M(k,:)=mean(X(find(j==k),:));endend层次聚类——K-means聚类Matlab程序实现（续）Z=zeros(N,K);form=1:NZ(m,j(m))=1;end

e=sum(sum(Z.*Dist)./N);fprintf('%dError=%f\n',n,e);Mo=M;end层次聚类——K-means聚类在图像分割上的简单应用例1：图片：一只遥望大海的小狗；此图为100x100像素的JPG图片，每个像素可以表示为三维向量（分别对应JPEG图像中的红色、绿色和蓝色通道）

；将图片分割为合适的背景区域（三个）和前景区域（小狗）；使用K-means算法对图像进行分割。层次聚类——K-means聚类在图像分割上的简单应用分割后的效果注：最大迭代次数为20次，需运行多次才有可能得到较好的效果。层次聚类——K-means聚类在图像分割上的简单应用例2：注：聚类中心个数为5，最大迭代次数为10。层次聚类——K-means聚类优点:相对有效性:O(tkn),其中n

是对象数目,k

是簇数目,t是迭代次数;通常,k,t<<n.当结果簇是密集的，而簇与簇之间区别明显时，它的效果较好弱点只有在簇的平均值(mean)被定义的情况下才能使用.可能不适用于某些应用,例如涉及有分类属性的数据需要预先指顶簇的数目k,不能处理噪音数据和孤立点(outliers)不适合用来发现具有非凸形状(non-convexshapes)的簇层次聚类——K-medoids聚类k-平均值算法对孤立点很敏感!因为具有特别大的值的对象可能显著地影响数据的分布.k-中心点(k-Medoids):不采用簇中对象的平均值作为参照点,而是选用簇中位置最中心的对象,即中心点(medoid)作为参照点.012345678910012345678910012345678910012345678910012345678910012345678910层次聚类——K-medoids聚类找聚类中的代表对象(中心点)PAM(PartitioningAroundMedoids,1987)首先为每个簇随意选择选择一个代表对象,剩余的对象根据其与代表对象的距离分配给最近的一个簇;然后反复地用非代表对象来替代代表对象，以改进聚类的质量

PAM

对于较小的数据集非常有效,但不能很好地扩展到大型数据集层次聚类——K-medoids聚类基本思想：首先为每个簇随意选择选择一个代表对象;剩余的对象根据其与代表对象的距离分配给最近的一个簇；然后反复地用非代表对象来替代代表对象,以改进聚类的质量；聚类结果的质量用一个代价函数来估算。层次聚类——K-medoids聚类为了判定一个非代表对象Orandom是否是当前一个代表对象Oj的好的替代,对于每一个非代表对象p,考虑下面的四种情况：

第一种情况：p当前隶属于代表对象Oj.如果Oj被Orandom所代替,且p离Oi最近,i≠j,那么p被重新分配给Oi

第二种情况：p当前隶属于代表对象Oj.如果Oj被Orandom代替,且p离Orandom最近,那么p被重新分配给Orandom

1.重新分配给Oi 2.重新分配给Orandom层次聚类——K-medoids聚类第三种情况：p当前隶属于Oi，i≠j。如果Oj被Orandom代替，而p仍然离Oi最近，那么对象的隶属不发生变化

第四种情况：p当前隶属于Oi，i≠j。如果Oj被Orandom代替，且p离Orandom最近，那么p被重新分配给Orandom

3.不发生变化4.重新分配给Orandom层次聚类——K-medoids聚类算法:k-中心点(1)随机选择k个对象作为初始的代表对象；(2)repeat (3)指派每个剩余的对象给离它最近的代表对象所代表的簇； (4)随意地选择一个非代表对象Orandom； (5)计算用Orandom代替Oj的总距离E,如果E比取代前下降则则用Orandom替换Oj，形成新的k个代表对象的集合，返回（4）；(6)until不发生变化(7)如果所有非代表对象都无法取代已存在的簇中心，则结束替代过程，并输出结果层次聚类——K-medoids聚类PAM012345678910012345678910K=2ArbitrarychoosekobjectasinitialmedoidsAssigneachremainingobjecttonearestmedoidsRandomlyselectanonmedoidobject,OramdomComputetotalcostofswapping012345678910012345678910TotalCost=26SwappingOandOramdomIfqualityisimproved.DoloopUntilnochange012345678910012345678910TotalCost=20层次聚类——K-medoids聚类PAM当存在噪音和孤立点时,PAM比

k-平均方法更健壮.这是因为中心点不象平均值那么容易被极端数据影响

PAM对于小数据集工作得很好,但不能很好地用于大数据集

每次迭代O(k(n-k)2)

其中

n

是数据对象数目,

k是聚类数基于抽样的方法, CLARA(ClusteringLARgeApplications)层次聚类——CLARACLARA(KaufmannandRousseeuwin1990)不考虑整个数据集,而是选择数据的一小部分作为样本它从数据集中抽取多个样本集,对每个样本集使用PAM,并以最好的聚类作为输出优点:可以处理的数据集比PAM大缺点:有效性依赖于样本集的大小基于样本的好的聚类并不一定是整个数据集的好的聚类,样本可能发生倾斜

例如,Oi是最佳的k个中心点之一,但它不包含在样本中,CLARA将找不到最佳聚类层次聚类——CLARACLARA--效率由取样大小决定PAM→利用完整资料集

CLARA→利用取样资料集

盲点：取样范围不包含最佳解

sampledbestTrade-off层次聚类——CLARACLARA改良解決：CLARANS(ClusteringLargeApplicationbaseduponRANdomizedSearch)应用

graph考虑紧邻节点不局限于区域性复杂度：O(n^2)→缺点层次聚类——CLARANSCLARANS(“Randomized”CLARA)(1994)CLARANS(AClusteringAlgorithmbasedonRandomizedSearch)(NgandHan’94)CLARANS将采样技术和PAM结合起来CLARA在搜索的每个阶段有一个固定的样本CLARANS任何时候都不局限于固定样本,而是在搜索的每一步带一定随机性地抽取一个样本聚类过程可以被描述为对一个图的搜索,图中的每个节点是一个潜在的解,也就是说k-medoids相邻节点：代表的集合只有一个对象不同在替换了一个代表对象后得到的聚类结果被称为当前聚类结果的邻居层次聚类——CLARANSCLARANS(“Randomized”CLARA)(1994)如果一个更好的邻居被发现,CLARANS移到该邻居节点,处理过程重新开始,否则当前的聚类达到了一个局部最优如果找到了一个局部最优,CLARANS从随机选择的节点开始寻找新的局部最优实验显示CLARANS比PAM和CLARA更有效CLARANS能够探测孤立点聚焦技术和空间存取结构可以进一步改进它的性能(Esteretal.’95)层次聚类——CLARANSCLARANS(“Randomized”CLARA)(1994)1、输入参数numlocal和maxneighbor。numlocal表示抽样的次数，maxneighbor表示一个节点可以与任意特定邻居进行比较的数目。令：i=1，i用来表示已经选样的次数mincost为最小代价，初始时设为大数。

2、设置当前节点current为Gn中的任意一个节点。

3、令j=1。（j用来表示已经与current进行比较的邻居的个数）

4、考虑当前点的一个随机的邻居S，并计算两个节点的代价差。5、如果S的代价较低，则current:=S，转到步骤3。

6、否则，令j=j+1。如果j<=maxneighbor,则转到步骤4。

7、否则，当j>maxneighbor，当前节点为本次选样最小代价节点.如果其代价小于mincost,令mincost为当前节点的代价，bestnode为当前的节点。

8、令i=i+1，如果i〉numlocal,输出bestnode，运算中止.否则，转到步骤2。算法步骤：层次聚类——CLARANSCLARANS(“Randomized”CLARA)(1994)1）代价值，主要描述一个对象被分到一个类别中的代价值，该代价值由每个对象与其簇中心点间的相异度（距离或者相似度）的总和来定义。代价差则是两次随机领域的代价差值。

（2）更新邻接点，CLARANS不会把搜索限制在局部区域，如果发现一个更好的近邻，CLARANS就移到该近邻节点，处理过程从新开始；否则，当前的聚类则产生了一个局部最小。如果找到一个局部最小，CLARANS从随机选择的新节点开始，搜索新的局部最小。当搜索的局部最小解达到用户指定的数目时，最好的局部最小作为算法的输出。从上面的算法步骤也可以看出这一思想。在第5步中更新节点current。层次聚类综合比较KmeansKmedoidsCLARACLARANS优点简单不受极值影响可处理大数据找到最佳解缺点受极值影响无法处理大数据不一定是最佳解速度慢复杂度O(nkt)O(k(n-k)^2)O(ks^2+k(n-k))O(n^2)精確度速度层次聚类层次聚类的主要缺点不具有很好的可伸缩性:时间复杂性至少是O(n2),其中n

对象总数合并或分裂的决定需要检查和估算大量的对象或簇不能撤消已做的处理,聚类之间不能交换对象.如果某一步没有很好地选择合并或分裂的决定,可能会导致低质量的聚类结果

层次聚类改进层次方法的聚类质量的方法:将层次聚类和其他的聚类技术进行集成,形成多阶段聚类BIRCH(1996):使用CF-tree对对象进行层次划分,然后采用其他的聚类算法对聚类结果进行求精ROCK1999：基于簇间的互联性进行合并CHAMELEON(1999):使用动态模型进行层次聚类CURE(1998):采用固定数目的代表对象来表示每个簇，然后依据一个指定的收缩因子向着聚类中心对它们进行收缩层次聚类——BIRCHBirch(BalancedIterativeReducingandClusteringusingHierarchies):利用层次方法的平衡迭代归约和聚类由Zhang,Ramakrishnan和Livny提出(SIGMOD’96),该算法的特点是能利用有限的内存资源完成对大数据集的高质量的聚类，同时通过单遍扫描数据集能最小化I/O代价。

两个重要概念聚类特征(ClusteringFeature,CF)聚类特征树(ClusteringFeatureTree,

CF树)聚类特征聚类特征(CF)是一个三元组，给出对象子类的信息的汇总描述设某个子类中有N个d维的点或对象{oI}，则该子类的CF定义如下

层次聚类——BIRCH聚类特征ClusteringFeature:CF=(N,LS,SS)N:数据点数目LS:N个节点特征线性和

Ni=1XiSS:N个节点特征平方和

Ni=1Xi2CF=(5,(16,30),(54,190))(3,4)(2,6)(4,5)(4,7)(3,8)层次聚类——BIRCH聚类特征假定簇C1中有两个点（1，2，3），（3，2，1），簇C2有三个点（1，1，2），（2，2，1），（2，1，2），簇3由C1和C2构成，则：CF1=（2，（1+3，2+2，3+1），（

））=（2，（4，4，4），（10，8，10））CF2=（3，（1+2+2，1+2+1，2+1+2），（

））=（3，（5，4，5），（9，6，9））因此得到CF3为：CF3=（2+3，（4+5，4+4，4+5），（10+9，8+6，10+9））=（5，（9，8，9），（19，14，19））层次聚类——BIRCH聚类特征

层次聚类——BIRCHBIRCH算法有意思的是簇中心、簇半径、簇直径以及两簇之间的距离D0到D3都可以由CF来计算，比如簇直径

簇间距离这里的N，LS和SS是指两簇合并后大簇的N，LS和SS。所谓两簇合并只需要两个对应的CF相加那可层次聚类——BIRCHBIRCH的CF树聚类特征从统计学的观点来看，聚类特征是对给定子类统计汇总:子聚类的0阶,1阶和2阶矩(moments)记录了计算聚类和有效利用存储的关键度量,并有效地利用了存储,因为它汇总了关于子类的信息，而不是存储所有的对象CF树是高度平衡的树，它存储了层次聚类的聚类特征

树中的非叶节点有后代或“孩子”

非叶节点存储了其孩子的CF的总和，即汇总了关于其孩子的聚类信息

CF树有两个参数----影响CF树的大小分支因子B:定义非树叶节点的孩子的最大个数阈值T:给出了存储在树的叶子节点中的子类的最大直径

层次聚类——BIRCHBIRCH的CF树CFtree的结构类似于一棵B-树，它有3个参数：内部节点平衡因子B，叶节点平衡因子L，簇直径阈值T。树中每个Nlonleaf节点最多包含B个孩子节点，Leaf最多只能有L个MinCluster（初始划分子簇），而一个MinCluster的直径不能超过T。例如，一棵高度为3，B为5，L为6的一棵CF树的例子如图所示：层次聚类——BIRCHBIRCH的CF树层次聚类——BIRCHBIRCH的CF树B=5L=6CF1child1CF3child3CF2child2CF6child5CF1child1CF3child3CF2child2CF5child5CF1CF2CF6prevnextCF1CF2CF4prevnextRootNon-leafnodeLeafnodeLeafnode层次聚类——BIRCHCF树构造过程(1)从根节点开始，自上而下选择最近的孩子节点

(2)到达叶子节点后，检查最近的元组CFi能否吸收此数据点

是，更新CF值

否，是否可以添加一个新的元组

是，添加一个新的元组

否则，分裂最远的一对元组，作为种子，按最近距离重新分配其它元组

(3)更新每个非叶节点的CF信息，如果分裂节点，在父节点中插入新的元组，检查分裂，直到root

层次聚类——BIRCHCF树构造过程生成CF树层次聚类——BIRCH构造CF树算法起初，我们扫描数据库，拿到第一个datapointinstance--（1,2,3）,我们创建一个空的Leaf和MinCluster，把点（1,2,3）的id值放入Mincluster，更新MinCluster的CF值为（1,（1,2,3），（1,4,9）），把MinCluster作为Leaf的一个孩子，更新Leaf的CF值为（1,（1,2,3），（1,4,9））。实际上只要往树中放入一个CF（这里我们用CF作为Nonleaf、Leaf、MinCluster的统称），就要更新从Root到该叶子节点的路径上所有节点的CF值。层次聚类——BIRCH插入一个节点当又有一个数据点要插入树中时，把这个点封装为一个MinCluster（这样它就有了一个CF值），把新到的数据点记为CF_new，我们拿到树的根节点的各个孩子节点的CF值，根据D2来找到CF_new与哪个节点最近，就把CF_new加入那个子树上面去。这是一个递归的过程。递归的终止点是要把CF_new加入到一个MinCluster中，如果加入之后MinCluster的直径没有超过T，则直接加入，否则譔CF_new要单独作为一个簇，成为MinCluster的兄弟结点。插入之后注意更新该节点及其所有祖先节点的CF值。层次聚类——BIRCH生成CF树1.从训练集读入第一个样本点，将它放入一个新的CF三元组A，这个三元组的N=1，将这个新的CF放入根节点。2.读入第二个样本点，该点和样本点A同在半径为T的超球体内，因此将该点加入CFA,此时需更新A的三元组值，A的三元组中N=2。3.第三个样本点不能融入之前两个节点形成的超球体内，需要生成一个新的CF三元组B。此时根节点有两个CF三元组A和B4.第四个样本点和第三个样本点在半径小于T的超球体内，因此将该点加入CFB。层次聚类——BIRCH节点分裂插入新节点后，可能有些节点的孩子数大于了B（或L），此时该节点要分裂。对于Leaf，它现在有L+1个MinCluster，我们要新创建一个Leaf，使它作为原Leaf的兄弟结点，同时注意每新创建一个Leaf都要把它插入到双向链表中。L+1个MinCluster要分到这两个Leaf中，怎么分呢？找出这L+1个MinCluster中距离最远的两个Cluster（根据D2），剩下的Cluster看离哪个近就跟谁站在一起。分好后更新两个Leaf的CF值，其祖先节点的CF值没有变化，不需要更新。这可能导致祖先节点的递归分裂，因为Leaf分裂后恰好其父节点的孩子数超过了B。Nonleaf的分裂方法与Leaf的相似，只不过产生新的Nonleaf后不需要把它放入一个双向链表中。如果是树的根节点要分裂，则树的高度加1。层次聚类——BIRCH节点分裂1.一个新的样本点读入，发现它离LN1节点最近，判断是否在sc1,sc2,sc3这3个CF对应的超球体之内，否，因此建立一个新的CF

sc8来容纳它。但是此时LN1的CF个数已经达到最大值了，不能再创建新的CF了，就要将LN1叶子节点一分为二了。2.将LN1里所有CF元组中，最远的两个CF做新叶子节点的种子CF，然后将LN1节点里所有CFsc1,sc2,sc3，以及新样本点的新元组sc8划分到两个新的叶子节点上。3.如果内部节点的最大CF数B=3，则此时叶子节点一分为二会导致根节点的最大CF数超了，此时根节点也要分裂，分裂的方法和叶子节点分裂一样。层次聚类——BIRCHBrich算法的阶段Ø

阶段一：扫描数据库，构造一颗CF树，并定义相关阈值，把稠密数据分成簇。Ø

阶段二：对CF树进行压缩，通过改变T值，将部分簇进行压缩合并，建立一个更小的CF树。Ø

阶段三：采用其他的聚类算法对其叶节点进行聚类，将稀疏的簇当作离群值进行删除，补救由于输入顺序和页面大小带来的分裂。Ø

阶段四：通过上阶段得出聚类质心，将其作为种子节点，将其他对象分配给质心，构成新的聚类。层次聚类——BIRCHBrich算法流程层次聚类——BIRCH重建过程从旧树的叶子节点建造一个新树。这样，重建树的过程不需要重读所有的对象----建树只需读一次数据在阶段三和四采用任何聚类算法，例如典型的划分方法BIRCH的性能支持增量聚类：因为它对每一个数据点的聚类的决策都是基于当前已经处理过的数据点，而不是基于全局的数据点。

线性可伸缩性:计算复杂性O(n),单遍扫描,附加的扫描可以改善聚类质量较好的聚类质量缺点只能处理数值数据对数据的输入次序敏感CF树结点不总是对应于[用户考虑的]自然簇(参数B和T)簇非球形时效果不好(使用半径/直径控制簇边界)层次聚类——CURE“单链”簇的邻近度为不同簇的两个最近的点之间的邻近度。会将由低密度带连接的两个簇错误的合并为一个簇。“组平均”簇邻近度为取自不同簇的所有点对邻近度的平均值（平均长度）。得到的簇偏向于球形，因此会将图中瘦长的簇拆散。层次聚类——CURECURE(ClusteringUsingREpresentatives):由Guha,Rastogi和Shim提出(1998)绝大多数聚类算法或者擅长处理球形和相似大小的聚类，或者在存在孤立点时变得比较脆弱CURE解决了偏好球形的问题，在处理孤立点上也更加健壮CURE采用了一种新的层次聚类算法选择基于质心和基于代表对象方法之间的中间策略.它不用单个质心或对象来代表一个簇,而是选择了数据空间中固定数目的具有代表性的点（采用的方法介于“单链”和“组平均”之间，克服了这两种层次聚类算法的不足之处。）首先选择簇中分散的对象,然后根据一个特定的收缩因子向簇中心“收缩”，距离质心越远的点（例如离群点）的收缩程度越大。层次聚类——CURE每个簇有多于一个的代表点使得CURE可以适应非球形的任意形状的聚类簇的收缩或凝聚可以有助于控制孤立点的影响CURE的优点CURE对孤立点的处理更加健壮能够识别非球形和大小变化较大的簇对于大规模数据库,它也具有良好的伸缩性,而且没有牺牲聚类质量

针对大型数据库,CURE采用了随机取样和划分两种方法的组合首先划分一个随机样本,每个划分被部分聚类然后对这些结果簇聚类,产生希望的结果

层次聚类——CURECURE算法核心:从源数据对象中抽取一个随机样本集S.将样本S分割为p个划分,每个的大小为

s/p将每个划分局部地聚类成s/pq

个簇删除孤立点通过随机选样如果一个簇增长太慢,就删除它.对局部聚类进行聚类.用相应的簇标签来标记数据层次聚类——CURExyyyyxyxs=50p=2s/p=25s/pq=5层次聚类——CURExyxy多个代表点向重心以因子

移动,进行收缩或凝聚多个代表点描述了每个簇的形状层次聚类——ROCKROCK(RObustClusteringusinglinKs)由S.Guha,R.Rastogi,K.Shim提出(ICDE’99).使用链接(link)度量相似性/接近性链接：两个对象间共同的近邻的数目不是基于距离的计算复杂性:基本思想:相似性函数:Jaccard系数

设T1={1,2,3},T2={3,4,5}层次聚类——ROCK两个点pi和pj是近邻，如果sim(pi,pj)>=用户指定阈值link(pi,pj)是两个点pi和pj共同的近邻的数目两个簇Ci和Cj的互连性被定义为两个簇间交叉链（crosslink）的数目ROCK首先根据相似度阀值和共享近邻的概念，从给定的数据相似度矩阵构建一个稀疏的图，然后在这个稀疏图上运行一个层次聚类算法层次聚类——CHAMELEONCHAMELEON:一个利用动态模型的层次聚类算法(Hierarchicalclusteringusingdynamicmodeling)由G.Karypis,E.H.Han,andV.Kumar’99提出对CURE和ROCK缺点的观察:Cure忽略了关于两个不同簇中对象的聚集互连性的信息Rock强调对象间互连性,却忽略了关于对象间近似度的信息CHAMELEON基于动态模型度量相似性如果两个簇间的互连性和近似度与簇内部对象间的互连性和近似度高度相关,则合并这两个簇层次聚类——CHAMELEON两阶段算法使用图划分算法:将数据对象聚类为大量相对较小的子类逐步用图划分算法把k近邻图分成相对较小的子簇，最小化割边。使用凝聚的层次聚类算法：通过反复地合并子类来找到真正的结果簇既考虑互连性,又考虑簇间的近似度,特别是簇内部的特征,来确定最相似的子类.这样,它不依赖于静态的用户提供的模型,能够自动地适应被合并的簇的内部特征割边最小化——簇c划分为两个子簇Ci和Cj时需要割断的边的加权和最小。割边用EC{Ci，Cj}表示，评估Ci和Cj的簇间的绝对互联性。层次聚类——CHAMELEON构造稀疏图划分图合并划分最终的簇DataSetK-最近邻居图层次聚类——CHAMELEONk-最近邻图Gk:图中的每个点代表一个数据对象,如果一个对象是另一个对象的k个最类似的对象之一,在这两个点之间存在一条边

k-最近邻图Gk动态地捕捉邻域的概念：一个对象的邻域半径由对象所在区域的密度所决定在一个密集区域,邻域的定义范围相对狭窄;在一个稀疏区域,它的定义范围相对较宽

区域的密度作为边的权重被记录下来一个密集区域的边趋向于比稀疏区域的边有更大的权重

层次聚类——CHAMELEONChameleon通过两个簇的相对互连性RI(Ci,Cj)和相对接近度RC(Ci,Cj)来决定簇间的相似度

RI(Ci,Cj)定义为Ci和Cj之间的绝对互联性关于两个簇的内部互连性的规范化

其中,EC{Ci，Cj}是包含Ci和Cj的簇分裂为Ci和Cj的割边,ECCi（或ECCj）是它的最小截断等分线的大小（即将图划分为两个大致相等的部分需要切断的边的加权和）

层次聚类——CHAMELEONRC(Ci,Cj)定义为Ci和Cj之间的绝对接近度关于两个簇的内部接近度的规范化

其中,是连接Ci和Cj顶点的边的平均权重

是Ci的最小二等分的边的平均权重

Contents聚类分析介绍01层次聚类02密度聚类03谱聚类04密度聚类基于密度的方法基于密度聚类(Density-BasedClustering)主要特点:发现任意形状的聚类处理噪音一遍扫描需要密度参数作为终止条件一些有趣的研究:DBSCAN:Ester,etal.(KDD’96)OPTICS:Ankerst,etal(SIGMOD’99).DENCLUE:Hinneburg&D.Keim(KDD’98)CLIQUE:Agrawal,etal.(SIGMOD’98)密度聚类基于密度的聚类：背景Ⅰ两个参数:Eps:邻域的最大半径MinPts:在Eps-邻域中的最少点数NEps(p): {qbelongstop|dist(p,q)<=Eps}直接密度可达的:点p

关于Eps,MinPts

是从点q直接密度可达的,如果

1)p

属于NEps(q)2)核心点条件:|NEps(q)|>=MinPts

pqMinPts=5Eps=1cm密度聚类密度概念核心对象(Coreobject):一个对象的

–邻域至少包含最小数目MinPts个对象,不是核心点,但落在某个核心点的Eps邻域内的对象称为边界点,不属于任何簇的对象为噪声.对于空间中的一个对象，如果它在给定半径e的邻域中的对象个数大于密度阈值MinPts，则该对象被称为核心对象，否则称为边界对象。CoreBorderOutlierEps=1cmMinPts=5密度聚类密度概念直接密度可达的(Directlydensityreachable,DDR):给定对象集合D,如果p是在q的

–邻域内,而q是核心对象,我们说对象p是从对象q直接密度可达的(如果q是一个核心对象，p属于q的邻域，那么称q直接密度可达p。)密度可达的(densityreachable):存在一个从q到p的DDR对象链(如果存在一条链<p1,p2,…..,pi>，满足p1=p，pi=q，pi+1直接密度可达pi，则称q密度可达p)pqMinPts=5Eps=1cm由一个核心对象和其密度可达的所有对象构成一个聚类。密度聚类基于密度的聚类：背景Ⅱ密度可达:点p

关于Eps,MinPts

是从

q密度可达的,如果存在一个节点链p1,…,pn,p1=q,pn=p

使得pi+1

是从pi直接密度可达的密度相连的:点p关于Eps,MinPts

与点

q是密度相连的,如果存在点o使得,p

和

q

都是关于Eps,MinPts

是从

o密度可达的(如果存在o，o密度可达q和p，则称p和q是密度连通的)pqopqp1密度聚类密度概念Eg:

假设半径

Ε=3

，

MinPts=3

，点

p

的

领域中有点

{m,p,p1,p2,o},

点

m

的

领域中有点

{m,q,p,m1,m2},

点

q的

领域中有

{q,m},

点

o

的

领域中有点

{o,p,s},

点

s

的

领域中有点

{o,s,s1}.那么核心对象有

p,m,o,s(q

不是核心对象，因为它对应的

领域中点数量等于

2

，小于

MinPts=3)

；点

m

从点

p

直接密度可达，因为

m

在

p

的

领域内，并且

p

为核心对象；点

q

从点

p

密度可达，因为点

q

从点

m

直接密度可达，并且点

m

从点

p

直接密度可达；点

q

到点

s

密度相连，因为点

q

从点

p

密度可达，并且

s

从点

p

密度可达。密度聚类例子：MinPts=3q是从p密度可达；p不是从q密度可达（q非核心）S和r从o密度可达；o从r密度可达；r,s密度相连密度聚类例子：a为核心对象，b为边界对象，且a直接密度可达b，但b不直接密度可达a,因为b不是一个核心对象密度聚类例子：c直接密度可达a,a直接密度可达b,所以c密度可达b，同理b不密度可达c，但b和c密度相连密度聚类——DBSCANDBSCAN(DensityBasedSpatialClusteringofApplicationswithNoise)一个基于密度的聚类算法可以在带有“噪音”的空间数据库中发现任意形状的聚类CoreBorderOutlierEps=1cmMinPts=5密度聚类——DBSCAN

DBSCAN：一种基于高密度连通区域的基于密度的聚类方法，该算法将具有足够高密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇。它将簇定义为密度相连的点的最大集合；算法任意选取一个点p得到所有从p

关于Eps

和MinPts密度可达的点.如果p

是一个核心点,则找到一个聚类.如果p

是一个边界点,没有从p

密度可达的点,DBSCAN将访问数据库中的下一个点.继续这一过程,直到数据库中的所有点都被处理.DBSCAN的复杂度采用空间索引,复杂度为O(nlogn),否则为O(n2)DBSCAN的缺点:对用户定义的参数是敏感的,参数难以确定(特别是对于高维数据),设置的细微不同可能导致差别很大的聚类.（数据倾斜分布）全局密度参数不能刻画内在的聚类结构密度聚类——DBSCANDBSCAN从任一对象p开始，根据参数e和MinPts提取所有从p密度可达对象，得到一个聚类。1.

从任一对象p开始。a)

如果p是核心对象，则p和p直接密度可达的所有对象被标记为类i。递归p直接密度可达的所有对象qi（即用qi代替p回到第一步）。b)

如果p是一个边界对象，那么p被标记为噪声。2.

i++3.

如果还有没被标记的对象，则从中任选一个作为p，回到第一步。密度聚类——DBSCAN算法：

DBSCAN输入：

—

半径

MinPts

—

给定点在

邻域内成为核心对象的最小领域点数

D

—

集合输出：目标类簇集合方法：

repeat1)

判断输入点是否为核心对象2)

找出核心对象的

邻域中的所有直接密度可达点

util

所有输入点都判断完毕

repeat

针对所有核心对象的

邻域所有直接密度可达点找到最大密度相连对象集合，

中间涉及到一些密度可达对象的合并。

Util

所有核心对象的

邻域都遍历完毕密度聚类——DBSCAN密度聚类——DBSCAN密度聚类——DBSCAN密度聚类——DBSCAN密度聚类——DBSCAN密度聚类——OPTICS在前面介绍的DBSCAN算法中，有两个初始参数

（邻域半径）和minPts(

邻域最小点数)需要用户手动设置输入，并且聚类的类簇结果对这两个参数的取值非常敏感，不同的取值将产生不同的聚类结果，其实这也是大多数其他需要初始化参数聚类算法的弊端。OPTICS(OrderingPointsToIdentifytheClusteringStructure)Ankerst,Breunig,Kriegel,和Sander提出(SIGMOD’99)为自动和交互的聚类分析计算一个簇次序(clusterordering).OPTICS并不显式的产生结果类簇，而是为聚类分析生成一个增广的簇排序（比如，以可达距离为纵轴，样本点输出次序为横轴的坐标图），这个排序代表了各样本点基于密度的聚类结构。它包含的信息等价于从一个广泛的参数设置所获得的基于密度的聚类，换句话说，从这个排序中可以得到基于任何参数E和minPts的DBSCAN算法的聚类结果。密度聚类——OPTICS这个次序代表了数据的基于密度的聚类结构。它包含了信息,等同于从一个广域的参数设置所获得的基于密度的聚类可用于自动和交互聚类分析,包括发现内在聚类结构可以使用图形或可视化技术表示考虑DBSCAN,对一个恒定的MinPts值,关于高密度的(即较小的

值)的聚类结果被完全包含在根据较低密度所获得的密度相连的集合中

扩展DBSCAN算法来同时处理一组距离参数值密度聚类——OPTICS为了同时构建不同的聚类,应当以特定的顺序来处理对象.优先选择最小的

值密度可达的对象,以便高密度的聚类能被首先完成

每个对象需要存储两个值对象p的核心距离(core-distance)是使得p成为核心对象的最小

。如果p不是核心对象,p的核心距离没有定义

对象q关于另一个对象p的可达距离(reachability-distance)是p的核心距离和p与q的欧几里得距离之间的较大值.如果p不是一个核心对象,p和q之间的可达距离没有定义

密度聚类——OPTICS例:设

=6(mm),MinPts=5.p的核心距离是p与四个最近的数据对象之间的距离

’.q1关于p的可达距离是p的核心距离(即

’=3mm),因为它比从p到q1的欧几里得距离要大.q2关于p的可达距离是从p到q2的欧几里得距离,它大于p的核心距离

=6mm

’=3mm=6mm

’=3mmppq1q2P的核心距离可达距离(p,q1)=’=3mm可达距离(p,q2)=d(p,q2)密度聚类——OPTICS例如：假设邻域半径E=2,minPts=3，存在点A(2,3),B(2,4),C(1,4),D(1,3),E(2,2),F(3,2)点A为核心对象，在A的E领域中有点{A,B,C,D,E,F}，其中A的核心距离为E’=1，因为在点A的E’邻域中有点{A,B,D,E}>3;点F到核心对象点A的可达距离为

，因为A到F的欧几里得距离

大于点A的核心距离1.OPTICS算法额外存储了每个对象的核心距离和可达距离。基于OPTICS产生的排序信息来提取类簇。密度聚类——OPTICS算法：OPTICS输入：样本集D,邻域半径E,给定点在E领域内成为核心对象的最小领域点数MinPts输出：具有可达距离信息的样本点输出排序方法：1、创建两个队列，有序队列和结果队列。（有序队列用来存储核心对象及其该核心对象的直接可达对象，并按可达距离升序排列；结果队列用来存储样本点的输出次序。你可以把有序队列里面放的理解为待处理的数据，而结果队列里放的是已经处理完的数据）；2、如果所有样本集D中所有点都处理完毕，则算法结束。否则，选择一个未处理（即不在结果队列中）且为核心对象的样本点，找到其所有直接密度可达样本点，如果该样本点不存在于结果队列中，则将其放入有序队列中，并按可达距离排序；3、如果有序队列为空，则跳至步骤2（重新选取处理数据）。否则，从有序队列中取出第一个样本点（即可达距离最小的样本点）进行拓展，并将取出的样本点保存至结果队列中(如果它不存在结果队列当中的话)。然后进行下面的处理。3.1.判断该拓展点是否是核心对象，如果不是，回到步骤3（因为它不是核心对象，所以无法进行扩展了。那么就回到步骤3里面，取最小的。这里要注意，第二次取不是取第二小的，因为第一小的已经放到了结果队列中了，所以第二小的就变成第一小的了。）。如果该点是核心对象，则找到该拓展点所有的直接密度可达点；3.2.判断该直接密度可达样本点是否已经存在结果队列，是则不处理，否则下一步；3.3.如果有序队列中已经存在该直接密度可达点，如果此时新的可达距离小于旧的可达距离，则用新可达距离取代旧可达距离，有序队列重新排序(因为一个对象可能直接由多个核心对象可达，因此，可达距离近的肯定是更好的选择)；3.4.如果有序队列中不存在该直接密度可达样本点，则插入该点，并对有序队列重新排序；4、迭代2，3。5、算法结束，输出结果队列中的有序样本点。密度聚类——OPTICS大家或许会很疑惑，这里不也有输入参数E和MinPts吗？其实这里的E和MinPts只是起到算法辅助作用，也就是说E和MinPts的细微变化并不会影响到样本点的相对输出顺序，这对我们分析聚类结果是没有任何影响。我们采用与先前DBSCAN相同的样本点集合，对于样本点a={2,3};b={2,4};c={1,4};d={1,3};e={2,2};f={3,2};g={8,7};h={8,6};i={7,7};j={7,6};k={9,5};l={100,2};//孤立点m={8,20};n={8,19};o={7,18};p={7,17};q={8,21};并且使用相同的E=2

MinPts=4时，输出具有可达距离信息的样本点输出排序密度聚类——OPTICS1->a:1.02->e:1.03->b:1.04->d:1.05->c:1.41421356237309516->f:1.4142135623730951------7->g:1.41421356237309518->j:1.41421356237309519->k:1.414213562373095110->i:1.414213562373095111->h:1.4142135623730951------12->n:2.013->q:2.014->o:2.015->m:2.0密度聚类——OPTICS如图，按照算法，分三个阶段输出了三波值,{a,e,b,d,},{c,f,g,j,k,I,h},{n,q,o,m}

这和DBSCAN的类簇结果是一样的。不仅如此，我们通过分析有序图还能直接得到当参数E=1.5,minPts=4时DBSCAN的类簇结果，只要在坐标图中找到Y值小于1.5的样本点即可，只有两类{a,e,b,d,c,f},{g,j,k,I,h},其他点被认为是孤立点，和DBSCAN聚类算法取E=1.5,minPts=4时的结果一致。所以说，这个OPTICS聚类算法所得的簇排序信息等价于一个广泛的参数设置所获得的基于密度的聚类结果。密度聚类——OPTICS这些值怎样使用？OPTICS算法创建了数据库中对象的一个次序,额外存储了每个对象的核心距离和一个适当的可达距离已经提出了一种算法,基于OPTICS产生的次序信息来抽取聚类.对于小于在生成该次序中采用的距离

的任何距离

’,为提取所有基于密度的聚类,这些信息是足够的

一个数据集合的聚类次序可以被图形化地描述，以助于理解

由于OPTICS算法与DBSCAN在结构上的等价性,它具有和DBSCAN相同的时间复杂度,即当使用空间索引时,复杂度为O(nlogn)

密度聚类——OPTICS可达距离‘密度聚类——OPTICS密度聚类——OPTICS密度聚类——OPTICS密度聚类——DENCLUEDENCLUE(DENsity-basedCLUstEring)由Hinneburg和Keim(KDD’98)提出,是基于密度分布函数的聚类方法主要特点坚实的数学基础,概括了其他的聚类方法,包括基于划分的,层次的,及基于位置的方法适用于具有大量噪音的数据集可用于高维数据集任意形状的聚类,它给出了简洁的数学描述明显快于现有算法(比DBSCAN快45倍)但是,需要大量参数,要求对密度参数σ和噪音阀值ξ进行仔细的选择密度聚类——DENCLUE使用栅格单元,但只保存实际存放数据点的栅格单元信息,并且在一个基于树的存取结构中管理这些单元.影响函数(Influencefunction):描述数据点在其邻域的影响.数据空间的整体密度可以被模拟为所有数据点的影响函数的总和聚类可以通过确定密度吸引点(densityattractor)来得到.密度吸引点是全局密度函数的局部最大值.密度聚类——DENCLUE设x和y是d维特征空间Fd中的对象.数据对象y对x的影响函数是一个函数fyB：Fd→R+0,它是根据一个基本的影响函数fB来定义的

fyB(x)=fB(x,y)原则上,影响函数可以是一个任意的函数,它由某个邻域内的两个对象之间的距离来决定

例如欧几里得距离函数,用来计算一个方波影响函数(squarewaveinfluencefunction)：

密度聚类——DENCLUE高斯影响函数一个对象x∈Fd的密度函数被定义为所有数据点的影响函数的和.给定n个对象,D={x1,…,xn}

Fd,在x上的密度函数定义如下

密度聚类——DENCLUE例如,根据高斯影响函数得出的密度