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

《CHAPTER10-聚类分析：基本概念和方法ppt课件.ppt》由会员分享，可在线阅读，更多相关《CHAPTER10-聚类分析：基本概念和方法ppt课件.ppt（100页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确费高雷费高雷通信与信息工程学院通信与信息工程学院2015年春季年春季第第1010章章 聚类分析：基聚类分析：基本概念和方法本概念和方法在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第第10章：聚类分析：基本概念和方法章：聚类分析：基本概念和方法n聚类分析聚类分析n划分方法划分方法n层次方法层次方法n基于密度的方法基于密度的方法n基于网格的方法基于网格的方法n聚类评估聚类评估n小结小结2在整堂课的教学中，刘教师总是让学生带着问题

2、来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确什么是聚类分析什么是聚类分析?n聚类聚类:数据对象的集合数据对象的集合/簇簇(cluster)n同一簇中的对象彼此相似同一簇中的对象彼此相似n不同簇中的对象彼此相异不同簇中的对象彼此相异n聚类分析聚类分析n将数据对象分组成为多个类或簇将数据对象分组成为多个类或簇n聚类是聚类是无监督的无监督的分类：没有预先定义的类分类：没有预先定义的类n典型应用典型应用n作为洞察数据内部分布的独一无二的工具作为洞察数据内部分布的独一无二的工具 n作为其它算法的预处理步骤作为其它算法的预处理步骤在整堂课的教学中，刘教师总是让学生带着问题来学习，而问

3、题的设置具有一定的梯度，由浅入深，所提出的问题也很明确聚类的一般应用聚类的一般应用 n模式识别模式识别n空间数据分析空间数据分析 n聚类产生聚类产生GIS(地理信息系统地理信息系统)的专题地图的专题地图thematic maps n在空间数据挖掘中检测空间聚类并解释它们在空间数据挖掘中检测空间聚类并解释它们n图象处理图象处理n经济科学经济科学(特别是市场研究特别是市场研究)nWWWn文本分类文本分类nWeb日志数据聚类，发现类似访问模式群日志数据聚类，发现类似访问模式群在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确聚类应用的例子聚类

4、应用的例子n市场营销市场营销:帮帮助助市市场场营营销销者者发发现现他他们们的的基基本本顾顾客客的的不不同同组组群群，然然后后利利用用这这一一知知识识制定有针对性的营销计划制定有针对性的营销计划n国土利用国土利用在地球观测数据库中识别类似的国土使用区域在地球观测数据库中识别类似的国土使用区域n保险保险 对汽车保险持有者的分组对汽车保险持有者的分组 n城市规划城市规划根据房子的类型，价值，和地理位置对一个城市中房屋的分组根据房子的类型，价值，和地理位置对一个城市中房屋的分组 n地震研究地震研究应当将观测到的地震震中沿大陆板块断裂进行聚类应当将观测到的地震震中沿大陆板块断裂进行聚类在整堂课的教学中，

5、刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确聚类分析的主要步骤聚类分析的主要步骤n特征选择特征选择n选择与任务密切相关的信息n尽可能减少信息冗余n相似度评价相似度评价n两个特征向量的相似性n聚类的评价准则聚类的评价准则n通过代价函数或某些规则n聚类算法聚类算法nk-均值、极大似然、n结果验证结果验证n验证聚类结果的有效性n结果解释结果解释n根据实际应用解释聚类结果6在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确什么是好的聚类方法什么是好的聚类方法?n一个好的聚类方法应当产生高质量的聚类一

6、个好的聚类方法应当产生高质量的聚类n类内相似性高类内相似性高n类间相似性低类间相似性低n聚聚类类结结果果的的质质量量依依赖赖于于方方法法所所使使用用的的相相似似性性度度量量和和它的实现它的实现.n聚聚类类方方法法的的质质量量也也用用它它发发现现某某些些或或全全部部隐隐藏藏的的模模式式的能力来度量的能力来度量在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确数据挖掘对聚类的要求数据挖掘对聚类的要求 n可伸缩性可伸缩性n有的算法当数据对象少于有的算法当数据对象少于200时处理很好时处理很好,但对大量数但对大量数据对象偏差较大据对象偏差较大n

7、大型数据库包含数百万个对象大型数据库包含数百万个对象n处理不同属性类型的能力处理不同属性类型的能力n许多算法专门用于数值类型的数据许多算法专门用于数值类型的数据n实际应用涉及不同数据类型（实际应用涉及不同数据类型（数值和分类数据混合）数值和分类数据混合）n发现任意形状的聚类发现任意形状的聚类n基于距离的聚类趋向于发现具有相近尺度和密度的球基于距离的聚类趋向于发现具有相近尺度和密度的球状簇状簇 n一个簇可能是任意形状的一个簇可能是任意形状的在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确数据挖掘对聚类的要求数据挖掘对聚类的要求(续续)n

8、用于决定输入参数的领域知识最小化用于决定输入参数的领域知识最小化n许许多多聚聚类类算算法法要要求求用用户户输输入入一一定定的的参参数数，如如希希望望产产生生的的簇的数目。簇的数目。n参数难以确定，增加用户负担，使聚类质量难以控制参数难以确定，增加用户负担，使聚类质量难以控制n处理噪声数据和孤立点的能力处理噪声数据和孤立点的能力 n一一些些聚聚类类算算法法对对于于噪噪音音数数据据敏敏感感,可可能能导导致致低低质质量量的的聚聚类结果类结果n现现实实世世界界中中的的数数据据库库大大都都包包含含了了孤孤立立点点,空空缺缺,或或者者错错误的数据误的数据 n对于输入记录的顺序不敏感对于输入记录的顺序不敏感

9、 n一一些些聚聚类类算算法法对对于于输输入入数数据据的的顺顺序序是是敏敏感感的的,以以不不同同的的次序输入会导致不同的聚类次序输入会导致不同的聚类在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确数据挖掘对聚类的要求数据挖掘对聚类的要求(续续)n高维性（高维性（high dimensionality）n许多聚类算法擅长处理低维的数据许多聚类算法擅长处理低维的数据,可能只涉及两到三维可能只涉及两到三维 n数据库或者数据仓库可能包含若干维或者属性数据库或者数据仓库可能包含若干维或者属性,数据可能数据可能非常稀疏非常稀疏,而且高度偏斜而且高度

10、偏斜 n整合用户指定的约束整合用户指定的约束n现实世界的应用可能需要在各种约束条件下进行聚类现实世界的应用可能需要在各种约束条件下进行聚类 n要找到既满足要找到既满足特定的约束特定的约束,又具有良好聚类特性的数据分又具有良好聚类特性的数据分组是一项具有挑战性的任务组是一项具有挑战性的任务 n可解释性和可用性可解释性和可用性 n用户希望聚类结果是可解释的用户希望聚类结果是可解释的,可理解的可理解的,和可用的和可用的 n聚类可能需要和特定的语义解释和应用相联系聚类可能需要和特定的语义解释和应用相联系 在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问

11、题也很明确聚类分析的方法聚类分析的方法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 criterionnTypical methods:Dian

12、a,Agnes,BIRCH,CAMELEONn基于密度的方法基于密度的方法:nBased on connectivity and density functionsnTypical methods:DBSACN,OPTICS,DenCluen基于网格的方法基于网格的方法:nbased on a multiple-level granularity structurenTypical methods:STING,WaveCluster,CLIQUE11在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确聚类分析的方法聚类分析的方法 n基于模

13、型的方法基于模型的方法:nA model is 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

14、application-specific constraintsnTypical methods:COD(obstacles),constrained clusteringn基于链接的方法基于链接的方法:nObjects are often linked together in various waysnMassive links can be used to cluster objects:SimRank,LinkClus12在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确13第第10章：聚类分析：基本概念和方法章：聚类分析：基本概

15、念和方法n聚类分析聚类分析n划分方法划分方法n层次方法层次方法n基于密度的方法基于密度的方法n基于网格的方法基于网格的方法n聚类评估聚类评估n小结小结在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确划分方法划分方法n划划分分方方法法:构构造造n个个对对象象数数据据库库D的的划划分分,将将其其划划分分成成k个个聚聚类类n给定给定 k,找找k 个个clusters 对于选定的划分标准它是最优的对于选定的划分标准它是最优的n全局最优全局最优(Global optimal):枚举所有的划分枚举所有的划分n启启发发式式方方法法(Heuristi

16、c methods):k-平平均均(k-means)和和k-中心点中心点(k-medoids)算法算法nk-平平均均(MacQueen67):每每个个簇簇用用簇簇的的重重心心(簇簇的的平平均均值值)表示表示nk-中中心心点点或或PAM(Partition around medoids)(Kaufman&Rousseeuw87):每每个个簇簇用用接接近近聚聚类类中中心心的的一一个个对对象象来来表表示示 在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确k-平均聚类算法平均聚类算法 n算法：算法：k-平均平均(1)任意选择任意选择k个对象作

17、为初始的簇中心；个对象作为初始的簇中心；(2)repeat(3)根据簇中对象的平均值根据簇中对象的平均值,将每个对象将每个对象(重新重新)赋给最类似的簇；赋给最类似的簇；(4)更新簇的平均值更新簇的平均值,即重新计算每个簇中对象的平均值；即重新计算每个簇中对象的平均值；(5)until 不再发生变化不再发生变化 n通常通常,采用平方误差准则作为收敛函数采用平方误差准则作为收敛函数,其定义如下其定义如下 其中其中,mi是簇是簇Ci的平均值的平均值该准则试图使生成的结果簇尽可能紧凑该准则试图使生成的结果簇尽可能紧凑,独立独立在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯

18、度，由浅入深，所提出的问题也很明确k-平均聚类算法平均聚类算法(续续)n例例012345678910012345678910012345678910012345678910K=2任任意意选选择择 K个个对对象象作作为初始聚类中心为初始聚类中心将每个将每个对象赋对象赋给最相给最相似中心似中心更新簇更新簇平均值平均值重新赋值重新赋值更新簇更新簇平均值平均值重新赋值重新赋值在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确k-平均聚类算法平均聚类算法(续续)n优点优点:相对有效性相对有效性:O(tkn),其中其中，n是对象数目，是对象数目，k

19、是簇数目，是簇数目，t 是迭代次数是迭代次数;通常：通常：k，t 1,2,3 8,9,10,25 1,2,3,8 9,10,25nk-中中心心点点(k-Medoids):不不采采用用簇簇中中对对象象的的平平均均值值作作为为参参照照点点,而而是是选选用用簇簇中中位位置置最最中中心心的的对对象象,即即中中心心点点(medoid)作为参照点作为参照点012345678910012345678910012345678910012345678910在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确k-中心点聚类方法中心点聚类方法(续续)n找聚类中

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

21、an,1994):随机选样随机选样在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确n算法算法:k-中心点中心点(1)随机选择随机选择k个对象作为初始的代表对象；个对象作为初始的代表对象；(2)repeat(3)指派每个剩余的对象给离它最近的代表对象所代表的簇；指派每个剩余的对象给离它最近的代表对象所代表的簇；(4)随意地选择一个非代表对象随意地选择一个非代表对象Orandom；(5)计算用计算用Orandom代替代替Oj的总代价的总代价S；(6)若若S0，用用Orandom替换替换Oj，形成新的形成新的k个代表对象的集合；个代表对象的

22、集合；(7)until 不发生变化不发生变化k-中心点聚类方法中心点聚类方法(续续)O1O2O3。Oj。OkOrandom在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确Total Cost=20012345678910012345678910k=2任任意意选择 k个个数数据据对象象作作为初初始始类中心点中心点将将每每个个剩余的剩余的数数据据对象安排象安排对最近最近的的类随随机机选择一一个个非非类中中心心数数据据对象象 Oramdom计算交算交换的代价的代价012345678910012345678910Total Cost=26若若

23、聚聚类质量量上上升升，交交换O与与 Oramdom.执行循环直执行循环直至类不在发至类不在发生变化生变化012345678910012345678910k-中心点聚类方法中心点聚类方法(续续)在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确k-中心点聚类方法中心点聚类方法(续续)n为为了了判判定定一一个个非非代代表表对对象象Orandom是是否否是是当当前前一一个个代代表表对对象象Oj的好的替代，对于每一个非代表对象，考虑下面四种情况：的好的替代，对于每一个非代表对象，考虑下面四种情况：n第第一一种种情情况况：p当当前前隶隶属属于于代

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

25、代替替，且且p离离Orandom最近，那么最近，那么p被重新分配给被重新分配给Orandom 在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确 1.重新分配给重新分配给Oi 2.重新分配给重新分配给Orandom 3.不发生变化不发生变化 4.重新分配给重新分配给Orandom 数据对象数据对象+簇中心簇中心 替代前替代前 替代后替代后k-中心点聚类代价函数的四种情况中心点聚类代价函数的四种情况+OrandomOiOjp+OrandomOiOjp+OrandomOiOjp+OrandomOiOjpk-中心点聚类方法中心点聚类方法(续续

26、)在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确n当存在噪音和孤立点时，当存在噪音和孤立点时，PAM 比比 k-平均方法更健平均方法更健壮，其原因是中心点不象平均值那么容易被极端数壮，其原因是中心点不象平均值那么容易被极端数据影响据影响 nPAM对于小数据集工作得很好，但不能很好地用于对于小数据集工作得很好，但不能很好地用于大数据集大数据集 n每次迭代每次迭代O(k(n-k)2)k-平均平均：O(tkn)其中其中，n 是数据对象数目，是数据对象数目，k 是聚类数是聚类数基于抽样的方法：基于抽样的方法：CLARA(Clustering

27、 LARge Applications)k-中心点聚类方法中心点聚类方法(续续)在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确26第第10章：聚类分析：基本概念和方法章：聚类分析：基本概念和方法n聚类分析聚类分析n划分方法划分方法n层次方法层次方法n基于密度的方法基于密度的方法n基于网格的方法基于网格的方法n聚类评估聚类评估n小结小结在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确层次方法层次方法n层次的聚类方法将数据对象组成一棵聚类的树层次的聚类方法将数据对象组成一棵聚类

28、的树n根根据据层层次次分分解解是是自自底底向向上上,还还是是自自顶顶向向下下形形成成,层层次次 的的 聚聚 类类 方方 法法 可可 以以 进进 一一 步步 分分 为为 凝凝 聚聚 的的(agglomerative)和和分裂的分裂的(divisive)层次聚类层次聚类 n使使用用距距离离矩矩阵阵作作为为聚聚类类标标准准.该该方方法法不不需需要要输输入入聚聚类数目类数目 k,但需要终止条件但需要终止条件在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确n凝聚的凝聚的(agglomerative)和分裂的和分裂的(divisive)层次聚类层

29、次聚类图示图示Step 0Step 1Step 2Step 3Step 4bdceaa bd ec d ea b c d eStep 4Step 3Step 2Step 1Step 0agglomerative(AGNES)divisive(DIANA)层次方法（续）层次方法（续）在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确AGNES(Agglomerative Nesting)n由由 Kaufmann和和Rousseeuw提出提出(1990)n已在一些统计分析软件包中实现已在一些统计分析软件包中实现.如如 Splusn使用单链接

30、使用单链接(Single-Link)方法和相异度矩阵方法和相异度矩阵 n合并具有最小相异度的节点合并具有最小相异度的节点n以非递减的方式继续以非递减的方式继续n最终所有的节点属于同一个簇最终所有的节点属于同一个簇在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确DIANA(Divisive Analysis)n由由 Kaufmann和和Rousseeuw提出提出(1990)n已在一些统计分析软件包中实现已在一些统计分析软件包中实现.如如 Splusn是是 AGNES的逆的逆n最终每个节点自己形成一个簇最终每个节点自己形成一个簇在整堂课的

31、教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确层次方法层次方法(续续)n四个广泛采用的簇间距离度量方法四个广泛采用的簇间距离度量方法 n最小距离：最小距离：dmin(Ci,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 的平的平均值，

32、均值，ni是簇是簇Ci中对象的数目中对象的数目 在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确层次方法层次方法(续续)n层次聚类的主要缺点层次聚类的主要缺点n不不具具有有很很好好的的可可伸伸缩缩性性:时时间间复复杂杂性性至至少少是是 O(n2),其中其中 n 对象总数对象总数n合并或分裂的决定需要检查和估算大量的对象或簇合并或分裂的决定需要检查和估算大量的对象或簇 n不不能能撤撤消消已已做做的的处处理理,聚聚类类之之间间不不能能交交换换对对象象.如如果果某某一一步步没没有有很很好好地地选选择择合合并并或或分分裂裂的的决决定定,可可能

33、能会会导导致低质量的聚类结果致低质量的聚类结果 在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确n改改进进层层次次方方法法的的聚聚类类质质量量的的方方法法:将将层层次次聚聚类类和和其其他的聚类技术进行集成，形成多阶段聚类他的聚类技术进行集成，形成多阶段聚类 nBIRCH(1996):使使用用 CF-tree对对对对象象进进行行层层次次划划分分,然然后后采用其他的聚类算法对聚类结果进行求精采用其他的聚类算法对聚类结果进行求精 nROCK1999：基于簇间的互联性进行合并：基于簇间的互联性进行合并nCHAMELEON(1999)：使用动态

34、模型进行层次聚类使用动态模型进行层次聚类nCURE(1998)：采采用用固固定定数数目目的的代代表表对对象象表表示示每每个个簇簇，依据一个指定的收缩因子向着聚类中心对它们进行收缩依据一个指定的收缩因子向着聚类中心对它们进行收缩层次方法层次方法(续续)在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确BIRCH(1996)nBirch(Balanced Iterative Reducing and Clustering using Hierarchies):利利用用层层次次方方法法的的平平衡迭代归约和聚类衡迭代归约和聚类n两个重要概念两个

35、重要概念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

36、)N:数据点数目数据点数目LS:Ni=1XiSS: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记记录录了了计计算算聚聚类类和和有有效效利利用用存存储储的的关

37、关键键度度量量,并并有有效效地地利利用用了了存存储储，因因为为它它汇汇总总了了关关于于子子类类的的信信息息，而而不不是是存存储所有的对象储所有的对象 在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确CF 树是高度平衡的树，它存储了层次聚类的树是高度平衡的树，它存储了层次聚类的聚类特征聚类特征 n树中的非叶节点有后代或树中的非叶节点有后代或“孩子孩子”n非非叶叶节节点点存存储储了了其其孩孩子子的的CF的的总总和和，即即汇汇总总了了关关于于其其孩孩子的聚类信息子的聚类信息 nCF树有两个参数树有两个参数影响影响CF树的大小树的大小n分支因

38、子分支因子B:定义非树叶节点的孩子的最大个数定义非树叶节点的孩子的最大个数n阈值阈值T:定定义存储在树的叶子节点中的子类的最大直径存储在树的叶子节点中的子类的最大直径 BIRCH的的CF树树在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确CF1child1CF3child3CF2child2CF6child6CF1child1CF3child3CF2child2CF5child5CF1CF2CF6prevnextCF1CF2CF4prevnextB=7T=6RootNon-leaf nodeLeaf nodeLeaf nodeCF树树

39、在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确BIRCH(续续)nBIRCH增增量量地地构构造造一一棵棵 CF 树树(Clustering Feature Tree)，CF树是一个层次数据结构，用于多阶段聚类树是一个层次数据结构，用于多阶段聚类n阶阶段段 1:扫扫描描 DB，建建立立一一棵棵初初始始的的存存放放在在内内存存的的 CF树树（数据的多层压缩，试图保留数据内在的聚类结构）（数据的多层压缩，试图保留数据内在的聚类结构）n阶段阶段 2:使用某种聚类算法对使用某种聚类算法对CF树的叶节点进行聚类树的叶节点进行聚类 在整堂课的教学

40、中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确BIRCH(续续)n在阶段一：随着对象被插入，在阶段一：随着对象被插入，CF树被动态地构造树被动态地构造n一个对象被插入到最近的叶子条目（子聚类）一个对象被插入到最近的叶子条目（子聚类）n如如果果在在插插入入后后存存储储在在叶叶子子节节点点中中的的子子类类的的直直径径大大于于阀阀值值,那么该叶子节点（可能还有其他节点）被分裂那么该叶子节点（可能还有其他节点）被分裂n新对象插入后，关于该对象的信息向着树根传递新对象插入后，关于该对象的信息向着树根传递n通过修改阀值，通过修改阀值，CF树的大小可以改变树的

41、大小可以改变 n树树重重建建：从从旧旧树树的的叶叶子子节节点点建建造造一一个个新新树树，重重建建树树的的过过程不需要重读所有的对象程不需要重读所有的对象建树只需读一次数据建树只需读一次数据 n阶阶段段二二：采采用用任任何何聚聚类类算算法法对对叶叶节节点点进进行行聚聚类类，例例如典型的划分方法如典型的划分方法在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确BIRCH(续续)nBIRCH的性能的性能n支持增量聚类支持增量聚类n线线性性可可伸伸缩缩性性:计计算算复复杂杂性性O(n),单单遍遍扫扫描描,附附加加的的扫扫描描可以改善聚类质量可以

42、改善聚类质量n较好的聚类质量较好的聚类质量n缺点缺点n只能处理数值数据只能处理数值数据n对数据的输入次序敏感对数据的输入次序敏感nCf树结点不总是对应于树结点不总是对应于用户考虑的用户考虑的自然簇自然簇(参数参数B和和T)n簇非球形时效果不好簇非球形时效果不好(使用半径使用半径/直径控制簇边界直径控制簇边界)在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确CHAMELEONnCHAMELEON:一一个个利利用用动动态态模模型型的的层层次次聚聚类类算算法法(Hierarchical clustering using dynamic mo

43、deling)由由G.Karypis,E.H.Han,and V.Kumar99 提出提出nCHAMELEON基于动态模型度量相似性基于动态模型度量相似性n如如果果两两个个簇簇间间的的互互连连性性和和近近似似度度与与簇簇内内部部对对象象间间的的互互连连性和近似度高度相关性和近似度高度相关,则合并这两个簇则合并这两个簇 n两阶段算法两阶段算法n使用图划分算法使用图划分算法:将数据对象聚为大量相对较小的子类将数据对象聚为大量相对较小的子类n使使用用凝凝聚聚的的层层次次聚聚类类算算法法：通通过过反反复复地地合合并并子子类类来来找找到到真正的结果簇真正的结果簇在整堂课的教学中，刘教师总是让学生带着问题

44、来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确n既既考考虑虑互互连连性性,又又考考虑虑簇簇间间的的近近似似度度,特特别别是是簇簇内内部部的的特特征征,来确定最相似的子类来确定最相似的子类.n这这样样,它它不不依依赖赖于于静静态态的的用用户户提提供供的的模模型型,能能够够自自动动地地适适应被合并的簇的内部特征应被合并的簇的内部特征 n割割边边最最小小化化簇簇C划划分分为为两两个个子子簇簇Ci和和Cj时时需需要要割割断断的的边的加权和最小。边的加权和最小。n割边用割边用ECCi，Cj表示，评估表示，评估Ci和和Cj的簇间的的簇间的绝对互联性绝对互联性。CHAMELEON（续）（

45、续）在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确构造稀疏图构造稀疏图划分图划分图合并划分合并划分最终的簇最终的簇Data SetK-最近邻居图最近邻居图CHAMELEON（续）（续）在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确nk-最最近近邻邻图图Gk:图图中中的的每每个个点点代代表表一一个个数数据据对对象象,如如果果一一个个对对象象是是另另一一个个对对象象的的k个个最最类类似似的的对对象象之之一一,在在这这两两个个点点之之间存在一条边间存在一条边nk-最最近近邻邻图

46、图Gk动动态态地地捕捕捉捉邻邻域域的的概概念念：一一个个对对象象的的邻邻域域半半径径由对象所在区域的密度所决定由对象所在区域的密度所决定n在在一一个个密密集集区区域域,邻邻域域的的定定义义范范围围相相对对狭狭窄窄;在在一一个个稀稀疏疏区域区域,它的定义范围相对较宽它的定义范围相对较宽 n区域的密度作为边的权重被记录下来区域的密度作为边的权重被记录下来n一个密集区域的边趋向于比稀疏区域的边有更大的权重一个密集区域的边趋向于比稀疏区域的边有更大的权重 CHAMELEON（续）（续）在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确nCham

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

48、堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确nRC(Ci,Cj)定定义义为为Ci和和Cj之之间间的的绝绝对对接接近近度度关关于于两两个个簇簇的的内内部接近度的规范化部接近度的规范化 其中其中,是是连接连接Ci和和Cj顶点的边的平均权重顶点的边的平均权重 是是Ci的最小二等分的边的平均权重的最小二等分的边的平均权重 CHAMELEON（续）（续）在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确48CHAMELEON（续）（续）在整堂课的教学中，刘教师总是让学生带着问题来学习，而

49、问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确概率层次聚类概率层次聚类n算法的层次聚类方法缺点算法的层次聚类方法缺点n为层次聚类选择一种好的距离量度常常是困难的为层次聚类选择一种好的距离量度常常是困难的 n为了使用算法的方法，数据对象不能有缺失的属性值为了使用算法的方法，数据对象不能有缺失的属性值n大大部部分分算算法法的的层层次次聚聚类类方方法法都都是是启启发发式式的的，因因此此结结果果聚聚类层次结构的优化目标不清晰类层次结构的优化目标不清晰n概率层次聚类概率层次聚类n利用概率模型表征聚类之间的距离利用概率模型表征聚类之间的距离49在整堂课的教学中，刘教师总是让学生带着问题来学习，而

50、问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确生成模型生成模型n给定给定1维数据点集维数据点集X=x1,xn，假设其服从高斯分布，假设其服从高斯分布n那么那么xi X被该模型生成的概率是：被该模型生成的概率是：nX被该模型生成的似然为：被该模型生成的似然为：n学习生成模型的任务是：找出使得似然最大的学习生成模型的任务是：找出使得似然最大的和和250在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确概率层次聚类算法概率层次聚类算法n若一个对象集和被分成若一个对象集和被分成m个聚类个聚类C1,.,Cm,那么其聚类质量那么其聚类质量