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

论文摘要

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

论文目录

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