数据降维（PCA、KPCA、PPCA）及C++实现

1、何为数据降维

1.1维数灾难：往往满足采样条件所需的样本数目巨大、样本稀疏、距离计算困难。

1.2降维：利用数学变换将原始高维属性空间转变为低维“子空间”，即在高维采样数据中提取能够表达原始数据的特征。

1.3 降维优点：数据集更易懂、使用和显示；降低算法计算开销；去除噪声。 2、一些降维算法

Principal Component Analysis （PCA）

Linear Discriminant Analysis（LDA）

Locally linear embedding（LLE）

Laplacian Eigenmaps

本文主要针对以下三种算法：

2.1 PCA：PCA算法是一种线性投影技术，利用降维后使数据的方差最大原则保留尽可能多的信息；

2.2 KPCA：PCA仅考虑了数据的二阶统计信息，而没有利用高阶统计信息，忽略了数据的非线性相关性，而KPCA，通过非线性变换将数据映射到了高维，在高维空间中进行特征提取，获得了更好的特征提取性能；

2.3 PPCA：PCA没有将数据的概率分布考虑，PPCA对PCA做了概率上的解释，延伸了PCA算法。

总之：PPCA和KPCA都是针对PCA算法的缺陷，做出了不同方向上的改进。 3 PCA、KPCA、PPCA算法步骤

3.1 PCA： 数据在低维线性空间上的正交投影，这个线性空间被称为主子空间，使得投影数据的方差被最大化。

》将原始数据按列组成n行m列矩阵X；

》将X的每一行（代表一个属性字段）进行零均值化，即减去这一行的均值；

》求出协方差矩阵C；

》求出协方差矩阵的特征值及对应的特征向量；

》将特征向量按对应特征值大小从上到下按行排列成矩阵，取前k行组成矩阵P；

》Y=PX即为降维到k维后的数据。

3.2 KPCA：通过使用一个非线性核替换线性的方式来对高维数据向低维投影。

》将原始数据按列组成m行n列矩阵X；

》计算核矩阵，先选定高斯径向核函数中的参数，计算核矩阵K，修正核矩阵得到KL；

》求出协方差矩阵C，运用雅可比迭代方法计算KL特征值与特征向量；

》将特征向量按对应特征值大小从上到下按行排列成矩阵，取前k行组成矩阵；

》通过施密特正交化方法单位正交化特征向量得到P；

》Y=PX即为降维到k维后的数据。

3.3 PPCA：PPCA是一种考虑每个变量概率分布的方法，在确定主元和误差的概率函数后，通过期望最大（EM）算法建立模型。

》将原始数据按列组成n行m列矩阵；

》对原始训练样本数据进行标准中心化处理得到X；

》在隐含变量x 的条件下得到观测数据的概率分布；

》通过EM 算法获得概率PCA 的模型参数W(因子矩阵)和方差；

》舍去不满足因子矩阵与方差特定关系的归一化数据；

》剩余满足条件数据即为降维到k维后的数据。 4、C++实现PCA、KPCA

（环境：Visual Studio 2013）

pca.h

    #include         #include         #include         #include         #include         #include     using namespace std;           typedef struct sourcedata      //声明了一个原始数据类型     {         int m;         int n;         double **data;     }SourceData;     class PCA     {     public:         PCA(int m, int n);                                //m为行数，n为列数             SourceData getdata(const  char *file);           //获取外部数据         void standarddata(double **a);                  //数据标准化         double  product(double *a, double *b);         //向量乘积         void  swap(double &x, double &y);             //数据交换         double  **matrixproduct(double **a);            //求解协方差矩阵         void  selectionsort(double *A, double **v);     //特征值排序         void  zhengjiao(double **v);                   //向量正交化         int jcb(double **a, double **v, double eps, int jt);         //求解特征值和特征向量         int selectcharactor(double *A, double getratio, double *B); //提取主分量         double  **getProject(int t, double **x, double **v);        //计算降维后特征点           void   saveProject(const char *projectfile, double **project, int t); //保存         ~PCA(){}     private:         int  rows;         int columns;     };

kpca.h

    #include     #include     #include     #include     #include     #include     #include     #include     using namespace std;           class KPCA     {     public:         KPCA(int m, int n);         SourceData getdata(const char *file); //获取外部数据         int randdef(int n1, int n2); //生成n1到n2随机整数         double getvar(double **testdata, int m, int n, int l, double left, double right);//通过对随机样本的最大特征提取效率获取高斯径向基函数的参数         double product(double *a, double *b, int size);  //向量乘积         double kernel(double var, double *x, double *y, int sign);  //核函数定义         double **getkernelmatrix(double **a, double var, int sign); //获取核矩阵         double **modifykernelmatrix(double **K);  //修正核矩阵         int jcb(double **a, double **v, double eps, int jt);    //求解矩阵的特征值和特征向量             void zhengjiao(double **v); //正交化特征向量         void swap(double &x, double &y); //交换元素         void selectionsort(double *A, double **v);  //特征值和特征向量选择排序         void saveeigenvectors(double A[], double **v, const char *vectorfile);//保存特征值和特征向量         int selectcharactor(double *A, double getratio, double *B);  //提取特征         double  **getProject(int t, double **x, double **v);  //获得投影         void saveProject(const char *projectfile, double **project, int t);  //保存投影         ~KPCA(){}     private:         int  rows;         int columns;     };

pca.cpp与kpca.cpp由于篇幅问题未分享，有意者邮箱：1490217008@qq.com或https://download.csdn.net/download/u010442908/10628230

main.cpp

    #include"pca.h"         #include"kpca.h"     void main()     {         //pca               cout