Abstract

Previous manifold learning algorithms mainly focus on uncovering  the low dimensional geometry structure from a set of samples that lie on or  nearly on a manifold in an unsupervised manner. However, the representations  from unsupervised learning are not always optimal in discriminating capability.   In this paper, a novel algorithm is introduced to conduct discriminant analysis  in term of the embedded manifold structure. We propose a novel clustering  algorithm, called Intra-Cluster Balanced K-Means (ICBKM), which ensures  that there are balanced samples for the classes in a cluster; and the local  discriminative features for all clusters are simultaneously calculated by  following the global Fisher criterion. Compared to the traditional linear/kernel  discriminant analysis algorithms, ours has the following characteristics: 1) it is  approximately a locally linear yet globally nonlinear discriminant analyzer; 2) it  can be considered a special Kernel-DA with geometry-adaptive-kernel, in  contrast to traditional KDA whose kernel is independent to the samples; and 3)  its computation and memory cost are reduced a great deal compared to  traditional KDA, especially for the cases with large number of samples. It does  not need to store the original samples for computing the low dimensional  representation for new data. The evaluation on toy problem shows that it is  effective in deriving discriminative representations for the problem with  nonlinear classification hyperplane. When applied to the face recognition  problem, it is shown that, compared with LDA and traditional KDA on YALE  and PIE databases, the proposed algorithm significantly outperforms LDA and  Mixture LDA, has better accuracy than Kernel-DA with Gaussian Kernel.