DBSCAN 论文笔记-理解

本文主要是介绍DBSCAN 论文笔记-理解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

论文: 点击这里下载DBSCAN论文原文

论文翻译:-.-

理解参考:

论文/算法的理解
https://www.cnblogs.com/pinard/p/6208966.html
http://blog.csdn.net/Exupery_/article/details/76181272
Python sklearn.cluster.DBSCAN的理解使用
http://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html
http://scikit-learn.org/stable/auto_examples/cluster/plot_dbscan.html#sphx-glr-auto-examples-cluster-plot-dbscan-py
http://www.jianshu.com/p/b004861105f4
https://www.cnblogs.com/pinard/p/6217852.html
http://blog.csdn.net/garfielder007/article/details/50757111

核心技术:

密度聚类原理
DBSCAN是一种基于密度的聚类算法(density-based clustering),此类算法假设聚类结构能够通过样本分布的紧密程度确定.通常情况下,密度聚类算法从样本的密度的角度来考察样本之间的可连接性,并基于可连接样本不断扩展聚类簇以获得最终的聚类结果.
DBSCAN中的一些定义
DBSCAN基于一组”邻域”(neigh-borhood)参数( $\epsilon$ , MinPts)来刻画样本分布的紧密程度,给定数据集 $D={x_1,x_2,.....x_m}$ ,定义一下几个概念:

2)核心对象(Core Object):若 $x_j$ 的 $\epsilon$ -邻域至少包含MinPts个样本,即 $|N_\epsilon(x_j)|\geq MinPts$ ,则 $x_j$ 是一个核心对象;

3)密度直达(directly density-reachable):若 $x_j$ 位于 $x_i$ 的 $\epsilon$ -邻域中,且 $x_i$ 是核心对象,则称 $x_j$ 由 $x_i$ 密度直达.

4)密度可达(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$ 密度可达;

5)密度相连(density-connected):对于 $x_i$ 与 $x_j$ ,如果存在 $x_k$ 使得 $x_i$ 与 $x_j$ 均由 $x_k$ 密度可达,则称 $x_i$ 和 $x_j$ 密度相连;

6)簇(cluster):一个具有参数( $\epsilon$ , MinPts)的簇 $C$ 是满足如下条件的一个D的非空子集:
i) $\forall p,q$ : if $p\in C$ and q is density-reachable from $p$ ( $\epsilon$ , MinPts) , then $q\in C$ (Maximality)
ii) $\forall p,q \in C$ : $p$ is density-connected to $q$ ( $\epsilon$ , MinPts).(Connectivity)

7)噪声点(noise): Let $C_1,C_2,....C_k$ be the clusters of the database D ( $\epsilon_i$ , MinPts_i,i=1,2…k). Then we define the noise as the set of points in the database $D$ not belonging to any cluster $C_i$ i.e. noise = { $p\in D | \forall i: p\notin C_i$ }

8)核心点：在半径Eps内含有超过MinPts数目的点。
边界点：在半径Eps内点的数目小于MinPts，但是落在核心点的临域内。
噪音点：既不是核心点也不是边界点的点。

概念的直观展示(来自周志华老师<机器学习>一书,p212,图9.8)
这里写图片描述
- 算法流程
1)将所有点标记为核心点、边界点或噪声点。
2)删除噪声点。
3)为距离在Eps之内的所有核心点之间赋予一条边。
4)每组连通的核心点形成一个簇。
5)将每个边界点指派到一个与之关联的核心点的簇中（哪一个核心点的半径范围之内）。
伪代码如下(来自周志华老师的<机器学习>一书,p213,图9.9):
这里写图片描述