ML - DBSCAN

密度聚类：desity-based clustering

此类算法假设聚类结构能通过样本分布的紧密程度确定。通常情形下，密度聚类算法从样本的密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇以获得最终的聚类结果。

DBSCAN是著名的密度聚类算法。它常常用于异常检测，他的注意力放在离群点上，所以，当遇到无监督的检测任务时，他是首选。

一些概念

1. DBSCAN: $基于一组邻域（neighborhood）参数来刻画样本分布的紧密程度，给定数据集D={x_1,x_2,…x_m}，定义一下几个概念：$基于一组邻域（neighborhood）参数来刻画样本分布的紧密程度，给定数据集D=x1​,x2​,…xm​，定义一下几个概念：
2. ϵ-邻域：$对x_j∈D,其ϵ-邻域包含样本集D中与x_j的距离不大于ϵ样本，即$对xj​∈D,其ϵ−邻域包含样本集D中与xj​的距离不大于ϵ样本，即
   
3. 核心对象(core object):$若x_j的ϵ-邻域至少包含MinPts个样本，即|N_ϵ (x_j )|≥MinPts,则x_j是一个核心对象$若xj​的ϵ−邻域至少包含MinPts个样本，即∣Nϵ​(xj​)∣≥MinPts,则xj​是一个核心对象
4. 密度直达(directly density-reachable):$若x_j位于x_i的ϵ-邻域中，且x_i是核心对象，则称x_j由x_i密度直达$若xj​位于xi​的ϵ−邻域中，且xi​是核心对象，则称xj​由xi​密度直达
5. 密度可达(density-reachable):$对x_i与x_j,若存在样本序列p_1,p_2,…,p_n,其中p_1=x_i，p_n=x_j且p_(i+1)由p_i密度直达，则称x_j由x_i密度可达$对xi​与xj​,若存在样本序列p1​,p2​,…,pn​,其中p1​=xi​，pn​=xj​且p(​i+1)由pi​密度直达，则称xj​由xi​密度可达
6. 密度相连(density-connected): $对x_i与x_j, 若存在x_k使得x_i与x_j均由x_k密度可达，则称x_i与x_j密度相连$对xi​与xj​,若存在xk​使得xi​与xj​均由xk​密度可达，则称xi​与xj​密度相连

例子

DBSCAN

基于以上概念，DBSCAN将“簇”定义为：由密度可达关系导出的最大的密度相连的样本集合。
DBSCAN算法先任选数据集中的一个核心对象为“种子”(seed),再有此初法确定相应的聚类簇。算法过程为：
1. 根据给定邻域参数(ϵ,MinPts)找出所有核心对象；
2. 以任一核心对象除法，找出其密度可达的样本生成聚类簇，直到所有核心对象均被访问过为止。

优点

1. 可以对任一形状的稠密数据集进行聚类，K-means一般只适用于球状数据集
2. 非常适合检测任务，寻找离群点
3. 不需要手动指定聚类的堆数（实际很难知道大致的堆数）

缺点

1. 样本集密度不均或聚类间距相差很大时，聚类效果较差
2. 半径的选择比较难，不同半径的结果差异非常大