决策树学习是一种逼近离散值目标函数的方法，在这种方法中学习到的函数被表示为一棵决策树。
表示法：把实例从根节点排列到某个叶子节点来分类实例，叶子节点即为实例所属的分类。树上的每一个节点指定了对实例的某个属性(attribute)的测试，并且该节点的每一个后缀分支对应于该属性的一个可能值。分类实例的方法是从这棵树的根节点开始，测试这个节点指定的属性，然后按照给定实例的该属性值对应的树枝向下移动。然后这个过程在以新节点为根的子树上重复。
上图是一棵学习到的决策树，根据天气情况分类“星期六上午是否适合打网球”。
决策树的适用问题：
- 实例是由“属性-值”对表示的
- 目标函数具有离散的输出值
- 可能需要析取的描述
- 训练数据可以包含错误
- 训练数据可以包含缺少属性值的实例
核心问题是将样例分类到各可能的离散值对应的类别(category)中，因此常被称为分类问题(classification problem)。
基本的决策树学习算法：
ID3算法：采用自顶向下的贪婪搜索遍历可能的决策树空间。
训练过程：通过自顶向下构造决策树来进行学习，构造过程是从“哪一个属性将在树的根节点被测试？”这个问题开始。使用统计测试来确定每一个实例属性单独分类训练样例的能力，分类最好的属性将被选作树的根节点，然后为根节点属性的每个值产生一个分支，重复整个过程。
算法概要：
但是，哪个属性是最佳的分类属性呢？
这就需要用到“奥坎姆剃刀”原则：优先选择拟合数据的最简单假设。
决策树遵照这个原则：较短的树比较长的优先。
那么怎么确定一个属性能够较好的划分训练数据呢？这就用到了信息论(information theory)。
信息就是不确定性的减少，并获取新的知识。
信息是确定性的增加—-逆Shannon信息定义。
一个事件的信息量与它出现的概率最为相关。
如果一个确定发生的事件发生了，那么确定性没有任何变化，所以得到的信息为0。而如果小概率的事件发生了，那么将得到比可能发生的事情更多的信息量。所以信息量与事件发生的概率成反比。
熵确定了要编码的集合S中任意成员的分类所需的最小二进制位数。
用熵度量样例的均一性：给定包含关于某个目标概念的正反样例集S，难么S相对这个布尔型分类的熵为：
Entropy(S) = -p+ log2p+ - p- log2p-
其中，p+是S中正例的比例，p-是S中反例的比例。
属性分类训练数据的能力的度量标准：信息增益(information gain),一个属性的信息增益是由于使用这个属性分隔样例而导致期望的熵降低，即，下式：
Values(A)是属性A所有可能值的集合，Sv是属性A的值为v的子集。
信息增益是ID3算法增长树的每一步中选取最佳拟合属性的度量标准。
决策树学习的常见问题：
- 确定决策树增长的长度
- 处理连续值的属性
- 选择一个适当的属性筛选度量标准
- 处理属性值不完整的训练数据
- 处理不同代价的属性
- 提高计算效率
避免过拟合
过拟合：给定一个假设空间H，一个假设h属于H，如果存在其他的假设h‘属于H，使得在训练样例上h的错误率比h‘小，但在整个实际分布上h‘的错误率比h‘小，那么就说H过度拟合(overfit)训练数据。
解决过拟合：
- 及早停止树增长，在ID3算法完美分类训练数据之前就停止树的增长
- 后修剪法(post-prune)，即允许树过度拟合数据，然后对着个树进行后修剪。
机器学习笔记——决策树学习,布布扣,bubuko.com
机器学习笔记——决策树学习
原文：http://blog.csdn.net/laozhaokun/article/details/24552559
