DBCURE-MR:

title: DBCURE-MR: An efficient density-based clustering algorithm for large data using MapReduce pdf dowload

code： None

abstract

本文提出了一种新的基于密度的聚类算法，DBCURE，对于不同密度具有较好的鲁棒性，并且能够使用MapReduce并行处理（DBSCURE-MR），实验证明不会影响聚类结果。此外，DBSCAN-MR对于不同规模和密度的数据集不敏感。

聚类算法大概分为四类：

其中，基于划分的例如K-means算法，只能发现球形（凸形）的类簇。基于层次的聚类依赖于前面的计算结果，不利于并行计算。基于密度的DBSCAN和OPTICS可以发现任意形状的类簇，能够通过分解dataset实现并行计算。

本文做出的贡献：

本文在DBSCAN的基础上引入了一个椭圆近邻（ellipsoidal）参数 $\tau$ -- neighborhoods 并且利用R*树结构来实现高维空间近邻点的快速查找。
本文提出了一种并行算法DBCURE-MR，该算法可以使用MapReduce来实现并行加速计算，最终聚类准确性和DBCURE差不多。
本文提出的DBCURE-MR和DBCURE算法对于不同密度的样本表现都很不错，相比于OPTICS更加容易并行计算加速
本文提出的MapReduce并行算法也可以单独用于传统的DBSCAN算法，速度比当前的最新的DBSCAN算法都要快

传统的DBSCAN和基于高斯核分布的DENCLUE方法对密度参数十分敏感，为了解决密度参数的敏感问题，提出了一种OPTICS的方法，该方法可以改变 $\epsilon$ 参数的大小，来根据不同的dataset来改变密度参数，但是该方法不能并行计算。

OPTICS方法和DBSCAN的方法原理差不多，本身不对样本数据直接排序，但是可以根据排序后的结果，加上 $\epsilon$ 参数就可以得到不同的分类结果，所以这里说该方法对密度不敏感

在大规模的数据场景下，DBSCAN的计算速度将变得异常缓慢，计算距离矩阵的时间复杂度是 $n^2$ , 为了加快DBSCAN的计算速度，可以采用抽样法、单独建立一个空间索引（spatial index）的方法，例如R*树，但是比较难以用于MapReduce计算框架中

并行DBSCAN的方法的思路一般分为两个步骤，第一步将数据集进行分割，然后将分割之后的数据集分别单独做DBSCAN聚类，然后将单独聚成的类进行合并操作。

本文作者提出的方法，the density-based clustering algorithm using ellipsoidal $\epsilon$ -- neighborhoods

样本点集： $D=\{p_1,...,p_n\}$ , $p_i \in D$ 为 $d$ 维空间下的一个点，记为 $<p_i(1), p_i(2),...,p_i(d)>$
点 $p_i 的 \tau$ 邻域:

image.png

核心点： $|N_\tau(p_i) | + 1 >= \delta$
边界点： $|N_\tau(p_i) | + 1 < \delta$

直接密度可达（directly density-reachable）：
$p_i \to _t,_\delta p_j$ 表示从 $p_j$ 点是 $p_i$ 点的领域内的点
密度可达（density-reachable）：
$p_i \Rightarrow _t,_\delta p_j$ 表示通过中间点， $p_i$ 能够到达 $p_j$ 点
密度相连（desity-connected）:
如果点 $p_k$ 能够密度可达 $p_i$ 点，同时 $p_k$ 点能够密度可达 $p_j$ 点，则称 $p_i$ 和 $p_j$ 密度相连