经典集成学习算法的有效性解释及算法改进研究

发布时间：2019-08-10 09:51

【摘要】：如何有效地对未知类别的新样例进行分类是数据挖掘领域中一项非常重要的研究课题。集成学习作为解决这一问题的一种强有力的技术自提出以来受到了广泛的关注和研究,并在实际应用中取得了极大的成功。集成学习已发展成数据挖掘领域中的一个重要研究分支。目前学者们已经提出了一些经典的集成学习算法,如Bagging、AdaBoost、DECORATE等,并取得了一些重要的研究成果。然而,对于这些集成学习算法的有效性,还不存在一种对其进行充分解释的较为通用的理论工具;此外,在特定训练环境下某些集成学习算法的性能还不够理想。本文致力于解决这些问题,具体的,可将本文的主要贡献总结如下。(1)由于不同的集成学习算法是学者们从不同角度提出的,自然的它们具有不同的工作机理。因此,若能从理论上对现有的经典集成学习算法的有效性进行分析,可使人们对这些算法产生更深刻的理解,更重要的是有助于发现一种能对集成学习算法有效性进行解释的较为通用的理论工具,从而为设计新的有效集成学习算法提供一定的理论指导。受margin理论所启发,本文尝试使用该理论对Bagging、AdaBoost和DECORATE这三种最有代表性的经典集成学习算法的有效性进行实证分析和比较。实验结果表明,对于探讨的每种集成学习算法,它在训练集上生成的margin分布越好,则其取得的测试精度就越高。也就是说,margin理论能够很好地解释这些算法的有效性。因此可得出结论:margin理论是对集成学习算法的有效性进行解释的一种较为通用的理论工具。基于这一发现,本文建议将margin分布作为设计新的集成学习算法时的优化目标。(2)为了得到理想的泛化性能,集成学习算法通常生成大量的基分类器来构成集成系统。然而在得到的集成系统中,可能存在一些精度较低或者相似的分类器,这不仅会增加集成系统的存储和计算开销而且会降低它的分类效率和泛化性能。为解决这一问题,本文提出了一种基于平均margin排序的基分类器选择方法,以便从初始集成系统中选择一个近似最优的分类器子集。该方法使用平均margin作为性能评价度量来对初始集成中个体分类器的性能进行评估。另外,本文还将平均margin与accuracy和diversity这两种常用的性能评价度量进行了全面比较。实验结果表明,本文的基分类器选择方法能有效地提高初始集成系统的分类效率和泛化性能,并且平均margin是一种比accuracy和diversity更好的性能评价度量。这对改善数据挖掘中分类任务的性能具有重要的理论和实践意义。(3)在一些多分类问题中,训练集有时会包含很多类标签被错误标记的噪声样例。集成学习算法AdaBoost对这些误标记噪声样例非常敏感并且容易产生过度拟合,从而对误标记噪声样例不具有鲁棒性。针对这一问题,本文提出了一种鲁棒的误标记噪声数据多分类方法Rob_MulAda。在Rob_MulAda中,形式地设计了一种基于噪声检测的多分类损失函数,并通过证明一个命题求解了其最小化问题;另外,给出了一种新的权值更新方式来克服误标记噪声样例的影响。在不同的噪声水平下将Rob_MulAda与其它几种相关方法进行了详细的实验比较,实验结果表明Rob_MulAda能够很好地改善AdaBoost在多分类问题中对误标记噪声样例的鲁棒性。(4)很多实际应用中收集的训练集往往具有不平衡的类分布。由于大多数基分类器学习算法被提出时都基于这一假设:训练集应该具有大体平衡的类分布,因此它们在类不平衡训练集上生成的分类器通常具有较差的泛化性能,尤其是对少数类样例不能有效地进行分类。鉴于集成学习在提高个体分类器性能方面的优势,本文尝试利用集成学习来提高分类器在类不平衡训练环境下的泛化性能,提出了一种基于进化欠抽样的Bagging集成方法EUS-Bag。在EUSBag中,为了使进化欠抽样EUS更加适合Bagging框架、以生成一些具有良好性能且多样化的个体分类器,本文设计了一种考虑了三个因素的新适应度函数,从而更好地将EUS和Bagging的优势进行结合。在类不平衡数据集上进行的比较实验表明,EUS-Bag能够有效地提高分类器对类不平衡数据的分类性能。
【图文】：

学习任务的种类括起来，数据挖掘领域研究的学习任务主要分为以下几类[1]：分类（classificatioegression）、聚类（clustering）、频繁模式挖掘（frequent pattern mining）。) 分类，直观上说，就是为每个新来的未知类别的对象指派一个明确的类标签，以确定该对象属于哪一个类别。形式上，给定一些具有类标签的训练样例组即训练集（training set）：1 1 2 2{( , ),( , ),...,( , )}tr N ND = x y x y x y，其中1 2( , ,..., i i i ix = x x x 1是属性的个数）是描述第 i （1 ≤ i ≤ N）个样例的属性元组（attribute tuple），iy样例的类标签（Y是该分类问题中所有不同类标签的集合），一般用 0、1、2 等，iy也称为该样例的目标属性（target attribute）。对于一个分类任务，可通过以完成。（1）分类器构造阶段。使用某种分类器学习算法 Learn（如决策树[27 29]、[30 32]等）在训练集trD上进行学习，以生成一个分类器C：( )trC = Learn D。该分属性的取值1 2_ , _ ,..., _pattri v attri v attri v与类标签y ∈ Y之间建立了一种函数关系1 2( _ , _ ,..., _ )p attri v attri v attri v；（ 2 ）分类阶段。当遇到一个新的未知类别的1 2 , ,..., )t t tpx x x时，分类器 C 根据该样例的各个属性值对它的类标签进行预测，从而类结果ty：( )t ty = C x。图 1.1 展示了分类任务的总体过程。

简单的说，就是把非常类似的对象放在同一个集合中，把存在较大差别的对象放 在 不 同 的 集 合中 ，下 面 给 出 聚 类 的形 式化 描 述 。 给 定N个 未 知类 别 的 样 例：D =1 2{ , ,..., }Nx x x =11 12 1 21 22 2{( , ,..., ),( , ,..., ),...,p px x x x x x1 2( , ,..., )}N N Npx x x，当采用像 k means[33 34]这样的经典聚类算法时，聚类的大体过程如下。（1）从样例集 D 中随机选择k （ k ≥ 2）个样例作 为初始的k个 簇中心：1 2, ,...,ko o o（,jo ∈ Dj = 1,2,...,k）， 则初始时 每个簇iCluster（1 ≤ i ≤ k）中只有一个样例io：{ }i iCluster = o，其中 k 是期望得到的簇数，即样例子集的数目；（2）对 D 中的每个样例jx（j = 1,2,...,N），使用某种距离度量（常用的是欧氏距离[1]）计算其与每个簇中心lo（l = 1, 2,...,k）之间的距离jld，并将jx分到与其最近的那个簇中心so（1 ≤ s ≤ k）所在的簇中： { }s s jCluster = Cluster ∪ x。对 D 中的所有样例分配完毕后，对得到的每个新簇的中心进行重新计算：1 1 11 2, ,...,ko o o；（3）将这些新的簇中心1 1 11 2, ,...,ko o o与之前的那些簇中心1 2, ,...,ko o o进行比较，若它们相同，则结束聚类过程，否则将1 1 11 2, ,...,ko o o作为当前的簇中心（即用1 1 11 2, ,...,ko o o更新1 2, ,...,ko o o）并重复执行步骤（2）和（3）。图 1.2 展示了聚类的总体过程，其中左边的子图表示根据随机选择的 3 个初始簇中心（用加号‘+’标示）对所有样例进行初次划分后所得到的结果，，中间的子图表示上面（2）、
【学位授予单位】：南京航空航天大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP181


本文编号：2525146