小樣本數據的MIFS過濾式特征選擇算法

王波,李時輝,鄭鵬飛

?

小樣本數據的MIFS過濾式特征選擇算法

王波,李時輝,鄭鵬飛

義烏工商職業技術學院, 浙江 義烏 322000

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

小樣本; MIFS; 算法

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

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

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

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

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

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

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

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

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

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

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

輸入數據：特征子集的數據集、候選特征數。

輸出數據：候選特征子集S。

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

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

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

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

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

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

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

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

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

1.2 MIFS特征選擇算法的拓展

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

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

輸入數據：特征子集的數據集、候選特征數、迭代數。

輸出數據：特征子集。

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

第2步：從中取出S相對應的數據組成新數據集D；

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

第4步：返回特征子集。

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

2 結果與分析

2.1 實驗數據

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

2.2 各算法特征選擇的結果對比

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

表 1 實驗數據統計

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

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

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

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

3 討論

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

4 結論

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

[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

浙江省自然科學基金:具有公共自行車子網的城市公交網絡建模與優化研究(LY17F030016)

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