周金容 羅 建

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

0 引 言

在大數(shù)據(jù)時代，高維數(shù)據(jù)已擴展到社交媒體、生物信息學、圖像處理和自然語言處理等不同領域[1-2]。計算負擔、過擬合和性能不佳是高維數(shù)據(jù)帶來的一些外在表現(xiàn)缺點[3]。在模式識別中，由于存在成千上萬的特征，因此從高維數(shù)據(jù)中選擇特征子集仍然是一個挑戰(zhàn)[4]，其中過濾掉無關和冗余的特征可以減少過度擬合，節(jié)省計算成本并提高分類的準確性。特征選擇算法是可以有效地將原始數(shù)據(jù)縮小到低維空間的算法。特征選擇是組合優(yōu)化問題，在當今許多科學領域中都是重要問題。

特征選擇技術已成功應用于各種人工智能領域，包括文本挖掘、圖像處理、生物信息學，以及其他領域[5]。目前，研究人員已經(jīng)開發(fā)了許多群體智能啟發(fā)優(yōu)化算法用于特征選擇。文獻[6]提出了一種基于多目標粒子群優(yōu)化的特征選擇方法，該方法根據(jù)特征在存檔集中的頻率對其進行排名，使用這些等級來優(yōu)化存檔集并引導粒子，消除了不相關、多余和嘈雜的特征，降低計算成本。文獻[7]提出了一種基于遺傳算法和禁忌搜索相結合的特征選擇方法，該方法通過定義一個過早收斂索引，以判斷遺傳算法過程中的收斂情況。當確實發(fā)生早收斂時，將執(zhí)行改進的變異算子，對具有較高適應性值的個體采用禁忌搜索算法。文獻[8]提出了一種基于烏鴉搜索的V形二值化包裝器，該包裝器利用二進制烏鴉搜索算法簡化了特征選擇模型和減少了分類處理時間。文獻[9]為了處理高維低樣本數(shù)據(jù)中的冗余特征和不相關特征，提出了一種基于粒度信息的特征選擇算法模型，該模型利用改進的具有特征粒度的二進制遺傳算法來選擇優(yōu)化粒子集重要特征。文獻[10]設計一種基于粗糙集與人工蜂群算法的動態(tài)數(shù)據(jù)流特征選擇算法，使用粗糙集定義數(shù)據(jù)流增量數(shù)據(jù)的適應度函數(shù)，利用人工蜂群算法從舊特征子集與增量數(shù)據(jù)提取新的全局特征子集，為了增強人工蜂群算法的魯棒性，通過降低人工蜂群算法過早收斂幾率來滿足動態(tài)特征選擇算法的穩(wěn)定性需要。文獻[11]提出一種基于加權社區(qū)檢測與增強人工蟻群算法的高維數(shù)據(jù)特征選擇算法，通過設計加權社區(qū)檢測算法，將特征相似性作為社區(qū)劃分的模塊度，利用人工蟻群算法并行地處理每個特征分類，提取全局最優(yōu)的特征子集，從而提高了特征選擇的時間效率。

為了降低高維數(shù)據(jù)特征選擇的運行時間和提高分類精度，提出一種基于聚類和二元螞蟻算法相結合的混合濾波器特征選擇方法，該方法通過線性二元螞蟻系統(tǒng)、應用聚類、阻尼突變策略三種組合來改進學習方法，通過在狀態(tài)空間中進行快速有效的全局和局部搜索來進行特征選擇，在短時間內獲得最佳特征。

1 二元螞蟻算法

蟻群優(yōu)化(Ant Colony Optimization，ACO)[12]算法是由Marco于1992年提出的一種基于概率技術元啟發(fā)式優(yōu)化方法，方法的主要目標是根據(jù)螞蟻在整個空間中搜尋食物來源的行為來獲得圖中最佳路徑。在自然世界中，蟻群在覓食過程中，會在其經(jīng)過的路徑上留下一種信息素的化學物質。蟻群個體對信息素具有感知能力，會沿著信息素濃度較高路徑行走，從而找出最短路徑。但是，由于蟻群優(yōu)化算法的解空間搜索受到限制，容易導致收斂到局部最優(yōu)解。為了克服這一問題，Manbari等[13]在2005年引入了一種二元螞蟻系統(tǒng)(Binary Ant System，BAS)，該系統(tǒng)應用于具有二元解結構的約束優(yōu)化問題，即搜索空間被表示為一個二進制圖，其中每個節(jié)點都通過兩個邊連接到下一個節(jié)點，如圖1所示。

圖1 BAS中的螞蟻路徑圖

螞蟻通過從開始到最后遍歷圖來生成其解決方案，解以二進制字符串表示：x={x1,x2,…,xn}，xj∈{0,1}。在每次迭代時，一組螞蟻開始搜索二進制搜索域，并且可以通過從圖1上的節(jié)點1到節(jié)點n+1依次行走的螞蟻來生成解決方案。在每個節(jié)點j上，螞蟻都會選擇兩條路徑中的一條，以步行到下一個節(jié)點j+1。節(jié)點xj的信息素值由τjs表示，s∈{0,1}，與選定/取消選定狀態(tài)相對應。對于選擇/取消選擇狀態(tài)，初始信息素分布在所有節(jié)點上，表示為τ0。在生成解時，螞蟻k根據(jù)式(1)所述的概率分布選擇節(jié)點j。

(1)

為了生成解決方案，所有螞蟻都會為每個節(jié)點進行選擇。一旦每只螞蟻完成了巡視，目標函數(shù)便會用于評估和比較整個當前迭代過程中生成的所有解決方案。系統(tǒng)保留當前已找到的最佳解決方案作為全局最佳解決方案Sgb，若當前迭代i中的解決方案Sib優(yōu)于Sgb，則更新最佳解決方案為Sib。在每個迭代周期的末尾執(zhí)行更新全局信息素的過程。此過程包括兩個步驟。在第一步信息素揮發(fā)過程中，所有信息素均會根據(jù)以下所述揮發(fā)規(guī)則輕微發(fā)散：

τjs(t+1)←(1-ρ)τjs(t)

(2)

式中：ρ表示揮發(fā)參數(shù)。第二步是將所選節(jié)點的信息素增強為Sgb：

τjs(t+1)←τjs(t+1)+ρΔτ(j,s)∈Sgb

(3)

式中：參數(shù)Δτ表示增強的信息素量。重復上述循環(huán)，直到滿足特定的終止條件為止。

目前，在二元螞蟻系統(tǒng)的基礎上，存在多個改進算法。Zhang等[14]為了在不影響解的質量的前提下進一步提高收斂速度，在二元螞蟻優(yōu)化算法中加入約束滿足條件。Mafarja等[15]為了提高最佳解的質量，在二元螞蟻系統(tǒng)中引入獅群優(yōu)化，在全局中尋找最優(yōu)解。

2 基于聚類和BAS的特征選擇

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

2.1 阻尼突變BAS

狀態(tài)轉移規(guī)則是概率性的，并且是基于節(jié)點信息素值和啟發(fā)式信息的混合而設計的，定義如下：

(4)

(5)

特征j和先前選擇的與特征j具有最大相似性的q個特征之間的平均相似性可表示為：

(6)

式中：Γk包含特征i與子集k中的每個特征之間具有最大相似性的q個節(jié)點/特征。

最后，根據(jù)式(7)和式(8)，選擇(S=1)或不選擇(S=0)節(jié)點i分別采用貪婪或概率規(guī)則來確定。為了避免陷入局部最優(yōu)和增加搜索空間，使用輪盤賭輪，使得基于閾值θ=0.7進行選擇或取消選擇過程。

(7)

(8)

式中：γ0為隨機值。

為了避免陷入局部最優(yōu)并克服搜索空間的限制，考慮一種突變策略。螞蟻的隨機運動意味著人工螞蟻從隨機選擇的節(jié)點開始在映射圖上移動；螞蟻的隨機方向，即螞蟻的順/逆時針移動方向應隨機確定；特定節(jié)點處的阻尼突變。采用阻尼變異是為了避免過早收斂。通過變異策略，交換圖上的一些節(jié)點用于修改節(jié)點的順序，增加搜索空間的狀態(tài)數(shù)。根據(jù)這種方法，螞蟻在初次迭代時被隨機放置在圖上；然后，變異算子根據(jù)變異條件交換圖上的特定節(jié)點；在隨后的迭代中，如果變異已經(jīng)發(fā)生，螞蟻會移動到新的變異圖上。如果當前迭代與前一迭代信息素比率之差小于變異率時，滿足變異條件。信息素比率PR是每個節(jié)點每次迭代中選定節(jié)點上信息素的值。為了比較突變率，這個變量應該被規(guī)范化：

(9)

突變率是決定突變的一個參數(shù)。突變率在迭代初始是最大值，在迭代過程中變異率會隨之降低。原因是該算法在學習初期具有較高的探索能力，然后通過降低變異率，使算法的局部搜索能力和收斂性逐漸提高。通過該技術的應用，在搜索空間中實現(xiàn)了勘探與開發(fā)的平衡。選擇節(jié)點時頻率較低的節(jié)點會被選擇頻率最高的節(jié)點所代替。在蟻群算法的每次迭代中，圖上隨機放置一個螞蟻。然后，隨機選擇螞蟻的順時針或逆時針運動。每只螞蟻根據(jù)運動方向不斷地遍歷圓圖，直到返回初始位置。同時，螞蟻根據(jù)概率狀態(tài)轉移規(guī)則選擇或取消選擇特征。狀態(tài)轉移規(guī)則尋求選擇具有最高項方差值且與式(4)描述的先前選擇的特征的相似性最低的特征。螞蟻選擇/取消選擇特定節(jié)點的次數(shù)被定義為特征狀態(tài)計數(shù)器。然后，在每次迭代結束時，通過特征狀態(tài)計數(shù)器和根據(jù)信息素的更新規(guī)則更新每個節(jié)點的信息素值。在滿足停止準則后，選擇信息素值最高的特征。

信息素更新規(guī)則適用于更新所有邊緣上的信息素。 每個螞蟻完成遍歷后，使用式(10)更新信息素值。

(10)

2.2 特征選擇算法

2.2.1特征聚類

基于要素之間的相似度將其分為幾個聚類。應用Louvain社區(qū)檢測算法[11]將圖劃分為小分區(qū)，在社區(qū)中通過最大化模塊化功能來檢測社區(qū)。這是一種實現(xiàn)算法的簡單、高效且簡便的方法，該算法應用于節(jié)點的相似度圖，可檢測非常大的圖中的社區(qū)。

2.2.2并行特征選擇

在每個聚類中分別執(zhí)行阻尼突變BAS，即將特征放置在阻尼突變BAS的搜索空間中表示，螞蟻開始搜索并注入信息素。特征聚類和圖形如圖3所示。

圖3 在特征聚類中執(zhí)行阻尼突變BAS

由于聚類是完全分離的，因此每個聚類由一批螞蟻并行滾動。與其他基于聚類的特征選擇方法相比，由于進行并行處理使得該階段的時間復雜度顯著降低。在對聚類進行處理后，基于阻尼突變BAS方法，信息素被螞蟻注入后，根據(jù)聚類中的信息素值對每個聚類中的特征進行排序。因此，每個聚類中的顯著特征位于列表的前段。

2.2.3順序特征選擇

在每次迭代中，從每個聚類中提取前K個剩余特征，將阻尼突變BAS應用于這些特征，并選擇K0個最佳特征。然后，將所選特征從所屬聚類中刪除，并更新聚類用于重新選擇K個要素。該循環(huán)一直持續(xù)到所需的特征子集完成為止。在這個過程中重復了nf/K0次，但此圖的處理時間遠遠少于包含所有特征的初始圖的處理時間。圖4給出了本文方法在K0=3時的示意圖。

圖4 本文方法示意圖

算法1中顯示了本文方法的偽代碼。在第1行和第2行中，完成了并行特征選擇，包括特征聚類，并且在每個聚類中應用了阻尼突變BAS。在并行特征選擇中，基于每個聚類信息素值排序的特征將被返回。在第4-第9行中，完成了順序特征選擇。在第4行中，重復循環(huán)，直到完成所需的特征子集為止。在第5行中，從每個聚類中選擇前K個特征。第6行則是選擇所有聚類中K個最佳特征。由于必須從各個聚類中選擇出最好的特征，因此聚類的信息素值必須具有可比性，因此對聚類的信息素值進行如下歸一化處理：

(11)

算法1基于聚類和阻尼突變BAS的特征選擇算法

輸入：所選特征數(shù)量nf，聚類數(shù)量nc，具有p個模式的n維數(shù)據(jù)集Dp×n。

輸出：降維的數(shù)據(jù)集Dp×nm。

1. 將特征進行聚類；

2. 在每個聚類上執(zhí)行阻尼突變BAS算法，并從中返回排序后的特征List_features；

3.K=nf/nc；K=K0

4. while 特征子集未完成

5. 從每個聚類中選擇前K個特征；

6. 從所有基于信息素的聚類中移除選擇的K個特征，并更新；

7. 對第5-6行中選擇的特征執(zhí)行阻尼突變BAS；

8. 選擇K0個最佳特征，添加值特征子集中，并將其從List_features中刪除；

9. End while；

10. 返回最終特征子集。

在第7行，將從聚類獲得的前段特征放置在小的二元圓形圖上，然后將阻尼突變BAS方法應用于特征上。從這些前段特征中選擇具有最大信息素值的K0個特征，并將其添加到第8行中選定特征的最終列表中。這些K0特征從特征列表中刪除，然后更新列表，重復循環(huán)，直到完成所需的特征子集為止。

最佳的聚類數(shù)是根據(jù)式(12)獲得的。

(12)

式中：nf是目標特征數(shù)量；μ是所有要素之間相似度的平均標準偏差。

3 實驗與結果分析

為了評價本文算法的性能，本文方法在相同條件下與基于遺傳算法和禁忌搜索混合的特征選擇(GATS)[7]、基于烏鴉搜索算法二值化特征選擇(BCSA)[8]、基于動態(tài)相關性和聯(lián)合互信息最大化的特征選擇(DRJMIM)[14]等現(xiàn)有的特征選擇方法相比。本文仿真實驗是在具有2.7 GHz頻率和6 GB RAM的Intel Core i5 CPU系統(tǒng)的PC上執(zhí)行的。使用C#.Net編程語言實現(xiàn)了所有算法，在實驗中使用的分類器為支持向量機SVM，其他參數(shù)如表1所示。

表1 本文方法的參數(shù)設置

3.1 數(shù)據(jù)集和評估標準

本文使用了來自UCI大學存儲庫的一些知名的真實世界數(shù)據(jù)集，數(shù)據(jù)集名稱為Wine、Ionosphere、Hepatitis、SpamBase、Arrhythmia、Madelon、Colon和Leukemia[1]。這些數(shù)據(jù)集已用于許多機器學習研究中，包括特征選擇并涵蓋了小、中和大特征維范圍。表2給出了這些數(shù)據(jù)集的特征總結。

采用準確率(Precision)、召回率(Recall)、綜合評價指標(F1-Measure)三個性能評價指標進行評估本文方法的性能。

準確率P表示被分類正確的樣品中實際為正確的比例，計算式表示為：

(13)

式中：TP表示為將正類預測為正類數(shù)；FP表示為將負類預測為正類數(shù)。

召回率R是覆蓋面的度量，度量有多個正類被分為正類：

(14)

式中：FN表示將負類預測為負類數(shù)。綜合評價指標F1值是準確率P和召回率R加權調和平均：

(15)

3.2 結果分析

圖5-圖7顯示了在UCI數(shù)據(jù)集上，本文方法與其他特征選擇方法在準確率、召回率、F1三個指標的測試結果比較?？梢钥闯?，相對其他方法，本文方法具有很好的性能，在三個測試指標中均獲得良好的結果。

圖5 不同特征選擇方法的準確率結果對比

圖6 不同特征選擇方法的召回率結果對比

圖7 不同特征選擇方法的F1指數(shù)結果對比

表3給出了本文算法與其他對比算法在數(shù)據(jù)集上的測試結果。可以看到，本文方法的平均執(zhí)行時間比其他方法縮短約49～56倍。本文方法的主要優(yōu)勢在于其性能與完全圖方法相同，而計算復雜度非常低，大大減少了高維數(shù)據(jù)集的運行時間。

表3 不同特征選擇方法的執(zhí)行時間 單位：ms

4 結 語

本文提出一種基于混合濾波器的特征選擇算法，用于降低計算成本、簡化學習模型、提高分類器性能。該算法由線性二進制螞蟻系統(tǒng)、聚類、阻尼突變策略組成。二元螞蟻系統(tǒng)可以克服搜索空間的挑戰(zhàn)，聚類在一定程度上減輕處理高維數(shù)據(jù)集的問題，通過引入突變使搜索空間更加隨機化。本文方法中，將特征聚類并順序放置在圓形圖中后，應用阻尼突變BAS算法，然后在迭代過程中選擇一些最佳特征，直到完成所需的特征子集為止。模型在聚類之間和聚類內部應用了全局和局部搜索功能。實驗結果表明，本文方法顯著減少了計算時間，并且比其他特征選擇方法具有更好的效果。