密度聚类

基于密度的聚类，假设聚类结构能够通过样本分布的紧密程度确定。通常情况下，密度聚类算法从样本密度的角度来考察样本之间的可连接性。

基于密度聚类的特性

• 发现任意形状的聚类
• 处理噪声
• 一遍扫描（只检查局部区域来判断密度）
• 需要密度参数作为终止条件

一些研究

• DBSCAN (KDD’96)
• OPTICS (sigmod’99)
• DENCLUE (kdd’98)
• CLIQUE (SIGMOD’98)也是基于网格的

DBSCAN

全称Density-Based Spatial Clustering Appliacations with Noise
DBSCAN，它基于一组”领域”参数(ϵ,MinPts)来刻画样本分布的紧密程度。

几个重要概念

• e-邻域
  对xj∈D,其ϵ-邻域包含样本集D种与xj的距离不大于ϵ的样本，即Nϵ(xj)=[xj∈D|dist(xi,xj)≤ϵ]
• 核心对象(core object)
  若xj的ϵ-邻域至少包含Minpts个样本，即|Nϵ(xj)≥MinPts，则xj是一个核心对象
• 密度直达(directly density-raechable)
  若p位于q的ϵ邻域，且q是核心对象，则p由q密度直达。
• 密度可达(density-reachable)
  对于p和q，若存在样本序列p1,p2,...,pn其中p1=q,pn=p且pi+1由pi密度直达。则称p由q密度可达。
• 密度相连(density-connected)
  若p和q均由o密度可达到，则p和q密度相连接

密度直达通常不满足对称性。
密度可达关系满足直递性，不满足对称性。
密度相连关系满足对称性。

DBSCAN簇定义

DBSCAN将簇定义为：
由密度可达关系导出的最大的密度相连的样本集合。
形式化定义，给定邻域参数(ϵ,MinPts)，簇C⊆D是满足以下性质的非空样本子集：

• 连接性(connectivity):xi∈C,xj∈C→xi与xj密度相连
• 最大性(maximality):xi∈C,xj由xi密度可达→xj∈C

D种不属于任何簇的样本被认为是噪声或异常样本

如何找簇

若x是核心对象，由x密度可达的所有样本组成的集合为满足连接性和最大性的簇

算法描述

参考资料
《机器学习》周志华 p.211
Cluster Analysis in Data Mining-Coursera