吳倩楠 顏學峰

(華東理工大學 能源化工過程智能制造教育部重點實驗室 上海 200237)

0 引言

分類是機器學習的核心之一,集成學習在解決分類問題中發(fā)揮了重要作用,已被推廣到對象識別[1]、對象跟蹤[2]和對象檢測[3]等領(lǐng)域。其基本思想是根據(jù)一定的規(guī)則組合若干個同質(zhì)的基分類器,以獲得一個泛化能力強的分類器。然而,當基分類器數(shù)量增多時,出現(xiàn)冗余基分類器的可能性提高,進而增加計算復雜度、削弱分類速度和性能。為此,文獻[4]提出了選擇性集成的方法,從原始基分類器中進行選擇之后再集成,以更少的存儲消耗和更短的運行時間收獲比集成學習更優(yōu)的結(jié)果。相較于集成學習,選擇性集成因其較強的泛化性能以及較高的運行效率在各領(lǐng)域受到了越來越多的關(guān)注。

在選擇性集成中,基分類器的準確性與差異性是影響集成性能的2 個重要因素,二者又互相矛盾[5]。構(gòu)建可靠性高的選擇性集成分類器取決于如何從初始基分類器集合中搜索出一個平衡了準確性和差異性的最優(yōu)子集。

以選擇性集成在尋找最佳子集過程中采用的搜索策略為根據(jù),可將選擇性集成分類器劃分成基于聚類、優(yōu)化、排序的分類器?；诰垲惖姆椒ò?個主要步驟:第1 步采用聚類算法將基分類器集合劃分為多個聚簇,同一簇中的各個成員有較強的相關(guān)性,不同簇之間差異性較強。分層聚類[6]、模糊聚類[7]、近鄰傳播[8]等已被廣泛應(yīng)用于此。第2 步修剪各簇以獲得集成子集[9]?；趦?yōu)化的方法首先為各基分類器隨機分配一個權(quán)重,然后利用優(yōu)化算法將權(quán)重向量演化為最優(yōu)解,最后舍棄權(quán)重低于預定閾值的基分類器。目前已有多名學者采用螢火蟲算法[10]、蟻群算法[11]、粒子群算法[12]等來演化最優(yōu)權(quán)重向量。基于排序的方法首先對基分類器進行排名,然后按照排名選擇滿足條件的基分類器。此類方法的關(guān)鍵在于選擇對基分類器性能排序的標準。文獻[13]采用加權(quán)調(diào)和公式將多樣性和準確性有效結(jié)合。文獻[14]定義了一種度量函數(shù),分別利用相關(guān)熵和距離方差作為準確性和差異性度量,并在目標函數(shù)中加入正則化因子。文獻[15]采用特征選擇中的最大相關(guān)最大互補法衡量基分類器性能。

以上策略中,基于聚類的算法受聚類算法不穩(wěn)定性的影響較大;基于優(yōu)化的方法中,使用啟發(fā)式搜索算法難以找到全局最優(yōu),且啟發(fā)式搜索時間復雜度高;相對而言,基于排序的方法最簡單。本文構(gòu)建了一種基于排序的選擇性集成分類器,該分類器將特征選擇的思想和方法擴展到基分類器的選擇上,以改進的最大相關(guān)最小冗余準則為核心進行最優(yōu)基分類器子集的搜索,保障了分類的準確性和實用性。

1 最大相關(guān)最小冗余準則

最大相關(guān)最小冗余算法(maximum relevance and minimum redundancy,mRMR)是用于特征選擇的經(jīng)典算法,該算法首先計算候選特征與目標類別間的互信息(相關(guān)項),然后計算候選特征與已選特征間的平均互信息(冗余項),通過相關(guān)項減去冗余項得到候選特征的mRMR 分數(shù),然后從所有待選特征中選擇分數(shù)最高的加入已選子集[16]。

令D=[d1,d2,…,dn]T為給定樣本集,每個樣本由一個p 維向量構(gòu)成,其中的每個元素稱為該樣本的一個特征,進而di=。給定特征集F={f1,f2,…,fp},S 為已選特征子集;fi∈S 為已選特征,fj∈F -S 為待選特征;l 為類別;I(·) 是互信息。根據(jù)mRMR 的思想,fj的mRMR分數(shù)為

所選擇的第m 個加入子集S 的特征應(yīng)滿足:

2 ImRMRSEC

本文構(gòu)建了一種基于改進最大相關(guān)最小冗余算法的選擇性集成分類器(improved mRMR-based selective ensemble classifier,ImRMRSEC),首先利用Bootstrap 采樣得到不同訓練集并訓練一組基分類器,然后基于改進mRMR 選擇部分基分類器,最后采用相對多數(shù)投票法集成。在選擇時,將各基分類器對驗證集的預測結(jié)果視為特征選擇中的一個個特征,然后計算特征與驗證集實際類別的相關(guān)性及特征間的冗余度,選出最佳基分類器子集。對于mRMR 存在的問題,本文在相關(guān)性度量、冗余性度量及搜索方式上作了改進。為方便描述,本節(jié)中將用“特征”指代各基分類器對樣本的預測類別。

2.1 相關(guān)性度量

傳統(tǒng)mRMR 中的相關(guān)性測度采用互信息,在計算互信息時需要同質(zhì)化變量的量綱及單位,且其值不是歸一化的。為設(shè)計一種通用性強的mRMR 算法,首先需要避免互信息的固有弊端,Pearson 系數(shù)[17]、距離協(xié)方差[18]、Fisher 指數(shù)[19]等也可用于度量相關(guān)性,但各有優(yōu)缺點。其中Fisher 指數(shù)簡單但不能捕獲變量間的非線性依賴程度,Pearson 相關(guān)系數(shù)只適用于呈正態(tài)分布的變量且只能衡量線性相關(guān)程度,距離協(xié)方差不是歸一化的系數(shù)。而距離相關(guān)系數(shù)(distance correlation coefficient,DCC)是一個好的選擇。DCC 通過兩變量間的聯(lián)合特征函數(shù)與變量邊際特征函數(shù)的差值刻畫“距離”。其不需要任何模型及變量假設(shè),能評估不同維數(shù)的變量間的線性及非線性相關(guān)性,且是歸一化的系數(shù),具有較好的普適性[20]。

兩變量X、Y 間的距離相關(guān)系數(shù)定義如下[20]:

式中,dcor(·) 為距離相關(guān)系數(shù),dcov(·) 為距離協(xié)方差,其定義為

其中,f(·) 是給定變量的特征函數(shù);ω 是權(quán)重函數(shù),其大小為

按以上方式計算出的是總體距離相關(guān)系數(shù),實際應(yīng)用時,往往需要計算兩兩樣本之間的距離相關(guān)系數(shù),為此,對于n 個樣本量的成對隨機變量X 和Y,本文按如下方式計算距離相關(guān)系數(shù)。

步驟1計算各變量的成對距離矩陣a 和b:

其中,akl為矩陣a 中第k 行l(wèi) 列的元素,bkl同理。

步驟2對成對距離矩陣進行中心化處理,得到中心距離矩陣A 和B,公式為

步驟3計算距離協(xié)方差dcov(X,Y)、距離方差dcov(X,X)、dcov(Y,Y)。

步驟4將式(10)～(12)帶入式(3),求出兩變量X 和Y 的距離相關(guān)系數(shù)dcor(X,Y)。

DCC 相較經(jīng)典相關(guān)系數(shù)有以下優(yōu)勢。

(1) 不需要模型及變量假設(shè)

經(jīng)典相關(guān)系數(shù)的計算依賴兩變量間協(xié)方差與各自的方差。概率論中指出,方差存在是協(xié)方差存在的必要條件,而隨機變量的方差未必存在。DCC 的定義只涉及變量的特征函數(shù),任意隨機變量都有特征函數(shù),因此總可以計算DCC。

(2) 兩變量維數(shù)不需要相同

從本質(zhì)上看,協(xié)方差的計算過程是求向量內(nèi)積,DCC 是矩陣內(nèi)積。所以經(jīng)典相關(guān)系數(shù)要求兩變量維數(shù)必須相同,DCC 定義在任意維數(shù)的變量間。

(3) 可衡量線性和非線性相關(guān)程度

DCC 定義中的權(quán)重函數(shù)沒有選擇可積函數(shù)。在X 和Y 數(shù)值較小時,可積函數(shù)會使DCC 退化成經(jīng)典相關(guān)系數(shù),從而失去衡量非線性相關(guān)程度的能力。

2.2 冗余性度量

文獻[21]強調(diào),可將冗余信息細分為相關(guān)冗余及無關(guān)冗余信息。相關(guān)冗余指特征攜帶的相同目標類別信息,無關(guān)冗余指特征中共同攜帶但與類別無關(guān)的信息。令f1表示已選特征,f2、f3表示待選特征,l 表示目標類別。利用Venn 圖來簡化特征攜帶的信息情況及特征之間的關(guān)系,如圖1 所示。

圖1 特征間關(guān)系Venn 圖(ri 等量)

對于f1與f2,r2是相關(guān)冗余,r3為無關(guān)冗余。對于圖1 給出的示例,在選定f1的情況下,f2中攜帶3 份新的類別信息(3 ×r5),f3攜帶1 份(r7)。利用傳統(tǒng)mRMR 算法,f2、f3的mRMR 分數(shù)為

但是,r3對分類無幫助,不應(yīng)抵消f2與l 之間的相關(guān)信息。換言之,由于無關(guān)冗余的存在,算法忽略了f1所不具備而f2攜帶的目標類別信息,從而根據(jù)mRMR 分數(shù),錯誤地選擇f3加入子集。

為消除無關(guān)冗余的影響,本文引入施密特正交化(Gram-Schmidt orthogonalization,GSO)算法,用原特征的等價標準正交向量替代原向量。

GSO 是矩陣論中的經(jīng)典算法之一。對于第1節(jié)中給出的特征集F,其對應(yīng)的正交特征集為O={o1,…,op}。在GSO 過程中,oi由以下方式獲得:

式(14)表明,在等價正交向量中,fi在其他所有特征上的投影分量都會被抹去,而這些投影分量對應(yīng)冗余信息。此外,由于GSO 過程是對自變量進行直角變換,所以不會破壞原始特征的分布假設(shè)[22]。

根據(jù)GSO 過程,設(shè)Sm-1={f1,f2,…,fm-1} 是已選特征集,下一個被選特征為fm,則Sm={f1,f2,…,fm-1,fm}。利用GSO 求Sm等價標準正交向量Em的過程如下。

步驟1正交化。利用式(13)、式(14)構(gòu)造Sm的等價正交向量組Om={o1,…,om}。

步驟2標準化。將Om中各元素單位化,得到滿足要求的標準正交向量組Em={e1,…,em}。

經(jīng)過GSO,待選特征的等價標準正交向量相對于已選特征已不含冗余,所以使用特征的等價標準正交向量僅需考慮等價向量與目標類別的相關(guān)性。因此,選擇加入子集的特征應(yīng)滿足:

所選特征子集的性能指標函數(shù)為

2.3 搜索方式

傳統(tǒng)mRMR 算法在搜索下一個最佳特征時采用序列前向選擇(sequential forward selection,SFS)。SFS 初始時將已選特征子集設(shè)為空集,每次迭代時從候選特征中選擇一個使性能指標取得最大值的特征加入已選子集,直到所選特征個數(shù)等于指定特征個數(shù)[23]。然而該策略只能獲得局部最優(yōu),且不能剔除特征,后續(xù)的搜索過度依賴已選特征。

為了避免SFS 的弊端,本文引入序列浮動前向選擇(sequential floating forward selection,SFFS)。SFFS 在每次迭代中主要由前向選擇和特征回溯組成。前向選擇即標準SFS 過程;特征回溯將已選子集中性能較差的特征剔除,使后續(xù)搜索到的更優(yōu)特征能被選擇[24]。算法過程如下。

(1) 初始化已選特征子集S=?;目標特征數(shù)量s;使用標準SFS 從候選特征子集中搜索使J(S1) 最大的f1,此時已選特征個數(shù)k=1;while k

(2) 前向選擇:采用標準SFS 從候選子集中選擇fk使得J(Sk) 取最大值;

(3) 特征回溯:遍歷Sk,從中依次去掉一個特征得到,若存在某個特征使≥J(Sk-1),則將其剔除,繼續(xù)遍歷,重復上述步驟;否則,k=k +1,并轉(zhuǎn)到步驟(2)。end

2.4 ImRMRSEC 描述

輸入:樣本數(shù)據(jù)集D,其中特征F∈Rn×p,類別l∈Rn×l;基分類器個數(shù)N;集成規(guī)模s

輸出:集成分類器預測值

步驟1基分類器生成

(1) 基于訓練集Dtrain,利用Bootstrap 采樣得到N 個訓練集,然后在這一組新的訓練集上訓練基分類器,記為C={c1,c2,…,cN};

(2) 應(yīng)用步驟(1)中的集合C 來分類驗證集數(shù)據(jù),記分類結(jié)果為PV={pv1,pv2,…,pvN}。

步驟2基分類器選擇

(3) 設(shè)已選基分類器集為S,并令S=?;

(4) 基于集合PV,利用式(3)計算出pvi與目標類別之間的相關(guān)性,記錄最高分數(shù)對應(yīng)的分類器編號k,將ck移動到S 中。此時,S1={ck},已選基分類器個數(shù)m=1;C1=C -ck;

(5) 利用SFFS 依次選出最佳基分類器:while m

1) 使用標準SFS 從集合Cm-1里選取符合式(17)的基分類器,并記錄下此時的性能指標值;

2) 遍歷Sm,從中逐項剔除一個子集成員得,若始終存在,則返回1),并令m=m +1,判斷是否停止搜索,否則執(zhí)行3);

步驟3基分類器集成

(6) 基于集合S 中的基分類器預測測試集樣本類別,然后運用相對多數(shù)投票法集成各預測結(jié)果。

2.5 算法復雜度分析

(1) 生成階段

假設(shè)訓練單個基分類器的時間復雜度為Tc,則生成階段的時間復雜度為NTc;

(2) 選擇階段

選擇階段的時間復雜度主要由4 部分組成,即DCC 的計算、排序過程、GSO 和SFFS。

1) DCC:計算兩樣本量為n 的變量間DCC 的時間復雜度為O(n2);對于N 個數(shù)據(jù),快速排序法的時間復雜度為O(N log2N)。所以步驟(4)的時間復雜度為

2) GSO:構(gòu)造N 個n 維向量的等價標準正交向量所需的時間復雜度為O((N -1)n);

3) SFFS:前向選擇的時間復雜度為O(N),特征回溯遍歷整個已選集合S,由于| S|≤s,故特征回溯的時間復雜度上界可近似為O(s)[25]。

綜合1)、2)、3)及迭代規(guī)則,在挑選得第m+1個基分類器時,算法的時間復雜度為

由于m <

進而,步驟(5)的時間復雜度為

(3) 集成階段

相對多數(shù)投票法的時間復雜度為O(Ns)。

綜上,ImRMRSEC 算法的時間復雜度為

進一步,log2s >1,s 于log2N 及n 來說是一個相對小的數(shù),式(23)可進一步簡化為

3 實驗分析

3.1 實驗方法與數(shù)據(jù)

為證明文章中構(gòu)建的分類器的性能,將其與集成所有基分類器(ALL)、基于排序(MRMCEP[15])、基于聚類(MCAS[7])、基于優(yōu)化(BGASEC[4])的選擇性集成分類器進行比較。實驗數(shù)據(jù)集為10 個來自于UCI 機器學習數(shù)據(jù)庫的數(shù)據(jù)集,具體參數(shù)如表1所示。

表1 實驗數(shù)據(jù)集

對于每一個數(shù)據(jù)集,首先利用MinMax 歸一化將所有數(shù)據(jù)映射到[0,1]以降低計算復雜度。實驗中各訓練100 個支持向量機(support vector machine,SVM)、K 近鄰(k-nearest neighbor,KNN,取k=5)、誤差反向傳播神經(jīng)網(wǎng)絡(luò)(error back propagation neural network,BP)和C4.5 決策樹作為基分類器,除基于優(yōu)化的方法自適應(yīng)尋找最優(yōu)集成基分類器個數(shù)外,其他方法的集成規(guī)模都定為10,將本文所提方法與前述4 種方法進行比較。

3.2 分類準確率比較

為了提高結(jié)果的可靠度,實驗中采用十折交叉驗證法獲得分類準確率,并利用成對t 檢驗求出置信度為0.95 的置信區(qū)間作為最終分類準確率結(jié)果。

表2 給出了基分類器為SVM 時各方法的分類結(jié)果,ImRMRSEC 的準確率在7 個數(shù)據(jù)集中達到最高,剩余3 個數(shù)據(jù)集中為次高,平均準確率最高。表3中展示的為基分類器為BP 模型時的準確率,所提出的算法實現(xiàn)了在8 個數(shù)據(jù)集中準確率最高、1個數(shù)據(jù)集中精度次高,其中在Diabetes 數(shù)據(jù)集中預測誤差略高,但平均精度仍最高。同時,在部分數(shù)據(jù)集上,集成所有基分類器(ALL)的準確率略高于選擇性集成分類器。這是由于算法不可避免地在該數(shù)據(jù)集上選擇了高冗余基分類器而忽視了高準確率基分類器帶來的偶然偏差,但從平均準確率來看,集成所有基分類器的平均精度仍為最低。表4 中的結(jié)果是在基分類器為5-NN 時得到的,在這一類模型中ImRMRSEC 的準確率在8 個數(shù)據(jù)集中最高,其中,在Balance Scale 和Ionosphere 數(shù)據(jù)集上的準確率與基于聚類的方法得到的準確率相同,但其置信區(qū)間更寬。表5 給出了基分類器取C4.5 決策樹時的分類情況,ImRMRSEC 僅實現(xiàn)了在6 個數(shù)據(jù)集中精度最高,但平均精度依然最高。從平均準確率來看,本文所構(gòu)建的分類器勝過另外4 個對照組。計算4 種基分類器上平均準確率的總均值,ImRMRSEC 相較于ALL、MRMCEP、MCAS、BGASEC 分別有12.63%、7.14%、3.65%、6.22%的提高。

表2 基分類器為SVM 時各方法分類準確率及置信度為0.95 的置信區(qū)間

表3 基分類器為BP 時各方法分類準確率及置信度為0.95 的置信區(qū)間

表6～表9 分別給出了基分類器為SVM、BP 神經(jīng)網(wǎng)絡(luò)、5-NN 和C4.5 決策樹時,5 種方法在所有數(shù)據(jù)集上的誤差比較。表格中,r 表示單元格所在列對應(yīng)方法的誤差幾何平均值與所在行對應(yīng)方法的誤差幾何平均值的比率;s 給出的是單元格所在列對應(yīng)方法相較于所在行對應(yīng)方法的win/tie/los 統(tǒng)計。綜合r、s,本文對比的5 種方法的性能排序依次為ImRMRSEC、MCAS、BGASEC、MRMCEP、ALL。同時,從表格中可見,ImRMRSEC 與4 種對比方法的r值均小于1,也可說明ImRMRSEC 的分類性能更優(yōu)。

表4 基分類器為5-NN 時各方法分類準確率及置信度為0.95 的置信區(qū)間

(續(xù)表4)

表5 基分類器為C4.5 決策樹時各方法分類準確率及置信度為0.95 的置信區(qū)間

表6 基分類器為SVM 時各方法誤差比較

表7 基分類器為BP 時各方法誤差比較

表8 基分類器為5-NN 時各方法誤差比較

表9 基分類器為C4.5 決策樹時各方法誤差比較

3.3 差異性比較

為了檢驗所構(gòu)建分類器與對比算法是否具有顯著差異,引入Friedman 檢驗和Nemenyi 后驗。Friedman 檢驗首先計算每種方法在所有數(shù)據(jù)集上的平均序值,然后比較各平均序值,兩種方法的平均序值相同時其性能相同。

表10 給出了5 種方法的平均序值及4 種基分類器下總平均序值的均值?？梢钥闯?5 種方法的平均序值各不相同,即各種方法的性能顯著不同。

利用Nemenyi 后驗來進一步區(qū)分各方法。Nemenyi 后驗指出,兩種方法的平均序值之差大于臨界值CD 時其具有顯著差異。臨界值為

其中,k=5 為要檢驗的方法數(shù),N=10 為數(shù)據(jù)集個數(shù),α=0.05,查“The Studentized Range Statistic”表得q0.05=1.860,從而CD=1.315。

由表10 可知,ImRMRSEC 與ALL、MRMCEP、MCAS、BGASEC 的平均序值之差分別為2.98、1.9、1.15、1.67,除了與MCAS 比,均大于CD,且與MCAS 的差值接近臨界值,因此本文所構(gòu)建的分類器與其他幾種分類器之間在統(tǒng)計意義上有顯著差別。

3.4 運行時間比較

由于實驗中選取的對照算法與本文所構(gòu)建的基分類器僅在基分類器的選擇階段不同,所以在對比算法耗費時長時將重點放在選擇階段。同時,實驗過程中不再采用交叉驗證,而是選擇70%樣本做訓練集,30%樣本做測試集,記錄在不同基分類器模型下各方法在各數(shù)據(jù)集上單次實驗所耗時間,然后求出各方法在4 種基分類器模型下的平均運行時間,結(jié)果如表11 所示。

由表11 可以看出,BGASEC 耗費時間最多,這是由于遺傳算法在求解復雜問題時的平均時間復雜度是問題規(guī)模的指數(shù)次方;MRMCEP 所耗費時間最少,ImRMRSEC 次之,二者差異的主要原因在于Im-RMRSEC 在搜索方式上選擇了SFFS,增加了一個特征回溯環(huán)節(jié)。相較之下,ImRMRSEC 增加了時間復雜度,但分類準確率也相應(yīng)上升了。

表11 各方法運行時間比較(單位:s)

4 結(jié)論

本文構(gòu)建了一種基于改進mRMR 的選擇性集成分類器,稱為ImRMRSEC。與單個最佳模型或集成所有基分類器的方法相比,選擇性集成分類器準確率更高、耗費時間更少。本文所提方法與最大相關(guān)最小冗余準則下的其他方法相比,主要優(yōu)勢在于:引入等價的正交向量可排除無關(guān)冗余的影響,同時序列浮動前向選擇方法的引入消除了前向選擇只能添加不能替換的弊端,二者都有益于提升集成子集質(zhì)量;此外,距離相關(guān)系數(shù)對基分類器信息的捕獲是全面的,故而所提方法在大多數(shù)實驗中優(yōu)于其他方法,并在多類模型的集成實驗中被證明。