聚类分析-层次聚类

智能数据挖掘Topic3--聚类分析层次聚类方法（HierarchicalMethods）层次方法层次的聚类方法将数据对象组成一棵聚类的树根据层次分解是自底向上,还是自顶向下形成,层次的聚类方法可以进一步分为凝聚的(agglomerative)和分裂的(divisive)层次聚类

纯粹的层次聚类方法的聚类质量受限于如下特点：一旦一个合并或分裂被执行，就不能修正最近的研究集中于凝聚层次聚类和迭代重定位方法的集成

使用距离矩阵作为聚类标准.该方法不需要输入聚类数目k,但需要终止条件11/10/2023层次方法(续)凝聚的(agglomerative)和分裂的(divisive)层次聚类图示Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0agglomerative(AGNES)divisive(DIANA)11/10/2023AGNES(AgglomerativeNesting)由Kaufmann和Rousseeuw提出(1990)已在一些统计分析软件包中实现.如Splus使用单链接(Single-Link)方法和相异度矩阵合并具有最小相异度的节点以非递减的方式继续最终所有的节点属于同一个簇11/10/2023DIANA(DivisiveAnalysis)由Kaufmann和Rousseeuw提出(1990)已在一些统计分析软件包中实现.如Splus是AGNES的逆最终每个节点自己形成一个簇11/10/2023层次方法(续)四个广泛采用的簇间距离度量方法

最小距离：dmin(Ci,Cj)=min

p∈Ci,p’∈Cj

|p-p’|

最大距离：dmax(Ci,Cj)=max

p∈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中对象的数目

11/10/2023层次方法(续)层次聚类的主要缺点不具有很好的可伸缩性:时间复杂性至少是O(n2),其中n

对象总数合并或分裂的决定需要检查和估算大量的对象或簇不能撤消已做的处理,聚类之间不能交换对象.如果某一步没有很好地选择合并或分裂的决定,可能会导致低质量的聚类结果

11/10/2023层次方法(续)改进层次方法的聚类质量的方法:将层次聚类和其他的聚类技术进行集成,形成多阶段聚类BIRCH(1996):使用CF-tree对对象进行层次划分,然后采用其他的聚类算法对聚类结果进行求精ROCK1999：基于簇间的互联性进行合并CHAMELEON(1999):使用动态模型进行层次聚类CURE(1998):采用固定数目的代表对象来表示每个簇，然后依据一个指定的收缩因子向着聚类中心对它们进行收缩11/10/2023BIRCH(1996)Birch(BalancedIterativeReducingandClusteringusingHierarchies):利用层次方法的平衡迭代归约和聚类由Zhang,Ramakrishnan和Livny提出(SIGMOD’96),该算法的特点是能利用有限的内存资源完成对大数据集的高质量的聚类，同时通过单遍扫描数据集能最小化I/O代价。

两个重要概念聚类特征(ClusteringFeature,CF)聚类特征树(ClusteringFeatureTree,

CF树)聚类特征聚类特征(CF)是一个三元组，给出对象子类的信息的汇总描述设某个子类中有N个d维的点或对象{oI}，则该子类的CF定义如下

11/10/2023聚类特征ClusteringFeature:CF=(N,LS,SS)N:数据点数目LS:

Ni=1XiSS:

Ni=1Xi2CF=(5,(16,30),(54,190))(3,4)(2,6)(4,5)(4,7)(3,8)11/10/2023聚类特征假定簇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））11/10/2023簇的质心和簇的半径。假如一个簇中包含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聚类可以在很大程度上对数据集进行压缩。11/10/2023有意思的是簇中心、簇半径、簇直径以及两簇之间的距离D0到D3都可以由CF来计算，比如簇直径

簇间距离这里的N，LS和SS是指两簇合并后大簇的N，LS和SS。所谓两簇合并只需要两个对应的CF相加那可11/10/2023BIRCH的CF树聚类特征从统计学的观点来看，聚类特征是对给定子类统计汇总:子聚类的0阶,1阶和2阶矩(moments)记录了计算聚类和有效利用存储的关键度量,并有效地利用了存储,因为它汇总了关于子类的信息，而不是存储所有的对象CF树是高度平衡的树，它存储了层次聚类的聚类特征

树中的非叶节点有后代或“孩子”

非叶节点存储了其孩子的CF的总和，即汇总了关于其孩子的聚类信息

CF树有两个参数----影响CF树的大小分支因子B:定义非树叶节点的孩子的最大个数阈值T:给出了存储在树的叶子节点中的子类的最大直径

11/10/2023CFtree的结构类似于一棵B-树，它有3个参数：内部节点平衡因子B，叶节点平衡因子L，簇直径阈值T。树中每个Nlonleaf节点最多包含B个孩子节点，Leaf最多只能有L个MinCluster（初始划分子簇），而一个MinCluster的直径不能超过T。例如，一棵高度为3，B为6，L为5的一棵CF树的例子如图所示：11/10/2023CF树的样子11/10/2023CFTreeCF1child1CF3child3CF2child2CF6child6CF1child1CF3child3CF2child2CF5child5CF1CF2CF6prevnextCF1CF2CF4prevnextB=5L=6RootNon-leafnodeLeafnodeLeafnode11/10/2023CF树构造过程(1)从根节点开始，自上而下选择最近的孩子节点

(2)到达叶子节点后，检查最近的元组CFi能否吸收此数据点

是，更新CF值

否，是否可以添加一个新的元组

是，添加一个新的元组

否则，分裂最远的一对元组，作为种子，按最近距离重新分配其它元组

(3)更新每个非叶节点的CF信息，如果分裂节点，在父节点中插入新的元组，检查分裂，直到root

11/10/2023构造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值。11/10/2023插入一个节点当又有一个数据点要插入树中时，把这个点封装为一个MinCluster（这样它就有了一个CF值），把新到的数据点记为CF_new，我们拿到树的根节点的各个孩子节点的CF值，根据D2来找到CF_new与哪个节点最近，就把CF_new加入那个子树上面去。这是一个递归的过程。递归的终止点是要把CF_new加入到一个MinCluster中，如果加入之后MinCluster的直径没有超过T，则直接加入，否则譔CF_new要单独作为一个簇，成为MinCluster的兄弟结点。插入之后注意更新该节点及其所有祖先节点的CF值。11/10/2023节点分裂插入新节点后，可能有些节点的孩子数大于了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。11/10/2023Birch算法的阶段：

Ø

阶段一：扫描数据库，构造一颗CF树，并定义相关阈值，把稠密数据分成簇。Ø

阶段二：对CF树进行压缩，通过改变T值，将部分簇进行压缩合并，建立一个更小的CF树。Ø

阶段三：采用其他的聚类算法对其叶节点进行聚类，将稀疏的簇当作离群值进行删除，补救由于输入顺序和页面大小带来的分裂。Ø

阶段四：通过上阶段得出聚类质心，将其作为种子节点，将其他对象分配给质心，构成新的聚类。11/10/2023BIRCH算法流程如下图所示：

BIRCH算法流程如下图所示：

11/10/2023BIRCH(续)重建过程从旧树的叶子节点建造一个新树。这样，重建树的过程不需要重读所有的对象----建树只需读一次数据在阶段三和四采用任何聚类算法，例如典型的划分方法BIRCH的性能支持增量聚类：因为它对每一个数据点的聚类的决策都是基于当前已经处理过的数据点，而不是基于全局的数据点。

线性可伸缩性:计算复杂性O(n),单遍扫描,附加的扫描可以改善聚类质量较好的聚类质量缺点只能处理数值数据对数据的输入次序敏感CF树结点不总是对应于[用户考虑的]自然簇(参数B和T)簇非球形时效果不好(使用半径/直径控制簇边界)11/10/2023CURE(1998)CURE(ClusteringUsingREpresentatives):由Guha,Rastogi和Shim提出(1998)绝大多数聚类算法或者擅长处理球形和相似大小的聚类，或者在存在孤立点时变得比较脆弱CURE解决了偏好球形的问题，在处理孤立点上也更加健壮CURE采用了一种新的层次聚类算法选择基于质心和基于代表对象方法之间的中间策略.它不用单个质心或对象来代表一个簇,而是选择了数据空间中固定数目的具有代表性的点首先选择簇中分散的对象,然后根据一个特定的收缩因子向簇中心“收缩”11/10/2023CURE(续)每个簇有多于一个的代表点使得CURE可以适应非球形的任意形状的聚类簇的收缩或凝聚可以有助于控制孤立点的影响CURE的优点CURE对孤立点的处理更加健壮能够识别非球形和大小变化较大的簇对于大规模数据库,它也具有良好的伸缩性,而且没有牺牲聚类质量

针对大型数据库,CURE采用了随机取样和划分两种方法的组合首先划分一个随机样本,每个划分被部分聚类然后对这些结果簇聚类,产生希望的结果

11/10/2023Cure(续)CURE算法核心:从源数据对象中抽取一个随机样本集S.将样本S分割为p个划分,每个的大小为

s/p将每个划分局部地聚类成s/pq

个簇删除孤立点通过随机选样如果一个簇增长太慢,就删除它.对局部聚类进行聚类.用相应的簇标签来标记数据11/10/2023CURE:例s=50p=2s/p=25xxxyyyyxyxs/pq=511/10/2023CURE:例(续)多个代表点向重心以因子

移动,进行收缩或凝聚多个代表点描述了每个簇的形状xyxy11/10/2023对分类数据聚类:ROCKROCK(RObustClusteringusinglinKs)由S.Guha,R.Rastogi,K.Shim提出(ICDE’99).使用链接(link)度量相似性/接近性链接：两个对象间共同的近邻的数目不是基于距离的计算复杂性:基本思想:相似性函数:Jaccard系数

设T1={1,2,3},T2={3,4,5}11/10/2023Rock(续)两个点pi和pj是近邻，如果sim(pi,pj)>=用户指定阈值link(pi,pj)是两个点pi和pj共同的近邻的数目两个簇Ci和Cj的互连性被定义为两个簇间交叉链（crosslink）的数目ROCK首先根据相似度阀值和共享近邻的概念，从给定的数据相似度矩阵构建一个稀疏的图，然后在这个稀疏图上运行一个层次聚类算法11/10/2023CHAMELEONCHAMELEON:一个利用动态模型的层次聚类算法(Hierarchicalclusteringusingdynamicmodeling)由G.Karypis,E.H.Han,andV.Kumar’99提出对CURE和ROCK缺点的观察:Cure忽略了关于两个不同簇中对象的聚集互连性的信息Rock强调对象间互连性,却忽略了关于对象间近似度的信息CHAMELEON基于动态模型度量相似性如果两个簇间的互连性和近似度与簇内部对象间的互连性和近似度高度相关,则合并这两个簇11/10/2023CHAMELEON(续)两阶段算法使用图划分算法:将数据对象聚类为大量相对较小的子类逐步用图划分算法把k近邻图分成相对较小de子簇，最小化割边。使用凝聚的层次聚类算法：通过反复地合并子类来找到真正的结果簇既考虑互连性,又考虑簇间的近似度,特别是簇内部的特征,来确定最相似的子类.这样,它不依赖于静态的用户提供的模型,能够自动地适应被合并的簇的内部特征割边最小化——簇c划分为两个子簇Ci和Cj时需要割断的边的加权和最小。割边用EC{Ci，Cj}表示，评估Ci和Cj的簇间的绝对互联性。11/10/2023C