基于動態(tài)異構(gòu)集成的多標(biāo)簽數(shù)據(jù)流分類算法

丁 劍，武紅鑫，韓 萌

(北方民族大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，寧夏 銀川 750021)

0 引 言

隨著大數(shù)據(jù)技術(shù)的快速發(fā)展，生活中產(chǎn)生了大量的數(shù)據(jù)，為了從這些數(shù)據(jù)中獲得人們所需要的信息，開展了許多與數(shù)據(jù)挖掘有關(guān)的研究[1]。這些數(shù)據(jù)呈現(xiàn)出連續(xù)、大容量、高速和動態(tài)變化的特點，稱為數(shù)據(jù)流[2]。由于它們是海量的，同時包含多個標(biāo)簽數(shù)據(jù)，尤其是標(biāo)簽會隨著數(shù)據(jù)分布的動態(tài)變化而出現(xiàn)，這就會導(dǎo)致發(fā)生概念漂移問題。因此，現(xiàn)有的數(shù)據(jù)流分類算法在準(zhǔn)確性方面有很大的挑戰(zhàn)。

許多研究者驗證利用多種學(xué)習(xí)算法構(gòu)成的集成比同構(gòu)集成具有更高生成多樣化分類器的潛力[3]。在單標(biāo)簽分類算法中，文獻(xiàn)[3]利用異構(gòu)集成來進(jìn)行不平衡學(xué)習(xí)。文獻(xiàn)[4]提出一種基于基分類器多樣性的動態(tài)加權(quán)異構(gòu)自適應(yīng)集成分類器，該算法在集成中利用不同類型的基分類器和使用Q統(tǒng)計量來度量集成分類器之間的多樣性。在處理概念隨時間變化的動態(tài)數(shù)據(jù)流時，動態(tài)自適應(yīng)集成可以提供一種合適的方法，可以保留長期存在的歷史概念并覆蓋新出現(xiàn)的概念[4]。同時在以往的研究中，異構(gòu)集成分類器中的基分類器數(shù)量是根據(jù)分類算法的數(shù)量來確定，即它使用H個不同算法生成H個基分類器并將其構(gòu)成集成模型進(jìn)行預(yù)測，例如文獻(xiàn)[5]中的異構(gòu)分類模型。除此之外，文獻(xiàn)[6]采用多種文本特征提取的主流情感進(jìn)行分類集成方法。文獻(xiàn)[7]提出一種基于GSO優(yōu)化權(quán)值的異構(gòu)集成學(xué)習(xí)入侵檢測算法。自適應(yīng)調(diào)整基分類器的數(shù)量可以更符合數(shù)據(jù)流特性，獲得更高的分類結(jié)果。

針對以上問題，本文提出一種基于動態(tài)異構(gòu)集成的多標(biāo)簽數(shù)據(jù)流分類算法(multi-label data stream classification algorithm based on dynamic heterogeneous ensemble，DHEML)，主要貢獻(xiàn)如下：

(1)提出動態(tài)生成候選分類器組E的方法，使E中的候選基分類器始終可以很好處理新實例，為構(gòu)建異構(gòu)集成分類器HE做準(zhǔn)備。

(2)提出自適應(yīng)選擇策略來動態(tài)集成HE，提高集成分類器的泛化性。

(3)在大量數(shù)據(jù)集上進(jìn)行實驗，DHEML在4個評估指標(biāo)中均獲得最好結(jié)果。

1 提出的DHEML算法

1.1 候選分類器組的動態(tài)生成策略

DHEML使用H個分類算法對固定大小的數(shù)據(jù)塊Dt訓(xùn)練生成候選分類器組E={E1，…，Eh，…，EH}， 其中Eh={Ch1，…，Chm，…，ChM}。E的生成過程中，共有兩種情況。為了限制E中候選基分類器的數(shù)目，設(shè)置上限值為K。第一種情況是當(dāng)數(shù)據(jù)塊個數(shù)T

(1)

(2)

取w的偏導(dǎo)數(shù)，并將梯度設(shè)置為零，得如式(3)所示

(3)

將式(3)化簡為式(4)

(4)

為了更好適應(yīng)新傳入的實例，DHEML會使用式(4)計算E中每個候選基分類器的權(quán)重，選出具有最小權(quán)重的候選基分類器并進(jìn)行替換，實現(xiàn)Ei的組內(nèi)動態(tài)更新。

1.2 異構(gòu)集成分類器的自適應(yīng)選擇策略

為了增加最終集成分類器中的泛化性，提出新的異構(gòu)集成分類器的自適應(yīng)選擇策略(adaptive selection strategies for heterogeneous ensemble classifiers，HEAS)，它將整合1.1節(jié)動態(tài)生成的E1，E2，…，EH中分類性能最佳的候選基分類器來構(gòu)成HE。在1.1節(jié)中，權(quán)重是以組為單位進(jìn)行計算的，不同組之間候選基分類器的性能不能進(jìn)行比較。為此，使用另一種方式計算候選基分類器的全局權(quán)重。

(5)

MSEr=∑yp(y)(1-p(y))2

(6)

將MSEm和MSEr結(jié)合，可以給出基分類器的準(zhǔn)確度信息和當(dāng)前類分布的情況。同時為了避免被零除法的問題，添加一個非常小的正值θ。

HEAS是選擇最佳的候選基分類器并將其進(jìn)行整合構(gòu)成HE的策略，使用式(7)計算組內(nèi)候選基分類器Chm的全局權(quán)重，并記為wg

(7)

HEAS的具體過程在算法1中進(jìn)行描述。第(1)～(5)行是為每組E中的候選基分類器計算wg的過程。第(7)行是選出wg最大的候選基分類器。它選擇的過程是按照組內(nèi)基分類器的順序進(jìn)行。首先，它將選出所有E中第一個候選基分類器 {C11，C21，…，CH1} 中具有最大wg的候選基分類器Cbest，并將其加入到HE中；之后，會選出E中的第二個候選基分類器 {C12，C22，…，CH2} 中具有最大的wg的候選基分類器Cbest，再將其加入到HE中。以此類推，直到HE中基分類器的數(shù)目與E中候選基分類器的數(shù)目相等。

算法1：HEAS算法

輸入：E：候選分類器組；C：E中的候選基分類器，M：當(dāng)前E中候選基分類器的數(shù)目，H：分類算法的數(shù)目。

輸出：HE：高層異構(gòu)集成分類器。

(1)For (h=0;h

(2) For (m=0;m

(4) End for

(5)End for

(6)For (m=0;m

(8)HE←將Cbest添加入HE中

(9)End for

(10)輸出HE

1.3 DHEML的實現(xiàn)過程

圖1描述了DHEML算法的實現(xiàn)過程。它分為3個模塊，分別為E的動態(tài)生成、候選基分類器的動態(tài)更新和HE的自適應(yīng)生成。首先是對章節(jié)1.1中的E生成過程進(jìn)行描述。由H種分類算法訓(xùn)練數(shù)據(jù)塊Dt生成H個候選基分類器C1t，C2t，…，CHt。 將同種算法生成的基分類器 {C11，C12，… }，{C21，C22，…}，…，{CH1，CH2，… } 分別構(gòu)成E1，E2，…，EH。 其次是E的動態(tài)更新過程，為了使其具有最佳的分類性能，需要進(jìn)行組內(nèi)候選基分類器的動態(tài)更新。圖1以EH1為例進(jìn)行介紹候選基分類器動態(tài)更新。當(dāng)當(dāng)前組內(nèi)候選基分類器數(shù)量t大于K時，使用最新數(shù)據(jù)塊Dt+1生成候選基分類器CHt+1去替換舊的、過時的候選基分類器。使用1.1節(jié)中的式(4)計算E中每個候選基分類器的權(quán)重w，選擇權(quán)重最小的基分類器CH2進(jìn)行替換。最后是使用章節(jié)1.2的HEAS動態(tài)生成HE。為了增加集成分類器的泛化性，算法將每個E中最優(yōu)的候選基分類器加入到HE中。DHEML使用章節(jié)1.2節(jié)中的式(7)計算每個E中候選基分類器的wg。 按圖中的列進(jìn)行比較，如C11，C21，…，CH1， 通過判斷選出wg最大的候選基分類器并將其加入到HE中。

圖1 DHEML算法實現(xiàn)過程

圖1生成的HE是一種極端的情況，即采用HEAS方法對不同算法生成的候選基分類器都有一個選中，但現(xiàn)實中并非如此，它會根據(jù)wg選擇出最合適、性能最好的候選基分類器將其加入到HE中，可能某個算法構(gòu)成的候選基分類器都沒有被選中，或者都被選中。該算法不再是根據(jù)構(gòu)建候選基分類器方法的類型來決定HE中基分類器的數(shù)量。

DHEML的訓(xùn)練與預(yù)測具體細(xì)節(jié)如算法2所示。第(2)～(7)行描述了該算法的預(yù)測階段，其中第(3)行使用章節(jié)1.2節(jié)的HEAS算法構(gòu)建HE。第(5)～(21)行描述了訓(xùn)練階段。其中第(6)～(8)行使用H種分類算法訓(xùn)練Dt數(shù)據(jù)塊生成H種候選基分類器。第(10)～(16)行是為E中候選基分類器的動態(tài)更新過程，即當(dāng)前組內(nèi)候選基分類器的數(shù)量大于上限數(shù)量K時，需要使用1.1節(jié)的式(4)計算權(quán)重，將權(quán)重值最小的候選基分類器與最新生成的候選基分類器進(jìn)行替換。第(17)～(20)行為候選基分類器的添加和增量更新過程。

算法2：DHEML訓(xùn)練與預(yù)測算法

輸入：D：數(shù)據(jù)流，Dt：數(shù)據(jù)塊，C：候選基分類器，E：候選分類器組，K：E中基分類器的上限數(shù)量，H：分類算法的數(shù)目，HE：異構(gòu)集成分類器。

(1)WhileD≠null //當(dāng)數(shù)據(jù)流中的實例不為空時

(2)xi←當(dāng)前的數(shù)據(jù)實例

(3)HE←使用HEAS構(gòu)建HE//使用1.2節(jié)的算法1

(5)IfDtis full //當(dāng)數(shù)據(jù)塊中的實例達(dá)到固定數(shù)目時

(6) For (h=0;h

(7)Chin←分類算法h使用Dt構(gòu)建候選基分類器

(8) End for

(9)t++; //統(tǒng)計Eh組內(nèi)候選基分類器的數(shù)量

(10) Ift>K//當(dāng)Eh中候選基分類器的數(shù)量大于上限數(shù)目時

(11) For (h=0;h

(12) 使用式(4)計算Eh中每個候選基分類器的權(quán)重w

(13)Chout←選擇Eh中權(quán)重最小的候選基分類器

(14)Eh←Eh-Chout//將Chout從Eh中移除

(15) End for

(16) End if

(17) For (h=0;h

(18)Eh←Eh∪Chin

(19)Eh←使用Di訓(xùn)練Eh中的候選基分類器 //對除Chin之外的其余基分類器進(jìn)行增量學(xué)習(xí)

(20) End for

(21) End if

(22)End While

2 實驗結(jié)果與分析

本實驗軟件環(huán)境是大規(guī)模在線分析開源平臺(massive online analysis，MOA)[12]，并結(jié)合MEKA[13]中的多標(biāo)簽方法。實驗預(yù)測采用了交錯式訓(xùn)練與測試(interleaved-test-then-train，ITTT)的評估方法[9]。

本章將提出3個DHEML算法與10種分類算法(EBR[13]、ECC[13]、EPS[14]、GORT[9]、EBRT[15]、EaBR、EaCC、EaPS[16]、ASEKNN[17]、MLSL[18])進(jìn)行對比，其中，DHEML1采用PS和CC的分類算法構(gòu)建HE，DHEML2采用BR和CC的分類算法構(gòu)建HE，DHEML3采用BR和CC的分類算法構(gòu)建HE。

2.1 實驗設(shè)置

實驗從研究領(lǐng)域、實例數(shù)(n)、特征數(shù)(m)、標(biāo)簽數(shù)(L)、標(biāo)簽基數(shù)(LC(D))和標(biāo)簽密度(LD(D))對數(shù)據(jù)集進(jìn)行介紹，見表1。其中，標(biāo)簽基數(shù)和標(biāo)簽密度如式(8)、式(9)所示

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

(8)

(9)

在多標(biāo)簽分類中，單一的使用某些評估指標(biāo)作為評估指標(biāo)是不合適的。針對多標(biāo)簽分類設(shè)計了許多評估指標(biāo)。本文使用準(zhǔn)確度、實例的F1值、微觀F1和宏觀F1來進(jìn)行評估。

2.2 實驗分析

(1)固定與動態(tài)調(diào)整基分類器對比實驗

傳統(tǒng)的異構(gòu)集成分類器是由不同分類算法訓(xùn)練的基分類器構(gòu)成，基分類器的數(shù)量由采用的不同分類算法的數(shù)量決定。為了驗證動態(tài)調(diào)整基分類器的數(shù)量可以提高分類性能的說法，本節(jié)將固定基分類器數(shù)量的HEML與動態(tài)調(diào)整基分類器數(shù)量的DHEML進(jìn)行實驗。在HEML中，每次選擇E中wg值最大的候選基分類器加入到HE中。為了保證小數(shù)據(jù)集也可以生成多樣性的基分類器，塊的大小設(shè)置為500。實驗結(jié)果如圖2所示，在大多數(shù)的情況下，DHEML算法比HEML算法具有更好的性能。DHEML2在Philosophy數(shù)據(jù)集上對比結(jié)果尤為明顯。由此得出自適應(yīng)調(diào)整異構(gòu)集成分類器中基分類器的數(shù)量可以提高分類的性能。

圖2 異構(gòu)集成分類對比

(2)與同構(gòu)/異構(gòu)集成的對比實驗

將DHEML1、DHEML2、DHEML3與EBR、ECC、EPS、GORT、ASEKNN、EBRT、EaBR、EaCC、EaPS算法在6個數(shù)據(jù)集上進(jìn)行對比的結(jié)果見表2，詳細(xì)的實驗結(jié)果包括每個算法的準(zhǔn)確度、實例的F1值、微觀F1和宏觀F1。最好的結(jié)果使用加粗表示。實驗中設(shè)置基分類器的數(shù)量均為10。

從表2中可以看出，DHEML1、DHEML2、DHEML3在4個評估指標(biāo)準(zhǔn)確度、實例的F1值、微觀F1和宏觀 F1上均獲得較好的結(jié)果，其中DHEML1算法獲得了最好排名。與EBR、ECC、EPS相比，在數(shù)據(jù)集Medical的準(zhǔn)確度中，DHEML1比EBR高9.3%，比ECC高9.7%，比EPS高8.1%。在數(shù)據(jù)集Ohsumed的準(zhǔn)確度中，DHEML3比EBR高12.5%，比ECC高13.6%，比EPS高18.1%。

與增加窗口機(jī)制的EaBR、EaCC、EaPS算法相比，使用DHEML的算法也可以獲得不錯的實驗結(jié)果。而在數(shù)據(jù)集Ohsumed上的準(zhǔn)確度中，對比算法EaCC卻不是很樂觀。DHEML1、DHEML2、DHEML3 比EaCC有明顯的提升。其中，DHEML1算法比EaCC的Accuracy值高達(dá)22.1%，DHEML2的算法比EaCC的Accuracy值高達(dá)19%，DHEML3的算法比EaCC的Accuracy值高達(dá)31.2%?？傮w來說，DHEML的算法比使用同構(gòu)集成的算法結(jié)果性能更好。因為該算法使用HEAS來選擇可以獲得更好性能的基分類器構(gòu)成HE。由此得出，采用異構(gòu)集成的分類算法提高集成分類器的多樣性，從而有效提高分類結(jié)果。

在時間效率方面，小型數(shù)據(jù)集時所有DHEML擁有較小的時間效率，但面對較大數(shù)據(jù)集時，隨著實例的增加和特征關(guān)系的復(fù)雜性，幾何加權(quán)方法會消耗大量的時間，所有DHEML的運行時間增加，比同構(gòu)集成算法花費更多時間。EPS的運行時間較短，這是因為它可以修剪不經(jīng)常出現(xiàn)的標(biāo)簽集來關(guān)注標(biāo)簽最重要的關(guān)系，從而節(jié)省時間。

(3)數(shù)據(jù)流分析

當(dāng)實例不斷增加，數(shù)據(jù)流算法的分類能力也會隨之改變。本節(jié)研究隨著實例的增加和實例分布變化引起概念漂移現(xiàn)象時，DHEML算法是否具有較好的自適應(yīng)調(diào)節(jié)能力。當(dāng)數(shù)據(jù)集較小時，如果分類算法選擇的數(shù)據(jù)塊太大，則不能很好應(yīng)對突變漂移，同時基分類器的數(shù)量也會減小，導(dǎo)致集成分類器的泛化性降低，使分類結(jié)果降低。當(dāng)數(shù)據(jù)集較大時，如果分類算法選擇的數(shù)據(jù)塊較小，則運行時間增多。針對以上兩種情況，本節(jié)選擇塊大小為500進(jìn)行實驗，并給出了10種算法分別在數(shù)據(jù)集Slashdot和Ohsumed上基于實例的F1的評估結(jié)果。結(jié)果如圖3所示。

圖3 基于窗口的模型評估

圖3可以看出，隨著實例的增加，集成分類器的分類性能也在不斷的變化。EPS、EaPS在兩個數(shù)據(jù)集中都位于圖片的中間位置，在圖3(a)中還呈現(xiàn)下降的趨勢，這是因為它的剪枝策略可能修剪掉了有用的信息使分類器不能充分的學(xué)習(xí)。DHEML1的最終結(jié)果都處于較好的位置。在圖3(b)中，DHEML1算法在訓(xùn)練基分類器時需要較多的實例才可以獲得更好的結(jié)果。由此可知，DHEML在數(shù)據(jù)流環(huán)境中可以較好應(yīng)對概念漂移同時具有較高的評估值。

3 結(jié)束語

為了實現(xiàn)自適應(yīng)調(diào)整基分類器的數(shù)量從而得到更符合數(shù)據(jù)特性的HE，本文提出了DHEML算法。為了可以處理新傳入的數(shù)據(jù)，使用幾何加權(quán)計算候選基分類器的權(quán)重，根據(jù)權(quán)重進(jìn)行更新替換；根據(jù)HEAS動態(tài)選擇適當(dāng)?shù)暮蜻x基分類器來構(gòu)建HE。通過實驗得知，自適應(yīng)調(diào)整基分類器的數(shù)量可以提高分類結(jié)果，同時與其它集成分類器的算法相比，DHEML算法可以在準(zhǔn)確度、實例的F1值、微觀F1和宏觀 F1上獲得較好的結(jié)果，綜合排名最好。但隨著數(shù)據(jù)集實例的增加，該算法的時間效率開始增加。在未來的工作中，本課題組將關(guān)注算法時間效率，在保證評估指標(biāo)穩(wěn)定的情況下，使E的候選基分類器生成和更新階段可以并行運行，提高算法的時間效率。