数据挖掘最新精品课程完整(第14讲)---基于密度的聚类课件

1、基于密度的聚类方法,1,PPT学习交流,基于密度的聚类方法,划分和层次方法旨在发现球状簇。他们很难发现任意形状的簇。 改进思想，将簇看作数据空间中由低密度区域分隔开的高密度对象区域。这是基于密度的聚类方法的主要策略。 基于密度的聚类方法可以用来过滤噪声孤立点数据，发现任意形状的簇。 DBSCAN：基于高密度连通区域聚类 OPTICS：通过点排序识别聚类结构 DENCLUE:基于密度分布函数的聚类,2,PPT学习交流,DBSCAN,基于密度的簇是密度相连的点的集合 主要思想 寻找被低密度区域分离的高密度区域 只要临近区域的密度（单位大小上对象或数据点的数目）超过某个阈值，就继续聚类,3,PPT学

2、习交流,DBSCAN,两个参数： Eps: 邻域的最大半径 MinPts: 一个核心对象以 Eps为半径的邻域内的最小顶点数,4,PPT学习交流,DBSCAN,密度 = 制定半径 (Eps)内点的个数 如果一个对象的 Eps 邻域至少包含最小数目MinPts 个对象，则称该对象为核心对象（Core point） 如果一个对象是非核心对象, 但它的邻域中有核心对象，则称该对象为边界点（ Border point ） 除核心对象和边界点之外的点是噪声点（ Noise point ）,5,PPT学习交流,DBSCAN: 核心、边界和噪声点,6,PPT学习交流,DBSCAN,密度可达的（Density

3、-reachable） 对于对象p和核心对象q(关于E和MinPts),我们称p是从q(关于E和MinPts)直接密度可达，若对象p在对象q的E邻域内。 如果存在一个对象链 p1, , pn, p1 = q, pn = p ，pi+1 是从pi关于Eps和MinPts 直接密度可达的，则对象p是从对象q关于Eps和MinPts 密度可达的。 密度可达性是直接密度可达性的传递闭包，这种关系是非对称的。 只有核心对象之间是相互可达的。,7,PPT学习交流,DBSCAN,密度相连的（Density-connected） 如果对象集合D中存在一个对象o，使得对象p和q是从o关于Eps 和 MinPts

4、密度可达的，那么对象p和q是关于Eps 和 MinPts 密度相连的。 密度相连性是一个对称的关系。,8,PPT学习交流,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均是“密度相连”的。,9,PPT学习交流,基于密度方法的聚类- DB

5、SCAN,DBSCAN 算法根据以上的定义在数据库中发现簇和噪声。簇可等价于集合D中簇核心对象密度可达的所有对象的集合。 DBSCAN通过检查数据集中每个对象的-邻域来寻找聚类。如果一个点p的-邻域包含多于MinPts个对象，则创建一个p作为核心对象的新簇C。然后，DBSCAN从C中寻找未被处理对象q的-邻域，如果q的-邻域包含多MinPts个对象，则还未包含在C中的q的邻点被加入到簇中，并且这些点的-邻域将在下一步中进行检测。这个过程反复执行，当没有新的点可以被添加到任何簇时，该过程结束。具体如下：,10,PPT学习交流,DBSCAN算法步骤,输入：数据集D，参数MinPts, 输出：簇集合

6、 (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) 输出C (14) Else 标记p 为噪声 (

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

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

9、过程,第7步，在数据库中选择一点7，由于在以它为圆心的，以1为半径的圆内包含5个点，因此它是核心点，寻找从它出发可达的点，聚出的新类2，6，7，8，11，选择下一个点。,16,PPT学习交流,DBSCAN聚类过程,第8步，在数据库中选择一点8，已经在簇2中，选择下一个点。 第9步，在数据库中选择一点9，已经在簇1中，选择下一个点。 第10步，在数据库中选择一点10，已经在簇1中，选择下一个点。 第11步，在数据库中选择一点11，已经在簇2中，选择下一个点。 第12步，选择12点，已经在簇1中，由于这已经是最后一点所有点都以处理，程序终止。,17,PPT学习交流,基于密度方法的聚类- DBSCA

10、N,算法执行过程：,18,PPT学习交流,DBSCAN,Original Points,Clusters,特点： 抗噪声 能处理任意形状聚类,19,PPT学习交流,基于密度方法的聚类,优点 能克服基于距离的算法只能发现“类圆形”的聚类的缺点，可发现任意形状的聚类，有效地处理数据集中的噪声数据，数据输入顺序不敏感 缺点 输入参数敏感确定参数，MinPts困难，若选取不当，将造成聚类质量下降 由于在DBSCAN算法中，变量，MinPts是全局惟一的， 当空间聚类的密度不均匀、聚类间距离相差很大时，聚类质量较差。 计算密度单元的计算复杂度大，需要建立空间索引来降低计算量，且对数据维数的伸缩性较差。这

11、类方法需要扫描整个数据库，每个数据对象都可能引起一次查询，因此当数据量大时会造成频繁的I/O操作。,20,PPT学习交流,OPTICS 算法,尽管dbscan能够根据给定的输入参数，和MinPts聚类对象，但是它把选择能产生可接受的聚类结果的参数值的责任留给了用户。这是许多其他算法都存在的问题。但是对于高维数据而言设定准确的参数非常困难。参数设置有细微的不同都可能导致差别很大的聚类结果。全局参数不能很好地刻画其内在的聚类结构。,21,PPT学习交流,OPTICS 算法,下图中所描述的数据集不能通过一个全局密度参数同时区分出簇A 、B 、C、C1、C2和C3，只能得到A 、B 、C或C1、C2和

12、C3，对于C1、C2和C3而言A 、B 、C都是噪声。 对于固定的MinPts 值，和两个 1 2，关于1的MinPts簇C一定是关于2和MinPts簇C的子集，这就意味着。如果两个对象在同一个基于密度的簇中，则它们也是在同一个具有较低密度要求的簇中。,22,PPT学习交流,OPTICS：通过点排序识别聚类结构,对于真实的，高维的数据集合而言，参数的设置通常是依靠经验，难以确定。 绝大多数算法对参数值是非常敏感的：设置的细微不同可能导致差别很大的聚类结果。 OPTICS算法通过对象排序识别聚类结构。 OPTICS没有显式地产生一个数据集合簇，它为自动和交互的聚类分析计算一个簇排序。 这个次序代

13、表了数据的基于密度的聚类结构。较稠密中的对象在簇排序中相互靠近。,23,PPT学习交流,OPTICS,簇排序选择这样的对象：即关于最小的E值，它是密度可达的，以便较高密度（较低E值）的簇先完成。 对象p的核心距离：使p成为核心对象的最小。如果p不是核心对象，那么p的核心距离没有任何意义。 可达距离：对象q到对象p的可达距离是指p的核心距离和p与q之间欧几里得距离之间的较大值。如果p不是核心对象，p和q之间的可达距离没有意义。,24,PPT学习交流,OPTICS 算法,核心距离与可达距离,假设 =6mm， MinPts =5 。P的核心距离是p于第四个最近的数据对象之间的距离，q1到p的可达距离

14、是p的核心距离（ =3mm），因为它比q1到p的欧氏距离大。q2关于p的可达距离是p到q2的欧氏距离，它大于p的核心距离。,25,PPT学习交流,OPTICS 算法,OPTICS 算法并不显式的产生数据及聚类，而是输出簇排序（cluster ordering），这个排序是所有分析对象的线性表，并且代表数据基于密度的聚类结构。 较稠密簇中的对象在簇排序中相互靠近。这个排序等价于从较广泛的参数设置中得到基于密度的聚类。这样optics不需要用户提供特定密度阈值。 簇排列可以用来提取基本聚类信息，导出内在的聚类结构，也可以提供聚类的可视化。,26,PPT学习交流,OPTICS 算法,为了构造不同的类

15、，对象需要按特定的次序处理，这个次序选择这样的对象，及关于最小的值，它是密度可达的，以便较高密度（较低 值）的簇先完成。 optics 算法计算给定数据库中所有对象的排序，并且存储每个对象核心距离和相应的可达距离。 optics 维护一个称作order seeds 的表来来产生输出排列，orderseeds 中的对象按到各自的最近核心对象的可达距离排序，及按每个对象的最小可达距离排序。,27,PPT学习交流,OPTICS：通过点排序识别聚类结构,算法思路 首先检查数据对象集合D中任一个对象的E邻域。设定其可达距离为“未定义”，并确定其核心距离，然后将对象及其核心距离和可达距离写入文件。 如果P

16、是核心对象，则将对象P的E邻域内的对象N (P)插入到一个种子队列中，包含在种子队列中的对象p按到其直接密度可达的最近的核心对象q的可达距离排序。 种子队列中具有最小可达距离的对象被首先挑选出来，确定该对象的E一邻域和核心距离， 然后将其该对象及其核心距离和可达距离写入文件中，如果当前对象是核心对象，则更多的用于扩展的后选对象被插入到种子队列中。 这个处理一直重复到再没有一个新的对象被加入到当前的种子队列 中。,28,PPT学习交流,OPTICS：通过点排序识别聚类结构,Step 1：有序种子队列初始为空结果队列初始为空 ； Step 2：如果所有点处理完毕算法结束；否则选择一个未处理对象（即不在结果队列中）放入有序种子队列： Step 3：如果有序种子队列为空，返回Step 2，否则选择种子队列中的第一个对象P进行扩张： Step 3.1：如果P不是核心节点转Step 4；否则，对P 的E邻域内任一未扩张的邻居q 进行如下处理 Step 3.1.1：如果q已在有序种子队列中且从P到 q的可达距离小于旧值，则更新q的可达距离，并调整q到相应位置以保证队列的有序性； Step 3.1.2：如果q不在有序种f