基于在線遷移學(xué)習(xí)的重現(xiàn)概念漂移數(shù)據(jù)流分類

文益民　唐詩淇　馮　超　高　凱

1(桂林電子科技大學(xué)計(jì)算機(jī)與信息安全學(xué)院　廣西桂林　541004)2(廣西可信軟件重點(diǎn)實(shí)驗(yàn)室(桂林電子科技大學(xué))　廣西桂林　541004)3(廣西信息科學(xué)實(shí)驗(yàn)中心(桂林電子科技大學(xué))　廣西桂林　541004)4　　　(河北科技大學(xué)信息學(xué)院　石家莊　050018)

?

基于在線遷移學(xué)習(xí)的重現(xiàn)概念漂移數(shù)據(jù)流分類

文益民1,2,3唐詩淇1馮超1高凱4

1(桂林電子科技大學(xué)計(jì)算機(jī)與信息安全學(xué)院廣西桂林541004)2(廣西可信軟件重點(diǎn)實(shí)驗(yàn)室(桂林電子科技大學(xué))廣西桂林541004)3(廣西信息科學(xué)實(shí)驗(yàn)中心(桂林電子科技大學(xué))廣西桂林541004)4(河北科技大學(xué)信息學(xué)院石家莊050018)

(ymwen2004@aliyun.com)

隨著大數(shù)據(jù)時(shí)代的到來，數(shù)據(jù)流分類被應(yīng)用于諸多領(lǐng)域，如：垃圾郵件過濾、市場預(yù)測及天氣預(yù)報(bào)等.重現(xiàn)概念是這些應(yīng)用領(lǐng)域的重要特點(diǎn)之一.針對重現(xiàn)概念的學(xué)習(xí)與分類問題中的“負(fù)遷移”和概念漂移檢測的滯后性，提出了一種基于在線遷移學(xué)習(xí)的重現(xiàn)概念漂移數(shù)據(jù)流分類算法——RC-OTL.RC-OTL在檢測到概念漂移時(shí)存儲剛學(xué)習(xí)的一個(gè)基分類器，然后計(jì)算最近的樣本與存儲的各歷史分類器之間的領(lǐng)域相似度，以選擇最適合對后續(xù)樣本進(jìn)行學(xué)習(xí)的源分類器，從而改善從源領(lǐng)域到目標(biāo)領(lǐng)域的知識遷移.另外，RC-OTL還在概念漂移檢測之前根據(jù)分類準(zhǔn)確率選擇合適的分類器對后續(xù)樣本分類.初步的理論分析解釋了RC-OTL為什么能有效克服“負(fù)遷移”，實(shí)驗(yàn)結(jié)果進(jìn)一步表明：RC-OTL的確能有效提高分類準(zhǔn)確率，并且在遭遇概念漂移后能更快地適應(yīng)后續(xù)樣本.

概念漂移；遷移學(xué)習(xí)；重現(xiàn)概念；在線學(xué)習(xí)；負(fù)遷移

隨著大數(shù)據(jù)時(shí)代的到來，數(shù)據(jù)流分類算法被應(yīng)用于許多領(lǐng)域.比如：天氣預(yù)報(bào)、信用卡欺詐分類、海嘯與地震的預(yù)測、商場對顧客購買興趣與偏好的掌控及產(chǎn)品質(zhì)量檢測等等.這些問題的共有特點(diǎn)是：不斷產(chǎn)生的數(shù)據(jù)形成流；數(shù)據(jù)流沒有終點(diǎn)；數(shù)據(jù)流中數(shù)據(jù)包含的概念隨時(shí)可能產(chǎn)生變化.數(shù)據(jù)流中這種概念的變化被稱為概念漂移[1].不同于傳統(tǒng)的機(jī)器學(xué)習(xí)算法，概念漂移數(shù)據(jù)流分類基于一個(gè)動態(tài)的學(xué)習(xí)環(huán)境，每當(dāng)概念發(fā)生變化后分類器必須進(jìn)行調(diào)整以適應(yīng)新到概念.特別是，有時(shí)某些概念會在數(shù)據(jù)流中重復(fù)出現(xiàn).比如：天氣隨季節(jié)而變化、客戶的購買興趣會受季節(jié)變化以及流行潮流變化的影響、股市行情的變化等.這種重復(fù)出現(xiàn)的概念被稱為重現(xiàn)概念.在概念漂移數(shù)據(jù)流分類中，如果事先存儲學(xué)習(xí)過的概念，當(dāng)概念重現(xiàn)時(shí)，就可以選擇這些存儲的歷史概念對新到樣本實(shí)施分類和學(xué)習(xí)，這必將大大減小分類器的學(xué)習(xí)花費(fèi)，并提升分類準(zhǔn)確率.

近些年來，在處理概念漂移數(shù)據(jù)流分類問題上取得了很多研究成果.Kuncheva等人[2]、Tsymbal等人[3]、王濤等人[4]、Zliobaite等人[5]、Hoens等人[6]、Gama等人[7-8]及文益民等人[9]先后對概念漂移數(shù)據(jù)流分類進(jìn)行了較深入的綜述.CVFDT[10]，AWE[11]，WMA[12]，DWM[13]，KnnM-IB[14]等算法有效地提升了數(shù)據(jù)流分類的準(zhǔn)確率.但是，這些分類算法都在檢測到概念漂移后，分類器需重新學(xué)習(xí)新到概念，原來學(xué)習(xí)到的分類器被丟棄.在有重現(xiàn)概念的數(shù)據(jù)流中，這將導(dǎo)致分類器學(xué)習(xí)重現(xiàn)概念的花費(fèi)較大，而且適應(yīng)重現(xiàn)概念的速度會更慢.為克服此弱點(diǎn)，處理重現(xiàn)概念漂移的數(shù)據(jù)流分類算法，如FLORA3[15]，EB[16]，EAE[17]，RCD[18]，CCP[19]，MM-DD[20]及MM-PRec[21]算法等，都在學(xué)習(xí)過程中存儲學(xué)習(xí)過的概念的相關(guān)信息，如樣本、分布特征或分類器等.當(dāng)檢測到重現(xiàn)概念后，通過檢索存儲的歷史概念的信息，以選擇適合重現(xiàn)概念的分類器以對后續(xù)樣本進(jìn)行分類和學(xué)習(xí).但是，當(dāng)后續(xù)樣本與所選擇的分類器不屬于同一分布時(shí)會產(chǎn)生“負(fù)遷移”現(xiàn)象，導(dǎo)致分類準(zhǔn)確率下降.另外，已有數(shù)據(jù)流分類算法一般都需收集到一定數(shù)量的新到樣本后再實(shí)施概念漂移檢測，然后才調(diào)整當(dāng)前分類器，從而無法避免概念漂移檢測的滯后性.若概念漂移發(fā)生在檢測之前，這會導(dǎo)致當(dāng)前分類器對新到樣本的分類準(zhǔn)確率降低.由于現(xiàn)有各種機(jī)器學(xué)習(xí)算法本質(zhì)上都是基于一個(gè)靜態(tài)學(xué)習(xí)環(huán)境，而以盡量保證學(xué)習(xí)系統(tǒng)之泛化能力為目標(biāo)的尋優(yōu)過程，以上這些問題給包含重現(xiàn)概念的數(shù)據(jù)流分類帶來了很大的挑戰(zhàn).

針對上面提到的這2個(gè)問題，在Zhao等人[22]提出的基于在線遷移學(xué)習(xí)的概念漂移學(xué)習(xí)算法——CDOL的啟發(fā)下，本文提出了一種基于在線遷移學(xué)習(xí)的重現(xiàn)概念漂移數(shù)據(jù)流分類算法——RC-OTL.RC-OTL做了3個(gè)方面的嘗試：

1) CDOL在檢測到概念漂移后才會調(diào)整“源”分類器.由于概念漂移檢測的滯后性，它可能會將剛學(xué)習(xí)過的概念作為源領(lǐng)域，從而導(dǎo)致“負(fù)遷移”.不同于CDOL，RC-OTL在檢測到概念漂移時(shí)，按照一定機(jī)制選擇一個(gè)基分類器作為歷史分類器存儲，再從存儲的各歷史分類器中選擇與新到樣本“負(fù)相似度”最小的基分類器作為“源”分類器，將其與一個(gè)新建的基分類器組合成一個(gè)集成分類器，以對后續(xù)樣本進(jìn)行在線學(xué)習(xí)，從而實(shí)現(xiàn)從某個(gè)歷史領(lǐng)域到新領(lǐng)域的知識遷移.

2) 證明了在“負(fù)遷移”較大的情形下HomOTL-I[22]能很快減弱“負(fù)遷移”的影響.這能解釋CDOL和RC-OTL為什么能有效克服“負(fù)遷移”.

3) 提出一個(gè)當(dāng)前分類器的調(diào)整算法以減少在檢測到概念漂移之前發(fā)生概念漂移導(dǎo)致的分類準(zhǔn)確率下降的程度.

1　相關(guān)工作

近年來，數(shù)據(jù)流中的概念重現(xiàn)問題引起了研究者的密切關(guān)注.Widmer等人[15]較早地注意到了數(shù)據(jù)流分類中的概念重現(xiàn)問題.他們提出的FLORA3使用3種基于“特征-值”對的描述項(xiàng)來表示和存儲概念.

Ramamurthy等人[16]提出了EB算法.EB每獲得一個(gè)數(shù)據(jù)塊D及各樣本的類別后，判斷分類器全局集合G中是否有分類器能較準(zhǔn)確地對D分類.若找不到這樣的分類器，則從G中選擇若干分類器構(gòu)成集成分類器，并判斷該集成分類器是否也能較準(zhǔn)確地對D分類，否則利用D訓(xùn)練一個(gè)新分類器加入G.這樣，當(dāng)概念重現(xiàn)時(shí)就可以從G中選擇到合適的分類器對后續(xù)樣本分類.Jackowski等人[17]提出了EAE算法.EAE使用存儲的分類器構(gòu)成集成分類器對新到樣本分類.當(dāng)分類準(zhǔn)確率發(fā)生變化時(shí)，EAE就把用新到樣本訓(xùn)練的分類器存儲.若進(jìn)一步檢測到概念漂移，EAE就利用進(jìn)化算法更新集成分類器，以使新的集成分類器更適合對后續(xù)樣本分類.Gon?alves等人[18]提出了一種處理重現(xiàn)概念漂移的算法框架RCD.RCD使用DDM[23]檢測概念漂移.當(dāng)處于警告狀態(tài)時(shí)，算法會另建一個(gè)備用分類器Cn學(xué)習(xí)新到樣本，同時(shí)將相應(yīng)的新到樣本存入緩存bn；當(dāng)檢測到概念漂移時(shí)，再采用多元非參統(tǒng)計(jì)方法判斷bn中的樣本是屬于已學(xué)習(xí)概念還是新概念.若是新概念，則將Cn存儲，并將當(dāng)前分類器調(diào)整為Cn；若屬于已學(xué)習(xí)概念，則利用bn從歷史分類器中選擇最合適的分類器作為當(dāng)前分類器.若在后續(xù)學(xué)習(xí)中沒有檢測到概念漂移，則刪除Cn和bn.Gomes等人[24]提出了一種基于語境信息的重現(xiàn)概念漂移數(shù)據(jù)流分類算法.該算法與RCD基本相似.不同之處在于：當(dāng)檢測到概念漂移時(shí)，計(jì)算Cn與存儲的歷史分類器的相似度，以判斷新到概念是否是重現(xiàn)概念.若非，則將Cn存儲，Cn作為當(dāng)前分類器；若是，則利用歷史分類器構(gòu)造一個(gè)集成分類器作為當(dāng)前分類器.Katakis等人[19]提出了CCP算法，CCP用概念向量表達(dá)和存儲多個(gè)概念.概念向量由樣本特征與類別間的概率關(guān)系組成.一個(gè)數(shù)據(jù)塊對應(yīng)一個(gè)概念向量，計(jì)算不同數(shù)據(jù)塊對應(yīng)的概念向量之間的距離，可判斷是否發(fā)生概念漂移或進(jìn)一步判斷是否是重現(xiàn)概念；如果是新概念，則將對應(yīng)的概念向量存儲.另外，通過概念向量的增量聚類可實(shí)現(xiàn)屬于同一概念的概念向量的合并.

與以上思路有些不同，Gama等人[20]、Angel等人[21]分別提出了基于元學(xué)習(xí)器與基學(xué)習(xí)器的分層框架.這2種分層框架的基本特點(diǎn)在于：使用基學(xué)習(xí)器對樣本進(jìn)行分類和學(xué)習(xí)；使用元學(xué)習(xí)器對概念漂移產(chǎn)生的情境，對應(yīng)每個(gè)概念的樣本及分類器的分類情況等進(jìn)行學(xué)習(xí).通過對概念間相似性的判斷，以選擇重現(xiàn)概念對應(yīng)的分類器重用.他們認(rèn)為使用元學(xué)習(xí)器比跟蹤新到樣本的分布或分類準(zhǔn)確率能更準(zhǔn)確地檢測到概念漂移.

遷移學(xué)習(xí)[25]是機(jī)器學(xué)習(xí)的熱門研究領(lǐng)域，已經(jīng)在推薦系統(tǒng)、文本分類等領(lǐng)域[26-27]取得很好的效果.它的基本思想是：當(dāng)目標(biāo)領(lǐng)域的知識獲取十分困難時(shí)，可以將相關(guān)源領(lǐng)域的知識遷移到目標(biāo)領(lǐng)域中輔助分類器學(xué)習(xí)目標(biāo)領(lǐng)域的知識.Zhao等人[22]較早地將遷移學(xué)習(xí)應(yīng)用于概念漂移數(shù)據(jù)流分類，提出了算法CDOL.在該算法中，當(dāng)前分類器由2個(gè)基分類器帶權(quán)組合而成，其中基分類器wt對應(yīng)新到概念，另一個(gè)ws對應(yīng)“源”概念.使用當(dāng)前分類器對新到樣本分類，獲得樣本類別后，按照遷移學(xué)習(xí)的思路更新當(dāng)前分類器.CDOL的特點(diǎn)在于：檢測到概念漂移后，ws被替換成ws與wt中的權(quán)值更大者.CDOL的不足之處在于：由于概念漂移檢測的滯后性，概念漂移產(chǎn)生時(shí)，它可能將剛學(xué)習(xí)過的舊概念作為源領(lǐng)域，這將導(dǎo)致較大“負(fù)遷移”.同時(shí)，CDOL不存儲學(xué)習(xí)過的歷史概念，不適應(yīng)有重現(xiàn)概念的數(shù)據(jù)流分類.本文受此啟發(fā)提出了基于在線遷移學(xué)習(xí)的重現(xiàn)概念漂移數(shù)據(jù)流分類算法——RC-OTL.

2　RC-OTL算法

2.1問題定義與遷移學(xué)習(xí)

定義數(shù)據(jù)流DS為按時(shí)間到達(dá)的T個(gè)樣本，也就是有：

DS={(xt,yt)|t=1,2,…,T}，

其中,(xt,yt)∈X×Y，X∈m，Y={-1,+1}.

設(shè)新到概念為Cnew，將其作為目標(biāo)領(lǐng)域.為將從歷史概念Cold上學(xué)習(xí)到的知識遷移到對新到概念的學(xué)習(xí)中，將歷史概念Cold設(shè)為源領(lǐng)域，記ws=wold，并新建分類器wt=0，將ws和wt作為基分類器加權(quán)組合為一個(gè)集成分類器f，作為當(dāng)前分類器對新到樣本進(jìn)行分類和學(xué)習(xí).新到樣本存入緩存PS中.f的定義如下：

(1)

其中α1和α2為基分類器的權(quán)重系數(shù).當(dāng)新建分類器f時(shí)初始化α1和α2為12，Π(z)為一個(gè)壓縮函數(shù)[22].

當(dāng)前分類器f每獲取到一個(gè)樣本xt及其真實(shí)類別yt后，使用(xt,yt)對分類器采用HomOTL-I的更新策略進(jìn)行更新，更新步驟如下：

2) 如果lt>0，則利用損失函數(shù)lt對wt進(jìn)行更新,即wt+1=wt+τytxt，其中τ=min(C,lt；

3)α1和α2的更新規(guī)則為

(2)

其中,st(w)=exp{-ηl*(Π(wTxt),Π(yt))}，η=0.5，?w∈m，l*(z,y)=(z-y)2，t為新到樣本序號.

2.2重現(xiàn)概念的檢測

在存在重現(xiàn)概念漂移的問題中，需要判斷新到概念是否發(fā)生概念漂移.若是概念漂移，則需進(jìn)一步判斷是學(xué)習(xí)過的歷史概念還是一個(gè)新概念.與CDOL類似，RC-OTL采取每隔p個(gè)樣本就進(jìn)行一次概念漂移檢測的策略.概念漂移檢測的方法可采取已有的各類概念漂移檢測算法.本文采取了Zhao等人[22]提出的OWA算法.若沒有檢測到概念漂移，則按照HomOTL-I算法繼續(xù)進(jìn)行在線學(xué)習(xí).

若檢測到了概念漂移，RC-OTL首先需將當(dāng)前分類器f的基分類器wt根據(jù)如下規(guī)則加入HS：設(shè)α1和α2為當(dāng)前分類器f中對應(yīng)基分類器ws和wt的權(quán)重系數(shù).若α1<α2，則將wt存入HS.然后，RC-OTL需要根據(jù)新到樣本集PS從HS中選擇最合適的基分類器作為“源”分類器，以便實(shí)現(xiàn)知識遷移.為從HS中選擇這樣的分類器，本文引入洪佳明等人[28]提出的一種當(dāng)目標(biāo)領(lǐng)域標(biāo)記樣本很少的情況下度量2個(gè)領(lǐng)域相似性的指標(biāo)——負(fù)相似度.他認(rèn)為2個(gè)領(lǐng)域的負(fù)相似度越小，則這2個(gè)領(lǐng)域越相似，其定義如下：

設(shè)PS(X,Y)和PT(X,Y)分別為源領(lǐng)域和目標(biāo)領(lǐng)域的概率分布.設(shè)ρ是一個(gè)小于1的正數(shù)，v為一正數(shù).若存在分類器F，使得F在PT(X,Y)上的泛化誤差小于ρ，且能以1-v的概率推斷，對于(x,y)～PS(X,Y)有F(x)=y成立，則稱PS以1-v的概率ρ-弱相似于PT，稱v為負(fù)相似度，記為v(F,PS,PT).負(fù)相似度的優(yōu)點(diǎn)在于：在已獲取的屬于新到概念的樣本很少的情況下就能選取合適的歷史分類器.

設(shè)HS={ws1,ws2,ws3,…,ws n,…}，參照以上定義，RC-OTL提出按照式(3)計(jì)算HS中各分類器的權(quán)值向量ws n與新到樣本集PS的負(fù)相似度：

(3)

其中，(xt,yt)∈PS，m為新到樣本的數(shù)量.選擇HS中與新到樣本集PS負(fù)相似度最小的權(quán)值向量ws i構(gòu)造線性分類器.一般情況下，它很可能是與后續(xù)樣本最領(lǐng)域相似的分類器.然后新建分類器wt=0，按照式(1)建立當(dāng)前分類器f，以對后續(xù)樣本實(shí)施分類和學(xué)習(xí).這樣能使得f對后續(xù)樣本的分類準(zhǔn)確率較高.

2.3負(fù)遷移的克服

證明. 當(dāng)t=2,3,…,T時(shí)，根據(jù)式(2)遞推可知：

令δ=min{δ2,δ3,…,δT}，則有：

證畢.

從定理1可以看出：“源”分類器對于目標(biāo)領(lǐng)域存在較大負(fù)遷移時(shí)，HomOTL-I算法將使“源”分類器的權(quán)重系數(shù)呈指數(shù)級衰減.因此，相比于RCD，由于RC-OTL以HomOTL-I算法為基本學(xué)習(xí)算法.在對概念漂移數(shù)據(jù)流分類時(shí)，RC-OTL能較有效地克服負(fù)遷移的影響.相比于同樣以HomOTL-I算法為基本學(xué)習(xí)算法的CDOL，RC-OTL會選擇負(fù)遷移更小的歷史分類器，從而能更快地適應(yīng)新概念.

2.4 當(dāng)前分類器的調(diào)整

RC-OTL還根據(jù)當(dāng)前分類器對每個(gè)窗口前半段樣本的分類錯(cuò)誤率e，判斷算法是否需要進(jìn)入當(dāng)前分類器調(diào)整階段.算法定義e如下：

其中，Nerr為當(dāng)前分類器對前半個(gè)窗口樣本的分類錯(cuò)誤數(shù)量，p為當(dāng)前窗口的長度.

預(yù)先給定一個(gè)閾值Fbuffer_err，當(dāng)e>Fbuffer_err時(shí)，則認(rèn)為在當(dāng)前窗口中疑似發(fā)生概念漂移.此時(shí)需將當(dāng)前分類器f中的基分類器wt與HS中的每一個(gè)歷史分類器ws n各建立一個(gè)集成分類器：

并將得到的所有集成分類器及當(dāng)前分類器f都存入集合POOL中，進(jìn)入當(dāng)前分類器調(diào)整階段.

在調(diào)整階段中，每獲取到一個(gè)樣本，通過BufferSelect算法從POOL中根據(jù)負(fù)相似度選擇一個(gè)集成分類器對新到樣本進(jìn)行分類.BufferSelect算法的詳細(xì)描述如算法1.當(dāng)獲到樣本的真實(shí)類別后，按照HomOTL-I的更新策略更新POOL中所有的集成分類器.

算法1. BufferSelect.

輸入:分類器池POOL、新到樣本的集合PS；

輸出:f.

①V=?;

② for eachws ninHS

④V.add(vn);

⑤ endfor

⑦ fori=1 tolength(HS)

⑨f=POOL[n];*選取當(dāng)前分類器*

⑩ break;

2.5RC-OTL算法描述

算法2. RC-OTL.

輸入:數(shù)據(jù)流DS、窗口大小p、分類器選擇閾值Fbuffer_err；

① ws=0;wt=0;bufferflag=0;Nerr=0;

fmemory=0;POOL=?;*初始化階段*

②PS=?;HS=?;*儲存新到樣本和存儲歷史分類器*

④ fort=1 toTdo

⑤ receive instancext∈X;

⑥ ifbufferflag>0 then*進(jìn)入當(dāng)前分類器調(diào)整階段*

⑦f=bufferSelect(POOL,PS);*使用bufferSelect調(diào)整當(dāng)前分類器*

⑧y=f.classify(xt);*使用當(dāng)前分類器對樣本xt分類*

⑨ receive the correct label:yt∈{-1,+1};

⑩ for eachfiinPOOL

的在線學(xué)習(xí)規(guī)則對fi進(jìn)行更新*

前半個(gè)窗口樣本的分類錯(cuò)誤率e*

與HS的其他wt按照式(1)

入HS*

分類器與新到樣本集PS的負(fù)相

(xi，yi)∈PS;

Nerr=0,fmemory=0;

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

3.1實(shí)驗(yàn)數(shù)據(jù)與實(shí)驗(yàn)方法

為了驗(yàn)證RC-OTL算法的有效性，本文使用了5個(gè)數(shù)據(jù)集*http://www.stevenhoi.org//OTL//email_list，MITface，usps，usenet1和usenet2.其中，email_list，usenet1和usenet2都是基于UCI的newsgroups20數(shù)據(jù)集，描述了在一段時(shí)間內(nèi)用戶對醫(yī)藥、太空和籃球的興趣的變化，其中“+”代表感興趣，“-”代表不感興趣.MITface來自MIT的人臉數(shù)據(jù)庫.Usps來自美國郵政手寫數(shù)字?jǐn)?shù)據(jù)集.email_list，MITface，usps，usenet1和usenet2的特征維數(shù)分別為913，361，256，99和99.這些數(shù)據(jù)集的具體描述如表1～5所示.我們將在這些數(shù)據(jù)集上對比概念漂移數(shù)據(jù)流分類算法PA-I[29]，CODL，RCD及本文提出的RC-OTL，RC-OTL-I(不對當(dāng)前分類器進(jìn)行調(diào)整)算法的累積分類準(zhǔn)確率，累積分類準(zhǔn)確率的變化以及實(shí)時(shí)分類準(zhǔn)確率(實(shí)時(shí)分類準(zhǔn)確率每30個(gè)樣本計(jì)算一次)的變化.其中，PA-I是一個(gè)在線學(xué)習(xí)算法，它不進(jìn)行概念漂移檢測.PA-I和CODL均使用Zhao等人提供的源程序①.CODL，RCD，RC-OTL和RC-OTL-I均使用PA-I作為基本學(xué)習(xí)算法.

Table1　email_list Data Set表1　email_list數(shù)據(jù)集

Table 2　MITface Data Set表2　MITface數(shù)據(jù)集

Table 3　usps Data Set表3　usps數(shù)據(jù)集

Table4　usenet1 Data Set表4　usenet1數(shù)據(jù)集

Table 5　usenet2 Data Set表5　usenet2數(shù)據(jù)集

實(shí)驗(yàn)中采用與Zhao等人[22]相同的參數(shù)：懲罰系數(shù)C=5，窗口大小p=30.將數(shù)據(jù)集中樣本投影到高維平面采用的核函數(shù)為高斯徑向函數(shù)，其參數(shù)σ=8.RCD使用了R語言擴(kuò)展包[30]中提供基于KNN的多元非參統(tǒng)計(jì)測試方法檢測新到概念是否為歷史概念，其中最近鄰數(shù)K=3，相似參數(shù)p_value=0.01，同時(shí)RCD最多儲存的歷史分類器數(shù)為15.另外，設(shè)置Fbuffer_err=7.

為了比較各個(gè)算法的分類準(zhǔn)確率和在發(fā)生概念漂移時(shí)分類準(zhǔn)確率的變化，實(shí)驗(yàn)給出了各算法在每個(gè)數(shù)據(jù)集上的累積分類準(zhǔn)確率和實(shí)時(shí)分類準(zhǔn)確率.實(shí)驗(yàn)數(shù)據(jù)集分別被按照概念隨機(jī)打亂，實(shí)驗(yàn)重復(fù)20次.Zhao等人提供了重復(fù)20次實(shí)驗(yàn)所需的數(shù)據(jù)集①.實(shí)驗(yàn)結(jié)果為20次實(shí)驗(yàn)的平均值.實(shí)驗(yàn)結(jié)果分別由表6、圖1及圖2描述.

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

表6和圖1提供了各個(gè)算法的累積分類準(zhǔn)確率情況.在圖1中，每個(gè)數(shù)據(jù)集均只提供了20個(gè)時(shí)間點(diǎn)的累積分類準(zhǔn)確率.從表6可以看出，RC-OTL的累積分類準(zhǔn)確率在上述每個(gè)數(shù)據(jù)集上均優(yōu)于其他算法.圖1進(jìn)一步表明：RC-OTL的累積分類準(zhǔn)確率與其他算法的差距隨著樣本的增加而不斷增大.RC-OTL-I的累積分類準(zhǔn)確率比RC-OTL稍低，但多數(shù)情況下也優(yōu)于CDOL和RCD.這說明：RC-OTL所采取的利用負(fù)相似度選擇最適合于新到樣本的基分類器的策略有效地減少了“負(fù)遷移”，從而有效地提高了累積分類準(zhǔn)確率.

Table 6　Cumulate Classification Accuracy表6　累積分類準(zhǔn)確率　%

Fig. 1　The variation of cumulate classification accuracy.圖1　累積分類準(zhǔn)確率變化圖

Fig. 2　The variation of real-time classification accuracy.圖2　實(shí)時(shí)分類準(zhǔn)確率變化圖

圖2描述了各算法在數(shù)據(jù)流分類與學(xué)習(xí)過程中實(shí)時(shí)分類準(zhǔn)確率的變化情況.從圖2可以看出，與CDOL和RCD相比，RC-OTL和RC-OTL-I能在遭遇概念漂移后顯示出對新到樣本更高的實(shí)時(shí)分類準(zhǔn)確率，這說明RC-OTL和RC-OTL-I能更快地適應(yīng)新到樣本.這表明：概念檢測后選擇負(fù)相似度最小的分類器為在線遷移學(xué)習(xí)提供了更好的基礎(chǔ).更進(jìn)一步地，由于RC-OTL的權(quán)重調(diào)整機(jī)制，能迅速減少由于“負(fù)遷移”對當(dāng)前分類器造成的影響，而RCD則難以做到.因此，RC-OTL能更快地適應(yīng)重現(xiàn)概念.另外，從圖2還可以看到：在多數(shù)情況下，當(dāng)?shù)?次概念漂移發(fā)生后，RC-OTL在以后各次概念漂移發(fā)生時(shí)它的分類準(zhǔn)確率的下降程度都比第1次概念漂移發(fā)生時(shí)的分類準(zhǔn)確率的下降程度要低.這說明：若概念漂移發(fā)生在概念漂移檢測之前，RC-OTL會利用負(fù)相似度調(diào)整當(dāng)前分類器，使分類準(zhǔn)確率不至于下降得太多.

4　總　　結(jié)

本文針對重現(xiàn)概念的學(xué)習(xí)與分類問題中的“負(fù)遷移”和概念漂移檢測的滯后性提出了一種基于在線遷移學(xué)習(xí)的重現(xiàn)概念漂移數(shù)據(jù)流分類算法——RC-OTL.RC-OTL存儲學(xué)習(xí)過的歷史分類器，計(jì)算新到樣本與存儲的歷史分類器之間的負(fù)相似度，以選擇最適合對后續(xù)樣本進(jìn)行分類和學(xué)習(xí)的基分類器，從而能更好地實(shí)現(xiàn)從源領(lǐng)域到目標(biāo)領(lǐng)域的知識遷移.初步的理論分析表明了RC-OTL的合理性.實(shí)驗(yàn)結(jié)果進(jìn)一步驗(yàn)證了RC-OTL的確能有效地提高分類準(zhǔn)確率，并且在遭遇概念漂移后，能夠很快地適應(yīng)新到樣本，顯示了更高的實(shí)時(shí)分類準(zhǔn)確率.

目前，本文只采用PA作為基分類器的學(xué)習(xí)算法，下一步將給出基于其他學(xué)習(xí)算法的RC-OTL算法，并探討不同概念漂移檢測方法對算法性能的影響以及存儲的歷史分類器的合并與淘汰問題.

[1]Schlimmer J, Granger R. Incremental learning from noisy data[J]. Machine Learning, 1986, 1(3): 317-354

[2]Kuncheva L I. Classifier ensembles for changing environments[C] //Proc of the 5th Workshop on Multiple Classifier Systems. Berlin: Springer, 2004: 1-15

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

[4]Wang Tao, Li Zhoujun, Yan Yuejin, et al. A survey of classification of data streams[J]. Journal of Computer Research and Development, 2007, 44(11): 1809-1815 (in Chinese)

(王濤, 李舟軍, 顏躍進(jìn), 等. 數(shù)據(jù)流挖掘分類技術(shù)綜述[J]. 計(jì)算機(jī)研究與發(fā)展, 2007, 44(11): 1809-1815)

[5]Zliobaite I. Learning under concept drift: An overview, abs//1010.4784[R]. Vilnius: Vilnius University, 2009

[6]Hoens T R, Polikar R, Chawla N V. Learning from streaming data with concept drift and imbalance: an overview[J]. Progress in Artificial Intelligence, 2012, 1(1): 1-13

[7]Gama J. A survey on learning from data streams: Current and future trends[J]. Progress in Artificial Intelligence, 2012, 1(1): 45-55

[8]Gama J, Zliobaite I, Bifet A, et al. A survey on concept drift adaption[J]. ACM Computing Surveys, 2014, 46(4): 1-37

[9]Wen Yimin, Qiang Baohua, Fan Zhigang. A survey of the classification of data streams with concept drift[J]. CAAI Trans on Intelligent Systems, 2013, 8(2): 96-104 (in Chinese)

(文益民, 強(qiáng)保華, 范志剛. 概念漂移數(shù)據(jù)流分類研究綜述[J]. 智能系統(tǒng)學(xué)報(bào), 2013, 8(2): 96-104

[10]Hulten G, Spencer L, Domingos P. Mining time-changing data streams[C] //Proc of the 7th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2001: 97-106

[11]Wang H, Fan W, Yu P S, et al. Mining concept-drifting data streams using ensemble classifiers[C] //Proc of the 9th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2003: 226-235

[12]Blum A. Empirical support for winnow and weighted-majority algorithms: Results on a calendar scheduling domain[J]. Machine Learning, 1997, 26(1): 5-23

[13]Kolter J Z, Maloof M A. Dynamic weighted majority: An ensemble method for drifting concepts[J]. Journal of Machine Learning Research, 2007, 8(12): 2755-2790

[14]Guo Gongde, Li Nan, Chen Lifei. Concept drift detection for data streams based on mixture model[J]. Journal of Computer Research and Development, 2014, 51(4): 731-742 (in Chinese)

(郭躬德, 李南, 陳黎飛. 一種基于混合模型的數(shù)據(jù)流概念漂移檢測算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(4): 731-742)

[15]Widmer G, Kubat M. Learning in the presence of concept drift and hidden contexts[J]. Machine Learning, 1996, 23(1): 69-101

[16]Ramamurthy S, Bhatnagar R. Tracking recurrent concept drift in streaming data using ensemble classifiers[C] //Proc of the 6th Int Conf on Machine Learning and Applications. Piscataway, NJ: IEEE, 2007: 404-409

[17]Jackowski K. Fixed-size ensemble classifier system evolutionarily adapted to a recurring context with an unlimited pool of classifiers[J]. Pattern Analysis Applications, 2014, 17(4): 709-724

[18]Gon?alves P M, Barros R S. RCD: A recurring concept drift framework[J]. Pattern Recognition Letters, 2013, 34(9): 1018-1025

[19]Katakis I, Tsoumakas G, Vlahavas I. Tracking recurring contexts using ensemble classifiers: An application to email filtering[J]. Knowledge and Information Systems, 2010, 22(3): 371-391

[20]Gama J, Kosina P. Learning about the learning process[C] //Proc of the 10th Int Conf on Advances in Intelligent Data Analysis X. Berlin: Springer, 2011: 162-172

[21]Angel A M, Bartolo G J, Ernestina M. Predicting recurring concepts on data-streams by means of a meta-model and fuzzy similarity function[J]. Expert Systems with Applications, 2016, 46(3): 87-105

[22]Zhao Peilin, Hoi S C H, Wang Jialei, et al. Online transfer learning[J]. Artificial Intelligence, 2014, 216(16): 76-102

[23]Gama J, Medas P, Castillo G, et al. Learning with drift detection[C] //Proc of the 7th Brazilian Symp on Artificial Intelligence. Berlin: Springer, 2004: 286-295

[24]Gomes J B, Menasalvas E, Sousa P A C. Learning recurring concepts from data streams with a context-aware ensemble[C] //Proc of ACM Symp on Applied Computing. New York: ACM, 2011: 994-999

[25]Pan S J, Yang Qiang. A survey on transfer learning[J]. IEEE Trans on Knowledge and Data Engineering, 2010, 22(10): 1345-1359

[26]Pan Weike, Zhong Hao, Xu Congfu, et al. Ming adaptive bayesian personalized ranking for heterogeneous implicit feedbacks[J]. Knowledge-Based Systems, 2015, 73(1): 173-180

[27]Pan Weike, Yang Qiang. Transfer learning in heterogeneous collaborative filtering domains[J]. Artificial Intelligence, 2013, 197(4): 39-55

[28]Hong Jiaming, Yin Jian, Huang Yun, et al. TrSVM: A transfer learning algorithm using domain similarity[J]. Journal of Computer Research and Development, 2011, 48(10): 1823-1830 (in Chinese)

(洪佳明, 印鑒, 黃云, 等. TrSVM: 一種基于領(lǐng)域相似性的遷移學(xué)習(xí)算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2011, 48(10): 1823-1830)

[29]Crammer K, Dekel O, Keshet J, et al. Online passive-aggressive algorithms[J]. The Journal of Machine Learning Research, 2006, 7(3): 551-585

[30]Chen L, Dai P, Dou W. Mtsknn: Multivariate two-sample tests based on k-nearest-neighbors[CP//OL].[2016-05-20]. http://cran.rproject.org//web//packages//MTSKNN//index.html

Wen Yimin, born in 1969. PhD. Professor and master supervisor in Guilin University of Electronic Technology. Senior member of China Computer Federation. His main research interests include machine learning, data mining, recommendation systems, big data analysis and online education.

Tang Shiqi, born in 1990. Master candidate in Guilin University of Electronic Technology. His main research interests include machine learning and data mining (tttpgs@163.com).

Feng Chao, born in 1989. Master from Guilin University of Electronic Technology. His main research interests include machine learning and data mining (henryfung01@126.com).

Gao Kai, born in 1968. PhD. Professor and master supervisor in Hebei University of Science and Technology. His main research interests include big data search and mining, natural language processing, Information retrieval, and social computing (gaokai@hebust.edu.cn).

Online Transfer Learning for Mining Recurring Concept in Data Stream Classification

Wen Yimin1,2,3, Tang Shiqi1, Feng Chao1, and Gao Kai4

1(SchoolofComputerScienceandInformationSecurity,GuilinUniversityofElectronicTechnology,Guilin,Guangxi541004)2(GuangxiKeyLaboratoryofTrustedSoftware(GuilinUniversityofElectronicTechnology),Guilin,Guangxi541004)3(GuangxiExperimentCenterofInformationScience(GuilinUniversityofElectronicTechnology),Guilin,Guangxi541004)4(SchoolofInformationScience&Engineering,HebeiUniversityofScienceandTechnology,Shijiazhuang050018)

At the age of big data, data stream classification is being applied to many fields, like spam filtering, market predicting, and weather forecasting, et al, in which recurring concept is an important character. Aiming to reduce the influence of negative transfer and improve the lag of detection of concept drift, RC-OTL is proposed for mining recurring concepts in data stream based on online transfer learning strategy. When a concept drift is detected, RC-OTL selects one current base classifier to store, and then computes the domain similarities between the current training samples and the stored classifiers, in order to select the most appropriate source classifier to combine with a new classifier for learning the upcoming samples, which results in knowledge transfer from the source domain to the target domain. In addition, RC-OTL can select appropriate classifier to classify when the current classification accuracy is detected below a given threshold before concept drift detection. The preliminary theory analysis explains why RC-OTL can reduce negative transfer effectively, and the experiment results further illustrates that RC-OTL can efficiently promote the cumulate accuracy of data stream classification, and faster adapt to the samples of new concept after concept drift takes place.

concept drift; transfer learning; recurring concept; online learning; negative transfer

2016-03-21；

2016-06-04

國家自然科學(xué)基金項(xiàng)目(61363029,U1501252)；廣西區(qū)自然科學(xué)基金項(xiàng)目(2014GXNSFAA118395)；廣西區(qū)科學(xué)研究與技術(shù)開發(fā)項(xiàng)目(桂科攻14124005-2-1)；廣西信息科學(xué)中心項(xiàng)目(YB408)

TP391

This work was supported by the National Natural Science Foundation of China (61363029, U1501252), the Natural Science Foundation of Guangxi District (2014GXNSFAA118395), Guangxi Scientific Research and Technology Development Project (14124005-2-1), and the Program of Guangxi Experiment Center of Information Science (YB408).