張育培，劉樹慧

(鄭州大學(xué)信息工程學(xué)院,河南 鄭州 450052)

基于特征漂移的數(shù)據(jù)流集成分類方法*

張育培，劉樹慧

(鄭州大學(xué)信息工程學(xué)院,河南 鄭州 450052)

為構(gòu)建更加有效的隱含概念漂移數(shù)據(jù)流分類器，依據(jù)不同數(shù)據(jù)特征對(duì)分類關(guān)鍵程度不同的理論，提出基于特征漂移的數(shù)據(jù)流集成分類方法(ECFD)。首先，給出了特征漂移的概念及其與概念漂移的關(guān)系；然后，利用互信息理論提出一種適合數(shù)據(jù)流的無監(jiān)督特征選擇技術(shù)(UFF)，從而析取關(guān)鍵特征子集以檢測(cè)特征漂移；最后，選用具有概念漂移處理能力的基礎(chǔ)分類算法，在關(guān)鍵特征子集上建立異構(gòu)集成分類器，該方法展示了一種隱含概念漂移高維數(shù)據(jù)流分類的新思路。大量實(shí)驗(yàn)結(jié)果顯示，尤其在高維數(shù)據(jù)流中，該方法在精度、運(yùn)行速度及可擴(kuò)展性方面都有較好的表現(xiàn)。

特征選擇；特征漂移；概念漂移；數(shù)據(jù)流；互信息；集成分類器

1 引言

近年來，隱含概念漂移的數(shù)據(jù)流分類問題引起了人們重視，并得到廣泛研究。文獻(xiàn)[1,2]對(duì)數(shù)據(jù)流模型、存在的問題以及概念漂移定義做了詳細(xì)描述，為研究工作提供充分有力的概念模型支持。數(shù)據(jù)流分類工作，尤其高速高維數(shù)據(jù)流，需應(yīng)對(duì)“無限性”、“高速性”、“大數(shù)據(jù)量”和“概念漂移”。雖已有大量研究工作及成果，但仍然缺少有效處理概念漂移且高效的分類方法。

數(shù)據(jù)流分類工作大致分為兩類：?jiǎn)蝹€(gè)增量模型和自適應(yīng)集成分類器。單個(gè)增量模型是通過維持和持續(xù)更新一個(gè)單分類器去應(yīng)對(duì)數(shù)據(jù)流中的概念漂移[3]，但學(xué)習(xí)速度慢且分類精度低，而且難以處理高速高維數(shù)據(jù)流。自適應(yīng)集成分類器利用加權(quán)集成分類器在隱含概念漂移數(shù)據(jù)流分類中具有更高精度的特性[4]，將概念漂移對(duì)分類結(jié)果的影響削弱在共同決策中[5，6]，并利用最新或最有效分類器替換過時(shí)分類器[7]以確保分類器的先進(jìn)性。然而以往集成分類器，大多基于完整數(shù)據(jù)而難以處理高維數(shù)據(jù)流且時(shí)間復(fù)雜度高。另外，特征選擇技術(shù)是高維數(shù)據(jù)分類及文本分類領(lǐng)域的一個(gè)重要研究方向，能夠有效縮減數(shù)據(jù)維度、提高分類精度并增強(qiáng)結(jié)果可理解性，主要可以分為濾波器法[8，9]、嵌入式法[10]及結(jié)合法。濾波器法快速簡(jiǎn)單但精度低而嵌入式法精確卻復(fù)雜，故而產(chǎn)生了兩者結(jié)合法。文獻(xiàn)[11]提出基于特征選擇的隨機(jī)森林分類方法，文獻(xiàn)[12]提出針對(duì)文本分類的DFS特征過濾算法，文獻(xiàn)[13]提出基于支持向量機(jī)的特征選擇和分類方法。但是，都沒有考慮數(shù)據(jù)流特性因而不適于數(shù)據(jù)流分類。

本文首先描述了特征漂移概念及其與概念漂移的關(guān)系；然后提出無監(jiān)督特征選擇技術(shù)UFF(Unsupervised Feature Filter)，利用相鄰特征集的不同來判定特征漂移發(fā)生;最后選用具有概念漂移處理能力的概念自適應(yīng)快速?zèng)Q策樹CAFDT(Concept Adaptive Fast Decision Tree)和在線貝葉斯(OnlineNB)為基礎(chǔ)算法，依選定的特征子集構(gòu)建基礎(chǔ)分類器，進(jìn)而建立異構(gòu)集成分類器，提出了基于特征漂移的數(shù)據(jù)流集成分類方法ECFD(Ensemble Classifier for Feature Drifting)。大量對(duì)比實(shí)驗(yàn)結(jié)果表明，ECFD具有較低復(fù)雜度，且在精度、運(yùn)行速度及可擴(kuò)展性上都有較強(qiáng)的表現(xiàn)。

2 相關(guān)概念及原理

2.1 問題描述

數(shù)據(jù)流是按時(shí)間順序不斷到來的數(shù)據(jù)序列，可形式化表示為：S={d1,d2,…,dn,…}，其中di=[f1,f2,…,fp]是維度為p的數(shù)據(jù)點(diǎn)，而di所對(duì)應(yīng)的已知類標(biāo)號(hào)為c∈{c1,c2,…,ck}。數(shù)據(jù)流分類任務(wù)是根據(jù)先驗(yàn)事件構(gòu)建模型M且di的類標(biāo)號(hào)ci=M(di)，使得S新到數(shù)據(jù)點(diǎn)di+1的分類概率P(M(dk+1)=ck+1)≥1/2。當(dāng)維度p非常大時(shí)，可以選擇最具有數(shù)據(jù)信息的特征子集CFS?{f1,f2,…,fp}來構(gòu)建數(shù)據(jù)流分類模型M，從而降低時(shí)間復(fù)雜度。同時(shí)，若S中兩段數(shù)據(jù)Sm和Sm+1具有不同的模型M，即MSm≠M(fèi)Sm+1，則利用MSm按時(shí)間順序?qū)m+1段的數(shù)據(jù)分類是不正確的，稱此時(shí)發(fā)生概念漂移[2]。

2.2 概念定義

定義2(關(guān)鍵度)對(duì)工作窗口W中數(shù)據(jù)分類時(shí)，依特征fi劃分之后，子集合的類別純度越高說明fi越關(guān)鍵，因此可以用fi的信息熵來表示其關(guān)鍵度CD(Critical Degree)，即CD=H(W|fi)。關(guān)鍵度達(dá)到閾值的特征，稱為關(guān)鍵特征；未達(dá)到閾值的特征，稱為噪特征。

定義3(關(guān)鍵特征集)對(duì)維度為p的數(shù)據(jù)流S分類時(shí)，從p個(gè)特征中選出對(duì)分類起關(guān)鍵作用的關(guān)鍵特征CF(Critical Feature)，也即析取關(guān)鍵度相對(duì)較高的特征，組成關(guān)鍵特征集CFS(Critical Feature Set)，即CFS?{f1,f2,…,fp}。

定義4(緩存窗口) 對(duì)工作窗口W的數(shù)據(jù)已經(jīng)完成特征選擇，但還未做分類，將此類數(shù)據(jù)暫存于緩存中以等待最終處理并交回?cái)?shù)據(jù)流S，稱這段緩存為緩存窗口(CW)。

定義7(特征分類器)選取具有概念漂移處理能力的基礎(chǔ)分類算法，依特征數(shù)據(jù)集CSw建立分類器，稱該分類器為特征分類器FC(Feature Classifier)。多個(gè)FC加權(quán)集成構(gòu)成集成分類器，稱為面向特征漂移的數(shù)據(jù)流集成分類器ECFD。

2.3 特征選擇原理

利用特征選擇技術(shù)可去除重復(fù)冗余的噪特征，降低分類時(shí)間復(fù)雜度。本文認(rèn)為噪特征對(duì)CFS的依賴度要低于關(guān)鍵特征對(duì)CFS的依賴度，可由互信息準(zhǔn)則[14]來表示，為此本文給出定理1。

□

2.4 特征漂移與概念漂移

數(shù)據(jù)流S中，使用i和i+1表示相鄰工作窗口，若Wi和Wi+1的過程中發(fā)生特征漂移，也即特征選擇得到的關(guān)鍵特征集而CFSi≠CFSi+1，則S在Wi和Wi+1之中發(fā)生概念漂移，為此本文給出定理2。

定理2數(shù)據(jù)流S中，特征漂移的發(fā)生必導(dǎo)致概念漂移的發(fā)生。

證明首先，S中數(shù)據(jù)段Wi+Wi+1發(fā)生特征漂移，因此由特征漂移定義知CFSi≠CFSi+1，即取得最關(guān)鍵特征top_crii({f1,f2,…,fp})≠top_crii+1({f1,f2,…,fp})。于是由定理1可知{I1,I2,…,Ip}i≠{I1,I2,…,Ip}i+1，而互信息值由關(guān)鍵度CD得到，所以{CD1,CD2,…,CDp}i≠{CD1,CD2,…,CDp}i+1。其次，機(jī)器學(xué)習(xí)建立數(shù)據(jù)模型是找到對(duì)訓(xùn)練數(shù)據(jù)擬合的模型M(f1,f2,…,fp)，而建立的模型M必定對(duì)關(guān)鍵度大的數(shù)據(jù)特征具有偏置性，因此Mi≠M(fèi)i+1。再者，由文獻(xiàn)[2]知,若相鄰數(shù)據(jù)段是由不同模型產(chǎn)生，則在這兩段數(shù)據(jù)中發(fā)生概念漂移。故特征漂移的發(fā)生必將導(dǎo)致概念漂移的發(fā)生。定理證畢。

□

反之，數(shù)據(jù)流S中，相鄰數(shù)據(jù)段Wi和Wi+1分別由Mi和Mi+1產(chǎn)生且Mi≠M(fèi)i+1，則在數(shù)據(jù)段Wi+Wi+1中發(fā)生概念漂移，但是概念漂移的發(fā)生不一定會(huì)引起特征漂移的發(fā)生，為此本文給出定理3。

定理3數(shù)據(jù)流S中，多數(shù)發(fā)生概念漂移的情況會(huì)導(dǎo)致發(fā)生特征漂移。

證明設(shè)數(shù)據(jù)質(zhì)心為G(f1,f2,…,fp),數(shù)據(jù)半徑為R(f1,f2,…,fp)。數(shù)據(jù)段Wi+Wi+1中發(fā)生概念漂移，也即數(shù)據(jù)流S的數(shù)據(jù)分布發(fā)生改變[2]。而本文認(rèn)為數(shù)據(jù)分布發(fā)生變化有兩個(gè)原因：數(shù)據(jù)分布質(zhì)心發(fā)生移動(dòng)和數(shù)據(jù)分布半徑發(fā)生變化。

(3)Gi+1≠Gi且Ri+1≠Ri，某些數(shù)據(jù)特征的關(guān)鍵度必定發(fā)生了變化，數(shù)據(jù)整體質(zhì)心分散。

因此，概念漂移發(fā)生時(shí)，數(shù)據(jù)特征CD不一定發(fā)生變化。據(jù)實(shí)驗(yàn)統(tǒng)計(jì)，實(shí)際中第(3)種混合情形占85%以上，故多數(shù)概念漂移會(huì)致使某些特征關(guān)鍵度變化，從而使CFS改變，引發(fā)特征漂移。故而多數(shù)概念漂移會(huì)引發(fā)特征漂移。定理證畢。

□

由定理2和定理3得知，特征漂移是概念漂移的充分條件，且現(xiàn)實(shí)中多數(shù)概念漂移引發(fā)特征漂移，因此本文提出以處理特征漂移替代處理概念漂移，由數(shù)據(jù)分布半徑引起的概念漂移交給基礎(chǔ)分類器去處理。由此可降低分類復(fù)雜度和運(yùn)行時(shí)間，且可即時(shí)檢測(cè)到大部分概念漂移，從而提高分類精度。

3 特征選擇UFF和ECFD算法

3.1 特征選擇技術(shù)UFF

由定理1可知，計(jì)算各數(shù)據(jù)特征與余下特征集的互信息值，其中互信息值較大者擁有更大的關(guān)鍵度，本文選取最大的num個(gè)特征為關(guān)鍵特征集。而互信息的計(jì)算需要對(duì)數(shù)據(jù)特征熵進(jìn)行計(jì)算，本文采用文獻(xiàn)[15]的熵估計(jì)法：

(1)

其中,tik表示數(shù)據(jù)點(diǎn)di和第k個(gè)近鄰在一維子空間的歐幾里得距離；lik為數(shù)據(jù)點(diǎn)di與第k個(gè)近鄰在p-1維子空間的歐幾里得距離。由定理1和公式(1)，同時(shí)利用數(shù)據(jù)流“無限性”，通過已標(biāo)記數(shù)據(jù)和已構(gòu)造分類器驗(yàn)證精度確定關(guān)鍵特征的個(gè)數(shù)。本文提出特征選擇算法UFF，如算法1所示。

算法1UFF算法

輸入：數(shù)據(jù)集S，特征集F，已標(biāo)記數(shù)據(jù)T和已構(gòu)造分類器M，正隨機(jī)小數(shù)?。

輸出：關(guān)鍵特征集CFS。

1： whileF≠null do

2： 利用公式(1)計(jì)算特征fi的UFFStr值并按從小到大放入數(shù)組UFFS；

3：endwhile

4：whileUFFS≠nulldo

5： num++；

6： 將UFFS中num_top_highest個(gè)特征作為關(guān)鍵特征集，利用T和M計(jì)算分類精度Pi；

8：CFS=num_top_highest-1；

9： end if

10： end while

為了處理數(shù)據(jù)流，本文將UFF算法使用于工作窗口中，以窗口數(shù)據(jù)為數(shù)據(jù)集S。當(dāng)工作窗口數(shù)據(jù)點(diǎn)數(shù)目達(dá)到閾值時(shí)，便啟動(dòng)UFF算法進(jìn)行特征選擇，同時(shí)清空工作窗口W以繼續(xù)接收數(shù)據(jù)流S的數(shù)據(jù)，將W中的數(shù)據(jù)交予緩存窗口CW等待最終處理。當(dāng)相鄰工作窗口得到的關(guān)鍵特征集不相同時(shí)，就斷定此時(shí)有特征漂移發(fā)生。

3.2 ECFD算法

本文提出ECFD算法的目的是對(duì)隱含概念漂移的數(shù)據(jù)流進(jìn)行分類，該方法從特征漂移入手，并利用特征選擇技術(shù)析取關(guān)鍵特征集，構(gòu)建特征集成分類器，從而降低時(shí)間和空間復(fù)雜度，且提高分類精度。ECFD算法流程包含四個(gè)步驟，如圖1所示。

Figure 1 Algorithm of ECFD圖1 ECFD算法流程示意圖

(2)判斷是否有特征漂移發(fā)生。若CFSi=CFSi-1，則沒有特征漂移發(fā)生，即特征漂移檢測(cè)FD過程返回NO，此時(shí)需對(duì)具有CFSi的特征分類器特征漂移FC進(jìn)行再學(xué)習(xí)，使FC提高分類精度且獲取最近數(shù)據(jù)信息；若CFSi≠CFSi-1，則有特征漂移發(fā)生，即FD過程返回YES，此時(shí)需利用新得到的特征數(shù)據(jù)集CS訓(xùn)練新的特征分類器FCnew。

(3)特征集成分類器ECFD學(xué)習(xí)與實(shí)時(shí)更新。對(duì)特征分類器FC的再訓(xùn)練，本文采用文獻(xiàn)[16]所提出的平均距離測(cè)試泊松分布方法得到Poisson(1)的值num，對(duì)特征數(shù)據(jù)集CS中的數(shù)據(jù)擬合訓(xùn)練Num次。而對(duì)于ECFD的更新，首先找出其中精度最高的和最差的特征分類器，利用新得到的CS訓(xùn)練，并選用與精度最高分類器同樣的基礎(chǔ)算法，得到新的FCnew，然后將FCnew替換掉最差FC。據(jù)定理2和定理3及以上分析，提出特征集成分類器ECFD的學(xué)習(xí)算法，如算法2所示。

算法2ECFD學(xué)習(xí)算法

輸入：數(shù)據(jù)流S，集成分類器數(shù)目N，工作窗口尺寸Wl。

輸出：ECFD集成分類器。

1： 以N*Wl個(gè)數(shù)據(jù)點(diǎn)初始化ECFD;

2： whileS≠null do

3： ifLen(W)

4： 將數(shù)據(jù)點(diǎn)d加入W；

5： else

6： 執(zhí)行UFF得到FCSi及CSi;

7： ifCFSi≠CFSi+1then

8： 以CSi評(píng)估ECFD得出精度最高b-FC及其類型T和w-FC;

9： 以類型T和數(shù)據(jù)CSi訓(xùn)練新分類器n-FC;

10： 以n-FC替換w-FC;

11：else

12： 令num=Poisson(1)[16];

13： 以CSi再訓(xùn)練ECFD中同特征FCnum次;

14： end if

15： end if

16： end while

(4)利用加權(quán)投票對(duì)數(shù)據(jù)進(jìn)行分類。由于ECFD進(jìn)行了特征選擇，故依文獻(xiàn)[4]的集成分類器權(quán)值計(jì)算方法和本文特征度量值UFFStr的定義，提出如公式(2)所示的ECFD加權(quán)法。公式(2)以分類所用關(guān)鍵特征集中所有特征的特征度量值之和彌補(bǔ)特征選擇帶來的偏置性，從而使各分類對(duì)于所有數(shù)據(jù)特征相對(duì)公平；同時(shí)，使用文獻(xiàn)[4]所提出的方法來區(qū)別各分類器權(quán)值比例。

(2)

算法3ECFD分類算法

輸入：未分類數(shù)據(jù)點(diǎn)d。

輸出：d的類標(biāo)矩陣C=[c1c2…ck]及最大類標(biāo)號(hào)。

1： 依據(jù)公式(2)計(jì)算ECFD中所有FC的權(quán)值w;

2： forFCi∈ECFD

3： ifFCi分類為Ctthen

4：ct=ct+wi

5： end if

6： end for

7： 返回向量C和類標(biāo)號(hào)argmax(C);

3.3 算法性能分析及比較

3.3.1 算法時(shí)間復(fù)雜度

設(shè)v為屬性值的最大個(gè)數(shù)，c為類別的最大個(gè)數(shù)，l為樹最長(zhǎng)的路徑長(zhǎng)度,p為數(shù)據(jù)流維度，k為ECFD中包含特征分類器的數(shù)目。由于分類算法與以往算法只是權(quán)值公式的不同，所以這里只對(duì)ECFD學(xué)習(xí)算法進(jìn)行分析。初始化不計(jì)入持續(xù)學(xué)習(xí)時(shí)間,ECFD算法主要包含以下三個(gè)步驟。

因此，ECFD學(xué)習(xí)算法的時(shí)間復(fù)雜度為三者之和，合并轉(zhuǎn)換后如公式(3)所示。

(3)

3.3.2 算法精度和抗噪性

ECFD算法主動(dòng)處理概念漂移和過濾無用特征，從而減少不必要的算法運(yùn)行和縮小分類器的規(guī)模，進(jìn)而達(dá)到降低時(shí)間復(fù)雜度和增加分類精度的目的。

(1)概念漂移的檢測(cè)與處理。ECFD方法采用先檢測(cè)后處理的辦法，且有特征漂移和概念漂移的雙重檢測(cè)，大大提高檢測(cè)能力，從而提高分類精度，而目前多數(shù)方法是邊訓(xùn)練邊檢測(cè)給分類器學(xué)習(xí)造成巨大負(fù)擔(dān)且檢測(cè)效果不佳。

(2)對(duì)信息的提取能力。ECFD算法采用UFF特征提取方法，有效地利用了數(shù)據(jù)流的特性，從而使得不再像其他大多數(shù)方法一樣疲于應(yīng)對(duì)數(shù)據(jù)流的特性。雖然特征提取丟棄了一些數(shù)據(jù)信息，但是同時(shí)也提高了ECFD算法的抗噪性，因?yàn)殛P(guān)鍵特征含有大量對(duì)分類有益的信息，而噪特征則含有大量的噪聲信息。因而ECFD可以達(dá)到相對(duì)高的分類精度。

(3)分類策略。ECFD的分類策略采用加權(quán)投票方式，一定程度上矯正了權(quán)值的偏置性，對(duì)優(yōu)良的特征分類器更為有利，具有更好的公平性，從而更有利凸出正確類別。

總之，從理論上ECFD可以達(dá)到相對(duì)高的分類精度，且具有更好的抗噪性。

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

為了對(duì)ECFD算法全面測(cè)試，首先對(duì)UFF特征選擇與已有先進(jìn)技術(shù)進(jìn)行對(duì)比實(shí)驗(yàn)，然后對(duì)概念漂移檢測(cè)能力進(jìn)行檢驗(yàn)并做對(duì)比，最后對(duì)算法整體性能進(jìn)行測(cè)試對(duì)比。實(shí)驗(yàn)中，設(shè)置ECFD擁有10個(gè)特征分類器，工作窗口尺寸為1 000。運(yùn)行環(huán)境為雙核CPU主頻2.27 GHz，內(nèi)存2 GB，使用VS2010平臺(tái)C++編程實(shí)現(xiàn)。

4.1 數(shù)據(jù)集描述

(1)人工數(shù)據(jù)集。便于與其他方法對(duì)比，本文依托MOA軟件平臺(tái)[18]分別使用仿真數(shù)據(jù)流產(chǎn)生器和移動(dòng)超平面數(shù)據(jù)流產(chǎn)生器，產(chǎn)生含有突變概念漂移和緩慢概念漂移的數(shù)據(jù)集，大小為100 000，并分別記為SEA和HYP。

(2)真實(shí)數(shù)據(jù)集。為真實(shí)反映ECFD對(duì)網(wǎng)絡(luò)數(shù)據(jù)實(shí)時(shí)動(dòng)態(tài)處理情況，將入侵檢測(cè)競(jìng)賽數(shù)據(jù)庫(kù)KDDCup99模擬為數(shù)據(jù)流,大小為494 022；為了檢測(cè)ECFD的抗噪性，選用UCI的LED數(shù)據(jù)集，大小為100 000；另外，通過雅虎Web服務(wù)接口采集的提供者與商家的雅虎購(gòu)物數(shù)據(jù)庫(kù)，記為數(shù)據(jù)集YSD，大小為840 000； http://www.csie.ntu.edu.tw/cjlin/libsvmtools/datasets手寫識(shí)別數(shù)據(jù)集，記為HWD，大小為60 000。

4.2 結(jié)果與分析

4.2.1 特征選擇

為了驗(yàn)證UFF算法的特征選擇能力，分別在各數(shù)據(jù)集運(yùn)行KP-SVM[13]與FCBF[9]各50次并計(jì)算平均結(jié)果，如表1所示。由于KP-SVM和UFF是具體的嵌入式方法，而FCBF是獨(dú)立的過濾方法，所以FCBF要比KP-SVM和UFF高效。但是，從表1可以看到，KP-SVM和UFF得到的關(guān)鍵特征均數(shù)都要比FCBF要小，這是因?yàn)榍度胧教卣鬟x擇要比過濾器方法對(duì)特征的評(píng)估更加有效。同時(shí)，表1顯示了UFF具有與KP-SVM相當(dāng)甚至更好的特征選擇能力，但UFF利用了數(shù)據(jù)流的特性故而適合于對(duì)數(shù)據(jù)流的分類。關(guān)鍵特征選擇結(jié)果說明，ECFD方法中特征選擇UFF算法的有效性，能夠去除冗余數(shù)據(jù)屬性，且充分利用數(shù)據(jù)流的特性縮短了算法運(yùn)行時(shí)間，更利于對(duì)高維數(shù)據(jù)流的處理，進(jìn)而降低了分類器學(xué)習(xí)的時(shí)間復(fù)雜度。

Table 1 Critical feature selection

4.2.2 概念漂移

為了驗(yàn)證ECFD方法檢測(cè)概念漂移的能力，與文獻(xiàn)[19]所提出的PSCCD漂移檢測(cè)算法進(jìn)行對(duì)比，對(duì)所有數(shù)據(jù)集進(jìn)行特征漂移檢測(cè)50次，結(jié)果如表2所示。從表2可以看到，ECFD在ESEA、HYP和YSD數(shù)據(jù)集上誤報(bào)次數(shù)高于PSCCD，是因?yàn)镋CFD算法是通過檢測(cè)特征漂移達(dá)到概念漂移檢測(cè)的目的，由定理3也可以得知特征漂移檢測(cè)并不能完全檢測(cè)概念漂移，但是少部分非特征漂移的概念漂移由分類器處理。而表2中ECFD的失報(bào)次數(shù)要低于PSCCD，主要是因?yàn)镋CFD算法是每個(gè)窗口都能進(jìn)檢測(cè)，而PSCCD算法是通過統(tǒng)計(jì)積累檢測(cè)故而會(huì)大量失報(bào)持續(xù)時(shí)間短的概念漂移。從表2也可以看到，ECFD算法的概念漂移檢測(cè)能力和PSCCD的相當(dāng)，甚至更好，這是因?yàn)榇蠖鄶?shù)概念漂移是由特征漂移引起的?？傊?，不論是人工數(shù)據(jù)集還是真實(shí)數(shù)據(jù)集，ECFD方法都能夠有效地檢測(cè)概念漂移，且分類結(jié)果證明失報(bào)率在可以接受的范圍內(nèi)。

Table 2 Dection of concept drifting

4.2.3 性能比較

(1)為了清楚地看到ECFD方法的有效性，在數(shù)據(jù)集上以先測(cè)試后訓(xùn)練最后再丟棄的順序，分別與AWE(NB)[4]、AWE(C4.5)[4]、Bagging(NB)[17]和Bagging(CVFDT)[17]進(jìn)行對(duì)比。將ECFD及AWE算法和Bagging算法在所有數(shù)據(jù)集上運(yùn)行50次并計(jì)算平均結(jié)果，如表3所示。從表3中可以看出，除在KDDCup99數(shù)據(jù)集外，ECFD分類精度都高于其他算法，這是因?yàn)閷?shí)際中多數(shù)概念漂移是由特征漂移引起的，ECFD準(zhǔn)確地

檢測(cè)特征漂移同時(shí)使用了具有概念漂移檢測(cè)能力的算法構(gòu)建特征分類器，所以有著比其他算法更好的概念漂移處理能力。而在KDDCup99數(shù)據(jù)集上也有著不錯(cuò)的精度，但不如Bagging(CVFDT)，主要是由于ECFD方法使完整數(shù)據(jù)集轉(zhuǎn)為特征數(shù)據(jù)集，因而缺少一定的訓(xùn)練維度造成的。另外，從表3還可以看出，除兩個(gè)人工數(shù)據(jù)集外，ECFD方法運(yùn)行時(shí)間也較其他方法快，維度越高越能體現(xiàn)其時(shí)間效率，這主要是因?yàn)镋CFD使用UFF特征選擇使得構(gòu)建分類器更簡(jiǎn)單，說明ECFD方法更容易應(yīng)對(duì)高維數(shù)據(jù)流。而在兩個(gè)低維模擬數(shù)據(jù)集上，ECFD特征選擇的時(shí)間相對(duì)構(gòu)建分類器來說比較大，從而該方法時(shí)效性不如Bagging(NB)?？傊?，實(shí)驗(yàn)結(jié)果也充分證實(shí)了文中對(duì)算法分析的結(jié)論，不論是人工數(shù)據(jù)集還是真實(shí)數(shù)據(jù)集，ECFD方法都有較高的分類精度和時(shí)間效率。

(2)為了驗(yàn)證ECFD算法在特征選擇之后數(shù)據(jù)流分類中的優(yōu)勢(shì)，與ACE集成分類算法[11]和KP-SVM分類算法[13]分別在各數(shù)據(jù)集上運(yùn)行50次，同樣ACE算法取10個(gè)分類器集成，結(jié)果如圖2所示。

Figure 2 Result of kinds of dataset with concept drifting圖2 含漂移各數(shù)據(jù)集

圖2說明ECFD算法在各實(shí)驗(yàn)數(shù)據(jù)集上的分類精度均高于其他兩者，而ACE算法的分類精度要高于KP-SVM，這主要是因?yàn)閿?shù)據(jù)集中隱含有概念漂移，而ECFD主動(dòng)處理概念漂移，ACE由于

Table 3 Algorithm comparison on precision and time

集成分類器而對(duì)概念漂移有一定應(yīng)對(duì)能力，KP-SVM沒有考慮概念漂移。但是，該實(shí)驗(yàn)還表明ECFD算法運(yùn)行速度要低于其他兩者，這是因?yàn)镋CFD特征選擇完之后需要去尋找合適的特征集數(shù)目。因此，ECFD可高精度處理隱含概念漂移的數(shù)據(jù)流分類。

(3)為了驗(yàn)證ECFD的抗噪性，本文選用HYP數(shù)據(jù)集和KDDCup99數(shù)據(jù)集分別加入5%、10%、15%、20%和25%的噪聲數(shù)據(jù)，各算法分別運(yùn)行50次并計(jì)算分類精度均值，如圖3和圖4所示。圖3中隨噪聲數(shù)據(jù)的增多，ECFD分類精度下降約17%，而其他算法的下降都大于20%；同時(shí)，圖4中隨噪聲數(shù)據(jù)的增多，ECFD分類精度下降約10%，而其他算法的下降都大于16%，且在噪聲數(shù)據(jù)達(dá)到20%以及更高時(shí)，ECFD精度超過了Bagging(CVFDT)。實(shí)驗(yàn)表明，ECFD算法比其他算法具有更好的抗噪性，這是因?yàn)镋CFD做了特征選擇而使得噪特征的噪聲對(duì)該算法沒有大的影響。

Figure 3 Result of dataset HYP圖3 HYP數(shù)據(jù)集

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

本文提出了一種基于特征漂移的數(shù)據(jù)流集成分類方法(ECFD)，首先給出特征漂移的概念及其與概念漂移的關(guān)系，論證了可以通過檢測(cè)特征漂移來檢測(cè)概念漂移的原理；然后為應(yīng)對(duì)數(shù)據(jù)流特性，利用互信息理論提出無監(jiān)督特征選擇UFF技術(shù)并檢測(cè)概念漂移；最后提出了ECFD的學(xué)習(xí)算法，并根據(jù)改造后的權(quán)值計(jì)算方法給出ECFD分類算法。ECFD充分利用數(shù)據(jù)流的特性比較成功地解決數(shù)據(jù)流難題，且特征選擇算法和基礎(chǔ)分類算法是可選的,為隱含概念漂移的數(shù)據(jù)流分類展示了一個(gè)新思路。理論分析和實(shí)驗(yàn)結(jié)果都表明ECFD算法具有更高的分類精度和更好的抗噪性。但是，對(duì)該方法的研究才剛開始，對(duì)特征選擇算法的穩(wěn)定性及算法框架的完整性有待研究，這將是下一步的研究方向。

[1] Babcock B, Babu S, Datar M, et al. Models and issues in data stream systems [C]∥Proc of ACM PODS, 2002:16-24.

[2] Tsymbal A. The problem of concept drift:Definitions and related work [R]. TCD-CS-2004-15. Ireland:Trinity College Dublin, Department of Computer Science, 2004.

[3] Hulten G, Spencer L, Domingos P. Mining time-changing data streams [C]∥Proc of ACM SIGKDD, 2001:97-106.

[4] Wang H, Fan W, YU P S, et al. Mining concept-drifting data streams using ensemble classifiers [C]∥Proc of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003:226-235.

[5] Masud M M, Gao J, Han J, et al. Classification and novel class detection in concept-drifting data streams under time constraints[J]. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(6):859-874.

[6] Zhang P, Zhu X, Tan Jian-long, et al. Classifier and cluster ensembles for mining concept drifting data streams [C]∥Proc of IEEE International Conference on Data Ming, 2010:1175-1180.

[7] Sattar H, Ying Y, Zahra M, et al. Adapted one-vs-all decision tree for data stream classification [J]. IEEE Transactions on Knowledge and Data Engineering, 2009, 21(5):624-637.

[8] Inza I, Larranaga P, Blanco R, et al. Filter versus wrapper gene selection approaches in DNA microarray domains[J]. Artificial Intelligence in Medicine, 2004, 31(2):91-103.

[9] Lei Y, Huan L. Feature selection for high-dimensional data:A fast correlation-based filter solution[C]∥Proc of the 20th ICML’03, 2003:856-863.

[10] Hsu W H. Genetic wrappers for feature selection in decision tree induction and variable ordering in Bayesian network structure learning[J]. Information Sciences, 2004, 163(1-3):103-122.

[11] Tuv E, Borisov A, Runger G, et al. Feature selection with ensembles, artificial variables, and redundancy elimination[J].Journal of Machine Learning Research, 2009, 10:1341-1366.

[12] Alper K U, Serkan G, A novel probabilistic feature selection method for text classification[J]. Knowledge-Based Systems,2012, 36:226-235.

[13] Maldonado S, Webber R, Basak J. Simultaneous feature selection and classification using kernel-penalized support vector machines [J]. Information Sciences, 2011, 181(1):115-128.

[14] Cover T M, Thomas J A. Elements of information theory[M]. New York:Wiley-Interscience, 1991.

[15] Goria M, Leonenko N, Mergel V, et al.A new class of random vector entropy estimators and its applications in testing statistical hypotheses[J]. Journal of Nonparametric Statistics, 2005 17(3):277-297.

[16] Gabor J S, Maria L R. Mean distance test of poisson distribution [J]. Statistics & Probability Letters, 2004, 67(3):241-247.

[17] Breiman L. Bagging predictors [J]. The Journal of Machine Learning Research, 1996,24(2):123-140.

[18] Bifet A, Holmes G, Kirkby R. MOA:Massive online analysis [J]. The Journal of Machine Learning Research, 2010,11:1601-1604.

[19] Niloofar M,Sattar H,Ali H.A precise statistical approach for concept change detection in unlabeled data streams [J]. Computers and Mathematics with Applications, 2011, 62:1655-1669.

ZHANGYu-pei,born in 1985,MS candidate，CCF member(E200027694G),his research interests include machine learning, and data mining.

2014中國(guó)計(jì)算機(jī)大會(huì)(CNCC2014)征文通知

第十一屆CCF中國(guó)計(jì)算機(jī)大會(huì)(CCF China National Computer Congress，CCF CNCC 2014)將于2014年10月23～25日在河南鄭州國(guó)際會(huì)展中心舉行，承辦單位是信息工程大學(xué)。CNCC是由中國(guó)計(jì)算機(jī)學(xué)會(huì)(CCF)于2003年創(chuàng)建的系列學(xué)術(shù)會(huì)議，已在不同的城市舉辦十屆，現(xiàn)每年一次。

CNCC旨在探討計(jì)算機(jī)及相關(guān)領(lǐng)域最新進(jìn)展和宏觀發(fā)展趨勢(shì)，展示中國(guó)學(xué)術(shù)界、企業(yè)界最重要的學(xué)術(shù)、技術(shù)事件和成果，使不同領(lǐng)域的專業(yè)人士能夠獲得探討交流的機(jī)會(huì)并獲得所需信息。CNCC2014將有逾2000人參會(huì)交流，有近百項(xiàng)科研成果進(jìn)行展示，是中國(guó)IT領(lǐng)域的一次盛會(huì)。

CNCC2014現(xiàn)公開征集會(huì)議論文，征文范圍涵蓋計(jì)算機(jī)領(lǐng)域各方向，要求是沒有公開發(fā)表過的原創(chuàng)性論文。本次大會(huì)不出版會(huì)議論文集，擬挑選不超過50篇的優(yōu)秀論文刊登在《計(jì)算機(jī)學(xué)報(bào)》上，其他錄用論文將推薦到《小型微型計(jì)算機(jī)系統(tǒng)》、《計(jì)算機(jī)科學(xué)》、《計(jì)算機(jī)工程與應(yīng)用》、《計(jì)算機(jī)工程與科學(xué)》等CCF會(huì)刊發(fā)表?！队?jì)算機(jī)學(xué)報(bào)》和《小型微型計(jì)算機(jī)系統(tǒng)》錄用文章將在2014年10月發(fā)表。

征稿范圍(但不限于)

(1)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)：高性能計(jì)算、CPU設(shè)計(jì)與多核處理器技術(shù)、 計(jì)算機(jī)網(wǎng)絡(luò)與新一代互聯(lián)網(wǎng)、 傳感器網(wǎng)絡(luò)和物聯(lián)網(wǎng)、 物理信息融合系統(tǒng)、 對(duì)等計(jì)算與網(wǎng)格計(jì)算、 云計(jì)算與數(shù)據(jù)中心網(wǎng)絡(luò)、 網(wǎng)絡(luò)存儲(chǔ)系統(tǒng)、 網(wǎng)絡(luò)安全、 信息與內(nèi)容安全。

(2)計(jì)算機(jī)軟件與理論:計(jì)算機(jī)科學(xué)理論、 程序設(shè)計(jì)語(yǔ)言與編譯技術(shù)、 軟件測(cè)試、 形式化方法、 操作系統(tǒng)與系統(tǒng)軟件、 數(shù)據(jù)庫(kù)技術(shù)、 數(shù)據(jù)挖掘、 內(nèi)容檢索、 軟件工程。

(3)計(jì)算機(jī)應(yīng)用技術(shù):人工智能與模式識(shí)別、 機(jī)器學(xué)習(xí)、 知識(shí)工程、 智能控制技術(shù)、 圖形學(xué)與人機(jī)交互、 虛擬現(xiàn)實(shí)與可視化技術(shù)、 多媒體技術(shù)、 中文信息技術(shù)、 電子政務(wù)與電子商務(wù)、 生物信息學(xué)。

投稿方式

稿件內(nèi)容要求以中文書寫，并隱去作者姓名和單位，請(qǐng)?zhí)峤籔DF文件

論文模板：中文論文模板

大會(huì)網(wǎng)站：http://cncc.ccf.org.cn(請(qǐng)務(wù)必正確注冊(cè)郵箱，并填寫詳細(xì)個(gè)人信息，包括聯(lián)系電話以及通訊地址，以便聯(lián)絡(luò)論文修改和寄發(fā)錄用通知等事宜，如信息不全，將會(huì)影響論文評(píng)審。)

聯(lián)系：cncc_pr@ccf.org.cn(請(qǐng)?jiān)卩]件標(biāo)題中注明“CNCC2014征文”)

重要日期

論文提交截止日期:2014年5月10日 錄用通知發(fā)出日期:2014年8月1日

CNCC召開日期：2014年10月23日～25日

Ensembleclassificationbasedonfeaturedriftingindatastreams

ZHANG Yu-pei,LIU Shu-hui

(School of Information Engineering,Zhengzhou University,Zhengzhou 450052,China)

In order to construct an effective classifier for data streams with concept drifting,according to the theory that different data feature has different critical degree for classification,a method of Ensemble Classifier for Feature Drifting in data streams (ECFD) is proposed. Firstly,the definite of feature drifting and the relationship between feature drifting and concept drifting is given.Secondly,mutual information theory is used to propose an Unsupervised Feature Filter (UFF) technique,so that critical feature subsets are extracted to detect feature drifting.Finally, the basic classified algorithms with the capability of handling concept drifting is chosen to construct heterogeneous ensemble classifier on the basis of critical feature subsets. This method exhibits a new idea of way to high-dimensional data streams with hidden concept drifting.Experimental results show that the method has strong appearance in accuracy, speed and scalability, especially for high-dimensional data streams.

feature selection;feature drifting;concept drifting;data stream;mutual information;ensemble classifier

1007-130X(2014)05-0977-09

2012-12-17;

：2013-02-18

TP274

：A

10.3969/j.issn.1007-130X.2014.05.032

張育培(1985-),男,河南嵩縣人，碩士生，CCF會(huì)員(E200027694G),研究方向?yàn)闄C(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘。E-mail:zzuiezhyp@163.com

通信地址：450052 河南省鄭州市大學(xué)路75號(hào)鄭州大學(xué)信息工程學(xué)院

Address:School of Information Engineering,Zhengzhou University,75 Daxue Rd,Zhengzhou 450052,Henan,P.R.China