REDPC: A residual error-based density peak clustering algorithm

• Main Authors: PARMAR, Milan, WANG, Di, ZHANG, Xiaofeng, TAN, Ah-hwee, MIAO, Chunyan, ZHOU, You
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2019
• Subjects: Clustering; Density peak clustering; Anomaly detection; Residual error; Low-density data points; Databases and Information Systems; Software Engineering; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/5185; https://ink.library.smu.edu.sg/context/sis_research/article/6188/viewcontent/NeuCom2018REDPC.pdf
• Institution: Singapore Management University

The density peak clustering (DPC) algorithm was designed to identify arbitrary-shaped clusters by finding density peaks in the underlying dataset. Due to its aptitudes of relatively low computational complexity and a small number of control parameters in use, DPC soon became widely adopted. However, because DPC takes the entire data space into consideration during the computation of local density, which is then used to generate a decision graph for the identification of cluster centroids, DPC may face difficulty in differentiating overlapping clusters and in dealing with low-density data points. In this paper, we propose a residual error-based density peak clustering algorithm named REDPC to better handle datasets comprising various data distribution patterns. Specifically, REDPC adopts the residual error computation to measure the local density within a neighbourhood region. As such, comparing to DPC, our REDPC algorithm provides a better decision graph for the identification of cluster centroids and better handles the low-density data points. Experimental results on both synthetic and real-world datasets show that REDPC performs better than DPC and other algorithms.