决策树

决策树是一种常见的机器学习方法,它基于二元划分策略(类似于二叉树),如下图所示

一棵决策树包括一个根节点、若干个内部节点和若干个叶节点。叶节点对应决策的结果,而其他节点对应一个属性测试。决策树学习的目的就是构建一棵泛化能力强的决策树。决策树算法的优点包括

使用决策树进行决策的过程就是从根节点开始,测试待分类项中相应的特征属性,并按照其值选择输出分支,直到到达叶子节点,将叶子节点存放的类别作为决策结果。

决策树所形成的分类边界有一个明显特点:轴平行,即它的分类边界由多个与坐标轴平行的分段组成。在多变量决策树中,通过替换该分段为斜划分实现决策树模型的简化。

划分选择

决策树学习的关键是如何选择最优划分属性。一般来说,我们希望划分后分支节点所包含的样本尽量属于同一个类别,即节点的纯度(purity)越来越高。

信息熵是度量样本纯度的一种常用指标,$$End(D)$$ 越小则纯度越高。

$$Ent(D)=-\sum^y_{k=1}p_klog_2p_k$$

其中,$$p_k$$是第k类样本所占的比例,k=1,2,…,y

而在属性选择时,要选择信息增益大的属性。其中,信息增益为

$$Gain(D, a) = Ent(D) - \sum^V_{v=1} \frac{|D^v|}{D} Ent(D^v)$$

常用算法

剪枝处理

剪枝(pruning)是决策树学习中解决过拟合问题的主要手段,其策略包括预剪枝和后剪枝两种。

连续与缺失值处理

参考文档

Pengfei Ni ©2021