一、PCA(主成分分析)
PCA是一种无监督的数据降维方法
降维是对数据高维度特征的一种预处理方法。降维是将高维度的数据保留下最重要的一些特征,去除噪声和不重要的特征,从而实现提升数据处理速度的目的。在实际的生产和应用中,降维在一定的信息损失范围内,可以为我们节省大量的时间和成本。降维也成为了应用非常广泛的数据预处理方法。
降维具有如下一些优点:
(1)使得数据集更易使用
(2)降低算法的计算开销
(3)去除噪声
(4)使得结果容易理解
PCA(principal Component Analysis),即主成分分析方法,是一种使用最广泛的数据压缩算法。在PCA中,数据从原来的坐标系转换到新的坐标系,由数据本身决定。转换坐标系时,以方差最大的方向作为坐标轴方向,因为数据的最大方差给出了数据的最重要的信息。第一个新坐标轴选择的是原始数据中方差最大的方法,第二个新坐标轴选择的是与第一个新坐标轴正交且方差次大的方向。重复该过程,重复次数为原始数据的特征维数。
通过这种方式获得的新的坐标系,我们发现,大部分方差都包含在前面几个坐标轴中,后面的坐标轴所含的方差几乎为0,。于是,我们可以忽略余下的坐标轴,只保留前面的几个含有绝不部分方差的坐标轴。事实上,这样也就相当于只保留包含绝大部分方差的维度特征,而忽略包含方差几乎为0的特征维度,也就实现了对数据特征的降维处理。
那么,我们如何得到这些包含最大差异性的主成分方向呢?事实上,通过计算数据矩阵的协方差矩阵,然后得到协方差矩阵的特征值及特征向量,选择特征值最大(也即包含方差最大)的N个特征所对应的特征向量组成的矩阵,我们就可以将数据矩阵转换到新的空间当中,实现数据特征的降维(N维)。
既然,说到了协方差矩阵,那么这里就简单说一下方差和协方差之间的关系,首先看一下均值,方差和协方差的计算公式:
由上面的公式,我们可以得到一下两点区别:
(1)方差的计算公式,我们知道方差的计算是针对一维特征,即针对同一特征不同样本的取值来进行计算得到;而协方差则必须要求至少满足二维特征。可以说方差就是协方差的特殊情况。
(2)方差和协方差的除数是n-1,这样是为了得到方差和协方差的无偏估计。具体推导过程可以参见博文:http://blog.csdn.net/maoersong/article/details/21823397
将数据转换为只保留前N个主成分的特征空间的伪代码如下所示:
去除平均值
计算协方差矩阵
计算协方差矩阵的特征值和特征向量
将特征值排序
保留前N个最大的特征值对应的特征向量
将数据转换到上面得到的N个特征向量构建的新空间中(实现了特征压缩)
总结:
(1)降维是一种数据集预处理技术,往往在数据应用在其他算法之前使用,它可以去除掉数据的一些冗余信息和噪声,使数据变得更加简单高效,提高其他机器学习任务的计算效率。
(2)pca可以从数据中识别主要特征,通过将数据坐标轴旋转到数据角度上那些最重要的方向(方差最大);然后通过特征值分析,确定出需要保留的主成分个数,舍弃其他主成分,从而实现数据的降维。
二、LDA(线性判别分析)
线性判别式分析(Linear Discriminant Analysis, LDA)是一种监督学习的降维技术,也就是说它的数据集的每个样本是有类别输出的。这点和PCA不同。PCA是不考虑样本类别输出的无监督降维技术。LDA的思想可以用一句话概括,就是“投影后类内方差最小,类间方差最大”。什么意思呢? 我们要将数据在低维度上进行投影,投影后希望每一种类别数据的投影点尽可能的接近,而不同类别的数据的类别中心之间的距离尽可能的大。
可能还是有点抽象,我们先看看最简单的情况。假设我们有两类数据 分别为红色和蓝色,如下图所示,这些数据特征是二维的,我们希望将这些数据投影到一维的一条直线,让每一种类别数据的投影点尽可能的接近,而红色和蓝色数据中心之间的距离尽可能的大。
上图中国提供了两种投影方式,哪一种能更好的满足我们的标准呢?从直观上可以看出,右图要比左图的投影效果好,因为右图的黑色数据和蓝色数据各个较为集中,且类别之间的距离明显。左图则在边界处数据混杂。以上就是LDA的主要思想了,当然在实际应用中,我们的数据是多个类别的,我们的原始数据一般也是超过二维的,投影后的也一般不是直线,而是一个低维的超平面。
1、二类LDA原理
现在我们回到LDA的原理上,我们在第一节说讲到了LDA希望投影后希望同一种类别数据的投影点尽可能的接近,而不同类别的数据的类别中心之间的距离尽可能的大,但是这只是一个感官的度量。现在我们首先从比较简单的二类LDA入手,严谨的分析LDA的原理。
假设我们的数据集D={(x1,y1),(x2,y2),…,((xm,ym))},其中任意样本xi为n维向量,yi∈{0,1}。我们定义Nj(j=0,1)为第j类样本的个数,Xj(j=0,1)为第j类样本的集合,而μj(j=0,1)为第j类样本的均值向量,定义Σj(j=0,1)为第j类样本的协方差矩阵(严格说是缺少分母部分的协方差矩阵)。
的表达式为:
的表达式为:
由于是两类数据,因此我们只需要将数据投影到一条直线上即可。假设我们的投影直线是向量w,则对任意一个样本本,它在直线w的投影为,对于我们的两个类别的中心点μ0,μ1,在在直线w的投影为和。由于LDA需要让不同类别的数据的类别中心之间的距离尽可能的大,也就是我们要最大化,同时我们希望同一种类别数据的投影点尽可能的接近,也就是要同类样本投影点的协方差和尽可能的小,即最小化。综上所述,我们的优化目标为:
我们一般定义类内散度矩阵为:
同时定义类间散度矩阵为:
这样我们的优化目标重写为:
仔细一看上式,这不就是我们的广义瑞利商嘛!这就简单了,利用我们第二节讲到的广义瑞利商的性质,我们知道我们的J(w)最大值为矩阵的最大特征值,而对应的w为的最大特征值对应的特征向量!
注意到对于二类的时候,的方向恒为,不妨令,将其带入:,可以得到, 也就是说我们只要求出原始二类样本的均值和方差就可以确定最佳的投影方向w了。
2、多类LDA原理
有了二类LDA的基础,我们再来看看多类别LDA的原理。
假设我们的数据集,其中任意样本xi为n维向量,。我们定义为第j类样本的个数,为第j类样本的集合,而为第j类样本的均值向量,定义为第j类样本的协方差矩阵。在二类LDA里面定义的公式可以很容易的类推到多类LDA。
由于我们是多类向低维投影,则此时投影到的低维空间就不是一条直线,而是一个超平面了。假设我们投影到的低维空间的维度为d,对应的基向量为,基向量组成的矩阵为W, 它是一个n×d的矩阵。
此时我们的优化目标应该可以变成为:
其中,μ为所有样本均值向量。
但是有一个问题,就是和都是矩阵,不是标量,无法作为一个标量函数来优化!也就是说,我们无法直接用二类LDA的优化方法,怎么办呢?一般来说,我们可以用其他的一些替代优化目标来实现。
常见的一个LDA多类优化目标函数定义为:
其中为A的主对角线元素的乘积,W为n×d的矩阵。
J(W)的优化过程可以转化为:
仔细观察上式最右边,这不就是广义瑞利商嘛!最大值是矩阵的最大特征值,最大的d个值的乘积就是矩阵的最大的d个特征值的乘积,此时对应的矩阵W为这最大的d个特征值对应的特征向量张成的矩阵。
由于W是一个利用了样本的类别得到的投影矩阵,因此它的降维到的维度d最大值为k-1。为什么最大维度不是类别数k呢?因为Sb中每个的秩为1,因此协方差矩阵相加后最大的秩为k(矩阵的秩小于等于各个相加矩阵的秩的和),但是由于如果我们知道前k-1个μj后,最后一个可以由前k-1个线性表示,因此Sb的秩最大为k-1,即特征向量最多有k-1个。
3、LDA算法流程
在第三节和第四节我们讲述了LDA的原理,现在我们对LDA降维的流程做一个总结。
输入:数据集,其中任意样本xi为n维向量,,降维到的维度d。
输出:降维后的样本集
1) 计算类内散度矩阵
2) 计算类间散度矩阵
3) 计算矩阵
4)计算的最大的d个特征值和对应的d个特征向量,得到投影矩阵
5) 对样本集中的每一个样本特征xi,转化为新的样本
6) 得到输出样本集
以上就是使用LDA进行降维的算法流程。实际上LDA除了可以用于降维以外,还可以用于分类。一个常见的LDA分类基本思想是假设各个类别的样本数据符合高斯分布,这样利用LDA进行投影后,可以利用极大似然估计计算各个类别投影数据的均值和方差,进而得到该类别高斯分布的概率密度函数。当一个新的样本到来后,我们可以将它投影,然后将投影后的样本特征分别带入各个类别的高斯分布概率密度函数,计算它属于这个类别的概率,最大的概率对应的类别即为预测类别。
由于LDA应用于分类现在似乎也不是那么流行,至少我们公司里没有用过,这里我就不多讲了。
4、LDA算法小结
LDA算法既可以用来降维,又可以用来分类,但是目前来说,主要还是用于降维。在我们进行图像识别图像识别相关的数据分析时,LDA是一个有力的工具。下面总结下LDA算法的优缺点。
LDA算法的主要优点有:
1)在降维过程中可以使用类别的先验知识经验,而像PCA这样的无监督学习则无法使用类别先验知识。
2)LDA在样本分类信息依赖均值而不是方差的时候,比PCA之类的算法较优。
LDA算法的主要缺点有:
1)LDA不适合对非高斯分布样本进行降维,PCA也有这个问题。
2)LDA降维最多降到类别数k-1的维数,如果我们降维的维度大于k-1,则不能使用LDA。当然目前有一些LDA的进化版算法可以绕过这个问题。
3)LDA在样本分类信息依赖方差而不是均值的时候,降维效果不好。
4)LDA可能过度拟合数据。
三、 LDA 和 PCA区别
LDA用于降维,和PCA有很多相同,也有很多不同的地方,因此值得好好的比较一下两者的降维异同点。
首先我们看看相同点:
1)两者均可以对数据进行降维。
2)两者在降维时均使用了矩阵特征分解的思想。
3)两者都假设数据符合高斯分布。
我们接着看看不同点:
1)LDA是有监督的降维方法,而PCA是无监督的降维方法
2)LDA降维最多降到类别数k-1的维数,而PCA没有这个限制。
3)LDA除了可以用于降维,还可以用于分类。
4)LDA选择分类性能最好的投影方向,而PCA选择样本点投影具有最大方差的方向。
这点可以从下图形象的看出,在某些数据分布下LDA比PCA降维较优。
当然,某些某些数据分布下PCA比LDA降维较优,如下图所示: