基于最小最大模塊化集成特征選擇的改進

周 豐，王未央

(上海海事大學信息工程學院，上海 201306)

基于最小最大模塊化集成特征選擇的改進

周 豐，王未央

(上海海事大學信息工程學院，上海 201306)

隨著數據規模的擴大，單個弱分類器的準確率已經無法很好地對未知樣本進行預測，為此提出了集成學習。在集成學習與分類器結合的同時，集成的思想同樣被用到了特征選擇中。從提高對樣本預測的準確率的角度出發，提出一種基于最小最大模塊化(Min-Max-Module，M3)的策略。它同時將集成學習應用到了特征選擇算法和分類器中，并對比了四種集成策略以及三種不同的分類方法。結果表明，提出的方法在大多情況下能取得不錯的效果，并且能很好地處理不平衡的數據集。

特征選擇;集成學習;最小最大模塊化策略;不平衡數據

1 概述

隨著各個領域涌現出的大量數據，機器學習與數據挖掘已經被應用到各行各業。但是現實生活中的數據非常復雜，平滑干凈的數據非常難得，大部分的數據中都有缺失值、異常值等噪聲。此時，數據預處理顯得格外重要。為了提高機器對這些數據的處理能力，可以通過一定的數學方法(如牛頓插值法、拉格朗日插值法等)進行處理，而特征選擇作為降低數據維度、平滑噪聲的一種有效方法，成為了研究熱點［1］。

在數據挖掘中，海量的原始數據中存在著大量不完整、不一致、有異常的數據，它們會嚴重影響到數據挖掘建模的執行效率，所以數據清洗尤為重要。數據清洗主要是刪除原始數據集中的無關數據、重復數據、平滑噪聲數據，篩選掉與挖掘主題無關的數據，處理缺失值、異常值等［2］。處理缺失值和異常值，通常有刪除記錄、數據插補和不處理等方法，而異常值一旦被檢測到，往往可以當作缺失值處理。常用的方法有均值/眾數/中位數插補法、固定值法、最近鄰插補、回歸方法以及插值法。插值法一般有拉格朗日插值法和牛頓插值法，文中使用牛頓插值法。箱型圖分析提供了識別異常值的標準:異常值通常被定義為小于QL-1.5IRQ或大于QU+1.5IRQ的值。其中，QL為下四分位數; QU為上四分位數;IRQ為四分位數間距，IRQ=QU-QL。

特征選擇是從特征集合中挑選出滿足一定評價準則的特征子集的過程，特征選擇過程可以除去不相關的冗余特征［1-2］，從而達到降維的目的。特征選擇算法一般分為四類:過濾器、封裝器、嵌入式和組合。過濾器最大的特點是直接從特征固有的性質出發來評判特征的重要性，并不考慮分類器，該類方法具有較高的效率，如Fisher［3］、Relief［4］等。封裝器則是依賴于分類器，它采用分類器來評價性能，這種方法采用搜索策略來尋找最優特征子集，其搜索策略有前向搜索、后向搜索、隨機搜索等，準確率較高但是效率較低。嵌入式則是在構建分類器的過程中進行特征選擇。而組合式先采用過濾器去除一些特征，再對剩下的特征子集采用封裝器進行搜索，結合了過濾器和封裝器的優點。

目前，數據量在不斷增長，傳統的特征選擇方法的效率顯然已經無法跟上數據增長的腳步［1］。為了更好地處理大規模數據，Hoi［5］等結合在線特征選擇和一種嵌入式算法，將原始數據轉換為序列型的數據;Wu［6］等使用在線流式特征選擇的方法。以上兩種方法都能明顯地提升對大規模數據的處理能力。

文中使用的是集成的方法，主要步驟包括:結合箱型圖分析和牛頓插值法對數據進行缺失值和異常值分析;再通過某種策略將數據劃分，從而將原始特征選擇和分類任務劃分為多個較小的相互獨立的可并行計算的子任務，每一個子任務同時進行特征選擇以及分類算法;最后利用最小最大策略將分類結果進行集成。

2 集成學習

2.1 集成學習的概念與框架

與傳統的單個學習模型相比，集成學習則是通過同時構建多個不同的基學習模型，并使用某種策略把多個模型的學習結果進行組合，從而獲得最終的學習結果。

此外，集成思想與特征選擇相結合，用以提高特征選擇的穩定性［2，7-9］。大量的理論研究和實際應用表明，集成學習有利于構建性能更好的學習模型。集成學習在分類問題中大致分為兩個步驟。首先，根據數據集訓練出多個不同的分類器;然后，將未知數據在不同分類器上的預測結果通過某種策略進行匯總，整合成最終的預測結果。匯總的策略有投票法、權重法、聚類法等。

常見的集成策略有以下幾種，如 Bagging、Ada-Boost、M3、RandomSpace等。該實驗使用基于M3的集成策略對結果進行集成，特征選擇算法使用了Fisher 與ReliefF;分類算法使用經典的、準確率較高的支持向量機，并與單個支持向量機分類器和樸素貝葉斯三者之間進行比較。

2.2 集成的策略

在每個子任務結束后，需要將每個任務的結果以某種方法集成起來，文中將介紹與對比四個集成的策略:均值法、投票法、K-中心聚類法以及最小最大集成策略。此處主要介紹前三種:

投票法對于特征選擇而言是先將結果轉換為特征子集，然后統計每個特征被選中的情況，將出現次數最多的M個特征作為最終輸出特征;同理對于分類而言則是統計每一個子分類器對同一個樣本預測的結果，取票數最高的作為輸出;

均值法將子任務返回的結果進行線性相加取均值得到最后的輸出;

K-中心聚類集成是應用了聚類的思想，從多個子任務中選擇具有代表性的結果作為輸出。相比前兩種方法，該方法可以保護特征之間的關聯性。文中采用了1-中心聚類集成。

3 最小最大集成策略

基于最小最大模塊化(Min-Max-Module，M3)的分類集成策略最早由Lu［10］等提出。該策略主要包含兩個步驟:任務分解和分類結果的合成。

3.1 任務分解

在任務分解階段，對于一個K類的分解問題，首先采用“一對一”的策略將其分解為K(K-1)/2個二分類問題。假設K類的訓練數據集表示為:其中，Li表示第i類樣本的個數;xil表示第i類樣本中的第l個樣本;yi表示第i類樣本對應的標簽。

那么通過“一對一”的策略，第i類樣本和第j類樣本組成的二分類問題的訓練數據集可以表示為:

如果二分類問題的規模較大或者具有不平衡性，可以進一步將它們劃分成規模更小的較為平衡的子問題。

任務分解方法包括基于隨機的分解方法和基于超平面的分解方法。該實驗中使用基于超平面的方法，其具體過程如算法1所示。假設把Ci類的訓練樣本分解成Ni個子集，把Cj類的訓練樣本分解成Nj個子集。這樣就可以把Ci類和Cj類的二分類問題分解成Ni×Nj個子二分類問題進行解決［11］。

算法1:基于超平面的數據集分塊方法。

輸入:某k類問題第i類的訓練樣本Xi，i=1，2，…，k。

(1)計算Ci類的每個訓練樣本x與超平面Z1+Z2+…+Zn=0的距離。

其中，xj，j=1，2，…，n是樣本x的分量。

(2)根據已經計算的dist(x，H)的值，對Ci類的訓練樣本進行排序，即把Ci類的訓練樣本按空間分布進行排序。

(3)把已經排序的訓練樣本按前后順序劃分成Ni份，每一份的訓練樣本個數近似相等(相差不超過一個)，即把該類訓練樣本的分布空間分割成Ni個部分，但不是分割后的空間相等，而是保證各個部分空間中包含的樣本個數相等。

3.2 分類結果集成

通過對第i類樣本和第j類樣本組成的二分類問題進行進一步的劃分，從而得到Ni×Nj個二分類子問題，然后在每個子問題對應的訓練數據集上訓練相應的分類器，得到Ni×Nj個基分類器，表示為:

對于測試樣本，使用這些基分類器分別對其進行預測，得到預測標簽:

對于預測結果，分別采用最小規則和最大規則進行合成:

MIN規則:是對擁有相同正類訓練樣本集和不同負類訓練樣本集的分類結果取最小值;

MAX規則:是對擁有相同負類訓練樣本集和不同正類訓練樣本集的分類結果取最大值。

該分類集成策略的整體流程如下:

算法2:基于最小最大規則的集成算法。

輸入:訓練集X，測試樣本e，第i類樣本的劃分塊數Ni，數據劃分方法P;

輸出:測試樣本的預測標簽O。

訓練與測試階段:

將K類樣本X劃分為X1，X2，…，Xk

3.3 最小最大策略的集成特征選擇以及分類

傳統的基于最小最大策略的分類是先將數據集進行特征選擇等預處理，再利用上文提到的數據劃分方法將數據劃分為M×N個樣本子集，再將數據塊進行合并分類，對每一個樣本都有M×N個預測標簽，再利用最大最小策略可以得到每一個樣本最終的預測標簽作為輸出［12］。

傳統的基于最小最大策略的集成特征選擇則是先使用上文提到的數據劃分方法進行數據劃分，得到M ×N個樣本子集，然后在每個樣本子集上進行特征選擇，得到M×N個特征選擇結果。最后利用最小化集成單元和最大化集成單元對這多個特征選擇結果進行組合［12-15］。

文中提出的方法是結合以上兩種傳統的集成方法，將特征選擇和分類同時使用最小最大模塊化進行集成，先進行數據分塊，對每一個數據子集進行特征選擇，并優先對特征選擇集成。同時，保存劃分的數據子集，在得到最優特征子集之后，更新數據子集并對新的數據子集進行分類集成，從而得到最后的結果。其過程如圖1所示。

圖1 基于最小最大規則集成分類特征選擇的框架

4 實驗及仿真

4.1 實驗步驟

文中所做的相關工作及實驗步驟為:

(1)對原始數據做箱型圖處理，尋找異常值并刪除，再將排除完異常值的數據集運用牛頓插值法(完成異常值和缺失值的處理過程具體見算法1)。

(2)接下來對數據進行標準化、歸一化處理，區間為［0，1］。

(3)對處理好的數據進行十字交叉驗證或者直接進行訓練集和測試集的按比例劃分。

(4)對訓練樣本和測試樣本分別使用基于超平面的方法得到若干較小數據子集，對每個數據子集使用相同的特征選擇算法，得到降維之后的數據。

(5)用降維之后的數據更新之前的數據子集，并對每個數據子集使用支持向量機算法進行分類。

(6)根據最小最大規則對分類結果進行集成得到最終輸出。

本節通過實驗結合了基于最小最大策略的分類算法和特征選擇算法，分別對比ReliefF和Fisher特征選擇算法、投票法、均值法、K-中心聚類法以及最小最大策略對分類準確率的影響。在集成方面，將文中提出的方法與傳統的M3-SVM和M3-Na?ve Bayes方法進行對比。實驗數據集為PCMAC和Adult。

4.2 實驗準備

(1)實驗數據集。

PCMAC數據集包含1 943條樣本，每條樣本有3 290維屬性，包含了若干異常值和缺失值，標簽一共有兩類，是一個低數據量高維的樣本。文中對其進行十字交叉驗證，得到訓練樣本和測試樣本。該數據集具體的分布情況如表1所示。

Adult數據集包含32 561條樣本，124維屬性，同時包含了異常值和缺失值，一共有兩類標簽。文中訓練集包含22 696條樣本，測試集9 865條樣本，具體分布如表2和表3所示。

需要說明的是，由于M3希望盡可能地保持每個子數據塊的樣本數相似，故對M3的分塊個數需要針對樣本個數區分，這樣也能很好地處理不平衡數據集。

(2)分類器的選擇及評價準則。

文中采用的分類器算法是支持向量機。支持向量機有良好的學習能力和泛化能力，主要思想是:對于樣本的輸入空間，構造一個最優的超平面，使得超平面到兩類樣本之間的距離最大化。它遵循結構風險最小化的原則，使得錯誤概率上界最小化，因此還可以有效減小過擬合。在支持向量機中，文中采用高斯核函數，其Sigmod值設置為2，損失函數C設置為32，采用SMO算法計算其參數。

對于分類結果的評價采用錯誤率度量標準，但是錯誤率不考慮類別之間的不平衡。對于平衡數據，常采用準確率或錯誤率來衡量;對于不平衡數據，常采用的評價標準包括ROC曲線、AUC、F-Measure和GMean等。文中采用G-Mean。

其中，TP表示正類樣本被正確分類的個數;FN表示正類樣本被錯誤分類的個數;TN表示負類樣本被正確分類的個數;FP表示負類樣本被錯誤分類的個數。

4.3 實驗結果

4.3.1 在PCMAC數據集上的實驗結果

該數據集樣本數較少，維數較高，且為平衡數據集，在該樣本上使用了Fisher特征選擇算法。

(1)使用ReliefF特征選擇算法。

基于超平面劃分數據后，對每一個數據子集使用Fisher特征選擇算法后使用SVM作為分類器，分別采用四種不同的集成策略以G-Mean為標準進行對比，如圖2所示。

圖2 不同集成策略對比圖(1)

對文中提出的集成特征選擇(FSE)結合集成分類(CFE)與傳統的FSE進行對比，并通過傳統的FSE對比了SVM和NB兩個分類器的效果，如圖3所示。

圖3 集成算法與單個算法對比圖(1)

4.3.2 在Adult數據集上的實驗結果

該數據集樣本數較多，且不平衡，屬性個數較少，此處僅采用了ReliefF特征選擇算法，同樣對比了文中提出的FSE+CFE與傳統的集成特征選擇，實驗結果如圖4和圖5所示。

圖4 不同集成策略對比圖(2)

4.3.3 實驗結果分析

實驗主要對比了四種集成策略:均值法、投票法、K-中心聚類法以及基于最小最大策略(分別記為Mean.Weight、Voting、K.Medoid、MIN.MAX)。并對比了三種不同的分類方法:基于最小最大策略的集成特征選擇與集成分類結合方法、傳統的集成特征選擇結合SVM、傳統的集成特征選擇結合樸素貝葉斯(分別記為M3.SVM、SVM、NB)。數據劃分部分使用了超平面劃分，特征選擇算法使用了ReliefF和Fisher，使用GMean作為評價準則。實驗數據集使用PCMAC和A-dult，前者樣本較少、特征較多，故采用10次交叉驗證。

根據實驗結果，在樣本較少特征較多的PCMAC中，文中提出的M3-FS結合M3-SVM的效果明顯優于其他集成策略和分類方法，特別是選取60至80維特征。對于大量低維的樣本Adult，由圖4、圖5可見，四種集成策略具有相似的結果及趨勢;在分類器選擇方面，文中提出的M3-FS結合M3-SVM的效果優于M3-FS結合SVM以及M3-FS結合NB。同時可以看出，使用M3的正負類樣本分別分塊策略也能很好地處理Adult這個不平衡的數據集。

綜上所述，從分類準確率的角度，文中提出的方法在大部分情況下均優于其他方法。

5 結束語

文中提出了一種對傳統的集成特征選擇方法加以改進的方法，即將分類集成與特征選擇的集成結合起來，以有效地提高對大規模數據的處理能力。該方法通過基于超平面的方法將數據劃分成多個數據子集，將原來的任務轉換為可同時進行的多個獨立的子任務，然后使用最小最大集成單元對分類結果進行集成，得到最終的預測標簽。通過比較，實驗結果表明在四種集成策略中，最小最大集成策略是占有一定的優勢的。在面對傳統的特征選擇集成方法中，在準確率方面，結合分類集成的方法的效果更為理想。

［1］ Tang J L，Alelyani S，Liu H.Feature selection for classification:a review［M］.Florida:The Chemical Rubber Company Press，2013.

［2］ Li Y，Gao S，Chen S.Ensemble feature weighting based on local learning and diversity［C］//Proc of AAAI conference on artificial intelligence.［s.l.］:［s.n.］，2012.

［3］ Gu Q，Li Z，Han J.Generalized fisher score for feature selection［C］//Proceedings of the twenty-seventh conference on uncertainty in artificial intelligence.Barcelona，Spain:［s.n.］，2011.

［4］ Robnik-?ikonja M，Kononenko I.Theoretical and empirical analysis of ReliefF and RReliefF［J］.Machine Learning，2003，53(1-2):23-69.

［5］ Hoi S C H，Wang J，Zhao P，et al.Online feature selection for mining big data［C］//Proc of international workshop on big data，streams and heterogeneous source mining:algorithms，systems，programming models and applications.［s.l.］:ACM，2012:93-100.

［6］ Wu X，Yu K，Wang H，et al.Online streaming feature selection ［C］//Proc of international conference on machine learning. ［s.l.］:［s.n.］，2010:1159-1166.

［7］ Woznica A，Nguyen P，Kalousis A.Model mining for robustfeature selection［C］//Proc of ACM SIGKDD conference on knowledge discovery and data mining.［s.l.］:ACM，2012:913 -921.

［8］ Awada W，Khoshgoftaar T M，Dittman D，et al.A review of the stability of feature selection techniques for bioinformatics data ［C］//Proc of international conference on information reuse and integration.［s.l.］:［s.n.］，2012:356-363.

［9］ 季 薇，李 云.基于局部能量的集成特征選擇［J］.南京大學學報:自然科學版，2012，48(4):499-503.

［10］ Lu B L，Ito M.Task decomposition and module combination

based on class relations:a modular neural network for pattern classification［J］.IEEE Transactions on Neural Networks，1999，10(5):1244-1256.

［11］周國靜，李 云.基于最小最大策略的集成特征選擇［J］.南京大學學報:自然科學版，2014，50(4):457-465.

［12］陳曉明.海量高維數據下分布式特征選擇算法的研究與應用［J］.科技通報，2013，29(8):79-81.

［13］連惠城.最小最大模塊化網絡及人臉屬性分類研究［D］.上海:上海交通大學，2008.

［14］解男男.機器學習方法在入侵檢測中的應用研究［D］.長春:吉林大學，2015.

［15］閆國虹.支持向量機不平衡問題和增量問題算法研究［D］.西安:西安電子科技大學，2012.

Improvement of Multi-classification Integrated Selection Based on Min-Max-Module

ZHOU Feng，WANG Wei-yang
(School of Information＆Engineering，Shanghai Maritime University，Shanghai 201306，China)

With the expansion of the data size，a single weak classifier has been unable to predict unknown samples accurately.To solve this problem，an integrated learning is proposed.Combined the integrated learning and classification，the idea of integration is also used in the feature selection at the same time.For the increase of sample prediction accuracy，a strategy based on Min-Max-Module(M3)is put forward.It makes integrated learning applied to feature selection algorithms and classifier，and compares four kinds of integration strategies as well as three different classification methods.The results show that the proposed method can be able to achieve good results in most cases，and can well handle imbalanced data sets.

feature selection;integrated learning;Min-Max-Module(M3);Imbalance Data Sets(IDS)

TP391

A

1673-629X(2016)09-0149-05

10.3969/j.issn.1673-629X.2016.09.033

2015-09-17

2016-01-06< class="emphasis_bold">網絡出版時間:2

時間:2016-08-23

國家自然科學基金青年項目(61303100)

周 豐(1991-)，女，碩士研究生，研究方向為挖掘算法中的特征處理;王未央，碩士生導師，研究方向為數據庫系統、系統與數據整合、數據挖掘及其在港航、海洋、物流信息系統中的應用。

http://www.cnki.net/kcms/detail/61.1450.TP.20160823.1343.032.html