面向概念漂移集成分類的三支決策優(yōu)化方法

徐健鋒，辛 朋，薛國澤，楊迎方

(1. 南昌大學(xué) 信息工程學(xué)院 江西 南昌 330031； 2. 南昌大學(xué) 軟件學(xué)院 江西 南昌 330047； 3. 同濟(jì)大學(xué) 電子與信息工程學(xué)院 上海 201804)

0 引言

隨著互聯(lián)網(wǎng)的快速發(fā)展，許多行業(yè)領(lǐng)域每時(shí)每刻都會(huì)產(chǎn)生海量的數(shù)據(jù)，它們通常以數(shù)據(jù)流[1]的形式產(chǎn)生和到達(dá)。隨著數(shù)據(jù)流的高速產(chǎn)生，其數(shù)據(jù)分布會(huì)發(fā)生改變，將這種數(shù)據(jù)分布隨著時(shí)間推移而發(fā)生變化的現(xiàn)象稱為“概念漂移”[2]。如何在快速變化的數(shù)據(jù)流中有效地處理概念漂移問題，已經(jīng)成為許多國內(nèi)外學(xué)者研究的重要課題[3-4]。目前有關(guān)抵抗概念漂移技術(shù)的研究主要集中在三個(gè)方向：自適應(yīng)基學(xué)習(xí)器[5]、單分類器設(shè)計(jì)模式[6]和多分類器集成技術(shù)[7-10]。自適應(yīng)基學(xué)習(xí)器通過對(duì)傳統(tǒng)機(jī)器學(xué)習(xí)算法加以改進(jìn)，使其在復(fù)雜多變的數(shù)據(jù)流環(huán)境中具有較好的適應(yīng)性。單分類器設(shè)計(jì)模式通常采用的方法有滑動(dòng)窗口技術(shù)和樣本加權(quán)，以此對(duì)數(shù)據(jù)集進(jìn)行重新構(gòu)造以獲得良好的實(shí)時(shí)表現(xiàn)。多分類器集成技術(shù)被認(rèn)為是處理概念漂移問題更為有效的方法，其主要思想是在不同時(shí)期的數(shù)據(jù)塊上構(gòu)造多個(gè)基分類器，并利用相應(yīng)結(jié)合策略產(chǎn)生最終的分類結(jié)果。在多分類器集成過程中，基分類器應(yīng)是準(zhǔn)確且多樣的[11-12]，多樣性通常體現(xiàn)在成員間的差異性方面?；诸惼鞑町愋允侵覆煌幕诸惼鲗?duì)相同的實(shí)例進(jìn)行分類而得到不同的類別，差異性可以通過不確定性進(jìn)行度量。提升多樣性的目的在于當(dāng)少數(shù)分類器分類錯(cuò)誤時(shí)，其他分類器也會(huì)在集成整合過程中糾正這個(gè)問題，從而使集成模型在復(fù)雜的數(shù)據(jù)環(huán)境中可以保持穩(wěn)定的分類性能。尤其在不斷發(fā)生概念變化的數(shù)據(jù)流環(huán)境中，考慮基分類器間的多樣性可避免陷入局部最優(yōu)解，提升集成模型的準(zhǔn)確性和泛化性。而當(dāng)前分類集成方法研究[13-14]主要把準(zhǔn)確性作為基分類器唯一的質(zhì)量衡量依據(jù)，對(duì)基分類器多樣性問題卻鮮有研究。如果能夠設(shè)計(jì)出一種在準(zhǔn)確性前提下考慮基分類器多樣性指標(biāo)的質(zhì)量評(píng)價(jià)方法，并根據(jù)該評(píng)價(jià)方法對(duì)基分類器的選擇制定合理的優(yōu)化策略，將會(huì)提升集成模型的分類效果。為此，本文提出一種基于信息熵的基分類器不確定性度量方法，作為基分類器的多樣性度量指標(biāo)；將其與經(jīng)典的準(zhǔn)確性度量方法進(jìn)行融合，作為基分類器的質(zhì)量評(píng)價(jià)策略；結(jié)合三支決策思想[15]，提出了一種改進(jìn)的基于質(zhì)量度量的基分類器三支過濾算法。

1 相關(guān)技術(shù)研究

1.1 基于數(shù)據(jù)塊的集成分類模型

集成技術(shù)被認(rèn)為是處理概念漂移問題較為有效的方法，其中最常用的是把數(shù)據(jù)流分塊[16]。為便于對(duì)算法進(jìn)行描述，對(duì)問題進(jìn)行符號(hào)化定義。數(shù)據(jù)流D={d1,d2,…,dt,…}，其中dt=(xt,yt)表示t時(shí)刻到達(dá)的一個(gè)實(shí)例。按照實(shí)例的到達(dá)順序，將實(shí)例劃分為大小相同的數(shù)據(jù)塊S={S1,S2,…,Si,…,Sn}，其中Sn為最新數(shù)據(jù)塊。Ci表示基于數(shù)據(jù)塊Si訓(xùn)練的基分類器，采用不同的評(píng)價(jià)方式給Ci賦相應(yīng)的權(quán)重值并對(duì)基分類器進(jìn)行篩選，然后采用加權(quán)投票等方式組合成集成分類器Π，最后對(duì)未知實(shí)例dt進(jìn)行預(yù)測(cè)。

1.2 三支決策基本理論

三支決策是在粗糙集基礎(chǔ)上提出的一種求解不確定問題的理論，它在二支決策基礎(chǔ)上增加了延遲決策，當(dāng)信息不足以支撐接受，也不足以支撐拒絕，采用延遲決策避免二支決策所引起的不必要代價(jià)。其初始目的是為粗糙集理論中的三個(gè)分類區(qū)域，即正域、負(fù)域和邊界域，提供合理的決策語義解釋。三支決策通過引入一對(duì)閾值(α,β)，0≤β<α≤1，在評(píng)價(jià)函數(shù)λ(x)下將集合Π中的元素x劃分入三個(gè)不相交的區(qū)域：接受域POS(α,β)(Π)、延遲域BND(α,β)(Π)和拒絕域NEG(α,β)(Π)。當(dāng)λ(x)≥α?xí)r，元素x被劃分入接受域，記作x屬于POS(α,β)(Π)；當(dāng)β<λ(x)<α?xí)r，元素x被劃分入延遲域，記作x屬于BND(α,β)(Π)；當(dāng)λ(x)≤β時(shí)，元素x被劃分入拒絕域，記作x屬于NEG(α,β)(Π)。

2 基分類器質(zhì)量權(quán)重設(shè)定

2.1 基分類器準(zhǔn)確性度量方法

當(dāng)系統(tǒng)獲取到最新數(shù)據(jù)塊Sn，計(jì)算集合Π中的基分類器在Sn上的準(zhǔn)確性?；诸惼鰿i在數(shù)據(jù)塊Sn上的均方誤差為

(1)

(2)

式中：p(y)表示在數(shù)據(jù)塊Sn中各個(gè)標(biāo)簽所占比例。對(duì)于集合Π中的基分類器，其準(zhǔn)確性度量權(quán)重Acc_ωi的計(jì)算過程有如下定義。

定義1對(duì)于任意基分類器Ci∈Π，其準(zhǔn)確性度量權(quán)重計(jì)算公式為

Acc_ωi=1/(MSEi+MSEr+ε)，

(3)

式中：ε是一個(gè)無窮小的正常數(shù)。在最新數(shù)據(jù)塊Sn上建立的基分類器Cn，其準(zhǔn)確性度量權(quán)重計(jì)算公式為

Acc_ωn=1/(MSEr+ε)。

(4)

由于Cn是基于最新數(shù)據(jù)塊建立的基分類器，它能夠代表當(dāng)前以及未來一段時(shí)間數(shù)據(jù)類分布信息，因此被賦予了最高的準(zhǔn)確性度量權(quán)重。

2.2 基分類器不確定性度量方法

在信息論中，信息熵的提出是用來度量隨機(jī)變量的不確定程度。在得到基分類器的不確定性度量之前，基于信息熵理論計(jì)算出基分類器之間的不確定性值。對(duì)于集合Π中任意兩個(gè)基分類器Ci和Cj，它們?cè)谧钚聰?shù)據(jù)塊Sn上的分類事件有四種組合結(jié)果：①N11表示基分類器Ci和Cj對(duì)其正確分類的樣例數(shù)目；②N00表示基分類器Ci和Cj對(duì)其錯(cuò)誤分類的樣例數(shù)目；③N10表示Ci對(duì)其正確分類且Cj對(duì)其錯(cuò)誤分類的樣例數(shù)目；④N01表示Ci對(duì)其錯(cuò)誤分類且Cj對(duì)其正確分類的樣例數(shù)目。通過概率的基本運(yùn)算可以得到上述四種組合結(jié)果出現(xiàn)的概率p11(Ci,Cj)、p00(Ci,Cj)、p10(Ci,Cj)及p01(Ci,Cj)。根據(jù)上述信息，可計(jì)算兩個(gè)基分類器Ci和Cj之間的不確定性值，有如下定義。

定義2對(duì)于任意兩個(gè)基分類器Ci,Cj∈Π，它們的不確定性度量H(Ci,Cj)的計(jì)算公式為

(5)

式中：pk(Ci,Cj)表示Ci和Cj對(duì)最新數(shù)據(jù)塊Sn分類情況的概率。但是，得到Ci和Cj之間的不確定性度量值仍不足以衡量某一個(gè)基分類器的不確定性度量，Ci的不確定性度量是相對(duì)于集合Π而言的。因此，在定義2的基礎(chǔ)上，計(jì)算基分類器Ci與集合Π中其他基分類器的不確定性值后再取平均值，作為其不確定性度量值，有如下定義。

(6)

(7)

為了能直觀展示上述計(jì)算過程，下面給出一個(gè)實(shí)例。假設(shè)在一個(gè)數(shù)據(jù)流實(shí)例S中，S={S1,S2,S3,S4}，S4為實(shí)例中的最新數(shù)據(jù)塊。C1、C2和C3分別是在數(shù)據(jù)塊S1、S2和S3上建立的基分類器，它們?cè)谧钚聰?shù)據(jù)塊S4上的分類情況如表1所示。其中第2列表示的是ti時(shí)刻到達(dá)的一個(gè)實(shí)例的屬性，第3列表示的是每個(gè)實(shí)例屬性所對(duì)應(yīng)的標(biāo)簽值。根據(jù)基分類器對(duì)分類組合情況，整理表1中基分類器的分類結(jié)果，統(tǒng)計(jì)所有基分類器對(duì)分類組合結(jié)果的實(shí)例數(shù)目，可以得到表2。根據(jù)表2中實(shí)例數(shù)目的統(tǒng)計(jì)結(jié)果，通過計(jì)算得到各個(gè)基分類器對(duì)組合結(jié)果的概率分布情況為

表1 各基分類器的分類情況Table 1 Classification of each base classifier

表2 各基分類器對(duì)的分類情況Table 2 Classification of a pair of base classifiers

由以上過程得到了所有基分類器對(duì)的概率分布信息，根據(jù)定義2中的不確定性度量公式計(jì)算弱分類對(duì)(Ci,Cj)的不確定性值H(Ci,Cj)，

2.3 基分類器質(zhì)量評(píng)估

(8)

(9)

定義4對(duì)于任意基分類器Ci∈Π，其質(zhì)量度量指標(biāo)ωi的計(jì)算公式為

(10)

式中：γ為權(quán)重因子，取值為[0,1]。

3 基分類器三支過濾

3.1 池機(jī)制更新過程

在進(jìn)行基分類器過濾前，設(shè)置了一種緩沖池與選擇池機(jī)制，選擇池與緩沖池用來存放一定數(shù)量的基分類器。在集成過程中，優(yōu)先從選擇池中選取加入集成階段的基分類器，當(dāng)滿足集成條件的基分類器數(shù)量不足時(shí)，再從緩沖池中調(diào)取所需數(shù)量的基分類器加入選擇池，繼續(xù)進(jìn)行過濾過程。設(shè)置池機(jī)制的優(yōu)勢(shì)在于緩沖池中保留了從選擇池中移除的基分類器，即保存了暫時(shí)表現(xiàn)不好的基分類器，它可能在之后重新變得有用，將來也可能加入集成過程。選擇池的存在維持了優(yōu)先選擇高權(quán)重基分類器的過程，并且給予了新加入基分類器一定的容錯(cuò)性。池機(jī)制更新算法如算法1所示。

算法1池機(jī)制更新算法

輸入：數(shù)據(jù)塊S={S1,S2,…,St,…}，最新數(shù)據(jù)塊Sn，選擇池容量K，緩沖池容量M。

輸出：選擇池集合E，緩沖池集合B。

Step 1 每次新到數(shù)據(jù)塊Sn，給Sn建立新的基分類器Cn；

Step 2 對(duì)基分類器Ci和Cn分別根據(jù)式(3)和式(4)進(jìn)行準(zhǔn)確性加權(quán)；

Step 3 對(duì)基分類器Ci和Cn分別根據(jù)式(5)～(7)進(jìn)行不確定性加權(quán)；

Step 4 根據(jù)Step 2、Step 3和式(8)～(10)求得所有基分類器的質(zhì)量權(quán)值；

Step 5 如果選擇池容量沒滿，即|E|

Step 6 否則將選擇池中最低質(zhì)量權(quán)值的基分類器Cmin移至緩沖池；

Step 8 得到選擇池集合E和緩沖池集合B。

3.2 三支決策過濾方法

三支決策在信息不足或者獲取足夠信息的代價(jià)較高時(shí)能夠兼顧決策代價(jià)與正確性。基于基分類器質(zhì)量度量方法及設(shè)置的池機(jī)制，提出一種三支決策基分類器過濾(3WQE)算法，如算法2所示。

算法2基于三支決策的分類器質(zhì)量?jī)?yōu)化算法

輸入：由算法1得到的選擇池集合E，緩沖池集合B，迭代次數(shù)Q，閾值α,β(0≤β<α≤1)。

輸出：集成分類器Π*。

Step 1 將選擇池E中的基分類器加入集合Π；

Step 2 對(duì)于E中基分類器Ci，根據(jù)式(3)～(10)求得所有基分類器的質(zhì)量權(quán)值ωi；

Step 3 如果Ci質(zhì)量權(quán)值ωi≥α，將基分類器Ci劃分到POS(α,β)(Π)域;

Step 4 如果Ci質(zhì)量權(quán)值β<ωi<α，將基分類器Ci劃分到BND(α,β)(Π)域;

Step 5 如果Ci質(zhì)量權(quán)值ωi≤β，將基分類器Ci劃分到NEG(α,β)(Π)域;

Step 6 刪除NEG(α,β)(Π)中所有基分類器，更新集合Π=Π-NEG(α,β)(Π)；

Step 7 在緩沖池B中選取|NEG(α,β)(Π)|個(gè)基分類器加入集合Π；

Step 8 返回Step 1；

Step 9 直到|NEG(α,β)(Π)|=0或到達(dá)指定迭代次數(shù)跳出循環(huán)；

Step 10 得到最優(yōu)的基分類器集合Π*。

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)集

數(shù)據(jù)集通常分為人工數(shù)據(jù)集與真實(shí)數(shù)據(jù)集。本文采用2個(gè)人工數(shù)據(jù)集與2個(gè)真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，各數(shù)據(jù)集的參數(shù)設(shè)置如表3所示。人工數(shù)據(jù)集由數(shù)據(jù)流分析框架MOA[17]平臺(tái)下的數(shù)據(jù)流生成器所生成，分別為SEA和LED數(shù)據(jù)集。真實(shí)數(shù)據(jù)集為CoverType和Electricity數(shù)據(jù)集。SEA數(shù)據(jù)集包含3個(gè)屬性值和2個(gè)標(biāo)簽值，屬性取值為0～10，標(biāo)簽值與其中兩個(gè)屬性相關(guān)，還有一個(gè)屬性是隨機(jī)取值的噪聲屬性。在SEA生成器上創(chuàng)建了SEAGD數(shù)據(jù)集，其中包含了4個(gè)漸變漂移。LED數(shù)據(jù)集由24個(gè)二進(jìn)制屬性組成，用于預(yù)測(cè)7段二極管上顯示的數(shù)字。在LED生成器上創(chuàng)建了LEDM數(shù)據(jù)集，其中既包含漸變漂移也包含突變漂移。CoverType數(shù)據(jù)集的任務(wù)是預(yù)測(cè)某個(gè)區(qū)域的森林覆蓋類型，包含581 012個(gè)實(shí)例、53個(gè)屬性和7個(gè)類標(biāo)簽。Electricity數(shù)據(jù)集來自澳大利亞新南威爾士州的電力提供商獲得的電力數(shù)據(jù)，電價(jià)受供求關(guān)系的影響而變化，包括45 312個(gè)樣本，每個(gè)樣本由 7 個(gè)屬性組成，用于預(yù)測(cè)電價(jià)是上漲還是下跌。

表3 各數(shù)據(jù)集的參數(shù)設(shè)置Table 3 Parameter setting of each dataset

4.2 實(shí)驗(yàn)設(shè)置與結(jié)果

4.2.1數(shù)據(jù)塊大小對(duì)算法性能影響評(píng)估 對(duì)于不斷到來的數(shù)據(jù)，將其劃分為多個(gè)大小相同的數(shù)據(jù)塊，用于基分類器的訓(xùn)練和集成分類器的評(píng)估，數(shù)據(jù)塊的大小直接影響算法性能。如果數(shù)據(jù)塊過大，集成分類器將不能有效地檢測(cè)到短暫的概念漂移；如果數(shù)據(jù)塊過小，則會(huì)降低集成分類器在數(shù)據(jù)平穩(wěn)期的分類精度。為驗(yàn)證數(shù)據(jù)塊大小對(duì)算法性能的影響，采用3WQE算法進(jìn)行了多次實(shí)驗(yàn)，不同數(shù)據(jù)塊大小的準(zhǔn)確率對(duì)比結(jié)果如圖1所示。由圖1可以看出，隨著數(shù)據(jù)塊的增大，算法的準(zhǔn)確率在整體上得到了提升，這是由于數(shù)據(jù)塊內(nèi)提供了較多的樣本使得基分類器得到了充分訓(xùn)練。但是隨著數(shù)據(jù)塊的繼續(xù)增大，算法準(zhǔn)確率呈現(xiàn)出逐漸下降的趨勢(shì)，這是由于數(shù)據(jù)塊內(nèi)所提供的樣本過多，使得集成分類器對(duì)概念漂移的識(shí)別能力降低，從而導(dǎo)致模型泛化能力的降低，影響了算法準(zhǔn)確率。各數(shù)據(jù)集在數(shù)據(jù)塊大小為500～1 000時(shí)，準(zhǔn)確率達(dá)到了峰值。

圖1 不同數(shù)據(jù)塊大小的準(zhǔn)確率對(duì)比Figure 1 Accuracy comparison of different chunk sizes

4.2.2算法準(zhǔn)確率評(píng)估 所提出的3WQE算法利用閾值(α,β)將基分類器劃分為三支區(qū)域，設(shè)置合理的閾值將會(huì)有效提升算法效率。經(jīng)過多次實(shí)驗(yàn)發(fā)現(xiàn)，當(dāng)閾值設(shè)置為α∈[0.6,0.8]，β∈[0.2,0.4]，算法分類準(zhǔn)確性有相對(duì)較好的表現(xiàn)。面對(duì)不同的數(shù)據(jù)集時(shí)，需要通過多次調(diào)整確定最佳閾值以達(dá)到算法的最佳性能。為驗(yàn)證3WQE算法的有效性，選取經(jīng)典算法AWE(accuracy weighted ensemble)、AUE2(accuracy updated ensemble2)、ARF(adaptive random forest)、DWM(dynamic weighted majority)[18]作為對(duì)比算法，對(duì)3WQE算法的相關(guān)性能進(jìn)行評(píng)估。設(shè)置選擇池容量K為14，數(shù)據(jù)塊大小為500，α取值為0.7，β取值為0.3，權(quán)重因子γ取值為0.4，表4給出了這些算法在不同數(shù)據(jù)集上的平均分類準(zhǔn)確率?？梢钥闯觯岢龅?WQE算法在這4種數(shù)據(jù)集的分類準(zhǔn)確率上平均排名最高。在SEAGD數(shù)據(jù)集中，AUE2和ARF算法的分類效果大體相當(dāng)，3WQE算法效果略優(yōu)于二者。3WQE算法在LEDM和CoverType數(shù)據(jù)集中也維持了高效的最佳分類效果。而在Electricity數(shù)據(jù)集中，ARF算法的分類效果最佳，3WQE算法次之。多組對(duì)比實(shí)驗(yàn)結(jié)果表明，3WQE算法表現(xiàn)出高效的分類性能，能很好地處理漸變漂移和突變漂移問題。說明基于三支決策的思想，依據(jù)質(zhì)量評(píng)價(jià)策略對(duì)基分類器進(jìn)行三支過濾，3WQE算法可以在保持較高分類準(zhǔn)確率的同時(shí)提升集成模型的泛化性。

表4 不同算法的平均分類準(zhǔn)確率Table 4 Average classification accuracy of different algorithms 單位：%

5 結(jié)論

本文提出一種面向概念漂移集成分類的基分類器三支過濾方法。該方法基于信息熵理論構(gòu)造了一種基分類器的不確定性度量策略，在此基礎(chǔ)上融合經(jīng)典的準(zhǔn)確性度量方法作為基分類器的質(zhì)量度量指標(biāo)。結(jié)合三支決策方法對(duì)基分類器進(jìn)行三支過濾，從而得到一組在當(dāng)前概念漂移數(shù)據(jù)環(huán)境中有較好性能的基分類器。通過一系列實(shí)驗(yàn)驗(yàn)證和對(duì)比，證明該算法可有效提升概念漂移集成分類的準(zhǔn)確性和泛化能力。