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

張育培，劉樹慧

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

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

張育培，劉樹慧

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

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

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

1 引言

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

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

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

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

2.1 問題描述

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

2.2 概念定義

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

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

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

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

2.3 特征選擇原理

利用特征選擇技術(shù)可去除重復冗余的噪特征，降低分類時間復雜度。本文認為噪特征對CFS的依賴度要低于關(guān)鍵特征對CFS的依賴度，可由互信息準則[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ā)生必導致概念漂移的發(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。其次，機器學習建立數(shù)據(jù)模型是找到對訓練數(shù)據(jù)擬合的模型M(f1,f2,…,fp)，而建立的模型M必定對關(guān)鍵度大的數(shù)據(jù)特征具有偏置性，因此Mi≠Mi+1。再者，由文獻[2]知,若相鄰數(shù)據(jù)段是由不同模型產(chǎn)生，則在這兩段數(shù)據(jù)中發(fā)生概念漂移。故特征漂移的發(fā)生必將導致概念漂移的發(fā)生。定理證畢。

□

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

定理3數(shù)據(jù)流S中，多數(shù)發(fā)生概念漂移的情況會導致發(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]。而本文認為數(shù)據(jù)分布發(fā)生變化有兩個原因：數(shù)據(jù)分布質(zhì)心發(fā)生移動和數(shù)據(jù)分布半徑發(fā)生變化。

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

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

□

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

3 特征選擇UFF和ECFD算法

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

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

(1)

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

算法1UFF算法

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

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

1： whileF≠null do

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

3：endwhile

4：whileUFFS≠nulldo

5： num++；

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

8：CFS=num_top_highest-1；

9： end if

10： end while

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

3.2 ECFD算法

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

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

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

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

算法2ECFD學習算法

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

輸出：ECFD集成分類器。

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

2： whileS≠null do

3： ifLen(W)

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

5： else

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

7： ifCFSi≠CFSi+1then

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

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

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

11：else

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

13： 以CSi再訓練ECFD中同特征FCnum次;

14： end if

15： end if

16： end while

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

(2)

算法3ECFD分類算法

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

輸出：d的類標矩陣C=[c1c2…ck]及最大類標號。

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

2： forFCi∈ECFD

3： ifFCi分類為Ctthen

4：ct=ct+wi

5： end if

6： end for

7： 返回向量C和類標號argmax(C);

3.3 算法性能分析及比較

3.3.1 算法時間復雜度

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

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

(3)

3.3.2 算法精度和抗噪性

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

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

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

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

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

4 實驗分析

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

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

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

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

4.2 結(jié)果與分析

4.2.1 特征選擇

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

Table 1 Critical feature selection

4.2.2 概念漂移

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

Table 2 Dection of concept drifting

4.2.3 性能比較

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

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

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

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

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

Table 3 Algorithm comparison on precision and time

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

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

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

5 結(jié)束語

本文提出了一種基于特征漂移的數(shù)據(jù)流集成分類方法(ECFD)，首先給出特征漂移的概念及其與概念漂移的關(guān)系，論證了可以通過檢測特征漂移來檢測概念漂移的原理；然后為應(yīng)對數(shù)據(jù)流特性，利用互信息理論提出無監(jiān)督特征選擇UFF技術(shù)并檢測概念漂移；最后提出了ECFD的學習算法，并根據(jù)改造后的權(quán)值計算方法給出ECFD分類算法。ECFD充分利用數(shù)據(jù)流的特性比較成功地解決數(shù)據(jù)流難題，且特征選擇算法和基礎(chǔ)分類算法是可選的,為隱含概念漂移的數(shù)據(jù)流分類展示了一個新思路。理論分析和實驗結(jié)果都表明ECFD算法具有更高的分類精度和更好的抗噪性。但是，對該方法的研究才剛開始，對特征選擇算法的穩(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中國計算機大會(CNCC2014)征文通知

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

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

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

征稿范圍(但不限于)

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

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

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

投稿方式

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

論文模板：中文論文模板

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

聯(lián)系：cncc_pr@ccf.org.cn(請在郵件標題中注明“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會員(E200027694G),研究方向為機器學習與數(shù)據(jù)挖掘。E-mail:zzuiezhyp@163.com

通信地址：450052 河南省鄭州市大學路75號鄭州大學信息工程學院

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