决策树实际上是特征选择，决策树的生成和剪枝过程
5.1决策树模型与学习
5.1.1 决策树模型
决策树模型定义分类鞠策书模型是一种描述对实例进行分类的树形结构，决策树由节点和有向边组成，节点有两种类型：内部节点和叶节点。内部节点标识一个特征或属性，叶节点标识一个类。
5.2特征选择
选取对训练数据有分类能力的特征，从而提高决策树的学习效率。
如果利用一个特征进行分类的结果和随机分类结果没有很大差别，则这个特征没有分类能力。
特征选择的准则是信息增益或信息增益比
1.1信息增益
熵（entropy）是标识随机变量不确定性的度量。设X是一个取有限个值的随机离散变量，概率分布为：
P(X = xi) = pi i=1,2,...n
随机变量X的熵为：
H(X) = -∑pi*logpi
- 当对数以2为底或者e为底，这是熵的单位分别称作比特(bit)和纳特(nat)
由定义可知，熵和X的分布有关，和X的取值无关，所以也可以将X的熵记作H(p)，即
H(p) = -∑pi*logpi
熵越大，随机变量的不确定性就越大，从定义可验证
0 <= H(p) <= logn
条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性，随机变量X给定的条件下随机变量Y的条件熵(conditional entropy) H(Y|X)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望
H (Y|X) = ∑pi*H(Y|X = xi)
这里，pi = P(X = xi), i = 1, 2, ...n
当条件熵中的概率有数据估计（特别是最大似然估计）得到时，所对应的熵与条件熵分别称为经验熵（empirical entropy） 和经验条件熵（empirical conditional entropy）.此时，如果有0概率，令0log0=0.
信息增益（information gain）表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。
信息增益定义 特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即
g(D,A) = H(D) - H(D|A)
一般的，熵H(Y)与条件熵H(Y|X)之差称为互信息（mutual information），决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
信息增益的算法
输入：训练数据集D和特征
输出：特征A对训练数据集D的信息增益g（D，A）
-
（1）计算数据集D的经验熵H(D)
H(D) = ∑pi*logpi H(D) = ∑|Ck|/|D|*log|Ck|/|D| -
（2）计算特征A对数据集D的经验条件熵H(D,A)
H(D|A) = ∑|Di|/|D|*H(D) -
（3）计算信息增益
g(D,A) = H(D) - H(D|A)
根据信息增益选择最优的特征
-
（1）首先计算经验熵H(D)
H(D) = -∑pi*logpi -
（2）计算各特征对数据集D的信息增益
g(D,A) = H(D) - H(D|A)
信息增益比
信息增益值的大小是相对于训练数据集而言的，并没有绝对意义，在分类问题困难时，也就是说在训练数据集的经验熵大的时候，信息增益值会偏大，反之信息增益值会偏小，使用信息增益比（information gain ratio）可以对这一问题进行校正，这是特征选择的另一个准则。
信息增益比定义特征A对训练数据集D的信息增益比gr(D,A)定义为其信息增益g(D，A)与训练数据集D的经验熵H(D)之比：
gr(D,A) = g(D，A) / H(D)
5.3决策树的生成
5.3.1 ID3算法
ID3算法的核心是在鞠策书各个节点上应用信息增益准则选择特征，递归的构建决策树，具体方法是：从根节点开始，对节点计算所有可能得特征的信息增益，选择信息增益最大的特征作为节点的特征，由该特征的不同取值建立子节点；再对自己点递归的调用以上方法，构建决策树；直到所有的特征的信息增益均很小或没有特征可以选择位置。最后得到一个决策树。ID3相当于用极大似然法进行概率模型的选择
ID3算法
输入：训练数据集D，特征集A，阈值e；
输出：决策树T
- （1）若D中所有实例属于同一类Ck，则T为单节点数，并将Ck作为该节点的类标记，返回T
- （2）若A=∅，则T为单节点树，并将D中实例数最大的类Ck作为该节点的类标记，返回T
- （3）否则，按算法5.1计算A中各特征对D的信息增益，选择信息增益最大得到特征Ag；
- （4）如果Ag的信息增益小于阈值e，则置T为单节点树，并将D中实力书最大的类Ck作为该节点的类标记，返回T；
- （5）否则，对Ag的每一可能值a1，依Ag = ai 将D分割为若干非空子集Di，将Di中实例数最大的类作为标记，构建子节点，由节点及其子节点构成树T，返回T；
- （6）对第i个子节点，以Di为训练集，以A-{Ag}为特征集，递归的调用步骤（1）-（5），得到子树Ti，返回Ti
C4.5的生成算法
C4.5与ID3算法相似，C4.5在生成过程中，用信息增益比来选择特征。可以平衡经验熵偏大或者偏小导致信息增益偏大偏小的问题。
5.4 决策树的剪枝
决策树生成算法递归的产生决策树，直到不能继续下去为止，这样产生的树往往对训练数据的分类很准确，但对于未知的测试数据的分类确没有那么准确，即出现过拟合现象。过拟合的原因在于学习时过多的考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。解决这个问题的办法是考虑决策树的复杂度，对已生成的决策树进行简化。
在决策树学习中将已生成的树进行简化的过程称为剪枝（pruning）。
降低模型复杂度，从而提升模型在未知数据上的预测准确率
5.4.1决策树的剪枝算法
决策树的剪枝往往通过极小化决策树整体的损失函数（loss function）或代价函数（cost function）来实现，设树T的叶节点个数为|T|，t是树T的叶节点，该叶节点有Ni个样本点，其中k类的样本点有Ntk个，k=1,2....，K，H(T)为叶节点t上的经验熵，a>=0为参数，决策树的损失函数为
Ca(T) = ∑NtHt(T) + a|T|
其中经验熵为
Ht(T) = -∑Ntk/Nt * logNtk/Nt
损失函数
Ca(T) = C(T) + a|T|
C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，|T|表示模型的复杂度，参数a>=0控制两者之间的影响，较大的a促使选择较简单的模型（树），较小的a促使选择较复杂的模型，a=0意味着只考虑模型与训练数据的拟合程度，不考虑模型复杂度。损失函数正好表示了对两者的平衡。
决策树生成只考虑了通过提高信息增益对训练数据进行更好的拟合，而决策树剪枝通过优化损失函数还考虑了减小模型复杂度，决策树生成学习局部的模型，而决策树剪枝学习整体的模型。
5.5 CART算法
CART算法有两个组成：
- 决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；
- 决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。
