丁 毅，王明亮，張道強

南京航空航天大學 計算機科學與技術(shù)學院，南京 211100

1 引言

集成學習是機器學習中的一個重要研究領(lǐng)域，在很多的實際問題研究中，集成學習往往能比單一的機器學習算法獲得更好的效果。構(gòu)建一個集成算法主要分為模型構(gòu)建和模型組合兩個步驟[1]，而構(gòu)建一個好的集成算法的關(guān)鍵在于基學習器的性能和差異性，但大多數(shù)實際情況下很難同時實現(xiàn)這兩個目標[2]。目前已經(jīng)有很多關(guān)于提高基學習器之間差異性的研究工作[3-4]。構(gòu)建具有差異性的基學習器的4種基本方法有：（1）使用不同的組合模式；（2）使用不同的學習器；（3）使用不同的特征子集；（4）使用不同的訓練集。在目前的研究中，第三種和第四種集成算法構(gòu)建方法更為常見，第三種最具代表性的就是隨機子空間集成（random subspace ensemble，RSE）[5]，它通過大量隨機選取特征子空間來分別構(gòu)建基學習器。而在第四種方法中，又分為直接隨機選取訓練子集和自適應(yīng)調(diào)整訓練集的方法，最具代表性的即Bagging[6]和Boosting算法中的Adaboost[7]。另一種常用的集成學習算法：隨機森林（random forest，RF），同時具備第三種和第四種集成算法構(gòu)建方式的特征，不僅每次隨機選取訓練集，并且每次在構(gòu)建決策樹的時候隨機選擇特征作為結(jié)點。在很多實際應(yīng)用中，集成學習算法能獲得很好的性能，而選擇哪種具體的算法則要根據(jù)實際的情況來確定。Boosting類型算法，例如Adaboost[7]，在噪聲較少的數(shù)據(jù)集上能獲得更優(yōu)秀的性能，卻容易過擬合有噪聲的數(shù)據(jù)集[8-10]，而Bagging和RSE則表現(xiàn)得更加魯棒[11]，尤其當數(shù)據(jù)具有很高的維度-數(shù)量比和很多冗余特征的時候，RSE能獲得更好的性能。

在很多實際應(yīng)用中，例如功能磁共振影像（functional magnetic resonance imaging，fMRI）分類任務(wù)中，醫(yī)學數(shù)據(jù)的樣本量較少，而fMRI數(shù)據(jù)的維度又非常高，文獻[12-14]都利用RSE成功地在這個任務(wù)上獲得了很好的性能。但是當給定一組基學習器時，選擇使用其中的一部分要比直接使用所有的基學習器要更好，因此如何選出這樣一組基學習器對于集成學習來說非常重要[15]。在集成學習中，基學習器之間的差異性是集成方法性能的關(guān)鍵，從所有的基學習器中選擇出一組最具差異性的不僅可以幫助減少基學習器之間的冗余度，而且可以提高集成方法的性能。目前已經(jīng)有很多關(guān)于基學習器之間差異性的研究，如文獻[16]的Chapter 5，但是這些方法并沒有真正考慮到隨機子空間集成的特性，即隨機子空間集成的差異性應(yīng)該體現(xiàn)在子空間分布結(jié)構(gòu)的差異上。因此本文基于聚類的思想，利用多核最大均值差異（maximum mean discrepancy，MMD）來衡量子空間的分布差異，提出了一種無監(jiān)督和不需要訓練的差異性隨機子空間選擇算法，并利用選擇到的差異性隨機子空間得到差異性優(yōu)化的集成模型。

2 隨機子空間集成

2.1 符號解釋

給定數(shù)據(jù)集X=[x1,x2,…,xN]∈RD×N，和對應(yīng)的標簽Y=[y1,y2,…,yN]∈R1×N，隨機采樣的第i個d維子空間數(shù)據(jù)集為一個集成學習模型由M個基學習器組成f(x)={f1(x),f2(x),…,fM(x)}，其中fi(x)表示為一個基學習器。

2.2 隨機子空間集成

給定數(shù)據(jù)集X，隨機選取M個d維子空間，從而得到M個新數(shù)據(jù)集?；鶎W習器fi(x)可以根據(jù)學習任務(wù)的需要進行選擇，例如支持向量機（support vector machine，SVM）、邏輯斯提回歸（logistic regression，LR）、最小二乘回歸（least square regression，LSR）、決策樹（decision tree，DT）等。一個基學習器對一個子空間數(shù)據(jù)集進行學習，最終綜合所有M個基學習器的結(jié)果輸出結(jié)果。當每個基學習器給出預測結(jié)果后，可以選擇多種方式來集成所有基學習器的結(jié)果。最常用的包括取均值、加權(quán)平均值、投票等方式[16]。

2.3 集成剪枝

集成剪枝是提高隨機子空間集成算法的推廣能力和效率的有效方式。集成剪枝主要分為3種類型[17]：（1）基于排序的剪枝；（2）基于聚類的剪枝；（3）基于優(yōu)化的剪枝?；谂判虻募糁18]即給定所有的基學習器一個合適的順序?；诰垲惖募糁夹g(shù)[19]基于利用基學習器的特性進行聚類，采用某種合適的策略從一個聚類中選取一個模型加入集成中。而基于優(yōu)化的剪枝[15]則是通過給每個基學習器一個權(quán)值，通過優(yōu)化一個設(shè)計的目標函數(shù)來學習到這個權(quán)值。然而這3種剪枝方法的前提都是先訓練好所有的基學習器，這需要大量的計算資源，并且對于RSE來說，這些策略并沒有充分地提高隨機子空間的差異性。

3 差異性隨機子空間集成

3.1 子空間差異性度量

子空間的差異性來源于樣本在這個子空間中的分布情況，如圖1所示，有4個不同分布結(jié)構(gòu)的二維子空間，不同的子空間分布結(jié)構(gòu)代表著不同的信息，需要盡可能利用不同的子空間信息，并且刪去大量的冗余子空間，例如在圖1中的第一個和第四個子空間具有非常相似的空間結(jié)構(gòu)，基于這兩個子空間的基學習器不能夠相互提供足夠的互補信息，因此只需要利用這兩個子空間中的一個。為了達到這個目的，需要找到一種合適的度量來衡量子空間之間的差異性，從而選取最具有差異性的子空間加入集成中。

Fig.1 Subspaces with different distribution structures圖1 具有不同分布結(jié)構(gòu)的二維子空間

衡量數(shù)據(jù)的分布差異一般通過數(shù)據(jù)的一階、二階統(tǒng)計信息即均值、方差來衡量，而低階的統(tǒng)計信息不足以完全表達出數(shù)據(jù)分布的信息。最大均值差異（MMD）[20]是一種非參數(shù)度量，最開始被使用在驗證兩組樣本是否屬于同一數(shù)據(jù)分布，它通過將數(shù)據(jù)分布投影到再生核希爾伯特空間（reproducing kernel Hibert space，RKHS）來計算它們之間均值（即高階統(tǒng)計量）的差距。MMD的公式化描述如下。

定義1令?:X→H是從特征空間到RKHS的投影，X、Y表示兩個數(shù)據(jù)集，兩個數(shù)據(jù)集之間的MMD定義為：

當S1和S2屬于同一數(shù)據(jù)分布時，MMD值為0。當選取合適的核函數(shù)k，式（1）可以被進一步展開為：

計算式（2）即計算兩個子空間之間的MMD的時間復雜度，為O(n2)，在本文的任務(wù)中n為數(shù)據(jù)集的樣本量，而計算所有子空間之間的MMD的時間復雜度為O(n2m2)，其中m為隨機選取的子空間的數(shù)量。在實際應(yīng)用中，數(shù)據(jù)量n往往會大于子空間數(shù)量m，此時計算開銷將主要消耗在計算MMD上。在這里使用多核MMD（multi-kernel MMD，MK-MMD）[21]來進行線性的MMD計算，從而極大降低復雜度。將式（2）中的核函數(shù)k替換為多核核函數(shù)：

根據(jù)文獻[21]中的理論分析，核函數(shù)的選擇對于雙樣本問題的檢驗能力十分重要，這里的多核通過利用不同的核函數(shù)來強化MK-MMD的檢驗能力。類似于文獻[21]，采用式（2）的無偏估計來表示MKMMD，這種表示可以被在線性時間內(nèi)完成計算。選取樣本元組vi:=[x2i-1,x2i,y2i-1,y2i]，

此時兩個子空間的MMD表示為：

從而，可以利用式（5）來衡量兩個子空間中數(shù)據(jù)分布的差異性。并且計算式（5）的時間復雜度降低到O(n)。下一步，需要選取合適的多核參數(shù)β來最大化MK-MMD的能力同時最小化TypeⅡError[21]，目標函數(shù)定義為：

從而式（6）被表示為：

其中，λ=10-4。通過求解式（7）這個二次規(guī)劃問題，得到優(yōu)化的多核參數(shù)β來計算MK-MMD。

3.2 基于聚類的差異性隨機子空間選擇

本文利用聚類的思想，利用MK-MMD作為距離度量，通過將具有相似數(shù)據(jù)分布的子空間聚到同一類中，選取這個聚類里的一個子空間作為代表，從而減少隨機子空間的冗余度。常用的聚類方法有K均值算法（K-means）、均值漂移（mean shifit）、譜聚類（spectral clustering）和高斯混合模型（Gaussian mixture）等。而在本文僅僅有子空間之間的距離信息，這使得需要計算聚類中心的聚類算法無法使用，因此在這里采用基于圖的譜聚類算法結(jié)合基于MKMMD的相似性度量來進行隨機子空間之間的聚類。譜聚類首先利用數(shù)據(jù)樣本構(gòu)造相似性矩陣。然后利用相似性矩陣得到拉普拉斯矩陣（Laplacian matrix），通過拉普拉斯矩陣的特征向量構(gòu)造一個新的、簡化的數(shù)據(jù)空間，在這個數(shù)據(jù)空間中數(shù)據(jù)間的相似性關(guān)系表現(xiàn)得更加直觀。最后得到隨機子空間的聚類結(jié)果后，從每個聚類中選取一個最具代表性的隨機子空間來代表這個聚類。在本文中，利用聚類C中的一個子空間i對于其他子空間的相似度的和作為其重要程度，如式（6），選擇重要程度最高的子空間作為聚類C的代表，并加入差異性隨機子空間（diverse random subspace，DRS）中：

差異性隨機子空間選擇的算法如算法1所示。

算法1差異性子空間選擇

輸入：隨機子空間集合RS∈RM×N×d（其中M為子空間數(shù)量，N為樣本數(shù)量，d為子空間維度），子空間聚類數(shù)量n。

（1）構(gòu)建子空間相似性矩陣A∈RM×M：

①對于任意兩個隨機子空間RSi和RSj，利用式（5）計算它們之間數(shù)據(jù)分布差異MMDi,j；

②當RSi和RSj分布一致，則MMDi,j=0，RSi和RSj的相似性定義為1/MMDi,j；

③Ai,j=1/MMDi,j。

（3）對拉普拉斯矩陣L進行特征分解，將其中前k個最大特征值所對應(yīng)的特征向量v1,v2,…,vk組合成新矩陣V=[v1,v2,…,vk]∈RM×k，并對矩陣V按元素進行歸一化。

（4）V中的第i行可以看作是第i個子空間的一種特征表示，對V中的樣本使用k-means算法聚類。

（5）在第i個聚類Ci中，根據(jù)式（8）計算每個隨機子空間的重要程度，選擇重要程度最高的子空間作為聚類Ci的代表，并加入到最后的差異性子空間集合DRS中。

輸出：差異性子空間DRS∈Rn×N×d。

3.3 差異性隨機子空間集成

當?shù)玫揭唤M差異性子空間集合DRS后，可以利用多種基學習器進行學習，例如決策樹、邏輯斯提回歸等。本文使用邏輯斯提回歸（LR）作為基學習器作為默認的DRS算法。LR是被廣泛應(yīng)用的分類模型，LR有著較為穩(wěn)定的分類性能，并且相比于同樣受到廣泛關(guān)注的支持向量機，LR更加容易訓練（在大規(guī)模應(yīng)用中可以利用隨機梯度下降等優(yōu)化方法），并且更容易實施（SVM需要存儲大量的支持向量，而LR只需要計算一次向量的內(nèi)積）?；贒RS的集成學習算法在訓練之前即進行了大量的剪枝，并且能夠保證剩余的隨機子空間保留足夠的差異性。雖然保證基學習器的差異性是被廣泛接受的集成算法設(shè)計思想[16]，但是在大多數(shù)情況下仍然無法保證基于差異性的基學習器能夠獲得優(yōu)秀的性能并且組成一個高性能的集成學習算法。由于DRS通過優(yōu)化差異性顯著降低了基學習器的數(shù)量，因此在本文中，將DRS和基于排序的集成剪枝技術(shù)結(jié)合。首先，將在驗證集上性能較差的，例如將分類精度低于50%的基學習器直接丟棄，然后根據(jù)訓練好的基學習器在驗證集上的表現(xiàn)進行排序，選取前k個基學習器作為最終的集成模型。差異性隨機子空間集成算法如算法2所示。

算法2差異性子空間集成

輸入：差異性隨機子空間DRS∈Rn×N×d，基學習器f(x)，驗證集V，測試集T，基學習器參數(shù)σ，集成大小k(k≤n)。

（1）使用基學習器f(x)和對應(yīng)的參數(shù)σ對DRS集合中的每一個隨機子空間進行學習。

（2）每個基學習器f(x)對驗證集V進行驗證得到驗證結(jié)果Vri=f(DSRi)。

（3）過濾Vri≤0.5的基學習器。

（4）根據(jù)Vri對基學習器進行排名，選取前k個基學習器加入集成E。

（5）使用最終的集成E對測試集T進行測試。

輸出：訓練后的差異性隨機子空間學習器集合。

4 實驗與分析

4.1 模擬數(shù)據(jù)集

構(gòu)造一個模擬數(shù)據(jù)集來驗證差異性隨機子空間選擇算法的效果。

首先構(gòu)造一個具有明顯判別性分布的二維數(shù)據(jù)集。分別從兩個二維高斯分布中各隨機采樣200個數(shù)據(jù)點，得到原始數(shù)據(jù)集A。原始數(shù)據(jù)分布如圖2所示。

Fig.2 Original feature space圖2 原始特征空間

為了驗證差異性隨機子空間集成的效果，為原始具有判別分布特性的兩個維度加入8維高斯白噪聲來混淆原始數(shù)據(jù)，得到新的數(shù)據(jù)集B。對數(shù)據(jù)集B隨機采樣100個二維隨機子空間，經(jīng)過分析，總共有45種不同的二維隨機子空間，其中具有差異性的隨機子空間只有4種，即原始的兩個維度，原始的其中一個維度加上噪聲維度和全噪聲維度。希望從隨機采樣的100個二維隨機子空間中利用本文提出的差異性隨機子空間選擇算法找到這4種差異性隨機子空間。

在算法執(zhí)行后，從100個二維隨機子空間中得到了4個隨機子空間聚類，通過式（6）定義的準則，從每個聚類中選取一個隨機子空間作為該聚類的代表，隨后得到了圖3中的結(jié)果，圖3中明確給出了通過算法1得出的4個差異性隨機子空間的分布結(jié)構(gòu)。通過分析，可以明確看到算法1所選擇出來的差異性子空間確實是這100個二維隨機子空間所具備的4種基本分布結(jié)構(gòu)，實驗結(jié)果表明了本文提出的差異性隨機子空間選擇的算法有理論上的作用。在4個聚類中，第一個聚類中只有圖3中的第一個差異性子空間，第二個聚類中只有圖3中的第二個差異性子空間，第三個聚類中有16個隨機子空間，如圖4所示，第四個聚類中有82個隨機子空間。以圖4為例，第三個聚類中大多數(shù)和圖3中的第三個子空間有相同的分布，只有少部分的錯誤聚類，可以觀察到第三個聚類中出現(xiàn)了第二個聚類中的子空間，這是因為所構(gòu)建的差異性隨機子空間選擇算法中的譜聚類過程受到了相似性矩陣尺度化的影響和圖分割算法的影響，這導致只能夠得到差異性隨機子空間聚類的近似最優(yōu)解，但是最終的代表性子空間選擇算法（算法1，步驟5）可以幫助排除小部分錯誤聚類的影響。

4.2 真實數(shù)據(jù)集

本文也比較了差異性隨機子空間集成（DRS）、隨機森林（RF）、隨機子空間集成（RSE）、Adaboost、Bagging和支持向量機（SVM)等算法在真實數(shù)據(jù)集上的性能。選用了10個公開數(shù)據(jù)集（https://www.csie.ntu.edu.tw/～cjlin/libsvmtools/datasets/，http://adni.loni.usc.edu/，http://archive.ics.uci.edu/ml/）。其中 MCI數(shù)據(jù)集來自于 ADNI（the Alzheimer's disease neuroimaging initiative）數(shù)據(jù)集，ADNI數(shù)據(jù)集是一個公開的用于研究老年癡呆癥（the Alzheimer's disease）的數(shù)據(jù)集，包含了MRI、PET等多種模態(tài)的數(shù)據(jù)，利用MCI（mild cognitive impairment，輕度認知障礙）的數(shù)據(jù)和正常人進行分類，由于MCI是老年癡呆癥的前兆，因此選擇這個任務(wù)也具有很大的意義。通過MRI數(shù)據(jù)構(gòu)建腦網(wǎng)絡(luò)[22]來提取4 005維特征進行分類，而另外9個常用公開數(shù)據(jù)集則來自于UCI數(shù)據(jù)集庫和Libsvm數(shù)據(jù)集庫。其中有4個數(shù)據(jù)集具有很高的特征-樣本比，另外3個數(shù)據(jù)集則是普通的數(shù)據(jù)集。在這里子空間中都利用LR作為基學習器。希望通過使用這7個數(shù)據(jù)集來了解基于差異性隨機子空間集成的方法的優(yōu)劣性。在本文的所有實驗中，使用5折交叉驗證的方法分割訓練集和測試集，總共進行20次5折交叉驗證的過程。DRS、RSE隨機采樣一半原始維度的子空間200次，DRS聚類后得到50個差異性子空間。其中RF、Adaboost、Bagging的基學習器數(shù)量被限制在200個。

Fig.3 Diverse random subspace圖3 差異性隨機子空間

Fig.4 The third cluster of subspaces圖4 第三個隨機子空間聚類中的子空間

表1、表2中展示了所有的實驗結(jié)果，其中ratio表示數(shù)據(jù)集的特征-樣本比。由表1、表2中可以看出，在特征-樣本比較高的數(shù)據(jù)集上，由于存在大量的冗余特征，因此降低了特征維度的隨機子空間和本文提出的差異性隨機子空間的方法能獲得很高的效果。在其中幾個數(shù)據(jù)集上，只有20個基學習器的差異性子空間集成方法超過了有200個基學習器的RF、Adaboost、Bagging算法，而相比較于有眾多基學習器的隨機子空間方法RSE，差異性子空間集成由于極大削減了由冗余噪聲組成的眾多噪聲子空間，在大部分數(shù)據(jù)集上得到了超越RSE的結(jié)果，并且在訓練和測試上有更高的效率。但是對于低維度的數(shù)據(jù)集，基于隨機子空間的RSE和DRS算法的基學習器失去了很多的關(guān)鍵信息，導致基學習器的性能都很差，集成的結(jié)果也無法提高。當數(shù)據(jù)集中存在大量的冗余特征時，差異性隨機子空間算法是提高常用的隨機子空間方法RSE的一種有效途徑。值得注意的是，和譜聚類等其他聚類算法一樣，RSE中聚類的數(shù)量的選擇作為一種超參數(shù)不具備單調(diào)的對性能的影響，因此在實際應(yīng)用中，可以利用交叉驗證的方法選擇出合適的聚類數(shù)量來提高最終性能。

Table 1 Comparison between different methods（High feature-sample ratio）表1 不同集成方法之間的比較（高特征-樣本比）

Table 2 Comparison between different methods（Low feature-sample ratio）表2 不同集成方法之間的比較（低特征-樣本比）

5 結(jié)束語

很多的真實數(shù)據(jù)集有很高的特征維度并且缺少足夠的樣本來訓練單個學習器，在這些高維特征中也存在著許多冗余的特征，這些特征會導致很多常用分類器的失效。在這種應(yīng)用場景下，隨機子空間集成方法由于對子空間進行了頻繁的采樣，從而在減少了冗余特征的隨機子空間中構(gòu)建性能更好的基學習器，對基分類器集成后得到更強大的集成算法。在很多情況下，冗余特征甚至會超過有效特征，從而采樣得到的大部分隨機子空間可能具有相同的數(shù)據(jù)分布，減弱了基學習器之間的差異性。本文提出了一種基于數(shù)據(jù)分布的差異性隨機子空間集成方法，利用MK-MMD在線性時間內(nèi)計算子空間之間的分布差異，并通過譜聚類的方法將相似的子空間集合到一起，并利用一定的準則選出一個代表性子空間，得到差異性的隨機子空間集合。實際的實驗表明，在大多數(shù)情況下，差異性隨機子空間集成的方法要強于隨機子空間集成，而在低維度數(shù)據(jù)集上，差異性隨機子空間集成和隨機子空間集成的性能都遠差于隨機森林、Adaboost、Bagging方法，這說明在不存在冗余特征的條件下，子空間無法充分利用有效信息，從而降低了集成方法的能力。本文提出的差異性隨機子空間集成方法是提升隨機子空間集成的一種直接而有效的途徑，未來差異性隨機子空間選擇方法可以進一步擴展到隨機森林、特征選擇等方面。