Sparse Coefficient-Based ${k}$ -Nearest Neighbor Classification

Abstract

K-nearest neighbor rule (KNN) and sparse representation (SR) are widely used algorithms in pattern classification. In this paper, we propose two new nearest neighbor classification methods, in which the novel weighted voting methods are developed for making classification decisions on the basis of sparse coefficients in the SR. Since the sparse coefficients can well reflect the neighborhood structure of data, we mainly utilize them to design classifier in the proposed methods. One proposed method is called the coefficient-weighted KNN classifier, which adopts sparse coefficients to choose KNNs of a query sample and then uses the coefficients corresponding to the chosen neighbors as their weights for classification. Another new method is the residual-weighted KNN classifier (RWKNN). In the RWKNN, KNNs of a query sample are first determined by sparse coefficients, and then, we design a novel residual-based weighted voting method for the KNN classification. The extensive experiments are carried out on many UCI and KEEL data sets, and the experimental results show that the proposed methods perform well.

Keywords

• K-nearest neighbor rule
• sparse coefficient
• weighted voting
• pattern classification