武煒杰，張景祥

江南大學(xué)理學(xué)院，江蘇無錫214122

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

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

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

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

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

1 相關(guān)工作

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

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

1.1 完全隨機(jī)森林

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

算法1CRForest

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

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

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

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

樣本空間Ω11內(nèi)樣本x的k近鄰：對(duì)k∈N?，在樣本空間Ω1中存在樣本z，它與樣本x之間的距離記作d(x,z)。若在Ω1中至少有不包括x在內(nèi)的k個(gè)樣本p∈Ω1{x}，滿足d(x,p)≤d(x,z)。則記這樣的k個(gè)樣本為樣本空間Ω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]使用已知類樣本訓(xùn)練SENCTree，根據(jù)iForest[14]算法提出的異常樣本往往落在平均路徑長(zhǎng)度較短的葉節(jié)點(diǎn)內(nèi)，將樣本空間劃分為正常區(qū)域與異常區(qū)域。其中已知類樣本通常分布在正常區(qū)域內(nèi)，而已知類異常樣本與新類樣本通常分布在異常區(qū)域內(nèi)。其中已知類異常樣本分布在正常區(qū)域的邊緣，新類樣本的分布距離正常區(qū)域更遠(yuǎn)。SENCForest 算法根據(jù)不同類型樣本的分布特點(diǎn)，根據(jù)劃分的區(qū)域區(qū)別正常樣本與異常樣本。在異常區(qū)域內(nèi)，以其中樣本的中心為球心，樣本中心到與之最遠(yuǎn)的樣本的距離為半徑畫球。在測(cè)試過程中，落在此異常區(qū)域內(nèi)球半徑外的樣本標(biāo)記為新類。

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

2.2 樣本離群值

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

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

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

樣本x的局部可達(dá)密度為：

2.3 KCRForest模型

2.3.1 KCRForest訓(xùn)練模型

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

算法2KCRForest算法訓(xùn)練階段

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

2.3.2 KCRForest測(cè)試模型

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

算法3KCRForest算法測(cè)試階段

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

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

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

則閾值τ記為：

2.3.3 KCRForest更新與集成模型

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)與評(píng)價(jià)性能指標(biāo)

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

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

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

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

本文實(shí)驗(yàn)采用分類準(zhǔn)確率（Accuracy）、新類召回率（newclass recall，NR）、新類精度（newclass precision，NP）和F-measure[18]作為評(píng)價(jià)指標(biāo)。

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

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

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

3.2 實(shí)驗(yàn)測(cè)試

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

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

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

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

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

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

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

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

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

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

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

3.2.2 長(zhǎng)數(shù)據(jù)流測(cè)試

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

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

3.3 參數(shù)k 值討論

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

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

Fig.5 Effect of k on Accuracy圖5 k 對(duì)Accuracy的影響

Fig.6 Effect of k on F-measure圖6 k 對(duì)F-measure的影響

4 結(jié)束語

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