作為機器學習中可解釋性非常好的一種算法，決策樹(Decision Tree)是在已知各種情況發生機率的基礎上，通過構成決策樹來求取淨現值的期望值大于等于零的機率，評價項目風險，判斷其可行性的決策分析方法，是直覺運用機率分析的一種圖解法。由于這種決策分支畫成圖形很像一棵樹的枝幹，故稱決策樹。在機器學習中，決策樹是一個預測模型，他代表的是對象屬性與對象值之間的一種映射關系。
一、初識決策樹
決策樹是一種樹形結構，一般的，一棵決策樹包含一個根結點，若幹個内部結點和若幹個葉結點：
葉結點：樹的一個方向的最末端，表示結果的輸出；
根結點：初始樣本全體；
内部結點：每個内部結點對應一個屬性測試（即一次決策）
從根結點——每個葉結點，形成各條判定序列；我們的進行決策樹分類器訓練的學習目的是産生一棵泛化能力強，即處理未見示例能力強的決策樹，其基本流程遵循“分而治之”的政策：
算法過程：
Step1：輸入樣本集D{(x1,y1),(x2,y2),...,(xn,yn)}，屬性集A{a1,a2,...,ad}，全體樣本集儲存在根結點中；
Step2：從屬性集A中經過一定的規則（具體規則由算法決定）挑選出一個最佳屬性a1,所有樣本從根結點流向該決策結點，根據樣本在a1這個屬性上的取值，流向對應的方向（如下圖）：
在樣本集通過某個屬性判斷，确定不同的流向後，會有以下幾種情況:
1.流向某個方向的所有樣本隻存在一個類别y0，這時把這個方向标記為葉結點，即最終從這個方向流出的樣本都可直接判定為類别y0；
2.通過目前屬性判斷後，某個方向沒有樣本流出，這通常是樣本量不夠多導緻的樣本多樣性不足，這時可以将這方向标記為葉結點，将訓練集中各類别的比例作為先驗機率，将所有從這個方向流出的新樣本都标記為先驗機率最大的那個類别；
3.在某個屬性判斷上，所有訓練樣本都取同一個值，和情況2相似，也是在其他可能方向上無訓練樣本流出，在對新樣本處理時方法同2；
Step3：通過Step2的過程将所有屬性利用完之後，形成了一棵完整的樹，其每個判斷路徑上都經過了所有屬性，這時對所有的葉結點規定輸出類别為訓練過程中到達該葉結點中的樣本中比例最大（即利用了先驗分布）的那一類，至此，一棵決策樹訓練完成。
二、訓練過程屬性的選擇
現在我們知道了決策樹的訓練過程，但對于哪一個屬性放在第一位，哪個放在第二位以此類推，還依然不知曉，這就是決策樹中非常重要也非常巧妙的一點——劃分選擇；
劃分選擇：決策樹學習的關鍵是如何選擇最優劃分屬性，我們希望随着劃分過程不斷進行，決策樹的分支結點所包含的樣本盡可能屬于同一類别，即結點的純度（purity）越來越高，下面我們介紹幾種不同的衡量樣本純度的規則，他們也分别産生了不同的決策樹算法：
1.資訊增益
在定義資訊增益之前，我們先介紹以下概念：
資訊熵（information entropy）：
度量樣本集合純度最常用的一種名額，假定目前樣本集合D中第k類樣本所占的比例為pk(k=1,2,...,|y|)，則D的資訊熵定義為：
其中|DV|指D中在a屬性取aV的樣本數量，則|DV| / |D|可看作在aV方向上的權重；
*原則：資訊增益越大，意味着使用a屬性進行劃分所劃得的“純度提升”最大，即目前最優劃分為：
2.增益率
有些時候，若樣本集中含有“編号”這種使得分支結點純度遠大于其他有效屬性的非有效屬性（因為編号會将每一個樣本獨立分開），導緻各個編号的分支能變成葉結點（對應特殊情況中的1），這樣的決策樹顯然不具有泛化能力，無法對新樣本進行預測，即，這種情況下資訊增益準則對可取值數目較多的屬性有所偏好，為減少這種偏好可能帶來的不利影響，下面引入：
C4.5算法：
不直接使用資訊增益，而是使用“增益率”來選擇目前最優劃分屬性；
增益率定義為：
叫做屬性a的固有值，屬性a的可能取值數目越大（即V越大），則IV(a)的值通常會越大；與資訊增益相比，增益率對屬性取值數目較少的屬性有偏好，是以C4.5算法并不直接以所有屬性的增益率作為比較依據，而是有一個啟發式的過程：先選擇候選劃分屬性中資訊增益高于平均水準的屬性，再從中選擇增益率最高的。
3.基尼系數
CART決策樹（Classfication and Regression Tree）使用基尼指數來選擇劃分屬性，則資料D的純度可用基尼值來度量：
三、剪枝處理
在決策樹學習中，為了盡可能正确分類訓練樣本，結點劃分過程不斷重複，有時會造成決策樹分支過多，這時就可能因訓練集過度學習，以緻于把訓練集本身的一些特點當作所有資料都具有的一般性質，進而導緻過拟合。
通過主動去掉一些分支來降低過拟合的風險的過程就叫做剪枝。
決策樹剪枝的基本政策：
1.預剪枝（prepruning）
在決策樹生成過程中，對每個結點在劃分前先進行性能估計，若目前結點的劃分不能帶來決策樹泛化性能的提升，則停止劃分并将目前結點标記為葉結點；
2.後剪枝（post-pruning）
先從訓練集生成一棵完整的決策樹，然後自底向上地對非葉結點進行考察，若将該結點對應的子樹替換成葉結點能帶來決策樹泛化能力提升，則将該子樹替換成葉結點。
預剪枝：
步驟：
Step1：為衡量泛化能力，利用留出法，劃分樣本集為訓練集和驗證集；
Step2：根據資訊增益準則，選出a*作為根結點下第一個非葉結點，分别訓練通過這一屬性進行分類的模型，和将該結點作為葉結點的模型，比較這兩個模型在驗證集上的正确率，選擇更優的方案；
Step3：重複Step2對所有屬性進行考察，直到最終決策樹完成；
*僅有一層劃分的決策樹稱為“決策樹樁”（decision stump）
原則：剪去（淘汰）正确率小于或等于目前正确率（即目前最高正确率）的分支操作；
優點：預剪枝使得決策樹的很多分支沒有展開，降低了模型過拟合的風險，還顯著減少了決策樹的訓練時間開銷和測試時間開銷；
缺點：有些分支的目前劃分雖不能提升泛化能力，甚至可能導緻泛化能力暫時下降，但在其基礎上進行的後續劃分卻有可能導緻性能顯著提升；
預剪枝基于“貪心”本質禁止這些分支展開，隻關心目前性能表現，給預剪枝決策樹模型帶來了欠拟合的風險。
後剪枝：
Step1：對于不經任何剪枝處理，僅依據某個資訊純度評價方法最終形成的一棵完整的使用了所有屬性的決策樹，從其最靠後的非葉結點開始，分别訓練不剪去該結點和剪去該結點時的模型，比較泛化能力；
Step2：若泛化能力得到了提高，則采取相應的模型變更/維持原狀操作；
Step3：重複上述過程直到所有非葉結點完成剪枝效果評估。
原則：若剪枝後正确率得到提高，則采取剪枝操作，否則不變；
優點：欠拟合風險很小，泛化能力往往優于預剪枝決策樹；
缺點：後剪枝過程是在生成完全決策樹之後進行的，并且需自底向上對樹中所有非葉結點進行逐一考察後，是以訓練時間開銷巨大。
以上就是決策樹算法的一些基本常識，下面我們分别在Python和R中實作決策樹算法：
四、Python
我們利用sklearn子產品中的tree下屬的DecisionTreeClassifier()進行決策樹分類，關于其細節在sklearn的官網中有詳細介紹：http://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html#sklearn.tree.DecisionTreeClassifier，下面我們對其主要參數進行介紹：
criterion : 字元型，用來确定劃分選擇依據的算法，有對應CART樹算法的“gini”和對應ID3算法的“entropy”，預設為“gini”
splitter : 字元型，用來确定選擇每個屬性判斷結點的方式，依據的是criterion中确定的名額數值，有對應最佳結點的“best”和對應随機選擇的“random”，預設是“best”
max_depth :整型，用來确定決策樹的最大深度（即最多的非葉結點數目規模），預設為None，即不限制深度
min_samples_split :有兩種情況，
1.整型，這時該參數确定用于分割非葉結點的最小樣本數，即如果小于該預設值，則該結點因為資訊不足可以直接根據先驗分布生成為葉結點輸出結果，預設值2；
2.浮點型，這時該參數功能不變，隻是确定的min_samples_split變為min_samples_split*n_samples，這裡代表百分比。
min_samples_leaf :有兩種情況，
1.整型，這時該參數确定用于生成葉結點的最小樣本數，即小于該數值時不可生成葉結點，預設值為1；
2.浮點型，同min_samples_split
min_weight_fraction_leaf :浮點型，該參數用于确定每個樣品的權重，在最終在葉結點産生結果時起作用，主要用于類别不平衡時的再縮放操作，預設每個樣品權重相等；
max_features : 該參數用于确定每一次非葉結點屬性劃分時使用到的屬性數目（在資訊增益和基尼指數的計算中起作用），預設使用全部屬性，有以下幾種情況：
1.整型，這時傳入的整數即為每次分割時考慮的最大屬性數；
2.浮點型，這時最大屬性數是該浮點參數*屬性總數；
3.字元型，“auto”時，最大屬性數為屬性總數開根号；“sqrt”時，同“auto”；“log2”時，最大屬性數為屬性總數取對數；
4.None，這時最大屬性數即為屬性總數；
max_leaf_nodes : 該參數用于确定最終的決策樹模型的最大葉結點數量，預設為無限制，即None
class_weight :用于處理類别不平衡問題的權重，建議使用“balanced”，即自動根據先驗分布賦權，預設為None，即忽略權重，每一類同等看待
以上就是sklearn.tree.DecisionTreeClassifier的主要參數介紹，下面我們以kaggle playground中的泰坦尼克号遇難者資料作為示範資料對生還與否進行二分類：
資料說明：
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split
import pandas as pd
import numpy as np
'''讀入資料'''
raw_train_data = pd.read_csv('train.csv')
train = raw_train_data.dropna()
target_train = train['Survived'].tolist()
#Ticket class
pclass = train['Pclass'].tolist()
sex = train['Sex'].tolist()
Sex = []
for i in range(len(sex)):
if sex[i] == 'male':
Sex.append(1)
else:
Sex.append(0)
age = train['Age'].tolist()
#在船上兄弟姐妹的數量
SibSp = train['SibSp'].tolist()
#在船上父母或孩子的數量
Parch = train['Parch'].tolist()
Fare = train['Fare'].tolist()
#登船的港口
Embarked = train['Embarked'].tolist()
sabor_C = []
sabor_Q = []
#為登船港口設定啞變量
for i in range(len(Embarked)):
if Embarked[i] == 'C':
sabor_C.append(1)
sabor_Q.append(0)
elif Embarked[i] == 'Q':
sabor_Q.append(1)
sabor_C.append(0)
else:
sabor_Q.append(0)
sabor_C.append(0)
'''定義自變量與目标'''
train_ = np.array([Sex,age,sabor_C,sabor_Q]).T
target_ = np.array(target_train)
'''重複多次随機分割樣本集的訓練取正确率平均值'''
S = []
for i in range(1000):
X_train, X_test, y_train, y_test = train_test_split(train_, target_, test_size=0.3)
clf = DecisionTreeClassifier(class_weight='balanced',max_depth=2)
clf = clf.fit(X_train,y_train)
S.append(clf.score(X_test,y_test))
'''列印結果'''
print('平均正确率：'+str(np.mean(S))) 訓練效果：
利用訓練好的模型不僅可以輸出新樣本值類别的預測值，還可以輸出對應的機率，這個機率即是葉結點的先驗分布：
'''列印對應預測類别的機率'''
clf.predict_proba(X_test) 我們都知道決策樹是利用與各坐标軸平行的線段拼湊而成組成決策邊界來劃分樣本點，在自變量個數不多時我們可以繪制出決策邊界的示意圖來加強可解釋性，下面以鸢尾花資料為例：
print(__doc__)
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier
# Parameters
n_classes = 3
plot_colors = "ryb"
plot_step = 0.02
# Load data
iris = load_iris()
for pairidx, pair in enumerate([[0, 1], [0, 2], [0, 3],
[1, 2], [1, 3], [2, 3]]):
# 對變量中所有兩兩變量間進行比對
X = iris.data[:, pair]
y = iris.target
# Train
clf = DecisionTreeClassifier().fit(X, y)
# 繪制決策邊界
plt.subplot(2, 3, pairidx + 1)
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, plot_step),
np.arange(y_min, y_max, plot_step))
plt.tight_layout(h_pad=0.5, w_pad=0.5, pad=2.5)
Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
cs = plt.contourf(xx, yy, Z, cmap=plt.cm.RdYlBu)
plt.xlabel(iris.feature_names[pair[0]])
plt.ylabel(iris.feature_names[pair[1]])
# 繪制訓練樣本點
for i, color in zip(range(n_classes), plot_colors):
idx = np.where(y == i)
plt.scatter(X[idx, 0], X[idx, 1], c=color, label=iris.target_names[i],
cmap=plt.cm.RdYlBu, edgecolor='black', s=15)
plt.suptitle("Decision surface of a decision tree using paired features")
plt.legend(loc='lower right', borderpad=0, handletextpad=0)
plt.axis("tight")
plt.show() 五、R
在R中使用決策樹相關算法有一個很大的友善之處，就是在對決策樹可視化的時候，我們都知道決策樹是一種解釋性很強的機器學習算法，這是它被廣泛使用的一個原因之一，在R中繪制決策樹非常友善；在R中，一棵決策樹的初步生成與剪枝是使用兩個不同的函數進行操作的，我們這裡使用rpart包來建立分類樹，其中rpart()函數建立決策樹，prune()函數用來進行樹的剪枝，具體參數如下：
對rpart():
formula：這是R中很多算法的輸入格式，用~連接配接左端的target列名稱和右端的自變量列名稱；
data：輸入資料框的名稱；
weights：可選的自定義類别權重，主要在類别不平衡時使用，類似邏輯分類中的再縮放；
na.action：對缺失值進行處理，預設删去target列缺失的樣本，但保留自變量存在缺失的樣本（決策樹中對缺失值較為寬容，有對應的處理方法）
parms：預設為“gini”指數，即CART決策樹分割結點的方法；
control：這是一個非常重要的參數集合，與Python在主體函數中賦參不同，rpart中關于決策樹的調參都集合在這個control參數中，control的指派格式為control=rpart.control()，對于rpart.control可以調節的參數如下：
minspilt：整數，預設為20，表示對節點中樣本進行劃分的最小樣本數，小于這個數目則直接根據先驗分布生成葉結點；
minbucket：整數，預設值為round(minspilt/3)，表示一個門檻值，若目前結點樣本數小于這個門檻值，則生成葉結點；
cp：複雜度，預設0.01；
maxcompete：在每次節點劃分中選擇使用的變量個數，預設為4，用于計算資訊增益名額；
xval：交叉驗證的數量，預設10，即十折交叉驗證；
maxdepth：控制決策樹的最大深度，這個最大深度指的是所有葉結點中距離根結點最遠的距值，是以決策樹樁深度為0；
對prune():
tree：指定先前儲存生成好的決策樹的變量名；
cp：複雜度，預設0.1，用于決定對決策樹裁剪的程度；
下面我們以Fisher的鸢尾花資料進行決策樹分類示範：
> rm(list=ls())
> library(rpart.plot)
> library(rpart)
> #挂載資料
> data(iris)
> data <- iris
> #留出法抽出0.8的訓練集與0.2的測試集
> sam <- sample(1:150,120)
> train_data <- data[sam,]
> test_data <- data[-sam,]
> #訓練決策樹
> dtree <- rpart(Species~.,data=train_data)
> #繪制決策樹複雜度變化情況
> plotcp(dtree)
> #進行剪枝，這裡設定複雜度門檻值為0.01
> dtree.pruned <- prune(dtree, cp=0.01)
> #繪制剪枝後的決策樹模型結構
> prp(dtree.pruned,type=0)
> title('Decision Tree for Iris Data')
> #對驗證集代入訓練好的模型進行預測
> dtree.pred <- predict(dtree.pruned,test_data[,1:4],type='class')
> #列印混淆矩陣
> (dtree.perf <- table(test_data[,5],dtree.pred))
dtree.pred
setosa versicolor virginica
setosa 10 0 0
versicolor 0 10 2
virginica 0 0 8 決策樹結構：
可以看出，決策樹在該資料集上的預測效果非常不錯，且隻使用了有效的資料，節省了計算時間成本。
六、關于決策樹實踐中的建議
本節内容選自sklearn官網決策樹頁面：http://scikit-learn.org/stable/modules/tree.html#tree-classification，由筆者自行摘抄翻譯：
1.決策樹在應對高維資料時很容易過拟合，是以保持自變量個數和樣本個數間的比例非常重要，其實不管是對什麼預測算法，當樣本個數接近自變量個數時都容易發生過拟合；
2.可以考慮對自變量進行維數約簡，或進行特征選擇，以最大程度保留較少更有說服力的自變量，以盡量減少過拟合的風險；
3.多使用決策樹結構的可視化方法，可以幫助你了解你目前樹的生長效果，也可以更好的與現實業務聯系起來進行解釋；
4.樹的深度（即距離最遠的葉結點對應距離根結點的距離）初始化設定為3較好，再逐漸增長該參數，觀察訓練效果的變化情況，以作出最好的選擇，以及控制過拟合情況；
5.使用min_samples_spilt或與其等價的參數來控制生成葉結點時的樣本個數下限，因為通常該參數越小，樹過拟合的風險都越大，是以盡早生成葉結點可以緩解對樣本資料獨特性的放大，進而減少過拟合風險；
6.在訓練之前盡量平衡類别間的比例，以避免訓練結果因為類别的嚴重不平衡而産生虛假結果（比如樣本中9個正例1個反例，訓練出的模型全部歸類為正例也能取得90%的正确率，但這不可靠），或者調節sample_weight來對所有類别進行再縮放；
以上就是決策樹的基本知識，若有筆誤，請指出。