第6章聚类分析.ppt

《第6章聚类分析.ppt》由会员分享，可在线阅读，更多相关《第6章聚类分析.ppt（168页珍藏版）》请在三一办公上搜索。

1、1,第6章 聚类分析,什么是聚类（Clustering）分析?聚类分析中的数据类型主要聚类方法分类划分方法（Partitioning Methods）层次方法（Hierarchical Methods）基于密度的方法（Density-Based Methods）基于网格的方法（Grid-Based Methods）基于模型的聚类方法（Model-Based Clustering Methods）孤立点分析（Outlier Analysis）小结,2,什么是聚类分析?,聚类:数据对象的集合/簇(cluster)同一簇中的对象彼此相似不同簇中的对象彼此相异聚类分析将数据对象分组成为多个类或簇聚类是

2、无指导的分类:没有预先定义的类典型应用作为洞察数据内部分布的独一无二的工具 作为其它算法的预处理步骤,3,聚类的一般应用,模式识别空间数据分析 聚类产生GIS(地理信息系统)的专题地图thematic maps 在空间数据挖掘中检测空间聚类并解释它们图象处理经济科学(特别是市场研究)WWW文本分类Web日志数据聚类，发现类似访问模式群,4,聚类应用的例子,市场营销:帮助市场营销者发现他们的基本顾客的不同组群，然后利用这一知识制定有针对性的营销计划国土利用在地球观测数据库中识别类似的国土使用区域保险 对汽车保险持有者的分组 城市规划根据房子的类型，价值，和地理位置对一个城市中房屋的分组 地震研究

3、应当将观测到的地震震中沿大陆板块断裂进行聚类,5,什么是好的聚类方法?,一个好的聚类方法应当产生高质量的聚类类内相似性高类间相似性低聚类结果的质量依赖于方法所使用的相似性度量和它的实现.聚类方法的质量也用它发现某些或全部隐藏的模式的能力来度量,6,数据挖掘对聚类的要求,可伸缩性有的算法当数据对象少于200时处理很好,但对大量数据对象偏差较大大型数据库包含数百万个对象处理不同属性类型的能力许多算法专门用于数值类型的数据实际应用涉及不同的数据类型,i.e.混合了数值和分类数据发现任意形状的聚类基于距离的聚类趋向于发现具有相近尺度和密度的球状簇 一个簇可能是任意形状的,7,数据挖掘对聚类的要求(续)

4、,用于决定输入参数的领域知识最小化许多聚类算法要求用户输入一定的参数,如希望产生的簇的数目.聚类结果对于输入参数十分敏感 参数难以确定,增加了用户的负担,使聚类质量难以控制处理噪声数据和孤立点的能力 一些聚类算法对于噪音数据敏感,可能导致低质量的聚类结果现实世界中的数据库大都包含了孤立点,空缺,或者错误的数据 对于输入记录的顺序不敏感 一些聚类算法对于输入数据的顺序是敏感的,以不同的次序输入会导致不同的聚类,8,数据挖掘对聚类的要求(续),高维性（high dimensionality）许多聚类算法擅长处理低维的数据,可能只涉及两到三维 数据库或者数据仓库可能包含若干维或者属性,数据可能非常稀

5、疏,而且高度偏斜 整合用户指定的约束现实世界的应用可能需要在各种约束条件下进行聚类 要找到既满足特定的约束,又具有良好聚类特性的数据分组是一项具有挑战性的任务 可解释性和可用性 用户希望聚类结果是可解释的,可理解的,和可用的 聚类可能需要和特定的语义解释和应用相联系,9,第6章.聚类分析,什么是聚类（Clustering）分析?聚类分析中的数据类型主要聚类方法分类划分方法（Partitioning Methods）层次方法（Hierarchical Methods）基于密度的方法（Density-Based Methods）基于网格的方法（Grid-Based Methods）基于模型的聚类方

6、法（Model-Based Clustering Methods）孤立点分析（Outlier Analysis）小结,10,数据结构,数据矩阵(two modes)相异度矩阵(Dissimilarity matrix)(one mode),11,评估聚类的质量,有一个单独的“质量”函数,它度量聚类的“好坏”.很难定义“足够类似”或“足够好”对此问题是相当主观的.相异度/相似度矩阵相似性用距离函数表示,通常记作 d(i,j)对于区间标度变量,二元变量,标称变量,序数和比例标度变量,距离函数的定义通常是很不相同的.根据应用和数据语义,不同的变量应赋予不同的权.,12,聚类分析的数据类型,区间标度变

7、量(Interval-scaled variables)二元变量(Binary variables)标称(名词性),序数,和比例标度变量(Nominal,ordinal,and ratio variables)混合类型变量(Variables of mixed types),13,区间标度变量,区间标度变量：一种粗略线形标度的连续度量为了避免度量单位的影响，数据标准化(1)计算平均绝对偏差:其中(2)计算标准化的度量值(z-score)使用平均绝对偏差比使用标准差更具有鲁棒性,14,对象之间的相似性/相异性,通常,使用距离来度量两个数据对象之间的相似性/相异性常用的距离包括:闵可夫斯基(Min

8、kowski)距离:其中 i=(xi1,xi2,xip)和 j=(xj1,xj2,xjp)是两个 p-维数据对象(q 正整数)如果q=1,d是曼哈坦(Manhattan)距离,15,对象之间的相似性/相异性,如果 q=2,d是欧几里德(Euclidean)距离:距离的性质非负性:d(i,j)0自身到自身的距离为0:d(i,i)=0对称性:d(i,j)=d(j,i)三角不等式:d(i,j)d(i,k)+d(k,j)也可以使用加权的距离,如加权的欧几里德距离,16,二元变量,二元变量(binary variable)只有两个状态0或1.0表示该变量为空,1表示该变量存在例如,描述病人的变量smok

9、er,1表示病人抽烟,而0表示病人不抽烟计算二元变量的相似度假定所有二元变量具有相同的权重,则得到一个两行两列的可能性表(contingency table),对象 i,对象 j,17,二元变量,对称的:二元变量的两个状态具有同等价值,并具有相同的权重例:性别是对称的二元变量恒定的相似度:基于对称的二元变量的相似度,当一些或全部二元变量编码改变时,计算结果不会发生变化对称的二元变量的相异度计算-简单匹配系数不对称的:二元变量的两个状态的输出不是同样重要例:疾病检查结果的肯定和否定.,18,二元变量(续),根据惯例,比较重要的输出结果是出现几率较小的例:HIV阳性是比较重要的结果,出现几率较小,

10、而HIV阴性(正常情况)出现几率较大通常,比较重要的输出结果编码为1,另一种结果编码为0两个都取1的情况(正匹配)比两个都取0的情况(负匹配)更有意义.-非恒定的相似度对于非对称的相似度,负匹配数目t被忽略.采用Jaccard系数,19,二元变量之间的相异度,例gender 是对称的其余都不是对称的Y和P的值设置为1,而 N的值设置为 0,20,标称变量-分类变量，名义变量,标称变量(Nominal variable)是二元变量的拓广,它可以取多于两种状态值,如,red,yellow,blue,green方法1:简单匹配m:状态取值匹配的变量数目,p:变量总数方法 2：（可以用非对称的二元变量

11、对标称变量编码）使用大量二元变量，对M个标称状态的每一个,创建一个新的二元变量.对于一个有特定状态值的对象,对应状态值的二元变量值置1,其余二元变量的值置0,21,序数型变量,序数型变量(ordinal variable)可以是离散的,也可以是连续的离散的序数型变量类似于标称变量,但序数型变量的M个状态是以有意义的序列排序 连续的序数型变量看起来像一个未知刻度的连续数据的集合.值的相对顺序是必要的,而其实际的大小则不重要 将区间标度变量的值域划分为有限个区间,从而将其值离散化,也可以得到序数型变量序数型变量的值可以映射为秩(rank).例如,假设变量f有Mf个状态,这些有序的状态定义了一个排列

12、1,Mf,22,序数型变量(续),相异度计算可以用类似于区间标度变量的方法处理设第i 个对象f 的值为 xif,用对应的值rif 替代xif,其中 rif 1,Mf 将每个变量的值域映射到0,1区间,以便每个变量都具有相同的权重:用下式替换rif 使用区间标度变量计算距离的方法计算相异度,z if作为第i 个对象f 的值,23,比例标度变量,比例标度变量(Ratio-scaled variable)非线性的刻度上取正的度量值，例如指数标度，近似地遵循如下的公式 AeBt 或Ae-Bt 相异度计算:采用与处理区间标度变量同样的方法 不是好的选择!(为什么?标度可能被扭曲)进行对数变换 yif=l

13、og(xif)将xif看作连续的序数型数据,将其秩作为区间标度值方法的选取取决于应用,但后两种方法比较有效,24,混合类型变量,数据库可能包含所有六种类型对称的二元变量,不对称的二元变量,标称的,序数的,区间的,比例标度的如何计算混合类型变量描述的对象的相异度?方法1:将变量按类型分组,对每种类型的变量单独进行聚类分析如果这些分析得到兼容的结果,这种方法是可行的在实际的应用中,这种方法行不通方法2:将所有的变量一起处理,只进行一次聚类分析.将不同类型的变量组合在单个相异度矩阵中,把所有变量转换到共同的值域区间0.0,1.0上,25,混合类型变量(续),假设数据集包含p个不同类型的变量，对象i

14、和j 之间的相异度d(i,j)定义为 其中,如果xif或xjf 缺失(即对象i 或对象j 没有变量f 的度量值)或者xif=xjf=0,且变量f 是不对称的二元变量,则指示项;否则,指示项变量f 对i 和j 之间相异度的计算方式与其具体类型有关 如果f 是二元或标称变量:如果 xif=xjf,dij(f)=0;否则 dij(f)=1,26,混合类型变量(续),如果f 是区间标度变量,使用规格化的距离如果f 是序数型或比例标度型变量计算秩rif 和 将 zif 作为区间标度变量对待,27,向量对象,向量x和y余弦度量Tanimoto系数,28,第8章.聚类分析,什么是聚类（Clustering）

15、分析?聚类分析中的数据类型主要聚类方法分类划分方法（Partitioning Methods）层次方法（Hierarchical Methods）基于密度的方法（Density-Based Methods）基于网格的方法（Grid-Based Methods）基于模型的聚类方法（Model-Based Clustering Methods）孤立点分析（Outlier Analysis）小结,29,主要聚类方法的分类,划分方法(Partitioning method):构造n个对象数据库D的划分,将其划分成k个聚类满足如下的要求：每个组至少包含一个对象每个对象必须属于且只属于一个组在某些模糊划分

16、技术中,第二个要求可以放宽 基本方法:首先创建一个初始划分.然后采用一种迭代的重定位技术,尝试通过在划分间移动对象来改进划分好的划分的一般准则:在同一个类中的对象之间尽可能“接近”或相关,而不同类中的对象之间尽可能“远离”或不同,30,主要聚类方法的分类(续),全局最优:穷举所有可能的划分 启发式方法:k-平均值(k-means)和 k-中心点(k-medoids)算法k-平均值(MacQueen67):每个簇用该簇中对象的平均值来表示 k-中心点或 PAM(Partition around medoids)(Kaufman&Rousseeuw87):每个簇用接近聚类中心的一个对象来表示 这些

17、启发式算法适合发现中小规模数据库中的球状聚类对于大规模数据库和处理任意形状的聚类,这些算法需要进一步扩展,31,主要聚类方法的分类(续),层次方法(Hierarchy method):对给定数据对象集合进行层次的分解 两种层次方法凝聚方法,也称为自底向上的方法:开始将每个对象作为单独的一个组;然后继续地合并相近的对象或组,直到所有的组合并为一个(层次的最上层),或者达到一个终止条件 分裂方法,也称为自顶向下的方法:开始将所有的对象置于一个簇;在迭代的每一步,一个簇被分裂为更小的簇,直到最终每个对象在单独的一个簇中,或者达到一个终止条件,32,主要聚类方法的分类(续),层次方法的缺点:一个步骤一

18、旦完成便不能被撤消.该规定可以避免考虑选择不同的组合,减少计算代价问题:不能更正错误的决定改进层次聚类结果的措施在每层划分中,仔细分析对象间的“联接”,例如CURE和Chameleon中的做法 综合层次凝聚和迭代的重定位方法。首先用自底向上的层次算法，然后用迭代的重定位来改进结果。例如在BIRCH中的方法,33,主要聚类方法的分类(续),基于密度的方法(Density-based method):基于密度函数基本思想:只要临近区域的密度(对象或数据点的数目)超过某个阀值,就继续聚类.也就是说,对给定类中的每个数据点,在一个给定范围的区域中必须至少包含一定数目的点 该方法可以用来过滤“噪音”数据

19、，发现任意形状的簇 DBSCAN是一个有代表性的基于密度的方法,它根据一个密度阀值来控制簇的增长OPTICS是另一个基于密度的方法,它为自动的,交互的聚类分析计算一个聚类顺序,34,主要聚类方法的分类(续),基于网格的方法(Grid-based method):把对象空间量化为有限数目的单元,形成了一个网格结构.所有的聚类操作都在这个网格结构(即量化的空间)上进行这种方法的主要优点是它的处理速度很快,其处理时间独立于数据对象的数目,只与量化空间中每一维的单元数目有关 STING是基于网格方法的一个典型例子CLIQUE和WaveCluster这两种算法既是基于网格的,又是基于密度的,35,主要聚

20、类方法的分类(续),基于模型的方法(Model-based Method):基于模型的方法为每个簇假定了一个模型,寻找数据对给定模型的最佳拟合,36,第6章.聚类分析,什么是聚类（Clustering）分析?聚类分析中的数据类型主要聚类方法分类划分方法（Partitioning Methods）层次方法（Hierarchical Methods）基于密度的方法（Density-Based Methods）基于网格的方法（Grid-Based Methods）基于模型的聚类方法（Model-Based Clustering Methods）孤立点分析（Outlier Analysis）小结,37

21、,划分方法,划分方法:构造n个对象数据库D的划分,将其划分成k个聚类给定 k,找k 个clusters 对于选定的划分标准它是最优的全局最优(Global optimal):枚举所有的划分启发式方法(Heuristic methods):k-平均(k-means)和k-中心点(k-medoids)算法k-平均(MacQueen67):每个簇用簇的重心(簇的平均值)表示k-中心点或PAM(Partition around medoids)(Kaufman&Rousseeuw87):每个簇用接近聚类中心的一个对象来表示,38,k-平均聚类算法,算法：k-平均(1)任意选择k个对象作为初始的簇中心；

22、(2)repeat(3)根据簇中对象的平均值,将每个对象(重新)赋给最类似的簇；(4)更新簇的平均值,即重新计算每个簇中对象的平均值；(5)until 不再发生变化 通常,采用平方误差准则作为收敛函数,其定义如下 其中,mi是簇Ci的平均值该准则试图使生成的结果簇尽可能紧凑,独立,39,k-平均聚类算法(续),例,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,K=2任意选择 K个对象作为初始聚类中心,将每个对象赋给最类似的中心,更新簇的平均值,重新赋值,更新簇的平均值,重新赋值,40,k-平均聚类算法(续),优点:相对有效性:O(tkn),其中 n

23、 是对象数目,k 是簇数目,t 是迭代次数;通常,k,t n.比较:PAM:O(k(n-k)2),CLARA:O(ks2+k(n-k)当结果簇是密集的，而簇与簇之间区别明显时，它的效果较好Comment:常常终止于局部最优.全局最优 可以使用诸如确定性的退火(deterministic annealing)和遗传算法(genetic algorithms)等技术得到,41,k-平均聚类算法(续),弱点只有在簇的平均值(mean)被定义的情况下才能使用.可能不适用于某些应用,例如涉及有分类属性的数据需要预先指顶簇的数目k,不能处理噪音数据和孤立点(outliers)不适合用来发现具有非凸形状(n

24、on-convex shapes)的簇,42,k-平均方法的变种,k-平均方法的变种,它们在以下方面有所不同初始k个平均值的选择相异度的计算计算聚类平均值的策略 较好的策略:先用层次凝聚算法决定簇的数目,并产生初始聚类,然后用迭代重定位改进聚类结果处理分类属性:k-模(k-modes)方法(Huang98)用模(modes众数)替代聚类的平均值使用新的相异性度量方法来处理分类对象 用基于频率的方法来修改聚类的模 k-原型(k-prototype)方法:k-平均和k-模的结合,处理具有数值和分类属性的数据,43,k-平均方法的变种(续),EM(Expectation Maximization,期

25、望最大)算法以另一种方式对k-means方法进行了扩展:不把对象分配给一个确定的簇,而是根据对象与簇之间隶属关系发生的概率来分派对象 怎样增强k-means算法的可扩展性？数据分成三种区域：可废弃的:一个对象与某个簇的隶属关系是确定的可压缩的:一个对象不是可废弃的,但属于某个紧密的子簇必须在主存:既不是可废弃的,又不是可压缩的迭代的算法只包含可压缩的对象和必须在主存中的对象的聚类特征,从而将一个基于二级存储的算法变成了基于主存的算法,44,k-中心点聚类方法,k-平均值算法对孤立点很敏感!因为具有特别大的值的对象可能显著地影响数据的分布.k-中心点(k-Medoids):不采用簇中对象的平均值

26、作为参照点,而是选用簇中位置最中心的对象,即中心点(medoid)作为参照点.,45,k-中心点聚类方法(续),找聚类中的代表对象(中心点)PAM(Partitioning Around Medoids,1987)首先为每个簇随意选择选择一个代表对象,剩余的对象根据其与代表对象的距离分配给最近的一个簇;然后反复地用非代表对象来替代代表对象，以改进聚类的质量 PAM 对于较小的数据集非常有效,但不能很好地扩展到大型数据集CLARA(Kaufmann&Rousseeuw,1990)抽样CLARANS(Ng&Han,1994):随机选样,46,k-中心点聚类方法(续),基本思想：首先为每个簇随意选择

27、选择一个代表对象;剩余的对象根据其与代表对象的距离分配给最近的一个簇然后反复地用非代表对象来替代代表对象,以改进聚类的质量聚类结果的质量用一个代价函数来估算,该函数评估了对象与其参照对象之间的平均相异度,47,k-中心点聚类方法(续),为了判定一个非代表对象Orandom 是否是当前一个代表对象Oj的好的替代,对于每一个非代表对象p,考虑下面的四种情况：第一种情况：p当前隶属于代表对象 Oj.如果Oj被Orandom所代替,且p离Oi最近,ij,那么p被重新分配给Oi 第二种情况：p当前隶属于代表对象 Oj.如果Oj 被Orandom代替,且p离Orandom最近,那么p被重新分配给Orand

28、om 第三种情况：p当前隶属于Oi，ij。如果Oj被Orandom代替，而p仍然离Oi最近，那么对象的隶属不发生变化 第四种情况：p当前隶属于Oi，ij。如果Oj被Orandom代替，且p离Orandom最近，那么p被重新分配给Orandom,48,k-中心点聚类方法(续),重新分配给Oi 2.重新分配给Orandom 3.不发生变化 4.重新分配给Orandom 数据对象+簇中心 替代前 替代后图8-3 k-中心点聚类代价函数的四种情况,+,+,+,Orandom,Oi,Oj,p,+,+,+,Orandom,Oi,Oj,p,+,+,+,Orandom,Oi,Oj,p,+,+,+,Orando

29、m,Oi,Oj,p,49,k-中心点聚类方法(续),算法:k-中心点(1)随机选择k个对象作为初始的代表对象；(2)repeat(3)指派每个剩余的对象给离它最近的代表对象所代表的簇；(4)随意地选择一个非代表对象Orandom；(5)计算用Orandom代替Oj的总代价S；(6)如果S0，则用Orandom替换Oj，形成新的k个代表对象的集合；(7)until 不发生变化,50,PAM,PAM(Partitioning Around Medoids)(Kaufman and Rousseeuw,1987)是最早提出的k-中心点聚类算法基本思想:随机选择k个代表对象反复地试图找出更好的代表对象

30、:分析所有可能的对象对，每个对中的一个对象被看作是代表对象,而另一个不是.对可能的各种组合,估算聚类结果的质量,51,PAM(续),Total Cost=20,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,K=2,Arbitrary choose k object as initial medoids,Assign each remaining object to nearest medoids,Randomly select a nonmedoid object,Oramdom,Compute total cost of swapping,Tot

31、al Cost=26,Swapping O and Oramdom If quality is improved.,Do loopUntil no change,52,PAM(续),当存在噪音和孤立点时,PAM 比 k-平均方法更健壮.这是因为中心点不象平均值那么容易被极端数据影响 PAM对于小数据集工作得很好,但不能很好地用于大数据集 每次迭代O(k(n-k)2)其中 n 是数据对象数目,k 是聚类数基于抽样的方法,CLARA(Clustering LARge Applications),53,CLARA(Clustering Large Applications)(1990),CLARA(

32、Kaufmann and Rousseeuw in 1990)不考虑整个数据集,而是选择数据的一小部分作为样本它从数据集中抽取多个样本集,对每个样本集使用PAM,并以最好的聚类作为输出优点:可以处理的数据集比 PAM大缺点:有效性依赖于样本集的大小基于样本的好的聚类并不一定是 整个数据集的好的聚类,样本可能发生倾斜 例如,Oi是最佳的k个中心点之一,但它不包含在样本中,CLARA将找不到最佳聚类,54,CLARANS(“Randomized”CLARA)(1994),CLARANS(A Clustering Algorithm based on Randomized Search)(Ng an

33、d Han94)CLARANS将采样技术和PAM结合起来CLARA在搜索的每个阶段有一个固定的样本CLARANS任何时候都不局限于固定样本,而是在搜索的每一步带一定随机性地抽取一个样本 聚类过程可以被描述为对一个图的搜索,图中的每个节点是一个潜在的解,也就是说 k medoids相邻节点：代表的集合只有一个对象不同在替换了一个代表对象后得到的聚类结果被称为当前聚类结果的邻居,55,CLARANS(续),如果一个更好的邻居被发现,CLARANS移到该邻居节点,处理过程重新开始,否则当前的聚类达到了一个局部最优如果找到了一个局部最优,CLARANS从随机选择的节点开始寻找新的局部最优实验显示CLA

34、RANS比PAM和CLARA更有效 CLARANS能够探测孤立点 聚焦技术和空间存取结构可以进一步改进它的性能(Ester et al.95),56,第6章.聚类分析,什么是聚类（Clustering）分析?聚类分析中的数据类型主要聚类方法分类划分方法（Partitioning Methods）层次方法（Hierarchical Methods）基于密度的方法（Density-Based Methods）基于网格的方法（Grid-Based Methods）基于模型的聚类方法（Model-Based Clustering Methods）孤立点分析（Outlier Analysis）小结,57

35、,层次方法,层次的聚类方法将数据对象组成一棵聚类的树根据层次分解是自底向上,还是自顶向下形成,层次的聚类方法可以进一步分为凝聚的(agglomerative)和分裂的(divisive)层次聚类 纯粹的层次聚类方法的聚类质量受限于如下特点：一旦一个合并或分裂被执行，就不能修正 最近的研究集中于凝聚层次聚类和迭代重定位方法的集成 使用距离矩阵作为聚类标准.该方法不需要输入聚类数目 k,但需要终止条件,58,层次方法(续),凝聚的(agglomerative)和分裂的(divisive)层次聚类图示,59,AGNES(Agglomerative Nesting),由 Kaufmann和Rousse

36、euw提出(1990)已在一些统计分析软件包中实现.如 Splus使用单链接(Single-Link)方法和相异度矩阵 合并具有最小相异度的节点以非递减的方式继续最终所有的节点属于同一个簇,60,DIANA(Divisive Analysis),由 Kaufmann和Rousseeuw提出(1990)已在一些统计分析软件包中实现.如 Splus是 AGNES的逆最终每个节点自己形成一个簇,61,层次方法(续),四个广泛采用的簇间距离度量方法 最小距离：dmin(Ci,Cj)=min pCi,pCj|p-p|最大距离：dmax(Ci,Cj)=max pCi,pCj|p-p|平均值的距离：dmea

37、n(Ci,Cj)=|mi-mj|平均距离：davg(Ci,Cj)=pCi pCj|p-p|/ninj其中,|p-p|是两个对象p和p之间的距离mi是簇Ci 的平均值，ni是簇Ci中对象的数目,62,层次方法(续),层次聚类的主要缺点不具有很好的可伸缩性:时间复杂性至少是 O(n2),其中 n 对象总数合并或分裂的决定需要检查和估算大量的对象或簇 不能撤消已做的处理,聚类之间不能交换对象.如果某一步没有很好地选择合并或分裂的决定,可能会导致低质量的聚类结果,63,层次方法(续),改进层次方法的聚类质量的方法:将层次聚类和其他的聚类技术进行集成,形成多阶段聚类 BIRCH(1996):使用 CF-

38、tree对对象进行层次划分,然后采用其他的聚类算法对聚类结果进行求精 ROCK1999：基于簇间的互联性进行合并CHAMELEON(1999):使用动态模型进行层次聚类CURE(1998):采用固定数目的代表对象来表示每个簇，然后依据一个指定的收缩因子向着聚类中心对它们进行收缩,64,BIRCH(1996),Birch(Balanced Iterative Reducing and Clustering using Hierarchies):利用层次方法的平衡迭代归约和聚类由Zhang,Ramakrishnan和Livny 提出(SIGMOD96)两个重要概念聚类特征(Clustering F

39、eature,CF)聚类特征树(Clustering Feature Tree,CF树)聚类特征聚类特征(CF)是一个三元组，给出对象子类的信息的汇总描述 设某个子类中有N个d维的点或对象oI，则该子类的CF定义如下,65,聚类特征,CF=(5,(16,30),(54,190),(3,4)(2,6)(4,5)(4,7)(3,8),66,BIRCH的CF树,聚类特征 从统计学的观点来看，聚类特征是对给定子类统计汇总:子聚类的0阶,1阶和 2阶矩(moments)记录了计算聚类和有效利用存储的关键度量,并有效地利用了存储,因为它汇总了关于子类的信息，而不是存储所有的对象 CF 树是高度平衡的树，它

40、存储了层次聚类的聚类特征 树中的非叶节点有后代或“孩子”非叶节点存储了其孩子的CF的总和，即汇总了关于其孩子的聚类信息 CF树有两个参数-影响CF树的大小分支因子B:定义非树叶节点的孩子的最大个数阈值T:给出了存储在树的叶子节点中的子类的最大直径,67,CF Tree,CF1,child1,CF3,child3,CF2,child2,CF5,child5,CF1,CF2,CF6,prev,next,CF1,CF2,CF4,prev,next,B=7T=6,Root,Non-leaf node,Leaf node,Leaf node,68,BIRCH(续),BIRCH增量地构造一棵 CF 树(C

41、lustering Feature Tree),CF树是一个层次数据结构,用于多阶段聚类阶段 1:扫描 DB,建立一棵初始的存放在内存的 CF树(数据的多层压缩,试图保留数据内在的聚类结构)阶段 2:使用某种聚类算法对CF树的叶节点进行聚类.在阶段一，随着对象被插入,CF树被动态地构造.一个对象被插入到最近的叶子条目(子聚类).如果在插入后存储在叶子节点中的子类的直径大于阀值,那么该叶子节点(可能还有其他节点)被分裂.新对象插入后.关于该对象的信息向着树根传递-类似于B+树构建中的插入和节点分裂 通过修改阀值，CF树的大小可以改变,69,BIRCH(续),重建过程从旧树的叶子节点建造一个新树。

42、这样，重建树的过程不需要重读所有的对象-建树只需读一次数据 在阶段二被采用任何聚类算法，例如典型的划分方法BIRCH的性能支持增量聚类线性可伸缩性:计算复杂性O(n),单遍扫描,附加的扫描可以改善聚类质量较好的聚类质量缺点只能处理数值数据对数据的输入次序敏感Cf树结点不总是对应于用户考虑的自然簇(参数B和T)簇非球形时效果不好(使用半径/直径控制簇边界),70,CURE(1998),CURE(Clustering Using REpresentatives):由 Guha,Rastogi 和 Shim提出(1998)绝大多数聚类算法或者擅长处理球形和相似大小的聚类，或者在存在孤立点时变得比较脆

43、弱 CURE解决了偏好球形的问题，在处理孤立点上也更加健壮 CURE采用了一种新的层次聚类算法选择基于质心和基于代表对象方法之间的中间策略.它不用单个质心或对象来代表一个簇,而是选择了数据空间中固定数目的具有代表性的点 首先选择簇中分散的对象,然后根据一个特定的收缩因子向簇中心“收缩”,71,CURE(续),每个簇有多于一个的代表点使得CURE可以适应非球形的任意形状的聚类簇的收缩或凝聚可以有助于控制孤立点的影响 CURE的优点CURE对孤立点的处理更加健壮能够识别非球形和大小变化较大的簇对于大规模数据库,它也具有良好的伸缩性,而且没有牺牲聚类质量 针对大型数据库,CURE采用了随机取样和划分

44、两种方法的组合首先划分一个随机样本,每个划分被部分聚类然后对这些结果簇聚类,产生希望的结果,72,Cure(续),CURE算法核心:从源数据对象中抽取一个随机样本S.将样本S分割为p个划分,每个的大小为 s/p将每个划分局部地聚类成 s/pq 个簇删除孤立点通过随机选样如果一个簇增长太慢,就删除它.对局部聚类进行聚类.用相应的簇标签来标记数据,73,CURE:例,s=50p=2s/p=25,x,x,s/pq=5,74,CURE:例(续),多个代表点向重心 以因子移动,进行收缩或凝聚多个代表点描述了每个簇的形状,75,对分类数据聚类:ROCK,ROCK(RObust Clustering usi

45、ng linKs)由S.Guha,R.Rastogi,K.Shim提出(ICDE99).使用链接(link)度量相似性/接近性链接：两个对象间共同的近邻的数目不是基于距离的计算复杂性:基本思想:相似性函数:Jaccard系数设 T1=1,2,3,T2=3,4,5,76,Rock(续),两个点pi和pj是近邻，如果sim(pi,pj)=用户指定阈值link(pi,pj)是两个点pi和pj共同的近邻的数目两个簇Ci和Cj的互连性被定义为两个簇间交叉链（cross link）的数目 ROCK首先根据相似度阀值和共享近邻的概念，从给定的数据相似度矩阵构建一个稀疏的图，然后在这个稀疏图上运行一个层次聚类

46、算法,77,CHAMELEON,CHAMELEON:一个利用动态模型的层次聚类算法(Hierarchical clustering using dynamic modeling)由G.Karypis,E.H.Han,and V.Kumar99 提出对CURE和ROCK缺点的观察:Cure忽略了关于两个不同簇中对象的聚集互连性的信息Rock强调对象间互连性,却忽略了关于对象间近似度的信息 CHAMELEON基于动态模型度量相似性如果两个簇间的互连性和近似度与簇内部对象间的互连性和近似度高度相关,则合并这两个簇,78,CHAMELEON(续),两阶段算法使用图划分算法:将数据对象聚类为大量相对较小

47、的子类逐步用图划分算法把k近邻图分成 相对较小de子簇，最小化割边。使用凝聚的层次聚类算法：通过反复地合并子类来找到真正的结果簇既考虑互连性,又考虑簇间的近似度,特别是簇内部的特征,来确定最相似的子类.这样,它不依赖于静态的用户提供的模型,能够自动地适应被合并的簇的内部特征 割边最小化簇c划分为两个子簇Ci和Cj时需要割断的边的加权和最小。割边用ECCi，Cj表示，评估Ci和Cj的簇间的绝对互联性。,79,CHAMELEON图示,构造稀疏图,划分图,合并划分,最终的簇,Data Set,K-最近邻居图,80,CHAMELEON(续),k-最近邻图Gk:图中的每个点代表一个数据对象,如果一个对象

48、是另一个对象的k个最类似的对象之一,在这两个点之间存在一条边 k-最近邻图Gk动态地捕捉邻域的概念：一个对象的邻域半径由对象所在区域的密度所决定在一个密集区域,邻域的定义范围相对狭窄;在一个稀疏区域,它的定义范围相对较宽 区域的密度作为边的权重被记录下来一个密集区域的边趋向于比稀疏区域的边有更大的权重,81,CHAMELEON(续),Chameleon通过两个簇的相对互连性RI(Ci,Cj)和相对接近度RC(Ci,Cj)来决定簇间的相似度 RI(Ci,Cj)定义为Ci和Cj之间的绝对互联性关于两个簇的内部互连性的规范化 其中,ECCi，Cj是包含Ci和Cj的簇分裂为Ci和Cj的割边,ECCi（

49、或ECCj）是它的最小截断等分线的大小（即将图划分为两个大致相等的部分需要切断的边的加权和）,82,CHAMELEON(续),RC(Ci,Cj)定义为Ci和Cj之间的绝对接近度关于两个簇的内部接近度的规范化 其中,是连接Ci和Cj顶点的边的平均权重 是Ci的最小二等分的边的平均权重,83,第6章.聚类分析,什么是聚类（Clustering）分析?聚类分析中的数据类型主要聚类方法分类划分方法（Partitioning Methods）层次方法（Hierarchical Methods）基于密度的方法（Density-Based Methods）基于网格的方法（Grid-Based Methods

50、）基于模型的聚类方法（Model-Based Clustering Methods）孤立点分析（Outlier Analysis）小结,84,基于密度的方法,基于密度聚类(Density-Based Clustering)主要特点:发现任意形状的聚类处理噪音一遍扫描需要密度参数作为终止条件一些有趣的研究:DBSCAN:Ester,et al.(KDD96)OPTICS:Ankerst,et al(SIGMOD99).DENCLUE:Hinneburg&D.Keim(KDD98)CLIQUE:Agrawal,et al.(SIGMOD98),85,密度概念,-邻域：给定对象半径内的领域核心对象(