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

1、第十章：聚类分析：基本概念和方法第十章：聚类分析：基本概念和方法10.310.3：层次方法：层次方法10.410.4：基于密度的方法：基于密度的方法10.3：层次方法：层次方法 层次聚类方法(hierarchical clustering method): 将数据对象组成层次结构或簇的“树”。对组织在层次结构中的数据进行汇总或特征化。层次划分可以递归继续，直到达到期望的粒度。层次结构对于数据可视化特别有用。一种提高层次方法聚类质量的有希望的方向是集成层次聚类与其他聚类技术，形成多阶段聚类。l凝聚的层次聚类方法使用自底向上的策略。l分裂的层次聚类方法使用自顶向下的策略。10.3.1：凝聚的与分裂

2、的层次聚类：凝聚的与分裂的层次聚类 层次聚类方法可以是凝聚的或分裂的，取决于层次分解是自底向上（合并）还是以自顶向下（分裂）方式形成。 在凝聚或分裂聚类中，用户都可以指定期望的簇个数作为终止条件。10.3.1：凝聚的与分裂的层次聚类：凝聚的与分裂的层次聚类凝聚的层次聚类算法AGNES(Agglomerative NESting)；分裂的层次聚类算法DIANA(Divisive ANAlysis)；单链接(single-linkoge)方法；树状图的树形结构来表示层次聚类的过程。详情见例10.310.3.2：算法方法的距离度量：算法方法的距离度量 无论使用凝聚方法还是只用分类方法，一个核心问题是

3、度量两个簇之间的距离，其中每个簇一般是一个对象集。 4个广泛采用的簇间距离簇间距离，也称链接度量链接度量(linkage measure)：最小距离：最大距离：均值距离：平均距离：min, (,)min |ijp Ci pCjdistC Cppmax, (,)max |ijp Ci p CjdistC Cpp( ,) |meanijijdistC Cmm, 1( ,)|ijavgijp Ci p CjdistC Cppnn最近邻聚类算法(nearest-neighbor clustering algorithm)单链接算法(single-linkage algorithm)最小生成树算法(mi

4、nimal spanning tree algorithm)最远邻聚类算法(farthest-neighbor clustering algorithm)全连接算法(complete-linkage algorithm)例10.410.3.2：算法方法的距离度量：算法方法的距离度量10.3.310.3.3 BIRCHBIRCH：使用聚类特征树的多阶段聚类：使用聚类特征树的多阶段聚类 平衡迭代归约和聚类(Balanced Iterative Reducing and Clustering using Hierarchies, BIRCH):是为大量数值数据聚类设计的将层次聚类(在初始微聚类阶段)

5、与诸如迭代地划分这样的其他聚类算法(在其后的宏聚类阶段)集成在一起克服了凝聚聚类方法所面临的两个困难可伸缩性不能撤销先前步骤所做的工作 10.3.310.3.3 BIRCHBIRCH：使用聚类特征树的多阶段聚类：使用聚类特征树的多阶段聚类BIRCH 使用聚类特征来概括一个簇使用聚类特征树(CF-树)来表示聚类的层次结构这些结构帮助聚类方法在大型数据库甚至在流数据库中取得好的速度和伸缩性这些结构使得BIRCH方法对新对象增量或动态聚类也非常有效10.3.310.3.3 BIRCHBIRCH：使用聚类特征树的多阶段聚类：使用聚类特征树的多阶段聚类 考虑一个n个d维的数据对象或点的簇。聚的聚类特征(

6、Clustering Feature, CF)是一个3维向量，汇总了对象簇的信息，定义如下：其中，LS是n个点的线性和(即 )，而SS是数据点的平方和(即 )。 聚类特征本质上是给定簇的统计汇总。使用聚类特征，我们可以很容易地推导出簇的许多有用的统计量。例如，簇的型心X0、半径R和直径D。 例10.5,CFn LS SS1niix21niix10.3.310.3.3 BIRCHBIRCH：使用聚类特征树的多阶段聚类：使用聚类特征树的多阶段聚类 BIRCH采用了一种多阶段聚类技术：数据集的单编扫描产生一个基本的好聚类，而一或多遍的额外扫描可以进一步地改进聚类质量。它主要包括两个阶段:l阶段一：B

7、IRCH扫描数据库，建立一棵存放于内存的初始CF-树，它可以被看做数据的多层压缩，试图保留数据的内在聚类结构。l阶段二：BIRCH采用某个(选定的)聚类算法对CF树的叶节点进行聚类，把稀疏的簇当做离群点删除，而把稠密的簇合并为更大的簇。 Chameleon(变色龙)是一种层次聚类算法，它采用动态建模来确定一对簇之间的相似度。在Chameleon中，簇的相似度依据如下两点评估：簇中对象的连接情况簇的邻近性图10.10解释Chameleon如何运作。10.3.410.3.4：ChameleonChameleon：使用动态的建模的多阶段层次聚类：使用动态的建模的多阶段层次聚类 Chameleon根据

8、两个簇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的内部互连度的规范化，定义如下：10.3.410.3.4：ChameleonChameleon：使用动态的建模的多阶段层次聚类：使用动态的建模的多阶段层次聚类|,|( ,)1(|)2ijC CijCiCjECRI C CECEC,(,)|ijEC Ci CjijiiECCECCiji

9、jSRC C CCCSSCCCC10.3.510.3.5：概率层次聚类：概率层次聚类 算法的层次聚类方法使用连接度量，往往使得聚类容易理解并且有效。它们广泛用在许多聚类分析应用中。然而，算法的层次聚类方法也有一些缺点。为层次聚类选择一种好的距离度量常常是困难的为了使用算法的方法，数据对象不能有缺失的属性值大部分算法的层次聚类方法都是启发式的，在每一步局部地搜索好的合并/划分。 因此，结果聚类层次结构的优化目标可能不清晰。10.3.510.3.5：概率层次聚类：概率层次聚类 概率层次聚类(probabilistic hierarchical clustering)旨在通过使用概率模型度量簇之间的

10、距离，克服以上某些缺点。 一种看待聚类问题的方法是，把待聚类的数据对象集看做要分析的基础数据生成机制的一个样本，或生成模型(generative model)。 实践中，我们可以假定该数据的生成模型采用常见的分布函数，如高斯分布或伯努利分布，它们由参数确定。于是，学习生成模型的任务就归结为找出使得模型最佳拟合观测数据集的参数值。 例10.6.10.3.510.3.5：概率层次聚类：概率层次聚类 概率的层次聚类的一个缺点是，它只输出一个关于选取的概率模型的层次结构。它不能处理聚类层次结构的不确定性。给出一个数据集，可能存在多个拟合观测数据的层次结构。算法的方法和概率的方法都不能发现这些层次结构分

11、布。最近，已经开发了贝叶斯树结构模型来处理这些问题。 划分和层次方法旨在发现球状簇，为了发现任意形状的簇，作为选择，我们可以把簇看做数据空间中被稀疏区域分开的稠密区域。这是基于密度的聚类方法的主要策略，该方法可以发现非球状的簇。基于密度聚类的基本技术-三种代表性的方法：DBSCANOPTICSDENCLUE10.4 10.4 基于密度的方法基于密度的方法10.4.110.4.1：DBSCANDBSCAN：一种基于高密度连通区域的基于密度的聚类：一种基于高密度连通区域的基于密度的聚类 “如何在基于密度的聚类中发现稠密区域如何在基于密度的聚类中发现稠密区域？”对象O O密度可以用靠近O O的对象数

12、度量。DBSCANDBSCAN(Density-Based Spatial Clustering of Applications with Noise，具有噪声应用的基于密度的空间聚类)找出核心对象核心对象，即其邻域稠密的对象。它连接核心对象核心对象和它们的邻域，形成稠密区域作为簇。 “DBSCANDBSCAN如何确定对象邻域如何确定对象邻域？”一个用户指定的参数 用来指定每个对象的邻域半径。对象O O的 邻域邻域是以O O为中心、以 为半径的空间。 由于邻域大小由参数 确定，因此，邻域的密度可以简单地用邻域内的对象数度量。为了确定一个邻域是否稠密，DBSCAN使用另一个用户指定的参数MinP

13、ts,指定稠密区域的密度阈值。如果一个对象的 邻域至少包含MinPts个对象，则该对象是核心对象(core objectcore object)。核心对象是稠密区域的支柱。 给定一个对象集D，我们可以识别关于参数 和MinPts的所有核心对象。聚类任务就归结为使用核心对象和它们的邻域形成稠密区域，这里稠密区域就是簇。对于核心对象q q和对象p p，我们说p p是从q q(关于 和MinPts)直接密度可直接密度可达的达的(directly density-reachable),如果p p在q q的 邻域内。显然，对象p p是从另一个对象q q直接密度可达的，当且仅当q q是核心对象，并且p p

14、在q q的 邻域中。10.4.110.4.1：DBSCANDBSCAN：一种基于高密度连通区域的基于密度的聚类：一种基于高密度连通区域的基于密度的聚类 “如何使用以核心对象为中心的小稠密区域来装配一个大稠密区域？”在DBSCAN中，p p是从q q（关于 和MinPts）密度可达的(density-reachable),如果存在一个对象链p1，p2，pn，使得p1=q， pn=p，并且对于pi D(1in),pi+1是从pi关于 和MinPts直接密度可达的。注意，密度可达不是等价关系，因为它不是对称的。如果o1和o2都是核心对象，并且o1是从o2密度可达的，则o2是从o1密度可达的。然而，如

15、果o2是核心对象而o1不是，则o1可能是从o2密度可达的的，但反过来就不可以。10.4.110.4.1：DBSCANDBSCAN：一种基于高密度连通区域的基于密度的聚类：一种基于高密度连通区域的基于密度的聚类 为了把核心对象与它的近邻连接成一个稠密区域，DBSCANDBSCAN使用密度相连概念。两个对象p p1,p p2 D是关于 和MinPts密度相连的密度相连的(density-connected),如果存在一个对象q q D,使得对象p p1和p p2都是从q q关于 和MinPts密度可达。不像密度可达，密度相连是等价关系。容易证明，对于对象o1、o2和o3，如果o1和o2是密度相连的

16、，并且o2和o3是密度相连的，则o1和o2也是密度相连的。例10.7。10.4.110.4.1：DBSCANDBSCAN：一种基于高密度连通区域的基于密度的聚类：一种基于高密度连通区域的基于密度的聚类 我们可以使用密度相连的闭包来发现连通的稠密区域作为簇。每个闭集都是一个基于密度的簇。子集C D是一个簇，如果（1）对于任意两个对象o1、o2 C, o1、o2 是密度相连的，并且（2）不存在对象o C和另一个对象o(D-C),使得o和o是密度相连的。 “DBSCAN如何发现簇？” 如果使用空间索引，则DBSCAN计算复杂度为O(nlogn)，其中n是数据库对象数，其复杂度为O(n2)。如果用户定

17、义的参数 和MinPts设置恰当，则该算法可以有效地发现任意形状的簇。10.4.110.4.1：DBSCANDBSCAN：一种基于高密度连通区域的基于密度的聚类：一种基于高密度连通区域的基于密度的聚类10.4.210.4.2：OPTICS:OPTICS:通过点排序识别聚类结构通过点排序识别聚类结构 为了克服在聚类分析中使用一组全局参数的缺点，提出了OPTICS聚类分析方法。OPTICS并不显式地产生数据集聚类，而是输出簇排序(clustering ordering)。这个排序是所有分析对象的线性表，并且代表了数据的基于密度的聚类结构。较稠密簇中的对象在簇排序中相互靠近。这个排序等价于从广泛的参

18、数设置中得到的基于密度的聚类。这样OPTICS不需要用户提供特定密度阈值。簇排序可以用来提取基本的聚类信息，导出内在的聚类结构，也可以提供聚类的可视化。 为了同时构造不同的聚类，对象需要按特定次序处理。这个次序选择这样的对象，即关于最小的 值，它是密度可达的，以便较高密度（较低 值）的簇先完成。基于这个想法，对于每个对象，OPTICS需要两个重要信息：对象p的核心距离核心距离(core-distance)是最小的值 ，使得p的 -邻域内至少有MinPits个对象。也就是说， 是使得p成为核心对象的最小半径阈值。如果p不是关于 和MinPts个对象，则p的核心距离没有定义。从对象q到对象p的可达

19、距离可达距离(reachability-distance)是使p从q密度可达的最小半径值。根据密度可达的定义，q必须是核心对象，并且p必须在q的邻域内。因此，从q到p的可达距离maxcore-distance(q),dist(p,q)。如果q不是关于 和MinPts的核心对象，则从q到p的可达距离没有定义。10.4.210.4.2：OPTICS:OPTICS:通过点排序识别聚类结构通过点排序识别聚类结构10.4.310.4.3：DENCLUE:DENCLUE:基于密度分布函数的聚类基于密度分布函数的聚类 DENCLUE(DENsity-based CLUstEring,基于密度的聚类)是一种基

20、于一组密度分布函数的聚类算法。 在概率统计中，密度估计是根据一系列观测数据集来估计不可观测的概率密度函数。在基于密度聚类的背景下，不可观测的概率密度函数是待分析的所有可能的对象的总体的真实分布。观测数据集被看做取自该总体的一个随机样本。 这种密度估计对所有使用的半径值非常敏感。为了解决这一问题，可以使用核密度估计(kernel density estimation),它是源自统计学的非参数密度估计方法。核密度估计的一般思想是简单的。我们把每个观测对象都看做周围区域中高概率密度的一个指示器。一个点上的概率密度依赖于从该点到观测对象的距离。10.4.310.4.3：DENCLUE:DENCLUE:

21、基于密度分布函数的聚类基于密度分布函数的聚类 DENCLUE使用高斯核估计基于给定的待聚类的对象密度。点x*称做密度吸引点(density attractor)，如果它是估计的密度函数的局部最大点。为了避免平凡的局部最大点，DENCLUE使用一个噪声阈值 ，并且满足 的密度吸引点x*。这些非平凡密度吸引点都是簇中心。 DENCLUE的一个簇是一个密度吸引点的集合X和一个输入对象的集合C，使得C中的每个对象都被分配到X中的一个密度吸引点，并且没对密度吸引点之间都存在一条其密度大于 的路径。通过使用被路径连接的多个密度吸引点，DENCLUE可以发现任意形状的簇。 DENCLUE有一些优点。它可以视为多种著名的聚类方法（如单链接方法和DBSCAN）的一般化。此外，DENCLUE是抗噪声的。核密度估计通过把噪声均匀地分布到输入数据，可以有效地降低噪声的影响。f ( *)x