利用集成OS-ELM的不平衡數據流分類與存儲方法

湯程皓，梅 穎，盧誠波

（1.浙江理工大學 計算機科學與技術學院，浙江 杭州 310018；2.麗水學院 數學與計算機學院，浙江 麗水 323000）

0 引言

在生產生活的許多領域，無時無刻都在產生具有實時、高速、海量等特點的數據流［1］，例如傳感器實時監測數據、網絡流量監測、交通監控等。其中，類分布不平衡的情況經常出現，例如網絡入侵檢測、垃圾郵件檢測。在網絡空間中，少數入侵事件隱藏在正常訪問請求中，具有高度隱蔽性［2］，在大量正常郵件中也混雜著少量垃圾郵件。

數據流類分布不均衡通常是指在數據流中，少數類樣本數量遠小于多數類樣本數量，多數類樣本的分布在數據流中占有絕對的統治地位。目前，數據流分類算法一般針對類分布基本均衡的數據流所設計，如果在類不平衡數據流上使用，得到的決策邊界會偏向于多數類，因此對少數類的分類準確率往往較差，存在非常嚴重的分類損失。在醫療診斷、信用卡欺詐交易監測等應用領域，正確識別少數類具有重要的現實意義。

然而，目前大多數針對不平衡數據流分類算法的研究都聚焦在提升分類性能［3-4］，較少關注數據流中歷史數據的存儲及查詢方法。為了更有效地利用有限的計算機性能資源，本文設計了一種基于集成欠采樣與在線序列超限學習機（Ensemble Undersampling and OS-ELM，EU-OSELM）方法，在提升分類性能的同時，可減少對計算機內存的占用。

1 相關研究

目前，在提升不平衡數據流分類性能方面，在數據層面可使用預處理技術處理原始數據，利用重采樣方法優化樣本空間，降低數據分布的不平衡程度，減輕模型在訓練中因偏態類分布對結果的干擾。重采樣方法可分為過采樣和欠采樣［5-6］。Chawla 等［7］提出的SMOTE 方法是其中最具有代表性的一種方法，使用線性插值在兩個少數類樣本間添加人工合成的樣本使類分布平衡，方法簡單且魯棒性強。在SMOTE 方法基礎上，Han 等［8］提出Borderline-SMOTE 方法，僅對分布在分類邊界的少數類樣本進行過采樣。樊東醒等［9］提出一種改進K 中心點算法的過采樣方法，首先選擇合適進行聚類采樣的區域，然后在聚類基礎上進行加權過采樣。He 等［10］提出ADASYN 算法可自適應地確定過采樣少數類時需要生成的樣本數量，多數類在進行簡單的欠采樣時也可降低數據分布的不平衡程度，但由于潛在特征損失，無法充分利用多數類特征，可能會導致模型學習不充分，影響預測準確率。Hou 等［11］提出一種欠采樣方法，在保留有效樣本信息的同時刪除噪聲。Ng等［12］先對多數類樣本進行聚類，然后選擇最具標識性的樣本計算敏感度，接下來選擇所需樣本。文獻［11、12］的算法均針對性地進行欠采樣，可使采樣結果盡量保留樣本的關鍵特征信息。于艷麗等［13］提出一種基于K-means 聚類的欠采樣方法，根據多數類樣本和簇心距離選擇所需樣本。

在算法層面，可改進、集成分類算法，使算法更符合在不平衡數據流上分類的要求，以提升分類精度。一般通過集成學習提升算法分類性能。Wang 等［14］結合過采樣、欠采樣和SMOTE 的重采樣方法，提出適用于多分類情況下的SMOTEBagging 集成學習方法。TAO 等［15］提出一種基于自適應代價權重的支持向量機代價敏感集成算法。Chen等［16-18］提出REA、SERA 和MuSeRA 一系列針對不平衡數據流的學習算法。REA 利用KNN 算法從保存的少數類樣本中選擇一部分樣本與當前數據塊合并訓練基分類器；SERA 利用少數類樣本間的相似程度選擇樣本，以平衡訓練數據集；MuSeRA 在SERA 基礎上引入權重機制訓練集成分類器。以上算法的共同特點均需保存全部歷史數據中的少數類樣本。

然而，以上類處理方法均存在共同缺陷，即不符合數據流單通道特征，正常情況下只有當數據第一次到達時才能對其進行處理。同時，REA、SERA 和MuSeRA 算法在訓練過程中需不斷保存歷史少數類樣本，隨著數據不斷到達，將耗盡內存空間［19］，在某些需要低成本部署的應用場景下，該問題將尤為嚴重。

2 通用框架集成算法與OS-ELM

2.1 通用框架集成算法

算法由采樣和集成（Sampling and Ensemble，SE）兩部分組成［20］。數據以塊形式到達，每接收到一個數據塊S，將數據分成少數類集合P和多數類集合Q。然后，將少數類樣本全部保存為一個數據集，隨著數據塊不斷到達，可將少數類的集合表示成AP={P1，P2，...，Pm-1}。接下來，將最新到達的數據塊Sm分成Pm、Qm，Pm加入到少數類集合中，集合更新為{P1，P2，...，Pm}，集合中樣本數為np，在多數類上進行隨機欠采樣得到Qm的一個子集O，使用分布率r、np控制采樣，得到的多數類樣本數量為nq=np/r。最后，獲得用于訓練基分類器的數據集{O，AP}。

根據設定基分類器的數量k、nq，在多數類Qm上進行k次隨機不放回欠采樣。因此，每個基分類器所用數據集中的多數類樣本完全不相交。根據所生成的k個數據集，訓練k個基分類器C1，C2，...，Ck，得到一個集成分類器。

2.2 OS-ELM

超限學習機（Extreme Learning Machine，ELM）［21］是一種基于單隱層前饋神經網絡的學習算法，結合最小二乘法計算輸出權重，隨機設置輸入權重和偏置，且后續無需迭代調整。ELM 能進一步被描述為一個線性參數模型，輸出權重具有最小訓練誤差，相較于傳統神經網絡算法無需使用梯度下降法更新輸入權重也能取得全局最優解，因此具備更高的訓練效率與較好的泛化性能。

為解決ELM 無法適用于數據流分類的問題，Liang等［22］基于ELM 的在線學習算法提出在線序列超限學習機（Online Sequential Extreme Learning Machine，OS-ELM），無需保存歷史數據，由初始化階段和序列學習階段組成。

2.2.1 初始化階段

從到達的第k個數據塊中選擇樣本x，設k=0，即最先到達的數據塊。隨機分配輸入權重ai、偏置bi，給定激活函數G(x)，計算初始輸出權重β(0)。

式中：T0為初始階段所選擇樣本對應的目標矩陣；H0為初始階段隱層輸出矩陣。

式中：n為樣本數量；N為隱藏層節點；P0為：

2.2.2 序列學習階段

在序列學習階段，接收到第k+1 塊數據，計算隱層輸出矩陣Hk+1。然后在線更新輸出權重β(k+1)、Pk+1。

式中：Tk+1為新到達樣本的標簽；Pk+1為：

式中：I為單位陣。

利用β可得預測的標簽T。

由于Chen 等［16-20］的集成算法需全部保存處理數據流中少數類樣本，隨著數據不斷到達，要為歷史少數類樣本數據開辟額外的內存空間，內存空間大小由數據量和數據維度兩方面決定。因此，在實際訓練過程中存在以下問題：①由于數據流具有高速、海量等特點，隨著時間推移，所需空間大小可能很快就會抵達計算機內存上限；②在到達上限后是否丟棄歷史數據或進行欠采樣，之后如何彌補潛在的少數類特征的損失也是需要考慮的問題；③由于數據流具有實時性特點，對算法的實時處理和分析能力提出了一定要求，如果將歷史數據存放在外部存儲介質中，將增加額外的I/O 操作，因此也不適合使用數據庫管理系統保存數據；④龐大的數據量也會增加模型訓練時間，導致模型在新到達的數據上變得過時的問題。

3 EU-OS-ELM 算法的分類與存儲

3.1 基本思想

本文集成欠采樣和OS-ELM 算法，提出一種面向不平衡數據流的分類、存儲與查詢歷史數據方法。EU-OSELM 算法利用ELM 網絡中固定大小的外權矩陣來存儲歷史數據的特征信息。必要時，通過查詢歷史數據的特征信息代替對歷史數據的查詢。由于EU-OS-ELM 算法僅保存歷史數據在特征空間的信息，因此可解決因不斷保存歷史數據而導致耗盡內存空間的問題。該算法使用集成方法來提升分類性能，在構建基分類器的訓練樣本時，使用不放回隨機欠采樣來進一步提升算法的魯棒性，降低因特征損失導致欠擬合對模型的影響。

EU-OS-ELM 算法的目的是在提升不平衡數據流的分類準確率基礎上，解決傳統方法因保存歷史數據而導致內存空間無限增長，占據大量存儲空間的問題。算法流程如圖1所示，歷史少數類特征信息的存儲方式如圖2所示。

Fig.1 Algorithm flow圖1 算法流程

Fig.2 Storage of historical sample feature information圖2 歷史樣本特征信息存儲

3.2 算法描述

在初始化階段，設隱藏層節點數為N，為每一個隱藏層節點隨機分配輸入權重ai、偏置bi，i=1，2，3，…，N。首先選取n0個少數類樣本進行初始化，在第k個數據塊上確定所需樣本后，使用激活函數計算隱藏層輸出矩陣，接下來根據式（1）、式（2）計算輸出權重，此處中保存的信息為少數類樣本的特征信息。

在集成在線學習階段，使用后續到達的數據塊中的少數類來更新輸出權重矩陣及訓練集成分類器。由于存在概念漂移現象，最近到達的數據塊Sm一般代表數據流中數據的最新分布情況，在最近到達的數據塊上訓練分類器有利于減少期望誤差。無論數據流發生何種形式概念漂移，在最近數據上更新模型總有利于后續預測結果［20］。在數據塊Sk+1，Sk+2，…，Sm-1中，Sk+i為初始化完成之后到達的數據塊，根據式（3）、式（4）保存并更新少數類F的特征信息，同時記錄已經到達的少數類的總數nA。

在特征空間中，通過組合低層特征可形成更抽象的高層特征，本文通過固定大小的矩陣存儲歷史數據的特征信息，在接收到新的樣本時通過式（3）、式（4）將當前少數類樣本的特征信息補充到中，實現對少數類樣本特征信息的存儲。特征信息矩陣更新方式如下：

當需要歷史數據時，查詢該數據在特征空間中的信息以代替原始數據完成任務，即使用保存的輸出權重矩陣，結合當前數據塊來訓練分類器。在最新數據塊Sm上，將數據分為多數類Q、少數類F，引入不平衡率r=|F|/|Q|為數據塊少數類樣本數量與多數類樣本數量的比率。

在多數類上進行不放回隨機欠采樣，得到多數類樣本集合Oi，Oi集合樣本數為nq=nA/r，可根據需要進行多次采樣，將每次采樣的結果和少數類F合并，得到一系列訓練樣本集合Train={{O0，F}，{O1，F}，…，{Od，F}}。將式（3）、式（4）改寫為式（8）、式（9），查詢并利用保存的歷史少數類樣本的特征信息訓練基分類器。

式中：Hi為Traini的隱藏層輸出矩陣；Ti為Traini的標簽矩陣。

本文根據式（8）、式（9）結合歷史數據特征信息訓練得到一個基分類器βi，由此得到一個集成分類器E={β0，β1，…，βd}。首先在測試數據塊Spre上根據激活函數得到Hpre，然后根據式（5）得到每一個基分類器的預測標簽，最后根據各基分類的分類結果進行投票得到最終預測結果。

算法1：EU-OS-ELM 算法

3.3 內存空間分析

EU-OS-ELM 算法在集成在線學習階段需占用額外內存空間，具體指為了保存歷史少數類的特征信息所需空間。在數據塊Si上，少數類樣本的隱藏層輸出矩陣H+i的維度為(n×N)，n、N分別為樣本數和隱藏層節點個數，Pi為一個維度為(N×N)的矩陣，Ti為樣本的標簽，維度為(n×t)，t為樣本長度。由此可知，保存少數類樣本特征信息的β+為固定大小的N×t矩陣，一旦算法初始化后，β+所需要的內存空間就不會再發生任何改變。

EU-OS-ELM 算法在訓練每個基分類器時，除了需要少數類樣本外，還需當前數據塊中的部分多數類樣本。如果簡單地對多數類樣本進行欠采樣會重復使用某一些樣本，導致基分類器間相似度過高，從而降低集成分類器的泛化性能。因此，算法1 中的步驟7 對當前數據塊中的多數類樣本，使用了不放回隨機欠采樣方法，每一次采樣得到的多數類樣本沒有重復項，能讓大量不同的多數類樣本參與學習，確保各基分類器訓練樣本的多樣性，降低因欠采樣導致特征損失對分類性能產生影響。此外，不放回隨機欠采樣使各基分類器間保持一定的差異性，既降低了算法方差，又提升了分類和泛化性能。

4 實驗結果與分析

4.1 實驗環境與評價指標

本文實驗在macOS 12.2 系統、Core i5 處理器、16 GB 內存的機器上運行，算法實現編程語言為Python 3.7.7。在不平衡數據流問題中，使用總體正確率無法準確反映模型對少數類樣本的分類性能，因此實驗使用ROC 曲線、P-R 曲線、AUC 及G-mean 評價算法的性能。其中，ROC 為一個橫軸為假正率（FPR），縱軸為真正率（TPR）的二維曲線圖；AUC 為ROC 曲線下面積，是評價分類算法處理不平衡數據流問題的常用指標；P-R 曲線橫軸為查全率（Recall），縱軸為查準率（Precision）；G-mean 為多數類準確率與少數類準確率的綜合指標。

不平衡率r的取值范圍為［0.3，0.6］，集成中基分類器個數設置為6，激活函數G(x)選擇Sigmoid 函數。

4.2 數據集

本文選擇8 個人工數據集和1 個真實數據集。其中，SEA、SIN 和STAGG 數據集考慮了帶有不同類型概念漂移的情況；Spiral為一個螺旋數據集，包含4條螺旋臂，將其中一條螺旋臂的數據視為少數類，剩余數據為多數類；Covtype 來自UCI 的真實世界數據集，將其中數量最少的一個類視為少數類。具體數據如表1所示。

Table 1 Details of datasets表1 數據集細節

4.3 結果分析

將REA［16］、SERA［17］、MuSeRA［18］、SE［20］算法作為對照算法與EU-OS-ELM 算法從分類性能和歷史少數類內存使用方面進行比較。集成算法SE 分別選擇Decision Tree（DT）、Naive Bayes（NB）、Neural Network（NN）和LogisticRegression（LR）作為基分類器，在實驗中分別標注為EDT、ENB、ENN、ELR。由表2 可知，EU-OS-ELM 算法在處理類不平衡數據流時能得到較為優異的分類性能。在hypercube、covtype 數據集上，EU-OS-ELM算法的AUC 達 到0.99；Naive Bayes（NB）作為基分類器的集成算法［20］，在covtype 數據集之外的數據集上性能較差，原因是數據集的樣本分布邊界較為復雜，會影響先驗概率與條件概率的計算。

Table 2 AUC and G-mean values of each algorithm in different data sets表2 各算法在不同數據集中的AUC和G-mean值

在處理類不平衡數據流時，對于少數類樣本的存儲問題，EU-OS-ELM 算法通過保存樣本在特征空間的信息的方式，避免直接存儲實際樣本。由表2 與內存使用量的分析可知，EU-OS-ELM 算法在處理類不平衡數據流的整個過程中，僅需非常少的內存空間，即可達到甚至優于一些傳統算法的分類精度。

圖3、圖4 為EU-OS-ELM 算法在Spiral 數據集上的ROC 曲線和P-R 曲線。由此可見，EU-OS-ELM 算法對應的P-R 曲線僅次于在通用框架集成算法SE 中選擇決策樹作為基分類器時的性能，ROC 曲線基本位于左上角，表2中相應的ROC 曲線下方面積AUC 值為0.912 3，可得出EU-OS-ELM 算法在該數據集的分類性能優秀。

Fig.3 ROC curve on Spiral圖3 Spiral上的ROC曲線

Fig.4 P-R curve on Spiral圖4 Spiral上的P-R曲線

圖5 展示了選擇不同基分類器的集成算法SE、REA、SERA、MuSeRA，在不同數據集上與EU-OS-ELM 算法的額外內存使用比較情況。由于SE、REA、SERA、MuSeRA 算法需要保存每個數據塊中原始的少數類樣本來處理不平衡問題，所使用的內存空間數量為nA(Features+1)，Features為樣本特征數量。隨著數據不斷到達，保存歷史少數類樣本所需的額外空間不斷增加，將很快消耗完計算機的內存空間。然而，EU-OS-ELM 算法由于使用固定大小的外權矩陣存儲歷史數據的特征信息，在整個學習過程中所使用的額外內存恒定為一個低值，所需內存空間數量為Nt，在不平衡數據流環境中nA?N，與歷史少數類樣本的數量規模和維度無關。因此，EU-OS-ELM 算法在提升分類準確率的同時，所使用的內存最少，當數據量越多時，在內存方面的優勢越明顯。

Fig.5 Memory space for storing historical minority samples on each data set圖5 各數據集上存儲歷史少數類樣本的內存空間

EU-OS-ELM 用于保存特征信息的外權矩陣在算法開始階段完成初始化，因此在圖5 中的每一個子圖的開始部分會出現EU-OS-ELM 算法所需的額外內存空間大于比較算法的情況，外權矩陣的內存使用量小于1 KB，并且在非常短的時間內就會被SE、REA、SERA、MuSeRA 算法所需的內存空間反超。因此，這一現象從處理不平衡數據流的整體過程而言對實驗結論沒有造成影響。

圖5 中折線呈階梯狀分布的原因為：①只需要保存少數類樣本，當數據到達后如果掃描到多數類樣本則跳過；②Python 的內存分配機制所導致，當預留的動態內存空間消耗完后會向系統請求一個新的、更大的內存空間，然后將數據拷貝到新的空間中，并釋放舊的內存空間，這一操作包含創建內存空間、移動數據和銷毀原始內存空間3 個步驟，在實際應用中存在額外的時間、空間及操作系統開銷，但EU-OS-ELM 算法在整個處理過程中只使用一個較小且恒定的內存空間，不存在額外開銷。為了確保實驗的客觀性，實驗中逐塊處理數據流，在不同算法中保證生成的數據流中數據塊的到達次序、同數據塊中的少數類樣本數量均一致，因此存儲這些少數類樣本所需的內存空間數量也一致，即不同傳統算法在處理完同一數據塊后，所需內存空間相同，解釋了圖5 傳統算法在間隔一定數量樣本后所需內存空間趨于一致的現象。

考慮到不同數據流樣本分布情況，EU-OS-ELM 所需隱藏層節點數不同。在二分類問題中，輸出權重β+的內存空間受隱藏層節點數的影響，如圖6 所示。由此可見，隨著隱藏層節點數N增加，輸出權重矩陣β+所需要的內存空間基本上呈現一個線性增長趨勢，完全處于可預估和控制的狀態。

Fig.6 Memory space occupied by different hidden layer nodes圖6 不同隱藏層節點數占用的內存空間

5 結語

本文基于OS-ELM 算法提出一種EU-OS-ELM 的不平衡數據流分類與存儲方法。采用集成方式，在利用OSELM 訓練基分類器時，使用不放回隨機欠采樣方法降低樣本間的相關性，使訓練得到的分類模型在對不平衡數據流進行分類時，具有更好的分類性能。

同時，為解決傳統方法因不斷保存歷史少數類樣本而導致的存儲問題，本文利用一個固定大小的外權矩陣β+保存少數類樣本特征信息，在需要使用歷史數據的信息時，只需查詢歷史數據的特征信息，因此大幅度減少了內存空間的使用。此外，在實際應用中也可用相似的方法存儲多數類樣本的特征信息。