决策树/DT

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

算法释义

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

算法步骤

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

特征选择

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

熵和条件熵

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

那么随机变量 Y 的熵的定义是:$$ H (Y) = - \sum^I } $$

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

信息增益

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

在决策树的特征选择中:$$\begin& H(D) = - \sum^K \frac {|Dk|} {|D|} \log2 {\frac {|Dk|} {|D|}} \& H(D|A) = - \sum^I \left({ \frac {|Di|} {|D|} } \sum^K \frac {|D|} {|Di|} \log2 {\frac {|D|} {|Di|}}\right)\end$$

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

信息增益比

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

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

基尼系数

除了熵之外,还可以用基尼系数来描述数据集的“纯度”:$$ Gini(p) = \sum^I = 1 - \sum^I p_i^2 $$

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

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

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

剪枝

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

预剪枝

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

后剪枝

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

连续与缺失值

连续值处理

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

缺失值处理

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

CART

pass

参考文献

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

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180825G1EGMF00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

同媒体快讯

扫码关注云+社区

领取腾讯云代金券