陸元福++彭天慈++季開洋++談海宇

摘要：隨著云計算、物聯(lián)網(wǎng)等技術(shù)的興起，流數(shù)據(jù)作為一種新型的大數(shù)據(jù)形態(tài)廣泛存在于各個鄰域。該文提出面向大數(shù)據(jù)的基于分布式計算平臺Storm的流分類挖掘算法及系統(tǒng)，采用并行化窗口和CVFDT算法，利用分布式平臺來檢測數(shù)據(jù)流中是否發(fā)生概念漂移，從而自適應(yīng)的改變建模樣本數(shù)據(jù)的流入，提高流數(shù)據(jù)模型的準確率和效率。

關(guān)鍵字：大數(shù)據(jù)；數(shù)據(jù)挖掘；分類算法；概念漂移

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2016）09-0011-03

Design and Implementation of Flow Mining Algorithm and Resistance Concept Drift System Based on Storm Platform

LU Yuan-fu， PENG Tian-ci， Ji Kai-yang， TAN Hai-yu

（College of Computer Science， Nanjing University of Posts and Telecommunications， Nanjing 210046， China）

Abstract：With the rise of cloud computing and Internet of things（LOT） technology，stream data widely exist in all fields as a new mega data form.This article propose a stream-classifying algorithm and system oriented to big data，which is based on DCP （Distributed Computing Platform）.Parallelize windows and CVFDT algorithm are both adopted.We use a DCP to test whether the mutation concept drift happened in data stream，so as to change the inflow of modeling sample data adaptively.The accuracy and efficiency of stream data model will be improved at last.

Key words： big data； data mining； classifying algorithm； concept drift

1 背景

隨著云計算、互聯(lián)網(wǎng)+等技術(shù)的快速發(fā)展，生產(chǎn)制造控制、無線通信網(wǎng)絡(luò)、電子商務(wù)交易、金融信息監(jiān)控等領(lǐng)域形成了高速、海量、動態(tài)的數(shù)據(jù)流，而有效的對數(shù)據(jù)流進行處理并從中挖掘有價值的信息就顯得尤為重要。

在流數(shù)據(jù)分類挖掘中，概念漂移是指流數(shù)據(jù)特性的改變使得目標分類模型隨著時間的變化而變化。針對流數(shù)據(jù)挖掘過程中的概念漂移問題，Hulten等人提出了概念自適應(yīng)快速決策（Concept-adaptingVeryFastDecisionTree，CVFDT）算法[1]。CVFDT 算法是一種擴展了VFDT算法用以解決概念漂移問題的高效算法，通過在原有的算法基礎(chǔ)上改進添加滑動窗口使得建立決策樹模型的數(shù)據(jù)流能夠不斷實現(xiàn)更新，從而保證在概念漂移的數(shù)據(jù)流中模型建立的準確率。

本文主要討論研究了基于分布式實時計算系統(tǒng)STORM平臺的去概念漂移算法及系統(tǒng)的設(shè)計與實現(xiàn)，在流挖掘過程中，利用分布式平臺的特點采用并行化窗口方案來檢測數(shù)據(jù)流中是否發(fā)生概念漂移，并行化窗口bin-win根據(jù)數(shù)據(jù)流中的概念漂移自適應(yīng)調(diào)整窗口大小，從而自適應(yīng)的改變建模樣本數(shù)據(jù)的流入，提高了流數(shù)據(jù)的準確性和高效性。

2 算法分析與實現(xiàn)

2.1 CVFDT算法

2.1.1 CVFDT算法的原理

概念自適應(yīng)快速決策樹（CVFDT）[2]是一種擴展了VFDT算法用以解決概念漂移問題的高效算法，具有類似VFDT的HT樹生成過程，在保持了VFD的速度和精度的前提下，能夠處理樣本產(chǎn)生過程中所出現(xiàn)的概念漂移問題[3]。CVFDT對樣本維持一個滑動窗口，并能夠動態(tài)改變窗口的大小。CVFDT算法過程包括CVFDTGrow過程、ForgetExample過程、RemoveExample過程和CheckSplitValidity過程。算法主要思想是先根據(jù)當前的數(shù)據(jù)構(gòu)建臨時決策樹，然后并不斷地獲取新的數(shù)據(jù)去優(yōu)化已建立的決策樹。若在某個時候出現(xiàn)了概念漂移，則算法會在出現(xiàn)漂移的節(jié)點上建立一個新的替代子樹。當替代子樹的分類效果優(yōu)于當前的決策子樹時，就直接取而代之。

2.1.2 CVFDT算法抵抗概念漂移問題

概念漂移表示目標變量的統(tǒng)計特性隨著時間的推移以不可預(yù)見的方式變化的現(xiàn)象[4]。在流數(shù)據(jù)分類挖掘中，也指流數(shù)據(jù)特性的改變使得目標分類模型隨著時間的變化而變化。CVFDT周期性的掃描HT生成樹的內(nèi)部節(jié)點來檢驗原先的分裂節(jié)點是否依然是最優(yōu)的分裂屬性節(jié)點。當該節(jié)點發(fā)生了概念漂移，最優(yōu)分裂屬性節(jié)點已不再是原先的Xa。CVFDT算法會重新尋找最佳測試屬性，新的屬性不直接取代原有的測試屬性，而是成為一個替代子樹的根節(jié)點，并且依據(jù)該根節(jié)點建立替代子樹。如果后繼滑動窗口的樣本在替代子樹上有較高的分類精度，則替代子樹便取代原先的決策樹，以維持滑動窗口的樣本和更新后的決策樹的一致性。

2.2 基于STORM平臺的CVFDT算法實現(xiàn)

2.2.1 CVFDT并行化窗口抵抗概念漂移算法設(shè)計

本小節(jié)討論以STORM作為分布式實時計算平臺，結(jié)合CVFDT流挖掘算法，解決數(shù)據(jù)流的概念漂移問題，從而提高模型建立的準確性?；趕torm分布式平臺的并行化窗口抵抗概念漂移方案，通過并行化窗口bin-win對數(shù)據(jù)流實時檢測實現(xiàn)概念漂移抵抗[5-6]，窗口調(diào)整流程圖如圖1所示。

從流程圖中，可以看到并行化窗口根據(jù)數(shù)據(jù)流中的概念漂移自適應(yīng)調(diào)整窗口大小，當窗口檢測數(shù)據(jù)流未發(fā)生概念漂移時，則增大窗口中的樣本量，反之，則減小并行化窗口的大小，有利于較快的適應(yīng)概念漂移。

其中，檢測是否發(fā)生概念漂移模塊，通過對HT樹中的非葉子節(jié)點的替代子樹調(diào)用CheckSplitValidity函數(shù)，計算屬性增益，從而判斷是否發(fā)生概念漂移，流程圖如圖2 所示。

2.2.2 CVFDT算法實現(xiàn)與分析

在現(xiàn)實生活中，大部分數(shù)據(jù)都是非平穩(wěn)分布的，數(shù)據(jù)流根據(jù)時間的推移不斷發(fā)生變化，即發(fā)生了概念漂移[7]。CVFDT算法通過并行化窗口檢測數(shù)據(jù)流是否發(fā)生概念漂移，窗口太大不能快速有效的抵抗數(shù)據(jù)流中的概念漂移，窗口太小影響模型建立的時間和模型一段時間內(nèi)的穩(wěn)定性，如圖3所示在建立決策樹模型時檢測到概念漂移，則減小窗口的大小。當數(shù)據(jù)流穩(wěn)定時，則增大窗口的大小，從而有效建立準確的決策樹模型。

3 系統(tǒng)實現(xiàn)

3.1 系統(tǒng)總體架構(gòu)

CVFDT算法在STORM平臺上的實現(xiàn)方式有兩種，一種是垂直并行化實現(xiàn)，一種是結(jié)合隨機森林的實現(xiàn)，該抵抗概念漂移系統(tǒng)的設(shè)計主要基于垂直并行化的實現(xiàn)方式。系統(tǒng)包括三大模塊：并行化窗口模塊、抵抗概念漂移模塊、決策樹建立更新模塊。系統(tǒng)整體框架如圖4所示。

3.2 系統(tǒng)界面

抵抗概念漂移流分類挖掘系統(tǒng)參數(shù)設(shè)置界面如圖5所示，用戶輸入訓(xùn)練樣本、更新樣本、測試樣本以及樣本所在文件的具體地址。點擊確定之后傳輸相應(yīng)參數(shù)，CVFDT算法執(zhí)行結(jié)束之后，彈出該算法挖掘結(jié)果顯示窗口，姐main如圖6所示，結(jié)果展示界面輸出當前決策樹以及其評價結(jié)果，以及未分類樣本的標記結(jié)果[8]。

4結(jié)束語

本文以分布式實時計算STORM平臺，設(shè)計并實現(xiàn)CVFDT算法，解決在流數(shù)據(jù)挖掘過程中出現(xiàn)的概念漂移現(xiàn)象，保證了流數(shù)據(jù)分類挖掘模型的準確性和高效性。CVFDT算法對樣本數(shù)據(jù)維持一個滑動窗口，在新樣本到達的時候更新節(jié)點上的統(tǒng)計信息，并在樣本滑出窗口的時候肩上其對應(yīng)的統(tǒng)計信息。STORM平臺保證算法能夠提前預(yù)測數(shù)據(jù)流中的概念漂移，并實時更改窗口的大小，提高決策模型的準確性。

本文設(shè)計實現(xiàn)的算法與系統(tǒng)僅僅只是數(shù)據(jù)挖掘的一個方面，隨著大數(shù)據(jù)時代的到來，數(shù)據(jù)流會越來越大，并且會不斷變化，這就影響到了決策模型的建立與改善，因此，如何設(shè)計準確的算法和平臺來徹底解決流數(shù)據(jù)的概念漂移仍然需要進一步的研究。

參考文獻：

[1] Hulten G， Spencer L， and Domingos P. Mining time-changing data streams[C]//Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Francisco， California， USA， 2001： 97-106.

[2] Ganti V， Johannes Gehrke， Raghu Ramakrishnan. Mining Data Streams under Block Evolution. [J].SIGKDD Explorations， 2002， 3（2）.

[3]Street W N， Kim Y S. A streaming ensemble algorithm （SEA） for large-scale classification[C]//Proceedings of the seventh International Conference on Knowledge Discovery and Data Mining. San Francisco， USA， 2001： 377-382.

[4] Mitchell T M. Machine learning[M]. New York City： McGraw-Hill， 1997.

[5] 楊雅雙. 關(guān)聯(lián)規(guī)則的并行挖掘算法研究[D]. 西安：西安科技大學，2010.

[6] 唐耀紅. 數(shù)據(jù)流環(huán)境中關(guān)聯(lián)規(guī)則挖掘技術(shù)的研究[D]. 北京：北京交通大學，2012.

[7] Gama J. A survey on learning from data streams： current and future trends[J]. Progress in Artificial Intelligence， 2011，1（1）： 45-55.

[8] 李明， 王曉鵬. Strom《源碼分析》[M]. 北京： 人民郵電出版社， 2014.