【机器学习基础】第十一课:决策树的基本流程

决策树的基本流程

Posted by x-jeff on February 14, 2020

【机器学习基础】系列博客为参考周志华老师的《机器学习》一书,自己所做的读书笔记。
本文为原创文章,未经本人允许,禁止转载。转载请注明出处。

1.初识决策树

决策树(decision tree),亦称判定树,是一类常见的机器学习方法。

顾名思义,决策树是基于树结构来进行决策的。例如,判断一个西瓜是否为好瓜:

一般的,一棵决策树包含一个根结点、若干个内部结点和若干个叶结点。其中,叶结点对应于决策结果,其他每个结点则对应于一个属性测试。每个结点包含的样本集合根据属性测试的结果被划分到子结点中,根结点包含样本全集。

决策树学习的目的是为了产生一棵泛化能力强,即处理未见示例能力强的决策树,其基本流程见下:

显然,决策树的生成是一个递归过程。在决策树基本算法中,有三种情形会导致递归返回:

  1. 当前结点包含的样本全属于同一类别,无需划分。
  2. 当前属性集为空,或是所有样本在所有属性上取值相同,无法划分。
  3. 当前结点包含的样本集合为空,不能划分。

在第(2)种情形下,我们把当前结点标记为叶结点,并将其类别设定为该结点所含样本最多的类别。

在第(3)种情形下,同样把当前结点标记为叶结点,但将其类别设定为其父结点所含样本最多的类别。

⚠️注意情形(2)和情形(3)处理方式的不同。