基於Python的決策樹分類器與剪枝

介紹

• 決策樹分類器是一種有監督的學習模型，在我們關心可解釋性時非常有用。

• 決策樹通過基於每個層次的多個問題做出決策來分解數據

• 決策樹是處理分類問題的常用演算法之一。
  爲了更好地理解它，讓我們看看下面 下麪的例子。
  
  決策樹通常包括：

• 根節點-表示被進一步劃分爲同質組的樣本或總體

• 拆分-將節點分爲兩個子節點的過程

• 決策節點-當一個子節點根據某個條件拆分爲其他子節點時，稱爲決策節點

• 葉節點或終端節點-不進一步拆分的子節點

• 資訊增益-要使用一個條件(比如說資訊最豐富的特徵)來分割節點，我們需要定義一個可以優化的目標函數。在決策樹演算法中，我們傾向於在每次分割時最大化資訊增益。在測量資訊增益時，通常使用三種度量。它們是基尼不純度、熵和分類誤差
  
  數學理解
  爲了理解決策樹是如何發展的，我們需要更深入地瞭解在每一步中如何使用度量使資訊增益最大化。

讓我們舉一個例子，其中我們有包含學生資訊的訓練數據，如性別、年級、因變數或分類變數，這些變數可以識別學生是否是美食家。我們有以下概述的資訊。

• 學生總數-20人
• 被歸爲美食家的學生總數-10
• 不屬於美食家的學生總數-10
• P(美食家)，即學生成爲美食家的概率=(10/20）=0.5
• Q(非美食家），學生不是美食家的概率=(10/20）=0.5

讓我們根據學生的性別將他們分成兩個節點，並重新計算上述指標。

男學生(節點A）

• 學生總數-10人
• 被歸爲美食家的學生總數-8
• 不屬於美食家的學生總數-2
• P(美食家)，學生成爲美食家的概率=(8/10）=0.8
• Q(非美食家），學生不是美食家的概率=(2/10）=0.2

女生(節點B）

• 學生總數-10人
• 被歸爲美食家的學生總數-4
• 不屬於美食家的學生總數-6
• P(美食家)，學生成爲美食家的概率=(4/10）=0.4
• Q(非美食家），學生不成爲美食家的概率=(6/10）=0.6

節點A的基尼指數 (GIn)=P²+Q²，其中P和Q是學生成爲美食家和非美食家的概率。GIn(節點A）=0.8²+0.2²=0.68

節點A的基尼不純度(GIp）=1-基尼指數=1–0.68=0.32

節點B或女生的基尼指數(GIn）=P²+Q²，其中P和Q是學生成爲美食家和非美食家的概率。GIn(節點B）=0.4²+0.6²=0.52

節點B的基尼不純度(GIp）=1-基尼指數=1–0.52=0.48

我們觀察到的是，當我們將學生按性別(男性和女性)分別劃分爲A和B節點時，我們分別得到了兩個節點的基尼不純度。現在，爲了確定性別是否是將學生分爲美食家和非美食家的正確變數，我們需要一個加權基尼不純度分數，該分數使用以下公式計算。

加權基尼不純度=(A節點總樣本數/數據集中總樣本數)基尼不純度(A節點)+(B節點總樣本數/數據集中樣本數)基尼不純度(B節點)

用此公式計算上例的加權基尼不純度分數，按性別劃分學生時加權基尼不純度分數=(10/20)0.32 + (10/20)0.48 = 0.4

一個分類問題涉及多個自變數。變數可以是名義變數，也可以是連續變數。決策樹很適合處理不同數據型別的變數。

決策樹演算法在決定每個節點的拆分時考慮了所有可能的變數，可以獲得最大加權不純度增益的變數被用作特定節點的決策變數。

在上面的例子中，使用「性別」作爲決策變數的加權不純度增益是0.4，但是，假設使用「年級」作爲決策變數，加權不純度增益0.56，演算法將使用「年級」作爲建立第一個分割的決策變數。所有後續步驟都遵循類似的方法，直到每個節點都是同構的。

決策樹演算法簡介

• 決策樹容易過度擬合，因爲演算法繼續將節點分割爲子節點，直到每個節點變得均勻

• 與測試集相比，訓練數據的精度要高得多，因此需要對決策樹進行剪枝，以防止模型過度擬合。剪枝可以通過控制樹的深度、每個節點的最大/最小樣本數、要拆分的節點的最小不純度增益和最大葉節點來實現

• Python允許使用者使用基尼不純度或熵作爲資訊增益準則來開發決策樹

• 可以使用網格搜尋或隨機搜尋CV對決策樹進行微調。CV代表交叉驗證

三種不同不純度標準的比較
下面 下麪概述的程式碼片段提供了不同不純度標準的直觀比較，以及它們如何隨不同的概率值而變化。注意下面 下麪的程式碼改編自Deeper Insights into Machine Learning by S.Raschka, D.Julian, and J.Hearty, 2016。

import matplotlib.pyplot as plt

import numpy as np

#-----計算基尼指數
def gini(p):
    return (p)*(1 - (p)) + (1 - p)*(1 - (1-p))

#-----計算熵
def entropy(p):
    return - p*np.log2(p) - (1 - p)*np.log2((1 - p))

#-----計算分類誤差
def classification_error(p):
    return 1 - np.max([p, 1 - p])

#-----建立一個從0到1的概率值Numpy陣列，增量爲0.01
x = np.arange(0.0, 1.0, 0.01)

#---不同p值的熵
ent = [entropy(p) if p != 0 else None for p in x]

#----獲得縮放後的熵
sc_ent = [e*0.5 if e else None for e in ent]

#--分類錯誤
err = [classification_error(i) for i in x]

#--繪圖

fig = plt.figure();
plt.figure(figsize=(10,8));
ax = plt.subplot(111);

for i, lab, ls, c, in zip([ent, sc_ent, gini(x), err], ['Entropy', 'Entropy (scaled)','Gini Impurity',
                                                        'Misclassification Error'],['-', '-', '--', '-.'],
                          ['black', 'darkgray','blue', 'brown', 'cyan']):
    line = ax.plot(x, i, label=lab,
    linestyle=ls, lw=2, color=c)
    
ax.legend(loc='upper center', bbox_to_anchor=(0.5, 1.15), ncol=3, fancybox=True, shadow=False)
ax.axhline(y=0.5, linewidth=1, color='k', linestyle='--')
ax.axhline(y=1.0, linewidth=1, color='k', linestyle='--')
plt.ylim([0, 1.1])
plt.xlabel('p(i=1)')
plt.ylabel('Impurity Index')
plt.show()

練習
問題陳述旨在建立一個分類模型來預測紅酒的品質。

這是一個典型的多類分類問題。注意，所有的機器學習模型都對異常值敏感，因此在構建樹之前，應該處理由異常值組成的特徵/獨立變數。

不同特性/獨立變數的一個重要方面是它們如何相互作用。皮爾遜相關可以用來確定數據集中兩個特徵之間的關聯程度。然而，對於像決策樹這樣的基於決策的演算法，我們不會丟棄高度相關的變數。

#匯入所需的庫-
%matplotlib inline

import numpy as np
import pandas as pd

from sklearn.tree import DecisionTreeClassifier

import numpy as np
import pandas as pd
import seaborn as sns

sns.set(color_codes=True)

from matplotlib import pyplot as plt
from sklearn.model_selection import train_test_split #分爲訓練集和測試集
from sklearn.tree import DecisionTreeClassifier #構建決策樹模型

from sklearn import metrics
from sklearn.metrics import accuracy_score,f1_score,recall_score,precision_score, confusion_matrix #模型驗證
%matplotlib inline

from IPython.display import display #用於在一個輸出中顯示多個數據幀

from sklearn.feature_extraction.text import CountVectorizer  #DT不接受字串作爲模型擬合步驟的輸入

import missingno as msno_plot #缺失值繪圖

wine_df = pd.read_csv('winequality-red.csv',sep=';')

數據的快速描述性統計

wine_df.describe().transpose().round(2)

檢查缺失值

#非缺失值的條形圖
plt.title('#Non-missing Values by Columns')
msno_plot.bar(wine_df);

異常值檢查和處理

#檢查異常值
plt.figure(figsize=(15,15))
pos = 1
for i in wine_df.columns:
    plt.subplot(3, 4, pos)
    sns.boxplot(wine_df[i])
    pos += 1

col_names=['fixed acidity', 'volatile acidity', 'citric acid', 'residual sugar',
       'chlorides', 'free sulfur dioxide', 'total sulfur dioxide', 'density',
       'pH', 'sulphates', 'alcohol']

display(col_names)

for i in col_names:
    q1, q2, q3 = wine_df[i].quantile([0.25,0.5,0.75])
    IQR = q3 - q1
    lower_cap=q1-1.5*IQR
    upper_cap=q3+1.5*IQR
    wine_df[i]=wine_df[i].apply(lambda x: upper_cap if x>(upper_cap) else (lower_cap if x<(lower_cap) else x))

上面的異常值使用Q1–1.5IQR和Q3+1.5IQR值進行提取。Q1、Q3和IQR分別代表第一四分位數、第三四分位數和四分位數間的範圍。

sns.pairplot(wine_df);

理解不同變數之間的關係。注意。在決策樹中，我們不需要刪除高度相關的變數，因爲節點只使用一個獨立變數被劃分爲子節點，因此，即使兩個或多個變數高度相關，產生最高資訊增益的變數也將用於分析。

plt.figure(figsize=(10,8))
sns.heatmap(wine_df.corr(),
            annot=True,
            linewidths=.5,
            center=0,
            cbar=False,
            cmap="YlGnBu")
plt.show()

分類問題對類別不平衡很敏感。當一個類值所佔比例較大時，就會出現類不平衡。類別平衡是通過將因變數「quality」屬性的值組合而產生的。

plt.figure(figsize=(10,8))
sns.countplot(wine_df['quality']);

wine_df['quality'] = wine_df['quality'].replace(8,7)
wine_df['quality'] = wine_df['quality'].replace(3,5)
wine_df['quality'] = wine_df['quality'].replace(4,5)
wine_df['quality'].value_counts(normalize=True)

將數據分爲訓練集和測試集，以檢查模型的準確性，並查詢是否存在過擬合或欠擬合。

# 將數據分解爲訓練集和測試集

from sklearn.model_selection import train_test_split

X_train, X_test, y_train, y_test =train_test_split(wine_df.drop('quality',axis=1), wine_df['quality'], test_size=.3, random_state=22)
X_train.shape,X_test.shape

利用基尼準則建立了決策樹模型。請注意，爲了簡單起見，我們將樹剪枝到最大深度3。這將有助於我們將樹視覺化，並將其與我們在初始部分中討論的概念聯繫起來。

clf_pruned = DecisionTreeClassifier(criterion = "gini", random_state = 100,
                               max_depth=3, min_samples_leaf=5)
clf_pruned.fit(X_train, y_train)

請注意，可以調整以下參數以改進模型輸出(Scikit Learn，2019）。

• criterion — 使用的度量，例如基尼不純度
• class_weight — None，代表所有類權重爲1
• max_depth — 3; 剪枝。當「None」表示節點將展開，直到所有葉子都是同構的
• max_features — None; 在決定節點的分割時，要考慮所有的特徵或自變數
• max_leaf_nodes — None;
• min_impurity_decrease — 0.0; 只有當分割確保不純度的減少大於或等於零時，節點才被分割
• min_impurity_split — None;
• min_samples_leaf — 1;一個葉子存在所需的最小樣本數
• min_samples_split — 2; 如果min_samples_leaf =1，則表示右節點和左節點應該各有一個樣本，即父節點或根節點應該至少有兩個樣本
• splitter — ‘best’; 用於在每個節點選擇分割的策略。最好確保在決定分割時考慮到所有的特徵

from sklearn.tree import export_graphviz
from sklearn.externals.six import StringIO  
from IPython.display import Image  
import pydotplus
import graphviz

xvar = wine_df.drop('quality', axis=1)
feature_cols = xvar.columns

dot_data = StringIO()
export_graphviz(clf_pruned, out_file=dot_data,  
                filled=True, rounded=True,
                special_characters=True,feature_names = feature_cols,class_names=['0','1','2'])

from pydot import graph_from_dot_data
(graph, ) = graph_from_dot_data(dot_data.getvalue())
Image(graph.create_png())

preds_pruned = clf_pruned.predict(X_test)
preds_pruned_train = clf_pruned.predict(X_train)
print(accuracy_score(y_test,preds_pruned))
print(accuracy_score(y_train,preds_pruned_train))

模型對訓練數據和測試數據的準確度得分分別爲0.60和0.62。

特徵重要性是指一類將分數分配給預測模型的輸入特徵的技術，該技術指示在進行預測時每個特徵的相對重要性。

## 計算特徵重要性

feat_importance = clf_pruned.tree_.compute_feature_importances(normalize=False)

feat_imp_dict = dict(zip(feature_cols, clf_pruned.feature_importances_))
feat_imp = pd.DataFrame.from_dict(feat_imp_dict, orient='index')
feat_imp.rename(columns = {0:'FeatureImportance'}, inplace = True)
feat_imp.sort_values(by=['FeatureImportance'], ascending=False).head()

DecisionTreeClassifier()提供諸如min_samples_leaf和max_depth等參數，以防止樹過度擬合。

可以看成是如下場景，在這個場景中，我們明確定義樹的深度和最大葉子數。然而，最大的挑戰是如何確定一棵樹應該包含的最佳深度和葉子。

在上面的例子中，我們使用max_depth=3，min_samples_leaf=5。這些數位只是用來觀察樹的行爲的範例圖。但是，如果在現實中，我們被要求研究這個模型併爲模型參數找到一個最佳值，這是一個挑戰，但並非不可能(決策樹模型可以使用GridSearchCV演算法進行微調)。

另一種方法是使用成本複雜性剪枝(CCP）。

成本複雜性剪枝爲控制樹的大小提供了另一種選擇。在DecisionTreeClassifier中，這種剪枝技術是由代價複雜性參數ccp_alpha來參數化的。ccp_alpha值越大，剪枝的節點數就越多。

簡單地說，成本複雜性是一個閾值。只有當模型的整體不純度改善了一個大於該閾值的值時，該模型纔會將一個節點進一步拆分爲其子節點，否則將停止。

當CCP值較低時，即使不純度減少不多，該模型也會將一個節點分割成子節點。隨着樹的深度增加，這一點很明顯，也就是說，當我們沿着決策樹往下走時，我們會發現分割對模型整體不純度的變化沒有太大貢獻。然而，更高的分割保證了類的正確分類，即準確度更高。

當CCP值較低時，會建立更多的節點。節點越高，樹的深度也越高。

下面 下麪的程式碼(Scikit Learn)說明了如何對alpha進行調整，以獲得更高精度分數的模型。

path = model_gini.cost_complexity_pruning_path(X_train, y_train)
ccp_alphas, impurities = path.ccp_alphas, path.impurities

fig, ax = plt.subplots(figsize=(16,8));
ax.plot(ccp_alphas[:-1], impurities[:-1], marker='o', drawstyle="steps-post");
ax.set_xlabel("effective alpha");
ax.set_ylabel("total impurity of leaves");
ax.set_title("Total Impurity vs effective alpha for training set");

讓我們瞭解隨着alpha的變化深度和節點數的變化。

clfs = clfs[:-1]

ccp_alphas = ccp_alphas[:-1]

node_counts = [clf.tree_.node_count for clf in clfs]

depth = [clf.tree_.max_depth for clf in clfs]

fig, ax = plt.subplots(2, 1,figsize=(16,8))

ax[0].plot(ccp_alphas, node_counts, marker='o', drawstyle="steps-post")
ax[0].set_xlabel("alpha")
ax[0].set_ylabel("number of nodes")
ax[0].set_title("Number of nodes vs alpha")
ax[1].plot(ccp_alphas, depth, marker='o', drawstyle="steps-post")
ax[1].set_xlabel("alpha")
ax[1].set_ylabel("depth of tree")
ax[1].set_title("Depth vs alpha")
fig.tight_layout()

瞭解α增加時精度的變化。

fig, ax = plt.subplots(figsize=(16,8)); #設定大小
train_scores = [clf.score(X_train, y_train) for clf in clfs]
test_scores = [clf.score(X_test, y_test) for clf in clfs]
ax.set_xlabel("alpha")
ax.set_ylabel("accuracy")
ax.set_title("Accuracy vs alpha for training and testing sets")
ax.plot(ccp_alphas, train_scores, marker='o', label="train",
        drawstyle="steps-post")
ax.plot(ccp_alphas, test_scores, marker='o', label="test",
        drawstyle="steps-post")
ax.legend()
plt.show()

i = np.arange(len(ccp_alphas))
ccp = pd.DataFrame({'Depth': pd.Series(depth,index=i),'Node' : pd.Series(node_counts, index=i),\
                    'ccp' : pd.Series(ccp_alphas, index = i),'train_scores' : pd.Series(train_scores, index = i),
                   'test_scores' : pd.Series(test_scores, index = i)})
ccp.tail()
ccp[ccp['test_scores']==ccp['test_scores'].max()]

上面的程式碼提供了在測試數據中產生最高精度的成本計算剪枝值。

參考文獻

• Raschka, S., Julian, D. and Hearty, J. (2016). Python : deeper insights into machine learning : leverage benefits of machine learning techniques using Python : a course in three modules. Birmingham, Uk: Packt Publishing, pp.83, 88, 89.
  *‌ Scikit-learn: Machine Learning in Python, Pedregosa et al., JMLR 12, pp. 2825–2830, 2011.
• Scikit Learn (2019). sklearn.tree.DecisionTreeClassifier — scikit-learn 0.22.1 documentation. [online] Scikit-learn.org. Available at: https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html.
• Scikit Learn (n.d.). Post pruning decision trees with cost complexity pruning. [online] Available at: https://scikit-learn.org/stable/auto_examples/tree/plot_cost_complexity_pruning.html.

今天的分享就到此結束，如果我的分享對你有幫助，也歡迎大家轉發我的文章讓更多人受益，如果你在學習Python和人工智慧的過程當中有遇見任何問題，可以加入我的人工智慧**qq羣：**84275181，多多交流問題，互幫互助，羣裡有不錯的學習教學和開發工具。學習python和人工智慧有任何問題（學習方法，學習效率，如何就業等等），可以隨時來諮詢我。或者加入我們的平臺：奇點人工智慧教學