一些基本概念

决策树简述

决策树（Decision Tree）是数据挖掘中一种基本的分类和回归方法，它呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程，可以认为是if−thenif−then规则的集合。决策树模型的主要优点是模型具有可读性，分类速度快。在学习时，利用训练数据，根据损失函数最小化原则建立决策树模型；而在预测时，对新的数据，利用决策树模型进行分类。主要的决策树算法有ID3算法、C4.5算法和CART算法。一个决策树的学习过程包括三个步骤：特征选择、决策树的生成以及决策树的修剪。

信息熵

信息熵是衡量样本纯度的一种指标，嘉定当前样本集合D中第k类样本所占的比例为$p_k(k=1,2,…,|y|)$,则D的信息熵定义为

$Ent(D)=-\sum_{k=1}^{\vert y\vert}p_klog_2{p_k}$

Ent(D)的值越小，则D的纯度越高。

以周志华西瓜书P76的西瓜数据集中的17个样本数据为例子。

显然，标签类别|y|=2.其中正例占$p_1$=8/17，反例占$p_2$=9/17。于是根节点的信息熵为

$Ent(D)=-\sum_{k=1}^2p_klog_2^{p_k}=-(\frac{8}{17}log_2\frac{8}{17}+\frac{9}{17}log_2\frac{9}{17})=0.998$

条件熵

$Ent(Y|X)$表示在已知随机变量X的条件下随机变量Y的不确定性，定义为X给定条件下Y的条件概率分布的熵对X的数学期望

$Ent\left( Y|X \right) =\sum_{i=1}^n{p_iEnt\left( Y|X=x_i \right)}$

特征选择

信息增益

信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。特征A对训练数据集D的信息增益Gain(D,a)定义为集合D的经验熵$Ent(D)$与特征A给定条件下D的经验条件熵$Ent(Y | X)$之差，即假定离散属性a有n个可能的取值${a^1,a^2,…a^n}$，若使用属性a的取值来对样本集合划分，则会产生n个分支节点子集$D_1,D_2,..,Dn$，$|D_i|$ 为$D_i$的样本个数。(考虑不同的分支节点所包含的样本数不同，用$\frac{|D^i|}{|D|}$代替期望概率$p_i$，即样本越多的分支节点的影响越大)

$Gain(D,a)=Ent(D)-\sum_{i=1}^n\frac{|D^i|}{|D|}End(D^i)$

以西瓜数据集的“色泽”属性为例，它有3个可能的取值{青绿，乌黑，浅白}。若使用该属性对D角线划分，则可以得到三个子集，分布记为$D^1$(色泽=青绿)={1,4,6,10,13,17}，正反例率分别为$p_1=\frac{3}{6}$，$p_2=\frac{3}{6}$；$D^2$(色泽=乌黑)={2,3,7,8,9,15}，正反例率分别为$p_1=\frac{4}{6}$，$p_2=\frac{2}{6}$ ；$D^3$(色泽=乌黑)={5,11,12,14,16}，正反例率分别为$p_1=\frac{1}{5}$，$p_2=\frac{4}{5}$。

首先，根据信息熵公式可计算出“色泽”划分之后所获得的3个分支节点的信息熵为

$Ent(D^1)=-(\frac{3}{6}log_2\frac{3}{6}+\frac{3}{6}log_2\frac{3}{6})=1.000 \\ \\ \\ Ent(D^2)=-(\frac{4}{6}log_2\frac{4}{6}+\frac{2}{6}log_2\frac{2}{6})=0.918 \\ \\ \\ Ent(D^3)=-(\frac{1}{5}log_2\frac{1}{5}+\frac{4}{5}log_2\frac{4}{5})=0.722$

之后根据上面公式可计算出属性“色泽”的信息增益为

$Gain(D,色泽)=Ent(D)-\sum_{i=1}^3\frac{|D^i|}{|D|}Ent(D^i) \\ \\ \\ =0.998-((\frac{6}{17}\times1.000+\frac{6}{17}\times0.918+\frac{5}{17}\times0.722)=0.109$

一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。其中ID3决策树就是以信息增益为准则来选择划分属性。根据得到的属性最大信息增益来划分结果示例如下所示。之后再根据子集样本进一步划分，直到只有一个样本个体或者样本个体都为同一类标签为止。

若我们把样本编号1-17也作为一个划分属性，则根据信息增益公式可计算出它的信息增益为0.998，远大于其他候选划分属性。这很容易理解，“编号”将产生17个分支，每个分支仅包含一个样本，这些分支节点纯度已打最大。然而这些侧介绍显然不具有泛化能力。

所以实际上，信息增益准则对可取数目较多的属性有所偏好；为了减少这种偏好，著名的C4.5决策树算法不直接采用信息增益，而是使用增益率来做最优划分属性。

增益率

增益率定义为其信息增益Gain(D，a)与训练数据集D关于特征a样本数的信息熵之比，增益率的数学定义为

$Gain_{ratio}(D,a)=\frac{Gain(D,a)}{IV(a)}$ $IV(a)=-\sum_{v=1}^n\frac{|D^i|}{|D|}log_2\frac{|D^i|}{|D|}$

（注意子集的划分是属性a样本的可取类别数目n，而不是标签类别|y|了啊），IV(a)可以成为属性a的内在信息，若属性a的可取数目越大，则IV(a)的值通常越大。这样就可以一定程度平衡信息增益对可取数目较多的属性的偏好。以“色泽”为例

$IV(色泽)=-\frac{6}{17}log_2\frac{6}{17}-\frac{6}{17}log_2\frac{6}{17}-\frac{5}{17}log_2\frac{5}{17}=1.580$

另外，需要注意的是，增益率准则对可取数值数目较少的属性有所偏好，因此，C4.5算法并不是直接选择增益率最大的候选划分属性，而是先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率的最高的。

基尼指数

数据集D的纯度可以用基尼指数来度量，Gini（D）越小，则数据集D的纯度越高。假设有K个类，样本点属于第k类的概率为$p_k$，则概率分布的基尼系数定义为

$Gini\left( p \right) =\sum_{k=1}^K{p_k\left( 1-p_k \right) =1-\sum_{k=1}^K{p_k^2}}$

根据基尼指数定义，可以得到样本集合D的基尼指数，其中$D_k$表示数据集D中属于第k类的样本子集

$Gini(D)=1-\sum_{k=1}^{K}\left(\frac{|D_k|}{|D|} \right)^2$

若样本集合D根据特征A是否取某一可能值a被分割成$D_1$和$D_2$两部分，即

$D_1=\left\{ \left( x,y \right) \in D|A\left( x \right) =0 \right\} \mathrm{，}D_2=D-D_1$

则在特征A的条件下，集合D的基尼指数定义为

$Gini\left( D,A \right) =\frac{|D_1|}{|D|}Gini\left( D_1 \right) +\frac{|D_2|}{|D|}Gini\left( D_2 \right)$

基尼系数Gini(D)表示集合D的不确定性，基尼系数Gini(D,A)表示A=a分割后集合D的不确定性。基尼指数越大，样本集合的不确定性越大。对于属性A，分别计算任意属性值将数据集划分为两部分之后的Gain_Gini，选取其中的最小值，作为属性A得到的最优二分方案。然后对于训练集S，计算所有属性的最优二分方案，选取其中的最小值，作为样本及S的最优二分方案。

$\min_{i\epsilon A}(Gain\_Gini(D,A))$ $\min_{A\epsilon Attribute}(\min_{i\epsilon A}(Gain\_Gini(D,A)))$

剪枝

剪枝是决策树学习算法对付“过拟合”的主要手段。在决策树学习中，为了尽可能正确分类样本，节点划分过程不断重复，有时会造成决策树分支过多，这时有时候把自身特点当做所有数据都具有的一般性质而导致过拟合，因此，可以通过主动去掉一些分支来降低过拟合的风险

基本策略有预剪枝和后剪枝，预剪枝是指在决策树生成过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能的提升，则停止划分当前节点标记为叶节点；后剪枝则是先从训练集生成一颗完整的决策树，然后自底向上地对非叶节点进行考察，若将该节点对应的字数替换为叶节点能带来决策树泛化性能提升，则将该子树替换为叶节点。

CART决策树的生成

ID3算法和C4.5按照信息增益和增益率最大的特征作为节点特征，然后递归构建。比较简单，还要注意这两种方法都容易过拟合。这里主要讲一下CART分类与回归树。

分类树与回归树（classification and regression tree，CART）模型（Breiman）由特征选择、树生成及剪枝组成，既可用于分类也可用于回归。CART算法采用二分递归分割的技术将当前样本集分为两个子样本集，使得生成的每个非叶子节点都有两个分支。因此CART算法生成的决策树是结构简洁的二叉树。CART可以处理连续型变量和离散型变量，利用训练数据递归的划分特征空间进行建树，用验证数据进行剪枝。利用训练数据递归的划分特征空间进行建树，用验证数据进行剪枝。

如果待预测分类是离散型数据，则CART生成分类决策树。
如果待预测分类是连续性数据，则CART生成回归决策树。

CART分类树

对分类树用基尼系数（Gini index）最小化准则，进行特征选择，生成二叉树。

具体算法步骤如下：

1）设结点的训练数据集为D，计算现有特征对该数据集的基尼指数。此时，对每一个特征A，对其可能取的每个值a，根据样本点对A=a的测试为”是”或者“否”将D分割为D1和D2两部分，计算其基尼系数。
2）在所有可能的特征A以及他们所有可能的切分点a中，选择基尼系数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。
3）对两个子结点递归地调用上述两个步骤，直至满足停止条件。
4）生成CART决策树

以生物特征分类数据为例

针对上述离散型数据，按照体温为恒温和非恒温(多类别属性也按’非’分成两类别)进行划分。其中恒温时包括哺乳类5个、鸟类2个，非恒温时包括爬行类3个、鱼类3个、两栖类2个，如下所示我们计算以体温为划分特征D1,D2的基尼指数。

$Gini(D_1)=1-[ (\frac{5}{7})^2+(\frac{2}{7})^2]=\frac{20}{49}$ $Gini(D_2)=1-[ (\frac{3}{8})^2+(\frac{3}{8})^2+(\frac{2}{8})^2]=\frac{42}{64}$

然后计算得到特征体温下数据集的Gini指数，最后我们选择Gain_Gini最小的特征和相应的划分

$Gain\_Gini(D,体温)=\frac{7}{15}*\frac{20}{49}+\frac{8}{15}*\frac{42}{64}$

在所有可能的特征A以及他们所有可能的切分点a中的二分划分中，选择基尼系数最小的特征及其对应的切分点作为最优特征与最优切分点，依次递归。

CART回归树

回归树衡量最好的标准不再是最大熵，而是最小化均方差。而且在每个节点（不一定是叶子节点）都会得一个预测值，这个预测值可为所有样本的平均值。我们利用最小二乘回归树生成算法来生成回归树f(x)，即在训练数据集所在的输入空间中，递归地将每个区域分为两个子区域并决定每个子区域上的输出值，构建二叉决策树。

回归树算法流程：j为选定的某个特征属性，s为在这个特征上的切分数值（需要遍历所有特征和切分点来选到最小化均方差），R1R2为切分的样本，C1C2为切分区域样本中的特征均值。

实例详解：

考虑如上所示的连续性变量，根据给定的数据点，考虑1.5,2.5,3.5,4.5,5.5,6.5,7.5,8.5,9.5共9个自定均分的切分点。对各切分点依次求出R1,R2,c1,c2及m(s)，例如当切分点s=1.5时，得到R1={1},R2={2,3,4,5,6,7,8,9,10}，其中c1,c2,m(s)如下所示

$c_1=\frac{1}{N_m}\sum_{x_i\epsilon R_m(j,s)}y_i=\frac{1}{1}\sum_{x_i\epsilon R_1(1,1.5)}5.56=5.56$ $c_2=\frac{1}{N_m}\sum_{x_i\epsilon R_m(j,s)}y_i=\frac{1}{9}\sum_{x_i\epsilon R_2(1,1.5)}(5.70+5.91+...+9.05)=7.50$ $m(s)=\min_{j,s}[\min_{c_1}\sum _{x_i\epsilon R_i(j,s)}(y_i-c_1)^2+\min_{c_2}\sum _{x_i\epsilon R_i(j,s)}(y_i-c_1)^2]=0+15.72=15.72$

依次改变(j,s)对，可以得到s及m(s)的计算结果，如下表所示。

当x=6.5时，此时R1={1,2,3,4,5,6},R2={7,8,9,10},c1=6.24,c2=8.9。回归树T1(x)为

$T_1(x)=\begin{cases} & 6.24,x<6.5 \\ & 8.91,x\ge 6.5 \end{cases}$ $f_1(x)=T_1(x)$

然后我们利用f1(x)拟合训练数据的残差(各目标值减去对应的c1,c2)，如下表所示

用f1(x)拟合训练数据得到平方误差

$L(y,f_1(x))=\sum_{i=1}^{10}(y_i-f_1(x_i))^2=1.93$

第二步求T2(x)与求T1(x)方法相同，只是拟合的数据是上表的残差。可以得到

$T_2(x)=\begin{cases} & -0.52,x<3.5 \\ & 0.22,x\ge 3.5 \end{cases}$ $f_2(x)=f_1(x)+T_2(x)= \begin{cases} & 5.72,x<3.5 \\ & 6.46,3.5\le x \le 6.5 \\ & 9.13,x\ge 6.5 \end{cases}$

用f2(x)拟合训练数据的平方误差

$L(y,f_2(x))=\sum_{i=1}^{10}(y_i-f_2(x_i))^2=0.79$

继续求得T3(x)、T4(x)、T5(x)、T6(x)，如下所示

$T_3(x)=\begin{cases} & 0.15,x<6.5 \\ & -0.22,x\ge 6.5 \end{cases} L(y,f_3(x))=0.47$ $T_4(x)=\begin{cases} & -0.16,x<4.5 \\ & 0.11,x\ge 4.5 \end{cases} L(y,f_4(x))=0.30$ $T_5(x)=\begin{cases} & 0.07,x<6.5 \\ & -0.11,x\ge 6.5 \end{cases} L(y,f_5(x))=0.23$ $T_6(x)=\begin{cases} & -0.15,x<2.5 \\ & 0.04,x\ge 2.5 \end{cases}$ $f_6(x)=f_5(x)+T_6(x)=T_1(x)+...+T_6(x)= \begin{cases} & 5.63,x<2.5 \\ & 5.82,2.5\le x \le 3.5 \\ & 6.56,3.5\le x \le 4.5 \\ & 6.83,4.5\le x \le 6.5 \\ & 8.95,x\ge 6.5 \end{cases}$

用f6(x)拟合训练数据的平方损失误差如下所示，假设此时已经满足误差要求，那么f(x)=f6(x)便是所求的回归树。

$L(y,f_6(x))=\sum_{i=1}^{10}(y_i-f_6(x_i))^2=0.71$

CART剪枝

们将一颗充分生长的树称为T0 ，希望减少树的大小来防止过拟化。但同时去掉一些节点后预测的误差可能会增大，即完整树T0拟合的损失是最小的。那么如何达到这两个变量之间的平衡则是问题的关键。因此我们用一个变量α 来平衡，定义损失函数如下

$C_\alpha(T)=C(T)+\alpha|T|$

T为任意子树，|T|为子树T的叶子节点个数。
α是参数，权衡拟合程度与树的复杂度。
C(T)为预测误差，可以是平方误差也可以是基尼指数，C(T)衡量训练数据的拟合程度。

那么我们如何找到这个合适的α来使拟合程度与复杂度之间达到最好的平衡呢？准确的方法就是将α从0取到正无穷，对于每一个固定的α，我们都可以找到使得$C_\alpha(T)$最小的最优子树T(α)。

当α很小的时候(相当于弱化正则)，T0 完整树是这样的最优子树.
当α很大的时候(相当于强化正则)，单独一个根节点就是最优子树。

Breiman等人证明：可以用递归地方法对树进行剪枝。将a从小增大，$0=a_0<a_1<…..a_n<+∞$产生一系列的区间$[a_i,a_i+1),i=0,1,…,n$剪枝得到的子树序列对应着区间$a∈[a_i,a_i+1)，i=0,1,2,…,n$的最优子树序列为${T_0,T_1,T_2,…,T_n}$,序列的子树是嵌套的。

具体地，从整体树$T_0$开始剪枝，对$T_0$的人以内部结点t，以t为单结点树的损失函数是

$C_a\left( t \right) =C\left( t \right) +a$

以t为根结点的子树$T_t$的损失函数是

$C_a(T_t)=C(T_t)+a|T_t|$

到这里，我们的目的就变得很明确了，当t为单节点树的损失比以t为根节点的子树$T_t$损失相等的时候，损失相同，而t的节点少，就进行剪枝操作。其过程会随a由0逐渐增大，单节点树t损失一开始大于子树$T_t$，随后不断减少，直到大于子树损失。具体的，当$\alpha =\frac{C\left( t \right) -C\left( T_t \right)}{|T_t|-1}$ ，$T_t$和t有相同的损失。

为此，对$T_0$中的每一个内部结点t，计算

$g\left( t \right) =\frac{C\left( t \right) -C\left( T_t \right)}{|T_t|-1}$

它表示剪枝后整体损失函数减少的程度。在$T_0$中减去g(t)最小的$T_t$，将得到的子树作为$T_1$，同时将最小的g(t)设为$a_1$，$T_1$为区间$[a_1,a_2)$的最优子树。如此剪枝下去，直至得到根结点。在这一过程中，不断得增加a的值，产生新的区间。

然后，在剪枝得到的子树序列$T_0,T_1,…,T_n$中通过交叉验证选取最优子树$T_a$.

具体地，利用独立的验证数据集，测试子树序列$T_0,T_1,…,T_n$中各棵子树的平方误差或基尼指数。平方误差或基尼指数最小的决策树被认为是最优的决策树。在子树序列中，每棵子树$T_0,T_1,…,T_n$都对应一个参数$a_1,a_2,…,a_n$。所以当最优子树$T_k$确定时，对应的$a_k$也就确定了，即得到最由决策树$T_a$.

应用

决策树分类边界

另外，决策树所形成的分类边界有一个明显的特点：轴平行，即它的分类边界有若干个与坐标轴平行的分段组成。

决策树的训练和可视化

下面的代码就是在我们熟知的鸢尾花数据集上进行一个决策树分类器的训练

决策树的众多特性之一就是，它不需要太多的数据预处理，尤其是不需要进行特征的缩放或者归一化。

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier
iris = load_iris()
X = iris.data[:, 2:] # petal length and width y = iris.target
    tree_clf = DecisionTreeClassifier(max_depth=2)
    tree_clf.fit(X, y)

你可以通过使用export_graphviz()方法，通过生成一个叫做iris_tree.dot的图形定义文件将一个训练好的决策树模型可视化

from sklearn.tree import export_graphviz
    export_graphviz(
            tree_clf,
            out_file=image_path("iris_tree.dot"),
            feature_names=iris.feature_names[2:],
            class_names=iris.target_names,
            rounded=True,
            filled=True
        )

然后，我们可以利用graphviz package 中的dot命令行，将.dot文件转换成 PDF 或 PNG 等多种数据格式。例如，使用命令行将.dot文件转换成.png文件的命令如下：

Graphviz是一款开源图形可视化软件包，http://www.graphviz.org/

1	$ dot -Tpng iris_tree.dot -o iris_tree.png

我们的第一个决策树如图

节点的samples属性统计出它应用于多少个训练样本实例，例如，我们有一百个训练实例是花瓣长度大于 2.45 里面的（深度为 1，右侧），在这 100 个样例中又有 54 个花瓣宽度小于 1.75cm（深度为 2，左侧）；节点的value属性告诉你这个节点对于每一个类别的样例有多少个，例如：右下角的节点中包含 0 个 Iris-Setosa，1 个 Iris-Versicolor 和 45 个 Iris-Virginica；最后，节点的Gini属性用于测量它的纯度：如果一个节点包含的所有训练样例全都是同一类别的，我们就说这个节点是纯的（Gini=0）

下面公式显示了训练算法如何计算第i个节点的 gini 分数。例如，深度为 2 的左侧节点基尼指数为：

$G_i=\sum_{k=1}^nP_{i,k}^2$

$p_{i,k}$ 是第i个节点中训练实例为的k类实例的比例

Scikit-Learn 用的是 CART 算法， CART 算法仅产生二叉树：每一个非叶节点总是只有两个子节点（只有是或否两个结果）。然而，像 ID3 这样的算法可以产生超过两个子节点的决策树模型

下图显示了决策树的决策边界。粗的垂直线代表根节点（深度为 0）的决定边界：花瓣长度为 2.45 厘米。由于左侧区域是纯的（只有 Iris-Setosa），所以不能再进一步分裂。然而，右边的区域是不纯的，所以深度为 1 的右边节点在花瓣宽度为 1.75 厘米处分裂（用虚线表示）。又由于max_depth设置为 2，决策树在那里停了下来。但是，如果将max_depth设置为 3，两个深度为 2 的节点，每个都将会添加另一个决策边界（用虚线表示）

估计分类概率

决策树还可以估计某个实例属于特定类k的概率：首先遍历树来查找此实例的叶节点，然后它返回此节点中类k的训练实例的比例。

例如，假设你发现了一个花瓣长 5 厘米，宽 1.5 厘米的花朵。相应的叶节点是深度为 2 的左节点，因此决策树应该输出以下概率：Iris-Setosa 为 0%（0/54），Iris-Versicolor 为 90.7%（49/54），Iris-Virginica 为 9.3%（5/54）。当然，如果你要求它预测具体的类，它应该输出 Iris-Versicolor（类别 1），因为它具有最高的概率。我们了测试一下

>>> tree_clf.predict_proba([[5, 1.5]])
array([[ 0. , 0.90740741, 0.09259259]])
>>> tree_clf.predict([[5, 1.5]])
array([1])

CART 训练算法

Scikit-Learn 用分裂回归树（Classification And Regression Tree，简称 CART）算法训练决策树（也叫“增长树”）。这种算法思想真的非常简单：

首先使用单个特征k和阈值$t_k$ (例如，“花瓣长度≤2.45cm”）将训练集分成两个子集。它如何选择k和$t_k$ 呢？它寻找到能够产生最纯粹的子集一对(k,$t_k$) ，然后通过子集大小加权计算.

算法会尝试最小化成本函数。方法如公式

当它成功的将训练集分成两部分之后，它将会继续使用相同的递归式逻辑继续的分割子集，然后是子集的子集。当达到预定的最大深度之后将会停止分裂（由max_depth超参数决定），或者是它找不到可以继续降低不纯度的分裂方法的时候。几个其他超参数（之后介绍）控制了其他的停止生长条件（min_samples_split，min_samples_leaf，min_weight_fraction_leaf，max_leaf_nodes）。

正如您所看到的，CART 算法是一种贪婪算法：它贪婪地搜索最高级别的最佳分割方式，然后在每个深度重复该过程。它不检查分割是否能够在几个级别中的全部分割可能中找到最佳方法。贪婪算法通常会产生一个相当好的解决方法，但它不保证这是全局中的最佳解决方案

计算复杂度

在建立好决策树模型后，做出预测需要遍历决策树，从根节点一直到叶节点。决策树通常近似左右平衡，因此遍历决策树需要经历大致 $O(log_2^m)$ 个节点。由于每个节点只需要检查一个特征的值，因此总体预测复杂度仅为$O(log_2^m)$ ，与特征的数量无关。所以即使在处理大型训练集时，预测速度也非常快.

然而，训练算法的时候（训练和预测不同）需要比较所有特征（如果设置了max_features会更少一些）
在每个节点的所有样本上。就有了$O(nmlog_2^m)$的训练复杂度。对于小型训练集（少于几千例），Scikit-Learn 可以通过预先设置数据（presort = True）来加速训练，但是这对于较大训练集来说会显着减慢训练速度。

基尼不纯度或是信息熵

通常，算法使用 Gini 不纯度来进行检测，但是你也可以通过将标准超参数设置为”entropy”来使用熵不纯度进行检测。这里熵的概念是源于热力学中分子混乱程度的概念，当分子井然有序的时候，熵值接近于 0

那么我们到底应该使用 Gini 指数还是熵(ID3,C4.5决策树)呢？事实上大部分情况都没有多大的差别：他们会生成类似的决策树。基尼指数计算稍微快一点，所以这是一个很好的默认值。但是，也有的时候它们会产生不同的树，基尼指数会趋于在树的分支中将最多的类隔离出来，而熵指数趋向于产生略微平衡一些的决策树模型。

正则化超参数

决策树几乎不对训练数据做任何假设（于此相反的是线性回归等模型，这类模型通常会假设数据是符合线性关系的）。

如果不添加约束，树结构模型通常将根据训练数据调整自己，使自身能够很好的拟合数据，而这种情况下大多数会导致模型过拟合。

这一类的模型通常会被称为非参数模型，这不是因为它没有任何参数（通常也有很多），而是因为在训练之前没有确定参数的具体数量，所以模型结构可以根据数据的特性自由生长。

DecisionTreeClassifier类还有一些其他的参数用于限制树模型的形状:

min_samples_split（节点在被分裂之前必须具有的最小样本数），min_samples_leaf（叶节点必须具有的最小样本数），min_weight_fraction_leaf（和min_samples_leaf相同，但表示为加权总数的一小部分实例），max_leaf_nodes（叶节点的最大数量）和max_features（在每个节点被评估是否分裂的时候，具有的最大特征数量）。增加min_hyperparameters或者减少max_hyperparameters会使模型正则化
预剪枝与后剪枝

下图显示了对moons数据集进行训练生成的两个决策树模型，左侧的图形对应的决策树使用默认超参数生成（没有限制生长条件），右边的决策树模型设置为min_samples_leaf=4。很明显，左边的模型过拟合了，而右边的模型泛用性更好。

回归

决策树也能够执行回归任务，让我们使用 Scikit-Learn 的DecisionTreeRegressor类构建一个回归树，让我们用max_depth = 2在具有噪声的二次项数据集上进行训练。

1
2
3

from sklearn.tree import DecisionTreeRegressor
tree_reg = DecisionTreeRegressor(max_depth=2)
tree_reg.fit(X, y)

结果如图：

这棵树看起来非常类似于你之前建立的分类树，它的主要区别在于，它不是预测每个节点中的样本所属的分类，而是预测一个具体的数值。例如，假设您想对的新实例进行预测。从根开始遍历树，最终到达预测值等于 0.1106 的叶节点。该预测仅仅是与该叶节点相关的 110 个训练实例的平均目标值。而这个预测结果在对应的 110 个实例上的均方误差（MSE）等于 0.0151

下图的左侧显示的是模型的预测结果，如果你将max_depth=3设置为 3，模型就会如 6-5 图右侧显示的那样.注意每个区域的预测值总是该区域中实例的平均目标值。算法以一种使大多数训练实例尽可能接近该预测值的方式分割每个区域。

译者注：图里面的红线就是训练实例的平均目标值，对应上图中的value

CART 算法的工作方式与之前处理分类模型基本一样，不同之处在于，现在不再以最小化不纯度的方式分割训练集，而是试图以最小化 MSE 的方式分割训练集

下面公式显示了成本函数，该算法试图最小化这个成本函数。

和处理分类任务时一样，决策树在处理回归问题的时候也容易过拟合。如果不添加任何正则化（默认的超参数），你就会得到图 6-6 左侧的预测结果，显然，过度拟合的程度非常严重。而当我们设置了min_samples_leaf = 10，相对就会产生一个更加合适的模型了，就如图 6-6 所示的那样

不稳定性

它很容易理解和解释，易于使用且功能丰富而强大。然而，它也有一些限制，首先，你可能已经注意到了，决策树很喜欢设定正交化的决策边界，（所有边界都是和某一个轴相垂直的），这使得它对训练数据集的旋转很敏感，例如图 6-7 显示了一个简单的线性可分数据集。在左图中，决策树可以轻易的将数据分隔开，但是在右图中，当我们把数据旋转了 45° 之后，决策树的边界看起来变的格外复杂。尽管两个决策树都完美的拟合了训练数据，右边模型的泛化能力很可能非常差。

解决这个难题的一种方式是使用 PCA 主成分分析，这样通常能使训练结果变得更好一些。

更加通俗的讲，决策时的主要问题是它对训练数据的微小变化非常敏感，举例来说，我们仅仅从鸢尾花训练数据中将最宽的 Iris-Versicolor 拿掉（花瓣长 4.8 厘米，宽 1.8 厘米），然后重新训练决策树模型，你可能就会得到图 6-8 中的模型。正如我们看到的那样，决策树有了非常大的变化（原来的如图 6-2），事实上，由于 Scikit-Learn 的训练算法是非常随机的，即使是相同的训练数据你也可能得到差别很大的模型（除非你设置了随机数种子）

练习题

在 100 万例训练集上训练（没有限制）的决策树的近似深度是多少？
节点的基尼指数比起它的父节点是更高还是更低？它是通常情况下更高/更低，还是永远更高/更低？
如果决策树过拟合了，减少最大深度是一个好的方法吗？
如果决策树对训练集欠拟合了，尝试缩放输入特征是否是一个好主意？
如果对包含 100 万个实例的数据集训练决策树模型需要一个小时，在包含 1000 万个实例的培训集上训练另一个决策树大概需要多少时间呢？
如果你的训练集包含 100,000 个实例，设置presort=True会加快训练的速度吗？

1、$log_210^6\approx20$

2、子节点的基尼指数通常比父节点更低，这是由CART训练树损失函数决定的，它只会每次减少子节点权重求和后的Gini指数。然而子节点的Gini并不会永远小于父节点，比如现在根节点包括{A B A A A}五个样本，其Gini为$1-\frac{1}{5}^2-\frac{4}{5}^2=0.32$，划分样本后为{A B}和 {A A A} ，Gini分别为0.5和0。权重求和后的Gini为$\frac{2}{5}\times0.5+\frac{3}{5}\times0=0.2$，其Gini指数划分后只会比原来的更小。

3、如果决策树过度拟合训练集，那么减少max_depth是个不错的选择。

4、决策树不关心训练数据是否缩放或居中，这是他们的优势之一。因此，如果决策树如果欠拟合，缩放输入功能只会浪费时间。

5、训练决策树的时间复杂度为$O(nmlog_2m)$，m为样本数，n为特征数。所以训练样本增加十倍，其训练时间会增加$K=(n\cdot 10m\cdot log_2(10m))=10\times log(10m)/log(m)$.如果m=10^6,则K$\approx$11.7

6、仅当数据集小于几千个实例时，预先训练训练集能加速训练。如果它包含100,000个实例，则设置presort = True将大大减慢训练速度。