四、线性判别分析
线性判别分析
Linear Discriminant Analysis:LDA
基本思想:- 训练时:给定训练样本集,设法将样例投影到某一条直线上,使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远离。要学习的就是这样的一条直线。
- 预测时:对新样本进行分类时,将其投影到学到的直线上,在根据投影点的位置来确定新样本的类别。
4.1 二分类模型
- 考虑二类分类问题。设数据集为: 。
4.1.1 投影
设 表示类别为
0
的样例的集合,这些样例的均值向量为 ,这些样例的特征之间协方差矩阵为 (协方差矩阵大小为 )。设 表示类别为
1
的样例的集合,这些样例的均值向量为 ,这些样例的特征之间协方差矩阵为 (协方差矩阵大小为 )假定直线为: ,其中 。
这里省略了常量 ,因为考察的是样本点在直线上的投影,总可以平行移动直线到原点而保持投影不变,此时 。
将数据投影到直线上,则:
- 两类样本的中心在直线上的投影分别为 和
- 两类样本投影的方差分别为 和
由于直线是一维空间,因此上面四个值均为实数
根据线性判别分析的思想:
要使得同类样例的投影点尽可能接近,则可以使同类样例投影点的方差尽可能小,即 尽可能小
要使异类样例的投影点尽可能远,则可以使异类样例的中心的投影点尽可能远,即 尽可能大
同时考虑两者,则得到最大化的目标:
.
4.1.2 求解
定义类内散度矩阵和类间散度矩阵:
类内散度矩阵
within-class scatter matrix
:它是每个类的散度矩阵之和。
类间散度矩阵
between-class scatter matrix
: 。它是向量 与它自身的外积。
利用类内散度矩阵和类间散度矩阵,线性判别分析的最优化目标为:
也称作 与 的广义瑞利商 。
现在求解最优化问题:
- 考虑到分子与分母都是关于 的二次项,因此上式的解与 的长度无关,只与 的方向有关。令 ,则最优化问题改写为:
应用拉格朗日乘子法,上式等价于
令 ,其中 为实数。则 。代入上式有:
由于与 的长度无关,可以令 则有:
考虑数值解的稳定性,在实践中通常是对 进行奇异值分解: ,其中 为实对角矩阵,对角线上的元素为 的奇异值 ; 均为酉矩阵,它们的列向量分别构成了标准正交基。
然后 。
4.2 多分类模型
可以将线性判别分析推广到多分类任务中。
假定存在 个类,属于第 个类的样本的集合为 , 中的样例数为 。其中: , 为样本总数。
定义类别 的均值向量为:所有该类别样本的均值:
类别 的样例的特征之间协方差矩阵为 (协方差矩阵大小为 )。
定义 是所有样例的均值向量。
定义各类别的类内散度矩阵、总的类内散度矩阵、总的类间散度矩阵:
定义类别 的类内散度矩阵为:
它实际上就等于样本集 的协方差矩阵 , 刻画了同类样例投影点的方差。
定义总的类内散度矩阵为: 。
它 刻画了所有类别的同类样例投影点的方差。
定义总的类间散度矩阵为: 。
它刻画了异类样例的中心的投影点的相互距离。
注意: 也是一个协方差矩阵,它刻画的是第 类与总体之间的关系。
由于这里有不止两个中心点,因此不能简单的套用二分类线性判别分析的做法。
这里用每一类样本集的中心点与总的中心点的距离作为度量。
考虑到每一类样本集的大小可能不同(密度分布不均),对这个距离施加权重,权重为每类样本集的大小。
根据线性判别分析的思想,设 是投影矩阵。经过推导可以得到最大化的目标:
其中 表示矩阵的迹。
- 一个矩阵的迹是矩阵对角线的元素之和,它是一个矩阵不变量,也等于所有特征值之和。
- 还有一个常用的矩阵不变量就是矩阵的行列式,它等于矩阵的所有特征值之积。
与二分类线性判别分析不同,在多分类线性判别分析中投影方向是多维的,因此使用投影矩阵 。
二分类线性判别分析的投影方向是一维的(只有一条直线),所以使用投影向量 。
上述最优化问题可以通过广义特征值问题求解:
- 的解析解为 的 个最大广义特征值所对应的特征向量组成的矩阵。
- 多分类线性判别分析将样本投影到 维空间。
- 通常 远小于数据原有的特征数,
LDA
因此也被视作一种经典的监督降维技术。