決策樹：
決策樹（decision tree）是一個樹結構（可以是二叉樹或非二叉樹）。其每個非葉節點表示一個特徵屬性上的測試，每個分支代表這個特徵屬性在某個值域上的輸出，而每個葉節點存放一個類別。使用決策樹進行決策的過程就是從根節點開始，測試待分類項中相應的特徵屬性，並按照其值選擇輸出分支，直到到達葉子節點，將葉子節點存放的類別作為決策結果。
構建樹的原則
我們構建一棵決策樹的基本想法就是，我們希望決策樹每個葉子節點包含的樣本儘可能屬於同一個類別，即結點的「純度」越來越高
決策樹劃分選擇的方法
根據構建樹的原則來看，即使得每個結點的純度儘可能小，那麼我們需要一些指標評價「純度」這個概念。信息熵和基尼指數是兩個常用的指標。
決策樹算法
1、熵(Entropy)
信息熵(information entropy)是度量樣本集合純度的常用指標；
在資訊理論與概率統計中，熵是表示隨機變量不確定性的度，熵越大，隨機變量的不確定性就越大，反之則不確定性越小；
假定當前樣本集合D中第k類樣本所占的比例為 pk(k=1,2,…,|Y|) ,則D的信息熵為:
()=−∑=1||2���(�)=−∑�=1|�|�����2��
Ent(D)的值越小，D的純度越高(約定：若p=0則plog2p=0)
數據集：
2、信息增益(Information Gain)
一般而言，信息增益越大，則意味著用屬性a來進行劃分所獲得的純度提升越大：
ID3就是以信息增益為準則來選擇劃分屬性的
舉例：
3、增益率
實際上，信息增益對可取值數目較多的屬性有所偏好(如編號，在西瓜集中若以編號為劃分屬性，則其信息增益最大)，為減少由於偏好而帶來的不利影響，C4.5算法使用增益率(gain ratio)來選擇最優劃分屬性:
其中：
稱為屬性a的固有值(intrinsic value),屬性a的可能數目越多，則IV(a)的值通常越大
- 信息增益率準則對可取值數目較少的屬性有所偏好，
- C4.5採用的是先從候選劃分屬性中尋找出信息增益率最高的屬性
舉例：
4、基尼指數（Gini Index）
CART(Classification and Regression Tree)使用基尼指數(Gini index)來選擇劃分屬性，數據集的純度可用基尼值來度量
屬性a的基尼指數定義為：
在屬性集合A中尋找:
CART決策樹使用基尼指數作為屬性劃分的標準
我們使用色澤屬性進行舉例，計算此時的基尼指數：
5、剪枝處理
剪枝(pruning)是決策樹學習算法對付過擬合的主要手段，基本策略有預剪枝(prepruning)和後剪枝(post-pruning)
- 預剪枝：在決策樹的生成過程中，對每個節點在劃分前先進行估計，若當前節點的劃分不能帶來泛化性能提升則停止劃分
- 後剪枝：先生成一個完整的樹，然後自底向上對非葉節點考察，若將該節點對應的子數替換為葉節點能提升泛化性能則替換
5.1 預剪枝
預剪枝的關鍵在於是否繼續進行劃分：
- 在上面的西瓜的例子當中，在劃分前，我們將其類別標記為訓練樣例最多的類別「好瓜」。那麼在驗證集用「臍部」這個結點進行劃分，則編號{4,5,8}被劃分正確，其劃分進度為 3/7*100%=42.9%
- 如果我們使用「臍部」進行劃分,那麼圖中②、③和⑥分別包含編號為{1 ， 2 ， 3 ， 14} 、{6 ， 7 ， 15 ， 17} 和{10 ， 16} 的訓練樣例,
- 因此這3個結點分別被標記為葉結點「好瓜」、"好瓜"、"壞瓜"（按其訓練樣例最多類別歸屬），此時，驗證集中編號為{4 ， 5 ， 8 ，11， 12} 的樣例被分類正確，驗證集精度為5/7 x 100% = 71.4% > 42.9%。於是，用"臍部"進行劃分得以確定。
預剪枝使決策樹的很多分支都沒有展開，不僅降低了過擬合的風險，還顯著減少了訓練時間和測試時間，但是可能會引起過擬合
5.2 後剪枝
後剪枝通常比預剪枝保留更多的分值，一般情況下，後剪枝欠擬合風險很小，泛化性能優於預剪枝，但其訓練時間比未剪枝和預剪枝都要大得多
- 我們基於信息增益算法進行劃分決策樹，最後在驗證集的劃分精度為42.9%，我們基於這顆完整的樹進行後剪枝
- 我們先考慮結點6 「紋理」，將其替換為葉結點，替換後的結點包含樣本{7，15}，因此將其標記為「好瓜」，則此時決策樹在驗證集的精度提升至57.1%，因此進行剪枝
連續與缺失值
連續值處理
在C4.5決策樹算法當中，使用二分法對連續的數值進行處理：我們可以考察包含n-1個元素的候選劃分點集合
我們將每個區間的中位點作為候選劃分點，然後我們使用想離散值屬性一樣來考察這些劃分點，選取最優的劃分點進行樣本集合的劃分，例如：
對上圖表格當中的例子而言，設置密度為：
根據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.
可以發現紋理的信息增益是最大的，所以我們選擇」紋理「作為根節點作為劃分屬性，然後每個結點劃分過程遞歸進行，最終生成如圖所示的決策樹：
缺失值的處理
一些數據由於敏感等原因，部分數據可能會出現缺失的情況，例如下面的情況：
在決策樹的C4.5算法當中，我們使用了沒有缺失值的樣本子集進行樹的構建。以上述表格為例子舉例，沒有缺失值的樣例子集包含編號為{2，3，4，6，7，8，9，10，11，12，14，15，16，17}的14個樣例（總共有17個樣例）。那麼相應的信息熵為：
其分別在」色澤「屬性上取值為」青綠「，」烏黑「以及」淺白「的樣本子集，那麼有：
因此在樣本子集上，其信息增益為：
那麼在樣本集上的」色澤「的信息增益為，要乘以其沒有缺失的樣例數量除以全部的樣例數量：
在上述文章提及的變量為，其中每個樣本的權重wk為1：
決策樹算法優缺點
優點：
- 決策樹具有高度可解釋性；
- 需要很少的數據預處理；
- 適用於低延遲應用。
劣勢：
- 很可能對噪聲數據產生過擬合。決策樹越深，由噪聲產生過擬合的可能性就越大。一種解決方案是對決策樹進行剪枝。
代碼演示-Decision Tree
- 數據集 iris
- sklearn
- 可視化決策樹插件 Download：https://graphviz.org/download/
- 決策樹插件安裝文檔：https://blog.csdn.net/u012744245/article/details/103360769
# -*- coding: utf-8 -*-
from sklearn.datasets import load_iris
from sklearn import tree
import pydotplus
import os
#用於劃分訓練集與測試集
os.environ["PATH"]+=os.pathsep+'C:/Program Files/Graphviz/bin/' #指定路徑
from sklearn.model_selection import train_test_split
from sklearn.metrics import classification_report
#加載數據
iris = load_iris()
#劃分訓練集與測試集
(training_inputs, testing_inputs, training_classes, testing_classes)=train_test_split(iris.data, iris.target,test_size=0.4, random_state=1)
# 構建模型
clf = tree.DecisionTreeClassifier()
clf = clf.fit(training_inputs, training_classes)
#測試值預測
y_predict = clf.predict(testing_inputs)
#預測值和測試值打分
score = classification_report(testing_classes, y_predict)
print(score)
# 保存模型
with open("iris.dot", 'w') as f:
f = tree.export_graphviz(clf, out_file=f)
# 畫圖，保存到pdf文件
# 設置圖像參數
dot_data = tree.export_graphviz(clf, out_file=None,
feature_names=iris.feature_names,
class_names=iris.target_names,
filled=True, rounded=True,
special_characters=True)
graph = pydotplus.graph_from_dot_data(dot_data)
# 保存圖像到pdf文件
graph.write_pdf("irsi.pdf")決策樹示意圖：