周金容 羅 建

1(南充職業(yè)技術(shù)學(xué)院電子信息工程系 四川 南充 637131) 2(西華師范大學(xué)計(jì)算機(jī)學(xué)院 四川 南充 637009)

0 引 言

在大數(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)獲得最佳特征。

1 二元螞蟻算法

蟻群優(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)解。

2 基于聚類(lèi)和BAS的特征選擇

本文提出一種基于BAS和聚類(lèi)的混合無(wú)監(jiān)督特征選擇算法，該算法首先將特征聚類(lèi)，其次通過(guò)將BAS應(yīng)用到每個(gè)集群，在并行過(guò)程中對(duì)不同集群中的特征進(jìn)行排序，然后在迭代過(guò)程中，通過(guò)BAS方法選擇每個(gè)群集的最佳特征。重復(fù)此階段，直到完成所需的特征子集為止。

2.1 阻尼突變BAS

狀態(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 特征選擇算法

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)偏差。

3 實(shí)驗(yàn)與結(jié)果分析

為了評(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è)置

3.1 數(shù)據(jù)集和評(píng)估標(biāo)準(zhǔn)

本文使用了來(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)

3.2 結(jié)果分析

圖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

4 結(jié) 語(yǔ)

本文提出一種基于混合濾波器的特征選擇算法，用于降低計(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í)間，并且比其他特征選擇方法具有更好的效果。