隨機非參數學習算法，第 2 部分: 隨機決策樹的實現和效果

大多數機器學習算法的計算復雜度都是隨著數據量或者維度呈線性增長，這是大規模機器學習的一大挑戰。上一篇文章介紹了隨機決策樹算法的基本方法，並從理論層面粗略的探討了為什麼隨機決策樹具有學習能力。本篇文章我們將著重介紹隨機決策樹的算法實現，算法的復雜度和實驗結果中展示的精度和效率。

算法實現

隨機決策樹的基本方法上篇文章已經介紹了，這一方法並不復雜，沒有什麼高深的東西。但在實現過程中，還是有許多注意的問題。我們這裡僅討論一棵樹的構造算法，多棵樹僅是需要多次執行這一個算法。

原始算法

在隨機決策樹（參考資源 [1]）中的原始算法采用的是遞歸方式建立空樹，以設置的最大樹深為結束條件。然後以遞歸方式基於訓練數據統計每個節點上的類別的頻率，再去除掉沒有數據或者不滿足條件（訓練樣本數不足）的葉子節點。在空樹的構建過程中，非數值型的特征在一條路徑上只能出現一次，為所有可能的取值建立分支。而數值型的則可出現多次，每次都是建立兩個子分支，但是分裂點則只能在這個節點的可能取值范圍內隨機選。在統計階段，把所有訓練數據自樹的根開始向下逐步分配到葉子節點，中間統計每個節點的類別分布頻率。在統計過程中，對於缺失值要做特殊處理。即，首先要統計一個節點的各個子分支的出現頻率（非缺失值的頻率），然後將缺失值的樣本按照這個頻率隨機選擇一個分支分配。在預測的時候，如果遇到缺失值也是根據子分支的頻率隨機分配。

這個算法的實現並不算復雜，麻煩一點的地方在於缺失值的處理。但是在數據量較大，維度較多和樹深較深的時候，會有一些缺點。首先是建立空樹就需要考慮所有的可能性。在最簡單的情況下，即所有維度都是 2 值時，則需要建立的是滿二叉樹。如果樹深為 d, 則一棵樹的節點數為，這在樹深很大的時候樹的結構會急劇膨脹從而使得內存開銷無法承受。而一般的情況下，每個特征的可能取值是大於等於 2 的，則樹的結構膨脹速度會比二叉樹的情況更遭。其次，樹的構建過程和統計過程，都是采用的遞歸實現，這在樹結構很大，樹很深的時候容易導致棧溢出。特別是在用 Java 實現時，由於棧空間相對於堆空間是非常小的，這個問題很容易出現。再有一個缺點就是缺失值的處理問題，不僅程序上帶來一些麻煩，提高了計算開銷，更重要的是這種處理方式並不足夠科學，特別是在缺失比例很高的情況下。

Dice 實現

Dice[2] 項目是用 Java 語言開發的，支持二分類，多分類，多標簽分類和回歸。隨機決策樹的原始實現存在很多問題，為了克服這些問題我在 Dice 項目的實現中進行了一些優化：

首先是先建空樹，然後剪枝的方式改成在樹的生長過程中根據數據的情況決定是否分支。對於非數值型的特征來說，在某個節點檢查在這個節點上的數據有多少種取值，然後根據取值個數分支。舉個例子，學歷這個特征可以有本科，研究生，博士生三個可能取值，但是在某一個節點上的數據裡只有本科生和研究生兩種取值，則只會分兩支。對於數值型的特征，則會隨機選擇兩個不同的值進行平均作為分裂值，如果所有的特征都相同則不會選擇這個特征。

其次，對於缺失值的處理是將其當作一個新的特征值獨立分支。這樣就不需要統計每個節點上的特征取值的分布，簡化了算法實現。

最後，將遞歸算法改為非遞歸算法，樹是逐層生長的。在生長過程中，有數據結構記錄每個樣本落在了哪個節點上，避免樣本重復從樹根走起。非遞歸實現不依賴於棧。

Dice 實現除了克服以上三個主要問題，算法實現上還做了很多的細節優化。比如，為了盡可能的節省內存，數據的存儲盡可能使用 primitive 類型的數組，相比於 Weka 將每個樣本封裝成一個對象，節省了大量的空間。Dice 的實現克服了原始算法的一些缺點，使得算法的效率和處理的數據規模有較大提高。下一節在算法的計算復雜度分析中將基於 Dice 的實現。

計算復雜度分析

隨機決策樹算法的計算復雜度來自於兩部分。一是構建樹結構的計算復雜度，二是統計每個葉子節點上的樣本類別分布的計算復雜度。構建樹結構的計算復雜度與訓練樣本數和特征數有關。但是在最壞的情況下，即樹的生長達到了最大的深度限制時，其復雜度僅與樹的最大深度限制和訓練數據數量有關。這是因為在最壞的情況下，樹的最大深度達到最大限制，而樹還是滿樹，即所有訓練樣本都走到了最深的深度上。設樹的最大深度為 d，訓練樣本樹為 n，則在此種情況下，構造一棵樹僅需要分配樣本 dn 次。則構造樹的最大復雜度為O(dn)。而一般情況下，並不是每棵樹都會生成最大深度的滿樹，實際開銷是還會要小不少。至於葉子節點統計時的開銷是極小的，這裡不做考慮。其他的決策樹算法分析裡也不考慮這部分開銷。基於以上分析，可以認為在訓練數據總數為 n，最大樹深為 d，樹棵樹為 m 時，隨機決策樹算法的訓練開銷為O(mdn)。一般的情況下，m<<n，d<<n。可以看到，算法的訓練復雜度在 m 和 d 給定的情況下僅與訓練樣本數 n 線性相關。

而傳統的 TDIDT 決策樹（Top-Down Induction of Decision Trees，包括 ID3 和 C4.5 算法）其訓練復雜度為, 其中, 而是第個特征的取值個數。顯然，該類算法的算法復雜度與特征個數是超線性關系。在一般情況下，所以隨機決策樹算法的計算復雜度是遠小於這類算法的。

精度和效率

前面簡單介紹了隨機決策樹算法的實現和訓練復雜度，這一節將簡要介紹下其精度和訓練效率，並與其他經典算法進行比較。

一個簡單例子

該例子引自范偉博士的網站：有一二維的人造正負樣本分布，如圖 1 所示。其中紅色為正樣本，綠色為負樣本。顯然這個問題不是線性可分的，

圖 1. 二維人造正負樣本分布

下面圖 2—圖 5 分別給出隨機決策樹算法、決策樹，線性 SVM 和 RBF 核的 SVM 算法的訓練結果。

圖 2. 隨機決策樹（訓練時間 5 秒）

圖 3. 決策樹 (訓練時間 1 秒)

圖 4. 線性 SVM(訓練時間半天)

圖 5. RBF SVM(訓練時間 1 天)

顯然，隨機決策樹對原分布的估計是較好的，與 RBF SVM 的效果在同一水平上。而決策樹算法則帶來了明顯的鋸齒型邊界，而線性 SVM 則無法將右上方的正樣本正確劃分。從訓練時間看，SVM 開銷非常大（可能未使用 SMO 方法），樹的算法都很快。但是隨機決策樹算法的訓練開銷比決策樹要高 5 倍，與我們前面的分析相反。這有兩個原因，一是對於低維度問題，隨機決策樹算法的效率與決策樹相比並沒有明顯優勢。因為決策樹算法的時間復雜度與特征數量的關系是超線性的，在特征較少時，其復雜度並不會太高，而隨著特征的增長，計算復雜度會快速增長。二是這個實驗是使用的隨機決策樹的原始實現，其效率並不是太高。

Dice 測試結果

我們從 Libsvm 選取了 9 個二分類數據集，這些數據集的統計信息列在表 1 中。

表 1. 從 Libsvm 選取的 9 個二分類數據集的統計信息

  Name Feature Type Feature Number Train Data Number Test Data Number Train Data Size Test Data Size a1a Binary 123 1,605 30,956 0.11M 2.11M a9a Binary 123 32,561 16,281 2.22M 3.33M mushrooms Binary 112 7,124 1,000 0.753M 0.105M w1a Binary 300 2,477 47,272 0.166M 3.15M w8a Binary 300 49,749 14,951 3.31M 1.00M splice Categorical 60 1,000 2,175 0.7M 1.48M cod-rna Numeric 8 59,535 271,617 4.45M 20.3M covtype Numeric 54 481,082 100,000 56.2M 11.6M gisette Numeric 5,000 6,000 1,000 50.4M 8.52M

對於以上數據集，我們使用 30 棵樹的隨機決策樹（其葉子節點最少保留 4 個訓練樣本，最大深度為特征數）進行實驗。並使用 Weka 測試 J48(C4.5 決策樹)，SMO(SMO 算法實現的 SVM) 和 Logistic Regression 算法。Weka 測試的算法的參數使用默認參數。所有的實驗結果列在表 2，其中訓練時間的單位為秒。 表 1. Weka 測試結果

表 2. Weka 測試結果

  Data RDT J48 SMO LR   AUC Tr.Time AUC Tr.Time AUC Tr.Time AUC Tr.Time a1a 0.879 0.569 0.712 1.861 0.760 1.574 0.751 1.010 a9a 0.890 24.171 0.755 647.013 0.761 1637.011 0.763 35.901 mushrooms 1.000 3.608 1.000 13.651 1.000 1.665 1.000 3.993 w1a 0.953 0.934 0.613 23.022 0.748 0.759 0.732 6.561 w8a 0.997 33.759 - - 0.797 487.39 0.822 371.836 splice 0.909 0.387 0.935 0.770 0.843 1.742 0.853 0.819 cod-rna 0.969 7.799 0.944 155.763 0.944 62.705 0.937 4.271 covtype 0.768 24.392 - - - - 0.705 299.667 gisette 0.934 82.513 - - - - -  

從上表中我們可以看到，隨機決策樹的精度總體上超過其他 3 個經典算法。雖然其他三個算法使用的是默認參數，但是隨機決策樹使用的也是默認參數，並未對不同數據集進行調參，因此比較也是基本公平的。而速度上可以看到隨機決策樹算法也是具有很大的優勢。注意到表中有一些空缺項，那是在 1 個小時內跑不出結果從而終止的實驗。可以看到 RDT 可以在所有數據集上跑出結果，而其他的算法則在稍大的數據集上有可能跑不出結果（Weka 的實現不夠高效可能也是原因之一）。

算法並行化討論

Dice 的實現是比較高效的，我曾經用在過騰訊廣點通的 CTR 估計上訓練上千萬樣本的問題，僅需要 10 分鐘就能完成訓練。但是畢竟這是個單機實現，處理問題的規模總有上限。為了處理更大規模的問題，我們需要考慮隨機決策樹算法的並行化問題（僅考慮在 Hadoop 和 Spark 上的並行）。但是，隨機決策樹算法的並行化卻有比較大的困難。Dice 對原始實現的優化中，很重要的一條就是將先建空樹改成逐層建樹，從而減少了內存的消耗。但是這會要求要多次使用訓練數據，即多次迭代訓練數據，在單機模式下不是大問題。但是在 Hadoop 上並行實現，則會要多次從 HDFS 上讀取訓練數據，而 Hadoop 程序最大的開銷就在 IO 上，這一實現會帶來效率的嚴重降低。而原始實現的先建空樹，反而可以只需要再讀一次數據進行剪枝，統計即可，只不過樹深受到極大限制。當然在 Spark 平台上可以把數據都存放在內存中，但是由於內存資源比較稀缺，並不是所有的問題，都可以把數據放在內存中，這一問題僅僅是緩解了而不是徹底解決了。同時，樹結構的復雜性，使得樹模型在不同節點間的同步和合並也有很多麻煩。目前，隨機決策樹在並行化上的困難，也讓該算法在解決大數據問題時遇到瓶頸。

結束語

隨機決策樹算法在精度和效率上都有不錯的表現，但是並行化卻很困難。可以看到我們在決策樹算法中用隨機方法替代了貪婪方法來構建樹結構，從而獲得了效率上的很大的提高。但是樹結構本身的復雜性，使得其很難進行並行。為了克服這個問題，我們是否可以考慮用其他方法（例如隨機決策哈希算法）來取代樹結構對數據空間的劃分，從而克服並行化困難呢？但由於篇幅有限，該問題暫不屬於本文的討論范圍，有機會筆者將在後續文章中討論。

學習參考

• Is random model better? On its accuracy and efficiency , Fan, W., Wang, H., Yu, P.~S. and Ma, S.:, IEEE, ICDM, 3 (2003).
• J. K. Martin and D. S. Hirschberg, The Time Com plexity of Decision Tree Induction, 1995.
• 隨機決策樹（Random Decision Tree）簡介。