Unconstrained neighbor selection for minimum reconstruction error-based K-NN classifiers

It is necessary to introduce convincing and effective classifiers for small datasets. K-NN-based classifiers are relatively simple and efficient. In this manuscript, we try to improve their performance and increase the recognition rate. All types of K-NN-based classifiers select a subset of samples as neighbors of the query sample. The selection of neighbors is the unavoidable part of the K-NN based classifiers. Therefore, how to choose neighbors can be pivotal to the performance of the K-NN-based classifiers. Most K-NN-based classifiers select neighbors based on the minimum Euclidean distance. The Euclidean distance-based selection of neighbors is rational for majority voting-based and mean-distance-based K-NN classifiers. However, this scheme of selection of neighbors is not logical for minimum reconstruction error-based K-NN classifiers, which decide about query sample according to the minimum error value. Sometimes, a sample is closer to a query sample than another sample, but it cannot well linearly reconstruct the query sample. It can reduce the performance of the minimum reconstruction error classifiers. On the other hand, a sample may provide minimum reconstruction error, but it is not in proximity to the query sample.

The minimum reconstruction error-based K-NN classifiers typically have the best performance [17]. In this manuscript, I propose a neighbor selection method based on the minimization reconstruction error of the query sample. In the proposed method, a subset of data that minimizes the reconstruction error is assigned as the neighbors of the query sample. Euclidian distance is not considered as a criterion to select the neighbors of the query sample. Also, an \({l}_{0}\)-based sparse representation scheme is introduced for determining the proposed neighbors. The proposed neighbor selection method is applicable for minimum reconstruction error-based classifiers. Three \({l}_{0}\)-MLMNN, \({l}_{0}\)-WRKNN, and \({l}_{0}\)-WLMRKNN classifiers are defined based on the proposed neighbor selection method.

The examples are based on different databases which include University of California Irvine (UCI) machine learning repository [26], UCR time-series classification archive [27], and a small subset of Modified National Institute of Standards and Technology (MNIST) handwritten digit database [28]. The results exhibit the suitable performance of the proposed method.

The rest of the manuscript is organized as follows. The system model and related works are presented in “System model and related works”. Next, the proposed neighbor selection method and proposed K-NN-based classifiers are described. In “Simulation results”, the simulation results and the discussion of the results are given. Finally, “Conclusion” concludes the manuscript.

First, K neighbors of the query sample are determined per class based on the minimum Euclidean distance. Then, K local mean pseudo-neighbors per class are calculated as

Then, the query sample is linearly reconstructed per class using K local mean pseudo-neighbors with a \({l}_{2}\)-norm constraint on reconstruction coefficients (\({{\boldsymbol{\beta}}}^{j}\)) aswhere \(\mu \) is a regularization parameter, \({\overline{{\varvec{X}}} }_{\mathrm{KNN}}^{j}=\left[{\overline{{\varvec{x}}} }_{1{\mathrm{NN}}}^{j}, {\overline{{\varvec{x}}} }_{2{\mathrm{NN}}}^{j},\ldots ,{\overline{{\varvec{x}}} }_{\mathrm{KNN}}^{j}\right]\), and \({{\boldsymbol{\beta}}}^{j}=\left[{\beta }_{1}^{j},{\beta }_{2}^{j},\ldots ,{\beta }_{K}^{j}\right]\) is the reconstruction coefficients vector of the jth class. The optimum \({{\boldsymbol{\beta}}}^{j}\) can be calculated as a closed-form solution

Then, reconstruction errors are computed as

Finally, the query sample is classified into the class with minimum reconstruction error [20].

Similar to MLMNN, first, K neighbors of the query sample are calculated per class. Then, reconstruction coefficients (\({{\boldsymbol{\eta}}}^{j}\)) of the query sample are calculated per class with a constraint on Euclidean distances of K-nearest neighbors (\({{\varvec{X}}}_{\mathrm{KNN}}^{j}\)) aswhere, \(\gamma \) is a regularization parameter, and \({{\varvec{T}}}^{j}\) is a diagonal matrix of Euclidean distances asand \({{\boldsymbol{\eta}}}^{j}\) can be solved in a closed-form per class as

After computing the optimum \({{\boldsymbol{\eta}}}^{j}\) per class, the query sample is classified to the class with minimum reconstruction error, which is calculated as

Most steps of WLMRKNN are similar to WRKNN. WLMRKNN employs local mean pseudo-neighbors (\({\overline{{\varvec{X}}} }_{\mathrm{KNN}}^{j}\), Eq. (1)) instead of nearest neighbors (\({{\varvec{X}}}_{\mathrm{KNN}}^{j}\)). The decision is also made based on the minimum reconstruction error of the query sample versus the pseudo-neighbors per class aswhere \({{\varvec{S}}}^{j}\) is the reconstruction coefficients vector of the jth class [17].

It has been shown that minimum reconstruction-based K-NN classifiers, i.e., WRKNN and WLMRKNN, have the best performance [17].

The proposed method is evaluated on seven datasets of the UCI machine learning repository and five datasets of the UCR time-series classification archive. Characteristics of the employed UCI and UCR datasets are given in Tables 1 and 2, respectively.

Each of the UCI datasets is randomly divided into the training (66.7%) and test (33.3%) subsets. The recognition rates of each UCI dataset are provided in each K by averaging the results for 50 independent iterations. Then, the average of the recognition rate on seven datasets is calculated for K = 1,…,15. Figures 4, 5 and 6 show the mean of the recognition rates on the seven UCI datasets. Also, the standard-deviation values of the accuracy on seven UCI datasets are given for different numbers of the neighbors in Table 3. The standard-deviation values of the proposed classifiers are less than the investigated minimum reconstruction error-based KNN classifiers for most numbers of neighbors. The accuracy and standard-deviation values show that the proposed \({l}_{0}\)-based method almost improves the performance of classifiers on all seven UCI datasets.

UCR includes some time-series datasets. In UCR, the recognition rates are calculated in accordance with the given test and training subsets of each dataset. Then, the average of the recognition rate on five datasets are calculated for K = 1,…, 15. Figures 7, 8 and 9 show the mean recognition rates on five UCR datasets using three common and proposed \({l}_{0}\)-based minimum reconstruction error-based K-NN classifiers. Also, Table 4 shows the standard-deviation values of the accuracy for different numbers of the neighbors on five UCR datasets. The higher recognition rate values and lower standard-deviation values demonstrate that the proposed method improves the performance of the minimum reconstruction error-based K-NN classifiers on all five UCR datasets.

As a consideration, Fig. 5 shows the performance of the \({l}_{0}\)-WRKNN is worse than WRKNN when the number of neighbors is greater than 12. In the WRKNN classifier, the distances among the query sample and neighbors are influential in calculating the coefficients vector; and then on the reconstruction error value (Eqs. 5 and 6). In the proposed \({l}_{0}\)-based neighbor selection method, when the number of neighbors increases, the samples with high Euclidean distances from the query sample can be selected as neighbors, because there is no constraint on the Euclidean distance of the neighbors. Therefore, the neighbors with extremely high Euclidean distances are lower effective in reconstructing the query sample. On the other hand, increasing the number of neighbors provides more freedom to reconstruct the query sample. Consequently, the WRKNN classifier sometimes performs better than the \({l}_{0}\)-WRKNN for higher numbers of neighbors. However, the WLMRKNN classifier is similar to WRKNN. However, in WLMRKNN, the local mean-based neighbors (Eq. 1) have been used to reconstruct the query sample. The Euclidean distances of the local mean-based neighbors are not very high because of the mean operation on the pre-selected neighbors. Thus, increasing the number of neighbors does not reduce the performance of the \({l}_{0}\)-WLMRKNN (Figs. 6 and 9).

In addition, McNemar’s statistical test is used to compare the proposed \({l}_{0}\)-based classifiers and the mentioned minimum reconstruction error-based K-NN classifiers. McNemar’s test is a statistical method to compare the performance of two classifiers on the same test set. Suppose there are two classifiers: classifier A and classifier B. In McNemar’s test, the null hypothesis is defined as A and B classifiers having the same error rate (i.e., \({n}_{01}={n}_{10}\)). Thus, the alternative hypothesis is that the performances of the classifiers are not the same. The below parameters are considered for either A and B classifiers:

Then, \({\chi }^{2}\) statistic value is computed as \({\chi }^{2}={\left({n}_{01}-{n}_{10}\right)}^{2}/\left({n}_{01}+{n}_{10}\right)\). \({\chi }^{2}\) is a chi-squared distribution with one degree of freedom. For a significance threshold of 0.05, i.e., p-value = 0.0.5, if the \({\chi }^{2}\) statistic value is greater than 3.48, the null hypothesis is rejected, and there is a significant difference between the A and B classifiers. In the following, the results of McNemar’s test (\({\chi }^{2}\) statistic value) on five UCR datasets are given for different numbers of the neighbors in Table 5.

The results demonstrate that there is a significant difference; and the recognition rate values (Figs. 7, 8 and 9) show the superiority of the proposed \({l}_{0}\)-based classifiers, especially \({l}_{0}\)-WLMRKNN, at most numbers of neighbors on most investigated UCR datasets. Of course, it should be noted that the results of McNemar’s test have not been provided on UCI datasets, because, in the evaluated experiments, the recognition rates of each UCI dataset are provided in each K by averaging the results for 50 independent iterations. Also, each UCI dataset is randomly divided into the training and test subsets in each iteration.

In this manuscript, a small subset of MNIST is used to evaluate the proposed method. MNIST database includes 60,000 train and 10,000 test samples of English handwritten digit images [28]. A training subset with 10,000 samples and a test subset with 5000 samples are used in our experiments. The train and test subsets are randomly selected from the train and test samples, respectively. The recognition rates using \({l}_{0}\)-MLMNN, \({l}_{0}\)-WRKNN, and \({l}_{0}\)-WLMRKNN classifiers are given in Figs. 10, 11 and 12, respectively. The results demonstrate that the proposed method improves the performance of all three reconstruction error-based KNN classifiers. Also, the results of the McNemar statistical test on the MNIST dataset are given for different numbers of the neighbors in Table 6. The results demonstrate that there is a significant difference between the investigated paired classifiers, especially for the number of neighbors of less than 9. Again, the recognition rate values show the proposed \({l}_{0}\)-based classifiers, especially \({l}_{0}\)-WLMRKNN, have the best performance.

Figures 10 and 11 show that the proposed method has similar recognition rates to the conventional minimum reconstruction error-based KNN classifiers for large K. The larger numbers of neighbors cause larger samples to be involved in reconstructing the query sample. Therefore, there is more freedom in reconstructing the query sample, and it can cause the performance of the classifiers will be closer to each other. However, the performance is depended on the data distribution and classifier type.

Also, as is inferrable, the proposed \({l}_{0}\)-based neighbor selection method can be more effective on datasets with a small number of samples or datasets with high variability per class. Results on MNIST show that the proposed \({l}_{0}\)-based classifiers and the mentioned minimum reconstruction error-based K-NN classifiers perform the same for the large amount of K when the training subsets include more than 10,000 samples. K-nearest neighbors of the query sample likely make minimum reconstruction error when there are datasets with large amounts of samples per class.

The results on the whole MNIST digit database are evaluated for more investigations in the following. The recognition rate results are given in Figs. 13, 14 and 15. The results are similar to the obtained results on a small subset of MNIST (Figs. 10, 11 and 12) and demonstrate the better performance of the proposed method, especially for the smaller number of neighbors. For the number of neighbors greater than 12, the performance of the WRKNN is better than the \({l}_{0}\)-WRKNN, but \({l}_{0}\)-WLMRKNN and \({l}_{0}\)-MLMNN perform similarly to WLMRKNN and MLMNN, respectively. The reasons have been described in the paragraph above Table 4. Also, in the MLMNN, the same as WLMRKNN, the local mean-based neighbors have been used to reconstruct the query sample. Therefore, the high Euclidean distances of the \({l}_{0}\)-based neighbors do not have any unsuitable effect on calculating and controlling the reconstruction coefficient values (Eq. 2). On the other hand, increasing the number of neighbors provides more freedom to reconstruct a query sample. It can make the performance of the MLMNN similar to \({l}_{0}\)-MLMNN.

Furthermore, the results of the proposed classifiers are compared with the SVM classifier. The results of the recognition rates are given in Table 7. The results demonstrate the better performance of the proposed classifiers than the SVM classifier on UCI, UCR, and MNIST databases. Also, the results of the proposed K-NN-based classifiers are approximately constant for K > 5, which exhibits less sensitivity of them to the initial parameter of the number of neighbors. Generally, the proposed method is a suitable classifier for classifying small datasets.

The minimum reconstruction error-based K-NN classifiers have the best performance among K-NN-based classifiers and are less sensitive to the number of neighbors. Usually, the neighbors are selected based on the minimum Euclidean distance of the data from the query sample. However, different kinds of K-NN-based classifiers make the decision using their specific criteria. Therefore, neighbor selection according to the criterion of the classifier can improve their performance. The proposed \({l}_{0}\)-based neighbor selection method decreases the reconstruction errors of the minimum reconstruction error K-NN-based classifiers and can improve their performance. Figure 16 shows the sum of the reconstruction error values for the query samples according to their category samples on the Chlorine Concentration dataset of UCR. The minimum reconstruction error values of query samples (i.e., \(r\left({\varvec{y}},{{\varvec{X}}}_{K}\right)={\Vert {\varvec{y}}-{{{\varvec{X}}}_{K}}^{\mathrm{T}}{\boldsymbol{\omega}}\Vert }_{2}^{2}\)) have been calculated using K training samples with the same category of each query sample. The results are provided for K = 2,…, 15 using WRKNN and \({l}_{0}\)-WRKNN classifiers. The Chlorine Concentration dataset includes 3840 query samples, and the number of the categories is 3 (C = 3). The results demonstrate the reconstruction errors are decreased using the proposed neighbor selection method.

The reconstruction error of the query sample, i.e., \(r\left({\varvec{y}},{{\varvec{X}}}_{K}\right)={\Vert {\varvec{y}}-{{{\varvec{X}}}_{K}}^{\mathrm{T}}{\boldsymbol{\omega}}\Vert }_{2}^{2}\), is the decision metric in all reconstruction error-based K-NN classifiers. \({{\varvec{X}}}_{K}\) is the matrix of K selected neighbors, and \({\boldsymbol{\omega}}\) is the reconstruction coefficients vector. \(\frac{\partial r}{\partial {{\varvec{x}}}_{ik}}\) exhibits the contribution of the \({{\varvec{x}}}_{ik}\) in classifying \({\varvec{y}}\). In \({l}_{0}\)-WRKNN, the weighted contribution of each neighbor can be calculated per class aswhere \({{\varvec{x}}}_{i-{l}_{0}}^{j}\) is the ith \({l}_{0}\)-based neighbor from the jth class, and \({\eta }_{i-{l}_{0}}^{j}\) is its corresponding coefficient. Equation (12) expresses behavior similar to WRKNN and shows that neighbors have different contributions in classification, corresponding to their reconstruction coefficients. This conclusion is also correct for \({l}_{0}\)-WLMRKNN and \({l}_{0}\)-MLMNN.

Besides, by deriving r to the reconstruction coefficients, i.e., \(\frac{\partial r}{\partial {w}_{iK}}\), the weighted contribution of the reconstruction coefficients can be evaluated. In \({l}_{0}\)-WRKNN, \(\frac{\partial {r}^{j}}{\partial {\eta }_{i-{l}_{0}}^{j}}\) is calculated as

Equation (13) shows that the weighted contribution of the \({\eta }_{i-{l}_{0}}^{j}\) depends on both the corresponding sample and the reconstruction error value. Because of selecting neighbors based on the minimum reconstruction error, the proposed \({l}_{0}\)-based K-NN classifiers can be less sensitive to the reconstruction coefficients. Generally, Eq. (13) can be applied for evaluating the reconstruction coefficients in every reconstruction error-based K-NN classifier. \(f\left(K,t\right)=\sum_{j=1}^{C}\sum_{i=1}^{K}\left|\frac{\partial {r}_{t}^{j}}{\partial {\eta }_{i}^{j}}\right|\) is introduced for comparing the sensitivity of the minimum reconstruction error-based K-NN classifiers to the reconstruction coefficients. \(\sum_{i=1}^{K}\left|\frac{\partial {r}_{t}^{j}}{\partial {\eta }_{i}^{j}}\right|\) is the summation of K absolute values of \(\frac{\partial {r}_{t}^{j}}{\partial {\eta }_{i}^{j}}\) corresponding K neighbors of the tth query sample. And \(f\left(K,t\right)\) is the summation of c values of \(\sum_{i=1}^{K}\left|\frac{\partial {r}_{t}^{j}}{\partial {\eta }_{i}^{j}}\right|\) corresponding to c categories. \({r}_{t}\) is the reconstruction error of the tth query sample. The smaller \(f\left(.,.\right)\) exhibits less sensitivity of the reconstruction error-based K-NN classifiers to the reconstruction coefficients.

Figure 17 shows \(f\left(5,.\right)\) of the query samples of the Chlorine Concentration dataset of UCR using WRKNN and \({l}_{0}\)-WRKNN. Also, \(\sum_{t=1}^{{N}_{t}}f\left(K,t\right)\) values using WRKNN, \({l}_{0}\)-WRKNN, WLMRKNN, and \({l}_{0}\)-WLMRKNN are given in Fig. 18 for K = 2,…, 15. \({N}_{t}\) is the number of query samples. Figures 17 and 18 demonstrate the proposed minimum reconstruction error-based K-NN classifiers are less sensitive to the reconstruction coefficients.

The minimum reconstruction error-based K-NN classifiers make the decision about a query sample based on the minimum reconstruction error. Generally, the reconstruction error of a sample versus the samples with the same class is less than the reconstruction errors versus the samples with a different class. On the other hand, the neighbors corresponding to Euclidean distance cannot always reconstruct the query sample with minimum error. The proposed \({l}_{0}\)-based neighbor selection method selects K samples from each class that obtain minimum reconstruction error. Therefore, it is more probable that the samples with the same class as the query sample provide the least reconstruction error.