SFS.SBS.GA特征提取比较

发表于 | 分类于

基于MATLAB的顺序前进、顺序后退及遗传算法特征提取比较

一、概念

特征提取

要在低维空间中更好的分类，变换的有效性最好用错误概率来衡量，然而其计算复杂。从计算观点看，用其中的一些判据进行特征提取往往是唯一可行的方法。

特征提取方法包括按欧氏距离度量、按概率距离判据、基于判别熵最小化等方法。

特征选择

特征选择即对原有特征进行删选优化，从原始特种中挑选出一些最有代表性、分类性能最好的特征进行分类。

需要解决的问题：选择的标准、快速寻优算法。

经典特征选择算法：
1）分支定界法：最优搜索
2）次优搜索：单独最优特征组合法、顺序前进法、顺序后退法
3）其他：模拟退火法、Tabu 搜索法、遗传算法

顺序前进法

顺序前进法是自下而上的搜索方法。

每次从未入选的特征中选择一个特征，使得它与已入选的特征组合在一起时所得的可分性或分类识别率为最大，直至特征数增加到d为止。该方法考虑了所选特征与已入选特征之间的相关性。比单独最优特征组合效果好。 †

缺点：一旦某特征已入选，即使由于后加入的特 征使它变为多于也无法再把它剔除。

顺序后退法

顺序后退法是自上而下的搜索方法。 该方法根据特征子集的分类表现来选择特征。 †

搜索特征子集：从全体特征开始，每次剔除一个特征，使得所保留的特征集合有最大的可分性或分类识别率。依次迭代，直至可分性或识别率开始下降为止。 †

和顺序前进法比较，顺序后退法有两个特点：计算过程中可以估计每此去掉一个特征所造可分性的降低；由于顺序后退法的计算是在高位空间进行的，所以计算量比顺序前进法要大。

遗传算法

从生物进化论得到启迪。遗传，变异，自然选择。基于该思想发展了遗传优化算法。 †

基因链码：待解问题的解的编码，每个基因链码也称为一个个体。对于特征选择，可用一个 D 位的 0/1 构成的串表示一种特征组合。 †

群体：若干个个体的集合，即问题的一些解的集合。 †

交叉：由当前两个个体的链码交叉产生新一代的两个个体。 †

变异：由一个链码随机选取某基因使其翻转。

适应度：每个个体xi的函数值fi，个体xi越好，适应度fi越大。新一代群体对环境的平均适应度比父代高。 †
遗传算法的基本框架： †
Step1: 令进化代数t=0。 †
Step2: 给出初始化群体P(t)，令xg为任一个体。 †
Step3: 对P(t)中每个个体估值，并将群体中最优解x’与xg比较，如果x’的性能优于 xg，则xg=x’。 †
Step4: 如果终止条件满足，则算法结束，xg为算法的结果。否则继续。
Step5: 从P(t)中选择个体并进行交叉和变异操作，得到新一代群体P(t+1)。令t=t+1,转到Step3。

二、分析

SFS、SBS

在顺序前进、顺序后退的特征提取中，先确定主函数。首先设定特征提取数为30，然后分别引用SFS、SBS函数进行特征提取，再用k近邻计算k值不同时的准确率，画出Figure1，进行比较。然后根据图像得出k=2 时特征提取准确率相对最高，所以令k=2，根据特征提取数的不同画出Figure2。在SFS函数中，先计算各分类中样本个数，然后将未提取特征数按种类分为两部分。逐个从未提取特征中抽取特征，通过separability函数计算可分性，将可分性最高的特征划入已抽取特征范围内。

SBS函数大体同上，将所有数据划入已抽取特征范围内，然后逐个抽取特征加入未提取特征。在separability函数中，可分性判定采用基于距离的方式——分别计算样本的类内离散度和类间离散度，进行trace操作。

遗传算法

在遗传算法主程序中，首先确定种群内染色体数、变异概率、交叉概率、迭代次数，然后引入genetic进行遗传处理。设定总共处理一百次，取其中的最大值输出。

在核心程序genetic中，先随机生成亲代，然后依次进行计算适应度、轮盘赌、交叉、变异操作，最后找到适应度最大的染色体选择的特征节点，最后用最近临法计算正确率。

在轮盘赌选择法中，如果适应度为0，则随机选择；如果适应度不为0，则只保留适应度不为1的个体。此外，引入精英选择，将最优质的染色体直接引入下一代。

计算适应度通过计算可分性达到。交叉是以所选节点为中心，将两个染色体进行调换。变异通过将染色体与1异或得到。

数据分析

Sonar：共有 208 个样本，特征数为 60，样本分为 97 和 111 两类。

三、核心代码

SFS、SBS

主程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
clear all
clc
load sonar;
[am,an]=size(sonar);
c=2;
r1=30;
r2=30;
sf=SFS(sonar,c,r1);
sb=SBS(sonar,c,r2);
cf=knn(19,sf,13,16);
cb=knn(19,sb,13,16);
x1=[1:2:19];
figure(1)
hold on;
plot(x1,cf,'b');
plot(x1,cb,'r');
plot(x1,cf,'o');
plot(x1,cb,'x');
grid on;
correctf=[];
correctb=[];
for i=1:an-1
    samplef=SFS(sonar,c,i);
    sampleb=SBS(sonar,c,(an-1-i));
    correctf=[correctf,knn(2,sf,13,16)];
    correctb=[correctb,knn(2,sb,13,16)];
end
x2=[1:an-1];
figure(2)
hold on;
plot(x2,correctf,'b');
plot(x2,correctb,'r');
plot(x2,correctf,'o');
plot(x2,correctb,'x');
grid on

SFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function [choosen]=SFS(data,c,r)
[am,an]=size(data);
data=sortrows(data,an);
data(am+1,1:an-1)=[1:an-1];
for i=1:c
    dd=find(data(:,an)==i); 
    ai(i)=length(dd); 
end
clear i
x1=data(1:ai(1),:);
x2=data(ai(1)+1:am,:);
choosen=zeros(am,r); 
for i=1:r
    p=size(x1,2);
    for j=1:p-1
        if i==1
            J(1,j)=separability(x1(:,j),x2(1:ai(2),j));
        else
            J(1,j)=separability([choosen(1:ai(1),:),x1(:,j)],[choosen(ai(1)+1:am,:),x2(1:ai(2),j)]);
        end
        J(2,j)=x2(ai(2)+1,j);
    end
    J=sortrows(J',1);
    e(i,:)=J(p-1,:);
    [row,col]==e(i,2);
    choosen(:,i)=[x1(:,col);x2(:,col)];
    x1(:,col)=[];
    x2(:,col)=[];
    clear J
end
choosen(:,r+1)=data(1:am,an);

SBS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function [choosen]=SBS(data,c,r)
[am,an]=size(data);
data=sortrows(data,an);
data(am+1,1:an-1)=[1:an-1];
for i=1:c
    dd=find(data(:,an)==i); 
    ai(i)=length(dd); 
end
clear i
choosen=data;
abandon=zeros(am,r);
for i=1:r
    p=size(choosen,2);
    for j=1:p-1
        x=choosen;
        x(:,j)=[];
        J(1,j)=separability_criterion(x(1:ai(1),:),x(ai(1)+1:am,:));
        J(2,j)=choosen(am+1,j);
    end
    J=sortrows(J',1);
    [row,col]==J(1,2); 
    abandon(:,i)=choosen(:,col);
    choosen(:,col)=[];
    clear J
end

separability

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function Jd=separability(w1,w2)
w1=w1';
w2=w2';
[mm1,nn1]=size(w1);
[mm2,nn2]=size(w2);
m1=mean(w1,2);
m2=mean(w2,2);
s1=zeros(mm1,mm1);
s2=zeros(mm2,mm2);
for i=1:mm1
    s1=s1+(w1(:,i)-m1)*(w1(:,i)-m1)';
end
for j=1:mm2
    s2=s2+(w2(:,j)-m1)*(w2(:,j)-m2)';
end
sw=s1+s2;
sb=(m1-m2)*(m1-m2)';
Jd=trace(sw+sb);

遗传算法

主程序

1
2
3
4
5
6
7
8
9
10
11
12
clear all
load sonar;
data=sonar;
pop=31;
pcr=0.6;
pmu=0.1;
L=150;
for i=1:100
    y(i)=heredity(data,pop,pcr,pmu,L);
end
x=max(y);
disp(sprintf('Correct rate of genetic algorithm£º%4.4f',x));

genetic

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function [y]=genetic(data,pop,pcr,pmu,L)
[am,an]=size(data);
data=sortrows(data,an);
data(am+1,1:an-1)=[1:an-1];
choosensize=size(data,2)-1;
parent=cell(1,pop);
for ip=1:pop
    parent{ip}=rand(choosensize,1);
    parent{ip}(parent{ip}>=0.5)=1;
    parent{ip}(parent{ip}<0.5)=0; 
end
clear ip
group=parent;
fit=cell(1,L);
for l=1:L
    fit{l}=fitness(pop,group,data);
    new=roulette(group,pop,fit{l});
    new=crossover(pcr,new,pop,an-1);
    group=mutation(new,pop,pmu,an-1);
end
index=find(group{1}(:,1)==1);
r=length(index);
choosen=[];
for i=1:r
    choosen=[choosen,data(:,index(i))];
end
choosen(:,r+1)=data(:,an);
k=1;
y=knn(k,choosen,13,16);

fitness

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function [f]=fitness(groupsize,group,data)
[am,an]=size(data);
for m=1:groupsize
    index=find(group{m}(:,1)==1);
    p=length(index);
    choosen=[];
    for i=1:p
        choosen=[choosen,data(:,index(i))];
    end
    for j=1:2
        d=find(data(:,an)==j);
        ai(j)=length(d);
    end
    f(m)=separability(choosen(1:ai(1),:),choosen(ai(1)+1:am,:));
end
rate=sum(f);
f(2,:)=[1:groupsize];
f=sortrows(f',1);
f(:,3)=f(:,1)/rate;
for i=1:groupsize
    f(i,4)=sum(f(1:i,3));
end

roulette

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function [new]=roulette(group,groupsize,fitness)
new=cell(1,groupsize);
index=zeros(1,groupsize);
if max(fitness(:,1))==0&min(fitness(:,1))==0
    index=ceil(rand(1,groupsize)*groupsize);
else
    index(1)=fitness(groupsize,2);
    persist=find(fitness(:,1));
    choose=group{persist};
    rou=rand(1,groupsize);
    for i=2:groupsize,
        for j=1:groupsize,
            if rou(i)<fitness(j,4)
                index(i)=j;
                break
            end
        end
    end
    for k=1:length(index);
        new{k}=group{index(k)};
    end
end

crossover

1
2
3
4
5
6
7
8
9
10
function [group]=crossover(crossrate,group,groupsize,n)
for i=2:2:groupsize-1 
    cross=rand;
    if cross<crossrate 
        point=ceil(rand*n); 
        x=group{i}(point:n,:);
        group{i}(point:n,:)=group{i+1}(point:n,:);
        group{i+1}(point:n,:)=x;
    end
end

mutation

1
2
3
4
5
6
7
8
function [group]=mutation(group,groupsize,mutaterate,n)
mutate=rand;
for i=2:groupsize
    if mutate<mutaterate
        point=ceil(rand*n);
        group{i}(point,1)=xor(group{i}(point,1),1);
    end
end

四、数据图像

顺序前进法、顺序后退法

图中蓝色线为特征前进法，红色线为顺序后退法。图一横坐标为k值，图二横坐标为选择特征数，两图纵坐标均为正确率。当选择特征数为30，K取不同值时，观察正确率的变化情况。由图可得k取2时正确率较高。

1

当K取2时，K近邻正确率随特征选择数的变化情况。

2

遗传算法

迭代150次，共进行100次运算，取正确率最大值。

Correct rate of genetic algorithm：0.8462