㈠ 决策树的原理及算法
决策树基本上就是把我们以前的经验总结出来。我给你准备了一个打篮球的训练集。如果我们要出门打篮球，一般会根据“天气”、“温度”、“湿度”、“刮风”这几个条件来判断，最后得到结果：去打篮球？还是不去？
上面这个图就是一棵典型的决策树。我们在做决策树的时候，会经历两个阶段：构造和剪枝。
构造就是生成一棵完整的决策树。简单来说，构造的过程就是选择什么属性作为节点的过程，那么在构造过程中，会存在三种节点：
根节点：就是树的最顶端，最开始的那个节点。在上图中，“天气”就是一个根节点；
内部节点：就是树中间的那些节点，比如说“温度”、“湿度”、“刮风”；
叶节点：就是树最底部的节点，也就是决策结果。
剪枝就是给决策树瘦身，防止过拟合。分为“预剪枝”（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 丨决策树（上）：要不要去打篮球？决策树来告诉你
㈡ 决策树分类算法有哪些
问题一：决策树算法是按什么来进行分类的 决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。
决策树方法最早产生于上世纪60年代，到70年代末。由J Ross Quinlan提出了ID3算法，此算法的目的在于减少树的深度。但是忽略了叶子数目的研究。C4.5算法在ID3算法的基础上进行了改进，对于预测变量的缺值处理、剪枝技术、派生规则等方面作了较大改进，既适合于分类问题，又适合于回归问题。
决策树算法构造决策树来发现数据中蕴涵的分类规则．如何构造精度高、规模小的决策树是决策树算法的核心内容。决策树构造可以分两步进行。第一步，决策树的生成：由训练样本集生成决策树的过程。一般情况下，训练样本数据集是根据实际需要有历史的、有一定综合程度的，用于数据分析处理的数据集。第二步，决策树的剪枝：决策树的剪枝是对上一阶段生成的决策树进行检验、校正和修下的过程，主要是用新的样本数据集（称为测试数据集）中的数据校验决策树生成过程中产生的初步规则，将那些影响预衡准确性的分枝剪除。
问题二：数据挖掘分类方法决策树可以分多类么 数据挖掘,也称之为数据库中知识发现是一个可以从海量数据中智能地和自动地抽取一些有用的、可信的、有效的和可以理解的模式的过程.分类是数据挖掘的重要内容之一.目前,分类已广泛应用于许多领域,如医疗诊断、天气预测、信用证实、顾客区分、欺诈甄别. 现己有多种分类的方法,其中决策树分类法在海量数据环境中应用最为广泛.其原因如下：
1、决策树分类的直观的表示方法较容易转化为标准的数据库查询
2、决策树分类归纳的方法行之有效,尤其适合大型数据集.
3、决策树在分类过程中,除了数据集中已包括的信息外,不再需要额外的信息.
4、决策树分类模型的精确度较高. 该文首先研究了评估分类模型的方法.在此基础上着重研究了决策树分类方法,并对决策树算法的可伸缩性问题进行了具体分析,最后给出了基于OLE DB for DM开发决策树分类预测应用程序.
问题三：基于规则的分类器（比如用RIPPER算法）和决策树的区别在哪，使用场景有什么不同？ 决策树实际上是规则分类器。基于转换的错误驱动学习方法的提出者曾经在论文中论证过这个问题，他的学习方法是规则学习器，但和决策树等价。
问题四：决策树的优缺点是什么啊 决策树(Decision Tree)是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。
决策树的优缺点：
优点：
1) 可以生成可以理解的规则。
2) 计算量相对来说不是很大。
3) 可以处理连续和种类字穿。
4) 决策树可以清晰的显示哪些字段比较重要
缺点：
1) 对连续性的字段比较难预测。
2) 对有时间顺序的数据，需要很多预处理的工作。
3) 当类别太多时，错误可能就会增加的比较快。
4) 一般的算法分类的时候，只是根据一个字段来分类。
问题五：c4.5决策树算法怎么得到分类结果 决策树主要有ID3，C4.5，CART等形式。ID3选取信息增益的属性递归进行分类，C4.5改进为使用信息增益率来选取分类属性。CART是Classfication and Regression Tree的缩写。表明CART不仅可以进行分类，也可以进行回归。
问题六：决策树分类算法的适用领域，不要概括成经济、社会、医疗领域，具体到实际问题。且用什么软件实现较方便。 决策树算法主要用于数据挖掘和机器学习，数据挖掘就是从海量数据中找出规律。一个有名的例子就是啤酒和尿布的例子，这是数据挖掘的典型。决策树算法包括ID3，C4.5，CART等，各种算法都是利用海量的数据来生成决策树的，决策树能帮助人或者机器做出决策。最简单的一个例子就是你去看病，根据决策树，医生能够判断这是什么病。软件的话用VISUAL STUDIO就可以，C语言，C++,C#，java都可以。
问题七：贝叶斯网络和贝叶斯分类算法的区别 贝叶斯分类算法是统计学的一种分类方法，它是一类利用概率统计知识进行分类的算法。在许多场合，朴素贝叶斯(Na?ve Bayes，NB)分类算法可以与决策树和神经网络分类算法相媲美，该算法能运用到大型数据库中，而且方法简单、分类准确率高、速度快。
由于贝叶斯定理假设一个属性值对给定类的影响独立于其它属性的值，而此假设在实际情况中经常是不成立的，因此其分类准确率可能会下降。为此，就衍生出许多降低独立性假设的贝叶斯分类算法，如TAN(tree augmented Bayes network)算法。
㈢ 机器学习故事汇-决策树算法
机器学习故事汇-决策树算法
【咱们的目标】系列算法讲解旨在用最简单易懂的故事情节帮助大家掌握晦涩无趣的机器学习，适合对数学很头疼的同学们，小板凳走起！
决策树模型是机器学习中最经典的算法之一啦，用途之广泛我就不多吹啦，其实很多机器学习算法都是以树模型为基础的，比如随机森林,Xgboost等一听起来就是很牛逼的算法（其实用起来也很牛逼）。
首先我们来看一下在上面的例子中我想根据人的年龄和性别（两个特征）对5个人（样本数据）进行决策，看看他们喜不喜欢玩电脑游戏。首先根据年龄（根节点）进行了一次分支决策，又对左节点根据性别进行了一次分支决策，这样所有的样本都落到了最终的叶子节点，可以把每一个叶子节点当成我们最终的决策结果（比如Y代表喜欢玩游戏，N代表不喜欢玩游戏）。这样我们就通过决策树完成了非常简单的分类任务！
再来看一下树的组成，主要结构有根节点（数据来了之后首先进行判断的特征），非叶子节点（中间的一系列过程），叶子节点（最终的结果），这些都是我们要建立的模块！
在决策中树中，我们刚才的喜欢玩电脑游戏的任务看起来很简单嘛，从上往下去走不就OK了吗！但是难点在于我们该如何构造这棵决策树（节点的选择以及切分），这个看起来就有些难了，因为当我们手里的数据特征比较多的时候就该犹豫了，到底拿谁当成是根节点呢？
这个就是我们最主要的问题啦，节点究竟该怎么选呢？不同的位置又有什么影响？怎么对特征进行切分呢？一些到这，我突然想起来一个段子，咱们来乐呵乐呵！
武林外传中这个段子够我笑一年的，其实咱们在推导机器学习算法的时候，也需要这么去想想，只有每一步都是有意义的我们才会选择去使用它。回归正题，我们选择的根节点其实意味着它的重要程度是最大的，相当于大当家了，因为它会对数据进行第一次切分，我们需要把最重要的用在最关键的位置，在决策树算法中，为了使得算法能够高效的进行，那么一开始就应当使用最有价值的特征。
接下来咱们就得唠唠如何选择大当家了，我们提出了一个概念叫做熵（不是我提出的。。。穿山甲说的），这里并不打算说的那么复杂，一句话解释一下，熵代表你经过一次分支之后分类的效果的好坏，如果一次分支决策后都属于一个类别（理想情况下，也是我们的目标）这时候我们认为效果很好嘛，那熵值就很低。如果分支决策后效果很差，什么类别都有，那么熵值就会很高，公式已经给出，log函数推荐大家自己画一下，然后看看概率[0,1]上的时候log函数值的大小（你会豁然开朗的）。
不确定性什么时候最大呢？模棱两可的的时候（就是你犹豫不决的时候）这个时候熵是最大的，因为什么类别出现的可能性都有。那么我们该怎么选大当家呢？（根节点的特征）当然是希望经过大当家决策后，熵值能够下降（意味着类别更纯净了，不那么混乱了）。在这里我们提出了一个词叫做信息增益（就当是我提出的吧。。。），信息增益表示经过一次决策后整个分类后的数据的熵值下降的大小，我们希望下降越多越好，理想情况下最纯净的熵是等于零的。
一个栗子：准备一天一个哥们打球的时候，包括了4个特征（都是环境因素）以及他最终有木有去打球的数据。
第一个问题：大当家该怎么选？也就是我们的根节点用哪个特征呢？
一共有4个特征，看起来好像用谁都可以呀，这个时候就该比试比试了，看看谁的能力强（使得熵值能够下降的最多）
在历史数据中，首先我们可以算出来当前的熵值，计算公式同上等于0.940，大当家的竞选我们逐一来分析，先看outlook这个特征，上图给出了基于天气的划分之后的熵值，计算方式依旧同上，比如outlook=sunny时，yes有2个,no有三个这个时候熵就直接将2/5和3/5带入公式就好啦。最终算出来了3种情况下的熵值。
再继续来看！outlook取不同情况的概率也是不一样的，这个是可以计算出来的相当于先验概率了，直接可以统计出来的，这个也需要考虑进来的。然后outlook竞选大当家的分值就出来啦（就是信息增益）等于0.247。同样的方法其余3个特征的信息增益照样都可以计算出来，谁的信息增益多我们就认为谁是我们的大当家，这样就完成了根节点的选择，接下来二当家以此类推就可以了！
我们刚才给大家讲解的是经典的ID3算法，基于熵值来构造决策树，现在已经有很多改进，比如信息增益率和CART树。简单来说一下信息增益率吧，我们再来考虑另外一个因素，如果把数据的样本编号当成一个特征，那么这个特征必然会使得所有数据完全分的开，因为一个样本只对应于一个ID，这样的熵值都是等于零的，所以为了解决这类特征引入了信息增益率，不光要考虑信息增益还要考虑特征自身的熵值。说白了就是用 信息增益/自身的熵值 来当做信息增益率。
我们刚才讨论的例子中使用的是离散型的数据，那连续值的数据咋办呢？通常我们都用二分法来逐一遍历来找到最合适的切分点！
下面再来唠一唠决策树中的剪枝任务，为啥要剪枝呢？树不是好好的吗，剪个毛线啊！这个就是机器学习中老生常谈的一个问题了，过拟合的风险，说白了就是如果一个树足够庞大，那么所有叶子节点可能只是一个数据点（无限制的切分下去），这样会使得我们的模型泛化能力很差，在测试集上没办法表现出应有的水平，所以我们要限制决策树的大小，不能让枝叶太庞大了。
最常用的剪枝策略有两种：
（1）预剪枝：边建立决策树边开始剪枝的操作
（2）后剪枝：建立完之后根据一定的策略来修建
这些就是我们的决策树算法啦，其实还蛮好的理解的，从上到下基于一种选择标准（熵，GINI系数）来找到最合适的当家的就可以啦！
㈣ 决策树之CART算法
一、基本概念
1.cart使用基尼系数作为划分标准。基尼系数越小，则不纯度越低，区分的越彻底。
2.假设有k个类别，第k个类别的概率为 ,则基尼系数表达式为：
Gini(p)= (1- )=1-
3.对于样本D，如果根据特征A 的值把样本分为D1,D2两部分，则在特征A条件下，D的基尼系数
Gini(D,A)= Gini(D1)+ Gini(D2)
4.CART建立起来的是二叉树，如果特征A有A1,A2，A3三个类别，CART会考虑把A分成{A1},{A2 ,A3}两组，或者是其他两种情况。由于这次A并没有完全分开，所以下次还有机会在子节点把A2,A3分开.
5.对于连续值的切分.假如有1 2 3 4 5 那么cart会有4个切分点 [1.5 2.5 3.5 4.5]
二.实例推导树的建立过程
1.假设我有以下源数据
序号 天气 周末 促销 销量
1 坏 是 是 高
2 坏 是 是 高
3 坏 是 是 高
4 坏 否 是 高
5 坏 是 是 高
6 坏 否 是 高
7 坏 是 否 高
8 好 是 是 高
9 好 是 否 高
10 好 是 是 高
11 好 是 是 高
12 好 是 是 高
13 好 是 是 高
14 坏 是 是 低
15 好 否 是 高
16 好 否 是 高
17 好 否 是 高
18 好 否 是 高
19 好 否 否 高
20 坏 否 否 低
21 坏 否 是 低
22 坏 否 是 低
23 坏 否 是 低
24 坏 否 否 低
25 坏 是 否 低
26 好 否 是 低
27 好 否 是 低
28 坏 否 否 低
29 坏 否 否 低
30 好 否 否 低
31 坏 是 否 低
32 好 否 是 低
33 好 否 否 低
34 好 否 否 低
该数据集有三个特征 天气 周末 促销
2.为了简化建立树的过程,我将忽略基尼系数与样本个数阀值
2.1 首先计算各个特征值对数据集的基尼系数,公式见---- 基本概念.3
Gini(D|天气)=17/34*(1-(11/17)^2-(6/17)^2)+17/34*(1-(7/17)^2-(10/17)^2)=0.4706
Gini(D|周末)=20/34*(1-(7/20)^2-(13/20)^2)+14/34*(1-(11/14)^2-(3/14)^2)=0.4063
Gini(D|促销)=12/34*(1-(9/12)^2-(3/12)^2)+22/34*(1-(7/22)^2-(15/22)^2)=0.4131
周末的基尼系数最小，这也符合我们的一般认识
2.2 第一个分列特征选择周末。此时数据集按照是否周末分成两个。
Gini(周末|天气)=0.2679
Gini(周末|促销)=0.2714
Gini(非周末|天气)=0.3505
Gini(非周末|促销)=0.3875
此时，周末应该以天气作为划分，非周末也是以天气作为划分，下面放个图
三、CART树对于连续特征的处理
假如特征A为连续型变量，则把特征A按照从小到大进行排序，取相邻两点的平均值为切分点，计算基尼系数。则基尼系数最小的点为切分点，大于切分点的为一类，小于切分点的为另一类。举例：特征A的值为 1，2，3，4，5，6 目标变量是高、低、高、低、高、低。则1.5处的基尼系数为 (1/6)*(1-1^2)+(5/6)*(1-(2/5)^2-(3/5)^2)=0.4 2.5处的基尼系数为 (2/6)*(1-(1/2)^2-(1/2)^2)+(4/6)*(1-(2/4)^2-(2/4)^2)=0.5 3.5处的基尼系数为 (3/6)*(1-(1/3)^2-(2/3)^2)+(3/6)*(1-(1/3)^2-(2/3)^2)=0.44 4.5处的基尼系数为 (4/6)*(1-(2/4)^2-(2/4)^2)+(2/6)*(1-(1/2)^2-(1/2)^2)=0.5 5.5处的基尼系数为 (5/6)*(1-(2/5)^2-(3/5)^2)+(1/6)*(1-1^2)=0.4 结论： 1.5和5.5处的基尼系数最小，可以把1分为一类，2-6分为另一类。或者6分为一类，1-5另一类。
四、关于回归树
1.回归树和分类树的区别在于输出值类型不同。分类树输出的是离散值，回归树输出的是连续值。
2.和分类树使用基尼系数不同，回归树使用和均方差来度量最佳分隔点。假设有1 2 3 4 5 6 六个数。假设3.5处把数据分开最合适，那么(1-2)^2+(2-2)^2+(3-2)^2+(4-5)^2+(5-5)^2+(6-5)^2在所有分割点中取得最小值。2，5为各自数据段的平均值。
3.回归树采用最后叶子的平均值或者中值作为输出结果
㈤ 决策树算法-原理篇
关于决策树算法，我打算分两篇来讲，一篇讲思想原理，另一篇直接撸码来分析算法。本篇为原理篇。
通过阅读这篇文章，你可以学到：
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都是基于特征选择进行优化。
参考文献
统计学习方法-李航
特征选择方法综述-李郅琴
决策树分类算法优化研究_陈沛玲
基于决策树生成及剪枝的数据集优化及其应用-李国和
㈥ 数据挖掘-决策树算法
决策树算法是一种比较简易的监督学习分类算法，既然叫做决策树，那么首先他是一个树形结构，简单写一下树形结构（数据结构的时候学过不少了）。
树状结构是一个或多个节点的有限集合，在决策树里，构成比较简单，有如下几种元素：
在决策树中，每个叶子节点都有一个类标签，非叶子节点包含对属性的测试条件，用此进行分类。
所以个人理解，决策树就是 对一些样本，用树形结构对样本的特征进行分支，分到叶子节点就能得到样本最终的分类，而其中的非叶子节点和分支就是分类的条件，测试和预测分类就可以照着这些条件来走相应的路径进行分类。
根据这个逻辑，很明显决策树的关键就是如何找出决策条件和什么时候算作叶子节点即决策树终止。
决策树的核心是为不同类型的特征提供表示决策条件和对应输出的方法，特征类型和划分方法包括以下几个：
注意，这些图中的第二层都是分支，不是叶子节点。
如何合理的对特征进行划分，从而找到最优的决策模型呢？在这里需要引入信息熵的概念。
先来看熵的概念：
在数据集中，参考熵的定义，把信息熵描述为样本中的不纯度，熵越高，不纯度越高，数据越混乱（越难区分分类）。
例如：要给（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为划分的总数，如果每个属性值具有相同的记录数，则 ，划分信息等于 ，那么如果某个属性产生了大量划分，则划分信息很大，信息增益率低，就能规避这种情况了。
为了防止过拟合现象，往往会对决策树做优化，一般是通过剪枝的方式，剪枝又分为预剪枝和后剪枝。
在构建决策树时，设定各种各样的条件如叶子节点的样本数不大于多少就停止分支，树的最大深度等，让决策树的层级变少以防止过拟合。
也就是在生成决策树之前，设定了决策树的条件。
后剪枝就是在最大决策树生成之后，进行剪枝，按照自底向上的方式进行修剪，修剪的规则是，评估叶子节点和其父节点的代价函数，如果父节点的代价函数比较小，则去掉这个叶子节点。
这里引入的代价函数公式是：
其中 代表的是叶子节点中样本个数， 代表的是该叶子节点上的不纯度度量，把每个叶子节点的 加起来，和父节点的 比较，之后进行剪枝即可。
㈦ 决策树算法之随机森林
在 CART 分类回归树 的基础之上，我们可以很容易的掌握随机森林算法，它们之间的区别在于，CART 决策树较容易过拟合，而随机森林可以在一定程度上解决该问题。
随机森林的主要思想是：使用随机性产生出一系列简单的决策树，并组合它们的预测结果为最终的结果，可谓三个臭皮匠赛过一个诸葛亮，下面我们就来具体了解一下。
产生随机森林的步骤大致为三步
在第 1 步，它是一个可放回抽样，即所产生的样本是允许重复的，这种抽样又被称为 Bootstrap，例如我们有以下 mmy 数据
在做完 Bootstrap 之后，可能的样本数据如下
可见，样本数据中，第 3 条和第 4 条样本是一样的，都对应的是原始数据中的第 4 条。
接下来，就是要使用上面的样本数据来产生决策树了，产生决策树的方法和 CART 基本一致，唯一的不同地方在于，节点的构建不是来自于全部的候选特征，而是先从中随机的选择 n 个特征，在这 n 个特征中找出一个作为最佳节点。
举个例子，假设 n = 2，且我们随机选择了“血液循环正常”和“血管堵塞”这两个特征来产生根节点，如下：
我们将在上述两个特征中选择一个合适的特征作为根节点，假设在计算完 Gini 不纯度之后，“血液循环正常”这个特征胜出，那么我们的根节点便是“血液循环正常”，如下图所示
接下来我们还需要构建根节点下面的节点，下一个节点将会在剩下的“胸口疼痛”、“血管堵塞”和“体重”三个特征中产生，但我们依然不会计算所有这 3 个特征的 Gini 不纯度，而是从中随机选择 2 个特征，取这 2 个特征中的 Gini 不纯度较低者作为节点。
例如我们随机选到了“胸口疼痛”和“体重”这两列，如下：
假设此时“体重”的 Gini 不纯度更低，那么第 2 个节点便是“体重”，如下图：
继续下去，我们便产生了一棵决策树。
随机森林是多棵决策树，在产生完一棵决策树后，接着会循环执行上述过程：Bootstrap 出训练样本，训练决策树，直到树的数量达到设置值——通常为几百棵树。
现在我们产生了几百棵树的随机森林，当我们要预测一条数据时，该怎么做呢？我们会聚合这些树的结果，选择预测结果最多的那个分类作为最终的预测结果。
例如我们现在有一条数据：
该条数据被所有树预测的结果如下：
上述结果聚合后为：
取最多的那项为最终的预测结果，即 Yes——该病人被诊断为患有心脏病。
以上，随机森林的两个过程： B ootstrap 和 Agg regate 又被称为 Bagging 。
本文我们一起学习了随机森林的算法，和 CART 决策树比起来，它主要被用来解决过拟合问题，其主要的思想为 Bagging，即随机性有助于增强模型的泛化（Variance） 能力。
参考：
相关文章：
㈧ 决策树(decisionTree)
决策树(decisionTree)是一种基本的分类和回归方法。此文仅讨论用于分类方法的决策树。
决策树的学习通常分为3步：
决策树的学习的思想主要源于
定义决策树 ：
分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点(node)和有向边(directed edge)组成。结点又分为内部结点(internal node)和叶结点(leaf node)。内部结点表示一个特征或属性，叶结点表示一个类。
形如：
其中，圆表示内部结点，方框表示叶结点。
if-then规则，简单来说就是 ：
举例：对于一个苹果，外表是红色的是红苹果，外表是绿色的是青苹果。可以表示为：
if-then规则集合具有一个重要的性质：
这就是说每一个实例都被一条路径或规则覆盖，并且只被一条路径或规则覆盖。这里所谓的覆盖是指实例的特征与路径上的特征一致，或实例满足规则的条件。
给定数据集：
其中， 为输入实例（特征向量），含有 个特征， 为类标记， , 为样本容量。
目标 ：
根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确分类。
特征选择在于选取对训练数据具有分类能力的特征，这样可以提高决策树学习的效率。
如果我们利用某一个特征进行分类的结果与随机分类的结果没什么很大的差别的话，则称这个特征没有分类能力。
那么问题来了，怎么选择特征呢？
通常特征选择的准则是
下面通过例子来说明一下。
目标 ：
希望通过所给的训练集数据，学习一个贷款申请的决策树。当新的客户提出贷款申请的时候，根据申请人的特征利用决策树决定是否批准贷款申请。
可见这里共有4个特征可供选择。用特征选择的准则是 。接下来介绍 。
：
熵是表示随机变量不确定性的度量。
设 是一个取有限个值的随机变量，其概率分布为
则随机变量 的熵定义为
若 ，则定义 。通常对数取以2为底，或是以 为底，熵的单位分布为比特（bit）或是纳特（nat）。
由上式可知，熵只依赖 的分布，而已 的值无关，则 的熵还可记作 ，即
则从定义可知
当随机变量只取2个值的时候，例如 时， 的分布为
熵为
熵随概率变化的曲线为
当 或 时 ，随机变量完全没有不确定性，当 时 ，熵取值最大，随机变量不确定性最大。
设随机变量 ，其联合概率分布
条件熵 表示在已知随机变量 的条件下随机变量 的不确定性。随机变量 给定条件下随机变量 的条件熵(conditional entropy)，定义为 给定条件下 的条件概率分布的熵对 的数学期望
信息增益
特征 对训练集 的信息增益
根据信息增益准则的特征选择方法：对训练集 ，计算其每个特征的信息增益，并比较大小，选择信息增益最大的特征。
前期定义各个量：
信息增益的算法
输入：训练集 和特征 ；
输出：特征 对训练集 的信息增益
回看刚才的例子，
解 ：
这一次我很无聊的想用一下.csv文件类型。
所以训练数据集部分如下，我存在一个loan.csv文件里了。对.csv文件的各种处理一般由python的pandas模块完成。
第一步，导入相关模块
第二步，读入数据
若是使用jupyter，可以即刻查看一下数据，和数据标签。
可以看出，除了'ID'之外前4个标签 'age', 'work', 'own house', 'Credit conditions'为我们一直在说的特征 ，而最后一个标签'label'是我们所说的类 ，所以要处理一下这些标签，
第三步，计算训练集 的熵 ：
这里会用到pandas的一个统计数据的功能， groupby(by = [列]).groups ，将数据统计成字典的形式，这么说比较抽象，看下图，将我们用pandas读入的data，分为2类， ， Index 表示索引，即第0，1，4，5，6，14（python计数从0开始）个数据的 ，第2，3，7，8，9，10，11，12，13个数据的 .
那么计算训练集 的熵
第四步，计算特征 对数据集 的条件熵
第五步 ，计算信息增益
输入：训练集 和特征 和阈值 ；
输出：决策树
(1) 中所有实例都属于同一类 ，则 为单结点树，并将类 作为该结点的类标记，返回 ；
(2) 若 ，则 为单结点树，并将 中实例数最大的类 作为该结点的类标记，返回 ；
(3)否则，按照上述信息增益的算法，计算 中各个特征对 的信息增益，选择信息增益最大的特征 ；
(4)如果特征 的信息增益小于阈值 ，将置 为单结点树，并将 中实例数最大的类 作为该结点的类标记，返回 ；
(5)否则，对 的每一个可能值 ，依 将 分割为若干非空子集 ，将 中实例数最大的类 作为该结点的类标记，构建子结点，由结点及其子结点构成树 ，返回 ；
(6)对第 个子结点，以 为训练集，以 为特征集，递归的调用步骤(1)~步骤(5)，得到子树 ，返回 。
对上述表的训练集数据，利用ID3算法建立决策树。
解 ：
第一次迭代 ：
【特征：有自己的房子】将数据集 划分为2个子集 （有自己的房子）和 （没有自己的房子），观察一下 和 ：
：
由于 所有实例都属于同一类 ，所以它是一个叶结点，结点的类标记为“是”。
：
对于 则需从特征 中选择新的特征。
第二次迭代 ：
将 看作新的数据集 。【特征：有工作】有2个可能值，划分为2个子集 （有工作）和 （没有工作），观察一下 和 ：
：
由于 所有实例都属于同一类 ，所以它是一个叶结点，结点的类标记为“是”。
：