張寶菊，陳一迪，薛 磊

（天津師范大學(xué) 天津市無線移動(dòng)通信與無線電能傳輸重點(diǎn)實(shí)驗(yàn)室，天津 300387）

現(xiàn)實(shí)生活中不斷產(chǎn)生著大量數(shù)據(jù).從數(shù)據(jù)分布角度來看，靜態(tài)數(shù)據(jù)的分布相對(duì)穩(wěn)定，而數(shù)據(jù)流是動(dòng)態(tài)的，其包含的概念可能隨時(shí)間變化而不斷改變，即發(fā)生概念漂移.概念漂移不僅要求數(shù)據(jù)流上的學(xué)習(xí)算法具有較高的分類精度，而且還要能夠適應(yīng)動(dòng)態(tài)變化的環(huán)境并做出正確的決策.目前，相關(guān)領(lǐng)域的學(xué)者已提出許多有效的學(xué)習(xí)算法來檢測(cè)數(shù)據(jù)流的概念漂移[1-12].文獻(xiàn)[1]基于概念相似性的錯(cuò)誤方差提出了DDM（Drift detection method）方法，該方法根據(jù)伯努利數(shù)據(jù)分布設(shè)定閾值來區(qū)分概念漂移和噪聲漂移.文獻(xiàn)[2]提出的基于信息熵的概念漂移檢測(cè)方法通過比較2個(gè)相鄰窗口的數(shù)據(jù)分布差異來判斷概念漂移及重復(fù)概念.文獻(xiàn)[3]利用約束懲罰回歸組合器來追蹤挖掘概念漂移.文獻(xiàn)[4]首次將集成分類技術(shù)引入到數(shù)據(jù)流分類中，并提出了SEA算法.文獻(xiàn)[5]針對(duì)集成分類器訓(xùn)練時(shí)間過長的問題，提出了一個(gè)在線的集成分類器模型.本文著重分析概念漂移對(duì)分類器的影響，在一定的概率下檢測(cè)概念漂移，并將其應(yīng)用于基于Choquet模糊積分[13]的集成學(xué)習(xí)算法，從而構(gòu)建一個(gè)集成分類器，實(shí)現(xiàn)漂移檢測(cè)的同時(shí)及時(shí)更新分類器模型.

1 概念漂移的并行檢測(cè)機(jī)制

1.1 基于錯(cuò)誤率的檢測(cè)方法

錯(cuò)誤率是衡量概念漂移算法的常用指標(biāo)，當(dāng)發(fā)生漂移時(shí)，分類模型將不再適合當(dāng)前的概念，錯(cuò)誤率就會(huì)上升.將數(shù)據(jù)集劃分為數(shù)據(jù)塊的形式，每個(gè)數(shù)據(jù)塊包含N個(gè)樣本，目標(biāo)函數(shù)f在數(shù)據(jù)塊D上的錯(cuò)誤率記作errorD（E），其中D滿足分布Φ.若前一個(gè)數(shù)據(jù)塊的錯(cuò)誤率是errori（E），則當(dāng)前數(shù)據(jù)塊上的錯(cuò)誤率是errori+1（E），當(dāng)errori+1（E）∈（errori（E）-σzα，errori（E）+σzα）時(shí)，在1-α的置信度下，當(dāng)前數(shù)據(jù)塊不會(huì)發(fā)生概念漂移，否則認(rèn)為當(dāng)前數(shù)據(jù)已經(jīng)出現(xiàn)異常.其中：zα是由置信度α和標(biāo)準(zhǔn)正態(tài)分布決定的常量，σ≈

1.2 基于漂移度的檢測(cè)方法

為了比較當(dāng)前數(shù)據(jù)塊和前一數(shù)據(jù)塊之間的差異，本研究采納歐氏距離定義漂移度的概念.對(duì)于當(dāng)前數(shù)據(jù)塊中的每個(gè)樣本（實(shí)例）xi，計(jì)算其與前一數(shù)據(jù)塊中所有樣本的歐氏距離，并比較它們的值，將距離最小值的樣本定義為最近鄰樣本，歐式距離計(jì)算公式為

其中：xi是當(dāng)前數(shù)據(jù)塊中的實(shí)例；xj是前一個(gè)數(shù)據(jù)塊中的實(shí)例；m是xi、xj的屬性數(shù).對(duì)于數(shù)值屬性a，rangea是該屬性數(shù)值中最大值和最小值的差，此處對(duì)其值的范圍進(jìn)行了歸一化處理.

比較xi與其最近鄰實(shí)例的類別標(biāo)簽，如果它們具有相同的類別， 則令 dis（i）=0， 否則 dis（i）=1.漂移度DE的計(jì)算公式為

其中dE（i）為dE（xi，xj）的最小值.若漂移度DE的值增加，則認(rèn)為發(fā)生了概念漂移.

1.3 概念漂移的并行檢測(cè)

基于錯(cuò)誤率和漂移度，本文提出概念漂移的并行檢測(cè)機(jī)制.首先使用學(xué)習(xí)算法訓(xùn)練模型獲得每個(gè)數(shù)據(jù)塊的分類錯(cuò)誤率，然后比較預(yù)測(cè)錯(cuò)誤率，若其超出單側(cè)置信區(qū)間，再計(jì)算基于歐氏距離的概念漂移度，若漂移度上升，表明數(shù)據(jù)分布很可能發(fā)生了變化，認(rèn)為發(fā)生了概念漂移.其實(shí)現(xiàn)過程如下：

輸入 數(shù)據(jù)塊 D1，D2，…，Di，Di+1，…； 每個(gè)數(shù)據(jù)塊包含的樣本數(shù)為N.

輸出分類錯(cuò)誤率errori；漂移度DE（i）；預(yù)測(cè)結(jié)果.

過程

①按照數(shù)據(jù)流到達(dá)的順序?qū)⑵浞謮K，數(shù)據(jù)塊包含的樣本數(shù)均為N.

②初始化errori=0，DE（i）=0.

③對(duì)每一個(gè)數(shù)據(jù)塊Di，使用貝葉斯分類算法進(jìn)行分類，返回分類錯(cuò)誤率.若

則計(jì)算基于歐氏距離的漂移度DE（Di+1）和DE（Di），若DE（Di+1）＞DE（Di），則判定發(fā)生概念漂移.

2 基于模糊積分的集成系統(tǒng)

2.1 模糊測(cè)度μ和Choquet積分

本文利用Choquet模糊積分[14]構(gòu)建集成分類器.

定義1設(shè)X為非空集合，F(xiàn)（X）為其子集構(gòu)成的集合，稱μ：F→[0，∞）為定義在F（X）上的模糊測(cè)度，若

（2）對(duì)任意 X1、 X2∈F（X）， 若 X1?X2， 則 μ（X1）≤μ（X2）， 即具有單調(diào)性.

在分類器學(xué)習(xí)領(lǐng)域，通常用μ表征各分類器的重要程度.μ的值越高，其分類結(jié)果準(zhǔn)確率越高，這里直接將μ值視為各分類器的預(yù)測(cè)準(zhǔn)確率.

定義2對(duì)于一個(gè)有限集合X={x1，x2，…，xn}，令μ為定義在X上的一個(gè)模糊測(cè)度，h是定義在X上的實(shí)值可測(cè)函數(shù)，則h關(guān)于μ的Choquet模糊積分為

其中： 0≤h（x1）≤…≤h（xn）≤1， C 為常數(shù).

2.2 基于Choquet模糊積分的集成分類系統(tǒng)

以模糊測(cè)度μ和基分類器的輸出作為Choquet積分的輸入，構(gòu)建集成分類系統(tǒng).設(shè)L個(gè)分類器為E1，E2，…，EL，通過對(duì)樣本x的學(xué)習(xí)，每個(gè)分類器得到一個(gè)m維向量.L個(gè)分類器的向量構(gòu)成矩陣

其中：第j行為第j個(gè)分類器的m維向量；dj，k表示第j個(gè)分類器判斷樣本為第k類的可能性.

基于Choquet積分的分類器集成過程如圖1所示.

2.3 用于概念漂移的模糊積分集成系統(tǒng)

對(duì)每一數(shù)據(jù)塊進(jìn)行獨(dú)立學(xué)習(xí)，得到每個(gè)分類器的分類性能，確定μi，作為Choquet積分的因子.根據(jù)式（3）和式（4）計(jì)算當(dāng)前樣本屬于每個(gè)類別的可能性，并根據(jù)最大隸屬原則選擇預(yù)測(cè)類別作為最終的分類輸出.

根據(jù)并行檢測(cè)機(jī)制對(duì)概念漂移進(jìn)行檢測(cè)，若檢測(cè)到概念漂移，則利用模糊測(cè)度重新計(jì)算Choquet積分，選擇具有最大值的類別作為最后的分類輸出結(jié)果，動(dòng)態(tài)更新集成分類系統(tǒng)，以適應(yīng)新的數(shù)據(jù)流環(huán)境.

圖1 基于Choquet積分的集成系統(tǒng)框架Fig.1 Integrated system framework based on Choquet integral

3 實(shí)驗(yàn)

3.1 數(shù)據(jù)集

（1）UCI數(shù)據(jù)庫：本文選擇UCI中的Ionosphere、Iris、Hypothyroid等3個(gè)數(shù)據(jù)集.數(shù)據(jù)集的實(shí)例數(shù)NI，屬性數(shù)NA和類別數(shù)NC見表1.

表1 UCI庫的數(shù)據(jù)集描述Tab.1 Dataset description of UCI library

（2）SEA 數(shù)據(jù)集：SEA 數(shù)據(jù)集的結(jié)構(gòu)為（f1，f2，f3，C），其中：f1、f2為條件屬性，f3為不相關(guān)屬性，C為包含2個(gè)類別標(biāo)簽的類別屬性.當(dāng)f1+f2≤θ時(shí)，實(shí)例屬于類1，否則屬于類2.給定閾值θ，當(dāng)閾值分別為9、8、7和9.5時(shí)，可以形成4個(gè)不同的概念.該數(shù)據(jù)集由MOA生成，它是一款開源數(shù)據(jù)流挖掘軟件，可生成具有概念漂移的數(shù)據(jù).實(shí)驗(yàn)中隨機(jī)生成104個(gè)實(shí)例，包含4個(gè)概念和3個(gè)概念漂移，噪聲率為10%.

（4）瑞典電網(wǎng)數(shù)據(jù)集：為了評(píng)估算法在實(shí)際應(yīng)用中的性能，選取了瑞典電網(wǎng)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn).該數(shù)據(jù)集為真實(shí)數(shù)據(jù)集，包含2 190個(gè)實(shí)例，12個(gè)條件屬性，按照時(shí)間分為2種類別.該數(shù)據(jù)集可用于檢測(cè)電力消費(fèi)中的概念漂移.

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

實(shí)驗(yàn)1為驗(yàn)證并行檢測(cè)機(jī)制的有效性，在SEA數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，使用誤檢率（False alarms）、漏檢率（Missing）以及檢測(cè)時(shí)延（Delay）3個(gè)指標(biāo)對(duì)概念漂移檢測(cè)方法進(jìn)行性能分析，包含3次漂移，噪聲率為10%，數(shù)據(jù)塊大小為100.進(jìn)行了10輪實(shí)驗(yàn)取平均值，結(jié)果見表2.

表2 SEA數(shù)據(jù)集上的概念漂移檢測(cè)性能比較Tab.2 Performance comparison of concept drift detection on SEA datasets

由表2數(shù)據(jù)可見，本文的并行檢測(cè)機(jī)制的誤檢率最低，時(shí)延最小，說明概念漂移的并行檢測(cè)機(jī)制較單一檢測(cè)更高效，結(jié)果更可靠.

實(shí)驗(yàn)2將本文的集成分類器與常見的經(jīng)典集成算法（Vote、Stacking、Bagging）進(jìn)行分類精度比較，實(shí)驗(yàn)在UCI庫的3個(gè)數(shù)據(jù)集上分別進(jìn)行，為保證實(shí)驗(yàn)的準(zhǔn)確性，均采用十折交叉驗(yàn)證的方法，得到平均水平下的集成分類器的性能表現(xiàn).實(shí)驗(yàn)結(jié)果見表3.

表3 模糊積分集成分類器與其他集成分類器的精度Tab.3 Accuracies of fuzzy integral ensemble classifier and other ensemble classifiers %

由表3數(shù)據(jù)可見，本文基于Choquet積分的集成分類器在3個(gè)數(shù)據(jù)集上均有較好的性能，僅在Ionosphere上略差于Stacking算法，總之，實(shí)驗(yàn)說明本文的集成分類器是有效的.

實(shí)驗(yàn)3為了測(cè)試本文的用于概念漂移的模糊積分集成系統(tǒng)的性能，選擇MOA平臺(tái)上常用的Naive Bayes、OzaBag和AWE算法作為對(duì)比算法.實(shí)驗(yàn)結(jié)合Weka和Matlab平臺(tái)進(jìn)行.

首先，在數(shù)據(jù)集SEA上進(jìn)行實(shí)驗(yàn)，按數(shù)據(jù)到達(dá)的先后順序進(jìn)行分塊處理，輸入集成系統(tǒng)進(jìn)行檢測(cè)，實(shí)驗(yàn)結(jié)果見圖2.

圖2 SEA數(shù)據(jù)集的預(yù)測(cè)精度Fig.2 Predicted accuracies of the SEA dataset

由圖2可知，在系統(tǒng)運(yùn)行過程中，幾種算法均出現(xiàn) 3 處（數(shù)據(jù)塊范圍為 20～30、45～55、70～80）較為明顯的精度低點(diǎn)，這是受到概念漂移的影響，本文的集成系統(tǒng)能很快識(shí)別出概念分布的變化并進(jìn)行更新，從而使精度迅速提升.在數(shù)據(jù)平穩(wěn)階段（5～20、30～45、55～70、80～100）， 本文算法的分類精度最高.

其次，將超平面數(shù)據(jù)集進(jìn)行分塊處理，數(shù)據(jù)集包含6×104個(gè)、噪聲率為10%的實(shí)例，每104個(gè)實(shí)例發(fā)生一次漂移.實(shí)驗(yàn)結(jié)果見圖3.

圖3 超平面數(shù)據(jù)集的預(yù)測(cè)精度Fig.3 Predicted accuracies of the hyperplane dataset

由圖3可以看出，在5次概念漂移發(fā)生的位置，4種分類算法的準(zhǔn)確率均迅速下降.在無概念漂移發(fā)生時(shí)，本文算法具有更高的精度.在發(fā)生概念漂移的瞬間，本文算法的精度立即降到最低，而后又在短時(shí)間內(nèi)迅速進(jìn)入平穩(wěn)階段，這說明本文算法對(duì)概念漂移十分敏感.而其他3種算法在概念漂移發(fā)生時(shí)，其精度曲線起伏不明顯.因此，本文模型更適合于對(duì)含有概念漂移的數(shù)據(jù)流進(jìn)行分類處理.

最后，在瑞典電網(wǎng)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果見圖4.

圖4 瑞典電網(wǎng)數(shù)據(jù)集的預(yù)測(cè)精度Fig.4 Predicted accuracies of the Swedish grid dataset

由圖4可看出，本文模型與其他集成模型在某些數(shù)據(jù)塊上均出現(xiàn)了精度降低的現(xiàn)象，這是概念漂移造成的.但本文模型一旦檢測(cè)到概念漂移就會(huì)自適應(yīng)調(diào)整，從而精度又迅速回升，而其他算法的精度起伏不明顯，且其精度均低于本文模型，這說明本文模型更適用于真實(shí)數(shù)據(jù)流的概念漂移檢測(cè)及分類集成.

實(shí)驗(yàn)4將本文算法與對(duì)比算法在各數(shù)據(jù)集上的整體分類精度進(jìn)行比較，結(jié)果見表4.

表4 實(shí)驗(yàn)數(shù)據(jù)集分類精度的比較Tab.4 Comparison of classification accuracy of experimental datasets %

由表4可見，本文算法與其他3種算法比較，除在超平面數(shù)據(jù)集上略差于AWE算法，在每個(gè)數(shù)據(jù)集上均具有更好的性能表現(xiàn).

4 結(jié)語

本文提出一種概念漂移的并行檢測(cè)機(jī)制，并利用Choquet模糊積分構(gòu)建集成分類器.在不同數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，并與已有算法進(jìn)行比較，結(jié)果表明該算法在分類精度和概念漂移檢測(cè)方面均具有良好的性能，且對(duì)人工模擬數(shù)據(jù)流和真實(shí)數(shù)據(jù)流均具有較強(qiáng)的適應(yīng)性和表現(xiàn).