Cell-Based DBSCAN Algorithm Using Minimum Bounding Rectangle Criteria
Cell-Based DBSCAN Algorithm Using Minimum Bounding Rectangle Criteria
复制标题
DOI：
10.1007/978-3-319-55705-2_10
复制
发表时间：
2017-03
期刊：
影响因子：
--
通讯作者：
Tatsuhiro Sakai;Keiichi Tamura;H. Kitakami
中科院分区：
文献类型：
--
作者：
Tatsuhiro Sakai;Keiichi Tamura;H. Kitakami
基于密度的带噪声应用空间聚类（DBSCAN）算法是数据库领域中一种有效的聚类算法，可以对多维数据进行聚类，提取任意形状的簇。近年来，随着对大数据的兴趣的增长和数据的日益多样化，数据库的典型大小和容量已经增加，并且数据越来越变得高维。因此，大量的DBSCAN算法的加速技术，包括精确和近似的方法已被提出。最快的DBSCAN算法是基于单元的算法，它将整个数据集划分为小单元。在本文中，我们提出了一种新的精确版本的细胞为基础的DBSCAN算法使用最小包围矩形（MBR）标准。连接单元步骤是基于单元的算法中最耗时的步骤。该算法采用MBR准则，能够快速处理连接单元的步骤。我们实现了建议的基于细胞的DBSCAN算法，并表明它优于传统的高维。
The density-based spatial clustering of applications with noise (DBSCAN) algorithm has been well studied in database domains for clustering multi-dimensional data to extract arbitrary shape clusters. Recently, with the growing interest in big data and increasing diversification of data, the typical size and volume of databases have increased and data have increasingly become high-dimensional. Therefore, a large number of speed-up techniques for DBSCAN algorithms including exact and approximate approaches have been proposed. The fastest DBSCAN algorithm is the cell-based algorithm, which divides the whole data set into small cells. In this paper, we propose a novel exact version cell-based DBSCAN algorithm using minimum bounding rectangle (MBR) criteria. The connecting cells step is the most time-consuming step of the cell-based algorithm. The proposed algorithm can process the connecting cells step at high speed by using MBR criteria. We implemented the proposed cell-based DBSCAN algorithm and show that it outperforms the conventional one in high dimensions.