数据挖掘层次聚类.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,7.5,层次聚类方法,层次聚类方法概述,层次聚类方法将数据对象组成一棵聚类树根据层次分解是自底向上（合并）还是自顶向下（分裂），进一步分为凝聚的和分裂的层次聚类方法概述,凝聚的层次聚类：一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足分裂的层次聚类：采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件层次凝聚的代表是,AGNES,算法层次分裂的代表是,DIANA,算法簇间距离,最小距离,簇间距离,最大距离,簇间距离,平均距离,簇间距离,均值距离,AGNES,算法,AGNES(AGglomerative NESting),算法最初将每个对象作为一个簇，然后这些簇根据某些准则被一步步地合并两个簇间的相似度由这两个不同簇中距离最近的数据点对的相似度来确定聚类的合并过程反复进行直到所有的对象最终满足簇数目AGNES,算法,输入：,n,个对象，终止条件簇的数目,k,。

输出：,k,个簇，达到终止条件规定簇数目1),将每个对象当成一个初始簇；,(2)REPEAT,(3),根据两个簇中最近的数据点找到最近的两个簇；,(4),合并两个簇，生成新的簇的集合；,(5)UNTIL,达到定义的簇的数目；,AGNES,算法例题,序号 属性,1,属性,2,1 1 1,2 1 2,3 2 1,4 2 2,5 3 4,6 3 5,7 4 4,8 4 5,第,1,步：根据初始簇计算每个簇之间的距离，随机找出距离最小的两个簇，进行合并，最小距离为,1,，合并后,1,2,两个点合并为一个簇第,2,步：对上一次合并后的簇计算簇间距离，找出距离最近的两个簇进行合并，合并后,3,4,点成为一簇第,3,步：重复第,2,步的工作，,5,6,点成为一簇第,4,步：重复第,2,步的工作，,7,8,点成为一簇第,5,步：合并,1,2,，,3,4,成为一个包含四个点的簇第,6,步：合并,5,6,，,7,8,，由于合并后的簇的数目已经达到了用户输入的终止条件，程序终止步骤 最近的簇距离 最近的两个簇 合并后的新簇,1 1 1,，,2 1,2,，,3,，,4,，,5,，,6,，,7,，,8,1 3,，,4 1,2,，,3,4,，,5,，,6,，,7,，,8,1 5,，,6 1,2,，,3,4,，,5,6,，,7,，,8,1 7,，,8 1,2,，,3,4,，,5,6,，,7,8,1 1,2,3,4 1,2,3,4,，,5,6,，,7,8,1 5,6,，,7,8 1,2,3,4,，,5,6,7,8,结束,AGNES,特点,AGNES,算法比较简单，但经常会遇到合并点选择的困难。

假如一旦一组对象被合并，下一步的处理将在新生成的簇上进行已做处理不能撤销，聚类之间也不能交换对象如果在某一步没有很好的选择合并的决定，可能会导致低质量的聚类结果DIANA,算法,DIANA,（,Divisive ANAlysis),算法是典型的分裂聚类方法在聚类中，用户能定义希望得到的簇数目作为一个结束条件算法,DIANA,（自顶向下分裂算法）,输入：,n,个对象，终止条件簇的数目,k,输出：,k,个簇，达到终止条件规定簇数目1,）将所有对象整个当成一个初始簇；,（,2,）,FOR,（,i=1;ik;i+)DO BEGIN,（,3,）在所有簇中挑出具有最大直径的簇,C,；,（,4,）找出,C,中与其它点平均相异度最大的一个点,p,并把,p,放入,splinter group,，剩余的放在,old party,中；,（,5,）,REPEAT,（,6,）在,old party,里找出到最近的,splinter group,中的点的距离不大于到,old party,中最近点的距离的点，并将该点加入,splinter group,7,）,UNTIL,没有新的,old party,的点被分配给,splinter group,；,（,8,）,splinter group,和,old party,为被选中的簇分裂成的两个簇，与其它簇一起组成新的簇集合。

9,）,END.,序号属性,1,属性,2,111,212,321,422,534,635,744,845,DIANA,算法例题,第,1,步，找到具有最大直径的簇，对簇中的每个点计算平均相异度（假定采用是欧式距离）1,的平均距离：（,1+1+1.414+3.6+4.24+4.47+5,）,/7=2.96,类似地，,2,的平均距离为,2.526,；,3,的平均距离为,2.68,；,4,的平均距离为,2.18,；,5,的平均距离为,2.18,；,6,的平均距离为,2.68,；,7,的平均距离为,2.526,；,8,的平均距离为,2.96,找出平均相异度最大的点,1,放到,splinter group,中，剩余点在,old party,中第,2,步，在,old party,里找出到最近的,splinter group,中的点的距离不大于到,old party,中最近的点的距离的点，将该点放入,splinter group,中，该点是,2,第,3,步，重复第,2,步的工作，,splinter group,中放入点,3,第,4,步，重复第,2,步的工作，,splinter group,中放入点,4,。

第,5,步，没有在,old party,中的点放入了,splinter group,中且达到终止条件（,k=2,），程序终止如果没有到终止条件，因该从分裂好的簇中选一个直径最大的簇继续分裂步骤具有最大直径的簇,splinter groupOld party,11,，,2,，,3,，,4,，,5,，,6,，,7,，,8 12,，,3,，,4,，,5,，,6,，,7,，,8,21,，,2,，,3,，,4,，,5,，,6,，,7,，,8 1,，,23,，,4,，,5,，,6,，,7,，,8,31,，,2,，,3,，,4,，,5,，,6,，,7,，,8 1,，,2,，,34,，,5,，,6,，,7,，,8,41,，,2,，,3,，,4,，,5,，,6,，,7,，,8 1,，,2,，,3,，,45,，,6,，,7,，,8,51,，,2,，,3,，,4,，,5,，,6,，,7,，,8 1,，,2,，,3,，,45,，,6,，,7,，,8,终止,层次聚类方法的改进,层次聚类方法尽管简单，但经常会遇到合并或分裂点的选择的困难改进层次方法的聚类质量的一个有希望的方向是将层次聚类和其他聚类技术进行集成，形成多阶段聚类。

下面介绍,3,个改进的层次聚类方法,BIRTH,，,ROCK,和,Chameleon,BIRCH,算法,BIRCH,（,Balanced Iterative Reducing and Clustering,）利用层次方法的平衡迭代归约和聚类,用聚类特征（,CF,）和聚类特征树来概括聚类描述该算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算聚类特征（CF）,CF(Clustering Feature),：包含簇信息的三元组,(N,LS,SS),，,N,：簇的数据点；,LS,：线性和；,SS,：平方和,假定在簇,C1,中有三个点,(2,5),(3,2),(4,3),聚类特征是：,CF1=,=,聚类特征,树,CF,树是一个具有两个参数分支因子,B,和阈值,T,的高度平衡树分支因子,B,：非叶节点可以拥有的孩子数,阈值,T,：叶子节点中的子聚类的最大直径,阶段一：扫描数据库，建立一个初始的,CF,树，它可以被看作一个数据的多层压缩，试图保留数据内在的聚类结构当一个对象被插入到最近的叶节点（子聚类）中时，随着对象的插入，,CF,树被动态地构造，因此，,BIRTH,方法对增量或动态聚类也非常有效。

阶段二：采用某个聚类算法对,CF,树的叶节点进行聚类在这个阶段可以执行任何聚类算法BIRCH,算法,ROCK,ROCK(Robust Clustering using linKs,使用连接的鲁棒聚类,大多数聚类算法在进行聚类时只估计点与点之间的相似度，即在每一步中那些最相似的几个点合并到一个簇中这种“局部”方法很容易导致错误例如：两个完全不同的簇可能有少数几个点的距离较近，仅仅依据点与点之间的相似度来做出聚类决定就会导致这两个簇合并ROCK,采用一种比较全局的观点，通过考虑成对点的邻域情况进行聚类ROCK,两个概念：近邻和链接,近邻：两个点,pi,和,pj,是近邻，如果,sim(pi,pj)=,sim,是相似度函数，,是指定的阈值,链接：两个点,pi,和,pj,的链接数定义为这两点的共同近邻个数由于在确定点对之间的关系时考虑邻近的数据点，因此比只关注相似度的聚类方法更加鲁棒ROCK,例：购物篮数据库包含关于商品,a,b,g,的事物记录簇,C1,涉及商品,a,b,c,d,e,簇,C2,涉及商品,a,b,f,g,假设：只考虑相似度而忽略邻域信息C1,中,a,b,c,和,b,d,e,之间的,Jaccard,系数,是,0.2,而,C1,中的,a,b,c,和,C2,中的,a,b,f,的,Jaccard,系数,是,0.5,说明：仅根据,Jaccard,系数，,很容易导致错误。

另一方面，如果考虑链接数，可以成功地把这些事务划分到恰当地簇中例如：令,=0.5,，则,C2,中的事务,a,b,f,与,a,b,g,的链接数是,5,而,C2,中的事务,a,b,f,与,C1,中的事,务,a,b,c,之间的链接数是,3.,因此，,ROCK,能够正确地区分出两个不同,的事务簇Chameleon,利用动态建模的层次聚类算法采用动态建模确定簇之间的相似度簇之间的相似度依据簇中对象的互连度和簇的邻近度，即如果两个簇的互连性都很高且它们又靠得很近则将其合并变色龙算法的聚类步骤,Chameleon,算法首先由数据集构造成一个,K-,最近邻图,Gk,再通过一个图的划分算法将图,Gk,划分成大量的子图,每个子图代表一个初始子簇,最后用一个凝聚的层次聚类算法反复合并子簇，找到真正的结果簇；,K,最近邻图,Gk,图中的每个点表示数据集中的一个数据点；若数据点,ai,到另一个数据点,bi,的距离值是所有数据点到数据点,bi,的距离值中,K,个最小值之一,则称数据点,ai,是数据点,bi,的,K-,最临近对象，则在这两个点之间加一条带权边,边的权重表示这两个数据点之间的近似度,即它们之间的距离越大,则它们之间的近似度越小,它们之间的边的权重也越小。

割边,图划分算法划分,k,近邻图，使得割边最小，即簇,C,划分为两个子簇,Ci,和,Cj,时需切断的边的加权和最小割边用,EC(Ci,Cj),表示，用于评估两个簇之间的绝对互连度Chameleon,根据每对簇,Ci,和,Cj,的相对互连度,RI(Ci,Cj),和相对接近度,RC(Ci,Cj),来决定它们之间的相似度相对互连度,(RI),相对互连性,RICi,Cj:,子簇,Ci,和子簇,Cj,之间绝对互连度关于两个簇间的内部互连度的规范化绝对互连度,ECCi,Cj:,连接子簇,Ci,和子簇,Cj,之间的边的权重之和内部互连度,ECCi:,是将簇,Ci,划分成大致相等的两部分的割边的最小和相对近似度,(RC),相对接近度,RCCi,Cj:,子簇,Ci,和子簇,Cj,之间绝对接近度关于两个簇间的内部接近度的规范化绝对接近度,TCCi,Cj:,连接子簇,Ci,和子簇,Cj,之间的边的平均权重内部接近度,TCCi:,一个子簇,Ci,做最小二分时需要去掉的边的平均权重小结,凝聚层次聚类算。