基于增量加權(quán)的不平衡漂移數(shù)據(jù)流分類算法

蔡博 張海清 李代偉 向筱銘 于曦 鄧鈞予

摘 要：

概念漂移是數(shù)據(jù)流學(xué)習(xí)領(lǐng)域中的一個難點(diǎn)問題，同時數(shù)據(jù)流中存在的類不平衡問題也會嚴(yán)重影響算法的分類性能。針對概念漂移和類不平衡的聯(lián)合問題，在基于數(shù)據(jù)塊集成的方法上引入在線更新機(jī)制，結(jié)合重采樣和遺忘機(jī)制提出了一種增量加權(quán)集成的不平衡數(shù)據(jù)流分類方法（incremental weighted ensemble for imbalance learning，IWEIL）。該方法以集成框架為基礎(chǔ)，利用基于可變大小窗口的遺忘機(jī)制確定基分類器對窗口內(nèi)最近若干實(shí)例的分類性能，并計(jì)算基分類器的權(quán)重，隨著新實(shí)例的逐個到達(dá)，在線更新IWEIL中每個基分器及其權(quán)重。同時，使用改進(jìn)的自適應(yīng)最近鄰SMOTE方法生成符合新概念的新少數(shù)類實(shí)例以解決數(shù)據(jù)流中類不平衡問題。在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，結(jié)果表明，相比于DWMIL算法，IWEIL在HyperPlane數(shù)據(jù)集上的G-mean和recall指標(biāo)分別提升了5.77%和6.28%，在Electricity數(shù)據(jù)集上兩個指標(biāo)分別提升了3.25%和6.47%。最后，IWEIL在安卓應(yīng)用檢測問題上表現(xiàn)良好。

關(guān)鍵詞：數(shù)據(jù)流；不平衡數(shù)據(jù)；概念漂移；增量加權(quán)；集成學(xué)習(xí)

中圖分類號：TP391?? 文獻(xiàn)標(biāo)志碼：A??? 文章編號：1001-3695（2024）03-031-0854-07doi： 10.19734/j.issn.1001-3695.2023.08.0330

Imbalanced drift data stream classification algorithm based on incremental weight

Cai Bo1a， Zhang Haiqing1a， 1b， Li Daiwei1a，1b， Xiang Xiaoming2， Yu Xi3， Deng Junyu1a

（1.a.School of Software Engineering， b. Sichuan Province Informationization Application Support Software Engineering Technology Research Center， Chengdu University of Information Technology， Chengdu 610255， China; 2.Sichuan Meteorological Observation & Data Center， Chengdu 610072， China; 3.Stirling College， Chengdu University， Chengdu 610106， China）

Abstract：

Concept drift is a difficult problem in the field of data stream learning， while the class imbalance problem existing in the data stream can seriously affect the classification performance of the algorithm. To address the joint problem of concept drift and class imbalance， this paper proposed an incremental weighted ensemble for imbalance learning （IWEIL） method for classifying unbalanced data streams by introducing an online update mechanism on the method based on the integration of data chunks， combined with the resampling and forgetting mechanism. The IWEIL method utilized a variable-size window-based forgetting mechanism to determine the classification performance of base classifiers for a number of recent instances within the window， and calculated the weights of the base classifiers. It updated each base classifier and its weight in IWEIL online as a new instance reached every time. The IWEIL used an improved adaptive nearest-neighbor SMOTE method to generate new minority class instances that conformed to the new concept to solve the class imbalance problem in the data stream. The experimental results show that compared with the DWMIL algorithm， IWEIL method improves the G-mean and recall on the synthesized HyperPlane dataset by 5.77% and 6.28% respectively， and the two metrics on the real-world Electricity dataset by 3.25% and 6.47% respectively. Finally， IWEIL has performed well in the Android app detection problem. Key words：data streams; imbalance data; concept drift; incremental weight; ensemble learning

0 引言

在許多實(shí)際應(yīng)用中，如在線購物、疾病診斷和欺詐檢測，以順序方式生成的大量數(shù)據(jù)稱為數(shù)據(jù)流。由于工作條件或環(huán)境隨時間的變化，新到達(dá)的數(shù)據(jù)可能表現(xiàn)出與之前數(shù)據(jù)不同的分布，這被稱為概念漂移［1，2］，在這種情況下根據(jù)歷史數(shù)據(jù)創(chuàng)建的分類器可能無法識別新概念，甚至導(dǎo)致分類錯誤。此外，屬于不同類別的樣本數(shù)量可能會發(fā)生傾斜，形成不平衡的數(shù)據(jù)流［3］，而傳統(tǒng)分類方法通常偏向于多數(shù)類，導(dǎo)致分類結(jié)果不準(zhǔn)確。

受集成學(xué)習(xí)思想的啟發(fā)，能夠同時處理概念漂移與類不平衡問題的數(shù)據(jù)流分類算法可以分為在線集成和基于數(shù)據(jù)塊的集成［4］。在線集成方法通過每個傳入的樣本更新預(yù)測模型，并使用漂移檢測器來監(jiān)視數(shù)據(jù)流。一旦檢測到任何概念的漂移，現(xiàn)有的預(yù)測模型就會被重置，并為新的概念建立一個新的模型。Wang等人［5］將重采樣技術(shù)與在線裝袋相結(jié)合，形成過采樣在線裝袋OOB（oversampling online bagging）和欠采樣在線裝袋UOB （undersampling online bagging），根據(jù)實(shí)時不平衡率動態(tài)調(diào)整重采樣實(shí)例的數(shù)量，有效解決了數(shù)據(jù)流中類不平衡問題。在線集成方法能夠與解決數(shù)據(jù)流不平衡問題的漂移檢測方法相結(jié)合，Wang等人［6］提出的在線不平衡漂移檢測方法DDM-OCI（drift detection for online class imbalance learning）結(jié)合在線裝袋，通過監(jiān)測少數(shù)類召回率的變化來檢測不平衡數(shù)據(jù)流中的概念漂移，但DDM-OCI假設(shè)數(shù)據(jù)流服從高斯分布，因而在實(shí)際應(yīng)用中存在較高的誤報率［7］。隨后Wang等人［8］提出了線性四率HLFR （hierarchical linear four rate），該方法監(jiān)控混淆矩陣中的四種比率，即少數(shù)類召回率和精度以及多數(shù)類召回率和精度，并具有統(tǒng)計(jì)支持的漂移檢測界限，如果四個速率中的任何一個超過界限，則將確認(rèn)漂移，有效降低了DDM-OCI的誤報率。

基于數(shù)據(jù)塊的方法是通過使用循環(huán)緩存數(shù)組，從數(shù)據(jù)流中捕獲每個新到達(dá)的實(shí)例，一旦循環(huán)數(shù)組已滿，就在數(shù)據(jù)塊上構(gòu)建基分類器。第一個基于塊的不平衡數(shù)據(jù)流方法是不相關(guān)裝袋UCB（uncorrelated bagging）［9］，UCB不斷累積歷史數(shù)據(jù)塊中的少數(shù)類實(shí)例，然后添加到當(dāng)前數(shù)據(jù)塊中，同時對當(dāng)前數(shù)據(jù)塊進(jìn)行欠采樣，從而平衡數(shù)據(jù)分布。但是這種方法需要大量內(nèi)存空間來保存先前數(shù)據(jù)塊中的少數(shù)類實(shí)例，且未考慮少數(shù)類實(shí)例可能發(fā)生概念漂移的問題，存在著較大的局限性。選擇性遞歸方法SERA（selectively recursive approach）［10］和遞歸集成方法REA（recursive ensemble approach）［11］使用距離度量來選擇與當(dāng)前數(shù)據(jù)塊中的實(shí)例具有相似特征的少數(shù)實(shí)例，用于平衡當(dāng)前數(shù)據(jù)塊中的類別分布，同時解決了少數(shù)類實(shí)例中的子概念問題。上述基于數(shù)據(jù)塊的集成方法都隱含地假設(shè)少數(shù)類實(shí)例的概念不會發(fā)生變化，先前數(shù)據(jù)塊中的少數(shù)類實(shí)例可以繼續(xù)使用，然而對于具有概念漂移的數(shù)據(jù)流，尤其是同時存在類不平衡問題時，類的先驗(yàn)概率會隨著時間發(fā)生變化，導(dǎo)致這一假設(shè)很難成立。Ditzler等人［12］提出了Learn++CDS和Learn++NIE方法，該方法無須保存任何歷史數(shù)據(jù)，為每個塊創(chuàng)建一個單獨(dú)的基分類器，基分類器通過時間衰減函數(shù)及其在當(dāng)前塊上的性能進(jìn)行加權(quán)。Learn++CDS將合成少數(shù)類過采樣技術(shù)（synthetic minority over-sampling technique，SMOTE）［13］與概念漂移處理算法Learn++.NSE相結(jié)合，在發(fā)生漂移時生成新的少數(shù)實(shí)例；在Learn++.CDS的基礎(chǔ)上，Learn++.NIE 修改了帶有懲罰約束的權(quán)重機(jī)制，并用基于Bagging的子集替換了SMOTE，有效平衡了不同類別的重要性。

基于塊的集成方法學(xué)習(xí)固定大小的數(shù)據(jù)塊，缺點(diǎn)在于對數(shù)據(jù)塊內(nèi)發(fā)生的突然概念漂移的響應(yīng)效率低下。盡管減小數(shù)據(jù)塊大小有助于解決突然漂移問題，但該方式會增加計(jì)算成本，并降低穩(wěn)定狀態(tài)下基分類器的性能［14］。在線集成方法由新到達(dá)的實(shí)例動態(tài)更新，優(yōu)點(diǎn)在于可快速適應(yīng)突然的概念漂移。與基于塊的訓(xùn)練相比，該方法在訓(xùn)練的初始階段可能表現(xiàn)較差，因?yàn)槊總€時間步僅使用一個實(shí)例。為此，本文基于數(shù)據(jù)塊集成方法引入在線更新機(jī)制，提出了一種增量加權(quán)集成的不平衡數(shù)據(jù)流分類方法（IWEIL），用于具有類別不平衡的漂移數(shù)據(jù)流。IWEIL以集成框架為基礎(chǔ)，基分類器隨著每個新到達(dá)的實(shí)例而增量更新，目的是在概念漂移后學(xué)習(xí)最新的數(shù)據(jù)特征，基分類器的權(quán)重會根據(jù)估計(jì)窗口的性能進(jìn)行在線更新，估計(jì)窗口的大小根據(jù)基分類器產(chǎn)生不同誤分點(diǎn)之間的間隔和分布自適應(yīng)調(diào)整，以準(zhǔn)確反映基分類器在每個時刻的準(zhǔn)確率，同時采用一種改進(jìn)的自適應(yīng)最近鄰SMOTE方法生成符合新概念的新少數(shù)類實(shí)例，以解決數(shù)據(jù)流中類不平衡問題。與同類方法相比，本文主要貢獻(xiàn)有三個方面：a）提出了一種基于可變大小窗口的遺忘機(jī)制，通過在線方式評估基分類器的性能，以刪除表現(xiàn)不佳的基分類器，保證基分類器的分類性能；b）構(gòu)建了增量加權(quán)集成模型來解決基于數(shù)據(jù)塊集成方法中的自適應(yīng)延遲問題，該模型根據(jù)所提出的遺忘機(jī)制，隨著新實(shí)例的逐個到達(dá)，增量更新每個基分類器及其權(quán)重，能夠迅速響應(yīng)突變漂移和漸變漂移，有效解決了數(shù)據(jù)流中的概念漂移問題；c）采用一種改進(jìn)的自適應(yīng)最近鄰SMOTE方法生成少數(shù)類最近鄰參數(shù)k，該方法根據(jù)兩個相鄰數(shù)據(jù)塊的分布變化生成適應(yīng)新概念的新少數(shù)樣本，無須保存歷史數(shù)據(jù)塊的少數(shù)類實(shí)例，有效解決了數(shù)據(jù)流中的類不平衡問題。

1 相關(guān)概念

1.1 不平衡問題

類不平衡一直是分類問題中的一個棘手問題，針對于此，研究人員對機(jī)器學(xué)習(xí)中的傳統(tǒng)分類器（如SVM、KNN、貝葉斯等）進(jìn)行了大量研究，提出了許多改進(jìn)后能適應(yīng)于類不平衡問題的分類算法。在數(shù)據(jù)流領(lǐng)域中，類不平衡指的是一個類別的實(shí)例數(shù)量遠(yuǎn)遠(yuǎn)超過其他類別。假設(shè)給定數(shù)據(jù)流為〈S1，S2，…，St-1，St，St+1…〉，其中St（xt，yt），xt表示時刻t到達(dá)實(shí)例的特征向量，yt表示該實(shí)例的類標(biāo)簽，少數(shù)類樣本實(shí)例集合記為P，多數(shù)類樣本實(shí)例集合記為N，則S=N∪P。因此，不平衡數(shù)據(jù)分類可以看作一個二分類問題，少數(shù)類通常稱為正類，多數(shù)類稱為負(fù)類，不均衡的數(shù)據(jù)分布會導(dǎo)致分類器偏向于更容易建模的多數(shù)類，因?yàn)榉诸惼骺梢酝ㄟ^選擇多數(shù)類來實(shí)現(xiàn)高精度。然而從數(shù)據(jù)推理的角度來看，少數(shù)類往往是更重要的類別，因?yàn)槠淇赡軘y帶更多的相關(guān)信息。在不平衡數(shù)據(jù)流分類中，如果少數(shù)類樣本實(shí)例極少且出現(xiàn)的頻率低，不同類別之間的數(shù)據(jù)樣本比達(dá)到1∶99，將造成分類模型根本無法預(yù)測到少數(shù)類，但最終分類準(zhǔn)確率卻高達(dá)99%的情況，這種分類結(jié)果對更重要的少數(shù)類來說毫無意義。例如在醫(yī)療健康領(lǐng)域中，患病人群遠(yuǎn)遠(yuǎn)少于健康人群，但正確地檢測出患病人群比檢測出正常人群更有價值。

數(shù)據(jù)流中的不平衡比率可以理解為：少數(shù)類樣本在整個樣本集合中所占的數(shù)量［15］，即IR=P/S。當(dāng)IR=0.5時，數(shù)據(jù)類別分布平衡，當(dāng)IR的值小于某一特定閾值時，則當(dāng)前數(shù)據(jù)存在類不平衡問題。

目前處理不平衡數(shù)據(jù)的分類方法可以分為數(shù)據(jù)方法和算法方法。數(shù)據(jù)方法包括各種重采樣技術(shù)，對少數(shù)類樣本進(jìn)行過采樣，對多數(shù)類樣本進(jìn)行欠采樣，通過操作訓(xùn)練數(shù)據(jù)以糾正傾斜的數(shù)據(jù)分布；算法方法通過修改分類器訓(xùn)練機(jī)制來解決類不平衡問題，其直接目的是提高少數(shù)類的準(zhǔn)確性。

1.2 概念漂移

在數(shù)據(jù)流中，實(shí)例是根據(jù)底層概率分布Pt（X，Y）隨著時間推移而生成的［2］，其中X對應(yīng)于特征向量，Y對應(yīng)于類標(biāo)簽。如果流中的所有實(shí)例都基于相同的概率分布而生成，那么數(shù)據(jù)流是固定的；如果流中的概念和數(shù)據(jù)分布隨著時間的推移而變化，那么數(shù)據(jù)流中存在概念漂移［16］。下面從概率的角度來定義概念漂移，當(dāng)在時間t和t+1的聯(lián)合概率發(fā)生變化時就會產(chǎn)生概念漂移，即Pt（X，Y）≠Pt+1（X，Y）。根據(jù)貝葉斯定理［17］，聯(lián)合概率P（X，Y）可以分解為P（X，Y）=P（Y）P（Y|X），因此這種漂移可以分為真實(shí)漂移和虛擬漂移。在不影響P（Y）的情況下改變后驗(yàn)分布P（Y|X），將導(dǎo)致真正的概念漂移，這可能會改變決策邊界并降低分類模型的性能。在不影響P（Y|X）的情況下改變先驗(yàn)概率P（Y），會導(dǎo)致虛擬概念漂移，這不會改變決策邊界，但會改變不同類別實(shí)例的比例，與類不平衡現(xiàn)象有關(guān)。

如果發(fā)生概念漂移，根據(jù)歷史數(shù)據(jù)創(chuàng)建的分類器可能無法識別新概念，從而導(dǎo)致錯誤分類。概念漂移根據(jù)概念變化的速度可分為突變型概念漂移和漸變型概念漂移［18］。突變漂移指的是新舊概念過渡很快，舊概念立即變?yōu)閿?shù)據(jù)分布完全不同的新概念，導(dǎo)致分類模型性能急劇下降；漸變漂移則是新舊概念過渡較慢，舊概念逐漸變?yōu)樾赂拍?，使分類模型有一個適應(yīng)新概念的調(diào)整期。當(dāng)類不平衡與概念漂移相結(jié)合時，不平衡比率不再是靜態(tài)的，而是隨著流的變化而變化，并且隨著時間的推移，多數(shù)類與少數(shù)類的身份可以相互轉(zhuǎn)換。

目前處理概念漂移主要可以分為主動檢測方法和被動適應(yīng)方法［2］。在主動方法中，采用概念漂移檢測機(jī)制，通過監(jiān)控性能指標(biāo)（如準(zhǔn)確率和召回率）的變化來檢測是否發(fā)生概念漂移。一旦監(jiān)測指標(biāo)出現(xiàn)較大波動，就會觸發(fā)概念漂移警報，并更新分類器。被動方法中沒有漂移檢測機(jī)制，隨著數(shù)據(jù)的不斷輸入，通過不斷更新分類器來適應(yīng)概念漂移。構(gòu)建集成分類器是被動方法的常見選擇，其中每個基分類器都構(gòu)建在新到達(dá)的數(shù)據(jù)塊上，可以通過修改結(jié)構(gòu)、調(diào)整基分類器的權(quán)重來適應(yīng)新概念［19］。

2 增量加權(quán)集成的不平衡數(shù)據(jù)流分類方法

本文提出的IWEIL是一種對具有概念漂移的不平衡數(shù)據(jù)流進(jìn)行分類的新方法，IWEIL的總體框架如圖1所示。

IWEIL屬于基于數(shù)據(jù)塊的集成方法，數(shù)據(jù)流中的實(shí)例是逐塊處理的。對于每個數(shù)據(jù)塊，采用了一種改進(jìn)的合成少數(shù)類過采樣技術(shù)（AnnSMOTE） ［20］來生成新的少數(shù)實(shí)例，AnnSMOTE中少數(shù)近鄰數(shù)量取決于先前數(shù)據(jù)塊的分布變化程度，隨后在基于重采樣后的數(shù)據(jù)塊上構(gòu)建新的基分類器，并與歷史基分類器集成生成基分類器池；接下來設(shè)計(jì)了一種基于可變大小窗口的遺忘機(jī)制來估計(jì)基分類器池中每個基分類器的當(dāng)前性能，基分類器會隨著新到達(dá)的每個實(shí)例而增量更新，目的是學(xué)習(xí)概念漂移后的最新數(shù)據(jù)特征。此外，基分類器的權(quán)重也會根據(jù)其對估計(jì)窗口內(nèi)實(shí)例的分類性能進(jìn)行在線更新，根據(jù)基分類器對窗口內(nèi)的實(shí)例產(chǎn)生不同誤分點(diǎn)的間隔和分布，自適應(yīng)調(diào)整估計(jì)窗口的大小。在穩(wěn)定的分類性能下，估計(jì)窗口保留較大的尺寸以保存更多的歷史信息。一旦基分類器連續(xù)對實(shí)例進(jìn)行錯誤分類，估計(jì)窗口的大小就會自動變小，以更加關(guān)注數(shù)據(jù)流的最新特征。IWEIL充分利用了基于塊的學(xué)習(xí)和在線學(xué)習(xí)的優(yōu)勢，能夠快速適應(yīng)變化，有效解決不平衡數(shù)據(jù)流中的概念漂移問題。

2.1 自適應(yīng)最近鄰合成少數(shù)過采樣技術(shù)

為了解決分類問題中的類不平衡問題，常采用各種重采樣技術(shù)，其中SMOTE是較為流行的過采樣方法之一。SMOTE是基于隨機(jī)過采樣的一種改進(jìn)算法，通過在同類近鄰樣本間線性插值來增加樣本數(shù)量，有效解決了靜態(tài)數(shù)據(jù)中的類不平衡問題。在傳統(tǒng)的SMOTE方法中，所有少數(shù)樣本選定的近鄰數(shù)量（k）被預(yù)設(shè)為相同的值。然而在數(shù)據(jù)流中，一旦數(shù)據(jù)塊內(nèi)發(fā)生概念漂移，即多數(shù)類概念與少數(shù)類概念發(fā)生相互轉(zhuǎn)換，那么在固定k下基于歷史概念生成的新少數(shù)實(shí)例將不符合當(dāng)前數(shù)據(jù)塊中的類別分布，導(dǎo)致生成的新樣本適應(yīng)新概念的效率低下。因此本文采用了一種改進(jìn)的自適應(yīng)最近鄰SMOTE方法（AnnSmote），它的特點(diǎn)是根據(jù)相鄰數(shù)據(jù)塊中的數(shù)據(jù)分布自適應(yīng)地調(diào)整k，有助于生成有價值的少數(shù)實(shí)例，同時對于少數(shù)類，其對應(yīng)的k值由其所在子區(qū)域的分布決定，能夠有效解決動態(tài)流式數(shù)據(jù)中的類不平衡問題。

在AnnSMOTE中，采用循環(huán)緩存數(shù)組來捕獲數(shù)據(jù)流中每個新到達(dá)的實(shí)例，一旦循環(huán)數(shù)組已滿，就會在此數(shù)據(jù)塊上創(chuàng)建基分類器，同時清空循環(huán)數(shù)組以緩存即將到來的新實(shí)例。對于每個新的數(shù)據(jù)塊，首先統(tǒng)計(jì)不同類別的實(shí)例數(shù)量，以判斷當(dāng)前數(shù)據(jù)塊是否平衡，AnnSMOTE僅對不平衡的數(shù)據(jù)塊進(jìn)行重新采樣。具體流程如下：假設(shè)Bn是第n個不平衡數(shù)據(jù)塊，其中xni表示第i個少數(shù)類實(shí)例，kni表示用于重采樣的最近鄰樣本數(shù)量，確定kni的關(guān)鍵是判斷xni周圍子區(qū)域的數(shù)據(jù)分布是否發(fā)生變化。與之前的數(shù)據(jù)塊相比，子區(qū)域內(nèi)少數(shù)樣本的時變分布一般分為密度增加、密度減少和密度不變?nèi)N類型［21］，其中密度增加或減少的區(qū)域可能發(fā)生漂移。

對于xni，選擇其在Bn－1塊中的K1個少數(shù)最近鄰構(gòu)成一個子集Nn－1。Bn－1中xni周圍子區(qū)域的密度定義為xni與其少數(shù)近鄰間Nn－1的平均距離，如式（1）所示。

3 實(shí)驗(yàn)結(jié)果及其分析

為了驗(yàn)證IWEIL方法的有效性，本章將IWEIL的分類性能與四種最先進(jìn)的方法在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行比較。對比算法可分為基于數(shù)據(jù)塊的集成方法（Learn++.NIE、DWMIL）和在線集成方法（OOB、DDM-OCI）。實(shí)驗(yàn)的硬件環(huán)境是Intel CoreTM i7-10875H，內(nèi)存為16? GB的PC機(jī)，操作系統(tǒng)是Windows 10，編程語言為Python 3.7，每個實(shí)驗(yàn)獨(dú)立運(yùn)行10次。IWEIL的參數(shù)設(shè)置為：基分類器根據(jù)Scikit-Multiflow庫中的Hoeffding tree使用默認(rèn)設(shè)置；少數(shù)鄰居數(shù)量K1和重采樣的最大鄰居數(shù)K2參照文獻(xiàn)［20］，分別設(shè)定為5和7；數(shù)據(jù)塊大小L根據(jù)大量實(shí)驗(yàn)確定，設(shè)定為500；基分類器最大數(shù)量Kmax設(shè)定為20。

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

在實(shí)驗(yàn)中采用了五個人工數(shù)據(jù)集和兩個真實(shí)數(shù)據(jù)集來驗(yàn)證算法的有效性。其中SEA、Sine、HyperPlane、Gaussian使用概念漂移生成器生成，Electricity和Weather為真實(shí)數(shù)據(jù)集。IWEIL算法主要以二分類數(shù)據(jù)流為主。為了更好地研究不平衡數(shù)據(jù)流中的概念漂移問題，人工數(shù)據(jù)集分為突變型（abrupt）漂移和漸變型（gradual）漂移，具體數(shù)據(jù)集特征如表1所示。

3.2 算法評估指標(biāo)

準(zhǔn)確率作為傳統(tǒng)指標(biāo)并不能全面評價分類器在不平衡數(shù)據(jù)集上的實(shí)際表現(xiàn)。相比之下，曲線下面積（AUC）、F-score、G-mean和recall可以更客觀地衡量不平衡分類方法。本文中，幾何平均值G-mean 和少數(shù)類召回率recall用于分析分類器的性能，G-mean衡量非平衡數(shù)據(jù)集的分類性能，recall衡量少數(shù)類別的分類性能。G-mean和recall用表2所示的混淆矩陣來定義，其具體定義如式（10）（11）所示。

3.3 塊大小對IWEIL算法的影響

IWEIL是基于數(shù)據(jù)塊的集成分類算法，流中的實(shí)例是逐塊處理的，因此數(shù)據(jù)塊的大小直接影響算法的分類效果。

本節(jié)使用不同大小的數(shù)據(jù)塊L對算法的G-mean性能進(jìn)行了實(shí)驗(yàn)，結(jié)果如表3所示。

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

為了驗(yàn)證IWEIL的分類性能，本節(jié)在7組數(shù)據(jù)集上與4種同類算法進(jìn)行了對比實(shí)驗(yàn)，算法評估指標(biāo)為幾何平均值G-mean 和recall，結(jié)果如表4和5所示。由表4可知，IWEIL算法在7個數(shù)據(jù)集上的平均排名（average rank）最高，僅在Sea_abrupt數(shù)據(jù)集上與DWMIL算法相差2.17%，表明IWEIL中所提出的增量加權(quán)機(jī)制在對概念漂移數(shù)據(jù)流分類時表現(xiàn)良好，通過縮小估計(jì)窗口大小，使得連續(xù)產(chǎn)生誤分類的過時分類器的權(quán)重迅速下降，同時新創(chuàng)建的分類器被分配更高的權(quán)重，以提供對新概念更準(zhǔn)確的預(yù)測；而DDM-OCI的G-mean性能很差，在Sea_abrupt上僅為48.69%，雖然該算法能夠檢測概念漂移，但在處理快速變化的不平衡數(shù)據(jù)流時容易出現(xiàn)誤報甚至漏檢的情況，特別在面對突變型漂移時，容易將少數(shù)類實(shí)例誤分為多數(shù)類。recall的結(jié)果如表5所示，IWEIL算法在5個數(shù)據(jù)集上的recall值高于其他算法，在Sea_abrupt和Weather數(shù)據(jù)集上排名第2，分別與DWMIL算法相差1.95%和1.72%。從表4和5可以得出，IWEIL在G-mean和少數(shù)類召回率recall上的整體性能均優(yōu)于DWMIL，表明IWEIL在少數(shù)類上取得較好表現(xiàn)的同時，沒有以犧牲多數(shù)類的分類性能為代價，在二分類數(shù)據(jù)流中達(dá)到了最佳平衡。

為了更直觀地對比不同算法的性能，圖2和3繪制了不同算法的G-mean和少數(shù)類召回率recall的實(shí)驗(yàn)結(jié)果。

圖2為HyperPlane數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，該數(shù)據(jù)集存在類別分布不平衡問題，同時包含了漸變型概念漂移。

IWEIL在兩個評價指標(biāo)上的性能曲線基本保持平穩(wěn)，沒有較大波動，表現(xiàn)出其對漸變型概念漂移有較好的適應(yīng)能力，并且在G-mean和recall上均排名第1，這表明IWEIL能夠較好地平衡在不同類別上的分類性能。而OOB和DDM-OCI的性能曲線存在較大的波動，主要是因?yàn)樗鼈儾荒苎杆夙憫?yīng)概念漂移，存在自適應(yīng)延遲，最終影響了其在多數(shù)類上的性能。

圖3為Sine_abrupt數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，該數(shù)據(jù)集類別分布平衡，同時包含了突變型概念漂移。

圖3中各方法在G-mean和recall上的性能曲線變化基本一致，其中IWEIL和DWMIL的性能曲線基本保持平穩(wěn)，沒有較大波動，而OOB、Learn++. NIE和DDM-OCI的性能曲線存在較大波動。Sine_abrupt數(shù)據(jù)集每間隔整個數(shù)據(jù)樣本的20%，通過改變底層概率分布產(chǎn)生一次突變型概念漂移，從圖3可以看出，IWEIL和DWMIL受其影響較小，其中IWEIL得益于增量加權(quán)更新機(jī)制，通過縮小估計(jì)窗口大小迅速降低過時分類器的權(quán)重，同時為新創(chuàng)建的分類器分配更高的權(quán)重，最先完成對新概念的適應(yīng)；而DDM-OCI受其影響最大，主要是因?yàn)樗鼪]有成員分類器加權(quán)機(jī)制和淘汰機(jī)制，當(dāng)面對突變型概念漂移時只能通過在線更新機(jī)制緩慢適應(yīng)新概念，存在較大的自適應(yīng)延遲。

3.5 運(yùn)行時間比較

本節(jié)比較了5種算法在7個數(shù)據(jù)集上的運(yùn)行時間，結(jié)果如表6所示。總體來說，在線集成方法在運(yùn)行時間上整體優(yōu)于基于數(shù)據(jù)塊的集成方法，其中OOB的平均運(yùn)行時間最短，主要是該方法沒有成員分類器的加權(quán)和淘汰機(jī)制，也不需要額外的開銷去保存任何歷史數(shù)據(jù)，在整個分類階段只需要保持集成模型的在線更新和對少數(shù)實(shí)例的過采樣。Learn++.NIE的平均運(yùn)行時間最長，主要是在成員分類器權(quán)重計(jì)算階段，Learn++.NIE方法不僅考慮該分類器在當(dāng)前數(shù)據(jù)塊上的分類性能，同時還要兼顧其在歷史數(shù)據(jù)塊上的性能，最終導(dǎo)致決策時間消耗變大。IWEIL方法是在基于數(shù)據(jù)塊的集成上引入了在線更新機(jī)制，平均運(yùn)行時間低于基于數(shù)據(jù)塊的集成方法，高于在線集成方法，符合預(yù)期結(jié)果，其中IWEIL算法在AnnSMOTE方法中尋找前后數(shù)據(jù)塊中的少數(shù)最近鄰時時間消耗較大。

3.6 算法統(tǒng)計(jì)分析

為了驗(yàn)證IWEIL與其他模型之間是否在統(tǒng)計(jì)學(xué)上存在顯著差距，本節(jié)對G-mean和recall性能指標(biāo)進(jìn)行了置信度為95%的Nemenyi檢驗(yàn)，Nemenyi事后檢驗(yàn)的臨界差（CD）為1.762，結(jié)果如圖4、5所示。對G-mean的統(tǒng)計(jì)檢驗(yàn)表明，IWEIL與DWMIL、Leaen++.NIE、DDM-OCI、OOB之間沒有顯著差異，但在recall指標(biāo)的統(tǒng)計(jì)檢驗(yàn)中，IWEIL優(yōu)于其他方法。同時在兩種指標(biāo)的檢驗(yàn)結(jié)果中，IWEIL均名列前茅，總體來說，IWEIL在G-mean和recall性能指標(biāo)上取得了最穩(wěn)定及最優(yōu)異的表現(xiàn)。

3.7 算法應(yīng)用

為了驗(yàn)證IWEIL的實(shí)用性，將其用于安卓應(yīng)用檢測問題，幫助用戶識別惡意應(yīng)用。RevealDroid（Reve）是由項(xiàng)目RevealDroid［22］創(chuàng)建的真實(shí)安卓惡意應(yīng)用的數(shù)據(jù)集，其樣本由220個屬性和2個類標(biāo)簽組成，包含了22 538個善意樣本，2 528個惡意應(yīng)用樣本。該數(shù)據(jù)集中的善意樣本與惡意樣本之間存在類不平衡問題，不平衡率為0.11，同時惡意樣本存在概念漂移問題，如某種新的惡意樣本突然出現(xiàn)所產(chǎn)生的突變型概念漂移，再如某種舊的惡意樣本逐漸變化為新的惡意樣本所產(chǎn)生的漸變型概念漂移。

圖6為IWEIL算法在Reve數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，其中G-mean平均值為81.45%，表明IWEIL能夠較好地平衡善意樣本與惡意樣本之間的分類性能；recall平均值為78.52%，表明IWEIL能夠較好地分類識別出惡意應(yīng)用樣本。IWEIL首先采用AnnSmote方法對不平衡數(shù)據(jù)塊進(jìn)行處理，該方法與現(xiàn)有基于數(shù)據(jù)塊的集成方法相比，無須保存先前數(shù)據(jù)塊中的少數(shù)類實(shí)例，因此IWEIL的內(nèi)存開銷較小，可以處理海量數(shù)據(jù)樣本，對真實(shí)的安卓惡意樣本處理效率較高。同時，IWEIL采用增量加權(quán)集成機(jī)制，用最新的數(shù)據(jù)樣本更新基分類及其權(quán)重，刪除表現(xiàn)不佳的分類器，保證了分類器在善意樣本與惡意樣本之間的分類性能。

4 結(jié)束語

本文首先對數(shù)據(jù)流中的類不平衡問題和概念漂移進(jìn)行了詳細(xì)介紹，并對相應(yīng)的解決方法進(jìn)行了概述。隨后提出了一種新的不平衡數(shù)據(jù)流分類方法IWEIL，它充分利用了基于塊的學(xué)習(xí)和在線學(xué)習(xí)的優(yōu)勢，能夠快速適應(yīng)變化，有效解決了不平衡數(shù)據(jù)流中的概念漂移問題。IWEIL算法中的每個基分類器都是基于數(shù)據(jù)塊創(chuàng)建的，同時由實(shí)例逐個增量更新。為了評估基分類器的性能，提出了一種基于可變大小窗口的新型遺忘機(jī)制，它根據(jù)基分類器在最新實(shí)例上的表現(xiàn)來估計(jì)基分類器的分類性能，并將估計(jì)值作為權(quán)重分配給IWEIL中的基分類器。對于不平衡數(shù)據(jù)塊，IWEIL根據(jù)少數(shù)類實(shí)例在前后數(shù)據(jù)塊中的分布變化，自適應(yīng)調(diào)整用于重采樣的最近鄰樣本數(shù)量，生成有價值的少數(shù)類實(shí)例，從而平衡數(shù)據(jù)塊中的類別分布。通過在安卓應(yīng)用檢測問題Reve數(shù)據(jù)集上的應(yīng)用，證明了IWEIL的應(yīng)用價值。

本文將IWEIL與四種主流的同類方法在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行了對比，實(shí)驗(yàn)結(jié)果表明，該算法在G-mean和recall上都取得了較好的效果，證明了IWEIL方法的有效性，IWEIL在少數(shù)類別上保持較好性能的同時沒有犧牲在多數(shù)類別上的性能。后續(xù)研究工作將進(jìn)一步探究IWEIL在多分類數(shù)據(jù)流上的應(yīng)用。

參考文獻(xiàn)：

［1］Ditzler G，Roveri M，Alippi C，et al. Learning in nonstationary environments： a survey ［J］. IEEE Computational Intelligence Magazine，2015，10（4）： 12-25.

［2］Lu Jie，Liu Anjin，F(xiàn)an Dong，et al. Learning under concept drift： a review ［J］. IEEE Trans on Knowledge and Data Engineering，2018，31（12）： 2346-2363.

［3］He Haibo，Garcia E A. Learning from imbalanced data ［J］. IEEE Trans on Knowledge and Data Engineering，2009，21（9）： 1263-1284.

［4］Wang Shuo，Minku L L，Yao Xin. A systematic study of online class imbalance learning with concept drift ［J］. IEEE Trans on Neural Networks and Learning Systems，2018，29（10）： 4802-4821.

［5］Wang Shuo，Minku L L，Yao Xin. Resampling-based ensemble me-thods for online class imbalance learning ［J］. IEEE Trans on Know-ledge and Data Engineering，2014，27（5）： 1356-1368.

［6］Wang Shuo，Minku L L，Yao Xin. A learning framework for online class imbalance learning ［C］// Proc of IEEE Symposium on Computational Intelligence and Ensemble Learning. Piscataway，NJ： IEEE Press，2013： 36-45.

［7］梁斌，李光輝，代成龍. 數(shù)面向概念漂移且不平衡數(shù)據(jù)流的G-mean加權(quán)分類方法 ［J］. 計(jì)算機(jī)研究與發(fā)展，2022，59（12）： 2844-2857. （Liang Bin，Li Guanghui，Dai Chenglong. G-mean weighted classification method for imbalanced data stream with concept drift ［J］. Journal of Computer Research and Development，2022，59（12）： 2844-2857.）

［8］Wang Heng，Abraham Z. Concept drift detection for streaming data ［EB/OL］. （2015-05-03）. https：//arxiv.org/pdf/1504.01044.pdf.

［9］Gao Jing，F(xiàn)an Wei，Han Jing，et al. A general framework for mining concept-drifting data streams with skewed distributions ［C］// Proc of SIAM International Conference on Data Mining. ［S.l.］： SIAM，2007： 3-14.

［10］Chen Sheng，He Haibo. Sera： selectively recursive approach towards nonstationary imbalanced stream data mining ［C］// Proc of the 18th International Joint Conference on Neural Networks. Piscataway，NJ： IEEE Press，2009： 522-529.

［11］Chen Sheng，He Haibo. Towards incremental learning of nonstationary imbalanced data stream： a multiple selectively recursive approach ［J］. Evolving Systems，2011，2（1）： 35-50.

［12］Ditzler G，Polikar R. Incremental learning of concept drift from strea-ming imbalanced data ［J］. IEEE Trans on Knowledge and Data Engineering，2013，25（10）： 2283-2301.

［13］Chawla N V，Bowyer K M，Hall L O，et al. Synthetic minority over-sampling technique ［J］. Journal of Artificial Intelligence Research，2002，16（1）： 321-357.

［14］Brzezinski D，Stefanowski J. Reacting to different types of concept drift： the accuracy updated ensemble algorithm ［J］. IEEE Trans on Neural Networks and Learning Systems，2013，25（1）： 81-94.

［15］王俊紅，郭亞惠. 面向動態(tài)數(shù)據(jù)塊的非平衡數(shù)據(jù)流分類算法 ［J］. 計(jì)算機(jī)工程與應(yīng)用，2021，57（13）： 124-129. （Wang Junhong，Guo Yahui. Imbalanced data stream classification algorithm for dynamic data chunk ［J］. Computer Engineering and Applications，2021，57（13）： 124-129. ）

［16］許冠英，韓萌，王少峰，等. 數(shù)據(jù)流集成分類算法研究綜述 ［J］. 計(jì)算機(jī)應(yīng)用研究，2019，37（1）： 1-8，15. （Xu Guanying，Han Meng，Wang Shaofeng，et al. Summarization of data stream ensemble classification algorithm ［J］. Application Research of Computers，2019，37（1）： 1-8，15. ）

［17］Kelly M G，Hand D J，Adams N M. The impact of changing populations on classifier performance ［C］// Proc of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM Press，1999： 367-371.

［18］Lu Ning，Lu Jie，Zhang Guangquan，et al. A concept drift-tolerant case-base editing technique ［J］. Artificial Intelligence，2016，230（1）： 108-133.

［19］Kolter J Z，Maloof M A. Dynamic weighted majority： an ensemble method for drifting concepts ［J］. Journal of Machine Learning Research，2007，8： 2755-2790.

［20］Jiao Botao，Guo Yinan，Gong Dunwei，et al. Dynamic ensemble selection for imbalanced data streams with concept drift ［J］. IEEE Trans on Neural Networks and Learning Systems，2022，35（1）： 1278-1291.

［21］Liu Anjin，Song Yiliao，Zhang Guanquan，et al. Regional concept drift detection and density synchronized drift adaptation ［C］// Proc of the 26th International Joint Conference on Artificial Intelligence. Palo Alto，CA： AAAI Press，2017： 2280-2286.

［22］Garcia J，Hammad M，Malek S. Lightweight，obfuscation-resilient detection and family identification of Android malware ［J］. ACM Trans on Software Engineering and Methodology，2018，26（3）：1-29.