使用ID3生成决策树

2016-02-26

ID3算法是一种贪心算法，用来构造决策树。ID3算法起源于概念学习系统（CLS），以信息熵的下降速度为选取测试属性的标准，即在每个节点选取还尚未被用来划分的具有最高信息增益的属性作为划分标准，然后继续这个过程，直到生成的决策树能完美分类训练样例。

优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
缺点：可能会产生过度匹配问题。
适用数据类型：数值型和标称型

例如我们有如下数据:

编号	Sky	AirTemp	Humidity	Wind	Water	Forecast	EnjoySport
1	Sunny	Warm	Normal	Strong	Warm	Same	Y
2	Sunny	Warm	High	Strong	Warm	Same	Y
3	Rainy	Cold	High	Strong	Warm	Same	N
4	Rainy	Warm	High	Strong	warm	Change	Y

如果根据Sky作为标准来分割集合，则得到的结果为：{(Sunny, Y), (Rainy, N),{Rainy, Y}}，对这个集合计算香农熵:
```
H1= -1/3*log(1/3) - 2/3*log(2/3)= 0.6365141682948128
```
如果根据AirTemp来分割，则得到的集合为:{(Warm, Y), (Cold, N) },对这个集合计算香农熵：
```
H2= -1/2*log(1/2) - 1/2*log(1/2)= 0.6931471805599453
```
如果根据Forecast来分割，则得到的集合为：{(Same, Y ), (Same, N), (Change, Y) }，对这个集合计算香农熵：
```
H3=-1/3*log(1/3) - 2/3*log(2/3) = 0.6365141682948128
```

以此类推，最终我们选择AirTemp来作为决策树的第一个节点，将集合分割成两个。然后递归得到的分支集合，做相同的处理。
递归结束的条件是：程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。

ID3算法简单且容易理解，但是会有过度匹配的问题，此时就需要一些剪枝的方法。除了ID3算法外，还有一些其他比较流行的决策树生成方法，例如C4.5和CART算法。

uncategorized