图片解析什么是决策树算法。
什么是决策树算法
所谓决策树，是一种树，一种依托于策略抉择而建立起来的树。据维基百科上的介绍：机器学习中，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。
从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。
下面举两个浅显易懂的例子：
第一个例子引自codinglabs.org上：通俗来说，决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：
女儿：多大年纪了？
母亲：26。
女儿：长的帅不帅？
母亲：挺帅的。
女儿：收入高不？
母亲：不算很高，中等情况。
女儿：是公务员不？
母亲：是，在税务局上班呢。
女儿：那好，我去见见。
这个女孩的决策过程就是典型的分类树决策。相当于通过年龄、长相、收入和是否公务员对将男人分为两个类别：见和不见。假设这个女孩对男人的要求是：30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员，那么这个可以用下图表示女孩的决策逻辑：
也就是说，决策树的简单策略就是，好比公司招聘面试过程中筛选一个人的简历，如果你的条件相当好比如说清华博士毕业，那么二话不说，直接叫过来面试，如果非重点大学毕业，但实际项目经验丰富，那么也要考虑叫过来面试一下，即所谓具体情况具体分析、决策。
第二个例子来自Tom M.Mitchell著的机器学习一书：
小王的目的是通过下周天气预报寻找什么时候人们会打高尔夫，他了解人们决定是否打球的原因最主要取决于天气情况。而天气状况有晴，云和雨；气温用华氏温度表示；相对湿度用百分比；还有有无风。如此，我们便可以构造一棵决策树，如下：
基本的决策树学习算法
ID3算法
从信息论知识中我们直到，期望信息越小，信息增益越大，从而纯度越高。所以ID3算法的核心思想就是以信息增益度量属性选择，选择分裂后信息增益最大的属性进行分裂。所以，ID3的思想便是：1、自顶向下构造决策树；2、从“哪一个属性将在树的根节点被测试”开始；3、使用统计测试来确定每一个实例属性单独分类训练样例的能力。
ID3的过程
- 分类能力最好的属性被选作树的根节点
- 根节点的每个可能值产生一个分支
- 训练样例排列到适当的分支
- 重复上面的过程
下图所示即是用于学习布尔函数的ID3算法概要：
最佳分类属性
信息增益
信息增益(Information Gain)是用来衡量给定的属性区分训练样例的能力，而ID3算法在增长树的每一步使用信息增益从候选属性中选择属性。
我们用熵度量样例的均一性，熵刻画了任意样例集的纯度，如果给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类的熵为：
上述公式中，p+代表正样例，比如去打羽毛球，而p-则代表反样例，不去打球。
信息论中对熵的一种解释，熵确定了要编码集合S中任意成员的分类所需要的最少二进制位数，更一般地，如果目标属性具有c个不同的值，那么S相对于c个状态的分类的熵定义为：
根据上述这个公式，我们可以得到：S的所有成员属于同一类，Entropy(S)=0；S的正反样例数量相等，Entropy(S)=1；S的正反样例数量不等，熵介于0，1之间，如下图所示：
信息增益度量期望的熵降低
属性的信息增益，由于使用这个属性分割样例而导致的期望熵降低，Gain(S,A)是在知道属性A的值后可以节省的二进制位数，Gain(S,A)的计算公式如下：
运用在本文开头举得第二个根据天气情况是否决定打羽毛球的例子上，得到的最佳分类属性如下图所示：
在上图中，计算了两个不同属性：湿度(humidity)和风力(wind)的信息增益，最终humidity这种分类的信息增益0.151>wind增益的0.048。说白了，就是在星期六上午是否适合打网球的问题诀策中，采取humidity较wind作为分类属性更佳，决策树由此而来。
ID3算法决策树的形成
OK，下图为ID3算法第一步后形成的部分决策树。这样综合起来看，就容易理解多了。1、overcast样例必为正，所以为叶子结点，总为yes；2、ID3无回溯，局部最优，而非全局最优，还有另一种树后修剪决策树。下图是ID3算法第一步后形成的部分决策树：
本文参考：
- http://www.cnblogs.com/leoo2sk/archive/2010/09/19/decision-tree.html；
- Mitchell, Tom M.Machine Learning. McGraw-Hill, 1997.
- http://zh.wikipedia.org/wiki/%E5%86%B3%E7%AD%96%E6%A0%91。