ID3

决策树方法最早产生于上世纪60年代，到70年代末。由JRossQuinlan提出了ID3算法，此算法的目的在于减少树的深度。但是忽略了叶子数目的研究。（比较于随机选择属性作为分裂节点来说，每次选择信息增益最大的属性可以减少树的深度。）

基本思想：

从上至下，分而治之的递归过程。
对当前例子集合，计算属性的信息增益；选择信息增益最大的属性Ai；把在Ai处取值相同的例子归于同一子集，Ai取几个值就得几个子集；对依次对每种取值情况下的子集，递归调用建树算法，即返回a；若子集只含有单个属性，则分支为叶子节点，判断其属性值并标上相应的符号，然后返回调用处。

属性选择

基于熵的信息增益

终止条件

1.数据已经不能继续再分
2.所有属性都已用尽
3.该群数据没有任何未处理的数据

优点

• 不存在无解的危险
• 可以利用全部训练例的统计性质进行决策，从而抵抗噪音。

缺点

• 只能处理分类数据，不能处理连续数据
• 划分过程会由于子集规模过小而造成统计特征不充分而停止
• D3算法在选择根节点和各内部节点中的分支属性时，采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多的属性，在有些情况下这类属性可能不会提供太多有价值的信息。
• 处理大型数据速度较慢，经常出现内存不足，不可以并行，不可以处理数值型数据；ID3（并行）和ID3（number）解决了后两个问题。
• 只适用于非增量数据集，不适用于增量数据集，可能会收敛到局部最优解而非全局最优解，最佳分离属性容易选择属性值多一些的属性。

Python实现