聚类分析基本概念和方法演示文稿

聚类分析基本概念和方法演示文稿当前第1页\共有20页\编于星期三\13点（优选）聚类分析基本概念和方法当前第2页\共有20页\编于星期三\13点凝聚的层次聚类方法使用自底向上的策略。分裂的层次聚类方法使用自顶向下的策略。：凝聚的与分裂的层次聚类层次聚类方法可以是凝聚的或分裂的，取决于层次分解是自底向上（合并）还是以自顶向下（分裂）方式形成。在凝聚或分裂聚类中，用户都可以指定期望的簇个数作为终止条件。当前第3页\共有20页\编于星期三\13点：凝聚的与分裂的层次聚类凝聚的层次聚类算法AGNES(AgglomerativeNESting)；分裂的层次聚类算法DIANA(DivisiveANAlysis)；单链接(single-linkoge)方法；树状图的树形结构来表示层次聚类的过程。详情见例10.3当前第4页\共有20页\编于星期三\13点：算法方法的距离度量

无论使用凝聚方法还是只用分类方法，一个核心问题是度量两个簇之间的距离，其中每个簇一般是一个对象集。4个广泛采用的簇间距离，也称链接度量(linkagemeasure)：最小距离：最大距离：均值距离：平均距离：当前第5页\共有20页\编于星期三\13点最近邻聚类算法(nearest-neighborclusteringalgorithm)单链接算法(single-linkagealgorithm)最小生成树算法(minimalspanningtreealgorithm)最远邻聚类算法(farthest-neighborclusteringalgorithm)全连接算法(complete-linkagealgorithm)例10.4：算法方法的距离度量当前第6页\共有20页\编于星期三\13点

BIRCH：使用聚类特征树的多阶段聚类平衡迭代归约和聚类(BalancedIterativeReducingandClusteringusingHierarchies,BIRCH):是为大量数值数据聚类设计的将层次聚类(在初始微聚类阶段)与诸如迭代地划分这样的其他聚类算法(在其后的宏聚类阶段)集成在一起克服了凝聚聚类方法所面临的两个困难可伸缩性不能撤销先前步骤所做的工作

当前第7页\共有20页\编于星期三\13点

BIRCH：使用聚类特征树的多阶段聚类BIRCH使用聚类特征来概括一个簇使用聚类特征树(CF-树)来表示聚类的层次结构这些结构帮助聚类方法在大型数据库甚至在流数据库中取得好的速度和伸缩性这些结构使得BIRCH方法对新对象增量或动态聚类也非常有效当前第8页\共有20页\编于星期三\13点

BIRCH：使用聚类特征树的多阶段聚类考虑一个n个d维的数据对象或点的簇。聚的聚类特征(ClusteringFeature,CF)是一个3维向量，汇总了对象簇的信息，定义如下：其中，LS是n个点的线性和(即)，而SS是数据点的平方和(即)。

聚类特征本质上是给定簇的统计汇总。使用聚类特征，我们可以很容易地推导出簇的许多有用的统计量。例如，簇的型心X0、半径R和直径D。

例10.5当前第9页\共有20页\编于星期三\13点

BIRCH：使用聚类特征树的多阶段聚类

BIRCH采用了一种多阶段聚类技术：数据集的单编扫描产生一个基本的好聚类，而一或多遍的额外扫描可以进一步地改进聚类质量。它主要包括两个阶段:阶段一：BIRCH扫描数据库，建立一棵存放于内存的初始CF-树，它可以被看做数据的多层压缩，试图保留数据的内在聚类结构。阶段二：BIRCH采用某个(选定的)聚类算法对CF树的叶节点进行聚类，把稀疏的簇当做离群点删除，而把稠密的簇合并为更大的簇。

当前第10页\共有20页\编于星期三\13点Chameleon(变色龙)是一种层次聚类算法，它采用动态建模来确定一对簇之间的相似度。在Chameleon中，簇的相似度依据如下两点评估：簇中对象的连接情况簇的邻近性图10.10解释Chameleon如何运作。：Chameleon：使用动态的建模的多阶段层次聚类当前第11页\共有20页\编于星期三\13点Chameleon根据两个簇Ci和Cj的相对互连度RI(Ci,Cj)和相对接近度RC(Ci,Cj)来决定它们的相似度：两个簇Ci和Cj的相对互连度RI(Ci,Cj)定义为Ci和Cj之间的绝对互连度关于两个簇Ci和Cj的内部互连度的规范化，即两个簇Ci和Cj的相对接近度RC(Ci,Cj)定义为Ci和Cj之间的绝对接近度关于两个簇Ci和Cj的内部互连度的规范化，定义如下：：Chameleon：使用动态的建模的多阶段层次聚类当前第12页\共有20页\编于星期三\13点：概率层次聚类算法的层次聚类方法使用连接度量，往往使得聚类容易理解并且有效。它们广泛用在许多聚类分析应用中。然而，算法的层次聚类方法也有一些缺点。为层次聚类选择一种好的距离度量常常是困难的为了使用算法的方法，数据对象不能有缺失的属性值大部分算法的层次聚类方法都是启发式的，在每一步局部地搜索好的合并/划分。因此，结果聚类层次结构的优化目标可能不清晰。当前第13页\共有20页\编于星期三\13点：概率层次聚类概率层次聚类(probabilistichierarchicalclustering)旨在通过使用概率模型度量簇之间的距离，克服以上某些缺点。一种看待聚类问题的方法是，把待聚类的数据对象集看做要分析的基础数据生成机制的一个样本，或生成模型(generativemodel)。实践中，我们可以假定该数据的生成模型采用常见的分布函数，如高斯分布或伯努利分布，它们由参数确定。于是，学习生成模型的任务就归结为找出使得模型最佳拟合观测数据集的参数值。

例10.6.当前第14页\共有20页\编于星期三\13点：概率层次聚类概率的层次聚类的一个缺点是，它只输出一个关于选取的概率模型的层次结构。它不能处理聚类层次结构的不确定性。给出一个数据集，可能存在多个拟合观测数据的层次结构。算法的方法和概率的方法都不能发现这些层次结构分布。最近，已经开发了贝叶斯树结构模型来处理这些问题。当前第15页\共有20页\编于星期三\13点划分和层次方法旨在发现球状簇，为了发现任意形状的簇，作为选择，我们可以把簇看做数据空间中被稀疏区域分开的稠密区域。这是基于密度的聚类方法的主要策略，该方法可以发现非球状的簇。基于密度聚类的基本技术-三种代表性的方法：DBSCANOPTICSDENCLUE10.4基于密度的方法当前第16页\共有20页\编于星期三\13点：DBSCAN：一种基于高密度连通区域的基于密度的聚类

“如何在基于密度的聚类中发现稠密区域？”对象O密度可以用靠近O的对象数度量。DBSCAN(Density-BasedSpatialClusteringofApplicationswithNoise，具有噪声应用的基于密度的空间聚类)找出核心对象，即其邻域稠密的对象。它连接核心对象和它们的邻域，形成稠密区域作为簇。“DBSCAN如何确定对象邻域？”一个用户指定的参数用来指定每个对象的邻域半径。对象O的邻域是以O为中心、以为半径的空间。当前第17页\共有20页\编于星期三\13点由于邻域大小由参数确定，因此，邻域的密度可以简单地用邻域内的对象数度量。为了确定一个邻域是否稠密，DBSCAN使用另一个用户指定的参数MinPts,指定稠密区域的密度阈值。如果一个对象的邻域至少包含MinPts个对象，则该对象是核心对象(coreobject)。核心对象是稠密区域的支柱。

给定一个对象集D，我们可以识别关于参数和MinPts的所有核心对象。聚类任务就归结为使用核心对象和它们的邻域形成稠密区域，这里稠密区域就是簇。对于核心对象q和对象p，我们说p是从q(关于和MinPts)直接密度可达的(directlydensity-reachable),如果p在q的邻域内。显然，对象p是从另一个对象q直接密度可达的，当且仅当q是核心对象，并且p在q的邻域中。：DBSCAN：一种基于高密度连通区域的基于密度的聚类当前第18页\共有20页\编于星期三\13点“如何使用以核心对象为中心的小稠密区域来装配一个大稠密区域？”在DBSCAN中，p是从q（关于和MinPts）密度可达的(density-reachable),如果存在一个对象链p1，p2，…，pn，使得p1=q，

pn=p，并且对于pi

D(1≤i≤n),pi+1是从pi关于和MinPts直接密度可达的。注意，密度可达不是等价关系，因为它不是对称的。如果o1和o2都是核心对象，并且o1是从o2密度可达的，则o2是从o1密度可达的。然而，如果o2是核心对象而o1不是，则o1可能是从o2密度可达的的，但反过来就不可以。：DBSCAN：一种基于高密度连通区域的基于密度的聚类当前第19页\共有20页\编于星期三\13点为了把核心对象与它的近邻连接成一个稠密区域，DBSCAN使用密度相连概念。两个对象p1,p2

D是关于和MinPts密度相连的(density-connec