写在前面的话：哈喽，大家早安、午安、晚安喽，欢迎大家指点，也希望我的内容可以温暖、帮助同在学习路上的人们~
正文开始~~
再次申明：本文的理论知识来自Peter Harrington的《机器学习实战》和李航的《统计学习方法》，非常感谢这些优秀人物和优秀书籍
决策树(decision tree)算法简介：决策树算法思想主要来源于由Quinlan在1986年提出的IID3算法和1993年提出的C4.5算法，以及由Breiman等人在1984年提出的CART(分类回归决策树)。决策树算法是一种基本的分类与回归算法。决策树学习通常包括3个步骤：特征选择、决策树的生成和决策树的修剪。本文仅讨论用于分类的决策树。
分类决策树工作原理：分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点(node)和有向边(directed node)组成。结点分两类：内部结点(internal tree)和叶结点(leaf node)。内部结点表示一个特征或属性，叶结点表示一个类。分类决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。开始，构建根结点，将所有训练数据都放在根结点。选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。如果这些子集已经能够被基本正确分类，那么构建叶结点，并将这些子集分到所对应的叶结点中去；如果还有子集不能被基本正确分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的结点。如此递归地进行下去，直至所有训练数据子集被基本正确分类，或者没有合适的特征为止。最后每个子集都被分到叶结点上，即都有了明确的类，最终生成了一颗决策树。以上方法生成的决策树可能对训练数据有很好的分类能力，但对未知的测试数据却并未有很好的分类能力，可能发生过拟合，因此需要对生成的决策树自下而上剪枝，将树变得简单，从而使他具有更好的泛化能力。
分类决策树算法的实现：
流程：1）收集数据：可以使用任何方法；2）准备数据：构造算法只适用于标称型数据，因此数值型数据必须离散化；3）分析数据：可以使用任何方法，构造树完成之后，应该检查图形是否符合预期；4）训练算法：构造树的数据结构；5）测试算法：使用经验树计算错误率；6）使用算法：此步骤可以适用于任何监督学习算法,而使用决策树可以更好地理解数据的内在含义。
特征选择：在上述第3）步中，决策树通过信息增益来选择特征，进而构建决策树。给定训练数据集D和特征A，经验熵H(D)表示对数据集D进行分类的不确定性。而经验条件熵H(D|A)表示在特征A给定的条件下对数据集D进行分类的不确定性。那么它们的差，即信息增益，就表示由于特征A而使得对数据集D的分类的不确定性减少的程度。显然，对于数据集D而言，信息增益依赖于特征，不同的特征往往具有不同的信息增益。信息增益大的特征具有更强的分类能力。
分类决策树的Python实现
1）利用香农熵公式计算整个数据集的信息熵，代码见图1
2）基于某一特征，会划分数据集，代码见图2
3）通过计算信息增益，找让信息增益最大的特征，也就是最好的分类特征，代码见图3
4）逐步递归，构建决策树
递归的结束条件：1）程序遍历完所有划分数据集的属性。此时存在的一种情况是数据集以及处理了所有属性，但是类标签依然不是唯一的，此时需要决定改如何定义该叶结点，一般采用多数表决的方法；2）每个分支下的所有实例都具有相同的分类。如果所有实例具有相同的分类，则得到一个叶子节点或者终止块。任何到达叶子节点的数据必然属于叶子节点的分类。
5）基于Matplotlib模块来绘制决策树。其中，Matplotlib的一些绘图操作可以查看Matplotlib官方文档、Matplotlib博客等。
好啦，以上基本就是基于Python的决策树实现算法，感觉自己还是不熟悉这块儿，希望得到大神指导或者大家分享一些棒棒哒的学习资源哈，提前谢谢大家啦~~
同样，接下来将基于scikit-learn的相关模型来实现决策树算法，敬请期待哈~~
