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对于不同规模和密度的数据集不敏感。
introduction
聚类算法大概分为四类：
- 基于划分
- 基于层
- 基于密度
- 基于网格。
其中，基于划分的例如K-means算法，只能发现球形（凸形）的类簇。基于层次的聚类依赖于前面的计算结果，不利于并行计算。基于密度的DBSCAN和OPTICS可以发现任意形状的类簇，能够通过分解dataset实现并行计算。
本文做出的贡献：
本文在DBSCAN的基础上引入了一个椭圆近邻（ellipsoidal）参数
-- neighborhoods 并且利用R*树结构来实现高维空间近邻点的快速查找。
本文提出了一种并行算法DBCURE-MR，该算法可以使用MapReduce来实现并行加速计算，最终聚类准确性和DBCURE差不多。
本文提出的DBCURE-MR和DBCURE算法对于不同密度的样本表现都很不错，相比于OPTICS更加容易并行计算加速
本文提出的MapReduce并行算法也可以单独用于传统的DBSCAN算法，速度比当前的最新的DBSCAN算法都要快
related work
传统的DBSCAN和基于高斯核分布的DENCLUE方法对密度参数十分敏感，为了解决密度参数的敏感问题，提出了一种OPTICS的方法，该方法可以改变参数的大小，来根据不同的dataset来改变密度参数，但是该方法不能并行计算。
OPTICS方法和DBSCAN的方法原理差不多，本身不对样本数据直接排序，但是可以根据排序后的结果，加上
参数就可以得到不同的分类结果，所以这里说该方法对密度不敏感
在大规模的数据场景下，DBSCAN的计算速度将变得异常缓慢，计算距离矩阵的时间复杂度是, 为了加快DBSCAN的计算速度，可以采用抽样法、单独建立一个空间索引（spatial index）的方法，例如R*树，但是比较难以用于MapReduce计算框架中
并行DBSCAN的方法的思路一般分为两个步骤，第一步将数据集进行分割，然后将分割之后的数据集分别单独做DBSCAN聚类，然后将单独聚成的类进行合并操作。
DBCURE
本文作者提出的方法，the density-based clustering algorithm using ellipsoidal -- neighborhoods
Definition
样本点集：
,
为
维空间下的一个点，记为
点
邻域:
- 核心点（core point）和边界点（border point）
核心点：
边界点：
直接密度可达（directly density-reachable）：
表示从
点是
点的领域内的点
密度可达（density-reachable）：
表示通过中间点，
密度相连（desity-connected）:
如果点能够密度可达
近邻点协方差矩阵的估计
点的近邻点的协方差矩阵
表示近邻点的分布。
为
点的近邻点的平均值，其中
为对应近邻点的权重，该值通过MBR网格是否包含来确定其值为1或者0，由此我们可以得到近邻点的协方差矩阵公式：
proposed clustering algorithm
整体思想和DBSCAN一样，替换其中的近邻点的计算方法如下：
采用R*树来搜索近邻点，对每个点的每一维度的数据做如下限制，得到一系列满足条件的邻域点
example:
DBCURE-MR
算法的并行版本一共分为如下四步：
- 并行计算每个点的近邻点方差矩阵
- 计算椭圆
- 根据
的大小（DBSCAN中的MinPts）来确定核心点
- 逐个遍历核心点，将非核心点依次合并到核心点中，剩下的为噪声点(outliner点)
example:
DBCURE-Overview:
cluster 融合策略：
局部map：
全局map：
final:
experiments
参数：
