前置知识

线性分类

指存在一个线性方程可以把待分类数据分开，或者说用一个超平面能将正负样本区分开，表达式为 。

线性分类器

线性分类器就是用一个“超平面”将两个样本隔离开，如：

1. 二维平面上的两个样本用一条直线来进行分类；

2. 三维立体空间内的两个样本用一个平面来进行分类；

3. N维空间内的两个样本用一个超平面来进行分类。

常见的线性分类器有：LR，贝叶斯分类，单层感知机、线性回归，SVM（线性核）等。

线性分类器速度快、编程方便且便于理解，但是拟合能力低。

非线性分类

指不存在一个线性分类方程把数据分开，它的分类界面没有限制，可以是一个曲面，或者是多个超平面的组合。

非线性分类器

非线性分类器就是用一个“超曲面”或者多个超平（曲）面的组合将两组样本隔离开（不属于线性的分类器），如：

1. 二维平面上的两组样本用一条曲线或折线来进行分类；

2. 三维立体空间内的两组样本用一个曲面或者折面来进行分类；

3. N维空间内的两组样本用一个超曲面来进行分类。

常见的非线性分类器：决策树、RF、GBDT、多层感知机、SVM（高斯核）等。

非线性分类器拟合能力强但是编程实现较复杂，理解难度大。

线性判别分析LDA

相对于主成分分析（PCA）降维算法，另外一种经典的降维方法线性判别分析（Linear Discriminant Analysis, 以下简称LDA）。LDA在模式识别领域（比如人脸识别，舰艇识别等图形图像识别领域）中有非常广泛的应用，因此我们有必要了解下它的算法原理。

我们有必要将其与自然语言处理领域中的LDA区分开：

在自然语言处理领域，LDA是隐含狄利克雷分布（Latent DIrichlet Allocation，简称LDA），它是一种处理文档的主题模型，我们本文讨论的是线性判别分析，因此后面所说的LDA均为线性判别分析。

LDA vs PCA

PCA是一种无监督的数据降维方法，LDA是一种有监督的数据降维方法。我们知道即使在训练样本上，我们提供了类别标签，在使用PCA模型的时候，我们是不利于类别标签的，而LDA在进行数据降维的时候是利用数据的类别标签提供的信息的。

从几何的角度来看，PCA和LDA都是将数据投影到新的相互正交的坐标轴上。只不过在投影的过程中他们使用的约束是不同的，也可以说目标是不同的。

PCA思想

PCA是将数据投影到方差最大的几个相互正交的方向上，以期待保留最多的样本信息。样本的方差越大表示样本的多样性越好，在训练模型的时候，希望数据的差别越大越好。PCA降维的目的：将数据投影到方差最大的几个相互正交的方向上。

对于左边这个数据集，我们可以将数据投影到 x 轴或者 y 轴，但这都不是最佳的投影方向，因为这两个方向都不能最好的反映数据的分布。很明显还存在最佳的方向可以描述数据的分布趋势，那就是图中红色直线所在的方向，也是数据样本作投影，方差最大的方向。向这个方向做投影，投影后数据的方差最大，数据保留的信息最多。

但是，对于右边这个数据集，PCA的这个投影后方差最大的目标就不太适合了。如果同样选择使用PCA选出的方差最大最佳投影方向，即图中红色直线所示的方向，来对数据进行降维。这样投影之后两类数据样本将混合在一起，将不再线性可分，甚至是不可分的。而如果使用图中黄色直线做投影，即能使数据降维，同时还能保证两类数据仍然是线性可分的。

LDA思想

上面右图中的数据集，如果使用LDA降维，即找出的投影方向是黄色直线所在的方向。

LDA的思想：“投影后类内方差最小，类间方差最大”。即数据在低维度上进行投影，投影后希望每一种类别数据的投影点尽可能的接近，而不同类别的数据的类别中心之间的距离尽可能的大。

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

LDA将带有标签的数据降维，投影到低维空间同时满足三个条件：

• 尽可能多的保留数据样本的信息（即选择最大的特征是对应的特征向量所代表的方向）。

• 寻找最佳投影方向以更好区分不同类样本。

• 投影后使得同类样本尽可能近，不同类样本尽可能远。

现在图解LDA的思想： 上图中提供了两种投影方式，哪一种能更好的满足我们的标准呢？从直观上可以看出，右图要比左图的投影效果好，因为右图的黑色数据和蓝色数据各个较为集中，且类别之间的距离明显。左图则在边界处数据混杂。

在实际应用中，数据一般超过二维，且是多类别的，投影后一般也不是直线，而是一个低维的超平面。

LDA与PCA异同

相同点：

1. 两者均可以对数据进行降维。

2. 两者在降维时均使用了矩阵特征分解的思想。

3. 两者都假设数据符合高斯分布。

不同点：

1. LDA是有监督的降维方法，而PCA是无监督的降维方法

2. LDA降维最多降到类别数 的维数，而PCA没有这个限制。

3. LDA除了可以用于降维，还可以用于分类。

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

为什么LDA降维最多降到类别数最大维度不是类别 k 呢？

因为类间散度矩阵 中每个 的秩为1，因此协方差矩阵相加后最大的秩为 （矩阵的秩小于等于各个相加矩阵的秩的和），但是由于我们知道前个μ 后，最后一个 可以由前 个 线性表示，因此 的秩最大为 ，即特征向量最多有 个。

LDA数学推导

二类LDA

LDA的原理：投影到维度更低的空间中，使得投影后的点，会形成按类别区分，一簇一簇的情况，相同类别的点，将会在投影后的空间中更接近方法。

什么是线性判别分析呢？所谓的线性就是，我们要将数据点投影到直线上（可能是多条直线），直线的函数解析式又称为线性函数，通常直线的表达式为：

其实这里的 x 就是样本向量（列向量），如果投影到一条直线上 w 就是一个特征向量（列向量形式）或者多个特征向量构成的矩阵

给定数据集，其中任意样本 为 维向量，。定义 ，，， 为第 类样本的个数、集合、均值向量及协方差矩阵。

的表达式为：

的表达式为：

402 Payment Required

将数据投影到直线 上，则两类样本的中心在直线上的投影分别为 ， 。考虑到所有样本点都投影到直线上，则两类样本的协方差分别为 和 ，直线 为一维空间，所以上述值均为实数。

由于LDA模型优化的目标是让不同类别的数据的投影点尽可能疏远，同一种类别数据的投影点尽可能的接近。也就是需要使得中心点之间的距离尽可能远，即最大化 ，同时要同类样本投影点的协方差尽可能的小，即最小化 。

我们知道方差可以用来度量数据的离散程度，越大，表示数据距离样本中心越远，数据越离散，数据的方差越大。

同样协方差 ，和 越大，表示数据距离样本中心越远，数据分布越分散，协方差越大。相反他们越小表示数据距离样本中心越近，数据分布越集中，协方差越小。

所以协方差不仅是反映了变量之间的相关性，同样反映了多维样本分布的离散程度（一维样本使用方差），协方差越大（对于负相关来说是绝对值越大），表示数据的分布越分散。所以上面的“欲使同类样例的投影点尽可能接近，可以让同类样本点的协方差矩阵尽可能小”就可以理解了。

综上所述，我们定义最大化目标函数为：

定义类内散度矩阵 为：

402 Payment Required

定义类间散度矩阵 为：

则目标函数可以改写为：

注意上面的分子和分母都是关于 的二次项，因此上面的解与 的长度无关，只与其方向有关，不失一般性，我们令：

对分母进行归一化：因为如果分子、分母都是可以取任意值的，那就会使得有无穷解

则优化目标等价于：

402 Payment Required

使用拉格朗日乘子法，将上式转换：

402 Payment Required

注意：

是否可逆，遗憾的是在实际的应用中，它通常是不可逆的，通常有两个办法解决它。

方法1：令 ，其中 是一个特别小的数，这样 一定可逆。

方法2：先用PCA对数据进行降维，使得在降维后的数据上 可逆，再使用LDA。

令 ，将其带入上述结果：

考虑到 矩阵数值解的稳定性，对其进行奇异值分解，即：

而后即可求的 的逆矩阵 。

多类别LDA

给定数据集

402 Payment Required

，其中任意样本 为 维向量， 。定义 ， ， ， 为第 类样本的个数、集合、均值向量及协方差矩阵。在二类LDA里面定义的公式可以很容易的类推到多类LDA。

由于我们是多类向低维投影，则此时投影到的低维空间就不是一条直线，而是一个超平面了。假设我们投影到的低维空间的维度为 ，对应的基向量为，基向量组成的矩阵为 , 它是一个 的矩阵。

定义目标函数为：

其中 为所有样本均值向量。

402 Payment Required

由于 和 都是矩阵，不是标量，无法直接用二类LDA的优化方法将其作为一个标量函数来优化，于是使用一些替代优化目标来实现。

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

402 Payment Required

其中 为 的主对角线元素的乘积， 为 的矩阵。

的优化过程可以转化为：

402 Payment Required

该目标函数的最大值是矩阵 的最大特征值，最大的 个值的乘积就是矩阵 的最大的 个特征值的乘积，此时对应的矩阵 为这最大的 个特征值对应的特征向量张成的矩阵。

LDA算法流程

输入：数据集 ，其中任意样本 为 维向量，，降维到的维度 。

输出：降维后的样本集

1. 对训练集按类别进行分组

2. 分别计算每组样本的均值和协方差

3. 计算类内散度矩阵

4. 计算类间散度矩阵

5. 对类内散度矩阵 进行奇异值分解，并求其逆  

6. 计算 的最大的 个特征值和对应的 个特征向量 得到投影矩阵

7. 对样本集中的每一个样本特征，转化为新的样本

8. 得到输出样本集

以上就是使用LDA进行降维的算法流程。实际上LDA除了可以用于降维以外，还可以用于分类。一个常见的LDA分类基本思想是假设各个类别的样本数据符合高斯分布，这样利用LDA进行投影后，可以利用极大似然估计计算各个类别投影数据的均值和方差，进而得到该类别高斯分布的概率密度函数。当一个新的样本到来后，我们可以将它投影，然后将投影后的样本特征分别带入各个类别的高斯分布概率密度函数，计算它属于这个类别的概率，最大的概率对应的类别即为预测类别。

LDA算法优缺点

LDA算法既可以用来降维，又可以用来分类，但是目前来说，主要还是用于降维。在我们进行图像识别图像识别相关的数据分析时，LDA是一个有力的工具。下面总结下LDA算法的优缺点。

主要优点：

1. 在降维过程中可以使用类别的先验知识经验，而像PCA这样的无监督学习则无法使用类别先验知识。

2. LDA在样本分类信息依赖均值而不是方差的时候，比PCA之类的算法较优。

主要缺点：

1. LDA不适合对非高斯分布样本进行降维，PCA也有这个问题。

2. LDA降维最多降到类别数k-1的维数，如果我们降维的维度大于k-1，则不能使用LDA。当然目前有一些LDA的进化版算法可以绕过这个问题。

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

4. LDA可能过度拟合数据。

sklearn中LDA

在scikit-learn中， LDA 类是 sklearn.discriminant_analysis.LinearDiscriminantAnalysis。那既可以用于分类又可以用于降维。LDA降维基本也不用调参，只需要指定降维到的维数即可。

重要参数

n_components：即我们进行LDA降维时降到的维数，默认的None。在降维时需要输入这个参数。注意只能为[1, 类别数-1)范围之间的整数。如果我们不是用于降维，则这个值可以用默认值。

solver : 即求LDA超平面特征矩阵使用的方法，默认值方法奇异值分解"svd"，其他还有最小二乘"lsqr"和特征分解"eigen"。一般来说特征数非常多的时候推荐使用svd，而特征数不多的时候推荐使用eigen。注意如果使用svd，则不能指定正则化参数shrinkage进行正则化。

shrinkage：正则化参数，默认是None。可以增强LDA分类的泛化能力。如果仅仅只是为了降维，则一般可以忽略这个参数。即不进行正则化。可以选择 "auto"，让算法自己决定是否正则化。当然我们也可以选择不同的[0,1]之间的值进行交叉验证调参。注意shrinkage只在solver为最小二乘"lsqr"和特征分解"eigen"时有效。

priors ：类别权重，可以在做分类模型时指定不同类别的权重，进而影响分类模型建立。降维时一般不需要关注这个参数。

如果只是为了降维，则只需要输入n_components，注意这个值必须小于“类别数-1”。PCA没有这个限制。

LDA降维实例

在LDA的原理篇我们讲到，PCA和LDA都可以用于降维。两者没有绝对的优劣之分，使用两者的原则实际取决于数据的分布。由于LDA可以利用类别信息，因此某些时候比完全无监督的PCA会更好。下面我们举一个LDA降维可能更优的例子。

import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
%matplotlib inline
from sklearn.datasets.samples_generator import make_classification
X, y = make_classification(n_samples=1000, 
                           n_features=3, 
                           n_redundant=0, 
                           n_classes=3, 
                           n_informative=2,
                           n_clusters_per_class=1,
                           class_sep =0.5, 
                           random_state =10)
fig = plt.figure(figsize=(8,8))
ax = Axes3D(fig, rect=[0, 0, 1, 1], elev=30, azim=20)
ax.scatter(X[:, 0], X[:, 1], X[:, 2],marker='o',c=y,s=40)

from sklearn.decomposition import PCA
from sklearn.discriminant_analysis import LinearDiscriminantAnalysis

pca = PCA(n_components=2)
pca.fit(X)
X_pca = pca.transform(X)
lda = LinearDiscriminantAnalysis(n_components=2)
lda.fit(X,y)
X_lad = lda.transform(X)
fig, axs = plt.subplots(1,2, figsize=(15,7))
axs[0].scatter(X_pca[:, 0], X_pca[:, 1],marker='^',c=y)
axs[0].set_title("Data after PCA")
axs[1].scatter(X_lad[:, 0], X_lad[:, 1],marker='^',c=y)
axs[1].set_title("Data after LDA")
plt.show()

参考资料

https://www.cnblogs.com/pinard/p/6244265.html 

https://www.cnblogs.com/pinard/p/6249328.html

推荐阅读：

我的2022届互联网校招分享

我的2021总结

浅谈算法岗和开发岗的区别

互联网校招研发薪资汇总
2022届互联网求职现状，金9银10快变成铜9铁10！！

公众号：AI蜗牛车

保持谦逊、保持自律、保持进步

发送【蜗牛】获取一份《手把手AI项目》（AI蜗牛车著）
发送【1222】获取一份不错的leetcode刷题笔记

发送【AI四大名著】获取四本经典AI电子书