有朋友问：为什么感觉对机器学习和神经网络，似乎总是隔着一层纱那样，不清晰，虽然能跑代码，但总是不放心，不知道自己做的是否有根据。 这是因为：你和机器学习之间，缺少了一个数学。

费雪的线性判别分析

缘起

对于线性判别分析的介绍，在网上或者有关书籍中，均能找到不少资料。但是，诸多内容中，未能将线性判别分析完整地讲解，要么缺失较为严格的数学推理，要么对线性判别分析的理解偏颇。

本文作者根据个人所学，参考有关文献，将线性判别分析给予梳理，供大家参考。

费雪的线性判别分析

英国统计学家费雪（Ronald Fisher）提出的专门为含有两个类别样本的有监督的降维方法，称为“费雪的线性判别分析（Fisher Linear Discriminant Analysis）。

费雪的线性判别分析基本思想是（如图1所示）：

图 1
  • 类内散度最小
  • 类间散度最大

获得数据在某直线（超平面）上的投影。

多数资料中介绍的线性判别分析的时候，都是按照上述费雪所提出的线性判别分析思想讲解的。

本文也首先介绍上述基本思想，而后引申出相关思考。

注意：以下内容是以数学推导为主，对此方面如读者有感不足，请参阅：《机器学习数学基础》的书籍或视频课程

二分类的样本数据

设数据样本 ，样本大小为 ，特征数（维数）是 。

假设此样本分为两类，类别 ，样本数为 ；类别 ，样本数量为 。 。

问题：投影可能重叠

有一条直线 L ，用单位向量 （）表示此直线的方向。

若将样本中的任意一个向量 向此直线投影，得到投影量 ，其中 表示投影量的大小。

由于 与 正交，即： ，所以： 故样本中每个数据 在直线 L 上的投影大小 为： 所在的空间称为 空间，投影 所在的空间称为 空间。

根据（2）式结果，可以得到 空间的每个类别样本的投影大小的平均数： 令 （），代表 空间的某个类别的所有样本的平均数向量（样本平均），故（3）式可以继续表示为： （4）式即表示将 空间的每个类别的样本平均（即向量 ，表示该类别的中心），投影到直线 L ，得到了 空间上每个类别样本投影的平均数（即 ，表示该类别样本投影的中心）。

于是得到两个类别样本中心投影的距离： （5）式说明，每个类别样本投影的中心的距离（ ）等于样本中心的距离（即 ）的投影 。

数据点与数据点之间的距离，表征了数据的分散程度，统计学中使用方差衡量数据的分散程度 （样本方差： ） 。因此，可以使用 度量不同类别的样本投影的中心的分散程度，并将其命名为类间散度（Between-class scatter），即： 散度与方差有相同的地方，都表示了数据相对平均值的分散程度。下图左边表示了散度较大，右边较小。

下面使用拉格朗日乘数法 ，找到适合的 ，使得 最大化。 定义拉格朗日函数： 其中 是拉格朗日乘数。计算 ： 令 ，则： 因为 是数量，所以： 这说明直线 L 的方向与两个类别的样本中心的距离矢量方向平行。

但是，如果按照（11）式的方式确定直线 L 方向，样本的投影有可能出现图 1 所示的重叠现象。

从降维的角度看，假设是将高维数据降到一维，上图演示的降维效果并不会有利于后续分类过程。

对此，费雪提出，应该兼顾类别之间和同一类别之内的样本投影的方差：

  • 不同类别之间的样本投影的方差越大越好
  • 同一类之内的样本投影的方差越小越好

这样，在直线上的投影，不同类别之间的中心的投影的距离就尽可能大；同一类别之内的样本的投影间就尽可能聚集在一起。

费雪准则

两个类别的样本数据的平均数，表示每个类别的样本数据的中心： 以下将 表述为两个类别分别在 空间的平均数向量。

在直线 L 上，两个类别的样本投影的平均数，表示每个类别的样本数据投影的中心： 以下将 表述为在 空间的平均数。

仿照方差的定义形式，定义 空间衡量类别内数据投影相对投影中心的分散程度的量： 空间类内散度（Within-calss scatter）： 前述（6）式定义了 空间的类间散度： 根据费雪的思想，既要实现 空间的类间散度最大化，同时又要实现 空间的类内散度最小化。也就是实现下述函数最大化：

散度矩阵

以下分别写出 空间的类内、类间散度的矩阵表示形式，分别称为散度矩阵：

  • 空间的类内散度矩阵：

  • 空间整体的类内散度矩阵：

  • 空间的类间散度矩阵：

其中 见（12）式。

根据（14）式和（2）、（13）式， 空间的类内散度 等于： 故： 空间的类间散度 等于： 于是，（16）式的费雪准则，可以用（21）式和（22）式的结果表示为： 由（17）和（18）式可知， 是半正定矩阵，如果样本大小 大于维数 （这种情况比较常见），则 一般为正定，且可逆。

由（19）式可知， 是半正定矩阵，若 ，则 。

最优化问题求解

对（23）式的最大化求解，可以有多种方法：

  • 法1：直接计算 求解
  • 法2：用线性代数方法：因为（23）式也称为广义瑞利商，故可以根据冠以特征值求解
  • 法3：拉格朗日乘数法：参考资料 [1] 中使用的这个方法，但推导过程不详细。

法1：

最直接的思路： 所以，得到（以下使用了矩阵导数，请见参考资料 [2] ）： 上式两侧同时除以 ，得： 对（26）式最后结果等号两边同时左乘 （其中 是标量函数），得： 又因为上式中的 是标量，故令： ，则上式进一步写成： 由此，可知：直线 L 的方向 满足： 此时能够实现费雪准则的要求，即 最大化。

这样，就找到了最佳投影的直线（或超平面），从而实现了最佳降维的目的。

法2：

由（18）和（19）式可知， 、 ，即 和 都是实对称矩阵，亦即厄米矩阵，故（23）式可以看做广义瑞利商 。

从而对 的最大化问题，等价于广义特征值问题，如下述方程： 因为 可逆，故： 又因为 和 都是半正定矩阵，所以 的特征值 是非负数，则特征向量 是实特征向量。

于是，可以对（30）式等号两边同时左乘 ，得： 将（32）式代入到（23）式，可得： 由此可知，只要找出最大的特征值，即可得到 的最大值。

又因为 ，则说明（31）式中的 只有一个大于零的特征值。

将（19）式中的 代入到（31）式中，得： 上式中的 是标量，故令： ，则上式进一步写成： 从而得到与（29）式同样的结论和解释。

法3：

对于（23）式，因为分子分母都有 ，故 与 的长度无关，可以设 ，则对（23）式的最大化问题，即转化为：

根据拉格朗日乘数法： 计算 ： 令： ，则： 因为 可逆，所以有： ，再将（19）式的 代入此时，得到： 这与（34）式雷同，只不过（40）中的 是拉格朗日乘数，但形式一样，故可得： 与（29）同样的结果。

在以上讨论中，使用三种方法找到了 的方向，虽然一般资料不如本文如此细致地讲解其来源，但也通常能给出最终结论。至此，事实上实现的是数据的降维（注意区别于 PCA），并没有实现对数据属于哪一个类别的“判别分析”。

当找到了 方向之后，假设有数据 ，要判断属于哪一个类别，必须要有阈值 ，即：

  • 当 时， 属于 类
  • 否则，属于 类

而 是多少？这在费雪的线性判别分析中并未提及。所以需要进一步探讨。

后续文章，会揭示 是多少，并进而实现对数据所述类别的判别分析。

计算判别阈值

如果要判别某个样本属于哪一类，上述的阈值 必须要求出来，求解方法有两种：

  1. 贝叶斯方法。此方法在另外一篇《线性判别分析》中详解
  2. 最小二乘法。此处演示此方法的求解过程

最小二乘法

将两个类别的线性边界写作： 相应的最小平方误差函数： 其中， 是样本数据的类别标签，即样本类别的真实值。若 ，则 为正例，否则为负例，不妨分别假设两个类别的标签分别是：

将（43）式分别对 和 求导：

令（44）式为零，即： 所以： 其中：

  • 是样本平均值（向量），记作
  • 前述（43）式后令 ，则

所以，（47）最终得： 而对于 ，在前述最优化求解中，已经得到： ，（如（41）式），又因为 的长度不影响边界，故可直接令： 于是，可以用： 作为判别标准。

检验

若 ，很显然，此样本属于 类，利用（50）式对此结论进行检验：

  • 由（18）式知：

于是，（51）式继续计算如下： （半）正定。

所以，检验成功。

用最小二乘法计算

在（45）式中，得到了 ，令它等于零，则可以计算 ，但是步骤比较繁琐，以下仅供参考。

由（17）式可得： 所以： 令（45）式的 ，即： 下面对上式等号左右两边分别计算： 因为 是标量，所以：

多类别判别分析

需要将上述两个类别下的类内散度和类间散度矩阵推广到多类别。

1. 多类别的类内散度矩阵

（18）式定义了 空间两个类别的类内散度矩阵，将其定义方式可以直接推广到多类别的类内散度矩阵： 其中：

  • ，
  • 且 ，共计有 个类别。
  • 表示总样本数等于每个类别样本数的和

2. 多类别的类间散度矩阵

多类别的类间散度矩阵，不能由（19）式直接推广。

令 表示 空间的全体样本的平均数（向量），即： 对于所有的样本，仿照样本（有偏）方差的定义，可以定义针对 空间的所有样本的 Total scatter matrix（参考资料 [1] 中称为“全局散度矩阵”。愚以为，由于此概念是针对当前全体样本而言，如果用“全局”一词，容易引起与“总体”的错误联系，是否可译为：全体样本散度矩阵）： 将（（60）式进一步写成： 因为：

  • 由（58）式可得：
  • 因为 （每个样本与平均数的差求和，结果为 0 ），故得：

所以，（61）式为： 令： 即为多类别的类间散度矩阵。

对于（63）式，如果 ，即为二类别下的类间散度矩阵： （64）式最终得到的二类别下的类间散度矩阵和（19）式相比，多了系数 ，因为它是常数，不会影响对 最大化求解。

3. 多类别样本下的费雪准则

假设由 个单位向量 作为 空间样本数据 投影的超平面（直线）方向，得到： 写成矩阵形式： 其中 是 矩阵。

由此，得到了 空间的样本 投影到 上的投影，即得到 空间的数据 ：

仿照 空间计算平均值（向量）的方法，计算 空间投影数据的平均值：

从而定义 空间的类内散度矩阵和类间散度矩阵

将（67）（68）代入到（70），得到： 将（68）（69）带入到（71），得到： 由此，多类别下的费雪准则，其目标函数有两种表示方式：

  • 第一种：用矩阵的迹表示

  • 第二种：用行列式表示

不论以上哪种形式，最终均可得到如下最优化条件： 由上式得： 。参考（30）式之后的推导， 为广义特征值， 是广义特征向量。以（74）式为例，可得如下结论（详细推导过程，请见参考资料 [7] 中的推导过程） 因特征值非负，故 。

又因为 是 的线性组合，故： 故 。

给定包含 个类别的样本，多类别判别分析所能产生有效线性特征总数最多是 ，即降维的最大特征数。

参考资料

[1]. 周志华. 机器学习. 北京：清华大学出版社

[2]. 齐伟. 机器学习数学基础. 北京：电子工业出版社

[3]. 拉格朗日乘数法

[4]. 广义特征值与极小极大原理。以下为此参考文献部分内容摘抄：

1、定义：设 、 为 阶方阵，若存在数 ，使得方程 存在 非零解，则称 为 相对于 的广义特征值， 为 相对于 的属于 广义特征值 的特征向量。

  • 当 （单位矩阵）时，广义特征值问题退化为标准特征值问题。

  • 特征向量是非零的

  • 广义特征值的求解

    或者

    特征方程：

    求得 后代回原方程 可求出

2、等价表述

正定，且可逆，即 存在，则： ，广义特征值问题化为了标准特征值问题。

3、广义瑞丽商

若 、 为 阶厄米矩阵（Hermitian matrix，或译为“艾米尔特矩阵”、“厄米特矩阵”等），且 正定，则：

为 相对于 的瑞丽商。

[5]. 谢文睿，秦州. 机器学习公式详解. 北京：人民邮电出版社

[6]. 线代启示录：费雪的判别分析与线性判别分析

作者: 老齐
链接: http://math.itdiffer.com/fisher-lda.html
来源: 机器学习
本文原创发布于「机器学习」,转载请注明出处,谢谢合作!

http://math.itdiffer.com/images/0.jpg

results matching ""

    No results matching ""