基于密方法的聚类演示

（优选）基于密度方法的聚类当前1页，总共64页。主要内容回顾密度聚类方法

DBSCAN算法OPTICS算法网格聚类方法

CLIQUE算法当前2页，总共64页。回顾聚类聚类(clustering)也称为聚类分析,指将样本分到不同的组中使得同一组中的样本差异尽可能的小，而不同组中的样本差异尽可能的大。聚类得到的不同的组称为簇(cluster)。一个好的聚类方法将产生以下的聚类最大化类中的相似性最小化类间的相似性当前3页，总共64页。回顾聚类的分类：

划分聚类方法层次聚类方法

密度聚类方法网格聚类方法

模型聚类方法当前4页，总共64页。在基于划分的聚类中，任务就是将数据划分成K个不相交的点集，使每个子集中的点尽可能同质。基于划分的方法，其代表算法有k-means算法、K-medoids等划分聚类方法当前5页，总共64页。k-means算法k-means算法基本步骤从n个数据对象任意选择k个对象作为初始聚类中心；根据每个聚类对象的均值(中心对象)，计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；重新计算每个(有变化)聚类的均值(中心对象)；计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止；如果条件不满足则回到步骤2。当前6页，总共64页。k-means优缺点主要优点：是解决聚类问题的一种经典算法，简单、快速。对处理大数据集，该算法是相对可伸缩和高效率的。当结果簇是密集的，它的效果较好。主要缺点在簇的平均值被定义的情况下才能使用。必须事先给出k（要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。不适合于发现非凸面形状的簇或者大小差别很大的簇。而且，它对于“躁声”和孤立点数据是敏感的。当前7页，总共64页。层次聚类方法层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为止。具体又可分为：

凝聚的层次聚类：一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。

分裂的层次聚类：采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。层次凝聚的代表是AGNES算法。层次分裂的代表是DIANA算法。当前8页，总共64页。层次聚类优缺点层次聚类方法是不可逆的，也就是说，当通过凝聚式的方法将两组合并后，无法通过分裂式的办法再将其分离到之前的状态，反之亦然。另外，层次聚类过程中调查者必须决定聚类在什么时候停止，以得到某个数量的分类。在不必要的情况下应该小心使用层次聚类方法。当前9页，总共64页。划分聚类方法层次聚类方法

密度聚类方法：基于密度的聚类方法以数据集在空间分布上的稠密程度为依据进行聚类，无需预先设定簇的数量，因此特别适合对于未知内容的数据集进行聚类。网格聚类方法

模型聚类方法密度聚类方法当前10页，总共64页。基于密度方法的聚类密度聚类方法的指导思想是，只要一个区域中的点的密度大于某个域值，就把它加到与之相近的聚类中去。对于簇中每个对象，在给定的半径ε的邻域中至少要包含最小数数目（MinPts）个对象。这类算法能克服基于距离的算法只能发现“类圆形”的聚类的缺点，可发现任意形状的聚类，且对噪声数据不敏感。代表算法有：DBSCAN、OPTICS、DENCLUE算法等。当前11页，总共64页。基于密度方法的聚类-DBSCANDBSCAN（Density-BasedSpatialClusteringofApplicationswithNoise）一个比较有代表性的基于密度的聚类算法。与层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在有“噪声”的空间数据库中发现任意形状的聚类。当前12页，总共64页。传统基于中心的密度定义为：数据集中特定点的密度通过该点ε半径之内的点计数(包括本身)来估计。显然，密度依赖于半径。传统的密度定义：基于中心的方法当前13页，总共64页。基于密度方法的聚类-DBSCAN所用到的基本术语定义对象的ε-邻域：给定对象在半径ε内的区域。定义核心对象：如果一个对象的ε-邻域至少包含最小数目MinPts个对象，则称该对象为核心对象。

例下图中，ε=1cm，MinPts=5，q是一个核心对象。定义直接密度可达：给定一个对象集合D，如果p是在q的ε-邻域内，而

q是一个核心对象，我们说对象p从对象q出发是直接密度可达的。

例在下图中，ε=1cm，MinPts=5，q是一个核心对象，对象

p1从对象q出发是直接密度可达的。当前14页，总共64页。基于密度方法的聚类-DBSCAN所用到的基本术语密度可达定义密度可达的：如果存在一个对象链p1，p2，…，pn，p1=q，

pn=p，对pi∈D，（1<=i<=n），pi+1是从pi关于ε和MitPts直接密度可达的，则对象p是从对象q关于ε和MinPts密度可达的。例在下图中，ε=1cm，MinPts=5，q是一个核心对象，p1是从q关于ε和MitPts直接密度可达，p是从p1关于ε和MitPts直接密度可达，则对象p从对象q关于ε和MinPts密度可达的当前15页，总共64页。基于密度方法的聚类-DBSCAN所用到的基本术语图密度相连图噪声定义噪声:一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合。不包含在任何簇中的对象被认为是“噪声”。边界点：边界点不是核心点，但落在某个核心点的邻域内。噪声就是那些既不是边界点也不是核心点的对象定义

密度相连的：如果对象集合D中存在一个对象o，使得对象p

和q是从o关于ε和MinPts密度可达的，那么对象p和q是关于

ε和MinPts密度相连的。当前16页，总共64页。DBSCAN算法概念示例如图所示，ε

用一个相应的半径表示，设MinPts=3，请分析Q,M,P,S,O,R这5个样本点之间的关系。“直接密度可达”和“密度可达”概念示意描述解答：根据以上概念知道：由于有标记的各点­M、P、O和R的ε

近邻均包含3个以上的点，因此它们都是核对象；M­是从P“直接密度可达”；而Q则是从­M“直接密度可达”；基于上述结果，Q是从P“密度可达”；但P从Q无法“密度可达”(非对称)。类似地，S和R从O是“密度可达”的；O、R和S均是“密度相连”的。当前17页，总共64页。基于密度方法的聚类-DBSCANDBSCAN算法根据以上的定义在数据库中发现簇和噪声。簇可等价于集合D中，这个簇核心对象密度可达的所有对象的集合。DBSCAN通过检查数据集中每个对象的ε-邻域来寻找聚类。如果一个点p的ε-邻域包含多于MinPts个对象，则创建一个p作为核心对象的新簇C。然后，DBSCAN从C中寻找未被处理对象q的ε-邻域，如果q的ε-邻域包含多MinPts个对象，则还未包含在C中的q的邻点被加入到簇中，并且这些点的ε-邻域将在下一步中进行检测。这个过程反复执行，当没有新的点可以被添加到任何簇时，该过程结束。具体如下：当前18页，总共64页。基于密度方法的聚类-DBSCANDBSCAN算法描述：输入：包含n个对象的数据库，半径ε，最少数目MinPts。输出：所有生成的簇，达到密度要求。1.REPEAT2.从数据库中抽取一个未处理过的点；3.IF抽出的点是核心点THEN找出所有从该点密度可达的对象，形成一个簇4.ELSE抽出的点是边缘点(非核心对象)，跳出本次循环，寻找下一点；5.UNTIL所有点都被处理；当前19页，总共64页。DBSCAN算法步骤

输入：数据集D，参数MinPts,ε输出：簇集合(1)首先将数据集D中的所有对象标记unvisited；(2)do(3)从D中随机选取一个unvisited对象p，并将p标记为visited；ifp的ε邻域包含的对象数至少为MinPts个创建新簇C，并把p添加到c中；令N为p的ε邻域中对象的集合；(7)forN中每个点piifpi是unvisited标记pi为visited；ifpi的ε邻域至少有MinPts个对象，把这些对象添加到N；ifpi还不是任何簇的对象。将pi添加到簇C中；(12)endfor(13)输出C(14)Else标记p为噪声(15)Untill没有标记为unvisited的对象当前20页，总共64页。基于密度方法的聚类-DBSCAN

下面给出一个样本事务数据库（见下表），对它实施DBSCAN算法。根据所给的数据通过对其进行DBSCAN算法，以下为算法的步骤（设n=12，用户输入ε=1，MinPts=4）

序号属性1属性2121251312422532642752862913102311531224样本事务数据库当前21页，总共64页。DBSCAN聚类过程第1步，在数据库中选择一点1，由于在以它为圆心的，以1为半径的圆内包含2个点（小于4），因此它不是核心点，选择下一个点。第2步，在数据库中选择一点2，由于在以它为圆心的，以1为半径的圆内包含2个点，因此它不是核心点，选择下一个点。第3步，在数据库中选择一点3，由于在以它为圆心的，以1为半径的圆内包含3个点，因此它不是核心点，选择下一个点。当前22页，总共64页。DBSCAN聚类过程第4步，在数据库中选择一点4，由于在以它为圆心的，以1为半径的圆内包含5个点，因此它是核心点，寻找从它出发可达的点（直接可达4个，间接可达3个），聚出的新类{1，3，4，5，9，10，12}，选择下一个点。当前23页，总共64页。DBSCAN聚类过程第5步，在数据库中选择一点5，已经在簇1中，选择下一个点。第6步，在数据库中选择一点6，由于在以它为圆心的，以1为半径的圆内包含3个点，因此它不是核心点，选择下一个点。当前24页，总共64页。DBSCAN聚类过程第7步，在数据库中选择一点7，由于在以它为圆心的，以1为半径的圆内包含5个点，因此它是核心点，寻找从它出发可达的点，聚出的新类{2，6，7，8，11}，选择下一个点。当前25页，总共64页。DBSCAN聚类过程第8步，在数据库中选择一点8，已经在簇2中，选择下一个点。第9步，在数据库中选择一点9，已经在簇1中，选择下一个点。第10步，在数据库中选择一点10，已经在簇1中，选择下一个点。第11步，在数据库中选择一点11，已经在簇2中，选择下一个点。第12步，选择12点，已经在簇1中，由于这已经是最后一点所有点都以处理，程序终止。当前26页，总共64页。基于密度方法的聚类-DBSCAN步骤选择的点在ε中点的个数通过计算可达点而找到的新簇112无222无333无445簇C1：{1，3，4，5，9，10，12}553已在一个簇C1中663无775簇C2：{2，6，7，8，11}882已在一个簇C2中993已在一个簇C1中10104已在一个簇C1中，11112已在一个簇C2中12122已在一个簇C1中算法执行过程：当前27页，总共64页。DBSCAN的时间复杂性时间复杂度DBSCAN算法要对每个数据对象进行邻域检查时间性能较低。DBSCAN的基本时间复杂度是O(N*找出Eps领域中的点所需要的时间),N是点的个数。最坏情况下时间复杂度是O(N2)在低维空间数据中,有一些数据结构如KD树，使得可以有效的检索特定点给定距离内的所有点，时间复杂度可以降低到O(NlogN)当前28页，总共64页。DBSCAM的空间复杂性空间复杂度

在聚类过程中，DBSCAN一旦找到一个核心对象，即以该核心对象为中心向外扩展．此过程中核心对象将不断增多，未处理的对象被保留在内存中．若数据库中存在庞大的聚类，将需要很大的存来存储核心对象信息，其需求难以预料．当数据量增大时，要求较大的内存支持I/0消耗也很大;

低维或高维数据中，其空间都是O(N)当前29页，总共64页。基于密度方法的聚类优点能克服基于距离的算法只能发现“类圆形”的聚类的缺点，可发现任意形状的聚类，有效地处理数据集中的噪声数据，数据输入顺序不敏感缺点输入参数敏感．确定参数ε，MinPts困难，若选取不当，将造成聚类质量下降．由于在DBSCAN算法中，变量ε，MinPts是全局惟一的，当空间聚类的密度不均匀、聚类间距离相差很大时，聚类质量较差。计算密度单元的计算复杂度大，需要建立空间索引来降低计算量，且对数据维数的伸缩性较差。这类方法需要扫描整个数据库，每个数据对象都可能引起一次查询，因此当数据量大时会造成频繁的I/O操作。。当前30页，总共64页。OPTICS算法

由于在DBSCAN算法中，变量ε，MinPts是全局惟一的，当空间聚类的密度不均匀、聚类间距离相差很大时，聚类质量较差。许多现实的数据集内在的聚类结构不能够通过全局的密度参数来描述，数据空间中不同区域的聚类需要不同的局部密度。当前31页，总共64页。OPTICS算法尽管dbscan能够根据给定的输入参数ε，和MinPts聚类对象，但是它把选择能产生可接受的聚类结果的参数值的责任留给了用户。这是许多其他算法都存在的问题。但是对于高维数据而言设定准确的参数非常困难。参数设置有细微的不同都可能导致差别很大的聚类结果。全局参数不能很好地刻画其内在的聚类结构。当前32页，总共64页。OPTICS算法下图中所描述的数据集不能通过一个全局密度参数同时区分出簇A、B、C、C1、C2和C3，只能得到A、B、C或C1、C2和C3，对于C1、C2和C3而言A、B、C都是噪声。对于固定的MinPts值，和两个ε1＜

ε2，关于ε1的MinPts簇C一定是关于ε2和MinPts簇C’的子集，这就意味着。如果两个对象在同一个基于密度的簇中，则它们也是在同一个具有较低密度要求的簇中。当前33页，总共64页。OPTICS算法为了克服在聚类分析中使用一组全局参数的缺点，提出了OPTICS聚类分析方法。P为对象，数据集D，为距离值，N(q)为邻域，MinPts

。两个定义：

P的核心距离：使得P成为核心对象的最小‘，‘是使p称为核心对象的最小半径阈值。若|（N(q)MinPts，即P不是核心对象，核心距离则无定义。q关于对象P的可达距离：是使q从p密度可达的最小半径。p的核心距离和p,q的欧几里得距离之间的较大值，p必须是核心对象且q在p的邻域内。若|N(p)|MinPts，即P不是核心对象，则无定义否则，定义为Max（核心距离，|（p,q）|）当前34页，总共64页。OPTICS算法例核心距离与可达距离,假设

=6mm，MinPts=5。P的核心距离是p于第四个最近的数据对象之间的距离‘，q1到p的可达距离是p的核心距离（‘=3mm），因为它比q1到p的欧氏距离大。q2关于p的科大距离是p到q2的欧氏距离，它大于p的核心距离。当前35页，总共64页。OPTICS算法OPTICS算法并不显式的产生数据及聚类，而是输出簇排序（clusterordering），这个排序是所有分析对象的线性表，并且代表数据基于密度的聚类结构。较稠密簇中的对象在簇排序中相互靠近。这个排序等价于从较广泛的参数设置中得到基于密度的聚类。这样optics不需要用户提供特定密度阈值。簇排列可以用来提取基本聚类信息，导出内在的聚类结构，也可以提供聚类的可视化。当前36页，总共64页。OPTICS算法为了构造不同的类，对象需要按特定的次序处理，这个次序选择这样的对象，及关于最小的值，它是密度可达的，以便较高密度（较低值）的簇先完成。optics算法计算给定数据库中所有对象的排序，并且存储每个对象核心距离和相应的可达距离。optics维护一个称作orderseeds的表来来产生输出排列，orderseeds中的对象按到各自的最近核心对象的可达距离排序，及按每个对象的最小可达距离排序。当前37页，总共64页。OPTICS算法当前38页，总共64页。寻找簇Reachability-distanceundefined‘Cluster-orderoftheobjects当前39页，总共64页。数据集的簇排序可以用图形描述，这有助于可视化和理解数据集中聚类结构。例如下图是一个简单的二维数据集的可达性图。可达距离未定义’当前40页，总共64页。OPTICS算法并不直接寻找各个簇,而是将基于密度查找簇所需要的信息记录下来,这些信息反映了数据空间基于密度的簇结构。同时从这些密度信息可以直接发现各个簇。OPTICS采取了两个方法来达到目标1)定义了对象的核心距离和可达距离,以反映对象附近的密度大小;2)在迭代查找可达对象时,对种子对象依可达距离进行排序,从而在簇扩展时优先扩展密度值较大区域的点。这样,OPTICS算法实现了数据库所有对象的排序,这一对象序列就可以反映出数据空间基于密度的簇结构信息。基于这些信息可以容易地确定合适的ε值,并随之发现各个簇。另外,OPTICS还提供了自动的簇发现方法。OPTICS算法较好地解决了DBSCAN算法的对输入参数ε敏感的问题,但是由于采用了复杂的处理方法以及额外的磁盘IPO操作,使得OPTICS实际运行的速度远远低于DBSCAN。当前41页，总共64页。当前42页，总共64页。当前43页，总共64页。当前44页，总共64页。不同密度、形状、大小的簇当前45页，总共64页。参数的影响减小，则可达距离为无穷大的点增多；

MinPts减小，核心对象增多，图象更尖锐当前46页，总共64页。

基于网格的方法（Grid-BasedMethods）

聚类高维数据是聚类分析中一个非常重要的任务，而一般聚类方法无法处理这些数据。用户感兴趣的通常是某个高维数据空间的若干个子空间，对该空间内数据点的聚类要比原始空间更好一些。高维数据中，通常只有少数几维与某些簇相关，其他不相关的维数据可能会产生大量的噪声而屏蔽真实的簇。

为聚类高维数据集便提出了基于网格的方法的聚类。当前47页，总共64页。

基于网格的方法（Grid-BasedMethods）

将数据空间划分成为有限个单元（cell）的网格结构，所有的处理都是以单个单元为对象的。这种方法的主要优点是它的处理速度很快，处理时间独立于数据对象的数目，只与每一维所划分的单元数目有关代表算法有：CLIQUE算法。当前48页，总共64页。CLQUE是一个综合了基于密度和基于网格方法的聚类算法，对于大型数据库中的高维数据的聚类比较有效,在高维数据的子空间中识别稠密的聚类，所产生的理解结果与所给的输入数据无关。CLIQUE：高维度数据的自动子空间聚类算法当前49页，总共64页。CLIQUE：聚类高维空间CLIQUE的中心思想如下：给定一个多维数据点的大集合，数据点在数据空间中通常不是均衡分布的。CLIQUE区分空间中稀疏的和“拥挤的”区域，以发现数据集合全局分布模式。

将数据空间中的每个维划分成等长且数量相等的间隔段，即单元。如果一个单元中的包含数据点超过了某个输入模型参数，则该单元是密集的。在CLIQUE中，一个聚类被定义为相连的密集单元的最大集合。当前50页，总共64页。问题描述

要能自动地识别一个高维数据的子空间限制在只对原始空间的子空间的搜索而不是使用一个新的维度为了识别数据点的密度，将数据空间划分并找出在每个单元中数据点的数量。聚类是子空间中相连的高密度单元的并集，即将聚类映射到轴对称的超矩形中。当前51页，总共64页。聚类在空间中的描述设A＝{A1,A2,…,Ad}是一个有界的、全部有序的域的集合。而S＝A1×A2×…×Ad是一个d维的数字空间，A1，A2，…，Ad定义为S的维。输入是由d维点集V＝{v1,v2,…,vm}组成的，其中Vi=<Vi1,Vi2,…,Vid>,Vi的第j个元素来自域Aj。将数据空间S划分成非重叠矩形单元。单元的划分方法是在每一个维上将维分割成ξ个等长的间隔段，ξ是输入参数。每一个单元u是由每一个属性一个间隔段组成的交集。形式为{u1,u2,…,ud}，其中ui=[li,hi）是在Ai的划分中的右边界开放的间隔段。当前52页，总共64页。聚类在空间中的描述一个点V＝<v1,v2,…,vd>属于单元u={u1,u2,..ud},当对所有的ui，有li≤vi<hi。一个单元的选择性（selectivity）：单元内数据点的数量与单元的总数据点数量之比。称单元u是稠密的：若单元的选择性大于密度阈值τ。当前53页，总共64页。聚类在空间中的描述两个k维单元u1，u2是连接的，即他们之间有一个公共面。若存在k-1维，假设是维At1，At2，…,Atk-1，单元u1＝{rt1,rt2,…,rtk}及u2={rt1’，rt2’，…,rtk-1’}是相连的，则有rtj=rtj’，并且有htk＝ltk’

或者htk’＝ltk。若R∩C＝R，则称一个区域R包含于一个聚类C中。若没有其他R的超集包含于聚类C中，则称区域R是最大的。一个聚类的最小描述是具有最大区域的聚类的非冗余的覆盖。

当前54页，总共64页。例子（一）

在下图中，二维空间（age,salary）划分成10×10格一个单元是间隔段的交集；例如单元u＝（30≤age<35）∧（1≤salary<2）。一个区域是单元的矩形的并集。A与B是两个区域：A＝（30≤age<50）∧（4≤salary<8）,B=（40≤age<60）∧（2≤salary<6）。假设阴影部分是稠密的单元，A∪B是一个聚类。该聚类的最小描述为：（（30≤age<50）∧（4≤salary<8））∨（（40≤age<60）∧（2≤salary<6））。当前55页，总共64