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

劉迎春，陳梅玲

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

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

劉迎春，陳梅玲

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

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

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

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

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

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

但隨著互聯(lián)網(wǎng)大數(shù)據(jù)需求的不斷增長(zhǎng)，滿足實(shí)時(shí)性、突發(fā)性、無(wú)限性分析要求的流式計(jì)算系統(tǒng)開(kāi)始出現(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)前急需解決的問(wèn)題。

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

1　介 紹

1.1流式計(jì)算介紹

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

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

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

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

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

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

互聯(lián)網(wǎng)領(lǐng)域就是很好的流式大數(shù)據(jù)應(yīng)用場(chǎng)景。該領(lǐng)域在日常運(yùn)營(yíng)中會(huì)產(chǎn)生大量數(shù)據(jù)，包括系統(tǒng)自動(dòng)生成的用戶、行為、日志等信息，也包括用戶所實(shí)時(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è)對(duì)系統(tǒng)響應(yīng)時(shí)間的高要求，這些數(shù)據(jù)往往需要實(shí)時(shí)的分析和計(jì)算，以便及時(shí)為用戶提供更理想的服務(wù)。

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

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

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

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

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

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

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

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

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

在隨機(jī)森林中，單棵樹(shù)的生長(zhǎng)過(guò)程如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

margin（x，y）大于零的樣本，說(shuō)明決策樹(shù)集可以得到正確結(jié)果。與已有的決策樹(shù)相似度高的樹(shù)并不會(huì)提高整個(gè)森林的準(zhǔn)確度，此類樣本不需要再次處理。為了讓新生成的決策樹(shù)能夠提高整個(gè)森林的準(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ī)森林方法，獲得一個(gè)新的決策樹(shù)集合｛h′（x，θk），k=1，…｝。數(shù)據(jù)集S′只代表了全部數(shù)據(jù)集中的一部分?jǐn)?shù)據(jù)，在S′中篩選一定比例的決策樹(shù)，加入原來(lái)的決策樹(shù)集合中。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

⑥清空訓(xùn)練數(shù)據(jù)集S′，開(kāi)始處理下一批數(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í)時(shí)計(jì)算和計(jì)算效率；

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

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

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

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

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

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

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

續(xù)表1

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

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

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

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

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

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

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

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

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

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

模式3：使用新的隨機(jī)森林方法來(lái)訓(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)的存儲(chǔ)空間如圖4所示。

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

可以看出，模式1所需要的存儲(chǔ)空間隨時(shí)間和數(shù)據(jù)量線性增長(zhǎng)，所需要的空間最大。模式2所需要的存儲(chǔ)空間與每個(gè)周期的總數(shù)據(jù)量相關(guān)，比模式1要少很多，在流量變化不大時(shí)會(huì)保持平穩(wěn)。模式3所需要的空間最少，遠(yuǎn)小于模式2，而且其波動(dòng)幅度僅與算法當(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)過(guò)分類器1次的情況下工作，不需要對(duì)海量的歷史數(shù)據(jù)進(jìn)行存儲(chǔ)和掃描，對(duì)存儲(chǔ)空間的要求很低；還可以根據(jù)流式大數(shù)據(jù)的變化進(jìn)行自我調(diào)整，適應(yīng)新的數(shù)據(jù)，在保證數(shù)據(jù)吞吐量和處理效率的同時(shí)，保持對(duì)數(shù)據(jù)的處理準(zhǔn)確度。

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

但該方法在其他類型的數(shù)據(jù)集上是否通用，剪枝的判定函數(shù)是否還可以有所提高，新決策樹(shù)所占的比例應(yīng)該是多少合適以及如何將改進(jìn)后的隨機(jī)森林算法與Storm、S4等分布式大數(shù)據(jù)處理架構(gòu)結(jié)合，實(shí)現(xiàn)更好的系統(tǒng)容錯(cuò)、資源調(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ù)庫(kù)，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：可伸縮的單通過(guò)分析用Map Reduce平臺(tái)［J］.ACM數(shù)據(jù)庫(kù)系統(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］ 李國(guó)杰，程學(xué)旗.大數(shù)據(jù)的研究現(xiàn)狀與科學(xué)思考［J］.中國(guó)科學(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é)報(bào)，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］ 覃雄派，王會(huì)舉，杜小勇，王珊.大數(shù)據(jù)分析——RDBMS與MapReduce的競(jìng)爭(zhēng)與共生［J］.軟件學(xué)報(bào)，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é)報(bào)，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ì)算平臺(tái).第十屆IEEE數(shù)據(jù)挖掘國(guó)際會(huì)議（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.臉書(shū)中Apachi Hadoop的實(shí)時(shí)應(yīng)用.ACM數(shù)據(jù)管理國(guó)際會(huì)議（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)研究。