一、決策樹原理
決策樹模型是運用于分類以及回歸的一種樹結構。決策樹由節點和有向邊組成，一般一棵決策樹包含一個根節點、若幹内部節點和若幹葉節點。決策樹的決策過程需要從決策樹的根節點開始，待測資料與決策樹中的特征節點進行比較，并按照比較結果選擇選擇下一比較分支，直到葉子節點作為最終的決策結果。
内部節點：對應于一個屬性測試
葉節點：對應于決策結果
根節點包含樣本全集；
每個節點包括的樣本集合根據屬性測試的結果被劃分到子節點中；
根節點到每個葉節點的路徑對應對應了一個判定測試路徑；
決策樹的結構還是比較好了解的，如果不明白，可以看一下圖中的例子，這是一個簡單判斷這個鍵盤我喜不喜歡的決策樹模型：
目标變量可以采用一組離散值的樹模型稱為分類樹(常用的分類樹算法有ID3、C4.5、CART)，而目标變量可以采用連續值（通常是實數）的決策樹被稱為回歸樹(如CART算法)。
決策樹算法本質上就是要找出每一列的最佳劃分以及不同列劃分的先後順序及排布。
優點：分類速度快，能在相對短的時間内能夠對大型資料源做出可行且效果良好的結果。
缺點：對未知的測試資料未必有好的分類、泛化能力，即可能發生過拟合現象，此時可采用剪枝或随機森林。
二、決策樹學習算法：
1、特征選擇
特征選擇也即選擇最優劃分屬性，從目前資料的特征中選擇一個特征作為目前節點的劃分标準。我們希望在不斷劃分的過程中，決策樹的分支節點所包含的樣本盡可能屬于同一類，即節點的“純度”越來越高。而選擇最優劃分特征的标準不同，也導緻了決策樹算法的不同。
為了找到最優的劃分特征，我們需要先了解一些資訊論的知識：
（1）熵（混亂程度）
在資訊論和機率統計中，熵(entropy)是表示随機變量不确定性的度量，熵越大，随機變量的不确定性越大。
設X是一個取有限值的離散随機變量，其機率分布為：
則随機變量X的熵定義：
為了能夠更好地了解熵的意義，舉一個例子來說明。A集合：[1,2,3,1,1,4,5]，B集合：[1,1,1,1,1,1,2]，A集合的熵更大。
（2）條件熵
設有随機變量(X,Y)，條件熵H(Y|X)表示在已知随機變量X的條件下随機變量Y的不确定性。
随機變量X給定的條件下随機變量Y的條件熵H(Y|X)定義為X給定條件下Y的條件機率分布的熵對X的數學期望。
其中：
（3）資訊增益
資訊增益表示得知特征X的資訊而使得類Y的資訊的不确定性減少程度。
特征A對訓練資料集D的資訊增益g(D,A),為集合D的熵H(D)與特征A給定條件下D的條件熵H(D|A)之差，即：
（4）資訊增益率
特征A對訓練資料集D的資訊增益率gR(D,A)定義為其資訊增益g(D,A)與訓練資料集D關于特征A的值的熵HA(D)之比，即：
，注意差別H(D|A)、HA(D)。
（5）基尼指數
基尼指數Gini(D)表示集合D不确定性，基尼指數Gini(D，A=a)表示集合D經A=a分割後的不确定性(類似于熵)，基尼指數越小，樣本的不确定性越小。
分類問題中，假設有K個類，樣本點屬于第k類的機率為pk,則機率分布的基尼指數定義為：
如果樣本集合D根據特征A是否取某一可能值aa被分割成D1和D2兩部分，即
則在特征A的條件下,集合D的基尼指數定義為
（6）相對熵 KL散度
相對熵可以用來衡量兩個機率分布之間的差異，上面公式的意義就是求 pp 與 qq 之間的對數差在 pp 上的期望值
（7）交叉熵
2、決策樹生成
（1）ID3算法原理
ID3算法的核心是在決策樹各個節點上應用資訊增益準則選擇特征遞歸地建構決策樹。
（1）熵：在資訊論中，熵是随機變量不确定性的度量，也就是熵越大，則随機變量的不确定性越大。
（2）條件熵：條件熵H(Y|X)表示在已知随機變量X的條件下，随機變量Y的不确定性。
（3）資訊增益定義為：
，即集合D的經驗熵H(D)與特征A給定條件下D的經驗條件熵H(H|A)之差。
選擇劃分後資訊增益大的作為劃分特征，說明使用該特征後劃分得到的子集純度越高，即不确定性越小。是以我們總是選擇目前使得資訊增益最大的特征來劃分資料集。
缺點：資訊增益偏向取值較多的特征。原因：當特征的取值較多時，根據此特征劃分更容易得到純度更高的子集，是以劃分後的熵更低，即不确定性更低，是以資訊增益更大。
ID3算法：
（2）C4.5算法原理
C4.5算法是對ID3算法做了改進，在生成決策樹過程中采用資訊增益比來選擇特征。我們知道資訊增益會偏向取值較多的特征，使用資訊增益比可以對這一問題進行校正。
資訊增益比定義：特征A對訓練資料集D的資訊增益比GainRatio(D,A)定義為其資訊增益Gain(D,A)與訓練資料集D的經驗熵H(D)之比。
C4.5算法過程與ID3算法一樣，差別就是将選擇特征的方法由資訊增益改成資訊增益比。
（3）CART算法原理
基尼指數Gini(D)表示集合D的不确定性，基尼指數Gini(D,A)表示經A=a分割後集合D的不确定性。基尼指數值越大，樣本集合的不确定性也就越大，這一點跟熵相似。
CART算法：
（4）回歸樹
回歸樹是可以用于回歸的決策樹模型，一個回歸樹對應着輸入空間（即特征空間）的一個劃分以及在劃分單元上的輸出值。與分類樹不同的是，回歸樹對輸入空間的劃分采用一種啟發式的方法，會周遊所有輸入變量，找到最優的切分變量j和最優的切分點s，即選擇第j個特征xj和它的取值s将輸入空間劃分為兩部分，然後重複這個操作。
而如何找到最優的j和s是通過比較不同的劃分的誤差來得到的。
一個輸入空間的劃分的誤差是用真實值和劃分區域的預測值的最小二乘來衡量的，即
舉個例子，我們要對南京市各地區的房價進行回歸預測，我們将輸入空間不斷的按最小誤差進行劃分，得到類似下圖的結果，将空間劃分後，我們會用該單元内的均值作為該單元的預測值，如圖中一片區域的平均房價作為該劃分單元内房價的預測值。
3、決策樹的剪枝
剪枝是決策樹學習過程中處理過拟合的方法，剪枝分為預剪枝和後剪枝。
預剪枝是在生成過程中，對節點進行估計，如果目前劃分不能提升系統的泛化能力，則停止分割。
後剪枝是先生成一顆完整的樹，自底向上對非葉節點進行考察，如果該葉節點替換成的子樹能帶來泛化性能的提升，則用該節點替換為葉節點。