算法1.DBSCAN算法

输入：包含n个样本点的数据集 D = ( x 1 , x 2 , ⋯ , x n ) ；邻域参数(Eps, MinPts)

输出：点云簇划分C

1) 初始化核心对象集合 Ω = ∅ ，初始化聚类簇数k = 0，初始化未访问样本集合 Γ = D ，簇划分 C = ∅

2) 对于 j = 1 , 2 , ⋯ , n ，按以下步骤寻找出其核心对象：

a) 通过距离度量方式找到样本 x j 的 ϵ 邻域子样本集 N ϵ ( x j )

b) 如果子样本集个数满足 | N ϵ ( x j ) | ≥ MinPts ，将样本 x j 加入核心对象样本集合： Ω = Ω ∪ { x j }

3) 如果核心对象集合 Ω = ∅ ，则算法结束，否则转入步骤4。

4) 在核心对象 Ω 中，随机选择一个核心对象ο，初始化当前簇核心对象队列 Ω c u r = { ο } ，初始化类别序号 k = k + 1 ，初始化当前簇样本集合 C k = { ο } ，更新未访问样本集 Γ = Γ − { ο }

5) 如果当前簇核心对象队列 Ω c u r = ∅ ，则当前聚类簇 C k 生成完毕，更新簇划分 C = ( C 1 , C 2 , ⋯ , C k ) ，更新核心对象 Ω = Ω − C k ，转入步骤3。

6) 在当前簇核心对象队列 Ω c u r 中取出一个核心对象 ο ′ ，通过邻域距离阈值Eps找出所有Eps-邻域子样本集 N ϵ ( ο ′ ) ，令 Δ = N ϵ ( ο ′ ) ∩ Γ ，更新当前簇类样本集合 C k = C k ∪ Δ ，更新未访问样本集合 Γ = Γ − Δ ，更新 Ω c u r = Ω c u r ∪ ( Δ ∩ Ω ) − ο ′ ，转入步骤5。

7) 输出簇划分： C = ( C 1 , C 2 , ⋯ , C k )