基于集成分類器的數(shù)據(jù)流分類算法

韓東紅 馬憲哲 李莉莉 王國仁

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

引 言

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

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

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

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

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

1.1 算法描述

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

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

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

假設(shè)用有序數(shù)據(jù)塊S1,S2,…,Sn來表示到來的數(shù)據(jù)流。集成模型在初始時(shí)是空的，伴隨著數(shù)據(jù)塊S1流入，在S1上使用CVFDT訓(xùn)練基礎(chǔ)分類器C1，并且把訓(xùn)練所得到的基分類器加入到集成模型中。接著數(shù)據(jù)塊S2到來，相應(yīng)的基礎(chǔ)分類器C2被訓(xùn)練并加入到集成模型中。當(dāng)基分類器的數(shù)量滿足小于L的條件時(shí)，給分類器設(shè)置權(quán)重1。循環(huán)上面的過程，基分類器的數(shù)量達(dá)到L時(shí)終止循環(huán)。本文提出的集成分類模型在構(gòu)造階段不對數(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在分類過程中引入了分類器更新機(jī)制，該更新機(jī)制使得數(shù)據(jù)塊大小對算法性能的影響不再明顯，而且通過使用不同的數(shù)據(jù)更新基分類器，增加了基分類器的不相似程度， 使得集成模型在分類性能評估上得到大大的提升。

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

(1)

(2)

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

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

(3)

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

CUE選擇MSEi>MSEr的基分類器進(jìn)行更新，其目的是能夠充分利用數(shù)據(jù)并增加基分類器之間的不相似度。可以理解為：MSEr表示任意分類器隨機(jī)猜測Sn中的實(shí)例的隨機(jī)錯(cuò)誤概率。當(dāng)Ci的均方誤差MSEi大于MSEr時(shí)，基分類器對集成模型不起作用，需要進(jìn)行更新。然而，直接使用Sn作為訓(xùn)練數(shù)據(jù)更新基分類器將減少基分類器之間的差異性。因此需要先對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)存使用情況和窗口大小對算法的影響及準(zhǔn)確率等方面對比本文提出的CUE算法和AWE算法的差異。在本實(shí)驗(yàn)中，AWE的基分類器通過訓(xùn)練VFDT得到。

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

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

(1) 美國聯(lián)邦森林覆蓋類型數(shù)據(jù)集：它是真實(shí)的數(shù)據(jù)集，該數(shù)據(jù)源于美國林業(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所示。隨著決策樹的增長，會(huì)產(chǎn)生更多的中間節(jié)點(diǎn)，每個(gè)中間節(jié)點(diǎn)都有一棵替代的子樹。 存儲(chǔ)和處理這些子樹也需要很多時(shí)間，因此限制樹的深度有助于提高算法的效率。這個(gè)實(shí)驗(yàn)中，限制決策樹的最大深度為8。

(1) 時(shí)間效率

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

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

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

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

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

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

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

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

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)存情況?？梢钥闯觯珻UE消耗的內(nèi)存比AWE多。CVFDT隨著數(shù)據(jù)增多逐漸增長，特別是當(dāng)數(shù)據(jù)集的屬性越多，可以替代的子樹和中間節(jié)點(diǎn)就越多，則需要更多的內(nèi)存來存儲(chǔ)這些子樹。 另外，CUE在基分類器的更新過程中提供裝袋抽樣，需要額外內(nèi)存存儲(chǔ)副本。隨著數(shù)據(jù)量的增加，CUE能夠符合數(shù)據(jù)流挖掘的內(nèi)存約束，因?yàn)镃UE算法在運(yùn)行過程中占用的內(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)確率都突然下降。接下來準(zhǔn)確率再次提升，且CUE有較快的提升速度。

為了形成突變漂移概念，從森林覆蓋數(shù)據(jù)集的開頭和中間提取連續(xù)的15 000條數(shù)據(jù)，尾部提取20 000條數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，結(jié)果如圖8所示。從圖8中可以看出，兩種算法的準(zhǔn)確度在加工數(shù)據(jù)在15 000條時(shí)開始迅速下降，然后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)確率對比

Fig.8 Comparison of accuracy on Forest CoverType data set

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

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

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

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

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

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

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

通過兩個(gè)實(shí)驗(yàn)的對比可以看出，CUE算法不用擔(dān)心訓(xùn)練數(shù)據(jù)不足的問題并且能更快適應(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)練好的分類器對數(shù)據(jù)流進(jìn)行分類；(3) 剪枝表現(xiàn)比較差的基分類器，訓(xùn)練新的基分類器來替換差的基分類器。

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)練決策樹作為基分類器，并將訓(xùn)練好的基分類器添加到集成模型中，最多能夠容納的基分類器的個(gè)數(shù)為L。循環(huán)該過程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 使用集成分類模型來進(jìn)行分類

用DCSC算法對數(shù)據(jù)流進(jìn)行分類由兩部分組成：首先采用歐幾里德距離計(jì)算每個(gè)基分類器對應(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ù)塊所對應(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è)簇的過程描述如圖11所示。具體處理流程如算法3所示。其中， distance(centroidi, record) 表示簇質(zhì)心與實(shí)例record之間的距離。choose_min_k(disti)是為了找出與實(shí)例record距離最近的k個(gè)質(zhì)心，計(jì)算p值并將其作為選擇分類器的依據(jù)。

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

輸入： INFO cluster (簇的信息)

Ensemble (基分類器集合)

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

輸出： label (分類器對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)分布變化的問題，去除表現(xiàn)不佳的基分類器，使用最近數(shù)據(jù)訓(xùn)練新的基分類器加入到集成模型中。

算法的更新頻率影響算法的效率。為了平衡算法的效率和更新頻率，DCSC算法在每處理一個(gè)數(shù)據(jù)塊之后，通過分類準(zhǔn)確率accuracy和分類數(shù)據(jù)塊時(shí)分類器被選擇的次數(shù)used_times來去除表現(xiàn)不佳的基分類器。MIN_FREQUENCY表示被選擇的最小次數(shù)， MIN_ACCURACY表示最小準(zhǔn)確率。如果在數(shù)據(jù)塊的處理之后選擇分類器的次數(shù)低于MIN_FREQUENCY，則表明分類器對整個(gè)集成模型的貢獻(xiàn)很小，與當(dāng)前概念有較大差異，應(yīng)該將其移除。如果選擇分類器的次數(shù)大于MIN_FREQUENCY，準(zhǔn)確率低于LOW_ACCURACY，表明該分類器不適應(yīng)當(dāng)前的概念并且應(yīng)當(dāng)移除該分類器。最后，通過訓(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ù)塊，首先對數(shù)據(jù)塊進(jìn)行聚類，然后訓(xùn)練分類器。分類器學(xué)到的規(guī)則越詳細(xì)，這些實(shí)例的分類準(zhǔn)確度就越高。 選擇基分類器之后，使用該分類器對實(shí)例進(jìn)行分類，并將結(jié)果用作實(shí)例的最終類標(biāo)簽。 完整描述如算法5所示。

算法5DCSC算法

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

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

算法描述：

數(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ù)集來模擬。

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

圖12顯示不同k值對準(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觀測點(diǎn)5 000Tree_height決策樹的高度8Grace_period分裂一個(gè)節(jié)點(diǎn)需要的最少的數(shù)據(jù)量200MIN_FREQUENCY基分類器最少被選中的次數(shù)50MIN_ACCURACY基分類器的最低準(zhǔn)確率/%70MAX_REPEATK-means最多迭代的次數(shù)100

圖12 不同k值對準(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í)而長，時(shí)而短。 這是因?yàn)镈CSC算法先進(jìn)行聚類分析，并存儲(chǔ)聚類結(jié)果，再對數(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)行決策樹的訓(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í)間長。

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

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

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

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

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

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

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

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

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需要對數(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)增長。 這表明DCSC算法可以有效地挖掘數(shù)據(jù)流，因?yàn)樵跀?shù)據(jù)流挖掘中存儲(chǔ)容量有限，DCSC滿足這一限制條件。

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

Fig.17 Comparison of memory usage on SEA data set

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

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

(4) 準(zhǔn)確率

對于SEA數(shù)據(jù)集，DCSC算法的準(zhǔn)確率始終高于AWE算法，如圖19所示。這是由于DCSC算法構(gòu)造出的模型只從集成模型中選擇一個(gè)基分類器來對分類的實(shí)例進(jìn)行分類，歷史數(shù)據(jù)對分類不產(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算法在對待分類的實(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ù)對數(shù)據(jù)流在相對平緩的環(huán)境下有較大的貢獻(xiàn)，結(jié)合每個(gè)基分類器的結(jié)果，產(chǎn)生較高的準(zhǔn)確率。DCSC當(dāng)突變漂移發(fā)生時(shí)只選擇一個(gè)基分類器對分類實(shí)例進(jìn)行分類，能夠更快地適應(yīng)概念漂移的數(shù)據(jù)流而不受到歷史數(shù)據(jù)的影響。

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

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

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

3 結(jié)束語

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

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