密度聚类

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

基于密度聚类的特性

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

一些研究

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

DBSCAN

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

几个重要概念

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

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

DBSCAN簇定义

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

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

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

如何找簇

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

算法描述

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