决策树是一种常用的分类和回归算法，其实现较为简单，呈树形结构。其有点主要为可读性，分类速度快。
常用决策树
- ID3
- C4.5
- CART
分别对应的启发函数为
ID3-最大信息增益
为样本集合，类别数为 ，经验熵为
其中是样本集合中集合 中属于第 类的样本子集， 表示该子集的元素个数，然后计算特征 对于数据集 的经验条件熵为
则信息增益
可表示为
C4.5-最大信息增益比
其中
CART-最大基尼指数
特征的Gini指数定义为
剪枝
通常分为预剪枝和后剪枝
预剪枝
即在树的构建中进行剪枝，常用的标准有
- 达到一定深度
- 节点样本数小于阈值
- 分裂对测试集的准确度提升小于阈值
后剪枝
即在树的构建完成后再自底向上进行剪枝