决策树(Decision Tree )是用树的数据结构表示决策规则和分类结果的模型，是将乍一看似乎无序杂乱的已知事例转换为能够通过某种技术手段预测未知事例的树的模型。
时隔半个月，近年关闭了。 AI产品经理一定知道算法的第三篇终于来了。 我今天想和大家说话的是决策树。 少说话，进入正题。
如前面定义的那样，决策树(Decision Tree )也被称为判断树，是用树的数据结构表现决定规则和分类结果的模型，作为归纳学习算法，可以通过某种技术手段对乍一看无序杂乱的已知事例进行预测的未知事例
既然说拗音的定义是既定的，那就用通俗易懂的例子来说明决策树算法的原理吧。
决策树也是监督学习的分类算法，需要输入一组标记班级的训练样本，每个训练样本由用于分类的几个特征表示。 决策树算法的训练目的是构建决策树，期望能够将训练样本按照其类别进行分类的决策树。
情况：现在我们想预测的是，女性到底想和什么样的人结婚？ 我们现在手上有未婚男性的数据，包括收入、不动产、容貌、学历等领域。
提示：在构建决策树时，每次选择区域索引最高的特征，利用该特征值分割数据，每次消耗一个特征，重复进行直到所有特征都被使用。
如果没有使用所有的特征，剩下的训练样本已经有了相同的类别，就可以早点完成决策树的构建。 使用所有特征后，如果剩下的培训样本还包含一个或多个类别，请选择剩下的培训样本中占有率最高的类别作为这些培训样本的类别。 利用决策树的思想，首先要考虑的是，上述哪些条件是女性选择男朋友时最重要的考虑指标？ 那么，如果我在意收入，在意物质，我构建的决策树是什么样的呢？ 看图大家就明白了。
释义：这张图想说的是，我们从以下几个方面来判断是否结婚。 首先，看看其收入是否达到1w元。 不满足的人不会结婚。 从已经合格的人中继续选择。 有没有不动产，没有不动产就不行。 这样，过滤所有重要指标后，构建完整的决策树。 之后，无论哪个男青年在这里，都可以通过决策树很容易地预测这个人是否能结婚。
出个问题看看吧。 有个男生很浪漫，风度翩翩，但是没有独立的不动产，收入不固定，学历是本科，要结婚吗？
照片的收入、不动产、学历等都是特征，每个特征都是判断的节点，不能再往下延伸的是叶子的节点。 可再分割的被称为分支节点。
接下来，我们来看看决策树算法的进化历史。 其中包括主流的几种决策树算法。 顺便还可以知道这些决策树的区别。
1. ID3（Iterative Dichotomiser 3）
J.R.Quinlan在20世纪80年代提出了ID3算法，该算法为未来决策树算法的发展奠定了基础。 ID3使用香味浓的信息熵来计算特征的区分度。 选择熵减少程度最大的特征进行数据分类，也就是“最大熵增益”的原则。 其核心思想是选择信息增益作为分裂属性的依据。的缺点：该算法没有考虑如何处理连续属性、属性缺失及噪声等问题。
介绍与此相关的两个概念。
信息熵是衡量信息的方法，代表信息混乱的程度。 也就是说，信息越有序，信息熵就越低。 让我们列举一下列子。 火柴整齐地放在火柴盒里，熵值很低。 相反，熵值很高。 公式如下。
信息增益：分割数据集前后信息发生变化称为信息增益，信息增益越大，可靠性越高。
2. C4.5
J.R.Quinlan针对ID3算法的不足，设计了C4.5算法，引入了信息收益率的概念。 克服了ID3算法无法处理属性缺失和连续属性的问题，引入了优化决策树的剪枝方法，使算法更高效、适用性更高。随后，1996年Mehta.M等人提出了C4.5算法的改进算法SLIQ算法，该算法采用属性表、分类表、类直方图的策略解决了内存溢出问题。
同样说明信息收益率，在决策树分类问题中，是决策树的属性选择引起的分割前和分割后的信息差。
3. CART（Classification and Regression Tree）
Breiman.L.I等人于1984年提出了CART算法，即分类回归树算法。 CART算法使用基尼指数(Gini Index )代替信息熵，使用二叉树作为模型结构，因此需要在所有属性中找到最优的二元分割，而不是基于属性值的直接数据分割。 CART算法通过递归操作不断分割决策属性，同时利用验证数据优化树模型。CART中用于变量选择的杂质量是Gini指数，整体所包含的类别越杂乱，Gini指数就越大(与熵的概念非常相似)。
2000年Rastogi.R等人以CART算法为理论基础提出了PUB
LIC（A Decision Tree Classifier that Integrates Building and Pruning）算法，剪枝策略更加高效。当我们了解了决策树的大概情况之后，接下来就学习一下，如何构造决策树？
第一步：特征选择；第二步：决策树的生成；第三步：决策树的剪枝。
我们来着重介绍一下剪枝。
剪枝的目的：决策树是充分考虑了所有的数据点而生成的复杂树，有可能出现过拟合的情况，决策树越复杂，过拟合的程度会越高。考虑极端的情况，如果我们令所有的叶子节点都只含有一个数据点，那么我们能够保证所有的训练数据都能准确分类，但是很有可能得到高的预测误差，原因是将训练数据中所有的噪声数据都”准确划分”了，强化了噪声数据的作用。剪枝修剪分裂前后分类误差相差不大的子树，能够降低决策树的复杂度，降低过拟合出现的概率。
如何剪枝？
先剪枝：当熵减少的数量小于某一个阈值时，就停止分支的创建。这是一种贪心算法。后剪枝：先创建完整的决策树，然后再尝试消除多余的节点，也就是采用减枝的方法。注意事项：
决策树的生成对应模型的局部选择，决策树的剪枝对应于模型的全局选择。决策树的生成只考虑局部最优，决策树的剪枝则考虑全局最优。
说了这么多，我们来总结一下决策树算法的优、缺点，以便了解的更为深入。
优点：
决策树易于理解和实现.人们在通过解释后都有能力去理解决策树所表达的意义。计算复杂度不高，输出结果易于理解，数据缺失不敏感，可以处理不相关特征。缺点：
容易过拟合。对于各类别样本数量不一致的数据，在决策树当中信息增益的结果偏向于那些具有更多数值的特征。本文由 @燕然未勒 原创发布于人人都是产品经理。未经许可，禁止转载。
题图来自 Unsplash ，基于 CC0 协议。