代码收藏家技术教程 2022-08-01

sklearn中的决策树（分类）

Sklearn库有很多机器学习模型，不同的模型有着不同的特点，针对不同的问题，选取对应的模型，可以很好地解决问题。树模型作为经典的机器学习模型，可以做分类以及回归，分类模型中有DecisionTreeClassifier与ExtraTreeClassifier；回归模型中有DecisionTreeRegressor与ExtraTreeRegressor。

　　目前网上大多数对于决策树等模型的讲解，原理与代码总是割裂的。本文试图在理解原理的基础上，结合Python中sklearn库的相关代码，互为补充理解。有一些原理上的原则，在实际运用中并非如此，比如大多数博客会以离散指标作为讲解Gini指数判断纯度的依据，但其实sklearn的决策树代码只会把所有特征视为连续变量，并对其离散化处理；还有对于后剪枝算法CCP，很多博客只是罗列概念，没有给出模型中参数ccp_alpha的具体含义，以及 $\alpha$ 到底怎么算……

　　本文试图弥补原理与代码之间的GAP，并作为我自学的笔记，供诸君参考，算是抛砖引玉，如有不正之处或者侵权，还望及时指出。

1 决策树（分类）基本概念

　　顾名思义，决策树就是一棵树，一棵决策树包含一个根节点、若干个内部结点和若干个叶结点；叶结点对应于决策结果，其他每个结点则对应于一个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集，从根结点到每个叶子结点的路径对应了一个判定测试序列。

　　对于离散的分类任务，决策树最后生成的树叶是根据算法构建出的最优类别，如果没有限定决策树的最大高度等参数，树叶内的数据一般会是纯的，即一片树叶内只有一种类别，但是经过剪枝（后面会讲）操作后，叶节点的数据可能会不纯。

2 分类问题决策树生成原理

2.1 “纯度”判断

　　决策树学习的关键在于如何选择最优的划分属性，所谓的最优划分属性，对于分类而言，就是尽量使划分的样本属于同一类别，即“纯度”最高的属性。

　　那么，如何定义数据的“纯度”就成了问题的关键，现在的主流算法是CART算法，sklearn中DecisionTreeClassifier就是用的CART算法，其判别纯度的指标是entropy熵与Gini指数。

熵的公式为： $H(X) = - \sum_{i=1}^{K}p_ilogp_i$

其中 $K$ 表示有 $K$ 种类别， $p_i$ 是 $X$ 取第 $i$ 种类的概率，实际计算直接用第i种类别所占的比例代替，熵越大，表示此时的混乱程度越大，数据越不纯。

　　如果利用某一种指标 $A=a$ 将原数据 $D$ 分为两类 $D_1$ 与 $D_2$ 之后，在这个分类下，定义此时的条件熵为 $H(D|A) = \frac{|D_1|}{|D|}H(D_1) +\frac{|D_2|}{|D|}H(D_2)$

接着定义信息增益： $I(D,A) = H(D) - H(D|A)$

基尼指数的公式为： $Gini(X)=\sum_{i=1}^{K}p_i(1-p_i)=1-\sum_{i=1}^{K} p_i^2$

同样 $K$ 表示有 $K$ 种类别， $p_i$ 是 $X$ 取第 $i$ 种类的概率，直观上说，基尼指数反映了从数据集中随机抽取两个样本，其类别标记不一致的概率，所以基尼指数也是越大表示越混乱。

　　同样地，利用某一种指标 $A=a$ 将原数据 $D$ 分为两类 $D_1$ 与 $D_2$ 之后，在这个分类下，定义此时的基尼指数为 $Gini(D|A) = \frac{|D_1|}{|D|}Gini(D_1) +\frac{|D_2|}{|D|}Gini(D_2)$

　　相比于熵的对数运算，基尼指数只涉及平方与加法运算，所以在大数据量问题上，基尼指数有更快的运行速度。

2.2 CART算法思路

　　CART算法生成的决策树是二叉树，每一步只对某一个指标做出划分。如果特征是离散的取值，那么就对每个特征的每个不同的取值作为二叉树的判定标准，大于或者小于等于该值分成两类，并计算以该点分类后，新节点的信息增益(information entropy)或者基尼指数，以两个子节点的样本数占比进行加权计算；如果特征是连续的取值，那么以每两个相邻的特征取值的算术平均离散化。

　　具体来说，如果某一个特征 $A$ 有 $|D| = n$ 个连续的属性，那么对应的取值从小到大排列为 $a_1,a_2,\dots,a_n$ ，以 $T = \{t|t=\frac{a_i+a_{i+1}}{2} , 1 \leq i \leq n-1 \}$ 为其n-1个划分点，将特征 $A$ 离散化。

2.2.1 算法伪代码

　　设需要分类的数据为 $D$ ，定义数据集内数据量为 $D$ ，属性集 $S$ ，算法的伪代码如下：

① 设定纯度判断阈值 $\epsilon$ 与样本数量阈值 $n_0$ 等防止树过深的参数

② 若 $Gini(D)<\epsilon$ 或 $|D|<n_0$ 或没有特征，则停止，返回当前树，否则转③

③根据所有特征的值进行二分类，选出基尼指数最小或信息增益最大的那个特征的值作为分类依据，得到的两个子数据集 $D_1 , D_2$ 并返回②

2.2.2 计算实例

　　假设有如下数据集，住房一栏中1表示拥有住房，0表示没有住房；婚姻一栏中，0表示单身，1表示已婚，2表示离异；年收入一栏中单位为1000元；拖欠贷款一栏0表示不拖欠，1表示拖欠。

拖欠贷款数据集
住房	婚姻	年收入	拖欠贷款
1	0	125	0
0	1	100	0
0	0	70	0
1	1	120	0
0	2	95	1
0	1	60	0
1	2	220	0
0	0	85	1
0	1	75	0
0	0	90	1

现在我们想构造一个决策树来拟合上述数据，根据前三列的特征数据，训练出一个决策树模型判断某个家庭会不会拖欠银行贷款。在sklearn的决策树CART算法中，其实没有所谓离散变量的特征，它将所有的特征均视为连续特征，根据上述提到的连续特征离散化的方式进行分类。

　　所以，对于住房来说，其分类的标准是以0.5为界限；对于婚姻来说，其分类标准是以0.5与1.5为界限；对于年收入来说，{65,72.5,80,87.5,92.5,97.5,110,122.5,172.5}是其分类指标集。现在依次计算以上述指标为二分类标准对应的基尼指数，如下表所示：

Gini指数
	标准	基尼指数
住房	0.5	0.343
婚姻	0.5	0.367
婚姻	1.5	0.400
年收入	65	0.400
年收入	72.5	0.375
年收入	80	0.343
年收入	87.5	0.417
年收入	92.5	0.400
年收入	97.5	0.300
年收入	110	0.343
年收入	122.5	0.375
年收入	172.5	0.400

　对于基尼指数具体的计算过程，举一个为例，如果以住房0.5为界限，那么会有如下状态表：

	有房	无房
拖欠	0	3
不拖欠	3	4

　假设有住房的数据集为 $D_1$ ，没住房的数据集为 $D_2$ ，则有 $|D_1| = 3$ ， $|D_2| = 7$ ，且有：

$Gini(D_1) = 0$

$Gini(D_2) = 1- p_{default}^2- p_{no\_default}^2 = 1 - (\frac{3}{7})^2 - (\frac{4}{7})^2 \approx 0.4849$

则有：

$Gini(D|\text{House= 0.5}) = \frac{|D_1|}{|D|}Gini(D_1) +\frac{|D_2|}{|D|}Gini(D_2) = 0.343$

　　从上表可以看出，基尼指数最小的是以年收入97.5k为界限的分裂，那么对得到的两个子数据集 $D_1$ 与 $D_2$ 做同样地计算，最后可以得到完整的决策树。

2.2.3 决策树的剪枝处理

　　对于决策树的剪枝处理是为了应对决策树容易出现过拟合现象的应对办法。由于在决策树学习中，为了尽可能正确分类训练样本，节点划分过程将不断重复，有时会造成决策树分支过多，会把训练集自身的一些特点当做所有一般性质而导致过拟合，所以可以通过主动去掉一些分支来降低过拟合的风险。

　　决策树的剪枝方法主要分为两类，“预剪枝”与“后剪枝”，概念如下：

预剪枝(pre-pruning)：预剪枝就是在构造决策树的过程中，先对每个结点在划分前进行估计，若果当前结点的划分不能带来决策树模型泛化性能的提升，则不对当前结点进行划分并且将当前结点标记为叶结点。

后剪枝(post-pruning)：后剪枝就是先把整颗决策树构造完毕，然后自底向上的对非叶结点进行考察，若将该结点对应的子树换为叶结点能够带来泛化性能的提升，则把该子树替换为叶结点。

　　对于这两种剪枝方法，各有优劣，其中后剪枝比预剪枝会保留更多的节点，不容易出现“欠拟合”问题；但是因为是先生成树，再对树进行剪枝，因此，时间开销比预剪枝大。

常用的是，先构建一棵决策树，然后根据特征重要性，筛选出重要的特征，再构建新的决策树。

　　对于预剪枝，在代码中我们可以用设定最大深度max_depth，叶节点最小样本数量min_samples_leaf等方式做到。

　　对于后剪枝，已经有一些比较成熟的算法，REP(Reduced-Error Pruning)、PEP(Pesimistic-Error Pruning)以及CCP(cost complexity pruning)是比较常见的，sklearn库中所运用的后剪枝算法就是CCP算法，ccp_alpha就是与之相关的参数。

　　下面重点说一下CCP算法即代价复杂性剪枝法。CCP算法为子树 $T_t$ 定义了代价和复杂度，以及一个衡量代价与复杂度之间关系的参数 $\alpha$ 。

其中代价指的是在剪枝过程中因子树T_t被叶节点替代而增加的错分样本;

复杂度表示剪枝后子树 $T_t$ 减少的叶结点数; 则表示剪枝后树的复杂度降低程度与代价间的关系，定义为： $\alpha = \frac{R(t)-R(T_t)}{|N|-1}$

① $R(t)$ 为节点 $t$ 的错误代价，有公式： $R(t) = r(t)\cdot p(t)$

② $r(t)$ 为节点 $t$ 的错分样本率： $r(t) = \frac{n_{false}^t} {n^t}$ ，其中 $n_{false}^t$ 为 $t$ 节点被错误划分的样本数量， $n^t$ 为 $t$ 节点总样本数

③ $p(t)$ 表示节点 $t$ 中样本占全部样本的比例： $p(t) = \frac{n^t}{n_{total}}$ ，其中 $n_{total}$ 为总样本数

④ $R(T_t)$ 为节点 $t$ 的子树错误代价，有公式： $R(T_t) = \sum_{i \in S(T_t)} R(j)$ ，其中 $S(T_t)$ 为子树 $T_t$ 所有叶节点集

⑤ $|N|$ 为子树 $T_t$ 中的叶节点数

CCP算法步骤：

①按照上述公式从下往上计算每一个非叶节点的 $\alpha$ 值，每次都减掉 $\alpha$ 值最小的子树，从而得到一个集合 $\{T_0,\dots,T_M\}$ ，其中 $T_0$ 表示之前算法得到的完整的树， $T_M$ 表示之前算法得到的树根。

②在集合 $\{T_0,\dots,T_M\}$ 中选出泛化能力最强的树作为最终的模型。

　　但是在实际的代码中，我们一般会设定一个参数ccp_alpha，然后再对生成的决策树中非叶节点计算其 $\alpha$ ，选出其中最小的而且要小于预设定的ccp_alpha，这个非叶节点才会被剪枝为叶节点。所以最后比较的决策树集合是包含于 $\{T_0,\dots,T_M\}$ 的。

2.3 决策树的Python代码

from sklearn import tree
import numpy as np
from io import StringIO
import pydotplus
X = np.array([[1, 0, 125],[0, 1, 100],[0, 0, 70],[1, 1, 120],
              [0, 2, 95],[0, 1, 60],[1, 2, 220],[0, 0, 85],
              [0, 1, 75],[0, 0, 90]])
y = np.array([[0], [0], [0], [0], [1],
              [0], [0], [1], [0], [1]])
tree_model = tree.DecisionTreeClassifier(criterion='gini', 
                                         max_depth=None,
                                         min_samples_leaf=1,
                                         ccp_alpha=0.0)
tree_model.fit(X, y)
dot_data = StringIO()
feature_names = ['House', 'Marriage', 'Annual salary']
target_names = ['No default', 'Default']
tree.export_graphviz(tree_model,
                     out_file=dot_data,
                     feature_names=feature_names,
                     class_names=target_names,
                     filled=True, 
                     rounded=True,
                     special_characters=True)
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())
graph.write_pdf("default.pdf")

　　针对前述问题，我们可以编写如上代码验证，并通过sklearn.tree中内置的可视化工具将决策树可视化呈现出来得到如下的决策树：

　　在这个决策树中，每个节点的第一行是分裂该节点所用的标准的名字以及数量指标；第二行表示判断纯度的指标；第三行是该节点所含样本数量；第四行表示不同的类别分别有多少样本数；第五行是该节点被标记的类别，以样本数量最多的那个类别为该节点的类别。

　　以这个决策树为例，我们可以来计算一下CCP算法中的 $\alpha$ 值，选择节点序号为1即图中白色框节点为计算对象，有：

$R(t) = \frac{3}{6} \cdot \frac{6}{10} = 0.3$

$R(T_t) = \frac{0}{3}\cdot \frac{3}{10} + \frac{0}{3} \cdot \frac{3}{10} = 0$
$\alpha =\frac{R(t)-R(T_t)}{|N|-1} = \frac{0.3-0}{2-1} =0.3$ 　　

同理，可以算出根节点对应的 $\alpha=0.15$ 。如果ccp_alpha设定的值超过0.30，那么经过后剪枝之后，这个决策树就只有一个节点了，初始设定如果在0.15到0.30之间，由于后剪枝是从下到上裁剪，所以不会直接剪枝到只剩一个根节点。

2.3.1 Python代码解析

①首先从sklearn中导入模组tree；导入numpy生成我们所需要的数据；从io库中导入StringIO模组，这个StringIO是用来将字符串读入内存的模组；导入pydotplus用来将导入内存的字符串转化为图像。

②然后利用numpy的array数组写入我们需要的数据，X是一个10*3的矩阵，表示特征；y是10*1的列向量，表示是否违约的类别。

③接着实例化类tree.DecisionTreeClassifier()为tree_model，其中有四个初始化参数最为重要，一是判断纯度的标准criterion，可以取'gini'或者'entropy'；二是设定树的最大深度max_depth，默认值为None，即没有限制，如果设定为某个整数k，则某个分支的深度达到k之后就不再分裂；三是每个叶节点样本数的最小值min_samples_leaf，默认为1；四是后剪枝算法中的参数ccp_alpha，默认值为0，即不进行后剪枝。实例化完之后利用tree_model.fit(X, y)就可以将模型训练好了。另外还有一些参数也可以用来调节、剪枝决策树，大家可以自行查阅。

④后面的工作是用来可视化我们得到的决策树，首先创建一个内存空间名为dot_data；然后指定我们生成的决策树中特征变量X对应的指标名字以及类的名字，利用tree模组中自带的tree.export_graphviz()函数将模型中的数据传入内存dot_data中，后面三个参数是用来修改最后树的形状的，可以自行设定；最后通过pydotplus画出树，并存到文件"default.pdf"中。

2.3.2 决策树的其他数量指标

　　根据我们上面代码得到的模型tree_model，我们可以接着输入以下代码查看一些数量指标：

x = np.array([[0,1,100]])
print(tree_model.predict(x))
print(tree_model.predict_proba(x))
print(tree_model.apply(x))

　　由于我们这个决策树模型最终得到的就是如果年收入在(80,97.5]区间内则会拖欠，其他情形均不拖欠(不用理会这个模型的合理性)，那么对应的结果分别是：

[0]
[[1. 0.]]
[4]

　第一行表示[0,1,100]这个新数据根据拟合出来的模型会被分类为不拖欠；第二行表示一个概率向量，x取不拖欠的概率是1，拖欠的概率是0；第三行表示x最终被分在哪个节点内，代码中的决策树节点序号排序规则是从上到下，从左到右，根节点序号为0.

　　假如另有一批新数据X_test与y_test，那么利用如下代码可以查看原模型的拟合程度，即可查看这个训练出来的模型在新数据集下的泛化能力，函数所返回的是模型的可决系数 $R^2$ ：

print(tree_model.score(X_test,y_test))

参考：

①相关概念参考周志华《机器学习》

②CCP算法参考决策树-剪枝算法（二） – DreamFaquir – 博客园

③计算例子参考决策树算法–CART分类树算法 – 知乎

来源：登高望远，倚树听泉

Python

物联沃分享整理
物联沃-IOTWORD物联网 » sklearn中的决策树（分类）

代码收藏家普通

分享到：