第5卷第3期 智能系统学报 Vol.5 No.3 2010年6月 CAAI Transactions on Intelligent Systems Jun.2010 doi:10.3969/i.issn.1673-4785.2010.03.003 采用核聚类分析的KPCA改进算法 邓貌，陈旭，陈天翔，王徽蓉1，鲁华祥 (1.中国科学院半导体研究所，北京100083：2.厦门理工学院电子与电气工程系，福建厦门361005) 摘要：为了解决核主分量分析方法处理大训练样本集时计算代价巨大的问题，在采用子集划分的KP℃A算法基础 上，提出采用核聚类划分子集，并用每个子集的协方差矩阵的特征值累积贡献率作为标准来选取相应的特征向量. 分别在人工和实际数据集上测试，实验结果显示在同一累积贡献率和给定子集个数的条件下，采用核聚类划分子集 总能得到较小尺寸的核矩阵，而核矩阵尺寸的减小有助于改善测试样本的特征提取速度以及降低特征分解核矩阵 的时间复杂度. 关键词：核主分量分析：核聚类；子集划分；协方差矩阵；特征向量 中图分类号：TP18文献标识码：A文章编号：16734785(2010)03022106 Improved kernel principal component analysis based on a clustering algorithm DENG Mao',CHEN Xu',CHEN Tian-xiang,WANG Hui-rong,LU Hua-xiang (1.Institute of Semiconductors,Chinese Academy Sciences,Beijing 100083,China;2.Department of Electronic and Electrical Engi- neering,Xiamen University of Technology,Xiamen 361005,China) Abstract:To overcome the computational problems of the standard kernel principal component analysis (KPCA) algorithm,the authors proposed a new method for eigenvector selection by evaluating the cumulative contribution rate of the eigenvalues of the covariance matrix.In addition,a new way to partition the training data set based on kernel clustering was also developed.The influence was then explored of different partitions of training data sets on the size of the final kernel matrix,on the conditions causing a given cumulative contribution rate,and on the num- ber of subsets.Experimental results showed that a smaller kernel matrix can be obtained when kemel clustering method are used to partition the training dataset.The proposed algorithm can be helpful to reduce the time complex- ity of the eigen decomposition of a kernel matrix and to improve the speed of feature extraction for test samples. Keywords:KPCA;kemel clustering;partition of training data set;covariance matrix;eigenvector 核主分量分析(kernel principal component anal- 为此，文献[6]提出将训练集划分成若干子集， ysis,KPCA)通过Mercer核函数实现非线性映射，将 并将每个子集在特征空间中的协方差矩阵用一些特 主分量分析(principal component analysis,.PCA)方 征向量近似表示.基于这种近似表示，使KPCA在求 法在特征空间中推广.由于KPCA算法具有较强的 解过程中，只需对一个阶数等于这些特征向量数目 提取数据非线性特征的能力，因此它在模式识别、故 之和的核矩阵进行特征值分解即可，该方法简单有 障分析等领域得到了广泛的应用和重视1].但标 效，但是文中没有讨论每个子集应选取多少个特征 准KPCA算法需要对一个M×M的核矩阵(M为训 向量，以及训练集划分子集的不同方式是否会明显 练样本个数)进行特征值分解，当训练大样本集时， 影响最后选择的特征向量个数，从而影响分解最终 该方法面临计算代价巨大的问题。 核矩阵的时间复杂度以及求解测试样本的特征提取 时间.本文将针对这2个问题进行探讨. 收稿日期：2009-12-19. 基金项目：国家“863”计划资助项目(2007AA04Z423,2006AA01Z106):国 1基于子集划分的KPCA 家自然科学基金资助项目(60576033)：福建省自然科学基金资 助项目(2008J04001);厦门市科技计划资助项目 (3502Z20083031). 由文献[6]，设训练样本集X={x:1,划分的 通信作者：陈旭.E-mai:8 hendacx(@163.com