陳詞濫調(diào)決策樹。提到?jīng)Q策樹，不能不說不純度的概念。

• 回歸不純度
  

  i(N)=∑j(yj?rj)2
  
  其中，rj為該結(jié)點的預(yù)測值輸出值，通常此處設(shè)為該節(jié)點所有值的均值，yj為真值。我們的目標(biāo)是最小化該值。

• 分類不純度
  熵不純度： i(N)=∑jP(ωj)log(ωj)
  Gini不純度：i(N)=∑j≠iP(wi)P(wj)=∑jP(wj)(1?P(wj))=1?∑jP(wj)2
  錯分不純度：i(N)=1?maxP(wj)

決策樹是1個統(tǒng)稱，其實它包括若干類，常見的種類有： ID3、C4.5 和CART,說說各自特點：
ID3: 1986 Ross Quinlan提出，采取 熵不純度規(guī)則分裂節(jié)點，通常分支因子Bj>2，標(biāo)準(zhǔn)版本的ID3沒有剪枝操作。
C4.5: 為ID3改進版本，特點值可以處理連續(xù)變量，采取信息熵增益比。
CART：分類回歸樹，與ID3和C4.5最重要的區(qū)分便是，其能處理回歸問題，即數(shù)值預(yù)測。節(jié)點分裂準(zhǔn)則采取Gini不純度。（其實，現(xiàn)在的CART算法，不純度模式是可選的）
　　由于CART的通用性，在1些機器學(xué)習(xí)庫中實現(xiàn)的決策樹絕大多數(shù)是CART樹，如opencv 和sklearn中。有必要系統(tǒng)的學(xué)習(xí)1下。以下以opencv為原型學(xué)習(xí)。
　　根據(jù)特點屬性和標(biāo)簽屬性是數(shù)值型還是分類型，可將決策樹分為4類：

• 特點為種別的分類樹 ：find_split_cat_class（）
• 特點為數(shù)值的分類樹：find_split_ord_class（）
• 特點為種別的回歸樹：find_split_cat_reg（）
• 特點為數(shù)值的回歸樹：find_split_ord_reg（）

詳細(xì)講授請參照博文：opencv 決策樹源碼分析 http://blog.csdn.net/zhaocj/article/details/50503450