決策樹算法是一種比較簡易的監(jiān)督學習分類算法伴网，既然叫做決策樹契耿，那么首先他是一個樹形結構祭陷，簡單寫一下樹形結構（數據結構的時候學過不少了）踪蹬。
樹
樹狀結構是一個或多個節(jié)點的有限集合姆另，在決策樹里寿酌，構成比較簡單根灯，有如下幾種元素：
- 根節(jié)點：沒有入邊（輸入）梁剔，但是有0或者多條出邊（輸出）脯颜。
- 非葉子節(jié)點： 有一條入邊哟旗，兩條或者多條出邊。
- 葉子節(jié)點： 只有一條入邊栋操，沒有出邊闸餐。
-
分支：就是出邊和入邊，代表決策的結果矾芙。
以圖為例：
決策樹
在決策樹中舍沙，每個葉子節(jié)點都有一個類標簽，非葉子節(jié)點包含對屬性的測試條件剔宪，用此進行分類拂铡。
所以個人理解，決策樹就是對一些樣本葱绒，用樹形結構對樣本的特征進行分支感帅，分到葉子節(jié)點就能得到樣本最終的分類，而其中的非葉子節(jié)點和分支就是分類的條件地淀，測試和預測分類就可以照著這些條件來走相應的路徑進行分類失球。
根據這個邏輯，很明顯決策樹的關鍵就是如何找出決策條件和什么時候算作葉子節(jié)點即決策樹終止帮毁。
條件分類
決策樹的核心是為不同類型的特征提供表示決策條件和對應輸出的方法实苞，特征類型和劃分方法包括以下幾個：
- 二元屬性，產生兩個可能的輸出（是或不是）烈疚。
- 標稱屬性黔牵，具有多個屬性值，有兩種表示方式爷肝，一種是多路輸出（有一個屬性值輸出一個分支）猾浦，另外一種是只產生二元劃分陆错，這樣的話就考慮創(chuàng)建
個屬性值的二元劃分的所有
中方法。
多路輸出
-
序數屬性跃巡，是有序的一組屬性值危号，不能違背序數屬性的有序性，進行分組素邪。
序數屬性 -
連續(xù)屬性：連續(xù)屬性就是能取任何值的屬性外莲，可以通過一定的范圍進行劃分（離散化）。
連續(xù)屬性
注意兔朦，這些圖中的第二層都是分支偷线，不是葉子節(jié)點。
最佳特征的劃分
如何合理的對特征進行劃分沽甥，從而找到最優(yōu)的決策模型呢声邦？在這里需要引入信息熵的概念。
信息熵
先來看熵的概念：
熵摆舟，熱力學中表征物質狀態(tài)的參量之一亥曹，用符號S表示，其物理意義是體系混亂程度的度量恨诱。
在數據集中媳瞪，參考熵的定義，把信息熵描述為樣本中的不純度照宝，熵越高蛇受，不純度越高，數據越混亂（越難區(qū)分分類）厕鹃。
例如：要給（0兢仰，1）分類，熵是0剂碴，因為能明顯分類把将，而均衡分布的（0.5，0.5）熵比較高忆矛，因為難以劃分察蹲。
信息熵的計算公式為：
其中代表信息熵。
是類的個數洪碳，
代表在
類時
發(fā)生的概率递览。
另外有一種Gini系數叼屠，也可以用來衡量樣本的不純度：
其中代表Gini系數瞳腌，一般用于決策樹的CART算法。
舉個例子：
| 分類 | 計數 |
|---|---|
| 類=0 | 3 |
| 類=1 | 3 |
如果有上述樣本镜雨，那么樣本中可以知道嫂侍，能被分為0類的有3個，分為1類的也有3個，那么信息熵為：
Gini系數為：
總共有6個數據挑宠，那么其中0類3個菲盾，占比就是3/6，同理1類各淀。
我們再來計算一個分布比較一下：
| 分類 | 計數 |
|---|---|
| 類=0 | 1 |
| 類=1 | 5 |
信息熵為：
Gini系數為：
很明顯懒鉴，因為第二個分布中，很明顯這些數偏向了其中一類碎浇，所以純度更高临谱，相對的信息熵和Gini系數較低。
有了上述的概念奴璃，很明顯如果我們有一組數據要進行分類悉默，最快的建立決策樹的途徑就是讓其在每一層都讓這個樣本純度最大化，那么就要引入信息增益的概念苟穆。
信息增益
所謂增益抄课，就是做了一次決策之后，樣本的純度提升了多少（不純度降低了多少）雳旅，也就是比較決策之前的樣本不純度和決策之后的樣本不純度跟磨，差越大，效果越好岭辣。
讓信息熵降低吱晒，每一層降低的越快越好。
度量這個信息熵差的方法如下：
其中代表的就是信息熵（或者其他可以度量不純度的系數）的差沦童，
是樣本(parent是決策之前仑濒，
是決策之后)的信息熵（或者其他可以度量不純度的系數），
為特征值的個數偷遗，
是原樣本的記錄總數墩瞳，
是與決策后的樣本相關聯(lián)的記錄個數。
當選擇信息熵作為樣本的不純度度量時氏豌，Δ就叫做信息增益喉酌。
我們可以遍歷每一個特征，看就哪個特征決策時泵喘，產生的信息增益最大泪电，就把他作為當前決策節(jié)點，之后在下一層繼續(xù)這個過程纪铺。
舉個例子：
如果我們的目標是判斷什么情況下相速，銷量會比較高（受天氣，周末鲜锚，促銷三個因素影響）突诬，根據上述的信息增益求法苫拍，我們首先應該找到根據哪個特征來決策，以信息熵為例：
首先肯定是要求旺隙，也就是銷量這個特征的信息熵：
接下來绒极，就分別看三個特征關于銷量的信息熵，先看天氣蔬捷，天氣分為好和壞兩種垄提，其中天氣為好的條件下，銷量為高的有11條周拐，低的有6條塔淤；天氣壞時，銷量為高的有7條速妖，銷量為低的有10條高蜂，并且天氣好的總共17條，天氣壞的總共17條罕容。
分別計算天氣好和天氣壞時的信息熵备恤，天氣好時：
根據公式，可以知道锦秒，N是34露泊，而天氣特征有2個值，則k=2旅择，第一個值有17條可以關聯(lián)到決策后的節(jié)點惭笑，第二個值也是17條，則能得出計算：
再計算周末這個特征生真，也只有兩個特征值沉噩，一個是，一個否柱蟀，其中是有14條川蒙，否有20條；周末為是的中有11條銷量是高长已，3條銷量低畜眨，以此類推有：
信息增益為：
另外可以得到是否有促銷的信息增益為0.127268。
可以看出术瓮，以周末為決策康聂，可以得到最大的信息增益胞四，因此根節(jié)點就可以用周末這個特征進行分支：
注意再接下來一層的原樣本集恬汁，不是34個而是周末為“是”和“否”分別計算，為是的是14個撬讽，否的是20個蕊连。
這樣一層一層往下遞歸，直到判斷節(jié)點中的樣本是否都屬于一類游昼，或者都有同一個特征值甘苍，此時就不繼續(xù)往下分了，也就生成了葉子節(jié)點烘豌。
上述模型的決策樹分配如下：
需要注意的是载庭，特征是否出現需要在分支當中看，并不是整體互斥的廊佩，周末生成的兩個分支囚聚，一個需要用促銷來決策，一個需要用天氣标锄，并不代表再接下來就沒有特征可以分了顽铸，而是在促銷決策層下面可以再分天氣，另外一遍天氣決策下面可以再分促銷料皇。
決策樹的模型比較容易解釋谓松，看這個樹形圖就能很容易的說出分類的條件。
計算過程中提到的信息熵践剂，換成Gini系數計算也是一樣的鬼譬。
不同類型屬性的劃分
我們知道屬性有二元屬性、標稱屬性逊脯、序數屬性和連續(xù)屬性优质，其中二元、標稱和序數都是類似的军洼，因為是離散的屬性巩螃，按照上述方式進行信息增益計算即可，而連續(xù)屬性與這三個不同匕争。
連續(xù)屬性的決策劃分
對于連續(xù)的屬性牺六，為了降低其時間復雜度，我們可以先將屬性內部排序汗捡，之后取相鄰節(jié)點的均值作為決策值淑际，依次取每兩個相鄰的屬性值的均值，之后比較他們的不純度度量扇住。
這樣的話春缕，得到的決策分支就會是這種類型的，指定一個范圍而不是一個固定的值艘蹋。
需要注意的是锄贼，連續(xù)屬性可能在決策樹中出現多次，而不是像離散的屬性一樣在一個分支中出現一次就不會再出現了女阀。
信息增益率
用信息熵或者Gini系數等不純度度量有一個缺點宅荤，就是會傾向于將多分支的屬性優(yōu)先分類——而往往這種屬性并不是特征屑迂。
例如上面例子中的第一行序號，有34個不同的值冯键，那么信息熵一定很高惹盼，但是實際上它并沒有任何意義，因此我們需要規(guī)避這種情況惫确，如何規(guī)避呢手报，有兩種方式：
- 限制條件只能是二元劃分，這樣就不會出現多分支的傾斜了改化，CART算法就是這種算法掩蛤，采用Gini系數作為度量。
- 修改決策劃分的標準陈肛，把決策條件產生的輸出數也算進去揍鸟，C4.5算法就是用這種模式，引入了信息增益率的概念句旱。
公式如下：
其中k為劃分的總數蜈亩，如果每個屬性值具有相同的記錄數，則前翎，劃分信息等于
稚配，那么如果某個屬性產生了大量劃分，則劃分信息很大港华，信息增益率低道川，就能規(guī)避這種情況了。
決策樹的優(yōu)化
為了防止過擬合現象立宜，往往會對決策樹做優(yōu)化冒萄，一般是通過剪枝的方式，剪枝又分為預剪枝和后剪枝橙数。
預剪枝
在構建決策樹時尊流，設定各種各樣的條件如葉子節(jié)點的樣本數不大于多少就停止分支，樹的最大深度等灯帮，讓決策樹的層級變少以防止過擬合崖技。
也就是在生成決策樹之前，設定了決策樹的條件钟哥。
后剪枝
后剪枝就是在最大決策樹生成之后迎献，進行剪枝，按照自底向上的方式進行修剪腻贰，修剪的規(guī)則是吁恍，評估葉子節(jié)點和其父節(jié)點的代價函數，如果父節(jié)點的代價函數比較小，則去掉這個葉子節(jié)點冀瓦。
這里引入的代價函數公式是：
其中代表的是葉子節(jié)點中樣本個數伴奥，
代表的是該葉子節(jié)點上的不純度度量，把每個葉子節(jié)點的
加起來翼闽，和父節(jié)點的
比較拾徙，之后進行剪枝即可。
決策樹算法的特點
- 計算效率比較高肄程。
- 解釋性好，在很多簡單的數據集中选浑，算法效果良好蓝厌。
- 對噪聲又較好的魯棒性。
- 對于共線性較強的特征古徒，不會產生不利的影響拓提。
