Mutual neighborhood and modified majority voting based KNN classifier for multi-categories classification

In this paper, two techniques for improving the performance of the k-Nearest Neighbors (KNN) based classifiers are proposed: mutual neighborhood (MN) for searching the neighbors of the query sample, and two-stage modified majority voting (MMV) based decision. In MN, two samples are the neighbors of each other, if each of them exists in the k-neighborhood of the other. Selecting the MN-based neighbors depends on the data distribution and makes to select the data with the same category and/or more similarity. Also, the number of neighbors is variable in MN. Moreover, a two-stage method is proposed to improve majority voting based classifiers which we call it modified majority voting. In MMV, if there is any ambiguous, the mean vectors of each category with majority voting are computed and then the decision is made based on the minimum Euclidean distance of the mean vectors from the query sample. By the proposed techniques, some new and extended KNN-based classifiers are defined. Two different kinds of databases are used in our experiments: eight datasets of UCI machine learning repository and fifteen datasets of UCR time series classification archive. The results exhibit the proposed techniques increase the recognition rates of the KNN-based classifies. In some cases, the rate of improvement is more than 10%.