非平衡概念漂移數據流主動學習方法

李艷紅 王甜甜 王素格 李德玉

隨著互聯網和移動通訊技術的發展,流數據變得越來越普遍,如社交網絡、超市交易、傳感器網絡、垃圾郵件過濾等領域的數據往往都是以流的形式出現,具有實時、動態變化、潛在無窮等特點[1].為從復雜多變的數據流中挖掘有價值的信息,迫切需要研究面向數據流的高效學習方法實時捕獲數據流中變化的簇結構[2].

在實際應用中,數據流的概念漂移、標簽成本昂貴和多類不平衡特性給數據流分類任務帶來挑戰,這些特性往往同時存在、相互影響,使得數據流的分類任務變得更加復雜[3].數據流的概念漂移是指隨著時間的推移其數據分布發生不可預見的變化,從而使得之前訓練的分類模型不再適用[4].目前概念漂移的處理包括主動檢測[5]和被動適應[6]兩種方法.主動檢測方法通?；诜诸惸Ｐ托阅艿南陆祷驍祿植嫉淖兓瘷z測概念漂移,只有在檢測到概念漂移時才會更新分類模型[7];被動適應方法通常以固定的時間間隔采樣數據流中的樣本并定期調整分類模型,無需進行概念漂移檢測[8].被動適應方法以恒定的速度更新模型,不具有針對性,時間開銷較大[9],因此本文采用主動檢測方法來處理概念漂移.根據數據分布隨時間推移變化速度和形式的不同,可將概念漂移分為4 種類型: 突變型、重復型、增量型和逐漸型.其中突變型概念漂移是指在某一時刻,舊數據分布突然變化為新數據分布;重復型概念漂移是指發生突然型概念漂移后,新數據分布維持一段時間又突然變為舊數據分布;增量型概念漂移是指舊數據分布在一段時間內緩慢變化為新數據分布,緩慢變化過程的數據分布為新舊數據分布的混合;逐漸型概念漂移是指在一段時間內新數據分布逐漸取代舊數據分布,在變化過程中新舊數據分布交替出現[10].為檢測概念漂移以及更新分類模型,現有的方法通常假定可以不受限制地訪問數據流中所有樣本的標簽(即有監督的學習方法),這在實際應用中是不現實的[11].而主動學習方法可以通過查詢少量最有價值的樣本標簽構建分類模型,進而解決標簽成本昂貴的問題[12-13].

數據流的類不平衡特性會使分類模型對少數類樣本的學習不夠充分,從而導致模型的分類準確率下降[14];而且類不平衡比率可能會隨著時間的推移發生變化,在設計標簽查詢策略時需要特別關注[15].類不平衡問題可以從數據[16]和算法[17]兩個層面加以解決.數據層面是指通過減少多數類樣本或增加少數類樣本來平衡類分布,但這種方式會丟失有用信息或增加過擬合的風險.算法層面是指通過給少數類樣本增加額外的損失代價,或者基于Boosting 方法重新訓練分錯的樣本,使得分類模型更加關注少數類樣本.本文在標簽查詢和基分類器重構時分別使用基于算法層面和數據層面的類不平衡處理方式.

本文提出一種非平衡概念漂移數據流主動學習方法(Active learning method for imbalanced concept drift data stream,ALM-ICDDS),該方法包括初始化階段和在線學習階段.在初始化階段訓練初始集成分類器.在線學習階段,首先使用初始集成分類器預測樣本并計算樣本的預測確定性,基于該確定性和邊緣閾值矩陣查詢樣本標簽;然后為了將難區分、少數類和代表當前數據分布的樣本保存在記憶窗口中,用新查詢到標簽的樣本替換窗口中記憶強度最低的樣本;最后當檢測到概念漂移時,利用記憶窗口中的樣本構建新基分類器并替換重要性最低的已有基分類器.本文的主要貢獻有以下幾點:

1)提出基于多預測概率的樣本預測確定性度量以及邊緣閾值矩陣的自適應調整方法,從而使標簽查詢策略適用于類別數較多的非平衡數據流.

2)提出基于記憶強度的樣本替換策略,將難區分、少數類和代表當前數據分布的樣本保存在記憶窗口中,并用于漂移后基分類器的重構.

3)定義基于分類精度的基分類器重要性評價及更新方法,提出一種集成分類器更新機制.

1 相關工作

本節將分別介紹基于監督學習和主動學習的非平衡概念漂移數據流分類方法的研究現狀.

1.1 數據流監督學習方法

在數據流監督學習方法中,依據對數據流處理方式的不同,可分為基于數據塊的批處理方法和基于單個樣本的在線學習方法.

基于數據塊的批處理方法首先將數據流劃分成固定大小的塊,然后對數據塊采樣來實現類平衡,采樣的樣本用于訓練分類模型.Gao 等[18]提出一種基于數據塊的類不平衡數據流集成分類方法,通過累計歷史數據塊中的少數類樣本和對當前數據塊中的多數類樣本隨機欠采樣來實現類平衡,并用于訓練新基分類器來適應概念漂移,但該算法需要累積足夠多的樣本才可以新建基分類器,因此缺乏快速適應新概念的能力.基于此,Lu 等[19]提出一種基于基分類器動態加權的集成分類方法,該方法通過對每個塊中的多數類樣本欠采樣來實現類平衡,并為每個塊創建一個新的基分類器來及時學習新概念,同時淘汰權重小于閾值的基分類器來提高算法效率.但是在真實數據流中概念漂移的位置是不可預知的,因此,此類方法面臨的主要問題是難以確定合適的塊大小[20].

基于單個樣本的在線學習方法首先用最初的一部分樣本建立初始分類模型,然后在線學習階段,用每個新到來樣本動態更新分類模型[21].Wang 等[22]提出在線過采樣(Oversampling online bagging,OOB)和在線欠采樣(Undersampling online bagging,UOB)兩種方法來解決數據流中的類不平衡問題,這兩個方法基于一個時間衰減函數來實時計算當前的類不平衡比率,當檢測到類不平衡比率發生嚴重的傾斜時,基于重采樣的樣本重新訓練分類模型,但這兩種方法沒有檢測數據流中的概念漂移.Cano 等[23]提出一種在線自調整集成分類方法(Robust online self-adjusting ensemble,ROSE),該方法為每類樣本設置一個滑動窗口緩沖區來保存最新的樣本,并基于自適應滑動窗口ADWIN 方法[24]比較兩個子窗口之間錯誤率的差異程度來檢測概念漂移,當檢測到發生概念漂移時,重構一個新的集成分類器,并與舊的集成分類器組合選出一組性能最好的基分類器.以上方法只能解決數據流分類中的二類不平衡問題,對于多類不平衡問題,Barros等[25]基于AdaBoost 提出BOLE (Boosting-like online learning ensemble)方法,該方法根據類不平衡比率為樣本設置初始化權重,同時使用Ada-Boost 將弱分類器逐步迭代為強分類器,并使用DDM[26]算法來檢測概念漂移,當檢測到發生概念漂移則重構分類模型.但基于AdaBoost 的集成分類方法時間復雜度較高,尤其當基分類器的誤差率較高時,基分類器需要迭代更多的次數,同時也容易出現過擬合的現象[27].Bifet 等[28]基于Bagging 提出LB (Leverage bagging)方法,該方法對每個新到來樣本都設置一個隨機權重,并基于ADWIN 來檢測概念漂移,當發生概念漂移時,新建一個基分類器來淘汰分類效果最差的基分類器.Ferreira 等[29]基于隨機森林進行改進提出ARFRE (Adaptive random forest with resampling)方法,該方法通過計算數據流中每類樣本出現的次數來評估當前的類不平衡比率,然后與泊松分布的輸出相結合作為樣本的訓練權重,從而增加少數類樣本用于訓練的機會.基于隨機森林的方法在Bagging 的基礎上引入隨機屬性的選擇,進一步增強基學習器之間的差異和獨立性[30].

以上數據流監督學習方法需要獲取全部樣本的標簽,然而在實際應用中獲取全部樣本標簽的代價往往十分高,此時該類方法難以得到很好的應用.

1.2 數據流主動學習方法

主動學習方法通過人工標注難區分樣本,并將其用于分類模型的更新,通過將專家知識融入分類模型,實現利用少量帶標簽樣本完成數據流的分類任務[31].主動學習方法的性能很大程度上依賴于標簽查詢策略的好壞[32].目前標簽查詢策略方法有隨機策略、不確定性策略,以及混合策略[33-36].隨機策略是指隨機選擇樣本進行標簽查詢.不確定性策略是指根據模型對樣本的預測不確定性程度選擇樣本進行標簽查詢.混合策略則是結合隨機策略和不確定性策略的一種綜合方法.數據流主動學習需要全面考慮類不平衡、概念漂移和異常點等因素對分類器性能的影響,設計高效的標簽查詢策略,從而提高數據流主動學習方法的性能.

針對二分類數據流,Xu 等[33]提出一種基于混合標簽查詢策略的數據流主動學習方法,包含用于樣本預測的靜態分類器和檢測概念漂移的動態分類器.該方法使用混合標簽查詢策略查詢到的樣本更新靜態分類器,基于動態分類器預測樣本的錯誤率變化來檢測概念漂移.當發生概念漂移時用動態分類器取代靜態分類器,并基于隨機策略查詢到的樣本重新訓練新的動態分類器.Liu 等[34]提出一種二分類概念漂移數據流在線主動學習方法,該方法除使用混合標簽查詢策略外,還基于數據流樣本的局部密度來查詢標簽(局部密度值大的樣本更具有代表性),并使用查詢到標簽的樣本更新分類模型以適應概念漂移.

上述兩個主動學習方法沒有考慮數據的平衡性,不適用于多類不平衡數據流.Liu 等[35]提出一種概念漂移多類不平衡數據流主動學習方法(A comprehensive active learning method for multiclass imbalanced streaming data with concept drift,CALMID),該方法使用一個非對稱邊緣閾值矩陣來存儲樣本預測的不確定性閾值,該方法在調整邊緣閾值矩陣時,采用固定的比率,沒有考慮樣本預測的不確定程度.李艷紅等[36]提出一種非平衡數據流在線主動學習方法(Online active learning method for imbalanced data stream,OALM-IDS),該方法定義基于不平衡比率的樣本重要性度量,使得AdaBoost.M2 適用于非平衡數據流,提出基于樣本預測不確定程度的邊緣閾值矩陣自適應調整方法,并定義基于概念漂移指數和不平衡比率的樣本重要性度量,實現漂移后的模型重構.方法CALMID和OALM-IDS 基于樣本預測的兩個最大概率值之差進行標簽查詢,不適用于數據流中樣本類別數較多的情況;并基于先進先出的樣本滑動窗口保存查詢到標簽的樣本,沒有考慮樣本被“回憶”的次數和樣本的預測誤差.

集成分類方法常用于數據流在線學習,當發生概念漂移時,舊基分類器很可能不再適用,需要被替換為適用于當前數據分布的新基分類器.研究者針對基分類器的選擇、組合和動態更新開展相關研究.Zhao 等[37]提出一種通過模型重用處理概念漂移的方法,該方法基于當前數據塊的分類性能自適應地為已有模型分配權重,將已有模型的加權組合作為新分類模型從而實現模型重用并適應概念漂移.Karimi 等[38]提出一種基于主動學習的預訓練模型選擇方法,該方法基于標簽查詢策略選擇信息較豐富的樣本進行人工標注,并根據標注樣本的分類性能為分類模型分配權重.Zyblewski 等[39]提出一種面向高度不平衡漂移數據流的預處理和分類器動態集成選擇方法,該方法結合欠采樣和過采樣對非平衡數據流進行預處理,將基于Bagging 生成的多個分類模型加入模型池,根據當前數據塊的分類性能選擇分類模型以適應概念漂移.

本文的研究工作將綜合考慮數據流分類任務中面臨的概念漂移、標簽成本昂貴和多類不平衡問題,從標簽查詢、記憶窗口維護和集成分類器更新三方面開展研究,從而提高數據流主動學習方法的性能.

2 問題的形式化定義

設本文要處理的數據流DS={x1,x2,···,xi,···},其中xi表示第i個樣本,ti為第i個樣本到達的時刻,Y為樣本的類別標簽,Y={y1,y2,···,yk},k為樣本的類別數.由于數據流中的樣本是實時到達并且無窮的,在初始化階段選取最初到達的Sl個樣本用于構建初始集成分類器E,同時將這Sl個樣本的類別標簽存入標簽滑動窗口LW[Sl],用于計算類不平衡比率im.

在線學習階段,用初始集成分類器E對新樣本xi進行類別預測,同時定義樣本預測的確定性度量D(xi).為篩選出難區分和少數類的樣本進行人工標注,定義nd維邊緣閾值矩陣M,用于保存集成分類器對樣本預測的前nd個可能類(即前nd大預測概率對應的類)不同取值下的樣本預測確定性閾值,矩陣元素初值為θ0.在新樣本到達的同時,采用先進先出的方式對LW進行更新,LW用于保存最近Sl個連續樣本的標簽(基于隨機策略查詢到的樣本存放真實類別標簽,基于不確定性策略查詢到的樣本和沒有查詢標簽的樣本存放Null標簽).將人工標記的樣本信息存儲在記憶窗口MW[k][Sm] 中,Sm為每類樣本存儲的個數,樣本信息包括樣本被“回憶”的次數λx、最后一次被“回憶”的時刻τx以及預測誤差f(x),MW用于計算樣本的記憶強度S(x).為在記憶窗口中保存難區分、少數類和代表當前數據分布的樣本,用新查詢到標簽的樣本替換窗口中記憶強度最低的樣本.每當基于標簽查詢策略為樣本查詢到真實標簽后,調用ADWIN 算法判斷是否發生概念漂移.如果發生概念漂移,則使用MW中的樣本重新訓練新的基分類器Cnew,同時更新集成分類器E中每個基分類器的重要性,并用Cnew替換重要性最低的基分類器.

本文采用Hoeffding 樹作為基分類器,利用由多個Hoeffding 樹構成的集成分類器E對樣本進行預測,并在查詢到樣本標簽時更新基分類器.本文的數據流學習框架適用于其他分類模型,例如可以使用支持向量機、極限學習機等作為基分類器,并設計相應的模型更新方法.

3 本文方法

3.1 樣本預測的確定性度量

數據流的主動學習就是在分類過程中查詢那些預測確定性低和代表性樣本的真實標簽,并將人工標注的樣本用于分類器更新,使得分類器適應當前的數據分布.因此如何度量樣本預測的確定性直接關系到選擇哪些樣本用于更新分類器.現有的研究工作中,樣本預測的確定性度量通?；谥眯哦?、邊緣抽樣和熵等方法.置信度是分類器對樣本預測最大概率值,置信度越低,表明分類器對該樣本預測的確定性越低;邊緣抽樣根據兩個樣本預測最大概率值之間的差值選擇樣本,差值越小,表明樣本預測的確定性越低;基于熵的方法通過度量分類器對樣本所有預測概率的混亂程度來選擇樣本,越混亂,熵越大,表明樣本預測的確定性越低.

基于置信度的方法只考慮樣本預測的最大概率值,而忽略其他類別的預測信息;邊緣抽樣方法只考慮兩個最大概率值之間的差值,忽略樣本預測的最大概率值;基于熵的方法對不同大小的預測概率是同等對待的,但在度量樣本預測確定性時,需要考慮預測概率的序關系,通常預測概率大的值之間的差異要比預測概率小的值之間的差異更重要.為提高標簽查詢策略的有效性,本文在度量樣本預測的確定性時考慮下面兩方面因素:

1)基于分類器對樣本預測的最大概率值和兩個最大概率值之間的差值綜合評價樣本預測的確定性(二者之和越大,樣本預測確定性越高,反之確定性越低).

2)當類別數較多時,還應考慮樣本預測最大概率值與其余預測概率的差值.

基于此,本文定義樣本預測的確定性度量D(xi)如下

其中,P(|xi)表示樣本預測的最大可能類概率,相應的類標簽為,調節參數β∈[0,1].μ(xi)表示最大可能類與其余類預測概率的平均差值,計算方式為

其中,P(|xi)表示樣本預測的第cj大概率值,相應的類標簽為.n為確定性度量所使用的預測概率的類別數.

為篩選出預測確定性低的樣本進行人工標注,需要指定樣本預測確定性閾值.不確定性標簽查詢策略[34-35]通常使用唯一的樣本預測確定性閾值(固定閾值或可變閾值),無法刻畫多分類問題中類之間區分難易程度的差異.為解決這一問題,本文使用邊緣閾值矩陣保存樣本預測確定性閾值.在邊緣閾值矩陣的動態調整過程中,難區分類之間的確定性閾值通常小于易區分類之間的確定性閾值,多數類對少數類的確定性閾值通常小于少數類對多數類的確定性閾值.在標簽查詢時,這種樣本預測確定性閾值的設置方式傾向于給難區分和少數類樣本更多的機會,而不是易區分和多數類樣本.

基于上述樣本預測確定性度量D(xi)和邊緣閾值矩陣M,本文提出一種標簽查詢策略,根據樣本分類難度查詢樣本的真實標簽,并基于樣本預測結果和類不平衡比率對邊緣閾值矩陣M進行自適應調整,具體方式如下:

1)如果D(xi)>M[c1,c2,···,],則表明分類器對樣本xi的預測結果較為確定,因此不需要查詢xi的真實標簽,也不需要調整邊緣閾值矩陣.

2)如果D(xi)≤M[c1,c2,···,],則表明分類器對樣本xi的預測結果不確定,需要查詢樣本的真實類別標簽y.若樣本預測的最大可能類與真實類別y一致,表明該樣本預測正確,無需查詢其標簽,此時應降低閾值M[c1,c2,···,].

閾值M[c1,c2,···,] 的降低程度應與類不平衡比率成正比,類不平衡比率越高,則表明該類樣本數量越多,閾值的降低程度應該越高,反之閾值的降低程度應該越低.據此,本文提出邊緣閾值矩陣自適應調整方式為

其中,0<α<1,不平衡比率基于標簽滑動窗口LW中累積的標簽進行計算,計算方式為

其中,labelnumy為LW中y類的標簽個數,nullnum為LW中空標簽的個數.

除上述基于樣本預測確定性的標簽查詢策略外,本文還隨機地從數據流中選擇一些樣本進行標簽查詢(稱為代表性樣本),用于刻畫數據流的整體分布,二者合稱混合標簽查詢策略.

3.2 基于記憶強度的樣本替換策略

如前所述,記憶窗口用于保存查詢到標簽的樣本,包括難區分、少數類樣本和當前數據分布的代表性樣本.隨著時間的推移,記憶窗口中的樣本需要被新查詢到標簽的樣本替換,現有的替換方法通常用到達時間作為樣本的重要性度量,即認為后到達的樣本比先到達樣本更能代表當前的數據分布,因而采用基于先進先出的替換策略.為替換記憶窗口中的樣本,本文從以下三個方面來衡量樣本的重要性:

1)樣本被“回憶”的次數(如果數據流的當前樣本落在記憶窗口中樣本x的鄰域范圍內,則稱樣本x被“回憶”一次).樣本被“回憶”的次數越多,表明在數據流中該樣本出現的次數越多,其重要性應該越高.

2)樣本最后一次被“回憶”的時刻.樣本最后一次被“回憶”的時刻與當前時刻越接近,表明該樣本越能代表當前數據分布,其重要性越高.

3)集成分類器對樣本的預測誤差.預測誤差越大,表明該樣本與歷史數據分布越不相符,應具有更高的重要性.

基于此,本文將記憶窗口MW中樣本x的重要性,即記憶強度S(x)定義為

其中,ti為當前樣本xi到達的時刻,τx為樣本x最后一次被“回憶”的時刻,λx為樣本x被“回憶”的次數,f(x)為樣本x的預測誤差.其中λx和f(x)的計算分別如式(6)和式(7)所示.

其中,Dis(xi,x)為樣本xi與x的距離,MinDis(x)為樣本x與記憶窗口中同類樣本的最小距離.I(·)為指示函數,當“ · ”為真時取值為1,為假時取值為0.

其中,P(y|x)為集成分類器對樣本x真實類別y的預測概率.

為解決數據流的多類不平衡問題,本文為記憶窗口中的所有類分配等量的存儲空間,并且樣本替換僅在同類樣本中進行.在記憶窗口維護過程中,少數類和難區分的樣本會頻繁發生替換,而多數類和易區分的樣本較少發生替換,從而保證記憶窗口中的樣本能夠代表數據流的當前分布.一旦發生概念漂移,基于這些樣本構建的基分類器可以更好地代表新的數據分布.此外,本文還將記憶強度作為樣本的權重來訓練新基分類器.

3.3 集成分類器的更新機制

在數據流分類過程中,為適應數據流中的概念漂移,需要不斷更新集成分類器.在對集成分類器更新時,通常采用新基分類器替代重要性較低的舊基分類器的方式,其關鍵在于基分類器的重要性評價.現有的方法通?；诜诸惥然騽摻〞r間對基分類器的重要性進行評價.本文提出一種新的基分類器重要性評價及更新方法: 新基分類器Cnew代表當前的數據分布,具有最高的重要性;舊基分類器對記憶窗口中樣本的分類精度越高,其重要性越高;舊基分類器Cd的重要性隨著新基分類器的加入不斷降低.

據此,基分類器重要性定義及更新方式為

其中,1≤d ≤D,D為集成分類器中基分類器的個數,hd(MW[i,j])為基分類器Cd對樣本MW[i,j]的預測類別,y為該樣本的真實類別.

基于上述基分類器重要性評價及更新方式,本文提出一種集成分類器更新機制: 當發生概念漂移時,首先基于記憶窗口MW中的樣本構建新基分類器Cnew,并初始化其重要性為 1/D;然后根據式(9)更新所有舊基分類器的重要性;接下來用Cnew替換重要性最小的舊基分類器,并歸一化所有基分類器的重要性.

在實際應用中數據流中會出現不同類型的概念漂移,當發生突變型和重復型概念漂移時,集成分類器中的基分類器往往會連續更替;當發生增量型和逐漸型概念漂移時,基分類器的更替速度相對較為緩慢.可見,本文提出的集成分類器更新機制適用于不同類型的概念漂移.

3.4 算法框架

本文提出一種非平衡概念漂移數據流的主動學習方法ALM-ICDDS,該方法包括初始化階段和在線學習階段,如圖1 所示.在初始化階段,使用最初到達的Sl個樣本訓練D個基分類器構成初始集成分類器E,同時將這Sl個樣本的類別標簽存入標簽滑動窗口LW中.在線學習階段中包括標簽查詢、記憶窗口維護、概念漂移檢測、集成分類器更新四個任務.

圖1 算法框架Fig.1 Algorithm framework

1)標簽查詢.首先集成分類器E對新到來樣本xi進行預測;然后判斷是否滿足混合標簽查詢策略,若滿足則由專家標注該樣本,否則將預測結果作為樣本標簽,集成分類器E繼續預測下一個樣本;接下來更新標簽滑動窗口LW,并計算當前數據流的類不平衡比率;最后根據樣本預測結果和類不平衡比率自適應調整邊緣閾值矩陣M.

2)記憶窗口維護.對于新查詢到真實標簽的樣本xi,首先要判斷該樣本是否為異常點,若是異常點則繼續預測下一個樣本,否則需要初始化樣本xi的相關“記憶”信息;然后更新記憶窗口MW中與xi同類樣本x的被“回憶”次數λx、最后一次被“回憶”時刻τx,并計算記憶強度S(x);接下來用xi替換記憶強度最低的樣本(若記憶窗口中xi類樣本數量未達到Sm,則直接將樣本xi的“記憶”信息存入記憶窗口MW中).

3)概念漂移檢測.當基于混合標簽查詢策略為樣本查詢到真實標簽后,使用概念漂移檢測算法ADWIN 檢測數據流中是否發生概念漂移,若發生概念漂移則更新集成分類器;否則使用樣本xi更新基分類器對應的Hoeffding 樹,然后繼續預測下一個樣本.更新Hoeffding 樹采用自頂向下預剪枝的方式,首先更新樣本xi對應葉結點的統計信息并計算分類精度,然后基于信息增益選擇最優分裂屬性,如果葉結點分裂后的分類精度高于分裂前,則對其進行分裂,否則不分裂.ADWIN 算法基于兩個相鄰子窗口中預測正確率的差異程度來檢測概念漂移.算法的基本流程為: 首先用窗口W保存待檢測數據流,若數據流中的樣本預測正確保存1,錯誤保存0 (本文只保存查詢到標簽的樣本的預測情況);然后基于指數矩形圖計算窗口W的切割點,將窗口W切割成兩個子窗口W0和W1,并比較W0和W1預測正確率的差異.如果差異大于閾值?cut,則認為至少以 1 -δ的概率發生概念漂移,拋棄較舊的子窗口W0,否則認為至少沒有以 1 -δ的概率發生概念漂移.閾值?cut的定義方式為

其中,n0為子窗口W0的大小,n1為子窗口W1的大小.置信度δ∈(0,1),在本文實驗中,δ設置為0.002,窗口W、子窗口W0和W1的大小在檢測過程中是動態變化的.

4)集成分類器更新.當檢測到概念漂移后,首先基于記憶窗口MW中的樣本訓練新基分類器Cnew,然后根據式(9)更新舊基分類器的重要性,最后使用新基分類器Cnew替換重要性最小的舊基分類器.

3.5 算法偽代碼

本節給出非平衡概念漂移數據流主動學習算法ALM-ICDDS、基于樣本預測確定性的標簽查詢(Label query based on sample prediction certainty,LQ-SPC)算法和基于記憶強度的樣本替換(Sample replace based on memory strength,SRMS)算法的偽代碼.

算法1.ALM-ICDDS

算法 3.SR-MS

3.6 復雜度分析

下面對本文提出的算法ALM-ICDDS 進行復雜度的分析,由于初始化集成分類器E的復雜度主要取決于隨機森林算法,因此只分析在線學習階段的復雜度.

假設數據流DS的樣本個數為N、標記成本為B,則集成分類器E對數據流中樣本預測的時間復雜度為 O (D·NlogN),標簽查詢算法的時間復雜度為O(N),樣本替換算法的時間復雜度為 O (N·B·Sm),因此在線學習的時間復雜度為O(D·NlogN+N+N·B·Sm).

在線學習階段需要使用邊緣閾值矩陣M、標簽滑動窗口LW[Sl] 和記憶窗口MW[k][Sm],因此算法的空間復雜度為 O (knd+Sl+k·Sm).

4 實驗結果和分析

4.1 實驗環境和數據

本文實驗環境為Window10,處理器為Intel Core i7-7 700 3.60 GHz,內存16 GB,開發軟件使用IntelliJ IDEA (Community Edition),所有實驗均基于大規模在線分析平臺MOA (Massive online analysis)[40]實現.

實驗使用11 個合成數據流和3 個真實數據流,數據流的特征如表1 和表2 所示(表2 中的4 個數據流用于分析本文所提算法對不同類型概念漂移數據流的適用性).合成數據流DS1,DS2,DS7～DS11為平衡數據流;DS3和DS4為類不平衡比率固定的非平衡數據流;DS5和DS6為類不平衡比率可變的非平衡數據流,且在第200 000 個樣本處類不平衡比率發生變化.數據流DS2,DS4,DS6,DS7中添加5%的異常點和3 次概念漂移,其中第1 次和第3次為增量型概念漂移,第2 次為突變型概念漂移,數據流DS8～DS11中添加1 次概念漂移,分別為突變型、重復型、增量型和逐漸型概念漂移.實驗采用MOA 平臺的數據流生成器RandomRBF 和概念漂移合成工具ConceptDriftStream 構造突變型和增量型概念漂移數據流,具體步驟為: 首先使用RandomRBF 對基準數據聚類,并從聚類結果中選擇部分簇作為具有特定分布的數據流(當聚類個數不同時,選出數據流的分布也不相同,可作為概念漂移前后的數據流);然后使用ConceptDrift-Stream 將不同分布的數據流進行鏈接,基于給定的概念漂移寬度,以前一部分數據流的最后一個樣本為中心向兩邊擴展,并對這部分數據使用給定的擾動函數模擬概念漂移.一次重復型概念漂移相當于兩次突變型概念漂移,逐漸型概念漂移在一段時間內用新數據分布逐漸取代舊數據分布[10],本實驗在RandomRBF 生成不同分布數據流的基礎上編寫函數構造這兩種類型的概念漂移.漂移前后數據流聚類個數取值分別為50 和100,突變型和重復型概念漂移寬度設置為1,增量型和逐漸型概念漂移寬度設置為10 000.3 個真實數據流來源于公開數據集UCIs (University of California at Irvine),均為多類不平衡數據流,且概念漂移的類型和數量都是未知的.

表1 數據流特征Table 1 Data stream feature

表2 概念漂移數據流特征Table 2 Concept drift data stream feature

4.2 ALM-ICDDS 算法的分類性能評價

下面用本文提出的ALM-ICDDS 算法在7 個合成數據流和3 個真實數據流上與6 種數據流分類算法進行分類性能對比,6 種算法包括3 種監督學習算法(LB、BOLE 和ARFRE)和3 種主動學習算法(CALMID、OALM-IDS 和ALM-ICDDS-E),其中主動學習算法ALM-ICDDS-E 是將ALM-ICDDS算法中的樣本預測確定性度量替換為基于熵的度量后得到的算法.同時本文使用精確率 (P)、召回率(R)、F 1 值、K appa 系數和ROC (Receiver operating characteristic)曲線作為評價指標.所有算法在同一數據流上的實驗結果均取10 次實驗的平均值.

為保證實驗的公平性,所有算法均使用集成分類器,且均包含11 個基分類器.除ARFRE 算法使用其構造的ARFHoeffding 樹作為基分類器之外,其余算法均使用Hoeffding 樹作為基分類器.4 種主動學習算法的標簽預算B均設置為20%.CALMID和OALM-IDS 算法中標簽和樣本滑動窗口的大小都設置為500,ALM-ICDDS-E 和ALM-ICDDS 算法中標簽滑動窗口LW大小Sl設置為500,記憶窗口MW中每類樣本存儲個數Sm設置為100.綜合考慮算法的性能和空間復雜度,邊緣閾值矩陣維數nd取2 或3,分別對應數據流中樣本的類別數小于等于10 或大于10 的情況.隨機選擇比率ε設置為0.1,調節參數β設置為0.8,邊緣閾值矩陣元素的初始值θ0設置為0.75,邊緣閾值矩陣自適應調整參數α設置為0.1.參數n為樣本預測確定性度量所使用的預測概率的數目,通過測試n的取值對數據流分類性能的影響,給出如下所示的設置方法,具體細節參見第4.4 節.

兩種主動學習算法CALMID、OALM-IDS 和本文所提算法ALM-ICDDS 在線學習階段的空間復雜度分別為O(k2+wl+ws)、O(k2+wl+ws)和O(knd+Sl+k·Sm),其中wl和ws分別為標簽滑動窗口與樣本滑動窗口的大小.可見當數據流中樣本的類別數大于10 時,本文算法中邊緣閾值矩陣的空間開銷比CALMID 和OALM-IDS 算法大.此外,為處理非平衡數據,本文算法在記憶窗口中等量存儲每類的樣本,因此記憶窗口的空間開銷為O (k·Sm).實驗結果如表3～6 所示.

表3 7 種算法的P 值(%)Table 3 P value of seven algorithms (%)

表4 7 種算法的R 值(%)Table 4 R value of seven algorithms (%)

表5 7 種算法的 F1 值 (%)Table 5 F1 value of seven algorithms (%)

由表3 和表6 可知,ALM-ICDDS 算法在6 個合成數據流和3 個真實數據流上的P值和Kappa系數均為最高,尤其在類別數較多的合成數據流DS7和真實數據流Kddcup99_10%上優勢更加明顯.在DS7數據流上P值和 K appa 系數比OALMIDS 算法分別高3.16%和3.48%,在Kddcup99_10%數據流上P值比OALM-IDS 算法高3.67%.僅在合成數據流DS5上,ALM-ICDDS 算法的P值和Kappa系數比ARFRE 略低,分別低0.13% 和0.05%,這是由于ARFRE 是監督學習算法,在算法執行過程中需要使用所有樣本的標簽信息.

表6 7 種算法的 K appa 值(%)Table 6 K appa value of seven algorithms (%)

由表4 和表5 可知,ALM-ICDDS 算法在所有數據流上的R和 F 1 值均優于其他的對比算法,同樣在類別數較多的兩個數據流(DS7、Kddcup99_10%)上優勢更加明顯.在DS7數據流上R和 F1 值比OALM-IDS 算法分別高2.84% 和3.02%,在Kddcup99_10%數據流上R和 F1 值分別比OALMIDS 算法高5.63%和5.12%.

通過對表3～6 的實驗結果分析可知,主動學習算法CALMID、OALM-IDS 和ALM-ICDDS 在10 個數據流上的分類性能均優于監督學習算法LB、BOLE 和ARFRE;主動學習算法ALM-ICDDS-E在7 個合成數據流上的分類性能優于監督學習算法LB 和BOLE,在3 個真實數據流上分類性能優于監督學習算法LB、BOLE 和ARFRE;ALMICDDS 算法在10 個數據流上的分類性能均優于其他3 種主動學習算法;所有算法在不包含概念漂移和異常點的數據流上,分類性能優于包含概念漂移和異常點的數據流;對于有無異常點和概念漂移的兩類數據流,所有算法在類平衡、類不平衡比率固定和類不平衡比率變化的數據流上的分類性能依次下降.

圖2 展示所有算法在10 個數據流上的接受者操作特征曲線ROC,ROC 曲線下面積能夠直觀地反映出分類性能的好壞.由圖2 可知,主動學習算法CALMID、OALM-IDS 和ALM-ICDDS 在7 個合成數據流和PokerHand 數據流上的ROC 曲線下面積優于監督學習算法LB、BOLE 和ARFRE;主動學習算法ALM-ICDDS-E 在7 個合成數據流上的ROC 曲線下面積優于監督學習算法LB 和BOLE,在3 個真實數據流上ROC 曲線下面積優于監督學習算法LB、BOLE 和ARFRE;ALMICDDS 算法除在PokerHand 數據流上優于ALMICDDS-E 算法但與CALMID 和OALM-IDS 算法的ROC 曲線下面積相同外,在其他數據流上均優于6 種對比算法;在類別數較多的合成數據流DS7和真實數據流Kddcup99_10%上ALM-ICDDS 算法優勢更明顯,在這兩個數據流上比ROC 曲線下面積第二大的算法分別高3%和4%.

圖3 展示所有算法在2 個較為復雜的數據流(DS6和Kddcup99_10%)上分類精確率隨樣本規模增加的變化曲線.可知ALM-ICDDS 算法在這2個數據流上的分類精確率均優于3 種主動學習算法(CALMID、OALM-IDS 和ALM-ICDDS-E),且明顯優于3 種監督學習算法(LB、BOLE 和ARFRE).ALM-ICDDS 算法在這2 個數據流上均可以用最少的標簽成本獲得最高的精確率,在DS6數據流上的標簽成本比OALM-IDS 算法低0.17%、比CALMID 算法低0.32%、比ALM-ICDDS-E 算法低0.43%,在Kddcup99_10%數據流上的標簽成本比OALM-IDS 算法低0.45%、比CALMID 算法低0.69%、比ALM-ICDDS-E 算法低0.75%.

圖3 7 種算法的精確率曲線Fig.3 Precision rate curves of seven algorithms

基于上述實驗結果可以得知,本文所提算法ALM-ICDDS 在各項評價指標上整體優于其他對比算法,這是由于ALM-ICDDS 算法在3 個方面進行改進.首先,定義基于多預測概率的樣本預測確定性度量,對難區分和少數類樣本查詢真實標簽;其次,提出基于記憶強度的樣本替換策略,使得代表當前數據分布的樣本能夠保留在記憶窗口中,提升新基分類器的分類性能;此外,定義基于分類精度的基分類器重要性評價及更新方法,用于發生概念漂移后集成分類器的更新.

4.3 消融實驗

為測試ALM-ICDDS 算法引入混合標簽查詢策略、樣本替換策略和集成分類器更新機制的有效性,在類不平衡比率可變、含有異常點和概念漂移的數據流DS6上進行5 種消融實驗.1)將ALMICDDS 的樣本預測確定性度量替換為只考慮兩個最大概率值的差值,得到ALM-ICDDS-rfs;2)將ALM-ICDDS 的樣本預測確定性度量替換為只考慮最大概率值,得到ALM-ICDDS-rf 算法;3)將ALM-ICDDS 的混合標簽查詢策略替換為隨機標簽查詢策略,得到ALM-ICDDS-r 算法;4)將ALMICDDS-r 中基于記憶強度的樣本替換策略改為基于先進先出的替換策略,得到ALM-ICDDS-rs 算法;5)將ALM-ICDDS-rs 的基分類器更新方法替換為只考慮分類精度,得到ALM-ICDDS-rse 算法.

通過對圖4 的實驗結果分析可知,只考慮兩個最大概率值差值的ALM-ICDDS-rfs 算法比ALMICDDS 的精確率有所下降;只考慮最大概率值的ALM-ICDDS-rf 算法精確率比ALM-ICDDS-rfs 更低;只考慮隨機標簽查詢策略的ALM-ICDDS-r 算法精確率比ALM-ICDDS 算法下降明顯;改為先進先出替換策略的ALM-ICDDS-rs 算法精確率繼續下降,且適應概念漂移速度變慢;基分類器更新方法只考慮分類精度的ALM-ICDDS-rse 算法精確率進一步下降,且適應概念漂移速度變得更慢,尤其適應突變概念漂移的速度下降明顯.綜上,本文在混合標簽查詢策略、樣本替換策略和集成分類器更新機制方面的改進能夠有效提升數據流分類的性能.

圖4 DS6 上消融實驗的結果Fig.4 Results of the ablation experiment on DS6

4.4 參數取值對ALM-ICDDS 算法分類性能的影響

樣本預測確定性度量中的參數β用于調節最大可能類的概率和最大可能類與其余類預測概率平均差值所起的作用,θ0為邊緣閾值矩陣元素初值,參數n為樣本預測確定性度量所使用的預測概率的數目,參數α用于調節類不平衡比率在邊緣閾值矩陣自適應調整中所起的作用,參數nd為邊緣閾值矩陣的維數.接下來測試參數β,θ0,n,α,nd對ALMICDDS 算法分類性能的影響.實驗使用含有異常點和概念漂移的4 個合成數據流和2 個真實數據流,采用P值、R值、F 1 值、K appa 系數4 個評價指標,所有實驗重復10 次,結果如圖5～9 所示.

圖5 參數 β 對算法的影響Fig.5 Effect of the parameter β on the algorithm

圖5 展示參數β對ALM-ICDDS 算法分類性能的影響,可知當β取0.8 時在6 個數據流上的P值、R值、F 1 值、K appa 系數都達到了最大值,表明在度量樣本預測確定性時,最大可能類的概率非常重要.當β大于0.8 時,算法分類性能下降,可知最大可能類與其余類預測概率平均差值的作用也至關重要.

圖6 展示邊緣閾值矩陣元素初值θ0對ALMICDDS 算法分類性能的影響,可知當θ0取0.75 時在6 個數據流上的P值、R值、F 1 值、K appa 系數都達到最大值.當θ0小于0.75 時,樣本被查詢標簽的可能性減小,會導致難區分和少數類樣本查詢不到真實標簽,從而使得ALM-ICDDS 算法的分類性能下降;當θ0大于0.75 時,樣本被查詢標簽的可能性增大,但由于標簽預算是一定的,同樣會導致難區分和少數類樣本查詢不到足夠的標簽,也會使得ALM-ICDDS 算法的分類性能下降.

圖6 參數 θ0 對算法的影響Fig.6 Effect of the parameter θ0 on the algorithm

圖7 展示參數n對ALM-ICDDS 算法分類性能的影響,可知在6 個數據流上隨著n的增大,P值、R值、F 1 值、K appa 系數增大到一定程度后保持基本穩定.在k=15 (數據流DS2,DS4,DS6)、k=50 (數據流DS7)、k=23 (數據流Kddcup99_10%)、k=10 (數據流PokerHand)時,當n分別增加到3,7,4,2 時,P值、R值、F 1 值、K appa 系數基本穩定.可以驗證上述n的取值與式(11)一致.

圖7 參數n 對算法的影響Fig.7 Effect of the parameter n on the algorithm

圖8 展示參數α對ALM-ICDDS 算法分類性能的影響,可知當α取0.1 時,算法在6 個數據流上的P值、R值、F 1 值、K appa 系數都達到最大值.

圖8 參數 α 對算法的影響Fig.8 Effect of the parameter α on the algorithm

圖9 展示參數nd對ALM-ICDDS 算法分類性能的影響,可知在類別數k>10 的5 個 數據流(DS2,DS4,DS6,DS7,Kddcup99_10%)上,當nd的取值由2 增加為3 時,P值、R值、F 1 值、Kappa系數明顯提升,當nd繼續增大時算法分類性能提升幅度較小.在類別數k=10 的數據流(PokerHand)上,當nd的取值由2 增加為9 時,P值、R值、F1值、K appa 系數提升幅度很小.考慮到邊緣閾值矩陣的空間開銷為 O (knd),因此實驗中在數據流的類別數k≤10 和k>10 兩種情況下,nd分別取2 和3.

圖9 參數 nd 對算法的影響Fig.9 Effect of the parameter nd on the algorithm

4.5 ALM-ICDDS 算法對不同類型概念漂移的處理

圖10 展示本文所提算法和5 個對比算法在4種不同類型概念漂移數據流上分類精確率隨樣本規模增加的變化曲線.可知ALM-ICDDS 算法在4 種不同類型概念漂移數據流上的分類精確率整體優于5 個對比算法.由于突變型和重復型的概念漂移寬度遠小于增量型和逐漸型的概念漂移寬度,由圖10可知,相比于增量型和逐漸型漂移,發生突變型和重復型概念漂移時,分類精確率下降更快,通過及時調整模型可以更快地適應概念漂移.此外,相比于增量型概念漂移,發生逐漸型概念漂移時,算法適應概念漂移的速度要慢,這是由于發生逐漸型概念漂移時,新數據分布在一段時間內逐漸取代舊數據分布,而舊數據分布的出現不利于概念漂移的檢測.

圖10 不同類型概念漂移數據流上的精確率曲線Fig.10 P curves on different types of concept drift data stream

5 結束語

本文研究概念漂移、標簽成本昂貴和多類不平衡數據流的主動學習方法,定義基于多預測概率的樣本預測確定性度量,使得標簽查詢策略適用于類別數較多的不平衡數據流;提出基于記憶強度的樣本替換策略,將難區分、少數類和代表當前數據分布的樣本保存在記憶窗口中;定義基于分類精度的基分類器重要性評價及更新方法,用于集成分類器更新.

為增強概念漂移數據流主動學習方法的適應性,在未來工作中,我們將關注以下問題.首先,已有的概念漂移檢測方法通常假定數據流中樣本的標簽都是已知的,而這在真實應用中是不現實的,需要研究無監督或半監督場景下的概念漂移檢測方法.其次,現有的大多數數據流學習模型通常假設樣本類別是固定的,只能泛化到訓練集中出現的類別,因此需要研究適用于類別增量出現的數據流學習模型.