Study On Feature Transformation Algorithm Based On K-Nearest-Neighbor Classification Rule

Feature transformation and metric learning play important roles in the field of pattern recognition. New representations of samples and more appropriate distance metrics can be learned by feature transformation, which can improve the performance of clustering and classification. Metric learning approaches actually transform samples into a new space, and if the dimensionality of the new space is lower than the original one, dimension reduction is performed simultaneously.We first review the classical feature transformation methods such as orthonormal transformation, whitening transformation, PCA (Principal Component Analysis), LDA (Linear Discriminant Analysis), and NDA (Nonparametric Discriminant Analysis) , and the relation between them are discussed. We also introduce manifold learning algorithms such as LLE (Locally Linear Embedding) and Laplacian Eigenmap. Then we propose a novel feature transformation method based on k-nearest-neighbor (knn) rule for classification, called DNE (Discriminant Neighborhood Embedding).In the proposed method, a disciminant adjacent matrix is built to characterize local geometry structure of multi-class data set. Using this disciminant adjacent matrix, we define an objective function to obtain an optimal transformation matrix which maps samples into a new space. By this means we learn an appropriate distance metric, and in the new metric space intra-class neighbors become even more nearby, while extra-class neighbors become as far away from each other as possible. Moreover, optimal dimensionality of the new space can be estimated by spectral analysis, which is largely different from other related methods.By transforming samples to a low-dimensional space, our method can alleviate the curse of dimensionality and save the computation cost for knn classification. It is non-parametric, i.e., not assuming that the class densities belong to any particular parametric family, so it is suitable for data with both uni- and multi-modal class distributions. It is non-iterative, i.e., there is no time-consuming iterative procedure employed for optimization in our algorithm. It does not calculate the inverse matrix, so the complication of matrix singularity due to Small Sample Size (SSS) problem is avoided.Through the neural network model and kernel trick, we extend DNE algorithm to be non-linear. In the non-linear case, samples are first mapped into a high-dimensional Hilbert space, and then a subspace suitable for knn classification is learned. The optimal dimensionalty of the new space may be lower than, equal to, or even larger than that of the original space. Experimental results show that non-linear DNE is especially suitable for those datasets with a larger number of lower-dimensional samples.