| 摘要: |
| 提出一种大规模数据集求解核主成分的计算方法.首先使用Gram矩阵生成一个Gram-power矩阵,根据线性代数的理论可知,新形成的矩阵和原先的Gram矩阵具有相同的特征向量.因此,可以把Gram矩阵的每一列看成核空间迭代算法的输入样本,这样,无须使用特征分解即可迭代地计算出核主成分.该算法的空间复杂度只有O(m);在大规模数据集的情况下,时间复杂度也降低为O(pkm).实验结果表明了所提出算法的有效性.更为重要的是,在大规模数据集的情况下,当传统的特征分解技术无法使用时,该方法仍然可以提取非线性特征. |
| 关键词: 核主成分分析 Gram矩阵 大规模数据集 协方差无关 特征分解 |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National High-Tech Research and Development Plan of China under Grant No.2007AA01Z176 (国家高技术研究发展计划(863)); the Key Project of the Ministry of Education of China under Grant No.104075 (国家教育部科学技术研究重点项目); the National Key Technology R&D Program of China under Grant No.2007BAH09B03 (国家科技支撑计划) |
|
| Efficient Kernel Principal Component Analysis Algorithm for Large-Scale Data Set |
|
SHI Wei-Ya,GUO Yue-Fei,XUE Xiang-Yang
|
| Abstract: |
| A covariance-free method of computing kernel principal components is proposed. First, a matrix, called Gram-power matrix, is constructed with the original Gram matrix. It is proven by the theorem of linear algebra that the eigenvectors of newly constructed matrix are the same as those of the Gram matrix. Therefore, each column of the Gram matrix can be treated as the input sample for the iterative algorithm. Thus, the kernel principle components can be iteratively computed without the eigen-decomposition. The space complexity of the proposed method is only O(m), and the time complexity is reduced to O(pkm). The effectiveness of the proposed method is validated by experimental results. More importantly, it still can be used even if traditional eigen-decomposition technique cannot be applied when faced with the extremely large-scale data set. |
| Key words: KPCA (kernel principal component analysis) Gram matrix large-scale data set covariance-free eigen-decomposition |
