A prototype selection technique based on relative density and density peaks clustering for k nearest neighbor classification

Article type: Research Article

Authors: Xiang, Lina

Affiliations: School of Intelligent Manufacturing and Information Engineering, Chongqing Jianzhu College, Chongqing 400072, China | E-mail: linali202104@163.com

Correspondence: [*] Corresponding author: School of Intelligent Manufacturing and Information Engineering, Chongqing Jianzhu College, Chongqing 400072, China. E-mail: linali202104@163.com.

Abstract: k-nearest neighbor classifier (KNN) is one of the most famous classification models due to its straightforward implementation and an error bounded by twice the Bayes error. However, it usually degrades because of noise and the high cost in computing the distance between different samples. In this context, hybrid prototype selection techniques have been postulated as a good solution and developed. Yet, they have the following issues: (a) adopted edition methods are susceptible to harmful samples around tested samples; (b) they retain too many internal samples, which contributes little to the classification of KNN classifier and (or) leading to the low reduction; (c) they rely on many parameters. The main contributions of our work are that (a) a novel competitive hybrid prototype selection technique based on relative density and density peaks clustering (PST-RD-DP) are proposed against the above issues at the same time; (b) a new edition method based on relative density and distance (EMRDD) in PST-RD-DP is first proposed to remove harmful samples and smooth the class boundary; (c) a new condensing method based on relative density and density peaks clustering (CMRDDPC) in PST-RD-DP is second proposed to retain representative borderline samples. Intensive experiments prove that PST-RD-DP outperforms 6 popular hybrid prototype selection techniques on extensive real data sets in weighing accuracy and reduction of the KNN classifier. Besides, the running time of PST-RD-DP is also acceptable.

Keywords: Prototype selection, instance reduction, k nearest neighbor, data preprocess, instance-based learning

DOI: 10.3233/IDA-226730

Journal: Intelligent Data Analysis, vol. 27, no. 3, pp. 675-690, 2023