劉壽強(qiáng)，祁明

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

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

劉壽強(qiáng)1，2，祁明2

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

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

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

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

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

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

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

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

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

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

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

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

3.1 垂直Hoeffding樹（VHT）算法

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

圖1 垂直Hoefffding樹

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

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

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

3.2 Storm集成到SAMOA

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

圖2 storm-samoa簡化設(shè)計(jì)圖

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

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

4 系統(tǒng)部署與實(shí)驗(yàn)

4.1 系統(tǒng)部署

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

4.2 分布式?jīng)Q策樹實(shí)驗(yàn)結(jié)果與分析

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

（1）運(yùn)行時間比較

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

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

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

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

（2）分類精度比較

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

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

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

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

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

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

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

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

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

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

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

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

第二部分驗(yàn)證實(shí)驗(yàn)：設(shè)VHT算法實(shí)驗(yàn)參數(shù)為并行度4，樹深度10，類個數(shù)2，標(biāo)稱屬性個數(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時，該算法模型與隨機(jī)決策樹模型最佳，因此分類精度最好。換句話說，當(dāng)VHT算法模型與隨機(jī)決策樹模型一致性較好時，分類的精度越好。

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

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

5 結(jié)語

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

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

[1]姚遠(yuǎn).海量動態(tài)數(shù)據(jù)流分類方法研究[D].大連：大連理工大學(xué)，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].計(jì)算機(jī)學(xué)報，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]葉愛玲.基于多重選擇機(jī)制的概念漂移數(shù)據(jù)流挖掘算法研究[D].合肥：安徽大學(xué).2010.

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

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

[9]程學(xué)旗，靳小龍，王元卓，等.大數(shù)據(jù)系統(tǒng)和分析技術(shù)綜述[J].軟件學(xué)報，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-），男，湖北人，講師，博士，研方向?yàn)樵朴?jì)算、大數(shù)據(jù)、電子商務(wù)、機(jī)器學(xué)習(xí)

2016-11-18

2016-12-10

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