武煒杰，張景祥

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

隨著科學技術(shù)的不斷發(fā)展，數(shù)據(jù)流挖掘在許多領(lǐng)域上被廣泛應(yīng)用，如控制系統(tǒng)[1]、時間預(yù)測[2]、異常檢測[3]等。數(shù)據(jù)流分類問題是數(shù)據(jù)挖掘任務(wù)中的重要研究內(nèi)容，特別是靜態(tài)數(shù)據(jù)向動態(tài)數(shù)據(jù)轉(zhuǎn)變過程中新類檢測、多類標檢測、數(shù)據(jù)漂移檢測等都給數(shù)據(jù)挖掘帶來了挑戰(zhàn)[4]。

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

學者們認為數(shù)據(jù)流中新類檢測問題是增量學習方式，并提出很多研究方法。Zhang 等人[5]提出類別增量學習（class-incremental learning，C-IL）算法，通過更新分類器來處理新類出現(xiàn)的情況。Da 等人[6]提出基于利用未標記數(shù)據(jù)學習新類（learning with augmented class with unlabeled data，LACU）框架的LACUSVM 半監(jiān)督學習算法，利用可便捷收集的大量未標記數(shù)據(jù)學習新類?，F(xiàn)有的類別增量學習算法（如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]等）大多基于聚類的方法來檢測新類，但由于聚類屬于無監(jiān)督學習方法，算法的新類檢測性能與分類精確度并不理想。

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

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

1 相關(guān)工作

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

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

1.1 完全隨機森林

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

算法1CRForest

1.2 基于樣本空間內(nèi)樣本的k 近鄰

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

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

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

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

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

2 KCRForest算法

2.1 KCRForest算法原理

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

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

2.2 樣本離群值

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

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

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

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

2.3 KCRForest模型

2.3.1 KCRForest訓練模型

KCRForest 算法是基于k近鄰?fù)耆S機森林算法，使用已知類樣本訓練初始分類器。

算法2KCRForest算法訓練階段

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

2.3.2 KCRForest測試模型

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

算法3KCRForest算法測試階段

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

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

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

則閾值τ記為：

2.3.3 KCRForest更新與集成模型

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

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

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

（2）利用節(jié)點內(nèi)樣本的中心生成與節(jié)點內(nèi)記錄的原樣本數(shù)目等數(shù)量的偽樣本，再進行節(jié)點分支。

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

由于在不同的時期中，新類樣本占測試數(shù)據(jù)流的比例不同。緩沖區(qū)Β設(shè)置的大小不能為靜態(tài)的，應(yīng)隨著新類樣本占測試數(shù)據(jù)流的比例而變化。本文KCRForest模型更新條件設(shè)為：

其中，?表示一時期內(nèi)新類樣本占測試數(shù)據(jù)流X的比例。

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

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

3 實驗與結(jié)果分析

3.1 實驗數(shù)據(jù)與評價性能指標

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

Table 1 UCI dataset used in experiment表1 實驗中使用的UCI數(shù)據(jù)集

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

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

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

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

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

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

3.2 實驗測試

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

3.2.1 短數(shù)據(jù)流測試

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

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

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

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

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

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

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

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

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

3.2.2 長數(shù)據(jù)流測試

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

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

3.3 參數(shù)k 值討論

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

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

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