基于密度的聚类算法：DBSCAN

只要一个区域中的点的密度大于某个阈值，就把它加到与之相近的聚类中去。

对于一个类中的每个对象，在其给定半径的领域中包含的对象不能少于某一给定的最小数目；

概念：

设置半径阈值$r$,数量阈值$m$;

核心对象的$r$-邻域至少包$m$个对象；

从核心对象出发，对任何$r$邻域内的点直接密度可达；

如果存在一个对象链$p_1，p_2，…，p_n，p_1=q，p_n=p$，对$p_i∈D，1\le i\le n$，$p_{i+1}$是从$p_i$关于$r,m$直接密度可达的，则对象$p$是从对象$q$​相互密度可达的。

如果存在一个对象$o$，使得对象$p$和$q$是从$o$关于$r,m$密度可达的，那么对象$p$和$q$​是密度相连的。

一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合 ;

• 连接性：$x_i\in C,x_j\in C \Rightarrow x_i,x_j$密度相连；
• 最大性：$x_i\in C,x_j$由$x_i$密度可达，$\Rightarrow x_j \in C$

DBSCAN算法先任选数据集中的一个核心对象为“种子” ,再由此出发确定相应的聚类簇;

算法类似于BFS搜索，维护一个队列；

优点：

• 能克服基于距离的算法只能发现“类圆形”的聚类的缺点，可发现任意形状的聚类；
• 对噪声数据不敏感；

缺点：

• 计算复杂度大，需要建立空间索引来降低计算量；
• 数据维数的伸缩性较差；
• 对参数$r,m$非常敏感；
• 如果数据库比较大的时候要进行大量的I/O 开销;
• 很难找到不同密度的簇;