Density Based Spatial Clustering of Applications with Noise

• 1. Algorithm
• 2. 一个朴素的并行求解方法

1. Algorithm

在DBSCAN中，数据点分为3类

• core points
• reachable points
• outliers

对于数据点$p$，如果与其距离小于$\epsilon$的数据点$q$数量超过minPts，则称$p$为core points，而$q$称为$p$的directly reachable

如果存在一个序列$p_1,p_2,...,p_n$，其中$p_1,p_2,...,p_{n-1}$都是core point，且$p_{i+1}$都是$p_i$的directly reachable，则称$p_n$为$p_1$的reachable

非任何core point的reachable point则称为outliers

DBSCAN如此定义一个簇

• 其中的所有core points都是互相的reachable
• 任意普通点都是簇中一个core point的directly reachable

2. 一个朴素的并行求解方法

• 两两计算距离，小于$\epsilon$则视为一条边连接，构建无向图的邻接表
• 根据邻接表标记core point
• 将每个core point与其邻接点构建集合
• 集合两两尝试合并（若有相同的core point则合并）
• 当任意两个集合都没有相同的core point结束，此时剩余的每个集合都是一个簇