MR-IDBSCAN
title: MR-IDBSCAN: Efficient Parallel Incremental DBSCAN Algorithm using MapReduce pdf download
code: None
abstract
本文基于DBSCAN的思想，提出了一种结合HadoopMapReduce计算框架的并行增量式DBSCAN聚类方法。在大数据量的情景下，该方法能够大幅度降低计算复杂度
introduction
聚类是一种无监督学习方式，根据类型不同，通常可以分为基于层次、基于划分、基于密度和基于网格的几种类型。DBSCAN是一种基于密度的聚类算法，通过将紧密相连的样本划分为各个不同的类别，就能得到最终的聚类结果。
DBSCAN基于一组领域来描述样本集的紧密程度，参数eps和MinPts分别表示领域距离的阈值和领域样本的个数，当满足领域阈值的样本个数大于等于MinPts的时候, 得到核心类，逐次迭代，得到最终结果。
DBSCAN具体的密度描述定义如下：
1） ϵ-邻域：对于xj∈D，其ϵ-邻域包含样本集D中与xj的距离不大于ϵ的子样本集，即, 这个子样本集的个数记为
- 核心对象：对于任一样本
，如果其ϵ-邻域对应的
至少包含
MinPts个样本，即如果，则
是核心对象。
3）密度直达：如果位于
的ϵ-邻域中，且
是核心对象，则称
由
密度直达。注意反之不一定成立，即此时不能说
由
密度直达, 除非且
也是核心对象。
4）密度可达：对于和
,如果存在样本样本序列
,满足p1=xi,pT=xj, 且pt+1由pt密度直达，则称
由
密度可达。也就是说，密度可达满足传递性。此时序列中的传递样本
,均为核心对象，因为只有核心对象才能使其他样本密度直达。注意密度可达也不满足对称性，这个可以由密度直达的不对称性得出。
5）密度相连：对于和
,如果存在核心对象样本
，使
和
均由
密度可达，则称
和
密度相连。注意密度相连关系是满足对称性的。
参考资料：
contribution
本文提出的一种增量式DBSCAN的方法，能够将新来的数据聚合和成的类，然后和之前的cluster进行合并操作。该算法中采用R-*树数据结构实现高维空间的索引。算法只考虑新数据和老数据的交集，对于每一个交集中的点，用增量式DBSCAN算法来确定新cluster的成员。
新类和老类的eps和MinPts应该是一致的。
新类和老类合并过程中，old cluster中密度不可达的点（Noise point）可能变成密度可达的点（Border point），old cluster中的border point也有可能变成了核心对象（Core point）,因此合并过程中，我们需要考虑的就是这些变化情况。
algorithm
IDBSCAN : Incremental DBSCAN algorithm
增量式DBSCAN算法描述：
- 初始数据集按照DBSCAN的方法聚类，得到
的类簇
- 新加入的数据集单独按照DBSCAN的方法聚类，得到
的类簇
- 计算
和
有相交部分的cluster，得到这些 cluster 的点（affected point），记为APS
- 从C中的核心对象出发，依次判断 APS是否密度可达，是则合并该点所在的cluster和C中当前的可达的核心对象的cluster
- 从C中的（border point）出发，依次判断 APS是否密度相连（old cluster 中的border point 变成了 new cluster 的core point），是则合并该点所在的cluster和C中当前的可达的核心对象的cluster
- 不满足4和5的点，保持不变；APS之外的incremental cluster也保持不变，都合并到new cluster
- 对于 old 和 new cluster 的噪声点（Noise point）,如果变成了某个cluster的border point，则将被吸收到该cluster中。
MR-IDBSCAN：
MR-IDBSCAN在IDBSCAN的基础上，使用Hadoop的Map Reduce框架实现了大规模数据下的增量式聚类。
MR-IDBSCAN
LC: Local Cluster, 在每个Map任务中，单独进行聚类之后的局部的cluster
GC：LC合并之后，得到的Global Cluster
summary
这篇文章利用Hadoop MapReduce计算框架，提出了增量式DBSCAN的聚类方法，能够在解决大规模数据下，单机无法处理的问题，并且增量式聚类能够显著降低计算量。
image.png
随着数据量的增大，MR-IDBSCAN的方法计算速度上的优势越来越明显
网友评论