PCA和LDA

参考1
参考2
原理就是一句话,把原来的$A$个维度映射到B(B

矩阵乘法

首先阐述一下矩阵乘法的含义（以下都以矩阵和向量乘法为例，矩阵乘以矩阵类似）
举个例子：

$$\begin{gathered} \begin{bmatrix} a & b & c\\ d & e & f\\ g & h & i \end{bmatrix} \times \begin{bmatrix} x\\ y\\ z \end{bmatrix} \end{gathered} \tag{1}$$

一个矩阵$A$和一个列向量$x$相乘。
我们知道，列向量各个维度上的值其实都是相应坐标系的坐标，因此该列向量也可以写作：

$$\begin{gathered} \begin{bmatrix} x\\ y\\ z \end{bmatrix}=x\begin{bmatrix} 1\\ 0\\ 0 \end{bmatrix}+y\begin{bmatrix} 0\\ 1\\ 0 \end{bmatrix}+z\begin{bmatrix} 0\\ 0\\ 1 \end{bmatrix} \end{gathered} \tag{2}$$

则公式$(1)$可以写作：

$$\begin{gathered} \begin{bmatrix} a & b & c\\ d & e & f\\ g & h & i \end{bmatrix} \times ( x\begin{bmatrix} 1\\ 0\\ 0 \end{bmatrix}+y\begin{bmatrix} 0\\ 1\\ 0 \end{bmatrix}+z\begin{bmatrix} 0\\ 0\\ 1 \end{bmatrix} )= x\begin{bmatrix} a\\ d\\ g \end{bmatrix}+y\begin{bmatrix} b\\ e\\ h \end{bmatrix}+z\begin{bmatrix} c\\ f\\ i \end{bmatrix}=\begin{bmatrix} ax+by+zc\\ dx+ey+fz\\ gz+hy+iz \\ \end{bmatrix} \end{gathered} \tag{3}$$

则有：

1. $x$的含义是：以$A$的列向量为基底的一个向量，$Ax$的含义是：以$A$的列向量为基底的的向量$x$在直角坐标下的坐标(要时刻谨记$Ax$是一个向量)。
2. 其实$Ax$才是准确定义向量的方式，其中$A$的列向量是基底，$x$是坐标，而我们平常所见的$x$其实是默认了$A$为单位矩阵。
3. 矩阵=线性变换,在直角坐标下，沿着矩阵$A$的列向量组成的矩阵，进行坐标为$x$的线性变换后的坐标。
   由此可衍生以下三类问题：
4. $Ax=?$: 求以$A$的列向量为基底的的向量$x$在直角坐标下的坐标。（直接计算）
5. $A?=y$: 求直角坐标系中$y$在以$A$的列向量为基底的坐标系中的坐标。(求方程/基础解系)
6. $?x=y$: 在某个坐标系中的向量$x$,其在直角坐标系下的坐标是$y$，求基底。

PCA

命题：

对于$P_{b \times a}X_{a\times n}=Y_{b \times n}$，假设$X$已知，且$r(X)=a$，则有无数个$P_{b\times a}$可以得到满足题意的$Y_{b\times n}$，当$b \lt a$的时候，就实现了数据降维，PCA要做的就是，找出一个$P_{b\times a}$使得求出的$Y_{b\times a}$最好。
原理：最大方差理论：在信号处理中认为信号具有较大的方差，噪声有较小的方差(没找到出处)。在此理论下，PCA的目标有两个：

1. $Y_{b\times n}$的列向量方差越大越好。
2. $Y_{b\times n}$的不同行向量之间协方差越小越好(绝对值)。
   那么当$Y_{b\times n}$满足什么条件时方差最大呢？
   首先确定一下方差怎么计算，我们认为$n$个具有$m$个特征的向量${[x_{11},x_{12},x_{13},…,x_{1m}],[x_{21},x_{22},x_{23},…,x_{2m}],…[x_{n1},x_{n2},x_{n3},…,x_{nm}]}$的方差为：

$$Var_j=\frac{1}{n}\sum_{i=1}^n(x_{ij}-\mu_j)^2 \tag{4}$$

其中$\mu_j$是第$j$个分量的均值，可以看到，如果$\mu_i=0$那么公式(4)就可以写作：

$$Var_j=\frac{1}{n}\sum_{i=1}^nx_{ij}^2 \tag{4}$$ $$Var=[Var_1,Var_2,Var_3,...Var_m]=\frac{1}{n}[\sum_{i=1}^nx_{i1}^2,\sum_{i=1}^nx_{i2}^2,\sum_{i=1}^nx_{i3}^2,...\sum_{i=1}^nx_{im}^2] \tag{5}$$

同理,第$\alpha$个分量和第$\beta$个分量协方差为：

$$Cov(\alpha,\beta)=\frac{1}{n}\sum_{i=1}^nx_{i\alpha}x_{i\beta} \tag{6}$$

假设上诉$n$个具有$m$个特征的向量组成的矩阵为：

$$A=\begin{gathered} \begin{bmatrix} x_{1,1} & x_{2,1} & x_{3,1} &...&x_{n,1}\\ x_{1,2} & x_{2,2} & x_{3,2} &...&x_{n,2}\\ x_{1,3} & x_{2,3} & x_{3,3} &...&x_{n,3} \\ ... &...&...&...&...\\ x_{1,m} & x_{2,m} & x_{3,m} &...&x_{n,m} \end{bmatrix} \end{gathered} \tag{7}$$

则

$$A\times A^T=\begin{gathered} \begin{bmatrix} Var_1 & Cov(1,2) & Cov(1,3) &...&Cov(1,m)\\ Cov(2,1) & Var_2 & Cov(2,3) &...&Cov(2,m)\\ Cov(3,1) & Cov(3,2) & Var_3 &...&Cov(3,m) \\ ... &...&...&...&...\\ Cov(m,1) & Cov(m,2) & Cov(m,3) &...&Var_m \end{bmatrix} \end{gathered} \tag{8}$$

试想，$Cov(i,j)$的绝对值最小就是0，那么(7)其实就是一个对角矩阵，我们想要的$Y$其实就是满足$A$的矩阵。
现在重新命题：
对于$P_{b \times a}X_{a\times n}=Y_{b \times n}$，假设$X_{a\times n}$已知，且$r(X)=a$，则有无数个$P_{b\times a}$可以得到满足题意的$Y_{b\times n}$，当$b \lt a$的时候，就实现了数据降维，要求我们找出一个$P_{b\times a}$，使得求出的$Y_{b\times a} \times Y_{b\times a}^T=\land$。

现在求解：

$$\land = YY^T=PX(PX)^T=PXX^TP^T=P(XX^T)P^T \tag{9}$$

我们知道$XX^T$是一个实对称矩阵，实对称矩阵有三条很重要的定理：

1. 一定可以对角化，而且特征值都是实数
2. 属于不同特征值的特征向量两两相交
3. 特征向量组成的矩阵正交化(施密特正交化+单位化)后所组成的矩阵依然可以将其对角化，特征值不变。

从第三条看出，正交化后的矩阵，必然$P^T=P^{-1}$，因此我们最终得出结论：$P$其实就是$XX^T$的特征向量组成的矩阵经过正交化的矩阵。

PCA步骤总结

1. 对$X$每行零均值化(每行减去当行的均值)
2. 求实对称协方差矩阵$XX^T$
3. 求实对称协方差矩阵的各个特征值以及其相应的特征向量
4. 将从左向右按照特征值大小取$b$个组成的矩阵施密特正交化+单位化，得到$P$,$Y=PX$即为所求。

LDA

命题

对于一个有监督二分类问题，训练样本$X_1=[x_1^1,x_2^1,x_3^1,…],X_2=[x_1^2,x_2^2,x_3^2,…]$，其中$x_i^k$维度为$d$，我们要寻找一个投影方向$w$(同为$d$维),使得投影后的样本变为$y_i^k=w^Tx_i^k$。要求类间间距要大，类内间距要小。

定义

各类内均值向量:

$$m_k=\frac{1}{N_{X_k}}\sum_{x_i^k\in X_k}x_i^k \tag{10}$$

类内离散度矩阵:

$$S_k=\sum_{x_i^k\in X_k}(x_i^k-m_k)(x_i^k-m_k)^T \tag{11}$$

总类内离散度矩阵(二分类):

$$S_w=S_1+S_2 \tag{12}$$

类间离散度:

$$S_b=(m_1-m_2)(m_1-m_2)^T$$

可以看出，$y_i^k$就是个标量，则投影后各类内均值为:

$$\widetilde m_k=\frac{1}{N_{X_k}}\sum_{x_i^k\in X_k}w^Tx_i^k \tag{13}$$

同理类内离散度为:

$$\widetilde S_k=\sum_{x_i^k\in X_k}(w^Tx_i^k-\widetilde m_k)^2 \tag{14}$$

总类内离散度：

$$\widetilde S_w= \widetilde S_1+\widetilde S_2 \tag{15}$$

类间离散度：

$$\widetilde S_b=(\widetilde m_1- \widetilde m_2)^2 \tag{16}$$

回到命题，我们就是想让$\widetilde S_b$越大越好，$\widetilde S_w$越小越好，于是可以定义优化函数公式(Fisher准则)：

$$maxJ(w)=\frac{\widetilde S_b}{\widetilde S_w}=\frac{w^TS_bw}{w^TS_ww} \tag{17}$$

求解

$$maxJ(w)'=\frac{(w^TS_ww)\times(S_bw)-(w^TS_bw)\times(S_ww)}{(w^TS_ww)^2} \tag{18}$$

令(18)=0,可得:

$$S_bw=\frac{w^TS_bw}{w^TS_ww}S_ww \tag{19}$$

令$\lambda = \frac{w^TS_bw}{w^TS_ww}$

$$S_bw=\lambda S_ww \tag{20}$$ $$S_w^{-1}S_bw=\lambda w \tag{21}$$

现在发现了，又是特征向量。

LDA步骤总结

1. 计算各类内均值向量$m_k$
2. 计算类内散度矩阵$S_w$和类间散度矩阵$S_b$
3. 计算$S_w^{-1}S_b$的特征向量和相应特征值，并按照从左到右特征值大小排序
4. 取top d 个最大特征值怼用的特征向量组成的特征矩阵$W_{n\times d}$
5. $Y=W_{n\times d} \times X$的到降维后数据。