鄧秀勤，李文洲，武繼剛，劉太亨

(1．廣東工業(yè)大學(xué) 應(yīng)用數(shù)學(xué)學(xué)院，廣州510006; 2．廣東工業(yè)大學(xué) 計算機(jī)學(xué)院，廣州510006)(*通信作者電子郵箱xiuqindeng@163．com)

0 引言

特征選擇也叫特征子集選擇，是指從已有的特征中選擇出一些有效特征以降低數(shù)據(jù)集維度的過程，是提高學(xué)習(xí)算法性能的一個重要手段，也是模式識別中關(guān)鍵的數(shù)據(jù)預(yù)處理步驟。在分類過程中，數(shù)據(jù)集往往包含大量的特征，但是并不是所有的特征對于分類都是有用的，其中很多無關(guān)和冗余的特征會導(dǎo)致分類效果不佳，同時導(dǎo)致維數(shù)的復(fù)雜性［1］，特征選擇是解決數(shù)據(jù)冗余和不相關(guān)的一種非常有效的方法。

特征選擇的任務(wù)是從一組N個特征中按一定的選擇標(biāo)準(zhǔn)選擇出一組由n(n＜N)個特征組成的特征子集，這個子集具有比特征全集更好的或一樣的分類功能。這實際是一個組合優(yōu)化的問題，且已被證明是非確定性多項式(Non-Deterministic Polynomial，NP)完全問題［2］，所以最優(yōu)特征子集的選擇很重要。特征選擇算法從模型上可分為Filter(濾波)模型和Wrapper(封裝)模型［3］。一般來說Filter模型的效率高，但效果差;Wrapper模型的效率低，但效果好［4］。為了解決這兩種模型存在的問題，文獻(xiàn)［5］提出了結(jié)合Filter模型和Wrapper模型的混合模型，在性能上有一定的提高。Hualonga等［6］提出一種混合特征選擇算法，將ReliefF算法與Shapley值結(jié)合，通過Shapley值選擇貢獻(xiàn)最高的相關(guān)特征，然后運用遺傳算法進(jìn)行特征子集選擇。由 Sasikala等［7］所提出的SVEGA(Shapley Value Embedded Genetic Algorithm)特征選擇算法，將遺傳算法與Shapley值結(jié)合，同時通過增l減r法進(jìn)行特征子集搜索以降低維度;對于同樣的中小型數(shù)據(jù)，SVEGA與 Hualonga等［6］、Tan 等［8］、Kannan 等［9］所提出的算法都進(jìn)行了比較，并且算法表現(xiàn)優(yōu)異。PSO-LSSU(Particle Swarm Optimization with Local Search using Symmetric Uncertainty)算法［10］是一種使用基于對稱不確定性的局部搜索方法改進(jìn)粒子群優(yōu)化(Particle Swarm Optimization，PSO)的特征選擇算法，對于同樣的8個高維數(shù)據(jù)集，它與 PSO-LS(PSO with Random Local Research)、PSO-LSRG(PSO with Random Local Research and Resetting Gbest)算法［11］進(jìn)行比較并得到了更好的訓(xùn)練結(jié)果。

文獻(xiàn)［12］經(jīng)過對醫(yī)療數(shù)據(jù)集特征選擇方法的研究，得出大多數(shù)現(xiàn)有方法存在以下問題:1)由于搜索方法的復(fù)雜性而導(dǎo)致迭代數(shù)過大;2)這些方法沒有考慮所選的特征子集中的特征之間的相互作用;3)產(chǎn)生最佳分類精度的方法采用的特征子集的特征較多，導(dǎo)致相應(yīng)的分類器需要更多的運行時間;相反，輸出最少數(shù)量特征的方法卻存在較差的分類精度。因此在實現(xiàn)最佳分類精度的同時盡可能減少特征數(shù)量，依然是個難題。文獻(xiàn)［13］提出對于醫(yī)療數(shù)據(jù)集，PSO算法與支持向量機(jī)(Support Vector Machine，SVM)分類器的組合在分類精度和性能上更優(yōu)于其他啟發(fā)式算法與其他分類器的組合。

為了在減少特征數(shù)量的同時盡可能地實現(xiàn)最佳分類精度，本文提出一種融合 Shapley值和粒子群優(yōu)化(Shapley Value and Particle Swarm Optimization，SVPSO)算法的混合特征選擇算法，將PSO算法與博弈論的Shapley值結(jié)合，通過計算特征的Shapley值，在特征子集的局部搜索中去除冗余和不相關(guān)特征得出表現(xiàn)最為優(yōu)異的特征子集，再運用SVM分類器進(jìn)行分類以達(dá)到在減少特征數(shù)的同時提高分類精度的目的。

1 粒子群優(yōu)化算法

PSO算法是一種全局隨機(jī)優(yōu)化算法。在PSO算法中，每個粒子代表一個解，每一次迭代，粒子通過跟蹤兩個“極值”更新自己:一個是粒子本身所找到的最優(yōu)解，稱為個體極值pbest;另一個極值是整個種群目前找到的最優(yōu)解，稱為全局極值gbest。每個粒子根據(jù)如下公式更新自己的速度和位置［14］:

很多學(xué)者提出了基于PSO算法的特征選擇方法［10－11］，不少方法致力于減少所選擇的特征數(shù)量，其中包括使用濾波模型以減少特征數(shù)量的方法。比如文獻(xiàn)［15］運用互信息評估特征之間的相關(guān)性和冗余度，從而過濾掉全局極值gbest中的冗余特征，實驗結(jié)果表明，相比以往的基于改進(jìn)后的PSO算法的特征選擇方法，所提方法在分類問題中表現(xiàn)更加優(yōu)異，而文獻(xiàn)［10］指出對于一些可能存在數(shù)千個不相關(guān)或冗余特征的數(shù)據(jù)集而言，文獻(xiàn)［15］方法不好確定全局極值gbest中該過濾掉的特征數(shù)量，因此本文提出運用Shapley值對PSO算法進(jìn)行局部搜索的特征選擇方法。

2 特征選擇中的Shapley值

Shapley值法是一種解決n個人合作對策問題的數(shù)學(xué)方法，合作中的每個人所得都與自己的貢獻(xiàn)相等，是一種分配方式，普遍用于經(jīng)濟(jì)活動中的利益合理分配等問題。因此Shapley值法在特征選擇中可用于計算特征子集中的每個特征的貢獻(xiàn)值［16－17］。

設(shè)集合N={1，2，…，n}，如果對于N的任一子集S(對應(yīng)n個人集合中的任一組合，即SN)都對應(yīng)著一個實值函數(shù)v(S)，v(S)表示子集S中每個人的貢獻(xiàn)值的總和。v(S)若滿足以下兩個條件:

2)兩個不相交的子集的并集的實值函數(shù)大于等于這兩個子集的實值函數(shù)的和:

v(Si∪ Sj) ≥ v(Si)+v(Sj)，Si∩ Sj=，Si、SjN，則稱［N，v］為多人合作對策，v為對策的特征函數(shù)。

Shapley值定義如下:在特征選擇中，將特征集合中的特征視為合作對策中的人，特征子集S的特征函數(shù)v(S)由子集S對分類器的性能的貢獻(xiàn)度來表示，因此，特征i在特征子集S中對分類精度的邊際貢獻(xiàn)度為:

那么特征i的Shapley值為:

其中:Π是n!個特征子集的集合，Si(π)是Π中所有包含特征i的特征子集。

3 融合Shapley值和粒子群的特征選擇

3．1 適應(yīng)度函數(shù)

特征選擇是一個典型的組合優(yōu)化問題，將二進(jìn)制PSO算法用于特征選擇時，每個粒子代表一個特征子集，如果某一特征位被選中，對應(yīng)的二進(jìn)制位為1，否則對應(yīng)位為0。特征選擇的目的是以較少的特征數(shù)實現(xiàn)更高的分類準(zhǔn)確率，因此適應(yīng)度函數(shù)包含著分類準(zhǔn)確率和子集大小兩項指標(biāo)。如果一個粒子既能夠使分類器獲得的分類精度越高，同時又使選擇的特征數(shù)目越少，那么它的適應(yīng)度值必定越高。而且，如果兩個粒子取得的準(zhǔn)確率相同，則特征數(shù)目少的粒子適應(yīng)度值較高。因此定義適應(yīng)度函數(shù)為:

其中，accuracy(xi)是子集xi在SVM分類器上的預(yù)測精度，SVM分類過程的一般步驟為劃分訓(xùn)練集和測試集、數(shù)據(jù)預(yù)處理(特征選擇)、訓(xùn)練SVM(訓(xùn)練集)、預(yù)測(測試集);nfeature(xi)代表特征子集的大小，即子集中1的個數(shù);A為控制分類精度和特征數(shù)目對適應(yīng)度函數(shù)的影響的因子，取值范圍為［0，1］。T為迭代次數(shù)，在實驗中T=50;t為當(dāng)前迭代次數(shù)。在封裝模式中，適應(yīng)度函數(shù)用于評價特征子集的好壞，數(shù)據(jù)分類的準(zhǔn)確率在適應(yīng)度函數(shù)中應(yīng)該起到主導(dǎo)作用。因此在實驗中，隨著迭代次數(shù)的增加，A將逐漸增大，當(dāng)?shù)鷶?shù)到達(dá)10次以后，A的取值固定為0．8。

3．2 基于Shapley值的局部搜索

局部搜索的目的是通過從當(dāng)前的特征子集中刪除一定數(shù)量的冗余特征找到更好的特征子集。在每次迭代中，根據(jù)式(5)計算粒子的適應(yīng)值并根據(jù)適應(yīng)值更新粒子的個體極值pbest。在粒子的局部搜索中，根據(jù)式(4)計算粒子中對應(yīng)二進(jìn)制位為1的每個特征的Shapley值并根據(jù)Shapley值對特征進(jìn)行排序，去掉對分類問題貢獻(xiàn)最低的特征，即將該特征的二進(jìn)制位由1改為0，得到新的粒子，計算其分類精度，若分類精度高于原粒子的分類精度，則用該粒子取代原粒子后繼續(xù)去掉Shalpey值最低的特征，以此類推，直到得到的新粒子的分類精度低于原粒子的分類精度為止則停止更新。計算最后得到的粒子的適應(yīng)度值，若其適應(yīng)值比個體極值pbest的適應(yīng)度值高則更新pbest。

基于Shapley值的特征子集局部搜索算法流程如下:

步驟1 輸入粒子(特征子集)，計算每個特征的Shapley值并排序;

步驟2 逐個去掉粒子中Shapley值最低的特征，并計算其分類精度;

步驟3 直到分類精度不再提高，更新粒子并輸出。

所有粒子經(jīng)過局部搜索后，得到全局極值gbest，根據(jù)式(1)、(2)對所有粒子的速度和位置進(jìn)行更新，然后進(jìn)入下一次迭代，直到達(dá)到最大迭代次數(shù)停止循環(huán)并輸出最后的全局極值 gbest。

3．3 SVPSO算法描述

輸入:粒子數(shù)M，迭代次數(shù)T;

輸出:特征子集。

1)初始化:隨機(jī)生成M個具有m個特征的粒子，每個粒子的每位

上的值為0或1;

2)while達(dá)到最大迭代次數(shù)時停止循環(huán)do

for i=1 to M do

計算每個粒子的適應(yīng)值f(xi);

if f(xi)＞f(xpbest)then

更新pbest;

end

3)運用Shapley值對粒子xi進(jìn)行局部搜索得到xi'，并計算其分類

精度acc(xi')

if acc(xi')＞acc(xi)then

更新xi;

end

if f(xi')＞f(xpbest)then

更新pbest;

end

end

4)更新gbest;

for i=1 to M do

根據(jù)式(1)更新粒子i的速度;

根據(jù)式(2)更新粒子i的位置;

end

end

4 仿真實驗與結(jié)果分析

本文使用了17個具有不同特征數(shù)量的數(shù)據(jù)集來做實驗，這些數(shù)據(jù)集來源于UCI機(jī)器學(xué)習(xí)數(shù)據(jù)集［18］和基因表達(dá)數(shù)據(jù)集［19］。這些用于測試的生物醫(yī)學(xué)數(shù)據(jù)集依據(jù)特征數(shù)量可分為小型數(shù)據(jù)集(2～30個特征)、中型數(shù)據(jù)集(31～1 000個特征)和大型數(shù)據(jù)集(超過1 000個特征)。數(shù)據(jù)集的相關(guān)信息如表1和表2的第1列所示。

表1 中小型數(shù)據(jù)集中不同算法得到的特征子集規(guī)模和分類準(zhǔn)確率Tab．1 Feature subset size and classification accuracy obtained by different algorithms in small and medium-sized datasets

為了測試本文提出的SVPSO算法的性能，本文使用10折交叉驗證，對上面的每個數(shù)據(jù)集運行了50次，數(shù)據(jù)集隨機(jī)分為訓(xùn)練集和測試集，在保證分類精度的情況下選擇特征數(shù)最少的特征子集。對于所有數(shù)據(jù)集，都將先進(jìn)行沒有經(jīng)過特征選擇的分類實驗，所得的分類精度將與經(jīng)過SVPSO算法進(jìn)行特征選擇后的實驗的分類精度比較。除此之外，SVPSO算法還都將與傳統(tǒng)的PSO算法進(jìn)行比較，而對于小型和中型數(shù)據(jù)集，SVPSO算法將與 SVEGA［7］進(jìn)行比較。對于大型數(shù)據(jù)集，SVPSO算法將與PSO-LSSSU算法［10］進(jìn)行比較。具體實驗結(jié)果分別列于表1和表2(“無”表示數(shù)據(jù)集沒有經(jīng)過特征選擇，直接用于分類實驗)。

對于中小型數(shù)據(jù)集，表1的實驗結(jié)果表明，將沒有經(jīng)過特征選擇的數(shù)據(jù)集直接進(jìn)行分類實驗所得到的分類準(zhǔn)確率普遍偏低，由此可見數(shù)據(jù)集中存在著大量不相關(guān)特征或冗余特征，而經(jīng)過SVPSO算法進(jìn)行特征選擇后，所選擇的特征數(shù)量比原數(shù)據(jù)集減少了55%以上，并且所減少的特征數(shù)量也隨著原有的特征數(shù)量的增加而增加，尤其是中型數(shù)據(jù)集，所選擇的特征數(shù)量更是減少了80%以上。根據(jù)所選擇的特征進(jìn)行分類實驗所得的分類準(zhǔn)確率提高了9～23個百分點。而與傳統(tǒng)的PSO算法相比，與Shapley值結(jié)合后，在所實驗的數(shù)據(jù)集中，SVPSO算法所選擇的特征數(shù)都比PSO算法的要少，尤其在數(shù)據(jù)集 Post operative patient、Lung cancer、Cardiac arrhythmia 中，最高能減少78%。在分類精度方面，在大部分的數(shù)據(jù)集中，SVPSO算法所選擇的特征子集的分類精度都要比PSO算法的高2～13個百分點。雖然在少數(shù)數(shù)據(jù)集中，比如Dermatology和Lung cancer，所得到的分類精度沒有PSO算法高，但是依然可以在保持分類精度不會太差的情況下大幅降低特征個數(shù)。由此表明，運用Shapley值對PSO算法進(jìn)行局部搜索可以有效消除冗余特征，從而可以發(fā)現(xiàn)具有更好辨別力的更小的特征子集。而在與SVEGA的對比中可以發(fā)現(xiàn)，除了第一個數(shù)據(jù)集Liver disorder的實驗結(jié)果沒有SVEGA的好，在其他數(shù)據(jù)集中所選出的特征子集不僅數(shù)量要比SVEGA的少25%～50%，分類精度也會差不多或者更高，最高能增加10個百分點。由此可見，Shapley值與PSO算法的結(jié)合在醫(yī)療數(shù)據(jù)集中要比與遺傳算法的結(jié)合表現(xiàn)更加優(yōu)異。

對于大型數(shù)據(jù)集，表2的實驗結(jié)果表明，在經(jīng)過SVPSO算法的特征選擇后，大部分?jǐn)?shù)據(jù)集的特征數(shù)量都能減少2個數(shù)量級，在數(shù)據(jù)集Leukemia1和Leukemia2中甚至能減少3個數(shù)量級，由此可見在大型數(shù)據(jù)集中，SVPSO算法是能夠有效減少特征數(shù)量的。而在減少大量特征的同時，所選特征的分類準(zhǔn)確率仍然能夠提高2～22個百分點。與傳統(tǒng)的PSO算法相比，融合了Shapley值的SVPSO所選擇的特征子集的特征數(shù)也能比PSO算法所選的特征數(shù)低1或2個數(shù)量級，在數(shù)據(jù)集Leukemia1中更是能減少3個數(shù)量級，與此同時在分類精度上也能提高1～9個百分點。而與表現(xiàn)同樣更加優(yōu)異的PSO-LSSU算法相比，可以發(fā)現(xiàn)SVPSO算法在數(shù)據(jù)集9Tumor和Prostate中無論是特征數(shù)量還是分類精度都能優(yōu)于PSOLSSU算法;而在數(shù)據(jù)集SRBCT、Brain Tumor 1和 Leukemia1中，SVPSO算法選擇的特征子集也能在保持分類精度和PSOLSSU算法所選子集的分類精度差不多的情況下大幅減少特征子集的特征個數(shù);在其他數(shù)據(jù)集中，SVPSO算法所選擇的特征子集要么就是在特征數(shù)量上少于PSO-LSSU算法，要么就是在分類精度上高于PSO-LSSU算法。因此，從整體上來看SVPSO算法的表現(xiàn)比PSO-LSSU算法更優(yōu)異。

5 結(jié)語

為了在減少特征數(shù)量的同時盡可能地實現(xiàn)最佳分類精度，本文融合Shapley值與PSO算法，提出一種新的混合特征選擇算法，并對17個具有不同特征數(shù)量的醫(yī)療數(shù)據(jù)集進(jìn)行分類實驗，通過計算特征子集中每個特征的Shapley值，從而在特征子集的局部搜索中刪除掉冗余特征，使得算法所選擇的特征子集的特征數(shù)量達(dá)到最小的同時保持一定的分類精度。仿真實驗結(jié)果表明，無論是中小型的數(shù)據(jù)集還是大型的數(shù)據(jù)集，本文SVPSO算法所選擇的特征子集在特征數(shù)量和分類精度上都能表現(xiàn)優(yōu)異，不僅能刪除數(shù)據(jù)集中55%以上不相關(guān)的或冗余的特征，尤其對于中大型數(shù)據(jù)集更能刪減80%以上，還能將分類準(zhǔn)確率提高2～23個百分點。

表2 大型數(shù)據(jù)集中不同算法得到的特征子集規(guī)模和分類準(zhǔn)確率Tab．2 Feature subset size and classification accuracy obtained by different algorithms in big-sized datasets