VFDT算法基于Storm平臺(tái)的實(shí)現(xiàn)方案

張發(fā)揚(yáng)，李玲娟，陳 煜

(南京郵電大學(xué)計(jì)算機(jī)學(xué)院，江蘇南京 210003)

VFDT算法基于Storm平臺(tái)的實(shí)現(xiàn)方案

張發(fā)揚(yáng)，李玲娟，陳 煜

(南京郵電大學(xué)計(jì)算機(jī)學(xué)院，江蘇南京 210003)

以提升流數(shù)據(jù)的分類效率為目標(biāo)，研究如何在流數(shù)據(jù)處理平臺(tái)Storm上實(shí)現(xiàn)快速?zèng)Q策樹算法-VFDT。設(shè)計(jì)了VFDT基于Storm的分布式并行化實(shí)現(xiàn)方案，將VFDT算法分為建樹、分類和評(píng)價(jià)共三個(gè)模塊，建樹模塊負(fù)責(zé)決策樹的初始化和增量建樹，分類模塊負(fù)責(zé)對(duì)待分類樣本進(jìn)行分類標(biāo)記，評(píng)價(jià)模塊負(fù)責(zé)用已標(biāo)記的樣本對(duì)VFDT決策樹進(jìn)行評(píng)價(jià)。通過(guò)正確設(shè)計(jì)Storm拓?fù)渲械腟pout/Bolt實(shí)現(xiàn)各模塊的功能，通過(guò)為分類Bolt設(shè)定多個(gè)Task來(lái)實(shí)現(xiàn)分類模塊的并行化;用內(nèi)存數(shù)據(jù)庫(kù)Redis實(shí)現(xiàn)三個(gè)模塊的有效銜接和決策樹的保存;用消息中間件Kafka來(lái)提高算法對(duì)流數(shù)據(jù)突增的容忍度?；谠摲桨傅腣FDT算法實(shí)現(xiàn)與測(cè)試結(jié)果表明:在Storm集群環(huán)境下的VFDT算法分類效率相對(duì)于單機(jī)環(huán)境有顯著提高，而且合理設(shè)定分類Bolt的Task數(shù)可使分類效率進(jìn)一步提高。

流數(shù)據(jù);快速?zèng)Q策樹算法;分布式;并行化;Storm

0 引言

20世紀(jì)末，為適應(yīng)網(wǎng)絡(luò)監(jiān)控、入侵檢測(cè)、情報(bào)分析、商業(yè)交易管理和分析等應(yīng)用的要求，數(shù)據(jù)流技術(shù)應(yīng)運(yùn)而生［1］。數(shù)據(jù)流中的數(shù)據(jù)(即流數(shù)據(jù))是有序的、連續(xù)的且不斷變化的，甚至是無(wú)限的［2］，不能像傳統(tǒng)的靜態(tài)數(shù)據(jù)一樣將其存儲(chǔ)在硬盤或者內(nèi)存之中，即再次處理這些數(shù)據(jù)的代價(jià)將非常昂貴。

流數(shù)據(jù)挖掘是指從快速、大量、連續(xù)的數(shù)據(jù)流中挖掘出有價(jià)值的信息。數(shù)據(jù)流具有快速、連續(xù)、大量的特點(diǎn)，傳統(tǒng)數(shù)據(jù)挖掘(Data Mining，DM)算法難以對(duì)流數(shù)據(jù)進(jìn)行有效的挖掘。對(duì)于流數(shù)據(jù)，它的搜集和挖掘過(guò)程必須同時(shí)進(jìn)行，且必須以最快的速度從不斷到來(lái)的數(shù)據(jù)中挖掘出用戶所需要的信息。傳統(tǒng)的靜態(tài)數(shù)據(jù)挖掘通常能滿足數(shù)據(jù)分析處理的精確性要求，但是，對(duì)流數(shù)據(jù)而言，由于數(shù)據(jù)收集的時(shí)間和處理速度有限，因此得到的挖掘模型是近似結(jié)果。流數(shù)據(jù)挖掘結(jié)果的近似性是其不同于傳統(tǒng)數(shù)據(jù)挖掘的一個(gè)重要特點(diǎn)。

分類挖掘是數(shù)據(jù)挖掘的主要任務(wù)之一，決策樹算法是分類挖掘的一類主流算法。VFDT(Very Fast Decision Tree)算法［3］是經(jīng)典的流分類算法之一。VFDT在假設(shè)數(shù)據(jù)流不發(fā)生概念漂移的情況下對(duì)持續(xù)不斷的數(shù)據(jù)流進(jìn)行增量學(xué)習(xí)，能夠很好地適應(yīng)流數(shù)據(jù)的分類。VFDT算法可以使每條訓(xùn)練樣本的處理花費(fèi)恒定的內(nèi)存和時(shí)間，因此可以有效解決時(shí)間和內(nèi)存的限制問(wèn)題。該算法通過(guò)最初的少量樣本生成隨時(shí)可用的分類器，并可隨著訓(xùn)練樣本的到來(lái)，對(duì)原有分類器進(jìn)行增量更新，不斷優(yōu)化原始決策樹，即VFDT算法以增量的形式，通過(guò)不斷地將葉子節(jié)點(diǎn)替換為決策節(jié)點(diǎn)而生成決策樹。

與傳統(tǒng)的靜態(tài)大數(shù)據(jù)處理平臺(tái)Hadoop［4］不同，Storm是開源的流數(shù)據(jù)處理框架［5］，能夠高效可靠地處理源源不斷的數(shù)據(jù)流。流挖掘算法運(yùn)行于數(shù)據(jù)流處理平臺(tái)是充分發(fā)揮算法效力的前提。為此，文中研究如何將VFDT算法部署到Storm平臺(tái)上進(jìn)行分布式并行化實(shí)現(xiàn)，以提高VFDT算法對(duì)流數(shù)據(jù)的分類效率。

1 VFDT算法分析

VFDT算法是通過(guò)對(duì)Hoeffding樹改進(jìn)而實(shí)現(xiàn)的。Hoeffding樹是通過(guò)不斷地將葉子節(jié)點(diǎn)轉(zhuǎn)換為內(nèi)部節(jié)點(diǎn)而生成的，其中每個(gè)葉節(jié)點(diǎn)都存有關(guān)于屬性值的統(tǒng)計(jì)信息，這些統(tǒng)計(jì)信息用于計(jì)算屬性的信息增益。當(dāng)數(shù)據(jù)流中一個(gè)新的樣本到來(lái)后，該樣本沿著決策樹從上到下遍歷，樹的每個(gè)內(nèi)部節(jié)點(diǎn)都對(duì)其進(jìn)行劃分測(cè)試，根據(jù)不同的屬性取值，樣本進(jìn)入不同的分枝，最終到達(dá)樹的葉節(jié)點(diǎn)。當(dāng)數(shù)據(jù)到達(dá)葉節(jié)點(diǎn)后，更新該葉節(jié)點(diǎn)上的統(tǒng)計(jì)信息。如果統(tǒng)計(jì)信息的計(jì)算結(jié)果滿足節(jié)點(diǎn)分裂條件，則該葉節(jié)點(diǎn)變?yōu)閮?nèi)部節(jié)點(diǎn)，并產(chǎn)生基于該內(nèi)部節(jié)點(diǎn)的子女葉節(jié)點(diǎn)。子女葉節(jié)點(diǎn)的個(gè)數(shù)取決于新的內(nèi)部節(jié)點(diǎn)的屬性的可能取值數(shù)目。

VFDT算法采用信息熵或者Gini指標(biāo)作為選擇分裂屬性的標(biāo)準(zhǔn)，以Hoeffding不等式作為判定節(jié)點(diǎn)分裂的條件。選擇Hoeffding不等式作為節(jié)點(diǎn)分裂條件的目的是確定葉子節(jié)點(diǎn)變?yōu)閮?nèi)部節(jié)點(diǎn)所需要的樣本數(shù)目，以達(dá)到使用盡量少的樣本建立準(zhǔn)確率較高的決策樹的目的。

以t作時(shí)間戳，xt表示t時(shí)刻到達(dá)的數(shù)據(jù)向量，數(shù)據(jù)流可表示為{…，xt-1，xt，xt+1，…}［6］。VFDT算法的有關(guān)定義如下:

(1)信息增益［7］:葉子節(jié)點(diǎn)l中存儲(chǔ)訓(xùn)練樣本集D的統(tǒng)計(jì)信息，則對(duì)于樣本集D分類所需的期望信息為Info(D)=-pilog2(pi)。其中，pi是樣本集D中任意一條樣本屬于類Ci的概率，pi= Ci，D/D，m是類別屬性的取值個(gè)數(shù)。對(duì)于葉子節(jié)點(diǎn)可能的分裂屬性A，設(shè)A有v個(gè)取值，則利用屬性A對(duì)樣本集D進(jìn)行劃分的期望信息為InfoA(D)=-，屬性A的信息增益為Gain(A)=Info(D)-InfoA(D)。

(2)Hoeffding邊界［8-9］:對(duì)一個(gè)真值隨機(jī)變量r∈R，設(shè)對(duì) r取了 n個(gè)獨(dú)立的觀察值，平均值為 r-，其Hoeffding約束以1-δ的概率保證變量r的真實(shí)值與觀察值r-之差小于ε，即:P(r≥r--ε)=1-δ。其中，ε，r代表信息增益，R的取值范圍是log2#Classes(Classes是類別屬性取值的數(shù)量)。

(3)主動(dòng)分裂系數(shù)τ［10］:τ的作用在于當(dāng)幾個(gè)屬性的信息增益值G幾乎相等時(shí)，可能需要更多的樣本來(lái)決定出葉子節(jié)點(diǎn)的決策屬性，通過(guò)設(shè)定τ值來(lái)主動(dòng)選擇屬性并實(shí)現(xiàn)葉子節(jié)點(diǎn)分裂。當(dāng)滿足ΔG＜ε＜τ時(shí)，選擇ΔG中信息增益最大或者次大的屬性作為該葉子節(jié)點(diǎn)的決策屬性。

VFDT算法的建樹流程如圖1所示。

概括地說(shuō)，一條訓(xùn)練樣本是一個(gè)Tuple，即一條流，樣本中各屬性的元素與初始化階段抽取的屬性信息保持一致，通過(guò)分析流的非類別屬性與類別屬性的關(guān)系建立一棵決策樹。增量建樹過(guò)程就是不斷將葉子節(jié)點(diǎn)轉(zhuǎn)化為內(nèi)部節(jié)點(diǎn)的過(guò)程，其中每個(gè)葉子節(jié)點(diǎn)都將保存有關(guān)節(jié)點(diǎn)分裂的統(tǒng)計(jì)信息。當(dāng)一個(gè)訓(xùn)練樣本到達(dá)之后，從根節(jié)點(diǎn)開始，根據(jù)該節(jié)點(diǎn)的屬性取值進(jìn)入不同的分支，以此過(guò)程進(jìn)行遞歸直至到達(dá)葉子節(jié)點(diǎn)。到達(dá)葉節(jié)點(diǎn)之后將對(duì)葉子節(jié)點(diǎn)的統(tǒng)計(jì)信息進(jìn)行更新，當(dāng)統(tǒng)計(jì)值滿足計(jì)算的閾值時(shí)將觸發(fā)計(jì)算各可能屬性的信息增益以及Hoeffding邊界值，若滿足節(jié)點(diǎn)分裂的條件，則將該葉子節(jié)點(diǎn)轉(zhuǎn)化為內(nèi)部節(jié)點(diǎn)，并根據(jù)決策屬性的取值產(chǎn)生新的葉子節(jié)點(diǎn)。

2 Storm平臺(tái)

Apache Storm是由Twitter公司開源的分布式實(shí)時(shí)計(jì)算系統(tǒng)。與Hadoop的批處理相比，Storm具有更好的實(shí)時(shí)性、可拓展性和容錯(cuò)性，能有效地處理流數(shù)據(jù)，被廣泛用于實(shí)時(shí)分析、在線機(jī)器學(xué)習(xí)等場(chǎng)景［11］。

圖1 VFDT算法的建樹流程

在Storm內(nèi)部，數(shù)據(jù)流是由拓?fù)?Topology)來(lái)處理的。拓?fù)浒琒pout、數(shù)據(jù)源以及Bolt［12］。Bolt是拓?fù)涞囊粋€(gè)重要實(shí)體，負(fù)責(zé)數(shù)據(jù)流動(dòng)轉(zhuǎn)換，比如計(jì)算、過(guò)濾、聚合以及機(jī)器學(xué)習(xí)等。一個(gè)拓?fù)淇梢杂幸粋€(gè)或者多個(gè)Bolt實(shí)現(xiàn)數(shù)據(jù)流的復(fù)雜流轉(zhuǎn)。

Storm集群的基本架構(gòu)如圖2所示，主要包括兩種節(jié)點(diǎn):主節(jié)點(diǎn)Nimbus(Master Node)以及工作節(jié)點(diǎn)Supervisor(Worker Node)。其中，Nimbus既負(fù)責(zé)將代碼分發(fā)到不同的工作節(jié)點(diǎn)，又負(fù)責(zé)監(jiān)控集群。在每個(gè)工作節(jié)點(diǎn)上都會(huì)運(yùn)行一個(gè)Supervisor，負(fù)責(zé)監(jiān)聽Nimbus分配給該節(jié)點(diǎn)的工作［13］。每個(gè)Worker進(jìn)程執(zhí)行一個(gè)具體的Topology，Worker中的執(zhí)行線程為Executor，每個(gè)Executor中又包含一個(gè)或者多個(gè)Task，Task為Storm的最小處理單元。一個(gè)運(yùn)行中的Topology是由運(yùn)行在一臺(tái)或者多臺(tái)工作節(jié)點(diǎn)上的Worker來(lái)完成具體的業(yè)務(wù)操作。Nimbus與Supervisor之間的通信由Zookeeper來(lái)完成。

圖2 Storm集群的基本架構(gòu)

3 VFDT算法基于Storm的實(shí)現(xiàn)方案設(shè)計(jì)

文中設(shè)計(jì)的VFDT基于Storm的分布式并行化實(shí)現(xiàn)方案，將VFDT算法分為建樹、分類和評(píng)價(jià)共三個(gè)模塊，建樹模塊負(fù)責(zé)決策樹的初始化和增量建樹，分類模塊負(fù)責(zé)對(duì)待分類樣本進(jìn)行分類標(biāo)記，評(píng)價(jià)模塊負(fù)責(zé)用已標(biāo)記樣本對(duì)VFDT決策樹進(jìn)行評(píng)價(jià)。各模塊都有相應(yīng)的Topology，如圖3所示。三個(gè)模塊之間通過(guò)內(nèi)存數(shù)據(jù)庫(kù)Redis［14］實(shí)現(xiàn)銜接，從而形成一個(gè)整體的計(jì)算框架，Redis也用于決策樹的保存;消息中間件Kafka［15］用來(lái)提高算法對(duì)流數(shù)據(jù)突增情況的容忍度。

圖中的TraData表示外部數(shù)據(jù)源，為建樹模塊提供訓(xùn)練樣本;Dspout1作為建樹拓?fù)涞臄?shù)據(jù)源從TraData中拉取數(shù)據(jù)并傳遞給其他數(shù)據(jù)處理Bolt;DataPro Bolt主要工作是對(duì)訓(xùn)練樣本進(jìn)行初始化，并將其轉(zhuǎn)換成算法所需要的類;VFDT Bolt接收樣本，并利用訓(xùn)練樣本進(jìn)行決策樹的增量建立;VFDTPrint Bolt接收增量建立的決策樹，并將決策樹進(jìn)行序列化存儲(chǔ)到Redis數(shù)據(jù)庫(kù)中;ClaData表示外部數(shù)據(jù)源，為分類模塊提供待分類樣本;Kafka是消息中間件，訂閱ClaData中的樣本，同時(shí)供分類模塊進(jìn)行消費(fèi);KafkaSpout作為分類拓?fù)涞臄?shù)據(jù)源，接收Kafka中的待分類樣本，并將樣本進(jìn)行分發(fā);Tree Spout1表示拓?fù)涞臎Q策樹數(shù)據(jù)源，從Redis中實(shí)時(shí)獲取決策樹并進(jìn)行分發(fā);Classification Bolt將利用Tree Spout1傳遞到?jīng)Q策樹對(duì)待分類樣本進(jìn)行分類; InstPrint Bolt主要是對(duì)標(biāo)記好的樣本進(jìn)行存儲(chǔ);EvaData表示外部數(shù)據(jù)源，為評(píng)價(jià)模塊提供評(píng)價(jià)樣本;Tree Spout2的功能與Tree Spout1一致;Evaluation Bolt利用EvaData對(duì)Tree Spout2中的決策樹進(jìn)行評(píng)價(jià);ResPrint Bolt將對(duì)評(píng)價(jià)結(jié)果進(jìn)行存儲(chǔ)。

(1)建樹模塊。

如前所述，建樹模塊主要負(fù)責(zé)決策樹的初始化以及決策樹的增量建立。初始化的過(guò)程主要包括數(shù)據(jù)集屬性信息的抽取以及根節(jié)點(diǎn)的建立。決策樹的增量建立過(guò)程包括讀入訓(xùn)練樣本集和基于圖1所示的流程建立決策樹。如圖3所示，DSpout1作為訓(xùn)練樣本的數(shù)據(jù)源，不斷向負(fù)責(zé)數(shù)據(jù)預(yù)處理的DataPro Bolt發(fā)送訓(xùn)練樣本，DataPro Bolt將訓(xùn)練樣本處理成算法需要的類，并將其傳遞到負(fù)責(zé)建樹的VFDT Bolt中，VFDT Bolt將調(diào)用VFDT插入樣本的方法實(shí)現(xiàn)決策樹的動(dòng)態(tài)更新，最后將VFDT決策樹傳遞到VFDTPrint Bolt中實(shí)現(xiàn)決策樹的序列化并存儲(chǔ)到Redis中。

(2)分類模塊。

分類模塊的主要功能是完成對(duì)待分類樣本的標(biāo)記工作?？紤]到待分類樣本數(shù)量大且源源不斷地到來(lái)，當(dāng)數(shù)據(jù)源突然增加時(shí)，有可能導(dǎo)致算法在Storm上并發(fā)度不足而引起異常，文中使用了消息中間件Kafka做數(shù)據(jù)暫存區(qū)。Kakfa具有高性能、高拓展性、分布式及持久性，當(dāng)數(shù)據(jù)源突然增加時(shí)可以將部分?jǐn)?shù)據(jù)持久化至硬盤中去，不至于造成數(shù)據(jù)的丟失［15］。為保證分類模塊的拓?fù)淠軌虮３州^高的數(shù)據(jù)吞吐量，文中將該模塊中的數(shù)據(jù)預(yù)處理DataPro Bolt以及對(duì)待分類樣本進(jìn)行分類的Classification Bolt的Task都設(shè)置為多個(gè)，以提高處理的并發(fā)度。

如圖3所示，DataPro Bolt使用Shuffle Grouping(隨機(jī)分組)的流分組方式從KafkaSpout中拉取數(shù)據(jù)，使得該Bolt的多個(gè)Tasks中的每個(gè)Task處理的樣本數(shù)目大致相同。Classification Bolt同樣采用Shuffle Grouping的方式使該Bolt中每個(gè)Task能夠平均處理數(shù)據(jù)。為了使該Bolt中的每個(gè)Task可以取到相同的決策樹，這部分還采用All Grouping(廣播分組)方式從負(fù)責(zé)由Redis內(nèi)存數(shù)據(jù)庫(kù)中實(shí)時(shí)獲取 VFDT決策樹的 Tree Spout1中拉取決策樹。最后對(duì)Classification Bolt中標(biāo)記過(guò)的待分類樣本采用Global Grouping(全局分組)的方式發(fā)送到InstancePrint Bolt中。

其中，Classification Bolt中利用決策樹VFDTTree對(duì)待分類樣本 ClaData進(jìn)行分類的偽代碼如算法1所示。

(3)評(píng)價(jià)模塊。

評(píng)價(jià)模塊的主要功能是利用已標(biāo)記的評(píng)價(jià)樣本實(shí)現(xiàn)對(duì)實(shí)時(shí)傳遞過(guò)來(lái)的VFDT決策樹的評(píng)價(jià)。為了保證評(píng)價(jià)樣本的實(shí)時(shí)性，文中采用滑動(dòng)窗口的方式保存最新的評(píng)價(jià)數(shù)據(jù)，每隔一秒觸發(fā)一次評(píng)價(jià)，并將評(píng)價(jià)結(jié)果傳輸至ResultPrint Bolt中。

如圖3所示，Dspout2作為評(píng)價(jià)樣本的數(shù)據(jù)源，向DataPro Bolt發(fā)送數(shù)據(jù)，經(jīng)過(guò)DataPro Bolt處理后發(fā)送到負(fù)責(zé)評(píng)價(jià)的Evaluation Bolt中，在Evaluation Bolt中維持一個(gè)固定大小的滑動(dòng)窗口，用于存儲(chǔ)最近的N條評(píng)價(jià)數(shù)據(jù)。每當(dāng)Evaluation Bolt從Tree Spout2中拉取最新的決策樹后，都利用窗口中的樣本對(duì)決策樹進(jìn)行一次評(píng)價(jià)，并將評(píng)價(jià)結(jié)果發(fā)送到ResPrint Bolt中，實(shí)現(xiàn)結(jié)果的存儲(chǔ)。

4 VFDT算法基于Storm的實(shí)現(xiàn)與性能測(cè)試

文中分別在單機(jī)和集群環(huán)境下，用Java進(jìn)行了VFDT算法的實(shí)現(xiàn)，算法運(yùn)行環(huán)境是:

集群硬件環(huán)境:1個(gè)Nimbus節(jié)點(diǎn)，2個(gè)Supervisor節(jié)點(diǎn)。

集群軟件環(huán)境:操作系統(tǒng)為Centos6.4、JRE1.7.0_ 13、Zookeeper-3.4.6、Storm0.9.1、Kafka2.8.1、redis-2.4.5。

單機(jī)環(huán)境:eclipse_4.5.0、JRE1.7.0_13、Windows7、2.13 GHz、4 GB內(nèi)存。

目的是借助流處理平臺(tái)提高VFDT算法的效率。為了驗(yàn)證所設(shè)計(jì)的VFDT算法基于Storm的實(shí)現(xiàn)方案的可行性和有效性，分別測(cè)試了單機(jī)與集群環(huán)境下，基于Storm的VFDT算法分類模塊的吞吐量與分類Bolt (Classification Bolt)的Task線程數(shù)(即并行度)的關(guān)系，以及相同的Task線程數(shù)下數(shù)據(jù)處理時(shí)間與數(shù)據(jù)量的關(guān)系。

測(cè)試使用的數(shù)據(jù)集是KDD CUP的Nursery數(shù)據(jù)集，屬性個(gè)數(shù)是8，類別屬性取值個(gè)數(shù)是5，基本訓(xùn)練樣本數(shù)量是12 400，通過(guò)復(fù)制得到所需量的分類樣本。

(1)吞吐量測(cè)試。

實(shí)驗(yàn)通過(guò)復(fù)制Nursery得到大規(guī)模的分類樣本。單機(jī)與集群環(huán)境下，VFDT分類模塊對(duì)應(yīng)于不同分類線程(Task)數(shù)的吞吐量如圖4所示。

可以看出，單機(jī)環(huán)境下，Task數(shù)為8時(shí)，吞吐量達(dá)到最大，為35 106.7條/s，當(dāng)線程繼續(xù)增加，吞吐量呈現(xiàn)下降趨勢(shì)。集群環(huán)境下，Task數(shù)為8時(shí)，吞吐量達(dá)到最大，為88 007.5條/s，當(dāng)線程繼續(xù)增加，吞吐量略呈下降趨勢(shì)。

(2)數(shù)據(jù)處理時(shí)間測(cè)試。

圖5對(duì)比了當(dāng)單機(jī)和集群環(huán)境下 Classification Bolt的Task數(shù)為8時(shí)，不同數(shù)據(jù)量所需的處理時(shí)間。單機(jī)環(huán)境下，隨著數(shù)據(jù)量的增加，處理時(shí)長(zhǎng)急劇增加;而集群環(huán)境下，隨著數(shù)據(jù)量的增加，處理時(shí)長(zhǎng)緩慢增加。

(3)測(cè)試結(jié)果分析。

由圖4以及圖5可以看出，基于 Storm集群的VFDT算法在處理規(guī)模較大的流式數(shù)據(jù)時(shí)，吞吐量?jī)?yōu)勢(shì)明顯，對(duì)數(shù)據(jù)量的增加具有較高的承受力。這是由于Storm是將Topology的各個(gè)組件(Spout/Bolt)分配到不同的Executor中，并在多個(gè)Worker中執(zhí)行的。由圖4還可以看出，合理設(shè)定分類Bolt的Task數(shù)可以最大限度發(fā)揮Storm的并行處理能力。

5 結(jié)束語(yǔ)

文中將經(jīng)典的流數(shù)據(jù)分類挖掘算法-VFDT部署于流數(shù)據(jù)處理平臺(tái)Storm上，以實(shí)現(xiàn)對(duì)流數(shù)據(jù)的分布式并行化分類。所設(shè)計(jì)的VFDT算法基于Storm的實(shí)現(xiàn)方案按算法功能劃分出建樹模塊、分類模塊和評(píng)價(jià)模塊，其中的分類模塊以并行化方式運(yùn)作;通過(guò)合理配置Storm拓?fù)浜褪褂肦edis與Kafka提高了實(shí)現(xiàn)方案的完整性和可行性?；谠摲桨傅腣FDT算法實(shí)現(xiàn)與性能測(cè)試結(jié)果說(shuō)明了方案的正確性和有效性，也說(shuō)明了基于Storm的VFDT算法對(duì)大規(guī)模流數(shù)據(jù)有良好的適應(yīng)能力。

［1］ 史金成，胡學(xué)鋼.數(shù)據(jù)流挖掘研究［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2007，17(11):11-14.

［2］ 顧 偉.分布式流數(shù)據(jù)實(shí)時(shí)計(jì)算框架的研究和開發(fā)［D］.杭州:浙江理工大學(xué)，2013.

［3］ Gama J，Rocha R，Medas P.Accurate decision trees for mining high-speed data streams［C］//Proceedings of the ninth ACM SIGKDD international conference on knowledge discovery and data mining.［s.l.］:ACM，2003:523-528.

［4］ White T.Hadoop:the definitive guide［M］.［s.l.］:O’Reilly Media，Inc.，2012.

［5］ The Apache Foundation.Storm official website［EB/OL］. ［2014-04-08］.http://storm-project.net.

［6］ Raahemi B，Zhong W，Liu J.Peer-to-peer traffic identification by mining IP layer data streams using concept-adapting very fast decision tree［C］//Proc of 20th IEEE international conference on tools with artificial intelligence.［s.l.］:IEEE，2008:525-532.

［7］ Maron O，Moore A W.Hoeffding races:accelerating model selection search for classification and function approximation ［J］.Advances in Neural Information Processing Systems，1993，6(1):59-66.

［8］ 王 濤，李舟軍，胡小華，等.一種高效的數(shù)據(jù)流挖掘增量模糊決策樹分類算法［J］.計(jì)算機(jī)學(xué)報(bào)，2007，30(8):1244-1250.

［9］ Littlestone N.Learning quickly when irrelevant attributes abound:a new linear-threshold algorithm［J］.Machine Learning，1988，2(4):285-318.

［10］蔣良孝，蔡之華，劉 釗.一種基于信息增益的分類規(guī)則挖掘算法［J］.中南大學(xué)學(xué)報(bào):自然科學(xué)版，2003，34(z1):69-71.

［11］Github Inc.Storm Wiki［EB/OL］.［2013-12-07］.https:// github.com/nathanmarz/storm/wiki.

［12］Marz N.Storm:distributed and fault-tolerant real time computation［EB/OL］.［2011-10-21］.https://www.infoq.com/ presentations/Storm-Introduction.

［13］Petkov V，Gerndt M.Integrating parallel application development with performance analysis in periscope［C］//Proc of IPDPSW.［s.l.］:IEEE，2010:1-8.

［14］曾泉?jiǎng)?基于Redis的分布式消息服務(wù)的設(shè)計(jì)與實(shí)現(xiàn)［D］.北京:北京郵電大學(xué)，2014.

［15］Kreps J，Narkhede N，Rao J.Kafka:a distributed messaging system for log processing［C］//Proceedings of the NetDB. Athens，Greece:［s.n.］，2011:1-7.

Implementation Scheme of VFDT Algorithm on Storm Platform

ZHANG Fa-yang，LI Ling-juan，CHEN Yu
(School of Computer，Nanjing University of Posts and Telecommunications，Nanjing 210003，China)

In order to improve the classification efficiency of the stream data，studies how to implement VFDT algorithm on Storm，a stream data processing platform.A scheme of distributed parallel implementing of VFDT algorithm based on Storm platform is designed. The VFDT algorithm is divided into three modules including building tree module，classification module and evaluation module.The building tree module is responsible for the initializing and incremental building of decision tree，and the classification module for classifying the samples，and the evaluation module for evaluating the VFDT decision tree using the labeled samples.The functions of each module are realized by correctly designing the Spout/Bolt of Storm Topology，and the parallelization of the classification module is implemented by deploying multiple tasks for Classification Bolt.The memory database Redis is used to realize the effective connection of the three modules and the preservation of the decision tree.The message middleware Kafka is used to improve the tolerance of burst stream data.The results of implementing and testing VFDT algorithm based on the proposed scheme show that the classification efficiency of VFDT algorithm under the Storm cluster environment is significantly improved compared with that under the single machine environment，and the classification efficiency can be further improved by reasonably setting the task number in Classification Bolt.

stream data;Very Fast Decision Tree(VFDT);distribution;parallelization;Storm

TP311

A

1673-629X(2016)09-0192-05

10.3969/j.issn.1673-629X.2016.09.043

2015-11-13

2016-03-03< class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間:

時(shí)間:2016-08-23

國(guó)家自然科學(xué)基金資助項(xiàng)目(61302158，61571238);中興通訊產(chǎn)學(xué)研項(xiàng)目

張發(fā)揚(yáng)(1990-)，男，碩士研究生，CCF會(huì)員，研究方向?yàn)榱鲾?shù)據(jù)挖掘;李玲娟，教授，CCF會(huì)員，研究方向?yàn)閿?shù)據(jù)挖掘、信息安全、分布式計(jì)算。

http://www.cnki.net/kcms/detail/61.1450.TP.20160823.1359.044.html