什么是决策树？

决策树是一种类似流程图的树形机制，其中每个内部节点表示对属性的测试，每个分支定义测试的结果，叶子节点描述类别或类别分布。树中最高的节点是根节点。

学习决策树的算法

算法 − 从给定的训练信息中创建决策树。

输入 − 由离散值属性描述的训练样本；属性集，属性列表。

输出 − 决策树。

方法

  • 创建一个节点 N；

  • 如果样本全部属于同一类别 C，则

  • 将 N 返回为标记为类别 C 的叶子节点

  • 如果属性列表为空，则

  • 将 N 返回为标记为样本中最常见类别的叶子节点。 // 多数投票

  • 选择测试属性，即属性列表中信息增益最高的属性。

  • 用测试属性标记节点 N。

  • 对于测试属性的每个已知值 ai // 分区样本。

  • 为条件测试属性 = ai 从节点 N 增长一个分支。

  • 令 si 为样本中测试属性 = ai 的样本集。

  • 如果 si 为空，则

  • 它可以连接一个标记为样本中最常见类别的叶子。

  • 否则，附加由生成决策树 (si，属性列表 - 测试属性) 返回的节点

决策树归纳

例如，决策规则的自动生成被称为规则归纳或自动规则归纳。它可以创建决策树隐式设计中的决策规则也经常被称为规则归纳，但是术语树归纳或决策树归纳经常被选择。

决策树归纳的基本算法是一种贪婪算法。它用于以自上而下递归分治的方式生成决策树。学习决策树的基本算法是 ID3 的一种形式，一种著名的决策树归纳算法。

基本方法如下：

  • 树开始时是一个单独的节点，定义训练样本。

  • 如果样本全部属于相同的类别，则该节点变为叶子节点，并用该类别标记。

  • 该算法应用一种基于熵的度量，称为信息增益，作为选择将样本划分为单个类别的属性的启发式方法。此属性成为节点的“测试”或“决策”属性。在这种算法形式中，所有属性都是分类的，即离散值的。连续值属性应离散化。

  • 为测试属性的每个已知值生成一个分支，并相应地划分样本。

  • 该算法使用类似的循环过程来为每个分支的样本形成决策树。因为一个属性已出现在一个节点上，所以它不需要在其一些后代节点中处理。

更新于：2021年11月22日

3K+ 次浏览

启动您的职业生涯

完成课程获得认证

开始学习
广告