數(shù)據(jù)流中概念漂移檢測的集成分類器設計

摘要：提出了一種稱為ICEA（incremental classification ensemble algorithm）的數(shù)據(jù)流挖掘算法。它利用集成分類器綜合技術，實現(xiàn)了數(shù)據(jù)流中概念漂移的增量式檢測和挖掘。實驗結果表明，ICEA在處理數(shù)據(jù)流的快速概念漂移上表現(xiàn)出很高的精確度和較好的時間效率。 

關鍵詞：數(shù)據(jù)挖掘； 數(shù)據(jù)流； 概念漂移

中圖分類號：TP311文獻標志碼：A

文章編號：1001－3695(2008)01－0164－04

數(shù)據(jù)流挖掘技術是數(shù)據(jù)挖掘技術中較新的研究分支。所謂數(shù)據(jù)流是指無限的數(shù)據(jù)序列持續(xù)、快速地到達，并且數(shù)據(jù)是隨著時間不斷變化的，且不可預測[1]。例如呼叫記錄、網(wǎng)頁訪問記錄以及傳感器記錄數(shù)據(jù)均屬于數(shù)據(jù)流的范疇。數(shù)據(jù)流中的數(shù)據(jù)隨著時間的流逝不斷變化，必然會導致數(shù)據(jù)流算法中概念模型不斷更新和維護。因此，這種概念模型的更新和維護也就引起了數(shù)據(jù)流中的概念漂移問題。例如在正常的數(shù)據(jù)中出現(xiàn)了一些不可預測的情況，如通貨膨脹、氣候反常或新產品上市，那么原來挖掘的消費趨向對應的知識就可能改變。這種由于潛在信息的變化而導致目標概念發(fā)生根本性變化的技術被稱為概念漂移。

1996年，Widmer等人提出了概念漂移的問題[2]，并且之后的學者利用機器學習等研究方法進行了廣泛的討論[3~6]。1997年，Salganicoff等人提出了PECS[8]算法。PECS算法是一種可以根據(jù)上下文進行選擇的懶惰學習算法。1998年，Harries等人給出了SPLICE[5]算法。SPLICE算法通過上下文聚類技術實現(xiàn)穩(wěn)定的隱藏信息的識別和局部概念的生成。2001年，Domingos等人對決策樹算法進行了改進并且給出了一種適應概念漂移的決策樹學習算法VFDT[7]。VFDT是一個典型的基于Hoeffding邊界的可以處理數(shù)據(jù)流的單分類樹決策算法。隨后，Gama等人對VFDT樹作了進一步的改進，擴展了VFDT樹的功能[8~10]。

2001年，Street等人提出了一個集成分類器算法SEA，同時，也把它應用到數(shù)據(jù)流的概念漂移的檢測中，并給出SEA concept[11]。2003年，Wang等人對集成分類器中的權值變化和裁減問題進行了討論，并且提出了根據(jù)分類器分類錯誤率動態(tài)改變權值的技術[12]。2004年，Rushing等人提出CBEA[13]，集中討論了一種基于聚類算法的集成分類器裁減問題。他們也強調了該研究領域的應用價值，特別說明在視頻數(shù)據(jù)流和網(wǎng)絡數(shù)據(jù)流中均存在隨著時間而變化的數(shù)據(jù)概念漂移問題。2004年，Chu等人將流行的Boosting技術用于數(shù)據(jù)流的概念檢測中，提出自適應集成分類器綜合挖掘方法[14]。

本文主要解決數(shù)據(jù)流中概念漂移問題的快速檢測和適應等問題。為了解決這個問題，本文利用集成分類器集成技術實現(xiàn)數(shù)據(jù)蘊藏的概念的更新和維護。隨著數(shù)據(jù)的流動和概念的改變，通過集成分類器的衰減探查與剪裁機制來控制算法的整體分類精度和算法的效率。

1集成分類器決策算法ICEA

1．1集成分類器的概念

集成分類器算法是一個由多個基礎分類器通過某種評價機制對數(shù)據(jù)流中的樣本進行綜合評價的集成算法。集成分類器算法已經(jīng)被實驗證明在處理存在概念漂移的數(shù)據(jù)流數(shù)據(jù)時比簡單的分類算法具有更好的適應性和精確性。

理論上，1988年，Kearns提出了弱學習算法與強學習算法的等價性問題[15]，即是否可以將弱學習算法提升成為強學習算法問題。1990年，Schapire證明了這樣的假設是成立的[16]，并給出了著名的Boosting方法。

這個理論也同時證明了集成分類器比一般單一分類器所具有的優(yōu)勢，即通過集成分類器進行綜合評價的效果要好于單個分類器的分類結果。

1．2集成分類算法ICEA與已有方法的比較

VFDT算法是一種典型的基于樹狀結構的單分類器數(shù)據(jù)流概念漂移檢測算法。VFDT算法是通過Hoeffding邊界以增量的形式不斷改變樹模型所維護的概念，用來適應數(shù)據(jù)流中概念漂移的現(xiàn)象。但是VFDT算法存在的主要問題在于VFDT采用單一的樹模型來維護數(shù)據(jù)流中概念的變化，在一定情況下，數(shù)據(jù)流中出現(xiàn)的概念會混雜在同一個樹模型中，導致VFDT樹模型的概念與數(shù)據(jù)流中的真實概念發(fā)生偏差。

集成分類算法SEA提出通過在模型中維護多個分類器的方法來解決上述VFDT算法的問題。SEA對每一個到達數(shù)據(jù)流的樣本，它首先聚集成一定大小的數(shù)據(jù)塊；然后將這個數(shù)據(jù)塊作為訓練用的數(shù)據(jù)集來構造分類器；最后通過評估已有的分類器來決定在集成分類器中保存哪些分類器。

基于批處理方式的SEA在概念漂移的檢測中也存在一些問題。由于SEA是基于批處理方式，它必須要收集一定的數(shù)據(jù)流樣本后才能學習到數(shù)據(jù)流中的變化。在一些情況下，當數(shù)據(jù)流中的概念發(fā)生快速變化或在某一階段數(shù)據(jù)流中只存在少量樣本可供學習，SEA將不能及時檢測到這些快速變化概念。

針對以上情況，筆者提出ICEA。ICEA是使用增量的ID4模型作為基礎分類算法，用來解決通過少量數(shù)據(jù)樣本就能夠對數(shù)據(jù)的快速變化作出反應的問題。

1．3集成分類器決策算法

ICEA的主要思想是采用增量式的學習算法作為基礎分類模型。隨著數(shù)據(jù)流的不斷變化，每個基礎的分類器都根據(jù)新到來的樣本進行增量式的學習；然后利用基礎分類器學習的結果得出全局分類結果，以此來判斷集成分類器E是否仍然適應數(shù)據(jù)的變化。當不適應時，就采用加入新分類器或者淘汰舊分類器來快速適應數(shù)據(jù)的變化。

實驗分析：從圖3中可以看出，SEA概念是采用批處理的方式學習概念，需要積累一定數(shù)量的訓練樣本才生成一個新的基礎分類器，所以在每次學習新概念時會占用較多的時間。對于增量式的ICEA來說，算法會在每一個時間點對集成分類器中的概念進行更新，加快了對數(shù)據(jù)流中數(shù)據(jù)樣本的處理速度。

總地來說，由上面三個實驗可以說明，ICEA在小容量和快速變化的概念漂移的數(shù)據(jù)流上的分類精確度和效率要優(yōu)于批處理方式的SEA。

4結束語

數(shù)據(jù)流中適應概念漂移的挖掘算法的研究是當前數(shù)據(jù)挖掘領域的一個研究熱點，而已經(jīng)提出的集成分類器算法在某些情況下還不能完全捕捉數(shù)據(jù)流中概念漂移的變化。本文提出了一種基于增量式的集成分類器算法ICEA。它通過集成分類器全局決策、集成分類器的自身更新和裁減來不斷改變自身的模型以更好地適應當前數(shù)據(jù)流中的目標概念。實驗證明，在少量訓練樣本和快速概念漂移的情況下，在精確度和時間效率上，ICEA要優(yōu)于SEA。

參考文獻：

[1]BABCOCK B， BABU S， DATAR M， et al. Models and issues in data stream systems[C]//Proc of PODS.Wisconsin:[s.n.]， 2002:1 16.

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

[3]WIDMER G， KUBAT M. Effective learning in dynamic environments by explicit context tracking[C]//Proc of the 6th European Conf on Machine Learning. Berlin:[s.n.]， 1993:227－243.

[4]WIDMER G. Tracking context changes through meta learning[J]. Machine Learning， 1997，27(3):259－286.

[5]HARRIES M， SAMMUT C， HORN K. Extracting hidden context[J]. Machine Learning， 1998，32(2):101 126.

[6]WIDYANTORO D， IOERGER T， YEN J. An adaptive algorithm for learning changes in user interests[C]//Proc of the 8th International Conference on Information and Knowledge Management. Kansas City:[s.n.]， 1999:405－412.

[7]DOMINGOS P， HULTEN G. Mining high speed data streams[C]//Proc of the 6th Association for Computing Machinery International Conference on Knowledge Discovery and Data Mining. Boston: [s.n.]， 2000:71－80.

[8]GAMA J， ROCHA R， MEDAS P. Accurate decision trees for mining high speed data streams[C]//Proc of the 9th International Confe￣rence on Knowledge Discovery and Data Mining. New York: [s.n.]， 2003:523－528.

[9]GAMA J， MEDAS P， ROCHA R. Forest trees for on line data[C]//Proc of ACM Symposium on Applied Computing. New York: [s.n.]， 2004: 632－636.

[10]GAMA J， MEDAS P， RODRIGUES P. Learning decision trees from dynamic data streams[C]//Proc of ACM Symposium on Applied Computing. New York: [s.n.]， 2005:573－577.

[11]STREET W， KIM Y. A streaming ensemble algorithm (SEA) for large scale classification[C]//Proc of the 7th ACM International Conference on Knowledge Discovery and Data Mining. New York: [s.n.]， 2001:377－382.

[12]WANG Hai xun， FAN Wei， YU P S， et al. Mining concept drifting data streams using ensemble classifiers[C]//Proc of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM Press， 2003:226－235.

[13]RUSHING J， GRAVES S， CRISWELL E， et al. A coverage based ensemble algorithm (CBEA) for streaming data[C]//Proc of the 16th IEEE International Conference on Tools with Artificial Intelligence. Washington D C: [s.n.]， 2004:106 112.

[14]CHU F， ZANIOLO C. Fast and light Boosting for adaptive mining of data streams[C]//Proc of the 5th Pacific Asia Conference on Know￣ledge Discovery and Data Mining. Sydney: [s.n.]， 2004:282－292.

[15]KEARNS M， VALIANT G. Learning boolean formulae or factoring， TR 1488[R]. Cambridge: Harvard University Aliken Computation Laboratory， 1988.

[16]SCHAPIRE R E. The strength of weak learnability[J]. Machine Learning， 1990，5(2):197－227.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”