决策树算法年份要管吗

❶ 决策树算法

决策树算法的算法理论和应用场景

算法理论：

我了解的决策树算法，主要有三种，最早期的ID3，再到后来的C4.5和CART这三种算法。

这三种算法的大致框架近似。

决策树的学习过程

1.特征选择

在训练数据中 众多X中选择一个特征作为当前节点分裂的标准。如何选择特征有着很多不同量化评估标准，从而衍生出不同的决策树算法。

2.决策树生成

根据选择的特征评估标准，从上至下递归生成子节点，直到数据集不可分或者最小节点满足阈值，此时决策树停止生长。

3.剪枝

决策树极其容易过拟合，一般需要通过剪枝，缩小树结构规模、缓解过拟合。剪枝技术有前剪枝和后剪枝两种。

有些算法用剪枝过程，有些没有，如ID3。

预剪枝：对每个结点划分前先进行估计，若当前结点的划分不能带来决策树的泛化性能的提升，则停止划分，并标记为叶结点。

后剪枝：现从训练集生成一棵完整的决策树，然后自底向上对非叶子结点进行考察，若该结点对应的子树用叶结点能带来决策树泛化性能的提升，则将该子树替换为叶结点。

但不管是预剪枝还是后剪枝都是用验证集的数据进行评估。

ID3算法是最早成型的决策树算法。ID3的算法核心是在决策树各个节点上应用信息增益准则来选择特征，递归构建决策树。缺点是，在选择分裂变量时容易选择分类多的特征，如ID值【值越多、分叉越多，子节点的不纯度就越小，信息增益就越大】。

ID3之所以无法 处理缺失值、无法处理连续值、不剪纸等情况，主要是当时的重点并不是这些。

C4.5算法与ID3近似，只是分裂标准从 信息增益 转变成  信息增益率。可以处理连续值，含剪枝，可以处理缺失值，这里的做法多是 概率权重。

CART：1.可以处理连续值 2.可以进行缺失值处理 3.支持剪枝 4.可以分类可以回归。

缺失值的处理是 作为一个单独的类别进行分类。

建立CART树

我们的算法从根节点开始，用训练集递归的建立CART树。

1) 对于当前节点的数据集为D，如果样本个数小于阈值或者没有特征，则返回决策子树，当前节点停止递归。

2) 计算样本集D的基尼系数， 如果基尼系数小于阈值 （说明已经很纯了！！不需要再分了！！），则返回决策树子树，当前节点停止递归。

3) 计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数。

4) 在计算出来的各个特征的各个特征值对数据集D的基尼系数中，选择 基尼系数最小的特征A和对应的特征值a。根据这个最优特征和最优特征值，把数据集划分成两部分D1和D2，同时建立当前节点的左右节点，做节点的数据集D为D1，右节点的数据集D为D2。 (注：注意是二叉树，故这里的D1和D2是有集合关系的，D2=D-D1)

5) 对左右的子节点递归的调用1-4步，生成决策树。

CART采用的办法是后剪枝法，即先生成决策树，然后产生所有可能的剪枝后的CART树，然后使用交叉验证来检验各种剪枝的效果，选择泛化能力最好的剪枝策略。

应用场景

比如欺诈问题中，通过决策树算法简单分类，默认是CART的分类树，默认不剪枝。然后在出图后，自行选择合适的叶节点进行拒绝操作。

这个不剪枝是因为欺诈问题的特殊性，欺诈问题一般而言较少，如数据的万几水平，即正样本少，而整个欺诈问题需要解决的速度较快。此时只能根据业务要求，迅速针对已有的正样本情况，在控制准确率的前提下，尽可能提高召回率。这种情况下，可以使用决策树来简单应用，这个可以替代原本手工选择特征及特征阈值的情况。

❷ 决策树法(一)

姓名：王映中 学号：20181214025 学院：广研院

转自 https://blog.csdn.net/weixin_42327752/article/details/117806076

【嵌牛导读】决策树（decision tree）是一种基本的分类与回归方法。决策树学习通常包括3个步骤：特征选择、决策树的生成和决策树的修剪。些决策树学习的思想主要来源于由Quinlan在1986年提出的ID3算法和1993年提出的C4.5算法，以及由Breiman等人在1984年提出的CART算法。

【嵌牛鼻子】决策树模型与学习

【嵌牛提问】如何建立决策树模型?

【嵌牛正文】

1 决策树模型与学习

决策树解决分类问题的一般方法

1.1 决策树模型

定义：分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点（node）和有向边（directed edge）组成。结点有两种类型：内部结点（internal node）和叶结点（leaf node）。内部结点表示一个特征或属性，叶结点表示一个类。

1.2 决策树与if-then规则

可以将决策树看成一个if-then规则的集合。将决策树转换成if-then规则的过程是这样的：由决策树的根结点到叶结点的每一条路径构建一条规则；路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。

    决策树的路径或其对应的if-then规则集合具有一个重要的性质：互斥并且完备。这就是说，每一个实例都被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖。这里所谓覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。

1.3 决策树与条件概率分布

1.4 决策树学习

决策树学习本质上是从训练数据集中归纳出一组分类规则，与训练数据集不相矛盾的决策树（即能对训练数据进行正确分类的决策树）可能有多个，也可能一个也没有。从另一个角度看，决策树学习是由训练数据集估计条件概率模型。基于特征空间划分的类的条件概率模型有无穷多个。我们选择的条件概率模型应该不仅对训练数据有很好的拟合，而且对未知数据有很好的预测。

    决策树的损失函数是正则化的极大似然函数。当损失函数确定以后，学习问题就变为在损失函数意义下选择最优决策树的问题。因为从所有可能的决策树中选取最优决策树是NP完全问题，所以现实中决策树学习算法通常采用启发式方法，近似求解这一最优化问题。这样得到的决策树是次最优（sub-optimal）的。

    决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。开始，构建根结点，将所有训练数据都放在根结点。选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。如果这些子集已经能够被基本正确分类，那么构建叶结点，并将这些子集分到所对应的叶结点中去；如果还有子集不能被基本正确分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的结点。如此递归地进行下去，直至所有训练数据子集被基本正确分类，或者没有合适的特征为止。最后每个子集都被分到叶结点上，即都有了明确的类。这就生成了一棵决策树。

    以上方法生成的决策树可能对训练数据有很好的分类能力，但对未知的测试数据却未必有很好的分类能力，即可能发生过拟合现象。我们需要对已生成的树自下而上进行剪枝，将树变得更简单，从而使它具有更好的泛化能力。具体地，就是去掉过于细分的叶结点，使其回退到父结点，甚至更高的结点，然后将父结点或更高的结点改为新的叶结点。

决策树学习算法包含特征选择、决策树的生成与决策树的剪枝过程。决策树学习算法包含特征选择、决策树的生成与决策树的剪枝过程。

    决策树学习常用的算法有ID3、C4.5与CART，下面结合这些算法分别叙述决策树学习的特征选择、决策树的生成和剪枝过程。

❸ 决策树基本概念及算法优缺点

分类决策树模型是一种描述对实例进行分类的树形结构. 决策树由结点和有向边组成. 结点有两种类型: 内部结点和叶节点. 内部节点表示一个特征或属性, 叶节点表示一个类.
决策树(Decision Tree),又称为判定树, 是一种以树结构(包括二叉树和多叉树)形式表达的预测分析模型.

分类树--对离散变量做决策树

回归树--对连续变量做决策树

优点:
(1)速度快: 计算量相对较小, 且容易转化成分类规则. 只要沿着树根向下一直走到叶, 沿途的分裂条件就能够唯一确定一条分类的谓词.
(2)准确性高: 挖掘出来的分类规则准确性高, 便于理解, 决策树可以清晰的显示哪些字段比较重要, 即可以生成可以理解的规则.
(3)可以处理连续和种类字段
(4)不需要任何领域知识和参数假设
(5)适合高维数据
缺点:
(1)对于各类别样本数量不一致的数据, 信息增益偏向于那些更多数值的特征
(2)容易过拟合
(3)忽略属性之间的相关性

若一事假有k种结果, 对应概率为 , 则此事件发生后所得到的信息量I为:

给定包含关于某个目标概念的正反样例的样例集S, 那么S相对这个布尔型分类的熵为:

其中 代表正样例, 代表反样例

假设随机变量(X,Y), 其联合分布概率为P(X=xi,Y=yi)=Pij, i=1,2,...,n;j=1,2,..,m
则条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性, 其定义为X在给定条件下Y的条件概率分布的熵对X的数学期望

在Hunt算法中, 通过递归的方式建立决策树.

使用信息增益, 选择 最高信息增益 的属性作为当前节点的测试属性

ID3( Examples,Target_attribute,Attributes )

Examples 即训练样例集. Target_attribute 是这棵树要预测的目标属性. Attributes 是除目标属性外供学习到的决策树测试的属性列表. 返回能正确分类给定 Examples 的决策树.

class 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)

限制决策树层数为4的DecisionTreeClassifier实例

This plot compares the decision surfaces learned by a dcision tree classifier(first column), by a random forest classifier(second column), by an extra-trees classifier(third column) and by an AdaBoost classifier(fouth column).

Output:

A comparison of a several classifiers in scikit-learn on synthetic datasets.
The point of this examples is to illustrate the nature of decision boundaries of different classifiers.

Particularly in high-dimensional spaces, data can more easily be separated linearly and the simplicity of classifiers such as naive Bayes and linear SVMs might lead to better generalization than is achieved by other classifiers.

This example fits an AdaBoost decisin stump on a non-linearly separable classification dataset composed of two "Gaussian quantiles" clusters and plots the decision boundary and decision scores.

Output:

❹ 决策树算法总结

目录

一、决策树算法思想

二、决策树学习本质

三、总结

一、决策树（decision tree）算法思想：

决策树是一种基本的分类与回归方法。本文主要讨论分类决策树。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。 它可以看做是if-then的条件集合，也可以认为是定义在特征空间与类空间上的条件概率分布 。决策树由结点和有向边组成。结点有两种类型：内部结点和叶结点，内部结点表示一个特征或属性，叶结点表示一个类。（椭圆表示内部结点，方块表示叶结点）

         决策树与if-then规则的关系

决策树可以看做是多个if-then规则的集合。将决策树转换成if-then规则的过程是：由决策树的根结点到叶结点的每一条路径构建一条规则；路径上的内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。决策树的路径或其对应的if-then规则集合具有一个重要的性质：互斥且完备。这就是说，每一个实例都被一条路径或一条规则所覆盖，且只被一条路径或一条规则所覆盖。这里的覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。

         决策树与条件概率分布的关系

决策树还表示给定特征条件下类的条件概率分布。这一条件概率分布定义在特征空间的一个划分上。将特征空间划分为互不相交的单元或区域，并在每个单元定义一个类的概率分布，就构成一个条件概率分布。决策树的一条路径对应于划分中的一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。

         决策树模型的优点

决策树模型具有可读性，分类速度快。学习时，利用训练数据，根据损失函数最小化原则建立决策树模型；预测时，对新的数据，利用决策树模型进行分类 。

二、决策树学习本质：

决策树学习是从训练数据集中归纳一组分类规则、与训练数据集不相矛盾的决策树可能有多个，也可能一个没有。我们需要训练一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。从另一个角度看 决策树学习是训练数据集估计条件概率模型 。基于特征空间划分的类的条件概率模型有无穷多个。我们选择的条件概率模型应该是不仅对训练数据有很好的拟合，而且对未知数据有很好的预测。 决策树的学习使用损失函数表示这一目标，通常的损失函数是正则化的极大似然函数。决策树的学习策略是以损失函数为目标函数的最小化。当损失函数确定后，决策树学习问题变为损失函数意义下选择最优决策树的问题。这一过程通常是一个递归选择最优特征，并根据特征对训练数据进行分割，使得对各个子数据集有一个最好分类的过程。这一过程对应着特征选择、决策树的生成、决策树的剪枝。

         特征选择 ： 在于选择对训练数据具有分类能力的特征，这样可以提高决策树的学习效率。

         决策树的生成 ： 根据不同特征作为根结点，划分不同子结点构成不同的决策树。

         决策树的选择 ：哪种特征作为根结点的决策树信息增益值最大，作为最终的决策树（最佳分类特征）。

         信息熵 ： 在信息论与概率统计中，熵是表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量，其概率分布为P(X= ) = ，i=1，2，3...n，则随机变量X的熵定义为

        H(X) =  —  ，0 <=  H(X) <= 1，熵越大，随机变量的不确定性就越大。

        条件熵（Y|X） ： 表示在已知随机变量X的条件下随机变量Y的不确定性。

         信息增益  ： 表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。

        信息增益  = 信息熵(父结点熵 ) — 条件熵（子结点加权熵）

三、 总结 ：

        优点

        1、可解释性高，能处理非线性的数据，不需要做数据归一化，对数据分布没有偏好。

        2、可用于特征工程，特征选择。

        3、可转化为规则引擎。

        缺点

        1、启发式生成，不是最优解。

        2、容易过拟合。

        3、微小的数据改变会改变整个数的形状。

        4、对类别不平衡的数据不友好。

❺ 决策树算法-原理篇

关于决策树算法，我打算分两篇来讲，一篇讲思想原理，另一篇直接撸码来分析算法。本篇为原理篇。
通过阅读这篇文章，你可以学到：
1、决策树的本质
2、决策树的构造过程
3、决策树的优化方向

决策树根据使用目的分为：分类树和回归树，其本质上是一样的。本文只讲分类树。

决策树，根据名字来解释就是，使用树型结构来模拟决策。
用图形表示就是下面这样。

其中椭圆形代表：特征或属性。长方形代表：类别结果。
面对一堆数据（含有特征和类别），决策树就是根据这些特征（椭圆形）来给数据归类（长方形）
例如，信用贷款问题，我根据《神奇动物在哪里》的剧情给银行造了个决策树模型，如下图：

然而，决定是否贷款可以根据很多特征，然麻鸡银行选择了：（1）是否房产价值>100w；（2）是否有其他值钱的抵押物；（3）月收入>10k；（4）是否结婚；这四个特征，来决定是否给予贷款。
先不管是否合理，但可以肯定的是，决策树做了特征选择工作，即选择出类别区分度高的特征。

由此可见， 决策树其实是一种特征选择方法。 （特征选择有多种，决策树属于嵌入型特征选择，以后或许会讲到，先给个图）即选择区分度高的特征子集。

那么， 从特征选择角度来看决策树，决策树就是嵌入型特征选择技术

同时，决策树也是机器学习中经典分类器算法，通过决策路径，最终能确定实例属于哪一类别。
那么， 从分类器角度来看决策树，决策树就是树型结构的分类模型

从人工智能知识表示法角度来看，决策树类似于if-then的产生式表示法。
那么， 从知识表示角度来看决策树，决策树就是if-then规则的集合

由上面的例子可知，麻鸡银行通过决策树模型来决定给哪些人贷款，这样决定贷款的流程就是固定的，而不由人的主观情感来决定。
那么， 从使用者角度来看决策树，决策树就是规范流程的方法

最后我们再来看看决策树的本质是什么已经不重要了。
决策树好像是一种思想，而通过应用在分类任务中从而成就了“决策树算法”。

下面内容还是继续讲解用于分类的“决策树算法”。

前面讲了决策树是一种 特征选择技术 。

既然决策树就是一种特征选择的方法，那么经典决策树算法其实就是使用了不同的特征选择方案。
如：
（1）ID3：使用信息增益作为特征选择
（2）C4.5：使用信息增益率作为特征选择
（3）CART：使用GINI系数作为特征选择
具体选择的方法网上一大把，在这里我提供几个链接，不细讲。

但，不仅仅如此。
决策树作为嵌入型特征选择技术结合了特征选择和分类算法，根据特征选择如何生成分类模型也是决策树的一部分。
其生成过程基本如下：

根据这三个步骤，可以确定决策树由：（1）特征选择；（2）生成方法；（3）剪枝，组成。
决策树中学习算法与特征选择的关系如下图所示：

原始特征集合T：就是包含收集到的原始数据所有的特征，例如：麻瓜银行收集到与是否具有偿还能力的所有特征，如：是否结婚、是否拥有100w的房产、是否拥有汽车、是否有小孩、月收入是否>10k等等。
中间的虚线框就是特征选择过程，例如：ID3使用信息增益、C4.5使用信息增益率、CART使用GINI系数。
其中评价指标（如：信息增益）就是对特征的要求，特征需要满足这种条件（一般是某个阈值），才能被选择，而这一选择过程嵌入在学习算法中，最终被选择的特征子集也归到学习算法中去。
这就是抽象的决策树生成过程，不论哪种算法都是将这一抽象过程的具体化。
其具体算法我将留在下一篇文章来讲解。

而决策树的剪枝，其实用得不是很多，因为很多情况下随机森林能解决决策树带来的过拟合问题，因此在这里也不讲了。

决策树的优化主要也是围绕决策树生成过程的三个步骤来进行优化的。
树型结构，可想而知，算法效率决定于树的深度，优化这方面主要从特征选择方向上优化。
提高分类性能是最重要的优化目标，其主要也是特征选择。
面对过拟合问题，一般使用剪枝来优化，如：李国和基于决策树生成及剪枝的数据集优化及其应用。
同时，决策树有很多不足，如：多值偏向、计算效率低下、对数据空缺较为敏感等，这方面的优化也有很多，大部分也是特征选择方向，如：陈沛玲使用粗糙集进行特征降维。
由此，决策树的优化方向大多都是特征选择方向，像ID3、C4.5、CART都是基于特征选择进行优化。

参考文献
统计学习方法-李航
特征选择方法综述-李郅琴
决策树分类算法优化研究_陈沛玲
基于决策树生成及剪枝的数据集优化及其应用-李国和

❻ 决策树的算法

C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：
1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；
2) 在树构造过程中进行剪枝；
3) 能够完成对连续属性的离散化处理；
4) 能够对不完整数据进行处理。
C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。
具体算法步骤如下；
1创建节点N
2如果训练集为空，在返回节点N标记为Failure
3如果训练集中的所有记录都属于同一个类别，则以该类别标记节点N
4如果候选属性为空，则返回N作为叶节点，标记为训练集中最普通的类；
5for each 候选属性 attribute_list
6if 候选属性是连续的then
7对该属性进行离散化
8选择候选属性attribute_list中具有最高信息增益率的属性D
9标记节点N为属性D
10for each 属性D的一致值d
11由节点N长出一个条件为D=d的分支
12设s是训练集中D=d的训练样本的集合
13if s为空
14加上一个树叶，标记为训练集中最普通的类
15else加上一个有C4.5（R - {D},C，s）返回的点 背景：
分类与回归树(CART——Classification And Regression Tree)) 是一种非常有趣并且十分有效的非参数分类和回归方法。它通过构建二叉树达到预测目的。
分类与回归树CART 模型最早由Breiman 等人提出，已经在统计领域和数据挖掘技术中普遍使用。它采用与传统统计学完全不同的方式构建预测准则，它是以二叉树的形式给出，易于理解、使用和解释。由CART 模型构建的预测树在很多情况下比常用的统计方法构建的代数学预测准则更加准确，且数据越复杂、变量越多，算法的优越性就越显着。模型的关键是预测准则的构建，准确的。
定义：
分类和回归首先利用已知的多变量数据构建预测准则, 进而根据其它变量值对一个变量进行预测。在分类中, 人们往往先对某一客体进行各种测量, 然后利用一定的分类准则确定该客体归属那一类。例如, 给定某一化石的鉴定特征, 预测该化石属那一科、那一属, 甚至那一种。另外一个例子是, 已知某一地区的地质和物化探信息, 预测该区是否有矿。回归则与分类不同, 它被用来预测客体的某一数值, 而不是客体的归类。例如, 给定某一地区的矿产资源特征, 预测该区的资源量。

❼ 决策树算法原理

决策树是通过一系列规则对数据进行分类的过程。它提供一种在什么条件下会得到什么值的类似规则的方法。决策树分为分类树和回归树两种，分类树对离散变量做决策树，回归树对连续变量做决策树。

如果不考虑效率等，那么样本所有特征的判断级联起来终会将某一个样本分到一个类终止块上。实际上，样本所有特征中有一些特征在分类时起到决定性作用，决策树的构造过程就是找到这些具有决定性作用的特征，根据其决定性程度来构造一个倒立的树--决定性作用最大的那个特征作为根节点，然后递归找到各分支下子数据集中次大的决定性特征，直至子数据集中所有数据都属于同一类。所以，构造决策树的过程本质上就是根据数据特征将数据集分类的递归过程，我们需要解决的第一个问题就是，当前数据集上哪个特征在划分数据分类时起决定性作用。

一棵决策树的生成过程主要分为以下3个部分:

特征选择：特征选择是指从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准，如何选择特征有着很多不同量化评估标准标准，从而衍生出不同的决策树算法。

决策树生成： 根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树停止生长。 树结构来说，递归结构是最容易理解的方式。

剪枝：决策树容易过拟合，一般来需要剪枝，缩小树结构规模、缓解过拟合。剪枝技术有预剪枝和后剪枝两种。

划分数据集的最大原则是：使无序的数据变的有序。如果一个训练数据中有20个特征，那么选取哪个做划分依据？这就必须采用量化的方法来判断，量化划分方法有多重，其中一项就是“信息论度量信息分类”。基于信息论的决策树算法有ID3、CART和C4.5等算法，其中C4.5和CART两种算法从ID3算法中衍生而来。

CART和C4.5支持数据特征为连续分布时的处理，主要通过使用二元切分来处理连续型变量，即求一个特定的值-分裂值：特征值大于分裂值就走左子树，或者就走右子树。这个分裂值的选取的原则是使得划分后的子树中的“混乱程度”降低，具体到C4.5和CART算法则有不同的定义方式。

ID3算法由Ross Quinlan发明，建立在“奥卡姆剃刀”的基础上：越是小型的决策树越优于大的决策树（be simple简单理论）。ID3算法中根据信息论的信息增益评估和选择特征，每次选择信息增益最大的特征做判断模块。ID3算法可用于划分标称型数据集，没有剪枝的过程，为了去除过度数据匹配的问题，可通过裁剪合并相邻的无法产生大量信息增益的叶子节点（例如设置信息增益阀值）。使用信息增益的话其实是有一个缺点，那就是它偏向于具有大量值的属性--就是说在训练集中，某个属性所取的不同值的个数越多，那么越有可能拿它来作为分裂属性，而这样做有时候是没有意义的，另外ID3不能处理连续分布的数据特征，于是就有了C4.5算法。CART算法也支持连续分布的数据特征。

C4.5是ID3的一个改进算法，继承了ID3算法的优点。C4.5算法用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足在树构造过程中进行剪枝；能够完成对连续属性的离散化处理；能够对不完整数据进行处理。C4.5算法产生的分类规则易于理解、准确率较高；但效率低，因树构造过程中，需要对数据集进行多次的顺序扫描和排序。也是因为必须多次数据集扫描，C4.5只适合于能够驻留于内存的数据集。

CART算法的全称是Classification And Regression Tree，采用的是Gini指数（选Gini指数最小的特征s）作为分裂标准,同时它也是包含后剪枝操作。ID3算法和C4.5算法虽然在对训练样本集的学习中可以尽可能多地挖掘信息，但其生成的决策树分支较大，规模较大。为了简化决策树的规模，提高生成决策树的效率，就出现了根据GINI系数来选择测试属性的决策树算法CART。

决策树算法的优点：

（1）便于理解和解释，树的结构可以可视化出来

（2）基本不需要预处理，不需要提前归一化，处理缺失值

（3）使用决策树预测的代价是O(log2m)，m为样本数

（4）能够处理数值型数据和分类数据

（5）可以处理多维度输出的分类问题

（6）可以通过数值统计测试来验证该模型，这使解释验证该模型的可靠性成为可能

（7）即使该模型假设的结果与真实模型所提供的数据有些违反，其表现依旧良好

决策树算法的缺点:

（1）决策树模型容易产生一个过于复杂的模型,这样的模型对数据的泛化性能会很差。这就是所谓的过拟合.一些策略像剪枝、设置叶节点所需的最小样本数或设置数的最大深度是避免出现该问题最为有效地方法。

（2）决策树可能是不稳定的，因为数据中的微小变化可能会导致完全不同的树生成。这个问题可以通过决策树的集成来得到缓解。

（3）在多方面性能最优和简单化概念的要求下，学习一棵最优决策树通常是一个NP难问题。因此，实际的决策树学习算法是基于启发式算法，例如在每个节点进行局部最优决策的贪心算法。这样的算法不能保证返回全局最优决策树。这个问题可以通过集成学习来训练多棵决策树来缓解,这多棵决策树一般通过对特征和样本有放回的随机采样来生成。

（4）有些概念很难被决策树学习到,因为决策树很难清楚的表述这些概念。例如XOR，奇偶或者复用器的问题。

（5）如果某些类在问题中占主导地位会使得创建的决策树有偏差。因此，我们建议在拟合前先对数据集进行平衡。

（1）当数据的特征维度很高而数据量又很少的时候，这样的数据在构建决策树的时候往往会过拟合。所以我们要控制样本数量和特征的之间正确的比率；

（2）在构建决策树之前，可以考虑预先执行降维技术（如PCA，ICA或特征选择），以使我们生成的树更有可能找到具有辨别力的特征；

（3）在训练一棵树的时候，可以先设置max_depth=3来将树可视化出来，以便我们找到树是怎样拟合我们数据的感觉，然后在增加我们树的深度；

（4）树每增加一层，填充所需的样本数量是原来的2倍，比如我们设置了最小叶节点的样本数量，当我们的树层数增加一层的时候，所需的样本数量就会翻倍，所以我们要控制好树的最大深度，防止过拟合；

（5）使用min_samples_split（节点可以切分时拥有的最小样本数） 和 min_samples_leaf（最小叶节点数）来控制叶节点的样本数量。这两个值设置的很小通常意味着我们的树过拟合了，而设置的很大意味着我们树预测的精度又会降低。通常设置min_samples_leaf=5；

（6）当树的类比不平衡的时候，在训练之前一定要先平很数据集，防止一些类别大的类主宰了决策树。可以通过采样的方法将各个类别的样本数量到大致相等，或者最好是将每个类的样本权重之和(sample_weight)规范化为相同的值。另请注意，基于权重的预剪枝标准（如min_weight_fraction_leaf）将比不知道样本权重的标准（如min_samples_leaf）更少偏向主导类别。

（7）如果样本是带权重的，使用基于权重的预剪枝标准将更简单的去优化树结构，如mn_weight_fraction_leaf，这确保了叶节点至少包含了样本权值总体总和的一小部分；

（8）在sklearn中所有决策树使用的数据都是np.float32类型的内部数组。如果训练数据不是这种格式，则将复制数据集，这样会浪费计算机资源。

（9）如果输入矩阵X非常稀疏，建议在调用fit函数和稀疏csr_matrix之前转换为稀疏csc_matrix，然后再调用predict。 当特征在大多数样本中具有零值时，与密集矩阵相比，稀疏矩阵输入的训练时间可以快几个数量级。

❽ 决策树法有年份要乘年份吗

决策树法有年份也不需要乘年份 不需要乘年份

❾ 决策树的原理及算法

决策树基本上就是把我们以前的经验总结出来。我给你准备了一个打篮球的训练集。如果我们要出门打篮球，一般会根据“天气”、“温度”、“湿度”、“刮风”这几个条件来判断，最后得到结果：去打篮球？还是不去？

上面这个图就是一棵典型的决策树。我们在做决策树的时候，会经历两个阶段：构造和剪枝。

构造就是生成一棵完整的决策树。简单来说，构造的过程就是选择什么属性作为节点的过程，那么在构造过程中，会存在三种节点：
根节点：就是树的最顶端，最开始的那个节点。在上图中，“天气”就是一个根节点；
内部节点：就是树中间的那些节点，比如说“温度”、“湿度”、“刮风”；
叶节点：就是树最底部的节点，也就是决策结果。

剪枝就是给决策树瘦身，防止过拟合。分为“预剪枝”（Pre-Pruning）和“后剪枝”（Post-Pruning）。

预剪枝是在决策树构造时就进行剪枝。方法是在构造的过程中对节点进行评估，如果对某个节点进行划分，在验证集中不能带来准确性的提升，那么对这个节点进行划分就没有意义，这时就会把当前节点作为叶节点，不对其进行划分。

后剪枝就是在生成决策树之后再进行剪枝，通常会从决策树的叶节点开始，逐层向上对每个节点进行评估。如果剪掉这个节点子树，与保留该节点子树在分类准确性上差别不大，或者剪掉该节点子树，能在验证集中带来准确性的提升，那么就可以把该节点子树进行剪枝。

1是欠拟合，3是过拟合，都会导致分类错误。

造成过拟合的原因之一就是因为训练集中样本量较小。如果决策树选择的属性过多，构造出来的决策树一定能够“完美”地把训练集中的样本分类，但是这样就会把训练集中一些数据的特点当成所有数据的特点，但这个特点不一定是全部数据的特点，这就使得这个决策树在真实的数据分类中出现错误，也就是模型的“泛化能力”差。

p(i|t) 代表了节点 t 为分类 i 的概率，其中 log2 为取以 2 为底的对数。这里我们不是来介绍公式的，而是说存在一种度量，它能帮我们反映出来这个信息的不确定度。当不确定性越大时，它所包含的信息量也就越大，信息熵也就越高。

ID3 算法计算的是信息增益，信息增益指的就是划分可以带来纯度的提高，信息熵的下降。它的计算公式，是父亲节点的信息熵减去所有子节点的信息熵。

公式中 D 是父亲节点，Di 是子节点，Gain(D,a) 中的 a 作为 D 节点的属性选择。

因为 ID3 在计算的时候，倾向于选择取值多的属性。为了避免这个问题，C4.5 采用信息增益率的方式来选择属性。信息增益率 = 信息增益 / 属性熵，具体的计算公式这里省略。

当属性有很多值的时候，相当于被划分成了许多份，虽然信息增益变大了，但是对于 C4.5 来说，属性熵也会变大，所以整体的信息增益率并不大。

ID3 构造决策树的时候，容易产生过拟合的情况。在 C4.5 中，会在决策树构造之后采用悲观剪枝（PEP），这样可以提升决策树的泛化能力。

悲观剪枝是后剪枝技术中的一种，通过递归估算每个内部节点的分类错误率，比较剪枝前后这个节点的分类错误率来决定是否对其进行剪枝。这种剪枝方法不再需要一个单独的测试数据集。

C4.5 可以处理连续属性的情况，对连续的属性进行离散化的处理。比如打篮球存在的“湿度”属性，不按照“高、中”划分，而是按照湿度值进行计算，那么湿度取什么值都有可能。该怎么选择这个阈值呢，C4.5 选择具有最高信息增益的划分所对应的阈值。

针对数据集不完整的情况，C4.5 也可以进行处理。

暂无

请你用下面的例子来模拟下决策树的流程，假设好苹果的数据如下，请用 ID3 算法来给出好苹果的决策树。

“红”的信息增益为：1“大”的信息增益为：0
因此选择“红”的作为根节点，“大”没有用，剪枝。

数据分析实战45讲.17 丨决策树（上）：要不要去打篮球？决策树来告诉你

❿ 数据挖掘-决策树算法

决策树算法是一种比较简易的监督学习分类算法，既然叫做决策树，那么首先他是一个树形结构，简单写一下树形结构（数据结构的时候学过不少了）。

树状结构是一个或多个节点的有限集合，在决策树里，构成比较简单，有如下几种元素：

在决策树中，每个叶子节点都有一个类标签，非叶子节点包含对属性的测试条件，用此进行分类。
所以个人理解，决策树就是 对一些样本，用树形结构对样本的特征进行分支，分到叶子节点就能得到样本最终的分类，而其中的非叶子节点和分支就是分类的条件，测试和预测分类就可以照着这些条件来走相应的路径进行分类。

根据这个逻辑，很明显决策树的关键就是如何找出决策条件和什么时候算作叶子节点即决策树终止。

决策树的核心是为不同类型的特征提供表示决策条件和对应输出的方法，特征类型和划分方法包括以下几个：

注意，这些图中的第二层都是分支，不是叶子节点。

如何合理的对特征进行划分，从而找到最优的决策模型呢？在这里需要引入信息熵的概念。

先来看熵的概念：

在数据集中，参考熵的定义，把信息熵描述为样本中的不纯度，熵越高，不纯度越高，数据越混乱（越难区分分类）。

例如：要给（0，1）分类，熵是0，因为能明显分类，而均衡分布的（0.5，0.5）熵比较高，因为难以划分。

信息熵的计算公式为：
其中 代表信息熵。 是类的个数， 代表在 类时 发生的概率。
另外有一种Gini系数，也可以用来衡量样本的不纯度：
其中 代表Gini系数，一般用于决策树的 CART算法 。

举个例子：

如果有上述样本，那么样本中可以知道，能被分为0类的有3个，分为1类的也有3个，那么信息熵为：
Gini系数为：
总共有6个数据，那么其中0类3个，占比就是3/6，同理1类。

我们再来计算一个分布比较一下：

信息熵为：
Gini系数为：

很明显，因为第二个分布中，很明显这些数偏向了其中一类，所以 纯度更高 ，相对的信息熵和Gini系数较低。

有了上述的概念，很明显如果我们有一组数据要进行分类，最快的建立决策树的途径就是让其在每一层都让这个样本纯度最大化，那么就要引入信息增益的概念。

所谓增益，就是做了一次决策之后，样本的纯度提升了多少（不纯度降低了多少），也就是比较决策之前的样本不纯度和决策之后的样本不纯度，差越大，效果越好。
让信息熵降低，每一层降低的越快越好。
度量这个信息熵差的方法如下：
其中 代表的就是信息熵（或者其他可以度量不纯度的系数）的差， 是样本(parent是决策之前， 是决策之后)的信息熵（或者其他可以度量不纯度的系数）， 为特征值的个数， 是原样本的记录总数， 是与决策后的样本相关联的记录个数。

当选择信息熵作为样本的不纯度度量时，Δ就叫做信息增益 。

我们可以遍历每一个特征，看就哪个特征决策时，产生的信息增益最大，就把他作为当前决策节点，之后在下一层继续这个过程。

举个例子：

如果我们的目标是判断什么情况下，销量会比较高（受天气，周末，促销三个因素影响），根据上述的信息增益求法，我们首先应该找到根据哪个特征来决策，以信息熵为例：

首先肯定是要求 ，也就是销量这个特征的信息熵：

接下来，就分别看三个特征关于销量的信息熵，先看天气，天气分为好和坏两种，其中天气为好的条件下，销量为高的有11条，低的有6条；天气坏时，销量为高的有7条，销量为低的有10条，并且天气好的总共17条，天气坏的总共17条。

分别计算天气好和天气坏时的信息熵，天气好时：

根据公式 ，可以知道，N是34，而天气特征有2个值，则k=2，第一个值有17条可以关联到决策后的节点，第二个值也是17条，则能得出计算：

再计算周末这个特征，也只有两个特征值，一个是，一个否，其中是有14条，否有20条；周末为是的中有11条销量是高，3条销量低，以此类推有：


信息增益为：

另外可以得到是否有促销的信息增益为0.127268。

可以看出，以周末为决策，可以得到最大的信息增益，因此根节点就可以用周末这个特征进行分支：

注意再接下来一层的原样本集，不是34个而是周末为“是”和“否”分别计算，为是的是14个，否的是20个。
这样一层一层往下递归，直到判断节点中的样本是否都属于一类，或者都有同一个特征值，此时就不继续往下分了，也就生成了叶子节点。

上述模型的决策树分配如下：

需要注意的是，特征是否出现需要在分支当中看，并不是整体互斥的，周末生成的两个分支，一个需要用促销来决策，一个需要用天气，并不代表再接下来就没有特征可以分了，而是在促销决策层下面可以再分天气，另外一遍天气决策下面可以再分促销。

决策树的模型比较容易解释，看这个树形图就能很容易的说出分类的条件。

我们知道属性有二元属性、标称属性、序数属性和连续属性，其中二元、标称和序数都是类似的，因为是离散的属性，按照上述方式进行信息增益计算即可，而连续属性与这三个不同。

对于连续的属性，为了降低其时间复杂度，我们可以先将属性内部排序，之后取相邻节点的均值作为决策值，依次取每两个相邻的属性值的均值，之后比较他们的不纯度度量。

需要注意的是，连续属性可能在决策树中出现多次，而不是像离散的属性一样在一个分支中出现一次就不会再出现了。

用信息熵或者Gini系数等不纯度度量有一个缺点，就是会倾向于将多分支的属性优先分类——而往往这种属性并不是特征。

例如上面例子中的第一行序号，有34个不同的值，那么信息熵一定很高，但是实际上它并没有任何意义，因此我们需要规避这种情况，如何规避呢，有两种方式：

公式如下：

其中k为划分的总数，如果每个属性值具有相同的记录数，则 ，划分信息等于 ，那么如果某个属性产生了大量划分，则划分信息很大，信息增益率低，就能规避这种情况了。

为了防止过拟合现象，往往会对决策树做优化，一般是通过剪枝的方式，剪枝又分为预剪枝和后剪枝。

在构建决策树时，设定各种各样的条件如叶子节点的样本数不大于多少就停止分支，树的最大深度等，让决策树的层级变少以防止过拟合。
也就是在生成决策树之前，设定了决策树的条件。

后剪枝就是在最大决策树生成之后，进行剪枝，按照自底向上的方式进行修剪，修剪的规则是，评估叶子节点和其父节点的代价函数，如果父节点的代价函数比较小，则去掉这个叶子节点。
这里引入的代价函数公式是：
其中 代表的是叶子节点中样本个数， 代表的是该叶子节点上的不纯度度量，把每个叶子节点的 加起来，和父节点的 比较，之后进行剪枝即可。