基于重采樣與屬性約簡的多模態選擇性集成學習

江 峰，李 瑞，張友強，楊愛光

(青島科技大學 信息科學技術學院，山東 青島 266061)

0 引 言

集成學習的目的是訓練多個不同的個體分類器，并通過某種組合策略(例如，投票)將這些個體分類器集成在一起，從而生成泛化能力更強的集成分類器[1,2]。如果只是選擇一部分的個體分類器來生成集成分類器，那么這種集成學習策略就稱為“選擇性集成”[3]。選擇性集成算法需要對個體分類器進行擾亂，按照擾亂手段的不同，可以將現有集成算法分成兩大類：基于單模態擾亂的選擇性集成算法(簡稱“單擾亂算法”)和基于多模態擾亂的選擇性集成算法(簡稱“多擾亂算法”)。單擾亂算法只利用一種策略來將數據集打亂，以得到多個不同的個體分類器[4,5]。多擾亂算法則利用多種策略來將數據集打亂，以得到多個不同的個體分類器[6]。相對于單擾亂算法而言，多擾亂算法具有顯著的優勢，即更容易實現個體分類器的多樣性。正是由于上述優勢，多擾亂算法得到了廣泛研究與應用[7,8]。

本文針對多擾亂算法進行研究，利用兩種策略分別將數據集的樣本與特征空間打亂，從而得到一種選擇性集成算法SE_RSAR。該算法的大體思路如下：①通過隨機的重復采樣策略將數據集的樣本空間打亂，產生多個采樣集；②對任意一個采樣集Sample，通過基于相對決策熵的屬性約簡策略先對Sample進行約簡，然后利用約簡后的采樣集訓練一個個體分類器；③從第②步所生成的所有個體分類器中，利用貪婪機制[9]挑選出若干個性能較好且差異性較大的個體分類器；④通過投票，把第③步所挑選出的個體分類器組合在一起，得到集成分類器。

實驗采用KNN算法來訓練個體分類器，并在UCI數據集上將SE_RSAR算法與現有的同類型集成學習算法性能相比較。實驗結果表明，SE_RSAR算法能夠取得更好的分類效果。

1 粗糙集的基本知識

本節引入與粗糙集理論相關的一些主要概念。在粗糙集中，一般使用信息系統來存儲數據(關于信息系統的詳細定義可參考文獻[10,11])。當我們將一個信息系統中的屬性集分成條件屬性集和決策屬性集時，就得到了另外一個概念：決策表(關于決策表的詳細定義也可參考文獻[10,11])。

在粗糙集領域，“知識”代表著一種分類的能力，知識通常由不可分辨關系來刻畫。不可分辨關系作為粗糙集理論的基礎，假定關于論域的某類知識，并采用屬性和屬性值來描述論域中的對象，若兩個對象(或對象集)存在相同的屬性及屬性值，則稱它們之間存在不可分辨關系。給定一個決策表DT=(U,C,D,V，f) 和任意的條件屬性子集B(其中，B?C)， 論域U上的二元關系IND(B)={(x,y)∈U×U∶?b∈B,f(x,b)=f(y,b)} 被稱為不可分辨關系。不可分辨關系本身也是一種等價關系。對于論域U中的任意一個元素u，u在不可分辨關系IND(B) 下所屬的等價類被定義成： [u]B={v∈U∶(u,v)∈IND(B)}。

利用不可分辨關系，可以進一步定義正區域、粗糙度、屬性依賴度等概念，其中，D的B-正區域是指U中所有根據關系U/IND(B) 可以準確劃分到U/IND(D) 中的等價類去的對象集合,具體定義見文獻[10-12]，另外，粗糙度和屬性依賴度的具體定義也同樣見文獻[10-12]。

2 基于相對決策熵的屬性約簡

屬性約簡是粗糙集理論中的一個重要研究課題，它是指在保持分類能力不變的前提下，將決策表中不影響決策或者分類的多余屬性去掉。在Pawlak提出的經典粗糙集模型中，通常使用代數表達式來定義粗糙集中的許多基本概念。粗糙集理論認為，知識的粗糙性可以通過集合之間的包含關系和代數中的等價關系來描述。但是，用這種方式很難從本質上來理解知識的粗糙性。為了深入刻畫粗糙集中信息與粗糙度之間的關系，許多研究人員將信息熵引入到粗糙集中[13]。本文將在粗糙集中引入一種新的信息熵——相對決策熵，并利用其來進行屬性約簡[14,15]。

與已有文獻中所提出的關于信息熵的定義不同，相對決策熵的定義與粗糙度這一概念有關[15]。

定義1 相對決策熵:給定決策表DT=(U,C,D,V,f)， 令U/IND(D)={D1,…,Dm} 表示不可分辨關系IND(D)對U的劃分。對任意B?C，D相對于B的決策熵RDE(D,B) 定義為

其中，γB(D) 表示決策屬性集D對B的依賴度，ρB(Di) 表示集合Di在關系IND(B)下的粗糙度， 1≤i≤m。

在定義1的基礎上，可以進一步定義基于相對決策熵的屬性約簡和基于相對決策熵的屬性重要性，具體定義可參考文獻[15]。

接下來，我們給出一個啟發式屬性約簡算法(即算法1)，用于在給定的決策表中計算出基于相對決策熵的約簡。

算法1： 基于相對決策熵的約簡計算

輸入： 決策表DT=(U,C,D,V,f)

輸出： 約簡R

算法初始化： 令Core←?,R←?

(1) 計算劃分U/IND(C),U/IND(D) 和U/IND(C∪D)。

(2) 計算相對決策熵RDE(D,C)。

(3) 對每個a∈C， 反復執行：

(3.1) 計算相對決策熵RDE(D,C-{a})；

(3.2) 如果RDE(D,C-{a})>RDE(D,C)， 則令Core←Core∪{a}。

(4) 令R←Core。

(5) 如果R=?， 則令Temp←RDE(D,C)+1， 否則，令Temp←RDE(D,R)。

(6) 當Temp≠RDE(D,C) 時， 反復執行：

(6.1) 對每個b∈C-R， 反復執行：

(I) 計算RDE(D,R∪{b});

(II) 計算b相對于R和D的重要性SGF(b,R,D)=RDE(D,R)-RDE(D,R∪{b})。

(6.2) 從C-R中選擇重要性最大的屬性bmax(如果有多個屬性同時具有最大的重要性，則選擇使得γ{bmax}(D) 值最大的bmax)。

(6.3) 令Temp←RDE(D,R∪{bmax}),R←R∪{bmax}。

(7) 對每個ai∈R(其中，下標i的取值從 |R|-1 逐步遞減到|Core|)， 反復執行：

計算RDE(D,R-{ai})， 如果RDE(D,R-{ai})=RDE(D,C)， 則將元素ai從集合R中移去。

(8) 返回約簡R。

在算法1中，我們采用一種預先對論域U進行計數排序，然后再計算劃分U/IND(B) 的策略(其中，B?C是任意一個屬性子集)，以此使得計算U/IND(B) 的時間復雜度為O(|B|×|U|)。 最壞情況下，算法1的時間復雜度為：O(|C∪D|2×|U|)， 空間復雜度為O(|C∪D|×|U|)。

3 SE_RSAR算法

Bagging、Boosting和RSM(random subspace me-thod) 是3個非常具有代表性的單擾亂算法，其中，前面兩個算法利用“樣本空間擾亂”這種策略來將數據集打亂；第三個算法則利用“特征空間擾亂”這種策略來將數據集打亂。通常，單擾亂算法在提升個體分類器的多樣性方面存在不足。針對這一不足，本文設計出多擾亂算法SE_RSAR[16-18]，利用兩種策略分別將數據集的樣本與特征空間打亂。SE_RSAR算法可分成4個階段：①樣本空間打亂階段。通過隨機的重復采樣策略將數據集的樣本空間打亂，產生多個采樣集；②特征空間打亂階段。對任意一個采樣集Sample，通過基于相對決策熵的屬性約簡策略先對Sample進行約簡[19]，然后利用約簡后的采樣集訓練一個個體分類器；③貪婪搜索階段。從第②階段所生成的所有個體分類器中，利用貪婪機制挑選出若干個性能較好且差異性較大的個體分類器；④投票階段。通過投票，把第③階段所挑選出的個體分類器組合在一起，得到集成分類器。

SE_RSAR算法的第③階段利用貪婪機制[20]挑選出若干個性能較好且差異性較大的個體分類器，具體過程如下：首先，利用給定的驗證集去驗證每一個待選的個體分類器的性能，根據這些個體分類器的性能從高到低對它們進行排序，并將性能最好的一個個體分類器挑選到分類器集合E中[21]；其次，從所有剩下的待選個體分類器中挑選出當前最優的個體分類器加入到E中，挑選標準為：相對于其它的待選個體分類器，將最優個體分類器加入到E中之后，由E中個體分類器所組合而成的集成分類器具有最好的性能；第三，重復執行第二步，每次挑選出當前最優個體分類器加入到E中之后，都把由E中元素所組合而成的集成分類器的性能保存起來。通常，集成分類器的性能一開始會不斷地增加，在獲得最高值之后將會逐漸地下降；第四，將那些在集成分類器的性能獲得最高值之后加入到E中的個體分類器從E中剔除。

下面，給出SE_RSAR的偽代碼。

算法2： 多擾亂算法SE_RSAR

輸入： 給定的訓練集與驗證集；待選的個體分類器數量M。

輸出： 集成分類器EC。

算法初始化： 將集合E、R和B都初始化為空集， 并且將變量num初始化為0。

(1) 對每一個i∈{1,2,…,M}， 循環執行下面的語句：

(1.1) 針對給定的訓練集，通過隨機的重復采樣策略對其進行采樣， 得到一個采樣集Si；

(1.2) 使用算法1在集合Si上產生一個約簡ri， 將ri作為一個元素加入到集合R， 并且利用ri對Si進行特征選擇， 從而得到特征選擇之后的采樣集Sri；

(1.3) 在采樣集Sri上通過預先確定的分類算法訓練一個個體分類器bi， 并且將bi作為一個元素加入到待選個體分類器集合B中。

(2) 對每一個i∈{1,2,…,M}， 循環執行下面的語句：

(2.1) 針對給定的驗證集， 通過約簡ri對其進行特征選擇， 從而得到特征選擇之后的驗證集Vri；

(2.2) 計算個體分類器bi在驗證集Vri上的分類精度。

(3) 將B={b1,…,bM} 中的所有待選個體分類器按照其分類精度從高到低進行排序。

(4) 挑選出B中排在第一位的個體分類器b1， 將b1作為選中的個體分類器加入到集合E中， 并從集合B中剔除b1。

(5) 如果集合B包含兩個或兩個以上的元素， 則循環執行下面的語句：

(5.1) 對于B中的任意一個個體分類器b， 將E∪{b} 中所有的個體分類器組合成一個集成分類器， 并驗證該集成分類器在給定驗證集上的分類精度Pb；

(5.2) 挑選出B中的個體分類器bmax， 挑選標準為： 由E∪{bmax} 中個體分類器所組合而成的集成分類器的分類精度Pbmax最大。令E←E∪{bmax},B←B-{bmax}, Array[num]←Pbmax, num←num+1。

(6) 把Array中值最大的元素的下標賦值給變量h， 并且將集合E中所有下標在h之后的個體分類器都從E中剔除。

(7) 通過投票， 把E中的個體分類器組合在一起， 得到集成分類器EC。

(8) 返回集成分類器EC。

4 實驗結果

為了驗證SE_RSAR算法的性能，我們在8個UCI數據集上進行了實驗，其中，基分類器采用1NN(1-最近鄰)分類算法來訓練。表1給出了這8個UCI數據集的詳細信息。

表1 8個UCI數據集

本文所采用的分類評估指標為：分類精度(Accuracy)。分類精度的具體定義如下：對于給定的測試集T，分類器正確分類的樣本數量與T中總的樣本數量之比。假設當前考慮的是一個二分類問題，分類精度可以通過表2所示的混淆矩陣來進行計算，即

Accuracy=(TP+TN)/(TP+FN+FP+TN)

我們采用Java語言實現了SE_RSAR算法。實驗中，對于數據集中的連續型屬性，我們預先使用等寬離散化算法進行離散化處理，其中，區間數設置為5。對于一個給定的數據集T，我們將T隨機分為一個訓練集(T中50%的數據)和一個測試集(剩余50%的數據)。另外，由于SE_RSAR 算法需要使用一個驗證集來選擇一組性能較好且差異性較大的個體分類器，因此，我們還從訓練集中隨機選取60%的樣本作為驗證集。對于SE_RSAR算法，我們還需要設定待選個體分類器的數量，在實驗中，待選個體分類器的數量統一設置為30。

在實驗過程中，我們分別采用了兩種不同的采樣方法來獲取采樣集：無放回采樣和有放回采樣。在使用無放回采樣時，我們采取了3種不同的采樣比例(90%、95%和98%)來對訓練集進行隨機采樣。在使用有放回采樣時，我們同樣采取了3種不同的采樣比例(90%、95%和100%)來對訓練集進行隨機采樣。表3給出了在使用無放回采樣時SE_RSAR算法在各個數據集上以及不同采樣比例下的分類性能。表4則給出了在使用有放回采樣時SE_RSAR 算法在各個數據集上以及不同采樣比例下的分類性能。

表3 無放回采樣時SE_RSAR算法的性能/%

表4 有放回采樣時SE_RSAR算法的性能/%

在表3和表4中，第2列-第4列的實驗結果都是在重復執行100次之后，取這100次實驗結果的平均值。另外，最后一列結果為第2-第4列結果的平均值，即SE_RSAR算法在3種不同采樣比例下的平均精度。

從表3可以看出，對于無放回采樣而言，95%的采樣比例在5個數據集上取得了最高的分類精度，90%的采樣比例則在兩個數據集上取得了最高的分類精度，98%的采樣比例只在“Vowel”數據集上取得了最高的分類精度。上述結果表明，95%的采樣比例比較適合于無放回采樣。另外，從表4可以看出，對于有放回采樣而言，100%的采樣比例在7個數據集上取得了最高的分類精度，而90%的采樣比例只在數據集“wdbc”上取得了最高的分類精度。上述結果表明，100%的采樣比例比較適合于有放回采樣。

如果將表3和表4中的數據進行對比，我們可以看出，SE_RSAR算法在無放回采樣下的性能要優于其在有放回采樣下的性能，這是因為在大部分數據集上(除了“Sonar”數據集之外)，采用無放回采樣的SE_RSAR算法，其平均精度要高于采用有放回采樣的SE_RSAR算法。

接下來，我們將SE_RSAR算法與兩種常用的單模態集成算法(Bagging和RSM)以及一種多模態集成算法(Bagging-RSM)進行對比，以驗證SE_RSAR算法的性能。為了確保比較的公平性，這里SE_RSAR算法將同樣采用在Bagging和Bagging-RSM中所使用的自助采樣方法，即對訓練集進行有放回并且采樣比例為100%的采樣。對于Bagging、RSM和Bagging-RSM，我們直接使用WEKA[22]中所提供的算法來進行實驗，所有參數均設置為WEKA中的默認值。

在表5中，我們給出了不同算法的分類結果。

表5 不同算法的分類精度對比/%

在表5中，1NN表示不使用集成方法，而是直接采用單個分類器來進行分類。從表5可以看出，SE_RSAR算法在7個數據集上的分類精度都要優于其它算法，唯一的例外是數據集“Dermatology”，不過，在該數據集上，SE_RSAR 算法的性能仍然要比Bagging和1NN方法好。因此，從總體上看，本文提出的SE_RSAR算法其性能要優于現有的集成學習方法。另外，可以看出，在“Iono”，“Sonar”和“ Vowel”這3個數據集上，Bagging的性能比單分類器算法1NN還要差，而在其它數據集上，Bagging相對于1NN而言其性能提升得也不明顯。上述結果表明，單模態的集成方法很多時候不足以提升集成學習的整體性能。

5 結束語

為了增加個體分類器之間的差異性，本文提出一種基于重采樣[23]和屬性約簡[24]的多模態選擇性集成學習方法。該方法利用重采樣技術來擾亂樣本空間，并通過基于相對決策熵的屬性約簡方法來擾亂特征空間，通過這種多模態的擾亂策略可以有效提升個體分類器之間的差異性。另外，我們還提出了一種基于貪婪機制的個體分類器選擇方法，可以進一步提升集成分類器的性能。實驗結果表明，本文所提出的SE_RSAR算法其性能要優于當前的單模態及多模態集成算法。

基于相對決策熵的屬性約簡方法是在Pawlak的經典粗糙集模型下所提出的。由于經典粗糙集模型只能用于處理離散型屬性，因此，SE_RSAR算法需要利用一個離散化過程將所有連續型屬性轉換為離散型屬性。但是，屬性的離散化可能會導致信息丟失。在下一步的工作中，我們將考慮把SE_RSAR算法擴展到鄰域粗糙集模型[25-27]中，該模型可以同時處理連續型和離散性屬性，從而不需要對連續型屬性進行離散化處理。