ID3算法

目录

ID3算法

 例子

ID算法总结

---

 

ID3算法

---

ID3算法是在每个结点处选取能获得最高信息增益的分支属性进行分裂

在每个决策结点处划分分支、选取分支属性的目的是将整个决策树的样本纯度提升

衡量样本集合纯度的指标则是熵；

 

举例来说，如果有一个大小为10的布尔值样本集Sb，其中有6个真值、4个假值，那么该布尔型样本分类的熵为：

 

计算分支属性对于样本集分类好坏程度的度量——信息增益

由于分裂后样本集的纯度提高，则样本集的熵降低，熵降低的值即为该分裂方法的信息增益

 例子

---

此样本集有“饮食习性”、“胎生动物”、“水生动物”、“会飞”四个属性可作为分支属性，而“哺乳动物”作为样本的分类属性，有“是”与“否”两种分类，也即正例与负例。共有14个样本，其中8个正例，6个反例，设此样本集为 S，则分裂前的熵值为：

 

 

ID算法总结

---

由根结点通过计算信息增益选取合适的属性进行分裂，若新生成的结点的分类属性不唯一，则对新生成的结点继续进行分裂，不断重复此步骤，直至所有样本属于同 一类，或者达到要求的分类条件为止

常用的分类条件：包括结点样本数最少于来设定的值、决策树达到预先设定的最大深度等

在决策树的构建过程中：会出现使用了所有的属性进行分支之后，类别不同的样本仍存在同一个叶子结点中。当达到了限制条件而被强制停止构建时，也会出现结点中子样本集存在多种分类的情况。对于这种情况，一般取此结点中子样本集占数的分类作为结点的分类

分支多的属性并不一定是最优的：就如同将100个样本分到99个分支中并没有什么意义，这种分支属性因为分支太多可能相比之下无法提供太多的可用信息，例如个人信息中的“省份”属性