ID3决策树算法及其相关算法

决策树算法是一类比较常用的机器学习的算法是一种监督学习算法其本质是归纳出一组分类规则.决策树算法一般可以分为分类树和回归树来对应对离散数据和连续数据的处理这里介绍的是分类决策树.一般一棵决策树包括一个根结点若干个内部结点和若干个叶子结点.其叶子结点对应于决策结果其他每个结点对应一个属性测试每个节结包含的样本集合根据属性测试的结果被划分到子结点中根结点包括样本全集.从根结点到每个叶子结点代表了一种分类规则.一般比较常见的决策树算法有ID3C4.5CART等.算法基本流程遵循下面的策略输入训练集D x1y1x2y2xm ym一般为离散值属性集为A a1a2 ad过程函数TreeGenerate D A1生成结点note2if该结点中所有样本属于同一类别C then将note中标记为C类结点return3ifA为非空OR D中样本在A取值相同then将note标记为叶结点