任务三决策树算法梳理

2.决策树的不同分类算法（ID3算法、C4.5、CART分类树）的原理及应用场景

4. 决策树防止过拟合手段

5. 模型评估

6. sklearn参数详解，Python绘制决策树

6.1sklearn参数详解

6.2Python绘制决策树

1. 信息论基础（熵联合熵条件熵信息增益基尼不纯度）

熵：

熵的概念最早起源于物理学，用于度量一个热力学系统的无序程度，在信息论里面，熵是对不确定性的测量。

$H(X) =- \sum_i p(x_i) \log p(x_i)$

联合熵：

联合熵就是度量一个联合分布的随机系统的不确定度。

分布为
$p(x,y)$
的一对随机变量（X,Y），其联合熵定义为：

$H(X,Y) = - \sum_{x \in X } \sum_{y \in Y} p(x,y) \log p(x,y)$

条件熵：

定义事件

X

与

Y

分别取

xi

和

yj

时的条件熵为

$H(X|Y)=-\sum_{x \in X } \sum_{y \in Y} p(x,y) \log{\frac{p(x,y)}{p(y)}} = \sum_{x \in X } \sum_{y \in Y} p(x,y) \log p(x|y)$

其中

p

(

xi

,

yj

)为

X

=

xi

且

Y

=

yj

时的概率。该条件熵应当理解为你知道

Y

的值前提下随机变量

X

的随机性的量。

信息增益：

特征A对训练数据集D的信息增益个
$g(D,A)$
定义为集合D的经验熵
$H(D)$
与特征A给定条件下D的经验条件熵
$H(D|A)$
之差，即：

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

一般熵H(Y)与条件熵H(Y|X)之差称为互信息。决策树学习中的信息增益等价于类与特征的互信息。

基尼不纯度：

从一个数据集中随机选取子项，度量其被错误的划分到其他组里的概率。

简单理解：一个随机事件变成它的对立事件的概率。

计算公式：
$I_G(p) = \sum _{i=1}^m p(1-p)$

2.决策树的不同分类算法（ID3算法、C4.5、CART分类树）的原理及应用场景

ID3算法：

以信息增益为准则来选择划分属性。在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。

具体方法：从根结点（root node）开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止，最后得到一个决策树。

C4.5

是 ID3 的后继者，并且通过动态定义将连续属性值分割成一组离散间隔的离散属性（基于数字变量），消除了特征必须被明确分类的限制。C4.5 将训练的树（即，ID3算法的输出）转换成 if-then 规则的集合。然后评估每个规则的这些准确性，以确定应用它们的顺序。如果规则的准确性没有改变，则需要决策树的树枝来解决。

C5.0 是 Quinlan 根据专有许可证发布的最新版本。它使用更少的内存，并建立比 C4.5 更小的规则集，同时更准确。

CART分类树

Classification and Regression Trees （分类和回归树）与 C4.5 非常相似，但它不同之处在于它支持数值目标变量（回归），并且不计算规则集。CART 使用在每个节点产生最大信息增益的特征和阈值来构造二叉树。

scikit-learn 使用 CART 算法的优化版本。

3. 回归树原理

4. 决策树防止过拟合手段

合理、有效地抽样，用相对能够反映业务逻辑的训练集去产生决策树；
剪枝：提前停止树的增长或者对已经生成的树按照一定的规则进行后剪枝。

剪枝的方法

剪枝是一个简化过拟合决策树的过程。有两种常用的剪枝方法：

(1)先剪枝（prepruning）：

通过提前停止树的构建而对树“剪枝”，一旦停止，节点就成为树叶。该树叶可以持有子集元组中最频繁的类；

先剪枝的方法

有多种不同的方式可以让决策树停止生长，下面介绍几种停止决策树生长的方法：

限制决策树的高度和叶子结点处样本的数目

1）定义一个高度，当决策树达到该高度时就可以停止决策树的生长，这是一种最为简单的方法；

2）达到某个结点的实例具有相同的特征向量，即使这些实例不属于同一类，也可以停止决策树的生长。这种方法对于处理数据中的数据冲突问题非常有效；

3）定义一个阈值，当达到某个结点的实例个数小于该阈值时就可以停止决策树的生长；

4）定义一个阈值，通过计算每次扩张对系统性能的增益，并比较增益值与该阈值的大小来决定是否停止决策树的生长。

(2)后剪枝（postpruning）：

它首先构造完整的决策树，允许树过度拟合训练数据，然后对那些置信度不够的结点子树用叶子结点来代替，该叶子的类标号用该结点子树中最频繁的类标记。后剪枝的剪枝过程是删除一些子树，然后用其叶子节点代替，这个叶子节点所标识的类别通过大多数原则(majority class criterion)确定。所谓大多数原则，是指剪枝过程中, 将一些子树删除而用叶节点代替,这个叶节点所标识的类别用这棵子树中大多数训练样本所属的类别来标识,所标识的类称为majority class .相比于先剪枝，这种方法更常用，正是因为在先剪枝方法中精确地估计何时停止树增长很困难。

后剪枝的方法

1)REP方法是一种比较简单的后剪枝的方法，在该方法中，可用的数据被分成两个样例集合：一个训练集用来形成学习到的决策树，一个分离的验证集用来评估这个决策树在后续数据上的精度，确切地说是用来评估修剪这个决策树的影响。这个方法的动机是：即使学习器可能会被训练集中的随机错误和巧合规律所误导，但验证集合不大可能表现出同样的随机波动。所以验证集可以用来对过度拟合训练集中的虚假特征提供防护检验。

该剪枝方法考虑将书上的每个节点作为修剪的候选对象，决定是否修剪这个结点有如下步骤组成：

1：删除以此结点为根的子树

2：使其成为叶子结点

3：赋予该结点关联的训练数据的最常见分类

4：当修剪后的树对于验证集合的性能不会比原来的树差时，才真正删除该结点

因为训练集合的过拟合，使得验证集合数据能够对其进行修正，反复进行上面的操作，从底向上的处理结点，删除那些能够最大限度的提高验证集合的精度的结点，直到进一步修剪有害为止(有害是指修剪会减低验证集合的精度)。

REP是最简单的后剪枝方法之一，不过由于使用独立的测试集，原始决策树相比，修改后的决策树可能偏向于过度修剪。这是因为一些不会再测试集中出现的很稀少的训练集实例所对应的分枝在剪枝过如果训练集较小，通常不考虑采用REP算法。

尽管REP有这个缺点，不过REP仍然作为一种基准来评价其它剪枝算法的性能。它对于两阶段决策树学习方法的优点和缺点提供了了一个很好的学习思路。由于验证集合没有参与决策树的创建，所以用REP剪枝后的决策树对于测试样例的偏差要好很多，能够解决一定程度的过拟合问题。

2)PEP,悲观错误剪枝,悲观错误剪枝法是根据剪枝前后的错误率来判定子树的修剪。该方法引入了统计学上连续修正的概念弥补REP中的缺陷，在评价子树的训练错误公式中添加了一个常数，假定每个叶子结点都自动对实例的某个部分进行错误的分类。它不需要像REP(错误率降低修剪)样，需要用部分样本作为测试数据，而是完全使用训练数据来生成决策树，又用这些训练数据来完成剪枝。决策树生成和剪枝都使用训练集, 所以会产生错分。

5. 模型评估

通过

评估指标

和

评估方法

来评估决策树模型。

评估指标

有分类准确度、召回率、虚警率和精确度等。而这些指标都是基于混淆矩阵 (confusion matrix) 进行计算的。

混淆矩阵是用来评价监督式学习模型的精确性，矩阵的每一列代表一个类的实例预测，而每一行表示一个实际的类的实例。以二类分类问题为例，如下表所示：

	预测的类
实际的类		类 = 1	类 = 0
	类 = 1	TP	FN	P
	类 = 0	FP	TN	N

其中

P (Positive Sample)：正例的样本数量。

N(Negative Sample)：负例的样本数量。

TP(True Positive)：正确预测到的正例的数量。

FP(False Positive)：把负例预测成正例的数量。

FN(False Negative)：把正例预测成负例的数量。

TN(True Negative)：正确预测到的负例的数量。

根据混淆矩阵可以得到评价分类模型的指标有以下几种。

分类准确度，就是正负样本分别被正确分类的概率，计算公式为：

$Accuracy = \frac{TP+TN}{P+N}$

召回率，就是正样本被识别出的概率，计算公式为：

$Recall = \frac{TP}{P}$

虚警率，就是负样本被错误分为正样本的概率，计算公式为：

$FPrate=\frac{FP}{N}$

精确度，就是分类结果为正样本的情况真实性程度，计算公式为：

$Precision=\frac{TP}{TP+FP}$

评估方法

有保留法、随机二次抽样、交叉验证和自助法等。

保留法 (holdout) 是评估分类模型性能的最基本的一种方法。将被标记的原始数据集分成训练集和检验集两份，训练集用于训练分类模型，检验集用于评估分类模型性能。但此方法不适用样本较小的情况，模型可能高度依赖训练集和检验集的构成。

随机二次抽样 (random subsampling) 是指多次重复使用保留方法来改进分类器评估方法。同样此方法也不适用训练集数量不足的情况，而且也可能造成有些数据未被用于训练集。

交叉验证 (cross-validation) 是指把数据分成数量相同的 k 份，每次使用数据进行分类时，选择其中一份作为检验集，剩下的 k-1 份为训练集，重复 k 次，正好使得每一份数据都被用于一次检验集 k-1 次训练集。该方法的优点是尽可能多的数据作为训练集数据，每一次训练集数据和检验集数据都是相互独立的，并且完全覆盖了整个数据集。也存在一个缺点，就是分类模型运行了 K 次，计算开销较大。

自助法 (bootstrap) 是指在其方法中，训练集数据采用的是有放回的抽样，即已经选取为训练集的数据又被放回原来的数据集中，使得该数据有机会能被再一次抽取。用于样本数不多的情况下，效果很好。

6. sklearn参数详解，Python绘制决策树

6.1sklearn参数详解

sklearn.tree.DecisionTreeClassifier(criterion='gini',
                                    splitter='best', 
                                    max_depth=None,
                                    min_samples_split=2,
                                    min_samples_leaf=1,
                                    min_weight_fraction_leaf=0.0, 
                                    max_features=None,random_state=None, 
                                    max_leaf_nodes=None, 
                                    min_impurity_decrease=0.0,
                                    min_impurity_split=None, 
                                    class_weight=None, 
                                    presort=False)

criterion
:特征选择的标准，有信息增益和基尼系数两种，使用信息增益的是ID3和C4.5算法（使用信息增益比），使用基尼系数的CART算法，默认是gini系数。
splitter
:特征切分点选择标准，决策树是递归地选择最优切分点，spliter是用来指明在哪个集合上来递归，有“best”和“random”两种参数可以选择，best表示在所有特征上递归，适用于数据集较小的时候，random表示随机选择一部分特征进行递归，适用于数据集较大的时候。
max_depth
:决策树最大深度，决策树模型先对所有数据集进行切分，再在子数据集上继续循环这个切分过程，max_depth可以理解成用来限制这个循环次数。
min_samples_split
:子数据集再切分需要的最小样本量，默认是2，如果子数据样本量小于2时，则不再进行下一步切分。如果数据量较小，使用默认值就可，如果数据量较大，为降低计算量，应该把这个值增大，即限制子数据集的切分次数。
min_samples_leaf
:叶节点（子数据集）最小样本数，如果子数据集中的样本数小于这个值，那么该叶节点和其兄弟节点都会被剪枝（去掉），该值默认为1。
min_weight_fraction_leaf
:在叶节点处的所有输入样本权重总和的最小加权分数，如果不输入则表示所有的叶节点的权重是一致的。
max_features
:特征切分时考虑的最大特征数量，默认是对所有特征进行切分，也可以传入int类型的值，表示具体的特征个数；也可以是浮点数，则表示特征个数的百分比；还可以是sqrt,表示总特征数的平方根；也可以是log2，表示总特征数的log个特征。
random_state
:随机种子的设置，与LR中参数一致。
max_leaf_nodes
:最大叶节点个数，即数据集切分成子数据集的最大个数。
min_impurity_decrease
:切分点不纯度最小减少程度，如果某个结点的不纯度减少小于这个值，那么该切分点就会被移除。
min_impurity_split
:切分点最小不纯度，用来限制数据集的继续切分（决策树的生成），如果某个节点的不纯度（可以理解为分类错误率）小于这个阈值，那么该点的数据将不再进行切分。
class_weight
:权重设置，主要是用于处理不平衡样本，与LR模型中的参数一致，可以自定义类别权重，也可以直接使用balanced参数值进行不平衡样本处理。
presort
:是否进行预排序，默认是False，所谓预排序就是提前对特征进行排序，我们知道，决策树分割数据集的依据是，优先按照信息增益/基尼系数大的特征来进行分割的，涉及的大小就需要比较，如果不进行预排序，则会在每次分割的时候需要重新把所有特征进行计算比较一次，如果进行了预排序以后，则每次分割的时候，只需要拿排名靠前的特征就可以了。

6.2Python绘制决策树

使用鸢尾花的数据集进行绘制决策树，代码如下：

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import load_iris
from sklearn import tree

%matplotlib inline
%config InlineBackend.figure_format = 'svg'


# Parameters
n_classes = 3
plot_colors = "ryb"
plot_step = 0.02


# Load data
iris = load_iris()
for pairidx, pair in enumerate([[0, 1], [0, 2], [0, 3],
                                [1, 2], [1, 3], [2, 3]]):
    # We only take the two corresponding features
    X = iris.data[:, pair]
    y = iris.target

    # Train
    clf = tree.DecisionTreeClassifier().fit(X, y)

    # Plot the decision boundary
    plt.subplot(2, 3, pairidx + 1)

    x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
    y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
    xx, yy = np.meshgrid(np.arange(x_min, x_max, plot_step),
                         np.arange(y_min, y_max, plot_step))
    plt.tight_layout(h_pad=0.5, w_pad=0.5, pad=2.5)

    Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)
    cs = plt.contourf(xx, yy, Z, cmap=plt.cm.RdYlBu)

    plt.xlabel(iris.feature_names[pair[0]])
    plt.ylabel(iris.feature_names[pair[1]])

    # Plot the training points 
    for i, color in zip(range(n_classes), plot_colors):
        idx = np.where(y == i)
        plt.scatter(X[idx, 0], X[idx, 1], c=color, label=iris.target_names[i],
                    cmap=plt.cm.RdYlBu, edgecolor='black', s=15)

plt.suptitle("Decision surface of a decision tree using paired features")
plt.legend(loc='lower right', borderpad=0, handletextpad=0)
plt.axis("tight")

plt.savefig('tmp.pdf', bbox_inches='tight')
plt.show()


import graphviz 
dot_data = tree.export_graphviz(clf, out_file=None) 
graph = graphviz.Source(dot_data) 


#:func:`export_graphviz` 出导出还支持各种美化，包括通过他们的类着色节点（或回归值），如果需要，使用显式变量和类名。Jupyter notebook也可以自动找出相同的模块::
dot_data = tree.export_graphviz(clf, out_file=None, # doctest: +SKIP
                            feature_names=iris.feature_names,  # doctest: +SKIP
                            class_names=iris.target_names,  # doctest: +SKIP
                            filled=True, rounded=True,  # doctest: +SKIP
                            special_characters=True)

graph.render("iris") 
graph = graphviz.Source(dot_data)
graph

结果如下：

决策树的分类区域：

原文链接：https://blog.csdn.net/u013327188/article/details/88096151

1. 信息论基础（熵 联合熵 条件熵 信息增益 基尼不纯度）

2.决策树的不同分类算法（ID3算法、C4.5、CART分类树）的原理及应用场景

3. 回归树原理

4. 决策树防止过拟合手段

5. 模型评估

6. sklearn参数详解，Python绘制决策树

6.1sklearn参数详解

6.2Python绘制决策树

你可能也喜欢

1. 信息论基础（熵联合熵条件熵信息增益基尼不纯度）