决策树是一种基本的分类与回归方法。在其分类问题中，表示基于特征对实例进行分类的过程，可以认为是if-else规则的集合，也可以认为是定义在特征空间与类空间上的条件分类。其主要优点是模型具有可读性、分类速度快。

决策树

  决策树是一种基本的分类与回归方法。在其分类问题中，表示基于特征对实例进行分类的过程，可以认为是
if-else规则的集合，也可以认为是定义在特征空间与类空间上的条件分类。其主要优点是模型具有可读性、分类速度快。
决策树学习的3个步骤：

• 特征选择
• 决策树生成
• 决策树的剪枝

决策树模型

  内部一个几点表示一个特征或属性，叶节点表示一个类。

if-else规则

  可以把决策树认为是 if-else规则的集合。

条件概率分布

  各叶节点上条件概率偏向某一类，即属于某一类的概率较大，决策树分类时将该结点的实例分到概率大的那一类。

决策树的学习

  本质上是从训练集中归纳出一组分类规则，用损失函数（正则化的极大似然函数）表示目标，将损失函数极小化。算法是递归选择最优特征，方法有C4.5/ID3/CART。

特征选择

信息增益

  我们先来回顾一下什么是熵与条件熵

熵是表示随机变量不确定行的度量

  假设Ｘ是取有限个值的离散随机变量，其概率分布是：$P(X=x_{i})=p_{i}, i=1,2,...,n$则随机变量Ｘ的熵的定义是：

$$H(X)=-\sum_{i=1}^{n}p_{i}\log{p_{i}}$$

  熵越大，表示随机变量的不确定性就越大。熵$H(p)$随概率$p$变化的曲线如下图：

  比如说，某个特征 $X^{j}$ 取 $\{0,1\}$ ，训练集中其中有一半取１，另一半取０，那么 $P(X^{j}=0)$ 和 $P(X^{j}=１)$ 都0.5，那么对应的熵$H(p)=1$，这表示提供随机变量$X^{i}$给我们带来的不确定性是最大的，自然我们也没办法根据变量$X^{i}$来进行预测。

  而条件熵$H(Y|X)$表示在已知随机变量X的条件下 $Y$ 的确定性，定义为

X在给定的条件下Y的概率分布的熵对X的数学期望:

$$H(Y|X)=\sum_{i=1}^{n}P(X=x_{i})H(Y|X=x_{i})$$

n表示变量X所有的可取值个数

  当熵和条件熵的概率由极大似然估计得到时，对应称为经验熵和经验条件熵。信息增益可以定义为：

特征A对于训练集的信息增益 $g(D,A)$ 可以定义为D的经验熵 $H(D)$ 与特征A给定条件下 D 的条件经验条件熵 $H(D|A)$ 之差。$g(D,A)=H(D)-H(D|A)$

  信息增益大意味着 $H(D|A)$ 小，即给定特征A后，经验条件熵小，确定性大。所以信息增益大意味着具有更强的分类能力。信息增益算法如下图所示：

实例可以参考P62的例5.2。

信息增益比

  特征A对训练集的信息增益比 $g_{R}(D,A)$ 定义为其信息增益与训练集关于特征A的熵 $H_{A}(D)$ 之比：

$$g_{R}(D,A)=\frac{g(D,A)}{H_{A}(D)}$$

其中

$$H_{A}(D)=-\sum_{i=1}^{n} \frac{|D_{i}|}{|D|} \log{\frac{|D_{i}|}{|D|}}$$

决策树的生成

• ID3树使用信息增益选择特征，当 $g(D,A)<\epsilon$ 时作为叶节点，分裂时，以每一个特征可取的值作为分裂；
• C4.5树使用信息增益比来选择特征。

决策树的剪枝

  决策树的剪枝往往通过极小化决策树的整体损失函数或代价函数来实现。假设树T的叶结点个数为 $|T|$ ,t是树T的叶结点，设叶结点有 $N_{t}$ 个样本，其中k类的样本点有 $N_{tk}$ 个， $H_{t}(T)$ 为叶结点上的经验熵，则损失函数可以定义为：

$$C_{\alpha}(T) = \sum_{t=1}^{|T|} N_{t}H_{t}(T) + \alpha |T|$$

其中， $H_{t}(T)=-\sum_{k} \frac{N_{tk}}{N_{t}} \log{\frac{N_{tk}}{N_{t}}}$ ，于是损失函数可以写为：

$$\begin{eqnarray} C_{\alpha}(T) &=& -\sum_{t=1}^{|T|}\sum_{k=1}^{K} N_{tk}\log{\frac{N_{tk}}{N_{t}}} + \alpha |T \\ &=& C(T)+\alpha|T| \end{eqnarray}$$

$C(T)$ 表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，$|T|$ 表示模型复杂度，参数 $\alpha \geq 0$ 。树的剪枝算法如下图：

CART

  CART（classification and regression tree）可能是应用最广泛的决策树方法了。CART同样由特征选择、树的生成和剪枝组成，既可以用于分类也可以用于回归。需要注意的是，CART假设决策树的二叉树，内部节点特征的取值为“是”和“否”，左枝表示“是”，右枝表示“否”。这样决策树等价于递归地二分每个特征，将输入空间划分成有限个单元，并在这些单元上确定预测的概率分布。特征选择时，回归树用平方误差最小化准则，分类树用基尼指数最小化准则。

回归树的生成

  对于数据集

$$D=\{(x_{1}, y_{1}),\dots,(x_{N}, y_{N})\}$$

回归树对应输入空间的一个划分以及在划分的单元上的输出值。假设已将输入空间划分成为M个单元$R_{1},\dots,R_{M}，并在每个单元R_{m}上有一个固定的输出值c_{m}$。那么回归树模型可以表示为：

$$f(x)=\sum_{m=1}^{M}c_{m}I(x \in R_{m})$$

  当输入空间的划分确定时，可以用平方误差

$$\sum_{x_{i} \in R_{m}} (y_{i}-f(x_{i}))^{2}$$

来表示预测误差，用平方误差最小的准则求解每个单元上的最优输出值。实际上，单元$R_{m}$上的$c_{m}$的最优值$\hat{c}_{m}$是$R_{m}$上的所有输入实例$x_{i}$对应的输出$y_{i}$的均值。

  那么如何对输入空间进行划分呢？我们采用启发式的方法，选择第j个变量$x^j$和它的取值s作为切分变量和切分点，并定义两个区域： $R_{1}(j,s)=\{x|x^j \leq s\} 和 R_{2}(j,s)=\{x|x^j > s\}$
然后对固定输入变量j可以找到最优切分点s，即求解：

$$\min_{j,s} \big[ \min_{c_{1}} \sum_{x \in R_{1}(j,s)} (y_{i} - c_{1})^2 + \min_{c_{2}} \sum_{x \in R_{2}(j,s)} (y_{i} - c_{2})^2 \big]$$

来找到固定输入变量j的最优切分点s，遍历所有的输入变量，找到最优的切分变量j，构成一个对 $(j,s)$ 。依此将输入空间划分为两个区域，重复这个过程直到满足停止条件为止。这样的回归树通常称为最小二乘回归树，算法如下图：

分类树的生成

  分类树用基尼指数选择最有特征，同时决定该特征的最优二值切分点。

基尼指数：分类问题中，假设有K个类，样本点属于第k类的概率为 $p_{k}$ ，则概率分布的基尼指数定义为： $Gini(p)=\sum_{k=1}^{K}p_{k}(1-p_{k})=1-\sum_{k=1}^{K}p_{k}^{2}$

  对于二分类问题，若样本点属于A类的概率是p，则概率分布的基尼指数为$Gini(p)=2p(1-p)$，对于给定的样本集合D，其基尼指数为：$Gini(D)=1-\sum_{k=1}^{K}(\frac{|C_{k}|}{|D|})^{2}$。如果样本集合D根据特征A是否取某一可能值a被划分为$D_{1}和D_{2}$两个部分，则在特征A的条件下，集合D的基尼指数定义为：

$$Gini(D,A)=\frac{|D_{1}|}{|D|}Gini(D_{1}) + \frac{|D_{2}|}{|D|}Gini(D_{2})$$

基尼指数表示集合D的不确定性，这一点与熵相似。
  下图展示了CART分类树的生成算法：

CART剪枝

enjoy it!