第10章 聚类分析：基本概念和方法.ppt

第十章：聚类分析：基本概念和方法 10.3：层次方法 10.4：基于密度的方法 10.3：层次方法 层次聚类方法(hierarchical clustering method): 将数据对象组成层次结构或簇的“树”。 对组织在层次结构中的数据进行汇总或特征化。 层次划分可以递归继续，直到达到期望的粒度。 层次结构对于数据可视化特别有用。 一种提高层次方法聚类质量的有希望的方向是集成层次聚类与其他聚类技术，形成多阶段聚类。 凝聚的层次聚类方法使用自底向上的策略。 分裂的层次聚类方法使用自顶向下的策略。 10.3.1：凝聚的与分裂的层次聚类 层次聚类方法可以是凝聚的或分裂的，取决于层次分解是自底向上（合并）还是以自顶向下（分裂）方式形成。 在凝聚或分裂聚类中，用户都可以指定期望的簇个数作为终止条件。 10.3.1：凝聚的与分裂的层次聚类 凝聚的层次聚类算法AGNES(Agglomerative NESting)； 分裂的层次聚类算法DIANA(Divisive ANAlysis)； 单链接(single-linkoge)方法； 树状图的树形结构来表示层次聚类的过程。 详情见例10.3 10.3.2：算法方法的距离度量 无论使用凝聚方法还是只用分类方法，一个核心问题是度量两个簇之间的距离，其中每个簇一般是一个对象集。 4个广泛采用的簇间距离，也称链接度量(linkage measure)： 最小距离： 最大距离： 均值距离： 平均距离： 最近邻聚类算法(nearest-neighbor clustering algorithm) 单链接算法(single-linkage algorithm) 最小生成树算法(minimal spanning tree algorithm) 最远邻聚类算法(farthest-neighbor clustering algorithm) 全连接算法(complete-linkage algorithm) 例10.4 10.3.2：算法方法的距离度量 10.3.3 BIRCH：使用聚类特征树的多阶段聚类 平衡迭代归约和聚类(Balanced Iterative Reducing and Clustering using Hierarchies, BIRCH): 是为大量数值数据聚类设计的 将层次聚类(在初始微聚类阶段)与诸如迭代地划分这样的其他聚类算法(在其后的宏聚类阶段)集成在一起 克服了凝聚聚类方法所面临的两个困难 可伸缩性 不能撤销先前步骤所做的工作 10.3.3 BIRCH：使用聚类特征树的多阶段聚类 BIRCH 使用聚类特征来概括一个簇 使用聚类特征树(CF-树)来表示聚类的层次结构 这些结构帮助聚类方法在大型数据库甚至在流数据库中取得好的速度和伸缩性 这些结构使得BIRCH方法对新对象增量或动态聚类也非常有效 10.3.3 BIRCH：使用聚类特征树的多阶段聚类 考虑一个n个d维的数据对象或点的簇。聚的聚类特征(Clustering Feature, CF)是一个3维向量，汇总了对象簇的信息，定义如下： 其中，LS是n个点的线性和(即 )，而SS是数据点的平方和(即 )。 聚类特征本质上是给定簇的统计汇总。使用聚类特征，我们可以很容易地推导出簇的许多有用的统计量。例如，簇的型心X0、半径R和直径D。 例10.5 10.3.3 BIRCH：使用聚类特征树的多阶段聚类 BIRCH采用了一种多阶段聚类技术：数据集的单编扫描产生一个基本的好聚类，而一或多遍的额外扫描可以进一步地改进聚类质量。它主要包括两个阶段: 阶段一：BIRCH扫描数据库，建立一棵存放于内存的初始CF-树，它可以被看做数据的多层压缩，试图保留数据的内在聚类结构。 阶段二：BIRCH采用某个(选定的)聚类算法对CF树的叶节点进行聚类，把稀疏的簇当做离群点删除，而把稠密的簇合并为更大的簇。 Chameleon(变色龙)是一种层次聚类算法，它采用动态建模来确定一对簇之间的相似度。在Chameleon中，簇的相似度依据如下两点评估： 簇中对象的连接情况 簇的邻近性 图10.10解释Chameleon如何运作。 10.3.4：Chameleon：使用动态的建模的多阶段层次聚类 Chameleon根据两个簇Ci和Cj的相对互连度RI(Ci,Cj)和相对接近度RC(Ci,Cj)来决定它们的相似度： 两个簇Ci和Cj的相对互连度RI(Ci,Cj)定义为Ci和Cj之间的绝对互连度关于两个簇