欢迎在文章下方评论，建议用电脑看
决策树应该是一个比较简单的算法了，对比后面svm，神经网络，PF树那些。所以应该讲起来应该会比较轻松，特别是学过数据结构的小伙伴来说，就更加的简单了。
下面开始吧！开头必须要上一个通俗的例子是吧！去网上找到一个比较有意思的例子，如下: 通俗来说，决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：
女儿：多大年纪了？
母亲：26。
女儿：长的帅不帅？
母亲：挺帅的。
女儿：收入高不？
母亲：不算很高，中等情况。
女儿：是公务员不？
母亲：是，在税务局上班呢。
女儿：那好，我去见见。
这个女孩的决策过程就是典型的分类树决策。相当于通过年龄、长相、收入和是否公务员对将男人分为两个类别：见和不见。假设这个女孩对男人的要求是：30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员，那么这个可以用下图表示女孩的决策逻辑（声明：此决策树纯属为了写文章而YY的产物，没有任何根据，也不代表任何女孩的择偶倾向）：
上图完整表达了这个女孩决定是否见一个约会对象的策略，其中绿色节点表示判断条件，橙色节点表示决策结果，箭头表示在一个判断条件在不同情况下的决策路径，图中红色箭头表示了上面例子中女孩的决策过程。
这幅图基本可以算是一颗决策树，说它“基本可以算”是因为图中的判定条件没有量化，如收入高中低等等，还不能算是严格意义上的决策树，如果将所有条件量化，则就变成真正的决策树了。
有了上面直观的认识，我们可以正式定义决策树了：
决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。
可以看到，决策树的决策过程非常直观，容易被人理解。目前决策树已经成功运用于医学、制造产业、天文学、分支生物学以及商业等诸多领域。知道了决策树的定义以及其应用方法，下面就详细的介绍下决策树吧！
首先是特征选择，特征选择在构造决策树是关键，主要有通过信息增益，信息增益比，基尼系数，对率回归来划分并进而构建决策树的方式！下面就一个一个的介绍吧！
信息增益在这里我不打算讲了，详细请看这篇博文
下面给出一些计算公式：
ID3算法的核心思想就是以信息增益度量属性选择，选择分裂后信息增益最大的属性进行分裂。下面来看看详细的算法过程
注意：停止构建树的临界点有如下: 1.提取特征后，剩下只有一个类。 2.Ag的信息增益小于阈值ε 3.没有特征可取。
例子：下面的例子来自《统计学习方法》(图片来自csnd):
ID3算法只有树的生成，所以该算法生成的树容易产生过拟合,针对这个问题，下面有专门的枝剪算法来防止过拟合。
信息增益比的生成决策树的算法和ID3的算法类似，所以下面讲不再专门用信息增益比（C4.5算法）来举例。
上面我们说了ID3和C4.5算法，下面我们就来总结下他们的特点：
一个属性的信息增益越大，表明属性对样本的熵减少的能力更强，这个属性使得数据由不确定性变成确定性的能力越强。 所以如果是取值更多的属性，更容易使得数据更“纯”（尤其是连续型数值），其信息增益更大，决策树会首先挑选这个属性作为树的顶点。结果训练出来的形状是一棵庞大且深度很浅的树，这样的划分是极为不合理的。
从节点的训练数据集D计算现有特征对该数据集的基尼指数(Gini)。此时，对每一个特征A，对其可能取得每一个值a，根据“样本A = a的结果是‘是’或‘否’”将D分割成D1，D2两部分，利用式①计算A = a 时的Gini。
PS：基尼指数(Gini)代表了某一集合的不确定性，Gini越大，样本集合的不确定性就越大，这点和熵相似。其实，我们可以将信息增益和基尼系数进行对比，他们的关系可以见下图：
PS：算法的停止条件是“节点的样本个数 < 预定阈值”或“样本集合的Gini < 预定阈值（样本基本属于同一类）”或“无更多特征”。
例子： 下面来看一个具体的例子。我们使用下图所示的数据集来作为示例，为了便于后面的叙述，我们将其再列出如下：
首先对数据集非类标号属性{是否有房，婚姻状况，年收入}分别计算它们的Gini系数增益，取Gini系数增益值最大的属性作为决策树的根节点属性。根节点的Gini系数
当根据是否有房来进行划分时，Gini系数增益计算过程为
若按婚姻状况属性来划分，属性婚姻状况有三个可能的取值{married，single，divorced}，分别计算划分后的
| {married} | {single,divorced} |
| {single} | {married,divorced} |
| {divorced} | {single,married} |
的Gini系数增益。
| 对比计算结果，根据婚姻状况属性来划分根节点时取Gini系数增益最大的分组作为划分结果，也就是{married} | {single,divorced}。 |
最后考虑年收入属性，我们发现它是一个连续的数值类型。我们在前面的文章里已经专门介绍过如何应对这种类型的数据划分了。对此还不是很清楚的朋友可以参考之前的文章，这里不再赘述。
对于年收入属性为数值型属性，首先需要对数据按升序排序，然后从小到大依次用相邻值的中间值作为分隔将样本划分为两组。例如当面对年收入为60和70这两个值时，我们算得其中间值为65。倘若以中间值65作为分割点。Sl作为年收入小于65的样本，Sr表示年收入大于等于65的样本，于是则得Gini系数增益为
其他值的计算同理可得，我们不再逐一给出计算过程，仅列出结果如下（最终我们取其中使得增益最大化的那个二分准则来作为构建二叉树的准则）：
最大化增益等价于最小化子女结点的不纯性度量（Gini系数）的加权平均值，之前的表里我们列出的是Gini系数的加权平均值，现在的表里给出的是Gini系数增益。现在我们希望最大化Gini系数的增益。根据计算知道，三个属性划分根节点的增益最大的有两个：年收入属性和婚姻状况，他们的增益都为0.12。此时，选取首先出现的属性作为第一次划分。
对于年收入属性则有：
最后我们构建的CART如下图所示：
最后我们总结一下，CART和C4.5/ID3的主要区别： C4.5/ID3采用信息增益/信息增益率来作为分支特征的选择标准，而CART则采用Gini系数； C4.5/ID3不一定是二叉树，但CART一定是二叉树。
因为决策树的生成算法容易构建过于复杂的决策树，产生过拟合。而剪枝从已生成的树上裁掉一些子树或叶结点，并将其根结点或父结点作为新的叶结点，从而简化分类树模型，在这里我们可以联想其实剪枝就是一直正则化手段，简化模型，防止过拟合！下面我们进行详细介绍：
预剪枝是指在决策树生成过程中，对每个结点事先估计，若不能提升泛化性能，则停止划分当前结点。预剪枝降低了过拟合的风险，也减少了决策树的训练时间，但是它是一种“贪心算法”很有可能会造成欠拟合。
在决策树学习中将已生成的树进行简化的过程称为剪枝(pruning)。具体地，剪枝从已生成的树上裁掉一些子树或叶结点，并将其根结点或父结点作为新的叶结点，从而简化分类树模型. 决策树的剪枝往往通过极小化决策树整体的损失函数(loss fimction)或代价函数( cost function)来实现。 设树T的叶结点个数为|T|, t是树T的叶结点，该叶结点有Nt个样本点，其中k类的样本点有Ntk个，k=1,2,…,K，Ht(T)为叶结点t上的经验嫡，a>=0为参数，则决策树学习的损失函数可以定义为
其中：
因前面的一项可以表示为：
则最终公式为：
C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，|T|表示平莫型复杂度，参数a>=0控制两者之间的影响。剪枝，就是当a确定时，选择损失函数最小的模型，即损失函数最小的子树。损失函数正好表示了对模型的复杂度和训练数据的拟合两者的平衡。 决策树生成只考虑了通过提高信息增益(或信息增益比)对训练数据进行更好的拟合，学习局部的模型； 决策树剪枝通过优化损失函数还考虑了减小模型复杂度，学习整体的模型。 利用损失函数最小原则进行剪枝就是用正则化的极大似然估计进行模型选择。
其实CART剪枝有挺多方式的，但在这里我只讲一种简单的常用的（也就是该博文中的：CCP—代价复杂度剪枝），其他方式可以看看这篇博文
来看下原文
参考资料：
《统计学习方法》-李航
《机器学习》-周志华
《机器学习实战》-Peter Harrington
斯坦福大学公开课-机器学习
网上的各位大牛的博文
