（计算机应用技术专业论文）特征选择算法研究及其在盾构隧道工程中的应用.pdf

上海大学硕士学位论文 摘要 特征选择是模式识别系统中非常关键和重要的部分，它不仅对于人类开发 和认识未知世界、找到未知事物的联系能够发挥较大的作用，而且对于构造一 个实际的模式识别系统也起着至关重要的作用。大规模数据的不断涌现，对已 有的特征选择算法提出了严峻的挑战，这是因为与特征选择相关的许多问题都 是n p 难问题，因此要找到最优特征子集，往往是不切实际的。然而研究人员 总是尽量提高特征选择的性能，从而找到一个接近最优的特征子集。本文在特 征选择算法设计以及盾构地铁隧道施工复杂系统的数据挖掘中进行了一些研 究和探讨，论文的主要工作和贡献有以下几个方面： 1 提出了一种基于自适应遗传算法和支持向量机的特征选择算法 a g a s v m 。该方法利用自适应遗传算法a g a 进行最优特征子集的搜索，用支 持向量机s v m 作为特征子集评价方法。a g a s v m 用于盾构地铁隧道施工质 量风险致险因子的选取，实验结果表明了a g a s v m 提高了特征选择的效率。 2 提出了一种用于解决“类标具有约束条件的约束性多分类问题”的模型 r m c m 和一种混沌离散粒子群算法c b p s o 。将c b p s o 与r m c m 模型结合， 得到一种基于c b p s o 特征选择的r m c m 模型c b p s o r m c m 。将 c b p s o r m c m 应用于盾构地铁隧道施工管片衬砌过程中的管片选型预测，实 验结果表明该模型的分类准确率比r m c m 有明显提高，且选取出的关键特征 集与领域专家的意见基本一致，为今后的管片选型预测提供了一种参考方法。 3 分析了f i l t e r 和w r a p p e r 两种模式的优缺点，提出了一种适用于回归的 基于层次聚类算法和偏最小二乘( p l s ) 的特征选择方法。该方法将原始特征 根据相关度进行聚类；同时，又用p l s 对每个特征的预测能力进行排序，最后 根据特征聚类和特征排序的结果生成最优特征子集( 称最优回归子集) ，使所 得最优回归子集中特征问的相关性低( 含冗余特征少) 并且绝大部分特征的预 测能力较强。该特征选择方法应用于盾构地铁隧道施工地面沉降的回归预测 中，实验结果表明所得最优s v r 和最优p l s 模型的回归精度、预测精度以及 计算效率均有明显提高。 关键词：特征选择；遗传算法：粒子群算法；聚类算法；偏最小二乘；盾构。 v 上海大学硕上学位论文 a b s t r a c t f e a t u r es e l e c t i o ni sav e r yp i v o t a la n di m p o r t a n tp a r ti nt h ep a t t e r nr e c o g n i t i o n s y s t e m i tp l a y sab a s i l i cr o l en o to n l yf o rd e v e l o p i n ga n du n d e r s t a n d i n gt h e u n k n o w nw o r l da n df i n d i n gt h er e l a t i o nb e t w e e nt h eu n k n o w nt h i n g s ，b u ta l s of o r c o n s t r u c t i n gar e a lp a t t e r nr e c o g n i t i o ns y s t e m a st h eh u g ed a t ac o m ef o r t h c o n s t a n t l y , m a n ye x i s t i n g f e a t u r es e l e c t i o na l g o r i t h m sm e e ta u s t e r ec h a l l e n g e b e c a u s em a n yp r o b l e m sa b o u tf e a t u r es e l e c t i o na r en p - h a r dp r o b l e m ，s oi ti s a l m o s ti m p o s s i b l et of i n dt h eb e s tf e a t u r e s u b s e t t h i sp a p e rh a sd o n es o m er e s e a r c h a n dd i s c u s s i o na b o u td e s i g no ff e a t u r es e l e c t i o na l g o r i t h m sa n dd a t am i n i n go f c o m p l i c a t e ds y s t e mi nt h es h i e l dt u n n e l i n gc o n s t r u c t i n gp r o c e s s t h e m a i nw o r k a n dc o n t r i b u t i o ni nt h ep a p e ra r ea sf o l l o w s ： 1 af e a t u r es e l e c t i o nm e t h o dw h i c hc o m b i n e sa d a p t i v eg e n e t i ca l g o r i t h mw i n l s u p p o r tv e c t o rm a c h i n c ( a g a s v m ) i sp r o p o s e d t h i sm e t h o ds e a r c h e st h eb e s t f e a t u r es u b s e tw i t ha d a p t i v eg e n e t i ca l g o r i t h m ( a g a ) a n de v a l u a t e st h ef e a t u r e s u b s e td e p e n d so nt h es u p p o r tv e c t o rm a c h i n e ( s v m ) t h ea g a s v mm e t h o di s u s e dt os e l e c tt h ek e yf a c t o r so fq u a l i t yr i s ki nt h es h i e l dt u n n e l i n gc o n s t r u c t i n g p r o c e s s ，a n dt h er e s u l to fe x p e r i m e n ts h o w st h a ta g a s v mc o u l di m p r o v et h e e f f i c i e n c yo f f e a t u r es e l e c t i o n 2 ar e s t r i c t i v em u l t i c l a s s e sm o d e l ( r m c m ) a n dac h a o t i cb i n a r yp a r t i c l e s w a r mo p t i m i z a t i o na l g o r i t h m ( c b p s o ) c o m b i n gc b p s ow i t l lr m c m ，an e w f e a t u r es e l e c t i o nm o d e lc a l l e dc b p s o - r m c mi sp r o p o s e d t h ec b p s o r m c mi s u s e dt op r e d i c t i n gt h es e l e c t i o no fs e g m e n tt y p ei ns h i e l dt u n n e l i n gp r o c e s s ，a n dt h e r e s u l to fe x p e r i m e n ts h o w st h a tc l a s s i f i c a t i o na c c u r a c yo ft h i sm o d e li so b v i o u s l y h i g h e rt h a nr m c m ；m e a n w h i l e ，t h es e l e c t e dk e yf e a t u r es u b s e ti sa ss i m i l a ra st h e o n ew h i c hd o m a n i a le x p e r t sd o t h ec b p s o - r m c mm o d e la l s op r o v i d e sau s e f u l r e f e r e n c e dm e t h o df o r t h es e l e c t i o no fs e g m e n tt y p ei nt h ef u t u r e 3 a f t e ra n a l y z i n gt h ea d v a n t a g ea n dd i s a d v a n t a g eo ff i l t e rp a t t e r na n dw r a p p e r p a t t e r n ，an e wf e a t u r es e l e c t i o nm e t h o dw h i c h i ss u i t a b l ef o r t h er e g r e s s i o np r o b l e m b a s e do nh i e r a r c h i c a lc l u s t e r i n ga n dp a r t i a ll e a s ts q u a r e si sp r o p o s e d t h i sm e t h o d f i r s t l yc l u s t e r sa l lt h ef e a t u r e sd e p e n d i n go nt h er e l e v a n c eo ff e a t u r e s t h e ns o r t s f e a t u r e sa c c o r d i n gt ot h ep r e d i c t i v ea b i l i t yo fe a c hf e a t u r e a tl a s tp r o d u c tt h eb e s t f e a t u r es u b s e tc a l l e dt h eb e s tr e g r e s s i o ns u b s e t t h er e l e v a n c eo fa n yt o wf e a t u r e s i n c l u d i n gt h eb e s tr e g r e s s i o ns u b s e ti sl o w t h ep r e d i c t i v ea b i l i t yo ft h em o s to f f e a t u r e si nt h eb e s tr e g r e s s i o ns u b s e ti sh i 曲t h em e t h o di su s e di nt h er e g r e s s i v e p r e d i c t i o no fg r o u n ds e d i m e n t a t i o ni ns h i e l dt u n n e l i n gp r o c e s s t h es i m u l a t i o n 上海大学硕士学位论文 e x p e r i m e n ts h o w st h a tt h eo p t i m a ls v ra n do p t i m a lp l sm o d e l sh a v eh i g h e r p r e c i s i o no fr e g r e s s i o na n dp r e d i c t i o n ，a sw e l la sl o w e rt r a i n i n gt i m e k e y w o r d s ：f e a t u r es e l e c t i o n ；g e n e t i ca l g o r i t h m ；p a r t i c l es w a r mo p t i m i z a t i o n ； c l u s t e r i n ga l g o r i t h m ；p a r t i a ll e a s ts q u a r e s ；s h i e l d v i i 上海大学硕上学位论文 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工 作。除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已发表或撰写过的研究成果。参与同一工作的其他同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：丑斗日期掣 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有权保留论文 及送交论文复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) i i 上海大学硕士学位论文 第1 章引言 1 1 问题的提出及其研究意义 随着计算机和数据库技术的飞速发展，越来越多的大型应用系统积累了大 量数据；同样，i n t e m e t 上也积累了海量数据。在大量的数据背后往往隐藏着 许多重要信息，而这些重要信息可以很好地支持人们的决策。 数据挖掘( d a t am i n i n g ) 作为数据库、机器学习和统计学等多学科的交叉， 被认为是解决上述问题、使数据得到有效利用的一种重要方法和手段，并显示 出了强大的生命力。研究人员和相关从业人员都发现，要有效地进行数据挖掘， 数据预处理是必不可少的。 在很多应用背景如基因数据分析、计算机视觉等方面都面临数据集规模很 大的难题，给数据分析和知识获取带来了难度。数据集的大小可以从两方面衡 量：特征的数目和样本的数目。如果用于分析的数据包含成千上万的特征，其 中可能大部分特征都是不相关或冗余的，而有用的特征很可能会被淹没在大量 无用特征之中。 为了提高决策的有效性，往往需要对原始数据集进行降维处理，其目的是 降低计算时间、提高决策精度。数据降维常用的两类方法是特征选择和特征提 取。特征提取是指将原有的特征空间进行某种形式的变换，以得到新的特征。 最常见的特征提取方法有：主成份分析( p r i n g c i p a lc o m p o n e n ta n a l y s i s ，p c a ) ， 因子分析( f a c t o r a n a l y s i s ，f a ) ，独立成分分析( i n d e p e n d e n tc o m p o n e n t a n a l y s i s ， i c a ) 【1 】以及判别分析( d i s 嘶m i n a n t a n a l y s i s ，d a ) t 2 】等。该类方法的降维效果较 明显，但是特征的理解性很差。而特征选择是从原始特征集中选择使某种评估 标准最优的特征子集，以求获得最小的特征子集使得分类或回归达到和特征选 择前近似甚至更好的预测效果。理论分析和实践证明：通过删除一些冗余或不 相关特征，可简化模型、提高预测精度、降低计算复杂度。 特征选择是统计学领域的经典问题，自上个世纪6 0 年代起就有学者对特 征选择问题进行研究，但当时主要是从统计学的角度进行研究，而且所涉及的 问题中包含的特征数目不多。同时，特征选择也是机器学习领域的重要问题， 对机器学习领域的所有问题都有重大意义，包括文本分类、数据挖掘、生物信 息学、计算机视觉、信息检索、时间序列预测等。在一个学习算法通过训练样 本对未知样本进行预测之前，必须决定哪些特征应该采用，哪些特征应该忽略。 在机器学习领域，学习算法方面己经开展了大量的研究，但特征选择方面的研 上海大学硕士学位论文 究则相对较少。自9 0 年代以来，特征选择方面的研究引起机器学习领域学者 前所未有的重视，主要原因有以下几个方面： 1 许多学习算法的性能受到不相关或冗余特征的负面影响。已有的研究 结果表明，大多数学习算法所需训练样本的数目随不相关特征的增多成指数性 增长。l a n g l e y 等人的研究表明最近邻法的样本复杂度随不相关特征成指数增 长，其他归纳算法也基本具有这一属性 _ 7 6 】。例如，决策树对于逻辑与概念的样 本复杂度随不相关特征线性增加，但对于异或概念的样本却是呈现指数增长； 贝叶斯分类器虽然对不相关特征的存在不敏感，但其性能却对冗余特征的存在 很敏感。因此，特征选择对不同情况下的学习算法都有重要作用。选择好的特 征不仅可以减小计算复杂度，提高预测精度，而且有助于寻找更精简更易理解 的算法模型。 2 大规模数据处理问题的不断出现。所谓大规模，一方面指样本数目的 庞大；另一方面指描述样本的特征维数高。数据挖掘的发展对大规模数据处理 的研究提出了迫切的要求，如信息检索，遗传基因数据分析等。特征空间的维 数不宜过高，这已经是机器学习领域中一条经验性的“公理”，否则将导致两 方面的问题，一个是“维数灾难”问题，由于目前大部分的特征选择算法的时 间复杂度是特征维数的二次甚至更高次，使得它们无法对高维特征进行有效地 选择；另一个是样本数远远小于特征维数，则将容易导致过学习问题。因此， 如何设计高效的适用于高维数据空间的特征选择算法是目前需要迫切解决的 难题之一。 3 当出现新的数据类型时，如何设计特定的特征选择算法。随着应用领 域的不断扩大，所遇到的数据类型也将不断变化，例如：基于文本的数据 ( e m a i l s ，在线新闻等) 和半结构数据( 如h t m l ，x m l ) 等。这就要求所设 计的特征选择算法能处理特殊的数据类型。 由于上述原因，特征选择成为机器学习领域重要的研究方向，引起越来越 多的机器学习领域学者的兴趣。国内外的各大研究机构如c m u 、s t a n f o r d 大学、 w a s h i n g o n 大学、南京大学、哈尔滨工业大学和北京工业大学等都开展了相关 研究。这表明研究特征选择算法具有重要的学术意义和实用价值。 1 2 研究现状简介 在模式识别领域中，通常要求特征空间的维数不宜过高。在训练样本数目 有限的情况下，过高的特征空间维数不仅会影响预测器( 通常包括分类器和回 归器) 的学习效率，同时也会导致预测器对训练样本过拟合的问题。 特征选择可以从两个方面提高系统性能：一是预测速度。通过特征选择可 2 上海大学硕士学位论文 以大大减少特征集中的特征个数，简化系统模型，降低计算复杂性，防止过拟 合。二是预测精度。通过适当的特征选择，不但不会降低系统的预测精度，反 而会使精度得到提高【j 7 7 1 。 最早的特征选择研究是6 0 年代初开始的【_ 玛】。早期的研究是在特征间独立 的假设下，单独研究每一个特征的预测能力，然后取效果好的若干个特征组合 在一起得到特征子集，没有考虑特征之间的相互作用，且一般涉及的特征个数 较少【_ 7 9 】。c o v e r 指出即使满足相互独立的条件，两个单独使用最好的特征组合 起来，也不能保证得到最好的组合，在极端情况下，还有可能成为最差的特征 组合【1 0 3 1 。 此后，一些基于近似最优解的启发式搜索方法不断被提出，典型的有序列 前向选择法( s e q u e n t i a lf o r w a r ds e l e c t i o n ，s f s ) 、序列后向选择法( s e q u e n t i a l b a c k w o r ds e l e c t i o n ，s b s ) 等。这些算法考虑了特征的相互作用，但缺点是： 特征一旦被加入或者被剔除，以后将不再改变，因此容易陷入局部最优。为克 服该缺点，s o m o l 提出了自适应浮动选择算法等，在一定程度上缓解了该问题。 上世纪9 0 年代以来，涌现出了大规模机器学习问题 1 0 4 , 7 7 】，使得已有的特 征选择算法受到严峻的挑战，迫切需要在大规模数据集上具有较高预测精度和 较低运行效率的特征选择算法。k i r a 和r e n d e l 于1 9 9 2 年提出了一种有效的特 征选择算法r “e f 该算法的特征选择标准是特征相关性。r e l i e f 算法最大的 局限性是在相关特征集中不能识别出冗余特征【1 0 5 】。a l m u a l l i a m 和d i e t t e r i c h 于 1 9 9 2 年提出了利用信息论的思想来进行特征选择，该算法对噪音数据的适应能 力较型1 0 6 1 。c a r u a n a h e 和f r e i t a g 于1 9 9 4 年提出了一个改进的基于w r a p p e r 模 型的贪心算法，但用于学习算法的度量却大大地增加了计算时间【1 0 7 1 。 近几年来，对遗传基因的数据分析发展迅速。人们遇到的问题是基因数据 的维度往往达到几万，而样本个数呈减少趋势( 有时候可能仅有几百个样本， 甚至更少) 。p s i l v a 等对多个特征选择算法在基因数据集上的性能问题进行了 比较，但他们只是针对真实的基因数据进行了测试。因为缺乏关于这些真实数 据的背景知识，可能存在着样本类标误标的情况，使得在分类正确率的计算上 有所偏差【7 】。j i a n p i n gh u a 等提出了一种用于高维数据的两阶段组合式特征选 择方法，介绍了一种用来产生人造基因数据的分布式模型。该算法在真实数据 和人造数据上均做了详细测试，效果较好【引。 近十几年来，特征选择研究呈现出多样化和综合性的趋势。各种新的搜索 算法和评估标准( 包括单个特征的评估标准以及特征子集的评估标准) 不断被 用到特征选择算法中。如粗糙集算法用于特征选择、t a b us e a r c h 算法应用于特 征选择、神经网络剪枝法进行特征选择，支持向量机的评估标准、特征集的模 糊熵评价等都被用于特征选择。同时，除了监督式学习的特征选择研究外，还 3 上海大学硕士学位论文 开展了关于非监督式学习以及半监督学习的特征选择研究。另外，还出现了关 于特征选择的算法融合性的研究，如关于将f i l t e r 方法和w r a p p e r 方法结合的 混合型特征选择算法的研裂7 ，9 4 l 】。 虽然特征选择领域的研究近年来取得了很大进展，但由于特征选择问题和 实际应用背景的复杂性，还需要进行更为深入的研究，目前研究热点和需解决 的问题包括以下方面： 1 使用具有代表性的研究数据。目前，大部分关于特征选择的研究采用 u c i 机器学习数据库作为研究平台，而u c i 数据多是由特定领域内的专家提供 的，剔除了其中的不相关特征，数据量不大。为了研究分析特征选择算法在大规 模数据集上的性能，可以选择特征数目较多、数据量较大的实际研究对象作为 实验平台。 2 研究f i l t e r 和w r a p p e r 相结合的特征选择算法。f i l t e r 方法的计算效率 高，但预测精度相对较低。w r a p p e r 方法运算效率较低但预测精度较高。目前 已有不少学者提出了将f i l t e r 方法和w r a p p e r 方法结合起来的混合型( 或称组 合式) 特征选择方法。 3 研究特征选择和学习算法之间的关系。f i l t e r 方法认为一个好的特征子 集应该在任何学习算法上都能取得较好的效果，因此这种方法在进行特征选择 的过程中不依赖具体的学习算法；而w r a p p e r 方法则认为特征选择不仅和数据 集以及目标函数有关，还和下一步要使用到的学习算法的性能密切相关，因此 要用学习算法本身的性能作为选择特征子集的评估标准。目前对特征选择和学 习算法之间的关系仍无定论，k o h a v i 用几个实例证明了f i l t e r 方法的不足 1 0 s ， 但是s a n m a y 认为k o h a v i 所举的都是很特殊的假象例子【1 0 9 ，在实际情况中一 个好的特征子集能使任何学习算法得到更好的结果。进一步深入研究特征选择 和学习算法之间的关系对于指导特征选择算法的构造有重要意义。 4 特征选择算法的推广能力。特征选择作为数据预处理的重要手段已经 被应用到很多领域中，并且取得了较好的效果，但是尚没有一种较为通用的特 征选择方法可以保证其在大多数数据集上均能表现出良好的性能和合理的结 果。目前大部分的特征选择方法缺乏理论上的严格证明，仅仅通过特定应用背 景的仿真实验结果并不能完全证明算法的合理性和科学性。 1 3 盾构地铁隧道工程风险控制简介 随着城市土地资源的日趋紧张，地铁隧道工程的建设已经成为解决城市交 通问题的重要手段。但是由于地下工程项目内在的不确定性( 包括地层和地下 水状况等) 、施工复杂性以及周边环境因素的影响，在工程的各个环节都存在 4 上海大学硕士学位论文 很大的风险，对人员安全、经济以及环境构成较大的威胁。然而，我国在地铁 隧道建设方面的发展历史较短，经验不足，缺乏风险意识，安全防范和风险管 理相对落后，导致地下工程事故时有发生。据统计，近几年全国每年发生的各 类事故造成1 3 万人死亡，7 0 多万人受伤，直接和间接经济损失高达2 5 0 0 多亿 元。尤其在大城市中，施工地点往往处于繁华地段，一旦发生危险，将会对周 边建筑物造成严重影响，损失更是难以估量。例如北京地铁复八线某区间竖井 涌水事故、2 0 0 3 年7 月上海地铁四号线区间横通道事故、2 0 0 4 年广州地铁塌 方事故以及2 0 0 8 年1 1 月杭州地铁一号线区间基坑坍塌事故等，造成的损失都 相当严重【1 2 1 。因此研究有效的风险辨识和评估方法将有助于施工全过程的风险 控制。 由于地铁隧道工程的整个施工阶段，风险是时时存在的，项目建设的成败 与否，取决于我们对项目建设全过程中所涉及的风险状态的识别、评价，以及 能否根据评价结果采取及时、正确的处理措施。如果能快速而准确地识别出当 前施工状态可能存在的风险，可以降低风险事故发生的概率，降低事故的严重 程度。另一方面，隧道工程在建设阶段面临的风险是由多方面引起的，有客观 因素也有人为因素，具体体现为工期延迟、质量问题、直接经济损失、环境影 响、人员安全等。本文只讨论盾构隧道施工过程中的质量风险。 由于目前人们主要是依靠层次分析法【1 3 】、故障树法【1 4 】以及因子分析法【1 5 】 等方法在施工前期对该工程可能遇到的风险事故大致作出强度和概率上的估 算，较多地依赖以往的经验，对实际施工中可能出现的突发事件无法作出预计， 从而无法达到施工状态的动态识别和控制。因此，只有对施工过程中的实时监 测数据进行挖掘和分析，发现这个复杂系统中的关键因素，才能很好地掌握当 前施工状态，及时识别各种风险状态，这对整个工程的质量控制和安全防范都 有很大的帮助。 1 4 论文主要工作 本文研究的主要内容： 1 特征选择算法的综合研究； 2 提出三种特征选择算法，对它们进行了详细分析，并做出实验及结果 评价： 3 特征选择算法在盾构隧道施工复杂系统数据挖掘中的应用研究。 特征选择领域是机器学习、模式识别学科的重要分支，目前绝大部分特征 选择算法是针对分类问题而提出的，目标是为了提高分类器的分类性能和计 算效率。然而，在统计学中的回归问题，对特征选择算法也有着同样的需求： 5 上海大学硕士学位论文 根据特征选择方法从原始特征集中选取一个优化特征子集使得回归器具有更 高的回归精度和预测精度。因此，特征选择算法应当适用于分类问题和回归 问题两个方面。本文的研究工作涉及到分类和回归两个方面，下文以后提到 的预测器泛指分类器和回归器的统称。 本文的核心工作是开展三种特征选择算法的研究。论文首先提出了一种基 于自适应遗传算法( a d a p t i v eg e n e t i ca l g o r i t h m ，a g a ) 和支持向量机( s u p p o r t v e c t o rm a c h i n e ，s ) 的特征选择方法( a g a s v m ) 。将标准的遗传算法( g a ) 改进为一种自适应遗传算法用于特征选择，并引入支持向量分类机评价特征子 集的分类性能。针对目前有监督分类法无法解决约束性分类问题，还提出了一 种约束性多分类模型( r e s t r i c t i v em u l t i c l a s s e sm o d e l ，r m c m ) ，它能实现具 有约束条件的多分类模式识别；其次，提出了一种基于混沌离散粒子群( c h a o t i c b i n a r yp a r t i c l es w a r mo p t i m i z a t i o n ，c b p s o ) 的特征选择方法，将c b p s o 与 r m c m 结合( 称c b p s o i 洲c m ) 用于约束性多分类问题，分类准确率有了明 显提高。论文还分析了目前f i l t e r 方法和w r a p p e r 方法各自存在的缺陷，提出 了一种适用于回归的基于层次聚类算法和偏最小二乘的特征选择方法。该方法 吸取了f i l t e r 方法根据数据集内在特性对特征预测能力进行评估的思想，同时 又考虑到特征之间的相关性问题，使所获得的优化特征子集( 最优回归子集) 中包含的大部分特征的预测能力较好，同时使这些特征间的相关性低。 在盾构施工实时信息数据挖掘方面主要做了以下三个方面的工作： 1 为了快速发现盾构正常推进段中可能出现的施工质量风险，首先需要 在诸多的风险因素中筛选出与施工质量关系最密切的关键特征集。将 a g a s v m 特征选择方法用于风险因子选取，实验结果表明该算法选取的特征 子集与领域专家的意见基本一致，对风险状态识别的准确率有较明显的提高。 2 将c b p s o r m c m 用于隧道管片衬砌过程的管片选型预测，仿真实验 表明，c b p s o r m c m 对管片选型的预测精度比直接用r m c m 预测有很大提 高。此方法也可作为今后盾构施工管片选型预测的参考方法之一。 3 在盾构推进过程中，地面沉降是必须严格控制的风险之一，它很可能 会对周边建筑物以及环境造成很大影响。本文将基于层次聚类算法和偏最小二 乘的特征选择方法用于施工中的地面沉降的回归预测，所选取的最优回归子集 与领域专家的意见基本一致。实验结果显示了用最优回归子集所构建的回归模 型具有更高的回归精度和预测精度，并明显降低了计算时间，对今后盾构施工 地面沉降预测方法的研究具有一定的参考意义。 6 上海大学硕士学位论文 1 5 论文组织结构 本文共分六章，各章具体安排如下： 第一章介绍了机器学习中高维数据特征选择问题的提出及研究背景和意 义，以及特征选择算法研究的现状。 第二章介绍了特征选择的基本概念和一般过程，典型的特征选择算法以及 特征选择算法的挑选及其应用等。 第三章对遗传算法和支持向量机的基本知识进行了简单的介绍，重点介绍 了本文提出的基于自适应遗传算法和s v m 的特征选择算法的设计，并在盾构 施工实时数据集上运行，分析了实验结果。 第四章在简单介绍了粒子群算法的思想和本文提出的约束性多分类模型 r m c m 后，重点介绍了本文提出的一种基于混沌离散粒子群c b p s o 的特征选 择方法c b p s o r m c m ，并将该方法用于盾构施工管片选型预测。在三组实验 数据集上进行测试并验证了算法的有效性，表明c b p s o r m c m 的寻优能力优 于二进制粒子群和自适应遗传算法。 第五章分析了f i l t e r 方法和w r a p p e r 方法的各自存在的缺陷，介绍了层次 聚类算法和偏最小二乘的基础知识，提出了一种适用于回归的基于层次聚类算 法和偏最小二乘的特征选择方法。将该方法用于盾构施工地面沉降预测，实验 结果较理想。 第六章总结了论文中的主要工作和结论，并展望下一步的工作方向。 7 上海人学硕士学位论文 第2 章特征选择算法概述 特征选择是模式识别和机器学习领域重要的研究方向。随着模式识别与数 据挖掘研究的深入，研究对象越来越复杂，对象的特征维数越来越高。大量高 维数据对象的特征空间中含有许多冗余特征甚至噪声特征，这些特征不仅可能 降低学习器的预测精度，而且会大大增加训练时间及空间复杂度。因此，在面 对高维数据进行分类或回归时，通常需要运用特征选择找到具有较好可分性的 特征子空间，从而实现降维，降低机器学习的时间及其空间复杂度。这样做一 方面可以提高预测精度和计算效率，另一方面可以找出包含有用信息的特征子 集，为决策提供依据。例如，找出与某种疾病密切相关的致病因素等。 2 1 特征选择的基本概念 2 1 1 特征选择的定义 机器学习中的特征选择可定义为：已知一特征集，从中选择一个子集使评 价标准最优。以上定义可表述为f 给定一个学习算法，一个数据集s ，数据集s 来自一个具有t 个特征 x 。，x ：，x 。，具有类别标记y 以及符合分布d 的例子空间，则一个最优特征 子集x o p t 是使得某个评价准则j = j ( l ，s ) 最优的特征子集。 从特征选择的定义可见，在给定学习算法、数据集、以及特征集的前提下， 各种评价准则的定义和优化技术的应用将构成特征选择的重要内容。 特征选择是机器学习领域的难题。在实际应用中，寻找最优的特征子集通 常是很难的，很多和特征选择相关的问题被发现是n p h a r d 问题。d a v i e s 证明 寻找满足要求的最小特征子集是n p 完全问题。但通过采用启发式搜索算法， 还是可以在运算效率和特征子集质量间寻找到一个好的平衡点的，这也是众多 特征选择算法努力的目标。 2 1 2 特征选择和学习算法的关系 图2 1 显示了包含特征选择的机器学习系统的基本组成部分，可见，整体 上来说，特征选择是机器学习算法的前处理阶段。 上海大学硕士学位论文 图2 1 机器学习系统的基本构成 特征选择和学习算法的关系可以从理论和实际应用两个方面来考虑。从理 论上讲，对于分类问题，如果存在某个识别函数，那么只有那些在识别函数中 出现的特征才是需要的。而在实际应用中，常常以某特征对学习算法是否有用 来作为选择的依据。因为实际应用中事先并不知道识别函数，这个识别函数正 是要通过学习才能得到的，学习总要选择一个学习算法来进行逼近，如决策树、 神经网络、贝叶斯估计等，未知样本的预测也要通过某学习算法得到的分类器 来进行，因此k o h a v i 等认为一个特征或者特征子集是否该选择，不应离开学 习算法而进行【1 0 引。然而，s a n m a y 等人认为一个好的特征子集应该在任何一个 学习算法上都有好的效果，特征选择的过程不应该依赖具体的学习算法【l 叫。 因此，对于特征选择的过程中是否需要依赖学习算法这一问题目前尚没有定 论。 无论如何，对学习算法来说，有效的特征选择可以降低学习问题的复杂性， 提高学习算法的泛化性能，简化学习模型。因此，只要是对提高机器学习算法 的性能和效率有帮助的特征选择结果，应该认为均是较理想的。 2 2 特征选择的四个要素 一般而言，特征选择可以看作一个搜索最优问题。对于大小为n 的原始特 征集合，搜索空间由2 一种可能的状态构成，也即一共存在2 “个特征选择方案。 理论上可以证明除了穷举式搜索，不能保证找到全局最优解。但是在实际应用 中，当原始特征的维数较大时，采取穷举式搜索策略的特征选择将会耗费极大 的计算量，因此研究者们致力于启发式搜索算法寻找次优解。一般把特征选择 算法的组成分为4 个要素：( 1 ) 搜索起点和方向；( 2 ) 搜索策略；( 3 ) 特征评 价标准；( 4 ) 停止准则。 2 2 1 搜索起点和方向 搜索起点是算法开始搜索的状态点，搜索方向是指评价的特征子集产生的 次序。搜索的起点和搜索方向是相关的，它们共同决定后面的搜索策略。一般 的，根据不同的搜索起点和方向，有以下4 种情况t 9 上海大学硕士学位论文 1 前向搜索( s f g ) ：搜索起点是空集s ，依据某种评价标准，随着搜索 的进行，从未被包含在s 里的特征集中选择最佳的属性不断加入s 。 2 后向搜索( s b g ) ：搜索起点是全集s ，依据某种评价标准不断从s 中 剔除最不重要的属性，知道达到某种停止标准。 3 双向搜索( b g ) ：双向搜索同时从两个方向开始搜索。一般搜索到特 征子集空间的中部时，需要评价的子集将会急剧增加。当使用单项搜索时，如 果搜索要通过子集空间的中部就会消耗掉大量的搜索时间，所以双向搜索是比 较常用的搜索方法。 4 随机搜索( r g ) ：随机搜索从任意的起点开始，对属性的增加和删除 也有一定的随机性。 2 2 2 搜索策略 假设原始特征集中有刀个特征( 也称输入变量) ，那么存在2 4 1 个可能的 特征子集。搜索策略就是为了从包含2 ”一1 个候选解的搜索空间中寻找最优特征 子集而采取的搜索方法。搜索策略可以大致分为三种： 1 完全搜索：也即穷举式搜索，它可以搜索到每个特征子集。完全搜索 的缺点主要是它会带来巨大的计算开销，尤其当特征数较大时，计算时间很长。 分支定界法( b r a n c ha n db o u n d ，b b ) 【3 】通过剪枝处理降低搜索时间。 2 序列搜索：它避免了简单的完全搜索，在搜索过程中依据某种次序不 断向当前特征子集中添加或剔除特征，从而获得优化特征子集。比较典型的序 列搜索算法如：前向后向搜索4 1 、浮动搜烈5 1 、双向搜索【4 1 以及序列向前和序 列向后算法等。序列搜索算法较容易实现，计算复杂度相对较小，但它们容易 陷入局部最优。 3 随机搜索：由随机产生的某个候选特征子集开始，依照一定的启发式 信息和规则逐步逼近全局最优解。例如：遗传算法( g e n e t i ca l g o r i t h m ，g a ) 、模 拟退火算法( s i m u l a t e da n n e a l i n g ，s a ) 粒子群算法( p a r t i c ls w a r mo p t i m i z a t i o n ， p s o ) 和免疫算法( i m m u n ea l g o r i t h m ，i n ) 等 2 2 3 评价标准 评价标准在特征选择过程中扮演着重要的角色，它是特征选择的依据。评 价标准可以分为两种：一种是用于单独地衡量每个特征的预测能力的特征评价 标准；另一种是用于评价某个特征子集预测性能的评价标准。 在f i l t e r 方法中，一般不依赖具体的学习算法来评价特征子集，而是借鉴 1 0 上海大学硕士学位论文 统计学、信息论等多门学科的思想，根据数据集的内在特性来评价每个特征的 预测能力，从而找出排序较优的若干个特征组成特征子集。通常，此类方法认 为最优特征子集是由若干个预测能力较强的特征组成的。 相反，例如在w r a p p e r 方法中，将后续的学习算法嵌入到特征选择过程中， 通过测试特征子集在此学习算法上的性能来决定该特征子集的优劣，而极少关 注特征子集中每个特征的预测性能如何。因此，第二种评价标准并不要求最优 特征子集中的每个特征都是优秀的。 本文在针对盾构施工实时监测数据进行特征选择算法的研究过程中，尝试 了若干种方法，其中不同特征选择方法中最主要的差别就是特征评价标准的制 定。因此，特征评价标准在很大程度上影响着特征选择算法的性能，也关系到 特征选择的结果。 2 2 4 停止准则 停止标准决定什么时候停止搜索，即结束算法的执行。它与评价准则或搜 索算法的选择以及具体应用需求均有关联。常见的停止准则一般有： 1 执行时间，即事先规定了算法执行的时间，在到达所制定的时间时强 制算法终止运行并输出结果。 2 评价次数，即制定算法需要运算多少次，通常用于规定随机搜索的次 数，尤其当算法运行的结果不稳定的情况下，通过若干次的运行结果找出其中 稳定的因素。 3 设置阈值，设置阈值在算法中十分常见，一般是给算法的目标值设置 一个评价门限值，通过目标与该阈值的比较决定算法停止与否。不过要设置一 个合适的阈值并不容易，需要对算法的性能有十分清晰的了解，否则设置阈值 过高会使得陷入死循环，阈值过d , n 达不到算法应达到的性能指标。 2 3 特征选择算法的分类 目前国际上对特征选择算法的研究主要集中在选择优化特征子集所需要的 两个主要步骤上，即搜索策略和评价标准。因此，可以从这两个方面来对特征 选择方法进行分类： 一按照搜索策略划分特征选择算法 根据算法进行特征选择过程中所采用的搜索策略，可以把特征选择算法分 为采用最优搜索策略、随机搜索策略和启发式搜索策略三类。 1 采用全局最优搜索的特征选择算法。到目前为止，唯一采用用全局最 上海大学硕士学位论文 优搜索策略得到最优结果的特征选择方法是“分支定界 ( b r a n c ha n db o u n d ) 算法【3 5 邓3 7 1 。该算法的主要思路是：定义一个评价准则函数，该评价准则函数 必须满足单调性条件，也就是对两个特征子集s 1 和s 2 而言，如果s 1 是s 2 的子 集，那么s 1 所对应的评价函数数值必须要小于s 2 所对应的评价函数值。在定 义了该评价函数的前提下，该算法对最终特征子集的选择过程可以用一颗树来 描述。树根是所有特征的的集合，从树根可分性判据值和事先定义的最佳特征 子集的特征数目，搜索满足要求的特征子集。这个过程中可使用各种树搜索算 法，例如“自上而下 搜索方法。使用不同的搜索算法可以提高该方法的搜索 效率，加快运行速度，相对于耗尽搜索方法大大节约计算时间，但是从统计的 角度而言，它的运算时间数量级与耗尽搜索仍然相差不远。 采用这种搜索算法策略的特征选择算法，能保证在事先确定优化特征子集 中