1、決策樹學習

有如下數據集：

一般決策樹學習算法是一個遞歸地選擇最優特征并根據特征對訓練數據進行分割，使每個子數據集都有一個最好的分類的過程。算法包括：

step1：特征選擇（根據熵或基尼指數選擇特征）

step2：決策樹生成（有ID3、C4.5、CART算法等）

step3：剪枝（防止過擬合）

2、特征選擇——基于信息熵

2.1熵

在信息論中，熵代表的意思是隨機變量不確定性的度量。簡單的說，有容量為100的數據集，特征A可以將數據集分為80容量和20容量的兩類，而特征B將數據集分為50容量和50容量的兩類，則特征A的信息熵要小于特征B的，因為A可以比較明確地將數據集分類，B并沒有明確地將數據集分類。因此A的不確定性小，即熵小。

設X是一個取有限個值的離散隨機變量，其概率分布為：

則隨機變量X的熵為：

若Pi=0，則定義0log0=0。熵越大隨機變量的不確定性越大。

設隨機變量(X|Y)，其聯合概率分布為：

隨機變量X給定條件下隨機變量Y的條件熵H(X|Y)定義為，X給定條件下Y的條件概率分布的熵對X的數學期望：

當熵和條件熵中的概率由數據估計得到時，則稱兩者為經驗熵和經驗條件熵。

2.2信息增益

信息增益表示得到特征X后使得類Y的信息不確定性減少的程度。信息增益越大，不確定性減少的程度越大。特征A對訓練集D的信息增益g(D,X)定義為集合D的經驗熵H(D)與特征X給定條件下的經驗條件熵H(D|X)之差，即：

本文所示例的ID3算法即是根據信息增益選擇特征的。對于訓練集D，計算每個特征的信息增益，選擇增益最大的特征。

2.3信息增益比

特征X對訓練數據集D的信息增益比gR(D,A)定義為信息增益與g(D,A)與訓練數據集D關于特征A的熵HA(D)之比：

其中，n為特征A取值的個數

3、決策樹生成

3.1   ID3算法

從根節點開始，對結點計算所有可能特征的信息增益，選擇信息增益最大的特征作為根節點，由改特征的不同取值對數據進行分類建立子節點。再對子節點遞歸地使用以上方法，建立決策樹，直到所有特征的信息增益均很小或沒有特征為止。

Python代碼示例——使用Scikit-Learn建立決策樹

數據集：將文章開頭的數據拷到一個Excel表格中即可，與py文件同目錄

源代碼：

#-*- coding: utf-8 -*-import pandas as pdinputfile = 'E:/Machine_Learning/Code/decision tree ID3/data.xls'    #數據文件路徑data = pd.read_excel(inputfile, index_col = u'序號')                         #導入數據#數據文件是excel表格，需要將標簽變為數據#用1表示好、是、高，用-1表示壞、否、低data[data == u'好'] = 1data[data == u'是'] = 1data[data == u'高'] = 1data[data != 1] = -1x = data.iloc[:,:3].as_matrix().astype(int)y = data.iloc[:,3].as_matrix().astype(int)from sklearn.tree import DecisionTreeClassifier as DTCdtc = DTC(criterion='entropy')                #建立決策樹模型，基于信息熵dtc.fit(x, y)                                  #訓練模型#導入相關函數，可視化決策樹。from sklearn.tree import export_graphvizx = pd.DataFrame(x)with open("tree.dot", 'w') as f:  f = export_graphviz(dtc, feature_names = x.columns, out_file = f)最后在目錄下生成一個dot文件，這是一個可視化的文件，需要安裝Graphviz軟件才可以查看，可轉為pdf或圖片格式。打開是如下效果：
3.2   C4.5算法
與ID3算法類似，不同的是C4.5使用信息增益比來選擇特征。
4、剪枝
決策樹在學習的過程中會產生過擬合現象，即過多地考慮提高訓練數據的正確分類，從而構造出復雜的決策樹。這時需要將生產的決策樹進行簡化，即剪枝。關于剪枝會在接下來的文章里闡述。