决策树

原创

花鸣溪

修改于 2019-12-05 14:36:31

8800

修改于 2019-12-05 14:36:31

文章被收录于专栏：数据分析与机器学习

一、决策树学习的基本算法

输入：训练集:D= \{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\} ；属性集:A= \{a_1,a_2,..,a_d\} 。

过程：函数Treegenerator(D,A)

生成节点node
if D 中样本全属于同一类别C，then
1. 将node标记为C类叶节点；return
end if
if A = \emptyset OR D 中样本在A上取值相同 then
1. 将node标记为叶节点，其类别标记为D中样本数最多的类；return
end if
从A中选择最优划分属性a_*
for a_* 的每一个值a_*^v do
1. 为node生成一个分支；另D_v表示D中在a_*上取值为a_*^v的样本子集
2. if D_v为空 then
  1. 将分支节点标记为叶节点，其类别标记为D中样本最多的类；return
3. else：
  1. 以Treegenerator(D_v,A-\{a_*\} )为分支节点
4. end if
end for

输出：以node为根节点的一棵决策树

二、评价指标

信息增益

Ent(D) = -\sum_{k = 1}^{|Y|}p_klog_2(p_k) （|Y|为目标变量集合）,Ent(D)的值越小，则D的纯度越高。

Gain（D,a） = Ent(D)-\sum_{v = 1}^V \frac{|D^v|}{|D|}Ent(D^v)

一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的"纯度提升"越大。因此，我们可用信息增益来进行决策树的划分属性选择，即在上述“决策树学习的基本算法”章节中第6行选择属性a_* = argmax_{a\in A}Gain(D,a).著名的ID3决策树学习算法就是以信息增益为准则来选择划分属性。

基尼系数

Gini(D) = \sum_{k = 1}^{C}\sum_{k'\ne k}p_kp_{k'}

Gini(D)反映了从数据集合D中随机抽取两个样本，其类别标记不一致的概率，Gini(D)越小，则数据集合的纯度越高。

Gini\_index(D,a) = \sum\_{v= 1}^V \frac{|D^v|}{|D|}Gini(D^{v})

在候选集合A中选择那个使得划分后基尼系数最小的属性作为最有划分属性，即a_* = argmin_{a\in A} Gini\_index(D,a)

信息增益率

信息增益有一个缺点，其倾向于选择那些取值数目较多的属性，为减少这种倾向所带来的不利影响。著名的C4.5决策树算法不直接使用信息增益，而是采用信息增益率指标。

Gain\_ratio = \frac{Gain(D,a)}{IV(a)}

其中，

IV(a) = -\sum_{v = 1}^V\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}

需要注意的是，与信息增益相反，信息增益率指标有倾向选择取值数目较少属性的缺点，因此，C4.5算法并不是直接选择信息增益率最大的属性作为候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的属性。

总结：

对信息增益和基尼系数进行理论分析显示，它们仅在2%的情况下会有所不同；注意对于连续变量，由于离散化的方式不同，可能会存在差异。
信息增益有倾向于选择取值数量较多属性的特点；而信息增益率有倾向于选择取值数量较少属性的特点；一般可将二者结合起来使用。

三、剪枝

剪枝是决策树处理“过拟合”（overfitting）的主要手段。在决策树学习过程中，由于其优化函数是尽可能降低误分类概率，导致划分节点不断细化，往往会导致将训练样本本身独有的属性学习进决策树中，误将其当做一般性能，导致产生过拟合问题——这种问题导致模型在训练样本上表现较好，但是在测试样本上表现出的泛化性能明显不足。

决策树剪枝的策略主要有“预剪枝”（preprunning）和“后剪枝”（postprunning）.

预剪枝是指在决策树生成过程中，对每个节点在划分前先估计，当前节点的进一步划分是否可以带来泛化性能的提升，否则停止划分将当前节点标记为叶节点。
后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶节点进行考察，若将该节点对应的子树替换为叶节点可以带来泛化性能的提升，则将改子树减掉标记为叶节点。

由于决策树算法本质上是一种递归算法，预剪枝策略存在一个问题——有些分支的当前划分虽不能提升泛化性能，甚至还会降低泛化性能，但是在其基础上进行的后续划分却可能导致泛化性能的明显提升，在这时，由于递归算法特点导致预剪枝策略的贪心本质，禁止了这些分支的划分，进而导致了“欠拟合”的问题。当然预剪枝也存在明显的优点，不仅降低了过拟合的风险，还大大缩减了决策树的训练时间。

而后剪枝策略针对欠拟合问题明显要优于预剪枝策略，泛化性能往往也要优于预剪枝策略；但是后剪枝策略的问题在于，其是在决策树生成之后进行的，并且要自底向上地对树中所有非叶节点进行逐一考察，因此其训练时间要远远大于未剪枝决策树和预剪枝决策树。

总结起来，这两种策略的优缺点如下：

剪枝策略	优点	缺点
预剪枝	降低过拟合风险，缩减训练时间	存在欠拟合问题
后剪枝	降低欠拟合风险，泛化性能优于预剪枝	训练时间较长

一种后剪枝算法

这里介绍一种基于C4.5算法和ID3算法决策树学习的剪枝算法。

决策树的剪枝往往是通过极小化决策树整体的损失函数（loss function）或代价函数（cost function）来实现。设树T的叶节点个数为|T|,t是树T的叶节点，该叶节点有N_t个样本点，其中k类的样本点有N_{tk}个(k = 1,2,3,...,K),H(T)为叶节点t上的经验熵，\alpha≥0为参数，则决策树学习的损失函数可以定义为：

C_{\alpha}(T) = \sum_{t = 1}^{|T|}N_tH_t(T)+\alpha|T|

其中经验熵为

H_t(T) = -\sum_k\frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t}

在损失函数中，将等式右边的第一项记为

C(T) = \sum_{t = 1}^{|T|}N_tH_t(T) = -\sum_{t = 1}^{|T|}\sum_{k = 1}^KN_{tk}log\frac{N_{tk}}{N_t}

这时，有

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

C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，|T|表示模型复杂度，参数\alpha控制两者之间的影响。较大的\alpha促使选择较简单的模型（树），较小的\alpha促使选择较复杂的模型（树）。

决策树的生成只考虑通过信息增益（或信息增益比）对训练集的拟合程度。而决策树剪枝则通过优化损失函数还考虑了减小模型复杂度，进而提高其泛化性能。换言之，决策树生成算法只学习局部的模型，而决策树剪枝算法则关注整体的泛化性能。

四、决策树算法总结：

决策树算法	输入数据类型	树类型	特征选择标准
ID3	离散型	多叉树	信息增益
C4.5	离散型、连续型	多叉树	信息增益率
CART分类回归	离散型、连续型	二叉树	基尼系数、平方误差