集成学习算法
Ⅰ 常见的分类方法
主要分类方法介绍解决分类问题的方法很多[40-42] ，单一的分类方法主要包括：决策树、贝叶斯、人工神经网络、K-近邻、支持向量机和基于关联规则的分类等；另外还有用于组合单一分类方法的集成学习算法，如Bagging和Boosting等。
（1）决策树
决策树是用于分类和预测的主要技术之一，决策树学习是以实例为基础的归纳学习算法，它着眼于从一组无次序、无规则的实例中推理出以决策树表示的分类规则。构造决策树的目的是找出属性和类别间的关系，用它来预测将来未知类别的记录的类别。它采用自顶向下的递归方式，在决策树的内部节点进行属性的比较，并根据不同属性值判断从该节点向下的分支，在决策树的叶节点得到结论。
主要的决策树算法有ID3、C4.5（C5.0）、CART、PUBLIC、SLIQ和SPRINT算法等。它们在选择测试属性采用的技术、生成的决策树的结构、剪枝的方法以及时刻，能否处理大数据集等方面都有各自的不同之处。
（2）贝叶斯
贝叶斯（Bayes）分类算法是一类利用概率统计知识进行分类的算法，如朴素贝叶斯（Naive
Bayes）算法。这些算法主要利用Bayes定理来预测一个未知类别的样本属于各个类别的可能性，选择其中可能性最大的一个类别作为该样本的最终类别。由于贝叶斯定理的成立本身需要一个很强的条件独立性假设前提，而此假设在实际情况中经常是不成立的，因而其分类准确性就会下降。为此就出现了许多降低独立性假设的贝叶斯分类算法，如TAN（Tree
Augmented Na?ve Bayes)算法，它是在贝叶斯网络结构的基础上增加属性对之间的关联来实现的。
（3）人工神经网络
人工神经网络（Artificial
Neural
Networks，ANN）是一种应用类似于大脑神经突触联接的结构进行信息处理的数学模型。在这种模型中，大量的节点（或称”神经元”，或”单元”）之间相互联接构成网络，即”神经网络”，以达到处理信息的目的。神经网络通常需要进行训练，训练的过程就是网络进行学习的过程。训练改变了网络节点的连接权的值使其具有分类的功能，经过训练的网络就可用于对象的识别。
目前，神经网络已有上百种不同的模型，常见的有BP网络、径向基RBF网络、Hopfield网络、随机神经网络（Boltzmann机）、竞争神经网络（Hamming网络，自组织映射网络）等。但是当前的神经网络仍普遍存在收敛速度慢、计算量大、训练时间长和不可解释等缺点。
（4）k-近邻
k-近邻(kNN，k-Nearest
Neighbors)算法是一种基于实例的分类方法。该方法就是找出与未知样本x距离最近的k个训练样本，看这k个样本中多数属于哪一类，就把x归为那一类。k-近邻方法是一种懒惰学习方法，它存放样本，直到需要分类时才进行分类，如果样本集比较复杂，可能会导致很大的计算开销，因此无法应用到实时性很强的场合。
（5）支持向量机
支持向量机（SVM，Support
Vector Machine）是Vapnik根据统计学习理论提出的一种新的学习方法[43]
，它的最大特点是根据结构风险最小化准则，以最大化分类间隔构造最优分类超平面来提高学习机的泛化能力，较好地解决了非线性、高维数、局部极小点等问题。对于分类问题，支持向量机算法根据区域中的样本计算该区域的决策曲面，由此确定该区域中未知样本的类别。
（6）基于关联规则的分类
关联规则挖掘是数据挖掘中一个重要的研究领域。近年来，对于如何将关联规则挖掘用于分类问题，学者们进行了广泛的研究。关联分类方法挖掘形如condset→C的规则，其中condset是项(或属性-值对)的集合，而C是类标号，这种形式的规则称为类关联规则（class
association
rules，CARS）。关联分类方法一般由两步组成：第一步用关联规则挖掘算法从训练数据集中挖掘出所有满足指定支持度和置信度的类关联规则；第二步使用启发式方法从挖掘出的类关联规则中挑选出一组高质量的规则用于分类。属于关联分类的算法主要包括CBA[44]
，ADT[45] ，CMAR[46] 等。
（7）集成学习（Ensemble Learning）
实际应用的复杂性和数据的多样性往往使得单一的分类方法不够有效。因此，学者们对多种分类方法的融合即集成学习进行了广泛的研究。集成学习已成为国际机器学习界的研究热点，并被称为当前机器学习四个主要研究方向之一。
集成学习是一种机器学习范式，它试图通过连续调用单个的学习算法，获得不同的基学习器，然后根据规则组合这些学习器来解决同一个问题，可以显着的提高学习系统的泛化能力。组合多个基学习器主要采用（加权）投票的方法，常见的算法有装袋[47]
（Bagging），提升/推进[48, 49] （Boosting）等。
有关分类器的集成学习见图2-5。集成学习由于采用了投票平均的方法组合多个分类器，所以有可能减少单个分类器的误差，获得对问题空间模型更加准确的表示，从而提高分类器的分类准确度。
图2-5：分类器的集成学习
以上简单介绍了各种主要的分类方法，应该说其都有各自不同的特点及优缺点。对于数据库负载的自动识别，应该选择哪种方法呢？用来比较和评估分类方法的标准[50]
主要有：（1）预测的准确率。模型正确地预测新样本的类标号的能力；（2）计算速度。包括构造模型以及使用模型进行分类的时间；（3）强壮性。模型对噪声数据或空缺值数据正确预测的能力；（4）可伸缩性。对于数据量很大的数据集，有效构造模型的能力；（5）模型描述的简洁性和可解释性。模型描述愈简洁、愈容易理解，则愈受欢迎。
Ⅱ 经典机器学习系列之【集成学习】
塌历老中国有句老古话，叫“ 三个臭皮匠顶个诸葛亮 ”，说的是人多力量大，可也有句成语叫“ 乌合之众 ”。在机器学习中也有一类算法，将这两种思想融合起来，取其精华，它就是 集成学习 ，算法将不同的学习器融合在一起。
在集成学习中，算法不要求每个学习器性能最好，但是期望它们对问题具有不同的看法，Good But Different (好而不同)。
如果在分类问题上描述的话，所表示的就是具有不同的划分能力，对于一些样本学习器 能划分，对于另外一些样本，学习器 能划分。并不要求单个学习器对所有样本都具备划分能力。
用专业一点的属于来说的话，就是不同的学习器具有不同的偏好模型，但是每一个都是弱监督模型，集成学习将多个弱监督模型组合，得到一个好的强监督模型。其思想是，不同的学习器之间相互地错误纠正，以达到最终准确率的提升。
集成学习，其英文名称叫做( ensemble learning )，它通过将多个学习器集成在一起来达到学习的目的。主要是将有限的模型相互组合，其名称有时也会有不同的叫法，有时也会被称为多分类器系统( multi-classifier system )、委员会学习( committee learning )、Molar systems、classifier fusion、combination、aggregation等。这些概念相互之间互相联系，又有些许区别，对于概念的定义业界还没有达成共识。整个算法所表现出来的性能非常地强悍，许多高水平的竞赛(Knowledge Discovery and Data Mining、Kaggle)中都是首选。
在机器学习，满足训练集的假设不一定在实际应用中有同样好的表现，这样学习算法选择哪个假设进行输出的时候就面临着一定的风险，把多个假设集成起来能够降低这种风险（这可以理解为通过集成使得各个假设和目标假设之间的误差得到一定程度的抵消）。
在周志华西瓜书中通过Hoeffding不等式证明了， 随着集成中个体分类器数目的增大 ， 集成的错误率将指数级下降 ， 最终趋于零 。
集成学习先产生一组“个体学习器”( indivial learner )，再通过某种策略将其结合起来。依据每个个体学习器所采用的学习算法是否相同，可以分为 同质集成 和 异质集成 。
集成学习器性能要好于单个个体学习器需要满足 好而不同 的两点要求：
第一个条件相对来说比较容易实现，在当前问题下训练一个模型，结果比瞎猜的结果好就行了。 第二个条件是集成学习研究的核心问题 。每个个体学习器学习的都是同一个问题，所以个体学习器不可能做到完全相互独立。想想小时候，老师让你发烂岁表不同的观点，想想写论文的时候找创新点，人都很难做到这样一件事情，何况它只是一个小小的学习算法。
想要在个体学习器足够好的前提下，增强其多样性，我们可以直观上来想象一下。整个的算法学习过程是从数据到模型再到输出。
首先考虑输入 。如果每个学习器学习不同的样本，那么可以学习出相对来说不同的个体学习器。那么现在的问题就是怎么划分训练样本，你可以随机抽取，或者利用不同的属性子集训练出不同的个体学习器。
其次考虑模型 ，如果基学习器的模型不一样，也能训练出不同的个体学习器。
最后考虑输出 ，如果我们依据标签的特性来进团升行划分，也能得到不同的个体学习器。
依据上述三点概念，主要有以下5种方法：
从原始训练样本中产生不同的样本子集，然后利用不同的样本子集训练不同的个体学习器。如 Bagging 中使用的 自助采样 ， Boosting 中使用的 序列采样 。
这种训练样本扰动的方法简单高效，但 只对不稳定的基学习器有效 ，像 决策树 、 神经网络 等；对于稳定的基学习器，如线性学习器、支持向量机、朴素贝叶斯、K-NN等，就效果不明显，产生这个问题的原因就是因为稳定的基学习器，“变通能力”并不是很强。
说到Bagging和Boosting，这里详细介绍一下这两种经典的方法：集成学习分为个体学习其之间存在强以来关系、必须 串行生成的序列化方法-Boosting 和不存在强依赖关系， 可同时生成并行化方法-Bagging 。
具体的实现方法是：首先给每一个训练 样例赋予相同的权重 ，然后训练第一个基本分类器并用它来对训练集进行测试， 对于那些分类错误的测试样例提高其权重 （实际算法中是降低分类正确的样例的权重）， 然后用调整后的带权训练集训练第二个基本分类器 ，然后重复这个过程直到最后得到一个足够好的学习器。
Boosting中最着名算法是1997年Yoav Freund所提出的AdaBoost（Adaptive Boosting）方法。下图是AdaBoost论文Bing学术搜索结果：
本文以周志华西瓜书推导过程为例，以“ 加性模型 ”（additive model）进行解析：
将基学习器 线性组合，则基学习器的线性组合表示为如下 形式：
定义整个学习器的损失函数为指数损失函数( exponential loss function )，期望指数损失函数最小化：
其中 是真实函数， ， 表示样本的权值分布(对于错误的样本权重要高一点，正确的样本权重要低一点，所有的样本组合起来就相当于有一个分布)。
若基学习器的线性组合 能够使得指数损失函数最小化，一般的做法就是求偏导数，令其等于零，求解。由于 取值只有两种，所以其求偏导数之后的结果如下所示：
令其偏导数为0，解得：
有：
这意味着若指数损失函数最小化，则分类错误率也将最小化。说明指数损失函数是原任务的替代函数，但由于其连续可微，所以用它替代 0/1 损失函数作为优化目标。上面这么多就是说接下来用这个连续的指数损失函数做进一步的处理。
在AdaBoost算法中，第一个基分类器 通过直接将基学习算法用于初始数据分布而得到；之后的 和 是通过迭代生成得到的。当基分类器 基于分布 产生之后，基分类器的权重 应该使得 最小化指数损失函数，只有 在判断错误的基分类器给予较小权值，判断正确的基分类器给予较大权值，才能使得 具有较准确的判断，从而最小化指数损失函数
其中 ，其实就是误判率。为了求得基分类器的权重，对其求导：
再令导数为0，可得：
到这里相当于自适应做完了，在这里，AdaBoost自适应的思想采取的是加权多数表决的方法，上述公式体现出来的就是加大分类器误差率小的弱分类器的权值，使其在表决中起较大作用。误差率较大的则相反。
现在要回到Boost的原理中对样本的处理，在改变这个样本的权值，或者说概率分布的时候，我们要实现的直观想法是： 提高那些被前一轮弱分类器错误分类样本的权值 ， 降低那些被正确分类的样本的权值 。接下来我们去把这个公式证出来：
这里通过基学习器开始证明，看基学习器在什么样本分布下能够学出来最小化分类误差。
AdaBoost 在得到 之后，调整样本分布，使得 能学出来之前的基学习器无法学习到的东西，能纠正 的一些错误，那这个 就能够最小化：
注意到 ，上式可使用 的泰勒展开式近似为如下公式：
于是理想的基学习器：
注意到 是一个常数。令 表示一个分布：
依据数学期望的定义，等价于令:
由 ， ， ，有：
则理想的基学习器：
由此可见，理想的 将在分布 下最小化分类误差。 和 的关系有：
上述公式就是下图AdaBoost的第7步更新公式，整个的AdaBoost算法如下图所示：
AdaBoost 算法第五行检查当前基分类器是否比随机猜测好，一旦不满足条件，当前基学习器即被抛弃，且学习过程停止。在这个请款下就有可能导致集成中包含基学习器数量过少，导致整体性能不佳。采用“重采样法”（re-sampling）来处理，即在每一轮学习中，根据样本分布对训练集重新采样，再用重采样而得到的样本集对基学习器进行训练，则可获得重启动。
是并行式集成学习方法着名代表，基于自助采样法( bootstrap sampling )，给定包含 个样本的数据集，有放回随机采样，经过 次得到含有 个样本的采样集，这样的采样，初始训练集中约有 的样本出现在采样集中。
照这样采样出 个含 个训练样本的采样集，然后基于每个采样集训练一个基学习器，再将这些基学习器进行结合。在预测输出时，Bagging通常对分类任务使用 简单投票法 。对回归任务使用 简单平均法 。
上图中 表示自助采样产生的样本分布。
输入属性扰动通常是从初始属性集中抽取出若干个属性子集，然后利用不同的属性子集训练出不同的个体学习器。比如有：
RF 在以 决策树 为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入随机属性。传统决策树在选择划分属性时是在当前结点的属性集合中选择一个最优属性；而在RF中，对基决策树的每个结点， 先从该结点的属性集合中随机选择一个包含 个属性的子集 ， 然后再从这个子集中选择一个最优属性用于划分 。
随机森林中基学习器多样性不仅来自样本扰动，还来自属性扰动，使得最终集成的泛化性能可通过个体学习器之间差异度的增加而进一步提升。
但这类输入属性扰动的方法只对大量冗余属性的数据集有效，但若数据集只包含少量属性，或者冗余属性很少，则不宜使用。随机森林由于起始引入了属性扰动，性能会比Bagging差一点，但随着个体数量增多，随机森林通常会收敛到更低的泛化误差。
算法参数扰动指的是通过随机设置不同的参数来训练差别较大的个体学习器。如下图所示的神经网络的隐层神经元数、初始连接权值等不同。
此类方法对参数较多的算法有效，对参数较少的算法，可通过将其学习过程中某些环节用其他类似方法代替？从而达到扰动的目的。这可能也是发论文的一个点吧，自己以后可能也不咋用这个算法，就不去做算法调研了。
输出标记扰动是对训练样本的类别标记稍作变动，将原来的多分类问题随机转化 多个二分类问题 来训练基学习器。经典的一个算法就是纠错输出编码法（Error-Correcting Output Codes，ECOC）
将每个类别对应一个长度为n的二进制位串（称为码字），共形成m个码字，这些码字的同一位描述了一个二值函数。学习结束后获得n个二分器，在分类阶段，每个二分器对输入样本产生的输出形成输出向量，然后由决策规则判定输入样本的类别。
这类方法对类数足够多的数据集有效，但若数据集包含的类数较少，则不宜使用。
混合扰动在同一个集成算法中同时使用上述多种扰动方法。比如随机森林就同时使用了训练样本扰动和输入属性扰动。
上文五点讨论的是如何产生好而不同的个体学习器。那产生了好而不同的个体学习器之后，我们如何结合这些策略？主要有 平均法 和常见的 投票法 (voting)，具体包括：
简单地将输出结果平均一下
乘以权值系数将其加起来。
即若某标记得票过半数，则分类为该标记，否则拒绝分类。
分类为得票最多的标记，若同时有多个标记获最高票，则从中随机选取一个。
给每个个体学习器预测的类标记赋一个权值，分类为权值最大的标记。这里的权值通常为该个体学习器的分类置信度（类成员概率）。
Ⅲ 集成算法名词解释
集成算法(Emseble Learning)是构建多个学习器，然后通过一定策略结合把它们来完成学习任务的，常常可以获得比单一学习显着优越的学习器。
Ⅳ 集成算法
集成学习包括Bagging方法和Boosting方法，下面详细分析这两种方法。
下面是决策树与这些算法框架进行结合所得到的新的算法：
1） Bagging + 决策树 = 随机森林
2）AdaBoost + 决策树 = 提升树
3）Gradient Boosting + 决策树 = GBDT
Bagging法假设训练样本集服从均匀分布，即1/N。
（1） 从训练样本集中 随机可放回抽样（Bootstrapping )N次 ，得到与训练集相同大小的训练集，重复抽样K次， 得到K个训练集 。
（2） 每个训练集得到一个最优模型， K个训练集得到K个最优厅弯模型。
（3） 分类问题：对K个模型采用 投票的方式得到分类结果 ；回归问题：对K个模型的值 求平均得到分 类结果。
每一个样本数据是有权重的，每一个学习器是有先后顺序的。在PAC（概率近似正确）的学习框架下，一定可以将弱分类器组装成一个强分类器。
（1）每一轮如何改变训练数据的权值和概率分布？
（2）通过什么方式来组合弱学习器？
其尺氏中，学习器性能越好，对应的权值也越大。样本权值1初始化为1/N，即初始样本集服从均匀分布，后面随着前一个学习器的结果更新样本权值。
集成学习得到多个学习器后，结合策略得到最终的结果。通常用到最多的是平均法，投票法和学习法。
适用范围：
规模大的集成，学习的权重较多 ， 加权平均法易导致过拟合
个体学习器性能相差较大时宜使用加权平均法，相近用简单平均法 。
绝对多数投票法：某标记 超过半数 ，也就是我们常说的要票过半数，否则就当会拒绝预测；
相对多数投票法：预测为得票 最多 的标记，若同时有多个标记的票最高，则从中随机选取一个，也就是所谓的“少数服从多数”。
加权投票法：提供了预测结果，与加权平均法类似。
对于学习法，代表方法是stacking，当使用stacking的结合策略时， 我们不是对弱学习器的结果做简单的逻辑处理，而是再加上一层学习器，也就是说，我们 将训练集弱学习器的学习结果作为输入， 将训练集的输出作为输出，重新训练一个学习器来得到最终结果。
在这种情况下，我们将弱学习器称为初级学习器，将用于结合的学习器称为次级学习器。对于测试集，我们首先用初级学习器预测一次，得到次级学习器的输入样本，再用次级学习器预测一次，得到最终的预测结果。
1）训练样本集
Bagging：训练集是有放回抽样，从原始集中选出的K组训练集是相互独立的。
Boosting：每一次迭代的训练集不变。
2）训练样本权扮困闷重
Bagging：每个训练样本的权重相等，即1/N。
Boosting：根据学习器的错误率不断调整样例的权值，错误率越大，权值越大。
3）预测函数的权重：
Bagging：K组学习器的权重相等，即1/K。
Boosting：学习器性能好的分配较大的权重，学习器性能差的分配较小的权重。
4）并行计算
Bagging：K组学习器模型可以并行生成。
Boosting：K组学习器只能顺序生成，因为后一个模型的样本权值需要前一个学习器模型的结果。
Bagging和Boosting方法都是把若干个学习器整合为一个学习器的方法，Bagging方法可以降低模型的方差，Boosting方法可以降低模型的偏差，在实际工作中，因情况需要选择集成方法。