摘要
Large-scale data clustering is an essential key for big data problem. However, no current existing approach is "optimal" for big data due to high complexity, which remains it a great challenge. In this article, a simple but fast approximate DBSCAN, namely, KNN-BLOCK DBSCAN, is proposed based on two findings: 1) the problem of identifying whether a point is a core point or not is, in fact, a kNN problem and 2) a point has a similar density distribution to its neighbors, and neighbor points are highly possible to be the same type (core point, border point, or noise). KNN-BLOCK DBSCAN uses a fast approximate kNN algorithm, namely, FLANN, to detect core-blocks (CBs), noncore-blocks, and noise-blocks within which all points have the same type, then a fast algorithm for merging CBs and assigning noncore points to proper clusters is also invented to speedup the clustering process. The experimental results show that KNN-BLOCK DBSCAN is an effective approximate DBSCAN algorithm with high accuracy, and outperforms other current variants of DBSCAN, including rho-approximate DBSCAN and AnyDBC.
学科与关键词
- GrDBSCAN: A Granular Density-Based Clustering AlgorithmSuchy, Dawid; Siminski, Krzysztof*International Journal of Applied Mathematics and Computer Science, 2023, 33(2): 297-312.
- Adaptive Density-Based Spatial Clustering for Massive Data AnalysisCai, Zihao; Wang, Jian; He, Kejing*IEEE Access, 2020, 8: 23346-23358.被引 11
- 一种基于高斯分布的自适应DBSCAN算法陈刚; 刘秉权; 吴岩微电子学与计算机, 2013, (03): 27.
