輕量化的增量式集成學習算法設計

丁嘉輝, 湯建龍, 于正洋

(西安電子科技大學電子工程學院, 陜西 西安 710071)

0 引 言

常規的分類與回歸樹算法(classification and regression tree, CART)作為一種典型的決策樹算法,其結構簡單、判決速度快、可解釋性較好[1],發展到現在已有多種變體與改進形式[2-3],廣泛應用于各種分類問題[4-8],在集成學習算法中也被認為是一種非常有效的基分類器。例如經典的隨機森林算法[9-13]就是以CART作為基分類器,通過投票的方式綜合所有基分類器的判決結果。但是常規的CART與集成學習算法也存在一個缺點,一旦有新類別進入分類范疇,算法模型通常需要重新訓練來實現對新類別樣本的認知,在分類類別數量較多時這將導致訓練時間的大幅度增加[14]。這一問題限制了CART算法在更復雜情景中的應用。例如在電子偵察領域,已經廣泛采用極限學習機[15-16]、集成學習等算法來解決輻射源分類問題[17-20],我們經常需要擴充分類器能夠識別的樣本類別庫,來適應復雜多變的戰場環境,如果每次都重新訓練分類器模型必然會大幅度增加計算量。

針對上述問題,本文提出了一種輕量化的增量式集成學習算法。首先,讓原有CART的葉節點再生長,在不破壞現有結構的基礎上使之具備開集識別的能力,從而能夠辨別訓練集類別之外的異常樣本。然后采用增量式的集成策略[21-23],以若干個具有開集識別能力的CART作為基分類器構成增量式集成學習算法,每個基分類器只負責其中一部分類別的分類。開集識別能力確保了每個基分類器只會對自己“認識”的樣本做出判決,否則投出“棄權票”。因此,當需要擴充新的分類類別時,只需添加對應的基分類器,所需的訓練時間將遠遠低于重新訓練整個模型所花費的時間,從而簡化學習過程,降低計算復雜度。

1 CART的開集識別改進算法

1.1 CART基本原理

CART算法采用基尼(GINI)系數的增益來篩選每個節點的分裂特征與分裂值。假設樣本共分為K類,令|D|表示進入當前節點樣本集D的樣本數量,|Dk|則表示其中第k類樣本Dk的數量,GINI系數定義如下:

(1)

式中,pk表示樣本屬于第k類的概率,采用|Dk|/|D|作為概率估計。GINI系數與信息熵有著類似的數學特性,GINI系數越小,則說明樣本的純凈度越高。

以連續型特征為例,CART節點的每次分裂都將當前樣本一分為二。定義條件基尼系數

Gini(y|A)=p(A≤α)Gini(y|A≤α)+

p(A>α)Gini(y|A>α)

(2)

來表示樣本集在選取特征A和對應的分裂值α作為分裂標準后的GINI系數,其中

(3)

可得經驗條件GINI系數為

Gini(y|A)=

(4)

式中,|D1|和|D2|表示分裂后的兩個數據集大小;|D1k|和|D2k|為分裂后的分別屬于第k類的樣本個數。從而可以定義GINI增益為

GGini(y,A)=Gini(y)-Gini(y|A)

(5)

用來表示當前分裂方式對樣本集純凈度的提高程度,從而篩選出最優的分裂標準。

下面給出了CART生成的基本算法步驟如下:

步驟1獲取進入當前節點的樣本集D。

步驟2如果樣本集D中所有樣本屬于同一類別(或者該類別占比超過某一比重),則停止生長形成葉節點,并將該類別作為當前節點的類別。否則,繼續生長。

步驟3獲取樣本集D中所有潛在的分裂特征與對應的分裂值取值集合,并分別計算每一種分裂方式的GINI增益,保留其中使GINI增益取得最大值的分裂特征與分裂值。

步驟4按照步驟3獲取的分裂方式生成兩個子節點,并將樣本集D分裂成D1和D2分別進入這兩個節點,重復步驟1。

1.2 開集識別改進

常規CART葉節點的最終形成,是以單個特征為依據,將一類樣本從樣本集中分離。例如圖1所示的某次節點分裂中,特征A以α為分裂值,將類別k的樣本從樣本集中剝離出,形成一個葉節點;剩余樣本則進入另一個子節點中,繼續分裂或者同樣生成葉節點。

圖1 葉節點生成示意圖

這種葉節點的生成方式可以區分訓練集中包含的類別,但無法識別訓練樣本類別之外的異常樣本。為了使CART具備開集識別的能力,考慮對進入葉節點的待測樣本進行二次確認,當且僅當待測樣本的各維度特征值符合訓練集在葉節點的分布范圍時,才給出分類判決,否則認為待測樣本異常。圖2給出了對一個葉節點做開集識別改進的示意圖。

圖2 葉節點的開集改進示意圖

假定進入原CART葉節點中的所有樣本屬于同一類別,統計特征向量中每一維度特征值Ai的分布,估算該特征值的取值下限Aimin與取值上限Ai max,并以此作為分裂值完成兩次節點分裂,從而把不在該特征值取值范圍內的待測樣本劃分為異常類(None)。對每個維度特征值做與上述相同的兩次節點分裂操作,將最后的葉節點標記為原葉節點所屬類別,作為最終輸出的有效分類判決。

根據上述思路,不改變原有CART生成算法,僅在生成葉節點時執行以下步驟:

步驟1獲取進入當前葉節點的訓練樣本集D,并剔除其中所有不屬于葉節點類別的樣本。對特征向量中的每一維度特征Ai(i=1, 2, …),循環執行步驟2～步驟4。循環結束后執行步驟5。

步驟2利用樣本集D估算特征Ai的取值下限Aimin與取值上限Aimax。

步驟3以特征Ai和分裂值Aimin對當前節點做分裂,將左子節點標記為異常類(None),并進入右子節點。

步驟4以特征Ai和分裂值Aimin對當前節點做分裂,將右子節點標記為異常類(None),并進入左子節點。

步驟5循環結束后,將當前節點標記為原葉節點所屬類別,結束分裂。

上述改進算法并沒有破壞CART原有的結構與生長方式,數據樣本在節點分裂中的分布情況也保持不變。由于只對葉節點做了改動,甚至可以直接在已有CART模型的基礎上修改而不影響原有的判決邏輯。

2 基于改進CART的增量式集成學習算法

2.1 算法原理

集成學習算法對樣本的認知是由它所有基分類器綜合體現的,因此通過修改其中基分類器的組成成分,就可以實現對集成學習算法分類器整體功能的調整。本文認為,如果基分類器具備開集識別的能力,將使這一過程變得非常簡單。以常規CART作為基分類器的集成學習算法只能區分訓練樣本中包含的類別,如果要增加新的分類類別,必須將新老樣本混合作為訓練集重新構建所有的基分類器,否則原有基分類器對新類別樣本必定會做出錯誤的判決[24-25]。而開集識別可以使分類器屏蔽那些不屬于訓練集類別的外來樣本,從而只對已知類別范疇內的樣本做出分類判決。

圖3給出了具備開集識別能力的增量式集成學習算法做出分類判決的示意圖。待測樣本以特征向量的形式進入集成學習算法,由每個基分類器獨立做出分類判決,只有那些具備該類樣本訓練知識的基分類器才會做出有效的判決,其余的基分類器均給出“棄權票”,最終的輸出結果將只取決于所有的有效判決。因此,只需在原有集成學習算法中添加同樣具有開集識別能力的基分類器,就可以使算法在識別新類別樣本的同時,不影響原有類別的分類效果。

圖3 增量式集成學習算法判決示意圖

在上述集成學習算法中,判決策略做出最終判決的一個充分條件是:在所有基分類器的有效判決中,某一類別占據多數。若待測樣本的類別標號為k,包含類別k的基分類器數量為N,其中做出正確且有效判決的數量為n,做出無效判決的數量為n0,其余的則是錯誤但有效的判決;而不包含類別k的基分類器數量為M,其中做出無效判決的數量為m,其余的也必然是錯誤但有效的判決。上述充分條件可以表示為

n>N-n-n0+M-m

(6)

即

2n+n0+m>N+M

(7)

假設所有基分類器相互獨立,且具有相同的集合內分類準確率ptest和開集識別準確率popen,那么滿足該充分條件的概率為

(8)

特別地,如果所有基分類器包含的類別互不重疊(即N=1),那么有

(9)

可以看出,集成學習算法的分類準確率會隨著基分類器的數量呈現出指數下降的形式。因此,讓基分類器維持較高的開集識別準確率是這一增量式算法的重要保證。從“穩定-可塑性”[26]的角度看,當集成學習算法中增加基分類器時,新基分類器的開集識別能力保障了原有分類器的分類效果,即“穩定性”;而原有基分類器的開集識別能力則給新基分類器的加入提供了足夠的空間,即“可塑性”。因此,讓基分類器維持較高的開集識別準確率也有助于解決增量式算法的“穩定-可塑性”問題。

2.2 計算復雜度分析

增量式算法最主要的一個優勢體現在:對一個已有模型進行修改的計算代價遠低于重新訓練一個模型所需的代價。下面將對CART算法與增量式集成學習算法的建模過程進行計算復雜度分析。

根據CART決策樹生成的算法流程分析可知, GINI增益的多次計算占據了絕大多數運算資源。令ND為特征向量維度,K為樣本的類別數量,NK為每個類別包含的訓練樣本數量,Ndiv為CART節點的分裂次數(即非葉節點的個數)。考慮到每一次節點分裂時,都要在每個特征維度遍歷當前節點中的所有訓練樣本,并計算每一種潛在分裂方式的GINI增益,所以CART的計算復雜度可以表示為

TCART(K)=O(NdivNDNKK)

(10)

而通常情況下,分裂次數Ndiv是關于類別數K的線性復雜度,因此

TCART(K)=O(NDNKK2)

(11)

再分析對CART做開集識別改進的計算復雜度。基于原有CART模型,改進算法在每個原有的葉節點上做了2ND次額外的節點分裂,令Nleaf為原CART中葉節點的數量,由于進入葉節點的樣本數已經下降至NK,所以計算復雜度可以表示為

Topen(K)=O(NleafNDNK)

(12)

又因為葉節點數量始終滿足Nleaf=Ndiv+1,也是關于類別數K的線性復雜度,因此

Topen(K)=O(NDNKK)

(13)

集成學習算法的計算復雜度是其所有基分類器的計算復雜度之和。假設將所有類別劃分成Ng組,每一組包含的類別數為Kg,而且每一組都利用對應訓練樣本構建Nt個具有開集識別能力的CART作為基分類器,并最終組合成集成學習分類器。所需的計算復雜度為

Tensemble(K)=O(NgNt(TCART(Kg)+Topen(Kg)))=

(14)

又因為類別數K=NgKg,所以

Tensemble(K)=O(NtNDNKKgK)

(15)

根據上述分析,假設每個類別包含的訓練樣本數量NK不變,CART生長過程的計算量是關于類別數K的平方復雜度,而對CART做開集識別改進的計算量是關于類別數K的線性復雜度。集成學習算法的計算量受到基分類器個數與單個基分類器計算量的影響,通過分組減少每個基分類器的訓練樣本類別數可以降低算法整體的計算量。當每組類別數Kg不變時,集成學習算法的計算量是關于總類別數K的線性復雜度;而總類別數K不變時,降低每組類別數Kg可以線性地降低計算量。

3 仿真與分析

仿真實驗以輻射源分類問題為背景,通過對比常規CART算法,研究本文所述增量式集成學習算法在計算復雜度與分類效果上的表現。仿真數據中包含了不同信噪比(信號與噪聲的功率之比)下132個類別(隨機標號為1～132)的輻射源脈沖信號樣本,數據處理流程如圖4所示。從包含不同輻射源參數的數據庫中隨機抽取132類,產生信號層數據流,疊加不同功率的噪聲來模擬不同的信噪比環境,經過包絡檢波與快速傅里葉變換(fast Fourier transform, FFT)頻譜分析,提取6個維度的特征——脈寬、中心頻率、脈首頻率、脈尾頻率、帶寬、調頻斜率,作為每個樣本的特征向量,計算它們在不同信噪比下的標準差如表1所示,信噪比降低(當信號功率不變時噪聲功率增大),會導致各特征值的測算誤差變大。

圖4 輻射源數據處理流程

表1 不同信噪比下各特征參數的測算標準差

在-4～2 dB的信噪比范圍內,隨機從每一類輻射源脈沖樣本選取60個,產生共計7 920個特征向量作為訓練集,分別根據常規CART算法與增量式集成學習算法進行如下實驗,實驗流程如圖5所示。

圖5 仿真實驗流程

(1)常規CART算法:從包含12個類別的訓練集(720個樣本)開始,每次增加12個類別的(720個)樣本擴充原有的訓練集,訓練集1包含類別1～12,訓練集2包含類別1～24,訓練集3包含類別1～36,以此類推到訓練集11,并在每個訓練集的基礎上構建常規CART分類器,以此模擬分類類別的擴充。如圖5(a)所示。

(2)增量式集成學習算法:將樣本類別1～132依次分成11組,每組12類,以每個組的720個樣本作為一個訓練集,訓練集1包含類別1～12,訓練集2包含類別13～24,訓練集3包含類別25～36,以此類推到訓練集11,在每個訓練集的基礎上分別構建一個CART分類器并做開集識別改進。將這11個CART作為基分類器,逐個添加到增量式集成學習算法中,以此模擬分類類別的擴充。如圖5(b)所示。

本文所有結果是在Ryzen 2700X、16G內存、64位操作系統環境下,以單核單線程運行所得。本實驗隨機從輻射源數據庫中抽取特征參數生成數據集,進行有關計算復雜度和分類效果的仿真,重復8次,最終結果取平均值。

3.1 計算復雜度仿真

本文采用浮點數運算次數(floating-point operations per second, FLOPs)來衡量訓練過程的計算復雜度。隨著分類類別的擴充,分別計算常規CART算法和增量式集成學習算法的FLOPs數值變化,得到關于類別數量的變化曲線如圖6所示。圖7則給出了這兩種算法在訓練過程中的實際耗時曲線。

圖6 FLOPs曲線

圖7 實際耗時曲線

實驗結果基本符合本文第2.2節對計算復雜度的分析,其中常規CART算法是關于樣本類別數的平方復雜度,而本文所述的增量式集成學習算法是關于樣本類別數的線性復雜度。根據FLOPs曲線,為了最終實現132類樣本的分類,后者所需的計算量僅是前者的1/22。從增量的角度看,常規CART算法擴充分類類別時必須重新訓練整個模型,而增量式集成學習算法只需增加對應的基分類器。當分類類別數量從120類擴充到132類時,增量式集成學習算法所需的計算量僅僅是常規CART的1/213。可以看出,在分類類別數量較多時,本文所述增量式集成學習算法在降低計算復雜度上具有明顯的優勢。

需要說明的是,FLOPs曲線沒有考慮CART在節點分裂、后剪枝過程中的額外計算開支與內存分配,而增量式集成學習算法在新建基分類器時重復了這些步驟,所以它的實際耗時曲線比FLOPs曲線具有更大的上升斜率,但這并不影響上述結論。

3.2 分類測試

以不同信噪比環境下的132類信號脈沖樣本作為測試集,其中每個類別包含40個樣本。對增量式集成學習算法中的11個基分類器依次進行以下3組測試:① 使用與訓練集相同類別的測試集(12類共480個樣本)評估CART在開集識別改進之前的集合內分類準確率;② 采用相同的方法評估CART在開集識別改進之后的集合內分類準確率;③ 使用訓練集類別范圍外的測試集(120類共4 800個樣本)評估每個CART在開集識別改進之后的集合外異常檢測率(開集識別準確率)。本文將集合內分類準確率定義為

(16)

式中,Ncorrect表示正確分類的樣本數;Nin表示訓練類別范圍之內的測試樣本數。集合外異常檢測率定義為

(17)

式中,Nopen表示正確識別為異常樣本的數量;Nout表示訓練類別范圍之外的測試樣本數。依次在-4 dB、-2 dB、0 dB、2 dB信噪比環境下,統計各基分類器的識別率均值,得到表2所示結果。

表2 CART開集識別改進前后的分類準確率

結果表明,對CART做開集識別改進會在一定程度上影響集合內的分類準確率,但是這一改進的好處是可以使基分類器具備集合外異常樣本的檢測能力,而且始終保持了很高的準確率,從而讓具有不同分類類別的基分類器可以同時存在于一個集成學習算法中。如果某一特征向量被所有基分類器都識別為異常樣本,就有理由認為該特征向量不屬于整個訓練集的類別范圍,從而實現集成學習算法整體的開集識別。

進一步地,為了觀察不同信噪比環境下,常規CART算法和增量式集成學習算法在擴充類別數量時分類準確率的變化,進行以下測試。分別在-4 dB、-2 dB、0 dB、2 dB信噪比環境下各取一組數據作為4個測試集,其中每個測試集都從各輻射源類別中隨機選取40個脈沖樣本(即每個測試集包含132類共5 280個特征向量)。得到常規CART算法和增量式集成學習算法的集合內分類準確率隨著類別數量增加而變化的曲線如圖8和圖9所示。

圖8 常規CART分類準確率變化曲線

圖9 增量式集成學習算法分類準確率變化曲線

實驗結果表明,兩種算法在信噪比較高的環境下都能維持很高的分類準確率,而隨著信噪比的下降,它們的分類準確率也都產生了不同程度的下滑。其中增量式集成學習算法的分類效果稍遜于常規CART算法,但在信噪比大于等于-4 dB的環境中依然能保持90%以上的分類準確率。另外,隨著類別數量的增加,兩種算法的分類準確率也表現出了不同程度的下降趨勢,不過由于增量式集成學習算法的基分類器始終具有很高的集合外異常檢測率(見表2),增加新的基分類器對原有集成學習算法分類效果的影響十分微小,使之在類別數量較多時依然能維持較高的分類準確率。

4 結束語

本文提出了一種輕量化的增量式集成學習算法,通過開集識別改進保證CART基分類器只會對已知的樣本做出有效判決,從而可以通過添加基分類器的方式來擴充集成學習算法能夠識別的類別范疇。以輻射源分類為背景的仿真實驗表明,該算法可以實現關于類別數量的線性計算復雜度,大幅度降低新增分類類別所需訓練成本;該算法的缺點是犧牲了少量的分類效果,但在一定信噪比范圍內依然能保持相對較高的分類準確率。

本文的仿真實驗只討論了一種最簡單的集成方式,即每個CART基分類器所能識別的樣本類別互不重疊,每次分類最多只有一個基分類器能做出正確的判決。如果不同基分類器的可識別類別互有交集,理論上會增加正確判決出現的概率,從而提高增量式集成學習算法整體的分類效果。這將是下一步的研究工作。