算法在某个集合中找个一个或者多个的和等于某个固定值_聚类算法总结-2密度聚类..._weixin_39875031的博客-CSDN博客

安宇雨 - 随手采集
2021-02-01 14:16:55
随手采集
0000-未整理-等待研究

4. 基于密度的聚类算法

基于密度的聚类，没有使用距离作为度量，而是依据样本分布的紧密程度来确定聚类结构。其使用一定邻域内点的数量作为连通性的标准，并基于该连通性不断扩展聚类簇得到最终的聚类结果。基于密度的聚类可以处理形状不规则的类，如spherical球状，drawn-out拉长，linear线状，elongated细长等。

4.1 DBSCAN(Density-Based Spatial Clustering of Application with Noise)

4.1.1 算法介绍

DBSCAN是一种经典的基于密度的聚类方法。首先介绍两个基本参数Eps(ε)和MinPts和其基本概念。

Eps(ε)：为定义密度时的邻域半径。

MinPts：为定义核心点时的阈值。

ε邻域：对任意一个点p，其ε邻域定义为：

密度：对X中的点x，则

为x的密度

核心点：对X中的点x，若x的密度大于等于MinPts，则称x为X的核心点，核心点构成的集合为

,X中非核心点构成的集合记为

边界点：若x为X中的非核心点，x的邻域中存在核心点，则称x为X的边界点，X中所有边界点的集合记为

。也可以理解为X中的非核心点即

中的落在某个核心点的邻域内，则成x为X的一个边界点。一个边界点可以落入多个核心点的邻域中。

噪音点：X中既不属于Xc，也不属于Xbd的点称为噪音点，噪音点集合记为

。

核心点对应稠密区域内部的点，边界点对应稠密区域边缘的点，噪音点对应稀疏区域的点

直接密度可达directly density-reachable：设

, 若

，则称y是从x直接密度可达的

密度可达density-reachable：假设存在一串点

，使得

从

是直接密度可达的，则称

是

密度可达的。密度可达不具有对称性，

均为核心点，若

为边界点则无法从

到

直接密度可达，更别谈p_n到p_1了

密度相连density-connected：对于

,y和z均是从x密度可达的，则称y和z是密度相连的，显然密度相连具有对称性。

类簇cluster：若X的非空子集满足：对于

[1](Maximality)若

,且y是从x密度可达的，则

[2](Connectivity)若

，则x,y是密度相连的

则C构成X的一个类簇

DBSCAN算法的核心思想概述为：从某个选定的核心点出发，不断向密度可达的区域扩张，从而得到一个包含核心点和边界点的最大化区域，区域中任意两点密度相连。

算法过程为：

Step1:初始化

1.给定参数

和M

2.生成

Step 2:遍历生成cluster标记数组

1：对I中任一个未标注的点i，初始化

2:若

，则

（暂时标注为噪音点）；

3：若

，则标注i的标号为k，即将i归为第k簇，同时对T中的所有元素若未标注或标注为噪音点，则将其标注

改为k，即均归为第k簇；若存在T中的元素j为核心点，则将j的邻域也纳入到T中统一考虑。

4：设置k=k+1，准备标注k+1簇的点

上述算法瓶颈在于计算点i的邻域，为提高效率可以计算指标索引，如kdtree或网格划分等，减少判断密度可达时搜索的范围。算法中的T也是动态变化的，逐步随着已纳入点中的核心点的邻域而扩张。

4.1.2 参数分析

邻域半径

的选取，DBSCAN使用了统一的

值，这样X中所有数据的邻域大小都一样，当数据密度和类簇间距离分布不均匀时，则若选取较小的epsilon值，则稀疏部分点的密度小于阈值M而被认为是边界点，无法做到扩张。并且进一步的这较稀疏部分的点会被划分成多个类簇。若选取较大的邻域半径，则离的近而密度高的那些多个类簇可能被合并为一个类簇。对于高维数据，邻域半径的选取更加困难。

密度阈值M的选取，指导性原则是

, dim为数据空间的维度

4.1.3 优缺点

优点：

[1]不需要指定类簇数目，只需要邻域半径及密度阈值

[2]可以发现任意形状的类簇，对噪音点不敏感