郭賽賽，李君怡

（四川大學(xué)計算機學(xué)院，成都610065）

0 引言

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

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

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

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

1 算法實現(xiàn)

1.1 算法思想

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

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

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

1.2 算法實現(xiàn)

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

（1）根據(jù)完整訓(xùn)練數(shù)據(jù)集D（d1，d2，…，dN）構(gòu)建隨機森林預(yù)測模型F（f1，f2，…，fM）；

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

（3）判斷當(dāng)前節(jié)點是否為葉子節(jié)點，如果否，執(zhí)行步驟（4），否則，執(zhí)行步驟（5）；

（4）判斷當(dāng)前節(jié)點是否存在過擬合風(fēng)險，如果否，判斷t下一步落入的節(jié)點，回到步驟（3），否則，執(zhí)行步驟（5）；

（5）停止繼續(xù)向下尋找節(jié)點，用當(dāng)前節(jié)點作為對應(yīng)決策樹最終的預(yù)測節(jié)點；

（6）用每棵樹最終給出的預(yù)測節(jié)點做負載預(yù)測。

1.3 細節(jié)描述

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

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

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

圖1

圖2

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

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

2 實驗結(jié)果

2.1 實驗環(huán)境

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

繪制系統(tǒng)：加入Light Linked List（LLL）算法[7]產(chǎn)生大規(guī)模動態(tài)光源光照效果、Screen Space Ambient Occlu?sion（SSAO）算法[8]優(yōu)化繪制效果、Order Independent Transparency（OIT）算法[9]繪制場景透明物體；

實驗數(shù)據(jù)：從繪制場景中多條漫游路徑采集1，195，906條數(shù)據(jù)構(gòu)成訓(xùn)練集，19，626條數(shù)據(jù)構(gòu)成測試集。

2.2 實驗結(jié)果

模型參數(shù)設(shè)置：

表1

數(shù)據(jù)集參數(shù)列表：

表2

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

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

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

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

實驗一：驗證K取值對原始測試集預(yù)測結(jié)果的影響

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

圖3

實驗二：模型改進前后對數(shù)據(jù)集Db的預(yù)測結(jié)果對比

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

實驗三：模型改進前后對數(shù)據(jù)集Dw的預(yù)測預(yù)測對比

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

3 結(jié)語

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