Ⅰ 决策树的原理及算法
决策树基本上就是把我们以前的经验总结出来。我给你准备了一个打篮球的训练集。如果我们要出门打篮球，一般会根据“天气”、“温度”、“湿度”、“刮风”这几个条件来判断，最后得到结果：去打篮球？还是不去？
上面这个图就是一棵典型的决策树。我们在做决策树的时候，会经历两个阶段：构造和剪枝。
构造就是生成一棵完整的决策树。简单来说，构造的过程就是选择什么属性作为节点的过程，那么在构造过程中，会存在三种节点：
根节点：就是树的最顶端，最开始的那个节点。在上图中，“天气”就是一个根节点；
内部节点：就是树中间的那些节点，比如说“温度”、“湿度”、“刮风”；
叶节点：就是树最底部的节点，也就是决策结果。
剪枝就是给决策树瘦身，防止过拟合。分为“预剪枝”（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 丨决策树（上）：要不要去打篮球？决策树来告诉你
Ⅱ 决策树算法-原理篇
关于决策树算法，我打算分两篇来讲，一篇讲思想原理，另一篇直接撸码来分析算法。本篇为原理篇。
通过阅读这篇文章，你可以学到：
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都是基于特征选择进行优化。
参考文献
统计学习方法-李航
特征选择方法综述-李郅琴
决策树分类算法优化研究_陈沛玲
基于决策树生成及剪枝的数据集优化及其应用-李国和
Ⅲ 决策树基本概念及算法优缺点
分类决策树模型是一种描述对实例进行分类的树形结构. 决策树由结点和有向边组成. 结点有两种类型: 内部结点和叶节点. 内部节点表示一个特征或属性, 叶节点表示一个类.
决策树(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:
Ⅳ 决策树算法
决策树算法的算法理论和应用场景
算法理论：
我了解的决策树算法，主要有三种，最早期的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的分类树，默认不剪枝。然后在出图后，自行选择合适的叶节点进行拒绝操作。
这个不剪枝是因为欺诈问题的特殊性，欺诈问题一般而言较少，如数据的万几水平，即正样本少，而整个欺诈问题需要解决的速度较快。此时只能根据业务要求，迅速针对已有的正样本情况，在控制准确率的前提下，尽可能提高召回率。这种情况下，可以使用决策树来简单应用，这个可以替代原本手工选择特征及特征阈值的情况。
Ⅳ 决策树总结
参考链接： https://www.cnblogs.com/yonghao/p/5061873.html
树：由节点和边两种元素组成。
父节点、子节点是相对的，子节点由父节点根据某一规则分裂而来。
根节点：没有父节点的节点，初始分裂节点。
叶子节点：没有子节点的节点。
决策树： 利用树形结构进行决策，每一个非叶子节点是一个判断条件，每一个叶子节点是结论。从根节点开始，经过多次判断得出结论。
每次选择一个属性进行判断（如何选择？），如果不能得出结论，继续选择其他属性进行判断，知道能够肯定地判断出用户类型或者上述属性都已使用完毕。
在决策树的过程中，三个问题最为关键：
贪婪思想：选择可以得到最有分裂结果的属性进行分裂。每一次分裂之后孩子节点的数据尽量“纯”。
信息增益
信息增益率
信息增益作为选择分裂的条件有一个不可避免的缺点：倾向选择分支比较多的属性进行分裂。（为什么？）
表示分列前后的数据复杂度和分裂节点数据复杂度的变化值：
Gain表示节点复杂度，Gain越大复杂度越高。
信息增益大 ，分裂后复杂度减小得多， 分类效果明显 。
复杂度的两种计算方式：
熵和基尼指数，主要区别在于，熵达到峰值的过程要相对慢一些。因此，熵对于混乱集合的判罚要更重一些。
a）熵Entropy
取值范围：[0,1]
熵大，混乱程度高，纯度低。v.v.
pi表示第i类的数量占比。Entropy也记为H(X)。
二分类中：如果两类数量相同，纯度最低，熵为1 。如果全部数据都属于一个类，及诶单纯度最高，熵为0 。
pi<1， 由上图可知，pi log(pi)为负值，故熵为pi log(pi)的和乘以-1。
条件熵：
随机变量X在给定条件下随机变量Y的条件熵。
X给定条件下Y的条件干率分布的熵对X的数学期望，在机器学习中为选定某个特征后的熵，公式如下：
b）基尼指数 Gini Index
取值范围：[0,1]
是一种不等性度量
总体内包含的类别越杂乱，gini指数越大，数据越不纯。
pi依旧为第i类的数量占比
使用信息增益作为选择分裂的条件倾向选择分支比较多的属性进行分裂。
为了解决这个问题，引入了信息增益率这个概念。信息增益率是在信息增益的基础上除以分裂节点数据量的信息增益。
InstrinsicInfo：分裂子节点数据量的信息增益
m：子节点数量
ni：第i个子节点的数据量
N：父节点数据量
离散型属性：按照属性值进行分裂，每一种属性值对应一个分裂节点。
连续性属性：按照该属性进行排序，并分为若干区间，每个区间对应一个节点。（区间大小如何选择？）
1）最小节点数
当街点数据量小于一个指定的数据量时，不继续分裂。
原因：
分类树：输出具体的类别
回归树：输出确定的数值
构建方法主要有三种：
预剪枝（Pre-Pruning）
后剪枝（Post-Pruning）
Ⅵ 决策树算法原理
决策树是通过一系列规则对数据进行分类的过程。它提供一种在什么条件下会得到什么值的类似规则的方法。决策树分为分类树和回归树两种，分类树对离散变量做决策树，回归树对连续变量做决策树。
如果不考虑效率等，那么样本所有特征的判断级联起来终会将某一个样本分到一个类终止块上。实际上，样本所有特征中有一些特征在分类时起到决定性作用，决策树的构造过程就是找到这些具有决定性作用的特征，根据其决定性程度来构造一个倒立的树--决定性作用最大的那个特征作为根节点，然后递归找到各分支下子数据集中次大的决定性特征，直至子数据集中所有数据都属于同一类。所以，构造决策树的过程本质上就是根据数据特征将数据集分类的递归过程，我们需要解决的第一个问题就是，当前数据集上哪个特征在划分数据分类时起决定性作用。
一棵决策树的生成过程主要分为以下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。 当特征在大多数样本中具有零值时，与密集矩阵相比，稀疏矩阵输入的训练时间可以快几个数量级。
Ⅶ 决策树的理解与应用
决策树🌲是一种基本的分类和回归的方法【以前总是下意识以为决策树只能用于分类，事实上还可以用于回归】。在分类问题中，决策树基于特征对实例进行分类，这个分类过程可以认为是if-then的规则集合，也可以认为是特征空间与类空间上的条件概率分布。
NOTE:
if—then规则集合具有一个重要的特征：互斥且完备，即每个实例都被一条路径或者一条规则所覆盖，而且只能被一条路径或一条规则所覆盖
优点 ：简单易理解、分类速度快
过程 ：利用损失函数最小化原则对训练集进行建模，再利用建立好的模型进行分类。决策树的学习算法通常是递归地选择最优特征，并根据特征对训练集进行分割，最终形成从【根结点->叶子结点】的树模型， 但是这样生成的树可以容易发生过拟合，所以需要自底向上修剪✋
决策树学习包括三个步骤：特征选择、决策树生成、决策树修剪
1.当特征数量较多时，在学习之前先进行特征选择
2.决策树生成对应局部最优
3.决策树修剪对应全局最优
目标 ：选择一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。
通常，特征选择的准则是 信息增益或者信息增益比
先介绍基本概念：
决策树的生成过程仅考虑到对训练数据集分类的准确性，这样生成的树模型容易出现过拟合且构建的树过于复杂，所以有必要对其进行剪枝。
剪枝 ：从已生成的树上裁掉一些子树或者叶结点，并将其根结点或者父结点作为新的叶结点，从而简化分类树模型。 剪枝往往是通过极小化决策树的整体损失函数来实现的
定义损失函数 ：
设树 的叶结点个数为 , 是树的叶结点，该叶结点有 个样本点，其中 类的样本点有 ，其中 是叶子结点 的经验熵， 为参数，决策树学习的损失函数为：
其中
所以最终的损失函数表示为：
公式解释： 是表示模型对训练集的预测误差，即模型与训练集的拟合程度， 表示模型的复杂度，叶子节点数越大模型越复杂， 是调节参数，控制模型的拟合和复杂程度。
当 确定时，选择损失函数最小的模型，这里定义的损失函数其实等价于正则化的极大似然估计。
算法：
INPUT: 生成算法产生的整个树 ，参数
OUPUT: 修剪后的子树
1.计算每个结点的经验熵
2.递归地从树的叶结点向上回缩
回缩前后整体树的损失函数比较，如果回缩前的损失函数大于回缩后，进行剪枝。
3.重复2，直到不能继续为止，得到损失函数最小的子树
后期加入
总结：决策树是一种简单快速的分类算法，本文不仅把熵相关的概念给整理了一遍，文中信息增益和信息增益比也可以用于其他模型的特征选择，而最后剪枝部分提到的决策树的损失函数是我之前在专门写的《详述机器学习中的损失函数》博客中没有提到的，这里也是一个补充。
Ⅷ 决策树算法总结
目录
一、决策树算法思想
二、决策树学习本质
三、总结
一、决策树（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、对类别不平衡的数据不友好。
Ⅸ 机器学习系列（三十六）——回归决策树与决策树总结
回归决策树树是用于回归的决策树模型，回归决策树主要指CART算法， 同样也为二叉树结构。以两个特征预测输出的回归问题为例，回归树的原理是将特征平面划分成若干单元，每一个划分租派耐单元都对应一个特定的输出。因为每个结点都是yes和no的判断，所以划分的边界是平行于坐标轴的。对于测试数据，我们只要将特征按照决策过程将其归到某个单元，便得到对应的回归输出值。
如上图所示的划分和相应的回归树，如果现在新来一个数据的特征是(6,7.5)，按照回归树，它对应的回归结果就是C5。节点的划分的过程也就是树的建立过程，每划分一次，随即确定划分单元对应的输出，也就多了一个结点。当根据相应的约束条件终止划分的时候，最终每个单元的输出也就确定了，输出也就是叶结点。这看似和分类树差不多，实则有很大的区别。划分点的寻找和输出值的确定羡慎是回归决策树的两个核心弊春问题。
一个输入空间的划分的误差是用真实值和划分区域的预测值的最小二乘来衡量的：
其中， 是每个划分单元的预测值，这个预测值是该单元内每个样本点的值的某种组合，比如可取均值：
（输入特征空间划分为 ）
那么求解最优划分即是求解最优化问题：
其中， 和 是每次划分形成的两个区域。
关于该最优化问题的求解这里不再介绍，下面直接使用skleaen中的决策回归树来看一下决策树的回归效果，数据集使用Boston房价数据：
不进行调参的话，可以看到在测试集上R方是0.59，显然这是不太好的结果，但是一个有趣的现象是，在训练集上：
R方值是1.0，也就是在训练集上决策树预测的回归结果完全吻合毫无偏差，这显然是过拟合。这个例子也说明了决策树算法是非常容易产生过拟合的，当然我们可以通过调参来缓解过拟合。
下面绘制学习曲线来直观看一下决策树回归模型的表现，首先绘制基于MSE的学习曲线：
学习曲线如下：
再绘制基于R方的学习曲线：
上面两种都是在默认情况下也就是不进行决策树深度和叶子节点个数等条件的限制得到的结果。发现在训练集上，如果不进行限制，可以做到0偏差，这是明显的过拟合。接下来调节参数再绘制学习曲线，为节约篇幅，只调节决策树深度这一个参数，而且只绘制基于R方的学习曲线：
max_depth=1时
max_depth=3时
max_depth=5时
随着深度的增加，模型复杂度越来越高，过拟合现象也越来越明显，可以测试，当max_depth=20时，在训练集上又为一条y=1的无偏差直线。有兴趣的仍然可以修改其它参数绘制学习曲线。
决策树的局限性：
使用本系列上篇文章中的鸢尾花数据，来看一下决策树对个别数据敏感会导致的结果，在本系列上篇文章中，使用信息熵划分，其余参数默认情况下绘制的决策边界是：
接着我们删除索引为138的数据，再来绘制决策边界：
发现此时的决策边界已经完全不同了，而这仅仅只是一个数据点的影响。
综上我们知道决策树实际是一种不够稳定的算法，它的表现极度依赖调参和数据，不过虽然决策树本身不是一种高效的机器学习算法，但是它们基于集成学习的组合——随机森林(RF)却是一个很鲁棒的机器学习算法，这将在下篇开始介绍。