数据挖掘层次聚类

数据挖掘层次聚类第1页，共34页，2023年，2月20日，星期六2023/4/21层次聚类2层次聚类方法概述层次聚类方法将数据对象组成一棵聚类树。根据层次分解是自底向上（合并）还是自顶向下（分裂），进一步分为凝聚的和分裂的。第2页，共34页，2023年，2月20日，星期六2023/4/21层次聚类3层次聚类方法概述凝聚的层次聚类：一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。分裂的层次聚类：采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。层次凝聚的代表是AGNES算法。层次分裂的代表是DIANA算法。第3页，共34页，2023年，2月20日，星期六2023/4/21层次聚类4簇间距离最小距离第4页，共34页，2023年，2月20日，星期六2023/4/21层次聚类5簇间距离最大距离第5页，共34页，2023年，2月20日，星期六2023/4/21层次聚类6簇间距离平均距离第6页，共34页，2023年，2月20日，星期六2023/4/21层次聚类7簇间距离均值距离第7页，共34页，2023年，2月20日，星期六2023/4/21层次聚类8AGNES算法AGNES(AGglomerativeNESting)算法最初将每个对象作为一个簇，然后这些簇根据某些准则被一步步地合并。两个簇间的相似度由这两个不同簇中距离最近的数据点对的相似度来确定。聚类的合并过程反复进行直到所有的对象最终满足簇数目。第8页，共34页，2023年，2月20日，星期六2023/4/21层次聚类9AGNES算法输入：n个对象，终止条件簇的数目k。输出：k个簇，达到终止条件规定簇数目。(1)将每个对象当成一个初始簇；(2)REPEAT(3)根据两个簇中最近的数据点找到最近的两个簇；(4)合并两个簇，生成新的簇的集合；(5)UNTIL达到定义的簇的数目；第9页，共34页，2023年，2月20日，星期六2023/4/21层次聚类10AGNES算法例题序号属性1属性2111212321422534635744845第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}，由于合并后的簇的数目已经达到了用户输入的终止条件，程序终止。步骤最近的簇距离最近的两个簇合并后的新簇11{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}结束第10页，共34页，2023年，2月20日，星期六2023/4/21层次聚类11第11页，共34页，2023年，2月20日，星期六2023/4/21层次聚类12第12页，共34页，2023年，2月20日，星期六2023/4/21层次聚类13第13页，共34页，2023年，2月20日，星期六2023/4/21层次聚类14AGNES特点AGNES算法比较简单，但经常会遇到合并点选择的困难。假如一旦一组对象被合并，下一步的处理将在新生成的簇上进行。已做处理不能撤销，聚类之间也不能交换对象。如果在某一步没有很好的选择合并的决定，可能会导致低质量的聚类结果。第14页，共34页，2023年，2月20日，星期六2023/4/21层次聚类15DIANA算法DIANA（DivisiveANAlysis)算法是典型的分裂聚类方法。在聚类中，用户能定义希望得到的簇数目作为一个结束条件。第15页，共34页，2023年，2月20日，星期六算法DIANA（自顶向下分裂算法）输入：n个对象，终止条件簇的数目k。输出：k个簇，达到终止条件规定簇数目。（1）将所有对象整个当成一个初始簇；（2）FOR（i=1;i≠k;i++)DOBEGIN（3）在所有簇中挑出具有最大直径的簇C；（4）找出C中与其它点平均相异度最大的一个点p并把p放入splintergroup，剩余的放在oldparty中；（5）REPEAT（6）在oldparty里找出到最近的splintergroup中的点的距离不大于到oldparty中最近点的距离的点，并将该点加入splintergroup。（7）UNTIL没有新的oldparty的点被分配给splintergroup；（8）splintergroup和oldparty为被选中的簇分裂成的两个簇，与其它簇一起组成新的簇集合。（9）END.第16页，共34页，2023年，2月20日，星期六序号 属性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

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放到splintergroup中，剩余点在oldparty中。第2步，在oldparty里找出到最近的splintergroup中的点的距离不大于到oldparty中最近的点的距离的点，将该点放入splintergroup中，该点是2。第3步，重复第2步的工作，splintergroup中放入点3。第4步，重复第2步的工作，splintergroup中放入点4。第5步，没有在oldparty中的点放入了splintergroup中且达到终止条件（k=2），程序终止。如果没有到终止条件，因该从分裂好的簇中选一个直径最大的簇继续分裂。步骤 具有最大直径的簇 splintergroup Oldparty 1 {1，2，3，4，5，6，7，8} {1} {2，3，4，5，6，7，8}2 {1，2，3，4，5，6，7，8} {1，2} {3，4，5，6，7，8} 3 {1，2，3，4，5，6，7，8} {1，2，3} {4，5，6，7，8} 4 {1，2，3，4，5，6，7，8} {1，2，3，4} {5，6，7，8} 5 {1，2，3，4，5，6，7，8} {1，2，3，4} {5，6，7，8}终止第17页，共34页，2023年，2月20日，星期六2023/4/21层次聚类18层次聚类方法的改进层次聚类方法尽管简单，但经常会遇到合并或分裂点的选择的困难。改进层次方法的聚类质量的一个有希望的方向是将层次聚类和其他聚类技术进行集成，形成多阶段聚类。下面介绍3个改进的层次聚类方法BIRTH，ROCK和Chameleon。第18页，共34页，2023年，2月20日，星期六2023/4/21层次聚类19BIRCH算法BIRCH（BalancedIterativeReducingandClustering）利用层次方法的平衡迭代归约和聚类用聚类特征（CF）和聚类特征树来概括聚类描述。该算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。第19页，共34页，2023年，2月20日，星期六2023/4/21层次聚类20聚类特征（CF）CF(ClusteringFeature)：包含簇信息的三元组(N,LS,SS)，N：簇的数据点；LS：线性和；SS：平方和假定在簇C1中有三个点(2,5),(3,2),(4,3)聚类特征是：CF1=<3,(2+3+4,5+2+3),(22+32+42,52+22+32)>=<3,(9,10),(29,38)>第20页，共34页，2023年，2月20日，星期六2023/4/21层次聚类21聚类特征树CF树是一个具有两个参数分支因子B和阈值T的高度平衡树。分支因子B：非叶节点可以拥有的孩子数阈值T：叶子节点中的子聚类的最大直径第21页，共34页，2023年，2月20日，星期六2023/4/21层次聚类22

阶段一：扫描数据库，建立一个初始的CF树，它可以被看作一个数据的多层压缩，试图保留数据内在的聚类结构。当一个对象被插入到最近的叶节点（子聚类）中时，随着对象的插入，CF树被动态地构造，因此，BIRTH方法对增量或动态聚类也非常有效。阶段二：采用某个聚类算法对CF树的叶节点进行聚类。在这个阶段可以执行任何聚类算法。BIRCH算法第22页，共34页，2023年，2月20日，星期六2023/4/21层次聚类23ROCKROCK(RobustClusteringusinglinKs,使用连接的鲁棒聚类大多数聚类算法在进行聚类时只估计点与点之间的相似度，即在每一步中那些最相似的几个点合并到一个簇中。这种“局部”方法很容易导致错误。例如：两个完全不同的簇可能有少数几个点的距离较近，仅仅依据点与点之间的相似度来做出聚类决定就会导致这两个簇合并。ROCK采用一种比较全局的观点，通过考虑成对点的邻域情况进行聚类。第23页，共34页，2023年，2月20日，星期六2023/4/21层次聚类24ROCK两个概念：近邻和链接近邻：两个点pi和pj是近邻，如果sim(pi,pj)>=θ,sim是相似度函数，θ是指定的阈值链接：两个点pi和pj的链接数定义为这两点的共同近邻个数。由于在确定点对之间的关系时考虑邻近的数据点，因此比只关注相似度的聚类方法更加鲁棒。第24页，共34页，2023年，2月20日，星期六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系数，很容易导致错误。第25页，共34页，2023年，2月20日，星期六另一方面，如果考虑链接数，可以成功地把这些事务划分到恰当地簇中。例如：令θ=0.5，则C2中的事务

{a,b,f}与{a,b,g}的链接数是5

而C2中的事务{a,b,f}与C1中的事务{a,b,c}之间的链接数是3.因此，ROCK能够正确地区分出两个不同的事务簇。第26页，共34页，2023年，2月20日，星期六2023/4/21层次聚类27Chameleon利用动态建模的层次聚类算法。采用动态建模确定簇之间的相似度。簇之间的相似度依据簇中对象的互连度和簇的邻近度，即如果两个簇的互连性都很高且它们又靠得很近则将其合并。第27页，共34页，2023年，2月20日，星期六2023/4/21层次聚类28变色龙算法的聚类步骤Chameleon算法首先由数据集构造成一个K-最近邻图Gk,再通过一个图的划分算法将图Gk划分成大量的子图,每个子图代表一个初始子簇,最后用一个凝聚的层次聚类算法反复合并子簇，找到真正的结果簇；第28页，共34页，2023年，2月20日，星期六2023/4/21层次聚类29K最近邻图Gk图中的每个点表示数据集中的一个数据点；若数据点ai到另一个数据点bi的距离值是所有数据点到数据点bi的距离值中K个最小值之一,则称数据点ai是数据点bi的K-最临近对象，则在这两个点之间加一条带权边,边的权重表示这两个数据点之间的近似度,即它们之间的距离越大,则它们之间的近似度越小,它们之间的边的权重也越小。第29页，共34页，2023年，2月20日，星期六2023/4/21层次聚类30割边图划分算法划分k近邻图，使得割边最小，即簇C划分为两个子簇Ci和C