{'fraction_non_alphanumeric': 0.03804416403785489, 'fraction_numerical': 0.012555205047318612, 'mean_word_length': 4.511474269819193, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
k-Relevance Vectors for Pattern Classification

This study combines two different learning paradigms, k-nearest neighbor (k-NN) rule, as memory-based learning paradigm and relevance vector machines (RVM), as statistical learning paradigm. This combination is performed in kernel space and is called k-relevance vector (k-RV). The purpose is to improve the performance of k-NN rule. The proposed model significantly prunes irrelevant attributes. We also introduced a new parameter, responsible for early stopping of iterations in RVM. We show that the new parameter improves the classification accuracy of k-RV. Intensive experiments are conducted on several classification datasets from University of California Irvine (UCI) repository and two real datasets from computer vision domain. The performance of k-RV is highly competitive compared to a few state-of-the-arts in terms of classification accuracy.

to 1, the query data is assigned to the class of the nearest neighbor, i.e. the one has shortest Euclidean distance to the query instance. The complexity of k-NN rule is O(Nl) where N is the total number of training data and l is the size of data columns. This complexity increases if the value of k increases. On the other hand, different values of k may alter the target value of the query instance, and hence, selecting a good value of k is a non-trivial task.
k-NN has been applied to several applications such as medical diagnosis [13][14][15], intrusion detection [16,17], image classification [18][19][20], video multimedia classification and segmentation [5,21,22]. Regardless of the merits of k-NN rule, it has two problems in learning from data. First, k-NN uses distance metric to calculate similarities between instances. k-NN assumes all variables equally contribute to the learning procedure which may lead to poor prediction if some variables are redundant. Additionally, the main patterns in data are contained in just a few variables. In this sense, weight assignment may better increase the accuracy of the nearest neighbor rule [23].
Second, the presence of noise in data may jeopardize the k-NN performance during calculating the similarity between instances [23]. For this problem, one can modify the distance measurement.
Tutz and Ramzan [28] used w-NN for imputation of missing data. The careful selection of distances using weights helped discover more information of the missing values and outperformed competing nearest neighbor methods. The main idea of study in [23] is to refine the distance metric of k-NN based on the Minkowski distance in order to include only a subset of relevant variables.
Experimental results on low-and high-dimensional datasets demonstrate the importance of these modifications. Takeuchi et.al propose an attribute selection and weighting method [25] for improvement of k-NN classifier. With a novel attribute weighting algorithm, the correct target neighbor is obtained, and nearest neighbors are updated through a sequential quadratic programming. This approach gained better performance than traditional k-NN.
In this study, using a simple yet versatile algorithm, the proposed k-RV rule may less suffer from the mentioned problems. We use sparsity to prune irrelevant and noisy attributes [29][30][31]. We borrow the idea of sparse Bayesian learning in RVM and combine it with k-NN. In [32], two drawbacks of extreme learning machine (ELM) [33], i.e. 1) suffering from overfitting problem and 2) sensitivity of the accuracy of ELM to the number of hidden neurons are resolved by relevance vector machine (RVM) [31] as sparse Bayesian learning (SBL) approach. During the learning process, several redundant hidden neurons of ELM are detected and pruned.
Study in [34], also reduces the number of hidden neurons of multivariate polynomial (MP) and reduced polynomial (RP) [35] with the sparsity approach in RVM. The sparsed methods, i.e.
sparse Bayesian RP (SBRP) and sparse Bayesian MP (SBMP) have better classification accuracy (CA) than MP and RP examined on several datasets.
In a similar fashion to [32,34] as the source of inspiration for our study, we also modify the distance metric in k-NN rule through sparse Bayesian learning method used in RVM. The learned sparsed weights obtained by RVM is served as the importance of each attribute for w-NN rule. The non-zero weights are fed into the distance metric of w-NN. And hence this builds up a sparsed w-NN rule, that we called k-relevance vector (k-RV).
Another study that can be also related to our research is a combination of RVM and k-NN for the improvement of RVM. Rismanchian and Rahimian [36] used nearest neighbor rule separately for each test instance to find the neighbors, and then RVM is performed on the neighbors of each test instance. This method is called localized RVM (LRVM) since it locally classifies each test instance with RVM. The purpose was to heal the RVM performance that suffers from the degeneracy of covariance function [37]. In contrast to [36] that uses k-NN to improve RVM, in our research we use sparsity approach in RVM to make a sparsed nearest neighbor rule, called k-

RV.
The contributions and advantages of k-RV are as follows: 1. We link two different learning approaches, k-NN as a memory-based learner and SBL as a statistical method for feature selection. Our combination adds a novel concept of similarity measurement into k-NN, we call k-relevancy, i.e. considering relevancy beside nearness.
2. We introduce a new parameter for early stopping of iterations in RVM. If query instance is far away from the RVs, then RVM may have poor prediction for that query instance [37].
We abort iteration in RVM if the change of (The variable is responsible for pruning train data) between current iteration i and previous iteration i-1 is smaller than a default value. We show that the performance of k-RV is further improved through tuning this parameter. 3. Intensive experiments on a generated toy data and two real-world data chosen from computer vision domain validate the reliability of k-RV comparing with several counterparts.
The remainder of this paper is organized as follows: Section two covers the related works, motivation and contributions. Section three discusses k-NN rule and RVM as preliminaries.
Section four expresses the proposed k-RV rule. Some theoretical points are explained in discussion section. Section six examines experiments conducted on several UCI datasets and two real databases chosen from computer vision domain. Last section pays attention to remarks and concludes this paper.

k-NN and w-NN rules
Assume ( 1 , 1 ), ( 2 , 2 ), … , ( N , N ) be N data points in which is the training input and with D dimensions and is the target value. To find the k nearest neighbors of the query instance , the Euclidean distance is performed as follows: Moreover, the importance of each attribute can be evaluated through weight assignment into Eq.
(1). This method is known as weighting nearest neighbor rule or w-NN. The new equation for w-NN is as follows: for each attribute may change the order of neighbors and may improve the accuracy of k-NN.

Relevance vector machine
Sparse Bayesian learning (SBL) and in particular relevance vector machine (RVM) [38] is a probabilistic formulation to support vector machine (SVM) [39]. To estimate the target vector ∈ ℝ 1× in kernel space, we suppose = T where ∈ ℝ ( +1)×1 is weight vector and ∈ ℝ ( +1)× is design matrix with training instances. For classification task, each training instance ∈ ℝ × with dimension is supposed to be drawn from an independent Bernoulli random variable with probability ( | ) where ∈ ℝ 1× is a target vector. Additionally, one can choose posterior probability ( , | ) as objective function with ∈ ℝ ( +1)×1 as hyperparameter vector. Showing this for training instances with Bernoulli likelihood, where , , and are respectively ℎ column vector of the kernel matrix , the network output and the nonlinear Sigmoid function. A closed form solution cannot be achieved since Sigmoid is a nonlinear function. Hence, according to [38], iterative Mackay procedure [40] is necessary to get the marginal likelihood.
To solve the posterior probability ( , | ) in an easy way, its decomposed part, i.e.
(5) and Eq. (6). This is an iterative algorithm and the parameters in Eq. (5), (6), and (7) should be repeated till to reach a stopping criterion. Since has inverse relationship to w, many 's tend to infinity and hence the corresponding 's tend to zero. Simply, pruning elements from vectors w, and the corresponding basis vectors from H yields sparsity.

Overview
The proposed k-RV is tailored to three main steps, namely, data kernelization with Gaussian and Polynomial kernels, kernel data sparsification with RVM, and final classification with sparsed weights. Fig. 1 shows the flowchart of the proposed k-RV.

k-RV: combination of k-NN and RVM
After kernelizing and pruning kernel matrix H with the sparsity approach in RVM, the sparsed weights w sp and corresponding sparsed kernel matrix H sp are fed into the distance metric in nearest neighbor rule. The distance metric in k-RV is modified as follows: with initialized w and .

End While Classification
For i = 1 : number of test instances 6. Assign the target value for every test instance using majority voting and RVs End For.

Datasets and Setup
Twenty datasets are selected from UCI data repository. To select these datasets, we care about both small size and large size in terms of the number of instances, binary and multi-class classification tasks. The descriptions of datasets are listed in the Table 1. 2. For k-NN based learners, the value for k is in the range {1,2, 3, … , 51}. To report the CA, we use the best value for k to predict the test labels. To find the best value for k, 10 runs of 10-fold cross validation is performed, and the average of CA is taken into consideration. We also examine the learners in this article on two real world data. The first dataset is German Traffic Sign Recognition Benchmark (GTSRB) [4]. The GTSRB images are collected from the roads in Germany during daytime and nighttime and the images have high variations due to the illumination, sunlight exposure, occluded by the obstacles of the roadsides, and rotations. There are in total more than 50,000 images; 39,209 for training and 12,630 for test. The number of classes of signs are 43 with highly unbalanced frequencies. The size of signs in the images has high variations. The second dataset is MNIST handwritten digit recognition database [41] with 70,000 images; 60,000 for training and 12,630 for test, in 10 classes. The images are black and white. The images were centered by calculating the center of mass of the pixels and the size for every image is fixed at 28 × 28. Fig. 2 displays instances for both MNIST and GTSRB data. To convert images to features, to be ready for learning purpose, we extract features with a histogram of Oriented Gradient (HOG) feature descriptor proposed by Dalal and Triggs at [42].
Cell size of HOG is set to 5 × 5. Every four cells construct a block and we consider 50% overlapping between blocks. The number of bins is set to 8. With these values assigned to HOG parameters, the total feature size is 1568.

Results on UCI Data
Tables 2 and 3 tabulate the average CA of all learners including the proposed k-RV on 20 UCI datasets with Gaussian and polynomial kernels respectively.   Tables 2 and 3, k-RV is very competitive compared to other counterparts for both Gaussian and polynomial kernels. The second best winner is RVM-Bern.

Following the results in
The proposed k-RV is also a clear winner compared to ker-NN. k-RV outperforms ker-NN on several UCI datasets, with 4% gap in average CA for Gaussian kernel and 1.7% gap in for polynomial kernel. This implies that sparsity plays an important role in data classification with nearest neighbor rules.
Tables 4 and 5 display the optimal number of RVs (# RV), the optimal width, the optimal ∆ (delta) and the number of relevant attributes (#used) for Gaussian and polynomial kernels respectively. The main point to be mentioned, for all datasets, at least 95% of training vectors (#used) are pruned by k-RV while the performance of k-RV is still better than ker-NN.    The k-RV and ker-NN models were run 10 times with 10-fold cross validation. Given 100 values of CAs, a statistical significance between k-RV and ker-NN based on a 95% confidence paired-t test is shown in Table 6. The hypothesis S with value '1' rejects the null hypothesis that the means of compared methods are equal, '0' otherwise. Referring to Table 6, the last column, the proposed k-RV is statistically significant compared to ker-NN on 10 out of 20 UCI datasets. Table 7 and Table 8 tabulate the performance of learners on two real-world datasets, GTSRB and MNIST, with Gaussian and polynomial kernels respectively. Boldface indicates the highest accuracy among classifiers under same conditions. RVM requires the inversion of covariance matrix that is timely. The test time of k-RV is better than ker-NN since k-RV uses sparsed weights and attributes to classify test instances while ker-NN is a dense learner and uses all weights and attributes.

Discussion
One aspect of our modelling to be mentioned is, RVM has poor predictions for those query instances are far away from the RVs. In [37], the source of problem is attributed to the degeneracy of covariance function. Intuitively, the fewer RVs, more probably the lower is the performance.
Thus, the early stopping of RVM helps to have more RVs, hence better performance. we adjust the ∆ and width of Gaussian kernel of basis functions to resolve the issue of the degeneracy of covariance function in RVM. Fig. 10 displays the plot of RVM application on Ripley's synthetic data. As it can be seen, adjustment of ∆ generates more RVs. Distance is an important feature of our k-RV for accurate estimation of the target value and with generating more RVs, the input space has adjacent RVs for every query instance. To verify the effectiveness of the new parameter ∆ , we also compare RVM-Gauss when is fixed with RVM-Gauss when is adjusted (RVM + -GK). Table 9 shows this comparison. Referring to table 9, RVM + -Gauss has better CA than RVM-Gauss on most datasets. To justify this better performance, we observe that the number of RV + s is greater than the number of RVs for every dataset. This implies that the traditional RVM prunes the datasets excessively, resulting in the degeneracy of covariance function [37]. The degeneracy means that the rank of the kernel matrix is equal to the number of RVs. Thus, the matrix is very low rank and ill-conditioned.
The new parameter ∆ , plays as a role of early stopping. This parameter does not allow RVM to prune data undesirably. Hence, more RVs are preserved and the rank increases. Fig. 5 also shows how adjusting the new parameter ∆ generates more RVs.

Conclusion
In this study, we linked two different learning approaches, memory-based learning and statistical learning. We showed that only very few relevant attributes and their corresponding weights are enough to improve the classification accuracy of the k-NN. Experiments conducted on several datasets with two different types of kernel showed the advantage of the proposed k-RV over a few state-of-the-arts. The new parameter that controls the stopping condition of RVM helped to produce more RVs and heal the degeneracy of covariance function in RVM. Thus, higher classification accuracy obtained by k-RV. Future research direction is conducted on improving the speed of the proposed algorithm with graphical processing unit (GPU) since k-RV has slow training time.

Author Contribution
Peyman Hosseinzadeh Kassani and Sara Hosseinzadeh Kassani are co-first authors and contributed equally to this work.