五，专著研读（第八章）

分类的目的
通过构建分类模型来预测一些数据元组的类标签。
分类的过程
决策树（Decision Tree）：是有监督学习的一种算法，并且是一种基本的分类与回归的方法。
两种：分类树，回归树。
决策树构建
- 特征选择
  如何选择最优特征来划分：决策树的分支节点所包含的样本尽可能属于同一类，也就是节点的纯度越来越高。
  在实际中我们衡量的常常是不纯度。度量不纯度的指标有：商，增益率，基尼系数。
  熵定义为信息的期望值。在信息论与概率统计中，熵是表示随机变量不确定性的度量。
- 决策树的构造
  - 构造根节点，根据属性选择性度量来选择合适的属性作为根节点。
  - 根据节点的属性（离散，连续，二值）进行分枝，每个分枝代表元组在该属性下可能满足的条件。
  - 判断经过分枝后元组类别是否单一，分支节点所包含的样本尽可能属于同一类，也就是节点的纯度越来越高。
  - 树停止生长。
- 决策树的剪枝
过拟合现象
决策树生成算法递归的产生决策树，直到不能继续下去为止。这样产生的树往往对训练数据的分类很准，对未知的测试数据却没那么准确，出现过拟合现象。过拟合的原因在于学习时过多的考虑如何提高对训练数据的正确分类，构建过于复杂的决策树。
解决过拟合的办法是考虑决策树的复杂度，对已经生成的决策树进行简化，也就是剪枝处理。
ID3算法
构建决策树的算法（ID3，C4.5和CART）
ID3算法的核心是在决策树各个节点上对应信息增益准则选择特征，递归构建决策树。
具体方法是：从根节点开始，对节点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征，由该特征的不同取值建立子节点；在对子节点递归调用以上那个方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止。最后得到一个决策树。
递归结束的条件：程序遍历完所有特征列，或者每个分支下的所有实例都具有相同的分类。如果所有的实例具有相同的分类，则得到一个叶节点。任何到达叶节点的数据必然属于叶节点的分类。
C4.5
C4.5使用信息增益率作为属性选择器。
CART决策树
- 基尼指数
  CART决策树使用基尼指数作为（Gini index）作为属性选择度量，用来衡量数据分区或训练元组的不纯度。
- 构造过程
  计算每个属性每个可能的二元划分的基尼系数
  选择最小基尼系数划分的属性作为根节点
  二元划分递归构造字数