基于Python的決策樹分類器與剪枝-有解無憂

作者|Angel Das
編譯|VK
來源|Towards Data Science

介紹

決策樹分類器是一種有監督的學習模型，在我們關心可解釋性時非常有用，
決策樹通過基于每個層次的多個問題做出決策來分解資料
決策樹是處理分類問題的常用演算法之一，

為了更好地理解它，讓我們看看下面的例子，

決策樹通常包括：

根節點-表示被進一步劃分為同質組的樣本或總體
拆分-將節點分為兩個子節點的程序
決策節點-當一個子節點根據某個條件拆分為其他子節點時，稱為決策節點
葉節點或終端節點-不進一步拆分的子節點
資訊增益-要使用一個條件(比如說資訊最豐富的特征)來分割節點，我們需要定義一個可以優化的目標函式，在決策樹演算法中，我們傾向于在每次分割時最大化資訊增益，在測量資訊增益時，通常使用三種度量，它們是基尼不純度、熵和分類誤差

數學理解

為了理解決策樹是如何發展的，我們需要更深入地了解在每一步中如何使用度量使資訊增益最大化，

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

學生總數-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)=P2+Q2，其中P和Q是學生成為美食家和非美食家的概率，GIn(節點A）=0.82+0.22=0.68

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

節點B或女生的基尼指數(GIn）=P2+Q2，其中P和Q是學生成為美食家和非美食家的概率，GIn(節點B）=0.42+0.62=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.5*IQR和Q3+1.5*IQR值進行提取，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 = https://www.cnblogs.com/panchuangai/p/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#sphx-glr-auto-examples-tree-plot-cost-complexity-pruning-py.

原文鏈接：https://towardsdatascience.com/decision-tree-classifier-and-cost-computation-pruning-using-python-b93a0985ea77

歡迎關注磐創AI博客站：
http://panchuang.net/

sklearn機器學習中文官方檔案：
http://sklearn123.com/

歡迎關注磐創博客資源匯總站：
http://docs.panchuang.net/

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/83579.html

標籤：其他

上一篇：第四章節 BJROBOT 線速度校正【ROS全開源阿克曼轉向智能網聯無人駕駛車】

下一篇：國內演算法比賽平臺匯總