一種面向不平衡數據流的集成分類算法

孫艷歌，王志海，白 洋

1(信陽師范學院 計算機與信息技術學院，河南 信陽 464000)

2(北京交通大學 計算機與信息技術學院，北京 100044)

1 引 言

隨著信息技術的快速發展，在諸如無線傳感器網絡、實時交通系統、網絡流量監測和信用卡欺詐檢測等諸多應用領域中產生了高速動態、數據規模宏大且連續不斷的數據流(Data Streams)[1].這些數據中蘊含著豐富的信息亟待我們去挖掘.

與傳統的靜態數據有所不同，數據流具有快速、實時、無限、單遍、且蘊含的概念會發生變化的特性.在真實的數據流環境中，數據是隨著時間不斷變化的[2，3]，因此數據所蘊含的概念會隨著時間而發生改變，即發生概念漂移(Concept Drift)[4，5].例如：顧客網上購物偏好隨個人興趣、商家信譽、服務類型等因素的變化而改變；天氣預報可能會隨著季節變化而發生改變.概念漂移會使得原有的分類模型不再適應新的數據，這就需要快速的檢測到這種變化，并動態更新模型以適應這種改變[6-8].

文獻[6]將傳統的概念漂移處理方法劃分為：基于實例選擇，基于實例加權與集成學習三種方法.其中，集成學習方法是最廣泛使用的用于處理概念漂移的方法[7].然而，已有的數據流分類算法都是基于數據流類分布是大致平衡這一假設的，然而在現實世界中存在著大量的類分布不均衡數據.如信用卡的欺詐辨識、網絡入侵檢測、在線實時醫療診斷等諸多應用中人們往往更關注對于少數類的分類情況.

在機器學習領域中，研究者對不平衡學習分類問題進行了大量的研究[9-13].主要集中在以下3個方面：一是通過調整不同類別樣本的權重來重構訓練集，但是有可能會丟失一部分樣本信息[9,10]；二是在改進傳統的算法的基礎上設計代價敏感的分類算法[11,12]；三是采用集成學習技術[13].由于數據流的連續、快速、無限和多變等特點，使得以上方法不能直接應用于數據流環境中.

本文提出了一種基于集成學習的不平衡數據流分類算法.主要貢獻如下：

1)針對數據流中的概念漂移問題，采用基于數據塊的集成方式，利用周期更新分類器權重來應對概念漂移.

2)針對數據流中的類不平衡問題，首先利用過采樣技術增加正類樣本的比例，再利用欠采樣技術來刪除負類樣本，從而達到平衡各類樣本的目的.

3)在提高集成分類效果方面，在分類器權重更新過程中綜合考慮了分類器在最新數據塊上的分類正確率和分類錯誤的代價，同時，在分類器的淘汰過程中考慮了各個分類器對集成分類的貢獻.

本文的主要結構如下：第2節總結相關的研究工作并給出所涉及的基本概念.第3節闡述本文提出的算法.在第4節中對所提出的算法進行實驗并進行性能分析.第5節進行全文總結以及對進一步工作的展望.

2 面向數據流的集成式分類研究背景

2.1 相關概念

數據流可表示為S={s1，s2，…，st，…}，其中st=(xt，yt)為t時刻(t= 1，2，…，T)的實例，xt∈(Rd是特征向量，yt∈ {c1，c2，…，ck}是類值，k(k>1)為S中所包含的類值數.根據源源不斷到達的實例，增量式的學習并產生了一個分類器f，并來對類別標記未知的實例預測類值.

目前，大多數文獻大多數都采用概率來定義概念.在本文將概念定義為聯合分布P(X，y).輸入變量和目標變量之間聯合概率的變化的現象稱為概念漂移，因此t0和t1時刻之間的概念漂移可表示為：

?X：Pt0(X，y)≠Pt1(X，y)

(1)

如圖1所示，用一維數據的均值變化來展示漂移發生過程.若數據流中數據分布在較短的時間內被另一個數據分布所取代，則稱此時發生了突變式概念漂移[6].而漸變式概念漂移是一種慢速率改變(如傳感器部件逐漸失靈)，概念漂移發生前后概念之間有或多或少的相似[6].

2.2 相關工作

近年來，隨著類不平衡數據問題研究的不斷深入，數據流中的類不平衡問題也吸引了大量的研究者.Gao等人中提出一個數據流中類不平衡問題的集成分類框架，改算法采用過采樣技術來處理不平衡問題[14].文獻[15]中提出一種處理不平衡數據流的方法，該方法不僅增加了正類實例，而且增加被錯誤分為負類實例，同時，該方法還提出一種新的定義正類和負類的邊界的方法，以提高分類器的集成效果.歐陽震凈等人結合基于權重的集成分類器與抽樣技術，提出了一種處理不平衡數據流集成分類器模型[16].最近，Ditzler等人提出了基于集成學習的方法Learn++.CDS和Learn++.NIE來解決類不平衡數據流中的概念漂移問題[17].Mirza等人提出了一種基于極端學習機(Extreme Learning Machine，ELM)的集成方法，該方法是以數據塊為單位來處理數據流的[18]，但并未考慮概念漂移問題.

類不平衡問題常常會和概念漂移一起存在于數據流中，然而上述算法大多只是針對其中一個問題進行研究的，并未充分考慮同時存在類不平衡和概念漂移現象的問題.

2.3 基于數據塊的數據流集成方法

令S表示數據流，在基于數據塊的集成分類方式中，將S平均分成若干個大小相等數據塊B1，B2，…，Bn，數據塊大小為d.不斷地在新到的數據塊Bi上建一個新分類器C′，添加到集成分類器中，以替換性能最差的分類器，從而適應數據流分布變化的需要，并采用加權投票等原則預測實例.基于數據塊的分類器集成方法的一般過程如算法1所示.

算法1.基于數據塊的集成分類框架

輸入：S：數據流，d：數據塊的大小，k：基分類器個數，Q(·)：分類器性能度量函數

輸出：ε：包含k個分類器的集成分類器

01：begin

02：for 數據塊Bi∈Sdo

03： 在Bi上訓練新分類器，并利用Q(·)計算其權值

04： 在Bi上根據Q(·)給E中所有分類器賦權值

05： if |ε|

06：ε←ε∪{C′}

07： else if ?i：Q(C′)>Q(Ci) then

08： 用C′替換ε中性能最差的分類器

09： end if

10：end for

11：end

如何動態更新分類器的權重是此類數據流集成分類方法研究的關鍵[19].Street等提出了數據流集算法(Streaming Ensemble Algorithm，SEA)[20]，此算法不斷的在最新數據塊上訓練新的基分類器，并采用啟發式策略替換性能最差的分類器，從而適應概念漂移.Wang等人提出了一種基于準確率加權集成(Accuracy Weighted Ensemble，AWE)算法[2]，以基分類器Cj在當前最新數據塊Bi上的誤差率作為加權的依據，其加權函數如公式(2)所示.

(2)

(3)

3 一種基于集成學習的不平衡數據流分類算法

3.1 基本思想

近年來，集成學習模型被廣泛用于處理概念漂移問題.Wang等人[2]從理論上證明了集成分類器的性能要優于單個分類器.為此，本文提出了一種基于集成的不平衡數據流分類算法(Ensemble Classifiers for Imbalanced Streaming Data，ECISD)，來處理數據流中的概念漂移和類不平衡問題.

圖2 算法流程圖Fig.2 Flow chart of ECISD

簡單起見，本文只考慮兩類的情況，可以擴展到多類的情況，其基本過程如圖2所示.算法主要包括兩個步驟：

1)數據采樣階段：采用SMOTE和Tomek Links相結合的方式，達到在增加正類樣本的目的，同時也減少負類樣本的目的，從而平衡各個類別.

2)集成分類階段：利用集成的方式對數據流進行分類，并綜合考慮了基分類器在最新的數據塊上的分類錯誤情況和分類錯誤的代價來動態更新各分類器的權重.并用最新分類器替換貢獻值最小的基分類器.

3.2 樣本采樣過程描述

由于SMOTE方法生成的正類樣本是通過線性差值得到的，在平衡類別分布的同時也會擴張了少數類的樣本空間，這樣一來，原本屬于負類樣本的空間可能會被正類樣本侵占，同時容易造成模型的過擬合.而Tomek Links方法刪除的是邊界點或噪聲點，因此可以用于解決SMOTE方法中存在的問題.偽代碼如算法2所示.

算法2.樣本采樣算法

輸入：T：正類樣本數，N%：過采用百分比，q：最近鄰數量

輸出：采樣后新樣本集合

01：begin

02：numattrs=屬性數

03：Sample[ ][ ]：原始正類樣本數組

04：newindex：新合成的人工樣本數量

05：Synthetic[ ][ ]：合成樣本數組

06：fori←1到T

07： 計算第i個正類樣本的q個最近鄰并保存到數組nnarray中

08： 生成人工合成的樣本(N，i，nnarray)

09：end for

10：找到樣本集合中的Tomek link對

11：刪除Tomek link對中的負類樣本

12：end

3.3 基于集成學習的不平衡數據流分類算法

令S表示數據流，將S平均分成若干個大小相等數據塊B1，B2，…，Bn，數據塊大小為d.不斷地在新到來的數據塊Bi上新建一個分類器C′.給新建的分類器賦予一個權值wC′.對于集成分類器ε={C1，C2，…Cm}中每一個分類器Cj，首先通評價它在最新數據塊上的分類性能來動態更新分類器權值，同時考慮到它分類錯誤的代價，接著將新建的分類器加入ε中.若此ε中分類器數達到最大允許數k時，則淘汰使集成分類正確率的降低的分類器.采用加權投票的方式對數據流中的實例的進行預測.

3.3.1 基分類器加權策略

在加權過程中考慮到分類錯誤的代價，即引入一個代價矩陣，如表1所示.

表1 代價矩陣Table 1 Cost matrix

其中，FPcost為將負類分為正類產生的代價，FNcost表示將正類分為負類產生的代價.一般來說FPcost

設將實際類別為y的實例x分為y′類的代價為Jy，y′(x)，Cj在數據塊Bi上誤分類總代價如公式(4)所示：

(4)

分類器Cj在數據塊Bi上的權值wij如公式(5)所示：

(5)

其中，α是一個很小的正數，為了避免出現分母為0的情況.最后，所有基分類器的權重還需要進行歸一化處理.

3.3.2 基分類器淘汰策略

每當到達一個新數據塊后，就根據已有的基分類器在最新數據塊上分類情況進行評價.集成分類器的整體正確率如公式(6)所示：

(6)

其中xl是Bi中的實例，Gε(xl)的定義如公式(7)所示：

(7)

若將分類器Cj從ε中移除，此時集成分類器的分類正確率就如公式(8)所示：

(8)

Cj在Bi上對集成分類器的分類正確率的貢獻Conε(j)如公式(9)所示：

Conε(j)=Pε(Bi)-Pε-Cj(Bi)

(9)

該值可以為正也可以為負.Conε(j)為負值，表示該分類器降低了整體的分類正確率，Conε(j)如果為正值，表示該基分類器可以提高整體的分類正確率.每當加入一個新建的分類器，就刪除Con值為負的分類器.

3.3.3 ECISD算法的描述

ECISD算法描述如算法3所示.

算法3. ECISD

輸入：S：數據流，k：集成分類器中的分類器數

輸出：ε：包含k個帶權值分類器的集成

01：begin

02：ε←φ

03：forBi∈Sdo

04： 在Bi上訓練新的分類器

06： forCj∈εdo

07： 計算MSEij，ctij，MSEr

09： 計算Conε(j)

10： ifConε(j)<0 then

11： 刪除Cj

12： end if

13： end for

14： if |ε|

15：ε←ε∪{C′}

16： else

17： 用C′替換ε中Con值最低的分類器

18： end if

19： forCj∈ε/{C′} do

20： 增量地在Bi上訓練分類器Cj

21： end for

22：end for

23：end.

4 實驗評價

本文算法均在大規模數據在線分析開源平臺MOA(Massive Online Analysis)[23]下實現.實驗程序是在CPU為2.8GHZ，內存為8GB，操作系統為Windows 7的PC機上進行實驗的.

4.1 數據集描述

實驗選取3個人工合成數據集和1個真實數據集：

1)STAGGER數據集，由Schlimmer等人提出，常被用來衡量分類器在概念漂移數據流上的分類性能.實驗中采用MOA中的數據流產生器STAGGERGenerator生成包含1000，000個實例的數據集.該數據集中有3個概念，漂移類型是突變式的，對于第一個概念，兩個類的不平衡比例為7，另外兩個概念是平衡的.

2)SEA是經典的突變式概念漂移數據集.其基本結構是，其中f1、f2和f3為條件屬性，C為類屬性，僅f1，f2和C相關.當實例的屬性滿足f1+f2≤θ時，屬于第一類，否則屬于第二類.采用數據流產生器SEAGenerator生成包含1000，000個實例，發生2次突變的數據集.

3)Rotating Spiral數據集：這是一個合成數據集，其中描述了4種螺旋.該數據集中的漂移類型是漸變式的.該數據集包含1000，000個實例，其中正類實例大約占5%.

4)Spam數據集包含9，324個實例，每個實例有500個屬性用于表示一個郵件的信息，被分為兩種類型：垃圾郵件(僅占20%)和合法郵件，因此該數據集既是一個不平衡數據集，同時數據集中的垃圾郵件的特征隨著時間緩慢變化即包含概念漂移*該數據集可在http://mlkd.csd.auth.gr/concept_drift.html下載.用MOA中的ArffFileStream產生器將靜態的數據模擬產生數據流.

4.2 參數設置與實驗結果分析

所提算法與以下3個算法進行對比：VFDT(Very Fast Decision Tree)[24]、AUE2和Learn++.NIE.VFDT是一種從數據流中增量式的生成決策樹的單分類器算法，利用Hoeffding不等式理論，能夠以一定的概率保證所構造決策樹的精度.為了便于比較，集成分類中分類器數k=15，基分類器為Hoeffding Tree，選取與文獻[24]相同的參數.本文所提出的算法的參數設置為：d= 1000，N= 300，q= 6；AUE2采用MOA中的默認設置.采用G-mean作為算法的評價指標，如公式(10)所示.

(10)

G-mean是分類器對正類樣本的分類精度(召回率)與對負類樣本分類準確度的幾何平均值.此指標常用于衡量不平衡數據流分類效果.

4.2.1 數據塊大小對算法性能影響

在STAGGER數據集上進行測試，為了驗證數據塊大小設置對算法性能的影響分別取值為[500，2000].由圖3可以看出，在一開始，隨著數據塊的增大使得構建分類器的數據增多，平均G-mean值也隨之上升.然而，隨著數據塊的繼續增大，概念漂移發現滯后，平均G-mean值反而略有降低.表2表明本文所提的方法受窗口大小設置影響很小，當數據塊大小為1000時可以獲得相對較高的G-mean值.

圖3 不同數據塊大小的平均G-mean值比較Fig.3 Average G-mean using different block sizes

表2 不同大小數據塊下的平均G-mean值Table 2 Average G-mean using different block sizes

4.2.2 不同算法性能比較分析

首先，在人工合成數據集上驗證所提算法的有效性.圖4是算法在STAGGER數據集上分類得到的G-mean值.我們觀察發現，所有算法變化趨勢基本一致.其中，Learn++.NIE算法和ECISD算法在該數據集上的性能較好，VFDT的性能最差.VFDT算法在第400，000個實例附近的G-mean值波動很大，同樣的情況也發生在第800，000個實例附近.這是由于基于數據塊的算法不斷在最新數據塊上訓練生成分類器，同時算法采用了周期加權機制，增加對最新數據的適應性，更適合具有概念漂移的環境.同時本文算法是基于基分類器性能和誤分類代價的，在分類之前加入采樣方法應對類不平衡問題，從而提高分類器的性能.而VFDT沒有任何處理概念漂移機制，因此不適合概念漂移環境.

圖4 在STAGGER數據集上的G-mean值Fig.4 G-mean on STAGGER dataset

圖5展示了算法在SEA數據集上的性能.從圖中可以看出，VFDT算法的性能最差，ECISD在該數據集上的性能較差，尤其在第500，000個實例附近，所有算法的G-mean值都急劇下降除了本文算法.本文算法能快速捕捉到概念變化，并建立新的分類器，從而及時應對這種變化.

圖5 在SEA數據集上的G-mean值Fig.5 G-mean on SEA dataset

圖6展示了算法在集Rotating Spiral上的性能.可以看出所有算法變化趨勢基本一致，波動都較大.VFDT算法性能最差，其他3種算法的性能都比VFDT要好，這是由于本文算法采用對實時數據流環境的數據不平衡問題的調節策略與方法，在數據的處理過程中采用數據采樣方法策略以調節正例和反例在整個模型或算法中的貢獻，保證算法或模型能及時有效地適應數據流的變化接著，在真實數據流數據集上驗證所提算法的有效性.圖7反應了在真實數據集Spam上的性能，所有算法的G-mean曲線均出現不同程度的波動，而本文算法和Learn++.NIE算法的曲線相對平穩，受到數據中概念漂移影響最小，表明算法對真實的數據環境有較好的適應性.而VFDT算法和AUE2算法的性能較差.

圖6 在Rotating Spiral數據集上的G-mean值Fig.6 G-mean on Rotating Spiral dataset

圖7 在Spam數據集上的G-mean值Fig.7 G-mean on Spam dataset

最后，我們來分析算法在4個數據集上的平均G-mean值.從表3可以看出ECISD在STAGGER和Spam數據集上的平均性能最好，在SEA上的性能較差，并且ECISD算法的平均排名最高.這是由于ECISD算法既可以處理類不平衡問題又可以處理概念漂移問題.VFDT算法不能處理類不平衡問題，同時它也沒有處理概念漂移的機制，因此它的平均性能最差.

表3 算法的平均G-mean值Table 3 Average G-mean of algorithms

5 總結與展望

針對數據流分類中的概念漂移和類別不平衡問題，提出了一種基于集成學習的不平衡數據流分類算法.在降低數據流不平衡分布的基礎上，考慮不同類型概念漂移的特征，設計基于不同類型的概念漂移的解決方案.通過實驗驗證了所提算法能夠在不平衡的概念漂移數據流上取得較好的分類效果.

由于本文提出的算法是以數據塊為單位進行處理的，存在數據塊大小選擇的問題.因此如何設計自適應數據塊大小的集成算法，是今后值得進一步研究的方向.

：

[1] Gama J.Knowledge discovery from data streams[M].New York：CRC Press，2010.

[2] Wang H，Fan W，Yu P S，et al.Mining concept-drifting data streams using ensembles classifiers[C].Proceedings of Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD 2003)，2003：226-235.

[3] Cohen L，Avrahami-Bakish G，Last M，et al.Real-time data mining of non-stationary data streams from sensor networks[J].Information Fusion，2008，9(3)：344-353.

[4] Widmer G，Kubat M.Learning in the presence of concept drift and hidden contexts[J].Machine Learning，1996，23(1)：69-101.

[5] Webb G I，Hyde R，Cao H，et al.Characterizing concept drift[J].Data Mining and Knowledge Discovery，2016，30(4)：964-994.

[6] Tsymbal A.The problem of concept drift：Definitions and related work[R].Technical Report TCD-CS-2004-15，Trinity College Dublin，2004.

[8] Qi Kai-yuan，Zhao Zhuo-feng，Fang Jun，et al.Real-time processing for high speed data stream over large scale data[J].Chinese Journal of Computers，2012，35(3)：477-490.

[9] He H，Garcia E A.Learning from imbalanced data[J].IEEE Transactions on Knowledge and Data Engineering，2009，21(9)：1263-1284.

[10] Chawla N V，Bowyer K W，Hall L O，et al.SMOTE：synthetic minority over-sampling technique[J].Journal of Artificial Intelligence Research，2002，16：321-357.

[11] Ling C X，Sheng V S，Yang Q.Test strategies for cost-sensitive decision trees[J].IEEE Transactions on Knowledge and Data Engineering，2006，18(8)：1055-1067.

[12] Sun Y，Kamel M S，Wong A K C，et al.Cost-sensitive boosting for classification of imbalanced data[J].Pattern Recognition，2007，40(12)：3358-3378.

[13] Wang S，Yao X.Diversity analysis on imbalanced data sets by using ensemble models[C].Proceedings of the IEEE Symposium Series on Computational Intelligence and Data Mining(CIDM 2009)，2009：324-331.

[14] Gao J，Fan W，Han J，et al.A general framework for mining concept-drifting data streams with skewed distributions[C].Proceedings of the 2007 SIAM International Conference on Data Mining，2007：3-14.

[15] Chen S，He H.Towards incremental learning of nonstationary imbalanced data stream：a multiple selectively recursive approach[J].Evolving Systems，2011，2(1)：35-50.

[16] Ouyang Zhen-jing，Luo Jian-shu，Hu Dong-min，et al.An ensemble classifier framework for mining imbalanced data streams[J].Chinese Journal of Electronics，2010，38(1)：184-189.

[17] Ditzler G，Polikar R.Incremental learning of concept drift from streaming imbalanced data[J].IEEE Transactions on Knowledge and Data Engineering，2013，25(10)：2283-2301.

[18] Mirza B，Lin Z，Toh K A.Weighted online sequential extreme learning machine for class imbalance learning[J].Neural Processing Letters，2013，38(3)：465-486.

[19] Gomes H M，Barddal J P，Enembreck F，et al.A survey on ensemble learning for data stream classification[J].ACM Computing Surveys(CSUR)，2017，50(2)：1-36.

[20] Street W N，Kim Y S.A streaming ensemble algorithm(SEA) for large-scale classification[C].Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，ACM，2001：377-382.

[21] Brzeziński D，Stefanowski J.Accuracy updated ensemble for data streams with concept drift[C].Proceedings of the 6th International Conference on Hybrid Artificial Intelligent Systems(HAIS 2011,LNCS 6678)，Berlin:Springer-Verlag,2011：155-163.

[22] Brzezinski D，Stefanowski J.Reacting to different types of concept drift：the accuracy updated ensemble algorithm[J].IEEE Transactions on Neural Networks and Learning Systems，2014，25(1)：81-94.

[23] Bifet A，Holmes G，Kirkby R，et al.MOA：massive online analysis[J].Journal of Machine Learning Research，2010，11(5)：1601-1604.

[24] Domingos P，Hulten G.Mining high-speed data streams[C].Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2000：71-80.

附中文參考文獻：

[8] 亓開元，趙卓峰，房 俊，等.針對高速數據流的大規模數據實時處理方法[J].計算機學報，2012，35(3)：477-490.

[16] 歐陽震凈，羅建書，胡東敏，等.一種不平衡數據流集成分類模型[J].電子學報，2010，38(1)：184-189.