数据挖掘6

聚类一个将数据集划分为若干组或类的过程，并使得同一个组内的数据对象具有较高的相似度；而不同组中的数据对象是不相似的。相似或不相似的描述是基于数据描述属性的取值来确定的。通常就是利用（各对象间）距离来进行表示的。聚类（Clustering）聚类（Clustering）是对物理的或抽象的对象集合分组的过程。聚类生成的组称为簇（Cluster），簇是数据对象的集合。簇内部的任意两个对象之间具有较高的相似度，而属于不同簇的两个对象间具有较高的相异度。相异度可以根据描述对象的属性值计算，对象间的距离是最常采用的度量指标。聚类分析简介聚类分析是数据分析中的一种重要技术，它的应用极为广泛。许多领域中都会涉及聚类分析方法的应用与研究工作，如数据挖掘、统计学、机器学习、模式识别、生物学、空间数据库技术、电子商务等。聚类分析简介从机器学习的角度讲，簇相当于隐藏模式。聚类是搜索簇的无监督学习过程。与分类不同，无监督学习不依赖预先定义的类或带类标记的训练实例，需要由聚类学习算法自动确定标记，而分类学习的实例或数据对象有类别标记。聚类是观察式学习，而不是示例式的学习。聚类算法特性数据挖掘工作希望聚类算法具备如下特性：处理不同类型属性的能力对大型数据集的可扩展性处理高维数据的能力发现任意形状簇的能力处理孤立点或“噪声”数据的能力对数据顺序的不敏感性对先验知识和用户自定义参数的弱依赖性基于约束的聚类聚类结果的可解释性和实用性数据矩阵（DataMatrix）设有n个对象，可用p个变量（属性）描述每个对象，则np矩阵称为数据矩阵。数据矩阵是对象-变量结构的数据表达方式。npnnppxxxxxxxxx212222111211相异度矩阵（DissimilarityMatrix）按n个对象两两间的相异度构建n阶矩阵（因为相异度矩阵是对称的，只需写出上三角或下三角即可）：其中d(i,j)表示对象i与j的相异度，它是一个非负的数值。当对象i和j越相似或“接近”时，d(i,j)值越接近0；而对象i和j越不相同或相距“越远”时，d(i,j)值越大。显然，d(i,j)=d(j,i)，d(i,i)=0。相异度矩阵是对象-对象结构的一种数据表达方式。0)2,()1,(0)2,3()1,3(0)1,2(0ndndddd对象间距离的计算设两个p维向量xi=(xi1,xi2,…,xip)T和xj=(xj1,xj2,…,xjp)T分别表示两个对象，有多种形式的距离度量可以采用。闵可夫斯基（Minkowski）距离：曼哈坦（Manhattan）距离：欧几里得（Euclidean）距离：切比雪夫（Chebyshev）距离：马哈拉诺比斯（Mahalanobis）距离：划分方法简介对于一个给定的n个对象或元组的数据库，采用目标函数最小化的策略，通过迭代把数据分成k个划分块，每个划分块为一个簇，这就是划分方法。划分方法满足两个条件：（1）每个分组至少包含一个对象；（2）每个对象必属于且仅属于某一个分组。常见的划分方法有k-均值方法和k-中心点方法。其他方法大都是这两种方法的变形。k-均值算法k-均值聚类算法的核心思想是通过迭代把数据对象划分到不同的簇中，以求目标函数最小化，从而使生成的簇尽可能地紧凑和独立。首先，随机选取k个对象作为初始的k个簇的质心；然后，将其余对象根据其与各个簇质心的距离分配到最近的簇；再求新形成的簇的质心。这个迭代重定位过程不断重复，直到每个聚类不再发生变化为止。k-均值算法输入期望得到的簇的数目k，n个对象的数据库。输出使得平方误差准则函数最小化的k个簇。方法选择k个对象作为初始的簇的质心；repeat计算对象与各个簇的均值的距离，将对象划分到距离其最近的簇；重新计算每个新簇的均值；until簇的均值不再变化。k-中心点算法(PAM)k-均值算法采用簇的质心来代表一个簇，质心是簇中其他对象的参照点。因此，k-均值算法对孤立点是敏感的，如果具有极大值，就可能大幅度地扭曲数据的分布。k-中心点算法是为消除这种敏感性提出的，它选择簇中位置最接近簇中心的对象（称为中心点）作为簇的代表点，目标函数仍然可以采用平方误差准则。采用k-中心点算法有两个好处：对属性类型没有局限性；通过簇内主要点的位置来确定选择中心点，对孤立点的敏感性小。k-中心点算法的处理过程首先，随机选择k个对象作为初始的k个簇的代表点，将其余对象根据其与代表点对象的距离分配到最近的簇；然后，反复用非代表点来代替代表点，以改进聚类质量，聚类质量用一个代价函数来估计，该函数度量对象与代表点对象之间的平均相异度。k-中心点算法输入n个对象的数据库，期望得到的簇的数目k输出使得所有对象与其最近中心点的偏差总和最小化的k个簇方法选择k个对象作为初始的簇中心repeat对每个对象，计算离其最近的簇中心点，并将对象分配到该中心点代表的簇随机选取非中心点Orandom计算用Orandom代替Oj形成新集合的总代价S如果S0，用Orandom代替Oj，形成新的k个中心点的集合until不再发生变化层次聚类层次聚类按数据分层建立簇，形成一棵以簇为节点的树，称为聚类图。按自底向上层次分解，则称为凝聚的层次聚类。按自顶向下层次分解，就称为分裂的层次聚类。凝聚的和分裂的层次聚类凝聚的层次聚类采用自底向上的策略，开始时把每个对象作为一个单独的簇，然后逐次对各个簇进行适当合并，直到满足某个终止条件。分裂的层次聚类采用自顶向下的策略，与凝聚的层次聚类相反，开始时将所有对象置于同一个簇中，然后逐次将簇分裂为更小的簇，直到满足某个终止条件。距离度量簇的凝聚或分裂要遵循一定的距离（或相似度）准则。常见的簇间距离度量方法如下：最小距离（单链接方法）最大距离（完全链接方法）平均距离（平均链接方法）均值的距离（质心方法）对象间距离函数有欧氏距离、曼哈坦距离、闵可夫斯基距离、马氏距离等。凝聚的和分裂的层次聚类a,b,c,d,ec,d,ed,ea,bedcba第4步第3步第2步第1步第0步凝聚的（AGENS）第0步第1步第2步第3步第4步分类的（DIANA）层次聚类方法的优缺点层次聚类方法的优点在于可以在不同粒度水平上对数据进行探测，而且容易实现相似度量或距离度量。单纯的层次聚类算法终止条件含糊，而且执行合并或分裂簇的操作后不可修正，这很可能导致聚类结果质量很低。由于需要检查和估算大量的对象或簇才能决定簇的合并或分裂，所以这种方法的可扩展性较差。通常考虑把层次聚类方法与其他方法（如迭代重定位方法）相结合来解决实际聚类问题。层次聚类和其他聚类方法的有效集成可以形成多阶段聚类，能够改善聚类质量。这类方法包括BIRCH、CURE、ROCK、Chameleon等。BIRCH算法BIRCH(BalancedIterativeReducingandClusteringusingHierarchies)算法利用层次方法进行平衡迭代归约和聚类。首先将对象划分成树形结构，然后采用其他聚类算法对聚类结果求精。BIRCH的核心概念是聚类特征和聚类特征树（CF树），并用于概括聚类描述。采用这种结构可以提高聚类算法对大型数据库的高效性和可扩展性。CURE算法CURE（利用代表点聚类）算法是介于基于质心方法和基于代表对象点方法之间的策略。在CURE算法中，不是利用质心点或单个代表对象来代表一个簇，而是首先在簇中选取固定数目的、离散分布的点，用这些点反映簇的形状和范围。然后把离散的点按收缩因子向簇的质心收缩。收缩后的离散点作为簇的代表点。两个簇的距离定义为代表点对（分别来自两个簇）距离的最小值，在CURE算法的每一步合并距离最近的两个簇。Chameleon算法虽然基于静态模型的聚类算法在多数情况下是有效的，但如果选择的静态模型参数不恰当或模型不能充分体现簇的特征，静态算法生成的簇质量就较低。当数据中包含多种形状、密度和尺寸的簇时，使用静态算法往往会失效。Chameleon算法是一种采用动态建模技术的层次聚类算法，是在CURE算法和ROCK算法的基础上提出的。Chameleon算法（续）CURE算法及其相关方案忽略了两个不同簇中数据项的聚集互联性信息；Chameleon算法既考虑两个簇之间的互联性，又考虑两个簇之间的接近度。在建立两个不同簇间互联度和接近度时，利用每个簇内部对象的特征来确定最相似的子簇。因此，Chameleon不依赖于静态的、用户提供的模型，而是能够用动态建模的技术自动适应被合并的簇的内部特征。Chameleon算法（续）Chameleon算法分两个步骤。第一步利用图划分算法将数据对象聚类为若干相对较小的子聚类。另一步是采用凝聚的层次聚类算法合并子簇，从而发现真实的簇。Chameleon中数据项的稀疏图表示采用k-最近邻居图方法。数据库k-最近邻居图数据库最终的族构建稀疏图划分图合并划分块基于密度的方法基于密度方法能够帮助发现具有任意形状的聚类。一般在一个数据空间中，高密度的对象区域被低密度（稀疏）的对象区域（通常就认为是噪声数据）所分割。基于密度的方法简介基于密度的方法主要有两类，即基于连通性的算法和基于密度函数的算法。基于连通性的算法包括DBSCAN、GDBSCAN、OPTICS、DBCLASD等；基于密度函数的算法有DBNCLUE等算法。DBSCAN算法DBSCAN（DensityBasedSpatialClusteringofApplicationswithNoise）算法是一种基于密度的聚类算法，它将足够高密度的区域划分为簇，能够在含有“噪声”的空间数据库中发现任意形状的簇。一些概念直接密度可达点p的ε-邻域记为Nε(p)，定义如下：Nε(p)={qD|dist(p,q)≤ε}如果p，q满足下列条件：（1）pNε(p)，（2）∣Nε(p)∣≥MinPts，则称点p是从点q关于ε和MinPts直接密度可达的。p：边界点q：核心点p是从q直接密度可达的，而q不是从p直接密度可达的pqqq(a)(b)密度可达如果存在一个点的序列p1,p2,…,pn，p1=q，pn=p，pi+1是从pi直接密度可达的，则称点p是从点q关于ε和MinPts密度可达的。p是从q密度可达的，q不是从p密度可达的P和q通过o密度相连pqqp（a）（b）密度相连如果存在一个点o，p和q都是从点o关于ε和MinPts密度可达的，则称点p是从点q关于ε和MinPts密度相连的。基于密度的簇令D表示数据点的集合，若D的非空子集C满足下列条件：对任意p和q，若pC且q是从p关于ε和MinPts密度可达的，则有qC。（最大性）p,qC:p与q是关于ε和MinPts密度相连的。（连通性）则称C是基于密度的簇。基于密度的簇是基于密度可达的最大的密度相连的点的集合。噪声令C1,C2,…,Ck是数据库中分别关于参数εi和MinPtsi构成的簇（i=1,2,…,k），则定义“噪声”为数据库D中不属于任何簇的数据点的集合，即集合{pD|i:pCi}簇的发现给定参数ε和MinPts，可以分两步发现簇。第一步，从数据库中任意选取一个满足核心点条件的点作为种子；第二步，检索从种子点密度可达的所有点，获得包括种子点在内的簇。算法的正确性引理1令p为数据库D中的一个点，∣Nε(p)∣≥MinPts，则集合O={o|oD且o是从p关于ε和MinPts密度可达的}是一个关于ε和MinPts的簇。引理2令C为一个关于ε和MinPts的簇，p为C中某个满足∣Nε(p)∣≥MinPts的点，则C等于集合O={o|oD且o是从p关于ε和MinPts密度可达的}。DBSCAN算法DBSCAN算法可以发现空间数据库中的簇和“噪声”。但必须为每个簇指定恰当的参数ε和MinPts，及至少每个簇中的一个点。为发现簇，DBSCAN算