隨機森林在短時交通流中的應用?

冒云香 李星毅

（江蘇大學計算機科學與通信工程學院 鎮江 212000）

1 引言

智能交通系統（ITS）迅速發展，交通流實時誘導成為ITS 研究的熱點問題，該問題核心是實時準確的短時交通流預測。中型規模城市每天的交通流數量約為千萬條，每年的數據量達到數百TB級，面對如此龐大的數據量，使用“分而治之”的MapReduce分布式計算模式能夠大大提高運行速度。

早期的交通流預測方法主要分為三種：1）傳統的統計方法，包括歷史平均模型、線性回歸模型、時間序列模型等；2）智能算法，包括支持向量機，神經網絡等；3）融合技術，融合多方法預測［1］。其中支持向量機（Support Vector Machine，SVM）是最為流行有效的一種方法，但不足之處在于對超參確定沒有良好的解決辦法，由于隨機森林對超參調節方便［2～3］，計算快，因此本文將學習并研究隨機森林對交通流的預測。隨機森林是以決策樹為基分類器，在決策樹訓練過程中引入隨機屬性選擇，傳統的選擇決策節點都是采用單一的分裂算法，存在適用性差等問題，針對此問題提出在MapReduce編程模式下組合多節點分裂的MR_ONRF 算法，得到最優的分裂節點，進而實現交通預測。

2 基于MapReduce的并行隨機森林

2.1 MapReduce工作原理

MapReduce 是一種快速高效處理海量數據的并行計算模式。具有易于編程，屏蔽底層實現的細節；良好的擴展性；高容錯性等特點。MapReduce包含映射和化簡兩部分［4］，其工作原理首先將數據集D 進行分割，分割成一定大小的數據集塊｛＜k1，v1＞，＜k2，v2＞，…，＜kn，vn＞｝，然后把分割的數據交給多個Mapper 函數進行處理，Mapper 函數處理后將得到一組規模更小的數據，多個小規模的Mapper 結果數據再提交給Reducer 函數進行處理，相同鍵的鍵值對映射到同一個reduce 結點進行計算處理得到最終需要的結果或者是更為小的數據塊。MapReduce編程模型如圖1所示。

圖1 MapReduce編程模型

2.2 隨機森林

隨機森林（Random Forest，RF）是一種有監督學習算法，是一個由一系列決策樹形式的基礎分類器以隨機方式構建的組合分類器［5～7］。基本思想是先將大量的分類回歸樹組合成森林，然后對測試的樣本進行投票表決，結果由森林的所有決策樹根據多數占優的原則投票得出。

隨機森林的一大優勢在于它既可用于分類，也可用于回歸問題，這兩類問題恰好構成了當前的大多數機器學習系統所需要面對的。本文研究隨機森林的回歸算法，步驟如下：對于數據集D［N，M］，通過bagging 生成k 個自助抽樣集｛D1，D2，…，DK｝；在每個Di上創建一個決策樹，在M個特征變量中隨機選擇m 個特征變量（m<

2.3 MR_RF

MR_RF［8～11］（MapReduce Random Forest）是 隨機森林為了適應大數據處理，將隨機森林改編成符合MapReduce 計算模式的并行隨機森林算法。在海量歷史交通流數據下利用MapReduce 并行計算模式，使得隨機森林算法能夠可以多部分并行進行，從而縮短了隨機森林決策樹的決策時間，其核心部分在于map 和reduce 兩個部分。基于MapReduce的隨機森林算法流程圖如圖2所示。

圖2 MR_RF算法流程

算法如下：

Step1 從HDFS 上讀取交通流歷史樣本數據，MapReduce 框架將數據進行分塊，每一塊中的數據都是鍵值對＜key，value＞的形式，對應的交給一個mapper函數進行處理；

Step2 針對第一步的數據塊，進行map 任務操作，構建決策樹，選擇最優的分裂節點進行分裂；

Step3 所有的map 任務執行結束完成之后，執行Reduce函數，將最終的結果寫到HDFS上。

3 MR_ONRF算法

MR_ONRF（MapReduce Optimal Node Random Forest）算法是在原始MR_RF 的基礎上，改進了決策樹分裂節點的選擇算法，從而使得決策樹最近的分裂效果大大增強［12～16］。

1984年，Breiman和Store等提出CART算法，該算法與ID3 和C4.5 算法的不同在于它采用了計算Gini系數最小的屬性來作為分裂節點，該指標的計算公式如下：

其中

1986 年，Quinlan 提出了ID3 算法，該算法是通過對比屬性之間的信息熵的大小，最終決定選擇哪個屬性作為分裂節點，該指標的計算公式如下：

其中：

1993 年，Quinlan 在改進ID3 算法的基礎上提出了C4.5算法，該算法針對于ID3用信息增益選擇屬性時會出現多值偏向問題，引入信息增益率來作為選擇分裂節點的評判標準。

其中：

大量的實驗數據表明，隨機森林決策樹在創建過程中最重要的部分就是分裂節點的選擇。不同的節點分裂算法，會選擇不同的屬性進而會得到不同的決策樹［10］，最終也會影響隨機森林的精確程度。由于單一的分裂算法在使用范圍容易受到限制，因此本文提出在生成決策樹時，選擇線性組合多個分裂算法，形成新的分裂規則，找到最優的屬性進行節點分裂。決策樹節點分裂算法有很多，最常見的就是CLS、ID3、C4.5、CART，如表1 是對后三者節點分裂算的對比，由于CLS是隨機選擇分裂節點，存在一定的盲目性，因此我們考慮ID3、C4.5、CART三者進行線性組合，如式（7）。

表1 分裂節點算法對比

其中：0≤α，β，γ≤1；α+β+γ=1；Gini(D,m)、Gain(D,m)GainRatio(D,m)為 式（1）、（3）、（5）。當Gini 指數最小、信息熵和信息增益率最大時，此時H(m)取得最小，得到的分裂節點為最優分裂節點。MR_ONRF算法流程圖如圖3所示。

算法如下：

Step1 從HDFS 上讀取交通流歷史樣本數據，MapReduce 框架將數據進行分塊，每一塊中的數據都是鍵值對＜key，value＞的形式，對應的交給一個mapper函數進行處理；

Step2 針對第一步的數據塊，進行map 任務操作，根據MR_ONRF 算法比較各屬性的H(m)值，找到H(m)值最小的屬性作為本次分裂的分裂節點，創建節點；

Step3 根據決策樹創建結束條件比對，如果符合結束條件，就生成葉子節點，結束本次分裂，否則轉為step2繼續進行節點的分裂，直達完成分裂；

Step4 所有的map任務執行結束完成之后，執行Reduce函數，將最終的結果寫到HDFS上。

4 實驗結果與分析

4.1 環境配置

本文采用的是開源Hadoop 分布式框架搭建MapReduce 仿真實驗室平臺，平臺為6 臺集群結點組成，其中一臺為NameNode 節點，其他五臺為DateNode 節點，100M 以太網，所有的主機相同配置。其中硬件環境：處理器Intel Core i5-2450，內存4G，硬盤500G；軟件環境：Windows10、jdk1.7、Hadoop版本：Hadoop 2.0.0 CDH 4.5。

為了驗證結果，本文在仿真的過程中將數據在單機環境和Hadoop 集群環境中分別進行性能測試，其中單機環境下的軟硬件環境和Hadoop 集群中的環境是相同的。

4.2 實驗數據集

本文的數據來自實際檢測的交通流數據，是深圳三條快速路的交通流數據（3 個月每天24h 的數據），采樣周期是30s，每條數據包含速度、流量、占有率以及交通流狀態，其中交通流狀態有暢通、緩行、擁堵。由于交通流數據存在周期性，因此在此數據中還加入了星期作為特征量。

為了提高預測精度，利用歷史趨勢法和相鄰補齊法修復原始交通流數據中的丟失數據和錯誤數據，然后對冗余數據進行約簡，數據原采樣周期是30s，簡約后的數據周期為3min，對此進行加權平均得到實驗數據。交通流格式如表2。

表2 交通流格式

4.3 實驗結果分析

本文對傳統的隨機森林、MR_RF 和MR_ONRF三者的預測速度、預測準確率進行了對比實驗，根據4.2 節處理后的交通流數據，對于不同的數據規模的數據進行實驗，來驗證文中提出的MR_ONRF在預測速度和準確率的優化效果。

圖4 表明MR_ONRF 和MR_RF 比傳統的隨機森林在處理交通流預測速度上有明顯的增加，這說明引入的MapReduce 編程模式能夠很好地處理海量數據集。其中MR_ONRF 算法比MR_RF 算法的耗時上又有所降低，并且能夠看出，當數據集規模擴大時這樣的效果更為明顯。

圖4 傳統RF、MR_RF和MR_ONRF三者耗時比

圖5 傳統RF、MR_RF和MR_ONRF預測準確率對比

圖5 表明MR_ONRF在交通流預測準確率上遠遠超過了MR_RF 和傳統的隨機森林，這說明本文提出的MR_ONRF 算法能夠很好地進行交通流預測。從實驗的數據線中可以看出，文中的算法更加穩定，更適用與交通流預測應用中。

5 結語

高效準確的短時交通流預測是優化智能交通系統的重點部分，從實際應用的基礎上，將MapReduce編程模式應用于海量交通流數據處理，能夠快速進行數據的處理，由于隨機森林計算效率高，對參數的調整要求低，所以將隨機森林模型應用在交通流預測中能夠獲得更為準確高效的預測結果。在決策樹構建的過程中，單一的決策樹分裂節點算法會引起分裂適應性差等問題，本文提出的組合多節點分裂MR_ONRF 算法大大地提高決策節點優化選擇，實驗結果表明該方法提升了最終的預測速度，提高最終的預測準確率。接下來的工作：1）運用Hadoop集群中采用不同數量的DataNode機器進行實驗分析，來驗證本文MR_ONRF 算法的伸縮性能，2）考慮到隨機森林在構建樹的過程中，森林中樹的個數選擇對森林的預測也會有影響，如何確定最佳樹個數也是未來學習研究重點。