学位论文 > 优秀研究生学位论文题录展示

大规模数据集下核方法的技术研究

作　者: 史卫亚
导　师: 薛向阳
学　校: 复旦大学
专　业: 计算机应用技术
关键词: 大规模数据集核主成分分析核方法核矩阵非线性特征矩阵分解迭代算法数据子集
分类号: TP301
类　型: 博士论文
年　份: 2008年
下　载: 335次
引　用: 3次
阅　读: 论文下载

内容摘要

主成分分析(Principal Component Analysis)是一种用于特征提取和降维的线性方法,它一般使用具有较大方差的维作为主成分而忽略方差小的维,从而将数据映射到低维的子空间中提取线性特征。但是当数据是线性不可分的情况下,该方法不能很好地提取判别特征,通常使用核方法把数据映射到高维特征空间进行主成分的运算,即核主成分分析(Kernel Principal Component Analysis),该过程不需要显式地知道映射函数,而是利用核技巧实现,提取的非线性特征被成功应用于图像处理等任务中。在核主成分计算过程中,需要储存全部数据集生成的核矩阵,该矩阵是通过核函数计算数据之间的内积而得到的,矩阵的大小随着数据集样本数目m变化而变化,空间复杂度为O(m~2),而对核矩阵进行特征分解的时间复杂度为O(m~3)。在大规模数据集的情况下,由于内存容量的限制,在一般计算机上对核矩阵的存储和计算都是困难的,应寻找可行的解决方法。在深入研究模式分析中核方法相关技术的基础上,本文针对大规模数据集问题,探讨了已有解决方法的实质以及相互之间的关系,提出了三种有效的求解核主成分的方法,具体内容包括:●使用incomplete Cholesky分解将核矩阵转化为两个互为转置的三角矩阵,三角矩阵的每一列可以看作为特征空间特殊的“输入样本”,将这些样本输入到主成分分析的迭代算法中,经过若干次迭代后,就可以计算出核主成分。该方法不需要对核矩阵进行特征分解,其空间和时间复杂度分别为O(nm)和O(nm)+O(nkp),其中n,k,m,p分别为核矩阵的秩、需提取的主成分数、样本数以及迭代次数。在大规模数据集的情况下,核矩阵的秩和要提取的主成分数通常远小于样本数,因此空间和时间复杂度都有较大程度的降低。●利用核矩阵的对称性质,基于初始核矩阵创建一个新的Gram-power矩阵,因为新矩阵和原核矩阵具有有相同的特征向量,可以计算Gram-Power矩阵的特征向量来代替核矩阵的特征分解,把核矩阵的每一列看成是迭代主成分分析算法的“输入样本”,经过若干次迭代后,可以很容易的求出核主成分,并且算法的空间复杂度从O(m~2)减少到O(m)。●提出了一个基于矩阵的核主成分分析(Matrix-based Kernel PrincipalComponent Analysis)方法,该方法首先将大规模数据集等分成许多小的数据子集,每个数据子集的自相关矩阵可以看成是核空间的“特殊样本”,用一个基于矩阵的创新核函数来计算数据子集之间的内积。由于子集的数量远小于数据集样本的数目,因此较大程度地降低核矩阵的大小,提出的方法和KPCA的实现过程几乎完全一样,并且自相关矩阵含有每个子集的高阶统计信息,有助于性能的改善。通过在人工合成的数据集以及真实的数据上进行实验,验证了大规模数据集的情况下所提出算法的有效性。

全文目录

摘要  5-7
ABSTRACT  7-9
第一章研究背景和本文工作  9-18
  1.1 模式分析中的核方法  9-14
  1.2 本文研究背景及意义  14
  1.3 主要工作  14-16
  1.4 论文结构  16-18
第二章特征提取的核方法分析  18-29
  2.1 再生核希尔伯特空间(REPRODUCTING KERNEL HILBERT SPACE)  18-20
  2.2 核主成分分析KPCA(KERNEL PRINCIPAL COMPONENT ANALYSIS)  20-24
  2.3 广义判别分析GDA(GENERALIZED DISCRIMINANT ANALYSIs)  24-28
  2.4 本章小结  28-29
第三章大规模数据集情况下的KPCA方法回顾  29-38
  3.1 引言  29-30
  3.2 核HEBBIAN算法(KERNEL HEBBIAN ALGORITHM,KHA)  30-33
  3.3 分块核主成分  33-36
  3.4 本章小结  36-38
第四章基于迭代算法的核主成分分析  38-65
  4.1 引言  38-40
  4.2 基于INCOMPLETE CHOLESKY分解的核主成分分析  40-53
    4.2.1 QR分解和incomplere Cholesky分解  40-43
    4.2.2 基于incomplete Cholesky分解的KPCA  43-45
    4.2.3 算法的计算复杂性  45-46
    4.2.4 计算的特征值的分析  46
    4.2.5 实验结果和讨论  46-53
    4.2.6 小结  53
  4.3 基于GRAM-POWER矩阵的核主成分分析  53-63
    4.3.1 构造新的矩阵Gram-Power  53-55
    4.3.2 基于Gram-Power矩阵的KPCA  55-56
    4.3.3 算法的复杂度分析  56-57
    4.3.4 计算的特征值分析  57
    4.3.5 实验结果和讨论  57-63
    4.3.6 小结  63
  4.4 本章总结  63-65
第五章基于矩阵的核主成分分析  65-78
  5.1 引言  65
  5.2 数据集的分割和自相关矩阵  65-66
  5.3 基于矩阵的多项式一矩阵核函数  66-69
  5.4 基于矩阵的KPCA  69-71
  5.5 实验结果  71-76
    5.5.1 Toy examples:简单问题  72-73
    5.5.2 USPS数据:  73-76
  5.6 本章总结:  76-78
第六章总结与展望  78-81
附录一博士期间发表的论文  81-82
附录二博士期间参加的科研项目  82-83
参考文献  83-91
致谢  91-92

大规模数据集下核方法的技术研究

内容摘要

全文目录

相似论文