分布式數(shù)據(jù)流決策樹VFDT分類算法研究

劉壽強，祁明

（1.華南師范大學物理與電信工程學院，廣州 510006；2.華南理工大學經(jīng)濟與貿(mào)易學院，廣州 510006）

分布式數(shù)據(jù)流決策樹VFDT分類算法研究

劉壽強1，2，祁明2

（1.華南師范大學物理與電信工程學院，廣州 510006；2.華南理工大學經(jīng)濟與貿(mào)易學院，廣州 510006）

隨著大數(shù)據(jù)時代的到來，網(wǎng)絡上充斥著大量高速變化的數(shù)據(jù)流，然而傳統(tǒng)數(shù)據(jù)挖掘技術不能很好地直接應用到數(shù)據(jù)流上。研究基于決策樹的數(shù)據(jù)流分類挖掘算法，其研究思路是首先描述一般決策樹；然后重點闡述數(shù)據(jù)流決策樹VFDT的算法的實現(xiàn)，采用Twitter Storm分布式流式計算框架的并行計算和Yahoo SAMOA機器學習平臺，對VFDT算法進行并行化設計；最后通過實驗驗證并行化的VHT決策樹算法具有良好的運行效率與性能。

數(shù)據(jù)流；數(shù)據(jù)挖掘；決策樹；Storm；SAMOA

1 數(shù)據(jù)流及其典型處理平臺概述

隨著互聯(lián)網(wǎng)應用的發(fā)展，產(chǎn)生大量的流數(shù)據(jù)（下文采用通用的說法“數(shù)據(jù)流”），與傳統(tǒng)的靜止數(shù)據(jù)不同。數(shù)據(jù)流是海量的、高速的、實時的。其蘊涵著大量信息，可以用來作為智能決策的依據(jù)。預測和分類是基本數(shù)據(jù)分析兩種形式[1]，可以用于提取描述重要數(shù)據(jù)類的模型或預測未來的趨勢。目前大部分算法是內(nèi)存駐留算法，通常假定數(shù)據(jù)量很小，無法有效地應用于數(shù)據(jù)量潛在無限的數(shù)據(jù)流。傳統(tǒng)的數(shù)據(jù)挖掘方式并不能很好地適用于數(shù)據(jù)流挖掘，數(shù)據(jù)流分類對傳統(tǒng)的分類技術提出了許多新的挑戰(zhàn)。由于分類理論和方法在不同領域有著相當廣泛的應用，在對大量數(shù)據(jù)流進行數(shù)據(jù)挖掘處理時，如何利用有限的計算資源對實時的數(shù)據(jù)流信息進行快速的處理是一個很大的挑戰(zhàn)和難點，因此，研究快速的、精確的、穩(wěn)定的數(shù)據(jù)流分類系統(tǒng)具有極高的理論價值和應用價值。

目前數(shù)據(jù)流的研究與應用在國內(nèi)剛剛起步，主要是一些大的互聯(lián)網(wǎng)公司如騰訊、百度、阿里巴巴用于內(nèi)部的數(shù)據(jù)與業(yè)務處理，國外則主要是TwitterStorm實時平臺和Yahoo的SAMO數(shù)據(jù)挖掘平臺[2]。這兩個平臺是開源的，本文所做的實驗基于這兩個平臺。

2 數(shù)據(jù)流快速決策樹算法（Very Fast Decision Tree，VFDT）

VFDF算法是一種基于Hoeffding樹的對數(shù)據(jù)流模型進行分類的決策樹方法[3-4]。Hoeffding樹在最壞情況下能在恒定時間內(nèi)對一個實例進行學習，而且所構建的決策樹的準確率不差于其他算法。VFDT系統(tǒng)則是在Hoeffding樹的基礎上發(fā)展而來的，它對每一個實例只掃描一次，不會對它們保存，所以適合大量數(shù)據(jù)流的挖掘，VFDT最主要的貢獻在于用Hoeffding不等式來估算樣本的數(shù)量。設HT是當前Hoeffding樹，E為訓練實例，G為不純度函數(shù)，VFDT的算法的主要步驟如下：

（1）訓練集經(jīng)HT逐層分類后，到達葉子，每個葉子都積累若干實例；

（2）對于同一類別實例較多的屬性，記錄在候選分裂集；

（3）對每個候選分裂集用G函數(shù)表示，記Xa是不純度最小的的屬性，Xb是不純度次小的的屬性，根據(jù)Hoeffding邊界計算出ε；

3 分布式數(shù)據(jù)流決策樹VFDT算法

3.1 垂直Hoeffding樹（VHT）算法

該算法是基于VFDT的，在它基礎上添加分布式和并行性（注：PI內(nèi)數(shù)字表示并行度）。

圖1 垂直Hoefffding樹

由圖1可得，Model-aggregator PI包含整個決策樹模型，它通過屬性流和控制流連接局部統(tǒng)計PI：根據(jù)垂直并行模型，Model-aggregator PI根據(jù)屬性分割instances，instances經(jīng)由屬性流傳遞信息；控制流通知local-statstic PI運算，且每個local-statsitc PI都會對相應的instances進行局部統(tǒng)計計算。局部統(tǒng)計結果會通過computation-result反饋給Model-aggregator。Modelaggregator PI將分類器結果經(jīng)由結果流發(fā)送給Evalutor PI分類。Evaluator PI評估算法的正確率。

當需要更新決策樹時，Model-aggregator PI經(jīng)由控制流（control stream）發(fā)送compute content event到Local-statistic PI。一旦Local-statistic PI接收到compute content event，就開始計算給它分配的屬性值的選出最優(yōu)以及次優(yōu)屬性。此時，Model-aggregator PI有可能會繼續(xù)處理incoming testing instance或等到接收完Local-statistic PI處理結果后才開始接收數(shù)據(jù)。

無論何時，算法接收到local-result content event，它都會從splitting leaves檢索出正確的葉子l，然后更新當前最優(yōu)（Xa）以及次優(yōu)（Xb）屬性。當所有的局部結果都反饋給Model-aggregator PI后，決策樹歸納算法計算hoeffding界和決定是否分裂出葉子l。僅當滿足條件才分裂，否則不分裂。Model-aggregator PI具有超時機制，一旦超時，就直接采用當前的Xa和Xb計算Hoeffding界和做分裂決策。在測試階段，Model-aggregator PI預測incoming instances的類值。Model aggregatro PI使用決策樹模型將新的incoming instances分類到正確的葉子，并且使用葉子預測類。然后，將類的預測值發(fā)送到result stream。

3.2 Storm集成到SAMOA

通過SPE-adapterLayer將storm集成到SAMOA，需要建立storm classes與SAMOA組件之間的聯(lián)系，如圖2所示。

圖2 storm-samoa簡化設計圖

將Storm集成到SAMO稱為storm-samoa。stormsamoa由StormEntranceProcessingItem和StormProcessingItem組成，它們繼承自Storm-TopologyNode。由StormTopology承擔創(chuàng)建StormStream和創(chuàng)建唯一標識的任務。Storm-EntranceProcessingItem包含storm的spout組件，而StromProcessingItem包含storm的bolt組件。利用spout和bolt組件，就可以組成storm的Topology，并且在storm集群上運行。

抽象類StormStream繼承自stream。抽象方法put用于發(fā)送content event到目標PI，使用抽象類Storm-Stream好處是避免spout和bolt發(fā)送tuple方式的差異性。StormSpoutStream繼承StormStream，StormEntranceProcessingItem使用stormSpoutStream發(fā)送contentevent。StormSpoutStream的put方法puts content event到StormEntranceSpout的隊列中，Storm利用pull模式，清空隊列并發(fā)送content event。另外，StormProcessingItem之間使用StromBoltStream發(fā)送content event，它里邊調(diào)用的就是boltoutputCollector方法實現(xiàn)該功能。

4 系統(tǒng)部署與實驗

4.1 系統(tǒng)部署

在本地搭建Storm環(huán)境以便開發(fā)測試，同時需要配置文件storm.yaml，修改storm的配置文件（storm. yaml），添加Nimbus的主機地址，將修改后的配置文件添加到目錄（～/.storm/）中。將Nimbus、Supervisor、Storm UI設置在同一臺PC上。在開發(fā)過程中，只需將Topology提交到本地Storm環(huán)境中，即可模擬集群環(huán)境使項目運行，方便調(diào)試與測試。選用3臺物理服務器來搭建實時數(shù)據(jù)分析處理系統(tǒng)所需的Storm集群，其中一臺只運行Nimbus守護進程，其余2臺只運行Supervisor，為每臺Surpervisor節(jié)點配置4個可使用的端口。

4.2 分布式?jīng)Q策樹實驗結果與分析

本實驗主要對比基于VFDT的并行化算法VHT與VFDT算法在多組數(shù)組下的運行情況，并從分類結果、分類時間和Kappa一致性檢驗進行分析。實驗數(shù)據(jù)采用SAMOA集成的隨機決策生成器生成隨機數(shù)據(jù)。該生成器生成的屬性均為離散值，不考慮連續(xù)屬性的情況。VFDT算法數(shù)據(jù)是使用MOA數(shù)據(jù)流挖掘軟件獲得。實驗樣本個數(shù)為107個，10次實驗取平均值，并從三個方面進行分析：運行時間，用于分析分類效率；分類精度，用于評價分類的精度；Kappa Statstic，用于檢測模型的一致性。

（1）運行時間比較

運行時間用來比較算法的執(zhí)行快慢，由于節(jié)點都是本地虛擬化的，這里忽略Storm節(jié)點通信耗時，忽略不同節(jié)點執(zhí)行重復數(shù)據(jù)的事件。實驗中Storm平臺節(jié)點數(shù)設置為3，一臺Nimbus，兩臺Supervisor。

實驗參數(shù)：VFDT算法的其它參數(shù)與VHT參數(shù)一致，VFDT與VHT樹的深度都為10，標稱屬性為10，類個數(shù)為2。此時VHT的并行度為4。

實驗結果（表1）表明，VFDT和VHT算法的運行時間都是隨著數(shù)據(jù)量的增大而增大，VFDT處理相同數(shù)據(jù)量的時間約為VHT的4倍，而由于VHT算法是基于VFDT算法的，也就是說，并行化使執(zhí)行時間縮短。

表1 VHT與VFDT算法執(zhí)行時間比較

（2）分類精度比較

該分析指標表明的是分類的精度。數(shù)值越大，分類的精準度越高。該實驗將從兩個方面驗證VHT的分類精度：第一，驗證并行度對VHT的分類精度的影響；第二，驗證標稱屬性個數(shù)對VHT的分類精度的影響。

第一部分驗證實驗：設VHT算法實驗參數(shù)為樹深度10，標稱屬性個數(shù)10，類個數(shù)2；并行度分別為1、4、10。

圖3 VHT在不同并行度下分類精度對比圖

圖3給出了在相同模擬數(shù)據(jù)下不同并行度下VHT算法的分類精度對比：第一，可以得出并行度4時，分類精度最高，并行度1的分類精度相對較好，而并行度10的分類精度最差。也就是說，并行度對整體的分類精度有影響，但在實驗中不是積極影響，并非并行度越高VHT算法的精度越好。這是因為Local-statstic-Pi在分裂屬性并沒有選取準確，導致決策樹模式出現(xiàn)問題；第二，無論并行度如何，分類精度曲線基本上會隨著樣本數(shù)的增加呈現(xiàn)平滑上升狀態(tài)，分類精度提高。

第二部分驗證實驗：設VHT算法實驗參數(shù)為并行度4，樹深度10，類個數(shù)2，標稱屬性個數(shù)5，10，20。

圖4給出了在同樣模擬數(shù)據(jù)下不同標稱屬性個數(shù)下VHT算法的分類精度對比：從大的方向，可以看出屬性個數(shù)越小，分類精度越高。實驗中，屬性個數(shù)為5的分類精度最好，屬性個數(shù)為10的次之，屬性個數(shù)20的最少。不過從圖4中可以看出分類的精度也可以達到70%；從圖4中還可以讀出，隨著樣本個數(shù)增大，分類精度越來越好。對于海量的數(shù)據(jù)流的，即使屬性個數(shù)較多，但該精度值還是在可接受的范圍之內(nèi)。

圖4 VHT不同屬性個數(shù)下分類準確率對比圖

（3）VHT的Kappa統(tǒng)計（Kappa Statstic）

該實驗驗證隨機決策樹與VHT算法的一致性，也可以說是評價VHT決策樹模型的優(yōu)劣性。該實驗的數(shù)據(jù)流生成器產(chǎn)生的是離散屬性，Kappa統(tǒng)計是檢驗分類變量資料一致性以及重現(xiàn)性的指標。該指標正適用于離散屬性，（0～0.4]重現(xiàn)性（或一致性）差，（0.4～0.75]重現(xiàn)性（或一致性）好，（0.75～1]重現(xiàn)性（或一致性）極好。

該評價值仍分為兩個實驗驗證：第一部分為不同并行度下VHT的Kappa Statstic值的影響；第二部分為不同標稱屬性個數(shù)對VHT的Kappa Statstic的影響。第一部分實驗：參數(shù)設置，VHT樹的深度為10，標稱屬性個數(shù)為10，類個數(shù)為2，并行度分別是1，4，10。

從圖5可以看出并行度為10時，Kappa Statstic為負數(shù)，接近0，并行度為1時Kappa Statstic曲線雖然呈上升狀態(tài)，但是最大值只是剛好達到40%；而并行度為4時Kappa Statstic曲線呈上升狀態(tài)，最大值達48%以上，也就是說并行度有個最好值，實驗中為4，隨意增加或者減少就會對Kappa Statstic造成不良影響。結合圖5，解釋并行度10分類精度<并行度1分類精度<并行度4分類精度的問題，這是因為VHT決策樹模型與隨機決策樹最一致就是并行度為4時，此時分類模型最佳；而并行度1、10一致性差，模型較差。

圖5 VHT不同并行度下Kappa Statstic對比圖

第二部分驗證實驗：設VHT算法實驗參數(shù)為并行度4，樹深度10，類個數(shù)2，標稱屬性個數(shù)5，10，20。從圖6可以看出，屬性個數(shù)對Kappa Stastic的影響：屬性個數(shù)為5時，Kappa Statstic最優(yōu)；屬性個數(shù)為10時，Kappa Statstic次之；屬性個數(shù)為20時Kappa Stastic最差。也就是說，屬性個數(shù)越多，Kappa Statstic越差，說明VHT算法并不適合用于多屬性的數(shù)據(jù)流分類中。用該參數(shù)就可以解釋圖6的現(xiàn)象，屬性個數(shù)為5時，該算法模型與隨機決策樹模型最佳，因此分類精度最好。換句話說，當VHT算法模型與隨機決策樹模型一致性較好時，分類的精度越好。

以上決策樹生成器生成人工數(shù)據(jù)對VHT分類器的性能進行一系列的驗證，主要從三個角度去分析VHT算法的性能：第一，運行效率；第二，分類精度；第三，一致性檢驗。從上述實驗結果可得，當數(shù)據(jù)量越來越大，VFDT執(zhí)行時間比VHT的執(zhí)行時間長得多，運行效率慢。也就是說，VHT算法對于大數(shù)據(jù)量時有較好的運行效率。但是對于改變VHT算法的并行度并不一定能夠提高性能，有可能造成性能降低。而且屬性個數(shù)較多時，VHT算法分類結果也不太理想。從Kappa Statstic分析可知，改變并行度以及屬性個數(shù)會導致VHT算法模型與隨機決策樹模型一致性變化，當一致性較差時，分類精度就不理想。從理論上講，就是VHT算法選擇分裂屬性不太精準，或者進行樹剪枝時，選擇的分枝不合適。

圖6 VHT不同屬性個數(shù)下Kappa Statstic對比圖

5 結語

本文結合當前開源的數(shù)據(jù)流計算框架對數(shù)據(jù)流挖掘算法進行探索。對于海量的數(shù)據(jù)，目前最好的做法是并行化處理，它能夠有效地提高運行效率。實驗證明VFDT分類是有效的：隨著樣本數(shù)目的增加，在分類精度上有了明顯的提升，雖然對比原VFDT算法有所減低，但是在并行度適中時，很大程度上提高了分類效率，這個效率在實驗測試中約為4倍左右，但是改變并行度并不利于分類精度的提升，而且VHT算法在屬性值較多時的分類精度不理想，該算法比VFDT算法更適于挖掘大型散屬性數(shù)據(jù)流[5]。

本文主要的工作是對數(shù)據(jù)流決策樹算法VFDT的并行化改進，但對原有算法缺陷的改進是有限的。VFDT算法主要是針對離散屬性的數(shù)據(jù)流的，對連續(xù)屬性的數(shù)據(jù)流缺乏處理能力，同時，對數(shù)據(jù)流概念漂移問題[6-7]并沒有考慮進算法設計當中。本文的設計只適用于數(shù)值類型，然而在實際應用中，數(shù)據(jù)流常常包含多種類型的數(shù)據(jù)，需要進一步研究如何對實時混合的數(shù)據(jù)分類。由于一類分類算法一般只解決一類問題，不同的數(shù)據(jù)流可能會使用到不同的分類方法，為了滿足大數(shù)據(jù)時代對海量數(shù)據(jù)的要求，需要設計多種并行分類方法，以便提高分類精度與效率。為解決海量數(shù)據(jù)流挖掘的高效計算問題，最有效途徑是采用云計算并行化改造[8]，并利用Storm或Spark等實時流計算框架，使海量數(shù)據(jù)流挖掘算法的性能與效率有著數(shù)量級別的提升[9]。

[1]姚遠.海量動態(tài)數(shù)據(jù)流分類方法研究[D].大連：大連理工大學，2013.

[2]Arinto Murdopo，Antonio Severien,Gianmarco De Francisci Morales,and Albert Bifet.Samoa-Developers-Guide-0-0-1.http://yahoo. github.io/samoa/，2013.

[3]王濤，李舟軍，胡小華，等.一種高效的數(shù)據(jù)流挖掘增量模糊決策樹分類算法[J].計算機學報，2007.

[4]Albert Bifet，Geoff Holmes，Richard Kirkby，Bernhard Pfahringer.Data Stream Mining[M].WAIKATO，2011.

[5]Albert Bifet，Jesse Read，Bernhard Pfahringer，Geoff Holmes.Pitfalls in Benchmarking Data Stream Classification and How to Avoid Them[J].Machine Learning and Knowledge Discovery in Databases Lecture Notes in Computer Science Volume 8188，2013，465-479.

[6]葉愛玲.基于多重選擇機制的概念漂移數(shù)據(jù)流挖掘算法研究[D].合肥：安徽大學.2010.

[7]李培培.數(shù)據(jù)流中概念漂移檢測與分類算法研究[D].合肥：合肥工業(yè)大學，2012.

[8]顏巍.基于云平臺的數(shù)據(jù)挖掘算法的研究與實現(xiàn)[D].成都：電子科技大學，2013.

[9]程學旗，靳小龍，王元卓，等.大數(shù)據(jù)系統(tǒng)和分析技術綜述[J].軟件學報，2014，25（9）:1889-1908.

Research on Decision Tree Classification Algorithm of Distributed Data Stream

LIU Shou-qiang1，2，QI Min1
（1.School of Physics and Telecommunication Engineering，South China Normal University，Guangzhou 510006；2.School of Economics and Commerce，South China University of Technology，Guangzhou 510006）

Since the arrival of the era of big data,data state has been changed,which is not only static but also dynamic streaming,the new type of data is called data stream owned the characteristics such as continuous,high-speed,dynamic and infinities etc.Thus traditional data mining techniques cannot be directly used for data stream mining,stream data mining technology is one of the new research directions in the field of data mining.Focuses on the data stream mining classification algorithm which is based on the decision tree algorithm, describes the general decision tree，after understanding the implementation of VFDT,one data stream decision tree algorithm,uses Twitter Storm distributed stream computing framework of parallel computing ability and machine learning platform framework of Yahoo SAMOA, proposes concurrent parallel design based on the arithmetic of VFDT algorithm,and finally the experiment demonstrates the excellent operating efficiency and performance of parallelized VHT decision tree algorithm.

Data Streams;Decision Treeclasscation Algorithm;Storm;SAMOA

1007-1423（2016）36-0003-06

10.3969/j.issn.1007-1423.2016.36.001

4-），男，湖北人，講師，博士，研方向為云計算、大數(shù)據(jù)、電子商務、機器學習

2016-11-18

2016-12-10

廣東省公益研究與能力建設專項資金項目（No.2016A020223012、No.2015A020217011）、廣東省交通科技計劃項目（No.2015-02-064）、廣東外語外貿(mào)大學南國商學院2016年教改重大項目、廣州大學華軟軟件學院重大科研培育項目（20000104與教研項目KY201412）