Pattern Classification By Using K-Nearest Neighbor Methods

In the fields of pattern recognition, machine learning, data mining, k-nearestneighbor rule (KNN) has been extensively studied and widely applied. In manypractical applications, due to its properties of intuitiveness, simplicity and effectiveness,k-nearest neighbor classifier has aways been adopted in pattern recognition, and it hasbeen viewed as one of10top algorithms in data mining. In recent years, many graphembedding methods, such as locality preserving projections (LPP) and its variants,construct local neighborhood structure of high-dimensional data using KNN indimensionality reduction, and obtain good classification performance. This paper is aresearch on pattern classification by using k-nearest neighbor rule, including theproblem of k-nearest neighbor classification and applications of k-neighborhood inconstructing graph of data in graph embedding for dimensionality reduction. The maincontributions are as follows:1. The classification performance of KNN-based nonparametrical classifiers isseriously influenced by the existing outliers, especially in the small sample cases. Toovercome the issues, local mean-based k-nearest centroid neighbor (LMKNCN)classifer has been developed. The proposed LMKNCN not only takes into account theproximity and spatial distribution of k neighbors, but also utilizes the local mean vectorof k neighbors from each class in making classification decision. LMKNCN has boththe robustness of local mean-based k-nearest neighbor (LMKNN) classifer in the case ofexisting outliers and effectiveness of k-nearest centroid neighbor (KNCN) classifer inthe small sample size settings. The extensive experimental results on real and artificialdatasets demonstrate that LMKNCN has a satisfactory classification performance withvarying the neighborhood size, the training sample size and feature space dimension.2. With respect to the problems of the small sample size, out-of sample andoverlearning locality that existed in graph embedding, a supervised graph embeddinglearning method, named locality-based discriminant neighborhood embedding (LDNE),has been developed. LDNE integrates both LPP and discriminant neighborhoodembedding (DNE) in the unified learning model. It can find an embedding that detects the underlying submanifold-based structures of data and has locality of LPP anddiscrimination of DNE, in order to further enhance the power of pattern discriminantion.A series of experiments on high-dimensional datasets demonstrate effectiveness ofLDNE with good classification.3. In LPP-based dimensionality reduction methods, the construction ofneighborhood graph and the allocation of the weight for its edges play an important role.In view of this, based on the basic idea of LPP, maximum neighborhood margindiscriminant projection (MNMDP) has been proposed. In MNMDP, the adjacent weightis defined by fully considering the class label information, and intra-class neighborhoodscatter and inter-class neighborhood scatter are determined. Moreover, it maximizes thegap between intra-class and inter-class neighbors by employing maximum margincriterion (MMC) in the objective function, so as to find a good graph embedding in newsubspace of high-dimensional data. MNMDP not only solves the related issues in graphembedding, but also improves the ability of pattern discriminantion. Experimentalresults on the hand-based biometrics datasets demonstrate the effectiveness of MNMDP.4. Based on sparsity preserving projections (SPP) and LPP, sparsity localitypreserving projections (SLPP) that integrates the sparse graph construction andk-neighborhood graph construction has been introduced. Through sparse learning, SLPPobtains sparse representation graph construction, then builds the sparse localitypreserving model of graph embedding, combined with k-neighborhood graphconstruction. SLPP not only preserves the intrinsic geometry of data and naturaldiscrimination of sparse representation, but also enhances the power of patterndiscriminantion. Experimental results on face datasets demonstrate the effectiveness ofSLPP.