• 问题描述

顺序前进法和顺序后退法

要求:在sonar 和iris数据上进行验证顺序前进法和顺序后退法特征选择性能

提示:特征选择由类别可分性判据+搜索算法实现;

作业形式:上机+报告+程序

iris数据集包含150个数据集，有4维，分为3类，每类50个数据。

somar数据包含208个数据集，有60维，分为2类，第一类为98个数据，第二类为110个数据。

• 基本原理

1.顺序前进法(sequential forward selection, SFS)

这是一种从底向上的方法。第一个特征选择单独最优的特征,第二个特征从其余所有特征中选择与第一个特征组合在一起后准则最优的特征，后面每一个特征都选择与已经人选的特征组合起来最优的特征。

与单独最优特征的选择方法相比，顺序前进法考虑了一定的特征间组合的因素,但是其第一个特征仍然是仅靠单个特征的准则来选择的,而且每个特征一旦入选后就无法再剔除，即使它与后面选择的特征并不是最优的组合。当然,SFS方法的计算量也比单独最优特征的选择要大。

2.顺序后退法(sequential backward selection，SBS)

这是一种从顶向下的方法，与顺序前进法相对应。从所有特征开始逐一剔除不被选中的特征。每次剔除的特征都是使得剩余的特征的准则函数值最优的特征。

同样也有广义顺序后退法(generalized sequential backward selection, GSBS),每次不是剔除一个特征 ,而是剔除r个特征。

顺序后退法也考虑了特征间的组合，但是由于是从顶向下的方法,很多计算在高维空间进行,计算量比顺序前进法大些。顺序后退法在一旦剔除了某-特征后就无法再把它选人。

3.类别可分性判据

4.实验算法流程

• 实验结果

• MATLAB核心代码展示

1、计算类别可分性判据函数

% swsb.m

function[J]=swsb(dataset)
class_end=[dataset(1,end),0];
[n,p]=size(dataset);
for i =2:n
    if dataset(i,end)~=class_end(end,1)
        class_end(end+1,1)=dataset(i,end);
        class_end(end-1,2)=i-1;
    end
end
class_end(end,2)=n;%第一列为标签，第二列为该类在总样本中最后一个样本的索引
class_num=size(class_end,1);
class_end=[0,0;class_end];
sb=zeros(p-1);%样本类间离散度矩阵
sw=zeros(p-1);%样本类内离散度矩阵
dataset_mean=mean(dataset(:,1:end-1));%总样本均值
for i=1:class_num
    the_class=[];
    for j=class_end(i,2)+1:class_end(i+1,2)
        the_class=[the_class;dataset(j,1:end-1)];
    end
    the_class_mean=mean(the_class);%当前类样本均值
    P=(class_end(i+1,2)-class_end(i,2))/n;%先验概率
    sb_=P*(the_class_mean-dataset_mean)'*(the_class_mean-dataset_mean);
    
    sw_=zeros(p-1);
    for j=class_end(i,2)+1:class_end(i+1,2)
        sw_=sw_+(dataset(j,1:end-1)-the_class_mean)'*(dataset(j,1:end-1)-the_class_mean);
    end
    sw_=P*sw_/(class_end(i+1,2)-class_end(i,2));
    sb=sb+sb_;
    sw=sw+sw_;
end
%类间可分离性判据
J=trace(sw+sb);
end

2、顺序前进法函数

% SFS.m

function [increase_n,acc]=SFS(data)
% 顺序前进法.
[n,p]=size(data);
u=zeros(1,p);
for i=1:p
   u(i)=i;
end
dataset=[u;data];
increase_n=[];
acc=[];
for k=1:p-1
    J_result=[];
    for i=1:size(dataset,2)-1
        runningdataset=dataset(2:end,:);
        runningdataset(:,i)=[];
        J_result(end+1)=swsb(runningdataset);
    end
    [a,b]=min(J_result);
    increase_n(end+1)=dataset(1,b);
    dataset(:,b)=[];
    acc(end+1)=swsb([data(:,increase_n),data(:,end)]);
end
end

3、顺序后退法函数

% SBS.m

function [delete_n,acc]=SBS(data)
% 顺序后退法.
[n,p]=size(data);
u=zeros(1,p);
for i=1:p
   u(i)=i;
end
dataset=[u;data];
delete_n=[];
acc=[];
for k=1:p-1
    J_result=[];
    for i=1:size(dataset,2)-1
        runningdataset=dataset(2:end,:);
        runningdataset(:,i)=[];
        J_result(end+1)=swsb(runningdataset);
    end
    [a,b]=max(J_result);
    delete_n(end+1)=dataset(1,b);
    dataset(:,b)=[];
    acc(end+1)=swsb(dataset(2:end,:));
end
end

4、主函数

% run.m

clc,clear
% 导入sonar数据
filename = 'sonar.csv';
dataset_sonar = csvread(filename);
dataset_sonar = sort_label(dataset_sonar);
 
% 导入iris数据
filename = 'iris.csv';
dataset_iris = csvread(filename);
dataset_iris = sort_label(dataset_iris);
 
[increase_n,accSFS]=SFS(dataset_sonar);
figure();plot(accSFS);title('sonar_SFS');
[delete_n,accSBS]=SBS(dataset_sonar);
figure();plot(accSBS);title('sonar_SBS');
[increase_n,accSFS]=SFS(dataset_iris);
figure();plot(accSFS);title('iris_SFS');
[delete_n,accSBS]=SBS(dataset_iris);
figure();plot(accSBS);title('iris_SBS');