亚洲精品色哟哟,人妻福利导航

2.11 PCA的算法原理和流程

基于最小投影距離為評(píng)價(jià)指標(biāo)推理：

假設(shè)數(shù)據(jù)集是 $m$ 個(gè) $n$ 維數(shù)據(jù)， $(x^{(1)}, x^{(2)},...,x^{(m)})$ ，也就是默認(rèn)為 $n$ 行 $m$ 列的矩陣。這個(gè)矩陣的數(shù)據(jù)已經(jīng)進(jìn)行了中心化。經(jīng)過(guò)投影變換得到新坐標(biāo)為 ${w_1,w_2,...,w_{n'}}$ ，其中 $w$ 是標(biāo)準(zhǔn)正交基，即 $| w |_2 = 1$ ， $w^T_iw_j = 0$ 。

降維
?經(jīng)過(guò)降維后，新坐標(biāo)為 ${ w_1,w_2,...,w_{n'} }$ ，其中 $n'$ 是降維后的目標(biāo)維數(shù)。樣本點(diǎn) $x^{(i)}$ 在新坐標(biāo)系下的投影為 $z^{(i)} = \left(z^{(i)}_1, z^{(i)}_2, ..., z^{(i)}_{n'} \right)$ ，其中 $z^{(i)}_j = w^T_j x^{(i)}$ 是 $x^{(i)}$ 在低維坐標(biāo)系里第 $j$ 維的坐標(biāo)值。
升維
?如果用 $z^{(i)}$ 去恢復(fù) $x^{(i)}$ ，則得到的恢復(fù)數(shù)據(jù)為 $\widehat{x}^{(i)} = \sum^{n'}_{j=1} x^{(i)}_j w_j = Wz^{(i)}$ ，其中 $W$ 為標(biāo)準(zhǔn)正交基組成的矩陣。

?考慮到整個(gè)樣本集，樣本點(diǎn)到這個(gè)超平面的距離足夠近，目標(biāo)變?yōu)樽钚』? $\sum^m_{i=1} | \hat{x}^{(i)} - x^{(i)} |^2_2$ 。對(duì)此式進(jìn)行推理，可得：

$\begin{aligned} \sum^m_{i=1} | \hat{x}^{(i)} - x^{(i)} |^2_2 &= \sum^m_{i=1} | Wz^{(i)} - x^{(i)} |^2_2 \\ &= \sum^m_{i=1} \left( Wz^{(i)} \right)^T \left( Wz^{(i)} \right) - 2\sum^m_{i=1} \left( Wz^{(i)} \right)^T x^{(i)} + \sum^m_{i=1} \left( x^{(i)} \right)^T x^{(i)} \\ &= \sum^m_{i=1} \left( z^{(i)} \right)^T \left( z^{(i)} \right) - 2\sum^m_{i=1} \left( z^{(i)} \right)^T z^{(i)} + \sum^m_{i=1} \left( x^{(i)} \right)^T x^{(i)} \\ &= - \sum^m_{i=1} \left( z^{(i)} \right)^T z^{(i)} + \sum^m_{i=1} \left( x^{(i)} \right)^T x^{(i)} \\ &= -tr \left( W^T \left( \sum^m_{i=1} x^{(i)} \left( x^{(i)} \right)^T \right)W \right) + \sum^m_{i=1} \left( x^{(i)} \right)^T x^{(i)} \\ &= -tr \left( W^TXX^TW \right) + \sum^m_{i=1} \left( x^{(i)} \right)^T x^{(i)} \end{aligned}$

?在推導(dǎo)過(guò)程中，用到了：

$\hat{x}^{(i)} = Wz^{(i)}$ ，
矩陣轉(zhuǎn)置公式 $(AB)^T = B^TA^T$ ，
$W^TW = I$ ，
$z^{(i)} = W^Tx^{(i)}$ 以及矩陣的跡。

最后兩步是將代數(shù)和轉(zhuǎn)為矩陣形式。由于 $W$ 的每一列向量 $w_j$ 是標(biāo)準(zhǔn)正交基， $\sum^m_{i=1} x^{(i)} \left( x^{(i)} \right)^T$ 是數(shù)據(jù)集的協(xié)方差矩陣， $\sum^m_{i=1} \left( x^{(i)} \right)^T x^{(i)}$ 是一個(gè)常量（因?yàn)闅w一化了）。最小化 $\sum^m_{i=1} | \hat{x}^{(i)} - x^{(i)} |^2_2$ 的問(wèn)題可以等價(jià)于
$\underbrace{\arg \min}_W - tr \left( W^TXX^TW \right) \\ s.t. \ W^TW = I$

利用拉格朗日函數(shù)可得到
$J(W) = -tr(W^TXX^TW) + \lambda(W^TW - I)$

對(duì) $W$ 求導(dǎo)，可得 $-XX^TW + \lambda W = 0$ ，也即 $XX^TW = \lambda W$ 。 $W$ 是 $n'$ 個(gè)特征向量組成的矩陣， $\lambda$ 為 $XX^T$ 的特征值。 $W$ 即為我們想要的矩陣。對(duì)于原始數(shù)據(jù)，只需要 $z^{(i)} = W^TX^{(i)}$ ，就可把原始數(shù)據(jù)集降維到最小投影距離的 $n'$ 維數(shù)據(jù)集。

由上述分析，得到PCA的算法流程。

輸入： $n$ 維樣本集 $D = \left( x^{(1)},x^{(2)},...,x^{(m)} \right)$ ，目標(biāo)降維的維數(shù) $n'$ 。
輸出：降維后的新樣本集 $D' = \left( z^{(1)},z^{(2)},...,z^{(m)} \right)$ 。
主要步驟如下：

歸一化。對(duì)所有的樣本進(jìn)行中心化， $x^{(i)} = x^{(i)} - \frac{1}{m} \sum^m_{j=1} x^{(j)}$ 。
計(jì)算樣本的協(xié)方差矩陣 $XX^T$ 。
對(duì)協(xié)方差矩陣 $XX^T$ 進(jìn)行特征值分解。
取出最大的 $n'$ 個(gè)特征值對(duì)應(yīng)的特征向量 ${ w_1,w_2,...,w_{n'} }$ 。
標(biāo)準(zhǔn)化特征向量，得到特征向量矩陣 $W$ 。
轉(zhuǎn)化樣本集中的每個(gè)樣本 $z^{(i)} = W^T x^{(i)}$ 。
得到輸出矩陣 $D' = \left( z^{(1)},z^{(2)},...,z^{(n)} \right)$ 。
注：在降維時(shí)，有時(shí)不明確目標(biāo)維數(shù)，而是指定降維到的主成分比重閾值 $k \ (k \in (0,1])$ 。假設(shè) $n$ 個(gè)特征值為 $\lambda_1 \geqslant \lambda_2 \geqslant ... \geqslant \lambda_n$ ，則 $n'$ 可從 $\sum^{n'}_{i=1} \lambda_i \geqslant k \times \sum^n_{i=1} \lambda_i$ 得到。