第七章分类和预测.pptVIP

Bagging Boosting 分类 决策树分类: ID3 C4.5 贝叶斯分类 后向传播分类 其它分类 分类法的准确性 评估分类法的准确率 保持（holdout） K-次交叉验证（k-fold cross validation） 提高分类法的准确率 bagging boosting 评估分类法的准确率 保持（holdout） 划分为两个独立的数据集： 通常:训练集 (2/3),测试集(1/3) 变形：随机子选样 评估分类法的准确率 K-次交叉验证 将数据集分为k个子集； 用k-1个子集作训练集，1个子集作测试集，然后k次交叉验证； 提高分类法的准确率 Bagging Boosting Bagging 基本思想: 给定一个弱学习算法,和一个训练集; 单个弱学习算法准确率不高; 将该学习算法使用多次,得出预测函数序列,进行投票; 最后结果准确率将得到提高. Bagging 算法: For t = 1, 2, …, T Do 从数据集S中取样（放回选样） 训练得到模型Ht 对未知样本X分类时,每个模型Ht都得出一个分类，得票最高的即为未知样本X的分类 也可通过得票的平均值用于连续值的预测 Bagging Bagging Bagging要求“不稳定”的分类方法； 比如：决策树，神经网络算法 不稳定：数据集的小的变动能够使得分类结果的显著的变动。 “The vital element is the instability of the prediction method. If perturbing the learning set can cause significant changes in the predictor constructed, then bagging can improve accuracy.” (Breiman 1996) Boosting背景 来源于:PAC-Learning Model Valiant 1984 -11 提出问题: 强学习算法: 准确率很高的学习算法 弱学习算法: 准确率不高,仅比随机猜测略好 是否可以将弱学习算法提升为强学习算法 Boosting背景 最初的boosting算法 Schapire 1989 AdaBoost算法 Freund and Schapire 1995 Boosting 基本思想： 每个样本都赋予一个权重 T次迭代，每次迭代后，对分类错误的样本加大权重，使得下一次的迭代更加关注这些样本。 Boosting也要求“不稳定”的分类方法 Boosting 过程: 在一定的权重条件下训练数据，得出分类法Ct 根据Ct的错误率调整权重 Boosting AdaBoost AdaBoost.M1 AdaBoost.M2 … AdaBoost 输入:(X1,Y1), (X2,Y2),…(Xn,Yn) Xi∈X, Yi∈Y={+1,-1} 初始化:D1(i)=1/n For t=1,…,T 在Dt下训练, 得到弱的假设ht: X-{-1,+1}, 错误率:Εt=ΣDt(i) [ht(Xi)≠Yi] 选择αt=1/2 ln ( (1- Εt)/ Εt ), 更改权值: if ht(Xi)≠Yi , Dt+1(i)=Dt(i)* e αt /Zt if ht(Xi)=Yi , Dt+1(i)=Dt(i)* e -αt /Zt 输出:H(X)=sign( ∑ αtht(X) ) AdaBoost.M1 初始赋予每个样本相等的权重1/N ； For t = 1, 2, …, T Do 学习得到分类法Ct； 计算该分类法的错误率Et Et=所有被错误分类的样本的权重和； βt= Et/（1 - Et） 根据错误率更新样本的权重； 正确分类的样本： Wnew= Wold* βt 错误分类的样本： Wnew= Wold 调整使得权重和为1； 每个分类法Ct的投票价值为log [ 1 / βt ] Boosting AdaBoost training error 将γt=1/2-Et ; Freund and Schapire 证明: 最大错误率为: 即训练错误率随γt的增大呈指数级的减小. AdaBoost generalization error(1) 最大总误差: m : 样本个数 d : VC维 T : 训练轮数 Pr: 对训练集的经验概率 如果T值太大,Boosting会导致过适应（overfi