———— 此时相望不相闻,愿逐月华流照君。

主成分分析 (Principal Component Analysis)

主成分分析 (Principal Component Analysis, PCA) 是⼀种被⼴泛应⽤于维度降低、数据压缩、特征提取等领域的方法,顾名思义,它的主要作用就是能够提取出数据中的主要成分或信息,一般可以通过映射到其他空间来实现,因此具有以上应用,它也被称为 Karhunen-Loève 变换。

主成分分析有两种常用定义,但是其算法思路大致相同。首先,主成分分析可以被定义为数据在低维线性空间上的正交投影,这个线性空间被称为主⼦空间 (principal subspace),使得投影数据的⽅差被最⼤化,便于区分。另一种定义是使平均投影代价最⼩的线性投影,平均投影代价是指数据点和它们的投影之间的平均平⽅距离。如下图所示,正交投影寻找⼀个低维空间作为主⼦平⾯,⽤紫⾊的线表示,使得红色数据点在⼦空间上的正交投影能够最⼤化绿色投影点的⽅差;另⼀个是基于投影误差的平⽅和的最⼩值,⽤蓝线表示。

图片来自 Bishop PRML. Figure 12.1.

1. 最大方差形式

考虑⼀组观测数据集 [公式] ,其中 [公式]  [公式] 是⼀个 [公式] 维空间中的向量。我们的⽬标是将数据投影到维度 [公式] 的空间中,同时最⼤化投影数据的⽅差。⾸先考虑在⼀维空间 [公式] 上的投影,使⽤ [公式] 维向量 [公式] 定义这个空间的⽅向,由于我们只对向量的方向感兴趣,不失一般性,假定选择⼀个单位向量,从⽽ [公式] 。这样,每个数据点 [公式] 被投影到标量值 [公式] 上,投影数据的均值是 [公式]  [公式] 是样本集合的均值,形式为

[公式]

投影数据的⽅差为

[公式]

其中 [公式] 是数据的协⽅差矩阵,定义为

[公式]

现在关于 [公式] 最⼤化投影⽅差 [公式] ,选择单位向量也是为了避免出现 [公式] ,因此引入单位向量归一化条件作为限制,有了这个限制,就可以很自然地引入拉格朗日乘数法,记作 [公式] ,然后对下式进⾏最⼤化

[公式]

通过令它关于 [公式] 的导数等于零,可以看到驻点满⾜

[公式]

这表明 [公式]  [公式] 的⼀个特征向量,如果左乘 [公式] ,根据限制条件,⽅差为

[公式]

因此当 [公式] 设置为与具有最⼤的特征值 [公式] 的特征向量相等时,⽅差会达到最⼤值,这个特征向量被称为第⼀主成分。

对于额外的主成分,如果我们考虑 [公式] 维投影空间的⼀般情形,那么最⼤化投影数据⽅差的最优线性投影由数据协⽅差矩阵 [公式]  [公式] 个特征向量 [公式] 定义,对应于 [公式] 个最⼤的特征值 [公式] ,根据特征值大小依次选择为主成分的方向。

主成分分析涉及到计算数据集的均值 [公式] 和协⽅差矩阵 [公式] ,然后寻找 [公式] 对应于 [公式] 个最⼤特征值的 [公式] 个特征向量。计算⼀个 [公式] 矩阵的特征向量分解的复杂度为 [公式] 。如果将数据投影到前 [公式] 个主成分中,我们只需寻找前 [公式] 个特征值和特征向量,这可以使⽤更⾼效的⽅法,例如幂⽅法或 EM 算法。

2. 最小误差形式

现在讨论主成分分析基于误差最⼩化投影的形式,引⼊ [公式] 维基向量的⼀个完整的单位正交集合 [公式] ,其中 [公式] ,并满⾜

[公式]

每个数据点可以精确地表示为基向量的⼀个线性组合,即

[公式]

其中,系数 [公式] 对于不同的数据点来说是不同的。这对应于将坐标系旋转到了⼀个由 [公式] 定义的新坐标系,原始 [公式] 个分量 [公式] 被替换为⼀个等价的集合 [公式] 。与 [公式] 做内积,然后使⽤单位正交性质,有 [公式] ,不失⼀般性,有

[公式]

我们的⽬标是使⽤限定数量 [公式] 个变量的⼀种表示⽅法来近似数据点,这对应于低维⼦空间上的⼀个投影, [公式] 维线性⼦空间可以⽤前 [公式] 个基向量表示,因此可以⽤下式来近似每个数据点

[公式]

其中 [公式] 依赖于特定数据点,⽽ [公式] 是常数,对所有数据点都相同。我们可以任意选择 [公式]  [公式]  [公式] ,从⽽最⼩化维度降低引⼊的失真。作为失真的度量,我们使⽤原始数据点与它的近似点 [公式] 之间的平⽅距离,然后在数据集上取平均。因此最⼩化

[公式]

⾸先考虑关于 [公式] 的最⼩化,消去 [公式] ,令它关于 [公式] 的导数为零,然后使⽤单位正交条件,有

[公式]

 [公式] 关于 [公式] 的导数等于零,再次使⽤单位正交,有

[公式]

消去公式 (10) 中的 [公式]  [公式] ,使⽤⼀般的展开式 (9),有

[公式]

可以看到,从 [公式]  [公式] 的位移向量位于与主⼦空间垂直的空间中,因为它是 [公式] 的线性组合,其中 [公式] ,而主子空间的投影向量由前 [公式] 个基向量线性组合而成,在后面空间上的分量为 0。投影点⼀定位于主⼦空间内,最⼩误差由正交投影给出。于是可以得到失真度量 [公式] 的表达式,它是⼀个关于 [公式] 的函数,形式为

[公式]

最后是关于 [公式]  [公式] 最⼩化,同样需要单位正交条件限制 [公式] 的绝对值大小,同之前一样,解可以表示为协⽅差矩阵的特征向量展开式。先考虑⼆维数据空间 [公式] 以及⼀维主⼦空间 [公式] 的情形,选择⼀个⽅向 [公式] 来最⼩化 [公式] ,同时满⾜限制条件 [公式] 。使⽤拉格朗⽇乘数 [公式] 引入这个限制,最⼩化

[公式]

令关于 [公式] 的导数为零,有 [公式] ,从⽽ [公式]  [公式] 的⼀个特征向量,且特征值为 [公式] 。因此任何特征向量都会定义失真度量的⼀个驻点,为了找到 [公式] 在最⼩值,将 [公式] 的解代回失真度量中,得到 [公式] 。于是通过将 [公式] 选择为特征值较⼩的特征向量,就可以得到 [公式] 的最⼩值。因此,应该将主⼦空间与具有较⼤特征值的特征向量对齐,即为了最⼩化平均平⽅投影距离,应将主成分⼦空间选为穿过数据点的均值且与最⼤⽅差⽅向对齐。对于特征值相等的情形,任何主⽅向的选择都会得到同样的 [公式] 值。 对于任意的 [公式]  [公式] ,最⼩化 [公式] 的⼀般解都可以通过将 [公式] 选择为协⽅差矩阵特征向量的⽅式得到,即

[公式]

其中 [公式] ,特征向量 [公式] 单位正交,失真度量的值为

[公式]

这就是与主⼦空间正交的特征值的加和。通过将这些特征向量选择成 [公式] 个最⼩的特征值对应的特征向量,来得到 [公式] 的最⼩值,并且定义了主⼦空间的特征向量是对应于 [公式] 个最⼤特征值的特征向量。

虽然已经考虑了 [公式] 的情形,但主成分分析对于 [公式] 的情形仍然成⽴,这种情况下没有维度的降低,仅仅是将坐标轴旋转,与主成分对齐即可。

3. 高维数据主成分分析

在主成分分析的⼀些应⽤中,数据点的数量⼩于数据空间的维度。例如将主成分分析应⽤于⼏百张图⽚组成的数据集,每个图⽚对应于⼏万维空间中的⼀个向量。在⼀个 [公式] 维空间中, [公式] 个数据点 [公式] 定义了⼀个线性⼦空间, 它的维度最多为 [公式] ,因此在使⽤主成分分析时,⼏乎没有 [公式] 的数据点。在主成分分析中,⾄少有 [公式] 个特征值为零,对应于沿着数据集⽅差为零⽅向的特征向量。此外,寻找 [公式] 矩阵的特征向量的算法复杂度为 [公式] ,因此对于诸如图像这种应⽤来说,直接应⽤主成分分析算法是不可⾏的。

可以这样解决这个问题,⾸先,将 [公式] 定义为 [公式] 维中⼼数据矩阵,它的第 [公式] ⾏为 [公式] ,这样协⽅差矩阵可以写成 [公式] ,对应特征向量⽅程变成了

[公式]

将两侧左乘 [公式] ,可得

[公式]

定义 [公式] ,有

[公式]

它是 [公式] 矩阵 [公式] 的⼀个特征向量⽅程。这个矩阵与原始协⽅差矩阵具有相同的 [公式] 个特征值,原始协⽅差矩阵本⾝有额外的 [公式] 个值为零的特征值,因此可以在低维空间中解决特征向量问题,计算复杂度为 [公式] ⽽不是 [公式] 。为了确定特征向量,将公式 (21) 两侧乘以 [公式] ,可得

[公式]

从中可以看到 [公式]  [公式] 的⼀个特征向量,对应特征值为 [公式] ,这些特征向量的长度未必等于 1。为了确定合适的归⼀化,我们使⽤⼀个常数来对 [公式] 进⾏标度,使得 [公式] 。假设 [公式] 的长度已经被归⼀化,那么有

[公式]

在高维空间应用主成分分析方法的思路就是先计算 [公式] ,然后找到其特征值和特征向量,最后再计算原始数据空间的特征向量。