数据聚类|聚类——密度聚类（DBSCAN、OPTICS、DENCLUE）机器学习|算法|聚类

文章目录

- 一、基于高密度连通区域聚类算法DBSCAN
- - 基本术语
  - DBSCAN算法描述：
  - DBSCAN算法步骤
  - DBSCAN算法举例
  - 优点
  - 缺点
- 二、通过点排序识别聚类结构算法OPTICS
- - 两个定义：
  - OPTICS算法描述
  - OPTICS算法步骤
  - 算法流程图
- 三、基于密度分布函数的聚类算法DENCLUE
- - 算法原理
  - DENCLUE算法步骤
  - 主要思想
  - 参数选择
- 三、三种算法优劣对比
- 相关课件

密度聚类方法：
==基于密度的聚类方法以数据集在空间分布上的稠密程度为依据进行聚类，无需预先设定簇的数量，因此特别适合对于未知内容的数据集进行聚类。

一、基于高密度连通区域聚类算法DBSCAN 基本术语

邻域的最大半径：Eps
在 Eps-邻域中的最少点数：MinPts
核心对象 (Core object)：一个对象的ε-邻域至少包含最小数目MinPts个对象
噪声：不属于任何簇的对象(孤立点)
边界点：不是核心点 ,但落在某个核心点的 Eps 邻域内的对象

文章图片

直接密度可达：给定一个对象集合D，如果p是在q的ε-邻域内，而q是一个核心对象，我们说对象p从对象q出发是直接密度可达的。
密度可达的：如果存在一个对象链p1，p2，…，pn，p1=q， pn=p，对pi∈D，（1<=i<=n），pi+1是从pi关于ε和MitPts直接密度可达的，则对象p是从对象q关于ε和MinPts密度可达的。
密度相连的：如果对象集合D中存在一个对象o，使得对象p 和q是从o关于ε和MinPts密度可达的，那么对象p和q是关于ε和MinPts密度相连的。

举个栗子;

文章图片

若MinPts=3，q是从p密度可达；p不是从q密度可达（q非核心）s和r从o密度可达；o从r密度可达；r, s密度相连
DBSCAN算法描述：

输入：包含n个对象的数据库，半径ε，最少数目MinPts。
输出：所有生成的簇，达到密度要求。

DBSCAN算法步骤

文章图片

文章图片
DBSCAN算法举例
设n=12，用户输入ε=1，MinPts=4

文章图片

第1步，在数据库中选择一点1，由于在以它为圆心的，以1为半径的圆内包含2个点（小于4），因此它不是核心点，选择下一个点。
第2步，在数据库中选择一点2，由于在以它为圆心的，以1为半径的圆内包含2个点，因此它不是核心点，选择下一个点。
第3步，在数据库中选择一点3，由于在以它为圆心的，以1为半径的圆内包含3个点，因此它不是核心点，选择下一个点。

文章图片
第4步，在数据库中选择一点4，由于在以它为圆心的，以1为半径的圆内包含5个点，因此它是核心点，寻找从它出发可达的点（直接可达4个，间接可达3个），聚出的新类{1，3，4，5，9，10，12}，选择下一个点。

文章图片
第5步，在数据库中选择一点5，已经在簇1中，选择下一个点。
第6步，在数据库中选择一点6，由于在以它为圆心的，以1为半径的圆内包含3个点，因此它不是核心点，选择下一个点。

文章图片

第7步，在数据库中选择一点7，由于在以它为圆心的，以1为半径的圆内包含5个点，因此它是核心点，寻找从它出发可达的点，聚出的新类{2，6，7，8，11}，选择下一个点。

文章图片

第8步，在数据库中选择一点8，已经在簇2中，选择下一个点。
第9步，在数据库中选择一点9，已经在簇1中，选择下一个点。
第10步，在数据库中选择一点10，已经在簇1中，选择下一个点。
第11步，在数据库中选择一点11，已经在簇2中，选择下一个点。
第12步，选择12点，已经在簇1中，由于这已经是最后一点所有点都以处理，程序终止。

步骤	选择为的点	在ε中点的个数	通过计算可达点而找到的新簇
1	1	2	无
2	2	2	无
3	3	3	无
4	4	5	簇C1：{1，3，4，5，9，10，12}
5	5	3	已在一个簇C1中
6	6	3	无
7	7	5	簇C2：{2，6，7，8，11}
8	8	2	已在一个簇C2中
9	9	3	已在一个簇C1中
10	10	4	已在一个簇C1中
11	11	2	已在一个簇C2中
12	12	2	已在一个簇C1中

文章图片
优点

能克服基于距离的算法只能发现“类圆形”的聚类的缺点，可发现任意形状的聚类，有效地处理数据集中的噪声数据，数据输入顺序不敏感

缺点

1.输入参数敏感．确定参数ε，MinPts困难，若选取不当，将造成聚类质量下降
2.由于在DBSCAN算法中，变量ε，MinPts是全局惟一的，当空间聚类的密度不均匀、聚类间距离相差很大时，聚类质量较差。
3.计算密度单元的计算复杂度大，需要建立空间索引来降低计算量，且对数据维数的伸缩性较差。这类方法需要扫描整个数据库，每个数据对象都可能引起一次查询，因此当数据量大时会造成频繁的I/O操作。

二、通过点排序识别聚类结构算法OPTICS

文章图片
在图中所描述的数据集不能通过一个全局密度参数同时区分出簇A 、B 、C、C1、C2和C3，只能得到A 、B 、C或C1、C2和C3，对于C1、C2和C3而言A 、B 、C都是噪声。为了克服在聚类分析中使用一组全局参数的缺点，提出了OPTICS 聚类分析方法。
两个定义：

文章图片

文章图片

核心距离与可达距离,假设ε =6mm， MinPts =5 。P的核心距离是p于第四个最近的数据对象之间的距离ε‘，q1到p的可达距离是p的核心距离（ ε‘=3mm），因为它比q1到p的欧氏距离大。q2关于p的可达距离是p到q2的欧氏距离，它大于p的核心距离。

文章图片
OPTICS算法描述

文章图片

输入：样本集D, 邻域半径ε, 给定点在ε领域内成为核心对象的最小领域点数MinPts
输出：具有可达距离信息的样本点输出排序

OPTICS算法步骤

Step 1：有序种子队列初始为空﹒结果队列初始为空；
Step 2：如果所有点处理完毕，算法结束；否则选择一个未理对象放入有序种子队列；
Step 3 ：如果有序种子队列为空，返问Step 2，否则选择第一个对象p进行扩张；
?Step 3.1：如果p不是核心点，转Step 4；否则，对p的ε邻域内任一未扩张的邻居q；
??Step 3.1.1：如果q 已在有序种子队列中且从p到q 的可达距离小于旧值、则更新q
的可达距离，并调整q到相应位置以保证队列的有序性；
??Step 3.1.2 ：如果q不在有序种子队列中，则根据p到的可达距离将其插入有序队列；
Step 4：从有序种子队列中删除p，并将p写入结果队列中，返回 Stp 3。

算法流程图

D: 待聚类的集合
Q: 有序队列，元素按照可达距离排序，可达距离最小的在队首
O: 结果队列，最后输出结果的点集的有序队列

文章图片

得到结果队列后，使用下面算法得到最终的聚类结果：

从结果队列中按顺序取出点，如果该点的可达距离不大于给定半径ε，则该点属于当前类别，否则至步骤2
如果该点的核心距离大于给定半径ε，则该点为噪声，可以忽略，否则该点属于新的聚类，跳至步骤1
结果队列遍历结束，则算法结束

文章图片

得到了输出结果序列，每个节点的可达距离和核心距离。将可达距离为纵轴，样本点输出次序为横轴进行可视化：

文章图片

其中：
X轴代表OPTICS算法处理点的顺序，Y轴代表可达距离。
簇在坐标轴中表述为山谷，并且山谷越深，簇越紧密
黄色代表的是噪声，它们不形成任何凹陷。
OPTICS的核心思想：
较稠密簇中的对象在簇排序中相互靠近
一个对象的最小可达距离给出了一个对象连接到一个稠密簇的最短路径