基于可信多數投票的快速概念漂移檢測

摘要: 數據流因具有數據持續到達，概念漂移產生時刻無法預測、概念的數量不確定等特征，使得滑動窗口的大小很難事先確定，滑動窗口包含概念的數量對概念漂移檢測存在影響。本文提出了基于可信多數投票的快速概念漂移檢測算法(CMV_SEA)，該算法使用SEA算法中的基分類器淘汰方法，使用可信多數投票實現滑動窗口中基分類器的集成。仿真實驗表明:相比于SEA算法，CMV_SEA算法提高了泛化能力;能在新概念產生的第一時間內檢測到概念漂移;對概念漂移的檢測能力和新概念的學習能力不受滑動窗口大小的影響。

關鍵字:學習系統;數據流;概念漂移

Fast Detecting Concept Drifts Based on Confident Majority Voting

Yi-Min Wen1，2#8224;， Yao-Nan Wang1， Ying-Zhang3

(1.College of Electrical and Information Engineering， Hunan Univ， Changsha， Hunan 410082， China

2.Hunan Industry Polytechnic， Changsha， Hunan 410208， China

3.College of Information Engineering， Xiangtan Univ， Xiangtan， Hunan 411105， China)

Abstract: Data stream has the characteristics of data comes continuously， the time of concept drift and the number of concept in it cannot be predicted exactly， so the size of window is difficultly to be set exactly and the number of concept in one window will affect the detecting of concept drift. The paper proposed an algorithm to fast detect concept drifts in data streams by taking a confident majority voting strategy(CMV-SEA)， the algorithm replaces base classifiers in a window like SEA does and uses majority voting strategy to ensemble all base classifiers in the window. The experimental results illustrated that CMV_SEA can promote predictive accuracy， detect concept drifts as soon as a new concept comes， and its ability to detect and learn a new concept don’t be influenced by the size of window.

Key words: learning systems; data stream; concept drift

在社會實踐中，有一類問題是數據所包含的概念隨時間而變化，也就是概念產生漂移。自動化生產線上，相近原因的問題產品會連續出現，然后由于原因的變化而導致問題產品的特征也隨之發生變化;商務活動中，顧客的購買興趣隨時間而變化;網絡安全中，網絡的訪問模式隨用戶不同而變化。這些問題的共同特點是:不斷產生的數據形成一個流;數據流沒有終點;數據流中的概念何時產生無法預測;數據流包含的概念的數量不確定。如果能盡早地檢測到概念漂移，則可以對不斷到來的數據盡可能早地正確判斷。因此，實現對經濟和社會領域的產品流或信息流的快速概念漂移檢測將帶來巨大的經濟和社會效益。

數據流分類問題已經引起眾多學者的關注。Schlimmer首次研究了數據流分類問題，提出了STAGGER算法[1]。Widmer、Salganicoff、Harries和Domingos等分別提出了FLORA[2]、PECS[3]、SPLICE[4]和VFDT[5]。王濤等改進VFDT后提出了fVFDT[6]。Wang等的研究表明:以上算法所學習到的模型只反映了部分最新數據包含的概念，這通常會導致較大誤差[7]。因此，國內外學者開始嘗試利用集成學習策略來處理數據流分類的概念漂移問題。Street等提出了SEA算法[8]，該算法首先根據一個評分標準淘汰舊的基分類器而保持基分類器總數不變的方法實現對概念漂移的學習，然后采用多數投票算法實現對概念漂移的檢測。Wang等則使用帶權多數投票算法實現對概念漂移的檢測，各基分類器的權值分別與其對最新近采集的數據集的錯誤率成反比[7]。Kolter等提出了動態帶權多數投票算法[9]。該算法根據最新近采集到的一個樣本對已訓練的各個基分類器的權值進行修改，同時還使用這個樣本對已訓練的基分類器進行增量學習或訓練一個新的分類器，以提高算法對概念漂移的檢測速度。孫岳等提出了一種基于多分類器的概念漂移挖掘算法[10]。相對于SEA算法，Wang、Kolter和孫岳的算法的共同特點是根據權值淘汰滑動窗口中的基分類器，同時利用權值實現對概念漂移的檢測，而權值的計算都是根據最新近采集的樣本。因此，以上全部算法的有效實現都有個前提——事先需要設置好滑動窗口的大小。然而，在實際問題中很難做到這一點。

本文提出了一種基于可信多數投票的概念漂移快速檢測算法。該算法對概念漂移的檢測不受滑動窗口大小的影響;滑動窗口中基分類器的更新采用SEA算法中的方法;概念漂移的檢測使用可信多數投票(confident majority voting， CMV)[11]。仿真實驗表明:相比SEA算法，本文提出的算法對概念漂移的檢測能力和對新概念的學習能力的確不受滑動窗口大小的影響，同時可信多數投票算法提高了泛化能力，最重要的是該算法切實提高了對概念漂移的反應速度。

1、分類置信度與可信多數投票

對一個分類器，除了希望它有很高的泛化能力以外，還希望其能夠對其輸出的分類結果本身給出確切性度量，即分類置信度。分類器的分類置信度是一個很重要的信息。當多個分類器的結果不一致時，應當選擇置信度較大的分類結果。有如多位專家參與決策，當各個專家給出的意見不一致時，傾向于采納權威專家的意見。

若測試樣本 被分類器 分類為 類，則對 的分類置信度 的定義如下:

(1)

其中: 為測試樣本 的真正類別， 為概率。

分類置信度計算已經有許多工作，劉明等提出了一種將局部分類精度變換為分類置信度的方法[12];Woods則使用局部類別準確率來計算分類置信度[13]。Woods提出的方法對分類算法本身沒有要求，是一種通用的計算分類置信度的方法。經過分析發現局部類別準確率是式(1)定義的分類置信度的一種近似[14]，下文中分類置信度的計算采用該方法。

本文對[11]提出的可信多數投票算法進行了改進，算法如圖1。

CMV( ， ， ， ， ， )

2、快速概念漂移檢測算法

為說明方便，將提出的算法命名為CMV_SEA，其主要思路為:將數據流分割成多個固定大小的數據塊，每順序采集到一個數據塊就訓練一個基分類器;采用支持向量機作為基分類器;滑動窗口的大小可以隨意設置;基分類器的淘汰采用SEA算法中的方法;當有測試樣本時，使用滑動窗口中的基分類器對該測試樣本進行可信多數投票而得到對該測試樣本的判斷結果。算法描述如圖2所示。

3、仿真實驗

為了評估CMV_SEA算法的泛化能力、概念漂移的檢測速度和對新概念的學習能力，在各種滑動窗口大小條件下進行了實驗。實驗環境為:2.8GHz CPU和4G RAM;操作系統平臺為windows;基分類器訓練使用libSVM，緩存的大小使用缺省設置。

3.1 數據集的選擇

實驗使用了測試數據流分類算法的經典數據集SEA[7]。該數據集中樣本為三維向量 ， ， 。概念被順序描述為 ， ， 與 和 不相關。因此，SEA數據集包含4種SEA概念。對每個概念分別隨機產生12500個樣本用于訓練和2500個樣本用于測試。在本文實驗中 、 。由于 ，因此每種概念的訓練集包含了25個數據塊?；瑒哟翱诒辉O置成 時，能保證在某個時刻滑動窗口中的各個基分類器同屬于一個概念。

實驗分兩種，第一種實驗中滑動窗口包含的概念不超過3種。在該實驗中，概念被先后設置成 、 、 、 。因此，數據流中要出現3次概念漂移。在各次實驗中，滑動窗口被分別設置成 、 、 、 。第二種實驗中滑動窗口包含的概念至少有3種。在該實驗中，概念被先后設置成 、 、 、 、 ，也就是概念 被重復一次。因此，數據流中要出現4次概念漂移。窗口大小被設置成 。因此，當第二個 的概念出現時，滑動窗口中肯定還包含有屬于第一個 概念的數據塊。

各實驗被重復100次，實驗結果為100次實驗的平均值。

3.2 學習能力和概念漂移檢測速度實驗

從圖3-圖6可以看出:(1)在各種滑動窗口大小條件下，CMV_SEA算法對概念漂移的檢測速度都比SEA算法要快。當屬于新概念的第一個數據塊被學習后，CMV_SEA算法的泛化能力馬上得到明顯提升。而SEA算法則需要等到屬于新概念的若干個數據塊學習了以后泛化能力才能得到提升;這是由于CMV_SEA算法采用了可信多數投票，滑動窗口中不屬于新概念的基分類器被屏蔽不能參加投票，因此一旦有屬于新概念的分類器訓練好，該分類器馬上就能發揮其對新概念樣本的識別能力。而SEA算法中采用的是多數投票法，屬于新概念的基分類器的數量不達到多數，SEA算法就不會輸出新概念;(2)從圖3-圖6的前25個數據塊可以看到，相比于多數投票算法，可信多數投票算法提高了泛化能力。這是由于CMV有效降低了方差(Variance)[14]。(3)滑動窗口大小為 或 時，SEA算法對新概念的識別能力下降，對新概念的檢測出現延時，而且對新概念的識別能力難以恢復，而CMV_SEA算法對新概念的識別能力很穩定。這是因為當 或 時，滑動窗口包含的概念最多不超過2種，而當 或 時，滑動窗口包含的概念有時會達到3種。

從圖7可以看出:從概念 變化到第二個 概念時，CMV_SEA算法沒有出現像SEA算法一樣在當第二個 概念出現前后的準確率出現大幅度變化，而是保持不變。根據SEA算法的基分類器淘汰規則可以知道:當滑動窗口中基分類器數量第一次達到最大時，滑動窗口中屬于 概念的基分類器數量為25，屬于 概念的基分類器數量為25，而屬于 概念的基分類器數量為13。隨著屬于 概念的基分類器繼續產生，屬于該概念的基分類器會逐步替換滑動窗口中屬于 概念的基分類器，直至 的概念第二次出現前，滑動窗口中還包含有屬于 概念的基分類器25個，屬于 概念的基分類器13個，屬于 概念的基分類器25。因此，在整個 、 概念的學習過程中屬于它們的基分類器數量不能達到大多數，所以SEA算法對這兩個概念的檢測效果不好。當屬于 概念的基分類器再次出現時，滑動窗口中屬于 概念的基分類器數量達到26而占大多數，因而此時SEA算法會出現準確率的大幅度提升。對于CMV_SEA算法而言，在學習概念 的整個過程中，滑動窗口中始終包含有屬于第一個 概念的基分類器，可信多數投票方法能激發這些基分類器輸出而屏蔽滑動窗口中的其他分類器。因此，當屬于 概念重新出現時CMV_SEA算法的準確率不會出現波動，而且保持對新概念的檢測能力。

4、結論

針對已經提出的多個基于分類器集成的數據流概念漂移檢測算法都不能很好地適應滑動窗口大小的變化，本文提出使用可信多數投票算法實現對概念漂移的快速檢測。仿真實驗表明:相比于SEA算法，CMV_SEA算法提高了泛化能力;能在新概念產生的第一時間內檢測到概念漂移;對概念漂移的檢測能力和新概念的學習能力不受滑動窗口大小的影響。未來將研究如何結合在線增量學習算法通過對數據流中樣本的選擇性學習，以進一步提高概念漂移的檢測速度。

參考文獻:

[1]SCHLIMMER J C， GRANGER R H. Incremental learning from noisy data[J]. Machine Learning， 1986， 1(3):317-354.

[2]WIDMER G， KUBAT M. Learning in the presence of concept drift and hidden contexts[J]. Machine Learning， 1996，23(1):69-101.

[3]SALGANICOFF M. Tolerating concept and sampling shift in lazy learning using prediction error context switching[J]. Artificial Intelligence Review(Special Issue on Lazy Learning)，1997，11(1-5):133-155.

[4]HARRIES M B， SAMMUT C， HORN K. Extracting hidden context[J]. Machine Learning， 1997，27(3):259-286.

[5]DOMINGOS P， HULTEN G. Mining high-speed data streams[C]//Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. USA， Boston， 2000: 71-80.

[6]王濤，李舟軍，胡小華，等。一種高效的數據流挖掘增量模糊決策樹分類算法[J]。計算機學報，2007，30(8):1245-1250.

WANG TAO， LI ZHOU-JUN， HU XIAO-HUA， et al. An incremental fuzzy decision tree classification method for data streams mining based on threaded binary search trees[J]. Chinese Journal of Computers， 2007，30(8): 1245-1250(In Chinese).

[7]WANG H， FAN W， YU S， et al. Mining concept-drifting data streams using ensemble classifiers[C]//Proceeding of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. USA， Washington， 2003: 226-235.

[8]STREET W N， KIM Y S. A streaming ensemble algorithm for large-scale classification[C]//Proceeding of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. USA， San Francisco， 2001: 377-382.

[9]KOLTER J Z， MALOOF M A. Dynamic weighted majority: a new ensemble method for tracking concept drift[C]//Proceedings of the 3th IEEE Conference on Data Mining. USA， Los Alamitos， 2003: 123-130.

[10]孫岳，毛國君，劉旭，等。 基于多分類器的數據流中的概念漂移挖掘[J]。自動化學報，2008，34(1):93-96.

SUN YUE， MAO GUO-JUN， LIU XU， et al. Mining concept drift from data streams based on multi-classifiers[J]. ACTA AUTOMATICA SINICA， 2008，34(1):93-96(In Chinese).

[11]WEN Y M， LU B L. A confident majority voting strategy for parallel and modular support vector machines[C]//Proceedings of the 3th International Symposium on Neural Networks. China， Nanjing， 2007:525-534.

[12]劉明，袁保宗，苗振江，等。從局部分類精度到分類置信度的轉換[J]。計算機研究與發展，2008，45(9):1612-1619.

LIU MING， YUAN BAO-ZONG， MIAO ZHENG-JIANG， et al. Transformation from local accuracy to classification confidence[J]. Journal of Computer Research and Development， 2008，45(9):1612-1619(In Chinese).

[13]WOODS K， KEGELMEYER W P J， BOWYER K. Combination of multiple classifiers using local accuracy estimates[J]. IEEE Trans. Pattern Analysis and Machine Intelligence， 1997， 19:405-410.

[14]文益民. 支持向量機的并行學習與增量學習方法研究[D]. 上海:上海交通大學計算機科學與工程系，2007.

WEN YI-MIN. A study on parallel and incremental learning of support vector machines[D]. Shanghai: Department of Computer Science Engineering in Shanghai Jiao Tong Univ.， 2007(In Chinese).