輕量化的增量式集成學(xué)習(xí)算法設(shè)計(jì)

丁嘉輝, 湯建龍, 于正洋

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

0 引 言

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

針對(duì)上述問題,本文提出了一種輕量化的增量式集成學(xué)習(xí)算法。首先,讓原有CART的葉節(jié)點(diǎn)再生長(zhǎng),在不破壞現(xiàn)有結(jié)構(gòu)的基礎(chǔ)上使之具備開集識(shí)別的能力,從而能夠辨別訓(xùn)練集類別之外的異常樣本。然后采用增量式的集成策略[21-23],以若干個(gè)具有開集識(shí)別能力的CART作為基分類器構(gòu)成增量式集成學(xué)習(xí)算法,每個(gè)基分類器只負(fù)責(zé)其中一部分類別的分類。開集識(shí)別能力確保了每個(gè)基分類器只會(huì)對(duì)自己“認(rèn)識(shí)”的樣本做出判決,否則投出“棄權(quán)票”。因此,當(dāng)需要擴(kuò)充新的分類類別時(shí),只需添加對(duì)應(yīng)的基分類器,所需的訓(xùn)練時(shí)間將遠(yuǎn)遠(yuǎn)低于重新訓(xùn)練整個(gè)模型所花費(fèi)的時(shí)間,從而簡(jiǎn)化學(xué)習(xí)過程,降低計(jì)算復(fù)雜度。

1 CART的開集識(shí)別改進(jìn)算法

1.1 CART基本原理

CART算法采用基尼(GINI)系數(shù)的增益來(lái)篩選每個(gè)節(jié)點(diǎn)的分裂特征與分裂值。假設(shè)樣本共分為K類,令|D|表示進(jìn)入當(dāng)前節(jié)點(diǎn)樣本集D的樣本數(shù)量,|Dk|則表示其中第k類樣本Dk的數(shù)量,GINI系數(shù)定義如下:

(1)

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

以連續(xù)型特征為例,CART節(jié)點(diǎn)的每次分裂都將當(dāng)前樣本一分為二。定義條件基尼系數(shù)

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

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

(2)

來(lái)表示樣本集在選取特征A和對(duì)應(yīng)的分裂值α作為分裂標(biāo)準(zhǔn)后的GINI系數(shù),其中

(3)

可得經(jīng)驗(yàn)條件GINI系數(shù)為

Gini(y|A)=

(4)

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

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

(5)

用來(lái)表示當(dāng)前分裂方式對(duì)樣本集純凈度的提高程度,從而篩選出最優(yōu)的分裂標(biāo)準(zhǔn)。

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

步驟1獲取進(jìn)入當(dāng)前節(jié)點(diǎn)的樣本集D。

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

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

步驟4按照步驟3獲取的分裂方式生成兩個(gè)子節(jié)點(diǎn),并將樣本集D分裂成D1和D2分別進(jìn)入這兩個(gè)節(jié)點(diǎn),重復(fù)步驟1。

1.2 開集識(shí)別改進(jìn)

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

圖1 葉節(jié)點(diǎn)生成示意圖

這種葉節(jié)點(diǎn)的生成方式可以區(qū)分訓(xùn)練集中包含的類別,但無(wú)法識(shí)別訓(xùn)練樣本類別之外的異常樣本。為了使CART具備開集識(shí)別的能力,考慮對(duì)進(jìn)入葉節(jié)點(diǎn)的待測(cè)樣本進(jìn)行二次確認(rèn),當(dāng)且僅當(dāng)待測(cè)樣本的各維度特征值符合訓(xùn)練集在葉節(jié)點(diǎn)的分布范圍時(shí),才給出分類判決,否則認(rèn)為待測(cè)樣本異常。圖2給出了對(duì)一個(gè)葉節(jié)點(diǎn)做開集識(shí)別改進(jìn)的示意圖。

圖2 葉節(jié)點(diǎn)的開集改進(jìn)示意圖

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

根據(jù)上述思路,不改變?cè)蠧ART生成算法,僅在生成葉節(jié)點(diǎn)時(shí)執(zhí)行以下步驟:

步驟1獲取進(jìn)入當(dāng)前葉節(jié)點(diǎn)的訓(xùn)練樣本集D,并剔除其中所有不屬于葉節(jié)點(diǎn)類別的樣本。對(duì)特征向量中的每一維度特征Ai(i=1, 2, …),循環(huán)執(zhí)行步驟2～步驟4。循環(huán)結(jié)束后執(zhí)行步驟5。

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

步驟3以特征Ai和分裂值A(chǔ)imin對(duì)當(dāng)前節(jié)點(diǎn)做分裂,將左子節(jié)點(diǎn)標(biāo)記為異常類(None),并進(jìn)入右子節(jié)點(diǎn)。

步驟4以特征Ai和分裂值A(chǔ)imin對(duì)當(dāng)前節(jié)點(diǎn)做分裂,將右子節(jié)點(diǎn)標(biāo)記為異常類(None),并進(jìn)入左子節(jié)點(diǎn)。

步驟5循環(huán)結(jié)束后,將當(dāng)前節(jié)點(diǎn)標(biāo)記為原葉節(jié)點(diǎn)所屬類別,結(jié)束分裂。

上述改進(jìn)算法并沒有破壞CART原有的結(jié)構(gòu)與生長(zhǎng)方式,數(shù)據(jù)樣本在節(jié)點(diǎn)分裂中的分布情況也保持不變。由于只對(duì)葉節(jié)點(diǎn)做了改動(dòng),甚至可以直接在已有CART模型的基礎(chǔ)上修改而不影響原有的判決邏輯。

2 基于改進(jìn)CART的增量式集成學(xué)習(xí)算法

2.1 算法原理

集成學(xué)習(xí)算法對(duì)樣本的認(rèn)知是由它所有基分類器綜合體現(xiàn)的,因此通過修改其中基分類器的組成成分,就可以實(shí)現(xiàn)對(duì)集成學(xué)習(xí)算法分類器整體功能的調(diào)整。本文認(rèn)為,如果基分類器具備開集識(shí)別的能力,將使這一過程變得非常簡(jiǎn)單。以常規(guī)CART作為基分類器的集成學(xué)習(xí)算法只能區(qū)分訓(xùn)練樣本中包含的類別,如果要增加新的分類類別,必須將新老樣本混合作為訓(xùn)練集重新構(gòu)建所有的基分類器,否則原有基分類器對(duì)新類別樣本必定會(huì)做出錯(cuò)誤的判決[24-25]。而開集識(shí)別可以使分類器屏蔽那些不屬于訓(xùn)練集類別的外來(lái)樣本,從而只對(duì)已知類別范疇內(nèi)的樣本做出分類判決。

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

圖3 增量式集成學(xué)習(xí)算法判決示意圖

在上述集成學(xué)習(xí)算法中,判決策略做出最終判決的一個(gè)充分條件是:在所有基分類器的有效判決中,某一類別占據(jù)多數(shù)。若待測(cè)樣本的類別標(biāo)號(hào)為k,包含類別k的基分類器數(shù)量為N,其中做出正確且有效判決的數(shù)量為n,做出無(wú)效判決的數(shù)量為n0,其余的則是錯(cuò)誤但有效的判決;而不包含類別k的基分類器數(shù)量為M,其中做出無(wú)效判決的數(shù)量為m,其余的也必然是錯(cuò)誤但有效的判決。上述充分條件可以表示為

n>N-n-n0+M-m

(6)

即

2n+n0+m>N+M

(7)

假設(shè)所有基分類器相互獨(dú)立,且具有相同的集合內(nèi)分類準(zhǔn)確率ptest和開集識(shí)別準(zhǔn)確率popen,那么滿足該充分條件的概率為

(8)

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

(9)

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

2.2 計(jì)算復(fù)雜度分析

增量式算法最主要的一個(gè)優(yōu)勢(shì)體現(xiàn)在:對(duì)一個(gè)已有模型進(jìn)行修改的計(jì)算代價(jià)遠(yuǎn)低于重新訓(xùn)練一個(gè)模型所需的代價(jià)。下面將對(duì)CART算法與增量式集成學(xué)習(xí)算法的建模過程進(jìn)行計(jì)算復(fù)雜度分析。

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

TCART(K)=O(NdivNDNKK)

(10)

而通常情況下,分裂次數(shù)Ndiv是關(guān)于類別數(shù)K的線性復(fù)雜度,因此

TCART(K)=O(NDNKK2)

(11)

再分析對(duì)CART做開集識(shí)別改進(jìn)的計(jì)算復(fù)雜度。基于原有CART模型,改進(jìn)算法在每個(gè)原有的葉節(jié)點(diǎn)上做了2ND次額外的節(jié)點(diǎn)分裂,令Nleaf為原CART中葉節(jié)點(diǎn)的數(shù)量,由于進(jìn)入葉節(jié)點(diǎn)的樣本數(shù)已經(jīng)下降至NK,所以計(jì)算復(fù)雜度可以表示為

Topen(K)=O(NleafNDNK)

(12)

又因?yàn)槿~節(jié)點(diǎn)數(shù)量始終滿足Nleaf=Ndiv+1,也是關(guān)于類別數(shù)K的線性復(fù)雜度,因此

Topen(K)=O(NDNKK)

(13)

集成學(xué)習(xí)算法的計(jì)算復(fù)雜度是其所有基分類器的計(jì)算復(fù)雜度之和。假設(shè)將所有類別劃分成Ng組,每一組包含的類別數(shù)為Kg,而且每一組都利用對(duì)應(yīng)訓(xùn)練樣本構(gòu)建Nt個(gè)具有開集識(shí)別能力的CART作為基分類器,并最終組合成集成學(xué)習(xí)分類器。所需的計(jì)算復(fù)雜度為

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

(14)

又因?yàn)轭悇e數(shù)K=NgKg,所以

Tensemble(K)=O(NtNDNKKgK)

(15)

根據(jù)上述分析,假設(shè)每個(gè)類別包含的訓(xùn)練樣本數(shù)量NK不變,CART生長(zhǎng)過程的計(jì)算量是關(guān)于類別數(shù)K的平方復(fù)雜度,而對(duì)CART做開集識(shí)別改進(jìn)的計(jì)算量是關(guān)于類別數(shù)K的線性復(fù)雜度。集成學(xué)習(xí)算法的計(jì)算量受到基分類器個(gè)數(shù)與單個(gè)基分類器計(jì)算量的影響,通過分組減少每個(gè)基分類器的訓(xùn)練樣本類別數(shù)可以降低算法整體的計(jì)算量。當(dāng)每組類別數(shù)Kg不變時(shí),集成學(xué)習(xí)算法的計(jì)算量是關(guān)于總類別數(shù)K的線性復(fù)雜度;而總類別數(shù)K不變時(shí),降低每組類別數(shù)Kg可以線性地降低計(jì)算量。

3 仿真與分析

仿真實(shí)驗(yàn)以輻射源分類問題為背景,通過對(duì)比常規(guī)CART算法,研究本文所述增量式集成學(xué)習(xí)算法在計(jì)算復(fù)雜度與分類效果上的表現(xiàn)。仿真數(shù)據(jù)中包含了不同信噪比(信號(hào)與噪聲的功率之比)下132個(gè)類別(隨機(jī)標(biāo)號(hào)為1～132)的輻射源脈沖信號(hào)樣本,數(shù)據(jù)處理流程如圖4所示。從包含不同輻射源參數(shù)的數(shù)據(jù)庫(kù)中隨機(jī)抽取132類,產(chǎn)生信號(hào)層數(shù)據(jù)流,疊加不同功率的噪聲來(lái)模擬不同的信噪比環(huán)境,經(jīng)過包絡(luò)檢波與快速傅里葉變換(fast Fourier transform, FFT)頻譜分析,提取6個(gè)維度的特征——脈寬、中心頻率、脈首頻率、脈尾頻率、帶寬、調(diào)頻斜率,作為每個(gè)樣本的特征向量,計(jì)算它們?cè)诓煌旁氡认碌臉?biāo)準(zhǔn)差如表1所示,信噪比降低(當(dāng)信號(hào)功率不變時(shí)噪聲功率增大),會(huì)導(dǎo)致各特征值的測(cè)算誤差變大。

圖4 輻射源數(shù)據(jù)處理流程

表1 不同信噪比下各特征參數(shù)的測(cè)算標(biāo)準(zhǔn)差

在-4～2 dB的信噪比范圍內(nèi),隨機(jī)從每一類輻射源脈沖樣本選取60個(gè),產(chǎn)生共計(jì)7 920個(gè)特征向量作為訓(xùn)練集,分別根據(jù)常規(guī)CART算法與增量式集成學(xué)習(xí)算法進(jìn)行如下實(shí)驗(yàn),實(shí)驗(yàn)流程如圖5所示。

圖5 仿真實(shí)驗(yàn)流程

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

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

本文所有結(jié)果是在Ryzen 2700X、16G內(nèi)存、64位操作系統(tǒng)環(huán)境下,以單核單線程運(yùn)行所得。本實(shí)驗(yàn)隨機(jī)從輻射源數(shù)據(jù)庫(kù)中抽取特征參數(shù)生成數(shù)據(jù)集,進(jìn)行有關(guān)計(jì)算復(fù)雜度和分類效果的仿真,重復(fù)8次,最終結(jié)果取平均值。

3.1 計(jì)算復(fù)雜度仿真

本文采用浮點(diǎn)數(shù)運(yùn)算次數(shù)(floating-point operations per second, FLOPs)來(lái)衡量訓(xùn)練過程的計(jì)算復(fù)雜度。隨著分類類別的擴(kuò)充,分別計(jì)算常規(guī)CART算法和增量式集成學(xué)習(xí)算法的FLOPs數(shù)值變化,得到關(guān)于類別數(shù)量的變化曲線如圖6所示。圖7則給出了這兩種算法在訓(xùn)練過程中的實(shí)際耗時(shí)曲線。

圖6 FLOPs曲線

圖7 實(shí)際耗時(shí)曲線

實(shí)驗(yàn)結(jié)果基本符合本文第2.2節(jié)對(duì)計(jì)算復(fù)雜度的分析,其中常規(guī)CART算法是關(guān)于樣本類別數(shù)的平方復(fù)雜度,而本文所述的增量式集成學(xué)習(xí)算法是關(guān)于樣本類別數(shù)的線性復(fù)雜度。根據(jù)FLOPs曲線,為了最終實(shí)現(xiàn)132類樣本的分類,后者所需的計(jì)算量?jī)H是前者的1/22。從增量的角度看,常規(guī)CART算法擴(kuò)充分類類別時(shí)必須重新訓(xùn)練整個(gè)模型,而增量式集成學(xué)習(xí)算法只需增加對(duì)應(yīng)的基分類器。當(dāng)分類類別數(shù)量從120類擴(kuò)充到132類時(shí),增量式集成學(xué)習(xí)算法所需的計(jì)算量?jī)H僅是常規(guī)CART的1/213?？梢钥闯?在分類類別數(shù)量較多時(shí),本文所述增量式集成學(xué)習(xí)算法在降低計(jì)算復(fù)雜度上具有明顯的優(yōu)勢(shì)。

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

3.2 分類測(cè)試

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

(16)

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

(17)

式中,Nopen表示正確識(shí)別為異常樣本的數(shù)量;Nout表示訓(xùn)練類別范圍之外的測(cè)試樣本數(shù)。依次在-4 dB、-2 dB、0 dB、2 dB信噪比環(huán)境下,統(tǒng)計(jì)各基分類器的識(shí)別率均值,得到表2所示結(jié)果。

表2 CART開集識(shí)別改進(jìn)前后的分類準(zhǔn)確率

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

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

圖8 常規(guī)CART分類準(zhǔn)確率變化曲線

圖9 增量式集成學(xué)習(xí)算法分類準(zhǔn)確率變化曲線

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

4 結(jié)束語(yǔ)

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

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