模式识别（LDA和PCA）
本文介绍了模式识别的特征选择与特征降维，着重介绍了线性判别分析（Linear Discriminant Analysis，LDA）和主成分分析法（Principal Component Analysis，PCA）。
1. 特征降维
机器学习的很多算法复杂度和数据的维数有着密切关系，甚至与维数呈指数级关联。当数据的特征维度达到成千上万甚至几十万的规模时，机器学习的资源消耗是不可接受的，且有很多特征可能与要解决的分类问题关系不大，因此就会对数据采取降维的操作。
降维就意味着信息的丢失，因为原本每个特征理论上都可以反映出原始数据的某些特质。但鉴于实际数据的特征之间本身常常存在相关性，所以在降维时可以采取一些办法降低信息的损失。
特征降维有两种方法：
- 特征选择：从已有特征向量中选择出若干维度的特征组成新的特征向量，新特征向量的维度一般远小于原始特征向量；
- 特征提取：将原始特征向量经过某种数学变换得到新的特征向量，新特征向量的维度一般远小于原始特征向量；
2. 线性判别分析（LDA）
线性判别分析（Linear Discriminant Analysis，LDA）是一种监督学习的降维技术，主要用于数据预处理中的降维、分类任务。LDA的目标是最大化类间区分度的坐标轴成分，将特征空间投影到一个维度更小的k维子空间中，同时保持区分类别的信息。简而言之，LDA投影后的数据类内方差最小，类间方差最大。
2.1. 瑞利商与广义瑞利商
定义瑞利商为
\[R(A,x)=\frac{x^HAx}{x^Hx}\]其中 $x$ 是非零向量，$A\in R^{n\times n}$ 是 Hermitan 矩阵（自共轭矩阵，矩阵中每一个第$i$行第$j$列元素都与第$j$行第$i$列元素共轭相等）。
性质：瑞利商的最大值等于矩阵 $A$ 最大的特征值，最小值等于矩阵 $A$ 的最小特征值。即
\[\lambda_{min} < R(A,x) < \lambda_{max}\]定义广义瑞利商为
\[R(A,x)=\frac{x^HAx}{x^HBx}\]其中 $B$ 为正定矩阵，其他定义同瑞利商。
性质：广义瑞利商的最大值为矩阵 $B^{-\frac{1}{2}}AB^{-\frac{1}{2}}$ 或者说 是矩阵 $B^{-1}A$的最大特征值，最小值是其最小特征值。
2.2. 两类 LDA
参考前述线性分类器中的Fisher投影准则介绍，类间离散度矩阵为
\[\boldsymbol{S}_b = (\boldsymbol{\mu}_1-\boldsymbol{\mu}_2)(\boldsymbol{\mu}_1-\boldsymbol{\mu}_2)^T\]为两向量的外积，其秩为1。
- 一个向量可以看做一个$n\times 1$ 矩阵或者 $1\times n$ 的矩阵，而一个矩阵 $A$ 的秩 $R(A)\leq \min(n,m)$，其中 $n$ 和 $m$ 是这个矩阵的行数和列数，所以单个向量的秩是1；
- 两向量外积也就是一个 $n\times 1$ 矩阵和一个 $1\times n$ 矩阵的积，又两矩阵的积的秩小于等于两者中秩最小的矩阵的秩，也就是 $R(AB)\leq \min(R(A),R(B))$，这里 $R(A)=R(B)=1$,所以 $R(AB)\leq 1$，即两向量外积的秩至多是1。
类内离散度矩阵为
\[\boldsymbol{S}_w = \sum_{i=1}^2 \boldsymbol{S}_{wi}=\sum_{i=1}^2 \sum_{x\in w_i}(x-\mu_i)(x-\mu_i)^T\]二分类LDA的优化目标函数可以写成
\[\arg\max_{\boldsymbol{w}} J(\boldsymbol{w}) = \frac{\boldsymbol{w}^T\boldsymbol{S}_b\boldsymbol{w}}{\boldsymbol{w}^T\boldsymbol{S}_w\boldsymbol{w}}\]目标是求使得 $J(\boldsymbol{w})$ 最大的投影方向 $\boldsymbol{w}$。
可以看出，目标函数正好是广义瑞利商的形式，因此其最大值为 $\boldsymbol{S}_w^{-1}\boldsymbol{S}_b$ 的最大特征值，那么投影方向 $\boldsymbol{w}$ 即为 $\boldsymbol{S}_w^{-1}\boldsymbol{S}_b$ 对应特征值 $\lambda$ 的特征向量。
若 $\boldsymbol{S}_w$ 不可逆，可进行如下操作进行松弛
\[\boldsymbol{S}_w = \boldsymbol{S}_w + \beta \boldsymbol{I}\]其中 $\beta$ 是一个很小的数。
实际使用时为得到数值解的稳定性，通常对 $\boldsymbol{S}_w$ 进行奇异值分解得到 $\boldsymbol{S}_w^{-1}$
\[\boldsymbol{S}_w=\boldsymbol{U}\Sigma \boldsymbol{V}^T \Rightarrow \boldsymbol{S}_w^{-1} = \boldsymbol{V}\Sigma \boldsymbol{U}^T\]2.3. 多类 LDA
假设为 $C$ 分类，类内离散度矩阵定义保持不变，有
\[\boldsymbol{S}_w = \sum_{i=1}^C \boldsymbol{S}_{wi}=\sum_{i=1}^C \sum_{x\in w_i}(x-\mu_i)(x-\mu_i)^T\]对于类间离散度矩阵，无法像之前二分类那样定义（即 $\boldsymbol{S}_b=(\boldsymbol{\mu}_1-\boldsymbol{\mu}_2)(\boldsymbol{\mu}_1-\boldsymbol{\mu}_2)^T$），即原来度量的是两个均值点的散列情况，现在度量的是每类均值点相对于样本中心的散列情况。类似于将 $\boldsymbol{\mu}_i$ 看作样本点，$\boldsymbol{\mu}$ 是均值的协方差矩阵。如果某类里面的样本点较多，那么其权重稍大，权重用 $N_i/N$ 表示，但由于 $J(\boldsymbol{w})$对倍数不敏感，因此使用 $N_i$ 即可
\[\boldsymbol{S}_b= \sum_{i=1}^C N_i(\boldsymbol{\mu}_i-\boldsymbol{\mu})(\boldsymbol{\mu}_i-\boldsymbol{\mu})^T\]注意到，$\boldsymbol{S}_b$ 仍然是 $C$ 个秩为 1 的向量外积得到的矩阵求和，因此 $\boldsymbol{S}_b$ 的秩不会超过 $C$。
矩阵的秩小于等于各个相加矩阵的秩的和，即 $R(A+B)\leq R(A)+R(B)$
又因为，各个类别的均值与总样本均值之间线性相关，即
\[\boldsymbol{\mu} = \frac{1}{N} \sum_{\forall \boldsymbol{x}}\boldsymbol{x} = \frac{1}{N}\sum_{\boldsymbol{x}\in w_i} N_i\boldsymbol{\mu}_i\]知道了前 $C-1$ 个 $(\boldsymbol{\mu}_i-\boldsymbol{\mu})$ 后，最后一个 $(\boldsymbol{\mu}_C-\boldsymbol{\mu})$ 可以有前面的 $\boldsymbol{\mu}_i$ 来线性表示，因此$\boldsymbol{S}_b$ 的秩为 $C-1$。
所以在计算特征向量矩阵（类内散度矩阵 $\boldsymbol{S}_w$ 的逆 $\times$ 类间散度矩阵 $\boldsymbol{S}_b$）时，可以发现只有 $C-1$ 个特征值不为零的特征向量。因此，LDA 最多将特征维度降低到 $C-1$ 维。
2.4. LDA 的特点
LDA 是一个有监督的方法，具有如下特点：
- 根据原始数据样本的均值进行分类
- 不同类数据拥有相近的协方差矩阵
当然，在实际情况中，不可能满足以上两个假设。但是当数据主要是由均值来区分的时候，LDA一般都可以取得很好的效果。见下面两个对比图。
上图中，两类数据的均值差异较大，但协方差矩阵十分接近，因此 LDA 分类效果好于 PCA。
上图中，两类数据的均值差异很小，但协方差矩阵相差十分明显，因此 LDA 分类效果差于 PCA。
LDA 的优点:
- 计算速度快
- 充分利用了先验知识
LDA 的缺点:
- 不适合对非高斯分布的样本降维
- 降维之后的维数最多为类别数-1，所以当数据维度很高，但是类别数少的时候，算法并不适用
- 可能会过度拟合数据
3. 主成分分析（PCA）
主成分分析（Principal Component Analysis，PCA）是常用的特征提取数据分析方法。PCA是通过线性变换，将原始数据变换为一组各维度线性无关的数据表示方法，可用于提取数据的主要特征分量，常用于高维数据的降维。
为了最大限度保留对原始数据的解释，一般会用最大方差理论或最小损失理论，使得第一主成分有着最大的方差或变异数 (就是说其能尽量多的解释原始数据的差异)；随后的每一个主成分都与前面的主成分正交，且有着仅次于前一主成分的最大方差 (正交简单的理解就是两个主成分空间夹角为90°，两者之间无线性关联，从而完成去冗余操作)。
3.1. 具体步骤
假设有 $m$ 个 $n$ 维向量，想将其变换为由 $d$ 个 $n$ 维向量表示的新空间中，那么首先将 $d$ 个基按行组成矩阵 $W$，然后将向量按列组成矩阵 $X$，那么两矩阵的乘积 $WX$ 就是变换结果，其中 $WX$ 的第 $m$ 列为 $X$ 中第 $m$ 列变换后的结果。
首先将 $m$ 个 $n$ 维数据排列成 $n$ 行 $m$ 列矩阵的形式，即每一列是一个样本数据
\[\boldsymbol{X} = [\boldsymbol{X}_1, \boldsymbol{X}_2,\cdots, \boldsymbol{X}_m] \in \mathbb{R}^{n\times m}\]然后对数据进行中心化，即计算所有数据的均值后，将所有数据减去均值
\[\begin{aligned} \bar{\boldsymbol{X}}&=[\boldsymbol{X}_1-\boldsymbol{\mu}, \boldsymbol{X}_2-\boldsymbol{\mu},\cdots, \boldsymbol{X}_m-\boldsymbol{\mu}]\\ &=[\bar{\boldsymbol{X}}_1, \bar{\boldsymbol{X}}_2,\cdots, \bar{\boldsymbol{X}}_m]\\ &=\begin{bmatrix} \bar x^1_1 & \bar x^2_1 & \cdots & \bar x^m_1\\ \bar x^1_2 & \bar x^2_2 & \cdots & \bar x^m_2\\ \vdots & \vdots & \ddots & \vdots \\ \bar x^1_n & \bar x^2_n & \cdots & \bar x^m_n\\ \end{bmatrix} \end{aligned}\]此时满足
\[\sum_{i=0}^m \bar{\boldsymbol{X}}_i = 0\]然后计算这个矩阵的协方差矩阵，即
\[\begin{aligned} \boldsymbol{\Sigma} &= \frac{1}{m-1}\bar{\boldsymbol{X}}\bar{\boldsymbol{X}}^T \in \mathbb{R}^{n \times n}\\ &=\frac{1}{m-1} \begin{bmatrix} \sum_{i=1}^m (\bar x^i_1)^2 & \sum_{i=1}^m \bar x^i_1\cdot \bar x^i_2 & \cdots & \sum_{i=1}^m \bar x^i_1\cdot \bar x^i_n\\ \sum_{i=1}^m \bar x^i_2\cdot \bar x^i_1 & \sum_{i=1}^m (\bar x^i_2)^2 & \cdots & \sum_{i=1}^m \bar x^i_2\cdot \bar x^i_n\\ \vdots & \vdots & \ddots & \vdots \\ \sum_{i=1}^m \bar x^i_n\cdot \bar x^i_1 & \sum_{i=1}^m \bar x^i_n\cdot \bar x^i_2 & \cdots & \sum_{i=1}^m (\bar x^i_n)^2\\ \end{bmatrix}\\ &=\frac{1}{m-1} \begin{bmatrix} \sum_{i=1}^m (x^i_1-\mu_1)^2 & \sum_{i=1}^m (x^i_1-\mu_1) (x^i_2-\mu_2) & \cdots & \sum_{i=1}^m (x^i_1-\mu_1) (x^i_n-\mu_n)\\ \sum_{i=1}^m (x^i_2-\mu_2) (x^i_1-\mu_1) & \sum_{i=1}^m (x^i_2-\mu_2)^2 & \cdots & \sum_{i=1}^m (x^i_2-\mu_2) x(^i_n-\mu_n)\\ \vdots & \vdots & \ddots & \vdots \\ \sum_{i=1}^m (x^i_n-\mu_n) (x^i_1-\mu_1) & \sum_{i=1}^m (x^i_n-\mu_n) (x^i_2-\mu_2) & \cdots & \sum_{i=1}^m (x^i_n-\mu_n)^2\\ \end{bmatrix} \end{aligned}\]其中，对角线上的元素为各个随机变量（特征）的方差，非对角线上的元素为两两随机变量之间的协方差。
求出协方差矩阵的特征值 $\lambda_i$ 和对应的正交化单位特征向量 $\boldsymbol{w}_i$。
将特征向量按照对应特征值从大到小，自上而下按行排列成矩阵，取前 $d$ 行组成矩阵 $\boldsymbol{W}$。
$\boldsymbol{Y} = \boldsymbol{W}\boldsymbol{X}$ 即为降维到 $d$ 维后的数据。
3.2. PCA 的特点
根据上面对PCA的数学原理的解释，可以了解到一些PCA的能力和限制。PCA本质上是将方差最大的方向作为主要特征，并且在各个正交方向上将数据“离相关”，也就是让它们在不同正交方向上没有相关性。
因此，PCA也存在一些限制，例如它可以很好的解除线性相关，但是对于高阶相关性就没有办法了，对于存在高阶相关性的数据，可以考虑Kernel PCA，通过Kernel函数将非线性相关转为线性相关。另外，PCA假设数据各主特征是分布在正交方向上，如果在非正交方向上存在几个方差较大的方向，PCA的效果就大打折扣了。
最后需要说明的是，PCA是一种无参数技术，也就是说面对同样的数据，如果不考虑清洗，谁来做结果都一样，没有主观参数的介入，所以PCA便于通用实现，但是本身无法个性化的优化。