A Novel Recursive Non-Parametric DBSCAN Algorithm for 3D Data Analysis with an Application in Rockfall Detection
Pitisit Dillon*1,*2,, Pakinee Aimmanee*1, Akihiko Wakai*3, Go Sato*4, Hoang Viet Hung*5, and Jessada Karnjana*2
*1Sirindhorn International Institute of Technology, Thammasat University
Phahonyothin Road, Khlong Nueng, Khlong Luang, Pathum Thani 12120, Thailand
*2National Electronics and Computer Technology Center (NECTEC), National Science and Technology Development Agency, Pathum Thani, Thailand
*3Graduate School of Science and Technology, Gunma University, Gumma, Japan
*4Graduate School of Environmental Information, Teikyo Heisei University, Tokyo, Japan
*5Faculty of Civil Engineering, Thuyloi University of Vietnam, Hanoi, Vietnam
The density-based spatial clustering of applications with noise (DBSCAN) algorithm is a well-known algorithm for spatial-clustering data point clouds. It can be applied to many applications, such as crack detection, rockfall detection, and glacier movement detection. Traditional DBSCAN requires two predefined parameters. Suitable values of these parameters depend upon the distribution of the input point cloud. Therefore, estimating these parameters is challenging. This paper proposed a new version of DBSCAN that can automatically customize the parameters. The proposed method consists of two processes: initial parameter estimation based on grid analysis and DBSCAN based on the divide-and-conquer (DC-DBSCAN) approach, which repeatedly performs DBSCAN on each cluster separately and recursively. To verify the proposed method, we applied it to a 3D point cloud dataset that was used to analyze rockfall events at the Puiggcercos cliff, Spain. The total number of data points used in this study was 15,567. The experimental results show that the proposed method is better than the traditional DBSCAN in terms of purity and NMI scores. The purity scores of the proposed method and the traditional DBSCAN method were 96.22% and 91.09%, respectively. The NMI scores of the proposed method and the traditional DBSCAN method are 0.78 and 0.49, respectively. Also, it can detect events that traditional DBSCAN cannot detect.
-  M. Ester, H.-P. Kriegel, J. Sander, and X. Xu, “A density-based algorithm for discovering clusters in large spatial databases with noise,” KDD’96: Proc. of the 2nd Int. Conf. on Knowledge Discovery and Data Mining, pp. 226-231, 1996.
-  E. Schubert, J. Sander, M. Ester, H.-P. Kriegel, and X. Xu, “DBSCAN revisited, revisited: why and how you should (still) use DBSCAN,” ACM Trans. on Database Systems (TODS), Vol.42, No.3, Article 19, pp. 1-21, 2017.
-  A. Abellán, J. Calvet, J. M. Vilaplana, and J. Blanchard, “Detection and spatial prediction of rockfalls by means of terrestrial laser scanner monitoring,” Geomorphology, Vol.119, No.3-4, pp. 162-171, 2010.
-  M. Tonini and A. Abellan, “Rockfall detection from terrestrial LiDAR point clouds: A clustering approach using R,” J. of Spatial Information Science, Vol.2014, No.8, pp. 95-110, 2014.
-  N. Micheletti, M. Tonini, and S. N. Lane, “Geomorphological activity at a rock glacier front detected with a 3D density-based clustering algorithm,” Geomorphology, Vol.278, pp. 287-297, 2017.
-  K. Sheridan, T. G. Puranik, E. Mangortey, O. J. Pinon-Fischer, M. Kirby, and D. N. Mavris, “An Application of DBSCAN Clustering For Flight Anomaly Detection During The Approach Phase,” American Institute of Aeronautics and Astronautics (AIAA) Scitech 2020 Forum, 2020.
-  A. Karami and R. Johansson, “Choosing DBSCAN Parameters Automatically Using Differential Evolution,” Int. J. of Computer Applications, Vol.91, No.7, pp. 1-11, 2014.
-  H. Darong and W. Peng, “Grid-based DBSCAN algorithm with referential parameters,” Physics Procedia, Vol.24, Part B, pp. 1166-1170, 2012.
-  L. McInnes, J. Healy, and S. Astels, “hdbscan: Hierarchical density based clustering,” J. of Open Source Software, Vol.2, No.11, Article 205, 2017.
-  W. Lai, M. Zhou, F. Hu, K. Bian, and Q. Song, “A new DBSCAN parameters determination method based on improved MVO,” IEEE Access, Vol.7, pp. 104085-104095, 2019.
-  A. Abellán, D. Carrea, A. Loye, M. Tonini, M. Jaboyedoff, M. Royan, and A. Pedrazzini, “Understanding precursory rockfalls along cracks,” Geophysical Research Abstracts, Vol.14, EGU2012-6037-1, 2012.
-  K. T. Chau, R. H. C. Wong, J. Liu, and C. F. Lee, “Rockfall hazard analysis for Hong Kong based on rockfall inventory,” Rock Mechanics and Rock Engineering, Vol.36, No.5, pp. 383-408, 2003.
-  “3D Landslide Website,” http://3d-landslide.com/ [accessed May 17, 2021]
-  “CloudCompare Website,” https://www.danielgm.net/cc/ [accessed May 17, 2021]
-  T. O. Kvålseth, “On normalized mutual information: measure derivations and properties,” Entropy, Vol.19, No.11, Article 631, 2017.
-  A. Lancichinetti, S. Fortunato, and J. Kertész, “Detecting the overlapping and hierarchical community structure in complex networks,” New J. of Physics, Vol.11, No.3, Article 033015, 2009.