8.4 基于密度的聚类在线视频

由于基于划分的聚类算法

与基于层次的聚类算法

往往只能发现球形的聚类簇

对于其他类型的聚类簇

如图所示的S型和椭圆型的聚类效果

并不理想

为了更好地

发现各种形状的聚类簇

提出了基于密度的聚类算法

基于密度的聚类算法是以

数据集在空间中分布的稠密程度

为依据进行聚类

并不需要预先设定簇的数量

因此适合对于未知内容的数据集

进行聚类

常见的基于密度的聚类算法有

DBSCAN

OPTICS

DENCLUE等

这里主要介绍DBSCAN算法

先介绍相关的概念

ε-邻域

对象o的ε-邻域是以该对象为中心

ε为半径的空间

核心对象

用户指定一个参数MinPts

指定稠密区域的密度阈值

如果一个对象的ε-邻域

至少包含MinPts个对象

则称该对象为核心对象

直接密度可达

对于指定的对象集合D

有对象p与q

如果对象p在对象q的ε-邻域内

并且q是核心对象

则称对象p是从

对象q关于ε-和MinPts

直接密度可达的

密度可达

假设有对象链

pˇ1,pˇ2,…,pˇn

且pˇ1=q

pˇn=p

如果对于pˇi (1≤i

有pˇ(i+1)

是从pˇi关于ε和MinPts

直接密度可达的

则称p是从对象q关于ε和MinPts

密度可达的

密度相连

对于指定的对象集合D

如果存在一个对象o

使得对象p和对象q

从o关于ε-和MinPts密度可达

那么对象p和对象q

是关于ε和MinPts密度相连的

边界对象

对于对象p

如果它的ε-邻域内

包含的对象少于MinPts个

但落在某个核心对象的ε-邻域内

则称对象p为边界对象

噪声对象

既不是核心对象

也不是边界对象的任何对象

例

密度可达与密度相连

给定圆的半径ε

令MinPts =3

考虑下图各点之间的关系

在图中

点m、p、o和r的ε-邻域中

均包含3个以上的点

因此它们都是核心对象

点m是从p直接密度可达的

q也是从m直接密度可达的

因此q是从p密度可达的

但p从q无法密度可达

即非对称

类似地

s和r从q是密度可达的

q、r和s均是密度相连（对称）的

DBSCAN

具有噪声应用的基于密度的空间聚类

根据以上概念

在数据对象集中查找簇和噪声

这里的簇指的是对象集中的簇

即核心对象密度可达的所有对象的集合

该算法的基本思想

每个簇的内部点的密度

比簇的外部点的密度要高得多

它定义簇为“密度相连”的

最大对象集

不包含在任何簇中的对象

被认为是“噪声”

DBSCAN算法将簇

定义为密度相连的点的最大集合

能够把

具有足够高密度的区域划分为簇

并可在噪声的空间数据库中

发现任意形状的聚类

能有效排除噪声的干扰

并且聚类结果

不受输入顺序的影响

DBSCAN发现簇的过程如下

①初始给定数据集D中

所有对象被标记为“unvisited”

②随机选择一个未访问的对象p

标记p为“visited”

并检查p的ε-邻域

是否至少包含MinPts个对象

如果不是

则p被标记为噪声点

否则为p创建一个新的簇C

并且把p的ε-邻域中

所有对象都放在候选集合N中

③迭代地把N中不属于

其他簇的对象添加到C中

在此过程中

对于N中标记为“unvisited”的对象p'

把它标记为“visited”

并且检查它的ε-邻域

如果p'的ε-邻域

至少包含MinPts个对象

则p'的ε-邻域中的对象都被添加到N中

继续添加对象到C

直到C不能扩展

即直到N为空

此时簇C完成生成

输出即可

④从剩下的对象中

随机选择一个未访问过的对象

重复②和③

直到所有对象都被访问

例 使用DBSCAN算法进行聚类

例 使用DBSCAN算法进行聚类

设有数据集D

对象分布如图所示

设ε=1

MinPts=4

利用DBSCAN算法进行聚类

解

对图中的对象

以从上往下

从左往右的顺序进行编号

以标识对象

①标记所有点为unvisited

②随机选择点6

标记为visited

以它为圆心

半径为1的邻域内包含2个点

不满足不小于MinPts的要求

因此它不是核心点

暂标记为噪声

如图所示

③随机选择点2

标记为visited

以它为圆心

半径为1的邻域内包含3个点

不满足不小于MinPts的要求

可知其不是核心点

暂标记为噪声

④随机选择点1

标记为visited

以它为圆心

半径为1的邻域内包含3个点

不满足不小于MinPts的要求

可知其不是核心点

暂标记为噪声

⑤随机选择点5

标记为visited

以它为圆心

半径为1的邻域内包含5个点

大于MinPts

可知其为核心点

生成新簇C1

将点5放入C1

即C1={5}

将点5的半径为1的邻域内的点

放入候选集合N中

即N=2,4,6,7点的集合

其中点2和点6为visited

点4和点7为unvisited

在N中选择unvisited的点4

标记为visited

以点4为圆心

半径为1的邻域内包含4个点

等于MinPts

可知点4也是核心点

因点4不属于其他簇

将点4放入C1

即C1={4,5}

将点4的半径为1的邻域内的点

放入候选集合N中

即N=1,2,3,6,7的集合

其中点1、点2和点6为visited

点3和点7为unvisited

在N中选择unvisited的点3

标记为visited

以点3为圆心

半径为1的邻域内包含2个点

不满足不小于MinPts的要求

可知其不是核心点

因点3不属于其他簇

将点3放入C1

即C1=3,4,5集合

N=1,2,6,7点的集合

其中点1、点2和点6为visited

点7为unvisited

在N中选择unvisited的点7

标记为visited

以点7为圆心、半径为1的邻域内包含3个点

不满足不小于MinPts的要求

可知其不是核心点

因点7不属于其他簇

将点7放入C1

即C1=3,4,5,7的集合

N=1,2,6集合

其中点1、点2和点6为visited

在N中点1、点2和点6虽为visited

但它们不属于其他簇

将它们放入C1

即C1=1,2,3,4,5,6,7的集合

N={}

这样可以得到一个簇

C1=1,2,3,4,5,6,7的集合

如图所示

⑥在其他unvisited的点中

随机选择点8

标记为visited

以它为圆心

半径为1的邻域内包含3个点

不满足不小于MinPts的要求

可知其不是核心点

暂标记为噪声

⑦随机选择unvisited的点10

标记为visited

以它为圆心

半径为1的邻域内有5个点

大于MinPts

可知其是核心点

生成新簇C2

将点10放入C2

即C2={10}

将点10的半径为1的邻域内的点

放入候选集合N中

即N=8,9,11,12的集合

其中点8为visited

点9、点11和点12为unvisited

在N中选择unvisited的点9

标记为visited

以点9为圆心

半径为1的邻域内包含2个点

不满足不小于MinPts的要求

可知其不是核心点

因点9不属于其他簇

将点9放入C2

即C2=9,10的集合

N=8,11,12的集合

其中点8为visited

点11和点12为unvisited

在N中选择unvisited的点11

标记为visited

以点11为圆心

半径为1的邻域内包含2个点

不满足不小于MinPts的要求

可知其不是核心点

因点11不属于其他簇

将点11放入C2

即C2=9,10,11的集合

N=8,12的集合

其中点8为visited

点12为unvisited

即C2包括9 10 11 点的集合

N包括8 12 点的集合

其中点8为visited

点12为unvisited

在N中选择unvisited的点12

标记为visited

以点12为圆心

半径为1的邻域内包含2个点

不满足不小于MinPts的要求

可知其不是核心点

因点12不属于其他簇

将点12放入C2

即C2=9,10,11,12的集合

N包括点8

其中点8为visited

在N中点8虽为visited

但它不属于其他簇

将它放入C2

即C2=8,9,10,11,12的集合

N为空集

可得到新簇C2

包括8,9,10,11,12的集合

如图所示

至此

数据集D中的所有点都为visited

这样就将原数据集D划分为

两个簇

C1包括

1,2,3,4,5,6,7点的集合

和C2

包括8,9,10,11,12点的集合

如图所示

DBSCAN聚类算法

可以对任意形状的稠密数据集

进行聚类

可以在聚类的同时发现异常点

对数据集中的异常点不敏感

聚类结果没有偏倚

但如果样本集的密度不均匀

聚类间距差相差很大时

聚类质量较差

这时用

DBSCAN聚类算法一般不适合

其次

如果样本集较大时

聚类收敛时间较长

再者

调参相对复杂

主要需要对距离阈值ε

邻域样本数阈值MinPts联合调参

不同的参数组合

对最后的聚类效果有较大影响