前面我們用 3 條推文從理論和代碼角度講述了決策樹的概念和粗暴生成。

機器學習算法-隨機森林之決策樹R 代碼從頭暴力實現（3）

機器學習算法-隨機森林之決策樹R 代碼從頭暴力實現（2）

機器學習算法 - 隨機森林之決策樹初探（1）

隨機森林的算法概述

決策樹我們應該都暴力的理解了，下面我們看隨機森林。

隨機森林實際是一堆決策樹的組合（正如其名，樹多了就是森林了）。

這是一個簡化版的理解，實際上要復雜一些。具體怎么做的呢？

假設有一個數據集包含n個樣品, p個變量，也就是一個n X p的矩陣，采用下面的算法獲得一系列的決策樹：

從數據集中有放回地取出n個樣品作為訓練集，訓練1棵決策樹。

假如數據集有6個樣品[a,b,c,d,e]，第一次有放回地取出6個樣品可能是[a,a,c,d,d,e]，第二次有放回地取出6個樣品可能是[a,c,c,d,e,e]。

每棵樹的訓練集是不完全相同的，每個訓練集內部包含重復樣本。

這一步稱為Bagging (Bootstrap aggregating) 自助聚合。

每棵決策樹構建時，通常隨機抽取m (m<<p) 個變量進行每個節點決策變量的選擇，m在選擇每一層節點時不變。

每棵決策樹野蠻生長，不剪枝。

重復第1,2,3步t次，獲得t棵決策樹。

通過聚合t棵決策樹做出最終決策：

• 分類問題：

  選擇t棵決策樹中支持最多的類作為最終分類 (服從多數，majority vote)

• 回歸問題：

  計算t棵決策樹預測的數值的均值作為最終預測值

為什么要這么做呢？

在數據科學中，很大數目的相對不相關的模型的群體決策優于任何單個模型的決策。

隨機森林的錯誤率取決于兩個因素：

• 不同樹之間的相關性越高，則錯誤率越大。

  這要求m盡可能小。

• 每個決策樹的分類強度越大，則錯誤率越小。

  這要求m盡可能大。

m通常為或。也可以通過oob (out-of-bag) error rate (自助聚合錯誤率)進行迭代調參選擇分類效果最好的m。

隨機森林工作機制

通過有放回采樣的方式構建訓練集時，通常有1/3的樣品沒有被選中。這些樣品可以用來估計該訓練集獲得的決策樹的分類錯誤率 (OOB), 也可以用來評估變量的重要性。

每棵決策樹構建好后，用所有的數據作為輸入獲得每個樣品在每個決策樹的分類結果，然后計算每一對樣品 (c1, c2)之間的相似度 ()。如果兩個樣品分類到相同的分類節點，它們彼此的相似性加一。最終的相似度除以決策樹的總數 (t)目獲得任意一對樣品標準化后的的相似度值。這個值可后續用于缺失值填充、異常樣品鑒定和對數據進行低維可視化。(i表示第i棵樹)

oob (out-of-bag) error rate (聚合錯誤率)

應用隨機森林時，無需交叉驗證或額外的測試集來評估錯誤率，而是在構建隨機森林時，可自行評估：

每一個決策樹構建時使用到的樣本是不同的。

因為是有放回地隨機采樣，在構建每棵樹時，大約1/3的樣品不會被用到。

這些沒有被抽樣到用于構建決策樹的樣品用來測試該決策樹的分類能力。

理論上每個樣品在1/3的決策樹中可作為測試樣品獲得一個分類結果和分類錯誤率。

聚合每個沒有被抽樣到的樣品在所有其不被用于訓練集構建的決策樹的分類結果作為該樣品的最終分類結果，與數據的原始分類一致則是分類正確，否則是分類錯誤。

所有分類錯誤的樣品除以總樣品即為構建的隨機森林模型的錯誤率。

(i表示第i棵樹)

確定分類的關鍵變量

對于每一棵隨機決策樹，統計其分類OOB數據集中所有樣品正確分類的次數 ?(O)。隨機排列OOB數據集中變量m的值，再用該決策樹分類，統計所有樣品被正確分類的次數 (P)。這兩個次數的差值(O-P)即為變量m在單棵決策樹的分類重要性得分 (CS, classification score)，其在所有分類樹中的均值即為該變量的整體重要性得分 (ACS, avraged classification score)。

通過大量數據測試發現，同一個變量不同決策樹獲得的CS的相關性很低，可以認為是彼此獨立的。隨后按照常規方式計算所有CS的標準差，ACS/CS獲得Z-score值。假設Z-score服從正態分布，根據Z-score估計該變量的重要性程度。

如果變量數目很多，只在第一次用所有變量評估，后續只評估第一次選出的最重要的一部分變量。

篩選關鍵分類變量的另一個指標 Gini importance

Gini impurity得分是確定決策樹每一層級節點和閾值的一個評判標準。每個變量 (m)貢獻的Gini impurity的降低程度(GD(m))可以作為該變量重要性的一個評價標準。變量(m)在所有樹中的GD(m)之和獲得的變量重要性評估與上面通過隨機置換數據獲得的變量評估結果通常是一致的。

變量互作 Interactions

變量互作定義為，一個決策樹通過變量m做了決策后的子節點可以更容易或更不容易通過變量k做決策。如果變量m與變量k相關，按m決策后，再按k決策就不容易分割因為已經被m分割了。

這也是基于兩個變量m和k是獨立的這一假設。通常通過每個變量作為決策節點時計算出的Gini impurity得分 (g(m)或 g(k)，得分越低說明決策分割效果越少)作為評價依據。他們的差值g(m) - g(k)即為變量m和k的互作值，這個值越大，說明基于變量m分割后更有利于基于變量k分割。

相似性 Proximities

每棵決策樹構建好后，用所有的數據評估決策樹，然后計算每一對樣品之間的相似度。如果兩個樣品分類到相同的分類節點，它們彼此的相似性加一。最終的相似度除以決策樹的總數目獲得任意一對樣品標準化后的的相似度值 (具體見前面的公式)。這些值構成一個n X n (n為總樣品數)的矩陣。這個值可后續用于缺失值填充、異常樣品鑒定和對數據進行低維可視化。

如果數據集較大，n X n的矩陣可能需要消耗比較多內存。這是可以使用n X t的矩陣來存儲 (t是隨機森林中決策樹的數目)。用戶也可以指定每個樣品只保留最相似的nrnn個樣本，以加快運算速度。

如果有測試數據集，測試集中的樣品也可以與訓練集中的樣品計算兩兩相似度。

降維展示 Scaling

樣品i和j的相似度定義為prox(i,j),這是一個不大于1的正數 (具體見前面公式)。1-prox(i,kj)則是樣品i和j的歐式距離。這樣就構成一個最大為n X n的距離矩陣。

隨后就可以通過MDS方式計算其內積，求解特征值和特征向量。可類比于PCA分析，獲得幾個新的展示維度。通常繪制第1,2維就可以比較好的展示樣品的分布。

原型 Prototypes

Prototypes是一種展示變量與分類關系的方式。對第j類，選擇基于相似性獲得的K近鄰樣品中落在j類最多的樣品。這k個樣品中，計算每個變量的中位數、第一四分位數和第三四分位數。這個中位數就是class j的原型 (prototype), 第一四分位數和第三四分位數則是原型的置信范圍。對于第二個原型，按之前的步驟計算，只是不考慮上一步用到的k的樣品。輸出原型時，如果是連續變量，則用原型值減去第5分位數并除以第95分位數和第5分位數的差值。如果是區域變量，原型就是出現次數最多的值。

訓練集中的缺失值填充 Missing value replacement for the training set

隨機森林有兩種方式填充缺失值。

• 第一種方式速度快。如果某個樣品屬于class j，其變量m值缺失，如果變量m的值是數值型，則用class j中所有樣品的變量m的值的中位數作為填充值；如果變量m的值是分類型，則用class j中所有樣品出現次數最多的變量m的值作為填充值；

• 第二種方式需要更多計算量但可以給出更好的結果，即便是存在大量缺失數據時。它只通過訓練集填充缺失值。首先對缺失值做一個粗略的、非精確的填充。然后計算隨機森林和樣本相似性。

定義樣品i的變量m的值為v(m,i)，如果變量m為連續性數值變量,則其填充值為其它樣品中變量m的值與該樣品與樣品i的相似性的乘積的均值 (n1是變量m不為缺失值的樣品)。如果變量m為分類型變量, 則替換其為所有樣品最頻繁出現的值（計算頻率時需要用根據每個樣品與樣品i的相似性進行加權）。

隨后使用填充后的數據集迭代構建隨機森林模型，計算新的填充值并且繼續迭代，通常4-6次迭代即可。

替換測試集中的缺失值 Missing value replacement for the test set

取決于測試集是否自帶樣品標簽（分類屬性）有兩種方式可以用于缺失值替換。

• 如果測試集有標簽，訓練集中計算出的填充值直接用于測試集填充。

• 如果測試集沒有標簽，則測試集中的每個樣品都重復n_class次 (n_class為總的分類數)。

  第一次重復的樣品設置其標簽為class 1，并用class 1的對應值填充。

  第二次重復的樣品設置其標簽為class 2，并用class 2的對應值填充。

這個重復后的測試集用構建好的隨機森林模型進行分類。在某個樣品的所有重復中，獲得最多分類的class則是該樣品的標簽，缺失值也根據對應class填充。

標簽有誤的樣品 Mislabeled cases

訓練集通常是人為判斷設定的標簽。在一些領域，誤標記會常出現。很多誤標記的樣本可以通過異常值檢測的方式鑒定出。

異常值 Outliers

異常樣本定義為需要從主數據集中移除的樣本。從數據上來說，異常樣品就是與其它所有樣品相似性 (proximity)都很低的樣品。通常為了縮小計算量，異常樣品是從每個分類內部計算鑒定的。class j的一個異常樣本就是在class j中某一個或多個與其它樣本相似性很低的樣本。

class j中的樣品 n與class j中其它樣品(k)的平均相似性定義為

樣品n是否為異常樣品的度量方式為

The raw outlier measure for case n is defined as

如果平均相似度較低，這個度量值就會很高。計算這一組數據 (class j中每個樣本 （J1, J2, Jn）與其它樣本的平均相似度)的中位數和絕對偏差。每個平均相似度值減去中位數除以絕對偏差即獲得最終的異常值度量標準。

無監督聚類 Unsupervised learning

無監督聚類問題中，每個樣品有一些度量值但都沒有分類標簽（分類問題）或響應變量（回歸問題）。這類問題沒有優化的標準，通常只能獲得模糊的結論。最常見的應用是對數據進行聚類，能聚成幾類，每一類是否意義明確。

在隨機森林中，所有原始數據都視為來源于class 1, 然后構建一個相同大小的合成數據集都視為來源于class 2。第二個合成數據集通過對原始數據進行單變量 (univariate distribution)隨機采樣構建。合成數據集每個樣品構建方式舉例如下：

• 樣品第一個變量的值從該變量在n個樣品中的值隨機抽取一個。

• 樣品第二個變量的值從該變量在n個樣品中的值隨機抽取一個。

• 以此類推

因此，Class 2數據有著獨立的隨機變量數據分布，并且每個變量的數據分布與原始矩陣的對應變量一致。Class 2數據打亂了原始數據的依賴結構?，F在全體數據就有了兩個分類，可以應用隨機森林算法構建模型。

如果這兩類數據的oob誤分類率為40%或更高，說明隨機森林the x -variables look too much like independent variables to random forests。變量的依賴在分組上貢獻不大。如果誤分類率低，則說明變量依賴發揮了重要作用。

把無標簽數據集改造為包含兩個分類的數據集給我們一些好處。缺失值可以有效填充。可以鑒定出異常樣品?？梢栽u估變量的重要性。可以做降維分析（如果原始數據有標簽，非監督的降維 (`scaling)通常能保留下原始分類的結構）。最大的一個好處是使得聚類成為了可能。

平衡預測錯誤 ?Balancing prediction error

在一些數據集，不同分類的預測錯誤是很不均衡的。一些分類預測錯誤率低，另一些類預測錯誤率高。這通常發生在每個類的樣品數目差別較大時。隨機森林試圖最小化總錯誤率，保持大的類有較低的分類錯誤率，較小的類有較高的分類錯誤率。例如，在藥物發現時，一個給定的分子會分類為有活性或無活性。通常分類為有活性的的概率為1/10或1/100。這時分類為有活性組的錯誤率就會很高。

用戶可以通過輸出每種分類的錯誤率作為預測不平衡性的評估。為了說明這個問題，我們采用一個有20個變量的合成數據集。class 1的數據符合一個球形的高斯分布，class 2的數據符合另一個球形高斯分布。訓練集包含1000個class 1樣品和50個class 2樣品。測試集包括5000個class 1樣品和250個class 2樣品。

包含500棵樹的隨機森林輸出的錯誤率為500 3.7 0.0 78.4?？傮w錯誤率較低(3.7%),但class 2的錯誤率高，為(78.4%)?？梢酝ㄟ^對每個class設置不同的權重來平衡錯誤率。一個class的權重越高，它的分類錯誤率降低的就越多。一個常規的設置權重的方式是與class中樣品數成反比。設置訓練集中class 1的權重為1, class 2的權重為20，再次構建模型，輸出為500 12.1 12.7 0.0。class 2的權重為20有點太高了，降低為10，獲得結果如下500 4.3 4.2 5.2。

這樣兩個分類的錯誤率差不多平衡了。如果要求兩個分類錯誤率相等，則還可以再微調class 2的權重。

需要注意的是，在平衡不同分類錯誤率時，總的錯誤率升高了。這是正常的。

檢測新樣品 Detecting novelties

對于測試集異常樣品的檢測可用來尋找新的不能分類于之前鑒定好的類中的樣品。

以下面的衛星圖像數據集做例子。訓練集有4435個樣品，測試集有2000個樣品，36個變量，6個分組。

在測試集中，等間距的選取了5個樣品。被選中樣品的每個變量的值用從訓練集中同一個變量的值隨機選取一個替換。采用參數noutlier=2; nprox=1作為運行參數，輸出下圖：

這展示了采用一個固定的訓練集，可以檢測測試集中的新樣品。訓練集構建的樹可以存儲起來用于檢測后續的數據集。這個檢測新樣品的方法目前還處于試驗階段，還不能區分DNA檢測中的新樣本。

接下來我們就選幾套數據集進行實戰操作，邊操作邊理解概念了。

往期精品(點擊圖片直達文字對應教程)

后臺回復“生信寶典福利第一波”或點擊閱讀原文獲取教程合集

?

（請備注姓名-學校/企業-職務等）

總結

以上是生活随笔為你收集整理的机器学习算法-随机森林之理论概述的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。