發布時間：2016-05-28所屬分類：科技論文瀏覽：1次
摘 要： 近年來，互聯網的發展是比較迅速的，隨著云計算、互聯網+等技術的快速發展，生產制造控制、無線通信網絡、電子商務交易、金融信息監控等領域形成了高速、海量、動態的數據流，而有效的對數據流進行處理并從中挖掘有價值的信息就顯得尤為重要。本文是一篇 工
近年來，互聯網的發展是比較迅速的，隨著云計算、互聯網+等技術的快速發展，生產制造控制、無線通信網絡、電子商務交易、金融信息監控等領域形成了高速、海量、動態的數據流，而有效的對數據流進行處理并從中挖掘有價值的信息就顯得尤為重要。本文是一篇工程師論文范文，主要論述了基于Storm平臺的流挖掘算法及抵抗概念漂移系統的設計與實現。
摘要：隨著云計算、物聯網等技術的興起，流數據作為一種新型的大數據形態廣泛存在于各個鄰域。該文提出面向大數據的基于分布式計算平臺Storm的流分類挖掘算法及系統，采用并行化窗口和CVFDT算法，利用分布式平臺來檢測數據流中是否發生概念漂移，從而自適應的改變建模樣本數據的流入，提高流數據模型的準確率和效率。
關鍵字：大數據,數據挖掘,分類算法,概念漂移
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 背景
在流數據分類挖掘中，概念漂移是指流數據特性的改變使得目標分類模型隨著時間的變化而變化。針對流數據挖掘過程中的概念漂移問題，Hulten等人提出了概念自適應快速決策(Concept-adaptingVeryFastDecisionTree，CVFDT)算法[1]。CVFDT 算法是一種擴展了VFDT算法用以解決概念漂移問題的高效算法，通過在原有的算法基礎上改進添加滑動窗口使得建立決策樹模型的數據流能夠不斷實現更新，從而保證在概念漂移的數據流中模型建立的準確率。
本文主要討論研究了基于分布式實時計算系統STORM平臺的去概念漂移算法及系統的設計與實現，在流挖掘過程中，利用分布式平臺的特點采用并行化窗口方案來檢測數據流中是否發生概念漂移，并行化窗口bin-win根據數據流中的概念漂移自適應調整窗口大小，從而自適應的改變建模樣本數據的流入，提高了流數據的準確性和高效性。
2 算法分析與實現
2.1 CVFDT算法
2.1.1 CVFDT算法的原理
概念自適應快速決策樹(CVFDT)[2]是一種擴展了VFDT算法用以解決概念漂移問題的高效算法，具有類似VFDT的HT樹生成過程，在保持了VFD的速度和精度的前提下，能夠處理樣本產生過程中所出現的概念漂移問題[3]。CVFDT對樣本維持一個滑動窗口，并能夠動態改變窗口的大小。CVFDT算法過程包括CVFDTGrow過程、ForgetExample過程、RemoveExample過程和CheckSplitValidity過程。算法主要思想是先根據當前的數據構建臨時決策樹，然后并不斷地獲取新的數據去優化已建立的決策樹。若在某個時候出現了概念漂移，則算法會在出現漂移的節點上建立一個新的替代子樹。當替代子樹的分類效果優于當前的決策子樹時，就直接取而代之。
2.1.2 CVFDT算法抵抗概念漂移問題
概念漂移表示目標變量的統計特性隨著時間的推移以不可預見的方式變化的現象[4]。在流數據分類挖掘中，也指流數據特性的改變使得目標分類模型隨著時間的變化而變化。CVFDT周期性的掃描HT生成樹的內部節點來檢驗原先的分裂節點是否依然是最優的分裂屬性節點。當該節點發生了概念漂移，最優分裂屬性節點已不再是原先的Xa。CVFDT算法會重新尋找最佳測試屬性，新的屬性不直接取代原有的測試屬性，而是成為一個替代子樹的根節點，并且依據該根節點建立替代子樹。如果后繼滑動窗口的樣本在替代子樹上有較高的分類精度，則替代子樹便取代原先的決策樹，以維持滑動窗口的樣本和更新后的決策樹的一致性。
2.2 基于STORM平臺的CVFDT算法實現
2.2.1 CVFDT并行化窗口抵抗概念漂移算法設計
本小節討論以STORM作為分布式實時計算平臺，結合CVFDT流挖掘算法，解決數據流的概念漂移問題，從而提高模型建立的準確性�；趕torm分布式平臺的并行化窗口抵抗概念漂移方案，通過并行化窗口bin-win對數據流實時檢測實現概念漂移抵抗[5-6]，窗口調整流程圖如圖1所示。 從流程圖中，可以看到并行化窗口根據數據流中的概念漂移自適應調整窗口大小，當窗口檢測數據流未發生概念漂移時，則增大窗口中的樣本量，反之，則減小并行化窗口的大小，有利于較快的適應概念漂移。
其中，檢測是否發生概念漂移模塊，通過對HT樹中的非葉子節點的替代子樹調用CheckSplitValidity函數，計算屬性增益，從而判斷是否發生概念漂移，流程圖如圖2 所示。
2.2.2 CVFDT算法實現與分析
在現實生活中，大部分數據都是非平穩分布的，數據流根據時間的推移不斷發生變化，即發生了概念漂移[7]。CVFDT算法通過并行化窗口檢測數據流是否發生概念漂移，窗口太大不能快速有效的抵抗數據流中的概念漂移，窗口太小影響模型建立的時間和模型一段時間內的穩定性，如圖3所示在建立決策樹模型時檢測到概念漂移，則減小窗口的大小。當數據流穩定時，則增大窗口的大小，從而有效建立準確的決策樹模型。
3 系統實現
3.1 系統總體架構
CVFDT算法在STORM平臺上的實現方式有兩種，一種是垂直并行化實現，一種是結合隨機森林的實現，該抵抗概念漂移系統的設計主要基于垂直并行化的實現方式。系統包括三大模塊：并行化窗口模塊、抵抗概念漂移模塊、決策樹建立更新模塊。系統整體框架如圖4所示。
3.2 系統界面
抵抗概念漂移流分類挖掘系統參數設置界面如圖5所示，用戶輸入訓練樣本、更新樣本、測試樣本以及樣本所在文件的具體地址。點擊確定之后傳輸相應參數，CVFDT算法執行結束之后，彈出該算法挖掘結果顯示窗口，姐main如圖6所示，結果展示界面輸出當前決策樹以及其評價結果，以及未分類樣本的標記結果[8]。
4結束語
本文以分布式實時計算STORM平臺，設計并實現CVFDT算法，解決在流數據挖掘過程中出現的概念漂移現象，保證了流數據分類挖掘模型的準確性和高效性。CVFDT算法對樣本數據維持一個滑動窗口，在新樣本到達的時候更新節點上的統計信息，并在樣本滑出窗口的時候肩上其對應的統計信息。STORM平臺保證算法能夠提前預測數據流中的概念漂移，并實時更改窗口的大小，提高決策模型的準確性。
本文設計實現的算法與系統僅僅只是數據挖掘的一個方面，隨著大數據時代的到來，數據流會越來越大，并且會不斷變化，這就影響到了決策模型的建立與改善，因此，如何設計準確的算法和平臺來徹底解決流數據的概念漂移仍然需要進一步的研究。
參考文獻：
[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
工程師論文發表期刊推薦《機械工業信息與網絡》（雙月刊）雜志以"推進企業信息化，服務機械制造業"為宗旨，扎根于現代制造業，溝通IT技術廠商，搭建暢通信息之橋，筑起合作與交流平臺。雜志欄目設置：本刊報道、專家訪談、信息化論壇、調研、方案推介、應用與分析、網絡·安全、電子商務、企業采風、政策、動態資訊等。雜志精心選題策劃，深度報道解析，形成內容優勢與特色；詮釋機械制造業信息化建設的方方面面，以價值回饋讀者。
SCISSCIAHCI
