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

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.