今天剛剛接觸到 PCA（Principal Components Analysis，主成分分析），感覺又是學起來很舒服的一個概念，原理很簡單，然後結果也很優美。
主成分分析，顧名思義的話，就是想要把資料集中的主要的特徵部分儘可能提取出來。它的輸入是一個總量為 $P$ ，維度為 $N$ 的資料集 $\vec{X}$，然後輸出一個總量為 $P$，維度為 $M(M<N)$ 的降維後的集合 $\vec{Y}$。
基本想法
PCA 最主要的想法就是想將高維向量投影到低維，同時儘可能使得不丟失重要的特徵。可以比較好想的是最大化投影結果的方差。由於 $\vec{Y}$ 中的每一個元素又都有 $M$ 個分量，因此可以對這 $M$ 個分量分別進行考慮。
設投影矩陣為
$$ \begin{matrix} -- & a_1 & -- \\ -- & a_2 & -- \\ -- & \cdots & -- \\ -- & a_M & -- \\ \end{matrix} $$
對輸出 $\vec{Y}$ 有 $Y_i = A \times {(X_i - \bar{X})}$。
推導
對於 $a_1$ 來說，它的規劃可以寫成
$$ \begin{aligned} \max && E{(a_1)} &= \frac{1}{P}{\sum_P}{|a_1X_i-a_1\bar{X}|^2} \\ s.t. && ||a_1|| &= 1 \end{aligned} $$
而
\[ \begin{aligned} E{(a_1)} &= \frac{1}{P}{\sum_P}{|a_1X_i-a_1\bar{X}|^2} \\ &=\frac{1}{P}{\sum_P}{[a_1(X_i-\bar{X})\times [a_1(X_i-\bar{X})]^\mathrm{T}]} \\ &=\frac{1}{P}{\sum_P}{[a_1(X_i-\bar{X})(X_i-\bar{X})^\mathrm{T}a_1^\mathrm{T}]} \\ &=a_1\Sigma{a_1^\mathrm{T}} \end{aligned} \]
其中 $\Sigma$ 為協方差矩陣:
$$ \Sigma = \frac{1}{P}{\sum_P[(X_i-\bar{X})(X_i-\bar{X})^\mathrm{T}]} $$
之後使用拉格朗日乘子法解規劃：
$$ M(a_1) = E(a_1) - \lambda(a_1a_1^\mathrm{T}) \\ \frac{\partial{M}}{\partial{a_1}} = 2\Sigma{a_1^\mathrm{T}} - 2\lambda{a_1^\mathrm{T}} $$
$$ \begin{aligned} a&=b+c \\ d+e&=f \end{aligned} $$
偏導為零，即可知 $\lambda$ 是協方差矩陣 $\Sigma$ 的特徵值，而又要使 $E(a_1)$ 最大化，$\lambda$ 為協方差矩陣的最大特徵值，$a_1$ 為該特徵根對應的特徵向量。
由於 $A$ 中的每一個行向量 $a_i$ 相互正交，可以類似推匯出其他的特徵向量。
演算法步驟
-
求協方差矩陣 $\Sigma$。
-
求該矩陣的更大的 $M$ 個特徵值所對應的特徵向量。
-
歸一化特徵向量，即可得到降維矩陣 $A$。