（电力系统及其自动化专业论文）电力系统暂态稳定评估中的特征选取.pdf

西南交通大学硕士研究生学位论文第1 | 页 a b s t r a c t f e a t u r es e l e c t i n gp l a y sav e r yi m p o r t a n tr o l ei np o w e rs y s t e mt r a n s i e n t s t a b i l i t ya s s e s s m e n t b a s e do nd a t am i n i n gt e c h n i q u e s ，a l g o r i t h m sf o rf e a t u r e s e l e c t i n ga l ed i s c u s s e di n t h i sd i s s e r t a t i o n a i m i n ga tp a r t i c u l a r i t i e so fd y n a m i c d a t ao np o w e rs y s t e m ，c o n f o r m i n gt oe x i s t e n ta l g o r i t h m s ，an e wa l g o r i t h mf o r f e a t u r es e l e c t i n gi sp r o p o s e db a s e do np r i n c i p a lc o m p o n e n ta n a l y s i sa n dg e n e t i c a l g o r i t h m i nt h ed i s s e r t a t i o n , t h em a i na s s e s sm e t h o d so fp o w e rs y s t e mt r a n s i e n t s t a b i l i t ya l ee x p a t i a t e du p o n ，a n da n dt h ea p p l i c a t i o na n dr e s e a c hs t a t u sa l e d e s c r i b e da s w e l l e l e m e n t a r yp r i n c i p l e sa n dd e v e l o p m e n ts t a t u so ff e a t u r e s e l b c t i o nm e t h o d si nd o m e s t i ca n do v e r s e a sa r e d i s c u s s e d ，a n dt h e nb o t h a d v a n t a g e sa n dd i s a d v a n t a g e so fe x i s t e n tm e t h o d sa r ea n a l y z e di nd e t a i l i ns t u d i e so fe v a l u a t i n gt r a n s i e n ts t a b i l i t y , m o s tt a r g e tp o w e rs y s t e mh a sa s m a l ls i z e ，s u c ha si e e e 3 9 - b u ss y s t e m i nt h ed i s s e r t a t i o nt h ep r i m a r yf e a t u r e s a m p l e so fi e e e l 6 一m a c h i n e8 6 - b u ss y s t e ma n di e e e 5 0 m a c h i n e4 5 3 b u ss y s t e m a l ee s t a b l i s h e d p r i n c i p a lc o m p o n e n ta n a l y s i s ( p c a ) a n dg e n e t i ca l g o r i t h m ( g a ) h a v eb e e nu s e dt oe f f i c i e n t l yr e d u c et h ed i m e n s i o no ft h ep r i m a r yf e a t u r e ；a tl a s t r e c o n s t r u c tt h ei n p u ts p a c eb yu s i n gt h ei d e ao ff a c tl o a d i n g ，t o a c c o m p l i s h f c a m r es e l e c t i o n t h ec a p a b i l i t ya n dr e l i a b i l i t yo fr e c o g n i t i o ni s p r o v i d e db yt h es v mt e s t r e s u l t k e yw o r d s ：d a t am i n i n g ；f e a t u r e s e l e c t i o n ；p r i n c i p i a lc o m p o n e n ta n a l y s i s ； g e n e t i ca l g o r i t h m ；s v m 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 全国电网互联u 】使得电力系统规模不断扩大，电网日盏复杂；环境和经 济等因素，使得电力系统运行接近稳定极限状态，因此安全稳定性问题成为 电力系统运行最突出问题之一。电力系统紧急控制是解决这一问题的一个有 效手段。电力系统是一个由发电机组、变压器、输配电线路和用电设备等元 件组成的复杂非线性动态系统。电力系统的任务是向用户供应可靠的、有良 好电能质量的电能，保持电力系统安全经济她稳定运行。 现代电力系统由于机组容量大、输电电压高、分布地域广、构成元件多 和响应速度快，因而运行特性复杂，控制管理困难，一个严重扰动可能波及 全系统导致大面积停电，乃至系统崩溃，从而给国民经济造成重大损失。可 见，保证电力系统的安全稳定运行是一个极端重要但也极端困难的问题。 电力系统暂态稳定分析的主要目的【2 】是检查系统在大扰动下( 如故障、 切机、切负荷、重合闸操作等情况) ，各发电机组间能否保持同步运行，如果 能保持同步运行，并具有可能接受的电压和频率水平，并称此电力系统在这 一大扰动下是暂态稳定的。 当电力系统受到大扰动时，发电机的输入功率和输出电磁功率失去平 衡，引起转子的速度及角度的变化，各机组闻发生捃对摇摆，其结果可能有 两种不同的情况。一种情况是这种摇摆最后平息下来，系统中各发电机仍能 保持同步运行，过渡到一个新的运行状态，则认为系统在此扰动下是暂态稳 定的。另一种情况是这种摇摆最终使一些发电机之间的相对角度不断增大， 也就是说发电机之间失去了同步，此时系统的功率及电压发生了强烈的振荡， 对于这种情况，我们称系统失去了暂态稳定。这时，应该将失步的发电机切 除并采取其他紧急措施。现代电力系统采用了先进技术和装置来改善系统的 暂态稳定性。 1 1 电力系统暂态稳定主要评估方法 现有的暂态稳定评估方法【2 i 【3 】可根据稳定评估思路的不同分为以下几大 类： 西南交通大学硕士研究生学位论文第2 页 1 1 1 时域仿真法 时域仿真法将电力系统各元件模型根据元件间拓扑关系形成全系统模 型，这是一种联立的微分方程组和代数方程组，然后以稳态工况或潮流解为 扔值，求扰动下的数值解，即逐步求得系统状态量和代数量随时问的变化曲 线，并根据发电机转子摇摆曲线来判别系统在大扰动下能否保持同步运行， 即皙态稳定。电力系统的模型可以由描述各发电机，电动机及其控制系统的 一组一阶微分方程式和描述网络的一组代数方程式组成。当前在国内外比较 有影响的是p s s e ，b p a ，e u r o s t a g e 和我国电科院的p s a s p 等，它们 均采用隐式梯形积分法。 时域仿真法是最成熟的一种方法，它适应面广，精确可靠，能同时研究 第一摇摆和后续摇摆失稳模式，也可通过反复迭代求解稳定指标。其用于暂 态稳定分析的主要优点是：( 1 ) 直观、信息丰富、可获得各种量随时间的变 化曲线。( 2 ) 可适应有几百台机、几千条线路、几千条母线的大系统，可适 应各种不同的元件模型和系统故障及操作。( 3 ) 可采用数值稳定性良好，并 有良好工程精度的计算方法。( 4 ) 可采用节点编号优化、稀疏矩阵技术、并 行计算机技术以节省内存和机时。( 5 ) 可作为各种物理问题及控制对策的时 域分析和校验手段等等。 但是，逐步积分计算速度慢、机时多；计算量过大，即使采用并行算法 仍难以满足大系统在线暂态稳定评估对速度的要求。 1 1 2 基于l y a p u n o v 稳定定理的能量函数法( 直接法) 直接法主要有3 种，即沿持久故障轨迹搜索最大势能点的势能界面法 ( p e b s ) ，辨识相关不稳定平衡点的r e u p 法和利用p c o i 映射来保存系统 稳定充要条件的e e a c 法。此外还有从p e b s 发展的b c u 法，将积分和直接 法相结合的混合法以及q u e p 法等。e e a c 法是一种不同于l y a p u n o v 函数， 但却非常严格的直接法，它保持了原积分空间的完整性，仅把观察空间等值 为单机无穷大系统，并保存了原多机动态过程的稳定特征。目前e e a c 法在 实际工程中已得到应用。直接法以其能够定量评估稳定裕度，适合于灵敏度 分析，计算快速等优点受到较多关注，成为时域仿真法的一种重要补充。它 将扰动后的系统看作初态下的自治系统来研究其稳定性，使时域仿真的计算 时间缩短到扰动停止时刻，大大加快了暂态稳定的判别速度。 直接法的最大优点如下：( 1 ) 能计算非线性，适应较大系统：( 2 ) 计算 西南交通大学硕士研究生学位论文第3 页 速度快，不必逐步积分求摇摆曲线；( 3 ) 能给出稳定度。但直接法也存在一 些很难克服的缺点，如对复杂模型缺乏有效的能量函数构造方法，尤其是 l y a p u n o v 定理本身只能提供稳定的充分条件，而不是充要条件，使评判结果 过于保守。表1 1 是时域法与直接法的一个比较： 表卜1 时域仿真与直接法的比较 比较内容时域仿真方法直接法 求解方法数值算法点式方法分析方法域式方法 建模能力详尽尚不够详尽 快速性计算量大，耗费机时极限参数计算速度快 1 1 3 人工智能的方法 目前用于电力系统暂态稳定分析评估的人工智能方法包括有专家系统、 人工神经网络、模式识别、模糊控制、灾变理论及熵网络理论等。 其中模式识别的方法，是在求取出能比较准确地直接或间接反映电力系 统暂态稳定性物理本质特性的模式特征集的基础上，通过离线学习或训练， 获得能快速识别电力系统暂态稳定性类别的判别函数或分类器。电力系统暂 态稳定性评估的问题可以简化为仅仅区分稳定和不稳定状态的两模式分类问 题。这问题看起来似乎很简单，但模式识别法的关键不在它的结果的复杂性， 其难点在于反映物理本质特性的原始特征的求取和分类器的设计上。 电力系统本身是一个十分复杂的非线性大系统，而暂态稳定性分析又是 其中较难的问题之一。在用模式识别法进行电力系统暂态稳定评估时，必须 在保证准确性的前提下充分发挥其速度快的优点，才能满足在线分析的要求。 该方法由于不需要建立系统的数学模型，直接从样本中寻求状态参数与稳定 性或稳定指标之间的映射关系，求解稳定指标不需要重复试探，计算量受系 统规模影响较小，整体评估速度很快。但它缺乏标准的实现方法，其精度对 样本规则选取，输入变量的选取等因素极为敏感，设计不当时评估的可靠性 和稳定性较差。 西南交通大学硕士研究生学位论文第4 页 1 2 电力系统暂态数据的特点 1 i 数据多 数据来源广泛，来自实际测量系统以及各种仿真数据，并且数据具有时 变特性，数据时时刻刻在更新。在电力系统中，数据主要分为由分布于系统 各处的各种装置实时采集的现场数据和由调度中心诸如s c a d a 系统收集的中 央数据以及管理信息系统( m i s ) 、地理信息系统( g i s ) 等在使用过程中产生 的大量数据，数据的来源多。另外，整个电力系统是用大规模的非线性微分 方程组和非线性代数方程组来描述，二者联立就组成了大规模奇异非线性动 态大系统，在对其进行特征描述时往往涉及到上千个状态变量。 2 数据种类混杂 数据种类繁多，有布尔型数据、连续型数据以及图象数据等，维数高。 电力系统是一个标准的混杂系统，其上层( 调度中心) 给出的调度决策主要 是逻辑性的操作指令，而下层控制( 如发电机的励磁与调速控制) 主要是连 绥性的。 素。 3 数据质量差 在电力系统中，采集到的数据包含着诸如噪声、数据缺失等不确定性因 4 电力系统对数据的要求商 当系统处于紧急状态，甚至瓦解状态时，必须制定实时在线快速决策， 使系统重新回到正常状态。 这就要求用于安全分析的暂态稳定方法要具有如下几个特点：处理如此 大样本空间的同时保证实时性、避免维数灾、自适应性强、能处理不确定数 据或模糊数据的能力强、适用于分类等。单一的数据挖掘方法很难满足需要， 需要采用混合的方法。一方面用于优化训练数据，提高容错性和灵活性：另 一方面用于归纳规则，便于调度运行人员理解不同系统模型对电网安全稳定 的全面影响。 在这种情况下，工程技术人员陷于一个难题，即“数据丰富”而“知识 贫乏”，为了缓解数据供给和数据分析能力之间的矛盾，数据挖掘技术应运而 生。 西南交通大学硕士研究生学位论文第5 页 1 3 数据挖掘在电力系统中的应用 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应 用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息 和知识的过程“1 ，也被称作数据库中的知识发现、知识挖掘、数据采掘等。 近年来，数据挖掘已经广泛应用于工业、医学、金融等行业，尤其在商业和 银行领域应用极为迅速，但是其在电力系统中的应用才刚刚起步嘲。 1 3 1 数据挖掘在电力系统中的应用现状 1 电力系统安全稳定性分析 电力系统的安全稳定性 8 9 , 1 0 , 1 1 , 1 2 1 3 - 1 5 1 受众多因素的影响( 包括一些未知 因素) ，而且用于仿真的模型参数有效性也有待验证，在这种情况下，如何利 用仿真、实测的历史数据找出目标电网的安全稳定规律，是数据挖掘的一个 热点，其挖掘内容主要包括：安全稳定实时预测模型的构建、安全稳定规则 模型的构建、安全稳定的可视化。 2 负荷预测模型的构建 负荷预测t 6 - 1 9 , 2 0 , 2 1 , 2 2 2 3 1 是利用已知的相似日负荷、天气情况、时期类型、 时间等历史数据，对未来的系统负荷需求做出提前预测。精确的负荷预测有 利于工程技术人员更合理安排调度计划，确定机组的组合方案。数据挖掘技 术在这方面具有独特的优势，可自发的利用多种分析方法对目标数据集进行 分析，并针对电网特性找出最佳的负荷预测方案。 3 电力系统故障诊断 电力系统经过多年的运行，已经积累了大量、充足的故障数据，如何利 用这些数据，找出偶发故障之后掩藏的客观规律，是电力工作者研究的重点。 鉴于数据挖掘技术强大的数据分析功能，可利用其集成的多种分析技术找出 故障原因，并制定相应的辅助决策规则，采取措施减少故障发生概率，提高 电力系统运营的可靠性和经济效益。 4 电力系统仿真模型的性能评估 大区域电网的互联和电力市场的逐步实施使得电力系统运行环境日趋复 杂，在这种情况下，对电力系统仿真的要求也越来越高。此时，为保证系统 的安全稳定运行，必须对仿真模型的性能进行评估。以控制模型的参数设计 西南交通大学硕士研究生学位论文第6 页 为例，鉴于电力系统的高维性、非线性，一般情况下，我们仅利用有限的运 行模式、扰动类型对其进行评估，以检验其控制效果，但这种测试方法无法 覆盖整个仿真空间，一旦实际运行环境与仿真环境有所偏离，控制的效果就 要大打折扣。为解决该问题，可利用数据挖掘技术智能生成目标电网可能的 仿真空间，对各种系统模型分别进行测试，评估其性能，并总结为规则，以 便从总体上把握模型的性能、应用条件及应用范围。 j 电力市场环境下的电力用户行为分析 在电力市场环境下唧洲，调度运行人员需要在保证系统安全稳定运行的 基础上提高电力运营的经济效益，为达到这一目标，可先利用数据挖掘技术 找出各类电力用户的固有行为特点，并总结为决策规则，而后，有针对性的 制定相应的调度方案和供电策略，降低能源损耗，增加电力企业的运营利润。 6 系统异常值监测 在电力系统的实测数据中，通常会存在与数据一般规律不相符的异常数 据对象，这类异常数据有可能是由于测量误差、传输误差造成的，其通常蕴 含着系统的一些内在特殊性质。因此，监测并分析电力系统数据集中所埋藏 的异常数据具有较强的实用价值，这方面的挖掘被称之为异常挖掘。 由于数据挖掘在电力系统中的应用才刚刚开始，很多研究方向现在正处 于探索阶段，专门针对电力系统的数据挖掘产品在国内还未见报道，在这种 情况下，为提高电力系统数据集的利用效率，找出系统的内在规律，需要广 大工程技术人员作更进一步的深入研究。 1 3 2 数据挖掘在电力系统暂态稳定评估的研究现状 近年来，专门针对电力系统安全稳定的数据挖掘得到了较快的发展，其 中，乙w e h e n k e 8 , 9 , 1 0 0 1 1 , 2 5 等学者在这方面做出了较为突出的贡献。研发的 a t d i d t ( 目前改名为p e p i t o ) 电力系统安全稳定挖掘软件现在已投入商业发 行，该软件中的决簧树模型可通过系统结构建模，从潮流及故障类型中提取 特征量，利用特征量建立离线的决策树，最后用得到的安全稳定规则在线快 速判断给定故障切除时间下系统的稳定程度。但该软件仍存在许多不足之处， 仅拿构造的决策树模型来说，其对系统故障地点、类型、网络结构的变化过 于敏感，影响电力系统稳定的因素考虑的不够全面，结果信息的描述也不够 浅显易懂，同时该软件中集成的算法也比较少，没有考虑利用实测数据对现 西南交通大学硕士研究生学位论文第7 页 有的安全稳定规则进行修正，软件使用比较复杂，人机交互较少，因此它还 算不上一个完全意义上的电力系统安全稳定挖掘软件，仅仅是一个集成多种 算法的安全稳定智能分析软件。 而国内专门针对电力系统的数据挖掘产品还没有出现。 1 4 本文的主要工作 1 、针对电力系统的特点，学习和理解电力系统的模型与运行数据，提出 与电力系统相关的暂态稳定特征，完成对初始特征的选取； 2 、研究电力系统数据的特点，利用仿真软件p s t2 0 ，对应所提出的初 始特征，完成对i e e e1 6 机和i e e e5 0 机数据样本的构造： 3 、结合电力系统暂态稳定分类评估的任务，研究特征选取的算法和评估 标准，基于评估标准，评价各种特征选择算法的优劣；并提出适合于电力系 统暂态稳定评估的特征选择算法； 4 、选用基于主成分和遗传算法的特征选择方法，对初始特征进行选择。 利用主成分分析法提取出一组有较好分类效果的综合特征；然后利用遗传算 法进行特征选择，从提取的综合特征中选择出使类内、类闽距离判据最大的 个综合特征，并通过因子负荷，完成暂态稳定输入特征的选择； 5 、特征选择得到的初始输入特征通过支持向量机( s v t ) 分类器的测试， 仿真结果表明压缩后的输入空间和原始输入空间具有相类似的分类准确率； 并比较了i e e e1 6 机和i e e e5 0 机系统特征选择结果的异同。 西南交通大学硕士研究生学位论文第8 页 第2 章数据挖掘中的特征选择方法 用于数据挖掘的海量数据可能包含成千上万的特征，其中大部分特征与 挖掘任务是不相关的或是冗余的，这些特征增加了数据量，减慢了挖掘进程， 并有可能使发现的知识质量很差。特征选择就是一个从原有的特征集合中选 择一个f 相对某种评价准则1 最优特征子集的过程。 机器学习2 9 3 0 】问题可以定义如下：给定一个样本描述和目标函数值已知 的样本集，我们利用学习算法逼近其真正的目标函数，并对新来的样本进行 预测。描述样本的属性就是特征( f e a t u r e ) ，也常被称为变量( v a r i a b l e ) 、属性 ( a t t r i b u t e ) 、特性( c h a r a c t e r i s t i c ) 等。样本( s a m p l e ) 2 7 常被称为记录( r e c o r d ) 、 样例( e x a m p l e ) 、实例( i n s t a n c e ) 等。 2 1 特征选择概述 从原始特征集中选出最优特征子集是模式识别和机器学习等领域的一个 关键问题，同时也是一个棘手问题。现已证明，最优( 最小) 特征子集选择 o f s s ( o p t i m a lf e a t u r es u b s e ts e l e c t i o n ) 是n p p l l ( n o n d e t e r m i n i s t i ep o l y n o m i a l l 难问题。 数据集的大小可以从两方面衡量：特征的数目n 和样本的数目p ，n 和 p 可能很大，而n 的庞大经常会引起维数灾难( c u r s eo f d i m e n s i o n a l i t y ) 等 问题。 2 1 1 特征选择方法的研究现状 最早的特征选择研究是2 0 世纪6 0 年代初开始的i _ ”，当时的研究通常集 中于统计学及信号处理问题，而且一般涉及到的特征较少，并且通常假定特 征间相互独立【3 3 1 1 3 4 1 。从2 0 世纪7 0 年代开始，特征选择得到了长足的发展， 它能够去除不相关特征和冗余特征，提高学习效率，改善学习性能，增强学 习结果的可理解性。 2 0 世纪9 0 年代以来出现的大规模机器学习问题，如基因工程 5 1 、文本 分类【3 6 】、客户关系管理【3 7 】口8 1 ，使得已有的特征选择算法受到严峻的挑战，迫 切需要适应大规模数据集的分类准确性和运行效率等综合性能较好的特征选 西南交通大学硕士研究生学位论文第9 页 择算法。特征选择引起了机器学习领域学者广泛的研究兴趣。 近十年来，特征选择研究呈现出多样化和综合性的趋势。各种新搜索算 法和评估标准都应用到特征选择算法中，如粗糙集算法 3 9 】、神经网络剪枝法 即、支持向量机f 4 1 1 1 4 2 1 、特征集的模糊熵评价1 4 3 1 、马尔可夫算法等【4 4 1 。并且 除监督式学习的特征选择研究外，也开展了关于非监督式学习的特征选择研 究【4 5 1 1 4 6 。另外还出现了关于特征选择算法的融合性研究，如关于过滤式方法 和封装式方法结合的研究f 4 7 1 ，以及特征选择和样本选择的组合研究1 4 8 j 。 2 1 2 典型特征选择算法 2 1 2 1 决策树 许多决策树算法本身就蕴含着特征选择的意味。比如常用的i d 3 ，c 4 5 和c a r t 算法，都是通过某神标准，定位到蕴含分类信息量最大的树节点， 分裂该节点并生长出树枝从而构造出整棵决策树。从所有的节点中定位需要 分裂的节点这一过程也可以被看作是一个特征选择的过程。与问题本质相关 联最紧密的特征梭一个接着一个地找出来，问题的实质也一点一点地展现在 人f 门的面前。 但决策树方法的缺点在于一次只能考虑一个特征对分类问题的贡献，假 如有几个特征联合起来表征问题的某种属性时，决策树算法无法将这几个特 征综合起来作为一个因素处理。 2 1 。2 2 神经网络 神经网络法正好可以解决上述决策树方法所无法解决的问题。神经网络 通过隐层神经元将输入环节和输出环节连接到一起，可以同时体现出所有输 入环节对输出环节的影响作用。 神经网络方法的缺点在于耗时长，由于需要不断地重复训练新的神经网 络，使得整个方法需要的计算时间非常之长。虽然有很多新的算法可以有效 地缩短单次神经网络训练所需的时间，但是当输入特征数比较多时，整个算 法的效率仍然显得很低。 2 1 2 3 遗传算法 遗传算法( g e n e t i ca l g o r i t h m g a ) 【4 9 l 【5 0 1 是模拟达尔文的遗传选择和自 然淘汰的生物进化过程的计算模型，最早是由美国密歇根( m i c h i g a n ) 大学 j h h o l l a n d 教授在1 9 7 5 年发表的论文“自然和人工系统的适配”中提出 的，文中叙述了以二进制数字串为基础的基因模式理论及基本定理，为遗传 西南交通大学硕士研究生学位论文第1 0 页 算法奠定了坚实的理论基础。遗传算法是模拟生物在自然环境中的遗传和进 化过程而形成的一种自适应全局优化概率搜索算法。 2 1 2 4 统计分析方法 利用统计学中的数学原理对数据库进行分析。有如下方法： 1 相关分析和回归分析。相关分析是用相关系数来度量变量间的相关程 度。回归分析是用数学方程来表示变量间的数量关系，方法有线性回归和非 线性回归。 2 差异分析。从样本统计量的值得出的差异来确定总体参数之间是否存 在差异( 假设检验) 。典型方法为方差分析，它是通过分析实验数据中不同来 源的变异对总体变异的贡献的大小，从而确定实验中的可控因素( 自变量) 是 否对实验结果f 因变量) 有重要的影响。 3 因子分析。它是用较少的综合变量来表达多个观察变量。根据相关性 大小把变量分组，使得同组变量之闻相关较高，不同变量闻的相关较低。 4 判别分析。建立一个或多个判别函数，并确定一个判别标准，然后针 对未知属性对象，根据测定的观察值，将其划归已知类别中的一类。判别准 则有错误率最小或损失最小等。 2 2 特征选择方法的分类 2 2 1 按特征选择和学习算法的关系划分 特征选择方法按特征选择和学习算法的关系可分为嵌入式( e m b e d d e d ) 、 过滤式( f i l t e r ) 和封装式( w r a p p e r ) 三种。 1 嵌入式特征选择 嵌入式特征选择指将样本选择作为学习算法的组成部分嵌入到学习算法 里。最初的方法是假设标记训练数据集对于学习系统是可用的，然而并不是 所有这些样本都是一样有用的。许多简单的归纳方法都使用这种方式，例如 感知算法、最近邻方法和一些增量连接方法，它们只从弄假它们当前假设的 样本中学习。这些嵌入式方法有时也叫做保守算法，即忽略了算法假设为真 的所有样本。 2 过滤式特征选择 过滤式特征选择的评估标准独立于学习算法，直接由数据集求得。过滤 式特征选择的评估依赖于数据集本身，通常是选择和目标函数相关度大的特 西南交通大学硕士研究生学位论文第1 1 页 征或特征子集，一般认为相关度较大的特征或者特征子集会对应得到后续学 习算法较高的准确率。过滤式特征选择的评估方法很多，如类间距离、信息 增益、关联度( c o r r e l a t i o n ) 及不一致度等等。过滤式特征选择应用不是十分 广泛。一般过滤器模型的时间复杂度较低，准确性不高，因其运行效率高而 适用于大规模数据集。 讲练数据 特征空间搜索机 j 墨定的特征子集 i 学习算法 特征子集特征评价结果测试致据 全部特征集合 基于训练数据的特征评价标准f i 图2 1 过滤式特征选择一般流程 3 封装式特征选择( w r a p p e r 式) 该算法的核心思想是：和学习算法无关的过滤式特征评价会和后续的分 类算法产生较大的偏差，而学习算法基于所选特征子集的性能是更好的特征 评价标准。不同学习算法偏好不同的特征子集，既然特征选择后的特征子集 最终将用于后续的学习算法，那么该学习算法的性能就是最好的评估标准。 因此在w r a p p e r 特征选择中将学习算法的性能作为特征选择的评估标准。 i 1 1 i 练教据 特征空间搜索机i - - - 选定的特征子集 - _ 学习算法 特征子集特征评价结果 讲i 练数据 全部特征集合 学习算法i l 图2 - 2w r a p p e r 特征选择一般流程 由于采用学习算法的性能作为特征评估标准，w r a p p e r 特征选择算法比 过滤式特征选择算法准确率高，但时间复杂度较高、算法效率较低。因此 些研究者努力寻找使评价过程加速的方法。随着数据量和特征维数的不断增 长，过滤器模型更具有现实意义。 西南交通大学硕士研究生学位论文第12 页 2 2 2 按搜索策略划分 按搜索策略划分特征选择算法。特征选择算法从原理上可以分为非搜索 性和搜索性算法二种。大部分常用算法都是搜索性特征选择算法。它利用一 定的评价准则对所得的子集进行评估，选取最佳特征子集，通常都包含着一 个搜索过程。常见搜索算法包括传统算法、遗传算法( g a ) 、模拟退火算法 ( s n ) 、t a b u 搜索算法( t s ) 和神经网络算法( n n ) 。传统算法实际是搜索 有向图，包括顺序前进法( s f s ) 、顺序后退法( s b s ) 、顺序浮动前进法( s f f s ) ， 增n 减1 法( p t a ) 、分支界定法( b b ) 等。 2 2 2 1 搜索算法的分类 而搜索算法根据其进行特征选择所用的搜索策略可以把特征选择算法分 为采用全局最优搜索算法，随机搜索策略或启发式搜索策略三种特征选择算 法。 1 到目前为止，唯一应用全局最优搜索策略得到最优结果的特征选择方 法是“分支定界”( b r a n c ha n d b o u n d ) p l j 算法。该算法的主要思路是：定义 一个评价准则函数，该评价准则函数必须满足单诵性条件，也就是，对两个 特征子集j 1 和j 2 而言，如果j 1 是j 2 的子集，那么一所对应的评价函数值必须 要小于s 2 所对应的评价函数值。在定义了该评价函数的前提下，该算法对最 终特征子集的选择过程可以用一棵树来描述。树根是所有特征的集合，从树 根往下，在树的每一级每一支都舍弃一个特征，而后根据可分性判据值和事 先定义的最佳特征子集的特征数目，搜索满足要求的特征子集。这个过程中 可使用各种树搜索算法，用以加速搜索效率，提高运行速度。 2 采用随机搜索策略的特征选择算法。这是一种非全局最优方法，它在 计算过程中把特征选择问题和模拟退火算法、禁忌搜索算法、遗传算法等结 合起来，以概率推理和采样过程作为算法的基础，基于对分类估计的有效性， 在算法运行中对每个特征赋以一定的权重，而后根据用户所定义的或自适应 的阚值，它就被选中作为重要的特征来训练分类器。这里对特征重要性的评 价既可以采取特征的统计得分，也可以采用特征对分类器的贡献率。遗传算 法在这一领域的应用最为广泛，在后面的章节中会有更详细的介绍。 3 采用启发式搜索策略的特征选择算法。主要有以下几种算法： ( 1 ) 单独最优特征组合：该方法依靠计算各特征单独使用时的判据值，然 后对特征加以排队。取前d 个特征为满足条件的特征组。这种方法仅当单个 西南交通大学硕士研究生学位论文第1 3 页 特征的判据值满足加和性或者乘性条件的时候才能选择出一组最优的特征。 但是在很多情况下，该方法可以用来去掉一些不重要的变量，是一种较好的 预处理方法。 ( 2 ) 序列前向选择算法( s f s ，s e q u e n t i nf o r w a r ds e l e c t i o n ) ：该方法也称 为集合增加法。它是一种自下而上的搜索方法。先把所需要的特征集合初始 化为一个空集，每一次向特征集合中增加一个特征直到到达最后的特征集。 该过程可以描述为：设所有的特征集合为q ，假设有一个已有西个特征的特 征集以。，对每一个未入选特征鲁( 即q 一以。中的特征) 计算其准则函数 5 ，= j ( x 。+ 掌，) 。选择使j ，最大的那个特征，并把它加入到集合j 匕中。实际 上，在算法的每一步，都选择了一个特征加入到当前集合，使得特征选择准 则最大。当最佳改进使得特征集性能变坏或达到最大允许的特征个数的时候， 该算法认为已经选择出最佳特征子集。该算法运算量相对较小，但是特征之 间的统计相关性没有得到充分的考虑。从这个角度出发的搜索方式仅能适合 - d , 部分满足特征条件的特征集合。 ( 3 ) 广义序列前向选择方法( g s b sg e n e r a l i z e ds e q u e n t i a lf o r w a r d s e l e c t i o n ) ：该方法是s f s 算法的加速算法，它可以根据准则函数一次性向特 征集合中增加r 个特征。也就是在没有入选优化特征子集的剩余的特征集中， 寻找一个规模为r 的小特征集r ，使得j ( _ 0 + ，：) 最大。该方法相对于s f s 在特征统计相关性上要好些，但是计算量相对s f s 增加了许多，且在s f s 中 出现的闻题依旧难以避免。 ( 4 ) 序列后向选择方法( s b s ，s e q u e n t i a lb a c k w a r ds e l e c t i o n ) ：该方法是 一种自上而下的方法。该方法在运行之初假定整个特征集合就是所需要的优 化特征集。而后在算法的每一步运行过程中删除一个对准则函数无贡献的特 征，直到剩余特征个数符合集合基数要求。该方法在一个较大的变量集上计 算准则函数，所以该算法相对于s f s 计算量要大。该方法的优势在于充分 考虑了特征之间的统计相关特性，因而在采用同样合理的准则函数的时候， 它的实际计算性能和算法的鲁棒性要大大优于s f s 算法。 ( 5 ) 广义序列后向选择方法( g s b s ，g e n e r a l i z e ds e q u e n t i a lb a c k w a r d s e l e c i o n ) ：该方法是s b s 算法的加速算法，它根据准则函数在算法的每个循 环当中，一次性删除一定个数的无用特征。它是一种可以应用于实际过程的 西南交通大学硕士研究生学位论文第1 4 页 快速特征选择方法。它的优点在于速度较快，性能相对较好。不足之处在于 有的时候，特征消除操作进行的太快，容易丢失重要的变量，导致找不到优 化的特征组。 ( 6 ) 增f 去，的选择方法：这种方法允许在特征选择的过程中进行回溯。如 果 ，则该算法是自下而上的方法。用s f s 方法将个特征加入到当前特征 集中，然后再用s b s 方法删除，个最差的特征。这种方法消除了嵌套问题， 因为某一步获得的特征集不一定是下一步特征集的子集。如果， 三对应的前k ( k p ) 个主成分。 i ，lf i 2 4 2 。因子分析 因子分析的核心是用较少的互相独立的因子反映原有变量的绝大部分 信息。可以将这思想用数学模型来表示。设原有p 个变量_ ，x ：，而，石， 且每个变量( 或经标准化处理后) 的均值均为0 ，标准差均为1 。现将每个原 有变量用k ( k t ， 则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止运算。 其流程图如图4 1 所示。 4 2 遗传算法用于暂态稳定评估的特征选择 4 2 1 利用遗传算法进行特征选择的过程 + i 初试化群体【7 3 - 7 5 ：令进化代数t = 0 ，生成初始群体p ( t ) 。各种遗传算法 的实施过程基本类似，所不同的是针对问题的具体编码方式和适应度函数的 实现过程。特征选择问题是从数据样本最初的d 个特征变量中选择出其中的 d 个特征。在用遗传算法解决这个问题时，可采用二进制染色体编码，即用 一个d 位由0 或1 构成的字符串表示一种特征组合，数字1 表示对应的特征 西南交通大学硕士研究生学位论文第4 0 页 j开始 4 1 , - 输入原始数据， g e n = 0 4 1 - 染色体编码，产生 初始群体 计算群体中每个个j 。 体的适应度函数值i 、 j | 选择 j 善 g e n = g e n + 1 交叉 i1 l 变异 l ii 新一代群体 i 叁 i v 输出结果 图4 - 1 遗传算法原理图 被选中，数字0 表示对应的特征未被选中。为了加快收敛，在产生初始群体 时，假设绝大多数特征变量都将被选择，对字符串中的每一位以0 9 的概率 取值为l 。 2 定义适应度函数： 西南交通大学硕士研究生学位论文第4 1 页 适应度函数也称为评价函数，是根据目标函数确定的用于区分群体中个 体好坏的标准，是算法演化过程的驱动力，也是自然选择唯一的依据。 - 为了得到对稳定效果最有效的特征，本文采用基于类内类间距离7 2 1 的可 分判据以作为适应度函数，具体定义如下： j 4 = t r ( s b 名( 艺) = ( 4 - 1 ) 其中： = 只( 啊一所) 7 ( 鸭一所) i t l ( 4 2 ) c 1_ r = p ( t “一) ( x k “一啊) 一17 t 。1 ( 4 3 ) r r 最= p ( 一埘) ( 一肌) f - l ( 4 4 ) 瓯：童p 上窆( 工k m - - m j ) ( 以一职) 7 瓯= p ( 工“1) ( 以“一职) 。 ，_ i2 2 1 ( 4 5 ) ：三争以( ) 。啊智 m = 跏 ( 4 6 ) ( 4 7 ) 式中，巩表示第i 类样本集的均值向量；所表示所有各类的样本集总均 值向量；称配为类间离散度矩阵；瓦为类内离散度矩阵；矗为类间离散度； 毛为类内离散度。直观上，希望被提取特征的类间离散度矗尽量大，类内离 散度j 。尽量小，则以越大，这样有利于分类。 3 计算群体中每个个体的适应度函数值，将个体解码，选中个体中基因 位为“l ”的特征( 对应到原解空间) ，组成一个新的空间，用类内类间距离 判据计算其适应度值。将第一次迭代具有最高适应度值的个体作为第一次迭 西南交通大学硕士研究生学位论文第4 2 页 代的最优解，记录其适应度值。对于第二次迭代以上的个体，将这一代计算 所得的最大适应度值与记录适应度值相比较。若小于记录值，则记录值保持 不变：若大于记录值，则将这一代具有最大适应度值的个体作为群体中的最 优解，修改记录值。 4 进行选择、交叉和变异操作，产生下一代。 5 重复3 ) 、4 ) ，直至进化代数超过给定的最大进化代数为止。特征选择 的结果就为最后一次迭代后群体中的最优解。 4 2 2 遗传算法中的控制参数的选择 遗传算法中的控制参数的选择非常关键，控制参数的不同选取对遗传算 法的性能产生较大的影响，影响到整个算法的收敛性。这些参数包括群体规 模n 、进化代数m 、编码长度、交叉概率、变异概率只等。 优化过程中，交叉概率始终控制着遗传算法中起主导地位的交叉算子， 不适合的交叉概率会导致意想不到的后果，交叉概率控制着交叉操作被使用 的频度：较大的交叉概率可使各代充分交叉，但群体中的优良模式遭到破坏 的可能性增大，以致产生较大的代沟，从而使搜索走向随机化：交叉概率越 低，产生的代沟就越小，这样就将保持一个连续的解空间，使找到全局最优 解的可能性增大，但进化的速度就越慢；若交叉概率太低，就会使得更多的 个体直接复制到下一代，遗传算法可能陷入停滞状态，所以一般建议p 的取 值范围是o 4 - - - 0 9 9 。 变异概率控制着变异操作被使用的频度，变异概率的取值较大时，虽然 能够产生较多的个体，增加了群体的多样性，但也有可能破坏掉很多好的模 式，使得遗传算法的性能近似于随机搜索算法的性能；若变异概率取值太小， 则变异操作产生新个体和抑制早熟现象的能力就会较差。 交叉运算是产生新个体的主要方法，它决定了遗传算法的局部搜索能力， 交叉算子和变异算子相互配合，共同完成对搜索空间的全局搜索和局部搜索。 从而使得遗传算法能够以良好的搜索性能完成最优问题的寻优过程。 群体规模的大小直接影响到遗传算法收敛性和计算效率。规模过小容易 收敛到局部最优解，规模过大，会造成计算速度降低，根据实际情况以1 0 2 0 0 为佳。 本文对要处理的数据进行一系列仿真，通过对结果的分析和比对，从中 找寻到较合适的控制参数。下面以i e e e l 6 机系统为例，介绍遗传算法中参 西南交通大学硕士研究生学位论文第4 3 页 数的选择问题。 设定种群规模为n = 2 0 ，个体长度( 编码长度) 1 0 ，进化代数m = 1 5 0 。 1 ) 设定交叉概率只= 0 7 ，变异概率只= 0 1 。 如图4 2 所示，随着进化的进行，群体中的个体趋于相同，最终趋于最 优解，证明所选择的进化代数是足够的，交叉概率和选择概率是恰当的。种 群均值在4 0 代之后总体上已经趋于稳定，上下波动是因为受到变异的影响。 由模式定理和积木块假设可知，随着进化的进行，平均适应度高的模式 增多，这些模式慢慢拼凑、叠加，逐渐形成较优解，并最终得到最优解。 i 二_ 嚣錾骛酱的变化 广 厂j 。 一 ，。j 、吣“，、饥，r 。r v o一? r 、f 、 ；，“l ， ， 图4 - 2 经过1 5 0 次迭代后最优解的变化和种群均值的变化 2 ) 设定其他参数不变( 变异概率己- - - - 0 1 ) ，交叉概率= 0 7 、0 8 、0 9 。 图4 3 所示，只= o 9 时，曲线上升势头最猛，算法最先收敛到最优解。但只 并不是越大越好，只越大，种群中参与交叉操作的的个体就越多，就有可能 破坏群体中优解的结构。 西南交通大学硕士研究生学位论文第4 4 页 嚣g 删嚣* 肺嚣” ”一例靴4 “”5 哗”# ”5 僦哪w ! 呻州垆妒一麟”铷 p c - - - 29 i l p c - - - 08 ， l p c - - 0 7 _ j i r 。r 。 f 毫一：。 矿 )45 0 。 。 1 0 0 一”5 i 1 1 一，“一。0 7 。舭t ! 一。一 ； “n 图4 - 3 交叉概率只= o 7 、0 8 、0 9 时最优解的变化 3 ) 设定其他参数不变( = o 7 ) ，变异概率只= 0 0 5 、0 1 图4 4 可以看出，只= o