前言

重要的算法还是写写笔记吧

PCA

主成分分析（PCA）是一种降维方法，使用一个超平面，对正交属性空间中的所有样本点进行恰当的表达。超平面应该满足这样的性质：

1. 最近重构性：样本点到这个超平面的距离都足够近
2. 最大可分性：样本点在这个超平面上的投影尽可能分开
   基于这两个可以分别得到等价推导。
   
   然后可得投影后的样本为 $W^{\top}X$W⊤X，这里是中心化后的样本。
   样本 $X$X 大小为 $d\times m$d×m。降维后的维数 $d'$d′ 由用户事先指定，可以通过交叉验证，或者指定重构阈值 $t$t，找到满足重构阈值的最小维数：
   
   其中 $\lambda_i$λi​ 为协方差矩阵的特征值。
   由于舍弃了最小的 $d-d'$d−d′ 个特征值对应的特征向量，因此必然会有信息的丢失，但这往往是必要的：

1. 增大采样密度
2. 最小的特征值对应的特征向量往往与噪声有关，舍弃他们往往能在一定程度上起到去噪的效果。

特征分解就是解行列式方程，比如求解矩阵 $A = \begin{bmatrix} -1 & 1 & 0 \\ -4 & 3 & 0 \\ 1 & 0 & 2\end{bmatrix}$A=⎣⎡​−1−41​130​002​⎦⎤​ 的特征值与特征向量。
$| A-\lambda E|=|\lambda E - A| = \left |\begin{matrix} \lambda+1 & 1 & 0 \\ -4 & \lambda-3 & 0 \\ 1 & 0 & \lambda-2\end{matrix}\right|=(\lambda+1)*(\lambda-3)*(\lambda-2)+1*0*1+0*(-4)*0-\\ 0*(\lambda-3)*1-1*(-4)*(\lambda-2)-(-1)*0*0\\=(\lambda+1)*(\lambda-3)*(\lambda-2)+4(\lambda-2)\\ =(\lambda -2)(\lambda^2-2\lambda-3+4)\\ =(\lambda -2)(\lambda -1)^2$∣A−λE∣=∣λE−A∣=∣∣∣∣∣∣​λ+1−41​1λ−30​00λ−2​∣∣∣∣∣∣​=(λ+1)∗(λ−3)∗(λ−2)+1∗0∗1+0∗(−4)∗0−0∗(λ−3)∗1−1∗(−4)∗(λ−2)−(−1)∗0∗0=(λ+1)∗(λ−3)∗(λ−2)+4(λ−2)=(λ−2)(λ2−2λ−3+4)=(λ−2)(λ−1)2
所以 $\lambda = 1,2$λ=1,2.
对于特征值 1，其对应的特征向量 $x=[x_1,x_2,x_3]^{\top}$x=[x1​,x2​,x3​]⊤ 为
$\left |\begin{matrix} -1-1 & 1 & 0 \\ -4 & 3-1 & 0 \\ 1 & 0 & 2-1\end{matrix}\right|x=0$∣∣∣∣∣∣​−1−1−41​13−10​002−1​∣∣∣∣∣∣​x=0
$\left |\begin{matrix} -2 & 1 & 0 \\ -4 & 2 & 0 \\ 1 & 0 & 1\end{matrix}\right|x=0$∣∣∣∣∣∣​−2−41​120​001​∣∣∣∣∣∣​x=0
所以标准化后的特征向量 $x=[\frac{-1}{\sqrt{6}},\frac{-2}{\sqrt{6}},\frac{1}{\sqrt{6}}]^{\top}$x=[6​−1​,6​−2​,6​1​]⊤