劉迎春，陳梅玲

（北京航空航天大學(xué)經(jīng)濟(jì)管理學(xué)院，北京 100191）

流式大數(shù)據(jù)下隨機(jī)森林方法及應(yīng)用

劉迎春，陳梅玲

（北京航空航天大學(xué)經(jīng)濟(jì)管理學(xué)院，北京 100191）

流式計(jì)算形態(tài)下的大數(shù)據(jù)分析一直是當(dāng)前需要解決的問題，而且研究成果和實(shí)踐經(jīng)驗(yàn)較少。隨機(jī)森林方法是目前應(yīng)用較多的分類算法，但在流式計(jì)算應(yīng)用場景中，數(shù)據(jù)所呈現(xiàn)出來的實(shí)時性、易失性、無序性等特征會使得算法準(zhǔn)確度逐漸降低。針對這個問題，分析了隨機(jī)森林的算法特點(diǎn)，提出了根據(jù)決策樹的準(zhǔn)確度進(jìn)行隨機(jī)森林剪枝的思路。同時為了適應(yīng)數(shù)據(jù)的變化，結(jié)合準(zhǔn)確度間隔的概念提出生成、驗(yàn)證并補(bǔ)充新決策樹的方法，最終形成可以不斷隨數(shù)據(jù)更新的隨機(jī)森林，滿足流式大數(shù)據(jù)環(huán)境對算法的要求。使用實(shí)際數(shù)據(jù)對改進(jìn)后方法的可行性進(jìn)行了驗(yàn)證，證明新方法在真實(shí)流式大數(shù)據(jù)場景中有著更高的分類準(zhǔn)確度，最后分析討論了隨機(jī)森林方法如何進(jìn)一步研究改進(jìn)的主題。

決策樹；隨機(jī)森林方法；大數(shù)據(jù)；流式計(jì)算；社交網(wǎng)站；搜索引擎；分類器；剪枝；客戶評分；分布式系統(tǒng)

在各應(yīng)用場景中，大數(shù)據(jù)計(jì)算模式［1-4］可分為批量計(jì)算、流式計(jì)算2種。批量計(jì)算，指先對數(shù)據(jù)收集存儲，再對已經(jīng)存儲靜態(tài)數(shù)據(jù)集中計(jì)算，發(fā)現(xiàn)數(shù)據(jù)價值。流式計(jì)算，指無法確定數(shù)據(jù)到來順序和時間，也無法將歷史數(shù)據(jù)全部存儲，而是當(dāng)數(shù)據(jù)流動進(jìn)來后在內(nèi)存直接實(shí)時計(jì)算數(shù)據(jù)，輸出有價值的信息。

大數(shù)據(jù)批量計(jì)算技術(shù)的研究相對更成熟［5-6］，例如開源的Hadoop系統(tǒng)、Google的MapReduce模型等，得到廣泛應(yīng)用的系統(tǒng)就都是基于批量計(jì)算技術(shù)的［7］。對于更看重輸出結(jié)果的準(zhǔn)確性、全面性的場景，批量計(jì)算更有優(yōu)勢。

對于實(shí)時性要求更高、數(shù)據(jù)流量不確定、對數(shù)據(jù)準(zhǔn)確度要求稍低的場景來說，流式計(jì)算具有明顯優(yōu)勢［8-9］。與大量的批量計(jì)算技術(shù)研究相比，關(guān)于流式計(jì)算的研究較少。早期的流式計(jì)算研究是以數(shù)據(jù)庫環(huán)境中的流式數(shù)據(jù)計(jì)算為主。

但隨著互聯(lián)網(wǎng)大數(shù)據(jù)需求的不斷增長，滿足實(shí)時性、突發(fā)性、無限性分析要求的流式計(jì)算系統(tǒng)開始出現(xiàn)，例如Yahoo在2010年推出的S4流式計(jì)算系統(tǒng)［10］、Twitter在2011年推出的Storm流式系統(tǒng)、Facebook的DFP系統(tǒng)［11］等。這些系統(tǒng)各有其缺點(diǎn)，如何構(gòu)建高可靠、高吞吐、低延遲、持續(xù)運(yùn)行的大數(shù)據(jù)流式計(jì)算系統(tǒng)，是當(dāng)前急需解決的問題。

本文分析了流式計(jì)算場景的特點(diǎn)，討論了流式計(jì)算技術(shù)應(yīng)該具有的主要技術(shù)特性，并基于Breiman等人在2001年提出的隨機(jī)森林方法（random forest），設(shè)計(jì)了在互聯(lián)網(wǎng)行業(yè)這一典型的大數(shù)據(jù)流式計(jì)算應(yīng)用場景中的流式計(jì)算方法，并利用真實(shí)數(shù)據(jù)進(jìn)行了測試，驗(yàn)證了方法的實(shí)際可行性。

1　介 紹

1.1流式計(jì)算介紹

流式大數(shù)據(jù)計(jì)算主要有以下特征：

1）實(shí)時性。流式大數(shù)據(jù)不僅是實(shí)時產(chǎn)生的，也是要求實(shí)時給出反饋結(jié)果。系統(tǒng)要有快速響應(yīng)能力，在短時間內(nèi)體現(xiàn)出數(shù)據(jù)的價值，超過有效時間后數(shù)據(jù)的價值就會迅速降低。

2）突發(fā)性。數(shù)據(jù)的流入速率和順序并不確定，甚至?xí)休^大的差異。這要求系統(tǒng)要有較高的吞吐量，能快速處理大數(shù)據(jù)流量。

3）易失性。由于數(shù)據(jù)量的巨大和其價值隨時間推移的降低，大部分?jǐn)?shù)據(jù)并不會持久保存下來，而是在到達(dá)后就立刻被使用并丟棄。系統(tǒng)對這些數(shù)據(jù)有且僅有一次計(jì)算機(jī)會。

4）無限性。數(shù)據(jù)會持續(xù)不斷產(chǎn)生并流入系統(tǒng)。在實(shí)際的應(yīng)用場景中，暫停服務(wù)來更新大數(shù)據(jù)分析系統(tǒng)是不可行的，系統(tǒng)要能夠持久、穩(wěn)定地運(yùn)行下去，并隨時進(jìn)行自我更新，以便適應(yīng)分析需求。

1.2應(yīng)用場景介紹

互聯(lián)網(wǎng)領(lǐng)域就是很好的流式大數(shù)據(jù)應(yīng)用場景。該領(lǐng)域在日常運(yùn)營中會產(chǎn)生大量數(shù)據(jù)，包括系統(tǒng)自動生成的用戶、行為、日志等信息，也包括用戶所實(shí)時分享的各類數(shù)據(jù)。互聯(lián)網(wǎng)行業(yè)的數(shù)據(jù)量不僅巨大，其中半結(jié)構(gòu)化和非結(jié)構(gòu)化所呈現(xiàn)的數(shù)據(jù)也更多。由于互聯(lián)網(wǎng)行業(yè)對系統(tǒng)響應(yīng)時間的高要求，這些數(shù)據(jù)往往需要實(shí)時的分析和計(jì)算，以便及時為用戶提供更理想的服務(wù)。

流式計(jì)算在互聯(lián)網(wǎng)大數(shù)據(jù)中的典型應(yīng)用場景如下：

1）社交網(wǎng)站。在社交網(wǎng)站中，要對用戶信息進(jìn)行實(shí)時分析，一方面將用戶所發(fā)布的信息推送出去，另一方面也要為用戶及時發(fā)現(xiàn)和推薦其感興趣的內(nèi)容，及時發(fā)現(xiàn)和防止欺詐行為，增進(jìn)用戶使用體驗(yàn)。

2）搜索引擎。搜素引擎除了向用戶反饋搜索結(jié)果以外，還要考慮和計(jì)算用戶的搜索歷史，發(fā)掘用戶感興趣的內(nèi)容和偏好，為用戶推送推廣信息。

3）電子商務(wù)。電子商務(wù)側(cè)重于大數(shù)據(jù)技術(shù)中的用戶偏好分析和關(guān)聯(lián)分析，以便有針對性地向用戶推薦商品。同時，隨著大量電子商務(wù)開始內(nèi)嵌互聯(lián)網(wǎng)消費(fèi)金融服務(wù)，對用戶的風(fēng)險分析和預(yù)警也是非常重要的。

可以預(yù)見，隨著技術(shù)的不斷發(fā)展、互聯(lián)網(wǎng)與物聯(lián)網(wǎng)等領(lǐng)域的不斷深入連接，未來要分析的數(shù)據(jù)量必然還會爆炸性增長。傳統(tǒng)的批量計(jì)算方式并不適合這類對響應(yīng)時間要求很高的場景，能持續(xù)運(yùn)行、快速響應(yīng)的流式計(jì)算方法，才能解決這一方面的需求。

1.3隨機(jī)森林方法介紹

隨機(jī)森林是目前海量數(shù)據(jù)處理中應(yīng)用最廣的分類器之一，在響應(yīng)速度、數(shù)據(jù)處理能力上都有出色表現(xiàn)［10，13］。隨機(jī)森林是決策樹｛h（x，θk），k=1，…｝的集合H，其中h（x，θk）是元分類器，是用CART算法生成的1棵沒有剪枝的回歸分類樹；x為輸入向量，｛θk｝是獨(dú)立而且同分布隨機(jī)向量，決定每一棵決策樹的生長過程。

每個元分類器h∈H，都等價于從輸入空間X到輸出類集Y的映射函數(shù)。對輸入空間X中的每一條輸入xi，h都可以得到h（xi）=yi，yi為分類器h給出的決策結(jié)果。

定義決策函數(shù)D，則分類器集合H對輸入xi所得到的最終結(jié)果y就可以定義如下：

在隨機(jī)森林中，單棵樹的生長過程如下：

1）針對原始訓(xùn)練集，使用Bagging方法在原始樣本集S中進(jìn)行有放回的隨機(jī)數(shù)據(jù)選取，形成有區(qū)別的訓(xùn)練集Tset。

2）采用抽樣的方式選取特征。假設(shè)數(shù)據(jù)集一共有N個特征，選擇其中M個特征，M≤N。每個抽取出來的訓(xùn)練集，使用隨機(jī)選取的M個特征來進(jìn)行節(jié)點(diǎn)分裂。

3）所有生成的決策樹自由生長，不進(jìn)行剪枝。每一棵決策樹的輸出結(jié)果之間可采用簡單的多數(shù)投票法（針對分類問題）或者結(jié)果平均法（針對回歸問題）組合成最終的輸出結(jié)果。

隨機(jī)森林方法是組合分類器算法的一種，是決策樹的組合。它擁有Bagging和隨機(jī)特征選擇這2種方法的優(yōu)點(diǎn)。在大數(shù)據(jù)環(huán)境下，隨機(jī)森林方法還有以下優(yōu)點(diǎn)：

①隨機(jī)森林方法可以處理大數(shù)據(jù)量，能夠應(yīng)對突發(fā)性數(shù)據(jù)；

②隨機(jī)森林方法生成較為簡單的決策樹，易于解讀；

③隨機(jī)森林方法適用于分布式和并行環(huán)境，擴(kuò)展性好，適用于對分布式架構(gòu)有很高要求的流式大數(shù)據(jù)處理環(huán)境；

4）決策樹分類器非常簡單，能以極高效率對新數(shù)據(jù)進(jìn)行處理，適用于流式大數(shù)據(jù)環(huán)境下對響應(yīng)速度要求高的特點(diǎn)；

在流式大數(shù)據(jù)環(huán)境下，隨機(jī)森林方法也存在一些問題，其中最核心的問題，就是流式大數(shù)據(jù)環(huán)境中數(shù)據(jù)具有實(shí)時性和易失性的特點(diǎn)，經(jīng)典隨機(jī)森林方法難以適應(yīng)。以訓(xùn)練集數(shù)據(jù)為基礎(chǔ)所生成的決策樹會過期，對新數(shù)據(jù)進(jìn)行分類的準(zhǔn)確度下降。

2　流式大數(shù)據(jù)環(huán)境下的算法改進(jìn)

2.1方法改進(jìn)思路

以往對隨機(jī)森林方法的改進(jìn)主要集中在幾個方面：

將隨機(jī)森林與Hadoop、MapReduce等計(jì)算框架結(jié)合，實(shí)現(xiàn)分布式隨機(jī)森林方法，提高算法的處理效率。

對數(shù)據(jù)進(jìn)行預(yù)處理，降低數(shù)據(jù)集的不平衡性，以此提升算法在非平衡性數(shù)據(jù)集上的準(zhǔn)確度和分類性能。

針對標(biāo)準(zhǔn)隨機(jī)森林方法采用C4.5作為節(jié)點(diǎn)分裂算法的情況，用效率更高的節(jié)點(diǎn)分裂算法如CHI2來替換C4.5，可以提高算法處理大數(shù)據(jù)集的能力。

基于分類器相似性度量和分類間隔概念，對冗余的分類器進(jìn)行修剪，以取得更好的分類效果與更小的森林規(guī)模。

這幾種改進(jìn)方法可以有效地在特定環(huán)境下提高隨機(jī)森林算法的表現(xiàn)，但都不能完全滿足流式大數(shù)據(jù)環(huán)境對算法的要求。鑒于流式大數(shù)據(jù)算法需求所表現(xiàn)出來的鮮明特征，從流式大數(shù)據(jù)的特征出發(fā)，對經(jīng)典的隨機(jī)森林方法進(jìn)行改造，思路如下：

1）使用隨機(jī)森林方法實(shí)時處理數(shù)據(jù)，由于隨機(jī)森林是一種比較簡單的分類器，對數(shù)據(jù)的響應(yīng)時間可以得到保障，能夠滿足實(shí)時性要求。

2）僅對一段時間內(nèi)的數(shù)據(jù)進(jìn)行存儲，在內(nèi)存可用的條件下處理少量數(shù)據(jù)，這樣就可以解決流式大數(shù)據(jù)的易失性和無限性特點(diǎn)。

3）由于數(shù)據(jù)的無序性，經(jīng)典隨機(jī)森林所產(chǎn)生的分類器無法滿足所有的輸入數(shù)據(jù)，必須令分類器能夠隨著新數(shù)據(jù)的輸入不斷更新，保持對數(shù)據(jù)的敏感性和準(zhǔn)確度。因?yàn)閿?shù)據(jù)的易失性，所以分類器的更新就必須基于算法所臨時保存的有限訓(xùn)練數(shù)據(jù)進(jìn)行。

4）分類器更新方法必須是可伸縮的、高效的，不能影響到分類器對數(shù)據(jù)的正常處理。

2.2改進(jìn)后的隨機(jī)森林方法

首先定義隨機(jī)森林中決策樹h的準(zhǔn)確度（accurate）Ah：

式中，nr是決策樹h給出正確結(jié)果的次數(shù)，n是決策樹h所處理過的所有數(shù)據(jù)數(shù)量。準(zhǔn)確度給出了在一定時間內(nèi)某棵樹給出正確結(jié)果的比例。

在回歸問題中，決策樹h給出的分類結(jié)果如與最終結(jié)果一致，則認(rèn)為該決策樹得出了正確結(jié)果。計(jì)算決策樹h給出結(jié)果xi與最終結(jié)果之間的差值，并取其標(biāo)準(zhǔn)差作為h的準(zhǔn)確度：

準(zhǔn)確度衡量一棵樹在一段時間內(nèi)判定結(jié)果的準(zhǔn)確程度。算法在執(zhí)行過程中跟蹤每棵樹的準(zhǔn)確度，并定期對隨機(jī)森林進(jìn)行更新，淘汰其中準(zhǔn)確度最低的樹：

1）按照標(biāo)準(zhǔn)的隨機(jī)森林方法構(gòu)造決策樹群H。

2）為每一棵決策樹h，h∈H建立1張記錄表Th，記錄隨機(jī)森林在處理數(shù)據(jù)過程中生成的結(jié)果。

3）一段時間后，對所有決策樹的結(jié)果記錄表進(jìn)行掃描，刪除其中準(zhǔn)確度最低的樹。

通過準(zhǔn)確度進(jìn)行篩選后，森林中樹的數(shù)量會越來越少，實(shí)現(xiàn)決策樹集的剪枝。但數(shù)量的過分減少，也會造成整個決策樹集在準(zhǔn)確度上的降低［11］。

為了保持一定數(shù)量的決策樹，在剪枝的同時，也要對數(shù)據(jù)集進(jìn)行跟蹤，生成新的決策樹來保持整個森林的質(zhì)量。為了從數(shù)據(jù)集中篩選出對生成新的決策樹更有用的樣本，引入間隔（margin）定義如下：間隔指隨機(jī)森林在1條給定樣本數(shù)據(jù)（x，y）上的整體決策正確度，定義為：

式中，avk（）是一個求均值函數(shù)，I（）是一個度量函數(shù)。如果在隨機(jī)森林中大部分決策樹對樣本（x，y）得到正確結(jié)果，則margin（x，y）大于零。如果margin（x，y）小于零或某一閾值，則說明該樣本被大部分決策樹識別失誤，算法對該樣本得出了錯誤結(jié)論。

margin（x，y）大于零的樣本，說明決策樹集可以得到正確結(jié)果。與已有的決策樹相似度高的樹并不會提高整個森林的準(zhǔn)確度，此類樣本不需要再次處理。為了讓新生成的決策樹能夠提高整個森林的準(zhǔn)確度，記錄margin（x，y）小于等于零的樣本，形成新的訓(xùn)練數(shù)據(jù)集S′。數(shù)據(jù)集S′的特點(diǎn)，是只占當(dāng)前數(shù)據(jù)集S中的一小部分，但其數(shù)據(jù)特征與其他數(shù)據(jù)不同。

在數(shù)據(jù)集S′上使用隨機(jī)森林方法，獲得一個新的決策樹集合｛h′（x，θk），k=1，…｝。數(shù)據(jù)集S′只代表了全部數(shù)據(jù)集中的一部分?jǐn)?shù)據(jù)，在S′中篩選一定比例的決策樹，加入原來的決策樹集合中。

根據(jù)S′與S之間的比例確定要篩選出的決策樹數(shù)量：

篩選方法可以有以下幾種：

S′篩選法：利用S′進(jìn)行檢驗(yàn)，并按照準(zhǔn)確度對所有決策樹排序，選擇其中準(zhǔn)確度最高的Nnew棵決策樹。

S篩選法：利用全部數(shù)據(jù)集S進(jìn)行檢驗(yàn)，并按準(zhǔn)確度對所有決策樹排序，選擇準(zhǔn)確度最高的Nnew棵樹。

Margin篩選法：計(jì)算每棵樹在數(shù)據(jù)集S′上的margin均值與margin方差之比［18］，作為每一棵決策樹的重要性衡量指標(biāo)，選擇最重要的Nnew棵樹。

改進(jìn)后的隨機(jī)森林方法流程如圖1所示。

圖1　改進(jìn)后隨機(jī)森林方法流程圖

①使用初始訓(xùn)練數(shù)據(jù)集S生成最初的隨機(jī)森林H；

②使用隨機(jī)森林H對當(dāng)前待處理的數(shù)據(jù)集Si進(jìn)行分類：

a）用隨機(jī)森林中的每一棵樹hj對Si中的每一條數(shù)據(jù)xj進(jìn)行分類；

b）記錄每一棵樹和每一條數(shù)據(jù)的分類結(jié)果，同時計(jì)算該條數(shù)據(jù)分類結(jié)果的間隔值margin（xj，y）；

c）如果margin（xj，y）小于給定閾值，則將xj加入新訓(xùn)練數(shù)據(jù)集S′。

③Si分類完畢后，計(jì)算每棵樹的準(zhǔn)確度，并進(jìn)行剪枝；

④在新訓(xùn)練數(shù)據(jù)集S′上執(zhí)行隨機(jī)森林方法，生成新的隨機(jī)森林H′；

⑤對新的隨機(jī)森林進(jìn)行剪枝，將剪枝后的H′與H合并，形成新的隨機(jī)森林H；

⑥清空訓(xùn)練數(shù)據(jù)集S′，開始處理下一批數(shù)據(jù)。

2.3新隨機(jī)森林方法的優(yōu)點(diǎn)

新的隨機(jī)森林方法有著以下優(yōu)點(diǎn)：

1）新方法每次所處理的數(shù)據(jù)集是有限的，在實(shí)際應(yīng)用中，可以根據(jù)內(nèi)存大小設(shè)計(jì)每次處理的數(shù)據(jù)集大小，保證數(shù)據(jù)的實(shí)時計(jì)算和計(jì)算效率；

2）新方法中，需要存儲的只有結(jié)果記錄表和新訓(xùn)練數(shù)據(jù)集，相比原始數(shù)據(jù)流小了很多，滿足流式大數(shù)據(jù)的易失性特點(diǎn)，在大數(shù)據(jù)量下的伸縮性更好；

3）對新數(shù)據(jù)的處理只需要使用隨機(jī)森林進(jìn)行驗(yàn)證和投票，執(zhí)行效率高，能夠?qū)崟r反饋數(shù)據(jù)的處理結(jié)果；

4）該系統(tǒng)可以持續(xù)地更新運(yùn)行下去，并能夠不斷使用數(shù)據(jù)的新特性來更新自身，滿足流式大數(shù)據(jù)環(huán)境的無序性和無限性特點(diǎn)。

3　數(shù)據(jù)驗(yàn)證

3.1測試數(shù)據(jù)集

測試數(shù)據(jù)集為來自互聯(lián)網(wǎng)行業(yè)的客戶信息數(shù)據(jù)。數(shù)據(jù)量為20萬條，5年時間跨度，每個季度的數(shù)據(jù)量為1萬條。數(shù)據(jù)包括1個目的類別（客戶值：高/低）和如表1所示的16個特征屬性。

表1　測試數(shù)據(jù)集

續(xù)表1

為了驗(yàn)證改進(jìn)后隨機(jī)森林算法的有效性，使用第1年第1季度的1萬條數(shù)據(jù)作為初始化訓(xùn)練集，利用這些數(shù)據(jù)建立最初的隨機(jī)森林，樹的數(shù)量ntree=100。

3.2數(shù)據(jù)模式的變化對算法的影響

以第1年第1季度的1萬條數(shù)據(jù)作為初始化訓(xùn)練集，建立隨機(jī)森林，并利用建好的隨機(jī)森林對后面的流式客戶數(shù)據(jù)進(jìn)行處理，每個季度為1個周期。隨著時間的變化，原有隨機(jī)森林會逐漸變得不適應(yīng)新的數(shù)據(jù)，客戶價值評級的準(zhǔn)確度隨時間降低，從第1季度的93%下降到第5年的81%。

定義剪枝數(shù)量為50%，用改進(jìn)后的隨機(jī)森林方法生成新的決策樹，加入到原有的隨機(jī)森林中。使用2.2節(jié)所描述的不同決策樹篩選方法，改進(jìn)后的隨機(jī)森林方法表現(xiàn)如圖2所示。

圖2　改進(jìn)后隨機(jī)森林方法的準(zhǔn)確度比較

可以看到，與原有的隨機(jī)森林方法相比，改進(jìn)后的隨機(jī)森林方法對數(shù)據(jù)模式的變化有明顯更好的適應(yīng)性，隨著時間的變化整個森林也在緩慢更新，改進(jìn)后方法的準(zhǔn)確度一直穩(wěn)定保持在90%以上。

在篩選新決策樹的方法中，使用在新樣本數(shù)據(jù)集S′上的準(zhǔn)確度進(jìn)行篩選（S′篩選法）和使用每棵樹的margin均值與margin方差之比篩選（margin篩選法），都可以得到很好的效果，方法之間差別很小。使用數(shù)據(jù)集S進(jìn)行篩選的方法（S篩選法）也可以提高準(zhǔn)確度，但其準(zhǔn)確度逐漸下降到87%，不如另外2種方法。

假設(shè)不考慮內(nèi)存限制，在每一季度結(jié)束后使用另外2種模式來更新隨機(jī)森林：

模式1：每次都使用從最開始到當(dāng)前的全部數(shù)據(jù)來重新訓(xùn)練生成隨機(jī)森林；

模式2：每次都使用上一季度的全部數(shù)據(jù)來重新訓(xùn)練生成隨機(jī)森林；

模式3：使用新的隨機(jī)森林方法來訓(xùn)練生成隨機(jī)森林；

以上3種模式下的隨機(jī)森林方法表現(xiàn)如圖3所示。

圖3　不同模式隨機(jī)森林方法的準(zhǔn)確度比較

可以看到，模式3的準(zhǔn)確度是最優(yōu)的，模式2的準(zhǔn)確度稍差，但是也較為平穩(wěn)，模式1的準(zhǔn)確度最差，隨數(shù)據(jù)量增大下降較快。

這3種模式分別所需要耗費(fèi)的存儲空間如圖4所示。

圖4　不同模式隨機(jī)森林方法所需存儲比較

可以看出，模式1所需要的存儲空間隨時間和數(shù)據(jù)量線性增長，所需要的空間最大。模式2所需要的存儲空間與每個周期的總數(shù)據(jù)量相關(guān)，比模式1要少很多，在流量變化不大時會保持平穩(wěn)。模式3所需要的空間最少，遠(yuǎn)小于模式2，而且其波動幅度僅與算法當(dāng)前準(zhǔn)確度有關(guān)，與總的數(shù)據(jù)流量關(guān)系不大。

4　結(jié) 論

本文在原有隨機(jī)森林方法的基礎(chǔ)上，提出了一種能夠適應(yīng)流式大數(shù)據(jù)環(huán)境的新隨機(jī)森林方法。新的方法可以在流式大數(shù)據(jù)只經(jīng)過分類器1次的情況下工作，不需要對海量的歷史數(shù)據(jù)進(jìn)行存儲和掃描，對存儲空間的要求很低；還可以根據(jù)流式大數(shù)據(jù)的變化進(jìn)行自我調(diào)整，適應(yīng)新的數(shù)據(jù)，在保證數(shù)據(jù)吞吐量和處理效率的同時，保持對數(shù)據(jù)的處理準(zhǔn)確度。

在使用真實(shí)互聯(lián)網(wǎng)行業(yè)流式大數(shù)據(jù)場景試驗(yàn)表明，新的隨機(jī)森林方法可以解決互聯(lián)網(wǎng)行業(yè)流式大數(shù)據(jù)場景所遇到的實(shí)際問題，驗(yàn)證了其有效性。

但該方法在其他類型的數(shù)據(jù)集上是否通用，剪枝的判定函數(shù)是否還可以有所提高，新決策樹所占的比例應(yīng)該是多少合適以及如何將改進(jìn)后的隨機(jī)森林算法與Storm、S4等分布式大數(shù)據(jù)處理架構(gòu)結(jié)合，實(shí)現(xiàn)更好的系統(tǒng)容錯、資源調(diào)度、負(fù)載均衡性能等有待探討。

［1］ 孟小峰，慈祥.大數(shù)據(jù)管理：概念、技術(shù)與挑戰(zhàn)［J］.計(jì)算機(jī)研究與發(fā)展，2013，50（1）：146-169

Meng X F，Ci X.Big Data Management：Concepts，Techniques and Challenges［J］.Journal of Computer Research and Development，2013，50（1）：146-169（in Chinese）

［2］ Lim L，Misra A，Mo T L.基于節(jié)能智能手機(jī)的連續(xù)處理傳感器數(shù)據(jù)流自適應(yīng)數(shù)據(jù)采集策略［J］.分布式和并行數(shù)據(jù)庫，2013，31（2）：321-351

Lim L，Misra A，Mo T L.Adaptive Data Acquisition Strategies for Energy-Efficient，Smartphone-Based，Continuous Processing of Sensor Streams［J］.Distributed and Parallel Databases，2013，31（2）：321-351（in Chinese）

［3］ Li B D，Mazur E，Diao Y L.SCALLA：可伸縮的單通過分析用Map Reduce平臺［J］.ACM數(shù)據(jù)庫系統(tǒng)通訊，2012，37 （4）：1-43

Li B D，Mazur E，Diao Y L.SCALLA：A Platform for Scalable One-Pass Analytics Using Map Reduce［J］.ACM Trans.on Database Systems，2012，37（4）：1-43（in Chinese）

［4］ Yang D，Rundensteiner E A，Ward M.數(shù)據(jù)流中的鄰近模式挖掘［J］.信息系統(tǒng)，2013，38（3）：331-350

Yang D，Rundensteiner E A，Ward M.Mining Neighbor-Based Patterns in Data Streams［J］.Information Systems，2013，38 （3）：331-350（in Chinese）

［5］ 李國杰，程學(xué)旗.大數(shù)據(jù)的研究現(xiàn)狀與科學(xué)思考［J］.中國科學(xué)院院刊，2012，27（6）：647-657

Li G J，Cheng X Q.Research Status and Scientific Thinking of Big Data［J］.Bulletin of Chinese Academy of Sciences，2012，27 （6）：647-657（in Chinese）

［6］ 王元卓，靳小龍，程學(xué)旗.網(wǎng)絡(luò)大數(shù)據(jù)：現(xiàn)狀與展望［J］.計(jì)算機(jī)學(xué)報，2013，36（6）：1125-1138

Wang Y Z，Jin X L，Cheng X Q.Network Big Data：Present and Future［J］.Chinese Journal of Computers，2013，36（6）：1125-1138（in Chinese）

［7］ 覃雄派，王會舉，杜小勇，王珊.大數(shù)據(jù)分析——RDBMS與MapReduce的競爭與共生［J］.軟件學(xué)報，2012，23（1）：32-45

Qin X P，Wang H J，Du X Y，Wang S.Big Data Analysis：Competition and Symbiosis of RDBMS and Map Reduce［J］.Ruan Jian Xue Bao/Journal of Software，2012，23（1）：32-45（in Chinese）

［8］ Kobielus A.大數(shù)據(jù)架構(gòu)中流式計(jì)算技術(shù)的角色.2013.http：//ibmdatamag.com/2013/01/the-role-of-stream-computing-inbig-data-architectures/

Kobielus A.The Role of Stream Computing in Big Data Architectures.2013.http：//ibmdatamag.com/2013/01/the-role-ofstream-computing-in-big-data-architectures/（in Chinese）

［9］ 孫大為，張廣艷，鄭緯民.大數(shù)據(jù)流式計(jì)算：關(guān)鍵技術(shù)及系統(tǒng)實(shí)例［J］.軟件學(xué)報，2014（4）：839-862

Sun D W，Zhang G Y，Zheng W M.Big Data Stream Computing：Technologies and Instances［J］.Journal of Software，2014 （4）：839-862（in Chinese）

［10］Neumeyer L，Robbins B，Nair A，Kesari A.S4：分布式流計(jì)算平臺.第十屆IEEE數(shù)據(jù)挖掘國際會議（ICDMW 2010）.Sydney：IEEE Press，2010.2010.170-177

Neumeyer L，Robbins B，Nair A，Kesari A.S4：Distributed Stream Computing Platform.In：Proc.of the 10th IEEE Int＇l Conf. on Data Mining Workshops（ICDMW 2010）.Sydney：IEEE Press，2010：170-177（in Chinese）

［11］Borthakur D，Sarma JS，Gray J，Muthukkaruppan K，Spigeglberg N，Kuang HR，Ranganathan K，Molkov D，Mennon A，Rash S，Schmidt R，Aiyer A.臉書中Apachi Hadoop的實(shí)時應(yīng)用.ACM數(shù)據(jù)管理國際會議（SIGMOD 2011 and PODS 2011）. Athens：ACM Press，2011：1071-1080

Borthakur D，Sarma JS，Gray J，Muthukkaruppan K，Spigeglberg N，Kuang HR，Ranganathan K，Molkov D，Mennon A，Rash S，Schmidt R，Aiyer A.Apache hadoop goes realtime at Facebook.In：Proc.of the ACM SIGMOD Int＇l Conf.on Management of Data（SIGMOD 2011 and PODS 2011）.Athens：ACM Press，2011：1071-1080（in Chinese）

Random Forest Method and Application in Stream Big Data Systems

Liu Yingchun，Chen Meiling
（School of Economics and Management，Beihang University，Beijing 100191，China）

Stream computing is an important form of big data computing.Random forest method is one of the most widely applied classification algorithms at present.From the actual requirements，random forest method faces not only huge number of features but also constantly changing data pattern over time.The accuracy of a random forest algorithm without self renewal and adaptive algorithm will gradually reduce over time.Aiming at this problem，this paper analyzes the characteristics of random forest algorithm，gives a new pruning idea according to the accuracy of the decision trees.In order to adapt to the change of data，a new random method based on margin is presented.This new method can update itself constantly and can be applied in stream big data environments.Using the actual data，the new method is verified has higher accuracy in classification，and analysis and discussion of how to further research and improve the random forest method in big data environment.

decision tree，random forest，big data，stream computing，social network，searching engine，classifier，pruning，customer rating，distributed system

TP391

A

1000-2758（2015）06-1055-07

2015-04-24

劉迎春（1980—），女，北京航空航天大學(xué)博士研究生，主要從事大數(shù)據(jù)、分布式系統(tǒng)研究。