并行繪制系統中基于隨機森林的預測算法改進

郭賽賽，李君怡

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

0 引言

隨著計算機硬件及軟件技術的不斷發展，計算機圖形學與虛擬現實的應用場景越來越多，特別是在科學、工程、醫學、生物學、娛樂業等領域得到了廣泛應用。一些應用領域如科學、VR游戲等，為了得到最佳的效果，通常會使用超分辨率的巨大屏幕或者較高的刷新頻率，增加真實性、提升用戶體驗。其中需要的圖形計算能力、輸出幀率對單一繪制系統提出了嚴峻挑戰。為了解決這個問題，并行繪制技術被提出，通過將一個大任務分解成多個子任務同時處理極大地提高了繪制效率。由于目前大部分的實時繪制算法如De?ferred Shading、Ray Tracing都是基于屏幕空間，因此本文采用基于屏幕空間的負載劃分來適應大多數繪制算法。本文用繪制時間來代表負載，目的是使得幾個子屏的繪制時間相當，以達到較好的負載平衡。如果在每一幀繪制任務被劃分后可以給出一個相對準確的負載預測結果，系統就可以根據這個結果去調整劃分方式，從而使得不同繪制區域的負載達到均衡，提高繪制速度。

本文將這個預測過程用機器學習的思想來實現，通過機器學習模型學習已有的數據，在新的一幀畫面到來的時候，將畫面轉換為訓練模型用到的數據格式，用模型做出預測，并根據這個預測結果去調整劃分方式。為了提高預測效率、并較好處理復雜繪制場景中的高維數據，本文選取Breiman[1]提出的隨機森林作為預測模型。

隨機森林中每棵決策樹[2]給出的預測結果由測試樣本所落入的葉子節點中的數據的平均值決定，這些數據的熵越小，純度越高，預測越準確。為了將訓練集劃分得足夠純，本文在構建隨機森林的時候，采用最小化殘差平方和（Residual Sum of Squares，RSS）[3]來確定每次節點劃分所用的特征與位置。但由于隨機森林中用來預測的一組葉子節點中的數據并不完全相同，因此，每棵樹給出的預測結果準確度也不同，而原始的隨機森林均值預測法并未考慮這個差異，從而使得最終的預測結果有一定偏差。

為了解決數據差異帶來的預測偏差，通常的解決方案是為每個預測用葉子節點加置信度，作為最終的預測權重。置信度的計算方式有很多，針對RSS劃分決策方法，每個葉子節點置信度通常用其所包含的數據方差來計算，即，方差越大，置信度越低。加入置信度后的隨機森林的預測能力會有一定程度的提升，但面對一些其他問題，如劃分得到的實際葉子節點空間較大使得落入的測試樣本與其中包含的訓練數據差異較大時，即使該節點中的數據方差很小，依然很難給出一個相對準確的預測結果。為了解決這個問題，本文提出根據擬合度判定函數來用路徑上的節點代替部分葉子節點做預測的方法。

1 算法實現

1.1 算法思想

隨機森林通過自助法（bootstrap）重采樣技術[4]，從大小為N的原始訓練樣本集中有放回地重復隨機抽取N個樣本生成新的訓練樣本集合，構成一棵決策樹，將該過程重復M次，得到由M棵決策樹組成的隨機森林。在解決分類問題時，一個測試樣本最終得到的預測結果是根據所有決策樹給出的投票結果決定的。而對于回歸問題，隨機森林給出的預測結果是每個決策樹給出結果的平均值。本文目的是對負載時間做預測，因此屬于回歸問題。

用路徑上的節點而非葉子節點做預測依然是以隨機森林為基礎。每棵決策樹是通過不斷選定一個特征的一個位置向下劃分，最終會將決策樹的整個數據空間劃分成一個個獨立的小的子空間，一個葉子節點代表了一個子空間。決策樹在向下劃分過程中，通常需要為它設定合適的停止劃分條件，避免最終將每個訓練數據單獨劃分到一個葉子節點得到過擬合[5]的決策樹。本文在選取劃分停止條件時主要考慮兩個問題：節點中數據量與節點中數據純度。數據量太多預測準確性較低，太少容易過擬合，最終根據實驗結果確定了一個最大數據量，當節點中數據量小于這個值就停止劃分。劃分的目的是使決策樹節點中的數據越來越純，因此，如果這些數據的值已經全部一樣，也就是純度已經達到最高后也會停止劃分。這兩個停止條件可能會帶來的兩個問題分別是：葉子節點中較少不同數據代替整個節點空間做預測；用相同的數據代替整個節點空間做預測。這兩個問題本質上與過擬合很相似，都是訓練數據不足以準確表達出其所代表的整個空間的特征。而隨機森林在構建過程中通常不考慮過擬合問題，因此，面對這兩個問題帶來的預測誤差，隨機森林的均值預測法往往不能給出有效調整。

用路徑上的節點代替葉子節點預測從根本上講，就是通過增加預測用的數據量來解決過擬合的問題，這一過程可以看做是對隨機森林做了“假”剪枝[6]。之所以是假的，是因為實際上并沒有剪枝。測試樣本從某棵決策樹根節點一直向下走的過程中，本文會在每個節點通過一個布爾函數來判斷這個葉子節點中的數據相對測試樣本來說是否過擬合，如果結果為真，就不再繼續往下，用停止位置的節點去預測，等于在該位置剪枝；否則，就繼續向下直到到達葉子節點，等于未做剪枝。也就是說，對于走同一條預測路徑的兩條測試樣本，可能有一條走到在路徑中間就停止，而另一條會走到路徑終點，也就是葉子節點，因此是“假”剪枝。

1.2 算法實現

原始隨機森林在預測的時候，每條測試樣本從進入一棵決策樹根節點開始，就要根據當前節點的劃分方式不斷的去判斷下一步是去左子節點還是右子節點，直到到達葉子節點。而將路徑上的節點加入最后的預測時，這個過程也會有一些變化，具體算法流程如下：

（1）根據完整訓練數據集D（d1，d2，…，dN）構建隨機森林預測模型F（f1，f2，…，fM）；

（2）依次將測試數據集T中的每條樣本t放入模型F（t初始是落入F中每棵決策樹的根節點）；

（3）判斷當前節點是否為葉子節點，如果否，執行步驟（4），否則，執行步驟（5）；

（4）判斷當前節點是否存在過擬合風險，如果否，判斷t下一步落入的節點，回到步驟（3），否則，執行步驟（5）；

（5）停止繼續向下尋找節點，用當前節點作為對應決策樹最終的預測節點；

（6）用每棵樹最終給出的預測節點做負載預測。

1.3 細節描述

在本文提出的算法中，關鍵點在于如何判斷一個節點中用來預測的數據相對于測試樣本來說過擬合。這里面包含了兩個點：用什么來表示擬合性；過擬合的標準怎么定。

通過對預測結果好壞不同的測試樣本研究發現，它們預測結果的差異大小與用來預測它們的節點中的數據分布有很大關系。因而本文最終采用根據測試樣本各維特征是否超出節點中數據特征范圍來判斷擬合性。擬合標準由實驗結果確定。

這里以二維數據集為例做簡單分析。如圖1對于某個非葉子節點A，通過選定一個特征α的位置β，將A劃分成了左右兩個子葉子節點B、C。節點A劃分前后的數據分布可能會出現圖1中左右兩種情況，這時如果一個測試樣本P最終落入了兩種情況下的同一個位置。可以發現，圖2左中P是落入一堆數據中間，而圖2右中P雖然落入葉子節點B中，但實際上與B中的數據有一定距離，甚至P離C中的數據反而更近。這個時候，同樣都用B中的數據去預測P，兩種情況給出的結果準確度肯定會有差異，而且可以猜測，圖2左給出的結果應該更加準確。如果出現圖2右的情況，用C節點做預測應該會優于用B節點，但隨機森林的特性就是根據劃分結果找到它以為最合理的預測節點，就是這里的B，因此將定位到的預測節點改為它的兄弟節點就與這個特性相沖突。這種情況如果出現在單棵決策樹的機器學習模型上，它會認為當前模型過擬合，通常的解決方案就是剪枝，這里就是永久性的去除B、C節點，用A做預測。結合單棵決策樹的剪枝策略，本文提出用路徑上非葉子節點代替葉子節點做預測的方案。如果擬合度判定函數結果顯示，A以后的節點相對測試樣本來說過擬合，將停止在A節點，用A節點做預測。這里不做真正意義上的剪枝還有一個好處，若與B節點中數據相似的測試樣本進入模型后，最終仍能到達B節點，而不是只能停在A。

圖1

圖2

根據數據分布特征，本文將擬合度判定函數f設定為與測試樣本x超出所到節點中全部數據各維特征范圍的數量K有關，當f（x）≥K時，即認為從當前節點開始，節點中的數據分布相對測試樣本來說差異較大，因此，不適合用更底層的節點預測。

本文這種考慮路徑上節點做預測的“假”剪枝方法在保持原有預測結果較好的樣本準確度變化不大的同時，增加了對預測結果不好的樣本的預測能力，最終提升了整體預測準確度。

2 實驗結果

2.1 實驗環境

PC配置：Intel Core i7-8700K 3.70GHz CPU，16G內存，NVIDIA GeForce GTX 1080顯卡；

繪制系統：加入Light Linked List（LLL）算法[7]產生大規模動態光源光照效果、Screen Space Ambient Occlu?sion（SSAO）算法[8]優化繪制效果、Order Independent Transparency（OIT）算法[9]繪制場景透明物體；

實驗數據：從繪制場景中多條漫游路徑采集1，195，906條數據構成訓練集，19，626條數據構成測試集。

2.2 實驗結果

模型參數設置：

表1

數據集參數列表：

表2

已知數據特征共16維，因此，擬合度判定函數中允許樣本超出維度數K的范圍應在1～16之間。

本文采用均方誤差（Mean-Square Error，MSE）[10]、R2Score（Coefficient of Determination）[11]兩種回歸算法最常用的性能度量方法來反映預測準確度。MSE越小說明預測越準確，R2Score越接近1說明預測結果越接近真實值。

為了驗證本文算法的正確性并找到合適的K取值，實驗一通過設置不同的K值，計算對應的MSE與R2Score值并與原始RF預測結果做對比。實驗二、三分別對原始RF預測結果最好、最差的前10000條測試樣本集Db、Dw進行測試，來驗證該方法對預測理想的數據的預測能力保留，對預測不理想數據的包容。

總而言之,脛骨平臺合并半月板損傷患者接受早期的脛骨平臺骨折手術修復治療,對損傷半月板進行修復,能夠在一期就實現愈合,避免了骨折預后創傷性關節炎的發生,臨床中效果比較突出,值得推廣使用。

實驗一：驗證K取值對原始測試集預測結果的影響

已知K值的大小決定了最終用來預測的節點位置，為了得到相對較好的結果，本文通過實驗驗證了不同K值下預測結果的變化。圖3中橫軸代表不同K的取值，實線與虛線分別代表了對應K取值下的MSE與R2Score值。已知在原始均值預測方法下，該測試集的MSE為0.571698，R2Score為0.795982。由實驗結果可知，當K取1～15之間的值時，改進后的算法預測能力都有所提升，而K的最佳取值為3。

圖3

實驗二：模型改進前后對數據集Db的預測結果對比

根據實驗結果，原始RF對最好的前10000條數據集Db的預測結果為MSE等于0.038829，R2Score等于0.982161，而將K設置為3時，MSE等于0.0546641，R2Score等于0.974886，并且進一步驗證了將K設置為1～16間的任何數后的預測結果都不優于原始RF，這說明對于已經學習到的數據來說，葉子節點可以給出更好的預測結果，也證明“假”剪枝中“假”的必要性。

實驗三：模型改進前后對數據集Dw的預測預測對比

原始RF對最差的前10000條數據集Dw的預測結果為MSE等于1.08791，R2Score為0.671973，K=3時，MSE等于0.907903，R2Score等于0.726248，預測能力有一定提升。而通過將K設定為1～16之間不同的值，發現K取1時，預測結果提升最大，這說明對于沒有很好學習到的數據，可能葉節點包含的數據及鄰近的數據與測試樣本的偏差更大，證明了“剪枝”的重要性。

3 結語

本文提出基于原始隨機森林用測試樣本預測路徑上的節點代替葉子節點做預測的算法，在保持用原始隨機森林預測較好的樣本預測結果變化不大的同時，增加了對預測不好的樣本的預測能力，并對該算法進行了實驗驗證，從結果可以看出該算法對模型預測能力整體有一定提升。