分类决策树

决策树

本篇博客主要讨论分类决策树.

介绍

决策树由结点和有向边组成,结点有两种类型:内部节点和叶节点,内部结点表示一个特征和属性,叶节点表示一个类.

决策树可以看成一个 if-then 规则,内部节点对应 if 的条件,叶节点代表最后的结果,同一结点延伸出来的内部节点必须互斥且完备,保证每一个示例都有路径可寻.

决策树的建立需要考虑拟合精度也不可过拟合.其大致路径为先生成决策树,生成的过程是一个递归的过程,将所有实例放入根节点,然后进行第一次分类,将分出的结果各自结成下一批内部节点,然后继续分下去.但是,为了防止过拟合,需要剪枝,将过于精细的分类合并.

决策树学习常用的算法有ID3,C4.5,CART

特征选择

在决策树开始之前,需要选择对数据具有分类能力的特征,该特征不是说能将数据分类即可,要将分类尽可能的符合符号.

直观上,如果一个特征具有更好的分类能力,或者说,按照这一特征将训练数据集分成子集,使得各个子集在当前条件下有最好的分类,那么就应该选择该特征.对此,我们的评判标准为信息增益.

信息增益

熵与条件熵

熵可能多多少少都有听过,既表示系统混乱度的度量.在信息论与概率统计中,熵表示随机变量不确定性的度量.

设 X 是一个取有限个值得离散随机变量,其概率分布为

$$P(X = x_i) = p_i$$

其熵的定义为:

$$H(X) = -\sum p_i log(p_i)$$

其中,特别定义,$0log0 = 0$.对于对数的底数,若 2 为底数,则叫做比特(bit),e 为底数,则叫做纳特(nat).

设有随机变量(X,Y),其联合概率分布为

$$P(X = x_i|Y = y_i) = p_{ij}$$

条件熵 $H(X|Y)$ 表示在已知随机变量 X 的条件下随机变量 Y 的不确定性.随机变量 X 给定的条件下随机变量 Y 的条件熵 $H(Y|X)$,定义为 X 给定条件下 Y 的条件概率分布的熵对 X 的数学期望

$$H(Y|X) = \sum p_i H(Y|X=x_i) \quad,其中 H(Y|X=x_i) 是一个一元变量的熵,由前面的公式可以算出$$

由样本估计(特别是极大似然估计)得到的称为经验熵和经验条件熵.

信息增益

信息增益表示得知特征 X 的信息而使得类 Y 的信息的不确定性减少的程度.

信息增益: 特征 A 对 训练数据集 D 的 信息增益 $g(D,A)$,定义为集合 D 的经验熵 $H(D)$ 与特征 A 给定条件下 D 的经验条件熵 $H(D|A)$ 之差,即

$$g(D,A) = H(D) - H(D|A)$$

信息增益最大的特征具有更强的分类能力.

信息增益比

以信息增益作为划分训练数据集的特征,存在偏向于选择取值较多的特征的问题.使用信息增益比可以对这一问题进行矫正,这是特征选择的另一个准则.

信息增益比:特征 A 对训练数据集 D 的信息增益比 $g_R(D,A)$ 定义为其信息增益 $g(D,A)$ 与训练数据集 D 关于特征 A 的值得熵 $H_A(D)$ 之比

$$g_R(D,A) = \frac{g(D,A)}{H_A(D)}$$

决策树的生成

ID3 算法

ID3 算法的核心是在决策树各个节点上引用信息增益准则选择特征,递归构建决策树.

具体方法:

• 先从根节点开始,对结点计算所有可能的特征的信息增益,选择信息增益最大的特征作为结点的特征,由该特征的不同取值建立子节点
• 对子节点递归调用以上方法

算法实现:

输入:训练数据集D,特征集A,阈值$\epsilon$,阈值用于防止过拟合

输出:决策树T

• 若D中所有实例属于同一类 $C_k$,则 T 为单节点树,并将类 $C_k$ 作为该节点的类标记,返回 T
• 若 $A = \empty $,则 T 为单节点树,将 D 中实例数最大的类 $C_k$ 作为该结点的类标记,返回 T.
• 否则,按照算法求得信息增益最大的特征值 $A_g$
• 如果 $A_g$ 的信息增益小于阈值 $\epsilon $,则T为单节点树,并将 D 中实例数最大的类 $C_k$ 作为该结点的类标记
• 否则,对 $A_g$ 的每一可能值 $a_i$,依照 A_g = a_i 将 D 分割为若干非空子集 $D_i$,将 $D_i$ 中实例数最大的类作为标记,构建子节点,由结点及其子节点构成数T,返回T
• 对第 i 各子节点,以 $D_i$ 为训练集,以 $A-{A_g}$ 为特征值,递归调用步骤 1-5,得到子树 $T_i$,返回 $T_i$

C4.5 算法

和 ID3 算法类似,只不过使用的是信息增益比来选择特征,就不再赘述了

决策树的剪枝

在决策树中将已生成的树进行简化的过程称为简直.裁掉一下子树或者叶节点,并将其根节点或父节点作为新的叶节点,从而简化分类树模型.

决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现.设树 T 的叶结点个数为 $|T|$,t是树 T 的叶结点,该叶结点由 $N_t$ 各样本点,其中 k 类的样本点有 $N_{tk}$ 个,$H_t(T)$ 为叶结点 t 上的经验熵,$\alpha$ 为参数,则决策树学习的损失函数为:

$$C_{\alpha}(T) = \sum N_tH_t(T) + \alpha |T|$$

其中经验熵为:
$$H_t(T) = - \sum \frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t}$$

令 $C(T) = H_t(T)$,则有$C_\alpha(T) = C(T) + \alpha |T|$

式中 $\alpha$ 表示拟合程度和复杂度之间的调和,$\alpha$ 越大,则倾向于更简单的模型,为0则指考虑模型的拟合程度.

剪枝既当给定 $\alpha$ 时,选择损失函数较小的模型.

剪枝算法:
输入:生成算法之后的整个树,参数 $\alpha$
输出:修剪后的子树 $T_\alpha$

• 计算每个结点的经验熵
• 递归从树的叶结点向上回缩
• 设一组叶结点回缩到其父节点之前与之后的整体树分别为 $T_B$ 和 $T_A$,其对应的损失函数分别为 $C_\alpha(T_B)$ 和 $C_\alpha(T_A)$,如果 $C_\alpha(T_A) \le C_\alpha(T_B)$ 则进行剪枝
• 返回第二步,知道不能继续为止

CART 算法

CART 算法既可以用于分类也可用于回归.其假设决策树是二叉树,内部节点特征的取值是 “是” 与 “否”,左分支为 “是”,右分支为 “否”.

CART 的生成

回归树的生成

设X与Y分别为输入和输出变量,并且Y是连续变量,给定训练数据集

$$D = {(x_1,y_1),…,(x_N,y_N)}$$

一颗回归树对应着输入空间的一个划分以及在划分的单元上的输出值,假设已将输入空间划分为 M 个单元 $R_1,…,R_M$.并且在每个单元 $R_m$ 上有一个固定的输出值 $c_m$,于是回归树模型表示为:

$$f(x) = \sum c_m I (x \in R_m)$$

当输入空间划分确定的时候,可以用平方误差 $\sum(y_i - f(x_i))^2$ 来表示预测误差,用平方误差最小的尊则求解每个单元上的最优输出值.易知,最优值 $\hat c_m$ 是 $R_m$ 上所有输入实例对应输出的均值

划分区域的方式启发式:
选择第 j 个变量 $x^{(j)}$ 和它取的值s,作为切分变量和切分点,并定义两个区域:

$$R_1(j,s) = {x|x_{(j) \le s}} 和 R_2(j,s) = {x|x_{(j) \gt s}}$$

然后寻找最优切分变量 j 和最优切分点 s,求解:

$$ \underset{j,s}{min} [ \underset{c_1}{min} \underset{x_1 \in R_1}{\sum} (y_i-c_1)^2 + \underset{c_2}{min} \underset{x_2 \in R_2}{\sum} (y_i-c_2)^2 ]$$

遍历所有输入变量,找到最优切分点,接着重复上述过程,直到满足停止条件.

算法:

输入:训练集D

输出:回归树 f(x)

• 选择最优切分便令和切分点,求解
  $$ \underset{j,s}{min} [ \underset{c_1}{min} \underset{x_1 \in R_1}{\sum} (y_i-c_1)^2 + \underset{c_2}{min} \underset{x_2 \in R_2}{\sum} (y_i-c_2)^2 ]$$
• 用选定的对(j,s)划分区域并决定响应的输出值:
  $$\begin{aligned}
  R_1(j,s) &= {x|x^{(j)} \le s},\quad R_2(j,s) = {x|x^{(j)} \gt s} \\
  \hat{c_m} &= \frac{1}{N_m} \sum y_i,\quad x \in R_m,\quad m = 1,2
  \end{aligned}$$
• 继续对两个子区域调用上诉步骤直至满足停止条件
• 将输入空间划分为 M 个区域,生成决策树

分类树的生成

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

基尼指数:分类问题中:假设有 K 个类,样本点属于第 k 类的概率为 $p_k$,则概率分布的基尼指数定义为:

$$Gini(p) = \sum p_k(1-p_k) = 1 - \sum p_k ^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,终止条件
输出:决策树

• 设结点的训练集合为 D,计算现有特征对该数据集的基尼指数,此时,对每一个特征 A,对其可能取得每个值 a,根据样本点对 A = a得测试为 “是” 或 “否”,将 D 分割成 D_1 和 D_2 两部分,计算 A = a 时得基尼指数.
• 选择基尼指数最小的特征作为切分点切分,划分左右结点
• 对子节点递归调用
• 生成决策树

CART 剪枝

其剪枝思路是从完整的决策树地段剪去一些子树,直到根节点,形成一个子树序列,然后通过交叉验证法在独立的验证数据集上对子树序列进行测试,从中选择最优的子树.

子树的损失函数为

$$C_{\alpha}(T) = C(T) + \alpha |T|$$

其中,$C(T)$ 时该决策树的预测误差(比如基尼指数,经验熵)

对于剪枝之后的单节点树 t 而言,其损失函数为:
$$C_{\alpha}(t) = C(t) + \alpha$$

对于以t为根结点的子树 $T_t$ 而言,其损失函数为:
$$C_{\alpha}(T_t) = C(T_t) + \alpha|T_t|$$

当 $\alpha = \frac{C(t) - C(T_t)}{|T_t| - 1}$ 时,因为损失函数值相同,但是 t 的结点更少,更加可取,需要剪枝.

因此,计算决策树 $T_0$ 中所有结点的 $g(t) = \frac{C(t) - C(T_t)}{|T_t| - 1}$,并且剪去其中最小的 $T_t$,将得到的子树作为 $T_1$,最小的 $g(t)$ 作为 $\alpha_1$,该子树为 $[\alpha_1,\alpha_2)$ 的最优子树.

这样一直剪枝,直到只剩下根节点,能得到一串子树序列,使用交叉验证法选出最好的哪一个子树.

算法思路:
输入:决策树 $T_0$
输出:最优决策树 $T_\alpha$

• 设 k = 0
• 设 $\alpha = \infty$
• 自下而上对各内部结点 t 计算 $C(T_t)$,$|T_t|$ 以及
  $$\begin{aligned}
  g(t) &= \frac{C(t) - C(T_t)}{|T_t| - 1} \\
  \alpha &= min(\alpha,g(t))
  \end{aligned}$$
• 对 $g(t) == \alpha$的内部结点进行剪枝,并对叶结点 t 以多数表决法决定其类,得到树 T
• $设 k = k + 1,\alpha_k = \alpha,T_k = T$
• 如果 $T_k$ 不是由根节点以及两个叶结点构成的树,则返回到第二步,否则令 $T_k = T_n$
• 交叉验证法选择最优子树