有新類的動態數據流分類算法研究

武煒杰，張景祥

江南大學理學院，江蘇無錫214122

隨著科學技術的不斷發展，數據流挖掘在許多領域上被廣泛應用，如控制系統[1]、時間預測[2]、異常檢測[3]等。數據流分類問題是數據挖掘任務中的重要研究內容，特別是靜態數據向動態數據轉變過程中新類檢測、多類標檢測、數據漂移檢測等都給數據挖掘帶來了挑戰[4]。

現實環境的改變使得數據分布變化，或新類出現，這就導致用先前數據訓練好的分類器不能準確地識別出數據流中新類樣本。

學者們認為數據流中新類檢測問題是增量學習方式，并提出很多研究方法。Zhang 等人[5]提出類別增量學習（class-incremental learning，C-IL）算法，通過更新分類器來處理新類出現的情況。Da 等人[6]提出基于利用未標記數據學習新類（learning with augmented class with unlabeled data，LACU）框架的LACUSVM 半監督學習算法，利用可便捷收集的大量未標記數據學習新類。現有的類別增量學習算法（如ECSMine（enhanced classifier for data streams with novel class miner）[7]、CLAM（class based micro classifier ensemble）[8]、SCDMiner（adaptive semi-supervised concept drift miner with novel class detection and delayed labeling）[9]等）大多基于聚類的方法來檢測新類，但由于聚類屬于無監督學習方法，算法的新類檢測性能與分類精確度并不理想。

Hawkins 揭示了異常點的本質[10]。將新類樣本看成與已知類樣本產生于不同機制的異常點樣本。基于隨機森林（random forest，RF）模型檢測異常點，學者們提出了許多有效方法。如張鈺等人[11]將隨機森林應用在滾動軸承故障診斷中，許歐陽等人[12]針對無線傳感器網絡異常數據檢測問題，使用變異二進制螢火蟲算法（mutation binary glowworm swarm optimization，MBGSO）優化RF 模型并提出MBGSO-ARF 異常點檢測算法，還有趙清華等人[13]將隨機森林應用在不平衡數據集上進行分類研究。周志華等人[14]提出的iForest（isolation forest）異常點檢測算法由于具有線性時間復雜度與高精準度，在工業上應用極為廣泛。Mu 等人[15]針對數據流新類分類問題，基于iForest隔離異常點的思想構造檢測器，提出基于完全隨機樹的無監督學習算法SENCForest（classification under streaming emerging new class），SENCForest 算法需要少量新類樣本信息更新，但在數據流檢測新類性能上有待提高。

針對動態數據流檢測新類性能低的問題，本文基于SENCForest 算法，將k近鄰策略融合到完全隨機森林的決策中，提出基于k近鄰完全隨機森林算法（completely randomized forest algorithm based onk-nearest neighbor，KCRForest）。該算法是在全局角度下，根據葉節點平均路徑長度將樣本空間分成正常區域與異常區域，并進一步在局部角度下引入樣本離群值檢測異常區域中的新類樣本。KCRForest 算法應用在不同時期內新類樣本數量變化的動態數據流中，利用新類樣本信息更新已構建的完全隨機樹中的節點信息，實現模型更新，以便實時檢測更多的新類。將k近鄰策略融合到完全隨機森林的決策中有助于提高KCRForest 算法在異常區域內檢測新類的準確率，并且算法在完全隨機樹劃分的樣本空間中尋找樣本k近鄰，而不是在整個樣本空間中搜索，避免了大量計算，降低系統開銷。

1 相關工作

數據流新類分類問題的目標是訓練已知類樣本構建分類器，當數據流通過分類器得到已知類樣本的樣本標簽并檢測出新類樣本。當新類樣本達到一定數目，分類器進行更新，并用來檢測更多的新類。動態數據流的新類分類問題的目標與上述一致，改變的是涌入分類器的數據流呈現動態變化，新類樣本數量占所有樣本的比例改變，每次模型更新所需樣本信息量不同。

KCRForest 算法的提出解決動態數據流新類分類問題。為了更加清楚地介紹KCRForest 算法，將引進相關的完全隨機森林（completely randomized forest，CRForest）算法，并給出決策樹劃分后樣本空間內樣本的k近鄰的定義。

1.1 完全隨機森林

完全隨機森林是以若干個完全隨機樹[15]基于Bagging 構建的一個組合分類器。其中的完全隨機樹是周志華所提出的iTree[14]（isolation tree）的變形。它完全沿用了iTree 的構建方法，在決策樹分割時特征選擇完全隨機。由完全隨機樹為基分類器所得到的完全隨機森林算法，相較于經典的隨機森林算法的優點在于，構建決策樹時不需繁復的計算，具有線性時間復雜度，在保持決策樹良好的分類能力的同時，還能檢測新類樣本。

算法1CRForest

1.2 基于樣本空間內樣本的k 近鄰

決策樹的分割將根節點處的樣本劃分到內部節點（或葉節點）中，相當于在樣本空間內劃分成若干個樣本子空間。本文給出由決策樹劃分后，樣本空間內樣本的k近鄰的定義。

樣本集D的樣本空間為Ω，決策樹第一次分割將樣本空間Ω劃分為Ω1和Ω2，決策樹第二次分割將樣本子空間Ω1劃分為Ω11和Ω12。決策樹劃分示意圖如圖1 所示。

Fig.1 Decision tree division diagram圖1 決策樹劃分示意圖

樣本空間Ω11內樣本x的k近鄰：對k∈N?，在樣本空間Ω1中存在樣本z，它與樣本x之間的距離記作d(x,z)。若在Ω1中至少有不包括x在內的k個樣本p∈Ω1{x}，滿足d(x,p)≤d(x,z)。則記這樣的k個樣本為樣本空間Ω11內樣本x的k近鄰，記作Nk(x)，如圖2所示。

Fig.2 k(k=5)-nearest neighbor of sample x in sample space Ω11圖2 樣本空間Ω11 內樣本x 的k（k=5）近鄰

2 KCRForest算法

2.1 KCRForest算法原理

SENCForest 算法[15]使用已知類樣本訓練SENCTree，根據iForest[14]算法提出的異常樣本往往落在平均路徑長度較短的葉節點內，將樣本空間劃分為正常區域與異常區域。其中已知類樣本通常分布在正常區域內，而已知類異常樣本與新類樣本通常分布在異常區域內。其中已知類異常樣本分布在正常區域的邊緣，新類樣本的分布距離正常區域更遠。SENCForest 算法根據不同類型樣本的分布特點，根據劃分的區域區別正常樣本與異常樣本。在異常區域內，以其中樣本的中心為球心，樣本中心到與之最遠的樣本的距離為半徑畫球。在測試過程中，落在此異常區域內球半徑外的樣本標記為新類。

SENCForest 算法雖然計算量小，但具體在SENCTree構建完成時，可能會出現異常區域（平均路徑長度較短的葉節點）內樣本數量較少（≤5）的情況。樣本信息量不足，導致畫球檢測已知類異常樣本與新類樣本的結果不可信。本文提出的KCRForest算法使用異常區域內樣本的k近鄰計算樣本離群值（樣本為離群點的程度），替代畫球法檢測已知類異常樣本與新類樣本，保證了樣本信息量充足與判斷的可信度。

2.2 樣本離群值

樣本離群值表示樣本為離群點的程度。根據不同樣本的分布特點，可知新類樣本的離群程度普遍大于已知類異常樣本的離群程度，即絕大部分新類樣本的離群值明顯大于已知類異常樣本的離群值。因此本文中樣本離群值表示樣本的標簽為新類的可能性，樣本離群值越大，樣本為新類的可能性越大。其中樣本離群值的計算與LOF[16]（local outlier factor）中一致。

圖2 中樣本空間Ω11內樣本x的k近鄰為Nk(x)，將樣本p到樣本x的可達距離記為：

其中，k-distance(x)表示樣本x的k近鄰中的樣本與樣本x的最遠距離。

樣本x的局部可達密度為：

2.3 KCRForest模型

2.3.1 KCRForest訓練模型

KCRForest 算法是基于k近鄰完全隨機森林算法，使用已知類樣本訓練初始分類器。

算法2KCRForest算法訓練階段

算法2 中的終止條件為葉節點內的樣本數小于或等于Minsize，或者KCRTree 達到限定高度high。葉節點的平均路徑長度與KCRTree 的閾值π計算分別與iForest算法和SENCForest算法一致。

2.3.2 KCRForest測試模型

記模型從訓練、測試到更新為一個時期，假設在一個時期內測試數據流中只有一種新類。若測試數據流在一個時期內有多種新類，其新類樣本標簽均記為Newclass。

算法3KCRForest算法測試階段

KCRForest 算法引入閾值τ界定樣本的離群程度是否能將樣本判為新類。閾值τ需要區別異常區域內的已知類異常樣本與新類樣本，其中多數新類樣本的離群值遠遠大于已知類異常樣本的離群值，根據這一特點設計閾值τ的計算方式。

學習者在沒有全面掌握目的語的規則的情況下通常會依賴母語，把母語的思維方式和使用方法套用到對目的語的學習中去，從而引起學習者母語的負遷移，這種母語知識的干擾常常見于目的語的初學者中，是引起第二語言初期學習過程中產生偏誤的主要原因之一。比如在英語中可以用“not much”、“not many”即“不多”來表示“少”，漢語中則不可以。

設X為測試數據流，其中在異常區域內的樣本集合記為D′。每個樣本x∈D′通過KCRTreei{i=1,2,…,N}得到離群值。記：

則閾值τ記為：

2.3.3 KCRForest更新與集成模型

在動態數據流中，每一時期的新類樣本占測試數據流的比例不同。KCRForest 算法需要對已知類樣本進行分類，檢測出這一時期內新類樣本，并且在下個時期中模型能識別出已出現過的類，檢測更多的新類，這需要對KCRForest模型進行更新與集成。

KCRForest 模型利用一時期內檢測的新類的樣本信息進行更新。將KCRForest 模型檢測的新類樣本存放在緩沖區Β內，當Β到達一定數目時，模型進行更新：

（1）緩沖區Β內的新類樣本落入KCRForest 中的每棵KCRTree 的節點，更新節點內樣本標簽分布與節點平均路徑長度。

（2）利用節點內樣本的中心生成與節點內記錄的原樣本數目等數量的偽樣本，再進行節點分支。

（3）更新KCRForest中的閾值π。

由于在不同的時期中，新類樣本占測試數據流的比例不同。緩沖區Β設置的大小不能為靜態的，應隨著新類樣本占測試數據流的比例而變化。本文KCRForest模型更新條件設為：

其中，?表示一時期內新類樣本占測試數據流X的比例。

KCRForest 模型可將這個時期的新類更新為下一時期的已知類。KCRForest 是一種半監督形式算法，將檢測的新類樣本用來更新模型，因此模型的有效性會隨模型更新逐漸下降。但要在多個時期進行檢測，保證模型有效性，本文設定KCRForest 模型只更新一次并對KCRForest模型集成。KCRForest模型更新完成后檢測到下個時期的新類樣本并存入緩沖區Β，檢測完畢后使用緩沖區Β內的新類樣本重新訓練一個新的KCRForest 模型，然后進行更新。如此重復，得到G個KCRForest 集成的模型。樣本x經過模型{KCRForestj|j=1,2,…,G}，可得G個樣本標簽{yj|j=1,2,…,G}，投票選擇最終標簽為：

KCRForest 模型的有效性對分類效果具有很大影響。考慮到算法內存限制和運行速度，并得到更好的分類效果，本文在集成KCRForest 模型中設立廢除機制。廢除集成KCRForest 模型中不常用的KCRForest，設置集成KCRForest 模型最大數目與SENCForest 算法一致：G=3。若已達到最大集成數目，則訓練新的KCRForest 模型替代現階段在動態數據流中使用最少的KCRForest模型。

3 實驗與結果分析

3.1 實驗數據與評價性能指標

本文實驗均使用Matlab 實現算法編碼，選用UCI中的4 個真實集對算法進行仿真測試。實驗所使用的數據集的相關信息如表1 所示。

Table 1 UCI dataset used in experiment表1 實驗中使用的UCI數據集

KCRForest 算法是在基于隔離異常點思想的SENCForest算法框架上改進，在完全隨機森林的決策中融入樣本的k近鄰策略，基于樣本的k近鄰計算樣本離群值。本文選擇3 種方法SENCForest[15]、iForest[14]+SVM、LOF[16]+SVM 與KCRForest 算法進行性能對比。其中iForest 算法與LOF 算法為異常點檢測算法，將其與SVM 算法組合后對測試樣本進行新類檢測與分類。SVM 的程序調用libsvm[17]工具箱，核函數為高斯徑向基函數，類型為C-SVC。SENCForest 程序來源于機器學習與數據挖掘研究所提供的代碼[15]。實驗中算法的參數如表2 所示，其中算法參數表示的含義與本文第2 章KCRForest 算法表示一致（N為樹的數量；Di為訓練子樣本集；Minsize為葉節點最小樣本數）。

Table 2 Parameter setting of algorithms used in experiment表2 實驗中使用的算法參數設置

本文實驗采用分類準確率（Accuracy）、新類召回率（newclass recall，NR）、新類精度（newclass precision，NP）和F-measure[18]作為評價指標。

分類準確率是所有通過分類器的樣本中識別類別為正確類別的樣本所占比例，其中S為通過分類器的所有樣本中準確識別類別的樣本數（包括準確識別已知類樣本與新類樣本）。W為所有通過分類器的樣本數。

NR表示分類器正確識別的新類樣本數占測試樣本集中新類樣本數的比例。NP表示分類器正確識別的新類樣本數占分類器檢測出的新類樣本數的比例。

F-measure 是評價新類檢測性能的綜合評價指標，它是NR和NP的調和平均，采用以下定義：

3.2 實驗測試

本節仿真實驗分別在一個時期的短數據流和多個時期的長數據流上進行。約定在一個時期內，測試數據流僅包含一個新類，兩個已知類。實驗前，分別在4 個數據集（Seeds、Wine、KddCup99 和Minst）上計算閾值τ，閾值τ的取值在1 的上下浮動，為方便計算，本文實驗中設定閾值τ=1。

3.2.1 短數據流測試

對所用的4 個數據集進行預處理，消除數據集中的冗余數據和冗余特征。一個數據集隨機選擇兩個類作為已知類，其余類為新類。進行10 次實驗，每次實驗的訓練樣本與測試樣本在數據集中隨機選取，測試樣本中已知類樣本與新類樣本比例設為2∶1。取10 次結果平均值作為衡量KCRForest 算法的性能指標。4個數據集上不同方法的新類檢測性能見表3～表6，分類精度見圖3。

本文實驗分別從KCRForest 算法新類檢測性能（表3～表6）與分類準確率（圖3）兩方面進行評估。在Seeds 數據集上，KCRForest 算法新類檢測性能稍遜于LOF+SVM 算法，與iForest+SVM 接近，明顯優于SENCForest算法。根據圖3（a）可看出，KCRForest算法的分類準確率高于其他3 種對比算法。在Wine 數據集上，KCRForest 算法犧牲了部分新類精度，但在新類檢測性能上比其他3 種算法優越。考慮分類準確率，根據圖3（b）可看出KCRForest算法的分類曲線剛開始低于iForest+SVM 算法與LOF+SVM 算法，但在最后分類準確率接近并高于iForest+SVM 算法與LOF+SVM 算法，并且明顯優于SENCForest算法。

Table 3 New-class detection measure of different algorithms on Seeds dataset表3 不同算法在Seeds數據集上的新類檢測性能

Table 4 New-class detection measure of different algorithms on Wine dataset表4 不同算法在Wine數據集上的新類檢測性能

Table 5 New-class detection measure of different algorithms on KddCup99 dataset表5 不同算法在KddCup99數據集上的新類檢測性能

在KddCup99 數據集上，KCRForest 算法與SENCForest 算法均具有高新類召回率，但KCRForest算法的新類精度上高于SENCForest 算法，因此KCRForest 算法在新類檢測性能上略優于SENCForest 算法，明顯優于iForest+SVM 算法與LOF+SVM 算法。考慮分類準確率，根據圖3（c）可看出，KCRForest 算法分類曲線穩定提升，雖在開始階段低于iForest+SVM 算法，但隨樣本數的增加超過了iForest+SVM算法達到最高。在Minst 數據集上，KCRForest 算法雖在新類召回率與新類精度上略遜于其他算法，但在新類檢測性能上與最高的SENCForest 算法接近，并明顯優于其他算法。考慮分類準確率，根據圖3（d）可看出，KCRForest 算法雖在開始低于iForest+SVM 算法與LOF+SVM 算法，但分類曲線一直保持提升狀態，最后結果接近分類準確率最高的LOF+SVM 算法。

從上述結果看，KCRForest 算法在4 個數據集上保持著較高的新類檢測性能與分類準確率，并且新類檢測性能優于或與iForest+SVM 算法和LOF+SVM算法相當，分類準確率明顯高于SENCForest 算法。

Table 6 New-class detection measure of different algorithms on Minst dataset表6 不同算法在Minst數據集上的新類檢測性能

Fig.3 Classification accuracy of different algorithms on 4 datasets圖3 不同算法分別在4 個數據集上的分類精度

3.2.2 長數據流測試

由于KCRForest 算法與SENCForest 算法便于模型更新，在長數據流上對KCRForest 算法進行仿真實驗時，對比算法選擇SENCForest 算法。實驗選取KddCup99 與Minst 兩個數據集，消除數據集中的冗余數據與冗余特征。在KddCup99 數據集上，隨機選取6 個類別分別作為每個時期檢測的新類，每個時期通過分類器1 200 個樣本；在Minst 數據集上，隨機選取5 個類別分別作為每個時期檢測的新類，每個時期通過分類器1 500 個樣本。在上述兩個數據集中，每個時期內新類樣本與已知類樣本比例是動態變化的。

在KddCup99 數據集上，實驗結果如圖4（a）所示，KCRForest 算法在初始階段分類準確率略低于SENCForest 算法，但接近第2 000 個樣本時，分類曲線超過了SENCForest 算法并一直保持。在Minst 數據集上，實驗結果如圖4（b），KCRForest 算法的精度曲線一直高于SENCForest 算法。但通過觀察兩個實驗結果可得，隨著時期的增加，模型的分類準確率在不斷下降。這是由于在使用緩沖區內新類的樣本信息更新分類器過程中，使用的新類樣本中有一部分是被檢測為新類的已知類樣本。

3.3 參數k 值討論

Fig.4 Classification accuracy of different algorithms on long data stream圖4 不同算法在長數據流上的分類精度

KCRForest算法引入了參數k，本文需要對k值進行討論。在完全隨機樹劃分的樣本空間中取落入該區域內樣本的k近鄰。由本文設置的Minsize=10，限制k的取值范圍在[1,11]。圖5、圖6 的仿真實驗分析了k取值分別對KCRForest 算法的Accuracy與Fmeasure 的影響。觀察圖5、圖6 可知，k取值對Accuracy與F-measure 的影響并不明顯，當k≥8，在3個數據集Wine、KddCup99 和Minst 上，KCRForest 算法的Accuracy與F-measure 波動幅度減小。在Seeds數據集上，算法的Accuracy與F-measure 顯著提高。本文考慮KCRForest 算法的綜合性能，將算法的預設參數k定為k=10。

Fig.5 Effect of k on Accuracy圖5 k 對Accuracy的影響

Fig.6 Effect of k on F-measure圖6 k 對F-measure的影響

4 結束語

針對動態數據流新類分類問題，本文提出了KCRForest 算法。KCRForest 算法是基于k近鄰的完全隨機森林算法，它將k近鄰策略融合到完全隨機森林的決策中，計算樣本的樣本離群值進行新類檢測。實驗結果表明，KCRForest 算法在檢測新類性能上優于或與iForest+SVM 算法和LOF+SVM 算法相當，分類準確率明顯高于SENCForest算法。本文可進一步改進的工作包括對各個分類效果不同的分類器設置權重，通過加權決策提升分類效果；或對數據集進行特征選擇，進一步提高新類檢測性能與分類準確率。