吳辰文，紀海斌

(蘭州交通大學 電子與信息工程學院,甘肅 蘭州 730070)

隨著基因芯片技術的發(fā)展,研究人員能夠快速、方便地獲取大量基因微陣列數(shù)據(jù),這些數(shù)據(jù)為疾病在分子水平上的診斷和分析提供了可能?；蛭㈥嚵袛?shù)據(jù)屬于典型的高維度數(shù)據(jù),其中存在著大量與疾病診斷無關、噪聲的基因,如何從中挖掘有價值的基因已成為對微陣列數(shù)據(jù)有效利用的關鍵所在[1-2]。分類是對微陣列數(shù)據(jù)最廣泛的應用,然而微陣列數(shù)據(jù)具有維度高、樣本少的特點,易引發(fā)維度災難問題,對基因數(shù)據(jù)分類造成了巨大的阻礙。為解決這些問題,通常采取特征選擇技術對數(shù)據(jù)進行約簡,特征選擇不僅能夠篩選出對分類有利的基因子集,而且能夠有效提高機器學習算法的性能和分類精度,但已知從大量特征中選擇最優(yōu)的相關特征子集是一個NP難題,為此,本文提出一種混合特征選擇算法來有效選擇相關的特征子集。

特征選擇是指從已有的特征子集中選擇更具有代表性的特征構成新的特征子集,所選特征子集相對原有子集更具代表性且具有更好的分類性能[3]。特征選擇方法按照評價策略可以分為兩類: 過濾式算法(filter)和封裝式算法(wrapper)。過濾式算法不依賴于后續(xù)分類模型,通過觀察數(shù)據(jù)集內(nèi)在統(tǒng)計屬性建立特征評分,根據(jù)排序準則函數(shù)選擇得分較高的特征,該類算法簡單、高效,但準確率不高。常見的過濾式算法有信息增[4]、ReliefF[5]、mRMR算法[6]、Fisher-Score[7]、基于相關的快速濾波算法(FCBF)[8]等。封裝式算法則依賴于后續(xù)分類模型的分類準確度作為特征子集的評價指標,該類算法可以提供更好的準確性,但計算開銷大。常見的封裝式算法有SFS、SBS、PSO[9]、GA[10]等。

微陣列數(shù)據(jù)具有較高的維度,僅采用過濾式或封裝式的特征選擇算法難以獲得最佳效果。對于高維數(shù)據(jù)的特征選擇,有學者結合過濾式算法和封裝式算法各自的優(yōu)勢,提出Filter-Wrapper混合特征選擇方法[11],這類方法先利用Filter算法對特征集進行預選,過濾掉相關性小的特征,再利用Wrapper算法對預選特征集進行精選,能夠更好地平衡分類精度和計算效率。

近年來,群體智能算法在解決特征選擇問題方面被廣泛應用,這類算法采用隨機搜索的方式對特征進行組合優(yōu)化,屬于Wrapper算法。由于腫瘤基因數(shù)據(jù)是高維度數(shù)據(jù),存在大量無關、冗余基因,單純使用群體智能算法進行特征搜索難以達到理想的效果,基于過濾式算法和群體智能封裝式算法的混合方法能夠在分類精度和計算效率方面互補,在處理高維基因特征選擇上具有較大的優(yōu)勢。例如,Akadi等使用混合mRMR和GA的兩階段算法對基因數(shù)據(jù)進行特征選擇,并使用SVM和貝葉斯分類器進行驗證,實驗取得了良好的結果[12];Dashtban等使用Fisher評分產(chǎn)生高統(tǒng)計相關的基因特征子集,然后采用改進的多目標蝙蝠算法進一步尋優(yōu),使用4種分類器和留一交叉法進行驗證,實驗結果表明該方法的優(yōu)越性[13]；葉超超等提出一種結合Relief-F和決策樹的自適應粒子群優(yōu)化算法(R-C-APSO),該算法不但具有較高的分類精度、較快的基因選擇速度,而且具有良好的穩(wěn)定性[14]。

磷蝦群算法(KH)[15]是由Gandomi和Alavi提出的一種元啟發(fā)式群體智能算法,該算法模擬了磷蝦群體對特定危險和環(huán)境做出響應并逐漸提高種群密度的過程,相比其他群體智能算法,該算法具有更好的全局搜索能力,已被成功應用于參數(shù)估計、模型優(yōu)化和分配調度等多種優(yōu)化問題上。與其他群體智能算法一樣,受到大量無關、冗余特征的影響,在高維數(shù)據(jù)上直接使用磷蝦群算法進行特征選擇存在計算效率低、效果差的問題。最小冗余最大相關算法(mRMR)[6]是一種非常有效的過濾式特征選擇方法,但與其他過濾式算法不同的是,該算法能在篩選出與分類變量最相關特征的同時，使特征間的的差異最大化,但其獲得的特征組合仍不能達到最佳效果。

腫瘤基因高維數(shù)據(jù)中存在大量不相關和冗余的特征,而與腫瘤類型識別相關的特征僅有很少的一部分,且難以通過窮盡所有特征組合的方式獲取最優(yōu)特征子集,因此,為了從腫瘤基因數(shù)據(jù)中獲取與腫瘤分類相關的、且特征數(shù)量盡可能少的特征子集,本文利用mRMR算法具有能夠過濾掉大量無關、冗余特征的特點,并結合磷蝦群算法具有較強的全局搜索能力的優(yōu)勢,提出一種基于mRMR和磷蝦群算法的腫瘤基因兩階段混合特征選擇方法。此外,為了使磷蝦群算法能夠處理特征選擇問題,使用編碼轉換原理對其進行離散化，并為了進一步提高磷蝦群算法的全局搜索能力,采用了步長非線性遞減和精英粒子局部搜索對其進行了改進。最后,通過多個腫瘤基因數(shù)據(jù)集對本文算法的效果進行驗證,實驗表明，本文算法在特征選擇數(shù)量和分類精度方面具有優(yōu)勢。

1 相關算法

1.1 mRMR算法

最小冗余最大相關(mRMR)方法是一種過濾式的特征選擇算法,其評價函數(shù)同時考慮了特征與類別、特征與特征之間的相關性,能夠篩選出的特征子集同時具有最大相關性和最小冗余性。該算法采用互信息度量變量之間的相關性,兩個變量的互信息表示為

(1)

其中：X和Y為兩個特征變量；p(x)和p(y)為相應變量的邊際概率函數(shù)；p(x,y)為聯(lián)合概率分布。

給定候選特征子集,特征與類別間的最大相關、特征與特征間的最小冗余的度量分別為

(2)

(3)

其中,S為特征集合;fi為第i個特征；c為目標類別;I(fi,c)為特征i和目標類別c之間的互信息;I(fi,fj)為特征i與特征j之間的互信息。

考慮所選特征子集的相關性和冗余性,將式(2)與式(3)組合,得到mRMR特征選擇算法的評價函數(shù)為

maxJ(D,R),J=D-R。

(4)

上述方程可通過逐漸增加單個變量來求解,假設集合S為全部特征集,St-1為已經(jīng)選出的具有t-1個特征的特征集,則下一步任務就是從集合S-St-1中選擇第t個特征，使上式最大化,也即通過式(5)最大化單變量相關性和冗余度的差值來確定添加的第t個特征。

(5)

1.2 磷蝦群算法

磷蝦群算法是一種仿生群體智能的優(yōu)化算法,主要模仿了南極磷蝦群在生存環(huán)境中不斷提高群體密度,且逐漸聚集在高密度的食物區(qū)域的行為。磷蝦個體會隨著時間運動，且運動方向受周圍磷蝦的誘導、覓食活動、隨機擴散3個因素共同影響,其位置更新方式為

xi(t+Δt)=xi(t)+Δt(Ni+Fi+Di)，

(6)

(7)

其中：Ni、Fi、Di分別代表磷蝦個體的誘導運動、覓食運動、隨機擴散運動;Ct為步長縮放因子;d表示總的變量數(shù);Uj、Lj表示第j個變量的上界和下界。

誘導運動是磷蝦個體受到最優(yōu)個體和鄰近個體的影響而產(chǎn)生的運動,表示為

Ni=Nmaxαi+wnNi,old。

(8)

其中：Nmax表示最大誘導速度;wn表示誘導權重;αi表示誘導方向。

覓食運動是磷蝦個體朝著食物位置和自身的歷史最優(yōu)位置的方向移動,表示為

Fi=Fmaxβi+wfFi,old。

(9)

其中：Fmax為最大覓食速度;wf為覓食權重;βi為覓食方向。

隨機擴散運動會增加磷蝦個體運動的不確定性,表示為

(10)

其中：Dmax表示最大隨機擴散速度；δ表示隨機擴散方向。

此外,受差分進化算法啟發(fā),為了進一步提高算法的搜索能力,原算法中引入了交叉、變異遺傳算子,分別表示如下:

(11)

(12)

其中：xgbest為全局最優(yōu)個體；xp、xq、xr為隨機挑選個體；m為維度；Cr為交叉概率，Cr=0.2Fiti,gbest，F(xiàn)iti,gbest為個體xi與xgbest適應度差值的絕對值；Mu為變異概率，Mu=0.05Fiti,gbest；rand為[0,1]上均勻分布的隨機數(shù);0≤μ≤1。

2 基于mRMR和IKH的特征選擇方法

對于腫瘤基因高維數(shù)據(jù),使用基于過濾式和封裝式的混合算法,能夠充分利用過濾式和封裝式算法各自的優(yōu)勢,選擇出更有效的特征子集。為此,本文提出了結合mRMR和磷蝦群的混合特征選擇算法,用于處理腫瘤基因數(shù)據(jù)的高維特征選擇問題。同時,針對原始磷蝦群算法不能直接用于處理離散特征選擇的問題,本文使用編碼轉換原理對其進行離散化處理;針對磷蝦群算法存在不能平衡前期勘探和后期開發(fā)能力、局部搜索能力較弱的問題,本文引入步長調整、精英粒子局部搜索對其進行改進。此外,使用磷蝦群算法特征選擇時,需要合理設置適應度函數(shù),適應度函數(shù)通常要綜合考慮分類精度和特征數(shù)量。

2.1 磷蝦群算法的離散化方法

為了使磷蝦群算法能夠處理特征選擇問題,需要將磷蝦個體的連續(xù)位置轉化為二進制位置,每個二進制位置被用于表示特征是否被選擇。本文使用編碼轉換策略[16-17],即每個磷蝦個體有其對應的連續(xù)位置和二進制位置,磷蝦個體在連續(xù)空間中運動,每個連續(xù)位置通過編碼轉換得到對應的離散二進制表示。磷蝦個體的二進制轉換表示為

(13)

其中:xij表示磷蝦個體xi第j維的實值位置,xij取值為[-1,1];yij為對應磷蝦個體yi第j維的二進制位置,yij∈{0,1}。

2.2 步長非線性遞減

在磷蝦群算法中，步長Δt可通過步長縮放因子Ct調節(jié),而Ct在原文中被認為是應該根據(jù)具體問題仔細設置的參數(shù),較小的Ct有利于進行精細搜索,較大的Ct有利于進行更大范圍探索,而群體智能算法通常在前期應該進行更廣泛的勘探,后期進行更局部的開發(fā)。但在原算法中，Ct被設置為常數(shù),在優(yōu)化過程中不利于勘探和開發(fā)。為了使整個迭代過程中前期勘探和后期開發(fā)平衡,本文采用指數(shù)非線性遞減[18]對縮放因子進行調節(jié),能夠使整個優(yōu)化過程前期具有較大步長,有利于勘探,后期具有較小步長,有利于局部開發(fā),表示為

Ct＿min。

(14)

其中：Ct＿max和Ct＿min分別為Ct的最大值和最小值；tmax為最大迭代次數(shù)；t為當前迭代次數(shù)；τ為調節(jié)參數(shù)。

2.3 精英Fuch混沌變異優(yōu)化

在磷蝦群算法中,精英群體具有較高的適應度,能夠有較大的概率接近全局最優(yōu)解,對精英空間的有效探索能夠進一步提高算法的搜索能力。混沌搜索具有遍歷性、隨機性,利用混沌對個體變異,能夠提高粒子的多樣性。為了進一步提高磷蝦群算法的全局搜索能力,本文采用精英混沌變異對精英空間進行局部搜索,通過對精英空間的局部搜索提高算法的全局搜索能力。

在混沌映射中,Fuch混沌映射[19]相比Logistic和Tent混沌映射具有更大的混沌性,任何微小的初始差異都會造成結果很大的不同。因此,本文采用Fuch混沌映射在精英空間生成一個與本體完全不同的變異個體,Fuch混沌映射公式為

(15)

其中：k為迭代次數(shù)；zk取值為[-1,1]。

(16)

(17)

2.4 適應度函數(shù)

在進行特征子集評價時應該充分考慮分類精度和特征數(shù)量,即所選特征數(shù)量要盡可能少,得到的分類準確度要盡可能大[20],本文采用的適應度函數(shù)為

fitness=α·Acc+β·(1-S/T)。

(18)

其中：Acc為使用分類器分類得到的準確率；S為所選基因子集長度；T為總的基因子集長度；α和β分別為分類精度和特征子集長度重要程度,α+β=1。

2.5 mRMR-IKH算法過程

本文提出了mRMR-IKH混合特征選擇方法,該方法結合mRMR和改進的磷蝦群算法各自的優(yōu)勢,可用于高效處理高維數(shù)據(jù)特征選擇的問題。算法流程圖如圖1所示,具體過程如下。

圖1 mRMR-IKH算法流程圖Fig.1 Flow chart of mRMR-IKH algorithm

Step1使用mRMR算法對各個特征進行評價,選擇前S個特征為初選特征子集，并作為改進磷蝦群算法的輸入。

Step2種群初始化及參數(shù)設置,初始化磷蝦實數(shù)位置xi(i=1,2，…,n),設置當前迭代次數(shù)t=1、最大迭代次數(shù)tmax、最大誘導速度Nmax、最大覓食速度Vf、最大隨機擴散速度Dmax、誘導慣性權重wn、覓食慣性權重wf、最大步長縮放因子Ct＿max、最小縮放因子Ct＿min、指數(shù)調節(jié)系數(shù)τ、混沌變異概率R、精英個數(shù)m和混沌迭代次數(shù)k等。

Step3使用式(13)獲取每個磷蝦的離散化位置,根據(jù)式(16)計算磷蝦個體的適應度。

Step4根據(jù)式(8)～(10)分別計算磷蝦個體的誘導速度、覓食速度、隨機擴散速度。

Step5根據(jù)式(14)計算步長縮放因子,并更新每個磷蝦的運動速度和位置。

Step6根據(jù)式(11)和式(12)對每個磷蝦進行遺傳操作以增加種群的多樣性。

Step7計算迭代后磷蝦種群的適應度值,選取前m個最優(yōu)個體組成精英空間，根據(jù)式(15)對精英個體進行混沌變異,計算混沌個體的適應度,將其與原個體對比,保留更優(yōu)的個體。

Step8令t=t+1,判斷是否達到最大迭代次數(shù),是則結束,否則返回Step 4。

3 實驗結果與分析

3.1 實驗數(shù)據(jù)集

為了驗證mRMR-IKH混合特征選擇算法的有效性,本文選取6個公開的基因數(shù)據(jù)集進行實驗,分別是ColonTumor、Lung、Leukemia、Prostata、MLL、SRBCT,其中,數(shù)據(jù)均經(jīng)過最小最大歸一化處理,各基因數(shù)據(jù)集的詳情如表1 所示。

表1 腫瘤基因數(shù)據(jù)集Tab.1 Tumor gene data set

本次實驗環(huán)境為64 位Windows 7操作系統(tǒng),計算機處理器為i5-4590，3.3 GHz,內(nèi)存8 GB,代碼運行環(huán)境為Matlab 2016。實驗采用SVM作為分類器,以SVM五折交叉驗證的準確率和特征子集數(shù)量的加權和作為適應度函數(shù),每一個基因數(shù)據(jù)集均獨立進行10次實驗,以10次實驗結果的平均值作為最終結果。

3.2 實驗結果與分析

為了驗證mRMR-IKH算法的效果,將本文算法與其他算法進行對比實驗,包括mRMR、mRMR+KH、mRMR+BPSO、mRMR+BBA。其中,由mRMR算法選擇前100個特征作為初始特征,粒子數(shù)設置為50,迭代次數(shù)為300。

1)平均分類準確率和平均特征子集數(shù)量比較

為了比較本文算法的效果,采用10次獨立實驗平均后的分類準確率Acc和特征數(shù)量Fea作為比較對象,表2 給出了6個數(shù)據(jù)集使用5種算法運行得到的實驗結果,同時給出了Acc和Fea的對應的標準差Std。

表2 5種算法在6個數(shù)據(jù)集上的平均準確率和平均特征數(shù)量比較Tab.2 Comparison of average accuracy and average number of features of 5 algorithms on 6 data sets

從表2可知,與單獨使用mRMR算法相比,混合群體智能的算法普遍能夠得到較少的平均特征數(shù)量和較高的平均準確率,這說明使用mRMR算法特征約減能力是有限的,使用群體智能算法能夠對mRMR算法產(chǎn)生的特征子集進行進一步尋優(yōu),達到更好的效果。此外,與其他群體智能算法相比,在平均分類準確率方面,除Lung數(shù)據(jù)集外,本文算法均得到了最高平均分類準確率,而Lung數(shù)據(jù)集未能取得較高的分類準確率是由于Lung數(shù)據(jù)集是一個不平衡數(shù)據(jù)集,且在尋優(yōu)過程中對特征的過度約減容易造成分類準確率的降低。在特征選擇數(shù)量方面,本文算法均獲得了最少的平均特征數(shù)量,這是由于本文算法采用的精英粒子混沌搜索進一步對精英空間進行了開發(fā);從分類準確率和特征數(shù)量的標準差方面來看,本文算法相對其他算法具有良好的穩(wěn)定性。

2)平均適應度曲線比較

為了進一步證明本文方法的有效性,將IKH算法在平均適應度曲線與KH、BPSO、BBA算法進行比較,在實驗中分類準確率應具有較高的重要性,因此,在本文中α取0.9,β取0.1,實驗結果如圖2所示,其中橫坐標為迭代次數(shù),縱坐標為適應度。

圖2 4種算法在6個數(shù)據(jù)集上的平均適應度曲線比較Fig.2 Comparison of average fitness curves of 4 algorithms on 6 data sets

從圖2中可以看出,本文算法在各個數(shù)據(jù)集上均能夠得到最高的適應度,與BPSO和BBA傳統(tǒng)算法相比,IKH算法能夠對空間進一步開發(fā),具有較強的全局搜索能力;與原KH算法相比,IKH算法引入了步長非線性遞減和精英混沌搜索,通過對步長的調整平衡了前期的全局勘探和后期精細搜索的能力,通過精英混沌搜索增加了粒子多樣性。從適應度曲線可以看出,IKH算法在迭代過程中能夠進一步加強搜索,且具有較快的收斂速度。

綜上分析,本文提出的mRMR-IKH算法結合了mRMR算法和IKH算法的各自優(yōu)勢,在mRMR算法提取特征子集的基礎上進一步對特征約減,獲得更加約減的特征子集,且具有良好的分類能力,同時IKH算法與其他3種智能算法相比,IKH算法具有更好的搜索能力,且穩(wěn)定性較好。

4 結語

本文針對腫瘤基因高維數(shù)據(jù)集的特征選擇問題,提出了一種基于mRMR和改進磷蝦群(IKH)算法的混合特征選擇方法。該方法通過mRMR算法篩選出一定數(shù)量相關但不冗余的基因,達到初步降維的目的,然后，利用磷蝦群算法的尋優(yōu)能力提取分類能力更強、更加精簡的特征子集。本文使用編碼轉換原理將磷蝦群算法二進制化,并采用步長遞減和精英混沌變異進一步提高了其搜索能力。通過在6個基因數(shù)據(jù)集的實驗結果表明,本文方法在選擇的特征數(shù)量和分類準確度方面具有優(yōu)勢,是一種有效的腫瘤基因特征選擇方法。本文算法采用精英局部搜索優(yōu)化策略,時間復雜度有所增加,此外,參數(shù)需要人工調整,因此，下一步工作是研究如何通過設置粒子適應度停滯次數(shù)決定是否局部搜索以降低時間復雜度，并通過大量實驗確定最佳參數(shù)設置以對算法進一步優(yōu)化。