03-機器學習-決策樹-Decision Tree
決策樹：
決策樹（decision tree）是一個樹結(jié)構(gòu)（可以是二叉樹或非二叉樹）。其每個非葉節(jié)點表示一個特征屬性上的測試，每個分支代表這個特征屬性在某個值域上的輸出，而每個葉節(jié)點存放一個類別。使用決策樹進行決策的過程就是從根節(jié)點開始，測試待分類項中相應的特征屬性，并按照其值選擇輸出分支，直到到達葉子節(jié)點，將葉子節(jié)點存放的類別作為決策結(jié)果。
構(gòu)建樹的原則
我們構(gòu)建一棵決策樹的基本想法就是，我們希望決策樹每個葉子節(jié)點包含的樣本盡可能屬于同一個類別，即結(jié)點的“純度”越來越高
決策樹劃分選擇的方法
根據(jù)構(gòu)建樹的原則來看，即使得每個結(jié)點的純度盡可能小，那么我們需要一些指標評價“純度”這個概念。信息熵和基尼指數(shù)是兩個常用的指標。
決策樹算法
1、熵(Entropy)
信息熵(information entropy)是度量樣本集合純度的常用指標；
在信息論與概率統(tǒng)計中，熵是表示隨機變量不確定性的度，熵越大，隨機變量的不確定性就越大，反之則不確定性越??；
假定當前樣本集合D中第k類樣本所占的比例為 pk(k=1,2,…,|Y|) ,則D的信息熵為:
Ent(D)的值越小，D的純度越高(約定：若p=0則plog2p=0)
數(shù)據(jù)集：
2、信息增益(Information Gain)
一般而言，信息增益越大，則意味著用屬性a來進行劃分所獲得的純度提升越大：
ID3就是以信息增益為準則來選擇劃分屬性的
舉例：
3、增益率
實際上，信息增益對可取值數(shù)目較多的屬性有所偏好(如編號，在西瓜集中若以編號為劃分屬性，則其信息增益最大)，為減少由于偏好而帶來的不利影響，C4.5算法使用增益率(gain ratio)來選擇最優(yōu)劃分屬性:
其中：
稱為屬性a的固有值(intrinsic value),屬性a的可能數(shù)目越多，則IV(a)的值通常越大
信息增益率準則對可取值數(shù)目較少的屬性有所偏好，
C4.5采用的是先從候選劃分屬性中尋找出信息增益率最高的屬性
舉例：
4、基尼指數(shù)（Gini Index）
CART(Classification and Regression Tree)使用基尼指數(shù)(Gini index)來選擇劃分屬性，數(shù)據(jù)集的純度可用基尼值來度量
屬性a的基尼指數(shù)定義為：
在屬性集合A中尋找:
CART決策樹使用基尼指數(shù)作為屬性劃分的標準
我們使用色澤屬性進行舉例，計算此時的基尼指數(shù)：
5、剪枝處理
剪枝(pruning)是決策樹學習算法對付過擬合的主要手段，基本策略有預剪枝(prepruning)和后剪枝(post-pruning)
預剪枝：在決策樹的生成過程中，對每個節(jié)點在劃分前先進行估計，若當前節(jié)點的劃分不能帶來泛化性能提升則停止劃分
后剪枝：先生成一個完整的樹，然后自底向上對非葉節(jié)點考察，若將該節(jié)點對應的子數(shù)替換為葉節(jié)點能提升泛化性能則替換
5.1 預剪枝
預剪枝的關鍵在于是否繼續(xù)進行劃分：
在上面的西瓜的例子當中，在劃分前，我們將其類別標記為訓練樣例最多的類別“好瓜”。那么在驗證集用“臍部”這個結(jié)點進行劃分，則編號{4,5,8}被劃分正確，其劃分進度為 3/7*100%=42.9%
如果我們使用“臍部”進行劃分,那么圖中②、③和⑥分別包含編號為{1 ， 2 ， 3 ， 14} 、{6 ， 7 ， 15 ， 17} 和{10 ， 16} 的訓練樣例,
因此這3個結(jié)點分別被標記為葉結(jié)點“好瓜”、"好瓜"、"壞瓜"（按其訓練樣例最多類別歸屬），此時，驗證集中編號為{4 ， 5 ， 8 ，11， 12} 的樣例被分類正確，驗證集精度為5/7 x 100% = 71.4% > 42.9%。于是，用"臍部"進行劃分得以確定。
預剪枝使決策樹的很多分支都沒有展開，不僅降低了過擬合的風險，還顯著減少了訓練時間和測試時間，但是可能會引起過擬合
5.2 后剪枝
后剪枝通常比預剪枝保留更多的分值，一般情況下，后剪枝欠擬合風險很小，泛化性能優(yōu)于預剪枝，但其訓練時間比未剪枝和預剪枝都要大得多
我們基于信息增益算法進行劃分決策樹，最后在驗證集的劃分精度為42.9%，我們基于這顆完整的樹進行后剪枝
我們先考慮結(jié)點6 “紋理”，將其替換為葉結(jié)點，替換后的結(jié)點包含樣本{7，15}，因此將其標記為“好瓜”，則此時決策樹在驗證集的精度提升至57.1%，因此進行剪枝
連續(xù)與缺失值
連續(xù)值處理
在C4.5決策樹算法當中，使用二分法對連續(xù)的數(shù)值進行處理：我們可以考察包含n-1個元素的候選劃分點集合
我們將每個區(qū)間的中位點作為候選劃分點，然后我們使用想離散值屬性一樣來考察這些劃分點，選取最優(yōu)的劃分點進行樣本集合的劃分，例如：
對上圖表格當中的例子而言，設置密度為：
根據(jù)Gain的計算公式可以得到屬性”密度“的信息增益位0.262，對應于劃分點0.381。同時按照之前的離散值的計算方法，計算離散屬性的信息增益的值：
Gain(D ，色澤) = 0.109; Gain(D ，根蒂) = 0.143;
Gain(D ，敲聲) = 0.141; Gain(D ，紋理) = 0.381;
Gain(D ，臍部) = 0.289; Gain(D ， 觸感) = 0.006;
Gain(D ，密度) = 0.262; Gain(D ，含糖率) = 0.349.
可以發(fā)現(xiàn)紋理的信息增益是最大的，所以我們選擇”紋理“作為根節(jié)點作為劃分屬性，然后每個結(jié)點劃分過程遞歸進行，最終生成如圖所示的決策樹：
缺失值的處理
一些數(shù)據(jù)由于敏感等原因，部分數(shù)據(jù)可能會出現(xiàn)缺失的情況，例如下面的情況：
在決策樹的C4.5算法當中，我們使用了沒有缺失值的樣本子集進行樹的構(gòu)建。以上述表格為例子舉例，沒有缺失值的樣例子集包含編號為{2，3，4，6，7，8，9，10，11，12，14，15，16，17}的14個樣例（總共有17個樣例）。那么相應的信息熵為：
那么在樣本集上的”色澤“的信息增益為，要乘以其沒有缺失的樣例數(shù)量除以全部的樣例數(shù)量：
因此在樣本子集上，其信息增益為：
那么在樣本集上的”色澤“的信息增益為，要乘以其沒有缺失的樣例數(shù)量除以全部的樣例數(shù)量：
在上述文章提及的變量為，其中每個樣本的權(quán)重wk為1：
決策樹算法優(yōu)缺點
優(yōu)點：
決策樹具有高度可解釋性；
需要很少的數(shù)據(jù)預處理；
適用于低延遲應用。
劣勢：
很可能對噪聲數(shù)據(jù)產(chǎn)生過擬合。決策樹越深，由噪聲產(chǎn)生過擬合的可能性就越大。一種解決方案是對決策樹進行剪枝。
代碼演示-Decision Tree
數(shù)據(jù)集 iris
sklearn
可視化決策樹插件 Download：https://graphviz.org/download/
決策樹插件安裝文檔：https://blog.csdn.net/u012744245/article/details/103360769
決策樹示意圖：
