决策树(descision tree)(分类树)

1. 决策树的基本概念

1.1 概念

决策树是一种根本的分类于回归办法，在分类问题中，示意基于特色对实例进行分类的过程。

1.2 决策树的三个根本步骤

• 特征选择
• 决策树的生成
• 决策树的修剪

1.3 用决策树分类

从 根节点 开始，对实例的某一特色进行测试，依据测试后果将实例调配到其 子节点 ，此时每一个子节点对应着该特色的一个取值，如此递归对实例进行测试并调配，直到达到 叶节点 ，最初将实例分到 叶节点 的类中。

<!–more–>

其中圆点是 外部节点 ，方框是 叶节点

要害概念：结点

1. 根节点：没有进边，有出边，蕴含最后的，针对特色问题发问
2. 两头节点：即有进边也有出边，进边只有一条，出边能够有很多条，都是针对特色问题发问
3. 叶子节点：有进边，没有出边，每一个叶子节点都是一个类别的标签

1.4 决策树的其余信息

• 决策树学习的指标：依据训练数据形成一个模型，而后对未知数据可能进行正当的分类
• 决策树的实质：从训练集中演绎出一组分类规定，或者说是由训练数据集预计 条件概率模型
• 决策树学习的损失函数：正则化的极大似然函数
• 决策树学习的测试：最小化损失函数
• 决策树学习的指标：在损失函数的意义下，抉择最优决策树的问题
• 决策树原理和问答猜想后果游戏类似，依据一系列数据，而后给出游戏的答案。(就是始终问问题)

1.5 决策树算法外围问题

1. 如何从数据表中找出最佳节点和最佳分枝？
2. 如何让决策树进行成长，避免过拟合？

2. 决策树的结构

2.1 决策树结构步骤

决策树学习的算法通常是一个递归地抉择最优特色，并依据该特色对训练数据进行宰割，使得各个子数据集有一个最好的分类的过程。这一过程对应着对特色空间的划分，也对应着决策树的构建。

1. 构建根节点，将所有的训练数据都放在根节点，抉择一个最优特色，按着这一特色将训练数据集宰割成子集，使得各个子集有一个在以后条件下最好的分类
2. 如果这些子集可能根本被正确分类，那么构建叶节点，并将这些子集分到对应的叶节点去。
3. 如过还有子集不可能被正确的分类，那么就对这些子集从新选最优特色，持续对其进行宰割，构建相应的节点，如果递归进行，晓得所有训练数据子集根本正确的分类，或者没有适合的特色为止。
4. 每个子集都分到叶节点上，即都有了明确的类，这样就生成了一个决策树。

2.2 决策树的特点

• 长处：计算复杂程度不高，输入后果好了解，两头值缺失不敏感，能够解决不相干特色数据。
• 毛病：可能会产生适度匹配的问题。
• 应用数据类型：数值型和标签型。

首先：确定以后数据集上的决定性特色，为了失去该决定性特色，必须评估每个特色，实现测试之后，原始数据集就被划分为几个数据子集，这些数据子集会散布在第一个决策点的所有分支上，如果某个分支下的数据属于同一类型，则以后无需浏览的垃圾邮件曾经正确的划分数据分类，无需进一步对数据集进行宰割，如果不属于同一类，则要反复划分数据子集，直到所有雷同类型的数据均在一个数据子集内。

2.3 决策树伪代码

创立分支的伪代码 createBranch()

检测数据集中每一个子项是否属于同一类：

if so return 类标签
else
    寻找划分数据集的最好特色
    划分数据集
    创立分支节点
        for 每个划分的子集
            调用 createBranch()并且返回后果到分支节点中
        return 分支节点

2.4 信息增益

2.4.1 简略概述

划分数据集的大准则是：将无序数据变得更加有序，信息论是量化解决信息得分支迷信，在划分数据集前后信息产生得变动称为 信息增益 ， 取得信息增益最高的特色就是最好的抉择 ，汇合信息的度量形式称为： 香农熵 ，或者简称为 熵。

2.4.2 联合实例

心愿通过所给的训练数据学习一个贷款申请的决策树，用以对将来的贷款申请进行分类，即当新的客户提出贷款申请时，依据申请人的特色利用决策树决定是否批准贷款申请。

特征选择就是决定用哪个特色来划分特色空间。

第一个图的根节点的特色是年龄，有 3 个取值，不同的取值有不同的节点。第二个图的根节点的特色是工作，有 2 个取值，不同的取值有不同的节点。两个决策树都能够延续下去，然而，咱们应该选取那一个特色更好一些呢？一般来说，如果一个特色具备更好的分类能力，或者说，依照这个特色将数据集宰割的子集，使得各个子集在以后条件下有最好的分类，那么就更应该抉择这个特色。

2.4.3 信息增益和教训熵

什么是信息增益？在划分数据集之前之后信息产生的变动成为信息增益，晓得如何计算信息增益，咱们就能够计算每个特征值划分数据集取得的信息增益，取得信息增益最 高的特色就是最好的抉择。

熵定义为信息的冀望，在待分类的事物可能划分在多个类中，则 $x_{i}$ 的信息定义为：

$$
l(x_{i})=-log_{2}p(x_i)
$$

其中 $p(x_{i})$ 是该分类的概率。

为了计算熵，咱们须要计算所有类别所有可能值所蕴含的信息期望值，通过下式失去：

$$
H=-\sum_{i=1}^{n}p(x_{i})log_{2}p(x_{i})
$$

其中 n 是分类的数目，n 为分类数目，熵越大，随机变量的不确定性就越大。

当熵中的概率是由数据计算的时候，咱们就称为教训熵。数据计算就是比方有 10 个数据，一共有两个类别，A 类和 B 类。其中有 7 个数据属于 A 类，则该 A 类的概率即为非常之七。其中有 3 个数据属于 B 类，则该 B 类的概率即为非常之三。通俗的解释就是，这概率是咱们依据数据数进去的。咱们定义贷款申请样本数据表中的数据为训练数据集 D，则训练数据集 D 的教训熵为 H(D)，|D| 示意其样本容量，及样本个数。假如共有 k 个类 $C_{k}, k=1,2,3..,k，|C_{k}|$ 为属于类 $C_{k}$ 的样本个数，所以教训熵公式能够写为：

$$
H(D)=-\sum_{k=1}^{K}\frac{|C_{k}|}{|D|}log_{2}\frac{|C_{k}|}{|D|}
$$

依据此公式计算教训熵 H(D)，剖析贷款申请样本数据表中的数据。最终分类后果只有两类，即放贷和不放贷。依据表中的数据统计可知，在 15 个数据中，9 个数据的后果为放贷，6 个数据的后果为不放贷。所以数据集 D 的教训熵 H(D)为：

$$
H(D)=-\frac{9}{15}log_{2}\frac{9}{15}-\frac{6}{15}log_{2}\frac{6}{15}=0.971
$$

所以，经计算可知，数据集 D 的教训熵 H(D)为 0.971

2.4.4 信息增益和条件熵

信息增益示意得悉特色 X 的信息而使得类 Y 的信息不确定性缩小的水平。

条件熵 H(Y|X)示意在已知随机变量 X 的条件下随机变量 Y 的不确定性，定义 X 给定条件下 Y 的条件概率分布的熵对 X 的数学冀望：

$$
H(Y|X)=\sum_{i=1}^{n}p_{i}H(Y|X=x_{i})
$$

其中，$p_{i}=p(X=x_{i})$

当熵和条件熵中的概率由数据预计（特地是极大似然预计）失去时，所对应的别离为教训熵和教训条件熵，此时如果有 0 概率，则令 $0log0=0$

信息增益 ：信息增益是绝对于特色而言的。所以，特色 A 对训练数据集 D 的信息增益 $g(D,A)$，定义为汇合 D 的教训熵 H(D) 与特色 A 给定条件下汇合 D 的教训条件熵 $H(D|A)$ 之差，即：

$$
g(D,A)=H(D)-H(D|A)
$$

个别地，熵 H(D)与条件熵 H(D|A)之差成为 互信息(mutual information)。决策树学习中的信息增益等价于训练数据集中类与特色的互信息。

信息增益值的大小绝对于训练数据集而言的，并没有相对意义，在分类问题艰难时，也就是说在训练数据集教训熵大的时候，信息增益值会偏大，反之信息增益值会偏小，应用信息增益比能够对这个问题进行校对，这是特征选择的另一个规范。

信息增益比：特色 A AA 对训练数据集 D 的信息增益比 $g_{R}(D,A)$ 定义为其信息增益 $g(D,A)$ 与训练数据集 D 对于特色 A 的教训熵之比：

$$
g_{R}(D,A)=\frac{g(D,A)}{H\_A(D)}
$$

3. sklearn 中的决策树

3.1 模块 sklearn.tree

sklearn 中的决策树都在 tree 这个模块下，这个模块蕴含五个类：

3.2 sklearn 的根本建模流程

1. 实例化，建设评估模型对象(实例化时须要应用的参数)
2. 通过模型接口训练模型(将训练样本放入其中)
3. 通过模型接口提取须要的信息

这个流程中，分类树对应代码如下：

# 导入须要的模块
from sklearn import tree

# 实例化
clf = tree.DecisionTreeClassifier()
# 导入训练集数据，用来训练模型
clf = clf.fit(x_train, y_train)
# 导入测试集数据，而后通过接口取得想要的信息
result = clf.score(x_test, y_test)

3.3 重要参数

3.3.1 criterion

为了要将表格转化为一棵树，决策树要找到最佳节点和最佳的分枝办法，对分类树来说，掂量这个算法的叫做“不纯度”。通常来说，不纯度越低，决策树对训练集的拟合越好，目前应用的决策树算法在分枝上大都是围绕某个不纯度相干指标的最优化上。

树中的每一个节点都有一个不纯度，并且子节点的不纯度肯定低于父节点的不纯度。

criterion 这个参数决定不纯度的计算方法。sklearn 提供了两种抉择：

1. 输出‘entropy’，应用 信息熵
2. 输出‘gini’，应用基尼系数

$$
Entropy(t)=-\sum_{i=0}^{c-1}p(i|t)log_{2}p(i|t)
$$

$$
Gini(t)=1-\sum_{i=0}^{c-1}p(i|t)^2
$$

其中 $t$ 代表给定的节点 (上述中的数据集 D)，$i$ 代表标签的任意分类，$P(i|t)$ 代表标签分类 $i$ 在节点 $t$ 上所占的比例。sklearn 理论计算的是基于信息熵的 信息增益，即是父节点的信息熵和子节点的信息熵之差。

信息熵对不纯度更加敏感，对不纯度的惩办最强。然而在理论利用中，信息熵和基尼系数基本相同。信息熵波及到了对数，所以它的计算会比基尼系数要慢一些。信息熵更敏感，所以信息熵作为指标时，决策树会更加“精密”，因而对于高维数据或者噪声很多的数据时，避免过拟合，基尼系数会比拟好，但并不是相对的。

3.3.2 根本流程概括

1. 计算全副特色党的不纯度指标
2. 选取不纯度指标最优的特色来分枝
3. 在第一个特色的分枝下，计算全副特色的不纯度
4. 选取指标最优的特色持续分枝

晓得没有特色可用，或整体的不纯度指标曾经最优，决策树就会进行成长。

3.3.3 sklearn 实例和一些问题

以 sklearn 中的红酒数据集为例

数据的导入与训练

# 对模块和数据的导入
from sklearn import tree
from sklearn.datasets import load_wine
# 这个包是用来宰割数据的
from sklearn.model_selection import train_test_split
import pandas as pd

# 导入数据
wine = load_wine()

# 将导入的数据合并成表
pd.concat([pd.DataFrame(wine.data), pd.DataFrame(wine.target)], axis=1)

# 留神后面数据所放的地位，不要弄错
Xtrain, Xtest, Ytrain, Ytest = train_test_split(wine.data, wine.target, test_size=0.3)

clf = tree.DecisionTreeClassifier(criterion="entropy")
clf = clf.fit(Xtrain, Ytrain)
score = clf.score(Xtest, Ytest)   # 返回预测的准确度 accuracy

画决策树

import graphviz

feature_names = ['酒精', '苹果酸', '灰', '灰的碱性', '煤', '总酚', '类黄酮', '非黄烷类酚类', '花青素', '色彩强度'
                , '色调', 'od280/od315 浓缩葡萄酒', '脯氨酸']

dot_data = tree.export_graphviz(clf
                                , feature_names = feature_names
                                , class_names=["琴酒", "雪莉", "贝尔摩德"]
                                , filled = True
                                , rounded =True
                                    
)

graph = graphviz.Source(dot_data)
graph

数据特色的重要水平

clf.feature_importances_
[*zip(feature_names, clf.feature_importances_)]

咱们在曾经理解一个参数的状况下，建设了一个残缺的决策树，然而建设模型，score 会还是有稳定，同样的数据，不同的训练，然而后果都不一样。他为什么这么不稳固呢？工夫上是优化每一个节点，失去一个最优化的决策树，然而最优的节点肯定能保障最优的树嘛？就比方，最好的种子肯定能种出最好的苹果树嘛？集成算法就被用来解决这个问题：sklearn 示意，既然每一棵树都不能保障最优，那就建设很多个不同的树，而后从中筛选最好的。(用很多的好种子去种树，而后把失去的树中最好的后果拿进去。)怎么样从一个数据集中建不同的树？在每次分枝的时候，不应用全副的特色，而是随机选取了一部分特色，从中选取不纯度相干指标最优的最为分枝用的节点。这样，树也就不同了。

3.3.4 random_state & splitter

• random_state是用来设置分枝中的随机模式的参数，默认为 None，在高纬度时的随机性会更加的显著，低纬度数据集比方鸢尾花，而随机性简直不会呈现。输出任意一个整数，会成长出同一棵树，让模型稳定下来。
• splitter也是管制决策树中的随机项的，有两种输出值，输出“best”，决策树在分枝时，尽管随机，然而它会抉择更重要的特色进行分枝(feature_importances_的后果)，输出“random”，分枝会更加的随机，树会更深，对数据的拟合水平会升高，这也是避免过拟合的形式。

# 设置一个随机数种子
clf = tree.DecisionTreeClassifier(criterion="entropy", random_state=0)
clf = clf.fit(Xtrain, Ytrain)
score = clf.score(Xtest, Ytest)
score

# 退出 splitter 参数
clf = tree.DecisionTreeClassifier(criterion="entropy", 
                                                    random_state=0,
                                                     splitter="random")
clf = clf.fit(Xtrain, Ytrain)
score = clf.score(Xtest, Ytest)
score

import graphviz

feature_names = ['酒精', '苹果酸', '灰', '灰的碱性', '煤', '总酚', '类黄酮', '非黄烷类酚类', '花青素', '色彩强度'
                , '色调', 'od280/od315 浓缩葡萄酒', '脯氨酸']

dot_data = tree.export_graphviz(clf
                                , feature_names = feature_names
                                , class_names=["琴酒", "雪莉", "贝尔摩德"]
                                , filled = True
                                , rounded =True
                                    
)

graph = graphviz.Source(dot_data)
graph

4. 决策树的构建

4.1 ID3 算法

ID3 算法的外围是 在决策各个结点上对于信息增益准则抉择特色，递归构建决策树。

具体方法是：

1. 从根结点 (root node) 开始，对结点计算所有可能的特色的信息增益，抉择 信息增益最大 的特色作为结点的特色。
2. 由该特色的不同取值建设子节点，再对子结点递归地调用以上办法，构建决策树；直到所有特色的信息增益均 很小或没有特色能够抉择 为止。
3. 最初失去一个决策树。

ID3 相当于用极大似然法进行概率模型的抉择

算法步骤：

• 输出：训练数据集是 D，特色集是 A，阈值是 $\varepsilon$
• 输入：决策树 T
• (1)：如果 D 中所有实例属于同一类 $C_{k}$，则 T 为单结点树，并将类 $C_{k}$ 作为该节点的类标记，返回 T
• (2)：如果 A =$\emptyset$，则 T 为单节点树，并将 D 中实例树最大的类 $C_{k}$ 作为该节点的类标记，返回 T
• (3)：否则计算 A 中的各特色对 D 的信息增益，抉择信息增益最大的特色 $A_{g}$
• (4)：如果 $A_{k}$ 的信息增益小于阈值 $\varepsilon$，则置 T 为单节点树，并将 D 中实例树最大的类 $C_{k}$ 作为该节点的类标记，返回 T
• (5)：否则，对 $A_{g}$ 的每一个可能取值 $a_{i}$，依 $A_{g}=a_{i}$ 将 D 宰割为若干非空子集 $D_{i}$，将 $D_{i}$ 中实例树最大的类作为标记，构建子节点，由节点及子节点形成树 T，返回 T；
• (6)：对第 $i$ 个子节点，以 $D_{i}$ 为训练集，以 $A-A_{g}$ 为特色集，递归调用第 (1) 到第 (5) 步，失去子树 $T_{i}$，而后返回 $T_{i}$。

4.2 C4.5 的生成算法

跟 ID3 相比，将信息增益比作为抉择特色的规范。

5. 决策树的剪枝

决策树生成算法递归的产生决策树，直到不能继续下去为止，这样产生的树往往对训练数据的分类很精确，但对未知测试数据的分类缺没有那么准确，即会呈现 过拟合景象。过拟合产生的起因在于在学习时过多的思考如何进步对训练数据的正确分类，从而构建出过于简单的决策树，解决办法是思考决策树的复杂度，对曾经生成的树进行简化。

5.1 根本解释

从曾经生成的树上裁掉一些子树或叶节点，并将其根节点或父节点作为新的叶子节点，从而简略分类树模型。

5.2 实现形式

极小化决策树整体的损失函数或代价函数来实现

决策树学习的损失函数定义为：

$$
C_{\alpha}(T)=\sum_{t=1}^{|T|}N_{t}H_{t}(T)+\alpha|T|
$$

其中：

因为有：

$$
C(T)=\sum_{t=1}^{T}N_{t}H_{t}(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^{k}N_{tk}log\frac{N_{tk}}{N_{t}}
$$

所以有：

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

其中参数：

剪枝就是当 $\alpha$ 确定时，抉择损失函数最小的模型，即损失函数最小的子树。

• 当 $\alpha$ 值确定时，子树越大，往往与训练数据拟合越好，然而模型的 复杂度越高
• 子树越小，模型的复杂程度越低，往往与训练数据的拟合不好
• 损失函数正好示意了对两者的均衡

损失函数认为对于每个分类起点（叶子节点）的不确定性水平就是分类的 损失因子 ，而叶子节点的个数是模型的 复杂程度，作为惩办项，损失函数的第一项是样本的训练误差，第二项是模型的复杂度。如果一棵子树的损失函数值越大，阐明这棵子树越差，因而咱们心愿让每一棵子树的损失函数值尽可能得小，损失函数最小化就是用正则化的极大似然预计进行模型抉择的过程。

决策树的剪枝过程 (泛化过程)，就是从叶子节点开始 递归，记其父节点将所有子节点回缩后的子树为

$T_{b}$(特质值比例所占最短的那个)，未回缩的子树为 $T_{a}$，如果 $C_{\alpha}(T_{a}) \geq C_{\alpha}(T_{b})$ 阐明回缩后使损失函数减小了，那么这棵子树就应该回缩，递归直到无奈回缩为止。能够看出，决策树的生成只是思考通过进步信息增益对训练数据进行更好的拟合，而决策树剪枝通过优化损失函数还思考了减小模型复杂度。

5.3 预剪枝和后剪枝

• 预剪枝是指在决策树的生成过程中，对每个节点在划分 前先进行评估，若以后的划分不能带来泛化性能的晋升，则进行划分，并将以后节点标记为叶节点。
• 后剪枝是指先从训练集生成一颗残缺的决策树，而后自底向上对非叶节点进行考查，若将该节点对应的子树替换为叶节点，能带来泛化性能的晋升，则将该子树替换为叶节点。
• 那么怎么来判断是否带来泛化性能的晋升那？最简略的就是留出法，即预留一部分数据作为验证集来进行性能评估。

6. sklearn 中的剪枝参数调优

在不加限度的条件下，一棵决策树会成长到掂量不纯度指标最优，或者没有更多的特色可用为止，这样的决策树往往会过拟合，这就是说，它会在训练集上体现很好，在测试集上却体现不太行。咱们收集的数据不可能与整体的情况完全一致，因而当一棵决策树对训练数据有了很好的解释性，也就是说它找出的规定必然包含了训练样本中的噪声，并使它对未知的数据拟合水平有余。

就比如说咱们的树对训练集的拟合水平是 1.0，然而对测试集只有的拟合水平只有 80 左右，阐明它对训练集过拟合了，融入了噪声等。

6.1 剪枝参数

为了让决策树有更好的泛化性，咱们要对决策树进行剪枝。剪枝策略对决策树的影响微小，正确的剪枝策略是优化决策树算法的外围。

6.1.1 max_depth

限度树的最大深度，超过设点的深度的树枝全副被剪掉，在高纬度低样本量时十分有成果。决策树多成长一层，对样本量的需要会更增加一倍，以限度树深度可能无效地限度过拟合。在 集成算法 中也十分实用。在理论中，能够先从 3 开始，依据后果再决定是否减少深度。也就是说最终后果只有 max_depth 层，超过这个数值的层将会被全副删除。

clf = tree.DecisionTreeClassifier(criterion="entropy", 
                                  random_state=0,
                                  splitter="random",
                                  max_depth=3)
clf = clf.fit(Xtrain, Ytrain)
score = clf.score(Xtest, Ytest)
score

这个后果跟原来的一样，阐明，原先的决策树 3 层往后是多余的，更举荐应用这个，计算少，正确率高。

6.1.2 min_samples_leaf

min_samples_leaf 限定后，一个节点在分枝后，每个子节点必须蕴含至多 min_samples_leaf 个训练样本，否则该该分枝可能就不会产生，或者，分枝会朝着满足每个节点都蕴含样本个数达到 min_samples_leaf 个样本的方向产生。

个别是搭配 max_depth 一起用，在回归树中，能够让模型变得更加平滑。这个参数的数量设置太小可能会引起过拟合，设置得太大就会阻止模型学习数据。个别倡议从 5 开始应用。如果叶节点含有得样本数量大，倡议输出浮点数作为样本量百分比来应用，同时这个参数能够保障每个叶子得最小尺寸。防止低方差，过拟合的叶子节呈现。类别不同的问题，1 通常是最好的抉择。

clf = tree.DecisionTreeClassifier(criterion="entropy", 
                                  random_state=0,
                                  splitter="random",
                                  max_depth=3,
                                    min_samples_leaf=10)
clf = clf.fit(Xtrain, Ytrain)
score = clf.score(Xtest, Ytest)
score

在原来的叶节点中，有的样本个数都是在 10 以下，然而加了这个参数之后，这些节点的个数都在 10 以上了，跟其同级叶子节点的个数均匀了。而后得分变低了，不采纳这个参数。

6.1.3 min_samples_split

min_samples_split 限定，一个节点必要蕴含至多 min_samples_split 个训练样本，这个节点能力被容许分枝，否则分枝就不会产生。

clf = tree.DecisionTreeClassifier(criterion="entropy", 
                                  random_state=0,
                                  splitter="random",
                                  max_depth=3,
                                  max_samples_split=25)
clf = clf.fit(Xtrain, Ytrain)
score = clf.score(Xtest, Ytest)
score

在图中咱们能够发现，它的节点 (样本数小于 25 的) 曾经不再分了。得分更低，不采纳。

6.1.4 max_features

max_features 限度分枝时思考的特色个数，超过限度个数的特色都会被舍弃。

max_features 是用来限度高纬度数据的过拟合的剪枝参数，其办法更加间接。比方 900 个特色，只抉择 max_features 个。是间接限度能够应用的特色个数，而强制让决策树停下的参数。在不晓得决策树各个特色重要水平的前提下，不要应用，防止学习有余。如果心愿降维的话，还是倡议应用 PCA、ICA 或者其余降维办法。

6.1.5 min_impurity_decrease

min_impurity_decrease 限度信息增益的大小。信息增益小于设定数值的分枝不会产生。

6.2 确认最优的剪枝参数

那么咱们该如何确定每个参数应该怎么填呢？伎俩填的话，未免会效率很低。这个时候，咱们就要应用超参数的曲线来判断了，持续应用咱们曾经训练好的决策树模型 clf。超参数的学习曲线，是一条以超参数的取值为横坐标，模型的度量指标为纵坐标的曲线，它是用来掂量不通过超参数取值下模型的体现的线。咱们这个模型中，模型的度量指标就是 score。

# 如何确定最优的参数
import matplotlib.pyplot as plt
test = []
for i in range(10):
    clf = tree.DecisionTreeClassifier(criterion='entropy',
                                      random_state=0,
                                      splitter='random',
                                      max_depth=i+1  
                                                        )
    clf = clf.fit(Xtrain, Ytrain)
    score = clf.score(Xtest, Ytest)
    test.append(score)
plt.plot(range(10), test, color='red', label='max_depth')
plt.legend()
plt.show()

思考：

剪枝参数肯定可能晋升模型在测试上的体现嘛？

7. 重要属性和接口

属性是在模型训练之后，可能调用查看的模型的各种性质。对决策树来说，最重要的属性就是 feature_importances_ 可能查看各个特色对模型的重要性，

sklearn 中许多的算法的接口都是类似的，比方 fit、score，简直对每个算法都能够应用这两个接口，决策树的最罕用的接口还有 apply 和 predict。apply 中输出测试集并返回每个测试样本所对应的类别的索引，predict 输出测试集返回每个测试样本的标签。返回的内容高深莫测并且很容易。

所有的接口中要求输出的 X_train，X_test 的局部，输出的特色的特色矩阵至多是一个二维矩阵，sklearn 不接管任何一维矩阵作为特色矩阵被输出。如果只有一个特色，那必须应用 reshape 来减少矩阵的维度。

# apply 返回每个测试样本所在叶子节点的索引
clf.apply(Xtest)

# predict 返回每个测试样本的剖析 / 回归后果
clf.predict(Xtest)

回归树(DecisonTreeRegressor)

1. 实践解释

对于分类树来说，它的标签是离散型的，如果标签是连续型的呢？这个时候咱们就用到了回归树。

假如 X 和 Y 别离作为输出和输入变量，并且 Y 是连续变量，给定训练数据集 $D=\{(x_{1}, y_{1}), (x_{2}, y_{2}), \cdots , (x_{N}, y_{N}) \}$ 思考如何生成回归树

• 如何抉择划分点？
• 如何决定树中叶节点的输入值？

一个回归树对应着输出空间 (特色空间) 的一个划分以及在划分单元上的输入值。假如输出空间划分为 M 个单元 $R_{1}, R_{2}, \cdots, R_{M}$，斌且每个单元 $R_{m}$ 上有一个固定的输入值 $c_{m}$，所以回归树模型能够示意为：

$$
f(x)=\sum_{m=1}^Mc_{m}I(x\in R_{m})
$$

能够用平方误差 $\sum_{x_{i}\in R_{m}}(y_{i}-f(x_{i}))^2$ 来示意回归树对于训练树据的预测误差，用平方误差最小的准则来求解每个单元上的最优输入值。易知，$R_{m}$ 上的 $c_{m}$ 的最优值 $\hat{c}_m$ 是 $R_m$ 上所有的输出实例 $x_i$ 对应输入 $y_i$ 的均值，即：

$$
\hat{c}_m = ave(y_i|x_i \in R_m)
$$

• 问题 1：怎么对输出空间进行划分？即如何抉择划分点？

  CART 回归树采纳启发式的办法对输出空间进行划分，抉择第 j 个变量 $x^{(j)}$ 和它的取值 s，作为切分变量和切分点，斌且定义两个区域：

  $$
  R_{1}(j,s)=(x|x^{(j)} \leq s)和 R_{2}(j,s)=(x|x^{(j)} > s )
  $$

  而后咱们就能够寻找到最优切分变量 j 和最优切分点 s。具体求解

  $$
  min_{j,s}[min_{c_{1}}\sum_{x_{i}\in R_{1}(j,s)}(y_{i}-c_{1})^2+min_{c_{2}}\sum_{x_{2}\in R_{2}(j,s)}(y_{i}-c_{2})^2]
  $$

  对于固定的输出变量 j 能够找到最优切分点 s

• 问题 2：如何决定树中叶节点的输入值？

  用选定的最优切分变量 j 和最优切分点 s 划分区域并决定相应的输入值：

  $$
  \hat{c}_1 =ave(y_i | x_i \in R_1 (j,s) ) 和 \hat{c}_2=ave (y_i |x_i \in R_2 (j,s) )
  $$

  遍历所有的输出变量，找到最优的切分变量 j，形成一个对（j, s）。依此将输出空间划分为两个区域。接着，对每个区域反复上述划分过程，直到满足进行条件为止。这样就生成一颗回归树。这样的回归树通常称为最小二乘回归树（least squares regression tree）。

2. 算法流程

输出：训练数据集 D

输入：回归树 f(x)

在训练数据集所在的输出空间中，递归地将每个区域划分为两个子区域并决定每个子区域上地输入值，构建二叉决策树：

1. 抉择最优切分变量 j 和切分点 s，求解

$$
min_{j,s}[min_{c_{1}}\sum_{x_{i}\in R_{1}(j,s)}(y_{i}-c_{1})^2+min_{c_{2}}\sum_{x_{2}\in R_{2}(j,s)}(y_{i}-c_{2})^2]
$$

​ 遍历变量 j，对固定地切分变量 j 扫描切分点 s，使其后果达到最小值的对(j, s)

2. 选定的对 (j, s) 划分区域并决定相应的输入值：

   $$
   R_1(j,s)=\{x|x_(j) \leq s \}, R_2(j, s)=(x| x_j > s)
   $$

其中对于上式有：

$\hat{c}_m= \frac{1}{N_m} \sum_{x_i \in R_m(j,s) } y_i, x_i\in R_m,m=1,2$

3. 持续对两个子区域调用步骤 1 和步骤 2，晓得满足进行条件

4. 将输出空间划分为 M 个区域 $R_{1}, R_{2}, \cdots, R_{M}$，生成决策树：

   $$
   f(x)=\sum_{m=1}^M\hat{c}_mI(x\in R_m)
   $$

3. 回归树实例

试用平方误差损失准则生成一个二叉回归树

抉择最优切分变量 j 和切分点 s：

$$
min_{j,s}[min_{c_{1}}\sum_{x_{i}\in R_{1}(j,s)}(y_{i}-c_{1})^2+min_{c_{2}}\sum_{x_{2}\in R_{2}(j,s)}(y_{i}-c_{2})^2]
$$

其中：

$c_{1}=ave(y_{i} | x_{i} \in R_{1}(j,s)) 和 c_{2}=ave(y_{i} | x_{i} \in R_{2}(j,s))$

例如，取 s =1。此时有 $R_{1}={1}, R_{2}=\{2, 3, 4, 5, 6, 7, 8, 9, 10 \}$，这两个区域的输入值别离为：

$c_{1}=4.50$

$c_{2}=\frac{1}{9}(4.75+4.91+5.34+5.80+7.05+7.90+8.23+8.70+9.00)=6.85$

根据上述计算失去下表：

把 $c_{1}, c_{2}$ 的值带入到均方差中：

$m(1)=(4.50-4.50)^2+(4.75-6.85)^2+(4.91-6.85)^2+(5.34-6.85)^2+(5.80-6.85)^2+(7.05-6.85)^2+(8.23-6.85)^2+(8.70-6.85)^2+(9.00-6.85)^2$

其中跟 $c_{1}$ 无关的只有第一项，跟 $c_{2}$ 无关的则是有 9 项。

同理，咱们能够得悉：

显然取 s = 5 时，m(s)有最小，所以第一个最优切分变量为：j=x、最优切分点为：s=5。

用选定的 (j, s) 划分区域，并决定输入值：

两个划分区域别离是：$R_{1}=\{1,2,3,4,5 \}, R_{2}=\{6,7,8,9,10 \}$。输入值用公式：

$\hat{c}_1=ave(y_i|x_i in R_1(j,s) 和 \hat{c}_2=ave(y_i|x_i \in R_2(j,s) $

失去 $c_{1}=5.06, c_{2}=8.18$

而后对两个子区域持续调用算法流程中的步骤(1)、（2)

对 $R_{1}$ 持续划分：

取切分点别离为：[1, 2, 3, 4, 5]，则各个区域的输入值 c 如下：

计算 m(s):

s= 3 时，m(3)最小。

而后进行递归，能够失去残缺的二叉回归树。

4.sklearn 中的回归树

4.1 重要参数，属性和接口

• criterion

回归树掂量分枝品质的指标，反对的规范有三种：

1. 输出“mse“应用均方差(MSE)，父节点和叶子节点间接的均方误差的差额将作为特征选择的规范，这种办法通过应用叶子节点的均值来最小化 $L_{2}$ 损失。
2. 输出”friedman_mse“应用费尔德曼均方误差，这样的指标应用针对潜在分枝种的问题改良办法。
3. 输出”mae“应用相对平均误差 MAE，这种指标应用叶节点的中值来最小化 $L{1}$ 损失。

在回归树种，MSE 不只是咱们的分枝品质衡量标准，也是咱们罕用的掂量回归树回归品质的指标。

当咱们在穿插验证的时候，或者其余形式获取回归树的后果时候，咱们往往会抉择均方误差作为咱们的评估(score 是准确率)。在回归中，咱们谋求的是 MSE 越小越好。而后回归树的接口 score 返回的是 $R^2$ 而不是MSE。

$$
R^2=1-\frac{u}{v}
$$

$u=\sum_{i=1}^{N}(f_{i}-y_{i})^2,v=\sum_{i=1}^{N}(y_{i}-\bar{y_{i}})^2$

其中 u 是残差平方和，v 是总平方和。

4.2 穿插验证

对于模型的训练，咱们最简略的想法就行把整个数据集分成两个局部，一部分用于训练，另一部分用于验证，也就是常说的训练集和测试集。

这样会有一个弊病，也就是模型与参数的选取将极大水平依赖于对训练集和测试集的划分。不同划分下，TEST 的 MSE 的变动是很大的，而且对应的最优 degree 也是不一样的。如果咱们对于训练集和测试集的划分办法不够好，很可能不能失去最好的模型和参数。

4.2.1 LOOCV

LOOCV 也蕴含将数据集分成训练集和测试集这一步骤。然而不同的是，咱们只用一个数据作为测试集，其余残余的数据都作为训练集，并且将此步骤反复 N 次。(N 是数据集的数据量)

就比方于 n 个数据 {1, 2, 3, …, n}，LOOCV 的办法就是每次取一个数据作为测试集的惟一元素，而其余的 n - 1 个数据作为训练集用于训练模型和调参。比方第一次用 1 来作为测试集，则剩下的数据{2, 3, 4, …, n} 就能够作为它的训练集，顺次类推，直到用 n 来作为测试集，剩下的数据作为训练集为止。后果就是咱们最终训练了 n 个模型，每次都能失去一个 MSE。最终 test MSE 则就是将这 n 个 MSE 取均匀。

$$
CV_{n} = \frac{1}{n}\sum_{i=1}^{n}MSE_{i}
$$

• 长处：首先它不受测试汇合训练集划分办法的影响，因为每一个数据都独自的做过测试集。同时，其用了 n - 1 个数据训练模型，也简直用到了所有的数据，保障了模型的 bias 更小。
• 毛病：那就是计算量过于大，是 test set approach 耗时的 n - 1 倍。

为了解决计算成本太大的弊病，对算法进行更进，使得 LOOCV 计算成本和只训练一个模型一样快。

$$
CV_{n}=\frac{1}{n}\sum_{i=1}^{n}(\frac{y_{i}-\hat{y_{i}}}{1-h_{i}})^{2}
$$

4.2.2 k-fold Cross Validation

k 折穿插验证和 LOOCV 的不同在于，咱们每次的测试集不再只蕴含一个数据，而是多个，具体数目将依据 K 的选取来决定。比方，k=5，那么咱们利用五折穿插验证的步骤就是：

1. 将所有数据集分成 5 份
2. 不反复地每次取其中一份作为测试集，用其余四份作训练集训练模型，之后计算该模型在测试集上的 $MSE_{i}$

3. 将 5 次的 $MSE_{i}$ 取均匀失去最初的 MSE

   $$
   CV_{k} = \frac{1}{k}\sum_{i=1}^{k}MSE_{i}
   $$

不难理解，其实 LOOCV 是一种非凡的 k -fold Cross Validation (K=N)。

4.2.3 Bias-Variance Trade-Off for k-Fold Cross-Validation

最初，咱们要说说 K 的选取。事实上，和结尾给出的文章里的局部内容一样，K 的选取是一个 Bias 和 Variance 的 trade-off。

K 越大，每次投入的训练集的数据越多，模型的 Bias 越小。然而 K 越大，又意味着每一次选取的训练集之前的相关性越大（思考最极其的例子，当 k =N，也就是在 LOOCV 里，每次都训练数据简直是一样的）。而这种大相关性会导致最终的 test error 具备更大的 Variance。

一般来说，依据教训咱们个别抉择 k = 5 或 10。

4.2.4 sklearn 种穿插验证的实现

from sklearn.datasets import load_boston
from sklearn.model_selection import cross_val_score
from sklearn.tree import DecisionTreeRegressor

boston = load_boston()
regressor = DecisionTreeRegressor(random_state=0)
cross_val_score(regressor, boston.data, boston.target, cv=5,
                scoring='neg_mean_squared_error')

在 cross_val_score 这个函数中，regressor 是任一构建好的模型实例，可是是 SVM 等等，后两个参数间接输人原始数据，不须要有任何改变或者划分。cv 参数就是将数据集划分的个数。因为在回归树中，咱们个别是看其 MSE，所以加上 scoring 参数，要不然返回的就是得分。