決策樹的學(xué)習(xí)算法包特征選擇、決策樹的生成與決策樹的剪枝過程杖小。
決策樹學(xué)習(xí)應(yīng)用信息增益準則選擇特征睬魂。信息增益大的特征具有更強的分類能力。
1烛愧、特征選擇問題。
特征選擇是決定用哪個特征來劃分特征空間掂碱。選擇具有分類能力的特征可以調(diào)高決策樹的學(xué)習(xí)的效率怜姿。
熵：表示隨機變量不確定性的度量，單位是比特疼燥。熵越大社牲，隨機變量的不確定性越大。
經(jīng)驗熵和條件經(jīng)驗熵：當(dāng)熵和條件熵中的概率由數(shù)據(jù)估計（特別是極大似然估計）得到時悴了，所對應(yīng)的熵與條件熵分別稱為經(jīng)驗熵和條件經(jīng)驗熵。
決策樹與條件概率分布违寿？
決策樹分類時將該結(jié)點的實例強行分到條件概率大的那一類去湃交。
什么是信息增益？信息增益：表示得知特征Ｘ的信息而使得類Ｙ的信息的不確定性減少的程度藤巢。根據(jù)信息增益準則的特征選擇方法是：對訓(xùn)練數(shù)據(jù)集(或子集)D搞莺，計算其每個特征的信息增益，并比較它們的大小掂咒，選擇信息增益最大的特征才沧。
2、決策樹ID3算法（信息增益）
ID3算法與用極大似然法進行概率模型選擇類似绍刮。
決策樹ID3算法-流程
1温圆、決定分類屬性；
2 孩革、對目前的數(shù)據(jù)表岁歉， 建立一個節(jié)點N
3 、如果數(shù)據(jù)庫中的數(shù)據(jù)都屬于同一個類膝蜈， N就是樹葉锅移， 在樹葉上標出所屬的類
4 、如果數(shù)據(jù)表中沒有其他屬性可以考慮饱搏， 則N也是樹葉非剃， 按照少數(shù)服從多數(shù)的原則在樹葉上標出所屬類別
5 、否則推沸， 根據(jù)平均信息期望值E或GAIN值選出一個最佳屬性作為節(jié)點N的測試屬性
6 备绽、節(jié)點屬性選定后券坞， 對于該屬性中的每個值：
從N生成一個分支， 并將數(shù)據(jù)表中與該分支有關(guān)的數(shù)據(jù)收集形成分支節(jié)點的數(shù)據(jù)表疯坤， 在表中刪除節(jié)點屬性那一欄如果分支數(shù)據(jù)表非空报慕， 則運用以上算法從該節(jié)點建立子樹
ID3算法的基本思想是， 以信息熵為度量压怠， 用于決策樹節(jié)點的屬性選擇眠冈， 每次優(yōu)先選取信息量最多的屬性， 亦即能使熵值變?yōu)樽钚〉膶傩裕?以構(gòu)造一顆熵值下降最快的決策樹菌瘫， 到葉子節(jié)點處的熵值為0蜗顽。 此時， 每個葉子節(jié)點對應(yīng)的實例集中的實例屬于同一類雨让。
關(guān)于書中如何根據(jù)經(jīng)驗熵和經(jīng)驗條件熵來計算信息增益比雇盖。理解注釋如下：
ID3算法由于只有樹的生成，所有該算法生成的樹容易產(chǎn)生過擬合
3栖忠、決策樹C4.5算法（信息增益比）
CART：表示分類與回歸樹崔挖，是classification and regression tree的縮寫。
C4.5相比ID3的改進在于使用信息增益比來選擇特征庵寞。信息增益比的定義如下：
4狸相、決策樹CART算法（平方誤差和基尼指數(shù)）
目標變量是類別的 --- 分類樹
目標變量是連續(xù)的 --- 回歸樹
決策樹的生成就是遞歸地構(gòu)建二叉決策樹的過程。對回歸樹用平方誤差最小化準則（比如最小二乘回歸樹生成）捐川，對分類用基尼指數(shù)最小化準則脓鹃，進行特征選擇，生成二叉樹古沥。
CART算法由一下兩步組成：
1瘸右、決策樹生成：基于訓(xùn)練數(shù)據(jù)集生成決策樹，生成的決策樹要盡量大岩齿。
2太颤、決策樹剪枝：用驗證數(shù)據(jù)集對已生成的樹進行剪枝并選擇最優(yōu)子樹，這時用損失函數(shù)最小化作為剪枝的標準盹沈。
In [1]: import numpy as np
...: import pandas as pd
...: import matplotlib.pyplot as plt
...: from sklearn.datasets import load_iris
...: from sklearn.model_selection import train_test_split
In [2]: def create_data():
...: iris = load_iris()
...: df = pd.DataFrame(iris.data, columns=iris.feature_names)
...: df['label'] = iris.target
...: df.columns = ['sepal length', 'sepal width', 'petal length', 'petal width', 'label']
...: data = np.array(df.iloc[:100, [0, 1, -1]])
...: # print(data)
...: return data[:,:2], data[:,-1]
In [3]: X, y = create_data()
...: X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3)
...:
In [5]: from sklearn.tree import DecisionTreeClassifier
...: from sklearn.tree import export_graphviz
...: import graphviz
...:
In [6]: clf = DecisionTreeClassifier()
...: clf.fit(X_train, y_train,)
...:
Out[6]:
DecisionTreeClassifier(class_weight=None, criterion='gini', max_depth=None,
max_features=None, max_leaf_nodes=None,
min_impurity_split=1e-07, min_samples_leaf=1,
min_samples_split=2, min_weight_fraction_leaf=0.0,
presort=False, random_state=None, splitter='best')
In [7]: clf.score(X_test,y_test)
Out[7]: 0.9666666666666667
#下面的樹圖在IPyhon終端下顯示不出來栋齿，可以用jupyter notebook下來使用顯示
In [8]: tree_pic = export_graphviz(clf, out_file="mytree.pdf")
...: with open('mytree.pdf') as f:
...: dot_graph = f.read()
...:
In [9]: graphviz.Source(dot_graph)
Out[9]: <graphviz.files.Source at 0x12078e80>
決策樹的剪枝
為什么進行決策樹的剪枝？
因為決策樹生成算法遞歸地產(chǎn)生決策樹襟诸，直到不能繼續(xù)下去為止瓦堵。這樣產(chǎn)生的決策樹往往對訓(xùn)練數(shù)據(jù)的分類很準確，但是對測試數(shù)據(jù)的分類卻沒有那么準確歌亲，即是會出現(xiàn)過擬合菇用。過擬合的原因是在于學(xué)習(xí)時過多地考慮如何提高對訓(xùn)練數(shù)據(jù)的正確分類，從而構(gòu)建出過于復(fù)雜的決策樹陷揪。
其中惋鸥，ID3和C4.5用于分類杂穷，即是離散變量。而CART既可以用于分類也可以用于回歸卦绣。
參考鏈接：
決策樹算法的Python實現(xiàn)
決策樹類算法總結(jié)
決策樹
李航 統(tǒng)計學(xué)習(xí)方法 第五章 決策樹 課后 習(xí)題 答案
