ID3算法原型见于J.R Quinlan的博士论文,是基础理论较为完善,使用较为广泛的决策树模型,在此基础上J.R
Quinlan进行优化后,陆续推出了C4.5和C5.0决策树算法,后二者现已称为当前最流行的决策树算法,我们先从ID3
开始讲起,再讨论如何从ID3逐渐优化至C4.5。
为了要将表格转化为一棵树,决策树需要找出最佳节点和最佳的分枝方法,而衡量这个“最佳”的指标叫做“不纯度”。
不纯度基于叶子节点来计算的,所以树中的每个节点都会有一个不纯度,并且子节点的不纯度一定是低于父节点的,
也就是说,在同一棵决策树上,叶子节点的不纯度一定是最低的。