大多數機器學習算法的計算復雜度都是隨著數據量或者維度呈線性增長，這是大規模機器學習的一大挑戰。本文將介紹隨機決策樹算法的基本方法，並從理論層面粗略的探討了為什麼隨機決策樹具有學習能力。
大數據給機器學習帶來了挑戰，效率成為大規模機器學習的關鍵問題。 隨著互聯網和移動互聯網的發展，人類社會產生的數據越來越多。根據新摩爾定律，數據的規模每 5 年增長 10 倍。除了數據量本身的增長外，數據的維度也越來越高。數據規模的快速增長，給機器學習創造了更大價值的機會。但同時也提出了很嚴峻的挑戰：數據量和維度的增長，使得機器學習的計算開銷急劇膨脹，使得學習效率問題變得越來越嚴重。這是因為經典的機器學習算法的計算復雜度大多隨著數據量或者維度的增長呈超線性增長。圖 1 引用自文獻，這個圖列出了 10 大經典機器學習算法在單核和多核模式下進行一個迭代的計算復雜度。從圖中可以看出，除了 Naïve Bayes、Neural Network、k-means 算法的計算復雜度與數據量和維度是線性關系外，其他的算法都是平方，甚至三次方的關系。這還是沒有考慮多次迭代情況下的計算復雜度。如果考慮迭代而又無法把所有數據存在內存中的情況，每次迭代除了計算開銷以外，還需要付出巨大的 IO 開銷。不幸的是，數據量的增長速度是快於內存增長的速度，而絕大多數機器學習算法都是需要迭代的。數據規模的增長和學習效率降低之間的矛盾變得越來越尖銳。
為了解決機器學習計算開銷急劇增大的問題，分布式機器學習算法和平台的研 究成為了機器學習領域的熱點之一。KDD（Knowledge Discovery and Data Mining）2015 有 3 個 Tutorial 都是關於這方面的內容。但實際上，對現有算法的分布式學習只是解決了計算能力的擴展問題以及在擴展過程中如何減少 IO, 網絡和同步開銷的問題，但數據量增長和算法效率之間的矛盾並沒有解決。而目前機器學習算法發展的主流還是在提高算法的精度，而為了提高精度往往要付出更大的計算代價，目前深度學習的發展就是一個例子。本系列文章將介紹一類非主流的機器學習算法，這類算法有別於經典機器學習算法的思想，采用隨機方法建模，使得計算開銷能夠降低到線性水平。本篇文章將從方法、原理、計算復雜度，效果及其局限等幾方面介紹隨機決策樹算法。
隨機決策樹（Random Decision Tree）算法的基本思想是隨機構建若干棵決策樹，在預測結果時將每棵樹的預測分值進行簡單平均得到最終結果。因為樹的構建過程是隨機的，不用計算 Gini Index、Information Gain 或者 Information Gain Ratio，其計算開銷非常小，僅與數據量為線性關系。這對解決機器學習問題來說，是很好的性質。其計算復雜度的具體分析，我們將在後面介紹，這裡先來看看基本的方法。
當創建一棵樹的時候，該算法在每個節點的擴展過程中從“剩余的”的特征中隨機選擇一個。在這一挑選的過程中，不會使用任何的純度函數 (如 information gain 和 gini 系數等) 來檢查特征。對於一個類別（ categorical）特征（如性別）如果在一條從根節點到當前節點的決策路徑上沒有出現過，那麼就被認為是“剩余的”。因為，一旦一個類別特征被使用了，那麼在同一條決策路徑上的學習樣本在這個 feature 上的值都會是一樣的（要麼全是男要麼全是女）。但是對於連續值特征（比如收入）在同一條決策路徑上可以被多次使用的，只是每次的分類阈值只能在當前路徑所包含的學習樣本的取值范圍內隨機選擇。樹的生長停止條件可以有以下兩種限制，一是樹的最大深度，一是每個葉子節點上最少需要保留的樣本個數，通常兩個條件一起使用。經驗上來講樹的最大深度一般設置為特征數的一半，葉子節點上最少需要保留的樣本個數可以在 4-10 之間選擇。當樹停止生長以後，再統計每個葉子節點上的類別頻率，從而獲得所有的樹模型。
在預測時，對一個給定的數據實例，在每棵樹上都能落在一個葉子節點上。以這個葉子節點上的正樣本頻率（假設是二分類問題）作為這棵樹對這個數據實例是正例的預測概率。將所有樹的預測概率簡單平均，即得到最後的預測概率。
隨機決策樹與隨機森林非常容易混淆。隨機森林也是使用多棵樹，而且在樹的構建過程中也引入了隨機因素。但最大的不同在於隨機決策樹算法構建樹時是完全隨機的，而隨機森林雖然引入了一些隨機因素，但是還是要計算 Gini Index, Information Gain 或者 Information Gain Ratio 這些分支選擇指標。隨機森林算法的邏輯比隨機決策樹要復雜得多，而其計算復雜度也不可能得到很大的改善。隨機深林是通過引入一些隨機因素來獲得有較高 Diversity 的多個模型，從而保證 Ensemble 模型具有較好的泛化能力，但本質上還是遵循經典決策樹算法的基本思想，通過貪婪算法來尋找最好的分類界面。而隨機決策樹算法則是隨機的把數據劃分成不同的部分，統計每個部分的類別分布。這是隨機決策樹與隨機森林和一般監督學習器之間的根本區別，通過下一節的分析，我們將更深入的了解這個區別。
隨機決策樹算法的基本思想與一般學習算法有很大的不同，是違反一般監督學習理論的常識的。因為在決策樹的結構構建中，根本沒有利用監督信息，從常識出發，該算法產生的模型不應該有預測能力。 但在實踐中，隨即決策樹算法的預測精度是可以跟經典的算法相媲美的。隨機決策樹為什麼能有學習能力，一直是令我著迷的一個問題。其相關文獻都只有一些在理論上都不夠嚴謹的說明和分析。本節將簡要介紹個人對這個問題的理解。
機器學習是伴隨著計算機的發明而出現的，上世紀 40 年代現代計算機發明後，50 年代就興起了第一波機器學習的研究浪潮。在計算機出現以前，統計學已經建立了嚴密的體系和方法。這些方法在小樣本量和很少維度的數據上，能夠有很多不錯的結果。到現在我們大學裡學的統計學都是專注在研究這些小樣本量和 1-2 維的問題。在理論上，把統計學的方法往高維空間中推廣並沒有困難，但在實際上這些方法往多維推廣遇到了維數詛咒問題。統計學很重要的一個工作就是估計概率密度函數，也提供了很多概率密度函數的模型，如最典型的正態分布函數。實質上概率密度函數估計就是函數擬合。但是隨著維度的增加，達到同樣估計精度需要的樣本數量幾何數級的增加，這就是維數詛咒問題。在多維情況下，經典的統計學工具無法有效解決問題。為此，機器學習在處理這些問題時，采用了兩種不同的策略。一種是放棄對估計精度的嚴格要求，采用簡單、強假設的、線性模型來擬合，典型的如樸素貝葉斯和邏輯回歸（Logistic Regression）。另一個方法，就如 Vapnik 所說，為了解決一個問題，不應該去解決比這個更難的問題。就分類問題而言，就是應該直接找分類界面而不是估計類別的分布概率函數。典型的算法就是 SVM, 而決策樹算法也可以歸為這一類。總之，機器學習實際上是統計在多維情況下對維數詛咒問題的妥協。
上面討論的機器學習和統計學主要涉及參數估計方法，也是我們在大學統計學教材中主要討論的方法。但是在統計學上有另外一套概率密度函數估計的方法，那就是非參數估計方法。非參數估計不需要假設數據是服從哪種分布模型的，因此該方法的適應性要強很多。但同時，非參數估計得出的模型相比參數模型則復雜很多，從數學上看也比較丑陋。最簡單的非參數估計方法就是直方圖。直方圖的缺點是估計出來的函數圖形是階梯壯的，兩個方柱之間估計結果是斷層跳躍的，這就使得直方圖的估計精度比較粗糙。為了克服直方圖的問題，Parzen Window 方法又在直方圖劃分的箱中引入了高斯核來平滑直方圖的估計。但是其計算開銷也遠大於直方圖。 而另一種比較小眾的非參數估計方法，平衡了這兩種方法的優缺點。這個方法就是 Averaged Shifted Histogram（平均偏移直方圖）。簡單來說 ASH 方法就是把多個直方圖的結果做簡單平均，這些直方圖的規格都是一樣的，不同的是這些直方圖之間有平移，也就是說用一組有平移關系的直方圖融合起來做概率估計。圖 2 中 ASH 的例子，展示了從一個直方圖到 32 個直方圖時估計的概率密度函數的變化。顯然，隨著直方圖數量的增加，概率函數的估計越來越平滑。雖然非參數估計有自身的優點，但是同樣受制於維數詛咒的問題，難以擴展到多維問題上。
回過頭來看隨機決策樹算法。如果我們把隨機決策樹算法用在一維的問題上，就會發現其跟 ASH 非常相似。一個一維問題的決策樹，實際上就是對一維空間做了分段，然後統計每個分段裡的類別出現頻率。這在形式上與直方圖是十分相似的。唯一的不同是一維的決策樹不要求每個段的寬度是一樣的。顯然， 多棵一維隨機決策樹算法也跟 ASH 算法相似，實際上也是一種非參數估計方法。
基於上面的分析，隨機決策樹擁有學習能力從原則上也並不是什麼神秘的事情，它可以看作是 ASH 算法在多維問題上的一種變種。ASH 算法由於直方圖在多維問題上的直接擴展會導致大量的空箱和一個樣本的箱使得估計誤差會變得很大而失去意義。而樹的結構卻克服了這個問題，樹結構實際上根據樣本在數據特征空間中的分布進行了劃分，並確保每個葉子節點上的樣本數不會少於一個給定的阈值。這就使得樹劃分出來的各個數據子空間（對應直方圖的箱）裡的概率估計相對准確。當然，在高維問題下，由於每個葉子節點幾乎���可能覆蓋所有的維度空間，這些葉子節點上的概率估計實際也只是邊緣概率的估計。由於有多棵樹對數據特征空間的不同劃分，使得對於一個給定點的聯合概率的估計由多組不同的邊緣概率的平均值來估計。隨機決策樹實際上就是非參數估計方法在高維問題上的一種妥協。
限於篇幅本篇文章僅簡要介紹了隨機決策樹算法的基本方法，以及為什麼這樣的純隨機算法具有學習能力。 我們看到隨機決策樹算法實際上是非參數估計方法在高維問題下的一種妥協。雖然非參數估計方法在低維問題上和效率上與參數估計方法相比並沒有什麼優勢，但是隨機決策樹算法在高維問題上顯示出了很高的效率優勢。本系列的下一篇文章將對隨機決策樹的兩種實現方式和算法復雜度進行具體分析，並與其他的一些算法的實際效果進行對比。