11.1 理解决策树
决策树方法在分类、预测、规则提取等领域有着广泛应用。在20世纪70年代后期和80年代初期,机器学习研究者J.Ross Quinilan提出了ID3[5-2]算法以后,决策树在机器学习、数据挖掘邻域得到极大的发展。Quinilan后来又提出了C4.5,成为新的监督学习算法。1984年几位统计学家提出了CART分类算法。ID3和ART算法大约同时被提出,但都是采用类似的方法从训练样本中学习决策树。
决策树是一树状结构,它的每一个叶节点对应着一个分类,非叶节点对应着在某个属性上的划分,根据样本在该属性上的不同取值将其划分成若干个子集。对于非纯的叶节点,多数类的标号给出到达这个节点的样本所属的类。构造决策树的核心问题是在每一步如何选择适当的属性对样本做拆分。对一个分类问题,从已知类标记的训练样本中学习并构造出决策树是一个自上而下,分而治之的过程。