基于相對熵的數據流概念漂移檢測算法

楊 帆 張 永,2*

1(遼寧師范大學計算機與信息技術學院 遼寧 大連 116081) 2(計算機軟件新技術國家重點實驗室(南京大學) 江蘇 南京 210023)

基于相對熵的數據流概念漂移檢測算法

楊 帆1張 永1,2*

1(遼寧師范大學計算機與信息技術學院 遼寧 大連 116081)2(計算機軟件新技術國家重點實驗室(南京大學) 江蘇 南京 210023)

針對數據流中出現的概念漂移問題，采用決策樹作為分類器，提出一種基于相對熵的數據流概念漂移檢測算法。提出的算法將分類器的準確率與相對熵作為判斷該數據塊是否發生概念漂移的標準。通過5個數據集對該方法進行驗證，該算法在其中4個數據集上都獲得了最優的結果，在另一個數據集上獲得了次優結果。實驗結果表明采用該方法不僅能夠有效地檢測概念漂移的發生，而且還能提高分類器的準確率。

數據流 概念漂移 相對熵 決策樹

0 引 言

數據流挖掘是當前數據挖掘領域的研究熱點之一，已經成功地應用于諸多領域，如醫學、金融分析、生物分析、股票分析、社交網絡、市場營銷等。數據流是由許多領域產生的具有實時性、未知性、海量性等特點的數據[1]。數據流的挖掘主要是通過在已經產生的數據流中挖掘有效的、有價值的潛在信息，從而預測未知的或即將到來的數據。數據流分析不僅給算法應用帶來了時間和空間的挑戰，而且為豐富數據挖掘理論和方法提供了新的可能。

如何高效地分類數據流是機器學習中一個重要的挑戰。目前，數據流分類的主要模型有決策樹、貝葉斯、BP神經網絡、KNN、支持向量機等單分類器模型和多分類器模型[2-4]。但在實際應用中，數據流中隱含的一些知識或概念也可能隨著環境變化和時間推移而發生改變，導致了概念漂移現象的發生[5]。

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

1 相關工作

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

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

2 基于相對熵的概念漂移檢測算法

2.1 相對熵

相對熵又稱KL散度，是衡量兩個概率分布差異的一種方法。通常用概率分布p來表示真實分布，q表示擬合真實分布。從信息論的角度看，相對熵表示用概率分布q來擬合真實分布p所產生的信息損耗。

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

(1)

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

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

綜上所述：相對熵非常適合判斷數據流的概念漂移；若數據流中出現了非平穩、無序的概率分布，相對熵會增大，則數據流發生了概念漂移；若數據流處于相對平穩的分布狀態，相對熵的值會非常小甚至接近于0，則沒有發生概念漂移。

2.2 算法思想

針對數據流產生的概念漂移問題，本文提出了一種基于相對熵的概念漂移檢測方法。很多研究者在對數據流中概念漂移檢測時，將分類器分類的準確率作為判斷概念漂移的標準，很少考慮數據塊間的概率分布變化。而本文提出的算法從準確率和相對熵兩個方面來判斷數據流中是否產生了概念漂移現象。

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

在創建決策樹模型時，根據信息增益率，即信息增益與分裂信息量的比值，求得具有最大價值的屬性作為根節點，以此類推遞歸創建決策樹。當數據塊較大時，決策樹分類易產生過擬合現象。因此，對決策樹進行適當剪枝，以減少分類的誤分類率。

算法首先對第一個數據塊進行訓練，建立決策樹cptree1。用cptree1測試下一個block，求出相對熵KL與準確率ACCi值，與置信區間進行比較。如果沒有發生漂移，則繼續測試一個block。若發生漂移或者可能漂移的情況，對當前數據塊的大小折半用當前分類器進行測試，求得相對熵KL與準確率right_rate，若仍然存在漂移或者可能漂移的情況，則判斷為漂移或者可能漂移，產生漂移情況說明數據發生了類別或屬性動態的變化。更新分類器，測試下一個數據塊。

2.3 基于相對熵的概念漂移檢測算法

基于上述思想，本文提出了基于相對熵的概念漂移檢測算法KLDT，將分類器的分類準確率與相對熵的值作為概念漂移的評判標準，如下算法所示。

算法：基于相對熵的概念漂移檢測算法KLDT

輸入：數據流S

輸出：輸出概念漂移數據塊

步驟1初始化：

選取S1個樣本作為訓練樣本；

構建決策樹ctree1；

對ctree1剪枝生成cpree1，Tcurr=cpree1；

得出準確率Acci；

步驟2對連續到達的數據塊Si(i∈2,…,n)：

用Tcurr對Si進行預測

計算Si的準確率Acci；

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

進行KS檢驗

對Acci與D(pi-1‖pi)進行KS檢驗，得到H0；

對結果進行判斷；

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

否則，返回步驟2。

3 實驗結果與分析

本文采用的數據集為使用MOA合成的數據集。MOA是一個用于在線數據流學習的開源環境，許多研究者都是用MOA作為數據生成器。數據集情況如表1所示，共包括5個數據集：SEA[9]數據集、HyperPlane數據集、RBF數據集、LED數據集、ELEC數據集。其中SEA數據集噪聲取10%，RBF的質心數量取50，LED數據集噪聲取10%，HyperPlane數據集噪聲取5%，選擇了一個真實數據集ELEC數據集，ELEC是通過電力市場中電價的變化反映市場供應問題。

表1 實驗數據集

為了驗證本文提出算法KLDT的有效性，分別與OCVFDT[10]、IOCSVM[13]、WOCSVM[12]算法進行了對比。OCVFDT通過設置目標類來區分是否發生了概念漂移。IOCSVM通過對數據塊設置權值，隨著數據塊的不斷增加對權值添加遺忘機制，最后判斷概念漂移情況。WOCSVM通過對訓練數據設置權值，進而對未知數據和未知異常數據進行檢測進而判斷概念漂移。

在進行對實驗中，每個數據塊的大小均取2 500。KLDT算法以準確率與相對熵為判斷標準。本實驗由于每個數據集的性質以及屬性不同，所以將決策樹作為分類器對每個數據集進行分類的準確率大有不同。實驗結果如表2所示。

表2 不同算法準確率對比 %

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

為了使該方法更具有泛化性，本文進行了數次實驗。其中數據塊的大小分別設為100、200、500、1 000、1 500、2 000、2 500和5 000。實驗結果如表3所示。

表3 不同塊大小的準確率 %

根據表3可以看出，在RBF、LED、SEA、HyperPlane數據集上，當數據塊大小為5 000時，提出的算法獲得了最優準確率。只有當ELEC數據集在數據塊為100時準確率最高，而在數據塊為5 000時卻是次優解。具體情況如圖1-圖5所示。

圖1 RBF數據集的準確率

圖2 LED數據集的準確率

圖3 SEA數據集的準確率

圖4 HyperPlane數據集的準確率

圖5 ELEC數據集的準確率

圖1-圖5可以看出準確率的波動并不是非常大，主要是因為若產生概念漂移或者是確定發生概念漂移，分類器都得到了及時的更新。根據圖1-圖5不同塊大小的準確率，可以看出當數據塊大小為5 000個數據時準確率特別的高，而數據塊大小為100個數據時具有最低的準確率。當數據塊較小時對概念漂移比較敏感，所以準確率較低，而當數據塊相對較大時，對概念漂移不是特別敏感，則準確率相對較高。相反的是，圖3所示的準確率在數據塊相對較小時，具有較高的準確率。表2中當數據塊為2 500個數據時的準確率相比WOCSVM較低，當數據塊大小取500、200、100個數據時則高出WOCSVM算法的準確率。

4 結 語

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

[1] 丁劍,韓萌,李娟.概念漂移數據流挖掘算法綜述[J].計算機科學,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].計算機研究與發展,2007,44(11):1809-1815.

[6] 李培培.數據流中概念漂移檢測與分類方法研究[D].合肥:合肥工業大學,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] 姚遠.海量動態數據流分類方法研究[D].大連:大連理工大學,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。國家自然科學基金面上項目(61373127)。楊帆，碩士生，主研領域：機器學習。張永，副教授。

TP311

A

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