應用于并行繪制系統負載均衡的改進隨機森林算法

李君怡，郭賽賽

（四川大學計算機學院，成都610065）

0 引言

近年來，隨著圖形軟硬件的發展和互聯網的廣泛應用，實時交互娛樂系統伴隨著日益強烈的需求得到了快速的發展。人們追求更真實更流暢的交互體驗，這對圖形繪制技術在輸出分辨率和輸出幀率等方面提出了更高的要求。單GPU 難以滿足如此巨大的計算需求，并行繪制[1]作為解決這個問題的有效途徑，通過將大型繪制應用場景中的繪制任務劃分成若干繪制子任務，合理地分配給多個繪制節點，當所有節點繪制完成后，將其繪制結果進行拼接形成最終繪制結果，以此達到提高整體繪制效率的目的。

本文采用的基于sort-first 的并行繪制系統，由一個控制節點，若干繪制節點以及顯示節點組成?？刂乒濣c將屏幕劃分為若干個子屏，每個子屏對應一個繪制節點負責執行子屏的繪制任務，各個子屏繪制結束后，由控制節點完成子屏畫面拼接工作，最終將完整的畫面輸出顯示。在這個過程中，控制節點如何將繪制任務均衡地分配給各個繪制節點，以此減少用于同步各繪制節點的繪制結果花費的額外等待時間，成為了關鍵點。如果每個繪制節點在開始繪制一幀畫面之前，獲取到繪制負載均衡時的屏幕劃分，就能實時地調度繪制節點以負載均衡的狀態執行繪制任務，避免負載失衡所帶來的額外時間花銷。借助機器學習中的隨機森林模型來預測各個子屏的繪制時間[2]，控制節點再根據預測結果不斷調整屏幕劃分，直至各子屏繪制時間相當，就能實現負載均衡。在并行繪制系統達到負載均衡的過程中，隨機森林的預測準確度越高，繪制節點所需調整次數越少，就能在更短的時間內達到負載均衡狀態。因此，可以通過改進隨機森林提升模型預測準確度，來提高并行繪制系統的幀率。

1 相關研究

原始隨機森林在處理分類任務時，各個決策樹對預測樣本的類別進行投票，最終選擇投票最多的類作為最終預測結果；而回歸任務則通過對所有決策樹的預測值求均值，作為最終預測結果。這兩種方法簡單且易于實現，但并不區分決策樹預測性能的優劣，所有決策樹對最終結果的貢獻度一樣，這顯然不合理。在提升隨機森林預測準確性的研究中，研究者提出了不同的加權隨機森林算法。Hongbo Li 等人提出的TWRT（Trees Weighting Random Forest）[3]，利用每棵決策樹各自的OOB（Out Of Bag）[4]數據作集為驗證集，以OOB 數據預測正確率為決策樹賦權重。在預測階段，所有決策樹加權投票，選擇投票最高的類作為預測類。Xiang Gao 等人利用OOB 數據測試決策樹[5]，根據決策樹的測試結果中真陽性率（True Positive Rate，TPR）與陽性預測值（Positive Predict Value，PPV），為決策樹賦予權重，并將其應用員工離職預測，獲得了比原始RF 更高的預測性能。Pham 等人則將Cesaro 平均法應用于隨機森林預測[6]，使用測試數據對決策樹的預測性能進行排序后，提出了一種只與決策樹排列序號有關的權重來提高預測準確性。Shiyang Xuan 提出的RWRT[7]根據所有測試數據在決策樹上累計的正確率和錯誤率之間的概率差來計算決策樹權重，這在預測不平衡以及非高維特征數據時，具有較好的預測性能。

眾多加權隨機森林的算法中，都著重為決策樹賦予權重，權重都是固定的，且都針對分類問題，這些方法并不適用于并行系統的負載預測。因此，本文提出一種改進隨機森林，為每個葉子節點設置一個動態更新的置信度，使得預測性能好的葉子節點不斷積累更高的權重，對最終的預測結果產生更大的影響，同時不斷弱化預測性能差的葉子節點，由此來提高隨機森林預測準確性。

2 算法實現

2.1 問題分析

為決策樹賦予權重能在一定程度上提升隨機森林的預測準確度，但對于一棵決策樹來說，實際每次預測都是由待預測樣本落入的葉子節點給出具體預測值。而為樹賦予權重，就是將該樹的所有葉子節點的權重設置為相同的值，并不對各葉子節點的預測性能優劣做區分?，F實情況中，葉子節點的預測性能優劣，與該葉子中所包含訓練樣本的純度或方差，以及其分布有關。一方面，決策樹的構造過程中使用到的屬性劃分函數，如基尼指數[8]、信息增益，決定了決策樹是朝著節點純度更高的葉子節點方向生長的，因此葉子節點純度越高，則其決策更具有確定性；另一方面，若待預測的數據落入到一個葉子節點后，與該節點中的訓練樣本“距離”較遠，則不能得到較好的預測結果。根據分析，同一棵決策樹葉子節點之間也存在預測性能差異，因此，不能以決策樹的權重來表示所有葉子節點的權重，應從決策樹級別上，為每個葉子節點賦予與其預測性能相關的權重。

2.2 改進隨機森林算法概述

結合并行繪制的應用背景，本文提出了葉子節點權重更新算法。葉子節點權重更新是指對于已構建完成的隨機森林，在預測前為決策樹每個葉子節點設定一個初始權重。在預測階段，對于第一次用于預測的葉子節點，其權重即為初始權重；隨著待預測的樣本逐一落入決策樹的葉子節點中，對于多次落入樣本的葉子節點，其權重是根據已落入的樣本的預測準確率來計算的。每個樣本的最終預測結果，由落入的所有葉子節點加權得出。如圖1 所示，在一個包含了m 棵決策樹的隨機森林T 中，假設決策樹t1 的初始葉子節點權重為wt1。當第一個待預測樣本sample 根據決策樹t1 的劃分規則落入葉子節點leaft1，將葉子節點leaft1的權重wt1以及其所代表的決策值vleaf1_t1代入公式（1）計算最終預測值：

獲取樣本預測值以及真實值后，計算預測準確度，結合預測準確度來更新leaft1的權重，更新后的新權重wt1*將作為下一個落入leaft1的待測試樣本在leaft1上的權重。決策樹每個被用于預測的葉子節點，按照這種動態權重計算方式不斷更新權重。

圖1 葉子節點權重“預測+更新”過程

一般為決策樹賦予權重的算法都采用靜態權重，權重一旦確定后，在預測階段就不能更改。當預測數據與訓練數據分布不同時，往往得不到好的預測結果。而這種動態的葉子節點權重更新方法，借助于并行繪制系統在繪制完一幀畫面后，能立即獲得該幀的實際繪制時間，來計算預測準確率，反映葉子節點對當前數據的預測性能。隨著待預測樣本數量的增加，該葉子節點通過這種“預測+更新”的方式不斷累積歷史預測準確來更新自身權重，獲得更真實的預測可信度。

2.3 權重更新方法

葉子節點權重更新過程中，關鍵是如何根據預測準確度調整權重。假設存在一個預測準確度閾值σ，當樣本預測準確度高于σ，則認為樣本所落入的葉子節點預測準確率相對較好，應適當提升其權重；當樣本預測準確度低于σ，則適當降低葉子節點的權重。通過與預測準確度閾值對比，來判斷預測性能的優劣，從而調整葉子節點的權重。為了能客觀地反映葉子節點的預測性能優劣，本文選擇將歷史樣本預測準確度平均值作為閾值σ。對于第n 個待預測樣本xn，在獲取了xn的預測值以及真實值后，按照公式（2）來計算隨機森林對xn的預測準確度，并按照公式（3）來計算預測當前準確度閾值σn：

其中，wcurrent表示葉子節點leaft更新前的權重，也是本次預測所使用的權重，當葉子節點leaft第一次落入樣本被用于預測時，初始權重設置為1。Accuracyleaf_t表示葉子節點leaft對樣本xn的預測準確度，Accuracyleaf_t與sigmoid 函數分別表示為公式（5）與公式（6）：

公式（6）中，k 作為sigmoid 函數的平滑參數，為一個固定值。本次更新的葉子節點leaft的權重wupdate將作為下一個落入leaft的樣本的預測權重。

3 實驗結果與分析

本文研究的目的在于提升隨機森林對繪制幀負載的預測準確率。因此，實驗部分將計算原始隨機森林與改進隨機森林對相同繪制幀的負載預測結果的MSE（Mean Squared Error）[9]與R2Score（Coefficient of Determination）[10]，來對比兩種方法的預測效果。MSE 用于反映預測值與真值之間差異程度，MSE 值越低，代表模型的預測準確性越高；R2Score 用于反映線性或非線性擬合程度好壞，其值介于0 到1 之間，越接近1 表示模型擬合程度越高。表1 表示了原始RF 與改進RF 預測性能對比情況：

表1 原始RF 與改進RF 預測性能對比

從表1 可以看出，改進RF 相對于原始RF，R2Score 更接近1，MSE 值也越低，說明改進后的隨機森林在對真值的擬合程度更好，預測值與真值之間的差異也更小。

4 結語

本文為了提升隨機森林對并行繪制系統中各個子屏負載的預測準確度，提出了一種改進隨機森林算法。利用并行繪制系統能在繪制過程中及時反饋每一幀的真實繪制時間，實時計算隨機森林預測準確度，來為決策樹的葉子節點賦予與其真實預測性能相符的權重，以此提升了模型的預測準確度，并通過實驗證明了改進隨機森林的有效性。