基于密度方法的聚类

1、聚 类 分 析,宋宜飞,主要内容,回顾 密度聚类方法 DBSCAN算法 OPTICS 算法 网格聚类方法 CLIQUE算法,回顾,聚类 聚类(clustering)也称为聚类分析,指将样本分到不同的组中使得同一组中的样本差异尽可能的小，而不同组中的样本差异尽可能的大。 聚类得到的不同的组称为簇(cluster)。 一个好的聚类方法将产生以下的聚类 最大化类中的相似性 最小化类间的相似性,回顾,聚类的分类： 划分聚类方法 层次聚类方法 密度聚类方法 网格聚类方法 模型聚类方法,在基于划分的聚类中，任务就是将数据划分成K个不相交的点集，使每个子集中的点尽可能同质。 基于划分的方法 ，其代表算法有

2、k-means算法、 K-medoids等,划分聚类方法,k-means 算法,k-means 算法基本步骤 从 n个数据对象任意选择 k 个对象作为初始聚类中心； 根据每个聚类对象的均值(中心对象)，计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分； 重新计算每个(有变化)聚类的均值(中心对象)； 计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止；如果条件不满足则回到步骤2。,k-means优缺点,主要优点： 是解决聚类问题的一种经典算法，简单、快速。 对处理大数据集，该算法是相对可伸缩和高效率的。 当结果簇是密集的，它的效果较好。 主要缺点 在簇的平均值被定

3、义的情况下才能使用。 必须事先给出k（要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。 不适合于发现非凸面形状的簇或者大小差别很大的簇。而且，它对于“躁声”和孤立点数据是敏感的。,层次聚类方法,层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为止。具体又可分为： 凝聚的层次聚类：一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。 分裂的层次聚类：采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。 层次凝聚的代表是AGNES算法。层次分裂的代表是DIANA

4、算法。,层次聚类优缺点,层次聚类方法是不可逆的，也就是说，当通过凝聚式的方法将两组合并后，无法通过分裂式的办法再将其分离到之前的状态，反之亦然。 另外，层次聚类过程中调查者必须决定聚类在什么时候停止，以得到某个数量的分类。 在不必要的情况下应该小心使用层次聚类方法。,划分聚类方法 层次聚类方法 密度聚类方法 ：基于密度的聚类方法以数据集在空间分布上的稠密程度为依据进行聚类，无需预先设定簇的数量，因此特别适合对于未知内容的数据集进行聚类。 网格聚类方法 模型聚类方法,密度聚类方法,基于密度方法的聚类,密度聚类方法的指导思想是，只要一个区域中的点的密度大于某个域值，就把它加到与之相近的聚类中去。对

5、于簇中每个对象，在给定的半径的邻域中至少要包含最小数数目（MinPts）个对象。 这类算法能克服基于距离的算法只能发现“类圆形”的聚类的缺点，可发现任意形状的聚类，且对噪声数据不敏感。 代表算法有：DBSCAN、OPTICS、DENCLUE算法等。,基于密度方法的聚类- DBSCAN,DBSCAN（Density-Based Spatial Clustering of Applications with Noise）一个比较有代表性的基于密度的聚类算法。与层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在有“噪声”的空间数据库中发现任意形状的聚类。

6、,传统基于中心的密度定义为： 数据集中特定点的密度通过该点半径之内的点计数(包括本身)来估计。 显然，密度依赖于半径。,传统的密度定义：基于中心的方法,基于密度方法的聚类- DBSCAN 所用到的基本术语,定义 对象的-邻域：给定对象在半径内的区域。 定义 核心对象：如果一个对象的-邻域至少包含最小数目MinPts个 对象，则称该对象为核心对象。 例 下图中，=1cm，MinPts=5，q是一个核心对象。 定义 直接密度可达：给定一个对象集合D，如果p是在q的-邻域内，而 q是一个核心对象，我们说对象p从对象q出发是直接密度可达的。 例 在下图中，=1cm，MinPts=5 ，q是一个核心对象

7、，对象 p1从对象q出发是直接密度可达的。,基于密度方法的聚类- DBSCAN 所用到的基本术语,密度可达,定义 密度可达的：如果存在一个对象链p1，p2，pn，p1=q， pn=p，对piD，（1=i=n），pi+1是从pi关于和MitPts直接密度 可达的，则对象p是从对象q关于和MinPts密度可达的。 例 在下图中，=1cm，MinPts=5，q是一个核心对象，p1是 从q关于和MitPts直接密度可达，p是从p1关于和MitPts直接密度 可达，则对象p从对象q关于和MinPts密度可达的,基于密度方法的聚类- DBSCAN 所用到的基本术语,图 密度相连,图 噪声,定义 噪声: 一

8、个基于密度的簇是基于密度可达性的最大的密度相 连对象的集合。不包含在任何簇中的对象被认为是“噪声”。 边界点：边界点不是核心点，但落在某个核心点的邻域内。 噪声就是那些既不是边界点也不是核心点的对象,定义 密度相连的： 如果对象集合D中存在一个对象o，使得对象p 和q是从o关于和MinPts密度可达的，那么对象p和q是关于 和MinPts密度相连的。,DBSCAN算法概念示例,如图所示， 用一个相应的半径表示，设MinPts=3，请分析Q,M,P,S,O,R这5个样本点之间的关系。,“直接密度可达”和“密度可达”概念示意描述,解答：根据以上概念知道：由于有标记的各点M、P、O和R的 近邻均包含

9、3个以上的点，因此它们都是核对象；M是从P“直接密度可达”；而Q则是从M“直接密度可达”；基于上述结果，Q是从P“密度可达”；但P从Q无法“密度可达”(非对称)。类似地，S和R从O是“密度可达”的；O、R和S均是“密度相连”的。,基于密度方法的聚类- DBSCAN,DBSCAN 算法根据以上的定义在数据库中发现簇和噪声。簇可等价于集合D中，这个簇核心对象密度可达的所有对象的集合。 DBSCAN通过检查数据集中每个对象的-邻域来寻找聚类。如果一个点p的-邻域包含多于MinPts个对象，则创建一个p作为核心对象的新簇C。然后，DBSCAN从C中寻找未被处理对象q的-邻域，如果q的-邻域包含多Min

10、Pts个对象，则还未包含在C中的q的邻点被加入到簇中，并且这些点的-邻域将在下一步中进行检测。这个过程反复执行，当没有新的点可以被添加到任何簇时，该过程结束。具体如下：,基于密度方法的聚类- DBSCAN,DBSCAN算法描述： 输入：包含n个对象的数据库，半径，最少数目MinPts。 输出：所有生成的簇，达到密度要求。 1. REPEAT 2. 从数据库中抽取一个未处理过的点； 3. IF 抽出的点是核心点 THEN找出所有从该点密度可达的对象，形成一个簇 4. ELSE 抽出的点是边缘点(非核心对象)，跳出本次循环，寻找下一点； 5. UNTIL 所有点都被处理；,DBSCAN算法步骤,输

11、入：数据集D，参数MinPts, 输出：簇集合 (1) 首先将数据集D中的所有对象标记unvisited ； (2) do (3) 从D中随机选取一个unvisited对象p，并将p标记为visited ； if p的 邻域 包含的对象数至少为MinPts个 创建新簇C ，并把p添加到c中； 令N为 p的 邻域 中对象的集合； (7) for N 中每个点pi if pi 是unvisited 标记pi 为visited； if pi 的 邻域 至少有MinPts个 对象，把这些对象添加到N ； if pi 还不是任何簇的对象。将 pi 添加到 簇C中 ； (12) end for (13)

12、输出C (14) Else 标记p 为噪声 (15) Untill 没有标记为unvisited 的对象,基于密度方法的聚类- DBSCAN,下面给出一个样本事务数据库（见下表），对它实施DBSCAN算法。 根据所给的数据通过对其进行DBSCAN算法，以下为算法的步骤（设n=12，用户输入=1，MinPts=4）,样本事务数据库,DBSCAN聚类过程,第1步，在数据库中选择一点1，由于在以它为圆心的，以1为半径的圆内包含2个点（小于4），因此它不是核心点，选择下一个点。 第2步，在数据库中选择一点2，由于在以它为圆心的，以1为半径的圆内包含2个点，因此它不是核心点，选择下一个点。 第3步，在数

13、据库中选择一点3，由于在以它为圆心的，以1为半径的圆内包含3个点，因此它不是核心点，选择下一个点。,DBSCAN聚类过程,第4步，在数据库中选择一点4，由于在以它为圆心的，以1为半径的圆内包含5个点，因此它是核心点，寻找从它出发可达的点（直接可达4个，间接可达3个），聚出的新类1，3，4，5，9，10，12，选择下一个点。,DBSCAN聚类过程,第5步，在数据库中选择一点5，已经在簇1中，选择下一个点。 第6步，在数据库中选择一点6，由于在以它为圆心的，以1为半径的圆内包含3个点，因此它不是核心点，选择下一个点。,DBSCAN聚类过程,第7步，在数据库中选择一点7，由于在以它为圆心的，以1为半

14、径的圆内包含5个点，因此它是核心点，寻找从它出发可达的点，聚出的新类2，6，7，8，11，选择下一个点。,DBSCAN聚类过程,第8步，在数据库中选择一点8，已经在簇2中，选择下一个点。 第9步，在数据库中选择一点9，已经在簇1中，选择下一个点。 第10步，在数据库中选择一点10，已经在簇1中，选择下一个点。 第11步，在数据库中选择一点11，已经在簇2中，选择下一个点。 第12步，选择12点，已经在簇1中，由于这已经是最后一点所有点都以处理，程序终止。,基于密度方法的聚类- DBSCAN,算法执行过程：,DBSCAN的时间复杂性,时间复杂度 DBSCAN算法要对每个数据对象进行邻域检查时间性

15、能较低。 DBSCAN的基本时间复杂度是 O(N*找出Eps领域中的点所需要的时间), N是点的个数。最坏情况下时间复杂度是O(N2) 在低维空间数据中,有一些数据结构如KD树，使得可以有效的检索特定点给定距离内的所有点，时间复杂度可以降低到O(NlogN),DBSCAM的空间复杂性,空间复杂度 在聚类过程中，DBSCAN一旦找到一个核心对象，即以该核心对象为中心向外扩展此过程中核心对象将不断增多，未处理的对象被保留在内存中若数据库中存在庞大的聚类，将需要很大的存来存储核心对象信息，其需求难以预料 当数据量增大时，要求较大的内存支持 I/0 消耗也很大; 低维或高维数据中，其空间都是O(N),

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

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

18、C3，只能得到A 、B 、C或C1、C2和C3，对于C1、C2和C3而言A 、B 、C都是噪声。 对于固定的MinPts 值，和两个 1 2，关于1的MinPts簇C一定是关于2和MinPts簇C的子集，这就意味着。如果两个对象在同一个基于密度的簇中，则它们也是在同一个具有较低密度要求的簇中。,OPTICS 算法,为了克服在聚类分析中使用一组全局参数的缺点，提出了 OPTICS 聚类分析方法。 P 为对象，数据集D，为距离值，N(q)为邻域，MinPts 。 两个定义： P 的核心距离：使得P成为核心对象的最小， 是使p 称为核心对象的最小半径阈值。 若|（ N(q) MinPts，即P不是核

19、心对象，核心距离则无定义。 q关于对象P的可达距离：是使 q从p密度可达的最小半径。p的核心距离和p,q的欧几里得距离之间的较大值，p必须是核心对象且q在p的邻域内。 若|N(p)| MinPts，即P不是核心对象，则无定义 否则，定义为Max（核心距离，|（p,q）|）,OPTICS 算法,例 核心距离与可达距离,假设 =6mm， MinPts =5 。P的核心距离是p于第四个最近的数据对象之间的距离，q1到p的可达距离是p的核心距离（ =3mm），因为它比q1到p的欧氏距离大。q2关于p的科大距离是p到q2的欧氏距离，它大于p的核心距离。,OPTICS 算法,OPTICS 算法并不显式的产

20、生数据及聚类，而是输出簇排序（cluster ordering），这个排序是所有分析对象的线性表，并且代表数据基于密度的聚类结构。 较稠密簇中的对象在簇排序中相互靠近。这个排序等价于从较广泛的参数设置中得到基于密度的聚类。这样optics不需要用户提供特定密度阈值。 簇排列可以用来提取基本聚类信息，导出内在的聚类结构，也可以提供聚类的可视化。,OPTICS 算法,为了构造不同的类，对象需要按特定的次序处理，这个次序选择这样的对象，及关于最小的值，它是密度可达的，以便较高密度（较低 值）的簇先完成。 optics 算法计算给定数据库中所有对象的排序，并且存储每个对象核心距离和相应的可达距离。 o

21、ptics 维护一个称作order seeds 的表来来产生输出排列，orderseeds 中的对象按到各自的最近核心对象的可达距离排序，及按每个对象的最小可达距离排序。,OPTICS 算法,寻找簇,Cluster-order of the objects,数据集的簇排序可以用图形描述，这有助于可视化和理解数据集中聚类结构。例如下图是一个简单的二维数据集的可达性图。,OPTICS算法并不直接寻找各个簇 ,而是将基于密度查找簇所需要的信息记录下来,这些信息反映了数据空间基于密度的簇结构。同时从这些密度信息可以直接发现各个簇。OPTICS采取了两个方法来达到目标 1)定义了对象的核心距离和可达距离

22、,以反映对象附近的密度大小;2)在迭代查找可达对象时,对种子对象依可达距离进行排序,从而在簇扩展时优先扩展密度值较大区域的点 。这样,OPTICS算法实现了数据库所有对象的排序,这一对象序列就可以反映出数据空间基于密度的簇结构信息。基于这些信息可以容易地确定合适的值,并随之发现各个簇。另外, OPTICS还提供了自动的簇发现方法。OPTICS算法较好地解决了DBSCAN算法的对输入参数敏感的问题,但是由于采用了复杂的处理方法以及额外的磁盘IPO操作,使得OPTICS实际运行的速度远远低于DBSCAN 。,不同密度、形状、大小的簇,参数的影响,减小，则可达距离为无穷大的点增多； MinPts减小

23、，核心对象增多，图象更尖锐,基于网格的方法（Grid-Based Methods）,聚类高维数据是聚类分析中一个非常重要的任务，而一般聚类方法无法处理这些数据。用户感兴趣的通常是某个高维数据空间的若干个子空间，对该空间内数据点的聚类要比原始空间更好一些。高维数据中，通常只有少数几维与某些簇相关，其他不相关的维数据可能会产生大量的噪声而屏蔽真实的簇。 为聚类高维数据集便提出了基于网格的方法的聚类。,基于网格的方法（Grid-Based Methods） 将数据空间划分成为有限个单元（cell）的网格结构，所有的处理都是以单个单元为对象的。 这种方法的主要优点是它的处理速度很快，处理时间独立于数据

24、对象的数目，只与每一维所划分的单元数目有关 代表算法有：CLIQUE算法。,CLQUE是一个综合了基于密度和基于网格方法的聚类算法，对于大型数据库中的高维数据的聚类比较有效,在高维数据的子空间中识别稠密的聚类，所产生的理解结果与所给的输入数据无关。,CLIQUE：高维度数据的自动子空间聚类算法,CLIQUE：聚类高维空间,CLIQUE的中心思想如下： 给定一个多维数据点的大集合，数据点在数据空间中通常不是均衡分布的。CLIQUE区分空间中稀疏的和“拥挤的”区域，以发现数据集合全局分布模式。 将数据空间中的每个维划分成等长且数量相等的间隔段，即单元。如果一个单元中的包含数据点超过了某个输入模型参

25、数，则该单元是密集的。在CLIQUE中，一个聚类被定义为相连的密集单元的最大集合。,问题描述,要能自动地识别一个高维数据的子空间 限制在只对原始空间的子空间的搜索而不是使用一个新的维度 为了识别数据点的密度，将数据空间划分并找出在每个单元中数据点的数量。 聚类是子空间中相连的高密度单元的并集，即将聚类映射到轴对称的超矩形中。,聚类在空间中的描述,设AA1,A2,Ad是一个有界的、全部有序的域的集合。而SA1A2Ad是一个d维的数字空间，A1，A2，Ad定义为S的维。 输入是由d维点集Vv1,v2,vm组成的，其中Vi=,Vi的第j个元素来自域Aj。 将数据空间S划分成非重叠矩形单元。单元的划分

26、方法是在每一个维上将维分割成个等长的间隔段，是输入参数。 每一个单元u是由每一个属性一个间隔段组成的交集。形式为u1,u2,ud，其中ui=li,hi）是在Ai的划分中的右边界开放的间隔段。,聚类在空间中的描述,一个点V属于单元u=u1,u2,.ud,当对所有的ui，有livihi。 一个单元的选择性（selectivity）：单元内数据点的数量与单元的总数据点数量之比。 称单元u是稠密的：若单元的选择性大于密度阈值。,聚类在空间中的描述,两个k维单元u1，u2是连接的，即他们之间有一个公共面。 若存在k-1维，假设是维At1，At2，,Atk-1，单元u1 rt1,rt2,rtk 及u2=r

27、t1， rt2，, rtk-1是相连的， 则有rtj= rtj，并且有htk ltk 或者htk ltk。 若RCR，则称一个区域R包含于一个聚类C中。若没有其他R的超集包含于聚类C中，则称区域R是最大的。 一个聚类的最小描述是具有最大区域的聚类的非冗余的覆盖。,例子（一）,在下图中，二维空间（age,salary）划分成1010格一个单元是间隔段的交集；例如单元u（30 age35）（1salary2）。 一个区域是单元的矩形的并集。A与B是两个区域：A（30 age50） （4 salary8）,B=（40 age60）（2 salary6）。 假设 阴影部分是稠密的单元，A B是一个聚类。 该聚类的最小描述为：（30 age50）（4 salary8） （40 age60）（2 salary6）。,例子（二）：,图二：原始数据空间的子空间中的聚类,在图二中，假设20，没有2-维单元是稠密的，在原始数据空间中就没有聚类。 但将数据点投影到维salary上，就有三个1维密度单元，其中两个是相连的，因此，在1维salary子空间上就有两个聚类：C5salary7及D2 salary3. 由于在age子空间中没有密度单元，故在该子空间中就没有聚类。,CLIQUE算法,由以下几部分组成： 1）含有聚