机器学习第四章：决策树

1.基本流程

决策树是基于树结构来进行决策的。
例如，我们要对“这是好瓜吗？”进行决策时，通常要进行一系列的判断或子决定：首先看“它是什么颜色？”，如果是青绿色，那么再看“它的根蒂是什么形态？”，如果是蜷缩，则…以此类推，最终得到最终决策：这是好瓜。

在这里插入图片描述

决策过程中提出的每个判定问题都是对某个属性的“测试”；

每个测试的结果要么导出最终结论，要么导出进一步的判定问题；

一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶节点；叶节点对应于决策结果，其他结点各对应一个属性测试；每个结点包括的样本集合根据属性测试的结果被划分到子节点中；根节点包含样本全集；从根节点到每个叶节点的路径对应了一个判定测试序列。

决策树学习的目的是为了产生一棵泛化能力强（处理未见示例能力强的决策树），其基本流程遵循“分而治之”的策略。

决策树学习基本算法：

输入：训练集D={（x1,y1），（x2,y2）,...,(xm,ym)}
      属性集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为根节点的一棵决策树

决策树的生成时一个递归过程；
在算法中，有三种情形会导致递归返回：
（1）当前节点包含的样本全属于同一类别，无需划分；
（2）当前属性集为空/所有样本在所有属性上取值相同，无法划分；
（3）当前节点包含样本集合为空，不能划分。

2.划分选择

决策树学习的关键在于如何选择最优划分属性；
随着划分过程的不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一类别（结点的“纯度”越来越高）。

2.1 ID3决策树

“信息熵”是度量样本集合纯度最常用的一种指标；
假设当前样本集合D中第k类样本所占比例为 $p_{k}(k=1,2,...,|Y|)$ ，则信息熵定义为：
$Ent\left( D\right) =-\sum ^{|Y|}_{i=1}p_{k}\log _{2}p_{k}$
$E n t (D)$ 的值越小，则D的纯度越高。

离散属性a有V个可能的取值 ${a^{1},a^{2},...,a^{V}}$ ,若使用a来对样本D进行划分，则会产生V个分支节点，其中第v个分支节点包含了D中所有在属性a上取值为 $a^{v}$ 的样本，记 $D^{v}$ ;
可计算出用属性a对样本集D划分所获得的“信息增益”：
$Gaint(D,a)=Ent(D)-\sum^V_{v=1}\dfrac{\left| D^{v}\right| }{\left| D\right| }Ent(D)$
信息增益越大，则使用属性a来进行划分所获得的“纯度提升”越大；
因此，在多个属性中选择使信息增益最大的属性来进行划分。

2.2 C4.5决策树

由于信息增益准则对可取值数目较多的属性有所偏好，（例如“编号”：将n个样本逐一编号，将产生n个分支，每个分支的结点仅包含一个样本，这些分支点的纯度已经达到最大，但这样的决策树不具有泛化能力，不能对新样本进行有效预测）；

为了减少信息增益的这种偏好带来的不利影响，C4.5决策树算法不直接使用信息增益，而使用“增益率”，其定义为：
$Gaint\_ratio(D,a)=\dfrac{Gaint(D,a)}{IV(a)}$
其中：
$IV(a)=-\sum_{v=1}^{V}\dfrac{|D^{v}|}{|D|}\log_2\dfrac{|D^{v}|}{|D|}$
它为属性a的固有值；
属性a的可能取值数目越多（V越大），则 $I V (a)$ 的值通常会越大；

但是，增益率准则又对可取值数目较少的属性有所偏好，所以也不能直接选择增益率准则来划分；
C4.5是采用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择出增益率最高的。

2.3 CART决策树

CART决策树使用了“基尼指数”；
数据集D的纯度可用基尼指数来度量：
$Gini(D)=\sum_{k=1}^{|Y|}\sum_{k^{'}\neq k}p_{k}p_{k^{'}}=1-\sum_{k=1}^{|Y|}p_{k}^{2}$
$G i n i (D)$ 反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率；
所以 $G i n i (D)$ 越小，数据集D的纯度越高；