5.1 决策树模型与学习
5.1.1 决策树模型
决策树：结点（内部结点和叶结点）和有向边。内部结点表示一个特征或属性，叶节点表示一个类。
5.1.2 决策树与if-then规则
决策树转换成if-then规则的过程：由决策树的根结点到叶结点的每一条路径构建一条规则；路径上内部结点的特征对应着规则的条件，而叶节点的类对应着规则的结论。
决策树的路径或其对应的if-then规则集合具有一个重要的性质：互斥且完备。
5.1.3 决策树与条件概率分布
决策树还表示给定特征条件下类的条件概率分布。这一条件概率分布定义在特征空间的一个划分上。将特征空间划分为互不相交的单元或区域，并在每个单元定义一个类的概率分布就构成了一个条件概率分布。
5.1.4 决策树学习
本质：从训练数据集中归纳出一组分类规则
损失函数：正则化的极大似然函数
策略：以损失函数为目标函数的最小化
决策树学习算法：特征选择、决策树的生成和决策树的剪枝。决策树的生成对应于模型的局部选择，只考虑局部最优；决策树的剪枝对应于模型的全局选择，考虑全局最优。
5.2 特征选择
5.2.1 特征选择问题
选取对训练数据具有分类能力的特征，通常的准则是信息增益或信息增益比。
5.2.2 信息增益
熵：随机变量不确定性
熵只依赖于X的分布，而与X的取值无关。熵越大，随机变量的不确定性就越大。
设有随机变量(X,Y)条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。定义为X给定条件下Y的条件概率分布的熵对X的数学期望
当熵和条件熵中的概率由数据估计得到时，所对应的熵与条件熵分别称为经验熵和经验条件熵。
信息增益表示得知特征X的信息而使得类Y的信息不确定性减少的程度。
信息增益：特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即
熵H(Y)与条件熵H(Y|X)之差称为互信息。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
根据信息增益准则的特征选择方法：对训练数据集D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。
信息增益算法：
输入：训练数据集D和特征A
输出：特征A对训练数据集D的信息增益g(D,A)
5.2.3 信息增益比
以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比可以矫正。
信息增益比：
5.3 决策树的生成
5.3.1 ID3算法
核心：在决策树各个结点上应用信息增益准则选择特征，递归的构建决策树。
ID3算法只有树的生成，所以容易过拟合。
5.3.2 C4.5的生成算法
用信息增益比来选特征
5.4 决策树的剪枝
过拟合原因：学习时过多的考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。
决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。
C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，|T|表示模型复杂度，α>=0控制两者之间的影响。
剪枝，当α确定时，选择损失函数最小的模型，即损失函数最小的子树。
5.5 CART算法
分类与回归树（classification and regression tree,CART）
算法：
①决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大
②决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，用损失函数最小作为剪枝的标准。
5.5.1 CART生成
对回归树用平方误差最小化准则，对分类树用基尼指数(Gini index)最小化准则，进行特征选择，生成二叉树
1. 回归树的生成
2. 分类树的生成
5.5.2 CART剪枝
①从生成算法产生的决策树T0底端开始不断剪枝，直到T0的根节点，形成一个子树序列{T0,T1,...,Tn}
②通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树
