06其他分类方法.ppt

典型的集成学习算法介绍 * 西安电子科技大学计算机学院 * Bagging Bagging?主要是减少分类模型的方差(variance) 因此，Bagging?一般用于训练算法对于训练数据较为敏感(即unstable)的场合(例如：决策树) 典型的集成学习算法介绍 * 西安电子科技大学计算机学院 * AdaBoost 基本思路：每一个样本都被赋予一个权重，表明其被选为训练集的概率修改权重的规则：如果某样本已被正确分类，则降低权重，否则提高权重。 最后根据每个分量分类器的性能，以加权投票的方式进行决策。 典型的集成学习算法介绍 * 西安电子科技大学计算机学院 * AdaBoost 典型的集成学习算法介绍 * 西安电子科技大学计算机学院 * * 西安电子科技大学计算机学院 * 选择性集成 * 西安电子科技大学计算机学院 * 分类器集成通过利用多个分类器来获得比及使用单个分类器更强的泛化能力。 尽管如此，分类器也并非越多越好,因为 更多的分类器导致更大的计算和存储开销 越多的分类器会使个体之间的差异越来越难获得 实验证实了过多分类器可能降低集成的泛化能力 选择性集成：使用部分训练好的分类器，从而在已有的个体分类器中进行选择之后再集成。 目标：获得更好的泛化能力，同时降低存储和计算开销。 选择性集成 * 西安电子科技大学计算机学院 * References： [1] Lior Rokach. Ensemble-based classifiers. Artif. Intell. Rev., 33:1-39, 2010. (1088) [2] Zhi-Hua Zhou. Ensembling neural networks: many could be better than all. Artif. Intell., 137(1-2): 239-263, 2002. (1688) [3] Zhi-Hua Zhou. Ensemble Methods: Foundations and Algorithms. Chapman Hall/CRC Press, 2010. (766) * 相对熵 相对熵，又称互熵，交叉熵，鉴别信息，Kullback熵，Kullback-Leible散度等 设p(x)、q(x)是X中取值的两个概率分布，则p对q的相对熵是  说明： 相对熵可以度量两个随机变量的“距离” 一般的，D(p||q) ≠D(q||p) * 互信息 两个随机变量X，Y的互信息，定义为X，Y的联合分布和独立分布乘积的相对熵。 I(X,Y)=D(P(X,Y) || P(X)P(Y)) * 计算H(X)-I(X,Y) * 整理得到的等式 H(X|Y) = H(X,Y) - H(Y) 条件熵定义 H(X|Y) = H(X) - I(X,Y) 根据互信息定义展开得到 有些文献将I(X,Y)=H(Y) – H(Y|X)作为互信息的定义式 对偶式 H(Y|X)= H(X,Y) - H(X) H(Y|X)= H(Y) - I(X,Y) I(X,Y)= H(X) + H(Y) - H(X,Y) 有些文献将该式作为互信息的定义式 * 决策树 (Decision Tree) 决策树是一种树型结构，其中每个内部结点表示在一个属性上的测试，每个分支代表一个测试输出，每个叶结点代表一种类别。 决策树学习是以实例为基础的归纳学习。 决策树学习采用的是自顶向下的递归方法，其基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处的熵值为零，此时每个叶节点中的实例都属于同一类。 * 决策树学习算法的特点 决策树学习算法的最大优点是，它可以自学习。在学习的过程中，不需要使用者了解过多背景知识，只需要对训练实例进行较好的标注，就能够进行学习。 显然，属于有监督学习。 从一类无序、无规则的事物(概念)中推理出决策树表示的分类规则。 决策树与随机森林 * 西安电子科技大学计算机学院 * 决策树 一个简化的树状决策过程例子 * 信息增益 概念：当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时，所对应的熵和条件熵分别称为经验熵和经验条件熵。 信息增益表示得知特征A的信息而使得类X的信息的不确定性减少的程度。 定义：特征A对训练数