王波,李時輝,鄭鵬飛

?

小樣本數(shù)據(jù)的MIFS過濾式特征選擇算法

王波,李時輝,鄭鵬飛

義烏工商職業(yè)技術(shù)學(xué)院, 浙江 義烏 322000

針對小樣本數(shù)據(jù)特征選擇以及最佳特征難確定的問題，本文提出一種MIFS過濾式特征選擇算法，同時結(jié)合Boruta算法，旨在降低數(shù)據(jù)集維度，確定出最佳特征的子集。通過實驗結(jié)果與分析，對比其它三種傳統(tǒng)的過濾式算法，驗證本文算法的有效性。結(jié)果表明：MIFS-Boruta算法體現(xiàn)出更廣的特征選擇量，并且平均最低分類錯誤率最低。

小樣本; MIFS; 算法

隨著互聯(lián)網(wǎng)及信息技術(shù)的發(fā)展，大數(shù)據(jù)應(yīng)用越來越普遍，但在實際生活中，小樣本數(shù)據(jù)依然不可或缺。例如基因分析數(shù)據(jù)就是一種典型的小樣本數(shù)據(jù)，主要由微陣列實驗進行獲取，而實驗成本一般比較昂貴，這對實驗次數(shù)產(chǎn)生了限制。整個基因分析數(shù)據(jù)規(guī)模較小，但數(shù)據(jù)維數(shù)很高，若采用傳統(tǒng)型的機器學(xué)習(xí)算法進行處理，容易導(dǎo)致數(shù)據(jù)失效。而利用特征選擇降低數(shù)據(jù)的維數(shù)，則是一種較為有效的解決辦法。特征選擇有利于去除數(shù)據(jù)的不相關(guān)性和冗余性，提升數(shù)據(jù)本身的質(zhì)量，減少數(shù)據(jù)集計算的代價，進而使數(shù)據(jù)挖掘變得更快[1]。常用的特征選擇方法有過濾法、封裝法和嵌入法[2]。過濾法是直接進行數(shù)據(jù)訓(xùn)練并評估數(shù)據(jù)性能的方法，根據(jù)評估結(jié)果去除相關(guān)性小、冗余度高的數(shù)據(jù)，與分類算法沒有關(guān)聯(lián)。封裝法和嵌入法都需要進行后續(xù)的分類計算，數(shù)據(jù)的維數(shù)越高，計算成本就會越大，不太適合小樣本數(shù)據(jù)特征的選擇。過濾法的評估函數(shù)是獨立的，在其評估標準中不會納入任何分類器，選出的特征子集與特定的分類算法無關(guān)，因此計算成本較低[3]。過濾法與另外兩種方法相比，計算也更加的高效。Kamatchi等對小樣本數(shù)據(jù)特征冗余性進行考慮，同時結(jié)合特征類型的區(qū)分能力，給出一致性度量的標準，若給定樣本之間的特征值相同，類別也相同，則可以判斷樣本是一致的，以此為基礎(chǔ)進行數(shù)據(jù)過濾[4]。Bernick等研究了過濾式特征選擇法，認為過濾法可以對特征之間的關(guān)系、特征和類型之間的關(guān)系進行很好的度量，進而使特征選擇變得更加有效[5]。本文研究了MIFS過濾式特征選擇算法，并結(jié)合Boruta算法進一步拓展，實驗證明本算法有效性較高。

1 MIFS特征選擇算法的基本步驟與拓展

1.1 MIFS特征選擇算法的基本步驟

對于小樣本數(shù)據(jù)來說，特征選擇不僅要對特征和類型之間的關(guān)聯(lián)性進行考慮，還要考慮不同特征可能產(chǎn)生的冗余性，當特征和類型關(guān)聯(lián)度有較大差別時，需要進一步避免冗余度的計算。根據(jù)以上問題的考慮，本文采用MIFS（MI-haled feature selection）算法，根據(jù)小樣本數(shù)據(jù)度量特征和類型的關(guān)系，首先按照兩者的關(guān)聯(lián)性進行特征排序，然后在一定標準下將特征分組，從中找出所需的特征組成特征子集。

設(shè)特征子集的數(shù)據(jù)集所擁有的樣本數(shù)量為，特征維度的數(shù)量為，而特征則用1,2,…,a

表示，類型用表示，用V表示a的值域，用V表示的值域。通過以上假設(shè)，a和的特征選擇指數(shù)(a,)計算公式如下：

在上式中，(?,?)代表a取值?且取值?的概率，特征選擇指數(shù)(a,)值越大，特征與類型之間的關(guān)聯(lián)程度就越高。根據(jù)式（1）依次計算每一個特征和類型的特征選擇指數(shù)，然后按照特征選擇指數(shù)的大小，從高到低排序，并進一步分組特征子集，依據(jù)的標準為，該值用以下公式計算：

在上式中，代表一個特征組，S是和類型的關(guān)聯(lián)度，R是里面全部特征的相似性。進一步計算S和R：

在上式中，里面的特征為a，a，(a,a)則是a和a的特征選擇指數(shù)，用以下公式計算：

在上式中，(?,?)代表a取值?且a取值?的概率，特征選擇指數(shù)(a,a)值越大，說明a與a越相似。同樣道理，的值越高，該特征組的特征和類型關(guān)聯(lián)度就越大，而組內(nèi)各特征的冗余度就越小。反之亦然。為計算的初始值，需要在分組中放入2個通過選擇的特征：第一個特征是排在首位的1；第二個特征需要計算1和另外各特征a的特征選擇指數(shù)，得出特征選擇指數(shù)值最大的特征，該特征與1最為相似。最后根據(jù)式（2）對標準值進行計算，記成0。

相對于另外的特征來說，將排在首位的特征在分組中添加并計算值，若≤0，則說明這個特征與其它特征有著較高的冗余度，這時需要進一步添加下一個特征，對新值進行計算并迭代，一直到>0為止，才停止添加特征。這時得到的特征組是第一個分組，沒有進入該特征組的其它特征可以重復(fù)上面的步驟，產(chǎn)生新的一個特征組，最后目標是全部特征都分配到相應(yīng)特征組內(nèi)。候選特征子集則由每一個特征組首個特征所組成。根據(jù)以上分析，MIFS算法的基本步驟如下：

輸入數(shù)據(jù)：特征子集的數(shù)據(jù)集、候選特征數(shù)。

輸出數(shù)據(jù)：候選特征子集S。

第1步：根據(jù)式（1）計算特征子集的數(shù)據(jù)集內(nèi)每一個特征和類型的特征選擇指數(shù)(a,)；

第2步：根據(jù)特征選擇指數(shù)的大小，從高到底進行排序，得出目標特征集；

第3步：使=1，從特征集內(nèi)取出排首位的特征1，放進特征組G；

第4步：根據(jù)式（3）對1和另外每一個特征a的特征選擇指數(shù)(a,a)進行計算，取最大值特征放進特征組G；

第5步：根據(jù)式（2）對G的值進行計算，記成0。

第6步：從目標特征集的剩余特征里，取排在首位的特征放進特征組G，根據(jù)式（2）對G的值進行計算，若≤0，重復(fù)第5步，若>0，當前的特征組G即可作為首個分組；

第7步：使=+1，從目標特征集的剩余特征里，繼續(xù)重復(fù)第3步到第6步，得出新特征組G，一直到=為止，或者目標特征集的剩余特征全部被分配到特征組；

第8步：取每一個特征組的首個特征，放進候選特征子集S；

第9不：返回候選特征子集S。

1.2 MIFS特征選擇算法的拓展

MIFS特征選擇算法雖然能夠利用特征分組逐步去除冗余特征，但與許多傳統(tǒng)型的過濾算法一樣，很難確定出最佳特征，這就需要進一步拓展該算法，即將MIFS算法與其它能夠有效確定最佳特征的算法相結(jié)合。本文選取了Boruta算法進行結(jié)合，形成一種新的MIFS-Boruta算法。Boruta屬于一種全覆蓋型的特征選擇算法，其優(yōu)勢在于信息預(yù)測，而不考慮關(guān)聯(lián)度的高低，能夠根據(jù)信息預(yù)測找出全部的相關(guān)特征，因此比較適合最佳特征的確定。

在MIFS-Boruta算法中，可以對過濾后的結(jié)果進行充分利用，不斷提高算法的運行效率，同時強化特征子集的分類性能。MIFS-Boruta算法還能確定特征子集內(nèi)的特征數(shù)量，與過濾算法形成良好的互補。該算法的主要目標是提升特征選擇算法的效果，能夠自動選擇冗余度及維數(shù)更小的特征，以確定最佳特征，基本計算步驟如下：

輸入數(shù)據(jù)：特征子集的數(shù)據(jù)集、候選特征數(shù)、迭代數(shù)。

輸出數(shù)據(jù)：特征子集。

第1步：在中進行MIFS計算，得出含有個候選特征的S；

第2步：從中取出S相對應(yīng)的數(shù)據(jù)組成新數(shù)據(jù)集D；

第3步：在D中進行Boruta計算，迭代數(shù)為；

第4步：返回特征子集。

在MIFS特征選擇算法初始階段，會選擇與特征選擇指數(shù)最接近的特征放入最新特征組中，并作為各特征組的代表，被選為最優(yōu)特征子集中的候選特征。這時需要通過Boruta算法從這些候選特征里面除去一些次要的特征，但是特征選擇指數(shù)值最高的特征有著很強的分類效果，這樣的特征不會被除去，而會在最優(yōu)特征子集中得到保留。

2 結(jié)果與分析

2.1 實驗數(shù)據(jù)

為驗證本文算法在高緯度小樣本數(shù)據(jù)中的有效性，選擇了9個公開的數(shù)據(jù)集，所有特征的維數(shù)在1024~18847之間，平均維度為7297，有5個數(shù)據(jù)集的維數(shù)大于5000，有2個數(shù)據(jù)集的維數(shù)大于10000，主要類型是圖像數(shù)據(jù)和生物學(xué)數(shù)據(jù)，如表1所示。

2.2 各算法特征選擇的結(jié)果對比

為驗證本文算法能否得到更好的特征選擇結(jié)果，引入ICAP、CMIM、CIFE三種較為典型的特征選擇算法，都屬于傳統(tǒng)的過濾式算法。為了使對比公平，在實驗里分別將這三種算法結(jié)合Boruta算法，在每一個樣本集中設(shè)定好候選特征數(shù)量，各算法最終選擇出來的特征個數(shù)如表2所示。實驗結(jié)果表明，任何一種算法的特征選擇數(shù)都低于原始特征的維度，而在9個數(shù)據(jù)集中，MIFS-Boruta算法有6個數(shù)據(jù)集的特征數(shù)最多，體現(xiàn)了更廣的特征選擇量。

表 1 實驗數(shù)據(jù)統(tǒng)計

表 2 不同算法組合Boruta得出的特征選擇結(jié)果

2.3 各算法特征子集的分類性能對比

為驗證本文算法對于特征選擇的有效性，依然以ICAP、CMIM、CIFE三種較為典型的特征選擇算法作對比，分別在支持向量機監(jiān)督學(xué)習(xí)模型上進行計算，實驗采用以下2個指標驗證性能：（1）最低分類錯誤率；（2）平均最低分類錯誤率。對比結(jié)果如表3所示。MIFS算法共有7個數(shù)據(jù)集的最低分類錯誤率最低，而且平均最低分類錯誤率也是最低，相對于其它算法來說有著良好的表現(xiàn)。

表 3 不同算法在支持向量機上的分類錯誤率統(tǒng)計（%）

3 討論

小樣本理論創(chuàng)始于十九世紀初，在區(qū)間估計和統(tǒng)計假設(shè)檢驗等領(lǐng)域得到廣泛應(yīng)用。小樣本統(tǒng)計省錢省力，極大地節(jié)約了計算的時間，不僅受到統(tǒng)計學(xué)家的歡迎，還被工業(yè)、農(nóng)業(yè)、科學(xué)研究等領(lǐng)域的工作者所重視。從此次實驗結(jié)果看，本文提出的算法在高緯度小樣本數(shù)據(jù)中的特征選擇較為有效，能夠取得更好的特征選擇結(jié)果。Ekiz等認為小樣本數(shù)據(jù)的特征維數(shù)較多，而且具備冗余特征，可以利用特征選擇的方法降低數(shù)據(jù)維數(shù)[6]。Brewer等提出一種面向高維數(shù)據(jù)的迭代式特征選擇方法，主要是改進了Lasso方法，實驗結(jié)果表明，該方法可以較好地選擇高維小樣本數(shù)據(jù)集特征，屬于當前比較有效的特征選擇法[7]。Dahl等基于粒計算角度，提出一種?；诤峡蚣芟碌母呔S數(shù)據(jù)特征選擇算法，首先將原始數(shù)據(jù)集?；尚∫?guī)模的數(shù)據(jù)子集，并在每一個粒上建立起若干個套索模型，從而實現(xiàn)粒特征的選擇，然后根據(jù)權(quán)重情況融合各粒特征的選擇結(jié)果[8]。

4 結(jié)論

本文針對小樣本數(shù)據(jù)特征選擇問題，采用MIFS算法進行特征分組計算，選出最大相關(guān)性的特征，降低數(shù)據(jù)集維度。為解決最佳特征難以確定的問題，拓展了MIFS算法，提出一種MIFS-Boruta算法，在降低數(shù)據(jù)集維度的基礎(chǔ)上，還能確定出最佳特征的子集。通過實驗分析，驗證了該算法的有效性。但是該算法涉及到的候選特征數(shù)量，需要通過人工方式進行設(shè)定，若數(shù)值偏大將會對最終的特征選擇效率造成一定影響，若數(shù)值偏小則會對選出的特征性能造成影響，所以這方面還有待于進一步研究。

[1] Ditlevsen O. Baysian estimation of(>) from a small sample of Gaussian data[J]. Structural safety, 2017,68(4):110-113

[2] Lunardon N, Scharfstein D. Comment on "Small sample GEE estimation of regression parameters for longitudinal data"[J]. Statistics in medicine, 2017,36(22):3596-3600

[3] McNeish DH, Jeffrey R. Correcting Model Fit Criteria for Small Sample Latent Growth Models With Incomplete Data [J]. Educational and Psychological Measurement, 2017,77(6):990-1018

[4] Kamatchi PMK, Kavitha DSN. Data analytics: feature extraction for application with small sample in classification algorithms[J]. International journal of business information systems, 2017,26(3):378-401

[5] Bernick CB, Guogen SS. Sample size determination for a matched-pairs study with incomplete data using exact approach[J]. The British journal of mathematical and statistical psychology, 2018,1(1):60-74

[6] Kirubavathi G, Anitha R. Structural analysis and detection of android botnets using machine learning techniques[J]. International Journal of Information Security, 2018,17(2):153-167

[7] Brewer RP, John HM. A Critical Review of Discrete Soil Sample Data Reliability: Part 2-Implications[J]. Soil & Sediment Contamination, 2017,26(1):23-44

[8] Dahl JB. Mathiesen O, Karlsen APH. Evolution of bias and sample size in postoperative pain management trials after hip and knee arthroplasty[J]. Acta Anaesthesiologica Scandinavica, 2018,62(5):666-676

MIFS Filtering Feature Selection Algorithm for Small Sample Data

WANG Bo, LI Shi-hui, ZHENG Peng-fei

322000

Aiming at the problem of feature selection for small sample data and the difficulty of determining the best feature, a MIFS filtering feature selection algorithm was proposed, which combined Boruta algorithm to reduce the dimension of data set and determine the subset of the best feature. Through the experimental results and analysis, comparing with the other three traditional filtering algorithms, the effectiveness of the proposed algorithm was verified. The results showed that MIFS-Boruta algorithm had broader feature selection and the lowest average classification error rate.

Small sample; NIFS; algorithm

TP301.4

A

1000-2324(2019)01-0145-05

10.3969/j.issn.1000-2324.2019.01.033

2018-03-26

2018-05-04

浙江省自然科學(xué)基金:具有公共自行車子網(wǎng)的城市公交網(wǎng)絡(luò)建模與優(yōu)化研究(LY17F030016)

王波(1982-),男,博士,副教授,主要研究方向為自動化技術(shù)、計算機技術(shù). E-mail:52672026@qq.com