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