聚类分析―层次聚类

智能数据挖掘Topic3--聚类分析层次聚类方法（HierarchicalMethods）层次方法层次的聚类方法将数据对象组成一棵聚类的树根据层次分解是自底向上,还是自顶向下形成,层次的聚类方法可以进一步分为凝聚的(agglomerative)和分裂的(divisive)层次聚类纯粹的层次聚类方法的聚类质量受限于如下特点：一旦一个合并或分裂被执行，就不能修正最近的研究集中于凝聚层次聚类和迭代重定位方法的集成使用距离矩阵作为聚类标准.该方法不需要输入聚类数目k,但需要终止条件2020/1/30层次方法(续)凝聚的(agglomerative)和分裂的(divisive)层次聚类图示Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0agglomerative(AGNES)divisive(DIANA)2020/1/30AGNES(AgglomerativeNesting)由Kaufmann和Rousseeuw提出(1990)已在一些统计分析软件包中实现.如Splus使用单链接(Single-Link)方法和相异度矩阵合并具有最小相异度的节点以非递减的方式继续最终所有的节点属于同一个簇0123456789100123456789100123456789100123456789100123456789100123456789102020/1/30DIANA(DivisiveAnalysis)由Kaufmann和Rousseeuw提出(1990)已在一些统计分析软件包中实现.如Splus是AGNES的逆最终每个节点自己形成一个簇0123456789100123456789100123456789100123456789100123456789100123456789102020/1/30层次方法(续)四个广泛采用的簇间距离度量方法最小距离：dmin(Ci,Cj)=minp∈Ci,p’∈Cj|p-p’|最大距离：dmax(Ci,Cj)=maxp∈Ci,p’∈Cj|p-p’|平均值的距离：dmean(Ci,Cj)=|mi-mj|平均距离(簇的直径D)：davg(Ci,Cj)=∑p∈Ci∑p’∈Cj|p-p’|/ninj其中,|p-p’|是两个对象p和p’之间的距离mi是簇Ci的平均值，ni是簇Ci中对象的数目2020/1/30层次方法(续)层次聚类的主要缺点不具有很好的可伸缩性:时间复杂性至少是O(n2),其中n对象总数合并或分裂的决定需要检查和估算大量的对象或簇不能撤消已做的处理,聚类之间不能交换对象.如果某一步没有很好地选择合并或分裂的决定,可能会导致低质量的聚类结果2020/1/30层次方法(续)改进层次方法的聚类质量的方法:将层次聚类和其他的聚类技术进行集成,形成多阶段聚类BIRCH(1996):使用CF-tree对对象进行层次划分,然后采用其他的聚类算法对聚类结果进行求精ROCK1999：基于簇间的互联性进行合并CHAMELEON(1999):使用动态模型进行层次聚类CURE(1998):采用固定数目的代表对象来表示每个簇，然后依据一个指定的收缩因子向着聚类中心对它们进行收缩2020/1/30BIRCH(1996)Birch(BalancedIterativeReducingandClusteringusingHierarchies):利用层次方法的平衡迭代归约和聚类由Zhang,Ramakrishnan和Livny提出(SIGMOD’96),该算法的特点是能利用有限的内存资源完成对大数据集的高质量的聚类，同时通过单遍扫描数据集能最小化I/O代价。两个重要概念聚类特征(ClusteringFeature,CF)聚类特征树(ClusteringFeatureTree,CF树)聚类特征聚类特征(CF)是一个三元组，给出对象子类的信息的汇总描述设某个子类中有N个d维的点或对象{oI}，则该子类的CF定义如下),,(SSSLNCF2020/1/30聚类特征ClusteringFeature:CF=(N,LS,SS)N:数据点数目LS:Ni=1XiSS:Ni=1Xi2012345678910012345678910CF=(5,(16,30),(54,190))(3,4)(2,6)(4,5)(4,7)(3,8)2020/1/30聚类特征假定簇C1中有两个点（1，2，3），（3，2，1），簇C2有三个点（1，1，2），（2，2，1），（2，1，2），簇3由C1和C2构成，则：CF1=（2，（1+3，2+2，3+1），（））=（2，（4，4，4），（10，8，10））CF2=（3，（1+2+2，1+2+1，2+1+2），（））=（3，（5，4，5），（9，6，9））因此得到CF3为：CF3=（2+3，（4+5，4+4，4+5），（10+9，8+6，10+9））=（5，（9，8，9），（19，14，19））2020/1/30簇的质心和簇的半径。假如一个簇中包含n个数据点：{Xi}，i=1,2,3...n.，则质心C和半径R计算公式如下：C=(X1+X2+...+Xn)/n，（这里X1+X2+...+Xn是向量加）R=(|X1-C|^2+|X2-C|^2+...+|Xn-C|^2)/n其中，簇半径表示簇中所有点到簇质心的平均距离。CF中存储的是簇中所有数据点的特性的统计和，所以当我们把一个数据点加入某个簇的时候，那么这个数据点的详细特征，例如属性值，就丢失了，由于这个特征，BIRCH聚类可以在很大程度上对数据集进行压缩。2020/1/30有意思的是簇中心、簇半径、簇直径以及两簇之间的距离D0到D3都可以由CF来计算，比如簇直径簇间距离这里的N，LS和SS是指两簇合并后大簇的N，LS和SS。所谓两簇合并只需要两个对应的CF相加那可2020/1/30BIRCH的CF树聚类特征从统计学的观点来看，聚类特征是对给定子类统计汇总:子聚类的0阶,1阶和2阶矩(moments)记录了计算聚类和有效利用存储的关键度量,并有效地利用了存储,因为它汇总了关于子类的信息，而不是存储所有的对象CF树是高度平衡的树，它存储了层次聚类的聚类特征树中的非叶节点有后代或“孩子”非叶节点存储了其孩子的CF的总和，即汇总了关于其孩子的聚类信息CF树有两个参数----影响CF树的大小分支因子B:定义非树叶节点的孩子的最大个数阈值T:给出了存储在树的叶子节点中的子类的最大直径2020/1/30CFtree的结构类似于一棵B-树，它有3个参数：内部节点平衡因子B，叶节点平衡因子L，簇直径阈值T。树中每个Nlonleaf节点最多包含B个孩子节点，Leaf最多只能有L个MinCluster（初始划分子簇），而一个MinCluster的直径不能超过T。例如，一棵高度为3，B为6，L为5的一棵CF树的例子如图所示：2020/1/30CF树的样子2020/1/30CFTreeCF1child1CF3child3CF2child2CF6child6CF1child1CF3child3CF2child2CF5child5CF1CF2CF6prevnextCF1CF2CF4prevnextB=5L=6RootNon-leafnodeLeafnodeLeafnode2020/1/30CF树构造过程(1)从根节点开始，自上而下选择最近的孩子节点(2)到达叶子节点后，检查最近的元组CFi能否吸收此数据点是，更新CF值否，是否可以添加一个新的元组是，添加一个新的元组否则，分裂最远的一对元组，作为种子，按最近距离重新分配其它元组(3)更新每个非叶节点的CF信息，如果分裂节点，在父节点中插入新的元组，检查分裂，直到root2020/1/30构造CF树算法起初，我们扫描数据库，拿到第一个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值。2020/1/30插入一个节点当又有一个数据点要插入树中时，把这个点封装为一个MinCluster（这样它就有了一个CF值），把新到的数据点记为CF_new，我们拿到树的根节点的各个孩子节点的CF值，根据D2来找到CF_new与哪个节点最近，就把CF_new加入那个子树上面去。这是一个递归的过程。递归的终止点是要把CF_new加入到一个MinCluster中，如果加入之后MinCluster的直径没有超过T，则直接加入，否则譔CF_new要单独作为一个簇，成为MinCluster的兄弟结点。插入之后注意更新该节点及其所有祖先节点的CF值。2020/1/30节点分裂插入新节点后，可能有些节点的孩子数大于了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。2020/1/30Birch算法的阶段：Ø阶段一：扫描数据库，构造一颗CF树，并定义相关阈值，把稠密数据分成簇。Ø阶段二：对CF树进行压缩，通过改变T值，将部分簇进行压缩合并，建立一个更小的CF树。Ø阶段三：采用其他的聚类算法对其叶节点进行聚类，将稀疏的簇当作离群值进行删除，补救由于输入顺序和页面大小带来的分裂。Ø阶段四：通过上阶段得出聚类质心，将其作为种子节点，将其他对象分配给质心，构成新的聚类。2020/1/30BIRCH算法流程如下图所示：BIRCH算法流程如下图所示：2020/1/30BIRCH(续)重建过程从旧树的叶子节点建造一个新树。这样，重建树的过程不需要重读所有的对象----建树只需读一次数据在阶段三和四采用任何聚类算法，例如典型的划分方法BIRCH的性能支持增量聚类：因为它对每一个数据点的聚类的决策都是基于当前已经处理过的数据点，而不是基于全局的数据点。线性可伸缩性:计算复杂性O(n),单遍扫描,附加的扫描可以改善聚类质量较好的聚类质量缺点只能处理数值数据对数据的输入次序敏感CF树结点不总是对应于[用户考虑的]自然簇(参数B和T)簇非球形时效果不好(使用半径/直径控制簇边界)2020/1/30CURE(1998)CURE(ClusteringUsingREpresentatives):由Guha,Rastogi和Shim提出(1998)绝大多数聚类算法或者擅长处理球形和相似大小的聚类，或者在存在孤立点时变得比较脆弱CURE解决了偏好球形的问题，在处理孤立点上也更加健壮CURE采用了一种新的层次聚类算法选择基于质心和基于代表对象方法之间的中间策略.它不用单个质心或对象来代表一个簇,而是选择了数据空间中固定数目的具有代表性的点首先选择簇中分散的对象,然后根据一个特定的收缩因子向簇中心“收缩”2