ID3算法学习笔记

原理

设存在一个集合S，算法的每次迭代，遍历S中每个未被便利的属性，且计算该属性的信息熵（entropy）或信息增益（information gain）。 然后选择最小熵（或最大信息增益）的属性，对S进行分离以生成子集。算法继续递归每个子集。

递归停止条件：

• 子集中每个元素都属于同一类别。如此，则节点变为叶节点，以该类别为标识。
• 子集中无更多的属性可以选择，但样本仍然不完全属于同一类别。如此，则节点变为叶节点，以样本中出现次数最多的类别为标识。
• 子集中无任何样例。如此，则创建一个叶节点，以父样本集中出现次数最多的类别为标识。

运用该算法，所构造的决策树的内部节点表示属性筛选的决策，叶节点表示分类的标识。

简单来说，过程就是：

1. 计算数据集S中每个属性的熵
2. 熵最小的属性被选择作为分离数据集的熵。
3. 创建一个节点以包含该属性。
4. 对子集（剩余属性）进行递归。

伪代码

ID3 (Examples, Target_Attribute, Attributes)
    Create a root node for the tree
    If all examples are positive, Return the single-node tree Root, with label = +.
    If all examples are negative, Return the single-node tree Root, with label = -.
    If number of predicting attributes is empty, then Return the single node tree Root,
    with label = most common value of the target attribute in the examples.
    Otherwise Begin
        A ← The Attribute that best classifies examples.
        Decision Tree attribute for Root = A.
        For each possible value, vi, of A,
            Add a new tree branch below Root, corresponding to the test A = vi.
            Let Examples(vi) be the subset of examples that have the value vi for A
            If Examples(vi) is empty
                Then below this new branch add a leaf node with label = most common target value in the examples
            Else below this new branch add the subtree ID3 (Examples(vi), Target_Attribute, Attributes – {A})
    End
    Return Root

属性

算法原型是一个贪婪算法，不能保证是最优解。可以通过backtracking进行优化。 ID3简历的树模型容易对训练集数据过拟合，通过先/后剪支解决。 ID3对连续型数据不友好，只能间接地计算连续性数据。

使用

一般在离线计算模块训练出决策树模型。在实时计算模块遍历已经构建好的决策树模型以得到分类的目标结果。

参考

• https://en.wikipedia.org/wiki/ID3_algorithm