一、ID3算法介绍

ID3算法就是一个按照信息增益选择特征的决策树算法,其基本思想为:每次选择一个信息增益最大的特征,逐节点的建立决策树(ID3算法其实是一个递归算法)。

二、ID3算法规定

输入:训练集D,特征集A,阈值ϵ\epsilon

输出:决策树T

  1. 如果D中所有样本均属于同一类别C,则T为单节点树,将C作为该节点的类别标志返回T
  2. 如果A为空,则T为单节点树,将D 中样本最多的类C作为该节点的类别标志,返回,否则计算 A 中各特征对D的信息增益,选择信息增益最大的特征A
  3. 如果AgA_g的信息增益小于阈值ϵ\epsilon,则将T视作单节点树,将D中样本最多的类C作为该节点的类别标记,返回T,否则按照AgA_g的每个可能取值aia_i,将D划分为n个子数据集DiD_i,作为 D的子节点
  4. 对于D的每个子节点D,如果D为空,则视T为单节点树将D的父节点D中样本最多的类作为 D的类别标记,否则以DiD_i作为训练集,以 A-[AgA_g]为特征集,递归地调用算法的1到 6 步,得到子决策树TiT_i,返回TiT_i

三、ID3算法举例