决策树(Hunt、ID3、C4.5、CART)

1、决策树

  决策树属于经典的十大数据挖掘算法之一，是一种类似于流程图的树型结构，其规则就是if…then…的思想，用于数值型因变量的预测和离散型因变量的分类。决策树算法简单直观，容易解释，而且在实际应用中具有其他算法难以比肩的速度优势。

  决策树方法在分类、预测和规则提取等领域有广泛应用。在20世纪70年代后期和80年代初期，机器学习研究人员J.Ross Quinlan开发了决策树算法，称为迭代的二分器（Iterative Dichotomiser, ID3），使得决策树在机器学习领域得到极大发展。Quinlan后来又提出ID3的后继C4.5算法，成为新的监督学习算法的性能比较基准。1984年几位统计学家又提出了CART分类算法。

  分类决策树模型是一种描述对实例进行分类的树形结构。决策树由节点(node)和有向边(directed edge)组成。节点有两种类型：内部节点和叶节点。内部节点表示一个特征或者属性，叶节点表示一个类。

  决策树分类过程：**从根节点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子节点；这时，每一个子节点对应该特征的一个取值。如此递归地对实例进行测试和分配，直至达到叶节点。**最后将实例分到叶节点地类中。如下图所