数据挖掘技术与应用：ID3算法

ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。具体方法是从根结点开始:首先对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，并由该特征的不同取值建立子结点；然后对子结点递归地调用以上方法，构建决策树，直到所有特征的信息增益均很小或没有特征可以选择为止；最后得到一棵决策树。ID3相当于用极大似然法进行概率模型的选择[6]。

算法4.2　ID3算法

输入:训练数据集D、特征集A、阈值ε；

输出:决策树T。

(1)若D中所有实例属于同一类Ck，则T为单结点树，并将类Ck作为该结点的类标记，返回T。

(2)若A＝φ，则T为单结点树，并将D中实例数最大的类Ck作为该结点的类标记，返回T。(www.xing528.com)

(3)否则，按算法4.1计算A中各特征对D的信息增益，选择信息增益最大的特征Ag。

(4)如果Ag的信息增益小于阈值ε，则置T为单结点树，并将D中实例数最大的类Ck作为该结点的类标记，返回T。

(5)否则，对Ag的每一个可能值ai，依Ag＝ai将D分割为若干非空子集Di，将Di中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T。

(6)对第i个子结点，以Di为训练集，以A－{Ag}为特征集，递归地调用步骤(1)　～(5)，得到子树Ti，返回Ti。

ID3算法只含有树的生成，所以，由该算法生成的树容易产生过拟合。