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