主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
史卫亚,郭跃飞,薛向阳.一种解决大规模数据集问题的核主成分分析算法.软件学报,2009,20(8):2153-2159
一种解决大规模数据集问题的核主成分分析算法
Efficient Kernel Principal Component Analysis Algorithm for Large-Scale Data Set
投稿时间:2008-04-10  修订日期:2008-06-03
DOI:
中文关键词:  核主成分分析  Gram矩阵  大规模数据集  协方差无关  特征分解
英文关键词:KPCA (kernel principal component analysis)  Gram matrix  large-scale data set  covariance-free  eigen-decomposition
基金项目: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 (国家科技支撑计划)
作者单位
史卫亚 复旦大学 计算机科学与技术系,上海 200433 
郭跃飞  
薛向阳  
摘要点击次数: 4171
全文下载次数: 4545
中文摘要:
      提出一种大规模数据集求解核主成分的计算方法.首先使用Gram矩阵生成一个Gram-power矩阵,根据线性代数的理论可知,新形成的矩阵和原先的Gram矩阵具有相同的特征向量.因此,可以把Gram矩阵的每一列看成核空间迭代算法的输入样本,这样,无须使用特征分解即可迭代地计算出核主成分.该算法的空间复杂度只有O(m);在大规模数据集的情况下,时间复杂度也降低为O(pkm).实验结果表明了所提出算法的有效性.更为重要的是,在大规模数据集的情况下,当传统的特征分解技术无法使用时,该方法仍然可以提取非线性特征.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利