楊 帆 張 永,2*

1(遼寧師范大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 遼寧 大連 116081) 2(計(jì)算機(jī)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室(南京大學(xué)) 江蘇 南京 210023)

基于相對(duì)熵的數(shù)據(jù)流概念漂移檢測(cè)算法

楊 帆1張 永1,2*

1(遼寧師范大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 遼寧 大連 116081)2(計(jì)算機(jī)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室(南京大學(xué)) 江蘇 南京 210023)

針對(duì)數(shù)據(jù)流中出現(xiàn)的概念漂移問題，采用決策樹作為分類器，提出一種基于相對(duì)熵的數(shù)據(jù)流概念漂移檢測(cè)算法。提出的算法將分類器的準(zhǔn)確率與相對(duì)熵作為判斷該數(shù)據(jù)塊是否發(fā)生概念漂移的標(biāo)準(zhǔn)。通過5個(gè)數(shù)據(jù)集對(duì)該方法進(jìn)行驗(yàn)證，該算法在其中4個(gè)數(shù)據(jù)集上都獲得了最優(yōu)的結(jié)果，在另一個(gè)數(shù)據(jù)集上獲得了次優(yōu)結(jié)果。實(shí)驗(yàn)結(jié)果表明采用該方法不僅能夠有效地檢測(cè)概念漂移的發(fā)生，而且還能提高分類器的準(zhǔn)確率。

數(shù)據(jù)流 概念漂移 相對(duì)熵 決策樹

0 引 言

數(shù)據(jù)流挖掘是當(dāng)前數(shù)據(jù)挖掘領(lǐng)域的研究熱點(diǎn)之一，已經(jīng)成功地應(yīng)用于諸多領(lǐng)域，如醫(yī)學(xué)、金融分析、生物分析、股票分析、社交網(wǎng)絡(luò)、市場(chǎng)營(yíng)銷等。數(shù)據(jù)流是由許多領(lǐng)域產(chǎn)生的具有實(shí)時(shí)性、未知性、海量性等特點(diǎn)的數(shù)據(jù)[1]。數(shù)據(jù)流的挖掘主要是通過在已經(jīng)產(chǎn)生的數(shù)據(jù)流中挖掘有效的、有價(jià)值的潛在信息，從而預(yù)測(cè)未知的或即將到來(lái)的數(shù)據(jù)。數(shù)據(jù)流分析不僅給算法應(yīng)用帶來(lái)了時(shí)間和空間的挑戰(zhàn)，而且為豐富數(shù)據(jù)挖掘理論和方法提供了新的可能。

如何高效地分類數(shù)據(jù)流是機(jī)器學(xué)習(xí)中一個(gè)重要的挑戰(zhàn)。目前，數(shù)據(jù)流分類的主要模型有決策樹、貝葉斯、BP神經(jīng)網(wǎng)絡(luò)、KNN、支持向量機(jī)等單分類器模型和多分類器模型[2-4]。但在實(shí)際應(yīng)用中，數(shù)據(jù)流中隱含的一些知識(shí)或概念也可能隨著環(huán)境變化和時(shí)間推移而發(fā)生改變，導(dǎo)致了概念漂移現(xiàn)象的發(fā)生[5]。

目前大多數(shù)的概念漂移檢測(cè)僅僅以準(zhǔn)確率與時(shí)間窗口大小為判斷標(biāo)準(zhǔn)，很少考慮前后數(shù)據(jù)塊概率分布的差異性。本文在準(zhǔn)確率的基礎(chǔ)之上，充分考慮了數(shù)據(jù)塊間概率分布的差異性，提出了一種基于相對(duì)熵的數(shù)據(jù)流概念漂移檢測(cè)算法。該算法通過計(jì)算相鄰數(shù)據(jù)塊間的相對(duì)熵來(lái)體現(xiàn)概率分布的差異性，同時(shí)本算法中的分類器只有在判斷可能漂移或者是漂移的情況下才更新分類器模型，從而減少了內(nèi)存占用。

1 相關(guān)工作

典型的學(xué)習(xí)方法，對(duì)于處理固定任務(wù)或者是分類概率不變的數(shù)據(jù)時(shí)，無(wú)需考慮實(shí)時(shí)更新分類器的問題。但是，對(duì)于數(shù)據(jù)流而言，當(dāng)前輸入的數(shù)據(jù)可能與前面數(shù)據(jù)間存在目標(biāo)概念上的變化，這種變化引起了概念漂移現(xiàn)象。因此，在對(duì)數(shù)據(jù)流的分類過程中，為了適應(yīng)概念漂移現(xiàn)象，必須不斷更新分類模型。概念漂移現(xiàn)象通常體現(xiàn)為以下三種漂移形式[6-8]：漸進(jìn)式漂移、突變式漂移與抽樣變化(數(shù)據(jù)類分布變化)。

針對(duì)概念漂移現(xiàn)象，國(guó)內(nèi)外學(xué)者已經(jīng)提出了一些解決方案。例如，Hulten等[9]基于快速?zèng)Q策樹(VFDT)提出了適應(yīng)概念的快速?zèng)Q策樹(CVFDT)方法，采用窗口大小固定的方式替換子樹，并且周期性檢查數(shù)據(jù)流中存在的概念漂移；Li等[10]提出了單類增量快速?zèng)Q策樹(OCVFDT)，對(duì)不同類型的概念漂移進(jìn)行處理；Scholkopf等[11]提出了單類支持向量機(jī)(OCSVM)，通過設(shè)置目標(biāo)類(將多數(shù)類變成二分類)判斷概念漂移情況；Bicego等[12]提出了加權(quán)的單類支持向量機(jī)(WOCSVM)，采用設(shè)置權(quán)值的方式優(yōu)化OCSVM； Krawczyk等[13]提出了增量式單類支持向量機(jī)(IOCSVM)，在WOCSVM的基礎(chǔ)之上加入了遺忘機(jī)制，處理帶有概念漂移情況的數(shù)據(jù)流。

2 基于相對(duì)熵的概念漂移檢測(cè)算法

2.1 相對(duì)熵

相對(duì)熵又稱KL散度，是衡量?jī)蓚€(gè)概率分布差異的一種方法。通常用概率分布p來(lái)表示真實(shí)分布，q表示擬合真實(shí)分布。從信息論的角度看，相對(duì)熵表示用概率分布q來(lái)擬合真實(shí)分布p所產(chǎn)生的信息損耗。

對(duì)于一個(gè)隨機(jī)變量X=(x1,x2,…,xn)，用p(x)、q(x)分別代表取值為xi(i=1,2,…,n)時(shí)的兩個(gè)隨機(jī)變量的概率分布，則p對(duì)q的相對(duì)熵可描述為：

(1)

相對(duì)熵具有兩個(gè)性質(zhì)：(1) 非負(fù)性，即D(p‖q)≥0；(2) 不對(duì)稱性，即D(p‖q)≠D(q‖p)。

根據(jù)式(1)易知，對(duì)于一個(gè)穩(wěn)定、有序的數(shù)據(jù)流而言，前后相鄰數(shù)據(jù)塊的相對(duì)熵值非常小。但是對(duì)于非平穩(wěn)、無(wú)序的數(shù)據(jù)流而言，相對(duì)熵的值則會(huì)增大。若兩個(gè)概率分布完全相同，則相對(duì)熵值為0。

綜上所述：相對(duì)熵非常適合判斷數(shù)據(jù)流的概念漂移；若數(shù)據(jù)流中出現(xiàn)了非平穩(wěn)、無(wú)序的概率分布，相對(duì)熵會(huì)增大，則數(shù)據(jù)流發(fā)生了概念漂移；若數(shù)據(jù)流處于相對(duì)平穩(wěn)的分布狀態(tài)，相對(duì)熵的值會(huì)非常小甚至接近于0，則沒有發(fā)生概念漂移。

2.2 算法思想

針對(duì)數(shù)據(jù)流產(chǎn)生的概念漂移問題，本文提出了一種基于相對(duì)熵的概念漂移檢測(cè)方法。很多研究者在對(duì)數(shù)據(jù)流中概念漂移檢測(cè)時(shí)，將分類器分類的準(zhǔn)確率作為判斷概念漂移的標(biāo)準(zhǔn)，很少考慮數(shù)據(jù)塊間的概率分布變化。而本文提出的算法從準(zhǔn)確率和相對(duì)熵兩個(gè)方面來(lái)判斷數(shù)據(jù)流中是否產(chǎn)生了概念漂移現(xiàn)象。

本文提出算法的主要思想如下：首先，對(duì)第一塊數(shù)據(jù)進(jìn)行初始化，創(chuàng)建決策樹模型；其次，用上一塊的分類器模型作為當(dāng)前塊的分類器，根據(jù)式(1)求得對(duì)應(yīng)的葉子節(jié)點(diǎn)的相對(duì)熵；再次，對(duì)求得的當(dāng)前塊的準(zhǔn)確率與相對(duì)熵設(shè)置置信區(qū)間，進(jìn)而判斷當(dāng)前塊是否發(fā)生概念漂移。判斷結(jié)果有三種情況[10]：(1) 明確發(fā)生概念漂移；(2) 可能發(fā)生概念漂移；(3) 沒有發(fā)生概念漂移。最后，對(duì)可能發(fā)生漂移與確定發(fā)生概念漂移的當(dāng)前塊重新訓(xùn)練分類器。

在創(chuàng)建決策樹模型時(shí)，根據(jù)信息增益率，即信息增益與分裂信息量的比值，求得具有最大價(jià)值的屬性作為根節(jié)點(diǎn)，以此類推遞歸創(chuàng)建決策樹。當(dāng)數(shù)據(jù)塊較大時(shí)，決策樹分類易產(chǎn)生過擬合現(xiàn)象。因此，對(duì)決策樹進(jìn)行適當(dāng)剪枝，以減少分類的誤分類率。

算法首先對(duì)第一個(gè)數(shù)據(jù)塊進(jìn)行訓(xùn)練，建立決策樹cptree1。用cptree1測(cè)試下一個(gè)block，求出相對(duì)熵KL與準(zhǔn)確率ACCi值，與置信區(qū)間進(jìn)行比較。如果沒有發(fā)生漂移，則繼續(xù)測(cè)試一個(gè)block。若發(fā)生漂移或者可能漂移的情況，對(duì)當(dāng)前數(shù)據(jù)塊的大小折半用當(dāng)前分類器進(jìn)行測(cè)試，求得相對(duì)熵KL與準(zhǔn)確率right_rate，若仍然存在漂移或者可能漂移的情況，則判斷為漂移或者可能漂移，產(chǎn)生漂移情況說(shuō)明數(shù)據(jù)發(fā)生了類別或?qū)傩詣?dòng)態(tài)的變化。更新分類器，測(cè)試下一個(gè)數(shù)據(jù)塊。

2.3 基于相對(duì)熵的概念漂移檢測(cè)算法

基于上述思想，本文提出了基于相對(duì)熵的概念漂移檢測(cè)算法KLDT，將分類器的分類準(zhǔn)確率與相對(duì)熵的值作為概念漂移的評(píng)判標(biāo)準(zhǔn)，如下算法所示。

算法：基于相對(duì)熵的概念漂移檢測(cè)算法KLDT

輸入：數(shù)據(jù)流S

輸出：輸出概念漂移數(shù)據(jù)塊

步驟1初始化：

選取S1個(gè)樣本作為訓(xùn)練樣本；

構(gòu)建決策樹ctree1；

對(duì)ctree1剪枝生成cpree1，Tcurr=cpree1；

得出準(zhǔn)確率Acci；

步驟2對(duì)連續(xù)到達(dá)的數(shù)據(jù)塊Si(i∈2,…,n)：

用Tcurr對(duì)Si進(jìn)行預(yù)測(cè)

計(jì)算Si的準(zhǔn)確率Acci；

根據(jù)式(1)計(jì)算Si與Si-1的相對(duì)熵D(pi-1‖pi)；

進(jìn)行KS檢驗(yàn)

對(duì)Acci與D(pi-1‖pi)進(jìn)行KS檢驗(yàn)，得到H0；

對(duì)結(jié)果進(jìn)行判斷；

若Acci與D(pi-1‖pi)的KS檢驗(yàn)中H0同時(shí)為1，則判斷為產(chǎn)生漂移，用Si重新訓(xùn)練分類器模型，得到Tcurr，返回步驟2；

否則，返回步驟2。

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

本文采用的數(shù)據(jù)集為使用MOA合成的數(shù)據(jù)集。MOA是一個(gè)用于在線數(shù)據(jù)流學(xué)習(xí)的開源環(huán)境，許多研究者都是用MOA作為數(shù)據(jù)生成器。數(shù)據(jù)集情況如表1所示，共包括5個(gè)數(shù)據(jù)集：SEA[9]數(shù)據(jù)集、HyperPlane數(shù)據(jù)集、RBF數(shù)據(jù)集、LED數(shù)據(jù)集、ELEC數(shù)據(jù)集。其中SEA數(shù)據(jù)集噪聲取10%，RBF的質(zhì)心數(shù)量取50，LED數(shù)據(jù)集噪聲取10%，HyperPlane數(shù)據(jù)集噪聲取5%，選擇了一個(gè)真實(shí)數(shù)據(jù)集ELEC數(shù)據(jù)集，ELEC是通過電力市場(chǎng)中電價(jià)的變化反映市場(chǎng)供應(yīng)問題。

表1 實(shí)驗(yàn)數(shù)據(jù)集

為了驗(yàn)證本文提出算法KLDT的有效性，分別與OCVFDT[10]、IOCSVM[13]、WOCSVM[12]算法進(jìn)行了對(duì)比。OCVFDT通過設(shè)置目標(biāo)類來(lái)區(qū)分是否發(fā)生了概念漂移。IOCSVM通過對(duì)數(shù)據(jù)塊設(shè)置權(quán)值，隨著數(shù)據(jù)塊的不斷增加對(duì)權(quán)值添加遺忘機(jī)制，最后判斷概念漂移情況。WOCSVM通過對(duì)訓(xùn)練數(shù)據(jù)設(shè)置權(quán)值，進(jìn)而對(duì)未知數(shù)據(jù)和未知異常數(shù)據(jù)進(jìn)行檢測(cè)進(jìn)而判斷概念漂移。

在進(jìn)行對(duì)實(shí)驗(yàn)中，每個(gè)數(shù)據(jù)塊的大小均取2 500。KLDT算法以準(zhǔn)確率與相對(duì)熵為判斷標(biāo)準(zhǔn)。本實(shí)驗(yàn)由于每個(gè)數(shù)據(jù)集的性質(zhì)以及屬性不同，所以將決策樹作為分類器對(duì)每個(gè)數(shù)據(jù)集進(jìn)行分類的準(zhǔn)確率大有不同。實(shí)驗(yàn)結(jié)果如表2所示。

表2 不同算法準(zhǔn)確率對(duì)比 %

根據(jù)表2可以看出，本實(shí)驗(yàn)的準(zhǔn)確率相比OCVFDT算法準(zhǔn)確率均有很大的提升；相比IOCVFDT算法在LED數(shù)據(jù)集的準(zhǔn)確率并沒有提高；相比WOCSVM算法而言，在LED與ELEC數(shù)據(jù)集的準(zhǔn)確率略低。

為了使該方法更具有泛化性，本文進(jìn)行了數(shù)次實(shí)驗(yàn)。其中數(shù)據(jù)塊的大小分別設(shè)為100、200、500、1 000、1 500、2 000、2 500和5 000。實(shí)驗(yàn)結(jié)果如表3所示。

表3 不同塊大小的準(zhǔn)確率 %

根據(jù)表3可以看出，在RBF、LED、SEA、HyperPlane數(shù)據(jù)集上，當(dāng)數(shù)據(jù)塊大小為5 000時(shí)，提出的算法獲得了最優(yōu)準(zhǔn)確率。只有當(dāng)ELEC數(shù)據(jù)集在數(shù)據(jù)塊為100時(shí)準(zhǔn)確率最高，而在數(shù)據(jù)塊為5 000時(shí)卻是次優(yōu)解。具體情況如圖1-圖5所示。

圖1 RBF數(shù)據(jù)集的準(zhǔn)確率

圖2 LED數(shù)據(jù)集的準(zhǔn)確率

圖3 SEA數(shù)據(jù)集的準(zhǔn)確率

圖4 HyperPlane數(shù)據(jù)集的準(zhǔn)確率

圖5 ELEC數(shù)據(jù)集的準(zhǔn)確率

圖1-圖5可以看出準(zhǔn)確率的波動(dòng)并不是非常大，主要是因?yàn)槿舢a(chǎn)生概念漂移或者是確定發(fā)生概念漂移，分類器都得到了及時(shí)的更新。根據(jù)圖1-圖5不同塊大小的準(zhǔn)確率，可以看出當(dāng)數(shù)據(jù)塊大小為5 000個(gè)數(shù)據(jù)時(shí)準(zhǔn)確率特別的高，而數(shù)據(jù)塊大小為100個(gè)數(shù)據(jù)時(shí)具有最低的準(zhǔn)確率。當(dāng)數(shù)據(jù)塊較小時(shí)對(duì)概念漂移比較敏感，所以準(zhǔn)確率較低，而當(dāng)數(shù)據(jù)塊相對(duì)較大時(shí)，對(duì)概念漂移不是特別敏感，則準(zhǔn)確率相對(duì)較高。相反的是，圖3所示的準(zhǔn)確率在數(shù)據(jù)塊相對(duì)較小時(shí)，具有較高的準(zhǔn)確率。表2中當(dāng)數(shù)據(jù)塊為2 500個(gè)數(shù)據(jù)時(shí)的準(zhǔn)確率相比WOCSVM較低，當(dāng)數(shù)據(jù)塊大小取500、200、100個(gè)數(shù)據(jù)時(shí)則高出WOCSVM算法的準(zhǔn)確率。

4 結(jié) 語(yǔ)

本文提出了一種基于相對(duì)熵的數(shù)據(jù)流概念漂移檢測(cè)算法。本文將決策樹作為分類器，根據(jù)判定條件不斷地更新分類器。相比增量式學(xué)習(xí)減少了內(nèi)存的使用。在判定條件中并不是單一地選擇準(zhǔn)確率，而是增加了相對(duì)熵。根據(jù)相對(duì)熵的非負(fù)性和非對(duì)稱性的性質(zhì)，可以判定相對(duì)熵適用于檢測(cè)數(shù)據(jù)流中存在的概念漂移問題。然而，本文的算法還有不足的地方，并不能同時(shí)適應(yīng)多種概念漂移特征，快速、準(zhǔn)確地檢測(cè)數(shù)據(jù)流中概念漂移的問題仍然是今后研究的重點(diǎn)。

[1] 丁劍,韓萌,李娟.概念漂移數(shù)據(jù)流挖掘算法綜述[J].計(jì)算機(jī)科學(xué),2016,43(12):24-29.

[2] Lomax S,Vadera S A.Survey of cost-sensitive decision tree induction algorithms[J].ACM Computing Surveys,2013,45(2):1-35.

[3] Song G,Ye Y,Zhang H,et al.Dynamic Clustering Forest:An ensemble framework to efficiently classify textual data stream with concept drift[J].Information Sciences,2016,357:125-143.

[4] Marseguerra M.Early detection of gradual concept drifts by text categorization and Support Vector Machine techniques:The TRIO algorithm[J].Reliability Engineering and System Safety,2014,129:1-9.

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

[6] 李培培.數(shù)據(jù)流中概念漂移檢測(cè)與分類方法研究[D].合肥:合肥工業(yè)大學(xué),2012.

[7] Wu X D,Li P P,Hu X G.Learning from concept drifting data streams with unlabeled data[J].Neurocomputing,2012,92:145-155.

[8] 姚遠(yuǎn).海量動(dòng)態(tài)數(shù)據(jù)流分類方法研究[D].大連:大連理工大學(xué),2013.

[9] Hulten G,Spencer L,Domingos P.Mining time-changing data streams[C]//Proceedings of the seventh ACM SIGKDD international conference on knowledge discovery and data mining,2001:97-106.

[10] Li C,Zhang Y,Li X.One-class very fast decision tree for one-class classification of data streams[C]//Proceedings of the Third International Workshop on Knowledge Discovery from Sensor Data,2009:79-86.

[11] Scholkopf B,Smola A J.Learning with kernels:support vector machines regularization and beyond[M].MIT Press,2001.

[12] Bicego M,Figueiredo M A T.Soft clustering using weighted one-class support vector machines[J].Pattern Recognition,2009,42(1):27-32.

[13] Krawczyk B,Wozniak M.Incremental one-class bagging for streaming and evolving big data[C]//Proceedings of the 2015 IEEE BigDataSE,2015:193-198.

ADATAFLOWCONCEPTUALDRIFTDETECTIONALGORITHMBASEDONRELATIVEENTROPY

Yang Fan1Zhang Yong1,2*

1(SchoolofComputerandInformationTechnology,LiaoningNormalUniversity,Dalian116081,Liaoning,China)2(StateKeyLabforNovelSoftwareTechnology,NanjingUniversity,Nanjing210023,Jiangsu,China)

Aiming at the problem of concept drift in data stream, this paper proposed a conceptual drift detection algorithm based on relative entropy based on decision tree as a classifier. The proposed algorithm combined the accuracy and relative entropy of the classifier as a criterion for judging whether the data block was drilled or not. The method was verified by 5 data sets. The algorithm obtained the optimal result on the four data sets, and the suboptimal result was obtained on the other data set. The experimental results showed that this method not only detected the occurrence of concept drift effectively, but also improved the accuracy of the classifier.

Data stream Concept drift Relative entropy Decision tree

2016-12-17。國(guó)家自然科學(xué)基金面上項(xiàng)目(61373127)。楊帆，碩士生，主研領(lǐng)域：機(jī)器學(xué)習(xí)。張永，副教授。

TP311

A

10.3969/j.issn.1000-386x.2017.12.049