1. 决策树定义

决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。

2. 决策树优缺点

决策树是一种简单但是广泛使用的分类器。通过训练数据构建决策树，可以高效的对未知的数据进行分类。

  • 决策数有两大优点：
    • 1、决策树模型可读性好，具有描述性，有助于人工分析
    • 2、效率高，决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度。
  • 决策树缺点：可能会产生过度匹配问题

3. 构造决策树

3.1 构造决策树算法

决策树算法有ID3算法、C4.5、CART等，以ID3为例:

  • 对于当前数据集，计算不同属性(特征)的信息增益，并从中取出信息增益最大的属性(特征)R
  • 用R作为划分root节点的方法，把R属性可能对应的不同值归为不同的子集
  • 对每个子集，递归调用建树算法
  • 若子集只含有单个属性，则分支为叶子节点，(即递归函数的停止条件)，判断其属性值并标上相应的符号，然后返回调用处

3.2 度量数据集无序程度

构造决策树需要解决的第一个问题就是，当前数据集上哪个特征在划分数据分类时起决定性作用。如果按照A特征划分之后已经完全正确的将数据集分类了，那么A特征就足够好，也可以说划分后的数据集无序程度下降了，即划分数据集的最大原则是：将无序的数据变得更加有序。而度量数据集无序程度的方法有熵(entropy)和基尼不纯度(Gini impurity)等，此处使用熵。
关于熵，熵定义为信息的期望值，而对于符号\(x_i\)的信息定义为\(l(x_i)=-\log_2p(x_i)\)，为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值，通过以下公式得到: \(H=-\sum_{i=1}^np(x_i)\log_2p(x_i)\)
熵越高，数据集的无序程度越大，即混合的数据越多

通过熵度量划分数据集的信息增益，判断按照哪个属性(特征)划分数据集为最好的划分方式

3.3 递归构建决策树

递归结束的条件是：遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。如果所有实例都具有相同的分类，则得到一个叶子节点或者终止块，任何到达叶子节点的数据必然属于叶子节点的分类

4. Matplotlib注解

以上构造的决策树为文本描述方式，不够直观，虽然实际应用中大多就是如此，但本着学习的态度，且数据集也很小，使用matplotlib注解直观形象的作出一个决策树，不详述

5. 测试算法

决策树构造完毕后，需要使用它来执行分类

6. 决策树的存储

决策树的构造过程十分耗时，如果每次使用决策树都需要先构造，会浪费计算时间，可以将训练好的决策树存储起来，需要使用的时候读取出来

7. 过渡拟合

这是ID3算法的不足之处，其概念和优化方法可以参见http://www.cnblogs.com/bourneli/archive/2013/03/15/2961568.html

8. 应用示例

Machine Learning in Action 书中使用了隐形眼镜示例，数据来源为UCI数据库，并进行了相应的改造
代码可见此处