摘 要：隨著信息技術(shù)的快速發(fā)展，數(shù)據(jù)中的高維特征極大地增加了產(chǎn)生冗余特征的可能性，冗余特征不僅導(dǎo)致搜索空間增大，而且影響了分類的準(zhǔn)確率。針對現(xiàn)有的特征選擇算法難以解決高維特征選擇問題，提出了基于樣本重疊與近似馬爾可夫毯的特征選擇算法（samples overlapping based modified Markov blanket，SOMMB）。該算法首先融合最大信息系數(shù)與改進(jìn)強近似馬爾可夫毯去除冗余特征；其次采用樣本重疊策略指導(dǎo)前向搜索的過程，選取相關(guān)特征。該算法在10個公開數(shù)據(jù)集上與目前流行的PGVNS、FCBF-MIC、CFS、mRMR、RF、CBFS、ReliefF以及FFSG算法進(jìn)行對比實驗，SOMMB算法的平均準(zhǔn)確率為82.519%，對比FFSG獲得的最高準(zhǔn)確率提升了4.214%，表明SOMMB算法可以提高分類精度。

關(guān)鍵詞：特征選擇； 最大信息系數(shù)； 改進(jìn)強近似馬爾可夫毯； 樣本重疊； 前向搜索

中圖分類號：TP393.04 文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695（2023）03-013-0725-06

doi：10.19734/j.issn.1001-3695.2022.08.0401

Feature selection based on samples overlapping characteristic andmodified Markov blanket

Wang Dazhi， Ji Yanjing， Chen Yanhua， Wang Hongfeng， Huang Min

（College of Information Science amp; Engineering， Northeastern University， Shenyang 110819， China）

Abstract：With the rapid development of information technology， the high-dimensional features in data greatly increase the possibility of producing redundant features， these redundant features not only cause the expansion of search space， but also affect the classification accuracy. Aiming at the difficulty of existing feature selection algorithms for high-dimensional features， this paper proposed a samples overlapping based modified Markov blanket（SOMMB） algorithm. Firstly， this algorithm combined the maximum information coefficient and the modified strong approximate Markov blanket to remove redundant features. Secondly， it used samples overlapping to guide forward search and select relevant features. This paper compared SOMMB algorithm with PGVNS、FCBF-MIC、CFS、mRMR、RF、CBFS、ReliefF and FFSG" algorithms on 10 public datasets. SOMMB can reach an average accuracy of 82.519%， 4.214% higher than the highest accuracy of FFSG. It shows superiority in feature selection regarding to classification accuracy.

Key words：feature selection; maximal information coefficient; modified strong approximate Markov blanket; samples overlapping; forward search

0 引言

隨著信息技術(shù)的快速發(fā)展，人們可以在極短的時間內(nèi)迅速獲取大量的數(shù)據(jù)，處理這些數(shù)據(jù)涉及到生物信息學(xué)、社會媒體++、模式識別、圖像處理以及自然語言處理等多個領(lǐng)域?？紤]到這些數(shù)據(jù)中存在的無關(guān)特征和冗余特征不僅會增加計算時間和搜索空間，還會降低分類的準(zhǔn)確率［1］，因此特征選擇對于機器學(xué)習(xí)至關(guān)重要。特征選擇也被稱為變量選擇，是指使用某種搜索策略從原始的特征集中找出最佳的特征子集，通過挖掘特征與特征之間以及特征與類別之間的關(guān)聯(lián)性去除冗余特征，選出相關(guān)特征。特征選擇是一個典型的NP-hard問題［2，3］，它需要通過枚舉出所有可能的特征組合并計算出該特征組合下的準(zhǔn)確率以找到最優(yōu)的特征集合，使機器學(xué)習(xí)的錯誤率降到最低?；谙嚓P(guān)性和冗余性分析是常用的特征選擇方法，通過去除冗余與非相關(guān)的特征找到一個滿意的特征子集而非最優(yōu)的特征子集［4］。國內(nèi)外眾多研究者提出了大量的特征選擇算法，根據(jù)它們與學(xué)習(xí)模型結(jié)合的方式，特征選擇算法可以概括為過濾法、包裝法以及嵌入法。過濾法［5］通過數(shù)據(jù)間的距離、依賴性、一致性等內(nèi)在屬性進(jìn)行特征選擇，該方法無須與某種分類器結(jié)合，因此具有快速性和公正性的優(yōu)點。包裝法［6］使用給定的分類器計算分類準(zhǔn)確率，并將準(zhǔn)確率作為所選特征子集的評價指標(biāo)。由于包裝法與特定的分類器結(jié)合，相比于過濾法，包裝法擁有更高的準(zhǔn)確率，但由于每次迭代都需要運行一次分類算法，所以計算時間更長，同時只針對訓(xùn)練時的分類器具有較高的分類精度。嵌入法［7］結(jié)合了過濾法和包裝法的優(yōu)點，與分類器獨特的內(nèi)在結(jié)構(gòu)結(jié)合，在進(jìn)行特征選擇的同時完成分類模型訓(xùn)練，具有計算時間低和準(zhǔn)確率高的優(yōu)點，但理論要求很高，推廣較難。

多種度量標(biāo)準(zhǔn)被用來衡量特征間以及特征與類別間的相關(guān)性。信息論中的信息增益（information gain，IG）［8］表示在給定的條件下，信息復(fù)雜度（不確定性）減少的程度，但對于具有更大數(shù)值的變量，IG值也相應(yīng)地增大，從而缺失了公平性。為了解決這一問題，對稱不確定性（symmetrical uncertainty，SU）［9］將數(shù)值進(jìn)行歸一化，使得數(shù)值的取值范圍為0～1，1表示特征之間完全相關(guān)，0表示特征之間相互獨立?；バ畔?（mutual information，MI）［10］用于分析任意兩個變量之間的關(guān)系，可以在不同條件下定量分析特征間的依賴性以及特征和類別間的相關(guān)性。上述的三種信息度量標(biāo)準(zhǔn)雖然可以度量特征之間的線性和非線性關(guān)系，但無法準(zhǔn)確度量特征間非函數(shù)關(guān)系［11］。為了解決這個問題，Reshef等人［12］提出了最大信息系數(shù)（maximal information coefficient，MIC），指出MIC具有普適性、公平性和對稱性的優(yōu)點，可以處理線性、非線性數(shù)據(jù)，計算復(fù)雜度低、魯棒性高。

面對高維數(shù)據(jù)，僅僅使用過濾法或者包裝法已無法滿足計算要求，學(xué)者們開始研究過濾—包裝混合型特征選擇算法并取得了良好的效果，如Nakariyakul［13］利用交互信息引導(dǎo)增量搜索，提出了IGIS算法。針對高維特征的選擇問題，本文提出的算法首先通過改進(jìn)后的強近似馬爾可夫毯去除冗余特征，將強近似馬爾可夫毯和最大信息系數(shù)結(jié)合，實現(xiàn)衡量變量間線性、非線性、函數(shù)與非函數(shù)關(guān)系的能力，進(jìn)而避免刪除與標(biāo)簽呈強相關(guān)性的特征，達(dá)到更加全面地衡量變量之間數(shù)學(xué)關(guān)系的目的；其次采用樣本重疊策略選取關(guān)鍵特征。算法在UCI以及Scikit特征選擇數(shù)據(jù)集上進(jìn)行實驗，結(jié)果表明提出的算法具有較好的性能和效果。

1 相關(guān)工作

目前根據(jù)信息理論提出了許多特征選擇的算法，其中應(yīng)用較廣泛的有最大相關(guān)最小冗余算法（maximal relevancy minimal redundancy，mRMR）［14］，該算法不僅考慮到特征和標(biāo)簽的關(guān)聯(lián)性，同時考慮到特征之間的冗余性，這為后續(xù)的研究提供了全新的方向。聯(lián)合互信息（joint mutual information，JMI）［15］用來衡量候選特征與已選特征之間的關(guān)聯(lián)性；此外，條件互信息（conditional mutual information，CMI）［16］可以選出與標(biāo)簽具有最大互信息的特征?？焖傧嚓P(guān)濾波方法（fast correlation-based filter，F(xiàn)CBF） ［17］使用了近似馬爾可夫毯的概念對相關(guān)性和冗余性進(jìn)行分析，選擇優(yōu)勢特征，去除冗余特征。孫廣略等人［11］考慮到最大信息系數(shù)的優(yōu)勢以及廣泛的應(yīng)用，將最大信息系數(shù)與近似馬爾可夫毯融合提出了FCBF-MIC算法，去除特征之間的冗余性，并證實該方法優(yōu)于快速相關(guān)濾波法。相關(guān)特征選擇（correlation based feature selection，CFS）［18］是一種基于過濾式的特征選擇算法，利用檢驗原理，通過評估特征之間與特征和類別之間的相關(guān)性評估特征子集的質(zhì)量。CBFS算法［19］通過比較特征對標(biāo)簽的可分性對特征進(jìn)行排序；Relief算法［20］是另一種基于過濾的特征選擇方法，通過從樣本中隨機采樣實例來度量特征和標(biāo)簽之間的相關(guān)性，但該方法只能用于二分類的問題中。為了適應(yīng)多分類問題，Kononenko提出了ReliefF算法［21］，該算法是Relief算法的拓展。

近年來，馬爾可夫毯在特征選擇中得到了廣泛的應(yīng)用，然而它屬于條件獨立性中的強條件，這種條件獨立關(guān)系屬于NP-hard問題，因此在實際應(yīng)用中，使用近似馬爾可夫毯代替馬爾可夫毯來選擇最佳子集。針對高維特征選擇問題，García-Torres等人［22］提出了基于主元素的變鄰域搜索方法（predominant group based variable neighborhood search，PGVNS） ，該方法基于近似馬爾可夫毯完成特征分組，每個特征組的第一個元素稱為主元素，組內(nèi)其他元素為冗余元素，予以刪除。后續(xù)學(xué)者在此方法的基礎(chǔ)上進(jìn)一步改善，Manikandan等人［23］使用互信息代替原算法中的對稱不確定性；Hua等人［24］為了避免將強相關(guān)特征誤判為冗余特征，通過引入閾值δ的計算提出了強近似馬爾可夫毯，為了縮短計算時間對所提出的算法進(jìn)一步改進(jìn)，提出了基于特征分組的過濾式特征選擇算法（filter-based feature selection by feature grouping，F(xiàn)FSG）， 使其更適用于高維的特征選擇問題。

2 最大信息系數(shù)和強近似馬爾可夫毯

2.1 互信息和對稱不確定性

假設(shè)A、B是兩個離散的隨機變量，其中A={a1，a2，…，an}，B={b1，b2，…，bn}，p（ai）是概率分布函數(shù)，p（ai，bj）是聯(lián)合概率分布函數(shù)，p（ai|bj）是條件概率分布函數(shù)。變量A的熵為H（A），A和B的聯(lián)合熵為H（A，B），A和B的條件熵為H（A|B），計算公式如下：

變量A和B之間的互信息記為I（A;B），計算公式如下：

變量A和B之間的對稱不確定性記為SU（A，B），公式為

2.2 最大信息系數(shù)

最大信息系數(shù)[12]不僅可以衡量兩個變量之間線性與非線性的關(guān)系，也可以衡量兩個變量之間的非函數(shù)關(guān)系。最大信息系數(shù)與互信息相比具有更高的準(zhǔn)確度，是一種優(yōu)秀的數(shù)據(jù)關(guān)聯(lián)性計算方法。

最大信息系數(shù)的計算中包含了互信息的概念，最大信息系數(shù)通過將變量之間的關(guān)系以散點圖的方式表示并對散點圖進(jìn)行網(wǎng)格化，將變量A的值域分成x段，變量B的值域分成y段，形成了一個x×y的網(wǎng)格；接著，分別計算每個網(wǎng)格方案對應(yīng)的互信息值，找出互信息最大值，對最大的互信息值進(jìn)行歸一化；最后，選擇不同尺度下互信息的最大值作為最終的最大信息系數(shù)值。計算公式如下：

其中：B（n）為網(wǎng)格劃分的上限，Reshef在論文中指出，當(dāng)B（n）=n0.6時實驗效果最佳，因此本文也采用該值完成相關(guān)實驗。

本文通過計算特征之間的MIC值以及特征與類別之間的MIC值判斷特征的冗余性和相關(guān)性。MIC的取值范圍在0～1，因此，當(dāng)特征之間的MIC值越接近1，表示特征之間的冗余性高，反之獨立性強；當(dāng)特征與類別之間的MIC值越接近1，表示特征和類別的相關(guān)性高，反之無關(guān)性強。

2.3 強近似馬爾可夫毯

冗余特征可以使用馬爾可夫毯［25］來定義?，F(xiàn)有一個特征選擇問題，包含m個特征和n個樣本，定義特征集合為F={f1，f2，f3，…，fm}；C表示標(biāo)簽集合；pf表示概率函數(shù)；fj表示定義1 馬爾可夫毯。利用馬爾可夫毯理論可以確定特征間的冗余度。定義特征集合MjFFjMj，當(dāng)且僅當(dāng)滿足以下公式：

稱Mj構(gòu)成了Fj的馬爾可夫毯。馬爾可夫毯Mj不僅包含了特征fj對于標(biāo)簽C的信息，也包含了其他特征集F-Mj-{fj}的信息。

定義2 近似馬爾可夫毯。給定兩個相關(guān)特征fi和fj（i≠j），當(dāng)且僅當(dāng)滿足以下兩個式子：

則稱fi構(gòu)成了關(guān)于fj的一個近似馬爾可夫毯?；诮岂R爾可夫毯的特征選擇方法屬于后向搜索方法，馬爾可夫毯特征集保證在不丟失相關(guān)特征的前提下去除冗余特征。

定義3 強近似馬爾可夫毯。給定兩個相關(guān)特征fi和fj（i≠j），當(dāng)且僅當(dāng)滿足以下三個式子：

此時稱fi是fj的強近似馬爾可夫毯，其中δ表示每兩個特征之間的相關(guān)性均值。根據(jù)馬爾可夫毯定義，fj屬于冗余特征。對于具有較小相關(guān)性的兩個特征，它們包含了關(guān)于標(biāo)簽的不同信息，因此這兩個特征不能相互替代。然而在這種情況下，其中一個特征依然可以構(gòu)成另一個特征的近似馬爾可夫毯，強相關(guān)特征可能被刪除。為了避免刪除與標(biāo)簽具有強相關(guān)性的特征，筆者引入式（11）以確保特征之間的高度相關(guān)性。與傳統(tǒng)的近似馬爾可夫毯相比，強近似馬爾可夫毯在計算特征之間的對稱不確定性時不要求樣本數(shù)顯著大于特征數(shù)，因此更適用于高維特征的選擇。

3 基于樣本重疊與近似馬爾可夫毯的特征選擇算法

強近似馬爾可夫毯方法是一種從原始特征集中找到冗余特征的有效方法，它能夠克服傳統(tǒng)近似馬爾可夫毯的缺陷。本文提出的基于樣本重疊與近似馬爾可夫毯的特征選擇算法，首先進(jìn)行冗余性分析?？紤]到最大信息系數(shù)不僅可以衡量變量之間線性和非線性關(guān)系，還可以衡量變量之間的非函數(shù)關(guān)系，同時具有標(biāo)準(zhǔn)化的特點。本文對強近似馬爾可夫毯進(jìn)行改進(jìn)，使用最大信息系數(shù)取代原來的對稱不確定性，提出改進(jìn)后的強近似馬爾可夫毯。給定兩個相關(guān)特征fi 和fj（i≠j），fi構(gòu)成fj的改進(jìn)強近似馬爾可夫毯的條件為

通過上述三個公式可以選出主元素，完成特征分組，從而剔除冗余特征，大幅度降低特征維數(shù)，為后續(xù)的特征選擇減少計算時間，節(jié)約存儲空間。但在這個過程中，無法選出與標(biāo)簽最相關(guān)的特征以及無法考慮特征之間的交互影響。

前向搜索是在特征分組得到的候選特征集的基礎(chǔ)上進(jìn)行相關(guān)性分析?，F(xiàn)有的特征選擇停止準(zhǔn)則包括執(zhí)行時間、評價次數(shù)和設(shè)置閾值，其中設(shè)置閾值一般是給算法的目標(biāo)值設(shè)置一個評價閾值，通過目標(biāo)與閾值的比較決定算法停止與否。但要設(shè)置一個合適的閾值并不容易，需要對算法的性能十分了解，否則，閾值過高會使得算法陷入死循環(huán)，過低則達(dá)不到預(yù)定的性能指標(biāo)。針對上述問題，本文提出一種新的確定特征選擇停止準(zhǔn)則的方法，即樣本重疊策略。使用樣本重疊策略對特征序列進(jìn)行前向搜索，將不再有新增的正確預(yù)測樣本作為第二階段特征選擇的停止準(zhǔn)則。采用此策略選出與標(biāo)簽相關(guān)的特征。

本文將提出的基于樣本重疊與近似馬爾可夫毯的特征選擇算法命名為SOMMB，總體框架如圖1所示。

a）SOMMB首先進(jìn)行特征分組如算法1所示。（a）對特征進(jìn)行降序排列，確定搜索序列；（b）選中排序后的第一個特征，其他特征按照順序判斷是否滿足改進(jìn)后的強近似馬爾可夫毯的定義；（c）根據(jù)主元素完成特征分組；（d）迭代直至所有特征完成分組，同時刪除每組中的冗余特征。在算法1中，δ′由式（14）計算得到，li表示第i個特征與其他特征的平均相關(guān)度，t表示迭代次數(shù)，G表示分組結(jié)果，Gt表示第t組的分組結(jié)果，G′由每組的第一個元素構(gòu)成，|G|和|F|分別表示G和F里的元素個數(shù)；L是li構(gòu)成的集合，對L里的元素降序排列得到Lsort。

G′取Gt的首元素。

b）在特征分組完畢后得到一組新的特征集合G′。在相關(guān)性分析階段首先計算每個候選特征與標(biāo)簽C的最大信息系數(shù)，根據(jù)最大信息系數(shù)的值對特征降序排列得到一組新的特征序列，利用樣本重疊策略確定特征個數(shù)。

對于給定的數(shù)據(jù)集，隨機將數(shù)據(jù)劃分為50%訓(xùn)練集和50%測試集，在訓(xùn)練集上，本文采用10折交叉驗證的方式，利用KNN分類器統(tǒng)計在給定特征組的情況下能夠正確預(yù)測的樣本集合。假設(shè)現(xiàn)有50個樣本，S為預(yù)測正確的樣本集合，S1，S2，…，S10分別為每個驗證集內(nèi)預(yù)測正確的樣本集合，則S={S1，S2，…，S10}，操作過程如圖2所示。

在新的特征序列上，選擇第一個特征統(tǒng)計預(yù)測正確的樣本，初始化S集合；接著依次選取第二個特征更新S集合，不斷迭代，直到S集合里不再有新增樣本，此時的特征集合記為F。但此時忽略了特征間的交互影響，因此本文在已選的特征集合F基礎(chǔ)上再次初始化樣本集合S，依據(jù)相同的迭代方式，每次選取后一個特征加入到集合F中，利用集合F內(nèi)的所有特征預(yù)測樣本，不斷更新樣本集合S，直到集合S里不再有新增的樣本，此時所選的特征即為第二階段選取的最終特征。具體過程如算法2所示，其中sample coverage（）表示在給定的特征下使用KNN分類器能夠正確預(yù)測的樣本集合。

假設(shè)現(xiàn)有6個特征、10個樣本，經(jīng)過排序后的特征序列為{3，1，5，0，2，4}，樣本集合為{0，1，2，3，4，5，6，7，8，9}。首先選取特征{3}，利用該特征統(tǒng)計預(yù)測正確的樣本，初始化S={1，2，4，8，9}；接著選取特征{1}，利用該特征統(tǒng)計預(yù)測正確的樣本，記為S′={5，6，8，9}，更新S={1，2，4，5，6，8，9}；再次選取特征{5}，記錄S′={1，2，8，9}，更新S，此時發(fā)現(xiàn)集合S里沒有新增的樣本，因此停止迭代，確定初始的特征集合F={3，1}。在上述特征集合F的基礎(chǔ)上，首先利用集合F初始化S={1，2，4，5，6，8，9}；其次選取特征{3，1，5}，記錄S′={0，1，2，3，4，5，6}，更新S={0，1，2，3，4，5，6，8，9}；再次選取特征{3，1，5，0}，記錄S′={0，1，2，3，4，8，9}，更新S，發(fā)現(xiàn)集合S內(nèi)無新增的樣本，停止迭代，根據(jù)特征數(shù)盡可能少的原則最終選取的特征集合F={3，1，5}。

通過這一階段，不僅考慮到單個特征對標(biāo)簽的作用，而且考慮到特征之間的交互性對標(biāo)簽的影響，增加了特征選擇的多樣性。與準(zhǔn)確率相比，采用樣本重疊策略能夠更準(zhǔn)確地衡量單個特征附帶的新增信息量。

SOMMB算法的時間復(fù)雜度由特征數(shù)m、樣本數(shù)n以及特征分組數(shù)ng決定。在進(jìn)行特征分組階段中，計算∑mk=1∑ml≠kMIC（fk，fl）/［m（m-1）］的時間復(fù)雜度為O（m2n），計算li的時間復(fù)雜度為O（m2），對Lsort進(jìn)行排序的時間復(fù)雜度為O（m log m），進(jìn)行特征分組的時間復(fù)雜度為O（m2ng），在每組選取第一個特征構(gòu)成G′的時間復(fù)雜度為O（ng）。因此，第一階段的總時間復(fù)雜度為O（m2n+ng+m2+mlogm+m2ng）=O（m2n）。在前向搜索階段，計算每個特征和標(biāo)簽最大信息系數(shù)的時間復(fù)雜度為O（ng），根據(jù)最大信息系數(shù)降序排列的時間復(fù)雜度為O（nglog ng），假設(shè)通過樣本覆蓋率選取的最終特征數(shù)為m′，計算時間復(fù)雜度為O（n+nm′）。因此，第二階段的總時間復(fù)雜度為O（ng +nglog ng +nm′）。綜上，SOMMB算法的時間復(fù)雜度為O（m2n+ng+nglog ng+nm′），考慮到nglt;lt;m，m′lt;lt;m，因此最終的時間復(fù)雜度為O（m2n）。

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

本文使用UCI［26］機器學(xué)習(xí)數(shù)據(jù)庫和Scikit［27］特征選擇數(shù)據(jù)庫中的10個公開數(shù)據(jù)集進(jìn)行實驗，并與使用了近似馬爾可夫毯的特征選擇方法PGVNS、FCBF-MIC與FFSG，基于信息論的特征選擇方法CFS、mRMR、CBFS與ReliefF以及嵌入式的特征選擇算法RF（random forest）進(jìn)行對比實驗。從表1可以看出，所選數(shù)據(jù)集包含了二分類和多分類數(shù)據(jù)，維數(shù)從13維到22 283維，樣本數(shù)從62個到1 559個。

采用隨機抽樣的方式將數(shù)據(jù)集劃分為50%的訓(xùn)練集和50%的測試集，使用KNN分類器（K=5）對選擇的特征集進(jìn)行準(zhǔn)確率評估?？紤]到mRMR、RF、CBFS和ReliefF算法只能給出特征序列，無法確定最佳的特征個數(shù)，因此，本文在mRMR、RF、CBFS和ReliefF算法基礎(chǔ)上結(jié)合樣本重疊策略確定特征個數(shù)。將SOMMB算法與PGVNS、FCBF-MIC、CFS、mRMR、RF、CBFS、ReliefF和FFSG算法應(yīng)用于上述的10個公開數(shù)據(jù)集，每個數(shù)據(jù)集單獨運行程序五次，并取平均值作為最終的分類精度，結(jié)果如表2所示。

由表2可知，SOMMB算法在10個數(shù)據(jù)集上整體優(yōu)于其他八種算法，但在Lung數(shù)據(jù)集以及TOX-171數(shù)據(jù)集上，SOMMB算法略遜于FCBF-MIC算法，與FCBF-MIC算法獲得的98%和69.25%的準(zhǔn)確率相比，SOMMB算法分別減少了3.638%和2.446%的準(zhǔn)確率；在Isolet數(shù)據(jù)集上，SOMMB算法與FFSG算法獲得的81.001%準(zhǔn)確率相比，其準(zhǔn)確率減少了0.486%；同時在Arcene數(shù)據(jù)集上，SOMMB算法略遜于CBFS算法，與CBFS獲得的84.2%的準(zhǔn)確率相比減少了8.044%；而在GLI-85數(shù)據(jù)集上SOMMB算法取得了與FCBF-MIC相同的準(zhǔn)確率，準(zhǔn)確率均為90.3%。為了進(jìn)一步比較上述九種特征選擇算法的綜合性能，本文對每種算法在10個數(shù)據(jù)集上的準(zhǔn)確率和所選的特征個數(shù)求取平均值，結(jié)果如表3所示。

由表3可知，本文提出的SOMMB算法與其余八種特征選擇算法相比取得了最高的平均準(zhǔn)確率，值為82.518 9%。該值與其余八種算法的最高準(zhǔn)確率相比高出4.214%，與其余八種算法的最低準(zhǔn)確率相比高出15.54%。在特征個數(shù)方面，SOMMB算法獲得了最少的特征個數(shù)，與FFSG算法獲得的特征個數(shù)相比減少了10。綜上，本文提出的SOMMB算法可以在較少的特征個數(shù)下取得較高的分類準(zhǔn)確率。

本文將特征選擇應(yīng)用于醫(yī)學(xué)上對威斯康星州乳腺癌的診斷，數(shù)據(jù)來源于美國威斯康星大學(xué)醫(yī)院的臨床病例報告，共有11個屬性，具體描述如表4所示。

根據(jù)表4，可以用來特征提取的屬性共有九個，將這九個屬性全部用來預(yù)測癌癥結(jié)果，得到62.068%的準(zhǔn)確率；利用SOMMB算法先進(jìn)行特征選擇，使用降維后的特征預(yù)測癌癥的分類結(jié)果，得到65.517%的準(zhǔn)確率，與未經(jīng)過特征提取的分類結(jié)果比較，提高了約3%的準(zhǔn)確率。經(jīng)過算法提取特征后得到的有效特征為屬性5、屬性3、屬性1以及屬性2，且特征對分類結(jié)果的影響力排序為屬性5＞屬性3＞屬性1＞屬性2。從上述結(jié)果中可以得出結(jié)論，單上皮細(xì)胞尺寸是乳腺癌最主要的影響因素，在實際醫(yī)療檢查中，醫(yī)生可以首先選擇對單上皮細(xì)胞尺寸的篩查，為病人爭取治療的黃金時間。

為了驗證使用樣本重疊策略確定的特征具備更優(yōu)秀的分類性能，本文使用mRMR、RF、CBFS和ReliefF算法分別對特征進(jìn)行排序，接著采用三種策略分別決定所選的特征個數(shù)。其中，策略1為本文提出的樣本重疊策略；策略2為利用子集評價函數(shù)［24］，計算公式如下：J（S）=mSU（S，C）m+m（m-1）SU（S，S）（17）

其中：m為特征個數(shù)；S為當(dāng)前的特征集合；C為標(biāo)簽類別。

依次從mRMR、RF、CBFS和ReliefF算法確定的特征序列中選擇特征，直到所選特征子集的評價函數(shù)值開始下降為止。策略3為使用5折交叉驗證方法計算在KNN分類器下取得最高分類準(zhǔn)確率的特征個數(shù)，為了避免出現(xiàn)特征冗余，增加實驗的可比性，限制最大的特征個數(shù)為SOMMB算法確定的特征個數(shù)的兩倍。

本文將上述的三種策略結(jié)合mRMR、RF、CBFS和ReliefF算法作用于10個數(shù)據(jù)集上，得到了每組的準(zhǔn)確率和特征個數(shù)。為了便于比較，本文比較了不同數(shù)據(jù)集對應(yīng)的分類準(zhǔn)確率和所選特征個數(shù)曲線圖，如圖3、4所示，其中（a）～（d）分別表示mRMR、RF、CBFS以及ReliefF算法與三種策略結(jié)合的效果圖。

由圖3、4可以看出，使用策略1和3獲得的關(guān)鍵特征對分類器KNN來說，可以取得相近的分類準(zhǔn)確率，兩者均明顯高于使用策略2取得的分類精度，但均低于SOMMB算法取得的分類精度。從特征數(shù)量上分析，策略1選取的特征個數(shù)明顯少于策略3，對于Isolet數(shù)據(jù)集，策略1確定的特征數(shù)比策略3確定的特征數(shù)減少約50；策略2是三種策略中選取特征個數(shù)最少的一種方案。

為了進(jìn)一步綜合比較這三種策略的優(yōu)勢和缺點，本文分別計算了這三種策略結(jié)合mRMR、RF、CBFS和ReliefF算法在10個數(shù)據(jù)集上取得的平均準(zhǔn)確率和平均特征數(shù)，結(jié)果如表5所示。

由表5可知，使用樣本重疊策略選擇的特征可以取得最高的平均準(zhǔn)確率，值為73.905%，與使用5折交叉驗證的方法取得的準(zhǔn)確率相比高出0.539%，兩者均低于SOMMB算法取得的平均準(zhǔn)確率82.518 9%。使用子集評價函數(shù)確定的特征雖然數(shù)量最少，但無法取得較高的準(zhǔn)確率，其平均準(zhǔn)確率為65.883%，與使用樣本重疊策略相比，降低了8.022%的準(zhǔn)確率。

5 結(jié)束語

a）對強近似馬爾可夫毯進(jìn)行改進(jìn)，結(jié)合最大信息系數(shù)，在高維特征中去除冗余特征；b）將過濾法和包裝法結(jié)合，基于特征排序完成相關(guān)特征選擇，能夠有效縮短計算時間；c）提出樣本重疊這一策略決定特征個數(shù)，一方面避免了在特征選擇中人為設(shè)置恰當(dāng)?shù)拈撝底鳛橥Ｖ箿?zhǔn)則的問題，另一方面與準(zhǔn)確率相比，樣本重疊策略能夠更精準(zhǔn)地衡量新增的信息量。但近似馬爾可夫毯與其他的過濾式算法相比，計算時間較長，因此當(dāng)面向高維數(shù)據(jù)時，本文的算法存在耗時較長的缺點。

接下來將著重研究如何對近似馬爾可夫毯進(jìn)一步改進(jìn)以縮短計算時間；同時，在相關(guān)特征選擇的過程中，將準(zhǔn)確率和樣本重疊策略結(jié)合考慮，以獲得質(zhì)量更佳的關(guān)鍵特征。

參考文獻(xiàn)：

［1］李郅琴，杜建強，聶斌，等. 特征選擇方法綜述［J］. 計算機工程與應(yīng)用，2019，55（24）：10-19. （Li Zhiqin，Du Jianqiang，Nie Bin，et al. Summary of feature selection methods［J］. Computer Enginee-ring and Applications，2019，55（24）：10-19.）

［2］Dokeroglu T，Deniz A，Kiziloz H E. A comprehensive survey on recent metaheuristics for feature selection［J］. Neurocomputing，2022，494（7）：269-296.

［3］Moradi P，Gholampour M. A hybrid particle swarm optimization for feature subset selection by integrating a novel local search strategy［J］. Applied Soft Computing，2016，43（6）：117-130.

［4］Zaman E A K，Mohamed A，Ahmad A. Feature selection for online streaming high-dimensional data：a state-of-the-art review［J］. Applied Soft Computing，2022，127（9）：109355.

［5］Hu Zebiao，Yin Haishuang，Liu Yuanhong. Locally linear embedding vote：a novel filter method for feature selection［J］. Measurement，2022，190（2）：110535.

［6］章成旭，葉紹強，周愷卿，等. 基于粗糙集和改進(jìn)二進(jìn)制布谷鳥搜索算法的高維數(shù)據(jù)特征選擇［J］. 南京大學(xué)學(xué)報：自然科學(xué)版，2022，58（4）：584-593. （Zhang Chengxu，Ye Shaoqiang，Zhou kaiqin，et al. Feature selection of high dimensional data utilizing improved binary cuckoo search algorithm and rough set［J］. Journal of Nanjing University：Natural Science，2022，58（4）：584-593.）

［7］武小軍，周文心，董永新. 一種改進(jìn)的嵌入式特征選擇算法及應(yīng)用［J］. 同濟大學(xué)學(xué)報：自然科學(xué)版，2022，50（2）：153-159. （Wu Xiaojun，Zhou Wenxin，Dong Yongxin. A novel embedded feature selection algorithm and its application［J］. Journal of Tongji University：Natural Science，2022，50（2）：153-159.）

［8］許召召，申德榮，聶鐵錚，等. 融合信息增益比和遺傳算法的混合式特征選擇算法［J］. 軟件學(xué)報，2022，33（3）：1128-1140. （Xu Zhaozhao，Shen Derong，Nie Tiezheng，et al. Hybrid feature selection algorithm combing information gain ratio and genetic algorithm［J］. Journal of Software，2022，33（3）：1128-1140.）

［9］Li Jundong，Cheng Kewei，Wang Suhang，et al. Feature selection：a data perspective［J］. ACM Computing Surveys，2017，50（6）：article No.94.

［10］Hassan K M，Islam M R，Nguyen T T，et al. Epileptic seizure detection in EEG using mutual information-based best individual feature selection［J］. Expert Systems with Applications，2022，193（5）：116414.

［11］孫廣路，宋智超，劉金來，等. 基于最大信息系數(shù)和近似馬爾可夫毯的特征選擇方法［J］. 自動化學(xué)報，2017，43（5）：795-805. （Sun Guanglu，Song Zhichao，Liu Jinlai，et al. Feature Selection method based on maximum information coefficient and approximate Markov blanket［J］. Acta Automatica Sinica，2017，43（5）：795-805.）

［12］Reshef D N，Reshef Y A，F(xiàn)inucane H K，et al. Detecting novel associations in large data sets［J］. Science，2011，334（6062）：1518-1524.

［13］Nakariyakul S. High-dimensional hybrid feature selection using interaction information-guided search［J］. Knowledge-Based Systems，2018，145（4）：59-66.

［14］Peng Hanchuan，Long Fuhui，Ding C. Feature selection based on mutual information criteria of max-dependency，max-relevance，and min-redundancy［J］. IEEE Trans on Pattern Analysis and Machine Intelligence，2005，27（8）：1226-1238.

［15］Salem O A M，Liu Feng，Chen Y P，et al. Effective fuzzy joint mutual information feature selection based on uncertainty region for classification problem［J］. Knowledge-Based Systems，2022，257（12）：109885.

［16］Souza F，Premebida C，Araújo R. High-order conditional mutual information maximization for dealing with high-order dependencies in feature selection［J］. Pattern Recognition，2022，131（11）：108895.

［17］張俐，袁玉宇，王樅. 基于最大相關(guān)信息系數(shù)的FCBF特征選擇算法［J］. 北京郵電大學(xué)學(xué)報，2018，41（4）：86-90. （Zhang Li，Yuan Yuyu，Wang Zong. FCBF feature selection algorithm based on maximum information coefficient［J］. Journal of Beijing University of Posts amp; Telecommunications，2018，41（4）：86-90.）

［18］Kishore B，Ananthamoorthy N P. Correlation-based feature selection using bio-inspired algorithms and optimized KELM classifier for glaucoma diagnosis［J］. Applied Soft Computing，2022，128（10）：109432.

［19］Ezenkwu C P，Akpan U I，Stephen B U A. A class-specific metaheuristic technique for explainable relevant feature selection［J］. Machine Learning with Applications，2021，6（12）：100142.

［20］孫林，黃苗苗，徐久成. 基于鄰域粗糙集和Relief的弱標(biāo)記特征選擇方法［J］. 計算機科學(xué)，2022，49（4）：152-160. （Sun Lin，Huang Miaomiao，Xu Jiucheng. Weak label feature selection method based on neighborhood rough sets and Relief［J］. Computer Science，2022，49（4）：152-160.）

［21］Kononenko I. Estimating attributes：analysis and extensions of RELIEF［C］//Proc of European Conference on Machine Learning. Berlin：Springer-Verlag，1994：171-182.

［22］García-Torres M，Gómez-Vela F，Melián-Batista B，et al. High-dimensional feature selection via feature grouping：a variable neighborhood search approach［J］. Information Sciences，2016，326（1）：102-118.

［23］Manikandan G，Abirami S. An efficient feature selection framework based on information theory for high dimensional data［J］. Applied Soft Computing，2021，111（11）：107729.

［24］Hua Zhongsheng，Zhou Jian，Hua Ye，et al. Strong approximate Markov blanket and its application on filter-based feature selection［J］. Applied Soft Computing，2020，87（2）：105957.

［25］李靜星，楊有龍. 針對高維數(shù)據(jù)的馬爾可夫毯特征選擇［J］. 計算機工程與應(yīng)用，2021，57（6）：58-66. （Li Jingxing，Yang Youlong. Feature selection of Markov blanket for high dimensional data［J］. Computer Engineering and Applications，2021，57（6）：58-66.）

［26］Lichman M. UCI machine learning repository［DB/OL］. （2015-11-10）. https：//archive. ics.uci.edu/ml.

［27］Li Jundong，Cheng Kewei，Wang Suhang，et al. Feature selection：a data perspective［J］. ACM Computing Surveys，2017，50（6）：102-118.

收稿日期：2022-08-05；修回日期：2022-09-27 基金項目：國家重點研發(fā)計劃資助項目（2020YFB1708202）

作者簡介：王大志（1978-），男，沈陽人，副教授，博導(dǎo)，博士，主要研究方向為系統(tǒng)建模與優(yōu)化、特征選擇；季焱晶（1999-），女（通信作者），碩士研究生，主要研究方向為特征選擇、機器學(xué)習(xí)（1095458576@qq.com）；陳彥樺（1996-），男，博士研究生，主要研究方向為特征選擇、風(fēng)險控制；王洪峰（1979-），男，教授，博導(dǎo)，主要研究方向為復(fù)雜系統(tǒng)建模優(yōu)化；黃敏（1968-），女，長江學(xué)者，教授，主要研究方向為物流供應(yīng)鏈．