聚类分析基本概念和方法

10.3：层次方法层次聚类方法(hierarchicalclusteringmethod):将数据对象组成层次结构或簇的“树”。对组织在层次结构中的数据进行汇总或特征化。层次划分可以递归继续，直到达到期望的粒度。层次结构对于数据可视化特别有用。一种提高层次方法聚类质量的有希望的方向是集成层次聚类与其他聚类技术，形成多阶段聚类。凝聚的层次聚类方法使用自底向上的策略。分裂的层次聚类方法使用自顶向下的策略。10.3.1：凝聚的与分裂的层次聚类层次聚类方法可以是凝聚的或分裂的，取决于层次分解是自底向上（合并）还是以自顶向下（分裂）方式形成。在凝聚或分裂聚类中，用户都可以指定期望的簇个数作为终止条件。10.3.1：凝聚的与分裂的层次聚类凝聚的层次聚类算法AGNES(AgglomerativeNESting)；分裂的层次聚类算法DIANA(DivisiveANAlysis)；单链接(single-linkoge)方法；树状图的树形结构来表示层次聚类的过程。详情见例10.310.3.2：算法方法的距离度量无论使用凝聚方法还是只用分类方法，一个核心问题是度量两个簇之间的距离，其中每个簇一般是一个对象集。4个广泛采用的簇间距离，也称链接度量(linkagemeasure)：最小距离：最大距离：均值距离：平均距离：min,'(,)min{|'|}ijpCipCjdistCCppmax,'(,)max{|'|}ijpCipCjdistCCpp(,)||meanijijdistCCmm,'1(,)|'|ijavgijpCipCjdistCCppnn最近邻聚类算法(nearest-neighborclusteringalgorithm)单链接算法(single-linkagealgorithm)最小生成树算法(minimalspanningtreealgorithm)最远邻聚类算法(farthest-neighborclusteringalgorithm)全连接算法(complete-linkagealgorithm)例10.410.3.2：算法方法的距离度量10.3.3BIRCH：使用聚类特征树的多阶段聚类平衡迭代归约和聚类(BalancedIterativeReducingandClusteringusingHierarchies,BIRCH):是为大量数值数据聚类设计的将层次聚类(在初始微聚类阶段)与诸如迭代地划分这样的其他聚类算法(在其后的宏聚类阶段)集成在一起克服了凝聚聚类方法所面临的两个困难可伸缩性不能撤销先前步骤所做的工作10.3.3BIRCH：使用聚类特征树的多阶段聚类BIRCH使用聚类特征来概括一个簇使用聚类特征树(CF-树)来表示聚类的层次结构这些结构帮助聚类方法在大型数据库甚至在流数据库中取得好的速度和伸缩性这些结构使得BIRCH方法对新对象增量或动态聚类也非常有效10.3.3BIRCH：使用聚类特征树的多阶段聚类考虑一个n个d维的数据对象或点的簇。聚的聚类特征(ClusteringFeature,CF)是一个3维向量，汇总了对象簇的信息，定义如下：其中，LS是n个点的线性和(即)，而SS是数据点的平方和(即)。聚类特征本质上是给定簇的统计汇总。使用聚类特征，我们可以很容易地推导出簇的许多有用的统计量。例如，簇的型心X0、半径R和直径D。例10.5,,CFnLSSS1niix21niix10.3.3BIRCH：使用聚类特征树的多阶段聚类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之间的绝对互连度关于两个簇Ci和Cj的内部互连度的规范化，即两个簇Ci和Cj的相对接近度RC(Ci,Cj)定义为Ci和Cj之间的绝对接近度关于两个簇Ci和Cj的内部互连度的规范化，定义如下：10.3.4：Chameleon：使用动态的建模的多阶段层次聚类|,|||(,)1(||||)2ijCCijCiCjECRICCECEC{,}(,)||||||||||||ijECCiCjijiiECCECCijijSRCCCCCSSCCCC10.3.5：概率层次聚类算法的层次聚类方法使用连接度量，往往使得聚类容易理解并且有效。它们广泛用在许多聚类分析应用中。然而，算法的层次聚类方法也有一些缺点。为层次聚类选择一种好的距离度量常常是困难的为了使用算法的方法，数据对象不能有缺失的属性值大部分算法的层次聚类方法都是启发式的，在每一步局部地搜索好的合并/划分。因此，结果聚类层次结构的优化目标可能不清晰。10.3.5：概率层次聚类概率层次聚类(probabilistichierarchicalclustering)旨在通过使用概率模型度量簇之间的距离，克服以上某些缺点。一种看待聚类问题的方法是，把待聚类的数据对象集看做要分析的基础数据生成机制的一个样本，或生成模型(generativemodel)。实践中，我们可以假定该数据的生成模型采用常见的分布函数，如高斯分布或伯努利分布，它们由参数确定。于是，学习生成模型的任务就归结为找出使得模型最佳拟合观测数据集的参数值。例10.6.10.3.5：概率层次聚类概率的层次聚类的一个缺点是，它只输出一个关于选取的概率模型的层次结构。它不能处理聚类层次结构的不确定性。给出一个数据集，可能存在多个拟合观测数据的层次结构。算法的方法和概率的方法都不能发现这些层次结构分布。最近，已经开发了贝叶斯树结构模型来处理这些问题。划分和层次方法旨在发现球状簇，为了发现任意形状的簇，作为选择，我们可以把簇看做数据空间中被稀疏区域分开的稠密区域。这是基于密度的聚类方法的主要策略，该方法可以发现非球状的簇。基于密度聚类的基本技术-三种代表性的方法：DBSCANOPTICSDENCLUE10.4基于密度的方法10.4.1：DBSCAN：一种基于高密度连通区域的基于密度的聚类“如何在基于密度的聚类中发现稠密区域？”对象O密度可以用靠近O的对象数度量。DBSCAN(Density-BasedSpatialClusteringofApplicationswithNoise，具有噪声应用的基于密度的空间聚类)找出核心对象，即其邻域稠密的对象。它连接核心对象和它们的邻域，形成稠密区域作为簇。“DBSCAN如何确定对象邻域？”一个用户指定的参数用来指定每个对象的邻域半径。对象O的邻域是以O为中心、以为半径的空间。由于邻域大小由参数确定，因此，邻域的密度可以简单地用邻域内的对象数度量。为了确定一个邻域是否稠密，DBSCAN使用另一个用户指定的参数MinPts,指定稠密区域的密度阈值。如果一个对象的邻域至少包含MinPts个对象，则该对象是核心对象(coreobject)。核心对象是稠密区域的支柱。给定一个对象集D，我们可以识别关于参数和MinPts的所有核心对象。聚类任务就归结为使用核心对象和它们的邻域形成稠密区域，这里稠密区域就是簇。对于核心对象q和对象p，我们说p是从q(关于和MinPts)直接密度可达的(directlydensity-reachable),如果p在q的邻域内。显然，对象p是从另一个对象q直接密度可达的，当且仅当q是核心对象，并且p在q的邻域中。10.4.1：DBSCAN：一种基于高密度连通区域的基于密度的聚类“如何使用以核心对象为中心的小稠密区域来装配一个大稠密区域？”在DBSCAN中，p是从q（关于和MinPts）密度可达的(density-reachable),如果存在一个对象链p1，p2，…，pn，使得p1=q，pn=p，并且对于piD(1≤i≤n),pi+1是从pi关于和MinPts直接密度可达的。注意，密度可达不是等价关系，因为它不是对称的。如果o1和o2都是核心对象，并且o1是从o2密度可达的，则o2是从o1密度可达的。然而，如果o2是核心对象而o1不是，则o1可能是从o2密度可达的的，但反过来就不可以。10.4.1：DBSCAN：一种基于高密度连通区域的基于密度的聚类为了把核心对象与它的近邻连接成一个稠密区域，DBSCAN使用密度相连概念。两个对象p1,p2D是关于和MinPts密度相连的(density-connected),如果存在一个对象qD,使得对象p1和p2都是从q关于和MinPts密度可达。不像密度可达，密度相连是等价关系。容易证明，对于对象o1、o2和o3，如果o1和o2是密度相连的，并且o2和o3是密度相连的，则o1和o2也是密度相连的。例10.7。10.4.1：DBSCAN：一种基于高密度连通区域的基于密度的聚类我们可以使用密度相连的闭包来发现连通的稠密区域作为簇。每个闭集都是一个基于密度的簇。子集CD是一个簇，如果（1）对于任意两个对象o1、o2C,o1、o2是密度相连的，并且（2）不存在对象oC和另一个对象o’(D-C),使得o和o’是密度相连的。“DBSCAN如何发现簇？”…如果使用空间索引，则DBSCAN计算复杂度为O(nlogn)，其中n是数据库对象数，其复杂度为O(n2)。如果用户定义的参数和MinPts设置恰当，则该算法可以有效地发现任意形状的簇。10.4.1：DBSCAN：一种基于高密度连通区域的基于密度的聚类10.4.2：OPTICS:通过点排序识别聚类结构为了克服在聚类分析中使用一组全局参数的缺点，提出了OPTICS聚类分析方法。OPTICS并不显式地产生数据集聚类，而是输出簇排序(clusteringordering)。这个排序是所有分析对象的线性表，并且代表了数据的基于密度的聚类结构。较稠密簇中的对象在簇排序中相互靠近。这个排序等价于从广泛的参数设置中得到的基于密度的聚类。这样OPTICS不需要用户提供特定密度阈值。簇排序可以用来提取基本的聚类信息，导出内在的聚类结构，也可以提供聚类的可视化。