基本流程

决策树是一种常用的机器学习方法，过程类似于树状结构每一层通过对属性进行决策来进行分类。

结构主要有：根节点（初始的所有数据集），内部节点（初步决策结果），叶节点（最终决策结果），路径（判定决策过程）。

决策树学习基本算法：

输入：训练集D,属性集A={a1,a2,...,ad}
过程：函数TreeGenerate(D,A)
  生成节点node:
  if D中样本全属于统一类别C then
    将node标记为C类叶节点;return
  end if 
  if A=空集 or D中样本在A上取值相同 then
    将node标记为叶节点，类别标记为D中最多的类;return
  end if
  从A中选择最优划分属性a*;
  for a* 的每一个取值a*v do
    为node生成一个分支;另Dv表示D在a*上取值为a*v的样本子集;
    if Dv为空 then
      将分支节点标记为叶节点，类别标记为D中最多的类;return
    else
      以TreeGenerate(Dv,A\{a*})为分支节点
    end if
  end for
输出：以node为根节点的一颗决策树

这个是一个递归过程，其中有三种情况导致递归返回：

当前节点所有样本属于同一类，不用再划分
当前节点属性集空，不能再划分（当前节点的后验分布）
当前节点样本集为空，不能再划分（将父节点的分布当成当前节点的先验分布）

划分选择

什么样的划分属性是最优的？划分后的结点中样本的纯度因该是比划分前高的。因此，引入了信息熵即度量样本集合纯度的指标，样本集合 $D$ 的信息熵定义为：
$Ent(D)=-\sum^{|y|}_{k=1}p_k\log_2p_k$
其中 $p_k$ 为第 $k$ 类样本所占的比例。信息熵的值越小， $D$ 的纯度越高。

当根据某一属性 $a=\lbrace a^1,a^2,\ldots,a^V\rbrace$ ，对 $D$ 进行划分后，形成的多个子结点的信息熵就是 $Ent(D^v)$ 。为了比较前后的信息熵变化，定义信息增益：
$Gain(D,a)=Ent(D)-\sum^V_{v=1}\frac{|D^v|}{|D|}Ent(D^v)$
其中 $\frac{|D^v|}{|D|}$ 为每个分支点的权重。信息增益越大，就表明通过属性 $a$ 划分得到的子结点的纯度提升越大。

同时注意到一个问题，信息增益作为度量的时候，对于取值数目多的属性具有偏爱性，比如样本序号（1，2，3，4，5），如果作为一种划分属性，得到的结果纯度达到 $100\%$ ，但是却不具有对新样本的预测能力。因此引入增益率:
$Gain_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$
其中：
$IV(a)=-\sum^V_{v=1}\frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|}$
但是，增益率对于取值数目少的属性具有偏爱性，因此长使用一种启发式：先挑选信息增益高于平均水平的属性，然后在选取增益率最高的属性。

CART决策树是一种著名的决策树学习算法，分类和回归任务都可用。它使用“基尼指数”来选择划分属性。D的基尼值度量为：
$Gini(D)=\sum^{|y|}{k=1}\sum_{k' \not= k}p_kp'_k$
$=1-\sum^{|y|}_{k=1}p_k^2$
指从D中随机抽取两个样本不同类的概率，越小，D的纯度越高。
属性 $a$ 的基尼指数定义为：
$Gini_index(D,a)=\sum_{v=1}^V \frac{|D^v|}{|D|}Gini(D^v)$
使得划分后基尼指数最小的属性为最优属性。

剪枝处理

剪枝指对决策树进行枝干的修剪，为了应对过拟合现象。分为以下两种：

预剪枝
预剪枝是在决策树形成的过程中，根据结点划分是否提升决策树整体的泛化性能来决定。这种方法计算量比较小，但是因为其贪婪特性，可能导致欠拟合（一些后续划分提升泛化性能的枝，会因为初始划分不能提升泛化性能而扼杀）。
后剪枝
后剪枝是在决策树形成后，自下而上，根据非叶结点替换为叶节点是否提高决策树泛化性能来决定是否替换。这种方法计算量比较大，但是不会欠拟合，而且多数情况比预剪枝的泛化性能要强。

连续与缺失值

连续值处理
对于给定的数据集D，连续属性 $a=\lbrace a^1,a^2, \dots,a^n\rbrace$ ，并不能像离散指那样直接按照取值进行划分。因此，将连续属性的所有取值进行，从小到大的排序，然后 $a^i,a^{i+1}$ 之间任意的取值划分效果相同，所以候选划分点集合为：
$T_a=\lbrace \frac{a^i+a^{i+1}}2|1\leq i \leq n-1\rbrace$
然后就可以按照离散属性值一样来考察这些划分点，选取最优划分点。例如：
$Gain(D,a)=max_{t \in T_a} Gain(D,a,t)$
$=max_{t \in T_a} Ent(D)-\sum_{\lambda \in \lbrace -,+\rbrace}\frac{|D^{\lambda}_t|}{|D|}Ent{D_t^\lambda}$
注意，与离散值不同的是，连续属性在划分后的后代结点还可继续划分。
缺失值处理
给定数据集 $D$ ，缺失属性 $a$ ， $D'$ 表示属性 $a$ 上没有缺失值的样本子集， $D'^v$ 表示 $D'$ 在属性a上不同取值的样本子集， $D'_k$ 表示 $D'$ 中的第几类样本。
问题主要是在存在属性值缺失的情况下，选择划分属性，并且进行划分。先要进行准备工作：
首先，每个样本初始化权重 $w_x$ （取值1），然后定义：
$\rho=\frac{\sum_{x \in D'}w_x}{\sum_{x \in D}w_x}$
$p'^k=\frac{\sum_{x \in D'_k}w_x}{\sum_{x \in D'}w_x}$
$r'_v=\frac{\sum_{x \in D'^v}w_x}{\sum_{x \in D'}w_x}$
根据这些式子就可以将信息增益推广：
$Gain(D,a)=\rho \times Gain(D',a)$
$=\rho \times(Ent(D')-\sum^V_{v=1}r'_vEnt(D'^v))$
其中：
$Ent(D')=-\sum_{k=1}^{|y|}p'_k \log_2 p'_k$
划分的过程中，样本在属性 $a$ 上的取值已知，直接划分对应的子结点，权重保持 $w_x$ ，如果未知，同时划入所有子结点，权重调整为 $r'_v \cdot x_x$ 。

多变量决策树

多变量决策树在划分的时候不再是针对一个属性，而是针对多个属性的组合。

我们把每个属性看做一个坐标轴， $d$ 个属性的样本就对应了 $d$ 维空间中的一个点，分类就相当与寻找一个边界将点划分开。决策树的划分有个特点就是，形成的划分界面是多段与坐标轴平行的线段组成（单每层单属性划分）。每一段对应了某个属性的取值，解释性强，但是运算量比较大。因此想要通过平滑的斜线来代替这些线段，这样可以简化模型，同时达到分类效果，即每次划分采用多属性的组合：
$\sum^d_{i-1}w_ia_i=t$
其中 $w_i$ 为属性 $a_i$ 的权重， $t$ 代表线性分类器， $w_i$ 和 $t$ 都可以在该结点对应样本集和属性集上学得。