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

资源描述

《CHAPTER10聚类分析基本概念和方法ppt课件》由会员分享，可在线阅读，更多相关《CHAPTER10聚类分析基本概念和方法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时处理很好时处理很好, 但对大量数但对大量数据对象偏差较大据对

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

8、求(续续)n用于决定输入参数的领域知识最小化用于决定输入参数的领域知识最小化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 cri

12、terionnTypical 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, CLIQUE11在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一

13、定的梯度，由浅入深，所提出的问题也很明确聚类分析的方法聚类分析的方法 n基于模型的方法基于模型的方法: 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基于约束的方法基于约束的方法:

14、nClustering by considering user-specified or 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在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一

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

16、最优(Global optimal): 枚举所有的划分枚举所有的划分n启启发发式式方方法法(Heuristic methods): k-平平均均(k-means)和和k-中心点中心点(k-medoids)算法算法nk-平平均均(MacQueen67): 每每个个簇簇用用簇簇的的重重心心(簇簇的的平平均均值值) 表示表示nk-中中心心点点或或PAM (Partition around medoids) (Kaufman & Rousseeuw87): 每每个个簇簇用用接接近近聚聚类类中中心心的的一一个个对对象象来来表表示示在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的

17、梯度，由浅入深，所提出的问题也很明确k-平均聚类算法平均聚类算法 n算法：算法： k-平均平均(1) 任意选择任意选择k个对象作为初始的簇中心；个对象作为初始的簇中心；(2) repeat(3) 根据簇中对象的平均值根据簇中对象的平均值, 将每个对象将每个对象(重新重新)赋给最类似的簇；赋给最类似的簇；(4) 更新簇的平均值更新簇的平均值, 即重新计算每个簇中对象的平均值；即重新计算每个簇中对象的平均值；(5) until 不再发生变化不再发生变化 n通常通常, 采用平方误差准则作为收敛函数采用平方误差准则作为收敛函数, 其定义如下其定义如下其中其中, mi是簇是簇Ci的平均值的平均值该准则

18、试图使生成的结果簇尽可能紧凑该准则试图使生成的结果簇尽可能紧凑, 独立独立在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确k-平均聚类算法平均聚类算法(续续)n例例012345678910012345678910012345678910012345678910K=2任任意意选选择择 K个个对对象象作作为初始聚类中心为初始聚类中心将每个将每个对象赋对象赋给最相给最相似中心似中心更新簇更新簇平均值平均值重新赋值重新赋值更新簇更新簇平均值平均值重新赋值重新赋值在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅

19、入深，所提出的问题也很明确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)作为参照点作为参照点0123456789100123456789100123456789100123456789

20、10在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确k-中心点聚类方法中心点聚类方法(续续)n找聚类中的代表对象找聚类中的代表对象(中心点中心点)nPAM （Partitioning Around Medoids, 1987）n首首先先为为每每个个簇簇随随意意选选择择一一个个代代表表对对象象, 剩剩余余的的对对象象根根据据其其与代表对象的距离分配给最近的一个簇与代表对象的距离分配给最近的一个簇n反复地用非代表对象替代代表对象，以改进聚类的质量反复地用非代表对象替代代表对象，以改进聚类的质量 nPAM 对对于于较较小小的的数数据据集集非

21、非常常有有效效, 但但不不能能很很好好地地扩扩展展到到大型数据集大型数据集nCLARA (Kaufmann & Rousseeuw, 1990)抽样抽样nCLARANS (Ng & Han, 1994): 随机选样随机选样在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确n算法算法: k-中心点中心点(1) 随机选择随机选择k个对象作为初始的代表对象；个对象作为初始的代表对象；(2) repeat(3) 指派每个剩余的对象给离它最近的代表对象所代表的簇；指派每个剩余的对象给离它最近的代表对象所代表的簇；(4) 随意地选择一个非代表对象随

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

23、余的数数据据对象安排象安排对最近最近的的类随随机机选择一一个个非非类中中心心数数据据对象象 Oramdom计算交算交换的代价的代价012345678910012345678910Total Cost = 26若若聚聚类质量量上上升升，交交换O与与 Oramdom .执行循环直执行循环直至类不在发至类不在发生变化生变化012345678910012345678910k-中心点聚类方法中心点聚类方法(续续)在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确k-中心点聚类方法中心点聚类方法(续续)n为为了了判判定定一一个个非非代代表表对对象象

24、Orandom是是否否是是当当前前一一个个代代表表对对象象Oj的好的替代，对于每一个非代表对象，考虑下面四种情况：的好的替代，对于每一个非代表对象，考虑下面四种情况： n第第一一种种情情况况：p当当前前隶隶属属于于代代表表对对象象Oj. 如如果果Oj被被Orandom所所代代替替, 且且p离离Oi最近最近, ij, 那么那么p被重新分配给被重新分配给Oi n第第二二种种情情况况：p当当前前隶隶属属于于代代表表对对象象Oj. 如如果果Oj 被被Orandom代代替替, 且且p离离Orandom最近最近, 那么那么p被重新分配给被重新分配给Orandom n第第三三种种情情况况：p当当前前隶隶属属

25、于于Oi，ij。如如果果Oj被被Orandom代代替替，而而p仍然离仍然离Oi最近，那么对象的隶属不发生变化最近，那么对象的隶属不发生变化 n第第四四种种情情况况：p当当前前隶隶属属于于Oi，ij。如如果果Oj被被Orandom代代替替，且且p离离Orandom最近，那么最近，那么p被重新分配给被重新分配给Orandom 在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确 1.重新分配给重新分配给Oi 2. 重新分配给重新分配给Orandom 3. 不发生变化不发生变化 4.重新分配给重新分配给Orandom 数据对象数据对象+ 簇中心

26、簇中心替代前替代前替代后替代后k-中心点聚类代价函数的四种情况中心点聚类代价函数的四种情况+OrandomOiOjp+OrandomOiOjp+OrandomOiOjp+OrandomOiOjpk-中心点聚类方法中心点聚类方法(续续)在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确n当存在噪音和孤立点时，当存在噪音和孤立点时， PAM 比比 k-平均方法更健平均方法更健壮，其原因是中心点不象平均值那么容易被极端数壮，其原因是中心点不象平均值那么容易被极端数据影响据影响 nPAM对于小数据集工作得很好，但不能很好地用于对于小数据集工

27、作得很好，但不能很好地用于大数据集大数据集 n每次迭代每次迭代O(k(n-k)2 ) k-平均平均：O(tkn)其中其中，n 是数据对象数目，是数据对象数目，k 是聚类数是聚类数基于抽样的方法：基于抽样的方法： CLARA(Clustering LARge Applications)k-中心点聚类方法中心点聚类方法(续续)在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确26第第10章：聚类分析：基本概念和方法章：聚类分析：基本概念和方法n聚类分析聚类分析n划分方法划分方法n层次方法层次方法n基于密度的方法基于密度的方法n基于网格的方

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

29、入入聚聚类数目类数目 k, 但需要终止条件但需要终止条件在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确n凝聚的凝聚的(agglomerative)和分裂的和分裂的(divisive)层次聚类层次聚类图示图示Step 0Step 1Step 2Step 3Step 4bdceaa bd ec d ea b c d eStep 4Step 3Step 2Step 1Step 0agglomerative(AGNES)divisive(DIANA)层次方法（续）层次方法（续）在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具

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

31、isive Analysis)n由由 Kaufmann和和Rousseeuw提出提出 (1990)n已在一些统计分析软件包中实现已在一些统计分析软件包中实现 . 如如 Splusn是是 AGNES的逆的逆n最终每个节点自己形成一个簇最终每个节点自己形成一个簇在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确层次方法层次方法(续续)n四个广泛采用的簇间距离度量方法四个广泛采用的簇间距离度量方法 n最小距离：最小距离：dmin(Ci, Cj) = min pCi, pCj |p-p| n最大距离：最大距离：dmax(Ci, Cj) = ma

33、是是 O(n2), 其中其中 n 对象总数对象总数n合并或分裂的决定需要检查和估算大量的对象或簇合并或分裂的决定需要检查和估算大量的对象或簇 n不不能能撤撤消消已已做做的的处处理理, 聚聚类类之之间间不不能能交交换换对对象象. 如如果果某某一一步步没没有有很很好好地地选选择择合合并并或或分分裂裂的的决决定定, 可可能能会会导导致低质量的聚类结果致低质量的聚类结果在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确n改改进进层层次次方方法法的的聚聚类类质质量量的的方方法法: 将将层层次次聚聚类类和和其其他的聚类技术进行集成，形成多阶段聚类

34、他的聚类技术进行集成，形成多阶段聚类 nBIRCH (1996): 使使用用 CF-tree对对对对象象进进行行层层次次划划分分, 然然后后采用其他的聚类算法对聚类结果进行求精采用其他的聚类算法对聚类结果进行求精 nROCK1999：基于簇间的互联性进行合并：基于簇间的互联性进行合并nCHAMELEON (1999)：使用动态模型进行层次聚类使用动态模型进行层次聚类nCURE (1998)：采采用用固固定定数数目目的的代代表表对对象象表表示示每每个个簇簇，依据一个指定的收缩因子向着聚类中心对它们进行收缩依据一个指定的收缩因子向着聚类中心对它们进行收缩层次方法层次方法(续续)在整堂课的教学中，刘

35、教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确BIRCH (1996)nBirch (Balanced Iterative Reducing and Clustering using Hierarchies): 利利用用层层次次方方法法的的平平衡迭代归约和聚类衡迭代归约和聚类n两个重要概念两个重要概念n聚类特征聚类特征(Clustering Feature, CF)n聚类特征树聚类特征树(Clustering Feature Tree, CF树树)n聚类特征聚类特征n聚聚类类特特征征(CF)是是一一个个三三元元组组，给给出出对对象象子子类类的的信信息息

36、的的汇总汇总描述描述 n设设某某个个子子类类中中有有N个个d维维的的点点或或对对象象oI，则则该该子子类类的的CF定义如下定义如下 CF = (N, LS, SS)在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确聚类特征聚类特征Clustering Feature：CF = (N, LS, SS)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 +

37、N2, LS1 + LS2, SS1 + SS1)在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确BIRCH的的CF树树n聚类特征聚类特征 n从从统统计计学学的的观观点点来来看看，聚聚类类特特征征是是子子聚聚类类的的0阶阶, 1阶阶和和 2阶矩阶矩( moments) n记记录录了了计计算算聚聚类类和和有有效效利利用用存存储储的的关关键键度度量量, 并并有有效效地地利利用用了了存存储储，因因为为它它汇汇总总了了关关于于子子类类的的信信息息，而而不不是是存存储所有的对象储所有的对象在整堂课的教学中，刘教师总是让学生带着问题来学习，而问

38、题的设置具有一定的梯度，由浅入深，所提出的问题也很明确CF 树是高度平衡的树，它存储了层次聚类的树是高度平衡的树，它存储了层次聚类的聚类特征聚类特征 n树中的非叶节点有后代或树中的非叶节点有后代或“孩子孩子” n非非叶叶节节点点存存储储了了其其孩孩子子的的CF的的总总和和，即即汇汇总总了了关关于于其其孩孩子的聚类信息子的聚类信息 nCF树有两个参数树有两个参数影响影响CF树的大小树的大小n分支因子分支因子B: 定义非树叶节点的孩子的最大个数定义非树叶节点的孩子的最大个数n阈值阈值T: 定定义存储在树的叶子节点中的子类的最大直径存储在树的叶子节点中的子类的最大直径 BIRCH的的CF树树在整堂课

39、的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确CF1child1CF3child3CF2child2CF6child6CF1child1CF3child3CF2child2CF5child5CF1CF2CF6prevnextCF1CF2CF4prevnextB = 7T = 6RootNon-leaf nodeLeaf nodeLeaf nodeCF树树在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确BIRCH (续续)nBIRCH增增量量地地构构造造一一棵棵 CF 树树(Clus

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

41、造树被动态地构造n一个对象被插入到最近的叶子条目（子聚类）一个对象被插入到最近的叶子条目（子聚类）n如如果果在在插插入入后后存存储储在在叶叶子子节节点点中中的的子子类类的的直直径径大大于于阀阀值值, 那么该叶子节点（可能还有其他节点）被分裂那么该叶子节点（可能还有其他节点）被分裂n新对象插入后，关于该对象的信息向着树根传递新对象插入后，关于该对象的信息向着树根传递n通过修改阀值，通过修改阀值，CF树的大小可以改变树的大小可以改变 n树树重重建建：从从旧旧树树的的叶叶子子节节点点建建造造一一个个新新树树，重重建建树树的的过过程不需要重读所有的对象程不需要重读所有的对象建树只需读一次数据建树只需读

42、一次数据 n阶阶段段二二：采采用用任任何何聚聚类类算算法法对对叶叶节节点点进进行行聚聚类类，例例如典型的划分方法如典型的划分方法在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确BIRCH (续续)nBIRCH的性能的性能n支持增量聚类支持增量聚类n线线性性可可伸伸缩缩性性: 计计算算复复杂杂性性O(n), 单单遍遍扫扫描描, 附附加加的的扫扫描描可以改善聚类质量可以改善聚类质量n较好的聚类质量较好的聚类质量n缺点缺点n只能处理数值数据只能处理数值数据n对数据的输入次序敏感对数据的输入次序敏感nCf树结点不总是对应于树结点不总是对应于用

43、户考虑的用户考虑的自然簇自然簇(参数参数B和和T)n簇非球形时效果不好簇非球形时效果不好(使用半径使用半径/直径控制簇边界直径控制簇边界)在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确CHAMELEONnCHAMELEON :一一个个利利用用动动态态模模型型的的层层次次聚聚类类算算法法 (Hierarchical clustering using dynamic modeling) 由由G. Karypis, E.H. Han, and V. Kumar99 提出提出nCHAMELEON基于动态模型度量相似性基于动态模型度量相似性n

44、如如果果两两个个簇簇间间的的互互连连性性和和近近似似度度与与簇簇内内部部对对象象间间的的互互连连性和近似度高度相关性和近似度高度相关, 则合并这两个簇则合并这两个簇 n两阶段算法两阶段算法n使用图划分算法使用图划分算法: 将数据对象聚为大量相对较小的子类将数据对象聚为大量相对较小的子类n使使用用凝凝聚聚的的层层次次聚聚类类算算法法：通通过过反反复复地地合合并并子子类类来来找找到到真正的结果簇真正的结果簇在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确n既既考考虑虑互互连连性性, 又又考考虑虑簇簇间间的的近近似似度度, 特特别别是是簇簇

45、内内部部的的特特征征, 来确定最相似的子类来确定最相似的子类.n这这样样, 它它不不依依赖赖于于静静态态的的用用户户提提供供的的模模型型, 能能够够自自动动地地适适应被合并的簇的内部特征应被合并的簇的内部特征 n割割边边最最小小化化簇簇C划划分分为为两两个个子子簇簇Ci和和Cj时时需需要要割割断断的的边的加权和最小。边的加权和最小。n割边用割边用ECCi，Cj表示，评估表示，评估Ci和和Cj的簇间的的簇间的绝对互联性绝对互联性。CHAMELEON（续）（续）在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确构造稀疏图构造稀疏图划分图划分

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

47、定n在在一一个个密密集集区区域域, 邻邻域域的的定定义义范范围围相相对对狭狭窄窄; 在在一一个个稀稀疏疏区域区域, 它的定义范围相对较宽它的定义范围相对较宽 n区域的密度作为边的权重被记录下来区域的密度作为边的权重被记录下来n一个密集区域的边趋向于比稀疏区域的边有更大的权重一个密集区域的边趋向于比稀疏区域的边有更大的权重 CHAMELEON （续）（续）在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确nChameleon通通过过两两个个簇簇的的相相对对互互连连性性RI(Ci, Cj)和和相相对对接接近近度度RC(Ci, Cj)来决定簇

48、间的相似度来决定簇间的相似度 nRI(Ci, Cj)定定义义为为Ci和和Cj之之间间的的绝绝对对互互联联性性关关于于两两个个簇簇的的内部互连性的规范化内部互连性的规范化其其中中, ECCi，Cj是是包包含含Ci和和Cj的的簇簇分分裂裂为为Ci和和Cj的的割割边边, ECCi（或或ECCj）是是它它的的最最小小截截断断等等分分线线的的大大小小（即即将将图图划划分分为为两两个大致相等的部分需要切断的边的加权和）个大致相等的部分需要切断的边的加权和） CHAMELEON （续）（续）在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确nRC(

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

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

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

52、似然n若合并其中的两类若合并其中的两类Cj1和和Cj2成为成为Cj1Cj2, 那么其聚类质量变那么其聚类质量变化为化为n定义定义C1和和C2两类之间的距离两类之间的距离51在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确52第第10章：聚类分析：基本概念和方法章：聚类分析：基本概念和方法n聚类分析聚类分析n划分方法划分方法n层次方法层次方法n基于密度的方法基于密度的方法n基于网格的方法基于网格的方法n聚类评估聚类评估n小结小结在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确基

53、于密度的方法基于密度的方法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 al. (SIGMOD98)在整堂课的教学中，刘教师总是让学生带着问题来

54、学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确密度概念密度概念n -邻域：给定对象半径邻域：给定对象半径内的领域内的领域n核核心心对对象象（core object）：一一个个对对象象的的邻邻域域至至少少包包含含最最小小数目个对象（数目个对象（ MinPts ）n直直接接密密度度可可达达的的（Directly density reachable, DDR）：给给定定对对象象集集合合D, 如如果果p是是在在q的的邻邻域域内内, 而而q是是核核心心对对象象, 我我们们说对象说对象p是从对象是从对象q直接密度可达的直接密度可达的n密密度度可可达达的的(density reach

55、able): 存存在在一一个个从从p到到q的的DDR对对象链象链n密密度度相相连连的的(density-connected): 如如果果对对象象集集合合D中中存存在在一一个个对对象象o，使使得得对对象象p和和q是是从从o关关于于和和MinPts密密度度可可达达的的，那么对象那么对象p和和q是关于是关于和和MinPts密度相连的密度相连的在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确基于密度的聚类基于密度的聚类: 背景背景In两个参数两个参数:n : 邻域的最大半径邻域的最大半径nMinPts: 在在 -邻域中的最少点数邻域中的最

56、少点数 nN (p):q belongs to D | dist(p,q) = MinPts pqMinPts = 5 = 1 cm在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确基于密度的聚类基于密度的聚类: 背景背景IIn密度可达密度可达: n点点 p 关关于于 , MinPts 是是从从 q密密度度可可达达的的, 如如果果存存在在一一个个节节点点链链 p1, , pn, p1 = q, pn = p 使使得得 pi+1 是是从从pi直直接密度可达的接密度可达的n密度相连的密度相连的:n点点p关关于于 , MinPts与与点点q是

57、是密密度度相相连连的的, 如如果果存存在在点点o使使得得, p和和q都都是是关于关于 , MinPts 是从是从o密度可达的密度可达的pqopqp1在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确例子例子nMinPts=3nq是从是从p密度可达；密度可达； p不是从不是从q密度可达（密度可达（q非核心）非核心）ns和和r从从o密度可达；密度可达；o从从r密度可达；密度可达；nr, s, o密度相连密度相连在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确DBSCAN(1996)

58、nDBSCAN(Density Based Spatial Clustering of Applications with Noise) 一个基于密度的聚类算法一个基于密度的聚类算法n可以在带有可以在带有“噪音噪音”的空间数据库中发现任意形状的聚类的空间数据库中发现任意形状的聚类 CoreBorderOutlier = 1cmMinPts = 5在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确DBSCAN(续续)n算法算法n任意选取一个点任意选取一个点 pn得到所有从得到所有从p 关于关于和和 MinPts密度可达的点密度可达的点.

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

60、大的聚类设置的细微不同可能导致差别很大的聚类. （数据倾斜分布）全局密度参数不能刻画内在的聚类结构（数据倾斜分布）全局密度参数不能刻画内在的聚类结构在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确OPTICS (1999)nOPTICS(Ordering Points To Identify the Clustering Structure)nAnkerst, Breunig, Kriegel, 和和 Sander 提出提出(SIGMOD99)n考考虑虑DBSCAN, 根根据据给给定定的的和和MinPts聚聚类类对对象象, 通通常常

61、参参数选择较为困难数选择较为困难n现现实实的的高高维维数数据据集集常常常常具具有有非非常常倾倾斜斜的的分分布布, 全全局局密密度度参参数不能很好的刻画其内在聚类结构数不能很好的刻画其内在聚类结构 n为为了了同同时时构构建建不不同同的的聚聚类类, 应应当当以以特特定定的的顺顺序序来来处处理理对对象象, 优优先先选选择择最最小小的的值值密密度度可可达达的的对对象象, 以以便便高高密密度度的的聚类能被首先完成聚类能被首先完成在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确OPTICS(续续)n每个对象需要存储两个值每个对象需要存储两个值

62、n对对象象p的的核核心心距距离离（core-distance）是是使使得得p成成为为核核心心对对象的最小象的最小。如果。如果p不是核心对象不是核心对象, p的核心距离没有定义的核心距离没有定义 n对对象象 q关关于于另另一一个个对对象象 p的的可可达达距距离离（ reachability-distance）是是p的的核核心心距距离离和和p与与q的的欧欧几几里里得得距距离离之之间间的的较较大大值值. 如如果果p不不是是一一个个核核心心对对象象, p和和q之之间间的的可可达达距距离离没有定义没有定义在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的

63、梯度，由浅入深，所提出的问题也很明确OPTICS(续续)n例例: 设设 =6(mm), MinPts=5.np的核心距离是的核心距离是p与第四个最近数据对象之间的距离与第四个最近数据对象之间的距离 nq1关关于于p的的可可达达距距离离是是p的的核核心心距距离离(即即 =3mm), 因因为为它它比比从从p到到q1的欧几里得距离要大的欧几里得距离要大nq2关关于于p的的可可达达距距离离是是从从p到到q2的的欧欧几几里里得得距距离离, 它它大大于于p的的核核心距离心距离 =6mm =3mm =6mm =3mmppq1q2P的核心距离的核心距离可达距离可达距离 (p,q1)= =3mm可达距离可达距离

64、 (p,q2)=d(p,q2)在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确n存存储每每个个对象象的的核核心心距距离离和和相相应可可达达距距离离的的表表（OrderSeeds），存），存储顺序按照可达距离从小到大排序序按照可达距离从小到大排序n迭迭代代过程程按按照照表表中中的的顺序序输出出（遍遍历）对象象，在在迭迭代代过程程中表不断被更新中表不断被更新n基本思路：基本思路：n开开始始以以任任意意对象象p作作为当当前前对象象，检索索当当前前对象象p的的领领域域，并并设设置置可达距离为未定义可达距

65、离为未定义n若若p是是核核心心对对象象，则则对对于于p的的领领域域内内每每个个对对象象q，更更新新从从p到到q的的核核心心距距离离（即即更更新新OrderSeeds）；转转移移到到OrderSeeds中中的的下下一一个个对象象重重复上述步复上述步骤n若若P不不是是核核心心对象象，转移移到到OrderSeeds下下一一个个对象象（开开始始阶段段OrderSeeds为空，空，则转移到数据移到数据库中任意其它中任意其它对象）象）n迭代迭代继续，直到，直到输入耗尽且入耗尽且OrderSeeds为空空OPTICS(续续)63在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，

66、由浅入深，所提出的问题也很明确OPTICS(续续)nOPTICS算算法法创创建建了了数数据据库库中中对对象象的的一一个个次次序序, 额额外外存存储储了了每个对象的核心距离和一个适当的可达距离每个对象的核心距离和一个适当的可达距离n已已经经提提出出了了一一种种算算法法, 基基于于OPTICS产产生生的的次次序序信信息息来来抽抽取取聚聚类类. 对对于于小小于于在在生生成成该该次次序序中中采采用用的的距距离离的的任任何何距距离离 , 为提取所有基于密度的聚类为提取所有基于密度的聚类, 这些信息是足够的这些信息是足够的 n一个数据集合的聚类次序可被图形化地描述一个数据集合的聚类次序可被图形化地描述,

67、以助于理解以助于理解n由由于于OPTICS算算法法与与DBSCAN在在结结构构上上的的等等价价性性, 它它具具有有和和DBSCAN相相同同的的时时间间复复杂杂度度, 即即当当使使用用空空间间索索引引时时, 复复杂杂度度为为O(nlogn) 在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确可达距离可达距离对象的簇次序对象的簇次序无定义无定义在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确66OPTICS及其应用及其应用在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的

68、设置具有一定的梯度，由浅入深，所提出的问题也很明确DENCLUE(1998)nDENCLUE(DENsity-based CLUstEring) 由由Hinneburg 和和Keim (KDD98)提出提出, 是基于密度分布函数的聚类方法是基于密度分布函数的聚类方法n主要特点主要特点n坚实的数学基础坚实的数学基础, 概括了其他的聚类方法概括了其他的聚类方法, 包括基于划分包括基于划分的的, 层次的层次的, 及基于位置的方法及基于位置的方法 n适用于具有大量噪音的数据集适用于具有大量噪音的数据集n可用于高维数据集任意形状的聚类可用于高维数据集任意形状的聚类, 它给出了简洁的数它给出了简洁的数学描

69、述学描述n明显快于现有算法明显快于现有算法 (比比 DBSCAN 快快 45倍倍)n但是但是, 需要大量参数需要大量参数,要求对密度参数要求对密度参数和噪音阀值和噪音阀值进行进行仔细的选择仔细的选择在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确n使用栅格单元使用栅格单元, 但只保存实际存放数据点的栅格单但只保存实际存放数据点的栅格单元信息元信息, 并且在一个基于树的存取结构中管理这些并且在一个基于树的存取结构中管理这些单元单元.n影响函数影响函数(Influence function): 描述数据点在其邻描述数据点在其邻域的影响域

70、的影响.n数据空间的整体密度可以被模拟为所有数据点的影数据空间的整体密度可以被模拟为所有数据点的影响函数的总和响函数的总和n聚类可以通过确定聚类可以通过确定密度吸引点密度吸引点 (density attractor)来得到来得到.n密度吸引点是全局密度函数的局部最大值密度吸引点是全局密度函数的局部最大值.Denclue: 技术要点技术要点在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确DENCLUE(续续)n设设x和和y是是d维特征空间维特征空间Fd中的对象中的对象. 数据对象数据对象y对对x的的影响函数影响函数是一个函数是一个函数f

71、 yB：Fd R+0, 它是根据一它是根据一个基本的影响函数个基本的影响函数 fB来定义的来定义的 f yB(x)= fB(x, y)n原则上原则上, 影响函数可以是一个任意的函数影响函数可以是一个任意的函数, 它由某它由某个邻域内的两个对象之间的距离来决定个邻域内的两个对象之间的距离来决定 n例如欧几里得距离函数例如欧几里得距离函数, 用来计算一个方波影响函用来计算一个方波影响函数数(square wave influence function)：在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确DENCLUE(续续)n高斯影响函数

72、高斯影响函数n一个对象一个对象xFd的密度函数被定义为所有数据点的影响函的密度函数被定义为所有数据点的影响函数的和数的和. 给定给定n个对象个对象, D=x1,xn Fd, 在在x上的密度上的密度函数定义如下函数定义如下在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确DENCLUE(续续)n例如例如, 根据高斯影响函数得出的密度函数是根据高斯影响函数得出的密度函数是 n根据密度函数根据密度函数, 我们能够定义该我们能够定义该函数的梯度函数的梯度和和密度吸引点密度吸引点(全局密度函数的局部最大全局密度函数的局部最大)n一个点一个点x是

73、被一个是被一个密度吸引点密度吸引点 x*密度吸引的密度吸引的, 如果存在一如果存在一组点组点x0, x1, ,xk, x0=x, xk=x*, 对对0i 0重复重复m次，比较总体的质量，选择能获得最好聚类质量的次，比较总体的质量，选择能获得最好聚类质量的k90在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确度量聚类的质量度量聚类的质量n两类方法两类方法: 外在方法和内在方法外在方法和内在方法 n外在方法：有监督的方法，需要基准数据外在方法：有监督的方法，需要基准数据n用一定的度量评判聚类结果与基准数据的符合程度用一定的度量评判聚类结果

74、与基准数据的符合程度n内在方法：无监督的方法，无需基准数据内在方法：无监督的方法，无需基准数据n类内聚集程度和类间离散程度类内聚集程度和类间离散程度91在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确外在方法外在方法n聚聚类类质质量量评评估估: 用用Q(C, Cg)表表示示聚聚类类C在在给给定定基基准准数数据据Cg条条件下的质量度量件下的质量度量. nQ 的好坏取决于四个条件：的好坏取决于四个条件：n簇的同质性：簇内越纯越好簇的同质性：簇内越纯越好n簇簇的的完完整整性性：能能够够将将基基准准数数据据中中属属于于相相同同类类的的样样本本

75、聚聚类类为相同的类为相同的类n碎碎布布袋袋：把把一一个个异异种种数数据据加加入入纯纯类类应应该该比比放放入入碎碎布布袋袋受受到更大的到更大的“处罚处罚”n小小簇簇的的保保持持性性：把把小小簇簇划划分分成成更更小小簇簇比比把把大大簇簇划划分分为为小小簇的危害更大簇的危害更大92在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确内在方法内在方法n轮廓系数：轮廓系数：n对对于于D中中的的每每个个对对象象o，计计算算o与与o所所属属的的簇簇内内其其它它对对象象之之间间的的平平均均距距离离a(o)：n类似的，类似的，b(o)是是o到不包含到不包含

76、o的所有簇的最小平均距离：的所有簇的最小平均距离：n轮廓系数定义为：轮廓系数定义为：n轮轮廓廓系系数数在在-1到到1之之间间1表表明明（类类内内紧紧凑凑，类类间间离离散散）聚聚类类质质量量高高，反之则不高。反之则不高。93在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确94第第10章：聚类分析：基本概念和方法章：聚类分析：基本概念和方法n聚类分析聚类分析n划分方法划分方法n层次方法层次方法n基于密度的方法基于密度的方法n基于网格的方法基于网格的方法n聚类评估聚类评估n小结小结在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设

77、置具有一定的梯度，由浅入深，所提出的问题也很明确SummarynCluster analysis groups objects based on their similarity and has wide applicationsnMeasure of similarity can be computed for various types of datanClustering algorithms can be categorized into partitioning methods, hierarchical methods, density-based methods, grid-ba

78、sed methods, and model-based methodsnK-means and K-medoids algorithms are popular partitioning-based clustering algorithmsnBirch and Chameleon are interesting hierarchical clustering algorithms, and there are also probabilistic hierarchical clustering algorithmsnDBSCAN, OPTICS, and DENCLU are intere

79、sting density-based algorithmsnSTING and CLIQUE are grid-based methods, where CLIQUE is also a subspace clustering algorithmnQuality of clustering results can be evaluated in various ways 95在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确References (1)nR.Agrawal,J.Gehrke,D.Gunopulos,andP.Ragha

80、van.Automaticsubspaceclusteringofhighdimensionaldatafordataminingapplications.SIGMOD98nM.R.Anderberg.ClusterAnalysisforApplications.AcademicPress,1973.nM.Ankerst,M.Breunig,H.-P.Kriegel,andJ.Sander.Optics:Orderingpointstoidentifytheclusteringstructure,SIGMOD99.nBeilF.,EsterM.,XuX.:FrequentTerm-BasedT

81、extClustering,KDD02nM.M.Breunig,H.-P.Kriegel,R.Ng,J.Sander. LOF:IdentifyingDensity-BasedLocalOutliers.SIGMOD2000.nM.Ester,H.-P.Kriegel,J.Sander,andX.Xu.Adensity-basedalgorithmfordiscoveringclustersinlargespatialdatabases.KDD96.nM.Ester,H.-P.Kriegel,andX.Xu.Knowledgediscoveryinlargespatialdatabases:F

82、ocusingtechniquesforefficientclassidentification.SSD95.nD.Fisher.Knowledgeacquisitionviaincrementalconceptualclustering.MachineLearning,2:139-172,1987.nD.Gibson,J.Kleinberg,andP.Raghavan. Clusteringcategoricaldata:Anapproachbasedondynamicsystems.VLDB98.nV.Ganti,J.Gehrke,R.Ramakrishan.CACTUSClusterin

83、gCategoricalDataUsingSummaries.KDD99.96在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确References (2)nD.Gibson,J.Kleinberg,andP.Raghavan.Clusteringcategoricaldata:Anapproachbasedondynamicsystems.InProc.VLDB98.nS.Guha,R.Rastogi,andK.Shim.Cure:Anefficientclusteringalgorithmforlargedatabases.SIGM

84、OD98.nS.Guha,R.Rastogi,andK.Shim.ROCK:Arobustclusteringalgorithmforcategoricalattributes.InICDE99,pp.512-521,Sydney,Australia,March1999.nA.Hinneburg,D.lA.Keim:AnEfficientApproachtoClusteringinLargeMultimediaDatabaseswithNoise.KDD98.nA.K.JainandR.C.Dubes.AlgorithmsforClusteringData.PrinticeHall,1988.

85、nG.Karypis,E.-H.Han,andV.Kumar.CHAMELEON:AHierarchicalClusteringAlgorithmUsingDynamicModeling.COMPUTER,32(8):68-75,1999.nL.KaufmanandP.J.Rousseeuw.FindingGroupsinData:anIntroductiontoClusterAnalysis.JohnWiley&Sons,1990.nE.KnorrandR.Ng.Algorithmsforminingdistance-basedoutliersinlargedatasets.VLDB98.9

86、7在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确References (3)nG.J.McLachlanandK.E.Bkasford.MixtureModels:InferenceandApplicationstoClustering.JohnWileyandSons,1988.nR.NgandJ.Han.Efficientandeffectiveclusteringmethodforspatialdatamining.VLDB94.nL.Parsons,E.HaqueandH.Liu,SubspaceClusteringforH

87、ighDimensionalData:AReview,SIGKDDExplorations,6(1),June2004nE.Schikuta.Gridclustering:Anefficienthierarchicalclusteringmethodforverylargedatasets.Proc.1996Int.Conf.onPatternRecognition,.nG.Sheikholeslami,S.Chatterjee,andA.Zhang.WaveCluster:Amulti-resolutionclusteringapproachforverylargespatialdataba

88、ses.VLDB98.nA.K.H.Tung,J.Han,L.V.S.Lakshmanan,andR.T.Ng.Constraint-BasedClusteringinLargeDatabases,ICDT01.nA.K.H.Tung,J.Hou,andJ.Han.SpatialClusteringinthePresenceofObstacles,ICDE01nH.Wang,W.Wang,J.Yang,andP.S.Yu.Clusteringbypatternsimilarityinlargedatasets,SIGMOD02.nW.Wang,Yang,R.Muntz,STING:AStati

89、sticalInformationgridApproachtoSpatialDataMining,VLDB97.nT.Zhang,R.Ramakrishnan,andM.Livny.BIRCH:Anefficientdataclusteringmethodforverylargedatabases.SIGMOD96.nXiaoxinYin,JiaweiHan,andPhilipYu,“http:/www.cs.uiuc.edu/homes/hanj/pdf/vldb06_linkclus.pdf”,inProc.2006Int.Conf.onVeryLargeDataBases(VLDB06)

90、,Seoul,Korea,Sept.2006.98在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确99Chapter 10. Cluster Analysis: Basic Concepts and MethodsnClusterAnalysis:BasicConceptsnWhatIsClusterAnalysis?nWhatisGoodClustering?MeasuringtheQualityofClusteringnMajorcategoriesofclusteringmethodsnClusteringstructuresn

91、CalculatingDistancebetweenClustersnPartitioningMethodsnk-Means:AClassicalPartitioningMethodnAlternativeMethods:k-Medoids,k-Median,anditsVariationsnHierarchicalMethodsnAgglomerativeandDivisiveHierarchicalClusteringnBIRCH:AHierarchical,Micro-ClusteringApproachnChameleon:AHierarchicalClusteringAlgorith

92、mUsingDynamicModelingnDensity-BasedMethodsnDBSCANandOPTICS:Density-BasedClusteringBasedonConnectedRegionsnDENCLUE:ClusteringBasedonDensityDistributionFunctionsnLink-BasedClusterAnalysisnSimRank:ExploringLinksinClusterAnalysisnLinkClus:ScalabilityinLink-BasedClusterAnalysisnGrid-BasedMethodsnSTING:STatisticalINformationGridnWaveCluster:ClusteringUsingWaveletTransformationnCLIQUE:ADimension-GrowthSubspaceClusteringMethodnSummary99在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确作业作业n课后习题：10.2(P320)，10.6(P320),10.16(P321)

展开阅读全文

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

最新文档