今天我们再来看一个新的算法---决策树（Decision Tree）。
决策树呢，在机器学习的算法里也是比较常见的一种分类与回归算法了。决策树模型是树状图结构，在分类问题中，表示基于特征对实例进行分类的过程。其实从简单角度来讲就是两个选择不是“是”就是“否”。下面我们从简单的图画中看一下什么是决策树吧！
从上面这个图中我们可以看出来决策树就是这么一层一层选择的过程，当所有的条件都满足后，就是我们想要的结果了。
通过这样一张图，现在我们来官方的解释一下决策树模型的定义吧！
分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型：内部节点和叶节点，内部节点表示一个特征或属性，叶节点表示一个类。
分类的时候，从根节点开始，对实例的某一个特征进行测试，根据测试结果，将实例分配到其子结点；此时，每一个子结点对应着该特征的一个取值。如此递归向下移动，直至达到叶结点，最后将实例分配到叶结点的类中。
就比如说我们现在要评判一个学生是不是优秀学生肯定需要从多个角度去评判，利用上图的结构，我们把条件先列举出来：
是否旷过课，是否挂过科，作业提交率，平均绩点是否大于3.8
（以上是个人观点，不代表优秀学生就是此条件，只是理解需要而已）
以上的决策树，方形的节点就是我们的判断条件，圆圈就是我们的决策结果了，横竖箭头表示判断条件不同的时候我们的决策路径，竖着的箭头就是我们的在判定优秀学生的决策过程了。
上面的这个过程是不是和我们python中的嵌套if特别像，先要满足第一个条件才能进来看第二个条件满不满足，如果不满足就直接pass了。这样的if和决策树都具备一个共同的特征：完备且互斥（这句话的意思就是每个实例都肯定有与之对应的条件，有且只有一条）。由决策树的根结点到叶结点的每一条路径构建一条规则；路径上的内部结点的特征对应着规则的条件，而叶结点对应着分类的结论。
对于决策树是如何学习的现在该了解一下了：
决策树学习算法包含特征选择，生成决策树，调整决策树（适当的剪枝）。决策树的学习算法是递归选择最优特征，利用最优特征对当前数据集进行分割。在开始时，构建你的根节点，选择最优特征，该特征有几种值就分割为几个子集，每个子集分别都递归调用此方法，返回结点，返回的结点就是上一层的子结点。直到所有特征都已经用完，或者数据集只有一维特征为止。
知道了学习原理之后，我们的问题也就来了，那就是如何选择特征对吧？
特征选择效果就是期望对目标数据产生较好的分类。越是能将目标数据分成我们想要的类别就是我们想要的特征，这可以提高决策树的学习效率。（如果存在一个特征，用它进行分类，所产生的结果与随机分类的结果没什么差别，这就是傻子特征<我瞎说的>，这种特征是不具备分类能力的）。下面我们举个例子：
我们现在想对一堆书进行分类，这需要选取特征，如果我们选取的特征是文字书或漫画书为特征，这样我们能很明确的把书分成两类，对于最后我要找到结果肯定是有帮助的，但是如果我们要一这个数有多厚进行分类，这很显然就傻掉了，这就是一个傻子特征<我瞎说的>，可以选择忽略这种特征了。
Ok，下面我们进入正题，既然是要解决特征选择的问题，那么这边我们就不得不引入一些理论性的概念了：
信息熵 & 信息增益
熵（entropy）： 熵指的是体系的混乱的程度，在不同的学科中也有引申出的更为具体的定义，是各领域十分重要的参量。
那使用代码如何实现？
信息论（information theory）中的熵（香农熵）： 是一种信息的度量方式，表示信息的混乱程度，也就是说：信息越有序，信息熵越低。例如：水是液态的时候水是很有序的排在一起，熵会比较低，当水变成水蒸气散到空气中的时候，水分子就比较乱了，它的熵就很高。
python代码实现：
信息增益（information gain）： 在划分数据集前后信息发生的变化称为信息增益。
根据信息增益准则的特征选择方法是：对训练数据集（或子集）计算其每个特征的信息增益，选择信息增益最大的特征。
计算信息增益的算法如下：
输入：训练数据集和特征；
输出：特征对训练数据集的信息增益.
(1)计算数据集的经验熵
(2)计算特征对数据集的经验条件熵
(3)计算信息增益
python实现：
那我们如何来构建一个决策树呢？
决策树说简单一点不就是if else嘛，所以我们可以定义一个方法来构建决策树：
这正是因为这样的特性也是它各具备优缺点，优点是计算复杂度不高，输出结果易理解，对于有缺失数据的时候照样可以运行，缺点呢就是很容易过拟合。
了解了决策树后，现在我们来准备开发了!
首先把思路整理一下，对于决策树，我们要做什么?
收集数据：可以使用任何方法。
准备数据：树构造算法 (这里使用的是ID3算法，只适用于标称型数据，这就是为什么数值型数据必须离散化。 还有其他的树构造算法，比如CART)
分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期。
训练算法：构造树的数据结构。
测试算法：使用训练好的树计算错误率。
使用算法：此步骤可以适用于任何监督学习任务，而使用决策树可以更好地理解数据的内在含义。
现在我们利用决策树来做一件事，我现在有一群动物，我想要把他们进行分类，我们要区分他们是不是鱼类：
判断特征：A在水中是否可以生存 B是否有鳍
首先我们创建一个数据集：
此处，由于我们输入的数据本身就是离散化数据，所以暂时就不需要构造算法了。
下面分析数据：
可以使用任何方法，构造树完成之后，我们可以将树画出来。
计算给定数据集的香农熵：
现在按照给定特征划分数据集
将指定特征的特征值等于 value 的行剩下列作为子数据集。
通过遍历dataSet数据集，求出index对应的colnum列的值为value的行。
一局index列进行分类，如果index列的数据等于value，就要将 index 划分到我们创建的新的数据集中。
函数的参数：dataSet 是待划分的数据集， index 表示每一行的index列 ，是划分数据集的特征， value 表示index列对应的value值是需要返回的特征的值。
我们现在要选择最好的数据集划分方式：
有了最好的特征，现在我们就来构造一个决策树的数据结构吧
定义好决策树，也有了最优特征，那现在我们做什么呢？
当然是开始分类啦！
三个需要传入的参数
inputTree 决策树模型， featLabels Feature标签对应的名称， testVec 测试输入的数据
运行结果：
代码地址：
