季夢(mèng)遙，袁 磊

(1．武漢大學(xué)人民醫(yī)院 消化內(nèi)科, 湖北 武漢 430000；2．武漢大學(xué)人民醫(yī)院 信息中心，湖北 武漢 4300002)

數(shù)據(jù)隨著時(shí)間延續(xù)而無限地、快速地、有序地動(dòng)態(tài)增長(zhǎng)稱之為數(shù)據(jù)流。目前數(shù)據(jù)流廣泛存在于現(xiàn)實(shí)世界的多個(gè)應(yīng)用場(chǎng)景，如氣象測(cè)控[1]、網(wǎng)絡(luò)監(jiān)控[2]、故障檢測(cè)[3]等。數(shù)據(jù)流分為穩(wěn)定數(shù)據(jù)流和動(dòng)態(tài)數(shù)據(jù)流，穩(wěn)定數(shù)據(jù)流是指數(shù)據(jù)分布或數(shù)據(jù)概念不隨時(shí)間的推移而變化，動(dòng)態(tài)數(shù)據(jù)流是指數(shù)據(jù)分布或數(shù)據(jù)概念隨時(shí)間的推移而變化，此類數(shù)據(jù)分布或概念變化即為概念漂移。例如，在網(wǎng)絡(luò)購(gòu)物記錄數(shù)據(jù)流分析中，顧客的購(gòu)物行為會(huì)因?yàn)殡[含的或不可預(yù)知的因素(如，愛國(guó)情愫、身份變更等)而發(fā)生根本性的概念變化。重現(xiàn)概念漂移(recurring concepts)是概念漂移的一種重要表現(xiàn)形式，它區(qū)別于突變式概念漂移和漸變式概念漂移的重點(diǎn)在數(shù)據(jù)概念之前出現(xiàn)在數(shù)據(jù)流中，但隨著時(shí)間推移該數(shù)據(jù)概念又重新再現(xiàn)。例如，天氣變化會(huì)隨時(shí)間的推移出現(xiàn)相同的氣候現(xiàn)象、顧客的購(gòu)買行為會(huì)隨著季節(jié)的變化出現(xiàn)類似的購(gòu)買行為等。然而，目前處理概念漂移的多數(shù)研究工作，大部分將重現(xiàn)概念漂移視為新概念，很少考慮重現(xiàn)概念漂移，因此在處理帶重現(xiàn)概念漂移的數(shù)據(jù)流時(shí)會(huì)導(dǎo)致分類器對(duì)概念漂移反應(yīng)遲鈍、學(xué)習(xí)時(shí)間過長(zhǎng)等問題。

隱含重現(xiàn)概念漂移的不平衡數(shù)據(jù)流是帶重現(xiàn)概念漂移數(shù)據(jù)流的復(fù)雜情況，是指數(shù)據(jù)流中數(shù)據(jù)分布存在不平衡性或失衡性，即數(shù)據(jù)流中某一類或多類數(shù)據(jù)的樣本數(shù)目明顯大于其他類的現(xiàn)象。樣本數(shù)目明顯偏多的類稱之為多數(shù)類，樣本數(shù)目明顯偏少的類稱之為少數(shù)類，少數(shù)類往往具有更高的價(jià)值。例如，在網(wǎng)絡(luò)監(jiān)測(cè)數(shù)據(jù)中，正常的網(wǎng)絡(luò)數(shù)據(jù)樣本數(shù)目(多數(shù)類)要遠(yuǎn)遠(yuǎn)大于異常的網(wǎng)絡(luò)數(shù)據(jù)(少數(shù)類)，而異常數(shù)據(jù)往往具有更高的價(jià)值。目前，關(guān)于數(shù)據(jù)流的分類研究有很多，但大多數(shù)數(shù)據(jù)流分類器多基于數(shù)據(jù)分布是平衡分布的。數(shù)據(jù)分布的不平衡性會(huì)使分類器的訓(xùn)練結(jié)果向多數(shù)類傾斜，嚴(yán)重影響分類器的分類性能。例如，在網(wǎng)絡(luò)監(jiān)測(cè)數(shù)據(jù)中，多數(shù)類數(shù)據(jù)占整個(gè)樣本的99.5%，少數(shù)類樣本占整個(gè)樣本的0.5%，訓(xùn)練所得的分類器對(duì)整體分類準(zhǔn)確率達(dá)99.5%，但是對(duì)少數(shù)類的分類準(zhǔn)確率卻十分低。帶重現(xiàn)概念漂移的不平衡數(shù)據(jù)流同時(shí)具有重現(xiàn)概念漂移和數(shù)據(jù)分布不平衡的雙重特征，如何有效地處理數(shù)據(jù)流的這兩種特征使訓(xùn)練所得的分類器同時(shí)具備快速檢測(cè)重現(xiàn)概念漂移和克服數(shù)據(jù)分布不平衡是本文的研究重點(diǎn)。

概念漂移在被提出之后，得到了學(xué)術(shù)界的重視并涌現(xiàn)出大量的研究成果。目前，隱含概念漂移數(shù)據(jù)流的分類研究工作可分為單分類器模式和集成分類器模式。例如，KATAKIS等[4]提出采用增長(zhǎng)式特征分類器來評(píng)估特征的價(jià)值用于檢測(cè)概念漂移。SOARES等[5]提出了一種全新的在線集成學(xué)習(xí)擬合模型，該模型利用OA技術(shù)檢測(cè)概念漂移。帶概念漂移的不平衡數(shù)據(jù)流是指帶概念漂移數(shù)據(jù)流中隱含著數(shù)據(jù)分布不平衡的特性，如某一類樣本數(shù)目遠(yuǎn)遠(yuǎn)大于其他類的樣本數(shù)目。概念漂移或數(shù)據(jù)分布不平衡都會(huì)影響分類器的性能，當(dāng)概念漂移和數(shù)據(jù)分布共存時(shí)會(huì)對(duì)數(shù)據(jù)流分類研究帶來具大挑戰(zhàn)。例如，傳統(tǒng)的用于處理概念漂移的分類器可能會(huì)對(duì)數(shù)據(jù)分布不平衡度不敏感，從而導(dǎo)致性能下降，這種性能下降在有價(jià)值的少數(shù)類分類上更加凸顯。用于處理不平衡數(shù)據(jù)流的分類模型，可能會(huì)因?yàn)閷?duì)概念漂移敏感度差而導(dǎo)致分類器過時(shí)或失效。目前，一些學(xué)者逐漸開始關(guān)注帶概念漂移不平衡數(shù)據(jù)流的分類研究。例如，DITZLER and ELWELL等[6-7]提出了Learn++.NIE(learning in nonstationary and imbalanced environments)和Learn++.CDS(combination of Learn++.NSE and SMOTE)算法用于處理帶概念漂移不平衡數(shù)據(jù)流的分類問題，該算法是Learn++.NSE(learn in nonstationary environments)算法[8]的擴(kuò)展。其中Learn++.CDS算法本質(zhì)上是Learn++.NSE與SMOTE采樣算法的結(jié)合。類似的研究還有諸如SEA算法[9]、SEAR算法[10]、REA算法[11]、UCB算法[12]等。然而，多數(shù)研究在處理帶概念漂移不平衡數(shù)據(jù)流時(shí)，未考慮重現(xiàn)概念漂移，而將重現(xiàn)概念漂移視為新的概念，因此不具備探測(cè)重現(xiàn)概念漂移的能力，從而導(dǎo)致錯(cuò)誤報(bào)警率提升、計(jì)算資源和人力資源浪費(fèi)。基于上述原因，本文提出了用于處理帶重現(xiàn)概念漂移的不平衡數(shù)據(jù)流分類算法(Random Balanced Sampling Recurring-concepts Imbalanced Streaming Ensemble Algorithm, RBSRISEA)。

1 算法描述

1.1 隨機(jī)平衡采樣算法

不平衡數(shù)據(jù)的存在會(huì)使傳統(tǒng)的分類器性能偏離價(jià)值更高的少數(shù)類，而偏向價(jià)值較低的多數(shù)類，從而導(dǎo)致分類器失效。針對(duì)上述問題，本文提出了一種數(shù)據(jù)再平衡算法，隨機(jī)平衡采樣算法(Random Balance Sampling，RBS算法)。RBS算法本質(zhì)是一種數(shù)據(jù)預(yù)處理再平衡算法，它通過隨機(jī)的改變數(shù)據(jù)集中的少數(shù)類或多數(shù)類的比例，而不改變?cè)瓉頂?shù)據(jù)集的數(shù)據(jù)分布。這種隨機(jī)再平衡技術(shù)不再是單純的加入少數(shù)類或者減少多數(shù)類樣本數(shù)，而是根據(jù)原數(shù)據(jù)分布改變少數(shù)類或多數(shù)類的比例生成新數(shù)據(jù)集用于訓(xùn)練分類器，從理論上保證了集成子分類器的多樣性，理論分析詳見后續(xù)，RBS算法如下所示。

輸入：原數(shù)據(jù)集S={(x1,y1),(x2,y2),…,

(xm,ym)}/,yi∈Y={-1,+1},xi∈X∈Rn

輸出：新的數(shù)據(jù)集S′

1.totalSize←|S|SN←{(xi,yi)∈S|yi=-1}

SP←{(xi,yi)∈S|yi=+1}

2.majoritySize←|SN|minoritySize←|SP|

3.newMajoritySize←[2,totalSize-2]之間的隨意整數(shù)

//隨機(jī)產(chǎn)生多數(shù)類；

4.newMinoritySize←totalSize-newMajoritySize

//隨機(jī)產(chǎn)生少數(shù)類；

5. if newMajoritySize

7.S′←S′+newMajoritySize

8.S′←S′+SMOTE(newMinoritySize-MinoritySize) 9. else

11.S′←S′+newMinoritySize

12.S′←S′+SMOTE(newMajoritySize-MajoritySize) 13. end if

14.輸出S′

1.2 RBSRISEA

帶重現(xiàn)概念漂移的不平衡數(shù)據(jù)流是數(shù)據(jù)流的復(fù)雜表現(xiàn)形式之一，具有概念漂移和數(shù)據(jù)分布不平衡的特征。針對(duì)帶重現(xiàn)概念漂移的復(fù)雜特征，帶重現(xiàn)概念漂移的不平衡數(shù)據(jù)流分類器必須同時(shí)滿足以下幾個(gè)條件：(1)歷史數(shù)據(jù)不可重現(xiàn)。(2)分類器對(duì)概念漂移有較強(qiáng)的敏感性。(3)分類器具有抵抗數(shù)據(jù)分布不平衡的能力。(4)分類器可區(qū)別重現(xiàn)概念與新概念?；谏鲜瞿繕?biāo)，本文提出了一種處理帶重現(xiàn)概念漂移不平衡數(shù)據(jù)流的分類算法，該算法是一種帶權(quán)重的集成分類器模型。RBSRISEA如下。

輸入：訓(xùn)練數(shù)據(jù)流D(t)={xi∈X,yi∈Y={1,-1}}，最新歷史全分類器G(t),最新集成分類器E(t)，

基分類器BC,集成分類器大小K, 時(shí)間戳t,

隨機(jī)采樣算法RBS，單個(gè)分類器預(yù)測(cè)誤差閾值β

fort=1…

1.Dt′=RBS(Dt),Mt=BC(Dt′)=hk∶X→Y,

Et=M∪Mt,G=Gt-1∪Mt

//當(dāng)集成分類器池未達(dá)到K時(shí)，先對(duì)每個(gè)數(shù)據(jù)塊Dt進(jìn)行隨機(jī)平衡采樣產(chǎn)生新的數(shù)據(jù)塊Dt′，之后用弱分類器對(duì)Dt′進(jìn)行學(xué)習(xí)，分別插入集成分類器池E和總分類器池G中，最終E滿，則輸出集成權(quán)重分類器Et

3. 用新來的數(shù)據(jù)流對(duì)Et進(jìn)行性能評(píng)估，評(píng)估的標(biāo)準(zhǔn)為1-FS。注FS為基于混淆矩陣的F-Score值

5. forMi∈E

//如果存在任意一個(gè)分類器預(yù)測(cè)值小于β,則存在重現(xiàn)概念，則保存目前集成分類器，go to 第3行

mi+1=BC(RBS(Dt+1))，

//如果所有的子分類器預(yù)測(cè)值都大于β，則為新概念，需重新訓(xùn)練分類器，并插入總分類器池G,半賦予權(quán)重，子分類器性能越佳，權(quán)重越高

//從總分類器池中選出子分類器預(yù)測(cè)值大于β的分類器重新生成新的集成分類器 end for

end for

end for

輸出：H(t)(x)

假設(shè)數(shù)據(jù)流以固定數(shù)據(jù)塊大小S={D1,D2,…,Dn}的形式連續(xù)到達(dá)，用基分類器對(duì)每個(gè)數(shù)據(jù)塊進(jìn)行學(xué)習(xí)得到一個(gè)獨(dú)立的弱分類器M={M1,M2,…,Mn}，當(dāng)弱分類器個(gè)數(shù)達(dá)到集成分類器池E上限K時(shí)，建立集成分類器E={M1∪M2,…∪Mk}。當(dāng)數(shù)據(jù)流中產(chǎn)生新概念時(shí)，建立新的分類器Mi。但是不刪除歷史分類器，而將歷史分類器存放于全分類器池G中。本文采用不刪除歷史分類器的方法可以成功地區(qū)分新概念與歷史概念，從而避免了重現(xiàn)概念被當(dāng)作新概念重新學(xué)習(xí)的瓶頸。

1.3 理論分析

RBS算法是一個(gè)隨機(jī)數(shù)據(jù)再平衡技術(shù)，這種數(shù)據(jù)再平衡技術(shù)不同于傳統(tǒng)的過采樣或欠采樣技術(shù)，不再是簡(jiǎn)單地加入少數(shù)類或減少多數(shù)類的平衡技術(shù)。它是一種能改變多數(shù)類與少數(shù)類比例的循環(huán)算法達(dá)到數(shù)據(jù)再平衡的技術(shù)，這種改變多數(shù)類與少數(shù)類比例包括多數(shù)類與少數(shù)類樣本數(shù)目相當(dāng)、多數(shù)類樣本數(shù)目占絕對(duì)優(yōu)勢(shì)和少數(shù)類樣本數(shù)目占絕對(duì)優(yōu)勢(shì)的可能情形。數(shù)據(jù)集yeast1的分類器邊界示意圖如圖1所示。圖中共有500個(gè)數(shù)據(jù)樣本，不平衡率為46，“o”表示多數(shù)類， “*”表示少數(shù)類，每個(gè)分類器邊界顏色代表少數(shù)類用于訓(xùn)練基分類器的概率，紅色、藍(lán)綠色和藍(lán)色分別表示用少數(shù)類訓(xùn)練基分類器的概率從高到低。實(shí)際上，當(dāng)少數(shù)類訓(xùn)練基分類器的概率較高時(shí)，子分類器對(duì)少數(shù)類的關(guān)注度較高，分類性能較高。反之，當(dāng)少數(shù)類訓(xùn)練基分類器的概率較低時(shí)，子分類器對(duì)少類器的關(guān)注度較低，分類性能較低。從圖1可以看出，采用RBS算法訓(xùn)練基本分器時(shí)，子分類器的邊界相對(duì)較寬，邊界向少數(shù)類偏移，子分類器呈現(xiàn)較強(qiáng)的多樣性和泛化能力。 理論上，在RBS算法中多數(shù)類和少數(shù)類入選生成新數(shù)據(jù)集用于訓(xùn)練基分類器的概率是不同的。當(dāng)多數(shù)類樣本數(shù)目占主動(dòng)地位時(shí)，少數(shù)類入選的概率偏高。反之，當(dāng)少數(shù)類樣本數(shù)目占絕對(duì)優(yōu)勢(shì)時(shí)，多數(shù)類入選的概率偏高。

(a)RBS算法 (b)Bagging算法 圖1 集成分類器邊界示意圖Fig.1 the ensemble classifiers′ boundaries

(1)

(2)

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

該部分主要內(nèi)容為驗(yàn)證RBSRISEA算法處理帶重現(xiàn)概念漂移不平衡數(shù)據(jù)流的能力，包括：(1)RBSRISEA算法是否可以檢測(cè)突發(fā)性概念漂移。(2)RBSRISEA算法是否可以檢測(cè)重現(xiàn)概念漂移。(3)RBSRISEA算法是否可以處理不平衡數(shù)據(jù)流的概念漂移。(4)RBSRISEA算法對(duì)不平衡數(shù)據(jù)是否對(duì)少數(shù)類具有較高的關(guān)注度。

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

本文采用的數(shù)據(jù)集如表1所示，其中yeast1為不含概念漂移的不平衡數(shù)據(jù)集，用于驗(yàn)證本文提出的RBS算法處理不平衡數(shù)據(jù)流的性能。SEA數(shù)據(jù)集[13]為帶突變概念漂移不平衡數(shù)據(jù)流合成數(shù)據(jù)集，elist和usps為不同不平衡率的含重現(xiàn)概念不平衡數(shù)據(jù)流數(shù)據(jù)集， 不平衡率范圍為6～18。

表1 實(shí)驗(yàn)數(shù)據(jù)Tab.1 Experimental data set

2.2 評(píng)價(jià)指標(biāo)

由于帶重現(xiàn)概念不平衡數(shù)據(jù)流具有數(shù)據(jù)分布不平衡的特點(diǎn)，從而使分類器缺少對(duì)少數(shù)類的分類關(guān)注度，而同時(shí)分類器的整體性能卻很高。因此，用于度量傳統(tǒng)分類器性能的評(píng)價(jià)體系不適用于帶重現(xiàn)概念不平衡數(shù)據(jù)流分類器的性能評(píng)估。本文采用分類評(píng)價(jià)指標(biāo)為基于混淆矩陣的評(píng)價(jià)體系，具體評(píng)價(jià)指標(biāo)包括接收者操作特征曲線下面積(Area Under Curve，AUC)、F-Score(FS)和召回率(Recall，R)三種。

2.3 結(jié)果與分析

分類器性能分析。為了驗(yàn)證RBSRISEA對(duì)處理帶重現(xiàn)概念不平衡數(shù)據(jù)流分類的有效性，本文分別在SEA和usps兩個(gè)數(shù)據(jù)集上對(duì)其進(jìn)行實(shí)驗(yàn)。同時(shí)將RBSRISEA與Learn++.NIE和UCB算法在AUC和R兩個(gè)方面進(jìn)行比較，實(shí)驗(yàn)結(jié)果如圖2所示。

(a)不同算法在數(shù)據(jù)集SEA上的性能比較 (b) 不同算法在數(shù)據(jù)集usps上的性能比較 圖2 分類器性能分析結(jié)果對(duì)比圖Fig.2 Comparison results between different classifiers

從圖2可見，當(dāng)三種算法處理突發(fā)概念漂移時(shí)，性能相當(dāng)。但應(yīng)對(duì)帶重現(xiàn)概念漂移時(shí)，RBSRISEA具有明顯的優(yōu)勢(shì)，召回率較高且概念識(shí)別度較高，延遲明顯小于其它兩種算法，這主要由于本算法不需要對(duì)重現(xiàn)概念進(jìn)行重新學(xué)習(xí)。

數(shù)據(jù)塊大小對(duì)分類器性能影響分析。RBSRISEA將數(shù)據(jù)流劃分為若干個(gè)大小相同的數(shù)據(jù)塊，數(shù)據(jù)塊用于建立子分類器和集成分類器的驗(yàn)證，數(shù)據(jù)塊的大小直接影響分類器的性能。如果數(shù)據(jù)塊太大，則集成分類器不能檢測(cè)到數(shù)據(jù)塊內(nèi)的小的概念漂移。如果數(shù)據(jù)塊太小，則集成分類器的泛化能力較差。圖3為數(shù)據(jù)塊大小對(duì)集成分類器性能FS的影響分析圖，橫坐標(biāo)表示數(shù)據(jù)塊大小，范圍為20～120，縱坐標(biāo)為集成分類器整體性能指標(biāo)FS。從圖3可以看出，當(dāng)數(shù)據(jù)塊較小或較大時(shí)，分類器的整體性能有較大的波動(dòng)。

圖3 數(shù)據(jù)塊大小對(duì)分類器性能的影響Fig.3 Classifier performances on different chunk size

應(yīng)對(duì)概念漂移時(shí)需建立子分類器個(gè)數(shù)分析。由于RBSRISEA采用不刪除歷史子分類器的方法，因此該算法對(duì)不平衡數(shù)據(jù)流中新概念與重現(xiàn)概念有較強(qiáng)的敏感度和區(qū)分能力。在不平衡數(shù)據(jù)流中，存在著重現(xiàn)概念、新概念、相近概念，RBSRISEA對(duì)識(shí)別不同種類的概念所需建立的子分類器個(gè)數(shù)也不相同。理論上，識(shí)別重現(xiàn)概念時(shí)，建立子分類器個(gè)數(shù)較少。相反地，識(shí)別新概念時(shí)，需建立子分類器個(gè)數(shù)較多。圖4顯示了RBSRISEA在數(shù)據(jù)集usps上應(yīng)對(duì)不同類型概念漂移時(shí)需建立子分類器的個(gè)數(shù)，其中橫坐標(biāo)表示時(shí)間戳，縱坐標(biāo)表示子分類器的個(gè)數(shù)。從圖4可以看出，當(dāng)發(fā)生概念漂移時(shí)，需建立的子分類器個(gè)數(shù)不同。其中，時(shí)間戳A、C表示新概念發(fā)生時(shí)，需建立子分類器的個(gè)數(shù)分別為12、15，需建立的分類器個(gè)數(shù)相對(duì)較多。而時(shí)間戳B、D表示重現(xiàn)概念漂移發(fā)生，需建立的子分類器個(gè)數(shù)最少為2個(gè)?？梢姡琑BSRISEA對(duì)重現(xiàn)概念漂移有較強(qiáng)的敏感度。相反地，Learn++.NIE算法無法識(shí)別重現(xiàn)概念，因此當(dāng)發(fā)生重現(xiàn)概念時(shí)需要建立更多的子分類器。

圖4 應(yīng)對(duì)重現(xiàn)概念漂移時(shí)建立集成分類器個(gè)數(shù)對(duì)比圖Fig.4 Different ensemble sizes with recurring concepts

3 結(jié)語

帶重現(xiàn)概念漂移的不平衡數(shù)據(jù)流廣泛存在于現(xiàn)實(shí)世界中，本文分別分析了處理重現(xiàn)概念漂移數(shù)據(jù)流和不平衡數(shù)據(jù)流的方法，提出了處理帶重現(xiàn)概念漂移不平衡數(shù)據(jù)流分類算法RBSRISEA。該算法是基于RBS算法的集成分類算法，實(shí)驗(yàn)證明該算法具有區(qū)分新概念和重現(xiàn)概念的能力，克服了重現(xiàn)概念被識(shí)為新概念而重新學(xué)習(xí)的困境，提高了分類器識(shí)別概念漂移的敏感度。同時(shí)，RBSRISEA是基于RBS算法的集成分類算法，RBS算法的數(shù)據(jù)再平衡能力使RBSRISEA具備抵抗數(shù)據(jù)流的數(shù)據(jù)分布不平衡特性，提高了分類器的整體性能和健壯性，尤其提高了對(duì)少數(shù)類的關(guān)注度。下一步，我們將采用不同的評(píng)價(jià)標(biāo)準(zhǔn)來量化子分類器的權(quán)重，同時(shí)也將嘗試采用不同的基分類器和更廣泛的數(shù)據(jù)集深度評(píng)估該算法的泛化能力。