周金容 羅 建
1(南充職業(yè)技術(shù)學(xué)院電子信息工程系 四川 南充 637131) 2(西華師范大學(xué)計(jì)算機(jī)學(xué)院 四川 南充 637009)
在大數(shù)據(jù)時(shí)代,高維數(shù)據(jù)已擴(kuò)展到社交媒體、生物信息學(xué)、圖像處理和自然語(yǔ)言處理等不同領(lǐng)域[1-2]。計(jì)算負(fù)擔(dān)、過(guò)擬合和性能不佳是高維數(shù)據(jù)帶來(lái)的一些外在表現(xiàn)缺點(diǎn)[3]。在模式識(shí)別中,由于存在成千上萬(wàn)的特征,因此從高維數(shù)據(jù)中選擇特征子集仍然是一個(gè)挑戰(zhàn)[4],其中過(guò)濾掉無(wú)關(guān)和冗余的特征可以減少過(guò)度擬合,節(jié)省計(jì)算成本并提高分類(lèi)的準(zhǔn)確性。特征選擇算法是可以有效地將原始數(shù)據(jù)縮小到低維空間的算法。特征選擇是組合優(yōu)化問(wèn)題,在當(dāng)今許多科學(xué)領(lǐng)域中都是重要問(wèn)題。
特征選擇技術(shù)已成功應(yīng)用于各種人工智能領(lǐng)域,包括文本挖掘、圖像處理、生物信息學(xué),以及其他領(lǐng)域[5]。目前,研究人員已經(jīng)開(kāi)發(fā)了許多群體智能啟發(fā)優(yōu)化算法用于特征選擇。文獻(xiàn)[6]提出了一種基于多目標(biāo)粒子群優(yōu)化的特征選擇方法,該方法根據(jù)特征在存檔集中的頻率對(duì)其進(jìn)行排名,使用這些等級(jí)來(lái)優(yōu)化存檔集并引導(dǎo)粒子,消除了不相關(guān)、多余和嘈雜的特征,降低計(jì)算成本。文獻(xiàn)[7]提出了一種基于遺傳算法和禁忌搜索相結(jié)合的特征選擇方法,該方法通過(guò)定義一個(gè)過(guò)早收斂索引,以判斷遺傳算法過(guò)程中的收斂情況。當(dāng)確實(shí)發(fā)生早收斂時(shí),將執(zhí)行改進(jìn)的變異算子,對(duì)具有較高適應(yīng)性值的個(gè)體采用禁忌搜索算法。文獻(xiàn)[8]提出了一種基于烏鴉搜索的V形二值化包裝器,該包裝器利用二進(jìn)制烏鴉搜索算法簡(jiǎn)化了特征選擇模型和減少了分類(lèi)處理時(shí)間。文獻(xiàn)[9]為了處理高維低樣本數(shù)據(jù)中的冗余特征和不相關(guān)特征,提出了一種基于粒度信息的特征選擇算法模型,該模型利用改進(jìn)的具有特征粒度的二進(jìn)制遺傳算法來(lái)選擇優(yōu)化粒子集重要特征。文獻(xiàn)[10]設(shè)計(jì)一種基于粗糙集與人工蜂群算法的動(dòng)態(tài)數(shù)據(jù)流特征選擇算法,使用粗糙集定義數(shù)據(jù)流增量數(shù)據(jù)的適應(yīng)度函數(shù),利用人工蜂群算法從舊特征子集與增量數(shù)據(jù)提取新的全局特征子集,為了增強(qiáng)人工蜂群算法的魯棒性,通過(guò)降低人工蜂群算法過(guò)早收斂幾率來(lái)滿足動(dòng)態(tài)特征選擇算法的穩(wěn)定性需要。文獻(xiàn)[11]提出一種基于加權(quán)社區(qū)檢測(cè)與增強(qiáng)人工蟻群算法的高維數(shù)據(jù)特征選擇算法,通過(guò)設(shè)計(jì)加權(quán)社區(qū)檢測(cè)算法,將特征相似性作為社區(qū)劃分的模塊度,利用人工蟻群算法并行地處理每個(gè)特征分類(lèi),提取全局最優(yōu)的特征子集,從而提高了特征選擇的時(shí)間效率。
為了降低高維數(shù)據(jù)特征選擇的運(yùn)行時(shí)間和提高分類(lèi)精度,提出一種基于聚類(lèi)和二元螞蟻算法相結(jié)合的混合濾波器特征選擇方法,該方法通過(guò)線性二元螞蟻系統(tǒng)、應(yīng)用聚類(lèi)、阻尼突變策略三種組合來(lái)改進(jìn)學(xué)習(xí)方法,通過(guò)在狀態(tài)空間中進(jìn)行快速有效的全局和局部搜索來(lái)進(jìn)行特征選擇,在短時(shí)間內(nèi)獲得最佳特征。
蟻群優(yōu)化(Ant Colony Optimization,ACO)[12]算法是由Marco于1992年提出的一種基于概率技術(shù)元啟發(fā)式優(yōu)化方法,方法的主要目標(biāo)是根據(jù)螞蟻在整個(gè)空間中搜尋食物來(lái)源的行為來(lái)獲得圖中最佳路徑。在自然世界中,蟻群在覓食過(guò)程中,會(huì)在其經(jīng)過(guò)的路徑上留下一種信息素的化學(xué)物質(zhì)。蟻群個(gè)體對(duì)信息素具有感知能力,會(huì)沿著信息素濃度較高路徑行走,從而找出最短路徑。但是,由于蟻群優(yōu)化算法的解空間搜索受到限制,容易導(dǎo)致收斂到局部最優(yōu)解。為了克服這一問(wèn)題,Manbari等[13]在2005年引入了一種二元螞蟻系統(tǒng)(Binary Ant System,BAS),該系統(tǒng)應(yīng)用于具有二元解結(jié)構(gòu)的約束優(yōu)化問(wèn)題,即搜索空間被表示為一個(gè)二進(jìn)制圖,其中每個(gè)節(jié)點(diǎn)都通過(guò)兩個(gè)邊連接到下一個(gè)節(jié)點(diǎn),如圖1所示。
圖1 BAS中的螞蟻路徑圖
螞蟻通過(guò)從開(kāi)始到最后遍歷圖來(lái)生成其解決方案,解以二進(jìn)制字符串表示:x={x1,x2,…,xn},xj∈{0,1}。在每次迭代時(shí),一組螞蟻開(kāi)始搜索二進(jìn)制搜索域,并且可以通過(guò)從圖1上的節(jié)點(diǎn)1到節(jié)點(diǎn)n+1依次行走的螞蟻來(lái)生成解決方案。在每個(gè)節(jié)點(diǎn)j上,螞蟻都會(huì)選擇兩條路徑中的一條,以步行到下一個(gè)節(jié)點(diǎn)j+1。節(jié)點(diǎn)xj的信息素值由τjs表示,s∈{0,1},與選定/取消選定狀態(tài)相對(duì)應(yīng)。對(duì)于選擇/取消選擇狀態(tài),初始信息素分布在所有節(jié)點(diǎn)上,表示為τ0。在生成解時(shí),螞蟻k根據(jù)式(1)所述的概率分布選擇節(jié)點(diǎn)j。
(1)
為了生成解決方案,所有螞蟻都會(huì)為每個(gè)節(jié)點(diǎn)進(jìn)行選擇。一旦每只螞蟻完成了巡視,目標(biāo)函數(shù)便會(huì)用于評(píng)估和比較整個(gè)當(dāng)前迭代過(guò)程中生成的所有解決方案。系統(tǒng)保留當(dāng)前已找到的最佳解決方案作為全局最佳解決方案Sgb,若當(dāng)前迭代i中的解決方案Sib優(yōu)于Sgb,則更新最佳解決方案為Sib。在每個(gè)迭代周期的末尾執(zhí)行更新全局信息素的過(guò)程。此過(guò)程包括兩個(gè)步驟。在第一步信息素?fù)]發(fā)過(guò)程中,所有信息素均會(huì)根據(jù)以下所述揮發(fā)規(guī)則輕微發(fā)散:
τjs(t+1)←(1-ρ)τjs(t)
(2)
式中:ρ表示揮發(fā)參數(shù)。第二步是將所選節(jié)點(diǎn)的信息素增強(qiáng)為Sgb:
τjs(t+1)←τjs(t+1)+ρΔτ(j,s)∈Sgb
(3)
式中:參數(shù)Δτ表示增強(qiáng)的信息素量。重復(fù)上述循環(huán),直到滿足特定的終止條件為止。
目前,在二元螞蟻系統(tǒng)的基礎(chǔ)上,存在多個(gè)改進(jìn)算法。Zhang等[14]為了在不影響解的質(zhì)量的前提下進(jìn)一步提高收斂速度,在二元螞蟻優(yōu)化算法中加入約束滿足條件。Mafarja等[15]為了提高最佳解的質(zhì)量,在二元螞蟻系統(tǒng)中引入獅群優(yōu)化,在全局中尋找最優(yōu)解。
本文提出一種基于BAS和聚類(lèi)的混合無(wú)監(jiān)督特征選擇算法,該算法首先將特征聚類(lèi),其次通過(guò)將BAS應(yīng)用到每個(gè)集群,在并行過(guò)程中對(duì)不同集群中的特征進(jìn)行排序,然后在迭代過(guò)程中,通過(guò)BAS方法選擇每個(gè)群集的最佳特征。重復(fù)此階段,直到完成所需的特征子集為止。
狀態(tài)轉(zhuǎn)移規(guī)則是概率性的,并且是基于節(jié)點(diǎn)信息素值和啟發(fā)式信息的混合而設(shè)計(jì)的,定義如下:
(4)
(5)
特征j和先前選擇的與特征j具有最大相似性的q個(gè)特征之間的平均相似性可表示為:
(6)
式中:Γk包含特征i與子集k中的每個(gè)特征之間具有最大相似性的q個(gè)節(jié)點(diǎn)/特征。
最后,根據(jù)式(7)和式(8),選擇(S=1)或不選擇(S=0)節(jié)點(diǎn)i分別采用貪婪或概率規(guī)則來(lái)確定。為了避免陷入局部最優(yōu)和增加搜索空間,使用輪盤(pán)賭輪,使得基于閾值θ=0.7進(jìn)行選擇或取消選擇過(guò)程。
(7)
(8)
式中:γ0為隨機(jī)值。
為了避免陷入局部最優(yōu)并克服搜索空間的限制,考慮一種突變策略。螞蟻的隨機(jī)運(yùn)動(dòng)意味著人工螞蟻從隨機(jī)選擇的節(jié)點(diǎn)開(kāi)始在映射圖上移動(dòng);螞蟻的隨機(jī)方向,即螞蟻的順/逆時(shí)針移動(dòng)方向應(yīng)隨機(jī)確定;特定節(jié)點(diǎn)處的阻尼突變。采用阻尼變異是為了避免過(guò)早收斂。通過(guò)變異策略,交換圖上的一些節(jié)點(diǎn)用于修改節(jié)點(diǎn)的順序,增加搜索空間的狀態(tài)數(shù)。根據(jù)這種方法,螞蟻在初次迭代時(shí)被隨機(jī)放置在圖上;然后,變異算子根據(jù)變異條件交換圖上的特定節(jié)點(diǎn);在隨后的迭代中,如果變異已經(jīng)發(fā)生,螞蟻會(huì)移動(dòng)到新的變異圖上。如果當(dāng)前迭代與前一迭代信息素比率之差小于變異率時(shí),滿足變異條件。信息素比率PR是每個(gè)節(jié)點(diǎn)每次迭代中選定節(jié)點(diǎn)上信息素的值。為了比較突變率,這個(gè)變量應(yīng)該被規(guī)范化:
(9)
突變率是決定突變的一個(gè)參數(shù)。突變率在迭代初始是最大值,在迭代過(guò)程中變異率會(huì)隨之降低。原因是該算法在學(xué)習(xí)初期具有較高的探索能力,然后通過(guò)降低變異率,使算法的局部搜索能力和收斂性逐漸提高。通過(guò)該技術(shù)的應(yīng)用,在搜索空間中實(shí)現(xiàn)了勘探與開(kāi)發(fā)的平衡。選擇節(jié)點(diǎn)時(shí)頻率較低的節(jié)點(diǎn)會(huì)被選擇頻率最高的節(jié)點(diǎn)所代替。在蟻群算法的每次迭代中,圖上隨機(jī)放置一個(gè)螞蟻。然后,隨機(jī)選擇螞蟻的順時(shí)針或逆時(shí)針運(yùn)動(dòng)。每只螞蟻根據(jù)運(yùn)動(dòng)方向不斷地遍歷圓圖,直到返回初始位置。同時(shí),螞蟻根據(jù)概率狀態(tài)轉(zhuǎn)移規(guī)則選擇或取消選擇特征。狀態(tài)轉(zhuǎn)移規(guī)則尋求選擇具有最高項(xiàng)方差值且與式(4)描述的先前選擇的特征的相似性最低的特征。螞蟻選擇/取消選擇特定節(jié)點(diǎn)的次數(shù)被定義為特征狀態(tài)計(jì)數(shù)器。然后,在每次迭代結(jié)束時(shí),通過(guò)特征狀態(tài)計(jì)數(shù)器和根據(jù)信息素的更新規(guī)則更新每個(gè)節(jié)點(diǎn)的信息素值。在滿足停止準(zhǔn)則后,選擇信息素值最高的特征。
信息素更新規(guī)則適用于更新所有邊緣上的信息素。 每個(gè)螞蟻完成遍歷后,使用式(10)更新信息素值。
(10)
2.2.1特征聚類(lèi)
基于要素之間的相似度將其分為幾個(gè)聚類(lèi)。應(yīng)用Louvain社區(qū)檢測(cè)算法[11]將圖劃分為小分區(qū),在社區(qū)中通過(guò)最大化模塊化功能來(lái)檢測(cè)社區(qū)。這是一種實(shí)現(xiàn)算法的簡(jiǎn)單、高效且簡(jiǎn)便的方法,該算法應(yīng)用于節(jié)點(diǎn)的相似度圖,可檢測(cè)非常大的圖中的社區(qū)。
2.2.2并行特征選擇
在每個(gè)聚類(lèi)中分別執(zhí)行阻尼突變BAS,即將特征放置在阻尼突變BAS的搜索空間中表示,螞蟻開(kāi)始搜索并注入信息素。特征聚類(lèi)和圖形如圖3所示。
圖3 在特征聚類(lèi)中執(zhí)行阻尼突變BAS
由于聚類(lèi)是完全分離的,因此每個(gè)聚類(lèi)由一批螞蟻并行滾動(dòng)。與其他基于聚類(lèi)的特征選擇方法相比,由于進(jìn)行并行處理使得該階段的時(shí)間復(fù)雜度顯著降低。在對(duì)聚類(lèi)進(jìn)行處理后,基于阻尼突變BAS方法,信息素被螞蟻?zhàn)⑷牒螅鶕?jù)聚類(lèi)中的信息素值對(duì)每個(gè)聚類(lèi)中的特征進(jìn)行排序。因此,每個(gè)聚類(lèi)中的顯著特征位于列表的前段。
2.2.3順序特征選擇
在每次迭代中,從每個(gè)聚類(lèi)中提取前K個(gè)剩余特征,將阻尼突變BAS應(yīng)用于這些特征,并選擇K0個(gè)最佳特征。然后,將所選特征從所屬聚類(lèi)中刪除,并更新聚類(lèi)用于重新選擇K個(gè)要素。該循環(huán)一直持續(xù)到所需的特征子集完成為止。在這個(gè)過(guò)程中重復(fù)了nf/K0次,但此圖的處理時(shí)間遠(yuǎn)遠(yuǎn)少于包含所有特征的初始圖的處理時(shí)間。圖4給出了本文方法在K0=3時(shí)的示意圖。
圖4 本文方法示意圖
算法1中顯示了本文方法的偽代碼。在第1行和第2行中,完成了并行特征選擇,包括特征聚類(lèi),并且在每個(gè)聚類(lèi)中應(yīng)用了阻尼突變BAS。在并行特征選擇中,基于每個(gè)聚類(lèi)信息素值排序的特征將被返回。在第4-第9行中,完成了順序特征選擇。在第4行中,重復(fù)循環(huán),直到完成所需的特征子集為止。在第5行中,從每個(gè)聚類(lèi)中選擇前K個(gè)特征。第6行則是選擇所有聚類(lèi)中K個(gè)最佳特征。由于必須從各個(gè)聚類(lèi)中選擇出最好的特征,因此聚類(lèi)的信息素值必須具有可比性,因此對(duì)聚類(lèi)的信息素值進(jìn)行如下歸一化處理:
(11)
算法1基于聚類(lèi)和阻尼突變BAS的特征選擇算法
輸入:所選特征數(shù)量nf,聚類(lèi)數(shù)量nc,具有p個(gè)模式的n維數(shù)據(jù)集Dp×n。
輸出:降維的數(shù)據(jù)集Dp×nm。
1. 將特征進(jìn)行聚類(lèi);
2. 在每個(gè)聚類(lèi)上執(zhí)行阻尼突變BAS算法,并從中返回排序后的特征List_features;
3.K=nf/nc;K=K0
4. while 特征子集未完成
5. 從每個(gè)聚類(lèi)中選擇前K個(gè)特征;
6. 從所有基于信息素的聚類(lèi)中移除選擇的K個(gè)特征,并更新;
7. 對(duì)第5-6行中選擇的特征執(zhí)行阻尼突變BAS;
8. 選擇K0個(gè)最佳特征,添加值特征子集中,并將其從List_features中刪除;
9. End while;
10. 返回最終特征子集。
在第7行,將從聚類(lèi)獲得的前段特征放置在小的二元圓形圖上,然后將阻尼突變BAS方法應(yīng)用于特征上。從這些前段特征中選擇具有最大信息素值的K0個(gè)特征,并將其添加到第8行中選定特征的最終列表中。這些K0特征從特征列表中刪除,然后更新列表,重復(fù)循環(huán),直到完成所需的特征子集為止。
最佳的聚類(lèi)數(shù)是根據(jù)式(12)獲得的。
(12)
式中:nf是目標(biāo)特征數(shù)量;μ是所有要素之間相似度的平均標(biāo)準(zhǔn)偏差。
為了評(píng)價(jià)本文算法的性能,本文方法在相同條件下與基于遺傳算法和禁忌搜索混合的特征選擇(GATS)[7]、基于烏鴉搜索算法二值化特征選擇(BCSA)[8]、基于動(dòng)態(tài)相關(guān)性和聯(lián)合互信息最大化的特征選擇(DRJMIM)[14]等現(xiàn)有的特征選擇方法相比。本文仿真實(shí)驗(yàn)是在具有2.7 GHz頻率和6 GB RAM的Intel Core i5 CPU系統(tǒng)的PC上執(zhí)行的。使用C#.Net編程語(yǔ)言實(shí)現(xiàn)了所有算法,在實(shí)驗(yàn)中使用的分類(lèi)器為支持向量機(jī)SVM,其他參數(shù)如表1所示。
表1 本文方法的參數(shù)設(shè)置
本文使用了來(lái)自UCI大學(xué)存儲(chǔ)庫(kù)的一些知名的真實(shí)世界數(shù)據(jù)集,數(shù)據(jù)集名稱(chēng)為Wine、Ionosphere、Hepatitis、SpamBase、Arrhythmia、Madelon、Colon和Leukemia[1]。這些數(shù)據(jù)集已用于許多機(jī)器學(xué)習(xí)研究中,包括特征選擇并涵蓋了小、中和大特征維范圍。表2給出了這些數(shù)據(jù)集的特征總結(jié)。
采用準(zhǔn)確率(Precision)、召回率(Recall)、綜合評(píng)價(jià)指標(biāo)(F1-Measure)三個(gè)性能評(píng)價(jià)指標(biāo)進(jìn)行評(píng)估本文方法的性能。
準(zhǔn)確率P表示被分類(lèi)正確的樣品中實(shí)際為正確的比例,計(jì)算式表示為:
(13)
式中:TP表示為將正類(lèi)預(yù)測(cè)為正類(lèi)數(shù);FP表示為將負(fù)類(lèi)預(yù)測(cè)為正類(lèi)數(shù)。
召回率R是覆蓋面的度量,度量有多個(gè)正類(lèi)被分為正類(lèi):
(14)
式中:FN表示將負(fù)類(lèi)預(yù)測(cè)為負(fù)類(lèi)數(shù)。綜合評(píng)價(jià)指標(biāo)F1值是準(zhǔn)確率P和召回率R加權(quán)調(diào)和平均:
(15)
圖5-圖7顯示了在UCI數(shù)據(jù)集上,本文方法與其他特征選擇方法在準(zhǔn)確率、召回率、F1三個(gè)指標(biāo)的測(cè)試結(jié)果比較??梢钥闯?,相對(duì)其他方法,本文方法具有很好的性能,在三個(gè)測(cè)試指標(biāo)中均獲得良好的結(jié)果。
圖5 不同特征選擇方法的準(zhǔn)確率結(jié)果對(duì)比
圖6 不同特征選擇方法的召回率結(jié)果對(duì)比
圖7 不同特征選擇方法的F1指數(shù)結(jié)果對(duì)比
表3給出了本文算法與其他對(duì)比算法在數(shù)據(jù)集上的測(cè)試結(jié)果??梢钥吹剑疚姆椒ǖ钠骄鶊?zhí)行時(shí)間比其他方法縮短約49~56倍。本文方法的主要優(yōu)勢(shì)在于其性能與完全圖方法相同,而計(jì)算復(fù)雜度非常低,大大減少了高維數(shù)據(jù)集的運(yùn)行時(shí)間。
表3 不同特征選擇方法的執(zhí)行時(shí)間 單位:ms
本文提出一種基于混合濾波器的特征選擇算法,用于降低計(jì)算成本、簡(jiǎn)化學(xué)習(xí)模型、提高分類(lèi)器性能。該算法由線性二進(jìn)制螞蟻系統(tǒng)、聚類(lèi)、阻尼突變策略組成。二元螞蟻系統(tǒng)可以克服搜索空間的挑戰(zhàn),聚類(lèi)在一定程度上減輕處理高維數(shù)據(jù)集的問(wèn)題,通過(guò)引入突變使搜索空間更加隨機(jī)化。本文方法中,將特征聚類(lèi)并順序放置在圓形圖中后,應(yīng)用阻尼突變BAS算法,然后在迭代過(guò)程中選擇一些最佳特征,直到完成所需的特征子集為止。模型在聚類(lèi)之間和聚類(lèi)內(nèi)部應(yīng)用了全局和局部搜索功能。實(shí)驗(yàn)結(jié)果表明,本文方法顯著減少了計(jì)算時(shí)間,并且比其他特征選擇方法具有更好的效果。