Design of computationally efficient density-based clustering algorithms

Efficent density-based clustering algorightms

title: Design of computationally efficient density-based clustering algorithms ---- pdf download

code: None

abstract

本文针对基于密度的聚类方法，提出了优化策略，能够大幅度降低计算复杂度。针对DBSCAN聚类策略，首先通过快速融合策略来降低初始化阶段的计算复杂度，然后考虑到相似性度量时候的相关系数，通过相关性来判断两个点是否属于同一个类。

proposed algorithm

DBSCAN算法一共分为两步：初始化核心对象和合并小的类两个步骤，该方法和传统的DBSCAN的方法有所不同，传统的DBSCAN中提到的两阶段方法如下：

第一步，计算所有的核心对象，得到核心对象集合
第二步，随机从核心对象集合中间取一个样本，计算该核心对象所有密度直达的点，依次判断这些点是否是核心对象，如果是的话，就加入到该核心对象的cluster中，否则（边界点）跳过该点。其中每个点只能被访问一次，也就是说每个点一旦被某个cluster吸收进去了，就不会在被其他cluster进行吸收，因此DBSCAN的最终分类的结果和样本的访问顺序是有关的，即DBSCAN是一种不稳定的聚类方法。

针对DBSCAN的方法，本文在第二步的时候，没有依次判断核心对象的所有密度直达的点是否是核心对象，而是在第一步计算完所有的核心对象之后，得到每个核心对象的small cluster之后，对这些small cluster进行合并，并且采用了一种很巧妙的方法极大的降低了计算复杂度。

合并策略如下

（1）基于距离度量的快速合并算法

对于两个cluster A 和 B，两个cluster的距离计算如下：

$d(C_1, C_2) = min\{d(y,z)\} ----(1)$

其中y和z分别是 $C_1$ 和 $C_2$ 的边界点，因此（1）的计算复杂度应为 $N(C_1) * N(C_2)$

image.png

加速策略：

但是考虑到每个cluster在高维空间是一个球形，因此我们先计算cluster A 和 cluster B的点，分别为 $A_0$ 和 $B_0$ ，如果 $A_0$ 和 $B_0$ 之前的距离大于 $3*\epsilon$ ，则A和B的最小点的距离必然大于 $\epsilon$ ，根据这个条件，我们可以判断两个类是否进行合并。