线性判别分析(Linear Discriminant Analysis), 简称 LDA, 是一种经典的线性学习方法. 在二分类问题上最早由 Fisher 提出, 也称 "Fisher 判别分析".
在主成分分析原理总结中, 我们对降维算法 PCA 进行了总结. 这里的 LDA 是另一种经典的的降维算法. 使用 PCA 进行降维, 我们没有将类别考虑进去, 属于无监督学习. 而 LDA 是一种监督学习的降维技术, 即它的每个样本是有类别输出的.
LDA 的思想
给定训练样例集, 设法将样例投影到一条直线上, 使得同类样例的投影点尽可能接近, 异类样例的投影点尽可能远离; 在对新样本进行分类时, 将其投影到同样的这条直线上, 再根据投影点的位置来确定新样本的类别.
用一句话概括就是: 投影后类内方差最小, 类间方差最大.
瑞利商与广义瑞利商(Rayleigh quotient)
瑞利商定义: 瑞利商是指这样的函数 \(R(A,x)\):
\[R(A,x)=\dfrac{x^HAx}{x^Hx}\]
其中 \(x\)为非零向量, 而 A 为 \(n\times n\)的 Hermitan 矩阵. 所谓的 Hermitan 矩阵就是它的共轭转置等于它本身, 属于推广的对称矩阵, 即 \(A^H=A\). 如果 A 是实对称阵,\(A^T=A\)即为 Hermitan 矩阵.
瑞利商 \(R(A,x)\)有 一个非常重要的性质, 即它的最大值等于矩阵 A 的最大特征值, 而最小值等于矩阵 A 的最小的特征值, 也就是满足:
\[\lambda_{min}\le \dfrac{x^HAx}{x^Hx}\le \lambda_{max}\]
当向量 x 是标准正交基时, 即满足 \(x^Hx=1\)时, 瑞利商退化为:
\[R(A,x)=x^HAx\], 这个形式在谱聚类和 PCA 中都有出现.
广义瑞利商: 是指这样的函数 \(R(A,B,x)\):
\[R(A,B,x)=\dfrac{x^HAx}{x^HBx}\]
其中 x 为非零向量, 而 A,B 为 \(n\times n\)的 Hermitan 矩阵, B 为正定矩阵.
它的最大值和最小值是什么?
我们令 \(x'=B^{-1/2}x\), 则分母转化为:
\[x^HBx=x'^H(B^{-1/2})^HBB^{-1/2}x'=x'^Hx'\]
而分子转化为:
\[x^HAx=x'^HB^{-1/2}AB^{-1/2}x'\]
此时我们的 \(R(A,B,x)\)转化为 \(R(A,B,x')\):
\[ R(A,B,x')=\dfrac{x'^HB^{-1/2}AB^{-1/2}x'}{x'^Hx'}\]
由前面瑞利商的性质, 我们可以知道 \(R(A,B,x)\)的最大值和最小值分别为矩阵 \(B^{-1/2}AB^{-1/2}\)的最大特征值和最小特征值, 或者说是 \(B^{-1}A\)的最大特征值和最小特征值.
回到 LDA - 考虑二分类问题
给定数据集 \(D={\{(x_i,y_i)}\}_{i=1}^m,y_i\in{\{0,1}\}\), 令 \(X_i,\mu_i,\Sigma_i\)分别代表第 \(i\in{\{0,1}\}\)类示例的集合, 均值向量, 协方差矩阵.
若将数据投影到直线 w 上, 则两类样本的中心在直线上的投影分别为 \(w^T\mu_0\),\(w^T\mu_1\); 若将所有样本点都投影在直线上, 则两类样本的协方差分别为
\(w^T\Sigma_0w\)和 \(w^T\Sigma_1w\).
由于直线是一维空间, 因此,\(w^T\mu_0\),\(w^T\mu_1\),\(w^T\Sigma_0w\)和 \(w^T\Sigma_1w\)均为实数.
要使得同类样例的投影点尽可能接近, 可以让同类样例投影点的协方差尽可能小, 即 \(w^T\Sigma_0w+w^T\Sigma_1w\)尽可能小; 而要使异类样例的投影点尽可能远离, 可以让类中心之间的距离尽可能大, 即:\(\lVert w^T\mu_0-w^T\mu_1\rVert_2^2\)尽可能大.
同时考虑二者, 可以得到最大化的目标如下:
- \begin{
- eqnarray
- }
- J&=&\dfrac{
- \lVert w^T\mu_0-w^T\mu_1\rVert_2^2
- }{
- w^T\Sigma_0w+w^T\Sigma_1w
- }\notag\
- &=&\dfrac{
- w^T(\mu_0-\mu_1)(\mu_0-\mu_1)^Hw
- }{
- w^T(\Sigma_0+\Sigma_1)w
- }\notag
- \end{
- eqnarray
- }
定义 "类内散度矩阵"(within-class scatter matrix):
- \begin{
- eqnarray
- }
- S_w&=&\Sigma_0+\Sigma_1\notag\
- &=&\sum_{
- x\in X_0
- }(x-\mu_0)(x-\mu_0)^T+\sum_{
- x\in X_1
- }(x-\mu_1)(x-\mu_1)^T\notag
- \end{
- eqnarray
- }
定义 "类间散度矩阵"(betweent-class scatter matrix):
\[S_b=(\mu_0-\mu_1)(\mu_0-\mu_1)^T\].
则 J 可重写为:
\[J=\dfrac{w^TS_bw}{w^TS_ww}\qquad(*)\]
这就是 LDA 欲最大化的目标, 即 \(S_b,S_w\)的瑞利商.
推导求解
推导
如何确定 w?
注意到 () 式的分子和分母都是关于 w 的二次项, 因此 () 式的解与 w 的长度无关, 只与其方向有关. 不失一般性, 令 \(w^TS_ww=1\), 则式 (*) 等价于:
- \[\min_w-w^TS_bw\]
- \[ s.t. w^TS_ww=1\]
由拉格朗日乘子法, 上式等价于:
\[ S_bw=\lambda S_ww\qquad(**)\]
因为 \(S_bw=(\mu_0-\mu_1)(\mu_0-\mu_1)^Tw\), 其中 \((\mu_0-\mu_1)^Tw\)是标量, 所以 \(S_bw\)的方向恒为 \(\mu_0-\mu_1\), 不妨令:
\[ S_bw=\lambda(\mu_0-\mu_1)\]
代入 (**) 式可得:
\[w=S_w^{-1}(\mu_0-\mu_1)\]
注意:
至此, 我们只要求出原始样本的均值和方差就可以求出最佳方向 w, 这就是 Fisher 于 1936 年提出的线性判别分析.
求解
考虑到数值解的稳定性, 在实践中, 通常是对 \(S_w\)进行奇异值分解, 即 \(S_w=U\Sigma V^T\), 这里 \(\Sigma\)是一个实对角矩阵, 对角线上的元素是 \(S_w\)的奇异值, 然后再由
\(S_w^{-1}=V\Sigma^{-1}U^T\)得到 \(S_w^{-1}\), 进而求解得到 \(W\).
一旦确定了 w, 就可以对特征进行降维计算:\(y=w^Tx\), 将示例的维数从 d 维降到 1 维.
LDA - 多分类问题
将 LDA 推广到多分类任务中, 假定存在 N 个类, 且第 i 类示例数为 \(m_i\), 总示例数为 \(m\), 则 \(m=\sum_{i=1}^N m_i\).
首先, 我们定义 "全局散度矩阵":
\[S_t=S_b+S_w=\sum_{j=1}^m(x_j-\mu)(x_j-\mu)^T\]
其中,\(\mu\)是所有示例的均值向量.
其次, 我们需要重新定义类内散度矩阵为每个类别的散度矩阵之和:
\[S_w=\sum_{i=1}^N S_{w_i}\]
其中,\(S_{w_i}=\sum_{x\in X_i}(x-\mu_i)(x-\mu_i)^T\)
类间散度矩阵:
\[S_b=S_t-S_w=\sum_{i=1}^N m_i(\mu_i-\mu)(\mu_i-\mu)^T\]
计算过程:
- \[S_t=\sum_{
- i=j
- }^m x_jx_j^T-\sum_{
- j=1
- }^m\mu\mu^T=\sum_{
- j=1
- }^m x_jx_j^T-\sum_{
- i=1
- }^N m_i \mu\mu^T\]
- \[S_w=\sum_{
- i=1
- }^N\sum_{
- x\in X_i
- } (xx^T-\mu_i\mu_i^T)=\sum_{
- j=1
- }^m x_jx_j^T-\sum_{
- i=1
- }^Nm_i \mu_i\mu_i^T\]
则有:
\(S_b=S_t-S_w=\sum_{i=1}^N m_i(\mu_i\mu_i^T-\mu\mu^T)=\sum_{i=1}^N m_i(\mu_i-\mu)(\mu_i-\mu)^T\)
推导与计算
由二分类的 LDA 我们可知, 若示例 \(x\)包含 d 个特征, 我们寻找一条直线 (方向为 \(w\)) 来做投影, 寻找最能使样本分离的直线. 将示例从 d 维降到一维.
当类别变成 N 个, 这里 N>2, 要使得投影后类别能够分离, 降维到一维可能已经不能满足要求, 需要将特征将到 N-1 维.
多分类 LDA 有多种实现方法, 常见的优化目标为:
\[\max_{W}\dfrac{tr(W^TS_bW)}{W^TS_wW}\]
其中,\(W\in R^{d\times(N-1)}\),\(tr(\cdot)\)表示矩阵的迹. 上式可以通过如下广义特征问题进行求解:
\[S_bW=\lambda S_wW\]
W 的闭式解是 \(S_w^{-1}S_b\)的 \(d'\)个最大非零广义特征值所对应的特征向量组成的矩阵,\(d'\le N-1\).
降维问题:
若将 W 视为一个投影矩阵, 则多分类 LDA 将样本投影到 \(d'\)维空间,\(d'\)常远小于数据原有的属性 d. 于是, 可通过投影来减小样本点的维数, 且投影过程中使用了类别信息, 故 LDA 也常被视为一种经典的监督降维技术.
得到 W, 进行降维计算得到新特征:\(y=W^Tx\)
注意:
由于 W 是一个利用了样本的类别得到的投影矩阵, 因此它降维到的维数最大值为 N-1.
为什么不是 N 呢?
因为 \(S_b\)中的每一个 \(\mu_i-\mu\)的秩为 1, 因此协方差矩阵相加后最大的秩为 N(矩阵和的秩小于等于各个矩阵秩的和), 但如果我们知道前 N-1 个 \(\mu_j\)之后, 最后一个 \(\mu_N\)可以由前 N-1 个 \(\mu_j\)线性表示, 因此 \(S_b\)的秩最大为 N-1 个, 所以特征向量最多有 N-1 个.
W 中的特征向量不一定是正交的, 因为 \(S_w^{-1}S_b\)不一定是实对称阵
若矩阵 \(S_w\)为奇异矩阵呢?
在实际应用中存在着许多典型的小样本问题, 比如在人脸图像识别问题中,\(S_w\)通常是奇异的, 这是因为待识别的图像矢量维数一般比较高, 而在实际问题中难以找到或者根本不可能找到足够多的训练样本来保证 \(S_w\)的可逆性. 在这种情况下, 可采用的做法是, 先用 PCA 进行降维, 再对降维后的数据用 LDA.
推广的 LDA-KLDA
思考: 线性判别分析仅在线性可分数据上能获得理想结果, 如何能使其较好地用于非线性可分数据?
回答: 在当前维度上不可分, 可以使用适当的映射方法, 使其在更高一维上可分. 典型的方法有 KLDA, 也就是核化 LDA.
KLDA
我们先假设可通过某种映射 \(\phi:\mathcal{x}\mapsto \mathbb{F}\)将样本映射到一个特征空间 \(\mathbb{F}\), 然后在 \(\mathbb{F}\)中执行线性判别分析, 以求得:
\[h(x)=w^T\phi(x)\]
类似于 LDA, KLDA 的学习目标是:
\[\max_{w} J(w) = \dfrac{w^TS_b^{\phi}w}{w^TS_w^{\phi}w}\]
其中,\(S_b^{\phi}, S_w^{\phi}\)分别为训练样本在特征空间 \(\mathbb{F}\)中的类间散布矩阵和类内散布矩阵.
令 \(X_i\)表示第 \(i\in{\{0,1}\}\)类样本的集合, 其样本数为 \(m_i\), 总样本数 \(m=m_0+m_1\). 第 i 类样本在特征空间 \(\mathbb{F}\)中的均值为:
\[\mu_i^{\phi}=\dfrac{1}{m_i}\sum_{x\in X_i}\phi(x)\]
两个散度矩阵分别为:
- \[ S_b^{
- \phi
- }=(\mu_1^{
- \phi
- }-\mu_0^{
- \phi
- })(\mu_1^{
- \phi
- }-\mu_0^{
- \phi
- })^T\]
- \[ S_w^{
- \phi
- }=\sum_{
- i=0
- }^1\sum_{
- x\in X_i
- }(\phi(x)-\mu_i^{
- \phi
- })(\phi(x)-\mu_i^{
- \phi
- })^T\]
注意:
通常我们难以知道映射 \(\phi\)的具体形式, 因此使用核函数 \(\mathcal{k}(x,x_i) =\phi(x_i)^T\phi(x)\) 来隐式地表达这个映射和特征空间 \(\mathbb{F}\).
写在最后
LDA 与 PCA 的比较:
最大化目标函数 J 时, PCA 最大化'全局散度矩阵':\(S_t=S_b+S_w\)
LDA 最大化'类间散度矩阵':\(S_b/S_w\)
相同点:
1)两者都可以对数据进行降维;
2)两者在降维时均使用了矩阵特征分解的思想;
3)两者都假设数据符合高斯分布
不同点
1)LDA 是有监督的降维方法, 而 PCA 是无监督的降维方法
2)LDA 降维最多可以降到类别数 - 1 的维数, 而 PCA 没有这个限制
3)LDA 不仅可以降维, 还可以用于分类
4)LDA 选择分类性能最好的投影方向, 而 PCA 选择样本点投影具有最大方差的方向
降维技术 2 - 线性判别分析(LDA)
来源: http://www.bubuko.com/infodetail-3375260.html