2014-03-14
DBSCAN是基于密度的聚类方法。
1、基本概念
由于每个对象在实际应用中涉及到数值，所以这里也把“对象”叫做“数据点”，在平面上，一个数据点是二维的，可以使用两个值来表示一个数据点，例如(1.2,3)。一个数据集里的所有数据点应具有相同的维度。
r邻域：给定数据点在以其为中心的半径r内的邻域称为该数据点的r邻域。这个r邻域包含了给定的那个数据点，否则应称为r去心邻域。
核心对象：如果某数据点的r邻域内至少包含了MinPts个数据点，那么该数据点叫做核心对象。至于MinPts个数据点是否应该包含该数据点看个人的算法实现，差别不大。
直接密度可达：若数据点p在核心对象q的r邻域内，则p从q出发是直接密度可达的。
密度可达：设数据点点序列p(1)，p(2)，p(3)，...，p(n)，其中p(1)是核心对象，p(2)是从p(1)出发直接密度可达，p(n)从p(1)出发是密度可达的。
噪声：如果某个数据点的r邻域内没有任何其他数据点，则意味着该数据点也不在其他任何数据点的r邻域内，该数据点可以看做为噪声。
2、基本思路
1、给定数据点集合D，邻域半径r，以及最小数目MinPts。 生成簇标识C。
2、选取一个未被标记的数据点p，判断该数据点是否为核心对象，若是核心对象则跳到步骤3，否则4。
3、将数据点p密度可达的所有数据点标记为C，表明这些数据点已被分类且属于簇C。
4、若数据点p是噪声点，将p标记为噪声点，否则标记为非噪声点的非核心对象。
5、更新簇标识C，跳回2，直到所有数据点被标记。
分析一下，可以发现，如何获取某数据点在r邻域内的其他数据点是略有难度的。在维基百科中给出了两种解决思路：一种是构造距离矩阵，一种是使用空间索引。
3、更多
资料[1]给出了dbscan的较详细内容，包括伪代码、时间复杂度问题和优缺点。资料[2]列出了当前较有名的一些空间索引方法，其中包括R tree。如果要通过中文版速成R tree，请参考资料[3]。关于dbscan的matlab实现，请见资料[4]。
下篇文章讲述dbscan的matlab实现，链接：浅入浅出：DBSCAN聚类算法（2）。