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.

Keywords

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

1. Introduction

The $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 [1]. Despite its longevity, it has been successful, received great praise and is still the subject of ongoing research, such as image processing, bioinformatics, biomedicine, financial risk control, natural language processing [2, 3, 4, 5]. The low efficiency in both running time and memory usage is a great challenge in the KNN classifier. This is because the KNN classifier does not generate a classification model from training data, but considers the most common label among its $k$ -nearest neighbors of the training data by computing a distance matrix.

The Prototype Selection (PS) technique [6] is one of the main solutions for the above shortcomings of the KNN classifier. The prototype selection technique is a special case of data preprocessing. It can reduce the size of the training set by removing noise and redundant samples while keeping the classification accuracy. Hence, the prototype selection technique is usually regarded as a multi-objective optimization problem by weighing the classification accuracy (accuracy) and the reduction rate ( $R$ ). Formally, let ${\bm{X}}$ denote the training set. The prototype selection technique seeks for a reduced set ${\bm{S}}\in{\bm{X}}$ . The accuracy obtained with ${\bm{S}}$ may be lower than or equal to that obtained with ${\bm{X}}$ . However, the number of samples is greatly reduced in ${\bm{S}}$ , which reduces the computational cost.

Condensing methods [7] and edition methods [8] are two typical representatives of prototype selection techniques. Condensing methods aim to search the minimal consistent subset by finding representatives. CNN (Condensing Nearest Neighbor) [7], Generalized Condensed Nearest Neighbor (GCNN) [9] and Multiedit CNN [10] are classical condensing methods. Edition methods intend to handle harmful samples, such as noise, outliers and borderline samples. ENN (Edited Nearest Neighbors) [8], NCNEdit (Nearest Centroid Neighbor Edition) [11] and ENaN (Edited Natural neighbor) [12] are instances of edition methods. Condensing methods can achieve a high reduction rate and rarely change the classification accuracy. By contrast, edition methods tend to improve the classification accuracy rather than the reduction rate.

Recently, hybrid prototype selection techniques combining condensing methods with edition methods have been developed and studied widely. Hybrid prototype selection techniques usually employ edition methods to delete noise and smooth the class boundary. Then, they use condensing methods to reduce the number of training samples dramatically. Representative examples are HMN-based IS (Hit Miss Networks-based Instance Selection) [13], CBP (Class Boundary Preserving Algorithm) [14], 1-FN [15], 1-EN [15], ISR (InstanceRank) [16], IRB (InstanceRank based on Borders) [17], BNNT (Binary Nearest Neighbor Tree) [18], ATISA (Adaptive Threshold-based Instance Selection Algorithm) [19], LSIR (Local Sets-based Instance Reduction) [20], MTRKNN (Modified Template Reduction for KNN) [12], NNGIR (Natural Neighborhood Graph-based Instance Reduction) [21], CNNIR (Constraint Nearest Neighbor for Instance Reduction) [22], LSNaNIR ( local Sets with Natural Neighbors for Instance Reduction) [23], etc. Although extensive empirical results have proved their effectiveness, they still have the following technical defects:

(a)
Adopted edition methods (e.g. ENN, ENaN and so on) in most hybrid prototype selection techniques (e.g. CBP, ISR, IRB, ATISA, MTKNN, NNGIR and CNNIR) are based on the majority voting and the local neighborhood of the tested sample. They are susceptible to harmful samples (noise and unsafe borderline samples) around the tested sample, when $k$ nearest neighbors of the tested sample contain harmful samples and an inappropriate value of $k$ is chosen. Take ENN with $k=$ 3 as an example in Fig. 1 with class 1 (circles) and class 2 (heptagons). Sample A and Sample D are noise because they are closer to other classes and away from samples of the same class as them. Sample B is an unsafe borderline sample of class 1. The $k$ nearest neighbors ( $k=$ 3) of sample A are samples B-D. Sample A is misjudged as normal samples by ENN ( $k=$ 3) because of considering harmful samples B and D around sample A in Fig. 1.

Figure 1.
Illustrating the drawbacks of edition methods in existing hybrid prototype selection techniques.

(b)
Most of them (e.g. HMN-based IS, 1-FN, 1-EN, BNNT, ATISA, LSIR, NNGIR and CNNIR, LSNaNIR) retain many internal samples, which contributes little to the classification of KNN classifier and (or) leads to the low reduction rate. Hence, they are hard to achieve both high accuracy and high reduction. In fact, Borderline samples actually play a decisive role in the classification accuracy of the KNN classifier.
(c)
Many methods rely on many parameters. CBP requires 3 parameters ( $k$ , $k_{R}$ , $\tau$ ). IRB requires 4 parameters (high, medium, low and $k$ ). ISR requires 2 parameters ( $k$ and $d$ ). BNNT requires 2 parameters (tree_level and $k$ ).

In order to solve the above technical defects and overcome the shortcomings of KNN classifiers, a hybrid prototype selection technique based on relative density and density peaks clustering (named PST-RD-DPC) is proposed. First, a new edition method based on relative density and distance (named EMRDD) is proposed to filter out harmful samples and smooth the class boundary. Second, a new condensing method based on relative density and density peaks clustering [24] (named CMRDDPC) is proposed to retain representative borderline samples. After that, the reduced training set is used to train the KNN classifier to achieve classification tasks. The main contributions are highlighted as follows:

(a)
A hybrid prototype selection technique based on relative density and density peaks clustering (PST-RD-DP) is proposed against the technical defects of existing hybrid prototype selection techniques and shortcomings of KNN classifiers.
(b)
A new edition method based on relative density and distance (EMRDD) is proposed. Compared to existing edition methods [8, 11, 12], EMRDD can alleviate the negative effect of harmful samples around test samples.
(c)
A new condensing method based on relative density and density peaks clustering (CMRDDPC) is proposed. Compared to existing condensing methods [7, 9, 10], CMRDDPC retains more representative borderline samples and is parameter-free.

The rest of our work is structured as follows. Related prototype selection techniques are reviewed in Section 2. The main ideas and algorithm process of PST-RD-DP are introduced in Section 3. Intensive experiments and experimental settings are shown in Section 4. Finally, conclusions are summarized and arrangements are made in Section 5.
2. Related work

The KNN classifier [1] is one of the most well-known instance-based supervised non-parametric classifications. However, it is sensitive to noise and has a large computational complexity and long response times. Prototype selection techniques have been postulated as a good solution. Scholars usually divide prototype selection techniques into three categories, i.e., condensing methods, edition methods and hybrid methods.

Condensing methods intend to search the minimal consistent subset by finding representatives. CNN [7] is one of the most classical condensing methods. CNN continuously adds a new sample whose nearest neighbor does not match in label with itself into the condensing set until all members have been absorbed. GCNN [9] and Multiedit CNN [10] are extensions of CNN. GCNN modifies the absorption criterion of CNN. GCNN checks whether all samples have been strongly absorbed. Multiedit CNN applies Multiedit to overcome the negative impacts of noise.

Edition methods focus on handling harmful samples, such as noise, outliers and borderline samples. ENN [8] is the earliest edition method. NCNEdit [11] and ENaN [12] are two representative improvements of ENN. ENN filter outs a harmful sample, when the harmful sample is misclassified by its $k$ nearest neighbors. NCNEdit modifies ENN by applying $k$ nearest centroid neighbor to find noisy samples. ENaN applies natural neighbors to find outliers and noisy samples misclassified by their natural neighbors.

Hybrid prototype selection techniques combine condensing methods with edition methods. HMN-based IS [13] is a hit miss network (HMN)-based hybrid prototype selection technique. In HMN-based IS, a HMN-based edition method (HMN-E) is proposed to handle noise and a HMN-based condensing method (HMN-C) is proposed to remove samples without affecting the accuracy of 1-NN classifier. CBP [14] is a multi-stage hybrid prototype selection technique. CBP employs ENN to prune noise and harmful borderline samples. Then, it uses the geometric characteristics of the underlying distribution to retain borderline samples. 1-FN [15], 1-EN [15], ISR [16] and IRB [17] are rank-based hybrid prototype selection techniques. 1-FN and 1-EN employ the voting strategy with a threshold to edit and condense the training set. The farther neighbors receive votes from considered samples in 1-FN while the neighbors near their enemies receive votes from considered samples in 1-EN. ISR is inspired by PageRank. It uses the idea of PageRank to compute the rank value of each sample. IRB employs the similarity between each sample and its $k$ nearest enemies to calculate the rank value. ISR and IRB employ ENN to prune training samples at the first step. BNNT [18] is the binary nearest neighbor tree-based hybrid prototype selection technique. BNNT uses ENN to deal with noise. Then, it uses the binary nearest neighbor tree to iteratively condense borderline and internal samples. ATISA [19] also uses ENN to filter out noise. Then, it calculates the adaptive threshold for each sample. Next, the adaptive threshold is used to condense the training set. LSIR [20] is based on local sets with enemy neighbors. LSIR uses local sets to edit noise, find borderline samples and condense internal samples. MTRKNN [12] is a distance-based hybrid prototype selection technique. MTRKNN employs ENaN to edit harmful samples. Then, a nearest neighbor-based chain is used to condense internal samples and retain borderline samples. NNGIR [21] is based on the natural neighborhood graph. NNGIR uses edges and vertexes of the natural neighborhood graph to select representative prototypes in the training set. CNNIR [22] is a recent distance-based hybrid method and uses the so-called constraint nearestneighbor chain to find edited border samples and core samples. LSNaNIR [23] is an advanced hybrid prototype selection technique based on local sets with natural neighbors. In LSNaNIR, a local sets-based edition method, a local sets-based and clustering-based condensing method are proposed.

The above hybrid prototype selection techniques have been proven to be effective in weighing the classification accuracy and the reduction rate. Yet, they still have the following technical drawbacks (as analyzed in Section 1): (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 leading to the low reduction; (c) they rely on many parameters. Hence, a novel competitive hybrid prototype selection technique based on relative density and density peaks clustering (PST-RD-DP) is proposed against the above issues.

3. Proposed hybrid prototype selection technique

Let ${\bm{X}}=\{{\bm{x}}_{1},{\bm{x}}_{2},\ldots,{\bm{x}}_{n}\}$ be the training set with $n$ samples. ${\bm{x}}_{i}=\{{\bm{x}}_{i,1},{\bm{x}}_{i,2},\ldots,{\bm{x}}_{i,d}\}$ is the $i$ th sample with $d$ attributes. ${\bm{Y}}=\{y_{1},y_{2},\ldots,y_{m}\}$ is the set of the class label in the training set with $m$ classes. $y_{i}$ is the class label of ${\bm{x}}_{i}$ . The prototype selection technique seeks for a reduced set ${\bm{S}}\in{\bm{X}}$ .

A flowchart of the proposed PST-RD-DP is shown in Fig. 2, which provides an overview. First, the proposed edition method based on relative density and distance (name EMRDD) is used to prune noise and smooth the class boundary. Hence, a training set without noise can be obtained. Second, the proposed condensing method based on relative density and density peaks clustering (CMRDDPC) is used to find the reduced set from the training set without noise. The reduced set contains representative borderline samples. After that, the reduced set is used to achieve the classification task of the KNN classifier.

Figure 2.

Flowchart of PST-RD-DP.

In the following, the proposed edition method based on relative density (EMRDD) is introduced in Section 3.1. The proposed condensing method based on relative density and density peaks clustering (EMRDDPC) is introduced in Section 3.2. The pseudo-code and analysis of PST-RD-DP are described in Section 3.3.

3.1 Edtion method based on relative density

Most existing hybrid prototype selection techniques use edition methods (e.g. ENN, ENaN and so on) based on the local neighborhood with the majority voting to prune harmful samples. However, these edition methods are susceptible to harmful samples around the tested sample, as analyzed in Section 1. Hence, a new edition method based on relative density and distance (EMRDD) is proposed in PST-RD-DP. The proposed EMRDD is inspired by two characteristics of noise, shown in Fig. 3. There are two different classes of samples in Fig. 3. Circles are class 1 and heptagons are class 2. Samples A and D are noise because they belong to class 1 and are surrounded by samples of class 2.

Figure 3.

Describing two characteristics of noise.

Characteristic One: the density between noise and its homogeneous $k$ nearest neighbors is lower than that between the noise and its heterogeneous $k$ nearest neighbors. Note that the homogeneous or heterogeneous $k$ nearest neighbors of sample ${\bm{x}}_{i}$ are the $k$ nearest neighbors which have the same class label as or have a different class from sample ${\bm{x}}_{i}$ , respectively. In Fig. 3a, heterogeneous $k$ nearest neighbors with $k=$ 3 of sample A are samples C, G, and F. The homogeneous $k$ nearest neighbors with $k=$ 3 of sample A in are samples B, D, and E. Obviously in Fig. 3a, the density (Den ${}_{1}$ ) between sample A (i.e., noise) and its homogeneous $k$ nearest neighbors is lower than that (Den ${}_{2}$ ) between sample A and its heterogeneous $k$ nearest neighbors. The above characteristic is formulated in Eq. (1).

$\displaystyle\textit{RelativeDensity}({\bm{x}}_{i})=\frac{k/\sum_{{\bm{x}}_{j}% \in\textit{Heter\_NN}_{k}({\bm{x}}_{i})}\textit{Dist}({\bm{x}}_{i},{\bm{x}}_{j% })}{k/\sum_{{\bm{x}}_{j}\in\textit{Hom\_NN}_{k}({\bm{x}}_{i})}\textit{Dist}({% \bm{x}}_{i},{\bm{x}}_{j})}=\frac{\sum_{{\bm{x}}_{j}\in\textit{Hom\_NN}_{k}({% \bm{x}}_{i})}\textit{Dist}({\bm{x}}_{i},{\bm{x}}_{j})}{\sum_{{\bm{x}}_{j}\in% \textit{Heter\_NN}_{k}({\bm{x}}_{i})}\textit{Dist}({\bm{x}}_{i},{\bm{x}}_{j})}$ (1)

In Eq. (1), Heter_NN ${}_{k}$ ( ${\bm{x}}_{i}$ ) or Hom_NN ${}_{k}$ ( ${\bm{x}}_{i}$ ) is heterogeneous or homogeneous $k$ nearest neighbors of sample ${\bm{x}}_{i}$ , respectively. Dist( ${\bm{x}}_{i}$ , ${\bm{x}}_{j}$ ) is the Euclidean distance between sample ${\bm{x}}_{i}$ and sample ${\bm{x}}_{j}$ . RelativeDensity( ${\bm{x}}_{i})$ is the relative density of sample ${\bm{x}}_{i}$ . RelativeDensity( ${\bm{x}}_{i}$ ) is the density between ${\bm{x}}_{i}$ and its Heter_NN ${}_{k}$ ( ${\bm{x}}_{i}$ ) divided by the density between ${\bm{x}}_{i}$ and Hom_NN ${}_{k}$ ( ${\bm{x}}_{i}$ ). Observing Eq. (1), if sample ${\bm{x}}_{i}$ has a larger RelativeDensity( ${\bm{x}}_{i}$ ), sample ${\bm{x}}_{i}$ is closer to other classes. Especially, if RelativeDensity( ${\bm{x}}_{i}$ ) is larger than 1, sample ${\bm{x}}_{i}$ is likely to be noise because the distance between sample ${\bm{x}}_{i}$ and its Hom_NN ${}_{k}$ ( ${\bm{x}}_{i}$ ) is larger than that between ${\bm{x}}_{i}$ and Heter_NN ${}_{k}$ ( ${\bm{x}}_{i}$ ). When RelativeDensity( ${\bm{x}}_{i}$ ) is between 0 and 1, the larger RelativeDensity( ${\bm{x}}_{i}$ ) indicates that sample ${\bm{x}}_{i}$ is closer to the class boundary.

Characteristic Two: the distance between noise and the class center with the same class label as the noise is greater than the distance between the noise and the class center with a different class from the noise. In Fig. 3 (b), P1 and P2 are the class centers of class 1 and class 2, respectively. Noisy sample A is close to P2 and away from P1. The above characteristic is formulated in Eq. (2).

$\displaystyle\textit{RelativeDistance}({\bm{x}}_{i})=\frac{\textit{Dist}({\bm{% x}}_{i},{\bm{P}}_{\textit{same}})}{\textit{Dist}({\bm{x}}_{i},{\bm{P}}_{% \textit{different}})}$ (2)

Let ${\bm{P}}=\{{\bm{P}}_{1},{\bm{P}}_{2},\ldots,{\bm{P}}_{m}\}$ be the set of centers from different classes. ${\bm{P}}_{\textit{same}}$ is the class center that has the same class label as sample ${\bm{x}}_{i}$ .

$\displaystyle{\bm{P}}_{\textit{same}}=\{{\bm{P}}_{j}\in{\bm{P}}|l({\bm{P}}_{j}% )=l({\bm{x}}_{i})\}$ (3)

In Eq. (3), the function $l({\bm{x}}_{i})$ or $l({\bm{P}}_{j})$ returns the class label of sample ${\bm{x}}_{i}$ or ${\bm{P}}_{j}$ . ${\bm{P}}_{\textit{different}}$ is the class center which has a different class label from sample ${\bm{x}}_{i}$ . When there are more than two classes in the training set, ${\bm{P}}_{\textit{different}}$ is the class center which has a different class label from sample ${\bm{x}}_{i}$ and is closest to sample ${\bm{x}}_{i}$ .

$\displaystyle{\bm{P}}_{\textit{different}}=\mathop{\arg\min}\limits_{{\bm{P}}_% {j}\in\{{\bm{P}}_{h}|l({\bm{P}}_{h})\neq l({\bm{x}}_{i})\}}(\textit{Dist}({\bm% {x}}_{i},{\bm{P}}_{j}))$ (4)

RelativeDistance( ${\bm{x}}_{i}$ ) is the relative distance of sample ${\bm{x}}_{i}$ . RelativeDistance( ${\bm{x}}_{i}$ ) is the distance between ${\bm{x}}_{i}$ and its ${\bm{P}}_{\textit{same}}$ divided by the distance between sample ${\bm{x}}_{i}$ and its ${\bm{P}}_{\textit{different}}$ . If RelativeDistance( ${\bm{x}}_{i}$ ) is larger than 1, sample ${\bm{x}}_{i}$ is likely to be noise because sample ${\bm{x}}_{i}$ is closer to the center of other classes. Based on Eqs (1)–(4), the noise is described in Eq. (5).

$\displaystyle{\bm{x}}_{i}\in\textit{noise}\to\textit{RelativeDensity}({\bm{x}}% _{i})>1\ \text{or}\ \textit{RelativeDistance}({\bm{x}}_{i})>1$ (5)

If sample ${\bm{x}}_{i}$ is noise, RelativeDensity( ${\bm{x}}_{i}$ ) is larger than 1 or RelativeDistance( ${\bm{x}}_{i}$ ) is larger than 1.

Algorithm 1: Edtion method based on relative density and distance (EMRDD)
Input: ${\bm{X}}$ (The training set), $k$ (the parameter of neighbors)		Time complexity
Output:EditedX (The training set without noise)
1	Noise $=\emptyset$ ;	$O$ (1)
2	Calculating the center for each class ${\bm{P}}=\{{\bm{P}}_{1},{\bm{P}}_{2},\ldots,{\bm{P}}_{m}\}$	$O(n\times m)$
3	for each sample ${\bm{x}}_{i}\in{\bm{X}}$	$O(n)$
4	Using the kd-tree to search for heterogeneous and homogeneous $k$ nearest neighbors of sample ${\bm{x}}_{i}$ ;	$O(n\times\textit{logn})$
5	Calculating RelativeDensity( ${\bm{x}}_{i})$ by Eq. (1);	$O(n)$
6	Finding ${\bm{P}}_{\textit{same}}$ and ${\bm{P}}_{\textit{different}}$ by Eqs (3) and (4);	$O(n\times m)$
7	Calculating RelativeDistance( ${\bm{x}}_{i}$ ) by Eq. (2);	$O(n)$
8	if sample ${\bm{x}}_{i}$ satisfies Eq. (5)	$O(n)$
9	Noise $=$ Noise $\cup\{{\bm{x}}_{i}\}$ ;	$O(n)$
10	end
11	end
12	EditedX $=$ X-Noise;	$O$ (1)
13	return EditedX;

The pseudo-code of the proposed EMRDD is described in Algorithm 1. At Line 2, the center for each class is calculated. The heterogeneous and homogeneous $k$ nearest neighbors of each sample is searched by the kd-tree [25] at Line 4. Then, the relative density and distance are calculated at Lines 5–7. Next, each sample is determined whether it is noise by Eq. (5) at Lines 8–10. After that, the training set without noise denoted as EditedX can be got at Lines 12–13. Please note that in Algorithm 1, several points need to be highlighted.

(a)

$m$ is the number of classes and is usually less than logn. Hence, the time complexity of Algorithm 1 is $O$ (nlogn) because the most time-consuming step is to search for $k$ -nearest neighbors by the kd-tree [25].

(b)

Existing edition methods (ENN, ENaN, and so on) [8, 11, 12] employ the majority voting strategy based on the local neighborhood and are susceptible to harmful samples around the test sample. By contrast, the proposed EMRDD uses the relative density and the relative distance to analyze not only the local distribution but also the global distribution of test samples. Hence, EMRDD is less affected by harmful samples around the test sample. As shown and analyzed in Figs 2 and 3, noisy sample A is misjudged as a normal sample by ENN and noisy sample A is correctly identified by EMRDD.

3.2 Condensing method based on relative density and density peaks clustering

The condensing methods in most existing hybrid prototype selection techniques retain many internal samples, which contributes little to the classification of the KNN classifier and (or) leads to a low reduction rate. Hence, a new condensing method based on relative density and density peaks clustering (CMRDDPC) is proposed in PST-RD-DP.

CMRDDPC is inspired by the characteristic of the relative density: if sample ${\bm{x}}_{i}$ has a larger RelativeDensity( ${\bm{x}}_{i}$ ), sample ${\bm{x}}_{i}$ is closer to the class boundary. Existing rank-based prototype selection techniques [15, 16, 17] use a threshold to select condensed samples. The proposed CMRDDPC uses the density peaks clustering (DPC) [24, 26, 27, 28], rather than a threshold, to adaptively select the condensed subset containing borderline samples. The chief ideas of CMRDDPC are that (a) the DPC is used to divide samples of each class into two sub-clusters according to their relative density; (b) The sub-cluster contains the highest relative density is condensed borderline subset. First, the local density of each sample is calculated by the Eq. (6).

$\displaystyle p({\bm{x}}_{i})=\sum_{j}{\Theta(d_{ij}-dc})$ (6) $\displaystyle\Theta(t)=\left\{\begin{array}[]{cl}1l&{t<0}\\ 0l&{\text{others}}\\ \end{array}\right.$ (7)

The local density of each sample is denoted as $p({\bm{x}}_{i})$ in DPC. $d_{ij}$ is the distance between two different samples in terms of their relative density. $d_{ij}$ is calculated by the Eq. (8).

$\displaystyle d_{ij}=\textit{RelativeDensity}({\bm{x}}_{i})-\textit{% RelativeDensity}({\bm{x}}_{j})$ (8)

In Eq. (8), the distance between two samples is based on their relative density. The dc is a cutoff value and calculated by the Eq. (9).

$\displaystyle dc=\mathop{\max}\limits_{i=1}^{n}\left(\mathop{\min}\limits_{j=1% }^{n}(d_{ij})\right)$ (9)

Then, the DPC calculates the distance $\delta({\bm{x}}_{i})$ of sample ${\bm{x}}_{i}$ by Eq. (10).

$\displaystyle\delta({\bm{x}}_{i})=\left\{\begin{array}[]{ll}\min_{j:p({\bm{x}}% _{i})<p({\bm{x}}_{j})}(d_{ij})&\textit{others}\\ \max_{j}(d_{ij})&\forall{\bm{x}}_{j},p({\bm{x}}_{i})\geqslant p({\bm{x}}_{j})% \\ \end{array}\right.$ (10)

Next, cluster centers are determined by the comprehensive value of the local density $p({\bm{x}}_{i})$ and the distance $\delta({\bm{x}}_{i})$ . The remaining samples are allocated to the nearest samples with a higher local density. Finally, sub-clusters are formed. After that, the condensed subset can be obtained by selecting the sub-clusters containing the highest relative density.end

Algorithm 2: Condensing method based on relative density and density peaks clustering (CMRDDPC)

Input:EditedX (The training set without noise), Relativedensity (The relative density of all samples

in EditedX)

Time complexity

Output:S (The reduced and condensed set)

{\bm{S}}=\emptyset

;

O

(1)

for

k=

1 to

m

O(m)

TempX is the set of samples from the

k

th class.

O(m\times n_{\textit{temp}})

Computing

d_{ij}

for different samples in TempX by Eq. (8);

O(m\times n_{\textit{temp}}^{2})

Calculating dc by

d_{ij}

and Eq. (9);

O(m\times n_{\textit{temp}}^{2})

\forall{\bm{x}}_{i}\in

TempX calculating local density

p({\bm{x}}_{i})

by Eq. (6);

O(m\times n_{\textit{temp}})

\forall{\bm{x}}_{i}\in

TempX calculating distance

\delta({\bm{x}}_{i})

by Eq. (10);

O(m\times n_{\textit{temp}})

\forall{\bm{x}}_{i}\in

TempX (

{\bm{R}}(x_{i})=p({\bm{x}}_{i})\times\delta({\bm{x}}_{i})

;

O(m\times n_{\textit{temp}})

Two cluster centers with top 2 values of

{\bm{R}}

are found;

O(m\times n_{\textit{temp}})

Two sub-clusters are formed in TempX by allocating the remaining samples to the nearest samples with a higher local density;

O(m\times n_{\textit{temp}})

Adding the sub-cluster containing the highest relative density into

{\bm{S}}

;

O(m\times n_{\textit{temp}})

end

return

{\bm{S}}

;

O

(1)

The pseudo-code of the proposed CMRDDPC is described in Algorithm 2. First, samples of each class are found at Lines 2–3. Then, DPC is used to divide samples of each class into two sub-clusters according to the relative density at Lines 4–10. The sub-cluster contains the highest relative density is added into the reduced and condensed set ${\bm{S}}$ at Line 11. Please note that in Algorithm 2, several points need to be highlighted.

Let the number of samples in TempX be $n_{\textit{temp}}\leqslant n.m$ is the number of classes and is usually a constant no greater than 10. Hence, the time complexity of CMRDDPC is similar to $O(n^{2})$ .

The sub-cluster containing the highest relative density is closer to the class boundary because samples with the high relative density and the sample with the highest relative density will be clustered together in DPC. Hence, the sub-cluster containing the highest relative density is retained and regarded as the condensed set.

Compared to existing condensing methods [7, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23], CMRDDPC is parameter-free and retain more borderline sample in the reduced and condensed set. Figs 4–5 visualize that the proposed CMRDDPC can effectively retain borderline samples.

3.3 Pseudo-code and analysis of proposed algorithm

The pseudo-code of the proposed PST-RD-DP is described in Algorithm 3. The proposed edition method EMRDD is first executed at Line 2. Then, the relative density of each sample in the edited training set is calculated again at Line 3. Next, the proposed condensing method CMRDDPC is executed at Line 4.

Algorithm 3: Prototype selection technique based on relative density and density peaks clustering
Input: ${\bm{X}}$ (The training set), $k$ (the parameter of neighbors)		Time complexity
Output: ${\bm{S}}$ (The reduced set)
1	${\bm{S}}=\emptyset$ ;	$O$ (1)
2	EditedX $=$ EMRDD ( ${\bm{X}},k$ );	$O$ (nlogn)
3	Calculating the relative density RelativeDensity of all samples in EditedX;	$O$ (nlogn)
4	${\bm{S}}=$ CMRDDPC (EditedXRelativeDensity );	$O(n^{2})$
5	return ${\bm{S}}$ ;	$O$ (1)

Please note that in Algorithm 3, several points need to be highlighted.

(a)
As analyzed by Algorithm 3, the time complexity of PST-RD-DP is $O(n^{2})$ .
(b)
Many existing hybrid prototype selection techniques [14, 16, 17, 18] require 2 or more than 2 parameters. By contrast, PST-RD-DP only relies on one parameter, i.e., the parameter $k$ .

Figure 4.
Visualizing the process of PST-RD-DP on synthetic data set one.

(c)
PST-RD-DP can effectively remove noise by the proposed EMRDD and retain more borderline samples by the proposed CMRDDPC. Figures 4–5 visualize the process of the proposed PST-RD-DP and prove its effectiveness. Figures 4–5a shows the original distribution of synthetic data sets, where different classes have different colors and shapes. In Figs 4–5b, noise is found by EMRDD and circled by red stars. Then, the training set without noise is obtained in Figs 4–5c. Finally, a condensed and reduced set is got by CMRDDPC in Figs 4–5d.

4. Experiments

4.1 Experimental settings

In order to prove the effectiveness of the proposed PST-RD-DP, real data sets are selected from Kaggle (https://www.kaggle.com/) and UCI (http://mlr.cs.umass.edu/ml/). Adopted real data sets are shown in Table 1. The columns labeled “#Sample”, “#Attributes” and “#Classes” represent the number of samples, the number of attributes and the number of classes, respectively. The column labeled “Areas” indicates the application area of adopted real data sets.

Table 1
Experimental real data sets

ID	Data sets	#Samples	#Attributes	#Classes	Areas
1	Biodegradation	1055	41	2	Gene biology
2	Indian Liver Patient	583	10	2	Medicine
3	Banknote Authentication	1372	4	2	Computer
4	Vertebral Column	310	6	2	Medicine
5	WaveForm	5000	21	3	Physical
6	Website Phishing	1353	9	3	Computer
7	Vowel Recognition	990	13	11	Physical
8	Cardiotocography	2126	22	3	Medicine
9	Optdigits	5620	64	10	Handwritten Image
10	Vehicle	846	18	4	Computer
11	Abalone	4177	8	3	Life
12	Mammographic Masses	961	5	2	Medicine
13	Image Segmentation	2310	19	7	Image
14	Isolet5	1559	617	26	Physical
15	Contraceptive Method Choice	1473	9	3	Life
16	German	1000	24	2	Financial
17	Z Alizadeh Sani	303	55	2	Life
18	Wisconsin Diagnostic Breast Cancer	569	30	2	Medicine
19	Breast Cancer Wisconsin	699	9	2	Medicine
20	Pendigits	10992	16	10	Handwritten Image

Figure 5.

Visualizing the process of PST-RD-DP on synthetic data set two.

Each data set is randomly divided into 5 parts, in which the test set T includes 1 part and the training set X includes 4 parts. All experiments were repeated 5 times. Additionally, the KNN classifier with $k=$ 3 is used as the test classifier because the proposed prototype selection technique aims to improve the KNN classifier. The classification accuracy (Acc) of the KNN classifier with $k=$ 3 and the reduction rate ( $R$ ) are used as evaluation metrics. Acc and $R$ are formulated as follows:

$\displaystyle\textit{Acc}=\frac{|{\bm{T}}_{\textit{correct}}|}{|{\bm{T}}|}% \times 100\%$ (11) $\displaystyle R=\left(1-\frac{|{\bm{S}}|}{|{\bm{X}}|}\right)\times 100\%$ (12)

In Eq. (11), $|{\bm{T}}_{\textit{correct}}|$ is the number of samples predicted correctly by the trained classifier in the test set ${\bm{T}}$ . In Eq. (12), $|{\bm{S}}|$ is the number of samples in the condensed set ${\bm{S}}$ and $|{\bm{X}}|$ is the number of samples in the training set ${\bm{X}}$ .

Table 2

Experimental comparative hybrid prototype selection techniques

ID	Comparative methods	Parameter	Time complexity
1	MTRKNN [12]	$\alpha=$ 1.2	$O(n^{2})$
2	ATISA1 [19]	$k=$ 3	$O(n^{2})$
3	IRB [17]	$k=$ 3, high $=$ 35%, medium $=$ 3%, low $=$ 3%	$O(n^{2})$
4	BNNT [18]	$k=$ 3, tree_level $=n$ /10	$O$ (nlogn)
5	LSIR [20]		$O(n^{2})$
6	NNGIR [21]		$O$ (nlogn)
7	PST-RD-DP	$k=$ 5	$O(n^{2})$

Table 3

Average accuracy of comparative prototype selection techniques in training KNN (%)

Data sets	MTRKNN	ATISA1	IRB	BNNT	LSIR	NNGIR	PST-RD-DP
Biodegradation	76.97	80.09	75.55	72.47	77.82	72.89	83.51
Indian Liver Patient	66.53	70.39	71.67	71.49	72.96	72.54	73.41
Banknote Authentication	98.72	98.18	96.35	95.07	95.80	96.35	97.07
Vertebral Column	79.03	85.48	81.45	74.35	83.06	73.14	84.03
WaveForm	82.60	81.10	81.70	73.35	78.75	80.50	86.50
Website Phishing	87.45	84.50	84.13	71.96	86.35	77.49	88.38
Vowel Recognition	61.36	42.42	48.23	38.97	55.30	35.99	58.02
Cardiotocography	87.47	88.80	87.08	75.80	86.13	83.22	89.12
Optdigits	97.49	97.60	97.39	88.02	97.27	87.60	98.43
Vehicle	58.26	57.08	52.36	51.19	61.42	53.15	59.45
Abalone	54.03	53.51	43.97	43.74	50.12	52.15	51.09
Mammographic Masses	76.56	76.38	67.88	68.11	76.04	69.79	78.13
Image Segmentation	89.25	87.23	80.45	78.86	89.32	82.83	88.93
Isolet5	74.43	71.44	71.98	66.01	75.47	68.77	77.76
Contraceptive Method Choice	51.92	51.93	46.50	43.67	49.43	44.72	54.07
German	69.00	66.67	69.83	64.67	67.67	69.33	70.83
Z Alizadeh Sani	63.75	68.66	70.28	63.36	61.50	69.19	68.18
Wisconsin Diagnostic Breast Cancer	87.35	91.79	92.96	67.49	91.51	86.49	93.84
Breast Cancer Wisconsin	94.74	96.66	96.89	84.79	95.94	76.93	97.13
Pendigits	95.89	98.41	96.09	67.61	96.91	91.52	97.79
Average	76.68	76.31	74.56	68.07	76.41	71.21	78.84
Mean Ranks	4.70	4.80	3.88	1.40	4.20	2.73	6.30
Wining Times	3/20	1/20	1/20	0/20	1/20	0/20	14/20
Wilcoxon	$+$	$+$	$+$	$+$	$+$	$+$	N/A

Adopted comparative hybrid prototype selection techniques are shown in Table 2 . MTRKNN, ATISA1 and LSIR are distance-based hybrid prototype selection techniques. MTRKNN is based on a defined chain structure and ENaN. ATISA1 is based on an adaptive distance threshold and ENN. LSIR uses LSSm to prune noise. Then, LSCo and LSBo are used to condense the training set without noise. BNNT and NNGIR are based on a defined tree structure and a defined graph structure, respectively. BNNT uses ENN to prune noise and NNGIR uses edges and vertexes to filter out noise. The time complexity of MTRKNN, ATISA1, IRB, BNNT, LSIR and NNGIR is $O(n^{2})$ , $O(n^{2})$ , $O(n^{2})$ , $O$ (nlogn), $O(n^{2})$ and $O$ (nlogn), respectively. The proposed PST-RD-DP, compared with IRB and BNNT, relies on fewer parameters. Compared to MTRKNN, ATISA1, IRB, BNNT, LSIR and NNGIR, the edition method in PST-RD-DP is new and is less affected by harmful samples around test samples. Although MTRKNN, ATISA, LSIR, and NNGIR rely on relatively few parameters or are parameter-free, they retain many internal samples, which contributes little to the classification of KNN classifier or (and) leads to the low reduction rate. Compared to other methods (including MTRKNN, ATISA, LSIR, NNGIR, etc), PST-RD-DP retains more borderline samples in the condensed and reduced set. Parameters of all comparative methods in Table 2 are set as their suggestions. In the proposed PST-RD-DP, the parameter $k$ is recommended to be set to 5.

Table 4

Average reduction of comparative prototype selection techniques in training KNN (%)

Data sets	MTRKNN	ATISA1	IRB	BNNT	LSIR	NNGIR	PST-RD-DP
Biodegradation	80.05	74.79	71.23	66.23	71.56	87.97	83.51
Indian Liver Patient	84.78	81.46	76.96	54.99	66.13	92.57	91.28
Banknote Authentication	82.42	96.31	64.89	96.49	96.95	96.08	82.97
Vertebral Column	83.06	76.21	70.77	64.72	76.21	92.94	88.15
WaveForm	59.86	63.74	71.73	54.34	67.90	87.83	89.15
Website Phishing	70.24	86.28	68.95	69.22	79.90	89.15	83.67
Vowel Recognition	49.75	74.87	65.85	87.31	67.74	87.90	86.42
Cardiotocography	83.05	87.32	68.02	81.60	81.83	90.69	86.60
Optdigits	44.28	88.89	65.33	97.73	89.27	90.45	71.08
Vehicle	70.30	77.78	76.90	53.74	60.84	85.58	81.28
Abalone	90.47	80.48	81.59	36.50	58.32	96.03	98.35
Mammographic Masses	84.18	85.00	71.78	61.38	73.47	89.02	85.18
Image Segmentation	69.16	87.21	66.68	95.96	84.00	92.39	79.55
Isolet5	44.07	67.53	72.15	94.12	61.68	86.40	79.75
Contraceptive Method Choice	82.09	79.72	81.98	40.00	56.92	85.88	86.42
German	83.67	79.67	75.88	58.00	61.92	87.33	83.63
Z Alizadeh Sani	93.81	81.57	76.89	51.03	64.50	95.74	96.70
Wisconsin Diagnostic Breast Cancer	95.17	92.90	67.20	87.26	89.09	92.17	85.23
Breast Cancer Wisconsin	93.98	93.09	66.03	85.88	87.87	98.33	92.85
Pendigits	75.59	86.65	65.20	87.25	87.90	87.80	88.45
Average	76.00	82.07	71.30	71.19	74.20	90.61	86.01
Mean Ranks	3.70	4.28	2.35	2.80	3.33	6.30	5.25
Wining Times	0/20	0/20	0/20	3/20	0/20	12/20	5/20
Wilcoxon	$+$	$+$	$+$	$+$	$+$	$\sim$	N/A

Two experiments are conducted to prove the effectiveness of PST-RD-DP. First, PST-RD-DP is compared with 6 hybrid prototype selection techniques on real data sets in terms of average Acc of the KNN classifier and average $R$ . Second, PST-RD-DP is compared with 6 hybrid prototype selection techniques in average running time.

Table 5

Average running time of comparative prototype selection techniques (Seconds)

Data sets	MTRKNN		ATISA1		IRB		BNNT		LSIR		NNGIR		PST-RD-DP
Biodegradation	2	.65	1	.03	0	.64	1	.31	5	.34	0	.44	1	.98
Indian Liver Patient	0	.66	0	.33	0	.17	0	.60	1	.52	0	.12	0	.61
Banknote Authentication	3	.33	1	.24	0	.86	1	.18	5	.21	0	.33	3	.08
Vertebral Column	0	.42	0	.25	0	.12	0	.29	0	.57	0	.13	0	.59
WaveForm	47	.16	21	.84	14	.80	17	.47	120	.63	14	.59	21	.39
Website Phishing	3	.15	1	.42	0	.90	1	.24	6	.42	0	.52	3	.01
Vowel Recognition	2	.16	1	.25	0	.78	0	.34	3	.57	0	.41	1	.88
Cardiotocography	7	.80	2	.54	1	.51	3	.45	18	.57	1	.00	5	.77
Optdigits	103	.14	110	.53	102	.17	25	.55	254	.59	20	.25	36	.59
Vehicle	2	.17	1	.11	0	.61	1	.32	3	.23	0	.33	1	.64
Abalone	6	.18	3	.75	2	.64	11	.40	54	.72	1	.39	7	.36
Mammographic Masses	1	.52	0	.87	0	.41	0	.92	3	.12	0	.28	2	.75
Image Segmentation	14	.65	4	.94	4	.03	1	.98	23	.63	1	.60	4	.00
Isolet5	83	.32	41	.57	37	.41	9	.67	107	.60	18	.13	22	.42
Contraceptive Method Choice	1	.67	1	.12	0	.58	2	.27	8	.47	0	.44	1	.09
German	1	.89	0	.90	0	.40	1	.32	4	.33	0	.35	1	.20
Z Alizadeh Sani	0	.46	0	.19	0	.12	0	.54	0	.90	0	.08	0	.35
Wisconsin Diagnostic Breast Cancer	1	.14	0	.67	0	.37	0	.64	1	.79	0	.14	1	.03
Breast Cancer Wisconsin	1	.38	0	.70	0	.38	0	.66	1	.78	0	.19	0	.83
Pendigits	249	.48	14	.93	132	.25	29	.94	331	.65	24	.64	37	.66
Mean Ranks	5	.60	3	.80	2	.45	3	.50	6	.90	1	.15	4	.60

Figure 6.

Average Acc and average $R$ of comparative methods.

4.2 Experiments on real data sets in accuracy and reduction

The average Acc and average $R$ of comparative methods in training the KNN classifier are shown in Tables 3–4. The row labeled “Average” is the average results of all data set. The row labeled “Mean Rank” is the mean rank of the Friedman test [29]. The row labeled “Winning Times” is the number of times that the comparative method in a given column outperforms others. The row labeled “Wilcoxon” indicates the Wilcoxon rank-sum test [30]. In each row, the highest value is bold.

Observing the row labeled “Average” in Tables 3–4, PST-RD-DP achieves the highest average results of Acc and the second-highest average results of ${\bm{R}}$ . The average results of ${\bm{R}}$ of PST-RD-DP is lower than NNGIR. Yet, the average results of Acc of PST-RD-DP are higher than NNGIR and others. The row labeled “Mean Ranks” indicates the mean ranks of the Friedman test. If a method performs better, it has a higher value of the mean rank. For instance, in the data set Biodegradation of Table 3, the ranks of comparative methods are 4, 6, 3, 1, 5, 2 and 7. The mean ranks are the average value of all data sets in terms of the above ranks. Tables 3–4 shows that PST-RD-DP achieves the highest mean ranks in Acc and the second-highest mean ranks in $R$ . Additionally, observing the row labeled “Winning Times” in Tables 3–4, PST-RD-DP achieves the best average Acc in 14 of 20 data sets and the best average $R$ of 5/20 data sets.

The Wilcoxon rank-sum test is also used to analyze Tables 3–4. In the row labeled “Wilcoxon”, the symbol $+$ or $\sim$ indicates that PST-RD-DP is significantly better than the comparative method in the given column or there is no significant difference between PST-RD-DP and the comparative method in the given column. The row labeled “Wilcoxon” shows that (a) PST-RD-DP is significantly better comparative methods in average Acc of the KNN classifier; (b) there is no significant difference between PST-RD-DP and NNGIR on average $R$ .

The reason why PST-RD-DP can achieve the highest average results of Acc is that PST-RD-DP can retain more borderline samples. Although NNGIR removes more redundant samples than PST-RD-DP, both NNGIR and PST-RD-DP have a relatively high value of $R$ with no significant difference between them. However, NNGIR removes more competitive borderline samples, which is harmful to the classification accuracy of the KNN classifier. Hence, from the perspective of the KNN classifier, PST-RD-DP is superior to NNGIR because (a) PST-RD-DP significantly outperforms NNGIR in average Acc; (b) NNGIR and PST-RD-DP have a relatively high value of $R$ with no significant difference.

Figure 6 shows the average results of Acc and $R$ of all data sets for comparative methods. If an algorithm is better, it is closer to the upper right corner of the coordinate axis in Fig. 6. By weighing $R$ and Acc, PST-RD-DP is obviously better than others because it is closer to the upper right corner of the axis in Fig. 6. In general, Tables 3–4 and Fig. 6 prove that PST-RD-DP is superior to the comparative hybrid prototype selection techniques on extensive real data sets by weighing Acc of the KNN classifier and $R$ .

4.3 Experiments on real data sets in average running time

The time complexity of MTRKNN, ATISA1, IRB, BNNT, LSIR and NNGIR is $O(n^{2})$ , $O(n^{2})$ , $O(n^{2})$ , $O$ (nlogn), $O(n^{2})$ and $O$ (nlogn), respectively. The proposed PST-RD-DP is with time complexity $O(n^{2})$ . The average running time of 5 execution for the comparative prototype selection techniques is shown in Table 5. Likewise, the mean ranks of the Friedman test are also employed to analyze Table 5. If a comparative method runs faster, it has a smaller value of the mean rank.

Observing Table 5, although the average running time of PST-RD-DP is slower than ATISA1, IRB, BNNT and NNGIR on most data sets, the difference in their average running time is not particularly obvious. Additionally, the proposed algorithm consumes less time than MTRKNN and LSIR on almost all data sets. In general, the average running time of the proposed PST-RD-DP is suitable for this field

5. Conclusions

The KNN is a well-known instance-based classifier. It is susceptible to noise and high cost in computing the distance between different samples. Hybrid prototype selection techniques can improve the KNN classifier in the above issues. Yet, they still have the following challenges: (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. In this paper, we present 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. First, a new edition method based on relative density and distance (EMRDD) in PST-RD-DP is proposed to remove harmful samples and smooth the class boundary. Second, a new condensing method based on relative density and density peaks clustering (CMRDDPC) in PST-RD-DP is proposed to retain representative borderline samples. PST-RD-DP is with time complexity $O(n^{2})$ .

We conduct experiments with extensive real data sets and report the performance according to both reduction rate and the classification accuracy of the KNN classifier. The first experiment proves that (a) PST-RD-DP outperforms state-of-the-art hybrid prototype selection techniques in improving the classification accuracy of the KNN classifier; (b) compared with comparative state-of-the-art hybrid prototype selection techniques, PST-RD-DP can achieve the relatively high reduction rate; (c) by weighing reduction rate and classification accuracy, PST-RD-DP achieves both high accuracy and high reduction. Furthermore, the second experiment proves that the average running time of the proposed PST-RD-DP is acceptable and suitable for this field.

As future work we plan to extend the proposed algorithm to more practical applications with a larger data scale. We are also interested in applying the proposed algorithm to other machine learning algorithms, such as recommendation algorithms [31], natural language processing algorithms [32], deep learning algorithms [33].

Footnotes

Funding

The Natural Science Foundation of Chongqing, China (cstc2019jcyj-msxmX0694).

References

Cover

and Hart

, Nearest neighbor pattern classification, IEEE Inf Theory 13(1) (1976), 21–27.

Guo

Han

Zhang

and Bai

, K-Nearest Neighbor combined with guided filter for hyperspectral image classification, Procedia Computer Science 129 (2018), 159–165.

Ning

and Zhao

, dForml(KNN)-PseAAC: Detecting formylation sites from protein sequences using K-nearest neighbor algorithm via Chou’s 5-step rule and pseudo components, Journal of Theoretical Biology 470 (2019), 43–49.

Majid

Ali

Iqbal

and Kausar

, Prediction of human breast and colon cancers from imbalanced data using nearest neighbor and support vector machines, Computer Methods and Programs in Biomedicine 113(3) (2014), 792–808.

Cheng

Chan

and Sheu

, A novel purity-based k nearest neighbors imputation method and its application in financial distress prediction, Engineering Applications of Artificial Intelligence 81 (2019), 283–299.

Rico-Juan

J.R.

Valero-Mas

J.J.

and Calvo-Zaragoza

, Extensions to rank-based prototype selection in k-Nearest Neighbour classification, Applied Soft Computing 85 (2019), 105803. doi: 10.1016/j.asoc.2019.105803.

Hart

, The condensed nearest neighbor rule, IEEE Trans Inf. Theory 14(3) (1968), 515–516.

Wilso

D.L.

, Asymptotic properties of nearest neighbor rules using edited data, IEEE Trans Syst Man Cybern 2(3) (1972), 408–421.

Chou

C.H.

Kou

B.H.

and Fu

, The generalized condensed nearest neighbor rule as a data reduction method. In: Proceedings of the 18th international conference on pattern recognition, IEEE Computer Society, 2006, pp. 556–559.

10.

Ferri

F.J.

Albert

J.V.

and Vidal

, Consideration about sample-size sensitivity of a family of edited nearest-neighbor rules, IEEE Trans Syst Man Cybern 29(4) (1999), 667–672.

11.

Sánchez

Barandela

Marques

Alejo

and Badenas

, Analysis of new techniques to obtain quality training sets, Pattern Recognition Letters 24(7) (2003), 1015–1022.

12.

Yang

Zhu

Huang

and Cheng

, Adaptive edited natural neighbor algorithm, Neurocomputing 230(22) (2017), 427–433.

13.

Marchiori

, Hit miss networks with applications to instance selection, J Mach Learn Res 9 (2008), 997–1017.

14.

Nikolaidis

Goulermas

J.Y.

and Wu

Q.H.

, A class boundary preserving algorithm for data condensation, Pattern Recogn 44(3) (2011), 704–715.

15.

Rico-Juan

J.R.

and Iñesta

J.M.

, New rank methods for reducing the size of the training set using the nearest neighbor rule, Pattern Recognition Letters 33(5) (2012), 654–660.

16.

Vallejo

C.G.

Troyano

J.A.

and Ortega

F.J.

, InstanceRank: bringing order to datasets, Pattern Recogn Letters 31(2) (2010), 131–142.

17.

Hernandezleal

Carrascoochoa

J.A.

MartínezTrinidad

J.F.

and Olveralopez

J.A.

, Instancerank based on borders for instance selection, Pattern Recognition 46(1) (2013), 365–375.

18.

and Wang

, A new fast reduction technique based on binary nearest neighbor tree, Neurocomputing 149(3) (2015), 1647–1657.

19.

Cavalcanti

G.D.C.

Ren

T.I.

and Pereira

C.L.

, ATISA: adaptive threshold-based instance selection algorithm, Expert Systems with Applications 40(17) (2013), 6894–6900.

20.

Leyva

Antonio

and Raúl

, Three new instance selection methods based on local sets: a comparative study with several approaches from a bi-objective perspective, Pattern Recogn 48(4) (2015), 1523–1537.

21.

Yang

Zhu

Huang

Cheng

and Hong

, Natural neighborhood graph-based instance reduction algorithm without parameters, Applied Soft Computing 70 (2018), 279–287.

22.

Yang

Zhu

Huang

Cheng

and Hong

, Constraint nearest neighbor for instance reduction, Soft Computing 23 (2019), 13235–13245.

23.

Zhu

and Wu

, A parameter-free hybrid instance selection algorithm based on local sets with natural neighbors, Applied Intelligence 50 (2020), 1527–1541.

24.

Rodriguez

and Laio

, Clustering by fast search and find of density peaks, Science 344 (2014), 1492–1496.

25.

Bentley

J.L.

, Multidimensional binary search trees used for associative searching Commun, ACM 18(9) (1975), 509–517.

26.

and Jiang

, A Graph Adaptive Density Peaks Clustering algorithm for automatic centroid selection and effective aggregation, Expert Systems with Applications (2022), 116539. doi: 10.1016/j.eswa.2022.116539.

27.

and Jiang

, A Graph Adaptive Density Peaks Clustering algorithm for automatic centroid selection and effective aggregation, Expert Systems with Applications (2022) 116539. doi: 10.1016/j.eswa.2022.116539.

28.

Zhu

M.-X.

X.-J.

Chen

W.-J.

C.-N.

and Shao

Y.-H.

, Local density peaks clustering with small size distance matrix, Procedia Computer Science 199 (2022), 331–338.

29.

Beasley

T.M.

and Zumbo

B.D.

, Comparison of aligned Friedman rank and parametric methods for testing interactions in split-plot designs, Computational Statistics & Data Analysis 42(4) (2003), 569–593.

30.

Demiar

and Schuurmans

, Statistical comparisons of classifiers over multiple data sets, Journal of Machine Learning Research 7(1) (2006), 1–30.

31.

Gutowski

Amghar

Camp

and Chhel

, Gorthaur-EXP3: Bandit-based selection from a portfolio of recommendation algorithms balancing the accuracy-diversity dilemma, Information Sciences 546 (2021), 378–396.

32.

Charemza

Makarova

and Rybiński

, Economic uncertainty and natural language processing; The case of Russia, Economic Analysis and Policy 73 (2022), 546–562.

33.

Duan

Zhou

and Huang

, Privacy-preserving and verifiable deep learning inference based on secret sharing, Neurocomputing (2022). doi: 10.1016/j.neucom.2022.01.061.

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

Abstract

Keywords

1. Introduction

3. Proposed hybrid prototype selection technique

4.1 Experimental settings

Table 1 Experimental real data sets

4.3 Experiments on real data sets in average running time

5. Conclusions

Footnotes

Funding

References

Table 1
Experimental real data sets