背景與原理：

決策樹算法是在各種已知情況發生概率的基礎上通過構成決策樹來求某一事件發生概率的算法，由于這個過程畫成圖解之后很像一棵樹形結構，因此我們把這個算法稱為決策樹。

而在機器學習中，決策樹是一種預測模型，代表對象屬性和對象值之間的一種映射，一棵決策樹的每個內部節點會處理數據的某個維度對應的變量，根據這個變量的取值向下進行分支，直到走到葉節點，每個葉節點代表輸入對應的一個最終輸出。

決策樹生成算法有很多種，比如ID3,C4.5和C5.0等，這里使用ID3實現方法。

決策樹直觀上很好理解，比如已知小明在晴天有空的時候去跑步的概率是90%，那么現在如果想預測小明是否會去跑步，那么我們首先觀察是否是晴天，這就產生了“是晴天”和“不是晴天”兩個分支，而對于“是晴天”的分支我們再觀察小明是否有空，這就產生了“有空”和“沒空”兩個分支，最后在“有空”這個分支我們已經找到了葉節點，發現小明去跑步的概率為90%，那我們就作出預測小明會去跑步。而對于其余的分支我們需要更多信息才能做出預測。

而對于決策樹而言，最重要的是要選擇每個節點處理哪個屬性。在上述例子中可能沒有體現，我們先觀察是否是晴天和先觀察是否有空對整個決策過程沒有影響，但是如果我們再加入一個條件“小明在沒空的時候一定不會去跑步（都沒空了跑什么步）”，那此時如果我們先觀察是否是晴天，我們仍然需要在每個分支里都觀察小明是否有空，而如果我們先觀察小明是否有空，那么在小明沒空的時候，我們不需要觀察是否是晴天就可以作出預測：小明不會去跑步！也就是說對于“有空”這個分支，我們才需要繼續向下分支，而對于“沒空”這個分支，我們直接到達了葉節點——“不去跑步”！

上述分析實際上體現了“熵”的思想：嚴格地：對于一個有$n$個取值$x_{1},...,x_{n}$的隨機變量$X$，那么定義其熵值為$H(X)=-\sum_{i=1}^{n}P(X=x_{i})\log_{b}P(X=x_{i})$，這里的$b$通常取$2,e,10$

我們說“信息”是用來消除“不確定性”的東西，而熵則是用來度量不確定性的量（比如如果一個隨機變量只有一個取值，那么這個隨機變量也就不再隨機了，不確定性為0，其熵值也是0）。因此我們可以認為一個信息的出現如果造成的熵減越大，那么這個信息的信息量越大。

所以對一個樣本集$T$，其原始的熵為$H(T)$，而當我們已知一個特征$X$的信息時，假設$X$有$n$個取值$x_{1},...,x_{n}$，我們定義條件熵$H(T|X)=\sum_{i=1}^{n}P(X=x_{i})H(T|X=x_{i})$，其中$H(T|X=x_{i})$是計算$T$在$X=x_{i}$下概率分布的熵，比如雖然原始的$T$可能有100種取值，但是當我們已知$X=x_{i}$時，$T$只會有一種取值，這樣的話$H(T|X=x_{i})=0$

這樣我們就可以非常自然地定義信息增益$IG(T,X)=H(T)-H(T|X)$，表示當我們引入條件$X$后消除了多少不確定性，而我們在每個節點上要選取的特征就是在當前能選取的特征中消除的不確定性最多的特征，即使$IG(T,X)$最大的$X$

代碼實現：

import numpy as np
from sklearn import tree
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
import matplotlib.pyplot as plt
from sklearn.datasets import load_iris
import graphviz

data=load_iris()
X=data.data
Y=data.target

X_train,X_test,Y_train,Y_test=train_test_split(X,Y,test_size=0.25)

clf=DecisionTreeClassifier(criterion="entropy")
clf=clf.fit(X_train,Y_train)

dot_data = tree.export_graphviz(clf,feature_names= ['f1','f2','f3','f4'],class_names=["class1","class2","class2"],filled=True,rounded=True,out_file=None)
graph = graphviz.Source(dot_data)
score_=clf.score(X_test, Y_test)
print(score_)
graph

這是對于鳶尾花數據集用決策樹分類的效果，這里的決策樹直接調了sklearn里的包，同時引用了graphviz包來做可視化（這個包的使用很復雜，建議在jupyter里運行上述代碼，不然可視化不太容易），而score是用來衡量分類效果的，這里的score得分還不錯。

小結與優化：

決策樹算法的一個問題在于可能出現過擬合——如果有一個特征的取值多到了可以直接根據這個特征分支出所有的類，那么上面的算法會很高興地建立這樣的決策樹，但是這樣的決策樹的泛化效果就會變得很差，因此在上述訓練過程中，可以加入參數random_state和splitter來控制決策樹的隨機模式，通過合理選擇模式降低對訓練集的擬合，從而一定程度上提高模型的泛化性能，同樣在原理層面可以把特征選取原則由信息增益變為信息增益率，通過增加一定的懲罰項減輕過擬合的問題等。

另一個問題是對于特征維度多、數據數量大的數據集決策樹訓練的效率不高，可以通過迭代增益、探索確定的分裂原則等手段進行優化。