Linear Discriminant Analysis

在《机器学习（十六）》中，我们已经讨论了一个LDA，这里我们来看看另一个LDA。

Linear Discriminant Analysis是Ronald Fisher于1936年提出的方法，因此又叫做Fisher’s linear discriminant。正如之前在《知名数据集》中提到的，Iris flower Data Set也是出自该论文。

之前我们讨论的PCA、ICA也好，对样本数据来言，可以是没有类别标签y的。回想我们做回归时，如果特征太多，那么会产生不相关特征引入、过度拟合等问题。我们可以使用PCA来降维，但PCA没有将类别标签考虑进去，属于无监督的。

比如回到上次提出的文档中含有“learn”和“study”的问题，使用PCA后，也许可以将这两个特征合并为一个，降了维度。但假设我们的类别标签y是判断这篇文章的topic是不是有关学习方面的。那么这两个特征对y几乎没什么影响，完全可以去除。

再举一个例子，假设我们对一张100*100像素的图片做人脸识别，每个像素是一个特征，那么会有10000个特征，而对应的类别标签y仅仅是0/1值，1代表是人脸。这么多特征不仅训练复杂，而且不必要特征对结果会带来不可预知的影响，但我们想得到降维后的一些最佳特征（与y关系最密切的），怎么办呢？

给定特征为d维的N个样例 x ( i ) { x 1 ( i ) , x 2 ( i ) , … , x d ( i ) } x^{(i)}\{x_1^{(i)},x_2^{(i)},\dots,x_d^{(i)}\} x(i){x1(i)​,x2(i)​,…,xd(i)​}，其中有$N_1$个样例属于类别$w_1$，另外$N_2$个样例属于类别$w_2$。

现在我们觉得原始特征数太多，想将d维特征降到只有一维，而又要保证类别能够“清晰”地反映在低维数据上，也就是这一维就能决定每个样例的类别。

我们将这个最佳的向量称为w（d维），那么样例x（d维）到w上的投影可以用下式来计算：

$$y=w^{T}x$$

这里得到的y值不是0/1值，而是x投影到直线上的点到原点的距离。

我们首先看看x是二维的情况，从直观上来看，右图比较好，可以很好地将不同类别的样本点分离。这实际上就是LDA的思想：最大化类间方差与最小化类内方差，即减少分类内部之间的差异，而扩大不同分类之间的差异。

接下来我们从定量的角度来找到这个最佳的w。

首先我们寻找每类样例的均值（中心点），这里i只有两个：

$${\mu }_i=\frac{1}{N_i}\sum _{x\in {\omega }_i}x$$

由于x到w投影后的样本点均值为：

$$\widetilde{{\mu }_i}=\frac{1}{N_i}\sum _{y\in {\omega }_i}y=\frac{1}{N_i}\sum _{y\in {\omega }_i}{w}^{T}x=w^T{\mu }_i$$

由此可知，投影后的的均值也就是样本中心点的投影。

什么是最佳的直线（w）呢？我们首先发现，能够使投影后的两类样本中心点尽量分离的直线是好的直线，定量表示就是：

$$J(w)=\mid \widetilde{{\mu }_1}-\widetilde{{\mu }_2}\mid =\mid w^T({\mu }_1-{\mu }_2)\mid$$

J(w)越大越好。

但是只考虑J(w)行不行呢？不行，看下图：

样本点均匀分布在椭圆里，投影到横轴$x_1$上时能够获得更大的中心点间距J(w)，但是由于有重叠，$x_1$不能分离样本点。投影到纵轴$x_2$上，虽然J(w)较小，但是能够分离样本点。因此我们还需要考虑样本点之间的方差，方差越大，样本点越难以分离。

我们使用另外一个度量值，称作散列值（scatter），对投影后的类求散列值，如下：

$${\widetilde{s_i}}^2=\sum _{y\in {\omega }_i}(y-\widetilde{{\mu }_i}{)}^2$$

从公式中可以看出，只是少除以样本数量的方差值，散列值的几何意义是样本点的密集程度，值越大，越分散，反之，越集中。

而我们想要的投影后的样本点的样子是：不同类别的样本点越分开越好，同类的越聚集越好，也就是均值差越大越好，散列值越小越好。正好，我们可以使用J(w)和S来度量，最终的度量公式是：

$$J(w)=\frac{\mid \widetilde{{\mu }_1}-\widetilde{{\mu }_2}\mid }{{\widetilde{s_1}}^2+{\widetilde{s_2}}^2}$$

接下来的事就比较明显了，我们只需寻找使J(w)最大的w即可。

先把散列值公式展开：

$${\widetilde{s_i}}^2=\sum _{y\in {\omega }_i}(y-\widetilde{{\mu }_i}{)}^2=\sum _{x\in {\omega }_i}(w^{T}x-w^T{\mu }_i{)}^2=\sum _{x\in {\omega }_i}{w}^T(x-{\mu }_i)(x-{\mu }_i{)}^{T}w$$

我们定义上式中间部分：

$$S_i=\sum _{x\in {\omega }_i}(x-{\mu }_i)(x-{\mu }_i{)}^T$$

这也被称为散列矩阵（scatter matrices）。

我们继续定义：

$$S_W=S_1+S_2$$

$S_W$称为Within-class scatter matrix。

$$S_B=({\mu }_1-{\mu }_2)({\mu }_1-{\mu }_2{)}^T$$

$S_B$称为Between-class scatter matrix。

那么J(w)最终可以表示为：

$$J(w)=\frac{w^T{S}_{B}w}{w^T{S}_{W}w}$$

在我们求导之前，需要对分母进行归一化，因为不做归一化的话，w扩大任何倍，公式都成立，我们就无法确定w。因此，我们打算令$\Vert w^T{S}_{W}w\Vert =1$，那么加入拉格朗日乘子后，求导：

$$\begin{gathered} c(w)=w^T{S}_{B}w-\lambda (w^T{S}_{W}w-1)\Rightarrow \frac{\text{d}c}{\text{d}w}=2S_{B}w-2\lambda S_{W}w=0 \\ \Rightarrow S_{B}w=\lambda S_{W}w\Rightarrow S_W^{-1}{S}_{B}w=\lambda w \end{gathered}$$

可见，w实际上就是矩阵$S_W^{-1}{S}_B$的特征向量。

因为：

$$S_{B}w=({\mu }_1-{\mu }_2)({\mu }_1-{\mu }_2{)}^{T}w$$

其中，后面两项的积是一个常数，记做${\lambda }_w$，则：

$$S_W^{-1}{S}_{B}w=S_W^{-1}({\mu }_1-{\mu }_2){\lambda }_w=\lambda w$$

由于对w扩大缩小任何倍不影响结果，因此可以约去两边的未知常数$\lambda ,{\lambda }_w$，得到：

$$w=S_W^{-1}({\mu }_1-{\mu }_2)$$

至此，我们只需要求出原始样本的均值和方差就可以求出最佳的方向w。

上述结论虽然来自2维，但对于多维也是成立的。大特征值所对应的特征向量分割性能最好。由于$$S_W^{-1}{S}_B$$不一定是对称阵，因此得到的K个特征向量不一定正交，这也是与PCA不同的地方。

PCA选择样本点投影具有最大方差的方向，LDA选择分类性能最好的方向。

使用LDA的一些限制：

1.LDA至多可生成C-1维子空间。C为类别数。

LDA降维后的维度区间在[1,C-1]，与原始特征数n无关，对于二值分类，最多投影到1维。

2.LDA不适合对非高斯分布样本进行降维。

上图中红色区域表示一类样本，蓝色区域表示另一类，由于是2类，所以最多投影到1维上。不管在直线上怎么投影，都难使红色点和蓝色点内部凝聚，类间分离。

3.LDA在样本分类信息依赖方差而不是均值时，效果不好。

上图中，样本点依靠方差信息进行分类，而不是均值信息。LDA不能够进行有效分类，因为LDA过度依靠均值信息。

对LDA稍加扩展就得到了《图像处理理论（一）》中的Otsu法。Otsu法实际上是一维离散域的LDA。

此外，对于二值分类问题，最小二乘法和Fisher线性判别分析是一致的。

参考：

https://mp.weixin.qq.com/s/u-6nPrb4r9AS2gtrl5s-FA

LDA(Linear Discriminant Analysis)算法介绍

http://www.cnblogs.com/jerrylead/archive/2011/04/21/2024384.html

线性判别分析（Linear Discriminant Analysis）（一）

http://www.cnblogs.com/jerrylead/archive/2011/04/21/2024389.html

线性判别分析（Linear Discriminant Analysis）（二）

t-SNE

概述

t-SNE(t-distributed stochastic neighbor embedding)是用于降维的一种机器学习算法，是由Laurens van der Maaten和Geoffrey Hinton在08年提出来。此外，t-SNE 是一种非线性降维算法，非常适用于高维数据降维到2维或者3维，进行可视化。

论文：

《Visualizing Data using t-SNE》

以下是几种常见的降维算法：

1.主成分分析（线性）

2.t-SNE（非参数/非线性）

3.萨蒙映射（非线性）

4.等距映射（非线性）

5.局部线性嵌入（非线性）

6.规范相关分析（非线性）

7.SNE（非线性）

8.最小方差无偏估计（非线性）

9.拉普拉斯特征图（非线性）

PCA的相关内容参见《机器学习（十四）》。