使用迭代方法求解核主成分分析  

To Solve Kernel Principal Component Analysis Using Iterative Method

作　　者：史卫亚[1,2] 郭跃飞[3] 

机构地区：[1]河南工业大学信息科学与工程学院,郑州450001 [2]粮食信息处理与控制教育部重点实验室,郑州450001 [3]复旦大学计算机科学技术学院,上海200433

出　　处：《小型微型计算机系统》2013年第8期1882-1885,共4页Journal of Chinese Computer Systems

基　　金：河南省教育厅自然科学研究计划项目(2010B520005)资助;河南工业大学博士基金项目(2009BS013)资助;国家自然科学基金项目(60875003)资助;河南省科技厅重点科技攻关项目(112102210190)资助;郑州市科技发展计划项目(2010SFXM470)资助

摘　　要：核主成分分析方法是使用核方法将经典的线性算法主成分分析推广到高维空间,用来处理复杂非线性数据的一种常用的特征提取算法,该算法首先在高维空间中计算所有样本之间的核矩阵,然后使用特征分解技术计算核矩阵的特征解,其计算的时间和空间复杂度分别为O(m2)和O(m3).然而在大规模数据集的情况下,由于储存和计算的问题无法进行正常的求解.文中提出首先使用幂迭代方法计算核矩阵的高阶特征解,然后重复使用Schur-Weilandt收缩方法分别计算出核矩阵的其它阶特征解.文中算法在计算过程中,不需要像传统的计算方法那样需要事先存储核矩阵,空间复杂度只有O(m).通过在模拟和真实数据的实验结果充分验证了算法的有效性.Kernel Principal Component Analysis （KPCA） is the generalized algorithm of famous Principal Component Analysis （ PCA）, which uses the kernel method and treats with the complex nonlinear dataset. It firstly computes the kernel matrix between mapped samples in high dimensional space, and uses eigen-decomposition technique to compute the eigen-solution for kernel matrix. The space and time complexity of the KPCA is O（ m2 ） and O（ m3 ） , respectively. When faced with large-scale data set, the method is infeasible for the sake of the storage and computational problem. In this paper, the Power iteration is introduced to compute the highest eigen-solution. Then the Schur-Weilandt deflation is repeatedly applied to achieve other higher order eigenvectors. In the process of computation, the kernel matrix needs not to compute and store in advance. The space complexity of the proposed method is only O （ m ）. The effectiveness of proposed method is validated from experimental results on toy and real dataset.

关 键 词：核主成分分析 核矩阵 大数据集 特征分解 幂迭代 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]