四、线性判别分析

  1. 线性判别分析Linear Discriminant Analysis:LDA 基本思想:

    • 训练时:给定训练样本集,设法将样例投影到某一条直线上,使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远离。要学习的就是这样的一条直线。
    • 预测时:对新样本进行分类时,将其投影到学到的直线上,在根据投影点的位置来确定新样本的类别。

4.1 二分类模型

  1. 考虑二类分类问题。设数据集为:四、线性判别分析 - 图1

4.1.1 投影

  1. 四、线性判别分析 - 图2 表示类别为 0 的样例的集合,这些样例的均值向量为 四、线性判别分析 - 图3,这些样例的特征之间协方差矩阵为 四、线性判别分析 - 图4(协方差矩阵大小为 四、线性判别分析 - 图5)。

    四、线性判别分析 - 图6 表示类别为 1 的样例的集合,这些样例的均值向量为 四、线性判别分析 - 图7,这些样例的特征之间协方差矩阵为 四、线性判别分析 - 图8(协方差矩阵大小为 四、线性判别分析 - 图9

  2. 假定直线为: 四、线性判别分析 - 图10,其中 四、线性判别分析 - 图11

    这里省略了常量 四、线性判别分析 - 图12 ,因为考察的是样本点在直线上的投影,总可以平行移动直线到原点而保持投影不变,此时 四、线性判别分析 - 图13

    将数据投影到直线上,则:

    • 两类样本的中心在直线上的投影分别为 四、线性判别分析 - 图14四、线性判别分析 - 图15
    • 两类样本投影的方差分别为 四、线性判别分析 - 图16四、线性判别分析 - 图17

    由于直线是一维空间,因此上面四个值均为实数

    LDA

  3. 根据线性判别分析的思想:

    • 要使得同类样例的投影点尽可能接近,则可以使同类样例投影点的方差尽可能小,即 四、线性判别分析 - 图19 尽可能小

    • 要使异类样例的投影点尽可能远,则可以使异类样例的中心的投影点尽可能远,即 四、线性判别分析 - 图20 尽可能大

    • 同时考虑两者,则得到最大化的目标:

      四、线性判别分析 - 图21

      .

4.1.2 求解

  1. 定义类内散度矩阵和类间散度矩阵:

    • 类内散度矩阵 within-class scatter matrix

      四、线性判别分析 - 图22

      它是每个类的散度矩阵之和。

    • 类间散度矩阵 between-class scatter matrix四、线性判别分析 - 图23

      它是向量 四、线性判别分析 - 图24 与它自身的外积。

  2. 利用类内散度矩阵和类间散度矩阵,线性判别分析的最优化目标为:

    四、线性判别分析 - 图25

    四、线性判别分析 - 图26 也称作 四、线性判别分析 - 图27四、线性判别分析 - 图28 的广义瑞利商 。

  3. 现在求解最优化问题:

    四、线性判别分析 - 图29

    • 考虑到分子与分母都是关于 四、线性判别分析 - 图30 的二次项,因此上式的解与 四、线性判别分析 - 图31 的长度无关,只与 四、线性判别分析 - 图32 的方向有关。令 四、线性判别分析 - 图33,则最优化问题改写为:

    四、线性判别分析 - 图34

    • 应用拉格朗日乘子法,上式等价于 四、线性判别分析 - 图35

      • 四、线性判别分析 - 图36,其中 四、线性判别分析 - 图37 为实数。则 四、线性判别分析 - 图38 。代入上式有:

        四、线性判别分析 - 图39

      • 由于与 四、线性判别分析 - 图40 的长度无关,可以令 四、线性判别分析 - 图41 则有:

        四、线性判别分析 - 图42

      • 考虑数值解的稳定性,在实践中通常是对 四、线性判别分析 - 图43 进行奇异值分解: 四、线性判别分析 - 图44,其中 四、线性判别分析 - 图45 为实对角矩阵,对角线上的元素为 四、线性判别分析 - 图46 的奇异值 ;四、线性判别分析 - 图47 均为酉矩阵,它们的列向量分别构成了标准正交基。

        然后 四、线性判别分析 - 图48

4.2 多分类模型

  1. 可以将线性判别分析推广到多分类任务中。

  2. 假定存在 四、线性判别分析 - 图49 个类,属于第 四、线性判别分析 - 图50 个类的样本的集合为 四、线性判别分析 - 图51四、线性判别分析 - 图52 中的样例数为 四、线性判别分析 - 图53 。其中: 四、线性判别分析 - 图54四、线性判别分析 - 图55 为样本总数。

    • 定义类别 四、线性判别分析 - 图56 的均值向量为:所有该类别样本的均值:

      四、线性判别分析 - 图57

      类别 四、线性判别分析 - 图58 的样例的特征之间协方差矩阵为 四、线性判别分析 - 图59 (协方差矩阵大小为 四、线性判别分析 - 图60)。

    • 定义 四、线性判别分析 - 图61 是所有样例的均值向量。

  3. 定义各类别的类内散度矩阵、总的类内散度矩阵、总的类间散度矩阵:

    • 定义类别 四、线性判别分析 - 图62 的类内散度矩阵为:

      四、线性判别分析 - 图63

      它实际上就等于样本集 四、线性判别分析 - 图64 的协方差矩阵 四、线性判别分析 - 图65, 刻画了同类样例投影点的方差。

    • 定义总的类内散度矩阵为: 四、线性判别分析 - 图66

      它 刻画了所有类别的同类样例投影点的方差。

    • 定义总的类间散度矩阵为:四、线性判别分析 - 图67

      它刻画了异类样例的中心的投影点的相互距离。

      注意:四、线性判别分析 - 图68 也是一个协方差矩阵,它刻画的是第 四、线性判别分析 - 图69 类与总体之间的关系。

      • 由于这里有不止两个中心点,因此不能简单的套用二分类线性判别分析的做法。

        这里用每一类样本集的中心点与总的中心点的距离作为度量。

      • 考虑到每一类样本集的大小可能不同(密度分布不均),对这个距离施加权重,权重为每类样本集的大小。

  4. 根据线性判别分析的思想,设四、线性判别分析 - 图70 是投影矩阵。经过推导可以得到最大化的目标:

    四、线性判别分析 - 图71

    其中 四、线性判别分析 - 图72 表示矩阵的迹。

    • 一个矩阵的迹是矩阵对角线的元素之和,它是一个矩阵不变量,也等于所有特征值之和。
    • 还有一个常用的矩阵不变量就是矩阵的行列式,它等于矩阵的所有特征值之积。
  5. 与二分类线性判别分析不同,在多分类线性判别分析中投影方向是多维的,因此使用投影矩阵 四、线性判别分析 - 图73

    二分类线性判别分析的投影方向是一维的(只有一条直线),所以使用投影向量 四、线性判别分析 - 图74

  6. 上述最优化问题可以通过广义特征值问题求解: 四、线性判别分析 - 图75

    • 四、线性判别分析 - 图76 的解析解为 四、线性判别分析 - 图77四、线性判别分析 - 图78 个最大广义特征值所对应的特征向量组成的矩阵。
    • 多分类线性判别分析将样本投影到 四、线性判别分析 - 图79 维空间。
    • 通常 四、线性判别分析 - 图80 远小于数据原有的特征数,LDA因此也被视作一种经典的监督降维技术。