機器學習算法10_決策樹+CART(回歸樹)

機器學習算法第十篇

主要内容:決策樹算法+CART(回歸樹)

  \  

CART算法概念

CART(classification and regression tree) 故英文名思意:分類和回歸樹.

CART算法包含決策樹生成和決策樹剪枝兩部分

CART決策生成樹部分主要分為生成回歸樹和生成分類樹

本篇主要講生成回歸樹

  \  

  \  

算法目的

建構一棵可以對輸入樣本進行很好預測,并輸出預測值的二叉決策回歸樹

  \  

  \  

恩, 開始測試的時候,它是這樣做的…

• 把一個樣本放入節點

  比較自身與節點的特征,選擇一個分支: ‘下去’

  循環 ‘下去’ , 直到葉子節點為止

  當一個測試樣本a落入某葉子時, 該葉子的c值作為該樣本a的預測值輸出

  (某葉子的c值是該樹在訓練時候, 訓練集劃分到該葉子的所有樣本的輸出值的平均值)

  (每個節點都有一個特征選擇,如:長頭發向左分支,短頭發向右分支,該選擇是決策樹生成的時候遺留的)

  \  

  \  

那問題來了, 訓練的時候如何生成一棵樹?

• 算法一開始将所有訓練樣本丢到根節點

  然後通過某準則将它們切成兩份,分别丢入左節點與右節點

  然後對每個節點按照該準則繼續切分,直到某個情況發生,停止切分,直接生成葉子節點

  (某情況是指:例如節點内樣本數不能低于10個,樹的層數不超過11層…參數設定的問題啊)

  \  

  \  

那問題又來了,什麼準則可以很好的切分?

• 算法這樣做滴:

  我們針對一個節點D, 定義一個誤差函數J 它可以計算該節點内所有樣本的的總誤差J(D)

  然後取節點内某特征m與該特征的某個取值n,

  再按照每個樣本的的 m ≤ n 與 m > n m \le n與m>n m≤n與m>n,将樣本集切成兩份 D 1 , D 2 D_1,D_2 D1​,D2​

  J ( D 1 ) + J ( D 2 ) J(D_1)+J(D_2) J(D1​)+J(D2​)的值,即此切法的總誤差P

  是以: 我們隻需要周遊節點内的所有特征,并在該特征内再周遊所有可能取值,取得一大堆總誤差P

  最後取最小的總誤差 P m i n P_{min} Pmin​所對應的特征與取值,進行切分就好

  \  

  \  

那問題又又來了,誤差函數怎麼定才好?

• 算法說:單個節點所有樣本的預測值與平均值之差的平方的和(總方差)作為該葉子節點誤差
• 即 : 單 個 節 點 誤 差 = ∑ i = 1 節 點 樣 本 總 數 ( y i − y ˉ ) 2 即:單個節點誤差=\sum^{節點樣本總數}_{i=1}(y_i-\bar y)^2 即:單個節點誤差=∑i=1節點樣本總數​(yi​−yˉ​)2

  \  

• 這個式子可以很好表達我們對誤差的定義,

• 同時每個葉子内部所有樣本輸出值y的總方差越小,其平均值c的代表性就越高

  (在樣本容量相同的情況下，方差越大，說明資料的波動越大，越不穩定)

  \  

  \  

  \  

  \  

  \  

  \