扫码加入数据分析学习群

决策树中使用的基本算法称为ID3（通过Quinlan）算法。 ID3算法使用自上而下的贪婪方法构建决策树。

简而言之，该算法的步骤如下： - 选择最佳属性→A - 分配A作为NODE的决策属性（测试用例）。 - 对于A的每个值，创建NODE的新后代。 - 将训练示例排序到适当的后代节点叶。 - 如果示例完全分类，则STOP else迭代新的叶节点。

决策树中一个重要问题是如何选择最佳属性。

对于ID3，我们考虑哪个属性具有最多信息增益的最佳属性，该度量表示属性基于分类将该数据拆分成组的程度。

伪代码： ID3是一种贪心算法，可以自上而下地生成树，在每个节点上选择最能对本地训练样例进行分类的属性。 这个过程一直持续到树完全分类训练样例或直到所有属性都被使用。

伪代码假定属性是离散的，并且分类是二进制的。 示例是培训示例。 Target_attribute是其值由树预测的属性。 属性是可以由学习的决策树测试的其他属性的列表。 最后，它返回一个决策树，正确分类给定的例子 。

ID3（ 示例，Target_attribute，Attributes ）： - 为树创建根节点 。 - 如果所有示例均为正数，则返回具有正标签的单节点树根。 - 如果所有示例均为负数，则返回带有否定标签的单节点树根。 - 如果Attributes为空，则返回单节点树根 ，并在示例中使用Target_attribute的最常见标签。 - 否则，开始 - A←来自属性的属性最佳*分类示例 - 根的决定属性←A - 对于每个可能的值$ v_i $ ，A， - 在根下添加新的树分支，对应于测试A = $ v_i $ - 让Examples_vi成为A值为$ v_i $的示例的子集。 - 如果Examples_vi为空 - 那么，在这个新分支下面添加一个叶节点，其中标签在示例中具有最常见的Target_attribute值。 - 否则，在这个新分支下面添加子树（或调用函数） - ID3（ Examples_vi，Target_attribute，Attributes- {A} ） - 结束 - 返回根。