《机器学习项目案例开发》课件 8.2聚类-DBSCAN.pptx

人工智能技术与应用

8.DBSCAN聚类;;DBSCAN概念;DBSCAN算法基本概念：

r邻域：给定对象半径为r内的区域称为该对象的r邻域。如图，P对象在半径r内构成的圆就是该对象的r邻域，如图1。

核心对象：如果给定对象r邻域内的样本点数大于等于MinPoints，则称该对象为核心对象；如图2：设置MinPoints的点为2，那么在对象p的e领域内有4个点，大于MinPoints，那么p对象就是核心对象。

ε-邻域的距离阈值：设定的半径r

直接密度可达：如果样本点q在p的r邻域内，并且p为核心对象，那么对象p-q直接密度可达，如图3。;DBSCAN算法基本概念：

密度可达：若有一个点的序列q0、q1、…qk，对任意qi-qi-1是直接密度可达的，则称从q0到qk密度可达，这实际上是直接密度可达的“传播”，如图1，q-p密度直达，m-q密度直达，那么m-p密度可达。

密度相连：若从某核心点p出发，点q和点k都是密度可达的,则称点q和点k是密度相连的，如图2：q-o是密度可达，p-o是密度可达，q-p是密度相连。

在DBSCAN中那些样本可以看成一个类（也称簇）。即最大的密度相连的样本集合。;密度可达与密度直达：

图中MinPts=5，红色的点都是核心对象，因为其?-邻域至少有5个样本。黑色的样本是非核心对象。所有核心对象密度直达的样本在以红色核心对象为中心的超球体内，如果不在超球体内，则不能密度直达。图中用绿色箭头连起来的核心对象组成了密度可达的样本序列。在这些密度可达的样本序列的?-邻域内所有的样本相互都是密度相连的。;DBSCAN算法基本概念：

边界点:属于某一个类的非核心点,不能发展下线了，如图中B、C点就是边界点。

噪声点：不属于任何一个类簇的点，从任何一个核心点出发都是密度不可达的，如图N点。

A核心对象、BC边界点、N离群点;DBSCAN流程：

参数D：输入数据集：

参数?：指定半径

MinPts：密度阀值;参数选择：

参数?：半径?，可以根据K距离来设定：找突变点

K距离：给定数据集P={p(i);i=0,1,…n}，计算点P(i)到集合D的子集S中所有点之间的距离，距离按照从小到大的顺序排序，d(k)就被称为k-距离。

MinPts：k-距离中k的值，一般取的小一些，多次尝试

;DBSCAN优缺点;敬请指导！