决策树/DT(Decision Tree)

摘要:决策树作为一种解释性好、训练效率高、了解简单的机器学习算法,在特征选择等领域使用的非常广泛。算法释义决策树通过递归地进行特征选择,将训练集数据 D 进行分类最终生成一颗由节点和有向边组成的树结构。其中结点分为两种类型:内部节点和叶节点,内部结点表示一个特征,叶结点表示一个类别。算法步骤输入:训练集 D

决策树作为一种解释性好、训练效率高、了解简单的机器学习算法,在特征选择等领域使用的非常广泛。

算法释义

决策树通过递归地进行特征选择,将训练集数据 D 进行分类最终生成一颗由节点和有向边组成的树结构。其中结点分为两种类型:内部节点和叶节点,内部结点表示一个特征,叶结点表示一个类别。

算法步骤

输入:训练集 D,特征集 A
输出:决策树 T
(1) 生成叶节点:
a. 若 D 中所有实例属于同一类 C,则 T 为单结点树,并将 C 作为该节点的类标记,返回 T
b. 若特征集 A 为空,则 T 为单结点树,并将 D 中实例最多的类 C 作为该节点的类标记,返回 T
c. 其余终止条件下,则 T 为单结点树,并将 D 中实例最多的类 C 作为该节点的类标记,返回 T
(2) 特征选择:根据某种标准,在特征集 A 中选择一个特征 a 和划分,而后将训练集划分为 n 份,其对应的特征集 A = {A - a}
(3) 递归生成:对(2)中划分之后的的训练集分别调使用该算法。


特征选择

特征选择在于选取对训练数据具备分类能力的特征,假如特征选择的结果和随机分类的结果错误率没有什么差别的话,就认为这样的特征选择是失败的,相反,假如特征选择使得决策树的叶节点内部基本都属于同一个类别,显然这样的特征选择错误率是很低的,也就是说决策树的叶节点的“纯度”要越高越好,那么数学上怎样去衡量这样的“纯度”呢?下面引入熵的概念。

熵和条件熵

在信息论和概率统计中,熵是表示随机变量不确定性的度量,假设随机变量 Y 是一个取有限个值得离散随机变量,其概率分布有:
P (Y = y_i) = p_i, i = 1,2,...,I

那么随机变量 Y 的熵的定义是:
H (Y) = - \sum_{i=1}^I {p_i \log_2 {p_i}}

不难看出,假如随机变量的纯度越高,那么其熵越小,相反假如随机变量的不确定越大,则其熵也越大。
条件熵 H(Y|X) 表示在已知随机变量 X 的条件下随机变量 Y 的不确定性:
H (Y|X) = \sum_{i=1}^I {P(X=x_i) H (Y|X=x_i)}

信息增益

信息增益 g 借助熵和条件熵,使用来形象的表示特征选择对分类“纯度”的提升:
g(D, A) = H(D) - H(D|A)

在决策树的特征选择中:
\begin{align} & H(D) = - \sum_{k=1}^K \frac {|D_k|} {|D|} \log_2 {\frac {|D_k|} {|D|}} \\ & H(D|A) = - \sum_{i=1}^I \left({ \frac {|D_i|} {|D|} } \sum_{k=1}^K \frac {|D_{ik}|} {|D_i|} \log_2 {\frac {|D_{ik}|} {|D_i|}}\right) \end{align}

决策树算法 ID3 就是采使用信息增益来做特征选择的。

信息增益比

使用信息增益作为判别标准时,会存在偏向于选择取值较多的特征的问题,为了避免这个问题,可以在信息增益的基础上除以一个惩罚参数,惩罚参数是训练数据集 D 关于特征 A 的值的熵:
g_R(D, A) = \frac {g(D, A)} {-\sum_{i=1}^I \frac {|D_i|} {|D|} \log_2 {\frac {|D_i|} {|D|}} }

决策树算法 C4.5 就是基于信息增益比来做特征选择的,但它并不是直接选择信息增益比最大的特征作为划分属性的,由于信息增益比会对可取数值较少的属性有偏好,因而它采使用的是一种启发式:先从候选划分属性中选择信息增益高于平均水平的属性,再从中选择信息增益比最高的划分属性。

基尼系数

除了熵之外,还可以使用基尼系数来形容数据集的“纯度”:
Gini(p) = \sum_{i=1}^I {p_i(1-p_i)} = 1 - \sum_{i=1}^I p_i^2

显然,基尼系数越小,数据集的“纯度”越高,对于给定的数据集,其基尼系数为:
Gini(D) = 1 - \sum_{i=1}^I \left( \frac {|D_i|} {|D|} \right)^2

在对特征 A 做二类属性划分是,其划分后的基尼系数可表示为:
Gini(D, A) = \frac {|D_1|} {|D|} Gini(D_1) + \frac {|D_2|} {|D|} Gini(D_2)

CART 分类决策树就是采使用基尼系数做特征选择,每一轮都会选择使基尼系数最小的划分属性。


剪枝

在决策树学习中,为了尽可能正确的分类训练样本,很容易造成决策树分支过多, 从而把训练集自身的少量特点当作数据具备的一般性质,从而导致过拟合,因而为了对付过拟合,可以用剪枝来减少决策树的复杂度,从而降低过拟合的风险。按照剪枝与决策树生成的关系,可以分为预剪枝和后剪枝。

预剪枝

预剪枝是在决策树的生成过程中,对每个节点在划分前先进行预计,假如当前结点不能带来泛化性能的提升,则中止划分并将该结点标记为叶结点。
判断泛化性能可以采使用留出法,训练前先留出一部分数据使用作测试集,而后使用决策树在测试集上的性能表示其泛化性能。
预剪枝不仅能降低过拟合的风向,而且还减少了决策树的训练时间,但是它也存在欠拟合的风险,由于预剪枝属于一种“贪心”本质的算法,有些分支划分可能暂时降低了泛化性能,但是其子结点的划分却有可能带来泛化性能的提升,而这时预剪枝无法预知的。

后剪枝

后剪枝是在完整的决策树生成之后,自底向上地对内部结点进行考察,若把该结点替换成叶结点能带来泛化性能的提升,则把该结点替换成叶结点。
相对于预剪枝,后剪枝算法可以降低欠拟合的风险,但是它需要在生成整颗决策树之后对所有内部结点进行逐一考察,因而其训练时间比预剪枝大的多。


连续与缺失值

连续值解决

采使用连续值离散化技术,把连续值通过一个阈值作为划分点进行划分。

缺失值解决

C4.5 算法在应对缺失值时,首先计算信息增益时,使用无缺失值的训练子集计算信息增益,而后乘以无缺失值的密度,当成属性划分的依据;而后在做划分时,根据各个类别所占的比例,将有缺失值数据按照比例划分到子结点。


CART

pass


参考文献

《统计学习方法》,李航
《机器学习》,周志华

上一篇 目录 下一篇
  • 全部评论(0)
最新发布的资讯信息
【系统环境|】极客时间-数据分析实战45讲【完结】(2021-09-02 16:26)
【系统环境|windows】字节跳动前台面试题解析:盛最多水的容器(2021-03-20 21:27)
【系统环境|windows】DevOps敏捷60问,肯定有你想理解的问题(2021-03-20 21:27)
【系统环境|windows】字节跳动最爱考的前台面试题:JavaScript 基础(2021-03-20 21:27)
【系统环境|windows】JavaScript 的 switch 条件语句(2021-03-20 21:27)
【系统环境|windows】解决 XML 数据应用实践(2021-03-20 21:26)
【系统环境|windows】20个编写现代CSS代码的建议(2021-03-20 21:26)
【系统环境|windows】《vue 3.0探险记》- 运行报错:Error:To install them, you can run: npm install --save core-js/modules/es.arra...(2021-03-20 21:24)
【系统环境|windows】浅谈前台可视化编辑器的实现(2021-03-20 21:24)
【系统环境|windows】产品经理入门迁移学习指南(2021-03-20 21:23)
血鸟云
手机二维码手机访问领取大礼包
返回顶部