3.1 特征规约算法原理介绍

特征规约算法在原理上大同小异，大体思路都是提取特征矩阵的某种特征数据，比如特征值、奇异值等。然后对这些特征数据做某些微调，去掉不必要的部分，最后基于特征数据还原简化了的特征矩阵，从而达到了规约的效果。

3.1.1 特征规约算法思想

特征规约算法的思想大体类似，本节先以PCA算法为例，介绍其算法思想。

PCA（Principal Component Analysis）即主成分分析，是一种将高维数据降维，然后在低维空间中尽可能地表示原始数据的降维方法，有很多典型的应用，比如图像识别。

假设有m个样本组成的样本集，每个样本都是N维数据，如果要将其降为r（小于n）维，从几何上理解就是将原有含n个坐标轴的坐标系进行坐标变换，得到新的含r个坐标轴的坐标系，将m个点置于新坐标系中，用r个坐标轴方向来表示它们。从代数上理解，就是将样本各维度（n维）的协方差矩阵（n×n）转为新协方差矩阵（r×r），且其具有对角矩阵形式。

进行坐标变换后，PCA的目的就是使得样本点在这些新坐标轴上的投影点尽量分散，分散程度可以用方差来表示。PCA把投影点方差最大的方向（坐标轴）定义为第一个主轴，记为PC₁，按正交方向和方差大小依次排列，分别为PC₂,PC₃,…,PC_r，这r个主成分为规约后的新特征。

3.1.2 特征规约算法流程

本节将以PCA算法为例，介绍特征规约算法的流程，具体如下。

1）将原始数据X组成n行m列的矩阵，其中n是维数、m是数据量。

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

3）求出协方差矩阵C（n×n维）：

4）求出协方差矩阵的特征值及特征向量。

5）将特征向量按对应特征值的大小从上到下按行排列成矩阵，取前r行组成矩阵W（r×n维）。

6）对原始数据X中的每一列数据，求其在r个主成分空间中的坐标WX（r×m），即降到r维后的数据，每一行是其一个属性字段，每一列是一个样本数据。

3.1.3 PCA算法及相关矩阵分解

本节将介绍几种与PCA算法不同的特征规约算法，并比较这几种算法之间的异同。

1.特征值分解（EVD）

主成分分析先针对原数据的各个变量求出协方差矩阵，对这个协方差矩阵（对称矩阵）求解特征值和特征向量的方法，称为特征值分解（EVD），其具体原理如下。

假设存在m×m的满秩矩阵X，它有m个特征值λ_i，按照特征值从大到小排列，对应的单位特征向量设为w_i，则根据特征向量与特征值的定义：

令：

则：

可得到X的特征值分解（由于W中的特征向量两两正交，因此W为正交矩阵）：

以上步骤使得W从右乘变为左乘，以符合前文中的坐标转换矩阵的用法。由式（3-6）可以得到：

式（3-7）中左右两边各取前r（r≤m）个特征向量，可以得到：

由此，通过特征值分解的方法得到了主成分分析所用到的转换矩阵：

2.奇异值分解（SVD）

上述特征值分解只对方阵有效，而奇异值分解（SVD）是一个能适用于任意矩阵的分解方法，它是特征值分解的一般化。假设X是一个n×m的矩阵，定义矩阵X的SVD为：

X =UΣVT

得到的U是一个n×n的方阵（里面的向量是正交的，U里面的向量称为左奇异向量），Σ是一个n×m的矩阵（除了对角线的元素都是0，对角线上的元素称为奇异值），VT （V的转置）是一个m×m的矩阵（里面的向量也是正交的，V里面的向量称为右奇异向量）。

那么如何求出U和V?

首先将XT与X矩阵相乘，得到m×m的方阵XTX，对其求特征值，如下：

只取u使得其为单位化后的向量。

将XTu_i单位化，先计算向量XTu_i的模长：

所以有： ｜XTu_i｜2 =λ_i， 取单位向量， 因此有：

其中σ_i=。

对于X来说，如果其秩为r（r≤min（m,n）），则上式中的i=1,2,…,r。这里得到σi就是矩阵X的奇异值，其中v就是X的右奇异向量，u就是X的左奇异向量，则可以得到：

为了得到完整的矩阵V，当r<i≤n时，对{v₁,v₂,…,v_r}扩展，求出{v_r+1,v_r+2,…,v_m}，即扩展成{v₁,v₂,…,v_m}m维空间的单位正交基。即在XTX的零特征值对应的特征向量空间中选取{v_r+1,v_r+2,…,v_m}，使得（XTX）v_i=0。

为了得到U，同样对{u₁,u₂,…,u_r}进行扩展，求出{u_r+1,u_r+2,…,u_n},使得{u₁,u₂,…,u_n}为n维空间中的一组正交基。

对式 （3-10） 左乘X再结合式 （3-12）， 可得X（XTX）v_i=λ_iX v_i⇒（X XT）u_i=λ_iu_i， 所以u_i是X XT的特征向量。 即在X XT的零特征值对应的特征向量空间中选取{u_r+1，u_r+2，…，u_n}，使得（XTX）u_i=0。 得到了U和V， 再由式 （3-12） 可得到：

因为：

又因为：

其中［v₁,v₂,…,v_r|v_r+1,…,v_m］-1=［v₁,v₂,…,v_r|v_r+1,…,v_m］T，从而可以得到矩阵X的奇异值分解：

其中U是一个n×n的正交阵，V是一个m×m的正交阵，Σ是一个n×m的对角阵。

再回顾以上过程， 以另外一种角度来解读奇异值分解， 会发现由于（XTX）v_i=λ_iv_i， 即v_i是XTX的特征向量； 由于X（XTX）v_i=λ_iXv_i⇒（X XT）u_i=λ_iu_i， 即u_i是X XT的特征向量。 而且， 也就是说作为XTX的对应于λ_i的特征向量v_i， 和作为XXT的对应于λ_i的特征向量u_i之间存在着的关系。 为什么会有这样的关系? 这里可以拆分为两个问题， 首先， 为什么λ_i既是XTX也是XXT的特征值? 其次， 为什么两者之间对应同样的特征值的特征向量v_i和u_i之间存在一定的关系?

针对第一个问题，有这样的一般化的性质，即：假设X是一个m×n的矩阵，则XT是一个n×m的矩阵，XTX和XXT有相同的非零特征值，下面给出证明。

首先证明r（XTX）=r（XXT）。

如果Xw=0，则XTXw=0，所以Xw=0的解都为XTXw=0的解。

如果XTXw =0， 两边同乘以wT可得： wTXTXw =0⇒（Xw）TXw =0， 即||Xw||=0。 所以Xw=0。 所以XTXw=0的解都为Xw=0的解。

所以Xw=0和XTXw=0有相同的解空间，所以r（XTX）=r（XXT）；同理r（XTX）=r（XXT），所以r（X）=r（XTX）=r（XXT）=r（XT）。

下面证明非零特征值相同。

假设w是XTX对应特征值λ的特征向量，则有（XTX）w=λw。两边同乘以X，得到（XXT）Xw=λXw，因此Xw是XXT对应于特征值λ的特征向量。因此可知XTX和XXT有相同的非零特征值。

针对第二个问题，由于我们已经知道XTX和XXT有相同的非零特征值。那么在求XTX的特征向量时只取v使得其为单位化后的向量，假设对应v的特征值为λ_i，那么XXT对应于特征值λ_i的特征向量u应该符合（XXT）u=λ_iu，同时因为（XTX）v=λ_iv，所以上式左乘X有（XXT）Xv=λ_iXv， 由此可知Xv就是XXT对应特征值λ_i的特征向量。 因此u∝Xv， 所以u可以取成。而Xv × Xv=（Xv）TXv=vTXTXv=vTλ_iv=λ_i， 因此， 因此对于每一个u_i和v_i，都有， 所以USVT=X， 奇异值分解得证。

3.特征值分解（EVD）和奇异值分解（SVD）的关联

PCA的全部工作简单点说，就是对原始的空间中顺序地找一组相互正交的坐标轴，第1个轴是使得方差最大的，第2个轴是在与第1个轴正交的平面中使得方差最大的，第3个轴是在与第1、2个轴正交的平面中方差最大的，这样假设在N维空间中，我们可以找到N个这样的坐标轴，取前r个去近似这个空间，这样就从一个N维的空间压缩到r维的空间了，但是我们选择的r个坐标轴能够使空间压缩，且使得数据的损失最小。

那么PCA在求解这个r个坐标轴时，自然而然采用的是特征值分解（EVD）。特征值分解的本质就是任何满秩方阵都可以分解对角阵和两个正交阵相乘。但是我们从奇异值分解知道，任何矩阵都可以进行奇异值分解为一个秩为r的矩阵和两个方阵相乘。那么特征值分解如何与奇异值分解对应起来?

回顾特征值分解中提到的一个结论，就是满秩m×m的矩阵X，可以得到特征向量组成的r ×m矩阵， 使得：

根据基变换的矩阵表示方式，上式可以理解为X（m×m）中的每一个样本（每一列为一个样本）经过W（r×m）这个坐标转换矩阵的转换，得到了所有m个样本在新的坐标空间中坐标表示，即Y（r×m），Y中每一列为一个样本，一共m列；每一样本含r个变量。

同样，对于一个n×m的矩阵X（每一列表示一个样本，每一行表示一个feature），PCA的流程告诉我们，可以先找到满秩协方差矩阵C（n×n），通过特征值分解求得r×n的坐标变换矩阵； 然后用W将原矩阵X进行坐标轴的变化， 将X转化为Y （ r × m）。

即：

而由之前SVD的过程可知：

对上式等式左右同时左乘U的转置UT_r×n：

上式因为U_{n × r}的每一列都是单位向量， 所以是单位矩阵。

将式（3-20）与式（3-18）对照发现，其实UT就是W，也就是一个用于坐标变化的向量。这里是将一个n×m的矩阵压缩到一个r×m的矩阵，也就是对行进行压缩，如果想对列进行压缩（在PCA的观点下，对列进行压缩可以理解为将一些相似的样本点合并在一起，或者将一些没有太大价值的样本点去掉），该怎么办呢?同样可以写出一个通用的列压缩例子：

式（3-21）就把一个m列的矩阵压缩到一个r列的矩阵了，对SVD来说也是一样的，对SVD分解的式（3-19）两边右乘以V：

这样就得到了对列进行压缩的式子。可以看出，其实PCA几乎可以说是对SVD的一个包装，如果实现了SVD，也就实现了PCA。而且更好的地方是，有了SVD，就可以得到两个方向的PCA，如果对XTX进行特征值分解，只能得到一个方向的PCA。

4.交替最小二乘（ALS）原理

交替最小二乘（Alternating Least Squares）常用于基于矩阵分解的推荐系统中。例如：将用户（user）对商品（item）的评分矩阵分解为两个矩阵，一个是用户对商品隐含特征的偏好矩阵，另一个是商品所包含的隐含特征的矩阵。在这个矩阵分解的过程中，评分缺失项得到了填充，也就是说我们可以基于这个填充的评分来给用户最优商品推荐。

由于评分数据中有大量的缺失项，传统的矩阵分解SVD（奇异值分解）不方便处理这个问题，而ALS能够很好地解决这个问题。对于R（m×n）的矩阵，ALS旨在找到两个低维矩阵X（k×m）和矩阵Y（k×n），来近似逼近R（m×n），即：

其中R（ m × n） 代表用户对商品的评分矩阵， X（ m × k） 代表用户对隐含特征的偏好矩阵， Y（ n × k） 表示商品所包含隐含特征的矩阵， T 表示矩阵X的转置。 实际中， 一般取k≪min （ m，n） ， 也就是相当于降维了。 这里所说的低维矩阵， 有的地方也叫低秩矩阵。

为了找到使低秩矩阵X和Y尽可能地逼近R，需要最小化下面的平方误差损失函数：

其中x_u（k×1）表示用户u的偏好的隐含特征向量，y_i（k×1）表示商品i包含的隐含特征向量， r_u，i（ m × n）表示用户u对商品i的评分， 内积是用户u对商品i的评分的近似。

损失函数一般需要加入正则化项来避免过拟合等问题，我们使用L2正则化，所以上面的公式改造为：

其中，λ是正则化项的系数。

由于变量和y_i耦合到一起， 这个问题并不好求解， 所以引入了ALS， 也就是说可以先固定Y （例如随机初始化Y）， 然后利用公式 （3-25） 先求解X， 接着固定X， 再求解Y， 如此交替往复直至收敛， 即所谓的交替最小二乘法求解法。 具体求解方法说明如下。

1）固定Y，将损失函数L（X,Y）对x_u求偏导，并令导数=0，得到：

令：

2）同理，固定X，可得：

令：

3）迭代步骤如下。

首先随机初始化Y，利用式（3-27）更新得到X，利用式（3-29）更新Y。然后判断均方根误差（RMSE）是否小于一定的阈值，或者判断迭代次数是否达到预先设定值，如果满足其中的一条则认为X,Y分解完毕。

r_ui（矩阵R（m×n）的元素）表示用户u对商品i的评分，是一个数。

得到X，Y后， 令， R_n×k=， L和R就是对应于代码中的L和R。 接下去对L、 R进行变换， 使得L中的所有样本均值为0 ， 即：

同时L中所有样本各个维度之间的协方差矩阵为对角阵，即：

L _i 代表矩阵L的第i行，是所有L_i的平均行向量， diag（ s）是对角阵， 其中的每个对角线元素s_i分别对应L中一列L_i的方差。

另外，还需要使变换后R的各列互相正交，且每个列向量均为单位向量，即：

为了实现上述目标，可由下述步骤实现：

对L进行中心化：， 其中。

对L和R进行调整：

其中U、D_x通过对RTR进行特征值分解得到，分别为特征向量矩阵和特征值矩阵，RTR=UD_xUT； V也通过特征值分解得到，=VD_wVT；

由此可知新的L和R满足式（3-32）和式（3-33）两个条件，因为：