分布式數據流決策樹VFDT分類算法研究

劉壽強，祁明

（1.華南師范大學物理與電信工程學院，廣州 510006；2.華南理工大學經濟與貿易學院，廣州 510006）

分布式數據流決策樹VFDT分類算法研究

劉壽強1，2，祁明2

（1.華南師范大學物理與電信工程學院，廣州 510006；2.華南理工大學經濟與貿易學院，廣州 510006）

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

數據流；數據挖掘；決策樹；Storm；SAMOA

1 數據流及其典型處理平臺概述

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

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

2 數據流快速決策樹算法（Very Fast Decision Tree，VFDT）

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

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

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

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

3 分布式數據流決策樹VFDT算法

3.1 垂直Hoeffding樹（VHT）算法

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

圖1 垂直Hoefffding樹

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

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

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

3.2 Storm集成到SAMOA

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

圖2 storm-samoa簡化設計圖

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

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

4 系統部署與實驗

4.1 系統部署

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

4.2 分布式決策樹實驗結果與分析

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

（1）運行時間比較

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

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

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

表1 VHT與VFDT算法執行時間比較

（2）分類精度比較

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

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

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

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

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

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

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

（3）VHT的Kappa統計（Kappa Statstic）

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

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

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

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

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

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

圖6 VHT不同屬性個數下Kappa Statstic對比圖

5 結語

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

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

[1]姚遠.海量動態數據流分類方法研究[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]王濤，李舟軍，胡小華，等.一種高效的數據流挖掘增量模糊決策樹分類算法[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]葉愛玲.基于多重選擇機制的概念漂移數據流挖掘算法研究[D].合肥：安徽大學.2010.

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

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

[9]程學旗，靳小龍，王元卓，等.大數據系統和分析技術綜述[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-），男，湖北人，講師，博士，研方向為云計算、大數據、電子商務、機器學習

2016-11-18

2016-12-10

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