特征选择

特征选择是一种特殊的模型选择方法。考虑一种情况，当样本维数n远大于样本个数m的时候，根据经验风险与结构风险的关系，如下：

K表示模型的VC维，m表示训练集大小。

样本维数n很大，那么即使是用最简单的线性回归，K也能达到O(n)，后一项很大。

样本数量m很小，那么后一项很大。

 这样，很容易造成过拟合问题。如上就是小样本的情况。

处理这种情况，由于VC维很难再降低了，而样本数的增加也是受限制的，我们选择减小样本维数。

一种方法是PCA，LDA等模式识别中常见的方法，类似小波变换，求得线性高能量子空间。还有一种就是这里要论述的特征选择。

wrapper model feature selection

我们寻找特征集的一个子集。考虑到n个特征的子集有n^2个，我们无法遍历这么多的子集。于是采用启发式的方法，一个简单的方式就是顺序寻找，流程如下：

每一次迭代，采用交叉验证的方法，选择效果最好的一个特征加入现有特征集合。

backward search

与上面的算法基本相同，只不过特征集合从满集开始，每次选取效果最差的特征去除。

上面两种方法，每次迭代加入或去除一个特征，那么如果遍历所有的，时间复杂度为O（n^2）。

Filter feature selection

下面这种方法是一种启发式的方法，用很少的代价选择特征。对于每个特征，计算简单的衡量值S(i)，以此决定是否选择特征。

一个常用的衡量方法是线性相似性度量，即衡量xi与标签y的线性相关性系数。或者进一步的，我们可以用互信息衡量非线性的相关性系数。

互信息表示，一直x，y的不确定度减少了多少。减少的越多，说明这个变量与标签越相关。

之所以说互信息是衡量非线性的相关性，如下：

X,y的互信息=p(x)p(y)与p(x,y)的KL距离，也就是用p(x)p(y)来替代p(x,y)，所要增加信息量。如果x,y完全独立，那么p(x,y)=p(x)p(y)，KL距离为0，即I(x,y)=0，无法根据x猜测关于y的任何信息。

Matlab实现

选用数据集：http://archive.ics.uci.edu/ml/datasets/Statlog+%28Australian+Credit+Approval%29

这里选用SVM为分类器。

Wrapper 方法

clear;
clc;
load ‘data.mat‘;
[N,M]=size(train_feature);
train=[];%不断增加的训练与测试集
test=[];

n_0=sum(test_label==0)
n_1=sum(test_label==1)
n=length(test_label);

flag=zeros(N,1);%标记哪些特征已在特征集中
F=zeros(N,1);%记录各个特征的F值
max_iter=10;%最大迭代次数
for iter=1:max_iter
    F=zeros(N,1);
    for i=1:N
        if(flag(i)==0)
            train_temp=[train;train_feature(i,:)];
            test_temp=[test;test_feature(i,:)];
            svmStruct=svmtrain(train_temp‘,(train_label+1)‘);
            D=svmclassify(svmStruct,test_temp‘);
            %计算测试F值
            acc=0;
            pd=0;
            pf=0;
            pre=0;
            D=D-1;
            for ii=1:n
                if(D(ii)==test_label(ii))
                    acc=acc+1;
                end
                if(D(ii)==1&&test_label(ii)==0)
                    pf=pf+1;
                end
                if(D(ii)==1&&test_label(ii)==1)
                    pd=pd+1;
                end
                if(D(ii)==1)
                    pre=pre+1;
                end
                
            end
            
            acc=acc/n;
            pre=pd/pre;
            pf=pf/n_0;
            pd=pd/n_1;
            Fmeasure = 2*pd*pre/(pd+pre);
            F(i)=Fmeasure;
        end
    end
    [a,b]=max(F);
    flag(b)=1;
    train=[train;train_feature(b,:)];
    test=[test;test_feature(b,:)];
    %把最大F值的特征加入到特征集中
    
end

结果为：F_measure=85.97%

Filter 方法

clear;
clc;
load ‘data.mat‘;
[N,M]=size(train_feature);
n_0=sum(test_label==0);
n_1=sum(test_label==1);
n=length(test_label);
for i=1:N
    temp=train_feature(i,:);
    I(i)=Info(temp,train_label);
end
[a,b]=sort(I,‘descend‘);
train=[];
test=[];
max_i=10;
for i=1:max_i
    train=[train;train_feature(b(i),:)];
    test=[test;test_feature(b(i),:)];
end
svmStruct=svmtrain(train‘,(train_label+1)‘);
D=svmclassify(svmStruct,test‘);
%计算测试F值
acc=0;
pd=0;
pf=0;
pre=0;
D=D-1;
for ii=1:n
    if(D(ii)==test_label(ii))
        acc=acc+1;
    end
    if(D(ii)==1&&test_label(ii)==0)
        pf=pf+1;
    end
    if(D(ii)==1&&test_label(ii)==1)
        pd=pd+1;
    end
    if(D(ii)==1)
        pre=pre+1;
    end
    
end

acc=acc/n;
pre=pd/pre;
pf=pf/n_0;
pd=pd/n_1;
Fmeasure = 2*pd*pre/(pd+pre);

计算一个特征与标签的互信息函数：

function I=Info(feature,label)
A=unique(feature);
[n,m]=size(label);
[N,M]=size(A);
n_0=sum(label==0);
n_1=sum(label==1);
p_xy=zeros(M,2);
p_y=zeros(1,2);
p_x=zeros(M,1);
p_y(1)=sum(label==0)/m;
p_y(2)=sum(label==1)/m;
for i=1:M
    p_xy(i,1)=sum(label(feature==A(i))==0)/m;
    p_xy(i,2)=sum(label(feature==A(i))==1)/m;
    p_x(i,1)=sum(feature==A(i))/m;
end
I=0;
for i=1:M
    if(p_xy(i,1)~=0)
        I=I+p_xy(i,1)*log(p_xy(i,1)/(p_x(i)*p_y(1)));
    end
    if(p_xy(i,2)~=0)
        I=I+p_xy(i,2)*log(p_xy(i,2)/(p_x(i)*p_y(2)));
    end
end

同样取K=10；

结果：F_measure=84.21%

特征选择,布布扣,bubuko.com

特征选择

原文：http://blog.csdn.net/ice110956/article/details/23559373