Await 做些相當庸俗的夢

PCA 演算法

今天剛剛接觸到 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$ 相互正交,可以類似推匯出其他的特徵向量。

演算法步驟

  1. 求協方差矩陣 $\Sigma$。

  2. 求該矩陣的更大的 $M$ 個特徵值所對應的特徵向量。

  3. 歸一化特徵向量,即可得到降維矩陣 $A$。



可能相關的