数据, 术→技巧, 机器学习, 法→原理

机器学习算法之线性判别分析(LDA)

钱魏Way · · 2,874 次浏览

线性判别分析(linear discriminant analysis, LDA)一种常用的数据降维方法,目的是在保持分类的前体下把数据投影至低维空间以降低计算复杂度。在学习LDA之前,有必要将其与自然语言处理领域的LDA区别开来,在自然语言处理领域LDA是隐含狄利克雷分布(Latent Dirichlet Allocation,简称LDA),是一种处理文档的主题模型。

LDA和PCA都是利用线性变换对数据进行降维的机器学习技术。之前也对主成分分析(PCA)原理进行了总结。PCA是一种无监督的降维技术,无视数据的分类信息挖掘数据中的模式,投影后方差最大的方向即为主成分。LDA是一种有监督的降维技术,对数据进行模式分类。如图所示,LDA要求类间的方差最大,而类内的方差最小,以保证投影后同一分类数据集中,不同分类间数据距离尽可能大。

LDA的思想可以用一句话概括,就是“投影后类内方差最小,类间方差最大”。

假设我们有两类数据分别为红色和蓝色,如下图所示,这些数据特征是二维的,我们希望将这些数据投影到一维的一条直线,让每一种类别数据的投影点尽可能的接近,而红色和蓝色数据中心之间的距离尽可能的大。

上图中提供了两种投影方式,哪一种能更好的满足我们的标准呢?从直观上可以看出,右图要比左图的投影效果好,因为右图的黑色数据和蓝色数据各个较为集中,且类别之间的距离明显。左图则在边界处数据混杂。以上就是LDA的主要思想了,当然在实际应用中,我们的数据是多个类别的,我们的原始数据一般也是超过二维的,投影后的也一般不是直线,而是一个低维的超平面。

LDA原理推导

瑞利商(Rayleigh quotient)与广义瑞利商(genralized Rayleigh quotient)

瑞利商是指这样的函数$R(A,x)$:

$$R(A,x) = \frac{x^HAx}{x^Hx}$$

其中$x$为非零向量,而A为$n \times n$的Hermitan矩阵。所谓的Hermitan矩阵就是满足共轭转置矩阵和自己相等的矩阵,即$A^H=A$。如果我们的矩阵A是实矩阵,则满足$A^T=A$的矩阵即为Hermitan矩阵。

瑞利商$R(A,x)$有一个非常重要的性质,即它的最大值等于矩阵A最大的特征值,而最小值等于矩阵A的最小的特征值,也就是满足:

$$\lambda_{min} \leq \frac{x^HAx}{x^Hx} \leq \lambda_{max}$$

当向量$x$是标准正交基时,即满足$x^Hx=1$时,瑞利商退化为:$R(A,x) = x^HAx$,这个形式在谱聚类和PCA中都有出现。

广义瑞利商是指这样的函数$R(A,B,x)$:

$$R(A,x) = \frac{x^HAx}{x^HBx}$$

其中x为非零向量,而A,B为$ n \times n$的Hermitan矩阵。B为正定矩阵。我们只要通过将其通过标准化就可以转化为瑞利商的格式。我们令$x=B^{-1/2}x’$,则分母转化为:

$$x^HBx = x’^H(B^{-1/2})^HBB^{-1/2}x’ = x’^HB^{-1/2}BB^{-1/2}x’ = x’^Hx’$$

而分子转化为:

$$x^HAx =  x’^HB^{-1/2}AB^{-1/2}x’$$

此时我们的$R(A,B,x)$转化为$R(A,B,x’)$:

$$R(A,B,x’) = \frac{x’^HB^{-1/2}AB^{-1/2}x’}{x’^Hx’}$$

利用前面的瑞利商的性质,我们可以很快的知道,$R(A,B,x’)$的最大值为矩阵$B^{-1/2}AB^{-1/2}$的最大特征值,或者说矩阵$B^{-1}A$的最大特征值,而最小值为矩阵$B^{-1}A$的最小特征值。

二类LDA原理

LDA希望投影后希望同一种类别数据的投影点尽可能的接近,而不同类别的数据的类别中心之间的距离尽可能的大,但是这只是一个感官的度量。现在我们首先从比较简单的二类LDA入手,严谨的分析LDA的原理。

假设我们的数据集$D=\{(x_1,y_1), (x_2,y_2), …,((x_m,y_m))\}$,其中任意样本$x_i$为n维向量,$y_i \in \{0,1\}$。我们定义$N_j(j=0,1)$为第j类样本的个数,$X_j(j=0,1)$为第j类样本的集合,而$\mu_j(j=0,1)$为第j类样本的均值向量,定义$\Sigma_j(j=0,1)$为第j类样本的协方差矩阵(严格说是缺少分母部分的协方差矩阵)。

$$\mu_j = \frac{1}{N_j}\sum\limits_{x \in X_j}x\;\;(j=0,1)$$

$$\Sigma_j = \sum\limits_{x \in X_j}(x-\mu_j)(x-\mu_j)^T\;\;(j=0,1)$$

由于是两类数据,因此我们只需要将数据投影到一条直线上即可。假设我们的投影直线是向量$w$,则对任意一个样本本$x_i$,它在直线$w$的投影为$w^Tx_i$,对于两个类别的中心点$\mu_0,\mu_1$,在在直线$w$的投影为$w^T\mu_0$和$w^T\mu_1$。由于LDA需要让不同类别的数据的类别中心之间的距离尽可能的大,也就是要最大化$||w^T\mu_0-w^T\mu_1||_2^2$,同时希望同一种类别数据的投影点尽可能的接近,也就是要同类样本投影点的协方差$w^T\Sigma_0w$和$w^T\Sigma_1w$尽可能的小,即最小化$w^T\Sigma_0w+w^T\Sigma_1w$。综上所述,我们的优化目标为:

$$\underbrace{arg\;max}_w\;\;J(w) = \frac{||w^T\mu_0-w^T\mu_1||_2^2}{w^T\Sigma_0w+w^T\Sigma_1w} = \frac{w^T(\mu_0-\mu_1)(\mu_0-\mu_1)^Tw}{w^T(\Sigma_0+\Sigma_1)w}$$

一般定义类内散度矩阵$S_w$为:

$$S_w = \Sigma_0 + \Sigma_1 = \sum\limits_{x \in X_0}(x-\mu_0)(x-\mu_0)^T + \sum\limits_{x \in X_1}(x-\mu_1)(x-\mu_1)^T$$

同时定义类间散度矩阵$S_b$为:

$$S_b = (\mu_0-\mu_1)(\mu_0-\mu_1)^T$$

这样优化目标重写为:

$$\underbrace{arg\;max}_w\;\;J(w) = \frac{w^TS_bw}{w^TS_ww}$$

上式就是广义瑞利商,利用广义瑞利商的性质,$J(w’)$最大值为矩阵$S^{-\frac{1}{2}}_wS_bS^{-\frac{1}{2}}_w$的最大特征值,对应的$w’$为$S^{-\frac{1}{2}}_wS_bS^{-\frac{1}{2}}_w$的最大特征值对应的特征向量。而$S_w^{-1}S_b$的特征值和$S^{-\frac{1}{2}}_wS_bS^{-\frac{1}{2}}_w$的特征值相同,$S_w^{-1}S_b$的特征向量$w$和$S^{-\frac{1}{2}}_wS_bS^{-\frac{1}{2}}_w$的特征向量$w’$满足$w = S^{-\frac{1}{2}}_ww’$的关系。

二类的时候,$S_bw$的方向恒平行于$\mu_0-\mu_1$,不妨令$S_bw=\lambda(\mu_0-\mu_1)$,将其带入:$(S_w^{-1}S_b)w=\lambda w$,可以得到$w=S_w^{-1}(\mu_0-\mu_1)$,也就是说我们只要求出原始二类样本的均值和方差就可以确定最佳的投影方向$w$了。

多类LDA原理

有了二类LDA的基础,我们再来看看多类别LDA的原理。假设我们的数据集$D=\{(x_1,y_1), (x_2,y_2), …,((x_m,y_m))\}$,其中任意样本$x_i$为n维向量,$ y_i \in \{C_1,C_2,…,C_k\}$。我们定义$ N_j(j=1,2…k)$为第j类样本的个数,$X_j(j=1,2…k)$为第j类样本的集合,而$\mu_j(j=1,2…k)$为第j类样本的均值向量,定义$\Sigma_j(j=1,2…k)$为第j类样本的协方差矩阵。在二类LDA里面定义的公式可以很容易的类推到多类LDA。

由于是多类向低维投影,则此时投影到的低维空间就不是一条直线,而是一个超平面了。假设投影到的低维空间的维度为d,对应的基向量为$(w_1,w_2,…w_d)$,基向量组成的矩阵为W, 它是一个$n \times d$的矩阵。

此时优化目标应该可以变成为:

$$\frac{W^TS_bW}{W^TS_wW}$$

其中$S_b = \sum\limits_{j=1}^{k}N_j(\mu_j-\mu)(\mu_j-\mu)^T$,$\mu$为所有样本均值向量。$S_w =  \sum\limits_{j=1}^{k}S_{wj} = \sum\limits_{j=1}^{k}\sum\limits_{x \in X_j}(x-\mu_j)(x-\mu_j)^T$

有个问题,就是$W^TS_bW$和$W^TS_wW$都是矩阵,不是标量,无法作为一个标量函数来优化。也就是说,我们无法直接用二类LDA的优化方法。一般来说,我们可以用其他的一些替代优化目标来实现。

常见的一个LDA多类优化目标函数定义为:

$$\underbrace{arg\;max}_W\;\;J(W) = \frac{\prod\limits_{diag}W^TS_bW}{\prod\limits_{diag}W^TS_wW}$$

其中$ \prod\limits_{diag}A$为A的主对角线元素的乘积,W为$ n \times d$的矩阵。

$J(W)$的优化过程可以转化为:

$$J(W) = \frac{\prod\limits_{i=1}^dw_i^TS_bw_i}{\prod\limits_{i=1}^dw_i^TS_ww_i} = \prod\limits_{i=1}^d\frac{w_i^TS_bw_i}{w_i^TS_ww_i}$$

上式最右边就是广义瑞利商。最大值是矩阵$S^{-1}_wS_b$的最大特征值,最大的d个值的乘积就是矩阵$S^{-1}_wS_b$的最大的d个特征值的乘积,此时对应的矩阵W为这最大的d个特征值对应的特征向量张成的矩阵。

由于W是一个利用了样本的类别得到的投影矩阵,因此它的降维到的维度d最大值为k-1。为什么最大维度不是类别数k?因为$S_b$中每个$\mu_j-\mu$的秩为1,因此协方差矩阵相加后最大的秩为k(矩阵的秩小于等于各个相加矩阵的秩的和),但是由于如果我们知道前k-1个$\mu_j$后,最后一个$\mu_k$可以由前k-1个$\mu_j$线性表示,因此$S_b$的秩最大为k-1,即特征向量最多有k-1个。

LDA算法流程

输入:数据集$D=\{(x_1,y_1), (x_2,y_2), …,((x_m,y_m))\}$,其中任意样本$x_i$为n维向量,$y_i \in \{C_1,C_2,…,C_k\}$,降维到的维度d。

输出:降维后的样本集$D’$

LDA进行降维算法流程:

  • 计算类内散度矩阵$S_w$
  • 计算类间散度矩阵$S_b$
  • 计算矩阵$S_w^{-1}S_b$
  • 计算$S_w^{-1}S_b$的最大的d个特征值和对应的d个特征向量$(w_1,w_2,…w_d)$,得到投影矩阵W
  • 对样本集中的每一个样本特征$x_i$,转化为新的样本$z_i=W^Tx_i$
  • 得到输出样本集$D’=\{(z_1,y_1), (z_2,y_2), …,((z_m,y_m))\}$

LDA算法小结

LDA用于降维,和PCA有很多相同,也有很多不同的地方,因此值得好好的比较一下两者的降维异同点。

相同点:

  • 两者均可以对数据进行降维
  • 两者在降维时均使用了矩阵特征分解的思想
  • 两者都假设数据符合高斯分布

不同点:

  • LDA是有监督的降维方法,而PCA是无监督的降维方法
  • LDA降维最多降到类别数k-1的维数,而PCA没有这个限制
  • LDA除了可以用于降维,还可以用于分类
  • LDA选择分类性能最好的投影方向,而PCA选择样本点投影具有最大方差的方向

若训练样本集两类的均值有明显的差异,LDA降维的效果较优,如下图:

若训练样本集两类的均值无明显的差异,但协方差差异很大,PCA降维的效果较优,如下图:

LDA最多将数据降维至C-1维,也就是说如果有两类数据,最终降维只能到1维,也就是说投影到一个直线上。这在很多情况下无法对数据进行很好的投影,例如下图中的几种情况。也就是说,LDA不适合对非高斯分布的样本进行降维。

优点:

  • 在降维过程中可以使用类别的先验知识经验,而像PCA这样的无监督学习则无法使用类别先验知识。
  • LDA在样本分类信息依赖均值而不是方差的时候,比PCA之类的算法较优。

缺点:

  • LDA不适合对非高斯分布样本进行降维,PCA也有这个问题
  • LDA降维最多降到类别数k-1的维数,如果我们降维的维度大于k-1,则不能使用LDA。当然目前有一些LDA的进化版算法可以绕过这个问题
  • LDA在样本分类信息依赖方差而不是均值的时候,降维效果不好
  • LDA可能过度拟合数据

LDA使用实例

sklearn实现:

class sklearn.discriminant_analysis.LinearDiscriminantAnalysis(solver='svd', shrinkage=None, priors=None, n_components=None, store_covariance=False, tol=0.0001)

参数说明:

  • solver: 即求LDA超平面特征矩阵使用的方法。可以选择的方法有奇异值分解”svd”,最小二乘”lsqr”和特征分解”eigen”。一般来说特征数非常多的时候推荐使用svd,而特征数不多的时候推荐使用eigen。主要注意的是,如果使用svd,则不能指定正则化参数shrinkage进行正则化。默认值是svd
  • shrinkage:正则化参数,可以增强LDA分类的泛化能力。如果仅仅只是为了降维,则一般可以忽略这个参数。默认是None,即不进行正则化。可以选择”auto”,让算法自己决定是否正则化。当然我们也可以选择不同的[0,1]之间的值进行交叉验证调参。注意shrinkage只在solver为最小二乘”lsqr”和特征分解”eigen”时有效。
  • Shrinkage:str or float类型,默认值为None。是否使用参数收缩
    • None:不使用参数收缩
    • auto:str,使用Ledoit-Wolf lemma
    • 浮点数:自定义收缩比例
  • priors:类别权重,可以在做分类模型时指定不同类别的权重,进而影响分类模型建立。降维时一般不需要关注这个参数。
  • n_components:即我们进行LDA降维时降到的维数。在降维时需要输入这个参数。注意只能为[1,类别数-1)范围之间的整数。如果我们不是用于降维,则这个值可以用默认的None。
  • store_covariance:一个布尔值。如果为True,则需要额外计算每个类别的协方差矩阵。
  • tol:一个浮点数。它指定了用于SVD算法中评判迭代收敛的阈值

代码示例:

import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.discriminant_analysis import LinearDiscriminantAnalysis

iris = datasets.load_iris()

X = iris.data
y = iris.target
target_names = iris.target_names

lda = LinearDiscriminantAnalysis(n_components=2)
X_r2 = lda.fit(X, y).transform(X)

colors = ['navy', 'turquoise', 'darkorange']

for color, i, target_name in zip(colors, [0, 1, 2], target_names):
    plt.scatter(X_r2[y == i, 0], X_r2[y == i, 1], alpha=.8, color=color,
                label=target_name)
plt.legend(loc='best', shadow=False, scatterpoints=1)
plt.title('LDA of IRIS dataset')

plt.show()

参考链接:

2 Replies to “机器学习算法之线性判别分析(LDA)”

  1. 写的很不错,但是第一句的linear错啦

回复 Jerry Mak 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注