基于PSO的小樣本特征選擇優化算法研究

楊鶴標，劉 芳，胡驚濤

(江蘇大學 計算機科學與通信工程學院， 鎮江 212013)

在實際生活應用中小樣本數據集普遍存在，如自然語言的文本數據、醫療領域的疾病數據、視覺成像的圖像數據等[1].小樣本數據是指數據維數高，樣本絕對數量少或者樣本數遠小于數據維數特征的數據[2].小樣本數據有維度高的特征，會出現噪聲、冗余和不相關特征等現象；加之訓練樣本數目少，使得傳統的學習方法效能嚴重降低，易造成過擬合現象.研究發現，在不改變原特征空間的前提下，選擇一些分辨力高同時能夠表征原始特征空間性質的特征子集是解決小樣本高維度[3]和過擬合問題[4]的關鍵.為此，文獻[5]利用數據集訓練attention模型，將一個標記的訓練集和一個未標記的測試集映射到其標簽中，進行微調以適應新的特征集，以解決one-shot learning問題；文獻[6]在孿生網絡[7]基礎上引入遷移學習[8]算法，利用YOLOv2算法模型參數，對損失函數進行修改，采取局部放大策略提高小樣本場景中算法的性能.目前還提出了K-緊鄰模型[9]、范數支持向量機[10]、低秩矩陣近似[11]等特征選擇方法，這些特征選擇方法在特征間冗余處理方面還未達到良好的效果.

最大化類間距離可以提高特征子集泛化能力，最小化類內距離可以提高特征子集的擬合精度，因此需要最大化類間距離的同時最小化類內距離，在對文本特征達到理想的精確度的同時還可以提高特征的泛化能力.對此采用粒子群算法(particle swarm optimization,PSO)，在獲取每個特征向量的gBest(全局最優權重)和pBest(局部最優權重)的基礎之上，能夠有效的挖掘到每個全局最優特征的信息并且避免局部最優特征的隔閡影響，這樣能夠在較低時間復雜度的情況下有效避免最優權值變化范圍出現的不平衡現象.

1 相關工作

1.1 特征選擇的相關研究

特征選擇是解決小樣本問題的關鍵步驟.目前主流的特征選擇方法支持向量機(support vector machines,SVM)[12]及套索算法回歸模型(lease absolution shrinkage and selection operator,Lasso)[13]等，在處理數據時有很大的優勢，SVM和Lasso目的是找到一個將分類效果達到最合理化的超平面，對不等式約束條件下的二次型遞推更新式函數進行優化，以達到目標函數的負梯度方向與約束函數的梯度方向一致最優解的目的[14].

但是在處理具有語義信息的數據時，上述方法存在不能獲取深層次語義組合特征的缺陷，會造成語義的缺失.長短期記憶網絡(long short-term memory,LSTM)有處理連續性數據的能力，在處理文本數據獲取文本特征的同時包含了上下文信息[9]，在自然語言處理領域已有多種應用，如谷歌在機器翻譯方面就使用了LSTM[15].學者們對LSTM進行了更加廣泛的研究，如樹形結構的長短期記憶神經網絡(Tree-LSTM)、雙向長短期記憶網絡(Bi-LSTM)等，是解決序列化的特征選擇問題的首選方法.

1.2 粒子群算法

PSO算法可完成人工神經網絡中的連接權值訓練、結構設計、學習規則調整、特征選擇、連接權值的初始化和規則提取[16-17]等.將個體權值與整個特征集里的其它特征向量權值共享，找到最優的個體權重作為整個特征集的當前全局最優解，特征中的所有特征向量通過自己找到的當前個體權重和整個特征集共享當前全局最優解權重，根據自己的上下義詞距離來確定最優權重.

令D為算法搜索空間的維數，S為特征集的規模(即包含特征的個數)，于是第i個特征在D維空間的位置定義為：

Xi=(xi1,xi2…，xiD)

(1)

第i個特征的上義詞距離為：

Vi=(xi1,vi2…，viD)

(2)

第i個特征的下義詞距離為：

V′i=(v′i1,v′i2…，v′iD)

(3)

第i個特征的局部最優權重為：

Pp=(pp1,pp2…，ppD)

(4)

第i個特征的全局最優權重為：

Pg=(pg1,pg2…，pgD)

(5)

對于第k代的第i個特征其第d維(1≤d≤D)的上下義詞距離更新公式為：

vid(k+1)=wvid(k)+c1randid(.)[pid(k)-xid(k)]+c2randid(.)[pid(k)-xid(k)]

(6)

式中：w∈[0,1];c1、c2為非負常數；randid(.)∈[0,1]，特征向量上下義詞差的絕對值小于等于閾值，產生趨于0的回歸系數，使均方誤差平滑收斂.

2 循環神經網絡下的Bi-PSO算法

文中選用基于LSTM的文本特征選擇模型，利用ReliefF算法效率高、普適性強的特點來獲取候選子集.使添加了記憶細胞變種的Bi-LSTM的梯度dct/dct-1為1，以防止出現梯度消失現象[18]；在獲得特征的上下文語義的基礎上，調整權值參數和偏置值，獲得文本特征權重.利用PSO的算法思想進行優化，限定學習因子c1和c2的值，度量新選特征Pi(k)和候選特征Xi(k)之間的相關性，以達到特征權重最優、整體平衡狀態，獲得最優特征子集.

2.1 候選子集生成

實際應用領域的數據集中，特征與特征之間存在各種各樣的內在關聯[19].ReliefF特征選擇算法的優勢在于能夠快速、簡單和高效地選擇出特征子集，獲得的子集在不同的學習算法中具有很強的普適性，一般直接利用所有訓練數據的統計性能評估特征.ReliefF特征選擇過程如圖1.

圖1 ReliefF模式特征選擇過程Fig.1 ReliefF mode feature selection process

特征的權重更新公式如下：

W(A)=

(7)

式中：diff(A,R1,R2)為樣本R1和R2在特征A上的差；Mj(C)為類C?class(R)中第j個最近鄰樣本;m為抽樣次數；R為近鄰數.

(8)

ReliefF模式特征選擇算法與具體的分類算法是相互獨立的，單獨作為學習算法的預處理步驟，得到候選特征子集.

2.2 基于Bi-LSTM的語義模型

循環神經網絡(recurrent neural network,RNN)在傳統的前饋神經網絡中隱藏層節點之間加入了連接關系，使得RNN有了時間的概念，能夠記住某個時間段的信息，從而對任意長度的序列數據進行處理.RNN單元含有一個記憶模塊，而這個記憶模塊與其輸入、輸出神經元直接相連，它可以選擇性的記憶某些詞語的信息而不會受到文本序列變長的影響.

理論上RNN可以處理任意長度的序列數據，但是由于梯度消失和梯度爆炸問題，使得RNN不能有效的解決長距離依賴問題.長短期記憶網絡(LSTM)就是為了解決這個問題而設計的，其核心結構是記憶細胞(Memory Cell)C，使得梯度dct/dct-1為1，比普通的循環神經網絡更好的獲取到長距離的信息.LSTM在處理序列文本時只考慮先前的時序信息而忽略了上下文信息，而它的變種雙向長短期記憶網絡(Bi-LSTM)則很好的解決了這一問題，它既能考慮到先前的時間信息，也能考慮到未來的時間信息，所以文中采用Bi-LSTM作為記憶層，Bi-LSTM的結構如圖2.

圖2 Bi-LSTM結構Fig.2 Bi-LSTM structure

給定句子輸入x={x1,x2,…,xn}，其中xt為t時刻的詞向量，t-1時刻隱藏層的狀態為ht-1，則t時刻LSTM的記憶細胞狀態由以下幾個門限決定.

忘記門：決定了LSTM何時會丟失細胞中的信息，公式為：

ft=σ(Wxfxt+Whfht-1+bf)

(9)

輸入與更新門：輸入門與更新門確定LSTM要把什么信息保存在細胞中，公式為：

it=σ(Wxixt+Whiht-1+bi)

(10)

ct=ftct-1+iiτ(Wxcxt+Whcht-1+bc)

(11)

輸出門：輸出門確定了將要輸出的值，公式為：

Ot=σ(Wxoxt+Who+ht-1+bo)

(12)

ht=otθ(ct)

(13)

式中：σ為Sigmoid層，用W和b來連接輸入層和隱藏層；O為神經網絡的輸出狀態；Q為輸出門的細細胞狀態.Bi-LSTM最終將兩個方向產生的輸出向量h相連接，得到最終的輸出：h?h.

2.3 Bi-PSO的算法原理

粒子群優化算法無法直接優化多目標問題，因此需要對多目標進行處理.文獻[20]將基于分解的多目標進化算法的思想引入粒子群優化，再將多目標聚合為單目標后，相鄰優化問題相互借鑒信息，以實現多目標問題.文中根據上下義詞進行動態加權，實現多目標優化問題.

首先，候選特征依據其與已選特征的相互關系(冗余或依賴)賦予動態權值，每當新特征被選出后，根據候選特征的權值進行動態的調整.算法通過不斷提高與已選特征子集具有依賴關系的特征的權值，以及降低與之具有冗余關系的特征的權值，從而能夠在較低時間復雜度的情況下選擇高度相關、內部依賴和低度冗余的特征子集.Bi-PSO算法的具體實現過程如下.

Bi-PSO算法Input:X// Candidate feature subsetOutput:D// Optimal feature subset1.D[ ]2.D[ ]3.PI=Random X()4.while (Xi(k+1)≥Pi(k)) do5. Pi(k+1)=Pi(k))6. D′.and(Pi(k+1))7. P(g)(k)=Random D′()//P(g)(k) is the Optimal feature8. if P(g)(k)=arg f(Pi(k)) then9. D.add (P(g)(k))10. else11. Xi(k+1)=Xi(k)+Vi(k+1)//Vi(k) is the adjustment range of the Threshold12. return Step413. end if14.else15. Pi(k+1)=Xi(k+1)16. D.add Pi(k+1)17.end while18.return D

Bi-PSO算法的主要特點是：候選特征根據其與已選特征的相互關系(冗余或依賴)賦予權值.根據候選特征的權值進行動態的改變，其步驟為：

(1) 隨機從原始特征空間中選取特征作為初始優化點，并在搜索過程中隨機選擇將要增加或刪除的特征(隨機搜索避免了在同一方向上容易產生局部最優解的缺點)，第i個候選特征的權重更新公式為：

Xi(k+1)=Xi(k)+Vi(k+1)

(14)

(2) 限定學習因子c1和c2的值，度量新選Pi(k)和候選特征Xi(k)之間的相關性，根據全局特征調整每個候選特征當前的權重Pi(k+1)，更新公式為：

(15)

式中:f(.)為目標函數.

(3) 調整最終特征權值，權衡整個特征子集g的最優權重，減少特征冗余，公式為：

Pg(k+1)=arg minf(Pi(k+1)) 1≤i≤S

(16)

(4) 判斷計算結果是否小于允許誤差精度，如果是則保存并輸出此時計算的特征權值和偏差值作為當前訓練的結果，加入最優特征子集，當前候選特征i訓練結束；否則繼續第二步計算.

(5) 提高與已選特征集合具有依賴關系的候選特征的權值、降低與之具有冗余關系的候選特征的權值，獲得最終特征子集D.

3 實驗環境和實驗數據

實驗環境配置1：使用python及TensorFlow框架編寫模型，Basic- LSTMCell(size)定義兩個LSTM網絡，size為制定的隱含層神經元數目，創建好后將兩個神經網絡傳入static_bidirectional_rnn

(lstm_fw_cell, lstm_bw_cell),即創建好雙向長短期記憶網絡.模型的訓練時間取決于模型的層數以及神經元的個數，文中設定每層神經元個數為20，層數為2層.

實驗環境配置2：根據Bi-LSTM得到的實驗結果進行特征子集的優化，采用了4種不同的分類算法分別比較各種特征選擇算法的性能，分別是樸素貝葉斯(Naive Bayesian)、支持向量機(SVM)、最近鄰(1-Nearest Neighbor,1-NN)和C4.5決策樹，并選用mRMR、ReliefF和IG作對比實驗.實驗平臺采用公認的機器學習集成軟件Weka，各學習算法的有關參數均設為Weka的默認值.

實驗數據：為了全面驗證所提特征選擇算法的有效性，模擬實驗采用了5個來自UCI機器學習存儲庫大小不同的測試數據集，這些數據集經常用來比較機器學習領域中特征選擇算法的性能，表1給出了這些測試集的簡單概要描述.

表1 實驗測試數據集的概要描述Table 1 Summary description of theexperimental test data set

從表1可以看出，這些數據集來自不同的領域，如生物醫學、計算機科學、人文學等，包含了不同數量的樣本數據、特征和類別屬性，類別數對應著類別屬性的個數，它們在一定程度上能夠驗證特征選擇算法在不同條件下的性能.

4 實驗結果與分析

Naive Bayesian、SVM、1-Nearest Neighbor和C4.5決策樹，分別代表了4種不同類型的機器學習算法，能夠更全面地對特征選擇算法性能進行驗證.模擬實驗中選用了mRMR、ReliefF和IG 3種典型的特征選擇算法作為對比實驗，其中mRMR算法是被業界廣為稱贊的基于信息理論的特征選擇算法，具有很強的代表性；ReliefF是非常優秀的基于歐式距離的特征選擇算法，其Neighbors和Istances分別設為5和30；IG是被業界廣為稱贊的基于信息熵的特征選擇算法.Ave為特征選擇算法在數據集上的平均分類準確性.原始特征列表示的是學習算法在沒有使用特征選擇算法情況下的分類準確率.得到的實驗結果如表2～5.

表2 特征選擇算法在Naive Bayesian分類性能比較Table 2 Comparison of feature selection algorithms in naive bayesian classification %

表3 特征選擇算法在SVM分類性能比較Table 3 Comparison of feature selection algorithms in SVM classification performance %

表4 特征選擇算法在1-NN分類性能比較Table 4 Comparison of feature selection algorithms in 1-NN classification %

表5 特征選擇算法在C4.5決策樹分類性能比較Table 5 Comparison of feature selection algorithms in C4.5 decision tree classification %

從表2～5可以看出Bi-PSO算法在性能上占明顯優勢，如數據顯示，Bi-PSO算法在所有訓練樣本數據集上對應的不同分類器，其平均性能分別是81.80%、81.12%、81.24%、80.32%，Bi-PSO算法分類性能平均比Bi-LSTM提高2.225%，Bi-PSO算法計算代價也是在可接受范圍之內的.

為了驗證已選子集中單個特征的區分性能，在相同特征子集規模上進行了一組對比試驗，將4種特征選擇算法分別在Lymphography、Synthetic樣本數據集上依次獲取不同數量的特征，并使用5種分類器進行訓練測試，使用十折交叉驗證方式獲取分類模型在數據集上的分類性能，實驗結果如圖3.

圖3 在不同特征個數上分類性能的比較Fig.3 Comparison of classification performanceon different feature numbers

圖3中，X軸為特征子集的前k個特征，Y軸為該前k個特征在的學習算法下的平均分類準確度，可以看出，Bi-PSO在特征數較少的情況下都能表現出良好的分類精度，在選擇出少量特征之后每次所選的特征都會對已選的特征性能帶來提升.從Lymphography數據集實驗結果中可以看出，在特征數小于16的情況下Bi-PSO分類精度曲線均高于其他算法；從Synthetic數據集結果中可以看出，在特征數大于55的情況下，Bi-PSO的分類精度與其他算法結果幾乎重合，而對于具有60個原始特征的Synthetic數據集來說，55個特征已失去了特征選擇的意義.

5 結論

循環神經網絡越來越多地運用到自然語言處理中，但存在著模型規模龐大、需要海量的數據、學習效率低等問題，因此，提出了一種基于Bi-LSTM，采用粒子群算法的思想的方法，讓神經網絡能夠很好地學習到小樣本數據集的特征.該算法對于小樣本的特征選擇的學習起到了重要作用，不僅可以很好解決特征的泛化和小樣本的過擬合問題，同時也提高了網絡的學習效率，為小樣本問題的研究提供了一種新思路.

下一步的研究工作：(1)如何進一步優化算法以實現粒子群自適應多目標選擇；(2)如何在獲取最優特征子集的過程中，通過限定學習因子降低時間復雜度，更快的訓練得到慣性權重.

參考文獻(References)

[1] 王翔,胡學鋼.高維小樣本分類問題中特征選擇研究綜述[J].計算機應用,2017,37(9):2433-2438,2448.DOI:10.11772/j.issn.1001-9081.2017.09.2433.

WANG Xiang,HU Xuegang.Overview on feature selection in high-dimensional and small-sample-size classification[J].Journal of Computer Applications,2017,37(9):2433-2438,2448.DOI:10.11772/j.issn.1001-9081.2017.09.2433.(in Chinese)

[2] VAPNIK V. The nature of statistical learning theory[M]. Springer Science & Business Media, 2013:163-167.

[3] 寧永鵬.高維小樣本數據的特征選擇研究及其穩定性分析[D].廈門：廈門大學,2014.3

[4] STEPHAN N , NATALIE L , MARIANNE D . Building change detection from historical aerial photographs using dense image matching and object-based image analysis[J]. Remote Sensing, 2014, 6(9):8310-8336.DOI:10.3390/rs6098310.

[5] VINYALS O,BLUNDELL C,LILLICRAP T,et al.Matching networks for one shot learning[C]//Proceedings of the 30th International Conference on Neural Information Processing Systems.Barcelona:NIPS: 2016：3637-3645.

[6] 柳青林.基于小樣本學習的目標匹配研究[D].西安：西安電子科技大學,2018:17-38

[7] BROMLEY J,GUYON I,LECUN Y,et al. Signature verification using a "SIAMESE" time delay neural network [J].International Journal of Pattern Recognition & Artificial Intelligence, 1993,7(4).669-688.DOI:10.1142/S0218001493000339.

[8] LUO Xiong,CHEN Yi,SHEN Feng. Text classification dimension reduction algorithm for Chinese web page based on deep learning [C]// International Conference on Cyberspace Technology.Beijing, China: IET, 2014:451-456.DOI:10.1049/cp.2013.2171.

[9] LüDERS B, SCHLGER M, KORACH A, et al. Continual and one-shot learning through neural networks with dynamic external memory[C]// European Conference on the Applications of Evolutionary Computation. Springer, Cham, 2017:886-901.DOI:10.1007/978-3-319-55849-3_57.

[10] 鮑捷,楊明,劉會東.高維數據的1-范數支持向量機集成特征選擇[J].計算機科學與探索,2012,6(10):948-953.DOI:10.3778/j.issn.1673-9418.2012.10.010.

BAO Jie,YANG Ming,LIU Huidong.Ensemble feature selection based on 1-norm support vector machine for high-dimensional data[J].Journal of Frontiers of Computer Science and Technology,2012,6(10):948-953. DOI:10.3778/j.issn.1673-9418.2012.10.010.(in Chinese)

[11] 張恒敏,楊健,鄭瑋.低秩矩陣近似與優化問題研究進展[J].模式識別與人工智能,2018,31(1):23-36.DOI:10.16451/j.cnki.issn1003-6059.201801003.

ZHANG Hengmin,YANG Jian,ZHENG Wei.Research progress of low-rank matrix approximation and optimization problem [J].Pattern Recognition and Artificial Intelligence,2018,31(1):23-36. DOI:10.16451/j.cnki.issn1003-6059.201801003.(in Chinese)

[12] LEI Haijun,HAN Tao,ZHOU Feng,et al. A deeply supervised residual network for hep-2 cell classification via cross-modal transfer learning[J]. Pattern Recognition the Journal of the Pattern Recognition Society,2018,79:290-302.DOI:10.1016/j.patcog.2018.02.006.

[13] 孫鑫.機器學習中特征選問題研究[D].長春：吉林大學,2013:25-24

[14] 童憶瑩.基于增量聚類和ReliefF的特征選擇方法[D].重慶：西南大學,2011:23-29.

[15] SHEN F,LUO X,CHEN Y.Text classification dimension reduction algorithm for Chinese web page based on deep learning[C]//International Conference on CyberspaceTechnology.IET, 2014:451-456.

[16] LOGANINA V, MAKAROVA L V, TARASOV R V, et al.The composition cement binder with the use of the synthesized aluminosilicates[J]. Advanced Materials Research, 2014,1022:3-6.DOI:10.4028/www.scientific.net/AMR.1022.3.

[17] TAN M, WANG L, TSANG I W. Learning sparse SVM for feature selection on very high dimensional datasets[C]// International Conference on International Conference on Machine Learning. Haifa, Israel:ICML,2010:1047-1054.

[18] 徐帥.基于統計學的大數據特征分析研究[D].北京：北京郵電大學, 2018:27-36,

[19] 崔鴻雁,徐帥,張利鋒.機器學習中的特征選擇方法研究及展望[J].北京郵電大學學報,2018,41(1):1-12.DOI:10.13190/j.jbupt.2017-150.

CUI Hongyan,XU Shuai,ZHANG Lifeng.The key techniques and future vision of feature selection in machine learning[J].Journal of Beijing University of Posts and Telecommunications,2018,41(1):1-12.DOI:10.13190/j.jbupt.2017-150.(in Chinese)

[20] 徐鶴鳴.多目標粒子群優化算法的研究[D].上海：上海交通大學, 2013:17-22.