线性判别分析

线性判别分析（Linear Discriminant Analysis）简称LDA，是一种监督学习方法。LDA是在目前机器学习、数据挖掘领域经典且热门的一个算法，据我所知，百度的商务搜索部里面就用了不少这方面的算法。

LDA的原理是，将带上标签的数据（点），通过投影的方法，投影到维度更低的空间中，使得投影后的点，会形成按类别区分，一簇一簇的情况，相同类别的点，将会在投影后的空间中更接近。要说明白LDA，首先得弄明白线性分类器：因为LDA是一种线性分类器。对于K-分类的一个分类问题，会有K个线性函数：

当满足条件：对于所有的j，都有Yk > Yj,的时候，我们就说x属于类别k。对于每一个分类，都有一个公式去算一个分值，在所有的公式得到的分值中，找一个最大的，就是所属的分类了。
上式实际上就是一种投影，是将一个高维的点投影到一条高维的直线上，LDA最求的目标是，给出一个标注了类别的数据集，投影到了一条直线之后，能够使得点尽量的按类别区分开，当k=2即二分类问题的时候，如下图所示：

clip_image002
红色的方形的点为0类的原始点、蓝色的方形点为1类的原始点，经过原点的那条线就是投影的直线，从图上可以清楚的看到，红色的点和蓝色的点被原点明显的分开了，这个数据只是随便画的，如果在高维的情况下，看起来会更好一点。下面我来推导一下二分类LDA问题的公式：
假设用来区分二分类的直线（投影函数)为：
image
LDA分类的一个目标是使得不同类别之间的距离越远越好，同一类别之中的距离越近越好，所以我们需要定义几个关键的值。
类别i的原始中心点为：（Di表示属于类别i的点)
image
类别i投影后的中心点为：
image
衡量类别i投影后，类别点之间的分散程度（方差）为：
image
最终我们可以得到一个下面的公式，表示LDA投影到w后的损失函数：
image
我们分类的目标是，使得类别内的点距离越近越好（集中），类别间的点越远越好。分 母表示每一个类别内的方差之和，方差越大表示一个类别内的点越分散，分子为两个类别各自的中心点的距离的平方，我们最大化J(w)就可以求出最优的w了。 想要求出最优的w，可以使用拉格朗日乘子法，但是现在我们得到的J(w)里面，w是不能被单独提出来的，我们就得想办法将w单独提出来。
我们定义一个投影前的各类别分散程度的矩阵，这个矩阵看起来有一点麻烦，其实意思是，如果某一个分类的输入点集Di里面的点距离这个分类的中心店mi越近，则Si里面元素的值就越小，如果分类的点都紧紧地围绕着mi，则Si里面的元素值越更接近0.
image
带入Si，将J(w)分母化为：
image
image
同样的将J(w)分子化为：
image
这样损失函数可以化成下面的形式：
image
这样就可以用最喜欢的拉格朗日乘子法了，但是还有一个问题，如果分子、分母是都可以取任意值的，那就会使得有无穷解，我们将分母限制为长度为1（这是用拉 格朗日乘子法一个很重要的技巧，在下面将说的PCA里面也会用到，如果忘记了，请复习一下高数），并作为拉格朗日乘子法的限制条件，带入得到：
image
这样的式子就是一个求特征值的问题了。
对于N(N>2)分类的问题，我就直接写出下面的结论了：
image
这同样是一个求特征值的问题，我们求出的第i大的特征向量，就是对应的Wi了。
这里想多谈谈特征值，特征值在纯数学、量子力学、固体力学、计算机等等领域都有广泛的应用，特征值表示的是矩阵的性质，当我们取到矩阵的前N个最大的特征 值的时候，我们可以说提取到的矩阵主要的成分（这个和之后的PCA相关，但是不是完全一样的概念）。在机器学习领域，不少的地方都要用到特征值的计算，比 如说图像识别、pagerank、LDA、还有之后将会提到的PCA等等。
下图是图像识别中广泛用到的特征脸（eigen face），提取出特征脸有两个目的，首先是为了压缩数据，对于一张图片，只需要保存其最重要的部分就是了，然后是为了使得程序更容易处理，在提取主要特 征的时候，很多的噪声都被过滤掉了。跟下面将谈到的PCA的作用非常相关。
image
特征值的求法有很多，求一个D * D的矩阵的时间复杂度是O(D^3), 也有一些求Top M的方法，比如说power method，它的时间复杂度是O(D^2 * M), 总体来说，求特征值是一个很费时间的操作，如果是单机环境下，是很局限的。

#-*- coding: UTF-8 -*-
from numpy import *
import numpy
def lda(c1,c2):
    #c1 第一类样本，每行是一个样本
    #c2 第二类样本，每行是一个样本

    #计算各类样本的均值和所有样本均值
    m1=mean(c1,axis=0)#第一类样本均值
    m2=mean(c2,axis=0)#第二类样本均值
    c=vstack((c1,c2))#所有样本
    m=mean(c,axis=0)#所有样本的均值

    #计算类内离散度矩阵Sw
    n1=c1.shape[0]#第一类样本数
    print(n1);
    n2=c2.shape[0]#第二类样本数
    #求第一类样本的散列矩阵s1
    s1=0
    for i in range(0,n1):
        s1=s1+(c1[i,:]-m1).T*(c1[i,:]-m1)
    #求第二类样本的散列矩阵s2
    s2=0
    for i in range(0,n2):
        s2=s2+(c2[i,:]-m2).T*(c2[i,:]-m2)
    Sw=(n1*s1+n2*s2)/(n1+n2)
    #计算类间离散度矩阵Sb
    Sb=(n1*(m-m1).T*(m-m1)+n2*(m-m2).T*(m-m2))/(n1+n2)
    #求最大特征值对应的特征向量
    eigvalue,eigvector=linalg.eig(mat(Sw).I*Sb)#特征值和特征向量
    indexVec=numpy.argsort(-eigvalue)#对eigvalue从大到小排序，返回索引
    nLargestIndex=indexVec[:1] #取出最大的特征值的索引
    W=eigvector[:,nLargestIndex] #取出最大的特征值对应的特征向量
    return W

function [ W] = FisherLDA(w1,w2)
%W最大特征值对应的特征向量
%w1 第一类样本
%w2 第二类样本

%第一步：计算样本均值向量
m1=mean(w1);%第一类样本均值
m2=mean(w2);%第二类样本均值
m=mean([w1;w2]);%总样本均值

%第二步：计算类内离散度矩阵Sw
n1=size(w1,1);%第一类样本数
n2=size(w2,1);%第二类样本数
  %求第一类样本的散列矩阵s1
s1=0;
for i=1:n1
    s1=s1+(w1(i,:)-m1)'*(w1(i,:)-m1);
end
  %求第二类样本的散列矩阵s2
s2=0;
for i=1:n2
    s2=s2+(w2(i,:)-m2)'*(w2(i,:)-m2);
end
Sw=(n1*s1+n2*s2)/(n1+n2);
%第三步：计算类间离散度矩阵Sb
Sb=(n1*(m-m1)'*(m-m1)+n2*(m-m2)'*(m-m2))/(n1+n2);
%第四步：求最大特征值和特征向量
%[V,D]=eig(inv(Sw)*Sb);%特征向量V，特征值D
A = repmat(0.1,[1,size(Sw,1)]);
B = diag(A);
[V,D]=eig(inv(Sw + B)*Sb);
[a,b]=max(max(D));
W=V(:,b);%最大特征值对应的特征向量
end

cls1_data=[2.95 6.63;2.53 7.79;3.57 5.65;3.16 5.47];
cls2_data=[2.58 4.46;2.16 6.22;3.27 3.52];
%样本投影前
plot(cls1_data(:,1),cls1_data(:,2),'.r');
hold on;
plot(cls2_data(:,1),cls2_data(:,2),'*b');
hold on;
W=FisherLDA(cls1_data,cls2_data);
%样本投影后
new1=cls1_data*W;
new2=cls2_data*W;
k=W(2)/W(1);
plot([0,6],[0,6*k],'-k');
axis([2 6 0 11]);
hold on;
 
%画出样本投影到子空间点
for i=1:4
    temp=cls1_data(i,:);
    newx=(temp(1)+k*temp(2))/(k*k+1);
    newy=k*newx;
    plot(newx,newy,'*r');
end;
 
for i=1:3
    temp=cls2_data(i,:);
    newx=(temp(1)+k*temp(2))/(k*k+1);
    newy=k*newx;
    plot(newx,newy,'ob');
end;

LDA算法学习（Matlab实现）