决策树
决策树(decision tree)是一种常见的机器学习方法,也叫“判定树”。
-
根据上下文,决策树有时候是指学习方法,有时候是指学得的树。
决策树是根据树形结构来进行决策的,这与人类在面临决策问题时的处理机制非常一致。在进行决策时,通常会进行一系列的判断或者决策,最后得出最终决策。
决策过程的最终结论,就是期望的判定结果。
决策过程中提出的每个判定问题,都是对某个属性的测试。
每个测试的结果,或是导出最终结论,或是导出进一步的判定问题。其考虑范围是在上次决策结果的限定范围之内。
一般来说,一颗决策树包含一个根节点,若干个内部节点和若干个叶节点。
-
叶节点对应于决策结果。
其他每个节点则对应于一个属性测试。
每个节点包含的样本集合根据属性测试的结果被划分到子节点中。
根节点包含样本全集。
从根节点到每个叶节点的路径对应一个判定测试序列。
决策树学习的目的是为了产生一棵泛化能力强——处理未见适应能力强的决策树。
决策树的基本流程遵循简单且直观的“分而制之”(divide and conquer)策略。
决策树的生成是一个递归过程。有三种情况会导致递归返回:
-
当前节点包含的样本全是同一类别,无需划分。
当前属性集为空,或者所有样本在所有属性上取值相同,无法划分。
当前节点包含的样本集合为空,不能划分。
注意:第2种、第3种情况,都把当前节点标记为叶节点。
第2种情况,将当前节点的类别设定为该节点所含样本最多的类别。利用当前节点的后验分布。
第3种情况,将当前节点的类别设定为其父节点所含样本最多的类别。把父节点的样本分布作为当前节点的先验分布。
决策树的关键是如何选择最优划分属性,这就是划分选择。
一般而言,随着划分过程不断进行,希望决策树的分支节点所包含的样本尽可能属于同一类别,即为节点的“纯度”(purity)越来越高。
划分选择
ID3与信息增益
“信息熵”(Information entropy)是度量样本集合纯度最常用的指标。
假设当前样本集合D中第k类样本所占的比例为pk,则D的信息商定义为 Ent(D)的值越小,则D的纯度越高。其中表示集合D中第k类样本所占的比例。
一般而言,“信息增益”(information gain)越大,则意味着使用属性a来进行划分所获得的纯度提升越大。因此可以用信息增益来进行决策树的划分属性选择。信息增益的定义如下:
其中,D^v表示第v个分支节点包含了D中所有在属性a上取值为a^v的样本。
著名的 ID3 决策树学习算法是以信息增益为准则来划分属性。 ID3 中的 ID 是 Iterative Dichotomiser(迭代二分器)的简称。
信息增益对可取值数目较多的属性有所偏好。
C4.5与增益率
为减少这种信息增益的偏好可能带来的不利影响,著名的 C4.5 决策树算法不直接使用信息增益而使用“增益率”(gain ratio)来选择最优划分属性。定义如下:
其中,称为属性a的“固有值”(intrinsic value)。
增益率准则对可取值数目较少的属性有所偏好。
C4.5 算法并不是直接选择增益率最大的候选划分属性,而是使用了一个启发式:先从候选划分中找出信息增益高于平均水平的属性,再从中选择增益率最高的。
CART与基尼指数
CART(Classification and regression tree) 决策树使用“基尼指数”(Gini index)来选择划分属性。 CART是一种著名的决策树学习算法,分类和回归任务都可用。
基尼值得定义如下:
基尼指数的定义如下:
观来说,Gini(D) 反映了从数据集D中随机抽取两个样本,其类别标记不一致的概率。因此 Gini(D) 越小,则数据集D的纯度越高。
选择使得划分后基尼指数最小的属性作为最优划分属性。