(8.3.1)--8.3基于层次的聚类.pdf

《(8.3.1)--8.3基于层次的聚类.pdf》由会员分享，可在线阅读，更多相关《(8.3.1)--8.3基于层次的聚类.pdf（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第8章章 聚聚类类目录目录 CONTENTS2 8.18.28.38.4聚类概述聚类概述基于划分的聚类基于划分的聚类基于层次的聚类基于层次的聚类基于密度的聚类基于密度的聚类基于网格的聚类基于网格的聚类8.5Chapter 8.3基于层次的聚类基于层次的聚类基于层次聚类的基本概念基于层次聚类的基本概念 层次聚类方法（Hierarchical Clustering Method）是一种应用广泛的经典聚类算法，能够揭示某些数据中蕴含的层次结构。对公司的职员组织进行划分 按照生物学特征对动物分组以期发现物种的分层结构 用层次结构的形式表述数据对象，有助于数据汇总和可视化。层次聚类方法通过将数据对象组

2、织成若干组（或簇）形成一个相应的树来进行聚类。4 8.3 基于层次的聚类基于层次聚类的基本概念基于层次聚类的基本概念层次聚类方法可分为凝聚层次分类和分裂层次聚类 凝聚的层次聚类方法 使用自底向上的策略。典型地,它从令每个对象形成自己的簇开始,迭代地把簇合并成越来越大的簇,直到所有的对象都在一个簇中,或者满足某个终止条件。典型代表算法：AGNES(AGglomerative NESting)算法 分裂的层次聚类方法 使用自顶向下的策略。它从把所有对象置于一个簇中开始,该簇是层次结构的根。然后,把根上的簇划分成多个较小的子簇,并且递归地把这些簇划分成更小的簇。直到最底层的簇都足够凝聚，或者仅包含一

3、个对象。典型代表算法：DIANA(DIvisive ANAlysis)算法5 8.3 基于层次的聚类凝聚的与分裂的层次聚类：凝聚的与分裂的层次聚类：Step 0Step 1Step 2Step 3Step 4bdceaa bd ec d ea b c d eStep 4Step 3Step 2Step 1Step 0凝聚的(AGNES)分裂的(DIANA)6 8.3 基于层次的聚类簇间距离簇间距离度量：度量：最短距离法（最大相似度）：定义两个簇中最靠近的两个对象间的距离为簇间距离。如公式(8-3)所示。?X G?,?=?X?,?(8-3)最长距离法（最小相似度）：定义两个簇中最远的两个对象间的

4、距离为簇间距离。如公式(8-4)所示。?X G?,?=?X?,?(8-4)簇平均法：计算两个簇中任意两个对象间的距离，取它们的平均值作为簇间距离。如公式(8-5)所示。?X G?,?=1?X?,?(8-5)中心法：定义两个簇的两个中心点的距离为簇间距离。如公式(8-6)所示。?X G?,?=?(8-6)其中?是两个对象?和?之间的距离，?和?分别是簇?和?的中心点，而?和?分别是簇?和?中对象的数目。这些度量又称连接度量(linkage measure)。7 8.3 基于层次的聚类簇间距离簇间距离度量：度量：最近邻聚类算法：当算法使用最小距离来衡量簇间距离时,如果当最近的两个簇之间的距离超过用

5、户给定的阈值时聚类过程就会终止,则称其为单连接算法(single-linkage algorithm)。最远邻聚类算法：当算法使用最远距离来衡量簇间距离时。如果当两个簇之间的最大距离超过用户给定的阈值时聚类过程就会终止,则称其为全连接算法(complete-linkage algorithm)。8 8.3 基于层次的聚类 分裂的层次聚类方法,使用自顶向下的策略把对象划分到层次结构中。从包含所有对象的簇开始，每一步分裂一个簇，直到仅剩下单点簇，或者满足用户指定的簇的个数时终止。这种方式需要确定将要分裂的簇和分裂方式。1.分裂层次聚类分裂层次聚类9 8.3 基于层次的聚类 DIANA(DIvisi

6、ve ANAlysis)算法是典型的层次分裂聚类算法。在聚类中，指定得到的簇数作为结束条件，同时它采用平均距离（或称为平均相异度）作为类间距度量方法，并且指定簇的直径由簇中任意两个数据点的距离中的最大值来表示。DIANA用到如下两个定义:簇的直径：在一个簇中的任意两个数据点都有一个欧式距离，这些距离中的最大值是簇的直径。平均相异度：两个数据点之间的平均距离。DIANA算法算法10 8.3 基于层次的聚类DIANA算法的基本过程分为以下几步：把所有对象整体作为一个初始簇；将splinter group和old party两个对象集合置空；在所有簇中挑出具有最大直径的簇C，找出C中与其他对象平均相

7、异度最大的一个对象p，把p放入splinter group，剩余的对象放入old party中；然后不断的在old party里找出满足如下条件的对象：该对象到splinter group中的对象的最近距离小于等于到old party中的对象的最近距离，把该对象加入splinter group，直到没有新的old party的对象被找到。此时，splinter group和old party两个簇与其他簇一起组成新的簇集合；重复步骤和，直至簇的数目达到终止条件规定的数目。DIANA算法算法11 8.3 基于层次的聚类例例8.3 使用使用DIANA算法进行聚类算法进行聚类样本数据集如表8-2所示

8、，样本点间欧几里得距离如表8-4所示。设终止条件为k=2，采用DIANA算法进行层次聚类。DIANA算法算法12 8.3 基于层次的聚类数据对象数据对象?x001.555y20002表8-2 数据集表8-4 样本点间距样本点样本点?022.55.45?201.555.4?2.51.503.54?5.453.502?55.4420解：首先初始簇为?,?,?,?,?，找到具有最大直径的簇，开始就是初始簇，对簇中的每个点计算平均距离（假设采用欧几里得距离）。样本点?的平均相异度：(2+2.5+5.4+5)4=3.725，样本点?的平均相异度：(2+1.5+5+5.4)4=3.475，样本点?的平均相

9、异度：(2.5+1.5+3.5+4)4=2.875，样本点?的平均相异度：(5.4+5+3.5+2)4=3.975，样本点?的平均相异度：(5+5.4+4+2)4=4.1将平均相异度最大的点?放到splinter group中，剩余点在old party中。DIANA算法算法13 8.3 基于层次的聚类在old party里找出到splinter group中的点的最近距离小于等于该点到old party中的其他点的最近距离的点，把该点加入splinter group。对于样本点?：?(?,?)=5；?(?,?)=2；?(?,?)=2.5；?(?,?)=5.4；对于样本点?：?(?,?)=5.

10、4；?(?,?)=2；?(?,?)=1.5；?(?,?)=5；对于样本点?：?(?,?)=4；?(?,?)=2.5；?(?,?)=1.5；?(?,?)=3.5；对于样本点?：?(?,?)=2；?(?,?)=5.4；?(?,?)=5；?(?,?)=3.5；在old party中仅有样点?到splinter group中的样本点?的距离2小于样点?到old party中的其他样本点的最近距离3.5，所以将点?加入到splinter group中。DIANA算法算法14 8.3 基于层次的聚类重复步骤对于样本点?：?(?,?)=5.4；?(?,?)=5；?(?,?)=2；?(?,?)=2.5；对于样

11、本点?：?(?,?)=5；?(?,?)=5.4；?(?,?)=2；?(?,?)=1.5；对于样本点?：?(?,?)=3.5；?(?,?)=4；?(?,?)=2.5；?(?,?)=1.5；没有新的old party中的对象放入splinter group，此时分裂的簇数是2，达到终止条件，算法结束。如果没有达到终止条件，下一阶段会从分裂好的簇中选择一个直径最大的簇继续分裂。上述步骤对应的簇的变化如表8-7所示，最终聚类结果为?,?,?和?,?。DIANA算法算法15 8.3 基于层次的聚类步骤步骤具有最大直径的簇具有最大直径的簇splinter groupold party?,?,?,?,?,?

12、,?,?,?,?,?,?,?,?,?终止表8-7 DIANA执行过程簇的变化 缺点是已做的分裂操作不能撤销，类之间不能交换对象。如果在某步没有选择好分裂点，可能会导致低质量的聚类结果。大数据集不太适用。DIANA算法算法16 8.3 基于层次的聚类 凝聚的层次聚类方法，使用自底向上的策略把对象组织到层次结构中。开始每个对象作为一个簇，每一步合并两个最相似（距离最近）的簇。这种方法需要定义簇的相似性度量方式和算法终止的条件。层次凝聚时采用的最短距离法称为单链或MIN层次凝聚，相应地采用最长距离法称为全链或MAX层次凝聚。2 .凝聚凝聚层次聚类层次聚类17 8.3 基于层次的聚类 AGNES(AG

13、glomerative NESting)算法是典型的凝聚层次聚类方法，最初将每个对象作为一个簇，然后根据某些准则一步步地合并这些簇。两个簇间的相似度由这两个不同簇中距离最近的数据点的相似度来确定，聚类的合并过程反复进行直到所有的对象最终满足终止条件设置的簇数目。AGNES算法算法18 8.3 基于层次的聚类AGNES算法的过程基本分为以下几步：将每个对象作为一个初始簇；根据两个簇中最近的数据对象找到最近的两个簇，合并两个簇，生成新的簇的集合；重复步骤，直到达到定义的簇的数目。AGNES算法算法19 8.3 基于层次的聚类例例8.4 使用使用AGNES算法进行聚类算法进行聚类样本数据集如表8-2

14、所示，样本点间欧几里得距离如表8-4所示。设终止条件为k=2，采用AGNES算法进行层次聚类。AGNES算法算法20 8.3 基于层次的聚类数据对象数据对象?x001.555y20002表8-2 数据集表8-4 样本点间距样本点样本点?022.55.45?201.555.4?2.51.503.54?5.453.502?55.4420解：将每个样本点作为一个簇，初始簇集合为：?，?，?，?，?。根据初始簇计算每个簇之间的距离，找出距离最小的两个簇进行合并：从表8-4中的样本点间距中找到?和?的距离1.5最小，合并?和?为1个新簇?,?，此时簇集合为：?，?,?，?，?。AGNES算法算法21 8

15、.3 基于层次的聚类对合并后的簇计算簇间最短距离，找出距离最近的两个簇进行合并：?X G?(?,?,?)=?X?(?,?),?(?,?)?=?X?2,2.5?=2?X G?(?,?,?)=?X?(?,?),?(?,?)?=?X?5,3.5?=3.5?X G?(?,?,?)=min?d(?,?),d(?,?)?=?X?5.4,4?=4?X G?(?,?)=5.4?X G?(?,?)=5?X G?(?,?)=2?和?,?的最短距离与?和?的最短距离都是2，为最小距离，下一步合并方案不唯一，此处选择合并?和?为1个新簇?,?，此时簇集合为：?，?,?，?,?。AGNES算法算法22 8.3 基于层次

16、的聚类对合并后的簇计算簇间最短距离，找出距离最近的两个簇进行合并：?X G?(?,?,?)=?X?(?,?),?(?,?)?=?X?2,2.5?=2,?X G?(?,?,?)=?X?(?,?),?(?,?)?=?X?5.4,5?=5,?X G?(?,?,?,?)=?X?(?,?),?(?,?),?(?,?),?(?,?)?=?X?5,5.4,3.5,4?=3.5,?和?,?的最短距离2为最小距离，合并?和?,?为1个新簇?,?,?，此时簇集合为：?,?,?，?,?。由于合并后簇的数目已经达到了用户输入的终止条件，算法结束。AGNES算法算法23 8.3 基于层次的聚类AGNES算法算法24 8.3 基于层次的聚类步骤步骤簇集合簇集合最近的两个簇最近的两个簇合并后的新簇合并后的新簇?，?，?，?，?,?，?,?，?，?，?,?，?，?,?，?,?，?,?，?,?，?,?,?,?,?,?，?,?算法终止表8-10 AGNES执行过程簇的变化算法性能：AGNES算法比较简单，但一旦一组对象被合并，下一步的处理将在新生成的簇上进行。已做处理不能撤消，聚类之间也不能交换对象。增加新的样本对结果的影响较大。AGNES算法算法25 8.3 基于层次的聚类THANKS FOR YOUR ATTENTION感谢指导！感谢指导！