大学精品课件：CHAPTER10-聚类分析：基本概念和方法.ppt

1、1作业：课后习题作业：课后习题8.7、8.12、8.14钱峰钱峰通信与信息工程学院通信与信息工程学院第第1010章章 聚类分析：基聚类分析：基本概念和方法本概念和方法3第第10章：聚类分析：基本概念和方法章：聚类分析：基本概念和方法n 聚类分析聚类分析n 划分方法划分方法n 层次方法层次方法n 基于密度的方法基于密度的方法n 基于网格的方法基于网格的方法n 聚类评估聚类评估n 小结小结什么是聚类分析什么是聚类分析?n聚类聚类:数据对象的集合数据对象的集合/簇簇(cluster)n同一簇中的对象彼此相似同一簇中的对象彼此相似n不同簇中的对象彼此相异不同簇中的对象彼此相异n聚类分析聚类分析n将数据

2、对象分组成为多个类或簇将数据对象分组成为多个类或簇n聚类是聚类是无监督的无监督的分类：没有预先定义的类分类：没有预先定义的类n典型应用典型应用n作为洞察数据内部分布的独一无二的工具作为洞察数据内部分布的独一无二的工具 n作为其它算法的预处理步骤作为其它算法的预处理步骤聚类的一般应用聚类的一般应用 n模式识别模式识别n空间数据分析空间数据分析 n聚类产生聚类产生GIS(地理信息系统地理信息系统)的专题地图的专题地图thematic maps n在空间数据挖掘中检测空间聚类并解释它们在空间数据挖掘中检测空间聚类并解释它们n图象处理图象处理n经济科学经济科学(特别是市场研究特别是市场研究)nWWWn

3、文本分类文本分类nWeb日志数据聚类，发现类似访问模式群日志数据聚类，发现类似访问模式群聚类应用的例子聚类应用的例子n市场营销市场营销:帮助市场营销者发现他们的基本顾客的不同组群，然后利用这一知帮助市场营销者发现他们的基本顾客的不同组群，然后利用这一知识制定有针对性的营销计划识制定有针对性的营销计划n国土利用国土利用在地球观测数据库中识别类似的国土使用区域在地球观测数据库中识别类似的国土使用区域n保险保险 对汽车保险持有者的分组对汽车保险持有者的分组 n城市规划城市规划根据房子的类型，价值，和地理位置对一个城市中房屋的分组根据房子的类型，价值，和地理位置对一个城市中房屋的分组 n地震研究地震研

4、究应当将观测到的地震震中沿大陆板块断裂进行聚类应当将观测到的地震震中沿大陆板块断裂进行聚类聚类分析的主要步骤聚类分析的主要步骤n特征选择特征选择n选择与任务密切相关的信息n尽可能减少信息冗余n相似度评价相似度评价n两个特征向量的相似性n聚类的评价准则聚类的评价准则n通过代价函数或某些规则n聚类算法聚类算法nk-均值、极大似然、n结果验证结果验证n验证聚类结果的有效性n结果解释结果解释n根据实际应用解释聚类结果7什么是好的聚类方法什么是好的聚类方法?n一个好的聚类方法应当产生高质量的聚类一个好的聚类方法应当产生高质量的聚类n类内相似性高类内相似性高n类间相似性低类间相似性低n聚类结果的质量依赖于

5、方法所使用的相似性度量聚类结果的质量依赖于方法所使用的相似性度量和它的实现和它的实现.n聚类方法的质量也用它聚类方法的质量也用它发现发现某些或全部隐藏的模某些或全部隐藏的模式的能力来度量式的能力来度量数据挖掘对聚类的要求数据挖掘对聚类的要求 n可伸缩性可伸缩性n有的算法当数据对象少于有的算法当数据对象少于200时处理很好时处理很好,但对大量数但对大量数据对象偏差较大据对象偏差较大n大型数据库包含数百万个对象大型数据库包含数百万个对象n处理不同属性类型的能力处理不同属性类型的能力n许多算法专门用于数值类型的数据许多算法专门用于数值类型的数据n实际应用涉及不同数据类型（实际应用涉及不同数据类型（数

6、值和分类数据混合）数值和分类数据混合）n发现任意形状的聚类发现任意形状的聚类n基于距离的聚类趋向于发现具有相近尺度和密度的球基于距离的聚类趋向于发现具有相近尺度和密度的球状簇状簇 n一个簇可能是任意形状的一个簇可能是任意形状的数据挖掘对聚类的要求数据挖掘对聚类的要求(续续)n用于决定输入参数的领域知识最小化用于决定输入参数的领域知识最小化n许多聚类算法要求用户输入一定的参数，许多聚类算法要求用户输入一定的参数，如希望产生的如希望产生的簇的数目。簇的数目。n参数难以确定，增加用户负担，使聚类质量难以控制参数难以确定，增加用户负担，使聚类质量难以控制n处理噪声数据和孤立点的能力处理噪声数据和孤立点

7、的能力 n一些聚类算法对于噪音数据敏感一些聚类算法对于噪音数据敏感,可能导致低质量的聚可能导致低质量的聚类结果类结果n现实世界中的数据库大都包含了孤立点现实世界中的数据库大都包含了孤立点,空缺空缺,或者错误或者错误的数据的数据 n对于输入记录的顺序不敏感对于输入记录的顺序不敏感 n一些聚类算法对于输入数据的顺序是敏感的一些聚类算法对于输入数据的顺序是敏感的,以不同的以不同的次序输入会导致不同的聚类次序输入会导致不同的聚类数据挖掘对聚类的要求数据挖掘对聚类的要求(续续)n高维性（高维性（high dimensionality）n许多聚类算法擅长处理低维的数据许多聚类算法擅长处理低维的数据,可能只

8、涉及两到三维可能只涉及两到三维 n数据库或者数据仓库可能包含若干维或者属性数据库或者数据仓库可能包含若干维或者属性,数据可能数据可能非常稀疏非常稀疏,而且高度偏斜而且高度偏斜 n整合用户指定的约束整合用户指定的约束n现实世界的应用可能需要在各种约束条件下进行聚类现实世界的应用可能需要在各种约束条件下进行聚类 n要找到既满足要找到既满足特定的约束特定的约束,又具有良好聚类特性的数据分又具有良好聚类特性的数据分组是一项具有挑战性的任务组是一项具有挑战性的任务 n可解释性和可用性可解释性和可用性 n用户希望聚类结果是可解释的用户希望聚类结果是可解释的,可理解的可理解的,和可用的和可用的 n聚类可能需

9、要和特定的语义解释和应用相联系聚类可能需要和特定的语义解释和应用相联系 聚类分析的方法聚类分析的方法n划分方法划分方法:nConstruct various partitions and then evaluate them by some criterion,e.g.,minimizing the sum of square errorsnTypical methods:k-means,k-medoids,CLARANSn层次方法层次方法:nCreate a hierarchical decomposition of the set of data(or objects)using some

10、 criterionnTypical methods:Diana,Agnes,BIRCH,CAMELEONn基于密度的方法基于密度的方法:nBased on connectivity and density functionsnTypical methods:DBSACN,OPTICS,DenCluen基于网格的方法基于网格的方法:nbased on a multiple-level granularity structurenTypical methods:STING,WaveCluster,CLIQUE12聚类分析的方法聚类分析的方法 n基于模型的方法基于模型的方法:nA model is

11、 hypothesized for each of the clusters and tries to find the best fit of that model to each othernTypical methods:EM,SOM,COBWEBn基于频繁模式的方法基于频繁模式的方法:nBased on the analysis of frequent patternsnTypical methods:p-Clustern基于约束的方法基于约束的方法:nClustering by considering user-specified or application-specific co

12、nstraintsnTypical methods:COD(obstacles),constrained clusteringn基于链接的方法基于链接的方法:nObjects are often linked together in various waysnMassive links can be used to cluster objects:SimRank,LinkClus1314第第10章：聚类分析：基本概念和方法章：聚类分析：基本概念和方法n 聚类分析聚类分析n 划分方法划分方法n 层次方法层次方法n 基于密度的方法基于密度的方法n 基于网格的方法基于网格的方法n 聚类评估聚类评估n

13、 小结小结划分方法划分方法n划分方法划分方法:构造构造n个对象数据库个对象数据库D的划分的划分,将其划分成将其划分成k个聚类个聚类n给定给定 k,找找k 个个clusters 对于选定的划分标准它是最优的对于选定的划分标准它是最优的n全局最优全局最优(Global optimal):枚举所有的划分枚举所有的划分n启发式方法启发式方法(Heuristic methods):k-平均平均(k-means)和和k-中中心点心点(k-medoids)算法算法nk-平均平均(MacQueen67):每个簇用簇的重心每个簇用簇的重心(簇的平均值簇的平均值)表示表示nk-中心点或中心点或PAM(Partit

14、ion around medoids)(Kaufman&Rousseeuw87):每个簇用接近聚类中心的一个对象来每个簇用接近聚类中心的一个对象来表示表示 k-平均聚类算法平均聚类算法 n算法：算法：k-平均平均(1)任意选择任意选择k个对象作为初始的簇中心；个对象作为初始的簇中心；(2)repeat(3)根据簇中对象的平均值根据簇中对象的平均值,将每个对象将每个对象(重新重新)赋给最类似的簇；赋给最类似的簇；(4)更新簇的平均值更新簇的平均值,即重新计算每个簇中对象的平均值；即重新计算每个簇中对象的平均值；(5)until 不再发生变化不再发生变化 n通常通常,采用平方误差准则作为收敛函数采

15、用平方误差准则作为收敛函数,其定义如下其定义如下 其中其中,mi是簇是簇Ci的平均值的平均值该准则试图使生成的结果簇尽可能紧凑该准则试图使生成的结果簇尽可能紧凑,独立独立21|kiCpiimpEk-平均聚类算法平均聚类算法(续续)n例例012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910K=2任意选择任意选择 K个对象作个对象作为初始聚类中心为初始聚类中心将每个将每个对象赋对象赋给最相给最相似中心似中心更新簇

16、更新簇平均值平均值重新赋值重新赋值更新簇更新簇平均值平均值重新赋值重新赋值k-平均聚类算法平均聚类算法(续续)n优点优点:相对有效性相对有效性:O(tkn),其中其中，n是对象数目，是对象数目，k是簇数目，是簇数目，t 是迭代次数是迭代次数;通常：通常：k，t 1,2,3 8,9,10,25 1,2,3,8 9,10,25nk-中心点中心点(k-Medoids):不采用簇中对象的平均值作为参照不采用簇中对象的平均值作为参照点点,而是选用簇中而是选用簇中位置最中心的对象位置最中心的对象,即中心点即中心点(medoid)作作为参照点为参照点01234567891001234567891001234

17、5678910012345678910k-中心点聚类方法中心点聚类方法(续续)n找聚类中的代表对象找聚类中的代表对象(中心点中心点)nPAM（Partitioning Around Medoids,1987）n首先为每个簇随意选择一个首先为每个簇随意选择一个代表对象代表对象,剩余的对象根据其剩余的对象根据其与代表对象的距离分配给最近的一个簇与代表对象的距离分配给最近的一个簇n反复地用非代表对象替代代表对象，以改进聚类的质量反复地用非代表对象替代代表对象，以改进聚类的质量 nPAM 对于较小的数据集非常有效对于较小的数据集非常有效,但不能很好地扩展到但不能很好地扩展到大型数据集大型数据集nCLA

18、RA(Kaufmann&Rousseeuw,1990)抽样抽样nCLARANS(Ng&Han,1994):随机选样随机选样n算法算法:k-中心点中心点(1)随机选择随机选择k个对象作为初始的代表对象；个对象作为初始的代表对象；(2)repeat(3)指派每个剩余的对象给离它最近的代表对象所代表的簇；指派每个剩余的对象给离它最近的代表对象所代表的簇；(4)随意地选择一个非代表对象随意地选择一个非代表对象Orandom；(5)计算用计算用Orandom代替代替Oj的总代价的总代价S；(6)若若S0，用用Orandom替换替换Oj，形成新的形成新的k个代表对象的集合；个代表对象的集合；(7)unti

19、l 不发生变化不发生变化k-中心点聚类方法中心点聚类方法(续续)O1O2O3。Oj。OkOrandomTotal Cost=20012345678910012345678910k=2任意选任意选择择 k k 个个数据对数据对象作为象作为初始类初始类中心点中心点将每个将每个剩余的剩余的数据对数据对象安排象安排对最近对最近的类的类随机选择一个非类中随机选择一个非类中心数据对象心数据对象 Oramdom计算交换计算交换的代价的代价012345678910012345678910Total Cost=26若聚类质若聚类质量上升，量上升，交 换交 换 O 与与 Oramdom.执行循环直执行循环直至类不

20、在发至类不在发生变化生变化012345678910012345678910k-中心点聚类方法中心点聚类方法(续续)k-中心点聚类方法中心点聚类方法(续续)n为了判定一个非代表对象为了判定一个非代表对象Orandom是否是当前一个代表对象是否是当前一个代表对象Oj的好的替代，对于每一个非代表对象，考虑下面四种情况：的好的替代，对于每一个非代表对象，考虑下面四种情况：n第一种情况：第一种情况：p当前隶属于代表对象当前隶属于代表对象Oj.如果如果Oj被被Orandom所代替所代替,且且p离离Oi最近最近,ij,那么那么p被重新分配给被重新分配给Oi n第二种情况：第二种情况：p当前隶属于代表对象当前

21、隶属于代表对象Oj.如果如果Oj 被被Orandom代替代替,且且p离离Orandom最近最近,那么那么p被重新分配给被重新分配给Orandom n第三种情况：第三种情况：p当前隶属于当前隶属于Oi，ij。如果如果Oj被被Orandom代替，而代替，而p仍然离仍然离Oi最近，那么对象的隶属不发生变化最近，那么对象的隶属不发生变化 n第四种情况：第四种情况：p当前隶属于当前隶属于Oi，ij。如果如果Oj被被Orandom代替，且代替，且p离离Orandom最近，那么最近，那么p被重新分配给被重新分配给Orandom 1.重新分配给重新分配给Oi 2.重新分配给重新分配给Orandom 3.不发生

22、变化不发生变化 4.重新分配给重新分配给Orandom 数据对象数据对象+簇中心簇中心 替代前替代前 替代后替代后k-中心点聚类代价函数的四种情况中心点聚类代价函数的四种情况+OrandomOiOjp+OrandomOiOjp+OrandomOiOjp+OrandomOiOjpk-中心点聚类方法中心点聚类方法(续续)n当存在噪音和孤立点时，当存在噪音和孤立点时，PAM 比比 k-平均方法更健平均方法更健壮，其原因是中心点不象平均值那么容易被极端数壮，其原因是中心点不象平均值那么容易被极端数据影响据影响 nPAM对于小数据集工作得很好，但不能很好地用于对于小数据集工作得很好，但不能很好地用于大数

23、据集大数据集 n每次迭代每次迭代O(k(n-k)2)k-平均平均：O(tkn)其中其中，n 是数据对象数目，是数据对象数目，k 是聚类数是聚类数基于抽样的方法：基于抽样的方法：CLARA(Clustering LARge Applications)k-中心点聚类方法中心点聚类方法(续续)27第第10章：聚类分析：基本概念和方法章：聚类分析：基本概念和方法n 聚类分析聚类分析n 划分方法划分方法n 层次方法层次方法n 基于密度的方法基于密度的方法n 基于网格的方法基于网格的方法n 聚类评估聚类评估n 小结小结层次方法层次方法n层次的聚类方法将数据对象组成一棵聚类的树层次的聚类方法将数据对象组成一

24、棵聚类的树n根据层次分解是自底向上根据层次分解是自底向上,还是自顶向下形成还是自顶向下形成,层次层次的聚类方法可以进一步分为的聚类方法可以进一步分为凝聚的凝聚的(agglomerative)和和分裂的分裂的(divisive)层次聚类层次聚类 n使用距离矩阵作为聚类标准使用距离矩阵作为聚类标准.该方法不需要输入聚该方法不需要输入聚类数目类数目 k,但需要终止条件但需要终止条件n凝聚的凝聚的(agglomerative)和分裂的和分裂的(divisive)层次聚类图示层次聚类图示Step 0Step 1Step 2Step 3Step 4bdceaa bd ec d ea b c d eStep

25、 4Step 3Step 2Step 1Step 0agglomerative(AGNES)divisive(DIANA)层次方法（续）层次方法（续）12141317181516 1 2 6 8 7 3 4 5 91011192023242122252627161820222426283032节点间聚类水平目 的 节 点 编 号层次方法（续）层次方法（续）Matlab层次聚类结果AGNES(Agglomerative Nesting)n由由 Kaufmann和和Rousseeuw提出提出(1990)n已在一些统计分析软件包中实现已在一些统计分析软件包中实现.如如 Splusn使用单链接使用单链

26、接(Single-Link)方法和相异度矩阵方法和相异度矩阵 n合并具有最小相异度的节点合并具有最小相异度的节点n以非递减的方式继续以非递减的方式继续n最终所有的节点属于同一个簇最终所有的节点属于同一个簇DIANA(Divisive Analysis)n由由 Kaufmann和和Rousseeuw提出提出(1990)n已在一些统计分析软件包中实现已在一些统计分析软件包中实现.如如 Splusn是是 AGNES的逆的逆n最终每个节点自己形成一个簇最终每个节点自己形成一个簇层次方法层次方法(续续)n四个广泛采用的簇间距离度量方法四个广泛采用的簇间距离度量方法 n最小距离：最小距离：dmin(Ci,

27、Cj)=min pCi,pCj|p-p|n最大距离：最大距离：dmax(Ci,Cj)=max pCi,pCj|p-p|n平均值的距离：平均值的距离：dmean(Ci,Cj)=|mi-mj|n平均距离：平均距离：davg(Ci,Cj)=pCi pCj|p-p|/ni nj其中：其中：|p-p|是两个对象是两个对象p和和p之间的距离；之间的距离；mi是簇是簇Ci 的平的平均值，均值，ni是簇是簇Ci中对象的数目中对象的数目 层次方法层次方法(续续)n层次聚类的主要缺点层次聚类的主要缺点n不具有很好的可伸缩性不具有很好的可伸缩性:时间复杂性至少是时间复杂性至少是 O(n2),其其中中 n 对象总数对

28、象总数n合并或分裂的决定需要检查和估算大量的对象或簇合并或分裂的决定需要检查和估算大量的对象或簇 n不能撤消已做的处理不能撤消已做的处理,聚类之间不能交换对象聚类之间不能交换对象.如果如果某一步没有很好地选择合并或分裂的决定某一步没有很好地选择合并或分裂的决定,可能会导可能会导致低质量的聚类结果致低质量的聚类结果 n改进层次方法的聚类质量的方法改进层次方法的聚类质量的方法:将层次聚类和其将层次聚类和其他的聚类技术进行集成，形成多阶段聚类他的聚类技术进行集成，形成多阶段聚类 nBIRCH(1996):使用使用 CF-tree对对象进行层次划分对对象进行层次划分,然后然后采用其他的聚类算法对聚类结

29、果进行求精采用其他的聚类算法对聚类结果进行求精 nROCK1999：基于簇间的互联性进行合并：基于簇间的互联性进行合并nCHAMELEON(1999)：使用动态模型进行层次聚类使用动态模型进行层次聚类nCURE(1998)：采用固定数目的代表对象表示每个簇，：采用固定数目的代表对象表示每个簇，依据一个指定的收缩因子向着聚类中心对它们进行收缩依据一个指定的收缩因子向着聚类中心对它们进行收缩层次方法层次方法(续续)BIRCH(1996)nBirch(Balanced Iterative Reducing and Clustering using Hierarchies):利用层次方法的平利用层次方

30、法的平衡迭代归约和聚类衡迭代归约和聚类n两个重要概念两个重要概念n聚类特征聚类特征(Clustering Feature,CF)n聚类特征树聚类特征树(Clustering Feature Tree,CF树树)n聚类特征聚类特征n聚类特征聚类特征(CF)是一个三元组，是一个三元组，给出给出对象子类的信息对象子类的信息的的汇总汇总描述描述 n设某个子类中有设某个子类中有N个个d维的点或对象维的点或对象oI，则该子类的则该子类的CF定义如下定义如下 CF=(N,LS,SS)聚类特征聚类特征Clustering Feature：CF=(N,LS,SS)N:数据点数目数据点数目LS:Ni=1XiSS:

31、Ni=1Xi2CF=(5,(16,30),(54,190)(3,4)(2,6)(4,5)(4,7)(3,8)可加性（类合并）：可加性（类合并）：CF=CF1+CF2=(N1+N2,LS1+LS2,SS1+SS1)BIRCH的的CF树树n聚类特征聚类特征 n从统计学的观点来看，聚类特征是子聚类的从统计学的观点来看，聚类特征是子聚类的0阶阶,1阶和阶和 2阶矩阶矩(moments)n记录了计算聚类和有效利用存储的关键度量记录了计算聚类和有效利用存储的关键度量,并有效地并有效地利用了存储，因为它汇总了关于子类的信息，而利用了存储，因为它汇总了关于子类的信息，而不是不是存存储所有的对象储所有的对象 C

32、F 树是高度平衡的树，它存储了层次聚类的树是高度平衡的树，它存储了层次聚类的聚类特征聚类特征 n树中的非叶节点有后代或树中的非叶节点有后代或“孩子孩子”n非叶节点存储了其孩子的非叶节点存储了其孩子的CF的总和，即汇总了关于其的总和，即汇总了关于其孩子的聚类信息孩子的聚类信息 nCF树有两个参数树有两个参数影响影响CF树的大小树的大小n分支因子分支因子B:定义非树叶节点的孩子的最大个数定义非树叶节点的孩子的最大个数n阈值阈值T:定定义义存储在树的叶子节点中的子类的最大直径存储在树的叶子节点中的子类的最大直径 BIRCH的的CF树树CF1child1CF3child3CF2child2CF6chi

33、ld6CF1child1CF3child3CF2child2CF5child5CF1CF2CF6prevnextCF1CF2CF4prevnextB=7T=6RootNon-leaf nodeLeaf nodeLeaf nodeCF树树BIRCH(续续)nBIRCH增量地构造一棵增量地构造一棵 CF 树树(Clustering Feature Tree)，CF树是一个层次数据结构，用于多阶段聚类树是一个层次数据结构，用于多阶段聚类n阶段阶段 1:扫描扫描 DB，建立一棵初始的存放在内存的，建立一棵初始的存放在内存的 CF树（树（数据的多层压缩，试图保留数据内在的聚类结构）数据的多层压缩，试图保

34、留数据内在的聚类结构）n阶段阶段 2:使用某种聚类算法对使用某种聚类算法对CF树的叶节点进行聚类树的叶节点进行聚类 BIRCH(续续)n在阶段一：随着对象被插入，在阶段一：随着对象被插入，CF树被动态地构造树被动态地构造n一个对象被插入到最近的叶子条目（子聚类）一个对象被插入到最近的叶子条目（子聚类）n如果在插入后存储在叶子节点中的子类的如果在插入后存储在叶子节点中的子类的直径大于阀值直径大于阀值,那么该叶子节点（可能还有其他节点）被分裂那么该叶子节点（可能还有其他节点）被分裂n新对象插入后，关于该对象的信息向着树根传递新对象插入后，关于该对象的信息向着树根传递n通过修改阀值，通过修改阀值，C

35、F树的大小可以改变树的大小可以改变 n树重建：从旧树的叶子节点建造一个新树，重建树的过树重建：从旧树的叶子节点建造一个新树，重建树的过程不需要重读所有的对象程不需要重读所有的对象建树只需读一次数据建树只需读一次数据 n阶段二：采用任何聚类算法对叶节点进行聚类，例阶段二：采用任何聚类算法对叶节点进行聚类，例如典型的划分方法如典型的划分方法BIRCH(续续)nBIRCH的性能的性能n支持增量聚类支持增量聚类n线性可伸缩性线性可伸缩性:计算复杂性计算复杂性O(n),单遍扫描单遍扫描,附加的扫描附加的扫描可以改善聚类质量可以改善聚类质量n较好的聚类质量较好的聚类质量n缺点缺点n只能处理数值数据只能处理

36、数值数据n对数据的输入次序敏感对数据的输入次序敏感nCf树结点不总是对应于树结点不总是对应于用户考虑的用户考虑的自然簇自然簇(参数参数B和和T)n簇非球形时效果不好簇非球形时效果不好(使用半径使用半径/直径控制簇边界直径控制簇边界)CHAMELEONnCHAMELEON:一个利用动态模型的层次聚类算法一个利用动态模型的层次聚类算法(Hierarchical clustering using dynamic modeling)由由G.Karypis,E.H.Han,and V.Kumar99 提出提出nCHAMELEON基于动态模型度量相似性基于动态模型度量相似性n如果两个簇间的互连性和近似度与

37、簇内部对象间的互如果两个簇间的互连性和近似度与簇内部对象间的互连性和近似度高度相关连性和近似度高度相关,则合并这两个簇则合并这两个簇 n两阶段算法两阶段算法n使用图划分算法使用图划分算法:将数据对象聚为大量相对较小的子类将数据对象聚为大量相对较小的子类n使用凝聚的层次聚类算法：通过反复地合并子类来找使用凝聚的层次聚类算法：通过反复地合并子类来找到真正的结果簇到真正的结果簇n既考虑互连性既考虑互连性,又考虑簇间的近似度又考虑簇间的近似度,特别是簇内部的特征特别是簇内部的特征,来确定最相似的子类来确定最相似的子类.n这样这样,它不依赖于静态的用户提供的模型它不依赖于静态的用户提供的模型,能够自动地

38、适应能够自动地适应被合并的簇的内部特征被合并的簇的内部特征 n割边最小化割边最小化簇簇C划分为两个子簇划分为两个子簇Ci和和Cj时需要割断的时需要割断的边的加权和最小。边的加权和最小。n割边用割边用ECCi，Cj表示，评估表示，评估Ci和和Cj的簇间的的簇间的绝对互联性绝对互联性。CHAMELEON（续）（续）构造稀疏图构造稀疏图划分图划分图合并划分合并划分最终的簇最终的簇Data SetK-最近邻居图最近邻居图CHAMELEON（续）（续）nk-最近邻图最近邻图Gk:图中的每个点代表一个数据对象图中的每个点代表一个数据对象,如果一个如果一个对象是另一个对象的对象是另一个对象的k个最类似的对象

39、之一个最类似的对象之一,在这两个点之在这两个点之间存在一条边间存在一条边nk-最近邻图最近邻图Gk动态地捕捉邻域的概念：一个对象的邻域半动态地捕捉邻域的概念：一个对象的邻域半径由对象所在区域的密度所决定径由对象所在区域的密度所决定n在一个密集区域在一个密集区域,邻域的定义范围相对狭窄邻域的定义范围相对狭窄;在一个稀疏在一个稀疏区域区域,它的定义范围相对较宽它的定义范围相对较宽 n区域的密度作为边的权重被记录下来区域的密度作为边的权重被记录下来n一个密集区域的边趋向于比稀疏区域的边有更大的权重一个密集区域的边趋向于比稀疏区域的边有更大的权重 CHAMELEON（续）（续）nChameleon通过

40、两个簇的相对通过两个簇的相对互连性互连性RI(Ci,Cj)和相对和相对接近度接近度RC(Ci,Cj)来决定簇间的相似度来决定簇间的相似度 nRI(Ci,Cj)定义为定义为Ci和和Cj之间的绝对互联性关于两个簇的之间的绝对互联性关于两个簇的内部互连性的规范化内部互连性的规范化 其中其中,ECCi，Cj是包含是包含Ci和和Cj的簇分裂为的簇分裂为Ci和和Cj的割边的割边,ECCi（或或ECCj）是它的最小截断等分线的大小（即将图划分为是它的最小截断等分线的大小（即将图划分为两个大致相等的部分需要切断的边的加权和）两个大致相等的部分需要切断的边的加权和）|)|(|21|),(,jijiCCCCjiE

41、CECECCCRICHAMELEON（续）（续）nRC(Ci,Cj)定义为定义为Ci和和Cj之间的绝对接近度关于两个簇的内之间的绝对接近度关于两个簇的内部接近度的规范化部接近度的规范化 其中其中,是是连接连接Ci和和Cj顶点的边的平均权重顶点的边的平均权重 是是Ci的最小二等分的边的平均权重的最小二等分的边的平均权重 jCiCjCiCECjijECjiiECjiSCCCSCCCSCCRC|),(,),(jiCCECSiCECSCHAMELEON（续）（续）50CHAMELEON（续）（续）概率层次聚类概率层次聚类n算法的层次聚类方法缺点算法的层次聚类方法缺点n为层次聚类选择一种好的距离量度常常

42、是困难的为层次聚类选择一种好的距离量度常常是困难的 n为了使用算法的方法，数据对象不能有缺失的属性值为了使用算法的方法，数据对象不能有缺失的属性值n大部分算法的层次聚类方法都是启发式的，因此结果聚大部分算法的层次聚类方法都是启发式的，因此结果聚类层次结构的优化目标不清晰类层次结构的优化目标不清晰n概率层次聚类概率层次聚类n利用概率模型表征聚类之间的距离利用概率模型表征聚类之间的距离51生成模型生成模型n给定给定1维数据点集维数据点集X=x1,xn，假设其服从高斯分布，假设其服从高斯分布n那么那么xi X被该模型生成的概率是：被该模型生成的概率是：nX被该模型生成的似然为：被该模型生成的似然为：

43、n学习生成模型的任务是：找出使得似然最大的学习生成模型的任务是：找出使得似然最大的和和252概率层次聚类算法概率层次聚类算法n若一个对象集和被分成若一个对象集和被分成m个聚类个聚类C1,.,Cm,那么其聚类质量那么其聚类质量可用下式度量可用下式度量其中其中P()是针对某一类的最大似然是针对某一类的最大似然n若合并其中的两类若合并其中的两类Cj1和和Cj2成为成为Cj1Cj2,那么其聚类质量变那么其聚类质量变化为化为n定义定义C1和和C2两类之间的距离两类之间的距离5354第第10章：聚类分析：基本概念和方法章：聚类分析：基本概念和方法n 聚类分析聚类分析n 划分方法划分方法n 层次方法层次方法

44、n 基于密度的方法基于密度的方法n 基于网格的方法基于网格的方法n 聚类评估聚类评估n 小结小结基于密度的方法基于密度的方法n基于密度聚类基于密度聚类(Density-Based Clustering)n主要特点主要特点:n发现任意形状的聚类发现任意形状的聚类n处理噪音处理噪音n一遍扫描一遍扫描n需要密度参数作为终止条件需要密度参数作为终止条件n一些有趣的研究一些有趣的研究:nDBSCAN:Ester,et al.(KDD96)nOPTICS:Ankerst,et al(SIGMOD99).nDENCLUE:Hinneburg&D.Keim (KDD98)nCLIQUE:Agrawal,et

45、al.(SIGMOD98)密度概念密度概念n-邻域：给定对象半径邻域：给定对象半径 内的领域内的领域n核心对象（核心对象（core object）：一个对象的）：一个对象的 邻域至少包含最小邻域至少包含最小数目个对象（数目个对象（MinPts）n直接直接密度可达的（密度可达的（Directly density reachable,DDR）：给定）：给定对象集合对象集合D,如果如果p是在是在q的的 邻域内邻域内,而而q是核心对象是核心对象,我们我们说对象说对象p是从对象是从对象q直接密度可达的直接密度可达的n密度可达的密度可达的(density reachable):存在一个从存在一个从p到到q

46、的的DDR对对象链象链n密度相连的密度相连的(density-connected):如果对象集合如果对象集合D中存在一中存在一个对象个对象o，使得对象使得对象p和和q是从是从o关于关于 和和MinPts密度可达的，密度可达的，那么对象那么对象p和和q是关于是关于 和和MinPts密度相连的密度相连的基于密度的聚类基于密度的聚类:背景背景In两个参数两个参数:n :邻域的最大半径邻域的最大半径nMinPts:在在 -邻域中的最少点数邻域中的最少点数 nN(p):q belongs to D|dist(p,q)=MinPts pqMinPts=5 =1 cm基于密度的聚类基于密度的聚类:背景背景I

47、In密度可达密度可达:n点点 p 关于关于,MinPts 是从是从 q密度可密度可达的达的,如果存在一个节点链如果存在一个节点链 p1,pn,p1=q,pn=p 使得使得 pi+1 是从是从pi直直接密度可达的接密度可达的n密度相连的密度相连的:n点点p关于关于,MinPts与点与点q是密度相是密度相连的连的,如果存在点如果存在点o使得使得,p和和q都是都是关于关于,MinPts 是从是从o密度可达的密度可达的pqopqp1例子例子nMinPts=3nq是从是从p密度可达；密度可达；p不是从不是从q密度可达（密度可达（q非核心）非核心）ns和和r从从o密度可达；密度可达；o从从r密度可达；密度

48、可达；nr,s,o密度相连密度相连DBSCAN(1996)nDBSCAN(Density Based Spatial Clustering of Applications with Noise)一个基于密度的聚类算法一个基于密度的聚类算法n可以在带有可以在带有“噪音噪音”的空间数据库中发现任意形状的聚类的空间数据库中发现任意形状的聚类 CoreBorderOutlier =1cmMinPts=5DBSCAN(续续)n算法算法n任意选取一个点任意选取一个点 pn得到所有从得到所有从p 关于关于 和和 MinPts密度可达的点密度可达的点.n如果如果p是一个核心点是一个核心点,则找到一个聚类则找到

49、一个聚类.n如果如果p是一个边界点是一个边界点,没有从没有从p密度可达的点密度可达的点,DBSCAN 将将访问数据库中的下一个点访问数据库中的下一个点.n继续这一过程继续这一过程,直到数据库中的所有点都被处理直到数据库中的所有点都被处理.nDBSCAN的复杂度的复杂度n采用空间索引采用空间索引,复杂度为复杂度为O(nlogn),否则为否则为O(n2)nDBSCAN的缺点的缺点:n对用户定义的参数是敏感的对用户定义的参数是敏感的,参数难以确定参数难以确定(特别是对于特别是对于高维数据高维数据),设置的细微不同可能导致差别很大的聚类设置的细微不同可能导致差别很大的聚类.（数据倾斜分布）全局密度参数

50、不能刻画内在的聚类结构（数据倾斜分布）全局密度参数不能刻画内在的聚类结构OPTICS(1999)nOPTICS(Ordering Points To Identify the Clustering Structure)nAnkerst,Breunig,Kriegel,和和 Sander 提出提出(SIGMOD99)n考虑考虑DBSCAN,根据给定的根据给定的 和和MinPts聚类对象聚类对象,通常参通常参数选择较为困难数选择较为困难n现实的高维数据集常常具有非常倾斜的分布现实的高维数据集常常具有非常倾斜的分布,全局密度参全局密度参数不能很好的刻画其内在聚类结构数不能很好的刻画其内在聚类结构 n