Created by potrace 1.13, written by Peter Selinger 2001-2015

线性辨别模型

线性辨别模型(Linear Discriminant Analysis, 简称LDA）是一种经典的线性学习方法.

LDA的思想可以用一句话概括，就是“投影后类内方差最小，类间方差最大”。 我们要将数据在低维度上进行投影，投影后希望每一种类别数据的投影点尽可能的接近，而不同类别的数据的类别中心之间的距离尽可能的大。在对新样本进行分类时,将其同样投影到这条直线上,再根据投影点的位置来确定类别.

image

下面两种投影方式，可以看出，右图要比左图的投影效果好.

image

二类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 的表达式为：

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

\Sigma_j 的表达式为：

\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 。样本在 \omega 上的投影的协方差为：
(\omega^Tx-\omega^T\mu_i)(\omega^Tx-\omega^T\mu_i)^T=\omega^T(x-\mu_i)(x-\mu_i)^T\omega=\omega^T\Sigma_i\omega

由于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_b 与 S_w 的广义瑞利商.如果对线性代数熟悉的话,可以直接用广义瑞利商的性质求得 J(w) 的最大值.这里我们用比较常见的拉格朗日来求极值.

因为分子分母都是关于w的二次项,所以解与w的长度无关,仅与方向有关,所以我们可以任意缩放w.下面对w进行缩放,令
w^TS_ww = 1

则优化函数可以写为:
\underbrace{arg\;min}_w\;\;J(w) = -w^TS_bw \; s.t.\; w^TS_ww = 1

求得拉格朗日方程:
l(w) = -w^TS_bw + \lambda(w^TS_ww - 1)

令 l(w) 导数为0,可得:
S_bw = \lambda S_ww

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

考虑到数值解的稳定性,在实践中通常是对 S_w 进行奇异值分解,即 S_w = U\Sigma V^T ,这里 \Sigma 是一个实对角矩阵,其对角线上的元素是 S_w 的奇异值,然后再由 S_w^{-1} = U\Sigma^{-1} V^T 求得 S_w 的伪逆.

多类LDA原理

有了二类LDA的基础，我们再来看看多类别LDA的原理。

假设我们的数据集 D=\{(x_1,y_1), (x_2,y_2), ...,((x_m,y_m))\} ,其中任意样本xi为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×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多类优化目标函数定义为：
\underbrace{arg\;max}_W\;\;J(W) = \frac{tr(W^TS_bW)}{tr(W^TS_wW)}
其中tr()表示矩阵的迹，W为n×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_w^{-1}S_b 的最大特征值,最大的d个值的乘积就是矩阵 S_w^{-1}S_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个。

编程实现:
https://www.kaggle.com/swimmingwhale/linear-discriminant-analysis

参考:
周志华-<机器学习>
https://www.cnblogs.com/pinard/p/6244265.html

posted @ 2018-09-14 08:01:33
评论加载中...
发表评论