ID3算法

维基百科,自由的百科全书
跳转至: 导航搜索

ID3算法(Iterative Dichotomiser 3 迭代二叉树3代)是一个由Ross Quinlan发明的用于决策树算法

这个算法是建立在奥卡姆剃刀的基础上:越是小型的决策树越优于大的决策树(简单理论)。尽管如此,该算法也不是总是生成最小的树形结构。而是一个启发式算法。奥卡姆剃刀阐述了一个信息熵的概念:

 I_{E}(i) = - \sum^{m}_{j=1}  f (i,j) \log_{2} f (i, j).

这个ID3算法可以归纳为以下几点:

  1. 使用所有没有使用的属性并计算与之相关的样本熵值
  2. 选取其中熵值最小的属性
  3. 生成包含该属性的节点

关于ID3算法的实现可以参考C4.5算法,它同时也是ID3的升级版。

相关主题[编辑]

参考文献[编辑]

  • Mitchell, Tom M. Machine Learning. McGraw-Hill, 1997.

外部连接[编辑]