LDA线性判别分析

LDA(线性判别分析)2017.11LDA(线性判别分析)LDA的全称是LinearDiscriminantAnalysis（线性判别分析1936RonaldFisher），是一种监督学习降维方法，也就是说它的数据集的每个样本是有类别输出的。这点和PCA（PrincipalComponentAnalysis）不同。PCA是不考虑样本类别输出的无监督降维技术。有监督学习：分类。通过已有的训练样本（即已知数据以及其对应标签）去训练得到一个最优模型（这个模型属于某个函数的集合，最优则表示在某个评价准则下是最佳的），再利用这个模型将所有的输入映射为相应的输出。KNN、SVM无监督学习：聚类。训练数据没有标签。K_means，PCA,随机森林半监督学习：其训练数据的一部分是有标签的，另一部分没有标签。在很多实际问题中，只有少量的带有标记的数据，因为对数据进行标记的代价有时很高半监督分类，半监督聚类。降维的目的：1.减少预测变量的个数在人脸识别中特征提取及数据维，假设输入200*200大小的人脸图像，单单提取它的灰度值作为原始特征，则这个原始特征将达到40000维，这给后面分类器的处理将带来极大的难度。2.确保这些变量是相互独立的有效信息的提取综合及无用信息的摈弃。3.提供一个框架来解释结果LDA是在目前机器学习、数据挖掘领域经典且热门的一个降维算法，LDA在模式识别领域（比如人脸识别，舰艇识别等图形图像识别领域）中有非常广泛的应用。百度商务搜索部里面也用了不少这方面的算法。降维标准：投影后类内方差最小，类间方差最大。我们要将数据在低维度上进行投影，投影后希望每一种类别数据的投影点尽可能的接近，而不同类别的数据的类别中心之间的距离尽可能的大。我们的数据一般是多个类别的，一般也是超过二维的，投影后的也一般不是直线，而是一个低维的超平面。•LDA人脸识别（Fisherface）通常情况下，待匹配人脸要和人脸库内的多张人脸匹配，所以这是一个多分类的情况。出于简单考虑，可以先介绍二类的情况然后拓展到多类。假设有二维平面上的两个点集x（x是包含横纵坐标的二维向量），它们的分布如下图（分别以蓝点和红点表示数据）：以数学公式给出投影点到到原点的距离：w以从原点出发的直线来表示，直线上的点是原数据的投影点。下图给出了两种w方案，直观判断右侧的w更好些，其上的投影点能够合理的区分原有的两个数据集。但是计算机不知道这些，所以必须要有确定的方法来计算这个w。首先计算每类数据的均值（中心点）：i是数据的分类个数，Ni代表某个分类下的数据点数，比如μ1代表红点的中心，μ2代表蓝点的中心。类均值点投影到w上的中心为：如何判断向量w最佳？1、不同的分类得到的投影点要尽量分开；2、同一个分类投影后得到的点要尽量聚合。从这两方面考虑，可以定义如下公式：J(w)代表不同分类投影中心的距离，它的值越大越好。上式称之为散列值（scattermatrixs），代表同一个分类投影后的散列值，也就是投影点的聚合度，它的值越小代表投影点越聚合。上式是w的函数，值越大w降维性能越好，下面的问题就是求解使上式取最大值的w。把散列函数展开：可以发现除w和wT外，剩余部分可以定义为：这就是原数据的散列矩阵了Sw称为Within-classscattermatrix。得到：展开J(w)的分子并定义SB，SB称为Between-classscatter。这样就得到了J(w)的最终表示：上式求极大值可以利用拉格朗日乘数法，不过需要限定一下分母的值，否则分子分母都变，怎么确定最好的w呢。可以令，利用拉格朗日乘数法得到：⇒𝑆𝐵𝑤=𝜆𝑆𝑤𝑤J𝑤=𝑤𝑇𝑆𝐵𝑤𝑤𝑇𝑆𝑤𝑤||𝑤𝑇𝑆𝑤𝑤||=1C𝑤=𝑤𝑇𝑆𝐵𝑤−𝜆(𝑤𝑇𝑆𝑤𝑤−1)⇒𝑑𝑐𝑑𝑤=2𝑆𝐵𝑤−2𝜆𝑆𝑤𝑤=0上式两边同乘以可以得到：发现w其实就是矩阵的特征向量。根据需求取前k个特征值最大的特征向量。举例：64*64大小的20张人脸图片进行训练。每一列表示一个样本，这样就一共有4096*20的待降维矩阵，然后对这个矩阵降维，请注意，如果采用列表示一个样本，那么获得的降维矩阵，是一个4096*19的矩阵，然后用这个降维矩阵对测试样本和训练样本降维，我们的测试样本是4096*1的矩阵，降维的时候这样：Y=UT*X;UT（对降维矩阵进行转置）为19*4096的矩阵，19*4096*4096*1，就获得了19*1的降维后的数据。𝑤=𝑆𝑤−1(𝜇1－𝜇2)𝑆𝑤−1𝑆𝐵𝑆𝑤−1𝑆𝐵𝑤=𝜆𝑤𝑆𝑤−1降维会不会对性能造成影响。并不是直接对原来的数据进行删减，而是把原来的数据映射到新的一个特征空间中继续表示，所有新的特征空间如果有19维，那么这19维足以能够表示非常非常多的数据，并没有对原来的数据进行删减，只是把原来的数据映射到新的空间中进行表示，所以你的测试样本也要同样的映射到这个空间中进行表示，这样就要求你保存住这个空间坐标转换矩阵，把测试样本同样的转换到相同的坐标空间中。小样本问题在LDA算法中存在训练样本数（20）比图像向量的维数4096要小很多的问题，即人脸小样本问题，因此类内离散度Sw总为奇异矩阵。这使得使用LDA方法求解变得很困难。为此，我们利用PCA算法将4096维的人脸图像压缩为71维，就可避免出现小样本问题。降维后再采用LDA算法利用人脸的类标签信息，就可提取出最具有判别能力的低维特征子空间。得到了k个特征向量，如何匹配某人脸和数据库内人脸是否相似呢，方法是将这个人脸在k个特征向量上做投影，得到k维的列向量或者行向量，然后和已有的投影求得欧式距离，根据阈值来判断是否匹配。1)计算类内散度矩阵Sw2)计算类间散度矩阵Sb3)计算矩阵Sw−1Sb4）计算Sw−1Sb的最大的d个特征值和对应的d个特征向量(w1,w2,...wd),得到投影矩阵5)对样本集中的每一个样本特征xi,转化为新的样本zi=WTxi6)得到输出样本集LDA过程回顾: