聚类分析—层次聚类.ppt

智能数据挖掘智能数据挖掘Topic3-聚类分析聚类分析层次聚类方法层次聚类方法（Hierarchical Methods）层次方法层次方法n层次的聚类方法将数据对象组成一棵聚类的树层次的聚类方法将数据对象组成一棵聚类的树n根据层次分解是自底向上根据层次分解是自底向上,还是自顶向下形成还是自顶向下形成,层次的聚类方层次的聚类方法可以进一步分为法可以进一步分为凝聚的凝聚的(agglomerative)和和分裂的分裂的(divisive)层次聚类层次聚类 n纯粹的层次聚类方法的聚类质量受限于如下特点：一旦一个纯粹的层次聚类方法的聚类质量受限于如下特点：一旦一个合并或分裂被执行，就不能修正合并或分裂被执行，就不能修正 n最近的研究集中于凝聚层次聚类和迭代最近的研究集中于凝聚层次聚类和迭代重定位方法重定位方法的集成的集成 n使用使用距离矩阵距离矩阵作为聚类标准作为聚类标准.该方法不需要输入聚类数目该方法不需要输入聚类数目 k,但需要终止条件但需要终止条件2024/5/25周六层次方法层次方法(续续)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)2024/5/25周六AGNES(Agglomerative Nesting)n由由 Kaufmann和和Rousseeuw提出提出(1990)n已在一些统计分析软件包中实现已在一些统计分析软件包中实现.如如 Splusn使用单链接使用单链接(Single-Link)方法和相异度矩阵方法和相异度矩阵 n合并具有最小相异度的节点合并具有最小相异度的节点n以非递减的方式继续以非递减的方式继续n最终所有的节点属于同一个簇最终所有的节点属于同一个簇2024/5/25周六DIANA(Divisive Analysis)n由由 Kaufmann和和Rousseeuw提出提出(1990)n已在一些统计分析软件包中实现已在一些统计分析软件包中实现.如如 Splusn是是 AGNES的逆的逆n最终每个节点自己形成一个簇最终每个节点自己形成一个簇2024/5/25周六层次方法层次方法(续续)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平均距离平均距离(簇的直径D)：davg(Ci,Cj)=pCi pCj|p-p|/n ni in nj其中其中,|p-p|是两个对象是两个对象p和和p之间的距离之间的距离mi是簇是簇Ci 的平均值，的平均值，ni是簇是簇Ci中对象的数目中对象的数目 2024/5/25周六层次方法层次方法(续续)n层次聚类的主要缺点层次聚类的主要缺点n不具有很好的可伸缩性不具有很好的可伸缩性:时间复杂性至少是时间复杂性至少是 O(n2),其中其中 n 对象总数对象总数n合并或分裂的决定需要检查和估算大量的对象或簇合并或分裂的决定需要检查和估算大量的对象或簇 n不能撤消已做的处理不能撤消已做的处理,聚类之间不能交换对象聚类之间不能交换对象.如果某一步没有很好如果某一步没有很好地选择合并或分裂的决定地选择合并或分裂的决定,可能会导致低质量的聚类结果可能会导致低质量的聚类结果 2024/5/25周六层次方法层次方法(续续)n改进层次方法的聚类质量的方法改进层次方法的聚类质量的方法:将层次聚类和其他的聚类将层次聚类和其他的聚类技术进行集成技术进行集成,形成多阶段聚类形成多阶段聚类 nBIRCH(1996):使用使用 CF-tree对对象进行层次划分对对象进行层次划分,然后采用其他的聚然后采用其他的聚类算法对聚类结果进行求精类算法对聚类结果进行求精 nROCK1999：基于簇间的互联性进行合并：基于簇间的互联性进行合并nCHAMELEON(1999):使用动态模型进行层次聚类使用动态模型进行层次聚类nCURE(1998):采用固定数目的代表对象来表示每个簇，然后依据一个采用固定数目的代表对象来表示每个簇，然后依据一个指定的收缩因子向着聚类中心对它们进行收缩指定的收缩因子向着聚类中心对它们进行收缩2024/5/25周六BIRCH(1996)nBirch(Balanced Iterative Reducing and Clustering using Hierarchies):利用层次方法的平衡迭代归约和聚类由利用层次方法的平衡迭代归约和聚类由Zhang,Ramakrishnan和和Livny 提出提出(SIGMOD96),该算法的特点是能利用有限的内存资源完成对大数该算法的特点是能利用有限的内存资源完成对大数据集的高质量的聚类，同时通过单遍扫描数据集能最小化据集的高质量的聚类，同时通过单遍扫描数据集能最小化I/O代价。代价。n两个重要概念两个重要概念n聚类特征聚类特征(Clustering Feature,CF)n聚类特征树聚类特征树(Clustering Feature Tree,CF树树)n聚类特征聚类特征n聚类特征聚类特征(CF)是一个三元组，是一个三元组，给出给出对象子类的信息对象子类的信息的汇总的汇总描述描述 n设某个子类中有设某个子类中有N个个d维的点或对象维的点或对象oI，则该子类的则该子类的CF定义如下定义如下 2024/5/25周六聚类特征聚类特征Clustering Feature:CF=(N,LS,SS)N:数据点数目数据点数目LS:Ni=1 XiSS:Ni=1Xi2CF=(5,(16,30),(54,190)(3,4)(2,6)(4,5)(4,7)(3,8)2024/5/25周六聚类特征聚类特征n假定簇C1中有两个点（1，2，3），（3，2，1），簇C2有三个点（1，1，2），（2，2，1），（2，1，2），簇3由C1和C2构成，则：nCF1=（2，（1+3，2+2，3+1），（）=（2，（4，4，4），（10，8，10）nCF2=（3，（1+2+2，1+2+1，2+1+2），（）=（3，（5，4，5），（9，6，9）n因此得到CF3为：nCF3=（2+3，（4+5，4+4，4+5），（10+9，8+6，10+9）=（5，（9，8，9），（19，14，19）2024/5/25周六簇的质心和簇的半径。n假如一个簇中包含n个数据点：Xi，i=1,2,3.n.，则质心C和半径R计算公式如下：nC=(X1+X2+.+Xn)/n，（这里X1+X2+.+Xn是向量加）nR=(|X1-C|2+|X2-C|2+.+|Xn-C|2)/nn其中，簇半径表示簇中所有点到簇质心的平均距离。CF中存储的是簇中所有数据点的特性的统计和，所以当我们把一个数据点加入某个簇的时候，那么这个数据点的详细特征，例如属性值，就丢失了，由于这个特征，BIRCH聚类可以在很大程度上对数据集进行压缩。2024/5/25周六n有意思的是簇中心、簇半径、簇直径以及两簇之间的距离D0到D3都可以由CF来计算，比如n簇直径n簇间距离n这里的N，LS和SS是指两簇合并后大簇的N，LS和SS。所谓两簇合并只需要两个对应的CF相加那可2024/5/25周六BIRCH的的CF树树n聚类特征聚类特征 n从统计学的观点来看，聚类特征是对给定子类统计汇总从统计学的观点来看，聚类特征是对给定子类统计汇总:子聚类的子聚类的0阶阶,1阶和阶和 2阶矩阶矩(moments)n记录了计算聚类和有效利用存储的关键度量记录了计算聚类和有效利用存储的关键度量,并有效地利用了存储并有效地利用了存储,因为它汇总了关于子类的信息，而不是存储所有的对象因为它汇总了关于子类的信息，而不是存储所有的对象 CF 树是高度平衡的树，它存储了层次聚类的聚类特征树是高度平衡的树，它存储了层次聚类的聚类特征 n树中的非叶节点有后代或树中的非叶节点有后代或“孩子孩子”n非叶节点存储了其孩子的非叶节点存储了其孩子的CF的总和，即汇总了关于其孩子的聚类信的总和，即汇总了关于其孩子的聚类信息息 nCF树有两个参数树有两个参数-影响影响CF树的大小树的大小n分支因子分支因子B:定义非树叶节点的孩子的最大个数定义非树叶节点的孩子的最大个数n阈值阈值T:给出了存储在树的叶子节点中的子类的最大直径给出了存储在树的叶子节点中的子类的最大直径 2024/5/25周六nCFtree的结构类似于一棵B-树，它有3个参数：内部节点平衡因子B，叶节点平衡因子L，簇直径阈值T。树中每个Nlonleaf节点最多包含B个孩子节点，Leaf最多只能有L个MinCluster（初始划分子簇），而一个MinCluster的直径不能超过T。n例如，一棵高度为3，B为6，L为5的一棵CF树的例子如图所示：2024/5/25周六CF树的样子2024/5/25周六CF TreeCF1child1CF3child3CF2child2CF6child6CF1child1CF3child3CF2child2CF5child5CF1CF2CF6prevnextCF1CF2CF4prevnextB=5L=6RootNon-leaf nodeLeaf nodeLeaf node2024/5/25周六CF树构造过程n(1)从根节点开始，自上而下选择最近的孩子节点n(2)到达叶子节点后，检查最近的元组CFi能否吸收此数据点n是，更新CF值n否，是否可以添加一个新的元组n是，添加一个新的元组n否则，分裂最远的一对元组，作为种子，按最近距离重新分配其它元组n(3)更新每个非叶节点的CF信息，如果分裂节点，在父节点中插入新的元组，检查分裂，直到root2024/5/25周六构造CF树n算法起初，我们扫描数据库，拿到第一个datapointinstance-（1,2,3）,我们创建一个空的Leaf和MinCluster，把点（1,2,3）的id值放入Mincluster，更新MinCluster的CF值为（1,（1,2,3），（1,4,9），把MinCluster作为Leaf的一个孩子，更新Leaf的CF值为（1,（1,2,3），（1,4,9）。实际上只要往树中放入一个CF（这里我们用CF作为Nonleaf、Leaf、MinCluster的统称），就要更新从Root到该叶子节点的路径上所有节点的CF值。2024/5/25周六插入一个节点n当又有一个数据点要插入树中时，把这个点封装为一个MinCluster（这样它就有了一个CF值），把新到的数据点记为CF_new，我们拿到树的根节点的各个孩子节点的CF值，根据D2来找到CF_new与哪个节点最近，就把CF_new加入那个子树上面去。这是一个递归的过程。递归的终止点是要把CF_new加入到一个MinCluster中，如果加入之后MinCluster的直径没有超过T，则直接加入，否则譔CF_new要单独作为一个簇，成为MinCluster的兄弟结点。插入之后注意更新该节点及其所有祖先节点的CF值。2024/5/25周六节点分裂n插入新节点后，可能有些节点的孩子数大于了B（或L），此时该节点要分裂。对于Leaf，它现在有L+1个MinCluster，我们要新创建一个Leaf，使它作为原Leaf的兄弟结点，同时注意每新创建一个Leaf都要把它插入到双向链表中。L+1个MinCluster要分到这两个Leaf中，怎么分呢？找出这L+1个MinCluster中距离最远的两个Cluster（根据D2），剩下的Cluster看离哪个近就跟谁站在一起。分好后更新两个Leaf的CF值，其祖先节点的CF值没有变化，不需要更新。这可能导致祖先节点的递归分裂，因为Leaf分裂后恰好其父节点的孩子数超过了B。Nonleaf的分裂方法与Leaf的相似，只不过产生新的Nonleaf后不需要把它放入一个双向链表中。如果是树的根节点要分裂，则树的高度加1。2024/5/25周六Birch算法的阶段：n阶段一：扫描数据库，构造一颗CF树，并定义相关阈值，把稠密数据分成簇。n阶段二：对CF树进行压缩，通过改变T值，将部分簇进行压缩合并，建立一个更小的CF树。n阶段三：采用其他的聚类算法对其叶节点进行聚类，将稀疏的簇当作离群值进行删除，补救由于输入顺序和页面大小带来的分裂。n阶段四：通过上阶段得出聚类质心，将其作为种子节点，将其他对象分配给质心，构成新的聚类。2024/5/25周六BIRCH算法流程如下图所示：nnBIRCH算法流程如下图所示：2024/5/25周六BIRCH(续续)n重建过程从旧树的叶子节点建造一个新树。这样，重建树的过程不需要重读重建过程从旧树的叶子节点建造一个新树。这样，重建树的过程不需要重读所有的对象所有的对象-建树只需读一次数据建树只需读一次数据 n在阶段三和四采用任何聚类算法，例如典型的划分方法在阶段三和四采用任何聚类算法，例如典型的划分方法nBIRCH的性能的性能n支持增量聚类：因为它对每一个数据点的聚类的决策都是基于当前支持增量聚类：因为它对每一个数据点的聚类的决策都是基于当前已经处理过的数据点，而不是基于全局的数据点。已经处理过的数据点，而不是基于全局的数据点。n线性可伸缩性线性可伸缩性:计算复杂性计算复杂性O(n),单遍扫描单遍扫描,附加的扫描可以改善聚附加的扫描可以改善聚类质量类质量n较好的聚类质量较好的聚类质量n缺点缺点n只能处理数值数据只能处理数值数据n对数据的输入次序敏感对数据的输入次序敏感nCF树结点不总是对应于树结点不总是对应于用户考虑的用户考虑的自然簇自然簇(参数参数B和和T)n簇非球形时效果不好簇非球形时效果不好(使用半径使用半径/直径控制簇边界直径控制簇边界)2024/5/25周六CURE(1998)nCURE(Clustering Using REpresentatives):由由 Guha,Rastogi 和和 Shim提出提出(1998)n绝大多数聚类算法或者擅长处理球形和相似大小的聚类，或绝大多数聚类算法或者擅长处理球形和相似大小的聚类，或者在存在孤立点时变得比较脆弱者在存在孤立点时变得比较脆弱 nCURE解决了偏好球形的问题，在处理孤立点上也更加健壮解决了偏好球形的问题，在处理孤立点上也更加健壮 nCURE采用了一种新的层次聚类算法采用了一种新的层次聚类算法n选择基于质心和基于代表对象方法之间的中间策略选择基于质心和基于代表对象方法之间的中间策略.它不用单个质心它不用单个质心或对象来代表一个簇或对象来代表一个簇,而是选择了数据空间中固定数目的具有代表性而是选择了数据空间中固定数目的具有代表性的点的点 n首先选择簇中分散的对象首先选择簇中分散的对象,然后根据一个特定的收缩因子向簇中心然后根据一个特定的收缩因子向簇中心“收缩收缩”2024/5/25周六CURE(续续)n每个簇有多于一个的代表点使得每个簇有多于一个的代表点使得CURE可以适应非可以适应非球形的任意形状的聚类球形的任意形状的聚类n簇的收缩或凝聚可以有助于控制孤立点的影响簇的收缩或凝聚可以有助于控制孤立点的影响 nCURE的优点的优点nCURE对孤立点的处理更加健壮对孤立点的处理更加健壮n能够识别非球形和大小变化较大的簇能够识别非球形和大小变化较大的簇n对于大规模数据库对于大规模数据库,它也具有良好的伸缩性它也具有良好的伸缩性,而且没有牺牲聚类质量而且没有牺牲聚类质量 n针对大型数据库针对大型数据库,CURE采用了随机取样和划分两采用了随机取样和划分两种方法的组合种方法的组合n首先划分一个随机样本首先划分一个随机样本,每个划分被部分聚类每个划分被部分聚类n然后对这些结果簇聚类然后对这些结果簇聚类,产生希望的结果产生希望的结果 2024/5/25周六Cure(续续)nCURE算法核心算法核心:n从源数据对象中抽取一个随机样本集从源数据对象中抽取一个随机样本集S.n将样本将样本S分割为分割为p个划分个划分,每个的大小为每个的大小为 s/pn将每个划分局部地聚类成将每个划分局部地聚类成 s/pq 个簇个簇n删除孤立点删除孤立点n通过随机选样通过随机选样n如果一个簇增长太慢如果一个簇增长太慢,就删除它就删除它.n对局部聚类进行聚类对局部聚类进行聚类.n用相应的簇标签来标记数据用相应的簇标签来标记数据 2024/5/25周六CURE:例例ns=50np=2ns/p=25xxxyyyyxyxns/pq=52024/5/25周六CURE:例例(续续)n多个代表点向重心多个代表点向重心 以因子以因子 移动移动,进行收缩或凝聚进行收缩或凝聚n多个代表点描述了每个簇的形状多个代表点描述了每个簇的形状xyxy2024/5/25周六对分类数据聚类对分类数据聚类:ROCKnROCK(RObust Clustering using linKs)由由S.Guha,R.Rastogi,K.Shim提出提出(ICDE99).n使用使用链接链接(link)度量度量相似性相似性/接近性接近性n链接：两个对象间共同的近邻的数目链接：两个对象间共同的近邻的数目n不是基于距离的不是基于距离的n计算复杂性计算复杂性:n基本思想基本思想:n相似性函数相似性函数:Jaccard系数系数设设 T1=1,2,3,T2=3,4,52024/5/25周六Rock(续续)n两个点两个点pi和和pj是近邻，如果是近邻，如果sim(pi,pj)=用户指定阈值用户指定阈值nlink(pi,pj)是两个点是两个点pi和和pj共同的近邻的数目共同的近邻的数目n两个簇两个簇Ci和和Cj的互连性被定义为两个簇间交叉链（的互连性被定义为两个簇间交叉链（cross link）的数目的数目 nROCK首先根据相似度阀值和共享近邻的概念，从给定的首先根据相似度阀值和共享近邻的概念，从给定的数据相似度矩阵构建一个稀疏的图，然后在这个稀疏图上数据相似度矩阵构建一个稀疏的图，然后在这个稀疏图上运行一个层次聚类算法运行一个层次聚类算法 2024/5/25周六CHAMELEONnCHAMELEON:一个利用动态模型的层次聚类算法一个利用动态模型的层次聚类算法(Hierarchical clustering using dynamic modeling)由由G.Karypis,E.H.Han,and V.Kumar99 提出提出n对对CURE和和ROCK缺点的观察缺点的观察:nCure忽略了关于两个不同簇中对象的聚集互连性的信息忽略了关于两个不同簇中对象的聚集互连性的信息nRock强调对象间互连性强调对象间互连性,却忽略了关于对象间近似度的信息却忽略了关于对象间近似度的信息 nCHAMELEON基于动态模型度量相似性基于动态模型度量相似性n如果两个簇间的互连性和近似度与簇内部对象间的互连性和近似度如果两个簇间的互连性和近似度与簇内部对象间的互连性和近似度高度相关高度相关,则合并这两个簇则合并这两个簇 2024/5/25周六CHAMELEON(续续)n两阶段算法两阶段算法1.使用图划分算法使用图划分算法:将数据对象聚类为大量相对较小的子类将数据对象聚类为大量相对较小的子类逐步用图划分算法把逐步用图划分算法把k近邻图分成近邻图分成 相对较小相对较小de子簇，子簇，最小化割边最小化割边。2.使用凝聚的层次聚类算法：通过反复地合并子类来找到真正的结果使用凝聚的层次聚类算法：通过反复地合并子类来找到真正的结果簇簇n既考虑互连性既考虑互连性,又考虑簇间的近似度又考虑簇间的近似度,特别是簇内部的特征特别是簇内部的特征,来确定最相似的子类来确定最相似的子类.n这样这样,它不依赖于静态的用户提供的模型它不依赖于静态的用户提供的模型,能够自动地适能够自动地适应被合并的簇的内部特征应被合并的簇的内部特征 n割边最小化割边最小化簇簇c划分为两个子簇划分为两个子簇Ci和和Cj时需要割断的边的加权和时需要割断的边的加权和最小。最小。n割边用割边用ECCi，Cj表示，评估表示，评估Ci和和Cj的簇间的的簇间的绝对互联性绝对互联性。2024/5/25周六CHAMELEON图示图示构造稀疏图构造稀疏图划分图划分图合并划分合并划分最终的簇最终的簇Data SetK-最近邻居图最近邻居图2024/5/25周六CHAMELEON(续续)nk-最近邻图最近邻图Gk:图中的每个点代表一个数据对象图中的每个点代表一个数据对象,如果一个对如果一个对象是另一个对象的象是另一个对象的k个最类似的对象之一个最类似的对象之一,在这两个点之间存在这两个点之间存在一条边在一条边 nk-最近邻图最近邻图Gk动态地捕捉邻域的概念：一个对象的邻域半径动态地捕捉邻域的概念：一个对象的邻域半径由对象所在区域的密度所决定由对象所在区域的密度所决定n在一个密集区域在一个密集区域,邻域的定义范围相对狭窄邻域的定义范围相对狭窄;在一个稀疏区域在一个稀疏区域,它的定它的定义范围相对较宽义范围相对较宽 n区域的密度作为边的权重被记录下来区域的密度作为边的权重被记录下来n一个密集区域的边趋向于比稀疏区域的边有更大的权重一个密集区域的边趋向于比稀疏区域的边有更大的权重 2024/5/25周六CHAMELEON(续续)nChameleon通过两个簇的通过两个簇的相对互连性相对互连性RI(Ci,Cj)和和相对接近度相对接近度RC(Ci,Cj)来决定簇间的相似度来决定簇间的相似度 nRI(Ci,Cj)定义为定义为Ci和和Cj之间的绝对互联性关于两个簇的内部互连性的之间的绝对互联性关于两个簇的内部互连性的规范化规范化 其中其中,ECCi，Cj是包含是包含Ci和和Cj的簇分裂为的簇分裂为Ci和和Cj的割边的割边,ECCi（或或ECCj）是它的最小截断等分线的大小（即将图划分为两是它的最小截断等分线的大小（即将图划分为两个大致相等的部分需要切断的边的加权和）个大致相等的部分需要切断的边的加权和）2024/5/25周六CHAMELEON(续续)nRC(Ci,Cj)定义为定义为Ci和和Cj之间的绝对接近度关于两个簇的内之间的绝对接近度关于两个簇的内部接近度的规范化部接近度的规范化 其中其中,是是连接连接Ci和和Cj顶点的边的平均权重顶点的边的平均权重 是是Ci的最小二等分的边的平均权重的最小二等分的边的平均权重 2024/5/25周六 作业（作业（Due date：11月月9日）日）2024/5/25周六专题思路：把搜下来的网页进行聚类，将聚类结果显示给用户，用户可以选择其中的一个类，标为关注，类的关键词作为主题，用户就可以跟踪这主题、了解主题的文章的情感（就是其它部分的功能）