Binary Particle Swarm Optimization(BPSO) for Feature Selection(二進制粒子群求解特征選擇)

文章目錄

• 前言
• 一、粒子群算法學習過程
• 二、特征選擇實戰
• • 1.資料集以及matlab源碼
  • 2.參數說明
  • 3.實驗結果
• 總結

前言

PSO算法是一種群智能優化算法，特點是布置速度快，收斂性強。同時面對着兩大問題，容易早熟和容易陷入局部最優。對于特征選擇這類離散型問題，我們使用二進制版本的BPSO進行優化。在PSO的疊代過程中，每個粒子都會向種群曆史最優解(Gbest)和粒子本身曆史最優解(Pbest)進行學習，同時也會不斷地更新Gbest與Pbest，最後會收斂在Gbest與Pbest之間的某個區域。

注意：（Gbest隻有一個，所有粒子都會向它學習，而Pbest對于每個粒子都有一個，隻屬于它們自己，它們隻會向自己的Pbest進行學習，這樣說應該大家都能聽懂了）

一、粒子群算法學習過程

對于特征選擇問題是這樣描述的，現實中由于采樣不均勻導緻某些采樣偏離了真實的分布，是以這部分特征反而會對資料的利用造成負面影響，那麼特征選擇的目的就是找出這些錯誤的特征和備援的特征。

那麼我們定義一個1*N維的0-1向量，每一位都隻能是0或者1，0代表不用這一維特征，1代表選用這一維

特征。

那麼BPSO是怎麼進行學習的呢？公式如下：

先看到第一個公式： 代表着粒子的速度更新公式，粒子在每一維都有一個速度值(前面我們已經提到了資料有很多元特征),那麼每一維都要進行更新。其中 ω ( t ) \omega(t) ω(t)代表着目前疊代次數的慣性系數，也就是說繼承來自上次疊代速度的比重，寫一篇部落格好難啊啊啊啊，繼續，另外加上的兩項呢，分别是與Pbest和Gbest位置的差異，這裡非常重要！！！，如果不好好了解，就弄不明白了。位置的差異通過兩個系數c1，c2和兩個[0,1]随機數r1，r2 相乘，學習系數的作用是加大向Pbest和Gbest靠攏的可能性，而随機數r1，r2的作用是也是一種精髓，啟發式随機搜尋的精髓，用它，肯定好，為什麼？誰也說不清，不用它，魯棒性真的會變差。

下面舉個例子，

粒子 [0 0 1 1 0 1 0 1]

gbest [1 0 1 0 0 0 1 1]

pbest [0 0 1 0 0 1 0 1]

先看第1維，我們現在要更新速度，發現

這兩個公式上面公式是0，下面公式是1，對吧，忽略前面的[0,1]随機數系數（期望值0.5）那麼加起來對速度的提升我們就假設為 1

現在看第6維，變成了上面公式是-1，下面公式是0，對速度的提升是-1，

由此我們發現，對于一個粒子如果它的Pbest和Gbest的某個次元位置不一緻，那麼它獲得速度的期望大概是-1。

好，再看第2維，上面公式是0，下面公式也是0，粒子沒有獲得速度提升，那麼之後會怎麼樣呢？變成了這樣

也就是說如果慣性系數小于1，那麼速度值越來越小了，大于1則越來越大。

再看到第二個公式： 這就是一個sigmoid函數，沒想到吧，這裡也會碰見神經網絡這哥們，為什麼用它？其他函數行嘛？當然可以，S型函數大家族那麼多，你挑一挑其他殺馬特(非主流)函數也行。大家都用sigmoid，這裡就照搬了。

再看到第三個公式：重點來了

如果sigmoid的傳回值大于[0,1]随機數(期望0.5),就把這個次元置為1，否則為1.注意這裡不是取反，而是單純的大于随機數置1，小于随機數置0，千萬不要記成取反了(我以前就這樣做)

我們再來複習一下sigmoid

那麼為什麼公式3有效呢？速度大就置為1，速度小就置為0，合理嗎？

我總結一下：

Pbest與Gbest為1，粒子為0，位置差異為正，那麼速度就大，此時粒子變為1的機率也越大，即完成了學習行為（向Pbest與Gbest靠攏了）

Pbest與Gbest為0，粒子為1，位置差異為負，那麼速度就小，此時粒子變為0的機率也越大，即完成了學習行為（向Pbest與Gbest靠攏了）

好好了解上述話語，即了解了BPSO粒子速度與位置更新的含義，網上有很多人說什麼以機率表示巴拉巴拉，其實并不好了解，隻是想當然得覺得很對。

二、特征選擇實戰

1.資料集以及matlab源碼

用一個資料集Wine(178instance，13features and 3 classes，資料集下載下傳連結和分類器ELM(沒别的就是快，下載下傳連結)進行實驗。

先把BPSO源碼貼出來再對BPSO算法參數進行一下說明：

代碼如下（示例）：

%% BinaryPSO
function [globalbest_x,globalbest_faval] = PSO(gN)
E0=0.999;                        %允許誤差
MaxNum=160;                      %粒子最大疊代次數
particlesize=30;                 %粒子群規模
c1=2;                            %每個粒子的個體學習因子，也稱為加速常數
c2=2;                            %每個粒子的社會學習因子，也稱為加速常數
w=0.6;                           %慣性因子
vmax=2;                          %粒子的最大飛翔速度
vmin=-vmax;

x = round(rand(particlesize,gN));% 初始化粒子位置
v = 4*rand(particlesize,gN)-2;   % 初始化粒子速度

f = zeros(particlesize,1);       % 初始化适應度函數
for i=1:particlesize
    f(i) = ELMResult(gN);
end

personalbest_x=x;%記錄粒子最佳位置
personalbest_faval=f;%記錄粒子最佳适應度函數值
[globalbest_faval,i]=max(personalbest_faval);%記錄種群最佳适應度函數值
globalbest_x=personalbest_x(i,:);%記錄種群最佳位置

k=1;  %開始疊代
while k<=MaxNum
    parfor i=1:particlesize
        f(i) = ELMResult(x(i,:));
        if f(i)>personalbest_faval(i) %判斷目前位置是否是曆史上最佳位置
            personalbest_faval(i)=f(i);
            personalbest_x(i,:)=x(i,:);
        end
    end
    if max(personalbest_faval)>globalbest_faval
        [globalbest_faval,i]=max(personalbest_faval);
        globalbest_x=personalbest_x(i,:);
    end
 
    % 更新方法，這部分也可以用矩陣完成，我故意貼一個很笨的更新方法，自己動手完成吧！
    for i=1:particlesize %更新粒子群裡每個個體的最新位置
        v(i,:)=w*v(i,:)+c1*rand*(personalbest_x(i,:)-x(i,:))...
            +c2*rand*(globalbest_x-x(i,:));
        for j=1:gN    %速度門檻值判斷及更新粒子的位置
            if v(i,j)>vmax
                v(i,j)=vmax;
            elseif v(i,j)<vmin
                v(i,j)=vmin;
            end
            if Sigmoid(v(i,j))>rand()
                x(i,j) = 1;
            else
                x(i,j) = 0;
            end
        end
    end  
    if abs(globalbest_faval)>E0,break,end
    k=k+1;
end
end
           

2.參數說明

MaxNum=160; %粒子最大疊代次數

代表粒子群算法的疊代次數，疊代次數越多當然效果越好啦，就是計算時間就上去了。

particlesize=30; %粒子群規模

種群規模一般不取太大了，30-100都可以把，個人調試一般取30或者40，其實特征次元稍微大一點比如100維，你多少個粒子塞進去，都影響不大了，還是要更快的看見種群之間的疊代差異以友善調參，把種群調小一點。

重點來了！！！！！

c1=2; %每個粒子的個體學習因子，也稱為加速常數

c2=2; %每個粒子的社會學習因子，也稱為加速常數

這兩個參數分别決定着粒子想Gbest和Pbest的學習機率，一般來說設成c1=2，c2=2，建議不要亂改，改下面兩個參數。

①

w=0.6; %慣性因子

很多說慣性因子，當然重要啊，重要極了，慣性因子越大，向Pbest與Gbest收斂的速度就越慢。當然，還有一種随着疊代次數慢慢減小的慣性因子:

wmax = 2;  wmin = 0.1;
w = wmax - (wmax-wmin)*k/MaxNum;
           

k為目前疊代次數，MaxNum為最大疊代次數, respectively.

②

vmax=2; %粒子的最大速度

vmin=-vmax;

速度最好要對稱呀！，關于0對稱，當然不對稱也是可以的，反正你拿着速度值域去看看sigmoid函數輸出是多少你大概就懂了，比如你取[0,2]就很容易向Pbest與Gbest學習靠攏，很快啊，沒有防出去，陷入局部最優了。比如你取[-2,0]，那麼粒子就會向按位取反的Gbest與Pbest中間取收斂。實際上，V就可以看成奔向Pbest與Gbest的速度嘛，太大了，容易很快陷入局部最優，建議極小值[-3，-1],極大值[1,3]。一定要進行速度限制，不然慣性系數大于1或者小于1的話，分别就會垂直起飛與垂直降落，直接玩完。

3.實驗結果

為了驗證特征選擇的有效性，我們先用ELM分類器對Wine資料集采用10-fold直接分類10000次(不要問為什麼這麼嚣張，問就是ELM快，i7-10700八核全開)，ELM兩個參數為(100隐藏層神經元，sig激活函數)，你猜猜一萬次運作多久？如圖：

平均運作時間：27/10000 = 0.0027秒，千分之三秒就分類完一次了，我們分别獲得了BestResult=98.24%accuracy，和AvgResult=95.64%acc.

那麼我們開啟特征選擇！

好家夥，就在我摁下去運作按鈕的一瞬間代碼已經終止了…

因為實際上我還有一個自動調整隐藏層神經元數量的子產品防止過拟合，那麼疊代兩代就找到了一個100%acc的解，它并沒有做特征選擇，隻是把隐藏層神經元數量改為了從100改為131，之前應該是神經元數量太少欠拟合了。那麼我們将神經元數量改為131，再來10000次ELM分類看看這個調整是否有效：

因為ELM帶有一定的随機性，是以選出來的解運作一次的話不一定更好，但是多次運作肯定是更好的，也就是平均結果。

如上圖，萬次結果最佳的為100%，與之前一緻，平均結果98.82%>95.64%，也有了很大的提升。

啊這，不是說好的特征選擇，怎麼變成調參了，好我們重新來一次：

可以看到第3次疊代acc已經為1了，選出了兩個沒用的特征，那麼我們将這個特征向量再去做萬次ELM，看看平均性能如何。。。。

可以看到，實驗了一個很基礎，簡單的UCI(寫這篇的時候伺服器抽筋了進不去，是以給了KEEl網址) dataset使用BPSO求解的特征向量選擇特征去做ELM分類，萬次最優acc為1，Avgacc為99.14%，遠高于之前的95.64%。

Wine 完結，撒花！

總結

提示：由于源碼涉及到機器學習内容，從資料導入，劃分資料集，定義K-fold，定義适應度函數等多個檔案，是以沒有一一貼出來，需要完整源碼可以私聊。