帶重現(xiàn)概念漂移的不平衡數(shù)據(jù)流分類研究

季夢遙，袁 磊

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

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

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

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

1 算法描述

1.1 隨機平衡采樣算法

不平衡數(shù)據(jù)的存在會使傳統(tǒng)的分類器性能偏離價值更高的少數(shù)類，而偏向價值較低的多數(shù)類，從而導致分類器失效。針對上述問題，本文提出了一種數(shù)據(jù)再平衡算法，隨機平衡采樣算法(Random Balance Sampling，RBS算法)。RBS算法本質是一種數(shù)據(jù)預處理再平衡算法，它通過隨機的改變數(shù)據(jù)集中的少數(shù)類或多數(shù)類的比例，而不改變原來數(shù)據(jù)集的數(shù)據(jù)分布。這種隨機再平衡技術不再是單純的加入少數(shù)類或者減少多數(shù)類樣本數(shù)，而是根據(jù)原數(shù)據(jù)分布改變少數(shù)類或多數(shù)類的比例生成新數(shù)據(jù)集用于訓練分類器，從理論上保證了集成子分類器的多樣性，理論分析詳見后續(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ù)

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

4.newMinoritySize←totalSize-newMajoritySize

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

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

基分類器BC,集成分類器大小K, 時間戳t,

隨機采樣算法RBS，單個分類器預測誤差閾值β

fort=1…

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

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

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

3. 用新來的數(shù)據(jù)流對Et進行性能評估，評估的標準為1-FS。注FS為基于混淆矩陣的F-Score值

5. forMi∈E

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

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

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

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

end for

end for

輸出：H(t)(x)

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

1.3 理論分析

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

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

(1)

(2)

2 實驗分析

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

2.1 實驗數(shù)據(jù)

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

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

2.2 評價指標

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

2.3 結果與分析

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

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

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

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

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

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

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

3 結語

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