线性特征降维——LDA

LDA线性判别分析

Fisher‘s Linear Discriminant (FLD) 是统计学上的经典分析方法，LDA (Linear Discriminant Analysis, 线性判别分析) 在FLD的基础上增加了关于变量分布和协方差的假设：1.样本数据服从正态分布，2.各类的协方差相等。虽然这些假设在实际中不一定满足，但是LDA既可以用来作线性分类，也可以用来对数据进行降维。下面，我们从LDA的思想，数学基础，原理，算法流程，python实现，使用LDA的限制以及与PCA的对比等方面对LDA进行总结。

LDA的思想

LDA是一种监督学习的降维技术，也就是说它的数据集的每个样本是有类别输出的。LDA的思想可以用一句话概括，就是“投影后类内方差最小，类间方差最大”。也就是说，我们要将数据在低维度上进行投影，投影后希望每一种类别数据的投影点尽可能的接近，而不同类别的数据的类别中心之间的距离尽可能的大。举例来说，假设我们有两类数据 分别为红色和蓝色，如下图所示，这些数据特征是二维的，我们希望将这些数据投影到一维的一条直线，让每一种类别数据的投影点尽可能的接近，而红色和蓝色数据中心之间的距离尽可能的大。

LDA

上图提供了两种投影方式，从直观上可以看出，右图要比左图的投影效果好，因为右图的同色数据较为集中，且类别之间的距离明显。左图则在边界处数据混杂。

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

数学基础

在具体讲解LDA原理之前，我们先补充一些相关的数学基础知识——瑞利商（Rayleigh quotient）与广义瑞利商（genralized Rayleigh quotient）。

  • 瑞利商

瑞利商的函数如下： ​

其中x为非零向量，而A为的Hermitan矩阵。所谓的Hermitan矩阵就是满足共轭转置矩阵和自己相等的矩阵，即。如果我们的矩阵A是实矩阵，则满足的矩阵即为Hermitan矩阵。

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

​

当向量x是标准正交基时，即满足时，瑞利商简化为：。

  • 广义瑞利商

广义瑞利商的函数如下：

其中x为非零向量，而A，B为的Hermitan矩阵，B为正定矩阵。我们可以将其通过标准化转化为瑞利商的格式。我们令，则分母转化为：

​

分子转化为：

此时转化为：

​

利用前面的瑞利商的性质，可知，的最大值为矩阵，也即矩阵的最大特征值。而最小值为矩阵的最小特征值。

LDA原理

二分类原理

假设我们的数据集。其中任意样本为n维向量，。我们定义为第j类样本的个数，为第j类样本的集合，而为第j类样本的均值向量，定义为第j类样本的协方差矩阵（严格说是缺少分母部分的协方差矩阵）。

的表达式为：

​

的表达式为：

​

由于是两类数据，因此我们只需要将数据投影到一条直线上即可。假设我们的投影直线是向量w，则对任意一个样本，它在直线w的投影为，对于我们的两个类别的中心点，，在直线w的投影为和。由于LDA需要让不同类别的数据的类别中心之间的距离尽可能的大，也就是我们要最大化，同时我们希望同一种类别数据的投影点尽可能的接近，也就是要同类样本投影点的协方差和尽可能的小，即最小化。

综上所述，我们的优化目标为：

​

我们一般定义类内散度矩阵为：

​

同时定义类间散度矩阵为：

​

这样，我们的优化目标重写为：

​

可以看出，上式即为广义瑞利商的形式，我们利用广义瑞利商的性质可知，的最大值为矩阵的最大特征值，而对应的w为的最大特征值对应的特征向量。

对于二类的时候，的方向恒为，不妨令，将其带入：，可以得到，也就是说我们只要求出原始二类样本的均值和方差就可以确定最佳的投影方向w了。

多分类原理

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

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

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

此时我们的优化目标应该可以变成为：

其中,

为所有样本的均值向量。

而 。

但是有一个问题，就是和都是矩阵，不是标量，无法作为一个标量函数来优化！也就是说，我们无法直接用二类LDA的优化方法，怎么办呢？一般来说，我们可以用其他的一些替代优化目标来实现。

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

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

的优化过程可以转化为：
​

仔细观察上式最右边，这正是广义瑞利商。最大值是矩阵的最大特征值，最大的d个值的乘积就是矩阵的最大的d个特征值的乘积，此时对应的矩阵为这最大的d个特征值对应的特征向量张成的矩阵。

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

LDA算法

在上面我们已经讲述了LDA的原理，现在我们对LDA降维的流程做一个总结。 输入：数据集 ，其中其中任意样本为n维向量，，降维到维度d。 输出：降维后的样本集

  1. 计算类内散度矩阵
  2. 计算类间散度矩阵
  3. 计算矩阵
  4. 计算的最大的d个特征值和对应的d个特征向量，得到投影矩阵
  5. 对样本集中的每一个样本特征，转化为新的样本
  6. 得到输出样本集

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

LDA的python实现

在scikit-learn中， 实现LDA的类是sklearn.discriminant_analysis.LinearDiscriminantAnalysis。这既可以用于分类又可以用于降维。当然，应用场景最多的还是降维。和PCA类似，LDA降维基本也不用调参，只需要指定降维到的维数即可。

LinearDiscriminantAnalysis类的参数如下：

  1. solver : 即求LDA超平面特征矩阵使用的方法。可以选择的方法有奇异值分解"svd"，最小二乘"lsqr"和特征分解"eigen"。一般来说特征数非常多的时候推荐使用svd，而特征数不多的时候推荐使用eigen。主要注意的是，如果使用svd，则不能指定正则化参数shrinkage进行正则化。默认值是svd。
  2. hrinkage ：正则化参数，可以增强LDA分类的泛化能力。如果仅仅只是为了降维，则一般可以忽略这个参数。默认是None，即不进行正则化。可以选择"auto",让算法自己决定是否正则化。当然我们也可以选择不同的[0,1]之间的值进行交叉验证调参。注意shrinkage只在solver为最小二乘"lsqr"和特征分解"eigen"时有效。
  3. priors ：类别权重，可以在做分类模型时指定不同类别的权重，进而影响分类模型建立。降维时一般不需要关注这个参数。
  4. n_components ：即我们进行LDA降维时降到的维数。在降维时需要输入这个参数。注意只能为[1,类别数-1)范围之间的整数。如果我们不是用于降维，则这个值可以用默认的None。

从上面的描述可以看出，如果我们只是为了降维，则只需要输入n_components,注意这个值必须小于“类别数-1”。PCA没有这个限制。

实现举例：

#生成三类三维特征的数据
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()
ax = Axes3D(fig, rect=[0, 0, 1, 1], elev=30, azim=20)
plt.scatter(X[:, 0], X[:, 1], X[:, 2],marker='o',c=y)

原始三维的数据的散点图。

散点图_降维前

#使用PCA降维到二维，注意PCA无法使用类别信息来降维
from sklearn.decomposition import PCA
pca = PCA(n_components=2)
pca.fit(X)
print "两个主成分方差比："
print pca.explained_variance_ratio_
print "两个主成分方差："
print pca.explained_variance_
X_new = pca.transform(X)
print "PCA降维效果图："
plt.scatter(X_new[:, 0], X_new[:, 1],marker='o',c=y)
plt.show()

# 输出结果
两个主成分方差比：
[ 0.43377069  0.3716351 ]
两个主成分方差：
[ 1.21083449  1.0373882 ]

PCA降维效果图：

散点图_PCA

由于PCA没有利用类别信息，我们可以看到降维后，样本特征和类别的信息关联几乎完全丢失。

#使用LDA降维到二维
from sklearn.discriminant_analysis import LinearDiscriminantAnalysis
lda = LinearDiscriminantAnalysis(n_components=2)
lda.fit(X,y)
X_new = lda.transform(X)
print "LDA降维效果图："
plt.scatter(X_new[:, 0], X_new[:, 1],marker='o',c=y)
plt.show()

LDA降维效果图：

散点图_LDA

可以看出降维后样本特征和类别信息之间的关系得以保留。

LDA与PCA的对比

降维方法 思想 分布 监督方式 投影 维度 目的
PCA 数据降维，矩阵特征分解 假设数据符合高斯分布 无监督 投影的坐标系都是正交的 直接和特征维度相关，比如原始数据是d维，PCA之后，可以任意选取1～n维 去除原始数据集中冗余的维度，让投影子空间各个维度的方差尽可能大
LDA 数据降维，矩阵特征分解 假设数据符合高斯分布 有监督 根据类别的标注关注分类能力，不保证投影到的坐标系是正交的 与数据本身的维度无关，和类别个数C相关，LDA之后，在1～C-1维进行选择 找到具有区分的维度，使得原始数据在这些维度上的投影能尽可能区分不同类别

如下图所示，是PCA和LDA分别选择的投影方向。

image

参考资料

  1. 特征哈希(Feature Hashing)
  2. Trevor Hastie et al. The Elements of Statistical Learning, 2001.
  3. Kilian Weinberger et al. Feature Hashing for Large Scale Multitask Learning, 2010.
  4. Joshua Attenberg et al. Collaborative Email-Spam Filtering with the Hashing-Trick, 2009.
  5. https://www.zhihu.com/question/264165760/answer/277634591
  6. sklearn.feature_extraction.FeatureHasher
  7. sklearn学习笔记2 Feature_extraction库
  8. 特征选择和稀疏学习
  9. 《西瓜书》笔记11：特征选择与稀疏表示（三）
  10. 特征选择与稀疏学习
  11. https://www.zhihu.com/question/24124122/answer/50403932
  12. https://blog.csdn.net/u014595019/article/details/52433754
  13. PCA算法详解
  14. 主成分分析（PCA）原理详解
  15. 主成分分析PCA算法：为什么去均值以后的高维矩阵乘以其协方差矩阵的特征向量矩阵就是“投影”？
  16. 用Python的sklearn库进行PCA(主成分分析)
  17. 用scikit-learn学习主成分分析(PCA)
  18. 独立成分分析（Independent Component Analysis）
  19. 独立成分分析 ( ICA ) 与主成分分析 ( PCA ) 的区别在哪里？
  20. 独立成分分析ICA系列4:ICA的最优估计方法综述
  21. ICA-独立成分分析
  22. 独立成分分析Independent component analysis(ICA)
  23. 线性判别分析LDA原理总结
  24. 一文读懂特征工程
  25. 线性判别分析LDA详解
  26. LinearDiscriminantAnalysis
  27. 用scikit-learn进行LDA降维
  28. https://blog.csdn.net/u010705209/article/details/53518772
  29. https://blog.csdn.net/u012162613/article/details/42214205
  30. https://blog.csdn.net/qianhen123/article/details/40077873
  31. https://github.com/ceys/jdml/wiki/ALS
  32. 美团点评技术团队之深入FFM原理与实践
  33. [深度学习笔记（一）稀疏自编码器] (https://blog.csdn.net/u010278305/article/details/46881443)
  34. Field-aware Factorization Machines for CTR Prediction ,Yuchin Juan et al.
  35. Factorization Machines, Steffen Rendle et al.[2010]
  36. http://deeplearning.stanford.edu/wiki/index.php/UFLDL_Tutorial
  37. 局部线性嵌入(LLE)原理总结
  38. Locally linear embedding(LLE)局部线性嵌入-降维
  39. LocallyLinearEmbedding
  40. 用scikit-learn研究局部线性嵌入(LLE)
  41. 聚类和降维的区别与联系
  42. 聚类算法
  43. 受限玻尔兹曼机（RBM）学习笔记
  44. 受限制玻尔兹曼机RBM原理简介
  45. 从SNE到t-SNE
  46. t-SNE完整笔记
  47. SNE降维与可视化
  48. 比PCA降维更高级 —— t-SNE聚类算法实现指南

results matching ""

    No results matching ""