（计算机应用技术专业论文）新型学习技术中特征选择的研究与应用.pdf

上海大学硕l 学位论文 摘要 特征选择是当前人工智能领域，尤其是机器学习领域的研究热点之一。随着 人工智能和计算机科学技术的迅速发展，特征选择在理论和应用方面均得到了较 大的发展。特征选择不仪可以去除数据的冗余特征信息和无关特征信息从而提高 原始数据的质量，而且还可以大大降低数据挖掘的成本。 本文主要讨论新型学习技术如集成学习和半监督学习中特征选择的研究及 其相关应用。在集成学习方面，本文主要采用瓦信息的方法进行特征选择的研究 和分析。在半监督学习方面，本文采用k n n 作为基学习器，运用嵌入式的特征 选择方法进行了深入的探讨。 本文的主要工作在于以下两点：1 ) 在集成学习中引入了互信息准则，从而提 出并论证了基于互信息准则的选择性集成学习算法m i s e n ；2 ) 在半监督学习中， 改进了原有的半监督学习算法，并在特征选择的基础上提出了基于嵌入式特征选 择的c o t r a i n i n g 算法f e s c o t 。 在多个标准数据集上的实验证明，本文所提出的算法比原有算法有更好的性 能。同时，这些算法在大脑胶质瘤诊断和药物活性预报等现实问题上得到了很好 的应用，体现了良好的应用性。 关键词：特征选择、集成学习、半监督学习 j ：海大学硕七学位论文 a b s t r a c t f e a t u r es e l e c t i o ni sah o tt o p i ci na r t i f i c i a li n t e l l i g e n c e ，e s p e c i a l l yi nm a c h i n e l e a r n i n g a st h er a p i dd e v e l o p m e n to fa r t i f i c i a li n t e l l i g e n c ea n dc o m p u t e rs c i e n c e ， f e a t u r es e l e c t i o ng r o w sv e r yf a s tb o t hi ni t st h e o r ya n di ni t sa p p l i c a t i o n a l lo ft h e s e a r eb e c a u s ef e a t u r es e l e c t i o nh e l p sr e m o v et h er e d u n d a n ta n dn o n - r e l e v a n tf e a t u r e si n d a t as e t ss ot h a tt h eq u a l i t yo fd a t ai n c r e a s e sw h i l et h ec o s to fd a t am i n i n gd e c r e a s e s i nt h i st h e s i s ，w ef o c u so nr e s e a r c ha n da p p l i c a t i o no ff e a t u r es e l e c t i o ni nn o v e l l e a r n i n gt e c h n i q u e s ，s u c ha se n s e m b l el e a r n i n ga n ds e m i s u p e r v i s e dl e a r n i n g w h e n e n s e m b l el e a r n i n gi sd i s c u s s e d ，m u t u a li n f o r m a t i o ni su s e df o rf e a t u r es e l e c t i o n a n d w h e ni tf o c u s e so ns e m i s u p e r v i s e dl e a r n i n g ，k n ni sa d o p t e da st h eb a s el e a r n e r w h i l ee m b e d d e df e a t u r es e l e c t i o nm e t h o di su s e d t h em a i nw o r ki n t h i st h e s i sl i e s i nt h ef o l l o w i n gt w oj o b s o n ei sf e a t u r e s e l e c t i o no ne n s e m b l el e a r n i n g i nt h i sp a r t ，w ep r o p o s ean e wa l g o r i t h m ，s e l e c t i v e e n s e m b l el e a r n i n gb a s e do nm u t u a li n f o r m a t i o n ，m i s e n a n dt h eo t h e ri sf e a t u r e s e l e c t i o no ns e m i s u p e r v i s e dl e a r n i n g w ep r o p o s ean e wa l g o r i t h mn a m e df e s c o t , w h i c hc o m b i n e sa ni m p r o v e dc o t r a i n i n ga l g o r i t h ma n da ne m b e d d e df e a t u r e s e l e c t i o nm e t h o dt o g e t h e r e x p e r i m e n t sa r ec a r r i e do u to ns o m es t a n d a r dd a t as e t su n d e rt h eg u i d eo ft h e a l g o r i t h m sp r o p o s e di nt h i st h e s i s ，a n da l lo ft h e s es h o wt h e i rb e t t e rp e r f o r m a n c e m e a n w h i l e ，g o o dp e r f o r m a n c eo ft h e s ea l g o r i t h m sc a na l s ob ep r o v e dw h e ns o l v i n g p r o b l e m si nr e a lw o r d ，c l a s s i f i c a t i o no fb r a i ng l i o m aa n dp r e d i c t i o no fd r u ga c t i v i t y k e yw o r d s ：f e a t u r es e l e c t i o n ，e n s e m b l el e a r n i n g ，s e m i s u p e r v i s e dl e a r n i n g l i 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人己发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：查止导师签名： i i 铆正 上海大学硕j ：学位论文 第一章绪论 1 1 研究背景和意义 1 1 1 集成学习 集成学习( e n s e m b l el e a r n i n g ) 是一种通过使用多个个体模型来解决同一个 任务的学习方式，即由多个个体模型的输出共同决定新样本的预报结果的一种通 用技术。研究表明，集成学习可以有效地提高单个学习器的泛化能力 d i e t t e r i c h 1 9 9 7 ，z h o u2 0 0 2 a ，z h o u2 0 0 2 b 】，并且该学习方法能够有效避免过拟合现象。 利用多个学习器来解决同问题的想法由来已久，很难考证究竟是什么时候 开始在机器学习中出现集成学习的踪迹。但是，集成学习直到2 0 世纪9 0 年代才 逐渐受到重视。集成学习的发展主要应归功于以下两项重要工作 z h o u2 0 0 6b 】： 第项是l k h a n s e n 和p s a l a m o n 的工作 h a n s e n1 9 9 0 】。他们曾使用一组 神经网络来解决问题。但是除了按照常规的做法选择出最好的神经网络之外，他 们还尝试通过投票法将所有的神经网络结合起来求解。直观上来看，一组神经网 络中既有比较好的个体，也有比较差的个体，那么把这一组神经网络结合起来的 整体性能应该比最好的个体差一些而比最差的个体好一些。然而，实验却表明： 一组神经网络个体的集成效果比最好的个体神经网络的效果还好正是这一 超乎想象的实验结果使得集成学习引起了诸多学者的重视。在2 0 世纪9 0 年代初， 集成学习技术已被用到了很多应用领域，并取得了相当好的效果。 第二项是r e s c h a p i r e 的工作 s c h a p i r e1 9 9 0 。m k e a r n s 和l g v a l i a n t k e a r n s1 9 8 8 提出了弱学习算法与强学习算法的等价性问题，即是否可以 将弱学习算法提升成强学习算法。如果两者等价，那么在机器学习中，只要找到 一个比随机猜测略好的弱学习算法就可以将该弱学习算法提升为强学习算法，而 不必直接去找寻通常情况下很难获得的强学习算法。r e s c h a p i r e s c h a p i r e1 9 9 0 】 对这个重要问题作出了构造性证明，其构造过程就是b o o s t i n g 算法。值得注意 的是，原始的b o o s t i n g 算法要求事先知道学习算法的泛化能力的下界，而泛化 能力的下界通常是难以获知的。因此原始的b o o s t i n g 算法实际上并不能用来解 上海大学硕士学位论文 决真实问题。后来，yf r e u n d 和r e s c h a p i r e f r e u n d1 9 9 7 做了进一步的工作， 提出了a d a b o o s t 算法，该算法由于不再要求事先知道泛化下界，因而具有较强 的适用性。事实上，b o o s t i n g 已经是目前集成学习中研究得最深入的一个算法族， 而且其影响已经扩展到计算机视觉等很多其他领域。b o o s t i n g 算法发展到现在， 已得到了很多改进，并且各种不同的b o o s t i n g 算法也不断涌现。但其中具有代 表性的当属a d a b o o s t 算法，其他各种b o o s t i n g 算法均由a d a b o o s t 算法发展而 来。 以上两个工作为当今集成学习的深入研究和广泛应用奠定了坚实的理论基 础，开创了集成学习的新纪元。 1 1 2 半监督学习 在机器学习领域，绝大多数的机器学习方法都是有监督的学习方法。有监督 的机器学习方法忽略了未标记样本的作用，完全依赖带标记的训练样本。然而， 数据的标记则必须首先由人来手工完成这是一项非常费时而又费力的工作， 并且现实世界中未标记的样本多而已标记的样本却十分稀少，因此，虽然利用大 规模的带标记数据进行训练可以提高学习算法的准确度，但是有监督的学习方法 却越来越无法满足现实世界的要求。 半监督学习是一种利用标记样本和未标记样本共同完成学习任务的学习方 法，能够在一定程度上解决上述监督学习方法的弊端。目前，半监督学习已是模 式识别和机器学习中的一个重要研究领域。近年来随着机器学习理论在数据分析 和数据挖掘的实际问题中的应用，例如网页检索和文本分类、基于生物特征的身 份识别、图像检索和视频检索、医学数据处理等问题，半监督学习在理论和实际 应用研究中都获得了长足的发展。半监督学习研究主要关注在训练数据的部分信 息缺失的情况下，如何获得具有良好性能和推广能力的学习器。此处的信息缺失 涵盖了数据的类别标签缺失或者存在噪声、数据的部分特征维缺失等多种情况。 自2 0 世纪八九十年代以来国际机器学习界研究者在半监督学习研究领域已 展开了广泛而深入的研究和探讨。其涵盖的范围非常广泛，例如半监督学习的回 归问题 z h o u2 0 0 5 ；利用标记和特征维都缺失的数据集进行学习 l i t t l e1 9 8 6 ， 2 i ：海大学硕士学位论文 s c h a f e r1 9 9 7 ：利用少量正样本和大量未标记数据进行学习以及对于大量未标记 数据中已知只存在少量正样本的情况下对正样本的检沏, u l i u2 0 0 2 ，l e e2 0 0 3 等。 1 1 3 特征选择 特征选择是模式识别和机器学习领域的经典问题，自上个世纪6 0 年代起就 有学者对特征选择问题进行研究，但是当时主要从统计学和信息处理这两个角度 出发进行研究，而且所涉及到的通常都是特征数目不多的数据 l e w i s1 9 6 2 ， k i t t l e r1 9 7 8 ，c o v e r1 9 7 4 】。在过去的十余年中，特征选择方法已被逐渐运用于机 器视觉、文本分类、流数据处理、生物信息学、信息检索和时间序列预测等方面， 并且取得了一定的效果。目前，特征选择是机器学习领域的一个研究热点之一， 主要研究从一组原始特征中挑选出一个最有效的特征子集以达到降低特征空间 维数和增强模型泛化能力的目的。 机器学习中的特征选择可以定义为：已知某一特征集，从中选择一个特征子 集使评价标准最优 b l u m1 9 9 4 。该定义又可表述为： 给定一个学习算法l 、个数据集s ，其中数据集s 具有n 个特征 x 。x ：，x 妒，x 。和类别标记y ，s 的数据分布为样本空间d ，那么数据集s 的最 优特征子集x 删是使得某个评价准则最优的特征子集。 当前机器学习领域中的许多算法均与特征选择密切相关，例如集成学习和半 监督学习。而如何将学习算法和特征选择有机地结合在一起以设计出更加有效的 学习方法，是当前一个极其重要的研究方向。本文的研究重点是集成学习和半监 督学习中特征选择的研究与应用，目的在于将特征选择算法运用于集成学习和半 监督学习中，从而设计出具有良好泛化能力和较高学习效率的机器学习模型。 特征选择之所以倍受关注，其原因主要在于以下几个方面： ( 1 ) 特征选择是模式识别领域的一个关键因素。模式识别系统大致可以分为 以下5 个模块：数据获取、预处理、特征选择或特征提取、回归或分类以及后处 理。从分类的角度看，模式识别是把具体事物归到某个类别的过程，即先采用一 定数量的样本，根据它们之间的相似性进行分类器的设计，再利用所设计的分类 器对待识别的样本进行分类。分类的过程既可以在原始数据空间中进行，也可以 3 l 海大学硕1 ：学位论文 在部分原始数据空间中进行，还可以对原始数据进行变换，将原始数据映射到最 能反映数据本质的特征空间中进行。相比而言，后两者使得机器学习的设计变得 更为容易。它们通过更为稳定和本质的特征进行学习器的设计，不但完善了学习 器的性能，而且也使得研究对象的潜在关系更加容易被发现。由此可见，特征是 决定分类器设计的关键因素之- - g a n e s h a n a n d a m1 9 8 9 】。 ( 2 ) 无关特征和冗余特征在一定程度上影响着许多学习器的性能。研究表 明，大多数学习器训练所需的样本数目随无关特征的增多而呈指数型增长 b l u m 1 9 9 4 ，j a i n1 9 9 7 ，x i n g2 0 0 1 。b l u m 等的研究表明最近邻法的样本复杂度随无关 特征呈指数增长；决策数对于逻辑与概念的样本而言其复杂度随无关特征的增加 而线性增长，但是对于异或概念的样木确实呈指数增长；贝叶斯分类器虽然对无 关特征的存在不太敏感，但贝叶斯分类器的性能却对冗余特征的存在很敏感 l a n g l e y1 9 9 3 b l u m1 9 9 4 。可见，特征选择不仅可以减少计算复杂度、提高分 类精确度，而且有助于寻找更为合理的模型。 ( 3 ) 大规模数据处理问题的出现迫切需要对高维数据进行降维。第一、特征 数据不宜过高是机器学习领域中的一条经验性公理；第二、经过特征选择后的大 规模数据将大大减少学习器的训练和推理时间；第三、特征个数的减少不仅能够 降低数据的存储代价而且也能够减小数据的测量代价。 基于以上原因，特征选择在学术界引起了越来越广泛的关注。国内外各大研 究机构如北京大学、清华大学、香港大学、微软亚洲研究院、c a m b r i d g e 、s t a n f o r d 、 c m u c a o2 0 0 7 ，w o l f 2 0 0 5 ，z h a n g2 0 0 6 ，h e2 0 0 5 1 等都展开了相关的研究。 1 2 课题来源和研究目的 本文的研究内容主要来源于国家自然科学基金资助项目( 项目号：2 0 5 0 3 0 1 5 ) 和上海市科委“创新行动计划”重大项目( 项目号：0 7 d z l 9 7 2 6 ) 。 本文主要在特征选择已有工作的基础上研究集成学习和半监督学习中特征 选择的应用。通过特征选择方法去除原始数据中的冗余特征和无关特征的工作不 仪可以达到提高数据质量和精简数据的目的，而且还可以提高学习器的泛化能力 和预报精度。该研究成果在化学、材料、气象、地震、医疗、生物和信息安全等 领域具有广阔的研究和应用前景。 4 、t - 海大学硕- l 学位论文 1 3 研究内容及安排 1 3 1 研究内容 特征选择虽然是一个复杂的过程，但却是数据建模的一个重要部分，在一定 程度上影响着模型的性能。从近年来在特征选择方面的研究来看，建模数据中无 关特征和冗余特征的去除不仅可以缩减学习规模，而且能够更为清晰地显现数据 之间的潜在关系，从而达到提高模型性能和学习效率的目的。因此，本文将从以 下两个方面展开： ( 1 ) 对基于特征选择算法的选择性集成学习进行研究。该研究的基本思想如 下所述：首先训练集成学习的各个个体子模型，然后运用特征选择算法对各个个 体子模型进行选择，最后对被选中的个体子模型进行集成学习。选择性集成学习 的意义在于提高了学习器的泛化能力，但是该方法也存在一定的缺陷，如：计算 效率比较低。 在这方面新算法的研究中，本文提出基于互信息准则的选择性集成学习算法 m i s e n ( s e l e c t i v ee n s e m b l el e a r n i n gb a s e do nm u t u a li n f o r m a t i o n ) 。该算法有效 地剔除了集成学习中泛化能力较差的个体学习器，从而提高了集成学习的学习效 率。 ( 2 ) 对基于特征选择的半监督学习进行研究。半监督学习是目前模式识别和 机器学习领域的研究热点，而近年来更是随着机器学习在网页分类、邮件过滤和 文本分类等方面的应用而受到了广泛的关注。然而，在半监督学习的研究中，通 常情况是样本数据中存在大量的冗余特征信息，而冗余信息会降低学习器的泛化 能力，所以如何通过降低冗余特征信息对半监督学习的影响就成了一个需要深入 研究的课题。 在这方面新算法的研究中，本文提出基于预报风险准则特征选择的半监督学 习算法f e s c o t ( f e a t u r es e l e c t i o nf o rc o t r a i n i n g ) 。该算法有效地提高了协同学 习c o t r a i n i n g 算法的学习效率和学习效果。 j ：海大学硕：f ：学位论文 1 3 2 论文结构安排 本文共分为五章，各章内容安排如下： 第一章概括地阐述集成学习、半监督学习和特征选择的研究背景及意义。集 成学习和半监督学习是当前机器学习领域的研究热点。集成学习不仅能够有效地 提高学习器的泛化能力，而且能够有效地避免过拟合现象；半监督学习则能够有 效地解决当前未标记样例多而已标记样例少的问题；而特征选择方法在集成学习 和半监督学习中的运用则不仪可以缩减学习规模，而且能够提高模型的性能和学 习效率。 第二章系统阐述集成学习和半监督学习中特征选择的相关工作和研究现状。 通过对集成学习中个体训练子集的特征选择和选择性集成学习的介绍，阐述了集 成学习中特征选择的相关工作；通过对基于最优化多目标的半监督学习的特征选 择算法和基于谱图理论的半监督学习的特征选择算法的介绍，阐述了半监督学习 中特征选择的研究现状。 第三章详细阐述互信息准则在集成学习中的研究和应用。本章详细介绍了基 于互信息准则的集成特征选择算法m i f e b ( m u t u a li n f o r m a t i o nb a s e df e a t u r e s e l e c t i o nf o rb a g g i n g ) 和基于互信息准则的选择性集成学习算法m i s e n 。在算 法详述的基础上，这两个基于互信息准则的集成学习算法被成功地运用在了解决 大脑胶质瘤的诊断问题上，从而印证了这两种基于互信息特征选择的集成学习算 法的优越性。 第四章详细阐述基于嵌入式特征选择的半监督学习的研究及应用。本章通过 对c o t r a i n i n g 算法的改进提出并且验证了基于嵌入式特征选择的c o t r a i n i n g 算 法f e s c o t 。该新算法在药物活性预报的问题上充分显现了优越性能。 第五章总结全文。 6 上海大学硕士学位论文 第二章相关工作 弟一早才日大上作 2 1 集成学习及其特征选择 2 1 1 集成学习 国际上对集成学习的研究已经成为当前机器学习方面的一个研究热点。由 于集成学习中利用多个学习器可以获得比仪仪使用单一学习器更强的泛化能力， 因此，一种直观的想法就是，也许可以通过使用大量的个体学习器来获得更好的 性能。但是在实际的研究中存在两个问题：第一、从集成学习的个体生成过程来 看，由于许多数据都是高维的，而高维数据中往往既存在无关特征也存在冗余特 征，这些特征在一定程度上影响学习器的性能。第二、从集成学习的结论合成方 法来看，一方面，使用更多的学习器将导致更大的计算和存储开销；另一方面， 当个体学习器的数目增加之后，学习器之间的差异将越来越难以获得 z h o u 2 0 0 6 】。因此集成学习中的这两个方面非常值得研究。目前，许多研究者己从集 成学习的理论分析、实现方法的设计和实际应用等几个方面出发展开了深入的研 究。集成学习在实现方法上可以分为个体生成和结论合成两部分。对于后者，分 类器主要采用多数投票法；对于前者，最流行的技术是b o o s t i n g 和b a g g i n g b a u e r 1 9 9 9 ，z h o u2 0 0 2 b ，b r e i m a n1 9 9 6 】。 2 1 1 1b o o s t i n g 算法介绍 19 9 5 年，f r e u n d 和s c h a p i r e f r e u n d19 9 5 提出了a d a b o o s t ( a d a p t i v eb o o s t i n g ) 算法，该算法的优点在于可以非常容易地应用于实际问题中，是b o o s t i n g 算法 中最典型的一个算法。因此下面以a d a b o o s t 算法为例，对b o o s t i n g 算法进行简 单介绍。 a d a b o o s t 算法的主要思想是首先给定某一弱学习器算法和某- - t ) l l 练数据集 ( 数据集是向量，对于分类问题为某一分类标记，对于回归问题则为一连续数 值) 。在算法的初始阶段，每一个训练样本均被赋以相等的权重，然后运用某一 7 j ：海大学硕：仁学位论文 给定的学习算法对训练数据子集进行t 轮模型的训练，而每次训练之后对训练 失败的样例赋以较大的权重。该策略使得学习算法在后续的学习中集中对比较难 的训练样例进行学习，从而得到一个预测函数序列，其中也有一定的权重。预测 效果比较好的预测函数所赋以的权重比较大，反之则比较小。最终的预测函数h 通过对分类问题采用有权重的投票方式，对回归问题采用加权平均的方法对新样 例进行预测。对于两类问题的a d a b o o s t 的具体算法如图2 1 所示： 输入：弱学习算法： x 表示样本空间； y 表示样本类别标识集合，y = ( 1 ，一1 ) ； s = ( x 。，y 。) ，( x 2 ，y ：) ，h ，y ) 表示样本训练数据集， 其中 x j x ，y f y ，i = 1 , 2 ，n ； 过程： 1 、初始化样本权重：对每一个( x iy ，) s ，令d l ( x i , y ，) = 1 n 。 2 、f o rt = 1 ，2 ，t ( t 为最大训练轮数) ； 1 ) 调用弱学习算法，获得弱分类器h ，：x 一】，； 2 ) 计算占，=d ，( 工，y ，) ； 若占， 0 5 ，选择口，= 去l n ( 1 一c t ) i t f 若占，0 5 ，删除本轮生成的弱分类器，转至步骤2 ； 3 ) 更新样本权重 州= 警e - a 矿i f 糍t ( x im ) = y ；i d ，( i ) e x p ( 一口，y ，h ，( x = _ _ - i _ - _ - _ - i _ _ i - _ _ - _ _ i _ _ _ i _ - _ i _ - _ _ _ - _ _ _ _ _ 。- _ 。_ - 。- - 一 zt ， 此处z ，是归一化因子，使得口( z ，y ，) = 1 ； 上海大学硕士学位论文 7 3 、 最终获得强分类器：( 石) = j 咖( 口，h ，( x ) ) 。 输出：强分类器h ( x ) 。 图2 1 对于两类问题的a d a b o o s t 算法 上述算法中，口，是第t 轮训练后产生的弱分类器的性能评价因子，该因子 由作用于样本数据集产生的分类错误的样本权重之和来决定。虽然b o o s t i n g 算 法能够有效地提升弱分类器为强分类器，但是人们总是追求更为合理，更为有效 的算法来解决实际问题。 2 1 1 2b a g g i n g 算法介绍 1 9 9 6 年，b r e i m a n 最先将b o o t s t r a p 算法运用于集成学习，并结合该算法提 出了与集成学习算法b o o s t i n g 相似的集成学习算法一b a g g i n g b r e i m a n1 9 9 6 】。 b a g g i n g 的基础是重复取样( b o o t s t r a ps a m p l i n g ) e f r o n1 9 9 3 。图2 2 为b a g g i n g 算法在分类问题上的流程图。就分类问题而言，b a g g i n g 算法的基本思想如下： 首先采用b o o t s t r a p 技术产生t 个样本子集，然后在每个样本子集上训练分类器， 最后采用多数投票法对分类器的分类结果进行集成，从而得到最终的分类模型。 输入：初始训练数据集s ； 基分类器i ； 循环代数t ； 过程： 1 、f o ri = lt ot 2 、 利用b o o t s t r a p 方法，从s 中得到一个训练样本子集s ； 3 、 c f = i ( s ) ； 4 、， 5 、c + ( 戈) = 得票最多的类别； 输出：分类器c 。 图2 - 2b a g g i n g 算法 9 e 海大学硕。 ：学位论文 b a g g i n g 方法通过重新选取训练数据集而增加了集成个体之间的差异度，从 而提高了模型的泛化能力。由等概率重复取样b o o t s t r a p 产生的样本数据集中， 初始训练数据集中的某些样本可能在新的训练子集中多次出现，而另外一些样本 则可能一次也不出现。 b r e i m a n1 9 9 6b 指出，稳定性是b a g g i n g 能否发挥作用 的关键因素。b a g g i n g 算法能在一定程度上提高预测结果不稳定的基学习器( 如： 决策树、神经网络等) 的预测精度，而对于稳定的基学习器( 如：k n n 、n a i v eb a y e s 等) 而言，b a g g i n g 算法却效果不很明显，有时甚至还会出现预测精度降低的情 况。 由上述可知，b a g g i n g 与b o o s t i n g 的区别在于以下三点： ( 1 ) b a g g i n g 对训练数据集的选择是随机的，各轮迭代中训练数据集之间相互 独立；而b o o s t i n g 对训练数据集则不独立，各轮迭代中训练数据集的选择与前 面各轮迭代的学习结果相关。 ( 2 ) b a g g i n g 算法的各个预测函数没有权重，而b o o s t i n g 算法的各个预测函 数则有权重。 ( 3 ) b a g g i n g 的各个预测函数可以并行生成，而b o o s t i n g 的各个预测函数只 能顺序生成。 2 1 2 集成学习中的特征选择 在集成学习中引入特征选择已是当前机器学习中的一大研究热点，其研究成 果己被广泛地应用于提高单个学习器的泛化能力。集成学习因其个体学习器的误 差分布于不同的输入空间而使得集成学习取得了比较好的效果 d i e n e r i c h1 9 9 8 】。 b a g g i n g 算法和b o o s t i n g 算法是目前比较流行的两种集成学习方法 b r e i m a n 1 9 9 6 ，b a u e r1 9 9 9 。这两种算法的性能提高主要来自于对集成学习中子模型训练 数据集的重复取样 b r o w n2 0 0 5 】。 特征选择方法主要可以分以下三类：滤波式模型、包装式模型和嵌入式模型。 其中，滤波式模型是一种与学习器无关的特征选择方法，而后两种特征选择方法 则依赖于相应的学习器，但最近新提出的嵌入式模型的计算复杂度要远远低于包 装式模型。 1 0 上海大学硕士学位论文 目前，已有很多将特征选择应用于构建新的集成学习方法的研究。例如： h o 首先提出了构建决策森林的随机子空间方法 h o1 9 9 8 】，后来g u n t e r 等人又提 出了该方法的改进方法 g u n t e r2 0 0 4 ；o p i t z 提出了基于遗传算法的特征选择的 集成学习算法 o p t i z1 9 9 9 ；o l i v e i r a 等人运用了多目标的遗传算法研究集成学习 中的特征选择 o l i v e i r a2 0 0 2 ；b r y l l a 等人提出了基于随机特征选择的特征 b a g g i n g 方法 b r y l l a 2 0 0 3 ；t s y m b a l 等人先研究了集成特征选择方法的不同搜索 策略 t s y m b a l2 0 0 3 ，后又提出了运用遗传算法进行集成特征选择 t s y m b a l 2 0 0 5 。从总体上看，以上基于特征选择的集成学习方法都是通过产生不同的特 征子集来构建不同的个体模型 b r o w n2 0 0 5 ，但是b a g g i n g 算法和b o o s t i n g 算法 则与这些不同这两种算法均通过产生不同的样本子集来构建不同的个体学 习模型。然而，目前却很少有人在重复取样的基础上进行特征选择方法的研究。 针对这一点，我们研究了b a g g i n g 算法中的特征选择技术，并由此提出了若干新 的算法。 特征选择在b a g g i n g 算法上的应用主要有以下两个方面。一方面是对 b a g g i n g 算法中通过由b o o s t r a p 方法所产生的个体子集进行特征选择，从而提高 个体模型之间的差异度和个体模型的精度。该研究主要运用嵌入式特征选择方法 和滤波式特征选择方法对在b a g g i n g 基础上所产生的个体学习器进行最优特征 子集的选择 l i2 0 0 6 ，l i u2 0 0 6 。 b a g g i n g 方法中特征选择应用的另一个方面在于对集成学习中个体学习器的 选择，也就是周志华等人提出的选择性集成学习 z h o u2 0 0 2 a 】。周志华等人提出 的基于遗传算法的选择性集成学习算法g a s e n 通过遗传算法对b a g g i n g 的个体 学习器进行选择，从而取得了比较好的结果 z h o u2 0 0 2 a 。这表明选择部分子模 型进行集成学习的效果优于运用所有子模型进行集成的效果。c a r u a n a 等人后来 也证明了这一说法的正确。| 生 c a r u a n a2 0 0 4 ，c a r u a n a2 0 0 6 。g a s e n 算法取得了比 较好的效果，但是该算法的计算复杂度比较高。针对这一点，本文提出了基于互 信息方法的选择性集成学习算法m i s e n e l i2 0 0 7 。 本章将分别从以上两个方面就目前国内外在集成学习的特征选择方面的研 究现状进行介绍并总结。 上海大学硕上学位论文 2 1 2 1 个体子集的特征选择 目前，许多研究成果已经证明集成学习方法能够有效地提高单个学习器的泛 化能力 d i e n e r i c h1 9 9 8 ，b r e i m a n1 9 9 6 ，b a u e r1 9 9 9 】，并且当运用s v m ( 支持向 量机) 作为集成学习子模型的学习器时效果尤为明显 l i2 0 0 4b 。v a l e n t i n i 和 d i e t t e r i c h 指出，通过降低s v m 子模型的错误率能够有效地降低基于s v m 的 b a g g i n g 学习的错误率 v a l e n t i n i2 0 0 4 。特征选择方法中，滤波式方法和卷积方 法运用较为广泛 g u y o n2 0 0 3 ，y u2 0 0 4 ，l i u2 0 0 5 】。目前，虽然已有研究人员将特 征选择方法运用于集成学习，并且也获得了比较好的效果 h o1 9 9 8 ，g u n t e r2 0 0 4 ， o p t i z1 9 9 9 ，o l i v e i r a2 0 0 2 ，b r y l l a2 0 0 3 ，t s y m b a l 2 0 0 3 ，t s y m b a l 2 0 0 5 ，但是其中的大 部分工作仪仅只局限于运用特征选择方法产生多样性的个体子模型。鉴于此，李 国正等人提出对b a g g i n g 中数据子集进行特征选择从而提高b a g g i n g 算法的集成 学习效果，并由此提出了两个新算法p r i f e b 和m i f e b l i2 0 0 6 ，l i2 0 0 6b 】，前 者是基于预报风险准则的嵌入式特征选择，后者是基于互信息准则的集成特征选 择算法。这两个算法的基本思想可用图2 3 所示的框架f e b ( f e a t u r es e l e c t i o nf o r b a g g i n g ) 表示首先利用b o o t s t r a p 进行子集生成，然后在子集上进行特征选 择，再在经特征选择后的子集上分别建立子模型，最后集成所有个体子模型。 研究表明，特征选择既能减少数据中的无关特征，又能去除数据中的冗余特 征，从而提高了个体模型的泛化能力。同时，因各个体模型中进行特征选择时所 删除的特征不尽相同而增加了集成学习中个体子模型之间的差异。由文献 d i e t t e r i c h1 9 9 8 可知，通过提高个体模型的正确率或者增加个体模型之间的差异 度均能有效地提高集成学习的性能，这也进一步证明了通过对个体子集进行特征 选择确实能够有效地提高集成学习技术的泛化能力。 1 2 上海大学硕士学位论文 输入：训练数据集s ，( z 1 ，x 2 ，工dc ) ； 个体子模型的个数t ； 学习器l ； 过程： f o r k = 1 ：t 运用b o o t s t r a p 取样算法在s ，上产生训练子集s 庸； 利用特征选择从训练子集如中选取其最优特征子集，从而得最优训练 子集s 啦删； 在最优训练子集s 腈叫妇删上训练个体子模型k ； e n d 输出：集成模型n 。 图2 - 3b a g g i n g 子集特征选择的f e b 框架 2 1 2 2 选择性集成学习 概括地说，集成学习方法( 如b a g g i n g 和b o o s t i n g 方法) 的基本原理和思想 是对学习过程中所产生的所有个体子模型进行集成。周志华等人指出如果以其中 部分个体子模型代替所有个体子模型进行集成，那么集成学习的性能将有所提 高，由此提出了一种新的学习方法即选择性集成学习。选择性集成学习的基本思 。 想是根据特定的评测方法在所有个体模型中选取部分个体模型进行集成学习 【z h o u2 0 0 2 a 。 周志华等人为了验证选择性集成学习的思想提出了g a s e n 算法基于遗 传算法的选择性集成学习算法。实验和研究均证明，该算法能够取得比经典集成 学习算法b a g g i n g 算法和b o o s t i n g 算法性能更优的模型 z h o u2 0 0 2 a 。该算法的 核心思路是首先通过b o o t s t r a p 方法产生多个学习个体，然后通过遗传算法选择 最优的若干个体子模型，最终形成集成模型。g a s e n 算法如图2 4 所示。 e 海大学硕士学位论文 输入：数据集d ( l ，厶，厶，t a r g e t ) 说明： c ：原始数据集的特征数； d ( l ，以，厶，t a r g e t ) ：输入原始训练集，t a r g e t 为目标值； 巩：训练集； d 抑：验证集； 仇：测试集； a ：预报精度； m o d e l ：训练模型； t r a i n ( d ) ：以d 为训练集训练模型函数； g a ( ) ：用遗传算法来选择用于集成的个体； p o p u l a t i o n ：集成的个体数； 过程： l 、f o ri = 1 ：p o p u l a t i o n 1 ) 用b o o t s t r a p 方法从原始训练集以中得到一个新的训练集 d 肛( i ) ，d 扩( f ) 的样本个数是珥的四分之三； 2 ) 用上一步得到的训练集d 护( f ) 训练个体模型， m o d e l ( i ) = t r a i n ( d 护( f ) ) ； e n d 2 、运用验证集d 和遗传算法g a ( ) 对p o p u l a t i o n 个个体模型进行选择，选 择出p o p u l a t i o n n e w 个个体模型m o d e l ( j ) 参加最后集成。j 表示将被 选择参加最后集成的个体模型的序号；p o p u l a t i o n n e w 表示被选择参 加最后集成的总个体数。 3 、f o rj = 1 ：p o p u l a t i o n n e w 用m o d e l ( j ) 预报测试集仇得到预报结果r e s u l t ( j ) ， r e s u l t ( j ) = t e s t ( d 耙，m o de l ( j ) ) ； e n d 1 4 一j ：海大学硕十学位论文 将p o p u l a t i o n n e w 个个体的预报结果r e s u l t ( j ) 按照多数投票法得到最 终的预报结果朋础倒，从而得到最终的预报精度彳韶一伽，。 输出：算法预报精度彳忙一例。 2 1 3 进一步的想法 图2 4g a s e n 算法 集成学习中特征选择的研究是当前机器学习领域的一个研究热点。目前，已 有许多研究人员和学者在这一方向展开了深入的研究。 就个体子集的特征选择而言，由于对集成个体中的训练数据进行了特征选 择，从而去除了训练数据中的无效特征和冗余特征，并同时扩大了各个集成个体 之间的差异度。因此，本文第三章将引入m i f e b 算法，并详细讨论该算法的原理及 应用。 就选择性集成学习而言，周志华等人提出的g a s e n 算法虽然具有一定的优 越性，但是由于遗传算法的计算量比较大，因而g a s e n 算法的计算复杂度比较 高。因此，本文提出利用计算量比较小的互信息准则进行个体子模型的选择，从 而提出了基于互信息的选择性集成算法m i s e n l i2 0 0 7 。本文第三章将详细讨 论m i s e n 算法的原理及应用。 2 2 半监督学习及其特征选择的研究 2 2 1 半监督学习 半监督学习己成为当前机器学习领域的又一研究热点，并且新算法不断涌 现。这里主要介绍三种半监督学习算法：e m ( e x p e c t i o n m a x i m i z a t i o n ) 算法、 c o - t r a i n i n g 算法和t s v m ( t r a n s d u c t i v es u p p o r tv e c t o rm a c h i n e s ) 算法。 ( 1 ) e m 算法是一种迭代爬山算法，用于解决在给定不完全数据的条件下求 解极大似然估计的问题。算法主要分为两步，首先运用当前模型估计不完整数据 的缺少值，然后再运用这些估计数据来改进模型。e m 算法 d e m p