决策树ID3算法以及Python实现

机器学习 算法

---

决策树

决策树是一棵树，其叶子节点决定了该类的归属，其内部节点则根据特征的值对数据进行子树寻找，以决定在哪棵子树上继续该决策过程。

特点

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

熵

信息的定义：待分类的事务可能处于多个类中，则符号$x_i$的信息定义如下：

$$l(x_i) = -log_2p(x_i)$$
计算熵，需要计算所有类别所有可能值包含的信息期望值： $$H = - \sum^n_i p(x_i)log_2p(x_i)$$ 其中n指的是可能的类别，而p指的是为某一类的可能性

构建决策树

1. 得到原始数据集，然后基于最好的属性划分数据集；可能存在多个分支的数据集划分；
2. 划分后，将子数据集递归调用决策树构建方法；直到所有属性都已经使用完毕或者每个分支下的所有实例都具有相同的分类；

Python实现

Github: https://github.com/spiritwiki/codes/tree/master/ID3
Coding.net：https://coding.net/u/spiritwiki/p/codes/git/tree/master/ID3