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

摘 要：

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

關鍵詞：數據流；不平衡數據；概念漂移；增量加權；集成學習

中圖分類號：TP391?? 文獻標志碼：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 引言

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

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

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

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

1 相關概念

1.1 不平衡問題

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

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

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

1.2 概念漂移

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

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

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

2 增量加權集成的不平衡數據流分類方法

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

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

2.1 自適應最近鄰合成少數過采樣技術

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

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

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

3 實驗結果及其分析

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

3.1 實驗數據集

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

3.2 算法評估指標

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

3.3 塊大小對IWEIL算法的影響

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

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

3.4 實驗結果分析

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

為了更直觀地對比不同算法的性能，圖2和3繪制了不同算法的G-mean和少數類召回率recall的實驗結果。

圖2為HyperPlane數據集上的實驗結果，該數據集存在類別分布不平衡問題，同時包含了漸變型概念漂移。

IWEIL在兩個評價指標上的性能曲線基本保持平穩(wěn)，沒有較大波動，表現出其對漸變型概念漂移有較好的適應能力，并且在G-mean和recall上均排名第1，這表明IWEIL能夠較好地平衡在不同類別上的分類性能。而OOB和DDM-OCI的性能曲線存在較大的波動，主要是因為它們不能迅速響應概念漂移，存在自適應延遲，最終影響了其在多數類上的性能。

圖3為Sine_abrupt數據集上的實驗結果，該數據集類別分布平衡，同時包含了突變型概念漂移。

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

3.5 運行時間比較

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

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

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

3.7 算法應用

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

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

4 結束語

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

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

參考文獻：

［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，Fan 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］梁斌，李光輝，代成龍. 數面向概念漂移且不平衡數據流的G-mean加權分類方法 ［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，Fan 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)數據塊的非平衡數據流分類算法 ［J］. 計算機工程與應用，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］許冠英，韓萌，王少峰，等. 數據流集成分類算法研究綜述 ［J］. 計算機應用研究，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.