模式识别之数据降维（三）：用SFS进行特征选择_专栏

之前的文章，我们已经介绍了特征选择的概念以及使用遗传算法进行特征选择，这篇文章，我们将讨论另一种特征选择的方法——使用SFS方法进行特征选择。

一、SFS简介

SFS(Sequential forward selection)，前向搜索法。这是一种类似于枚举法的方法，大概思路如下：先从所有特征中挑选一个最优特征，即挑选一个对学习样本分类最有帮助的一个特征，记作特征a，找到这个特征a之后，我们从头开始继续搜索，在寻找一个特征b，这个特征b和特征a组合在一起可以达到最优的分类效果，以此类推。比如我们要从5个特征中选择3个特征，首先，我们从5个特征中选择一个特征a，该特征满足：我们仅使用特征a就可以实现相比于其他特征单独分类更好的分类效果，然后再从头搜索，寻找一个特征b，使得特征a和特征b组合起来可以实现相比于其他特征与特征a组合起来更好的分类效果，接着，我们继续从头进行搜索，找到一个特征b，和特征a，b组合起来可以实现最好的分类效果，这样，我们就找到了5个特征里面最优的3个特征。以上，就是SFS的基本原理。

二、SFS的matlab实现

在介绍基本原理的时候，我们提到：要寻找最优的特征，那这个“最优”怎么去评判呢？这个评判依据称为可分性依据，可分性依据有很多，一种是直接使用机器学习算法的分类正确率作为可分性依据，这里我们使用最小错误贝叶斯分类器的正确率作为可分性依据。之前，我们使用遗传算法进行特征选择的时候，就是如此。下面是具体的matlab实现：
（1）导入二分类数据集，并初始化相关参数

（2）进行每一轮的特征选择，一次选取一组特征并计算已选特征下的可分性依据，每轮取最优性能下的一组特征。

（3）保存所选的特征信息，并打印最终的正确率

（4）计算可分性依据的函数如下（与贝叶斯二分类算法部分的代码一致，函数输入参数为目前已选择的特征组成的样本及标签信息，输出为分类正确率）

完整代码如下：

%使用SFS方法，学习算法采用贝叶斯
clear
load('2-Class Problem.mat');
tic

feature_end_nums=40;%从190维数据中选择40个
feature_selected=0;%所选择特征的索引值
dim=size(Training_class1,1);%维数

for select=1:feature_end_nums
    fprintf('开始第%d轮SFS\n',select);
    for d=1:dim
        %如果当前特征已经被选中，则跳过当前循环
        if isempty(feature_selected(feature_selected==d))==false
            continue;
        end
        feature_selected(select)=d;
        % 计算可分性依据
        res(d)=j(feature_selected,Training_class1,Training_class2,Testing,Label_Testing);
    end
    [max_acc,argmax]=max(res);%根据准确度，找出性能最优的维度
    res=0;%清零
    feature_selected(select)=argmax;
end
% 保存选择好的20个特征向量到文件中
save('feature_selected_SFS','feature_selected');
%最终准确率
acc_end=max_acc;
fprintf('正确率是%.2f%%\n',acc_end*100);
toc
%贝叶斯算法的准确度作为可分性依据
function result=j(feature_selected,Training_data1,Training_data2,Testing_data,Testing_label)
    %获取训练数量
    n1=size(Training_data1,2);
    n2=size(Training_data2,2);
    % 先验概率
    pw1=n1/(n1+n2);
    pw2=n2/(n1+n2);
    %选择训练数据和测试数据相应位置的特征值
    Training_data1=Training_data1(feature_selected,:);
    Training_data2=Training_data2(feature_selected,:);
    Testing_data=Testing_data(feature_selected,:);
    %参数估计
    [miu1,sigma1]=ParamerEstimation(Training_data1);
    [miu2,sigma2]=ParamerEstimation(Training_data2);
    %预测结果
    predict_label=0;
    test_num=size(Testing_data,2);%获取测试数据数量
    for i=1:test_num
        x=Testing_data(:,i);
        pxw1=gaussian(miu1,sigma1,x);
        pxw2=gaussian(miu2,sigma2,x);
        if pw1*pxw1>pw2*pxw2
            predict_label(i)=1;
        else
            predict_label(i)=2;
        end
    end
    % 计算精度
    acc=sum(predict_label==Testing_label)/test_num;
    result=acc;
end

程序运行结果：

用SFS选择最优的40个特征所用时间为595s，使用最终选择的40个特征进行分类可以达到100%的正确率。