在学习 LDA 之前，有必要将其自然语言处理领域的 LDA 区别开来，在自然语言处理领域， LDA 是隐含狄利克雷分布（Latent Dirichlet Allocation，简称 LDA），他是一种处理文档的主题模型。这里讨论的 LDA 是线性判别分析。

线性判别分析的基本原理

LDA 是一种监督学习的降维技术，也就是说它的数据集的每个样本是有类别输出的。这点和 PCA 不同。PCA 是不考虑样本类别输出的无监督降维技术。LDA 的思想可以用一句话概括，就是“投影后类内方差最小，类间方差最大”。更明确的含义就是我们要将数据在低维度上进行投影，投影后希望每一种类别数据的投影点尽可能的接近，而不同类别的数据的类别中心之间的距离尽可能的大。比如当我们的每个样本的特征是二维的，我们希望将二维特征降到一维，也就是说我们要找一条直线（直线方向为 ωω）来投影，寻找的是尽可能使样本点分离并且相同类别的样本点尽可能密集的直线。如下图所示：

从直观上看，右图更好。

线性判别分析（二类情况）

假设我们有数据集 D=(x(1),y(1)),(x(2),y(2)),…,(x(m),y(m))D=(x(1),y(1)),(x(2),y(2)),…,(x(m),y(m))，一共有 mm 个样本，其中 y(i)∈c1,c2y(i)∈c1,c2，x(i)x(i) 的维度为 nn，x(i)=[x(i)1,x(i)2,…,x(i)n]Tx(i)=[x1(i),x2(i),…,xn(i)]T。另外假设我们一共有 N1N1 个样本属于 c1c1 类，这 N1N1 个点的集合为 X1X1，N2N2 个样本属于 c2c2 类，这 N2N2 个点的集合为 X2X2。现在我们觉得原始特征数太多，想将 nn 维特征降到只有一维。也就是将数据点投影到一条直线上。这条直线的基本选取规则在上文已经介绍过了。现在假设这条直线的最佳方向为 ωω。

样例点 x(i)x(i) 到直线的投影可以表示为：
ωTx(i)ωTx(i)

每类样例的均值（中心点）为：
μj=1Nj∑x(i)∈Xjx(i)(j=1,2)μj=1Nj∑x(i)∈Xjx(i)(j=1,2)

投影后的每类样本点的均值（中心点）为：
˜μj=2Nj∑x(i)∈XjωTx(i)=ωTμj(j=1,2)μj~=2Nj∑x(i)∈XjωTx(i)=ωTμj(j=1,2)

首先考虑使“不同类别的类别中心之间的距离尽可能的大”。也就是使下式的 J(ω)J(ω) 越大越好。
J(w)=|˜μ1−˜μ2|=|ωT(μ1−μ2)|J(w)=|μ1~−μ2~|=|ωT(μ1−μ2)|

但是只考虑这一点是不够的，如下图所示，样本点均匀分布在椭圆里，投影到横轴 x1x1 上时能够获得更大的中心点间距 J(w)J(w)，但是由于有重叠，x1x1 不能分离样本点。投影到纵轴 x2x2 上，虽然 J(w)J(w) 较小，但是能够分离样本点。因此我们还需要考虑样本点之间的方差，方差越大，样本点越难以分离。

我们使用另外一个度量值，称作散列值（scatter），对投影后的类求散列值：
˜sj2=∑x(i)∈Xj(ωx(i)−˜μj)2(j=1,2)sj~2=∑x(i)∈Xj(ωx(i)−μj~)2(j=1,2)
从公式中可以看出，只是少除以样本数量的方差值，散列值的几何意义是样本点的密集程度，值越大，越分散，反之，越集中。

而我们想要的投影后的样本点的样子是：不同类别的样本点越分开越好，同类的越聚集越好，也就是均值差越大越好，散列值越小越好。我们结合散列值可以得到下式：
J(w)=|˜μ1−˜μ2|2˜s12+˜s22J(w)=|μ1~−μ2~|2s1~2+s2~2

将散列值展开：
˜sj2=∑x(i)∈Xj(ωx(i)−˜μj)2 =∑x(i)∈Xj(ωx(i)−ωμj)2 =∑x(i)∈XjωT(x(i)−μj)(x(i)−μj)Tωsj~2=∑x(i)∈Xj(ωx(i)−μj~)2=∑x(i)∈Xj(ωx(i)−ωμj)2=∑x(i)∈XjωT(x(i)−μj)(x(i)−μj)Tω

为了简化式子，我们做以下定义：
sj=∑x(i)∈Xj(x(i)−μj)(x(i)−μj)Tsj=∑x(i)∈Xj(x(i)−μj)(x(i)−μj)T

这个公式的样子不就是少除以样例数的协方差矩阵么，称为散列矩阵（scatter matrices）。

当确定了 ωω，也就确定了 s1s1 和 s2s2。我们定义：
sω=s1+s2sω=s1+s2
其中 SωSω 称为 within-class scatter matrix。

我们可以得到：
˜sj2=ωTsjω ˜s12+˜s22=ωTsωωsj~2=ωTsjωs1~2+s2~2=ωTsωω

然后我们展开分子：
|˜μ1−˜μ2|2=(ωT(μ1−μ2))2=ωT(μ1−μ2)(μ1−μ2)Tω|μ1~−μ2~|2=(ωT(μ1−μ2))2=ωT(μ1−μ2)(μ1−μ2)Tω

同样为了简化式子，我们令：
Sb=(μ1−μ2)(μ1−μ2)TSb=(μ1−μ2)(μ1−μ2)T
SbSb 称为 between-class scatter。

我们最终可以推导出我们的优化目标为：
argmaxwJ(w)=wTSbwwTSwwargmax⏟wJ(w)=wTSbwwTSww

在我们求导之前，需要对分母进行归一化，因为不做归一的话，ωω 可以任意的扩大缩小。那么就没有办法确定 ωω 的方向了。所以我们令 ∥ωTSωω∥‖ωTSωω‖ = 1。那么可以发现这是一个带约束条件的求最大值的问题。哦我们可以用拉格朗日乘数法来求解，我们写除拉格朗日函数：
C(ω)=ωTSbω−λ(ωTSωω)C(ω)=ωTSbω−λ(ωTSωω)
求导，令导数为 0：
Sbω=λSωωSbω=λSωω

若 SωSω 可逆，那么：
S−1ωSbω=λS−1ωSωω=λωSω−1Sbω=λSω−1Sωω=λω
也就是说此时 ωω 为 S−1ωSbSω−1Sb 的特征向量。这个公式称为 Fisher linear discrimination。

再观察下以下公式：
Sb=(μ1−μ2)(μ1−μ2)TSb=(μ1−μ2)(μ1−μ2)T

两边同时乘上 ωω，可得：
Sbω=(μ1−μ2)(μ1−μ2)Tω=(μ1−μ2)λwSbω=(μ1−μ2)(μ1−μ2)Tω=(μ1−μ2)λw

将上式带入 S−1ωSbω=λS−1ωSωω=λωSω−1Sbω=λSω−1Sωω=λω 可得：
S−1ω(μ1−μ2)λw=λωSω−1(μ1−μ2)λw=λω
再因为对 ωω 扩大缩小任何倍不影响结果，因此可以约去两边的未知常数 λλ 和 λwλw，得到下式：
S−1ω(μ1−μ2)=ωSω−1(μ1−μ2)=ω

至此，我们只需要求出原始样本的均值和方差就可以求出最佳的方向 ωω，这就是 Fisher 于 1936 年提出的线性判别分析。

文章标题:线性判别分析

文章字数:1,545

本文作者:ylhao

发布时间:2018-05-18, 21:28:26

最后更新:2019-06-07, 11:50:53

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。