Kim Sang-Woon, Oommen B John
Department of Computer Science and Engineering, Myongji University, Yongin, Korea.
IEEE Trans Syst Man Cybern B Cybern. 2008 Apr;38(2):564-70. doi: 10.1109/TSMCB.2007.914446.
Fisher's linear discriminant analysis (LDA) is a traditional dimensionality reduction method that has been proven to be successful for decades. Numerous variants, such as the kernel-based Fisher discriminant analysis (KFDA), have been proposed to enhance the LDA's power for nonlinear discriminants. Although effective, the KFDA is computationally expensive, since the complexity increases with the size of the data set. In this correspondence, we suggest a novel strategy to enhance the computation for an entire family of the KFDAs. Rather than invoke the KFDA for the entire data set, we advocate that the data be first reduced into a smaller representative subset using a prototype reduction scheme and that the dimensionality reduction be achieved by invoking a KFDA on this reduced data set. In this way, data points that are ineffective in the dimension reduction and classification can be eliminated to obtain a significantly reduced kernel matrix K without degrading the performance. Our experimental results demonstrate that the proposed mechanism dramatically reduces the computation time without sacrificing the classification accuracy for artificial and real-life data sets.
费希尔线性判别分析（LDA）是一种传统的降维方法，几十年来已被证明是成功的。人们提出了许多变体，如基于核的费希尔判别分析（KFDA），以增强LDA对非线性判别的能力。尽管KFDA有效，但计算成本高昂，因为其复杂度会随着数据集规模的增大而增加。在本通信中，我们提出了一种新颖的策略来加速整个KFDA族的计算。我们主张，不是对整个数据集调用KFDA，而是先使用原型约简方案将数据约简为一个较小的代表性子集，然后通过对这个约简后的数据集调用KFDA来实现降维。通过这种方式，可以消除在降维和分类中无效的数据点，从而在不降低性能的情况下显著减小核矩阵K的规模。我们的实验结果表明，所提出的机制在不牺牲人工数据集和实际数据集分类准确率的情况下，显著减少了计算时间。
