Python语言PPT14.5DBSCAN聚类算法.ppt

1、问题问题 基于划分的聚类算法的弱点基于划分的聚类算法的弱点不适合用来发现具有非凸形状的簇不适合用来发现具有非凸形状的簇解决方法：基于密度的聚类解决方法：基于密度的聚类DBSCANDBSCAN是一个基于密度的是一个基于密度的聚类算法聚类算法.(其他聚类方法大其他聚类方法大都是基于对象之间的距离都是基于对象之间的距离进行聚类，聚类结果是球进行聚类，聚类结果是球状的簇状的簇)基于密度的聚类是寻找被基于密度的聚类是寻找被低密度区域分离的高密度低密度区域分离的高密度区域。区域。DBSCAN算法的基本思想算法的基本思想 该算法将簇定义为密度相连的点的最大集，将具该算法将簇定义为密度相连的点的最大集，将具有

2、高密度的区域划分为簇。有高密度的区域划分为簇。特点：不需要指定聚类的个数，聚类簇的形状可特点：不需要指定聚类的个数，聚类簇的形状可以是任意的。以是任意的。密度的定义密度的定义传统基于中心的密度定义为：传统基于中心的密度定义为：数据集中特定点的密度通过该点数据集中特定点的密度通过该点EpsEps半径之内的点计数半径之内的点计数来估计。来估计。显然，密度依赖于半径。显然，密度依赖于半径。传统的密度定义：基于中心的方法传统的密度定义：基于中心的方法 基于密度定义，我们将点分为：基于密度定义，我们将点分为：稠密区域内部的点稠密区域内部的点(核心点核心点)稠密区域边缘上的点稠密区域边缘上的点(边界点边界

3、点)稀疏区域中的点稀疏区域中的点(噪声或背景点噪声或背景点).).DBSCAN核心点核心点(core point)core point):在半径在半径EpsEps内含有超过内含有超过MinPtsMinPts数目的点，则该点为核心点数目的点，则该点为核心点 这些点都是在簇内的边界点边界点(border point):border point):在半径在半径EpsEps内点的数量小于内点的数量小于MinPtsMinPts，但是在核心点的邻居，但是在核心点的邻居噪音点噪音点(noise point):noise point):任何不是核心点或边界点的任何不是核心点或边界点的点点.DBSCANDBSC

4、AN:核心点、边界点和噪音点核心点、边界点和噪音点Original PointsPoint types:core,border and noiseEps=10,MinPts=4DBSCAN:核心点、边界点和噪音点核心点、边界点和噪音点DBSCAN算法概念Eps邻域：给定对象半径给定对象半径Eps内的邻域称为该对象的内的邻域称为该对象的Eps邻域，我邻域，我们用们用 表示点表示点p的的Eps-半径内的点的集合，即半径内的点的集合，即:核心对象：如果对象的如果对象的Eps邻域至少包含最小数目邻域至少包含最小数目MinPts的对的对象，则称该对象为核心对象。象，则称该对象为核心对象。边界点：边界点不

5、是核心点，但落在某个核心点的邻域内。边界点不是核心点，但落在某个核心点的邻域内。噪音点：既不是核心点，也不是边界点的任何点既不是核心点，也不是边界点的任何点)(pNEpsEpsq),distance(pDq|q)(中，在数据集pNEpsDBSCAN算法概念直接密度可达：给定一个对象集合给定一个对象集合D，如果，如果p在在q的的Eps邻域内，邻域内，而而q是一个核心对象，则称对象是一个核心对象，则称对象p 从对象从对象q出发时是直接密度可出发时是直接密度可达的达的(directly density-reachable)。密度可达：如果存在一个对象链如果存在一个对象链 ，对于对于 ，是从是从 关于

6、关于Eps和和MinPts直接直接密度可达的，则对象密度可达的，则对象p是从对象是从对象q关于关于Eps和和MinPts密度可达的密度可达的(density-reachable)。密度相连：如果存在对象如果存在对象OD，使对象，使对象p和和q都是从都是从O关于关于Eps和和MinPts密度可达的，那么对象密度可达的，那么对象p到到q是关于是关于Eps和和MinPts密度密度相连的相连的(density-connected)。ppqppppnn,121)1(niDpi1ipipDBSCAN算法概念示例算法概念示例 如图所示，如图所示，Eps用一个相应的半径表示，设用一个相应的半径表示，设MinP

7、ts=3，请分析，请分析Q,M,P,S,O,R这这5个样本点之间的关系。个样本点之间的关系。“直接密度可达直接密度可达”和和“密度可达密度可达”概念示意描述概念示意描述解答：根据以上概念知道：由于有标记的各点M、P、O的Eps近邻均包含3个以上的点，因此它们都是核对象；M是从P“直接密度可达”；而Q则是从M“直接密度可达”；基于上述结果，Q是从P“密度可达”；但P从Q无法“密度可达”(非对称)。类似地，S和R从O是“密度可达”的；O、R和S均是“密度相连”的。DBSCAN算法原理算法原理 DBSCAN通过检查数据集中每点的通过检查数据集中每点的Eps邻域来搜索簇，如邻域来搜索簇，如果点果点p的

8、的Eps邻域包含的点多于邻域包含的点多于MinPts个，则创建一个以个，则创建一个以p为核心对象的簇。为核心对象的簇。然后，然后，DBSCAN迭代地聚集从这些核心对象直接密度可迭代地聚集从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并达的对象，这个过程可能涉及一些密度可达簇的合并。当没有新的点添加到任何簇时，该过程结束当没有新的点添加到任何簇时，该过程结束.DBSCAN算法的输入算法的输入 DBSCAN共包括3个输入数据：数据集D，给定点在邻域内成为核心对象的最小邻域点数：MinPts,邻域半径：Eps参数设置参数设置(1)Eps的值可以使用绘制k-距离曲线(k-dist

9、ancegraph)方法得当，在k-距离曲线图明显拐点位置为对应较好的参数。若参数设置过小，大部分数据不能聚类；若参数设置过大，多个簇和大部分对象会归并到同一个簇中。（2）MinPts必须选择大于等于3的值。若该值选取过小，则稀疏簇中结果由于密度小于MinPts，从而被认为是边界点儿不被用于在类的进一步扩展；若该值过大，则密度较大的两个邻近簇可能被合并为同一簇。DBSCAN算法伪代码算法伪代码 输入：数据集输入：数据集D，参数，参数MinPts,Eps 输出：簇集合输出：簇集合(1)首先将数据集首先将数据集D中的所有对象标记为未处理状态中的所有对象标记为未处理状态(2)for 数据集数据集D中

10、每个对象中每个对象p do(3)if p已经归入某个簇或标记为噪声已经归入某个簇或标记为噪声 then(4)continue;(5)else(6)检查对象检查对象p的的Eps邻域邻域 ；(7)if 包含的对象数小于包含的对象数小于MinPts then(8)标记对象标记对象p为边界点或噪声点；为边界点或噪声点；(9)else(10)标记对象标记对象p为核心点，并建立新簇为核心点，并建立新簇C,并将并将p邻域内所有点加入邻域内所有点加入C(11)for 中所有尚未被处理的对象中所有尚未被处理的对象q do(12)检查其检查其Eps邻域邻域 ，若若 包含至少包含至少MinPts个对象，个对象，则将

11、则将 中未归入任何一个簇的对象加入中未归入任何一个簇的对象加入C；(13)end for(14)end if(15)end if(16)end for(p)NEps(p)NEps(q)NEps(q)NEps(p)NEps(q)NEpsDBSCAN聚类算法的细节聚类算法的细节DBSCAN运行效果好的时候运行效果好的时候Original PointsClusters 对噪音不敏感对噪音不敏感 可以处理不同形状和大小的数据可以处理不同形状和大小的数据DBSCAN运行不好的效果运行不好的效果Original Points(MinPts=4,Eps=9.75).(MinPts=4,Eps=9.92)密度

12、变化的数据密度变化的数据高维数据高维数据DBSCAN的其它问题的其它问题DBSCAN的时间复杂性的时间复杂性 时间复杂度时间复杂度DBSCANDBSCAN的基本时间复杂度是的基本时间复杂度是 O(NO(N*找出找出EpsEps领域中的点所需要领域中的点所需要的时间的时间),N),N是点的个数。最坏情况下时间复杂度是是点的个数。最坏情况下时间复杂度是O(NO(N2 2)在低维空间数据中在低维空间数据中,有一些数据结构如有一些数据结构如KDKD树，使得可以有效树，使得可以有效的检索特定点给定距离内的所有点，时间复杂度可以降低到的检索特定点给定距离内的所有点，时间复杂度可以降低到O(NlogN)O(

13、NlogN)DBSCAM的空间复杂性的空间复杂性 空间复杂度空间复杂度低维或高维数据中，其空间都是低维或高维数据中，其空间都是O(N)O(N)，对于每个点它只需要，对于每个点它只需要维持少量数据，即簇标号和每个点的标识维持少量数据，即簇标号和每个点的标识(核心点或边界点核心点或边界点或噪音点或噪音点)如何合适选取如何合适选取EPS和和MinPts思想是这样的思想是这样的:对于在一个类中的所有点对于在一个类中的所有点,它们的第它们的第k个最近邻大概距离是一样的个最近邻大概距离是一样的噪声点的第噪声点的第k个最近邻的距离比较远个最近邻的距离比较远所以所以,尝试根据每个点和它的第尝试根据每个点和它的

14、第k个最近邻之间的距个最近邻之间的距离来选取离来选取然后然后:Eps取什么？取什么？MinPts取什么？取什么？DBSCAN算法的优缺点算法的优缺点 优点优点基于密度定义，相对抗噪音，能处理任意形状和大小的簇基于密度定义，相对抗噪音，能处理任意形状和大小的簇 缺点缺点当簇的密度变化太大时，会有麻烦当簇的密度变化太大时，会有麻烦对于高维问题，密度定义是个比较麻烦的问题对于高维问题，密度定义是个比较麻烦的问题DBSCAN聚类算法的聚类算法的Sklearn实现实现 引入引入DBSCAN类类from sklearn.cluster import DBSCAN DBSCAN类的参数类的参数1）eps：即

15、邻域半径。默认值是：即邻域半径。默认值是0.5。2）min_samples：即最小包含点数，默认值是：即最小包含点数，默认值是5。3）metric：距离度量方法，默认使用欧式距离。：距离度量方法，默认使用欧式距离。4）algorithm：最近邻搜索算法参数：最近邻搜索算法参数例如：例如：y_pred=DBSCAN(eps=0.11,min_samples=10).fit(X)4.6 OPTICS聚类算法聚类算法一种一种DBSCAN的改进算法的改进算法DBSCAN算法存在的问题算法存在的问题 DBSCAN算法对输入参数比较敏感。给定全局参数算法对输入参数比较敏感。给定全局参数eps和和MinPt

16、s时，不同的全局参数会得到不同的聚类结果。时，不同的全局参数会得到不同的聚类结果。OPTICS聚类：有效地解决了密度不同导致的聚类效果不好的问题。OPTICS对对DBSCAN算法的改进算法的改进 OPTICS对对DBSCAN算法进行有效的扩展，其主要思想是算法进行有效的扩展，其主要思想是选取多个邻域参数选取多个邻域参数eps进行聚类，这样就能得到不同进行聚类，这样就能得到不同eps下的聚类结果下的聚类结果 并不直接将最初的聚类结果作为簇。而是对这些聚类并不直接将最初的聚类结果作为簇。而是对这些聚类结果进行排序，从这个排序中可得到各种结果进行排序，从这个排序中可得到各种eps和和MinPts时的聚类结果。时的聚类结果。OPTICS定义了两个新的概念定义了两个新的概念 核心距离：给定参数核心距离：给定参数（即（即eps）和）和M（即（即MinPts），使），使得样本得样本x成为核心点的最小邻域半径为成为核心点的最小邻域半径为x的核心距离的核心距离 只有核心点才有核心距离，核心距离实际上就是核心只有核心点才有核心距离，核心距离实际上就是核心点与其邻域半径内第点与其邻域半径内第M近点之间的距离