丁 劍，武紅鑫，韓 萌

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

0 引 言

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

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

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

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

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

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

1 提出的DHEML算法

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

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

(1)

(2)

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

(3)

將式(3)化簡(jiǎn)為式(4)

(4)

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

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

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

(5)

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

(6)

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

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

(7)

HEAS的具體過(guò)程在算法1中進(jìn)行描述。第(1)～(5)行是為每組E中的候選基分類器計(jì)算wg的過(guò)程。第(7)行是選出wg最大的候選基分類器。它選擇的過(guò)程是按照組內(nèi)基分類器的順序進(jìn)行。首先，它將選出所有E中第一個(gè)候選基分類器 {C11，C21，…，CH1} 中具有最大wg的候選基分類器Cbest，并將其加入到HE中；之后，會(huì)選出E中的第二個(gè)候選基分類器 {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的實(shí)現(xiàn)過(guò)程

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

圖1 DHEML算法實(shí)現(xiàn)過(guò)程

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

DHEML的訓(xùn)練與預(yù)測(cè)具體細(xì)節(jié)如算法2所示。第(2)～(7)行描述了該算法的預(yù)測(cè)階段，其中第(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中候選基分類器的動(dòng)態(tài)更新過(guò)程，即當(dāng)前組內(nèi)候選基分類器的數(shù)量大于上限數(shù)量K時(shí)，需要使用1.1節(jié)的式(4)計(jì)算權(quán)重，將權(quán)重值最小的候選基分類器與最新生成的候選基分類器進(jìn)行替換。第(17)～(20)行為候選基分類器的添加和增量更新過(guò)程。

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

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

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

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

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

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

(6) For (h=0;h

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

(8) End for

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

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

(11) For (h=0;h

(12) 使用式(4)計(jì)算Eh中每個(gè)候選基分類器的權(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中的候選基分類器 //對(duì)除Chin之外的其余基分類器進(jìn)行增量學(xué)習(xí)

(20) End for

(21) End if

(22)End While

2 實(shí)驗(yàn)結(jié)果與分析

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

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

2.1 實(shí)驗(yàn)設(shè)置

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

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

(8)

(9)

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

2.2 實(shí)驗(yàn)分析

(1)固定與動(dòng)態(tài)調(diào)整基分類器對(duì)比實(shí)驗(yàn)

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

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

(2)與同構(gòu)/異構(gòu)集成的對(duì)比實(shí)驗(yàn)

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

從表2中可以看出，DHEML1、DHEML2、DHEML3在4個(gè)評(píng)估指標(biāo)準(zhǔn)確度、實(shí)例的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的算法也可以獲得不錯(cuò)的實(shí)驗(yàn)結(jié)果。而在數(shù)據(jù)集Ohsumed上的準(zhǔn)確度中，對(duì)比算法EaCC卻不是很樂(lè)觀。DHEML1、DHEML2、DHEML3 比EaCC有明顯的提升。其中，DHEML1算法比EaCC的Accuracy值高達(dá)22.1%，DHEML2的算法比EaCC的Accuracy值高達(dá)19%，DHEML3的算法比EaCC的Accuracy值高達(dá)31.2%?？傮w來(lái)說(shuō)，DHEML的算法比使用同構(gòu)集成的算法結(jié)果性能更好。因?yàn)樵撍惴ㄊ褂肏EAS來(lái)選擇可以獲得更好性能的基分類器構(gòu)成HE。由此得出，采用異構(gòu)集成的分類算法提高集成分類器的多樣性，從而有效提高分類結(jié)果。

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

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

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

圖3 基于窗口的模型評(píng)估

圖3可以看出，隨著實(shí)例的增加，集成分類器的分類性能也在不斷的變化。EPS、EaPS在兩個(gè)數(shù)據(jù)集中都位于圖片的中間位置，在圖3(a)中還呈現(xiàn)下降的趨勢(shì)，這是因?yàn)樗募糁Σ呗钥赡苄藜舻袅擞杏玫男畔⑹狗诸惼鞑荒艹浞值膶W(xué)習(xí)。DHEML1的最終結(jié)果都處于較好的位置。在圖3(b)中，DHEML1算法在訓(xùn)練基分類器時(shí)需要較多的實(shí)例才可以獲得更好的結(jié)果。由此可知，DHEML在數(shù)據(jù)流環(huán)境中可以較好應(yīng)對(duì)概念漂移同時(shí)具有較高的評(píng)估值。

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

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