基于密度的方法：DBSCAN

• DBSCAN=Density-Based Spatial Clustering of Applications with Noise
• 本算法将有足够高密度的区域划分为簇，并可以发现任何形状的聚类

若干概念

r-邻域：给定点半径r内的区域

核心点：如果一个点的r-邻域至少包含最少数目M个点，则称该点为核心点

直接密度可达：如果点p在核心点q的r-邻域内，则称p是从q出发可以直接密度可达

如果存在点链是从关于r和M直接密度可达 ，则称点p是从q关于r和M密度可达的

如果样本集D中存在点o，使得点p、q是从 o关于r和M密度可达的，那么点p、q是关于r和M密度相连的

DBSCAN基本思想

1. 指定合适的r和M
2. 计算所有的样本点，如果点p的r邻域里有超过M个点，则创建一个以p为核心点的新簇
3. 反复寻找这些核心点，直接密度可达（之后可能是密度可达）的点，将其加入到相应的簇，对于核心点发生”密度相连“状况的簇，给予合并
4. 当没有新的点可以被添加到任何簇时，算法结束

DBSCAN算法描述

输入：包含n个对象的数据库，半径e，最少数目MinPts

输出：所有生成的簇，达到密度要求

(1) Repeat

(2) 从数据库中抽出一个未处理的点

(3) IF抽出的点是核心点THEN找出所有从该点密度可达的对象，形成一个簇

(4) ELSE抽出的点是边缘点（非核心对象），跳出本次循环，寻找下一个点

(5) UNTIL所有的点都被处理

DBSCAN对用户定义的参数很敏感，细微 的不同都可能导致差别很大的结果，而参数的选择无规律可循，只能靠经验确定