您的位置: 首页  >  文章  >  机器学习：线性(Fisher)判别分析

机器学习：线性(Fisher)判别分析

分类: 文章 • 2025-03-04 09:42:23

文章目录

前言

线性(Fisher)判别分析(Linear Discriminant Analysis, LDA)也属于线性分类方法的一种，由(Fisher,1936)提出，所以也叫Fisher判别分析。

LDA的基本思想是：对于给定的训练数据样本，将样本投影到一条直线上，让同类的样例的投影点尽可能近，异类样例投影点尽可能远，这样就区分开了两类样本。当对新的样本预测时，将其投影到这条直线上，看其离哪个分类近来确定它的类别。

将上面的思想转化成对目标函数的优化，就得到了：
max⁡wJ(w)=类间平均距离类内平均距离 \max_{\mathbf w}J(\mathbf w) = \frac{类间平均距离}{类内平均距离}

下图是LDA的二维示意图：
机器学习：线性(Fisher)判别分析

一、散度矩阵

首先设给定数据集D={(xi,yi)i=1m,yi∈{0,1}}D=\{(\mathbf x_i,y_i)_{i=1}^m, y_i\in \{0,1\}\}，我们需要用给定数据去刻画类间和类内距离。

  • 类间距离
    两类样本的类间距离怎么刻画？这么多点，只能通过找两个代表性的点来计算距离，显然是均值向量点。将两个均值向量(μ1,μ2\mu_1,\mu_2)投影到直线上，得到投影点（m1,m2m_1,m_2）之间的距离平方(m1−m2)2(m_1-m_2)^2。 向量μ\mu在另一向量w\mathbf w上的投影为wTμ\mathbf w^T \mu(忘了的可以看机器学习：线性分类问题（基础知识）)。
    机器学习：线性(Fisher)判别分析
    由此我们有
    类间距离的平方=(m1−m2)2=[wT(μ→1−μ→2)]2=[wT(μ→1−μ→2)][wT(μ→1−μ→2)]T=wT(μ→1−μ→2)(μ→1−μ→2)Tw=wTSbwSb=(μ→1−μ→2)(μ→1−μ→2)T,类间散度矩阵 类间距离的平方= (m_1-m_2)^2 \\ = [\mathbf w^T(\overrightarrow \mu_1-\overrightarrow \mu_2)] ^2\\ = [\mathbf w^T(\overrightarrow \mu_1-\overrightarrow \mu_2)][\mathbf w^T(\overrightarrow \mu_1-\overrightarrow \mu_2)]^T\\ = \mathbf w^T(\overrightarrow \mu_1-\overrightarrow \mu_2)(\overrightarrow \mu_1-\overrightarrow \mu_2)^T\mathbf w\\ = \mathbf w^T S_b \mathbf w\\ S_b = (\overrightarrow \mu_1-\overrightarrow \mu_2)(\overrightarrow \mu_1-\overrightarrow \mu_2)^T,类间散度矩阵

  • 类内距离
    所谓类内距离刻画的就是同类中各个样本的松散程度，只要看每个点和均值点的距离平方和类内散裂度（类似方差）即可。类内散列度越小，意味着样本靠的越近。
    机器学习：线性(Fisher)判别分析
    由此，记类内散列度为Sc2S_c^2有
    Sc2=∑i∈C(wTxi−mc)2=∑i∈C(wT(xi−μ→c)2)=∑i∈C[wT(xi−μ→c)][wT(xi−μ→c)]T=∑i∈CwT(xi−μ→c)(xi−μ→c)Tw=wT[∑i∈C(xi−μ→c)(xi−μ→c)T]w S_c^2 = \sum_{i\in C}(\mathbf w^T\mathbf x_i - m_c)^2 \\ = \sum_{i\in C}(\mathbf w^T(\mathbf x_i - \overrightarrow \mu_c)^2)\\ = \sum_{i\in C}[\mathbf w^T(\mathbf x_i - \overrightarrow \mu_c)][\mathbf w^T(\mathbf x_i - \overrightarrow \mu_c)]^T\\ = \sum_{i\in C}\mathbf w^T(\mathbf x_i-\overrightarrow \mu_c)(\mathbf x_i-\overrightarrow \mu_c)^T\mathbf w\\ = \mathbf w^T[\sum_{i\in C}(\mathbf x_i-\overrightarrow \mu_c)(\mathbf x_i-\overrightarrow \mu_c)^T]\mathbf w
    但这只是一个分类的，要同时考虑两个分类的类内散列度，如下
    S12+S22=wT[∑i∈C1(xi−μ→1)(xi−μ→1)T]w+wT[∑i∈C2(xi−μ→2)(xi−μ→2)T]w=wT[∑j=1,2∑i∈Cj(xi−μ→j)(xi−μ→j)T]w=wTSwwSw=∑j=1,2∑i∈Cj(xi−μ→j)(xi−μ→j)T,类内散度矩阵S_1^2 + S_2^2 = \mathbf w^T[\sum_{i\in C_1}(\mathbf x_i-\overrightarrow \mu_1)(\mathbf x_i-\overrightarrow \mu_1)^T]\mathbf w \\+ \mathbf w^T[\sum_{i\in C_2}(\mathbf x_i-\overrightarrow \mu_2)(\mathbf x_i-\overrightarrow \mu_2)^T]\mathbf w \\ = \mathbf w^T[\sum_{j=1,2}\sum_{i\in C_j} (\mathbf x_i-\overrightarrow \mu_j)(\mathbf x_i-\overrightarrow \mu_j)^T]\mathbf w \\ = \mathbf w^T S_w\mathbf w \\ S_w = \sum_{j=1,2}\sum_{i\in C_j} (\mathbf x_i-\overrightarrow \mu_j)(\mathbf x_i-\overrightarrow \mu_j)^T,类内散度矩阵

    推导过程其实不难，仔细一点就能理解

二、目标函数与权重向量

有了类间距离和类内距离的刻画后， 依据上文的定义，可以得到我们的目标函数如下：
max⁡wJ(w)=类间距离类内距离=(m1−m2)2S12+S22=wTSbwwTSww \max_{\mathbf w} J(\mathbf w) = \frac{类间距离}{类内距离} \\ = \frac{(m_1-m_2)^2}{S_1^2+S_2^2} \\ = \frac{ \mathbf w^T S_b \mathbf w}{ \mathbf w^T S_w\mathbf w}
理解该公式中Sb,SwS_b,S_w都是根据训练数据确定的值，我们的目标是找到使得JJ最大的w\mathbf w,利用拉格朗日乘子法，原问题可转变为
max⁡wL(w,λ)=wTSbw−λ(wTSww−C)\max_{\mathbf w} L(\mathbf w, \lambda) = \mathbf w^T S_b \mathbf w - \lambda(\mathbf w^T S_w \mathbf w-C)
对w\mathbf w求偏导可得，
∂L(w,λ)∂w=Sbw−λSww=0  ⟹  Sbw=λSww  ⟹  Sw−1Sbw=λw\frac{\partial L(\mathbf w, \lambda)}{\partial \mathbf w} = S_b\mathbf w- \lambda S_w\mathbf w = 0\\ \implies S_b\mathbf w = \lambda S_w\mathbf w \\ \implies S_w^{-1}S_b\mathbf w = \lambda \mathbf w
实际上到这已经发现w\mathbf w是Sw−1SbS_w^{-1}S_b的特征向量了，用求特征向量的方法即可得到w\mathbf w。但是可以利用Sb=(μ→1−μ→2)(μ→1−μ→2)TS_b = (\overrightarrow \mu_1-\overrightarrow \mu_2)(\overrightarrow \mu_1-\overrightarrow \mu_2)^T对其进一步化简，如下
Sbw=(μ→1−μ→2)(μ→1−μ→2)Tw=(μ→1−μ→2)[(μ→1−μ→2)Tw],[]内是个标量=β(μ→1−μ→2)S_b \mathbf w = (\overrightarrow \mu_1-\overrightarrow \mu_2)(\overrightarrow \mu_1-\overrightarrow \mu_2)^T\mathbf w \\= (\overrightarrow \mu_1-\overrightarrow \mu_2)[(\overrightarrow \mu_1-\overrightarrow \mu_2)^T\mathbf w],[]内是个标量\\ = \beta (\overrightarrow \mu_1-\overrightarrow \mu_2)
将结果带入上面得到
Sw−1β(μ→1−μ→2)=λw  ⟹  w=βλSw−1(μ→1−μ→2)  ⟹  w=Sw−1(μ→1−μ→2),βλ相当于对w放缩，可以省略S_w^{-1}\beta (\overrightarrow \mu_1-\overrightarrow \mu_2) = \lambda \mathbf w \\ \implies \mathbf w = \frac{\beta}{\lambda} S_w^{-1}(\overrightarrow \mu_1-\overrightarrow \mu_2)\\ \implies \mathbf w = S_w^{-1}(\overrightarrow \mu_1-\overrightarrow \mu_2),\frac{\beta}{\lambda} 相当于对\mathbf w放缩，可以省略

至此，我们就将所需直线的方向向量w\mathbf w（也是样本的权重向量）计算出来了。实际上当直线的方向确定后，各类样本在直线上投影的相对位置就确定了，即类间距离和类内距离确定。但是为了方便决策，我们希望在投影之后有一个明确的数值分解，例如0，投影结果大于0是一类，投影结果小于0是一类，而这个就是决策函数g(x)=wTx+w0g(\mathbf x) = \mathbf w^T\mathbf x +w_0的偏置w0w_0决定。考虑两类均值向量的中心点12(μ→1+μ→2)\frac{1}{2}(\overrightarrow \mu_1+\overrightarrow \mu_2)，这个点样本讲道理应该可以任意分入两类，也可以两边都不分入，所以作为分界点最合适，我们的决策函数应该要通过该点，因此有
w0=−12(wTμ→1+wTμ→2)g(x)=wTx+w0w_0 = -\frac{1}{2}(\mathbf w^T\overrightarrow \mu_1+\mathbf w^T\overrightarrow \mu_2) \\ g(\mathbf x ) = \mathbf w^T\mathbf x + w_0

三、总结

线性鉴别分析的主要思想还是很好理解的，就是一个类间距离和一个类内距离，让类间距离尽可能大，分类界限更清晰，类内距离尽可能小，同类更紧密。由上面的思想可以将Fisher鉴别分成如下几步：

  1. 根据正反例求各类均值μ→1,μ→2\overrightarrow \mu_1,\overrightarrow \mu_2，作为类别间最大方向

  2. 求类内散度矩阵SwS_w
    Sw=∑i=12∑x∈Ci(x−μi)(x−μi)T S_w = \sum_{i=1}^2 \sum_{x\in C_i}(x-\mu_i)(x-\mu_i)^T

  3. 求类内散度矩阵的逆Sw−1S_w^{-1}

  4. 求权重向量w\mathbf w
    w=Sw−1(μ1−μ2) \mathbf w = S_w^{-1}(\mu_1-\mu_2)

  5. 计算两类投影中心u1,u2u_1,u_2
    ui=wTμi,i=1,2 u_i = \mathbf w^T \mu_i, i=1,2

  6. 得到决策函数
    g(x)=wTx−12(u1+u2) g(\mathbf x ) = \mathbf w^T\mathbf x -\frac{1}{2}(u_1+u_2)

参考资料

  • 周志华. 机器学习. 2016
  • 周晓飞. Fisher线性鉴别推导过程

相关推荐