模式识别与人工智能之八课件

Pattern Recognition&artificial IntelligenceLecture 7:聚聚类算法（四）算法（四）1基于密度的聚类算法基于密度的聚类算法DBSCANDBSCAN：基于高密度连通区域聚类：基于高密度连通区域聚类 OPTICSOPTICS：通过点排序识别聚类结构：通过点排序识别聚类结构DENCLUE:DENCLUE:基于密度分布函数的聚类基于密度分布函数的聚类 2基于密度的聚类方法基于密度的聚类方法划分划分和和层次层次方法旨在发现球状类。他们很难发现任方法旨在发现球状类。他们很难发现任意形状的类。意形状的类。改进思想，将改进思想，将类类看作数据空间中由低密度区域分隔看作数据空间中由低密度区域分隔开的高密度对象区域。这是基于密度的聚类方法开的高密度对象区域。这是基于密度的聚类方法的主要策略。的主要策略。基于密度的聚类方法可以用来过滤噪声孤立点数据，基于密度的聚类方法可以用来过滤噪声孤立点数据，发现任意形状的类。发现任意形状的类。3密度概念密度概念核心对象核心对象(Core object):一个对象的邻域至少包含最小数目MinPts个对象。边界点：边界点：不是核心点，但落在某个核心 点的 Eps 邻域内的对象称为边界点。噪声：噪声：不属于任何类的对象为噪声。边界对象：边界对象：对于空间中的一个对象，如果它在给定半径e的邻域中的对象个数大于密度阀值MinPts，则该对象被称为核核心对象心对象，否则称为边界对象边界对象。4由一个核心对象和其密度可达的所有对象构成聚类由一个核心对象和其密度可达的所有对象构成聚类。直接密度可达的直接密度可达的(Directly density reachable,DDR):给定对象集合D,如果p是在q的邻域内,而q是核心对象,我们说对象p是从对象q直接密度可达的(如果q是一个核心对象，p属于q的邻域，那么称p直接密度可达q。)密度可达的密度可达的(density reachable):存在一个从p到q的DDR对象链(如果存在一条链，满足p1=p，pi=q，pi直接密度可达pi+1，则称p密度可达q)密度概念密度概念两个参数两个参数:Eps:邻域的最大半径邻域的最大半径MinPts:在在 Eps-邻域中的最少点数邻域中的最少点数 NEps(q):q belongs to D|dist(p,q)=MinPts 密度概念密度概念6密度可达密度可达:点点 p 关于关于Eps,MinPts 是从是从 q密度可达密度可达的的,如果如果 存在一个节点链存在一个节点链 p1,pn,p1=q,pn=p 使得使得 pi+1 是从是从pi直接密度直接密度可达的可达的密度相连的密度相连的:点点 p关关于于 Eps,MinPts 与与点点 q是是密密度度相相连连的的,如如果果 存存在在点点 o 使使得得,p 和和 q 都都是是关关于于Eps,MinPts 是是从从 o 密密度度可可达达的的(如果存在o，o密度可达q和p，则称p和q是密度连通密度连通的)pqp1pqo密度概念密度概念7Eg:假设半径 =3，MinPts=3。点p的 邻域中有点m,p,p1,p2,o,点m的 邻域中有点m,q,p,m1,m2,点q的 邻域有q,m,点o的 邻域中有点o,p,s,点s的 邻域中有点o,s,s1.那么核心对象有p,m,o,s(q不不是是核核心心对对象象，因为它对应的 领域中点数量等于2，小于MinPts=3)；点m从点p直直接接密密度度可可达达，因为m在p的 领域内，并且p为核心对象；点q从点p密密度度可可达达，因为点q从点m直接密度可达，并且点m从点p直接密度可达；点q到点s密密度度相相连连，因为点q从点p密度可达，并且s从点p密度可达。密度概念：例子密度概念：例子8密度概念：例子密度概念：例子MinPts=3q是从p密度可达；p不是从q密度可达（q非核心）S和r从o密度可达；o从r密度可达；r,s密度相连9DBSCAN(Density Based Spatial Clustering of Applications with Noise)DBSCAN：一种基于高密度连通区域高密度连通区域的基于密度的聚类方法，该算法将具有足够高密度的区域划分为类，并在具有噪声的空间数据库中发现任意形状的类。它将类定义为密度相连的点的最大集密度相连的点的最大集合合。10DBSCAN通过检查数据集中每个对象的-邻域来寻找聚类。如果一个点p的-邻域包含多于MinPts个对象，则创建一个p作为核心对象的新类C。然后，DBSCAN从C中寻找未被处理对象q的-邻域，如果q的-邻域包含多MinPts个对象，则还未包含在C中的q的邻点被加入到类中，并且这些点的-邻域将在下一步中进行检测。这个过程反复执行，当没有新的点可以被添加到任何类时，该过程结束。具体如下：DBSCAN(Density Based Spatial Clustering of Applications with Noise)11输入：数据集D，参数MinPts,输出：类集合首先将数据集D中的所有对象标记unvisited；do 从D中随机选取一个unvisited对象p，并将p标记为visited；if p的 邻域 包含的对象数至少为MinPts个 创建新类C，并把p添加到c中；令N为 p的 邻域 中对象的集合；for N 中每个点pi if pi 是unvisited 标记pi 为visited；if pi 的 邻域 至少有MinPts个 对象，把这些对象添加到N；if pi 还不是任何类的对象。将 pi 添加到 类C中；end for 输出C Else 标记p 为噪声 Untill 没有标记为unvisited 的对象DBSCAN(Density Based Spatial Clustering of Applications with Noise)12下面给出一个样本事务数据库（见下表），对它实施DBSCAN算法。根据所给的数据通过对其进行DBSCAN算法，以下为算法的步骤（设n=12，用户输入=1，MinPts=4）序号属性 1属性 2121251312422532642752862913102311531224样本事务数据库样本事务数据库DBSCAN(Density Based Spatial Clustering of Applications with Noise)13Step1:在数据库中选择一点1，由于在以它为圆心的，以1为半径的圆内包含2个点（小于4），因此它不是核心点，选择下一个点。Step2:在数据库中选择一点2，由于在以它为圆心的，以1为半径的圆内包含2个点，因此它不是核心点，选择下一个点。Step3:在数据库中选择一点3，由于在以它为圆心的，以1为半径的圆内包含3个点，因此它不是核心点，选择下一个点。DBSCAN(Density Based Spatial Clustering of Applications with Noise)14Step4:在数据库中选择一点4，由于在以它为圆心的，以1为半径的圆内包含5个点，因此它是核心点。寻找从它出发可达的点（直接可达4个，间接可达3个），聚出的新类1，3，4，5，9，10，12，选择下一个点。DBSCAN(Density Based Spatial Clustering of Applications with Noise)序号属性 1属性 212125131242253264275286291310231153122415Step5:在数据库中选择一点5，已经在类1中，选择下一个点。Step6:在数据库中选择一点6，由于在以它为圆心的，以1为半径的圆内包含3个点，因此它不是核心点，选择下一个点。序号属性 1属性 2121251312422532642752862913102311531224DBSCAN(Density Based Spatial Clustering of Applications with Noise)16Step7:在数据库中选择一点7，由于在以它为圆心的，以1为半径的圆内包含5个点，因此它是核心点，寻找从它出发可达的点，聚出的新类2，6，7，8，11，选择下一个点。DBSCAN(Density Based Spatial Clustering of Applications with Noise)序号属性 1属性 212125131242253264275286291310231153122417Step8:在数据库中选择一点8，已经在类2中，选择下一个点。Step9:在数据库中选择一点9，已经在类1中，选择下一个点。Step10:在数据库中选择一点10，已经在类1中，选择下一个点。Step11:在数据库中选择一点11，已经在类2中，选择下一个点。Step12:选择12点，已经在类1中，由于这已经是最后一点所有点都以处理，程序终止。DBSCAN(Density Based Spatial Clustering of Applications with Noise)18步骤选择的点在中点的个数通过计算可达点而找到的新类112无222无333无445类C1：1，3，4，5，9，10，12553已在一个类C1中663无775类C2：2，6，7，8，11882已在一个类C2中993已在一个类C1中10104已在一个类C1中，11112已在一个类C2中 12122已在一个类C1中算法执行过程：DBSCAN(Density Based Spatial Clustering of Applications with Noise)19Original PointsClusters特点：特点：抗噪声能处理任意形状聚类DBSCAN(Density Based Spatial Clustering of Applications with Noise)20Pros:能克服基于距离的算法只能发现能克服基于距离的算法只能发现“类圆形类圆形”的聚类的缺点，可发现任意的聚类的缺点，可发现任意形状的聚类，有效地处理数据集中的噪声数据，数据输入顺序不敏感形状的聚类，有效地处理数据集中的噪声数据，数据输入顺序不敏感Cons:输入参数敏感确定参数输入参数敏感确定参数，MinPts困难，若选取不当，将造成聚类质量困难，若选取不当，将造成聚类质量下降下降由于在由于在DBSCAN算法中，变量算法中，变量，MinPts是全局惟一的，是全局惟一的，当空间聚类的密当空间聚类的密度不均匀、聚类间距离相差很大时，聚类质量较差。度不均匀、聚类间距离相差很大时，聚类质量较差。计算密度单元的计算复杂度大，需要建立空间索引来降低计算量，且对计算密度单元的计算复杂度大，需要建立空间索引来降低计算量，且对数据维数的伸缩性较差。这类方法需要扫描整个数据库，每个数据对象数据维数的伸缩性较差。这类方法需要扫描整个数据库，每个数据对象都可能引起一次查询，因此当数据量大时会造成频繁的都可能引起一次查询，因此当数据量大时会造成频繁的I/O操作。操作。DBSCAN(Density Based Spatial Clustering of Applications with Noise)21 下图中所描述的数据集不能通过一个全局密度参数同时区分出类A、B、C、C1、C2和C3，只能得到A、B、C或C1、C2和C3，对于C1、C2和C3而言A、B、C都是噪声。DBSCAN：can not handle varying densities22DBSCAN：sensitive to parameters23DBSCAN：Determining the Parameters and MinPts24？OPTICS(Ordering Points To Identify the Clustering Structure)为了同时构建不同的聚类,应当以特定的顺序来处理对象.优先选择最小的 值值密度可达的对象,以便高密度的聚类能被首先完成；每个对象需要存储两个值：对象p的核心距离核心距离(core-distance)是使得p成为核心对象的最小。如果p不是核心对象，p的核心距离没有定义。对象q关于另一个对象p的可达距离可达距离(reachability-distance)是p的核心距离和p与q的欧几里得距离之间的较大值.如果p不是一个核心对象,p和q之间的可达距离没有定义 OPTICSOPTICS算法通过对象排序识别聚类结构。算法通过对象排序识别聚类结构。25OPTICS(Ordering Points To Identify the Clustering Structure)Eg:设=6(mm),MinPts=5.p的核心距离是p与四个最近的数据对象之间的距离 q1关于p的可达距离是p的核心距离(即=3mm),因为它比从p到q1的欧几里得距离要大.q2关于p的可达距离是从p到q2的欧几里得距离,它大于p的 核心距离 P的核心距离的核心距离可达距离可达距离(p,q1)=3mm可达距离可达距离(p,q2)=d(p,q2)26OPTICS(Ordering Points To Identify the Clustering Structure)输输入入：样本集D,邻域半径E,给定点在E领域内成为核心对象的最小领域点数MinPts输出：输出：具有可达距离信息的样本点输出排序方法：方法：Step1:Step1:创建两个队列，有序队列和结果队列。（有序队列用来存储核心对象及其该核心对象的直接可达对象，并按可达距离升序排列；结果队列用来存储样本点的输出次序）；Step2:Step2:如果所有样本集D中所有点都处理完毕，则算法结束。否则，选择一个未处理（即不在结果队列中）且为核心对象的样本点，找到其所有直接密度可达样本点，如果该样本点不存在于结果队列中，则将其放入有序队列中，并按可达距离排序；Step3:Step3:如果有序队列为空，则跳至上一步，否则，从有序队列中取出第一个样本点（即可达距离最小的样本点）进行拓展，并将取出的样本点保存至结果队列中，如果它不存在结果队列当中的话:27Step3.1判断该拓展点是否是核心对象，如果不是，回到步骤3，否则找到该拓展点所有的直接密度可达点；Step3.2判断该直接密度可达样本点是否已经存在结果队列，是则不处理，否则下一步；Step3.3如果有序队列中已经存在该直接密度可达点，如果此时新的可达距离小于旧的可达距离，则用新可达距离取代旧可达距离，有序队列重新排序；重新排序；Step3.4如果有序队列中不存在该直接密度可达样本点，则插入该点，并对有序队列Step4:算法结束，输出结果队列中的有序样本点。OPTICS(Ordering Points To Identify the Clustering Structure)28OPTICS(Ordering Points To Identify the Clustering Structure)Example:有如下表所示的数据集。当设置=2，MinPts=4时，采用OPTICS算法进行聚类的过程如下：点名称点名称属性属性1属性属性2点名称点名称属性属性1属性属性2a23j76b24k95c14l1002d13m820e22n819f32o718g87p717h86q821i7729OPTICS(Ordering Points To Identify the Clustering Structure)Example:数据分布散点图数据分布散点图序序号号点名点名称称可达可达距离距离序序号号点名点名称称可达可达距离距离1a1.09k1.412e1.010i1.413b1.011h1.414d1.012n2.05c1.4113q2.06f1.4114o2.07g1.4115m2.08j1.41求各个点的可达距离，如下表所示，表中序号指出输出次序，对于未输出的点，表示该点的可达距离没有定义。k30OPTICS(Ordering Points To Identify the Clustering Structure)Example:如图，按照算法，分三个阶段输出了三波值,a,e,b,d,c,f,g,j,k,I,h,n,q,o,m这和DBSCAN的聚类结果是一样的。不仅如此，我们通过分析有序图还能直接得到当参数E=1.5,minPts=4时DBSCAN的类类结果，只要在坐标图中找到Y值小于1.5的样本点即可，只有两类a,e,b,d,c,f,g,j,k,I,h,其他点被认为是孤立点，和DBSCAN聚类算法取E=1.5,minPts=4时的结果一致。所以说，OPTICS聚类算法所得的类排序信息等价于一个广泛的参数设置所获聚类算法所得的类排序信息等价于一个广泛的参数设置所获得的基于密度的聚类结果。得的基于密度的聚类结果。31OPTICS(Ordering Points To Identify the Clustering Structure)对对于于真真实实的的，高高维维的的数数据据集集合合而而言言，绝绝大大多多数数算算法法对对参参数数值值是是非非常常敏敏感感的的，参参数数的的设设置置通通常常是是依依靠靠经经验验，难难以以确确定。而定。而OPTICS算法可以帮助找出合适的参数。算法可以帮助找出合适的参数。OPTICS算法通过对象排序识别聚类结构。算法通过对象排序识别聚类结构。OPTICS没没有有显显式式地地产产生生一一个个数数据据类类类类，它它为为自自动动和和交交互互的的聚聚类类分分析析计计算算一一个个类类排排序序。这这个个次次序序代代表表了了数数据据的的基基于密度的聚类结构。于密度的聚类结构。特点：特点：32DBSCAN VS OPTICSDBSCANOPTICSDensityBoolean value(high/low)Numerical value(core distance)Density-connectedBoolean value(yes/no)Numerical value(reachability distance)Searching strategyrandomgreedyWhen OPTICS Works WellCluster-order of the objectsWhen OPTICS Does NOT Work WellCluster-order of the objectsDefinition 1:Influence FunctionThe influence of a data point y at a point x in the data space is modeled by a function e.g.:DENCLUE(DENsity-based CLUstEring)Definition 2:Density FunctionThe density at a point x in the data space is defined as the sum of influences of all data points xe.g.:DENCLUE(DENsity-based CLUstEring)ExampleDENCLUE(DENsity-based CLUstEring)Definition 3:GradientThe gradient of a density function is defined ase.g.:DENCLUE(DENsity-based CLUstEring)Definition 4:Density AttractorA point x*Fd is called a density attractor for a given influence function,if f(x*)is a local maximum of the density-function Example of Density-AttractorDENCLUE(DENsity-based CLUstEring)Definition 5:Density attracted pointA point xk Fd is density attracted to a density attractor x*,if k N:d(xk,x*)withxi is a point in the path between xk and its attractor x*density-attracted points are determined by a gradient-based hill-climbing methodDENCLUE(DENsity-based CLUstEring)Definition 6:Center-Defined ClusterA center-defined cluster with density-attractor x*()is the subset of the database which is density-attracted by x*.DENCLUE(DENsity-based CLUstEring)Definition 7:Arbitrary-shaped clusterA arbitrary-shaped cluster for the set of density-attractors X is a subset C D,where1)xC,x*X:x is density attracted to x*and2)x1*,x2*X:a path P Fd fromx1*to x2*with pP:DENCLUE(DENsity-based CLUstEring)Noise-InvarianceAssumption:Noise is uniformly distributed in the data spaceLemma:The density-attractors do not change when the noise level increases.Idea of the Proof:-partition density function into signal and noise-density function of noise approximates a constant.DENCLUE(DENsity-based CLUstEring)Example of noise invarianceDENCLUE(DENsity-based CLUstEring)Parameter-:It describes the influence of a data point in the data space.It determines the number of clusters.DENCLUE(DENsity-based CLUstEring)Parameter-:Choose such that number of density attractors is constant for the longest interval of.DENCLUE(DENsity-based CLUstEring)Parameter-It describes whether a density-attractor is significant,helping reduce the number of density-attractors such that improving the performance.DENCLUE(DENsity-based CLUstEring)49Clusters are defined according to the point density function which is the sum of influence functions of the data points.It has good clustering in data sets with large amounts of noise.It can deal with high-dimensional data sets.It is significantly faster than existing algorithmsDENCLUE(DENsity-based CLUstEring)Properties50写在最后写在最后成功的基础在于好的学习习惯成功的基础在于好的学习习惯The foundation of success lies in good habits谢谢聆听 学习就是为了达到一定目的而努力去干,是为一个目标去战胜各种困难的过程,这个过程会充满压力、痛苦和挫折Learning Is To Achieve A Certain Goal And Work Hard,Is A Process To Overcome Various Difficulties For A Goal