一个解决大数据集问题的核主成分分析算法.pdf
一个解决大数据集问题的核主成分分析算法史卫亚,郭跃飞+,薛向阳(复旦大学 计算机科学与技术系,上海 200433)An efficient Kernel Principal Component Analysis Algorithm for large-scale data set*Shi Weiya,Guo Yue-Fei+,Xue Xiangyang(Department of Computer Science and Technology,Fudan University,Shanghai 200433,China)+Corresponding author:Phn:+86-21-65643922,Fax:+86-21-65643922,E-mail:,http:/Abstract:Kernel principal component analysis(KPCA)is a popular nonlinear feature extraction method in the field of machine learning.It uses eigen-decomposition technique to extract the principal components.But the method is infeasible for large-scale data set because of the store and computational problem.To overcome these disadvantages,a new covariance-free method of computing kernel principal components is proposed.First,a matrix,called Gram-power matrix,is constructed using the original Gram matrix.It is proven by the theorem of linear algebra that the eigenvectors of newly constructed matrix are the same as the ones of the Gram matrix.Therefore,we can treat each column of the Gram matrix as the input sample for the covariance-free algorithm.Thus,the kernel principle components can be iteratively computed without the eigen-decomposition.The space complexity of proposed method is only,the time complexity is reduced to.The effectiveness of proposed method is validated from experimental results.More important,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;Gram matrix;large-scale data set;covariance-free;eigen-decomposition摘 要:核主成分分析是一种流行的非线性特征提取方法。一般情况下它使用特征分解技术提取核主成分，但是在大数据集情况下因为储存和计算问题是不可行的。为了解决这个问题，本文提出一种大数据集求解核主成分的计算方法。首先使用Gram矩阵生成一个Gram-power矩阵，根据线性代数的理论可知新形成的矩阵和原先的Gram矩阵具有相同的特征向量。因此，我们可以把Gram矩阵的每一列看成核空间迭代算法的输入样本，通过迭代计算出核主成分。提出的算法的空间复杂度只有，在大数据集的情况下时间复杂度也降低为。实验结果证明了所提出算法的有效性。更为重要的是当传统的特征分解技术无法使用的情况下，所提出的方法仍然可以提取非线性特征。关键词:核主成分分析;Gram 矩阵;大数据集;协方差无关;特征分解中图法分类号:TP301文献标识码:A主成分分析是一种用于特征提取和维度减少的经典方法 1。该方法一般使用具有较大方差的主成分而忽略较少重要的成分。尽管主成分分析成功用于维度减少，但是在非线性数据分布情况下该方法不是太好。通常使用核方法2将其推广到核空间使用。其主要思想是把数据映射到高维的特征空间，在映射的特征空间中，可以使用传统的线性算法而实现非线性特征的特征提取。其中不用知道映射函数而采用核技巧就可以计算数据之间的内积。提取的非线性特征被用于许多复杂的应用中，例如人脸识别，图像压缩等。在标准的核主成分计算过程中，需要储存所有数据形成的Gram矩阵3，其空间复杂度为，其中mthe 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(国家科技支撑计划课题);the National High Technology Research and Development Program of China under Grant No.2007AA01Z176（国家高技术研究发展计划资助项目（863计划）2表示样本数。另外，对Gram矩阵进行特征分解的时间复杂度为。因为有限的内存容量，当大数据集情况下该方法是不可行的。郑4提出把数据集分成若干小的数据集，然后分别处理。贪婪的核主成分分析方法5通过采样训练集而近似求解特征向量。但是这些方法仍然存在较大的储存问题。在6中，通过把传统的广义Hebbian算法扩展到核空间迭代的求解核主成分，可以避免储存问题，但是这种方法的收敛性不能保证。本文提出了一种大数据集情况下有效的求解核主成分的方法。主要思想是利用线性代数中对称矩阵的性质，首先使用初始的Gram矩阵创建一个新的Gram-power矩阵。因为新构成的矩阵和原先的矩阵具有相同的特征向量，所以我们可以把Gram矩阵的每一列看成核空间迭代算法7的输入样本。通过若干迭代后，可以很容易的求出核主成分。所提出的方法不需要事先存储Gram矩阵，空间复杂度从减少到。另外算法的快速收敛性已经被证明 8。更为重要的是处理非常大数据集情况下，传统的特征分解技术没法使用，所提出的方法仍然可以较好的提取非线性特征。通过在人工合成的数据集以及真实的数据上进行实验，充分证明了所提出算法的有效性。下一部分对核主成分的实现过程进行回顾，同时把常用的一些迭代算法进行比较；在第二部分详细描述本文所提出的方法；然后给出实验结果证明提出算法的有效性；最后给予总结。1 核主成分分析的回顾和迭代算法分析1 1 核主成分分析的回顾假定是输入空间的数据集，其中是d维向量，m是数据集中的总样本数。存在一个函数把数据映射到高维（甚至无限维）的希尔伯特空间。（1）使用这个映射函数，我们可以得到特征空间的数据集。一个核函数被用于计算这些映射数据样本之间的内积，这个核函数定义为，这样在映射的特征空间协方差定义为：（2）它符合特征方程：(3)其 中和分 别 对 应 协 方 差 矩 阵 的 特 征 向 量 和 特 征 值。因 为 解可 以 用 全 部 数 据 集 的张程表示为：(4)将公式3和4代到公式2中，可以推导出下面的公式：(5)其中是张程系数，是Gram矩阵，定义为。该矩阵的元素为。理论证明9Gram矩阵是半正定的。为了计算核主成分，一般都是对Gram矩阵采用特征分解的方法。这样得到特征向量后，可以使用公式4计算核主成分。对于任何一个测试样本，其非线性特征为：(6)史卫亚 等:一个解决大数据集问题的核主成分分析算法3在 上 面 的 推 导 中 是 假 定 所 有 数 据 具 有 零 均 值 的，如 果 不 是 的，可 以 得 到，其中3。1 2 迭代算法分析因为传统的特征分解方法需要非常大的内存。为了克服这个不便，一些计算主成分的迭代方法被提出，例如GHA 10,APEX 11。但是这些方法一般收敛速度较慢。翁7利用统计学上的效能估计概念提出了一个增量的协方差无关的方法，该方法不是像传统方法一样特征分解协方差矩阵，而是循环地输入样本向量，与其它迭代方法相比起来，收敛速度快，而且计算复杂度很低。因此我们选用这种方法作为所提出算法的迭代工具。2 提出的核主成分算法一般情况下，映射函数是不知道的，因此，特征空间的样本向量没法明确表示，这样在核空间就没有办法使用上述迭代方法计算核主成分。为了解决这个问题并给出我们的方法，首先给出一个线性代数的定理1213。定理：矩阵和具有相同的特征向量和不同的特征值。证明：假定和分别是矩阵的特征向量和特征值，（7）（8）因此，矩阵的特征向量和特征值即为和。2 1 提出的方法因为Gram矩阵是半正定的，可以得到，因此可以构造一个矩阵Gram-power，定义为。根据前面的定理，新构造的矩阵的特征向量与Gram矩阵的特征向量相同，但有不同的特征值和()。（9）其中，因此，我们可以把矩阵的每一列作为迭代算法7的输入样本，这样经过一些迭代后，就可以迅速得到矩阵的特征向量。而不用像传统方法那样对Gram矩阵特征分解。因为在实际计算中，我们每次只需计算，从而有效地解决了大样本需要存储Gram矩阵的问题。下面，我们具体给出求解矩阵G的特征向量的算法过程。根据定义，新构造的Gram-power矩阵的特征向量和特征值符合下面的公式：4 （10）其中是特征向量在第n时刻估计，在得到特征向量后，可以很容易的计算特征向量和特征值。因为现在的“输入样本”为，因此可以依次将样本输入到迭代算法中，这样在n时刻第i阶核主成分的估计可以表示为：（11）其中是计算第i阶核主成分时在t时刻的输入样本。其它高阶特征向量可以用残留的数据向量计算。而残留的数据向量是用最初数据减去其在低阶特征向量的投影():（12）这样通过迭代计算就可以得到需要的特征向量和特征值。算法概括如下：1?使用前个样本初始化前阶特征向量.2?Iteration=1:p进行下面计算3?进行下面计算4?进行下面计算5?对每个输入样本，计算相应的，作为输入向量6?使用公式11和12计算前阶主成分7?转到步骤48?转到步骤39?转到步骤210?输出特征向量和特征值2 2 算法的复杂度分析整个计算过程中，不需要特征分解Gram矩阵，因为这样空间复杂度是，时间复杂度是。相反，在每一步只处理样本，其复杂度只有，这样经过一些迭代后就可以得到核主成分。因为算法需要经过一些迭代，总的时间复杂度为,其中分别为迭代次数，特征向量数目和总的样本数。在大样本数据集情况下，迭代次数和提取向量的数目远小于样本数目。因此所提出算法时间复杂度也大大降低。史卫亚 等:一个解决大数据集问题的核主成分分析算法5Fig.1 Contour image of first 3 principal components obtained from proposed method(the top row)and standard KPCA(the bottom row).图.1 使用提出的方法（上行）与标准的方法（下行）产生的前三个主成分的轮廓图。Table1 Experiment result of the first 3 eigenvalues()表.1使用两种方法得到的前三个特征值()3 实验结果和讨论为验证提出算法的有效性，我们使用标准的KPCA算法和提出的方法在一个具有3聚类，2维的简单问题上进行实验。除此之外，还使用USPS数据集在图像降噪和分类上验证提出算法的可行性。实验中如果没有明确说明，核函数使用高斯核（是核函数的宽度参数，一般需要通过交叉验证而确定）。模拟问题：2维的数据集含有三个聚类，每个聚类有三十个样本，都具有高斯分布，其均值分别为-0.5-0.2,0 0.6,0.5 0，标准方差为0.1，核参数为0.1.前3个特征值 1 2 3 5.556 4.95 0.247 22.558 20.936 4.648图1给出了实验结果，它表征了两种方法提取的前三个核主成分的轮廓图，灰度值代表测试样本投影的非线性特征值。所得到的对应特征值在表1中列出。其中和分别是用提出方法和标准的方法得到的特征值。从结果可以清晰的看到，提出方法可以得到与标准方法类似的结果。另外，我们还比较两种方法产生的前3个特征向量的平均内积随迭代次数的变化，结果见图2，从图中可以观察到，经过一些迭代后，所提出的方法得到的特征向量非常好的收敛到标准方法产生的特征向量。6Fig.2 Average dot product of first 3 principal components obtained from standard KPCA and the proposed method.图.2 使用标准方法和提出方法所得到的前三个特征向量的平均内积。Fig.3 De-nosing results obtained by different methods.First row:original image;Second row:noisy image;Third row:de-noising result by batch KPCA;Fourth row:de-noising result by proposed method.图.3 使用两种方法得到的图像降噪结果。从上到下分别为原图像、加噪图像、使用标准方法以及本方法经过降噪处理后得到的图像。Table 2 Error rate of 2007 testing sample of USPS data set using the proposed method（%）.表 2使用本方法在USPS数据集上用全部训练样本训练，使用最近邻分类方法得到的测试样本的误差率（%）.USPS数据集：接下来我们在一些标准数据集上测试提出的方法。USPS数据集是256维的字符向量，含有7291个训练样本和2007个测试样本。在这个实验中核参数设置为，其中d是数据向量的维度，c设置为数据平均方差的两倍。首先使用提取的特征进行降噪实验。随机取3000个训练样本用标准的KPCA和提出方法进行训练，提取前64个主成分。测试样本用均值为0，方差为0.5的高斯噪声迭加。利用提取的非线性特征进行重组图像，实验结果见图3，从图中可以看到两种方法重组的图像都获得了很好的降噪效果。为了进一步验证提出的方法，我们使用所有的训练样本来提取非线性特征，实验中使用多项式核（d为多项式度）。在这种情况下Gram矩阵的大小为，如果用标准的KPCA方法因为样本数目太大，没法进行计算。但是我们提出的方法仍然可以提取核主成分。测试样本在提取的前64个主成分上进行投影，然后用最近邻方法进行分类，表2给出了分类的误差率。数据表明提出的方法在大样本情况下获得了较好的分类效果。提取的主成分数 d=2 3 4 5 6 64 5.88 6.13 6.57 7.06 7.25史卫亚 等:一个解决大数据集问题的核主成分分析算法74 结束语本文提出了一种大数据集情况下提取核主成分的有效方法。方法首先利用Gram矩阵构造一个Gram-power矩阵，因为两个矩阵有相同的特征向量，因此不需要像传统方法一样特征分解Gram矩阵，而是用Gram矩阵的每一列作为每一步迭代算法的输入样本。这样可以有效解决传统方法在大数据集下无法使用的问题。提出的方法空间复杂度减少为，时间复杂度也降低为。更为重要的是，当样本数目非常大时，所提出方法仍然可以提取非线性特征。References:1 Kirby Y and Sirovich L.Application of the Karhunen-loeve Procedure for the Characterization of Human Faces.IEEE Trans.Pattern Anal.Mach.Intell.,1990,12(1):103108.2 Scholkopf B and Smola A.Learning with kernel:Support Vector Machines,Regularization,Optimization and Beyond.,London,England,MIT Press,2002,25-553 Scholkopf B,Smola A,and Muller KR.Nonlinear component analysis as a kernel eigenvalue problem.Neural computation,1998,10,1299-1319.4 Zheng W,Zou C and Zhao L.An improved Algorithm for Kernel Principal Components Analysis.Neural Processing Letters,2005,22,49-56.5 France V and Hlavac V.Greedy algorithm for a training set reduction in the kernel methods.in:Proc.Int.conf.Computer Analysis of Images and patterns,2003,426-433.6 Kim KI,Franz MO,and Scholkopf B.Iterative kernel component analysis for image modeling.IEEE Trans Pattern Analysis.Machine.Intelligent,2005,27(9):1351-1366.7 Weng J,Zhang Y and Huang WS.Candid covariance-free incremental principal component analysis.IEEE Trans Pattern Analysis.Machine.Intelligence,2003,25(8),1034-1040.8 Zhang Y and Weng J.Covergence analysis of complementary candid incremental principal component analysis.Technical Report MSU-CSE-01-23,Dept.of Computer Science and Eng.,Michigan State Univ.,East Lansing,20019 Shawe-Taylor J and Cristianini N.Kernel Methods for Pattern Analysis.first ed.,Endland,Cambridge University Press,2004,68-82.10 Sander TD.Optimal unsupervised learning in a single-layer linear feedforward neural network.Neural Network,1989,12,459473.11 kung SY and Diamantaras KI.A neural network learning algorithm for adaptive principal component extraction(apex).in:Proc.IEEE Conf.On Acoustics,Speech,and Signal.,Vol.2,Albuquerque,1990,861864.12 Golub GH and Van Loan CF.Matrix Computation.third edi.,The Johns Hopkins University Press,Baltimore,MDm USA,1996,49-8513 Strang G.Introduction to Linear Algebra.second ed.,Wellesley-Cambridge Press,1998,245-282
