决策树decision tree
什么是决策树
输入：学习集
输出：分类觃则（决策树）
- 算法的核心问题
该按什么样的次序来选择变量（属性）？
最佳分离点（连续的情形）在哪儿？
ID3算法
image.png
例子
image.png
C4.5算法
image.png
例子
image.png
CART算法
image.png
image.png
代价复杂度剪枝
http://blog.csdn.net/tianguokaka/article/details/9018933
C4.5的悲观剪枝法
http://blog.csdn.net/tianguokaka/article/details/9018933
R语言实现决策树：rpart扩展包
image.png
怎样评估分类器效能？
image.png
提升分类器准确率的组合方法
image.png
- 组合算法的优势
能明显提升判别准确率
对误差和噪音更加鲁棒性
一定程度抵消过度拟合
适合并行化计算
装袋算法
image.png
- 袋装算法的优势
准确率明显高于组合中任何单个的分类器
对于较大的噪音，表现丌至于很差，并且具有鲁棒性
不容易过度拟合
提升（boosting）算法思想
训练集中的元组被分配权重
权重影响抽样，权重越大，越可能被抽取
迭代训练若干个分类器，在前一个分类器中被错误分类的元组，会被提高权重，使到它在后面建立的分类器里被更加“关注”
最后分类也是由所有分类器一起投票，投票权重取决于分类器的准确率
- Adaboost算法
image.png
image.png
- 提升算法的优缺点
可以获得比bagging更高的准确率
容易过度拟合
随机森林（Random Forest）算法
由很多决策树分类器组合而成（因而称为“森林”）
单个的决策树分类器用随机方法构成。首先，学习集是从原训练集中通过有放回抽样得到的自助样本。其次，参不构建该决策树的变量也是随机抽出，参不变量数通常大大小于可用变量数。
单个决策树在产生学习集和确定参不变量后，使用CART算法计算，丌剪枝
最后分类结果取决于各个决策树分类器简单多数选举
- 随机森林算法优点
准确率可以和Adaboost媲美
对错误和离群点更加鲁棒性
决策树容易过度拟合的问题会随着森林觃模而削弱
在大数据情况下速度快，性能好
- R的randomForest包
