韓東紅 馬憲哲 李莉莉 王國(guó)仁

(東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院, 沈陽(yáng), 110819)

引 言

近年來(lái)，數(shù)據(jù)流作為一種典型的大數(shù)據(jù)類型得到廣泛的應(yīng)用，例如應(yīng)用于傳感器網(wǎng)絡(luò)[1]、監(jiān)控系統(tǒng)[2]以及網(wǎng)絡(luò)入侵檢測(cè)[3]等領(lǐng)域。和傳統(tǒng)的靜態(tài)數(shù)據(jù)不同，數(shù)據(jù)流的連續(xù)、無(wú)限、概念漂移和快速等特點(diǎn)使得使用傳統(tǒng)的分類技術(shù)進(jìn)行數(shù)據(jù)流挖掘效果不佳。因此，面向數(shù)據(jù)流的實(shí)時(shí)動(dòng)態(tài)更新的分類算法研究成為相關(guān)領(lǐng)域的研究熱點(diǎn)。

文獻(xiàn)[4]使用描述項(xiàng)的值來(lái)描述概念，通過(guò)向前滑動(dòng)窗口來(lái)刪除或者增添描述項(xiàng)。由于該系統(tǒng)存儲(chǔ)所有值對(duì)，因此該系統(tǒng)具有較高的更新成本，不能實(shí)時(shí)處理數(shù)據(jù)流。Wang等[5]提出了一個(gè)精度加權(quán)集成(Accuracy weighted ensembles, AWE)模型，用來(lái)挖掘概念漂移數(shù)據(jù)流，用組合的加權(quán)分類器來(lái)進(jìn)行數(shù)據(jù)流挖掘，該模型能夠很好地處理概念漂移，并且其分類準(zhǔn)確率較高。Domingos等[6]提出了一種基于Hoeffding 的快速?zèng)Q策樹(shù)(Very fast decision tree，VFDT) 算法，通過(guò)考察將當(dāng)前的最佳屬性作為中間節(jié)點(diǎn)，將所使用的測(cè)試數(shù)據(jù)項(xiàng)的數(shù)量在Hoeffding的邊界統(tǒng)計(jì)范圍之內(nèi)作為考察依據(jù)，但該算法不能解決概念漂移問(wèn)題。文獻(xiàn)[7]在VFDT的基礎(chǔ)上提出概念自適應(yīng)快速?zèng)Q策樹(shù)算法(Concept very fast decision tree, CVFDT)，解決了數(shù)據(jù)流概念漂移問(wèn)題。 文獻(xiàn)[8]提出任意窗口流建模算法用于在傳感器網(wǎng)絡(luò)中發(fā)現(xiàn)感興趣的模式。文獻(xiàn)[9]在按需分類中采用了CluStream的微集群思想，獲得了較高的分類準(zhǔn)確率。文獻(xiàn)[10]提出了一種新分類方法，研究怎樣使用歷史數(shù)據(jù)來(lái)進(jìn)行數(shù)據(jù)流分類。當(dāng)輸入一些新的數(shù)據(jù)，通過(guò)比較以下4個(gè)分類器的準(zhǔn)確性，從中選擇準(zhǔn)確率較高的分類器:(1) 一個(gè)舊的分類器; (2)從新的數(shù)據(jù)中學(xué)習(xí)的分類器; (3)從新數(shù)據(jù)中選擇和舊數(shù)據(jù)相似的數(shù)據(jù)學(xué)習(xí)到的分類器; (4)從舊數(shù)據(jù)中選擇和新數(shù)據(jù)相似的數(shù)據(jù)學(xué)習(xí)到的分類器。對(duì)這4個(gè)分類器進(jìn)行精度檢驗(yàn)，選出精度最高的分類器，并將其作為新的分類器。Zhang等[11]提出了一種雙集成模型對(duì)偏斜數(shù)據(jù)流進(jìn)行分類。文獻(xiàn)[12]提出了一種有效的半監(jiān)督框架，利用檢測(cè)分類器置信度來(lái)觀察概念漂移。Osojnik等[13]利用多目標(biāo)回歸提出了一種新的面向數(shù)據(jù)流的多標(biāo)簽分類方法。文獻(xiàn)[14]針對(duì)重現(xiàn)概念漂移檢測(cè)中的概念表征和分類器選擇問(wèn)題，提出基于主要特征抽取的概念聚類和預(yù)測(cè)算法。

本文從分析數(shù)據(jù)流的特點(diǎn)入手，針對(duì)具有概念漂移的數(shù)據(jù)流分類問(wèn)題，提出一種新穎的基于集成分類模型的數(shù)據(jù)流分類算法，目的是提高分類精度和時(shí)空效率。本文的貢獻(xiàn)點(diǎn)如下：

(1) 提出概念自適應(yīng)快速?zèng)Q策樹(shù)更新集成(CVFDT update ensemble, CUE)，旨在增加集成模型中基分類器的不相似度。首先利用概念自適應(yīng)快速?zèng)Q策樹(shù)CVFDT在每個(gè)數(shù)據(jù)塊上訓(xùn)練決策樹(shù)，并將訓(xùn)練得到的決策樹(shù)作為基分類器，循環(huán)這個(gè)過(guò)程，當(dāng)基分類器的數(shù)量達(dá)到L時(shí)停止循環(huán)。 其次整合每個(gè)基分類器通過(guò)加權(quán)求平均的方法得出最終結(jié)果，并將其作為待分類實(shí)例的最終分類標(biāo)簽。 然后當(dāng)發(fā)生漂移時(shí)，導(dǎo)致存在一些不適合當(dāng)前概念的基分類器，這時(shí)將使用最新數(shù)據(jù)塊對(duì)其更新。數(shù)據(jù)塊在更新之前被裝袋，從而得到各不相同的副本，這使得基分類器之間的不相似性增加。當(dāng)完成對(duì)基分類器進(jìn)行更新時(shí)，要進(jìn)行對(duì)基分類器調(diào)整權(quán)重的操作。實(shí)驗(yàn)表明，該算法的準(zhǔn)確率較高。

(2) 提出基于聚類的集成分類算法(Dynamic classifier selection with clustering, DCSC)，該算法源于集成分類器的動(dòng)態(tài)選擇思想。 首先對(duì)數(shù)據(jù)塊進(jìn)行聚類并保存聚類信息。其次訓(xùn)練決策樹(shù)并將其作為基分類器。并且集成模型保證有L個(gè)簇信息和基礎(chǔ)分類器。然后在對(duì)實(shí)例進(jìn)行分類時(shí)，分類依據(jù)是選擇與該實(shí)例具有最高相似度的基分類器，該實(shí)例的最終類標(biāo)簽就是其分類結(jié)果。在集成模型中修剪選擇較少或精度低于設(shè)定閾值的基分類器，借助新到來(lái)的數(shù)據(jù)訓(xùn)練新的基分類器，并將其加入到集成模型中。 最后的實(shí)驗(yàn)結(jié)果表明，DCSC處理數(shù)據(jù)流時(shí)具有較高的效率，對(duì)突發(fā)漂移具有較快的適應(yīng)性。

1 帶有基分類器更新的集成分類算法

1.1 算法描述

CUE算法是本文提出的一種帶有基分類器更新的數(shù)據(jù)流分類算法，該算法包含集成分類模型的構(gòu)造和集成分類模型的更新兩部分。

1.1.1 集成分類模型的構(gòu)造

CUE算法利用CVFDT算法訓(xùn)練基分類器，通過(guò)使用后續(xù)數(shù)據(jù)塊中的數(shù)據(jù)對(duì)它進(jìn)行更新。

假設(shè)用有序數(shù)據(jù)塊S1,S2,…,Sn來(lái)表示到來(lái)的數(shù)據(jù)流。集成模型在初始時(shí)是空的，伴隨著數(shù)據(jù)塊S1流入，在S1上使用CVFDT訓(xùn)練基礎(chǔ)分類器C1，并且把訓(xùn)練所得到的基分類器加入到集成模型中。接著數(shù)據(jù)塊S2到來(lái)，相應(yīng)的基礎(chǔ)分類器C2被訓(xùn)練并加入到集成模型中。當(dāng)基分類器的數(shù)量滿足小于L的條件時(shí)，給分類器設(shè)置權(quán)重1。循環(huán)上面的過(guò)程，基分類器的數(shù)量達(dá)到L時(shí)終止循環(huán)。本文提出的集成分類模型在構(gòu)造階段不對(duì)數(shù)據(jù)流進(jìn)行分類，基分類器構(gòu)造描述如算法1所示。

算法1基分類器構(gòu)造算法

輸入：S(一個(gè)數(shù)據(jù)流實(shí)例)

d(數(shù)據(jù)塊Si的大小)

L(基分類器的數(shù)量)

輸出：E(L個(gè)在線分類器的集合)

算法描述：

E←?

repeat

train classifierCionSi;

addCitoEand set weighti= 1;

untilLclassifiers inE

returnE

1.1.2 集成分類模型的更新

CUE在分類過(guò)程中引入了分類器更新機(jī)制，該更新機(jī)制使得數(shù)據(jù)塊大小對(duì)算法性能的影響不再明顯，而且通過(guò)使用不同的數(shù)據(jù)更新基分類器，增加了基分類器的不相似程度， 使得集成模型在分類性能評(píng)估上得到大大的提升。

通過(guò)1.1.1節(jié)對(duì)基分類器的訓(xùn)練，集成模型中已經(jīng)存在訓(xùn)練好的基分類器L個(gè)?？梢哉J(rèn)為最新的數(shù)據(jù)塊Sn最接近當(dāng)前數(shù)據(jù)流中類分布，因此把最新的數(shù)據(jù)塊Sn當(dāng)做測(cè)試集，使用式(1)計(jì)算所有的基分類器的均方誤差MSE為

(1)

(2)

式中：ε用來(lái)避免MSEi為0的情況，將其設(shè)置為無(wú)窮小正常數(shù)。

計(jì)算任何一個(gè)基分類器對(duì)數(shù)據(jù)塊Sn中實(shí)例的類別進(jìn)行隨意猜測(cè)的均方誤差MSEr為

(3)

其中p(c) 代表在Sn中各個(gè)類所占比例，其取值在0到1之間。

CUE選擇MSEi>MSEr的基分類器進(jìn)行更新，其目的是能夠充分利用數(shù)據(jù)并增加基分類器之間的不相似度?？梢岳斫鉃椋篗SEr表示任意分類器隨機(jī)猜測(cè)Sn中的實(shí)例的隨機(jī)錯(cuò)誤概率。當(dāng)Ci的均方誤差MSEi大于MSEr時(shí)，基分類器對(duì)集成模型不起作用，需要進(jìn)行更新。然而，直接使用Sn作為訓(xùn)練數(shù)據(jù)更新基分類器將減少基分類器之間的差異性。因此需要先對(duì)Sn進(jìn)行裝袋操作，得到原始數(shù)據(jù)塊的不同副本，從而增加基分類器彼此間的不相似度和獨(dú)立性，該集成模型的分類能力也得到提高。算法描述如算法2所示。

算法2CUE更新算法

輸入：S(一個(gè)數(shù)據(jù)流實(shí)例)

d(數(shù)據(jù)塊Si的大小)

k(基分類器的數(shù)量)

輸出：E(由k個(gè)可更新權(quán)重的在線分類器構(gòu)成的集成分類器)

算法描述：

for all classifiersCi∈Edo

applyCionSnto derive MSEi

derive weightw′ forCiusing equation (2)

end for

for all classifiersCi∈Edo

if MSEi>MSErthen

update classifierCiwithSnusing bagging

end if

end for

E← updated weighted classifiers ∈E

classify a new instance withEusing weighted average

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

集成分類算法AWE[5]具有較好的分類準(zhǔn)確率和概念漂移處理能力，是有代表性的數(shù)據(jù)流分類算法。在本文的實(shí)驗(yàn)中，分別在時(shí)間效率、內(nèi)存使用情況和窗口大小對(duì)算法的影響及準(zhǔn)確率等方面對(duì)比本文提出的CUE算法和AWE算法的差異。在本實(shí)驗(yàn)中，AWE的基分類器通過(guò)訓(xùn)練VFDT得到。

1.2.1 數(shù)據(jù)集

采用兩個(gè)數(shù)據(jù)集模擬數(shù)據(jù)流環(huán)境來(lái)評(píng)估CUE算法的性能，即美國(guó)聯(lián)邦森林覆蓋類型數(shù)據(jù)集和波形數(shù)據(jù)集。

(1) 美國(guó)聯(lián)邦森林覆蓋類型數(shù)據(jù)集：它是真實(shí)的數(shù)據(jù)集，該數(shù)據(jù)源于美國(guó)林業(yè)局的區(qū)域資源信息系統(tǒng)，該數(shù)據(jù)集共包含數(shù)據(jù)記錄581 012條。選擇其中的50 000條用于實(shí)驗(yàn)，每條記錄由54個(gè)屬性組成。

表1 默認(rèn)實(shí)驗(yàn)參數(shù)設(shè)置

(2) 波形數(shù)據(jù)集：該數(shù)據(jù)集是一個(gè)由3個(gè)類別標(biāo)簽組成的人工合成數(shù)據(jù)集，其中每個(gè)實(shí)例有屬性值是實(shí)數(shù)的屬性40個(gè)，后19個(gè)有噪聲，帶有緩慢的概念漂移。

1.2.2 實(shí)驗(yàn)分析

兩種算法中參數(shù)設(shè)置如表1所示。隨著決策樹(shù)的增長(zhǎng)，會(huì)產(chǎn)生更多的中間節(jié)點(diǎn)，每個(gè)中間節(jié)點(diǎn)都有一棵替代的子樹(shù)。 存儲(chǔ)和處理這些子樹(shù)也需要很多時(shí)間，因此限制樹(shù)的深度有助于提高算法的效率。這個(gè)實(shí)驗(yàn)中，限制決策樹(shù)的最大深度為8。

(1) 時(shí)間效率

算法所使用的時(shí)間分為訓(xùn)練時(shí)間和測(cè)試時(shí)間。圖1和圖2分別顯示了AWE算法和CUE算法分別在兩個(gè)數(shù)據(jù)集上訓(xùn)練的平均訓(xùn)練時(shí)間。CUE算法比AWE算法的訓(xùn)練時(shí)間長(zhǎng)。經(jīng)過(guò)分析原因有兩個(gè)：一方面CUE中學(xué)習(xí)基分類器算法采用CVFDT；另一方面當(dāng)CUE算法發(fā)現(xiàn)集成模型中存在不適應(yīng)當(dāng)前概念的基分類器時(shí)，使用Bagging技術(shù)對(duì)多個(gè)副本進(jìn)行采樣再更新基本分類器。但AWE僅使用VFDT學(xué)習(xí)基分類器，和CUE算法相比缺少更新分類器和抽取樣本兩個(gè)過(guò)程。

Fig.1 Comparison of average chunk training time on Waveform data set

圖2 在森林覆蓋數(shù)據(jù)集上一個(gè)數(shù)據(jù)塊的平均訓(xùn)練時(shí)間對(duì)比

Fig.2 Comparison of average chunk training time on Forest CoverType data set

圖3和圖4顯示了分別在波形數(shù)據(jù)集和森林覆蓋數(shù)據(jù)集上CUE和AWE算法的測(cè)試時(shí)間。從圖3，4中可以看出，CUE的平均測(cè)試略高于AWE。 這是因?yàn)镃VFDT算法的中間節(jié)點(diǎn)會(huì)隨新數(shù)據(jù)流入而改變，增加了時(shí)間成本。 另外，兩種算法的測(cè)試時(shí)間不隨數(shù)據(jù)量的增加而增加，維持在一個(gè)恒定范圍內(nèi)，這滿足數(shù)據(jù)挖掘?qū)r(shí)間的約束。

圖3 在波形數(shù)據(jù)集上一個(gè)數(shù)據(jù)塊的平均測(cè)試時(shí)間對(duì)比

Fig.3 Comparison of average chunk test time on Waveform data set

>圖4 在森林覆蓋數(shù)據(jù)集上一個(gè)數(shù)據(jù)塊的平均測(cè)試時(shí)間對(duì)比

Fig.4 Comparison of average chunk test time on Forest CoverType data set

(2) 內(nèi)存占用情況

圖5和圖6分別顯示了在波形數(shù)據(jù)集和森林覆蓋數(shù)據(jù)集上CUE和AWE算法的占用內(nèi)存情況?？梢钥闯?，CUE消耗的內(nèi)存比AWE多。CVFDT隨著數(shù)據(jù)增多逐漸增長(zhǎng)，特別是當(dāng)數(shù)據(jù)集的屬性越多，可以替代的子樹(shù)和中間節(jié)點(diǎn)就越多，則需要更多的內(nèi)存來(lái)存儲(chǔ)這些子樹(shù)。 另外，CUE在基分類器的更新過(guò)程中提供裝袋抽樣，需要額外內(nèi)存存儲(chǔ)副本。隨著數(shù)據(jù)量的增加，CUE能夠符合數(shù)據(jù)流挖掘的內(nèi)存約束，因?yàn)镃UE算法在運(yùn)行過(guò)程中占用的內(nèi)存接近于一個(gè)常數(shù)。

Fig.5 Comparison of memory usage on Waveform data set

圖6 在森林覆蓋數(shù)據(jù)集上內(nèi)存使用情況

Fig.6 Comparison of memory usage on Forest Cover-Type data set

(3) 準(zhǔn)確率

圖7顯示了在波形數(shù)據(jù)集上兩種算法的準(zhǔn)確率情況。從圖7中可以看出CUE算法的平均準(zhǔn)確率高于AWE算法。在20 000數(shù)據(jù)點(diǎn)處，波形數(shù)據(jù)集產(chǎn)生突變概念漂移，此時(shí)CUE算法和AWE算法的準(zhǔn)確率都突然下降。接下來(lái)準(zhǔn)確率再次提升，且CUE有較快的提升速度。

為了形成突變漂移概念，從森林覆蓋數(shù)據(jù)集的開(kāi)頭和中間提取連續(xù)的15 000條數(shù)據(jù)，尾部提取20 000條數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，結(jié)果如圖8所示。從圖8中可以看出，兩種算法的準(zhǔn)確度在加工數(shù)據(jù)在15 000條時(shí)開(kāi)始迅速下降，然后CUE準(zhǔn)確率逐漸升高，30 000條數(shù)據(jù)時(shí)再次急劇下降，然后再升高。由于CUE適應(yīng)當(dāng)前新概念， 其準(zhǔn)確率總是高于AWE，并可以快速適應(yīng)突變概念漂移。

Fig.7 Comparison of accuracy on Waveform data set

圖8 在森林覆蓋數(shù)據(jù)集上的準(zhǔn)確率對(duì)比

Fig.8 Comparison of accuracy on Forest CoverType data set

(4) 數(shù)據(jù)塊大小對(duì)算法性能的影響

圖9和圖10分別顯示了在波形數(shù)據(jù)集和森林覆蓋數(shù)據(jù)集上數(shù)據(jù)塊的大小對(duì)準(zhǔn)確率的影響。如圖9所示，隨著數(shù)據(jù)塊增大，在波形數(shù)據(jù)集上CUE算法和AWE算法的準(zhǔn)確率呈下降的趨勢(shì)，在1 000處性能最好。主要是因?yàn)閮煞N算法在數(shù)據(jù)塊為500時(shí)都能很快適應(yīng)流中變化，但由于AWE算法的訓(xùn)練數(shù)據(jù)不足，基分類器的分類能力不強(qiáng)，因此整體分類準(zhǔn)確率不高。CUE算法通過(guò)不斷使用新數(shù)據(jù)更新基分類器，幾乎不受數(shù)據(jù)塊大小影響，因此整體分類準(zhǔn)確率高于AWE算法。當(dāng)數(shù)據(jù)塊大小為1 000時(shí)， AWE算法由于訓(xùn)練數(shù)據(jù)充分，其準(zhǔn)確率大大提升?？梢?jiàn)這兩種算法在數(shù)據(jù)塊大小為1 000時(shí)獲得最佳的分類準(zhǔn)確率。此后隨著數(shù)據(jù)塊大小的增加，準(zhǔn)確率緩慢下降。這是由于：數(shù)據(jù)塊過(guò)大會(huì)影響算法對(duì)流中變化的反應(yīng)速率并且使得同一數(shù)據(jù)塊中包含數(shù)據(jù)存在多種概念，這將導(dǎo)致集成分類器的分類能力不強(qiáng)，學(xué)習(xí)到的基分類器的分類規(guī)則可能模糊等問(wèn)題。同時(shí)從圖9可以看出，當(dāng)數(shù)據(jù)塊的大小為2 500時(shí)，CUE算法比AWE算法的準(zhǔn)確率低。數(shù)據(jù)塊較大的情況掩蓋了CUE算法基分類器可更新的優(yōu)點(diǎn)。

圖10的變化趨勢(shì)與圖9中波形數(shù)據(jù)集基本相同，但精度低于圖9波形數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果，主要原因是森林覆蓋數(shù)據(jù)集的數(shù)據(jù)概念漂移更頻繁。 過(guò)大的數(shù)據(jù)塊影響算法的更新速度和準(zhǔn)確率，使得算法的更新速度變慢，準(zhǔn)確度變低。 另外可以看出，在大數(shù)據(jù)塊的情況下，CUE算法的準(zhǔn)確率比AWE算法的準(zhǔn)確率低。

圖9 在波形數(shù)據(jù)集上數(shù)據(jù)塊大小對(duì)準(zhǔn)確率的影響對(duì)比

Fig.9 Comparison of influence of different chunk size on accuracy on Waveform data set

圖10 在森林覆蓋數(shù)據(jù)集上數(shù)據(jù)塊大小對(duì)準(zhǔn)確率的影響對(duì)比

Fig.10 Comparison of influence of different chunk size on accuracy on Forest CoverType data set

通過(guò)兩個(gè)實(shí)驗(yàn)的對(duì)比可以看出，CUE算法不用擔(dān)心訓(xùn)練數(shù)據(jù)不足的問(wèn)題并且能更快適應(yīng)流的變化，因此能夠提高整體分類能力，適合于較小的數(shù)據(jù)塊環(huán)境。

2 基于聚類的動(dòng)態(tài)選擇分類器DCSC

2.1 算法描述

DCSC算法是基于聚類技術(shù)的數(shù)據(jù)流分類算法。該算法的提出采用動(dòng)態(tài)選擇思想，可以分為：(1) 基分類器的訓(xùn)練；(2) 采用訓(xùn)練好的分類器對(duì)數(shù)據(jù)流進(jìn)行分類；(3) 剪枝表現(xiàn)比較差的基分類器，訓(xùn)練新的基分類器來(lái)替換差的基分類器。

2.1.1 集成分類模型的構(gòu)造

首先將數(shù)據(jù)流劃分成大小相等的數(shù)據(jù)塊S1,S2,…,Sn，按照到達(dá)順序聚類每個(gè)數(shù)據(jù)塊，把訓(xùn)練數(shù)據(jù)分成各不相交的簇，保留每個(gè)簇的概要信息。簇的概要信息公式為

INFOcluster=

(4)

式中：n為簇中訓(xùn)練數(shù)據(jù)的個(gè)數(shù)，centroid為簇的聚類中心。

聚類結(jié)束后，使用VFDT在數(shù)據(jù)塊上的訓(xùn)練決策樹(shù)作為基分類器，并將訓(xùn)練好的基分類器添加到集成模型中，最多能夠容納的基分類器的個(gè)數(shù)為L(zhǎng)。循環(huán)該過(guò)程L-1次，當(dāng)集成模型存在L個(gè)基分類器時(shí)結(jié)束循環(huán)，構(gòu)造集成分類器完成。 集成模型可表示為：Ensemble = (C1,C2,…,CL)。 與此同時(shí)，保存DCSC處理一個(gè)數(shù)據(jù)塊后基分類器Ci被選擇的次數(shù)CHOSEN_NUMi(i= 1,2,…,L)。

2.1.2 使用集成分類模型來(lái)進(jìn)行分類

用DCSC算法對(duì)數(shù)據(jù)流進(jìn)行分類由兩部分組成：首先采用歐幾里德距離計(jì)算每個(gè)基分類器對(duì)應(yīng)簇與實(shí)例R之間的距離。歐幾里德距離為

(5)

其中Ri=(ri1,ri2,…,rin)代表實(shí)例Ri的屬性值，Rj=(rj1,rj2,…,rjn)代表實(shí)例Rj的屬性值。根據(jù)式(5)，找到數(shù)據(jù)塊中最接近實(shí)例R的k個(gè)簇，并計(jì)算這些k個(gè)距離的總和，標(biāo)記為DISTANCEKL，然后計(jì)算k個(gè)簇中所包含的數(shù)據(jù)量總量Num。由于距離總和的大小象征該數(shù)據(jù)塊與待分類實(shí)例的相似程度，數(shù)據(jù)量總和的大小象征在數(shù)據(jù)塊上與待分類實(shí)例類似的的數(shù)據(jù)的數(shù)量的大小，所以找到滿足最大Num值且最小DISTANCEk的數(shù)據(jù)塊所對(duì)應(yīng)的基分類器。求出Num和DISTANCEk的商，并將其標(biāo)記為p，如式(6)所示。

圖11 數(shù)據(jù)塊中找最近的簇的示意圖 (k=2) Fig.11 Diagram of finding the clos-est cluster in chunk(k=2)

(6)

把L個(gè)基分類器具有最大p值的基分類器C′的分類結(jié)果作為集成模型的分類結(jié)果。在數(shù)據(jù)塊中找最近k個(gè)簇的過(guò)程描述如圖11所示。具體處理流程如算法3所示。其中， distance(centroidi, record) 表示簇質(zhì)心與實(shí)例record之間的距離。choose_min_k(disti)是為了找出與實(shí)例record距離最近的k個(gè)質(zhì)心，計(jì)算p值并將其作為選擇分類器的依據(jù)。

算法3使用DCSC對(duì)實(shí)例分類

輸入： INFO cluster (簇的信息)

Ensemble (基分類器集合)

Record(數(shù)據(jù)流上到來(lái)的待分類的實(shí)例)

輸出： label (分類器對(duì)record分類的類標(biāo))

算法描述：

for each INFO cluster

for each centroidido

disti= distance(centroidi, record)

end for

choose_min_k(disti)

calculatep

end for

choose the classifier with maxp

label ←classify record using chosen classifier

return label

2.1.3 集成分類模型更新

集成分類模型的更新是為了適應(yīng)數(shù)據(jù)流環(huán)境下發(fā)生的概念漂移和圍標(biāo)分布變化的問(wèn)題，去除表現(xiàn)不佳的基分類器，使用最近數(shù)據(jù)訓(xùn)練新的基分類器加入到集成模型中。

算法的更新頻率影響算法的效率。為了平衡算法的效率和更新頻率，DCSC算法在每處理一個(gè)數(shù)據(jù)塊之后，通過(guò)分類準(zhǔn)確率accuracy和分類數(shù)據(jù)塊時(shí)分類器被選擇的次數(shù)used_times來(lái)去除表現(xiàn)不佳的基分類器。MIN_FREQUENCY表示被選擇的最小次數(shù)， MIN_ACCURACY表示最小準(zhǔn)確率。如果在數(shù)據(jù)塊的處理之后選擇分類器的次數(shù)低于MIN_FREQUENCY，則表明分類器對(duì)整個(gè)集成模型的貢獻(xiàn)很小，與當(dāng)前概念有較大差異，應(yīng)該將其移除。如果選擇分類器的次數(shù)大于MIN_FREQUENCY，準(zhǔn)確率低于LOW_ACCURACY，表明該分類器不適應(yīng)當(dāng)前的概念并且應(yīng)當(dāng)移除該分類器。最后，通過(guò)訓(xùn)練新基分類器，并將訓(xùn)練的新基分類器添加到集成模型中完成集成模型的更新操作，完整描述如算法4所示。

算法4更新集成分類模型

輸入： Ensemble (包含L個(gè)基分類器的集成模型)

Sn(數(shù)據(jù)流中第n個(gè)數(shù)據(jù)塊)

輸出： Ensemble (更新后的集成模型)

算法描述：

classify current chunkSn

for each classifierCiin the Ensemble

ifCi.used_times < MIN_FREQUENCY

then removeCi

else ifCi.accuracy < MIN_ACCURACY

then removeCi

end if

end if

end for

if account(Ensemble)

cluster current chunk and trainC′ on the current chunkSn

addC′ to Ensemble

end if

return Ensemble

2.1.4 集成分類模型的整體描述

DCSC算法將數(shù)據(jù)流劃分為等大的數(shù)據(jù)塊，首先對(duì)數(shù)據(jù)塊進(jìn)行聚類，然后訓(xùn)練分類器。分類器學(xué)到的規(guī)則越詳細(xì)，這些實(shí)例的分類準(zhǔn)確度就越高。 選擇基分類器之后，使用該分類器對(duì)實(shí)例進(jìn)行分類，并將結(jié)果用作實(shí)例的最終類標(biāo)簽。 完整描述如算法5所示。

算法5DCSC算法

輸入：S(一個(gè)數(shù)據(jù)流的實(shí)例)

輸出：C(數(shù)據(jù)流上每個(gè)實(shí)例的預(yù)測(cè)類別)

算法描述：

數(shù)據(jù)流劃分為相同大小的數(shù)據(jù)塊

按順序L次在每個(gè)數(shù)據(jù)塊中訓(xùn)練一個(gè)分類器

for each chunk

classify each instance in the chunk by Algorithm 3

for each classifierCiin the Ensemble

ifCi.used_times < MIN_FREQUENCY orCi.accuracy < MIN_ACCURACY

update the ensemble using Algorithm 4

end if

end for

end for

returnC

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

DCSC算法從集成模型中的基分類器中選擇與待分類的實(shí)例具有最高相似度的基分類器，該實(shí)例的類標(biāo)由所選擇的基分類器的分類結(jié)果確定。與整合分類模型相比，DCSC具有較快分類未知類別實(shí)例的優(yōu)點(diǎn)，分類準(zhǔn)確率高于單分類器。

2.2.1 數(shù)據(jù)集

本實(shí)驗(yàn)所使用數(shù)據(jù)流環(huán)境用KDD CUP’99[15]網(wǎng)絡(luò)入侵?jǐn)?shù)據(jù)集和SEA數(shù)據(jù)集來(lái)模擬。

(1) KDD CUP’99[15]網(wǎng)絡(luò)入侵?jǐn)?shù)據(jù)集。該數(shù)據(jù)集是真實(shí)數(shù)據(jù)集，是麻省理工學(xué)院林肯實(shí)驗(yàn)室管理的局域網(wǎng)的兩個(gè)星期內(nèi)TCP的連接記錄，均為正常連接或入侵或攻擊記錄。

(2) SEA數(shù)據(jù)集。該數(shù)據(jù)集是合成數(shù)據(jù)集，在數(shù)據(jù)挖掘中經(jīng)常用到，數(shù)據(jù)集中的每條記錄都有2個(gè)類標(biāo)簽和3個(gè)連續(xù)的屬性。它首先出現(xiàn)在文獻(xiàn)[16]中，并被用于算法SEA的實(shí)驗(yàn)部分。

2.2.2 實(shí)驗(yàn)分析

兩個(gè)算法的參數(shù)設(shè)置如表2所示。

(1) 參數(shù)影響

在DCSC算法中，對(duì)待分類的實(shí)例進(jìn)行分類需要選擇合適的基分類器，在此過(guò)程中，考慮簇中包含的數(shù)據(jù)量，找到最接近待分類實(shí)例的k個(gè)簇的質(zhì)心。由于實(shí)驗(yàn)中將每個(gè)數(shù)據(jù)塊上的簇?cái)?shù)設(shè)置為10，與待分類實(shí)例最近的簇k不能太大。在本節(jié)中，通過(guò)實(shí)驗(yàn)研究DCSC在k= 1,2和3時(shí)的精確率。

圖12顯示不同k值對(duì)準(zhǔn)確率的影響。如圖12所示，因?yàn)閗=2不僅可以保證相似性，而且兼顧到足夠多的訓(xùn)練數(shù)據(jù)， DCSC算法在k=2時(shí)具有最高的準(zhǔn)確率，因此在其他實(shí)驗(yàn)中，均取k=2。

表2默認(rèn)實(shí)驗(yàn)參數(shù)設(shè)置Tab.2Defaultparametersetting

參數(shù)含義設(shè)定值Base_num基分類器個(gè)數(shù)15Chunk_size數(shù)據(jù)塊大小1 000Recordpoint觀測(cè)點(diǎn)5 000Tree_height決策樹(shù)的高度8Grace_period分裂一個(gè)節(jié)點(diǎn)需要的最少的數(shù)據(jù)量200MIN_FREQUENCY基分類器最少被選中的次數(shù)50MIN_ACCURACY基分類器的最低準(zhǔn)確率/%70MAX_REPEATK-means最多迭代的次數(shù)100

圖12 不同k值對(duì)準(zhǔn)確率的影響

Fig.12 Influence of differentkon accuracy

(2) 時(shí)間效率

圖13和圖14顯示AWE算法和DCSC算法分別在SEA數(shù)據(jù)集和KDD CUP’99數(shù)據(jù)集上的平均訓(xùn)練時(shí)間。如圖13，14所示，DCSC算法的平均訓(xùn)練時(shí)間與AWE算法相比，時(shí)而長(zhǎng)，時(shí)而短。 這是因?yàn)镈CSC算法先進(jìn)行聚類分析，并存儲(chǔ)聚類結(jié)果，再對(duì)數(shù)據(jù)塊上的基分類器進(jìn)行訓(xùn)練，因此DCSC算法比AWE算法需要更多的時(shí)間。但是在更新頻率上DCSC算法比AWE算法低。DCSC算法只有在選擇基分類器次數(shù)和準(zhǔn)確率低于分別設(shè)定的MIN_FREQUENCY和MIN_ACCURACY值時(shí)，才會(huì)更新。然而，AWE算法隨著新數(shù)據(jù)塊的到達(dá)，都要進(jìn)行決策樹(shù)的訓(xùn)練，并將其作為后備的基分類器以供使用。 除此之外，AWE算法需要為每個(gè)數(shù)據(jù)塊重新分配權(quán)重。 因此，當(dāng)處于平緩數(shù)據(jù)流的環(huán)境中，在更新頻率上，DCSC算法低于AWE算法，在平均訓(xùn)練時(shí)間上，DCSC算法小于AWE算法。 當(dāng)數(shù)據(jù)流中的概念漂移或類分布發(fā)生變化時(shí)，DCSC算法的平均訓(xùn)練時(shí)間將比AWE算法的平均訓(xùn)練時(shí)間長(zhǎng)。

通過(guò)對(duì)比圖15和圖16可以看出，DCSC算法在兩個(gè)數(shù)據(jù)集上分類每個(gè)數(shù)據(jù)塊的平均測(cè)試時(shí)間明顯比AWE算法少。這是因?yàn)镈CSC算法在對(duì)待分類的實(shí)例進(jìn)行分類時(shí)只選擇一個(gè)基分類器，這就導(dǎo)致沒(méi)有給基分類器賦予權(quán)值的必要，所以該算法的計(jì)算復(fù)雜度減少。而在AWE算法中，基分類器全部都參與分類，然后綜合每個(gè)基分類器分類的結(jié)果。

圖13 在SEA數(shù)據(jù)集上每個(gè)數(shù)據(jù)塊的平均訓(xùn)練時(shí)間對(duì)比

Fig.13 Comparison of average chunk training time on SEA data set

圖14 在KDD CUP’99數(shù)據(jù)集上每個(gè)數(shù)據(jù)塊的平均訓(xùn)練時(shí)間對(duì)比

Fig.14 Comparison of average chunk training time on KDD CUP’99 data set

圖15 在SEA數(shù)據(jù)集上每個(gè)數(shù)據(jù)塊的測(cè)試時(shí)間對(duì)比

Fig.15 Comparison of average chunk test time on SEA data set

圖16 在KDD CUP’99數(shù)據(jù)集上每個(gè)數(shù)據(jù)塊的測(cè)試時(shí)間對(duì)比

Fig.16 Comparison of average chunk test time on KDD CUP’99 data set

(3) 內(nèi)存使用情況

兩種算法內(nèi)存使用情況實(shí)驗(yàn)結(jié)果如圖17，18所示。由圖17和圖18可以看出，DCSC算法的存儲(chǔ)占用率比AWE算法要高。這是因?yàn)镈CSC需要對(duì)數(shù)據(jù)塊進(jìn)行聚類并保存聚類的結(jié)果信息。因此在內(nèi)存占用上，DCSC算法比AWE算法消耗略多。 并且在聚類分析時(shí)，所消耗的內(nèi)存與數(shù)據(jù)屬性的數(shù)量存在正相關(guān)關(guān)系，DCSC算法在KDD CUP’99數(shù)據(jù)集中消耗的內(nèi)存比在SEA數(shù)據(jù)集上要多。

圖17和圖18同時(shí)也顯示，算法AWE和算法DCSC隨著數(shù)據(jù)流的不斷流入在內(nèi)存的消耗上都保持在一個(gè)恒定的范圍內(nèi)增長(zhǎng)。 這表明DCSC算法可以有效地挖掘數(shù)據(jù)流，因?yàn)樵跀?shù)據(jù)流挖掘中存儲(chǔ)容量有限，DCSC滿足這一限制條件。

圖17 在SEA數(shù)據(jù)集上內(nèi)存使用情況對(duì)比

Fig.17 Comparison of memory usage on SEA data set

圖18 在KDD CUP’99 數(shù)據(jù)集上內(nèi)存使用情況對(duì)比

Fig.18 Comparison of memory usage on KDD CUP’99 data set

(4) 準(zhǔn)確率

對(duì)于SEA數(shù)據(jù)集，DCSC算法的準(zhǔn)確率始終高于AWE算法，如圖19所示。這是由于DCSC算法構(gòu)造出的模型只從集成模型中選擇一個(gè)基分類器來(lái)對(duì)分類的實(shí)例進(jìn)行分類，歷史數(shù)據(jù)對(duì)分類不產(chǎn)生影響，因而準(zhǔn)確率高。當(dāng)處理20 000條的數(shù)據(jù)時(shí)，為了模擬突變漂移，改變SEA數(shù)據(jù)生成器參數(shù)。 圖19顯示AWE算法和DCSC算法的準(zhǔn)確率都快速下降并且恢復(fù)，其中DCSC算法的準(zhǔn)確率恢復(fù)得更快。 這是因?yàn)镈CSC算法在對(duì)待分類的實(shí)例進(jìn)行分類時(shí)選擇的基分類器數(shù)量只有一個(gè)，不需要使用歷史數(shù)據(jù)就可以獲得分類結(jié)果，DCSC算法能夠快速適應(yīng)新的概念。

在網(wǎng)絡(luò)入侵?jǐn)?shù)據(jù)集KDD CUP’99中，為了模擬數(shù)據(jù)流的突變漂移，在數(shù)據(jù)集上間隔較大的3部分分別連續(xù)抽取10 000, 15 000, 20 000條數(shù)據(jù)，準(zhǔn)確率如圖20所示。從圖20可以看出AWE算法具有較高準(zhǔn)確率。這是由于歷史數(shù)據(jù)對(duì)數(shù)據(jù)流在相對(duì)平緩的環(huán)境下有較大的貢獻(xiàn)，結(jié)合每個(gè)基分類器的結(jié)果，產(chǎn)生較高的準(zhǔn)確率。DCSC當(dāng)突變漂移發(fā)生時(shí)只選擇一個(gè)基分類器對(duì)分類實(shí)例進(jìn)行分類，能夠更快地適應(yīng)概念漂移的數(shù)據(jù)流而不受到歷史數(shù)據(jù)的影響。

圖19 不同算法在SEA數(shù)據(jù)集上的準(zhǔn)確率對(duì)比

圖20 不同算法在KDD CUP’99數(shù)據(jù)集上的準(zhǔn)確率對(duì)比

Fig.20 Comparison of accuracy on KDD CUP’99 data set

3 結(jié)束語(yǔ)

首先，本文提出了一個(gè)動(dòng)態(tài)數(shù)據(jù)流集成分類算法CUE，使用概念自適應(yīng)快速?zèng)Q策樹(shù)CVFDT訓(xùn)練基分類器。 選擇概念自適應(yīng)快速?zèng)Q策樹(shù)CVFDT的原因，是CVFDT使用后續(xù)數(shù)據(jù)訓(xùn)練備選基分類器，更新具有較低分類準(zhǔn)確率的基分類器。 采用更新操作不僅使得基分類器之間的不相似度增加，而且使得基分類器的分類能力提高。 為了使算法適應(yīng)數(shù)據(jù)流漂移概念的能力得到提高，用最新的數(shù)據(jù)塊更新分類準(zhǔn)確率較低的基分類器，使基分類器適應(yīng)當(dāng)前的概念，使得整個(gè)集成模型的分類性能得到改善。實(shí)驗(yàn)表明，在具有概念漂移的數(shù)據(jù)流環(huán)境下，該算法具有快速的反應(yīng)能力和良好的分類準(zhǔn)確率。

其次，本文提出了集成分類算法DCSC，該算法基于聚類動(dòng)態(tài)選擇思想。該算法首先對(duì)到來(lái)的數(shù)據(jù)流的每個(gè)數(shù)據(jù)塊進(jìn)行聚類，并將聚類結(jié)果保存到內(nèi)存中。接下來(lái)再訓(xùn)練決策樹(shù)，并在集成模型中加入訓(xùn)練好的決策樹(shù)作為基分類器。集成模型保持L個(gè)基分類器和相應(yīng)的L個(gè)聚類結(jié)果。在對(duì)待分類的實(shí)例進(jìn)行分類時(shí)，選擇與實(shí)例具有最高相似度的分類器，該分類器的分類結(jié)果作為該實(shí)例的最終分類標(biāo)簽。通過(guò)選擇具有較低準(zhǔn)確率且被選中次數(shù)少的基分類器，將其刪除并訓(xùn)練新的基分類器來(lái)更新集成模型。實(shí)驗(yàn)表明，該算法處理具有概念漂移的數(shù)據(jù)流具有較高的時(shí)間效率，能夠快速適應(yīng)突發(fā)漂移。

綜上所述，本文提出的對(duì)帶有概念漂移的數(shù)據(jù)流進(jìn)行分類的CUE算法和DCSC算法，有自己不同的優(yōu)點(diǎn)。CUE算法是為了增加集成模型中的基分類器之間的相異度而提出的，該算法能夠?qū)崿F(xiàn)在線更新，且對(duì)帶有概念漂移的數(shù)據(jù)流，其在分類準(zhǔn)確率和快速反應(yīng)能力上都有很好的提升。DCSC算法的提出源于集成分類器動(dòng)態(tài)選擇思想，該算法對(duì)突變漂移有較快的適應(yīng)能力，并且具有較高的時(shí)間效率。