決策樹 - 簡書

決策樹

Profile

Decision Tree,非參數(shù)的學(xué)習(xí)算法,可以解決分類問題,天然地解決多分類問題(類似KNN,不需要通過ovr或者ovo),也可以解決回歸問題(先將待測樣本分到某一個葉子節(jié)點,再將同一葉子節(jié)點下所有樣本的平均值作為預(yù)測值),具有良好的可解釋性

Example

eg.1 OFFER FOR ML ENGINEER

+發(fā)表過頂會論文?
- Y OFFER
- N + 是否是研究生?
  - Y + ML專業(yè)相關(guān)?
    - Y OFFER
    - N + GPA TOP10%?
      - Y OFFER
      - N INSPECT
  - N + GPA TOP10%?
    - Y OFFER
    - N INSPECT

Explanation of nouns

depth: 一次決策最多需要進行判斷的次數(shù)

構(gòu)建決策樹

選一個維度
找到這個維度的一個閾值
以這個閾值進行劃分

信息熵

一組樣本的不確定性越高(混亂程度越高),則它的信息熵越高,一個系統(tǒng)的熵
$H=-\sum_{i=1}^{k}h_i \\ 其中h_i=\begin{cases} p_ilog(p_i) &p_i \ne 0\\ 0 &p_i= 0 \end{cases}$
eg.
$\left\{\frac{1}{3},\frac{1}{3},\frac{1}{3}\right\}$ 的系統(tǒng)中, $H=-(\frac{1}{3}log\frac{1}{3}+\frac{1}{3}log\frac{1}{3}+\frac{1}{3}log\frac{1}{3})=1.0986$
$\left\{\frac{1}{10},\frac{2}{10},\frac{7}{10}\right\}$ 的系統(tǒng)中, $H=-(\frac{1}{10}log\frac{1}{10}+\frac{2}{10}log\frac{2}{10}+\frac{7}{10}log\frac{7}{10})=0.8018$
$\left\{10^{-8},10^{-8},1-2*10^{-8}\right\} 的系統(tǒng)中,H=3.7841\times10^{-7}$
$\left\{0,0,1\right\} 的系統(tǒng)中,H=0$
對于二分類問題, $H=-plog(p)-(1-p)log(1-p)$

基尼系數(shù)

$G={1}-\sum_{i=1}^{k}p_i^2 \\$
G函數(shù)和H函數(shù)在[0,1]上具有相同的遞增區(qū)間和遞減區(qū)間,對于二分類二者的圖像如下
橫軸為概率p,縱軸為系數(shù)G或者H

20190611165304.jpg

信息熵的計算比基尼系數(shù)慢一些,sklearn默認(rèn)使用基尼系數(shù),二者通常沒有特別的效果優(yōu)劣

CART

Classification And Regression Tree(分類與回歸樹),根據(jù)某一個維度d以及某一個閾值v進行二分,最后得到的決策樹一定是一棵二叉樹,這種樹叫做CART是sklearn的決策樹實現(xiàn)方式,其他的實現(xiàn)方式還有ID3,C4.5,C5.0等
構(gòu)造一棵CART的流程如下:

遍歷樣本的所有維度(d),在每個維度中遍歷所有相鄰點的中點(v),以d=v作為超平面將訓(xùn)練點分成X_left和X_right兩份,分別對應(yīng)y_left和y_right
計算每個每一組y_left和y_right的信息熵(或者基尼系數(shù))H,取H得最小值,此時對應(yīng)的d=v即為當(dāng)前節(jié)點的決策超平面
遞歸處理X_left->y_left和X_right->y_right,直到節(jié)點的信息熵=0,此時這個節(jié)點作為葉子節(jié)點

復(fù)雜度

CART樹預(yù)測時間復(fù)雜度為 $O(log(m))$ ,訓(xùn)練復(fù)雜度為 $O(n*m*log(m))$

最后編輯于：2019.06.11 18:04:21

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者