[理学]第4章聚类分析.ppt

第4章 聚类分析,4.1 概述 4.2 基于划分的聚类算法 4.3 层次聚类算法 4.4 基于密度的聚类算法 4.5 基于图的聚类算法 4.6 一趟聚类算法 4.7 基于原型的聚类算法 4.8 聚类算法评价,4.1 概述,简单地描述，聚类(Clustering)是将数据集划分为若干相似对象组成的多个组(group)或簇(cluster)的过程，使得同一组中对象间的相似度最大化，不同组中对象间的相似度最小化。或者说一个簇(cluster)就是由彼此相似的一组对象所构成的集合，不同簇中的对象通常不相似或相似度很低。,类间相似度最小化(距离最大化),类内相似度最大化(距离最小化),从机器学习的角度看，聚类是一种无监督的机器学习方法，即事先对数据集的分布没有任何的了解，它是将物理或抽象对象的集合组成为由类似的对象组成的多个类的过程。聚类方法的目的是寻找数据中：潜在的自然分组结构和感兴趣的关系。 聚类分析中“簇”的特征： 聚类所说的簇不是事先给定的，而是根据数据的相似性和距离来划分 聚的数目和结构都没有事先假定,注意：聚类也可以是不明确的,聚类分析正在蓬勃发展，广泛应用于一些探索性领域,如统计学与模式分析，金融分析，市场营销，决策支持，信息检索，WEB挖掘，网络安全，图象处理，地质勘探、城市规划，土地使用、空间数据分析，生物学，天文学，心理学，考古学等。,4.1.1 聚类分析研究的主要内容,(1) 模式表示(包括特征提取和/或选择)； (2) 适合于数据领域的模式相似性定义； (3) 聚类或划分算法； (4) 数据摘要； (5) 输出结果的评估。,4.1.2 数据挖掘对聚类算法的要求 聚类是一个富有挑战性的研究领域，数据挖掘对聚类的典型要求如下： (1)可伸缩性(Scalability) (2)处理不同类型属性的能力 (3)发现任意形状的聚类 (4)用于决定输入参数的领域知识最小化 (5)对于输入记录顺序不敏感 (6)高维性 (7)处理噪音和异常数据的能力 (8)基于约束的聚类 (9)可解释性,4.1.3 典型聚类方法简介,划分方法(partitioning methods)基于质心(K-means)、中心的划分方法 层次的方法(hierarchical methods)BIRCH 、ROCK 、CURE 基于密度的方法 DBSCAN、 OPTICS 基于图的方法 Chameleon、SNN 基于网格的方法(grid-based methods) STING 、WaveCluster 、CLIQUE 基于模型的方法(model-based methods)EM、 COBWEB、神经网络 其他聚类方法 谱聚类算法(spectral clustering)、蚁群聚类算法等,基于划分的聚类,原始数据点,基于划分的聚类结果,基于层次的聚类,传统的层次聚类,非传统的基于层次的聚类,非传统的树图,传统的基于层次的树图,4.2 基于划分的聚类算法,给定一个 n 个对象或元组的数据库，一个划分方法构建数据的k个划分，每个划分表示一个聚类，并且k=n。也就是说，它将数据划分为k个组，同时满足如下的要求： (1)每个组至少包含一个对象； (2)每个对象必须属于且只属于一个组。 划分式聚类算法需要预先指定簇数目或簇中心，通过反复迭代运算，逐步降低目标函数的误差值，当目标函数值收敛时，得到最终聚类结果。这类方法分为基于质心的(Centroid-based)划分方法和基于中心的(Medoid-based)划分方法。,4.2.1 基本k-means聚类算法,k-means聚类算法： (1)从数据集D中任意选择k个对象作为初始簇中心； (2) repeat (3) for 数据集D中每个对象P do (4) 计算对象P到k个簇中心的距离 (5) 将对象P指派到与其最近(距离最短)的簇； (6) end for (7) 计算每个簇中对象的均值，做为新的簇的中心； (8) until k个簇的簇中心不再发生变化,K-means算法采用来表示一个簇,k-means聚类算法示例-1,例 4.1 对表4-1中二维数据，使用k-means算法将其划分为2个簇，假设初始簇中心选为P7(4，5)，P10(5，5)。 表4-1 k-means聚类过程示例数据集1 解：图4-2 显示了对于给定的数据集k-means聚类算法的执行过程。 (1)根据题目，假设划分的两个簇分别为C1和C2，中心分别为(4，5)和(5，5)，下面计算10个样本到这2个簇中心的距离，并将10个样本指派到与其最近的簇： (2)第一轮迭代结果如下： 属于簇C1的样本有：P7，P1，P2，P4，P5，P8 属于簇C2的样本有：P10，P3，P6，P9 重新计算新的簇的中心，有：C1的中心为(3.5，5.167)，C2的中心为(6.75，4.25),k-means聚类算法示例-2,(3)继续计算10个样本到新的簇的中心的距离，重新分配到新的簇中，第二轮迭代结果如下： 属于簇C1的样本有： P1，P2，P4，P5，P7，P10 属于簇C2的样本有： P3，P6，P8，P9 重新计算新的簇的中心，有：C1的中心为(3.67，5.83)，C2的中心为(6.5，3.25) (4)继续计算10个样本到新的簇的中心的距离，重新分配到新的簇中，发现簇中心不再发生变化，算法终止。,图4-2 k-means算法聚类过程示例,k-means算法描述容易、实现简单、快速，但存在不足： (1)簇的个数难以确定； (2) 聚类结果对初始值的选择较敏感； (3)这类算法采用爬山式技术寻找最优解,容易陷入局部最优值； (4)对噪音和异常数据敏感； (5)不能用于发现非凸形状的簇，或具有各种不同大小的簇。,(a) 大小不同的簇 (b) 形状不同的簇 图4.3 基于质心的划分方法不能识别的数据,4.2.2 二分k-means算法,二分K-means算法是基本k-means算法的直接扩充，基于如下想法：为了得到k个簇，将所有点的集合分裂成两个簇，从中选择一个继续分裂，如此重复直到产生k个簇。算法详细描述如下： 初始化簇表，使之包含由所有的点组成的簇。 Repeat 从簇表中选取一个簇。 对选定的簇进行多次二分“试验” For i=1 to 试验次数 do 使用基于基本k-means，二分选定的簇 End for 从二分试验中选择具有最小总SSE的两个簇。 将这两个簇添加到簇表中 Until 簇表中包含k个簇,4.2.3 k-means聚类算法的拓展 -1,对于聚类分析而言，聚类表示和数据对象之间相似度的定义是最基础的问题，直接影响数据聚类的效果。 这里介绍一种简单的聚类表示方法，并对Minkowski距离进行推广以使聚类算法可以有效处理含分类属性的数据。 假设数据集D有m个属性，其中有mC个分类属性和mN个数值属性，m=mC+mN ，用Di表示第i个属性取值的集合。,定义4-1 给定簇C， ，a 在C中关于Di 的频度定义为C在 Di上的投影中包含a 的次数： 定义4-2 给定簇C，C的摘要信息CSI(Cluster Summary Information)定义为： ，其中 为C的大小, 由分类属性中不同取值的频度信息和数值型属性的质心两部分构成，即：,4.2.3 k-means聚类算法的拓展 -2,定义4-3 给定D的簇C、 和 ,对象 与 ， x0。 (1)对象p，q在属性i上的差异程度(或距离) 定义为： 对于分类属性或二值属性， ; 对于连续数值属性或顺序属性， ； (2)两个对象p，q间的差异程度(或距离) 定义为： ;,4.2.3 k-means聚类算法的拓展 -3,(3)对象p与簇C间的距离 定义为p与簇C的摘要之间的距 离： 。 这里 为p与C在属性 上的距离，对于分类属性 其值定义为p与C中每个对象在属性 上的距离的算术平均值，即 ；对于数值属性 其值定义为 。 (4) 簇C1与C2间的距离 定义为两个簇的摘要间的距离： 。,4.2.3 k-means聚类算法的拓展 -4,这里 为 与 在属性 上的距离，对于分类属性 其值定义为 中每个对象与 中每个对象的差异的平均值： 对于数值属性 其值定义为 。 在定义4-3的(2)中，当x=1时，相当于曼哈顿(Manhattan)距离，当x=2时，相当于欧式(Euclidean)距离。,4.2.3 k-means聚类算法的拓展 -5,距离计算示例,例4-2 假设描述学生的信息包含属性：性别，籍贯，年龄。有两条记录p，q及两个簇C1，C2的信息如下，分别求出记录和簇彼此之间的距离： p=男，广州，18 ， q=女，深圳，20 C1=男：25，女：5；广州：20，深圳：6，韶关：4；19 C2=男：3，女：12；汕头：12，深圳：1，湛江：2；24 按定义4-3，取x=1得到的各距离如下： d(p，q)=1+1+(20-18)=4 d(p，C1)=(1-25/30)+(1-20/30)+(19-18)=1.5 d(p，C2)=(1-3/15)+(1-0/15)+(24-18)=7.8 d(q,C1)=(1-5/30)+(1-6/30)+(20-19)=79/30 d(q,C2)=(1-12/15)+(1-1/15)+(24-20)=77/15 d(C1,C2)=1-(25*3+5*12)/(30*15)+1-6*1/(30*15)+(24-19)=1003/1506.69,4.2.3 k-means聚类算法的拓展 k-summary,k-summary算法由几个主要步骤完成: (1)从数据集D中任意选择k个对象，并创建k个簇的摘要信息CSI； (2) repeat (3) for 数据集D中每个对象P do (4) 计算对象P到k个簇中心的距离 (5) 将对象P指派到与其最近(距离最短)的簇； (6) end for (7) 更新簇的摘要信息CSI； (8) until k个簇的摘要信息不再发生变化,k-summary算法示例-1,例4-3 对于表4-2所示的数据集，请使用k-summary算法将其划分为3个簇。 表4-2 聚类过程示例数据集2,k-summary算法示例-2,解：(1)假定选择第5条记录 rainy，68,80，FALSE ，第7条记录overcast，64，65，TRUE和第10条记录 rainy，75，80，FALSE 作为三个簇C1、C2和C3的初始中心（摘要）。 (2) 划分对象到最近的簇，各记录与三个簇之间的距离 (使用欧几里得距离) 如下表：,k-summary算法示例-3,第一次划分后三个簇的摘要信息更新为： 簇C1: rainy:3 ;69.667; 89.000; FALSE:2,TRUE:1; 簇C2: overcast:1,rainy:1,sunny:1 ;66.0;68.333;FALSE:1,TRUE:2 ; 簇C3: overcast:3,rainy:1,sunny:4;77.875;83.875; FALSE:5,TRUE:3 (3)重新划分对象到最近的簇，第二次迭代结果：,k-summary算法示例-4,第二次划分后三个簇的摘要信息更新为 簇C1: overcast:1,rain:3,sunny:1 ;70.6;90.4; FALSE:3,TRUE:2; 簇C2: overcast:1,rainy:1,sunny:2; 68.25;68.75; FALSE:1,TRUE:3; 簇C3: overcast:2,rainy:1,sunny:2; 80.8;83.2; FALSE:4,TRUE:1 (4)重新划分对象到最近的簇，第三次迭代结果：,k-summary算法示例-5,第三次划分后三个簇的摘要信息更新为 簇C1: overcast:1,rain:3,sunny:1;70.6;90.4; FALSE:3,TRUE:2 ; 簇C2: overcast:1,rainy:1,sunny:2; 68.25;68.75; FALSE:1,TRUE:3; 簇C3: overcast:2,rainy:1,sunny:2; 80.8;83.2; FALSE:4,TRUE:1 (5)经过三轮划分后，三个簇的摘要不再发生改变，聚类结束。 簇C1包含的记录集合为1,2,3,10,13，摘要信息为 C1:overcast:1,rain:3,sunny:1;70.6;90.4; FALSE:3,TRUE:2 ；簇C2 包含的记录集合为4,5, 8,12, 14，摘要信息为 C2:overcast:1,rainy:1,sunny:2; 68.25;68.75; FALSE:1,TRUE:3； 簇C3包含的记录集合为6,7,9,11，摘要信息为 C3:overcast:2,rainy:1,sunny:2; 80.8;83.2; FALSE:4, TRUE:1。,4.2.4 k-medoids算法,算法：k-medoids (1)任意选取k个不同对象作为初始中心点 (2)repeat (3) 把剩余对象分配到距它最近的代表点所在的簇； (4) 随机选择一个非中心点对象Or； (5) 计算用Or交换Oj的总代价s； (6) 如果s0，则用Or替换Oj，形成新的k个中心点； (7)until k个中心点不在发生变化,4.3 层次聚类算法,自下而上聚合层次聚类方法(或凝聚层次聚类)。这种自下而上策略就是最初将每个对象(自身)作为一个簇，然后将这些簇进行聚合以构造越来越大的簇，直到所有对象均聚合为一个簇，或满足一定终止条件为止。绝大多数层次聚类方法属于这一类，只是簇间相似度的定义有所不同。 自顶向下分解层次聚类方法(或分裂层次聚类)。这种策略的作法与自下而上策略的作法相反。它首先将所有对象看成一个簇的内容，将其不断分解以使其变成越来越小但个数越来越多的小簇，直到所有对象均独自构成一个簇，或满足一定终止条件为止。,图4.4 两种不同层次聚类算法,4.3.1 BIRCH算法,聚类特征CF是一个三维向量，汇总了对象簇的信息。给定簇中n个m维对象或点 ，则该簇的CF定义如下,假定在簇 中有三个点(2，5)，(3，2)和(4，3)。 的聚类特征是： CF1 = = 假定 是与 不相交的簇， CF2 = 。 和 合并形成一个新的簇 ，其聚类特征便是 ，即： CF3= = ,例题：,CF树,一个CF-树是一个高度平衡的树，它具有两个参数：分支因 子和阈值T，分支因子包括非叶节点CF条目最大个数B和叶 节点中CF条目的最大个数L。 图4.5(1) CF-树结构图,CF-树的构造过程实际是一个数据点的插入过程，其步骤如 下： (1) 从根节点开始递归往下，计算当前条目与要插入数据点之间的距离，寻找距离最小的那个路径，直到找到与该数据点最接近的叶节点中的条目。 (2) 比较计算出的距离是否小于阈值T，如果小于则当前条目吸收该数据点；如果距离大于等于阈值T，则转(3)。 (3) 判断当前条目所在叶节点的条目个数是否小于L，如果是则直接将数据点插入为该数据点的新条目，否则需要分裂该叶节点。分裂的原则是寻找该叶节点中距离最远的两个条目并以这两个条目作为分裂后新的两个叶节点的起始条目，其它剩下的条目根据距离最小原则分配到这两个新的叶节点中，删除原叶节点并更新整个CF树。 当数据点无法插入时，这个时候需要提升阈值T并重建树来吸收更多的叶节点条目，直到把所有数据点全部插入完毕。,BIRCH算法描述 BIRCH算法主要分为四个阶段：第一个阶段对整个数据集进行扫描，根据给定的初始阈值T建立一棵初始聚类特征树；第二阶段通过提升阈值T重建CF树，得到一棵压缩的CF树。第三、四阶段利用全局聚类算法对已有的CF树进行聚类得到更好的聚类结果。 其中具体建树阶段算法步骤如下： (1) 给定一个初始的阈值T并初始化一棵CF-树t1。 (2) 扫描数据点并插入到CF-树t1中。 (3) 判断内存是否溢出，如果没有溢出转(4)，如果溢出转(5)。 (4) 此时已经扫描完所有数据点，将存储在磁盘中的潜在离群点重新吸收到CF-树t1中，结束建树。 (5) 提升阈值T的值并根据新的阈值通过CF-树t1中各节点条目重建CF-树t2：在重建过程中，如果t1的叶节点条目是潜在的离群点并且磁盘仍有空间，则将该离群点写入磁盘，否则使用该条目重建树t2。整个树t2建好后，重新将t2赋给t1。 (6) 判断此时存储潜在离群点的磁盘是否已满，如果没有满则转(2)继续扫描下一个数据点。如果此时磁盘满了，则将存储在磁盘中的潜在离群点重新吸收到CF-树t1中，并转转(2)继续扫描下一个数据点。,4.3.2 CURE算法,特点： 解决了偏好球形和相似大小的问题，在处理孤立点上也更加健壮。 采用了一种新的层次聚类算法，该算法选择了位于基于质心和基于代表对象方法之间的中间策略。 不用单个质心或对象来代表一个簇，而是选择了数据空间中固定数目的具有代表性的点。 一个簇的代表点通过如下方式产生：首先选择簇中分散的对象，然后根据一个特定的分数或收缩因子向簇中心“收缩”或移动它们。在算法的每一步，有最近距离的代表点对(每个点来自于一个不同的簇)的两个簇被合并。,CURE是一种自底向上的层次聚类算法，首先将输入的每个点作为一个簇，然后合并相似的簇，直到簇的个数为k 时停止。 算法描述如下： (1)从源数据对象中抽取一个随机样本 S； (2)将样本 S划分为一组分块； (3)对每个划分局部地聚类； (4)通过随机取样剔除孤立点。如果一个簇增长得太慢，就去掉它。 (5)对局部的簇进行聚类。 落在每个新形成的簇中的代表点根据用户定义的一个收缩因子 a 收缩或向簇中心移动。这些点描述和捕捉到了簇的形状。 (6)用相应的簇标签来标记数据。,4.3.3 ROCK算法,ROCK采用一种比较全局的观点，通过考虑成对点的邻域情况进行聚类。如果两个相似的点同时具有相似的邻域，那么这两个点可能属于同一个簇而合并。 两个“点”即两个事务 和 之间的相似度用Jaccard系数定义为：,例4-4同时使用点间相似度和邻域链接信息的影响分析示例,假定一个购物篮数据库包含关于商品a,b,g的事务记录。考虑这些事务的两个簇C1和C2。C1涉及商品a，b，c，d，e，包含事务a，b，c，a，b，d，a，b，e，a，c，d，a，c，e，a，d，e，b，c，d，b，c，e，b，d，e，c，d，e。C2涉及商品a，b，f，g，包含事务a，b，f，a，b，g，a，f，g，b，f，g。假设我们首先只考虑点间的相似度而忽略邻域信息。C1中事务a，b，c和b，d，e之间的Jaccard系数为1/5=0.2。事实上，C1中任意一对事务之间的Jaccard系数都在0.2和0.5之间(如a，b，c和a，b，d)。而属于不同簇的两个事务之间的Jaccard系数也可能达到0.5(如C1中的a，b，c和C2中的a，b，f或a，b，g)。很明显，仅仅使用Jaccard系数，无法得到所期望的簇。,ROCK基于链接的方法可以成功地把这些事务划分到恰当的簇中。直观地看，对于每一个事务，与之链接最多的那个事务总是和它处于同一个簇中。例如，令，则C2中的事务a，b，f与同样来自同一簇的事务a，b，g之间的链接数为5(因为它们有共同的近邻a，b，c，a，b，d，a，b，e，a，f，g和b，f，g)。然而，C2中的事务a，b，f与C1中事务a，b，c之间的链接数仅为3(其共同的邻居为a，b，d，a，b，e和a，b，g)。类似地，C2中的事务a，f，g与C2中其它每个事务之间的链接数均为2，而与C1中所有事务的链接数都为0。因此，这种基于链接的方法能够正确地区分出两个不同的事务簇，因为它除了考虑对象间的相似度之外还考虑邻近信息。,ROCK使用一个相似度阈值和共享近邻的概念从一个给定的数据相似度矩阵中首先构建一个稀疏图。然后在这个稀疏图上执行凝聚层次聚类。使用一个优度(goodness measure)度量评价聚类，采用随机抽样处理大规模的数据集。,ROCK算法的聚类过程描述如下： (1) 随机选择一个样本； (2) 在样本上用凝聚算法进行聚类，簇的合并是基于簇间的相似度，即基于来自不同簇而有相同邻居的样本的数目； (3) 将其余每个数据根据它与每个簇之间的连接，判断它应归属的簇。,4.4 基于密度的聚类算法,通常将簇看作是数据空间中被低密度区域(代表噪声)分割开的稠密对象区域。基于密度的方法典型的包括 DBSCAN (Density-Based Spatial Clustering of Applications with Noise) OPTICS(Ordering Points to Identify the Clustering Structure),图4.6 基于密度的聚类算法可聚类的形状,DBSCAN算法-1,DBSCAN是一种基于高密度连通区域的聚类方法，该算法将具有足够高密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点的最大的集合。根据点的密度将点分为三类：(1) 稠密区域内部的点(核心点)，(2) 稠密区域边缘上的点(边界点)，(3) 稀疏区域中的点(噪声或背景点)。下面将介绍一些基本概念。 给定一个对象集合D，对象之间的距离函数为distance(*，*)，邻域半径为Eps。 数据集中特定点的密度通过该点的Eps半径之内包含的点数(包括点本身)来估计。,DBSCAN算法-2,Eps邻域：给定对象半径Eps内的邻域称为该对象的Eps邻域。我们用 表示点p的Eps-半径内的点的集合，即 MinPts：给定邻域 包含的点的最小数目，用以决定点p是簇的核心部分还是边界点或噪声。 核心对象：如果对象的Eps邻域包含至少MinPts个的对象，则称该对象为核心对象。 边界点：边界点不是核心点，但落在某个核心点的邻域内。 噪音点：既不是核心点，也不是边界点的任何点。,DBSCAN算法-3,直接密度可达：如果p在q的Eps邻域内，而q是一个核心对象，则称对象p 从对象q出发时是直接密度可达的(directly density-reachable)。 密度可达：如果存在一个对象链 ，对于 ， 是 从关于Eps和MinPts直接密度可达的，则对象p是从对象q关于Eps和MinPts密度可达的(density-reachable)。 密度相连：如果存在对象OD，使对象p和q都是从O关于Eps和MinPts密度可达的，那么对象p到q是关于Eps和MinPts密度相连的(density-connected)。,算法具体描述,(1) 首先将数据集D中的所有对象标记为未处理状态 (2) for 数据集D中每个对象p do (3) if p已经归入某个簇或标记为噪声 then (4) continue; (5) else (6) 检查对象p的Eps邻域 ； (7) if 包含的对象数小于MinPts then (8) 标记对象p为边界点或噪声点； (9) else (10) 标记对象p为核心点，并建立新簇C； (11) for 中所有尚未被处理的对象q do (12) 检查其Eps邻域 ，若 包含至少MinPts个对象，则将 中未归入任何一个簇的对象加入C； (13) end for (14) end if (15) end if (16) end for,例4-5 DBSCAN算法示例1,如图4.7所示，Eps用一个相应的半径表示，设MinPts=3。,图4.7 “直接密度可达”和“密度可达”概念示意描述,解答：根据以上概念知道：由于有标记的各点M、P、O和R的Eps近邻均包含3个以上的点，因此它们都是核对象；M是从P“直接密度可达”；而Q则是从M“直接密度可达”；基于上述结果，Q是从P“密度可达”；但P从Q无法“密度可达”(非对称)。类似地，S和R从O是“密度可达”的；O、R和S均是“密度相连”的。,例4-6 DBSCAN算法示例2,对于表4-3所示二维平面上的数据集，取Eps=3，MinPts=3 来演示 DBSCAN算法的聚类过程(使用Mahattan距离公式)。 表4-3 聚类过程示例数据集3,DBSCAN算法示例2,解答：(1) 随机选择一个点，如P1(1，2)，其Eps邻域中包含P1，P2，P3，P13，P1是核心点，其邻域中的点构成簇1的一部分，依次检查P2，P3，P13的Eps邻域，进行扩展，将点P4并入，P4 为边界点； (2) 检查点P5，其Eps邻域中包含P5，P6，P7，P8，P5是核心点，其邻域中的点构成簇2的一部分，依次检查P6，P7，P8的Eps邻域，进行扩展，每个点都是核心点，不能扩展； (3) 检查点P9，其Eps邻域中包含P9，P9为噪声点或边界点； (4) 检查点P10，其Eps邻域中包含P10，P11，P10为噪声点或边界点；检查P11，其Eps邻域中包含P10，P11，P12，P11为核心点，其邻域中的点构成簇3的一部分；进一步检查，P10、P12为边界点。,DBSCAN算法示例2,所有点标记完毕，P9没有落在任何核心点的邻域内，为噪声点。 最终识别出三个簇，P9为噪声点。簇1包含P1，P2，P3，P4，P13，P4为边界点，其它点为核心点；簇2包含P5，P6，P7，P8 ，其全部点均为核心点；簇3包含P10，P11，P12，P10、P12为边界点，P11为核心点； 如果MinPts=4，则簇3中的点均被识别成噪声点。,4.5 基于图的聚类算法,基于图的聚类算法需要用到一些重要方法 (1) 稀疏化邻近度图，只保留对象与其最近邻之间的连接。这种稀疏化有利于降低噪声和离群点的影响。可以利用为稀疏图开发的有效图划分算法来进行稀疏化。 (2) 基于共享的最近邻个数，定义两个对象之间的相似性度量。该方法基于这样的观察，对象和它的最近邻通常属于同一个簇。该方法有助于克服高维和变密度簇的问题。 (3) 定义核心对象并构建环绕它们的簇。与DBSCAN一样，围绕核心对象构建簇，设计可以发现不同形状和大小的簇的聚类技术。 (4) 使用邻近度图中的信息，提供两个簇是否应当合并的更复杂的评估。两个簇合并仅当结果簇具有相似于原来的两个簇的特性。,4.5.1 Chameleon聚类算法,利用动态模型的层次聚类算法 Chameleon算法是一种基于图的层次聚类算法，该算法利用基于图的方法得到的初始数据划分与一种新颖的层次聚类方案相结合，使用簇间的接近性和互连性概念以及簇的局部建模来高质量地发现具有不同形状、大小和密度的簇。,Chameleon聚类算法-2,确定合并哪些簇 Chameleon力求合并这样的一对簇，合并后产生的簇，用互连性和紧密性来度量时，其与原来的一对簇最相似。为了理解互连性和紧密性概念，需要用邻近图的观点，并且需要考虑簇内和簇间点之间的边数和这些边的强度。 相对互连度(relative interconnectivity，RI)：簇 和 之间的绝对互连度是连接簇 和 中顶点的所有边的权重之和，其本质是同时包含簇 和 的边割(edge cut，EC)，用 表示。簇 的内部互连度可以通过它的最小二分边割 的大小(即将图划分成两个大致相等的部分的边的加权和)表示。簇 和 间的相对互连度 定义为用簇 和 的内部互连度规格化簇 和 间的绝对互连度，计算公式如下：,Chameleon聚类算法-3,这里， 为绝对互连度，其值为“跨越两个簇的所有边的权重 和”， 表示内部互连度，其值为“簇 内所有边的权重和”。图 4.8解释了相对互连度的概念。两个圆形簇(c)和(d)比两个矩形簇(a)和 (b)具有更多连接，然而，合并(c)和(d)产生的簇具有非常不同于(c)和 (d)的连接性。相比之下，合并(a)和(b)产生的簇的连接性与簇(a)和(b) 非常类似。,图4.8 第一对簇更“紧密”,Chameleon聚类算法-4,相对紧密度(relative closeness, RC)：簇 和 间的相对紧密度 被定义为用簇 和 的内部紧密度规格化簇 和 间的绝对紧 密度。度量两个簇的紧密度的方法是取簇 和 间连接边的平均 权重。具体计算公式如下： 式中， 为簇 和 间的绝对紧密度，通过簇 和 的 连接边的平均权重来度量，即 ， 是内部紧 密度，通过簇 内连接边的平均权重来度量，即 RI和RC可以用多种不同的方法组合，以产生自相似性(self-similarity) 的总度量。Chameleon使用的是合并最大化 的簇对，其中是用户指定的参数，通常大于1。,Chameleon算法由三个关键步骤组成：,图4.9 Chameleon算法聚类步骤,Chameleon算法具体描述： 构建稀疏图：由数据集构造成一个k-最近邻图 ； 多层图划分：通过一个多层图划分算法将图 划分成大量的子图，每个子图代表一个初始子簇； 合并子簇：合并关于相似度函数 而言，最好地保持簇的自相似性的簇； 重复步骤(3),直至不再有可以合并的簇或者用户指定停止合并时的簇个数。,Chameleon算法演示示例-1,例4-7：对表4-4所示数据集(图形化显示如图4.10所示)，演示Chameleon算法聚类过程。 表4-4 Chameleon算法示例数据集,图4.10 Chameleon算法示例数据集,Chameleon算法演示示例-2,解答：对于表4-4中所示数据，采用 计算点 ， 之间的相似度，得到的相似度矩阵如表4-5所示。,Chameleon算法演示示例-3,在Chameleon聚类算法的第一阶段，采用图划分方法得到细粒度子簇。对于所考虑的数据，得到四个初始的子簇，即 簇1：C1=(2，2)，(3，1)，(3，4)，(5，3)，这些点的索引集为1， 2，3，4。 簇2：C2=(9，8)，(9，7)，(10，10)，(11，8)，这些点的索引集为 5，6，7，8。 簇3：C3=(1，6)，(2，7)，(1，7)，这些点的索引集为9，10，13。 簇4：C4=(11，4)，(12，5)，(13，4)，这些点的索引集为11， 12，14。 为了便于说明，我们对数据进行重新排序，使得同一组内点的编号是 连续的。在算法的第二阶段，基于相对互连度(RI)和相对紧密度(RC) 度量，寻找可以合并的簇对。,Chameleon算法演示示例-4,对于不同的簇 和 ， 为两个簇的所有点对间的相似度之和， (即 )为 内的所有点对间的相似度之和，可以通过表4-5中的阴影区域和非阴影区域不同块中所有元素之和而得到，表4-6显示了计算得到的结果。 表4-6 簇对的互连度(非对角线)和内部互连度(对角线)度量 由 计算簇 和 间的相对互连性度量，利用 表4-6中得到的数据进行计算，计算结果如表4-7所示。,Chameleon算法演示示例-5,表4-7 相对互连性度量 以 为例说明计算过程， 。 利用表4-6中数据及已知的每个簇包含元素的数目，按下列公式计算相对紧密度 下面以 为例，说明计算过程：,Chameleon算法演示示例-6,表4-8给出了所有簇之间的相对紧密性度量计算结果。 表4-8 相对紧密性度量,通过把表4-7和表4-8中的元素对应相乘得到表4-9。 表4-9 互连性和紧密性度量积(RI*RC),Chameleon算法演示示例-7,从表中可以发现，簇对(1,3)和(2,4)使得RI*RC最大化，因此合并相应的两个簇，现在我们只剩两个簇，分别用C13和C24表示。 为了画出树状图，需要计算簇之间的距离，可以从平均紧密度度量推导。 是簇C1与C3内12个点对间的相似度之和，因此，平均值 。我们可以利用关系 或者 将它转换为距离度量，得到 。类 似地，可以得到 。 对于簇C13和C24，进一步计算可以得到： ， ， ， 。,Chameleon算法演示示例-8,聚类结果树状图显示在图4.11中。,图4.11 树状图,4.5.2 基于SNN密度的聚类算法,SNN，即共享最近邻 (Shared Nearest Neighbor, SNN), SNN相似度旨在解决低相似度和不同密度两个问题。当两个对象都在对方的最近邻列表中，SNN相似度就是它们共享的近邻个数。计算共享最近邻相似度的具体步骤： 找出所有点的k-最近邻。 If 两个点x和y不是相互在对方的k-最近邻中 then Similarity(x,y)=0 Else Similarity(x,y)=共享的近邻个数 End if,Levent Ertoz等人基于共享最近邻相似度上，提出了一种基于共享最近邻聚类算法SNN(Shared Nearest Neighbor,)。该算法的主要步骤如下： 构造SNN相似度矩阵； 进行最近k邻居的稀疏处理(使用相似度阈值)，并以此构造出最近邻居图，使得具有较强联系的样本间有链接。 统计出所有样本点的链接力度，以此确立聚类中心和噪声数据，将噪声数据从样本点中排除出来，并再次对图中的链接进行一次过滤。 最后依据确定的聚类中心和剩下的最近邻居图来进行聚类处理。,基于SNN密度概念，其相应的聚类算法如下所示： 计算SNN相似度。 以用户指定的参数Eps和MinPts，使用DBSCAN聚类。 该算法自动地确定数据中的簇的个数。在这里，并非所有的点都被聚类，一些噪声、离群点和没有很强地链接到一组点的那些点都是被丢弃的点。,4.6 一趟聚类算法,现有聚类算法的普遍存在以下不足： 对于大规模数据集，聚类时效性和准确性难以满足要求； 难以直接处理混合属性的数据； 聚类结果依赖于参数，而参数的选择主要靠经验或试探，没有简单、通用的方法。,一趟聚类算法描述 基于最小距离原则的聚类算法CABMDP (Clustering Algorithm Based on Minimal Distance Principle)采用摘要信息CSI表示一个簇，将数据集分割为半径几乎相同的超球体(簇)。具体过程如下： 初始时，簇集合为空，读入一个新的对象； 以这个对象构造一个新的簇； 若已到数据库末尾，则转(6)，否则读入新对象，利用给定的距离定义，计算它与每个已有簇间的距离，并选择最小的距离； 若最小距离超过给定的半径阈值r，转(2)； 否则将该对象并入具有最小距离的簇中并更新该簇的各分类属性值的统计频度及数值属性的质心，转(3)； 结束。,半径阈值r的选择,采用抽样技术来计算阈值范围，具体描述如下： (1) 在数据集D中随机选择对对象； (2) 计算每对对象间的距离； (3) 计算(2)中距离的平均值EX和标准差DX； (4) 取r在EX+0.25DX到EX-2DX之间,一趟聚类算法聚类过程示例-1,例4-8 对于表4-11所示的数据集，请使用一趟聚类算法对其进行聚类。(使用Mahattan距离公式) 表4-11 聚类过程示例数据集2,一趟聚类算法聚类过程示例-2,解：聚类阈值取r= 16(经计算得EX=19，DX=10) 。 (1) 取第1条记录作为簇C1的初始簇中心，其摘要信息为 sunny:1;85;85;FALSE:1； (2) 读取第2条记录，其到簇C1的距离d=0+5+5+1=1116，以第4条记录构建一个新的簇C2，其摘要信息为 rainy:1；70；96；FALSE:1； (5) 读取第5条记录，其到簇C1的距离为1-0/3+14.67+7+1- 2/3=2316，到簇C2的距离为0+2+16+0=1816，以第5条记录构 建一个新的簇C3，其摘要信息为 rainy:1；68；80；FALSE:1；,一趟聚类算法聚类过程示例-3,(6) 读取第6条记录，其到簇C1的距离为1-0/3+17.67+17+1-1/3=36.3316，到簇C2的距离为0+5+26+1=3216，到簇C3的距离为0+3+10+1=1416，到簇C2的距离为1+6+31+1=3916，到簇C3的距离为1+2.5+10+1-1/2=1416，到簇C2的距离为1+2+1+0=416，将第8条记录划分到簇C2中，簇C2的摘要信息更新为rainy:1,sunny:1；71；95.5；FALSE:2; (9) 读取第9条记录，其到簇C1的距离为1-2/3+13.67+17+1-2/3=31.3316，到簇C2的距离为1-1/2+2+25.5+1-2/2=2816，到簇C3的距离为1-0/3+3.33+1.67+1-1/3=6.6716，将第9条记录划分到簇C3中，簇C3的摘要信息更新为rainy:2,sunny:1,overcast:1；66.5；71.25；FALSE:2,TRUE:2;,一趟聚类算法聚类过程示例-4,(10) 读取第10条记录，其到簇C1的距离为1-0/3+7.67+7+1-2/3=1616，到簇C3的距离为1-2/4+8.5+8.75+1-2/4=18.2516，将第10条记录划分到簇C1中，簇C1的摘要信息更新为rainy:1,sunny:2,overcast:1；80.75；85.25；FALSE:3,TRUE:1; (11)读取第11条记录，其到簇C1的距离为1-2/4+5.75+15.25+1-1/4=22.2516，到簇C2的距离为1-1/2+4+25.5+1-0/2=3116，到簇C3的距离为1-1/4+8.5+1.25+1-2/4=1116，将第11条记录划分到簇C2中，簇C2的摘要信息更新为rainy:1,sunny:1,overcast:1；71.33；93.67；FALSE:2,TRUE:1;,一趟聚类算法聚类过程示例-5,(13)读取第13条记录，其到簇C1的距离为1-1/4+0.25+10.25+1-3/4=11.516，到簇C3的距离为1-1/5+12.8+ 4+1-2/5=18.216，将第11条记录划分到簇C1中，簇C1的摘要信息更新为rainy:1,sunny:2,overcast:2；80.8；83.2；FALSE:4,TRUE:1; (14)读取第14条记录，其到簇C1的距离为1-1/5+9.8+7.8+1-1/5=19.216，到簇C2的距离为1-1/3+0.33+2.67+1-1/3=4.3316，将第11条记录划分到簇C2中，簇C2的摘要信息更新为rainy:2,sunny:1,overcast:1；71.25；93；FALSE:2,TRUE:2; (15) 全部记录处理完之后，得到三个簇。簇C1包含的记录集合为1，2，3，10，13，摘要信息为rainy:1,sunny:2,overcast:2；80.8；83.2；FALSE:4,TRUE:1;簇C2包含的记录集合为4，8，12，14，摘要信息为rainy:2,sunny:1,overcast:1；71.25；93；FALSE:2,TRUE:2;簇C3包含的记录集合为5，6，7，9，11，摘要信息为rainy:2,sunny:2,overcast:1；68.2；71；FALSE:2,TRUE:3。,一趟聚类算法的优劣,优点：高效，参数选择简单，对噪声不敏感 缺点：不能用于发现非凸形状的簇，或具有各种不同大小的簇。,4.7 基于模型的聚类算法,基于模型的聚类方法试图将给定数据与某个数学模型达成最佳拟合。此类方法经常是基于数据都有一个内在的混合概率分布假设来进行的。主要包括： 期望最大化方法 概念聚类 自组织神经网络方法,4.7.1 期望最大化方法EM,期望最大化EM(Expectation Maximization)算法是一种流行的迭代求精算法，EM不是把每个对象指派到特定的簇，而是根据一个代表隶属概率的权重将每个对象指派到簇。 算法描述如下： (1)对参数向量作初始估计：包括随机选择k个对象代表簇的均值或中心(就像k-means算法)，以及估计其它的参数。 (2)按如下两个步骤反复求精参数(或簇)： (a)期望步:计算每个对象 指派到簇 的概率；换言之，这一步对每簇计算对象 的簇隶属概率。 (b)最大化步：利用前一步得到的概率估计重新估计(或求精)模型参数。这一步是对给定数据的分布似然“最大化”。,4.7.2 概念聚类,概念聚类是一种机器学习聚类方法，给定一组未标记的对象，产生对象的分类模式。与传统的聚类不同，概念聚类除了确定相似的对象分组外，还找出每组对象的特征描述，其中每组对象代表一个概念或类。因此，概念聚类是一个两步的过程：首先进行聚类，然后给出特征描述。,COBWEB是一个常用的且简单的增量式概念聚类方法。它 的输入对象是采用符号值对(属性-值)来加以描述的。 COBWEB方法采用分类树的形式来创建一个层次聚类