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

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

2、邻域的最大半径 minpts: 一个核心对象以 eps为半径的邻域内的最小顶点数,5,dbscan,密度 = 制定半径 (eps)内点的个数 如果一个对象的 eps 邻域至少包含最小数目minpts 个对象，则称该对象为核心对象（core point） 如果一个对象是非核心对象, 但它的邻域中有核心对象，则称该对象为边界点（ border point ） 除核心对象和边界点之外的点是噪声点（ noise point ）,dbscan: 核心、边界和噪声点,7,dbscan,密度可达的（density-reachable） 对于对象p和核心对象q(关于e和minpts),我们称p是从q(关于e和

3、minpts)直接密度可达，若对象p在对象q的e邻域内。 如果存在一个对象链 p1, , pn, p1 = q, pn = p ，pi+1 是从pi关于eps和minpts 直接密度可达的，则对象p是从对象q关于eps和minpts 密度可达的。 密度可达性是直接密度可达性的传递闭包，这种关系是非对称的。 只有核心对象之间是相互可达的。,8,dbscan,密度相连的（density-connected） 如果对象集合d中存在一个对象o，使得对象p和q是从o关于eps 和 minpts密度可达的，那么对象p和q是关于eps 和 minpts 密度相连的。 密度相连性是一个对称的关系。,dbsca

4、n算法概念示例,如图所示， 用一个相应的半径表示，设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均是“密度相连”的。,基于密度方法的聚类- dbscan,dbscan 算法根据以上的定义在数据库中发现簇和噪声。簇可等价于集合d中簇核心对象密度可达的所有对象的集合。 dbscan通过检查数据集中每

5、个对象的-邻域来寻找聚类。如果一个点p的-邻域包含多于minpts个对象，则创建一个p作为核心对象的新簇c。然后，dbscan从c中寻找未被处理对象q的-邻域，如果q的-邻域包含多minpts个对象，则还未包含在c中的q的邻点被加入到簇中，并且这些点的-邻域将在下一步中进行检测。这个过程反复执行，当没有新的点可以被添加到任何簇时，该过程结束。具体如下：,dbscan算法步骤,输入：数据集d，参数minpts, 输出：簇集合 (1) 首先将数据集d中的所有对象标记unvisited ； (2) do (3) 从d中随机选取一个unvisited对象p，并将p标记为visited ； if p的

6、邻域 包含的对象数至少为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 为噪声 (15) untill 没有标记为unvisited 的对象,基于密度方法的聚类- dbscan,下面给出一个样本事务数据库（见下表），对它实施dbscan算法。 根据所给的数

7、据通过对其进行dbscan算法，以下为算法的步骤（设n=12，用户输入=1，minpts=4）,样本事务数据库,dbscan聚类过程,第1步，在数据库中选择一点1，由于在以它为圆心的，以1为半径的圆内包含2个点（小于4），因此它不是核心点，选择下一个点。 第2步，在数据库中选择一点2，由于在以它为圆心的，以1为半径的圆内包含2个点，因此它不是核心点，选择下一个点。 第3步，在数据库中选择一点3，由于在以它为圆心的，以1为半径的圆内包含3个点，因此它不是核心点，选择下一个点。,dbscan聚类过程,第4步，在数据库中选择一点4，由于在以它为圆心的，以1为半径的圆内包含5个点，因此它是核心点，寻找

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

9、经在簇1中，选择下一个点。 第10步，在数据库中选择一点10，已经在簇1中，选择下一个点。 第11步，在数据库中选择一点11，已经在簇2中，选择下一个点。 第12步，选择12点，已经在簇1中，由于这已经是最后一点所有点都以处理，程序终止。,基于密度方法的聚类- dbscan,算法执行过程：,19,dbscan,original points,clusters,特点： 抗噪声 能处理任意形状聚类,基于密度方法的聚类,优点 能克服基于距离的算法只能发现“类圆形”的聚类的缺点，可发现任意形状的聚类，有效地处理数据集中的噪声数据，数据输入顺序不敏感 缺点 输入参数敏感确定参数，minpts困难，若选取

10、不当，将造成聚类质量下降 由于在dbscan算法中，变量，minpts是全局惟一的， 当空间聚类的密度不均匀、聚类间距离相差很大时，聚类质量较差。 计算密度单元的计算复杂度大，需要建立空间索引来降低计算量，且对数据维数的伸缩性较差。这类方法需要扫描整个数据库，每个数据对象都可能引起一次查询，因此当数据量大时会造成频繁的i/o操作。,optics 算法,尽管dbscan能够根据给定的输入参数，和minpts聚类对象，但是它把选择能产生可接受的聚类结果的参数值的责任留给了用户。这是许多其他算法都存在的问题。但是对于高维数据而言设定准确的参数非常困难。参数设置有细微的不同都可能导致差别很大的聚类结果

11、。全局参数不能很好地刻画其内在的聚类结构。,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的子集，这就意味着。如果两个对象在同一个基于密度的簇中，则它们也是在同一个具有较低密度要求的簇中。,23,optics：通过点排序识别聚类结构,对于真实的，高维的数据集合而言，参数的设置通常是依靠经验，难以确定。 绝大多数算法对参数值是非常敏感的：设置的细

12、微不同可能导致差别很大的聚类结果。 optics算法通过对象排序识别聚类结构。 optics没有显式地产生一个数据集合簇，它为自动和交互的聚类分析计算一个簇排序。 这个次序代表了数据的基于密度的聚类结构。较稠密中的对象在簇排序中相互靠近。,24,optics,簇排序选择这样的对象：即关于最小的e值，它是密度可达的，以便较高密度（较低e值）的簇先完成。 对象p的核心距离：使p成为核心对象的最小。如果p不是核心对象，那么p的核心距离没有任何意义。 可达距离：对象q到对象p的可达距离是指p的核心距离和p与q之间欧几里得距离之间的较大值。如果p不是核心对象，p和q之间的可达距离没有意义。,optics

13、 算法,核心距离与可达距离,假设 =6mm， minpts =5 。p的核心距离是p于第四个最近的数据对象之间的距离，q1到p的可达距离是p的核心距离（ =3mm），因为它比q1到p的欧氏距离大。q2关于p的可达距离是p到q2的欧氏距离，它大于p的核心距离。,optics 算法,optics 算法并不显式的产生数据及聚类，而是输出簇排序（cluster ordering），这个排序是所有分析对象的线性表，并且代表数据基于密度的聚类结构。 较稠密簇中的对象在簇排序中相互靠近。这个排序等价于从较广泛的参数设置中得到基于密度的聚类。这样optics不需要用户提供特定密度阈值。 簇排列可以用来提取基本

14、聚类信息，导出内在的聚类结构，也可以提供聚类的可视化。,optics 算法,为了构造不同的类，对象需要按特定的次序处理，这个次序选择这样的对象，及关于最小的值，它是密度可达的，以便较高密度（较低 值）的簇先完成。 optics 算法计算给定数据库中所有对象的排序，并且存储每个对象核心距离和相应的可达距离。 optics 维护一个称作order seeds 的表来来产生输出排列，orderseeds 中的对象按到各自的最近核心对象的可达距离排序，及按每个对象的最小可达距离排序。,28,optics：通过点排序识别聚类结构,算法思路 首先检查数据对象集合d中任一个对象的e邻域。设定其可达距离为“未

15、定义”，并确定其核心距离，然后将对象及其核心距离和可达距离写入文件。 如果p是核心对象，则将对象p的e邻域内的对象n (p)插入到一个种子队列中，包含在种子队列中的对象p按到其直接密度可达的最近的核心对象q的可达距离排序。 种子队列中具有最小可达距离的对象被首先挑选出来，确定该对象的e一邻域和核心距离， 然后将其该对象及其核心距离和可达距离写入文件中，如果当前对象是核心对象，则更多的用于扩展的后选对象被插入到种子队列中。 这个处理一直重复到再没有一个新的对象被加入到当前的种子队列 中。,29,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到相应位置以保证队列