Abstract: The Sparse Representation based Classifier (SRC) is a classical representation method for classification. The solution of SRC is obtained by l1 norm minimization which cannot obtain the closed form solution. Thus, the computational complexity of SRC is a little high. The Collaborative Representation Classifier (CRC) is another classical method for classification. The solution of CRC is obtained by l2 norm minimization, from the l2 norm minimization, it can obtain the closed form solution which makes the computational complexity of CRC is much lower than SRC. Although, CRC is effective for classification, there are also some problems about CRC. Under some conditions, some test samples may be misclassified by CRC. This study proposes a local CRC method which is called KNN-CRC. This method firstly chooses K nearest neighbors of a test sample from all the training samples, then given a test sample, the test sample is represented by these K training samples. The solution of KNN-CRC is obtained by l2 norm minimization and the size of K is much smaller than the total number of all training samples. Thus, the computational complexity of KNN-CRC is much lower than SRC and CRC. Furthermore, the extensive experiments show that the proposed KNN-CRC can obtain very competitive classification results compared with other methods.
INTRODUCTION
With the rapid development of computer network technology and information technology, the research of big data is becoming a hot research field recently. Data mining is very important for handling big data application problems. However, the research of data mining includes many aspects. Classification is one of the most important aspects in the field.
Given some training samples from multiple classes, the aim of classification is to assign class labels to a test sample. Classification has been widely used in many fields such as data mining, computer vision, machine learning, pattern recognition, etc (Chi and Porikli, 2012; Roweis and Saul, 2000; Wright et al., 2009; Zhang et al., 2011). There are many conventional methods for handling classification problems such as Linear SVM, Nearest Subspace Classifier, K Nearest Neighbor, etc. Recently, there has been an increasing interest in the research of representation theory. With the rapid development of l0 and l1 norm minimization algorithms (Chen and Donoho, 1994; Pati et al., 1993), sparse representation has been applied for solving many data mining problems. These sparse representation methods have been studied in many literatures. Sparse Representation based Classifier (SRC) is a classical sparse representation among all the representation methods. The SRC was proposed by Wright et al. (2009) which is an interesting and effective method for handling the pattern classification problems. A test sample is first sparsely represented by all the training samples and then the classifier computes the residual for every class, if the ith residual is the smallest, the SRC method will judge that the test sample belongs to the ith class. The SRC is a classical representation method which boosts the research of representation theory and applications. Based on SRC, many other representation methods are proposed, a lot of application problems such as face recognition, digit recognition, signal processing etc., are also solved by representation methods.
Although, SRC is effective for handling pattern classification problems (Elhamifar and Vidal, 2011, 2012; Fuchs, 2005; Guha and Ward, 2012; Mairal et al., 2009; Saul et al., 2003; Soltanolkotabi et al., 2014; Stojnic et al., 2009; Tropp, 2004; Wright et al., 2010), there are also some problems about SRC (Chi and Porikli, 2012; Zhang et al., 2011). First, the SRC method only looks for the sparsest representation of a test sample, however, the sparsest representation does not mean obtaining the highest right classification rate. Under some conditions, some test samples are misclassified by SRC. Second, the solution of SRC is obtained by l1 norm minimization which cannot obtain the closed form solution. Thus, the computational complexity of SRC is a little high.
In view of the advantages and disadvantages of SRC, some study proposed many other representation methods, Chi and Porikli (2012) proposed a Collaborative Representation Optimized Classifier (CROC). The CROC method combines the advantages of Nearest Subspace Classifier (NSC) and Collaborative Representation Classifier (CRC). Elhamifar and Vidal (2011, 2012) proposed a Block-Sparse representation for face recognition. They casted the classification problem as a structured sparse representation problem, they much emphasized the structured property of training samples. Zhang et al. (2011) argued that not the sparse representation but the usage of collaborative representation is more important for the success of the SRC. They proposed a kind of Collaborative Representation Classifier (CRC) method, by using l2 norm minimization, CRC method can obtain closed form solution. Combined the advantages of KNN and SRC, Zhang and Yang (2010) proposed the KNN-SRC method. First, for every test sample, KNN-SRC chooses the K nearest neighbors form all the training samples then KNN-CRC makes these K nearest neighbors as the training samples. Finally, the classifier computes the residual for every class, if the ith residual is the smallest, the classifier will judge that the test sample belongs to the ith class.
These representation methods are all effective for handling classification problems, however, they all have advantages and disadvantages. For the Block-Sparse representation method, the solution of it is also obtained by l1 norm minimization, the computational complexity of Block-Sparse representation is still a little high. For the CRC method, under some conditions, some test samples are also misclassified by CRC method. For the KNN-SRC method, the solution of KNN-SRC is also obtained by l1 norm minimization, its computational complexity is also a little high. Furthermore, under some conditions, some test samples are also misclassified by KNN-SRC.
The KNN is a conventional method for classification which is familiar to us. And CRC is an another representation method for classification, the solution of CRC is obtained by l2 norm minimization, thus, the computational complexity of CRC is low. In this study, combined the KNN and CRC, a new classification method is proposed, namely KNN-CRC method. This method combines the advantages of KNN and CRC, KNN-CRC firstly chooses the K nearest neighbors for every test sample as the training samples, then the solution of KNN-CRC is obtained by l2 norm minimization, it is a closed form solution and the size of K is much smaller than the total number of all training samples.
Thus, the computational complexity of KNN-CRC is much lower than SRC, KNN-SRC and CRC. Furthermore, the extensive face and digit classification experiments clearly show that the proposed method can obtain very competitive results compared with other methods.
METHODOLGY
Multi-class classification problem: Assume that there are L know classes, for every class, there are ni training samples {bijεRm}nij = 1 in the ith class which formed a matrix as:
Bini [bi1, bi2,...,bini]εRmxni
B is denoted by the collection of all training samples:
B = [B1, B2...bL]
If given a test sample yεRm , the aim of multi-class classification task is to judge the test sample y belongs to which class (Adler et al., 2011; Aharon et al., 2006; Bruckstein et al., 2009; Cheng et al., 2010; Chi and Porikli, 2012; Cotter, 2010; Elad and Aharon, 2006; Wright et al., 2009; Zhang et al., 2011).
K Nearest Neighbors (KNN) classification method: The nearest neighbor classifier was proposed by Hart and Cover for solving the classification problems. It was improved to the K Nearest Neighbors classifier immediately (Zhang and Yang, 2010). Assume that there are K classes, for every class there are ni training samples {bijεRm}nij = 1 in the ith class:
Bi = [bi1, vi2...bini]εRmxni
constitute the training samples of the ith class. Given a test sample y, it is easy to find its nearest neighbors bir in every class. The square of Euclidean distance between y and the ith class is obtained as:
Suppose the distance between y and the ith class is the minimal distance, then the1-NN classifier will identify that the test sample y belongs to the ith class. The 1-NN is a conventional and easy method for classification. The K Nearest Neighbor classification (KNN) method is the improvement of the 1-NN algorithm. First, given a test sample y, the KNN classifier chooses the K nearest neighbors between the test sample and all the training samples. Second, assume that there are ki samples from the ith class, if kj = maxiki(1≤i≤L), the KNN classifier will identify that the test sample y belongs to the jth class. The KNN is also a conventional method for classification. However, the extensive experiments show that under many conditions, the accurate classification rates of KNN are not high.
Collaborative Representation Classifier (CRC): The Sparsest solution to y = Bx can be obtained by solving the following problem:
However, the Plo problem is a NP hard problem. Fortunately, Bruckstein et al. (2009) proved that Plo problem can be substituted by Pl1 problem. From l1 norm minimization, the sparsest solution of y = Bx can be also obtained. The Pl1 program is as follows:
However, from l1 norm minimization, it cannot obtain the closed form solution. The computational complexity of l1 norm minimization is a little high. Thus, some study proposed other method by using l2 norm minimization. Collaborative Representation Classifier (CRC) is proposed by Zhang and Yang (2010) which is a typical method by l2 norm minimization. The steps of CRC are given in Algorithm 1 (Zhang and Yang, 2010).
| Algorithm 1: Step of CRC method for classification |
From l2 norm minimization, a closed form solution can be obtained which gives x = (BTB+λI)-1 BTy . Its computational complexity is low. Although, CRC is useful for classification, it also has some problems. Extensive experiments show that, under some conditions, some test samples are misclassified by CRC. Thus, combined the advantages of KNN and CRC, this study proposes a local method, namely Collaborative Representation Classifier based on K Nearest Neighbors (KNN-CRC) method. The computational complexity of KNN-CRC is lower than SRC and CRC. Furthermore, under many conditions, the classification results of KNN-CRC are better than KNN and CRC.
Collaborative representation classifier based on k nearest neighbors:
| • | :KNN-CRC method: Combined the advantages of KNN and CRC, this study proposes a local CRC method, namely KNN-CRC method. The basic steps of KNN-CRC are as follows. First, given a test sample, find its K nearest neighbors from all the training samples. Second, make the K nearest neighbors as the dictionary, represent the test sample with the dictionary. It can also obtain the closed solution from l2 norm minimization. Third, compute the residual between the test sample and the each class in the dictionary. Finally, the KNN-CRC classifier can identify the test sample belongs to which class |
Specifically, the representation using KNN-CRC method is defined by Eq. 1
| (1) |
where, y denotes a test sample. denotes the dictionary which is composed of the K nearest neighbors chosen from all the training samples. Unlike CRC, the KNN-CRC method uses the K nearest neighbors as the dictionary. However, CRC method uses all the training samples as the dictionary. The size of K is much smaller than the total number of all training samples, thus, the computational complexity of KNN-CRC is much lower than SRC and CRC. The extensive experiments also clearly show that the proposed method can obtain very competitive classification results compared with other methods.
From KNN-CRC method, the solution to Eq. 1 is:
Using Lagrange multiplier, a relaxed form of Eq. 1, we obtained Eq. 2:
| (2) |
Taking derivative of Eq. 2 with respect to x, we obtained Eq. 3:
| (3) |
Solution of Eq. 3 is obtained as:
| • | KNN-CRC classifier: From the KNN-CRC method, the solution can be obtained. The solution is represented as: |
x = [xλ1,...,xλ2,...,xλk]
where, xλj is the part of coefficients corresponding to the jth class in x. The jth block of y is defined as:
For j = 1,…,k, this classifier will compute the residual:
It can find the smallest residual easily. If the jth residual is the smallest, it will identify that the test sample y belongs to the jth class.
EXPERIMENTS
In this study, some experiments on digit recognition and face recognition are presented to show the results of classification. These experiments focus on the property evaluation of KNN-CRC and other methods on the digit recognition and face recognition. Three databases, including AR (Chi and Porikli, 2012; Wright et al., 2009; Zhang et al., 2011), Extended Yale-B (Chi and Porikli, 2012; Wright et al., 2009; Zhang et al., 2011) and MNIST Handwritten Digits database (Chi and Porikli, 2012) are used to test the performance of KNN-CRC and other methods including NN, SRC and CRC. The KNN-CRC is proposed in this study. The NN is the nearest neighbors algorithm which is a conventional method for classification. The SRC is the classical sparse representation method (Wright et al., 2009). The CRC is the collaborative representation based classification with regularized least square (Zhang et al., 2011). This experiments focus on the property comparison of KNN-CRC and other methods.
Face recognition: The KNN-CRC and other methods are tested for comparing the recognition rate. Recognition rate denotes how many test samples can be classified correctly for all the test samples. Higher recognition rate means the property of this method is better. In this experiments, the Eigenface is used as preprocessing in feature extraction.
| • | AR database: The AR database contains about 4000 frontal images for 126 individuals (Chi and Porikli, 2012; Wright et al., 2009; Zhang et al., 2011). These images are captured under different facial disguises, illuminations and expressions. The images are cropped to size 60x43. A few samples of AR database are shown in Fig. 1. Table 1 show the recognition rates versus feature dimension by NN, SRC, CRC and KNN-CRC |
| • | Extended Yale-B database: The Extended Yale-B database contains 2414 frontal face images of 38 individuals (Chi and Porikli, 2012; Wright et al., 2009; Zhang et al., 2011). These samples were cropped and normalized to 54x48. A few samples of Extended Yale-B database are shown in Fig. 2. Table 2 shows the recognition rates versus feature dimension by NN, SRC, CRC and KNN-CRC |
| Table 1: | Face recognition rates of different methods on the AR database |
| Fig. 1: | Some training samples from the AR database |
| Fig. 2: | Some training samples from the extended Yale-B database |
| Fig. 3: | Some training samples from the MNIST database |
| Table 2: | Face recognition rates of different methods on the extended Yale-B database |
| Table 3: | Digit recognition results of different methods on the MNIST database |
| • | Digit recognition: The MNIST database is used to test the property of these methods. The dimension of each image is 28x28. Every image which is an 8 bit gray scale image from 0-9 (Chi and Porikli, 2012). The MNIST handwritten digits database which has a training set of 60,000 samples and a test set of 10,000 samples. For our experiment, 10 training samples are randomly selected from each class, 10 test samples are also randomly selected from each class. A few images of MNIST database are shown in Fig. 3. Table 3 show the recognition rates versus feature dimension by NN, SRC, CRC and KNN-CRC |
RESULTES AND DISCUSSION
Experiment results and analysis: From all the above face recognition and digit recognition experiments, the differences of SRC, CRC, NN and KNN-CRC can be seen clearly. The SRC is the classical sparse representation method. However, it cannot obtain the closed form solution, its computational complexity is high. In many cases, the recognition rate of KNN-CRC is higher than SRC.
| Table 4: | Comparison of KNN-CRC and other methods |
The CRC is the l2 norm constraint method, it can obtain the closed form solution, its computational complexity is lower than SRC. However, the recognition rate of KNN-CRC is also higher than CRC. The NN is a simple method for classification. However, in many cases, the recognition rate of NN is the lowest. Compared to other methods, KNN-CRC has many advantages. The recognition rate of KNN-CRC is higher than other methods, the computational complexity of KNN-CRC is also low. The comparison of KNN-CRC and other methods is listed in Table 4.
CONCLUSION
In this study, a new classification method is proposed which is different from SRC and CRC method, namely collaborative representation classifier based on K nearest neighbors (KNN-CRC) method. The KNN-CRC combines the advantages of KNN and CRC methods, the solution of KNN-CRC is obtained from the l2 norm minimization, it is a closed form solution. Furthermore with the KNN-CRC method, the training samples of a test sample are from the K nearest neighbors of the test sample. The number of the K nearest neighbors is much fewer than all the training samples. A closed form solution is also obtained from KNN-CRC. Thus, the computational complexity of KNN-CRC is much lower than SRC and CRC.
From the digit recognition and face recognition experiments, it clearly showed that the proposed KNN-CRC method can obtain very competitive results compared with SRC, CRC and other epresentation methods.
ACKNOWLEDGMENTS
This study was supported by the key fund project of Sichuan Educational department (NO.14ZA0005).