决策树模型

决策树简介

基本原理

决策树的基本原理是通过对一系列问题进行 if / else 的推导，从而实现相关决策。

决策树中的树即是数据结构中的树。它通过结点的概念来组成的。如下就是一个抽象的决策树：

图片来源：根据 https://www.geeksforgeeks.org/decision-tree/ 以及 https://youtube.com/watch?v=ZVR2Way4nwQ 二次创作

决策树的建树依据主要是基尼系数(gini)，用于计算一个系统中的失序程序。建立决策树的目的就是降低系统的混乱程度，从而得到合适的数据分类效果。

基尼系数的计算公式如下：

\\[ gini(T) = 1 - \sum p_i^2 \\]

其中 \\( p_i \\) 为类别 \\( i \\) 在样本 \\( T \\) 中出现的频率（所占比例）。

当引入某个用于分类的变量时，分类后的基尼系数的公式为：

\\[ gini(T) = \frac{S_1}{S_1 + S_2}gini(T_1) + \frac{S_2}{S_1 + S_2}gini(T_2) \\]

其中 \\( S_1 \\) 、\\( S_2 \\) 为划分后的两类各自的样本量，\\( gini(t_1) \\) 、\\( gini(t_2) \\) 为两类各自的基尼系数。

若划分后，系统的基尼系数降低，则说明该划分有效。

若一个模型有许多变量，都是通过计算根据变量划分后系统的基尼系数，再通过计算划分后的基尼系数，判断如何划分结点，从而搭建出一个有效的决策树模型。

采用基尼系数进行运算的决策树也称为CART决策树

信息熵

除了基尼系数，还有另一种衡量系统混乱程度的方法：信息熵 。

信息熵 \\( H(X) \\) 的计算公式如下：

\\[ H(X) = - \sum p_i \log_2 (p_i) \\]

其中 \\( X \\) 表示随机变量，在 \\( n \\) 分类问题中有 \\( n \\) 个取值。\\( p_i \\) 表示随机变量 \\( X \\) 取值为 \\( X_i \\) 的频率。

当引入某个用于分类的变量 \\( A \\) 后，根据信息熵划分后的信息熵又称为条件熵，其计算公式如下：

\\[ H_A(X) = \frac{S_1}{S_1 + S_2}H(X_1) + \frac{S_2}{S_1 + S_2}H(X_2) \\]

其中 \\( S_1 \\) 、\\( S_2 \\) 为划分后的两类样本量，\\( H(X_1) \\) 、\\( H(X_2) \\) 为两类各自的信息熵。

为了衡量不同划分方式降低信息熵的效果，还需要计算分类后信息熵的减少值：

\\[ Gain(A) = H(X) - H_A(X) \\]

该减少值称为熵增益或信息增益，其值越大，说明分类后的系统混乱程序越低，即分类越准确。

由于决策树涉及到的计算量较大，因此一般使用平方运算的基尼系数而不是对数运算的信息熵。

代码实现

决策树既能做分类分析（预测分类变量值），也能做回归分析（预测连续变量值），对应的模型分别为分类决策树模型(Decision Tree Classifier)和回归决策树模型(Decision Tree Regressor)。

分类决策树模型

分类决策树模型代码如下：

from sklearn.tree import DecisionTreeClassifier
model = DecisionTreeClassifier(random_state=42)
model.fit(X_train, Y_train)
DecisionTreeClassifier(random_state=42)

决策树模型会优先选择使整个系统基尼系数下降最大的划分方式进行结点划分，但是具体的阈值可能有所不同。因此以上使用 random_state 参数确保运行后会得到一样的树。

接下来查看预测的准确性：

from sklearn.metrics import accuracy_score
accuracy_score(model.predict(X_test), Y_test)
0.85

利用得到的模型计算其准确率：

model.score(X_test, Y_test)
0.9125

相当不错的结果，绘制 ROC 曲线如下：

from sklearn.metrics import roc_curve

FPR, TPR, threshold = roc_curve(Y_test, model.predict_proba(X_test)[:, 1])

plt.plot(FPR, TPR)

plt.show()

并计算曲线的 AUC 值：

from sklearn.metrics import roc_auc_score
roc_auc_score(Y_test, model.predict_proba(X_test)[:, 1])
0.9584478021978022

并且还可以评价各个特征变量的的重要程度，即特征重要性，表示特征变量对整体基尼系数下降的贡献程度，取值范围为 \\( (0, 1) \\) 。

通过如下代码查看各变量的特征重要性：

model.feature_importances_
array([0.       , 0.5083096, 0.4916904])

结果说明第一个特征变量“性别”对购买产品基本无关系，其余特征变量“年龄”“薪水”对结果的影响效果相似。

Graphviz插件与模型可视化

Graphviz插件是一个用于将决策树可视化表现的一个插件。

可以在 https://graphviz.gitlab.io/download/ 里下载该插件。

下载完成后安装到本地。安装时尽量将其添加到系统的环境变量中。

接下来还需要额外安装 graphviz 库。可直接使用 pip 安装：

(sci) PS D:\MachineLearning\demo> pip install graphviz

配合使用 sklearn 和 graphviz ，通过以下代码便可生成可视化的决策树模型：

from sklearn.tree import export_graphviz
import graphviz
import os
os.environ['PATH'] = os.pathsep + r'D:\MachineLearning\Graphviz\bin'
graph = graphviz.Source(
    export_graphviz(model, class_names=['Purchased', 'Not']))
graph.render('result', format='png')
'result.png'

其中有关于 os 库的代码是为了将 Graphviz 添加到系统的环境变量中。如果不指定导出的格式，默认导出为 PDF 文件。

截取图片部分如下：

其中 X[1] 表示第二个特征变量（该例中为 'Age' ），以此类推；gini 表示该结点的基尼系数；samples 表示该结点中的样本数；value 表示各结点中样本的各类别的数量；class 表示分类类别。

对于每一条待预测的数据，根据第一行的条件对其 if / else 判断，根据判断结果选择进入哪一个子结点继续判断，最终在叶结点得到其属于的分类。

模型最终预测结果取决于叶结点的分类，其余结点的分类都是无意义的。

每一次进行二分类后，基尼系数的下降都是模型经过计算后的最优解。

叶结点停止分裂的主要依据有两个：

基尼系数已经为 0 ，无需再分裂
树达到了限定的深度，停止分裂

分类的概率计算基于叶结点，根据对应叶结点中的 value 占比，得出属于该分类的概率。绘制 ROC 曲线时，阈值也是基于这些概率得到的。

回归决策树模型

决策树还能进行回归分析从而预测连续变量，此时的决策树称为 回归决策树 。

生成回归决策树的代码和分类决策树类似：

from sklearn.tree import DecisionTreeRegressor
X_regr = [[1, 2], [2, 4], [4, 6], [5, 8], [8, 10]]
Y_regr = [1, 2, 4, 5, 6]
model = DecisionTreeRegressor(max_depth=2, random_state=42)
model.fit(X_regr, Y_regr)
model.predict([[7, 9]])
array([5.5])

这里仅为了演示简单手动生成了少数数据。

回归决策树模型的概念与分类决策树的基本一致，最大的不同是其划分标准不是基尼系数或信息熵，而是均方误差MSE，其计算公式如下：

\\[ MSE = \frac{1}{n} \sum (y^{(i)} - \hat y^{(i)})^2 \\]

其中 \\( n \\) 为样本数量，\\( y^{(i)} \\) 为实际值，\\( \hat y^{(i)} \\) 为理论值。

借助可视化查看树的模型如下：

可以看到预测结果并不完全是连续的，而是类似于多分类问题。

参数调优

K折交叉验证

有时需要对数据集多次划分，组成多组不同的训练集和测试集来评估模型的有效性，并选出最好的模型，该方法称为交叉验证。

交叉验证有以下常用方法：

简单交叉验证
K折交叉验证
留一交叉验证

其中K折交叉验证应用较广泛，其原理是将数据随机划分为 \\( K \\) 份，每次选取 \\( K-1 \\) 份作为训练集，用剩下的一份作为测试集，得到 \\( K \\) 个模型后对它们平均测试的结果作为最终的模型效果。

通常来说，如果模型集较小需要增大 K 值保证更多有效数据可以用于训练；如果模型集较大可以适当减小 K 值来减少计算成本。

交叉验证的代码实现如下：

from sklearn.model_selection import cross_val_score
acc = cross_val_score(model, X, Y, cv=5)
acc
array([0.7375, 0.95  , 0.9   , 0.8125, 0.825 ])

参数 cv 代表交叉验证的次数 \\( K \\) 。通过数组的 .mean() 方法查看平均值：

acc.mean()
0.845

以上默认以准确度作为评估标准，如果要以 ROC 曲线的 AUC 值作为评估标准，需要指定 scoring 参数为 'roc_auc' ，代码如下：

cross_val_score(model, X, Y, scoring='roc_auc', cv=5)
array([0.72252747, 0.95398352, 0.90094659, 0.8326572 , 0.892833  ])

GridSearch网格搜索

网格搜索是一种穷举搜索的参数调优手段，通过遍历所有候选参数来循环建立模型并评估模型的有效性和准确性，选取表现最好的参数作为最终结果。

决策树的最大深度 max_depth 不宜过高或过低：过低可能发生欠拟合，过高把样本分的太细，可能导致过拟合。可以使用网格搜索评价树的合适深度。

决策树剪枝

决策树剪枝的目的是为了防止构建的决策树出现过拟合。决策树分为前剪枝和后剪枝，定义如下：

前剪枝：从上往下剪枝，通常利用参数控制树的形状如深度、叶结点数

后剪枝：从下往上剪枝，通常在结果中合并相近的类别

单参数调优

使用网格搜索确定树深度的代码如下：

from sklearn.model_selection import GridSearchCV
parameters = {'max_depth': np.arange(1, 7)}
model = DecisionTreeClassifier()
grid_search = GridSearchCV(model, parameters, scoring='roc_auc', cv=5)
grid_search.fit(X_train, Y_train)
GridSearchCV(cv=5, estimator=DecisionTreeClassifier(),
             param_grid={'max_depth': array([1, 2, 3, 4, 5, 6])},
             scoring='roc_auc')

网格搜索利用K折交叉验证确定评估结果，因此要对其设置 cv 参数。

接着可以输出参数的最优值如下：

print(grid_search.best_params_, grid_search.best_score_)
{'max_depth': 3} 0.9414634146341463

可以验证该参数确实能得到最佳的模型。

多参数调优

多参数调优下，遍历的过程类似于在网格里寻找一个最优值，因此该方法得名网格搜索。

分类决策树有很多参数，除了最大深度外常用的还有：

criterion ：特征选择标准，可以选择基尼系数 'gini' 或者信息熵 'entropy'
splitter ：取值为 'best' 或 'random' ，前者在特征的所有划分中找出最优的划分点，适合样本量不大的情况；后者随机在部分划分点中寻找局部最优的情况，适合样本量非常大的情况
min_samples_split ：子结点往下分裂所需的最小样本数，默认为 2 ，小于该值则停止分裂
min_samples_leaf ：叶结点的最小样本数，默认为 1 ，小于该值时会连同兄弟结点一起被剔除并停止分裂

其余参数的作用可以参见文档。

使用多参数对模型调优如下：

from sklearn.model_selection import GridSearchCV
parameters = {'max_depth': range(2, 6), 'min_samples_split': range(5, 16, 2),
              'criterion': ('entropy', 'gini')}
model = DecisionTreeClassifier()
grid_search = GridSearchCV(model, parameters, scoring='roc_auc', cv=5)
grid_search.fit(X_train, Y_train)
GridSearchCV(cv=5, estimator=DecisionTreeClassifier(),
             param_grid={'criterion': ('entropy', 'gini'),
                         'max_depth': range(2, 6),
                         'min_samples_split': range(5, 16, 2)},
             scoring='roc_auc')

查看此时的调优结果：

print(grid_search.best_params_, grid_search.best_score_)
{'criterion': 'entropy', 'max_depth': 4, 'min_samples_split': 15} 0.946659597030753

结果确实比单参数调优要好。

机器学习入门笔记03