摘  要： 提出一种快速算法，该算法利用贪心算法构造卷数据降维矩阵，在保持点与点之间“核距离”不变的情况下，把待分解矩阵变换成一个低维矩阵。在没有偏差的情况下，将对原始大矩阵的分解变成对这个低维矩阵的分解，大幅降低了时间复杂度，减少了对内存的使用率的同时增加了算法的稳定性。
关键词： 主成分分析；贪心算法；卷数据降维矩阵；时间复杂度

　自从1986年美国人提出PCA[1]的有关思想以后，PCA就成了一个强有力的工具。由于PCA具有最大化方差、最小化冗余、最小化损失等优良特性，它可以广泛地应用在多源融合、数据降维、模式识别以及分析数据互相关性等方面。如最近发表的基于小波和PCA的火炮输弹系统故障诊断研究[2]和基于L2，1范数的PCA维数约简算法[3]，PCA在其中起了提取主元和维数约简预处理的重要作用。虽然以后出现了大量的其他方法，如CMS[4]、RP[5]和一些非线性的算法，如Isomap[6]、LLE[7]、LTSA[8]等算法，并广泛地应用在各个领域，如机器学习、图像检索、模式识别和人工智能等方面。但是PCA作为一种基本的线性方法，其地位是其他方法所无法比拟的。
　近年来，由于计算机技术高速发展，各种数据量以指数级的速度增加，各种大规模数据广泛地出现在各个计算机领域，如图像处理中的图像的分辨度越来越高，数据库也越来越大。但是目前计算机硬件的发展仍然满足不了数据处理的要求。比如在人脸识别中，图像的尺寸为128×128，而整个图片集又有3 000张，那么在图像分类中把图片当成一个列的大矩阵的尺寸将是16 384×3 000，这是非常大的矩阵，计算复杂度高，其中最费时部分就是在最后一步分解矩阵来求得特征向量和特征值。鉴于此提出了一种基于贪心算法[7-8]的快速算法——贪心快速主成分分析，简称PCA-G。该算法在保持与PCA相同的处理效果的同时，降低了时间复杂度，增加了算法稳定性减少了内存使用率，从而使计算时间大大缩短。
1 PCA算法简述
　统计学上PCA的定义为：用几个较少的综合指标来代替原来较多的指标，而这些较少的综合指标既能尽量多地反映原来较多指标的有用信息，且相互之间又是无关的。作为一种建立在统计最优原则基础上的分析方法，主成分分析具有较长的发展历史。在1901年，Pearson首先将变换引入生物学领域，并重新对线性回归进行了分析，得出了变换的一种新形式。Hotelling于1933年则将其与心理测验学领域联系起来，把离散变量转变为无关联系数。在概率论理论建立的同时，主成分分析又单独出现，由Karhunen于1947年提出，随后Loeve于1963年将其归纳总结。因此，主成分分析也被称为K-L变换。
PCA运算就是一种确定一个坐标系统的直交变换，在这个新的坐标系统下，变换数据点的方差沿新的坐标轴得到了最大化。这些坐标轴经常被称为是主成分。PCA运算是一个利用了数据集的统计性质的特征空间变换，这种变换在无损或很少损失数据集信息的情况下降低了数据集的维数。


1.2 主成分分析的实现步骤
　基于上述主成分分析的基本原理，可以得出主成分分析的计算步骤如下所示：
　（1）将所获得的n个指标（每一指标有m个样品）的一批数据写成一个（m×n）维数据矩阵：
　
2 基于贪心算法的PCA快速算法
　从式（4）可以看出PCA主要是求样本协方差矩阵的特征向量和特征值。所以在程序中PCA就转化为对原始矩阵的SVD分解或者是特征分解。且PCA最费时的就在这一步，针对这一步矩阵分解做出改进。正如现在矩阵正变得越来越大，当矩阵的行数和列数都很大时，无论如何变换矩阵，能降低的时间复杂度都是非常有限的。一般PCA的时间复杂度可以达到O（n3）[9]（其中n为协方差矩阵的行数），所以在遇到行数和列数都很大的协方差矩阵分解时往往很费时。但是要求的往往只是整个矩阵分解出来的几个特征值或者特征向量，于是找到一个低维矩阵，它保持了降维核上各点距离不变的性质，使最后分解出来的主要特征值和特征向量与原始高维矩阵分解出的主要特征值和特征向量相等。
　算法分为以下三步：


3 时间复杂度分析
　标准的PCA内置Matlab代码中eigs函数的时间复杂度高达O（n3）（其中n为协方差矩阵的行数），算法中第一步的时间复杂度等价于O（n），第二步的时间复杂度为O（m2×n），第三步为m2×n，所以总的时间复杂度为O（n2），而标准的SVD算法时间复杂度为O（n3），所以算法时间复杂度要比标准的算法低一阶。
4 实验对比
　所有的实验都是在惠普康柏笔记本上进行的，它的配置是Intel（R）core（TM）i3 M330 2.13 GHz，内存是2 GB，操作系统是Windows 7旗舰版7.0，算法由matlab实现。实验主要用来计算算法在各种大规模矩阵上计算的快速性，用随机函数产生n×n矩阵来衡量计算所需要的运行时间。为了进行实验，使每次计算的n取不同值，且m的值应远大于d的值，以保证矩阵充分保留了原矩阵的某些特征。这里的d和m取不同的值。在此情况下比较了新算法和标准PCA算法在保证矩阵分解质量前提下的快速性。实验结果如表1~表12所示。
5 实验分析与结论
　可以从实验中看到以下几点：
　（1）当矩阵规模比较大时，当n在3 000甚至以上时（见表1~表4），算法在保持分解质量即特征值不变（篇幅有限取最大的前三个）的前提下，速度至少比标准的PCA算法快一倍多。

　（2）当所构建的低维空间的维数减小时，如小于12倍的d（见表5~表8），尽管此时运算速度会加快，但是与标准算法相比会出现偏差，当运算精度要求不高，运算时间比较珍贵时，可以采取此法。

　（3）当矩阵规模较小时（见表9~表12），算法和标准PCA差别不大，而当构造空间维数降低时，偏差同样会出现。
　通过以上分析可以看出，算法在应用到大规模矩阵时（尤其n当大于3 000时）优越性比较明显，能明显地加快算法的处理速度。所以在数据规模越来越大的今天，快速算法有广泛的用武之地。
参考文献
[1] JOLLIFFE I T． Principal Component Analysis[M]． New York， USA： Springer-Verlag，1986.
[2] 张鹏军，薄玉成，王惠源，等.基于小波和ＰＣＡ的火炮输弹系统故障诊断研究[J].计算机工程与设计，2012，33（12）：4746-4750.
[3] 刘丽敏，樊晓平，廖志芳，等.一种基于Ｌ２，１范数的ＰＣＡ维数约简算法[J].计算机应用与研究，2012，30（1），39-41.
[4] YOUNG F W. Encyclopedia of statistical sciences[J]. Multidimensio-nal scaling. John Wiley & Sons，Inc，1985，5.
[5] ACHLIOPTAS D. Database-friendly random projections[C]. Proc.20th PODS，2001.
[6] TENENBAUM J B， DE SILVA V， LANGFORD J C. A global geometric framework for nonlinear dimensionality reduction. Science[J]. 2000，290（5500）：2319-2323.
[7] ROWEIS S T， SAUL L K. Nonlinear dimensionality reduction by locally linear embedding[J]. Science 2000，290（5500），2323-2326.
[8] ZHANG Z Y， ZHA H Y. Principal manifolds and nonlinear dimensionality reduction via tangent space alignment[J]. SIAM J.Sci.Comput， 2004，26（1）：313-338.
[9] WANG J. Geometric structure of high-dimensional data and dimensionality reduction[M]. Springer， 2012.
[10] CHUI C， WANG J. Dimensionality reduction of hyper-spectral imagery data for feature classification[C]. In：W.Freeden， Z. Nashed， T. Sonar（eds.） handbook of Geomathematics.Springer，berlin，2010.
[11] CHUI C， WANG J. Randomized anisotropic transform for nonlinear dimensionality reduction[J]. International Journal on Geomathematics，2010，1（1）：23-50.