（信号与信息处理专业论文）遗传算法在网络告警预测中的应用.pdf

遗传算法在网络告警预测中的应用 摘要 近些年来，随着电信运营商电信网络的不断扩大和升级，网络产 生的告警越来越多，越来越复杂。面对着这些繁多复杂的电信网络告 警，运营商希望能够有效地解决网络告警过多而产生的问题，并且能 够预测和控制网络告警。所以，网络告警预测就成为当前研究网络告 警问题的几个重要领域之一。本论文针对此目标，利用遗传算法的寻 优特性，设计并完成了遗传算法在电信网络告警预测问题中的应用， 使我们提出的算法能够满足面向纷繁复杂的电信网络告警数据进行 大规模、实时性的告警数据关联挖掘的要求。论文的主要工作包括以 下几点： 1 ) 对预测模式挖掘方法的发展过程做了一个较全面的研究，针对 实际应用的特点，对遗传算法的进行一些尝试性探索。 2 ) 在设计与开发算法的过程中，对相关遗传算法和关联规则挖掘 的目前一些较新的研究成果，如：r i c e ( r u l ei n d u c t i o no f c o m p u t e re v e n t s ，基于分类的预测模式挖掘方法) ，基于s v m 的告警预测模式挖掘( a l a 瑚sp r e d i c t i o np a t t e r nm i n i n g b a s e do ns v m ) 方法，基于序列模式挖掘的告警预测模式挖掘 方法( a l a r mp r e d i c t i o np a t t e r nm i n i n gb a s e do ns e q u e n t i a l p a t t e r nm i n i n g ) 等耳前比较先进的算法做了一定的学习与研 究。 3 ) 设计并实现了一个适合于实际电信网络应用的网络告警关联 规则挖掘系统。在电信网络告警关联规则挖掘平台的原型系统 开发过程中，笔者完成了基于遗传算法的网络告警关联规则挖 掘算法的设计和实现工作，同时也参与了平台告警地域分析模 块的设计和开发工作。 本论文的意义在于，在目前基于遗传算法的网络告警数据关联规 则的挖掘技术研究尚不太成熟的情况下，在该平台当中实现的基于遗 传算法的网络告警关联规则的挖掘算法具有一定的实际意义，同时设 计和实现的该算法是采用模块化设计，可以集成到不同的系统当中， 所以对算法的移植和更广泛的应用有一定的实用价值。 关键词：关联规则遗传算法适应度函数 a p p l i c a t i o no fg e n e t i ca l g o r i t h m i nt h em i n i n go fn e t w o r ka l a r mr e g u l a t i o n a b s t r a c t i nt i l er e c e my e a r s ，w i t ht l l e r 印i dd e v e l o p m e n to ft h et e l e c o m n e t 、v o r k ，t h ea l a m l so f m et e l e c o mn e t w o r kh a v eb e e np r o d u c e dm o r ea n d m o r e t h eo p e r a t o r sa r em 描n gs o m er e s e a r c ht 0f i n ds o m ew a y st o r e d u c em en u m b e ro fn e t w o r ka l a r mm a k e l ec o n 仃0 1o fa i l dp r e d i c t s o m ei m p o r t 姐tn e 铆o r ka l a m s s om ep r e d i c to fn 酏w o r ka l a n i lh a s b e c o m eo n eo ft l l em o s t i m p o r t 觚tr e s e a r c h i n g f i e l d si i ln e t v m r k m a n a g e m e n td o m a i n t h i se s s a yw i ni n 昀d u c eg a ( g e n e t i ca l g o r i t h m ) f o rt l l ep r e d i c t i o no ft h en e t 、v o r ka l a ms y s t e ms o 脚a r e t h ef o l l o w i n g s a r ew h a tt i l ew r i t e rh a sw o r l ( e do nf o rt i l i sm e s i s ： 1 ) m a d e a g e n e r a ls t u d yo nt h ed e v e l o p m e n to ft h em i n i n g p r e d i c t i n gp a 船mt e c l l l l o l o 烈a i l dp r a c t i c e dat 锄p t i n gr e s e a r c ho n 吐l e f e a 协r e s 锄dm e t h o d sf o r l eg a ( g e n e t i ca l g o 枷蛐) 2 ) 0 i ln l ew a yo fd e s i 盟i n ga n dd e v e l o p i n gn l e1 1 1 i n i n gr e g u l a t i o n a l g o r i m lb a s e do ng a ( g e n e t i ca 1 9 0 r i t l l i n ) ，p a r t i a l l y 咖d i e ds o m e r e l a t e dn e wa l g o r i t l l i n s ，s u c h 够砒c e ( r u l ei n d u c t i o no fc o m p u t e r e v e n t s ) ，a 1 a r n l sp r e d i c t i o np a 批mm i n i n gb a s e do ns ，a l a n i l p r e d i c t i o np a t t e mm m i n gb a s e do n s e q u e m i a lp a t t e mm i n i n g 3 ) d e v e l o p e dap r o t o 妙p es y s t e mo ft h ep r e d i c t i n ga l 猢p l a t f o r n l f o rt h e p r a c t i c a lt e l e c o mn e t w o r k i nt h ep r o c e s so fd e v e l o p i n gt h e p l a t 土l o r mo fp r e d i c t i n gn e t w o r ka l a n i l ，ih a v et a k e np a ni i lt h eg e n e m l a n a l y s i so fm ew h o l es y s t e m ，a n dd e s i g l l e da n dd e v e l o p e dm em i n i n g r e g u l a t i o na l g o r i t l l mb a s e do ng a ( g e n e t i ca l g o r i t h m ) b ym y s e l t h em e a n i n go f t h i se s s a yi st h a tt h en e t w o r ka l a r n lm i n i n gp l a t f o m c a nm a k ep r a c t i c a lc o n t r i b u t i o nt ot 1 1 es o l u t i o nf o rn l ep r e d i c t i o no f n e 觚o r ka l a mi nm es i t u a t i o nt o d a yt h a tm er e s e a r c h e sf o rt h ep r e d i c t i o n o fn e t w o r ka l 猢a r en o tm a t u r ee n o u g h a n dt h em o d u l eo ft l l em i n i n g r e g u l a t i o na l g o r i t h mb a s e do ng a ( g e n e t i ca l g o r i m m ) i nm i ss y s t e m ， i m p l e m e m e db yt h em o d u l ed e s i g n ，s oi tc a nb e 缸e g r a t e di n t oo m e r m i n i n gr e g u l a t i o ns y s t e me a s i ly k e yw o r d s ：m i n i n gr e g u l a t i o n ，g a ( g e n e t i ca l g o r i t h m ) ，f i t n e s s 如n c t i o n 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料着有不实之处，本人承担一切相关责任。 本人签名：骞奎盆垂扭日期：曼生i ，芝12 l 1 f 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位 本人签名； 导师签名： 日期：之二塑：至：兰i ， 日期：至啤：i ：缉 北京邮电大学硕士学位论文遗传算法在网络告警预测中的应用 第一章概述 1 1 网络告警预测问题的提出 网络告警的预测模式是故障管理中的另一类重要知识，特别是对于某些重大 告警的预测模式来说更是如此。告警预测模式的实用价值在于：某些重大告警代 表了网络故障的发生，如“链路中断”“设备关闭”等“1 ，如果在其发生之前 做出准确预测，则意味着能够提前采取保护措施，避免网络故障的发生，极大地 提高网络的可靠性。同情景规则一样，网络的设备和系统之间的关联性为预测模 式的挖掘提供了可能：某些故障在发生之前总会出现一些“征兆”，反映在告警上 就是某些告警模式总是重复出现在表示故障的重大告警之前，如果这些模式出 现，重大告警也会以一个较高的概率在较短的时间内出现“1 。举一个简单的例子 来说，网络设备通常靠交流和直流两种方式供电，正常情况下靠交流供电，如果 交流电源中断，则采用直流电源供电，同时发出“交流电源中断”告警；随着直 流电源电量的逐步减少，设备又持续发出类似于“直流电源电量不足”的告警； 最终，直流电源电量耗尽时，设备关闭，其它设备又发出“某设备关闭”告警。 这里，如果把“设备关闭”作为表示故障的重大告警。】，那么“交流电源中断” “直流电源电量不足”则可以作为“设备关闭”的预测模式。 我们希望通过知识发现的手段“”“，从历史告警数据中挖掘出诸如此类的 针对某种特定告警的预测模式。然而，基于情景规则挖掘的方法并不能很好地完 成这种任务，尽管预测模式也是告警之间的一种关联关系，可以表示为情景规则 的形式“预测模式一特定告警”嘲，但二者有明显区别：情景规则主要用来滤 除大量重复出现的、冗余的相关告警，预测模式则用来预测一些重大告警( 即故障) 的发生“；情景规则挖掘要求规则中涉及到的告警发生足够频繁( 即满足最小支 持度) ，预测模式中所要预测的告警由于其严重性，发生次数一般比较稀少。因 此，用常规的情景规则挖掘的方法( 如w i n e p i 算法嘲) 难以找出期望的预测模式。 北京邮电大学硕七学位论文 遗传算法在网络告警预测中的应用 就目前国内外的研究情况看，基于数据挖掘的告警关联分析主要是集中在对 情景删则的挖掘上。，关于预测模式挖掘的研究则相对较少。g a r ymw e i s s 等 人较早研究了稀有事件预测的问题，提出了基于遗传算法的t i m e w e a v e r 算法。1 ， 能够从通信告警数据库中发现可预测小概率时间时序模式，并把该算法应用到 a n s w e r 故障预测系统中。i b m 的r v i l a l t a 和s m a 等在提出了一种计算机事件 规则归纳( r u l ei n d u c t i o no fc o m p u t e re v e n t s ) 方法，把预测模式的挖掘转化 成分类问题，根据历史数据构造学习样本训练分类器，从而生成一个基于规则的 告警预测系统。后来又出现了采用序列模式挖掘的方法，首先挖掘出目标告警之 前的频繁模式，然后找出其中预测性能最好的一部分作为预测模式。 总的来说，预测模式挖掘本质上可以看作是一个机器学习的问题，但是由于 待预测的告警发生次数非常稀少，所以问题的关键在于如何根据有限的样本获得 最佳的学习效果。 1 2 网络告警预测的数学模型 告警预测是一类比较特殊的时间序列分析问题，为便于下文讨论，首先抽象 出问题的数学模型。g a r ymw i s s 在 4 】中做过这方面的工作，本文在 4 】的基础上 做进一步的归纳。 如果把一条告警看作是某种事件e 在某时刻f 的一次发生，用髓表示，那么 历史苦警数据集就是单个告警组成的有序的事件序列s = b ，毋：，风， ，f - 1 ，以。同时，定义s ( ，f 2 ) 是s 中发生在 和f 2 之间的告警所组成的 子序列。我们所要预测的某种特定告警称之为目标事件，用t a 唱e t 表示。 t mtt wt + w 十p 图卜1 告警预测的阶段划分 2 北京邮电大学硕士学位论文遗传算法在网络告警预测中的应用 如图1 1 所示，告警的预测可分为三个阶段：监测期，长度为吖，系统或 用户记录出现在监测期的所有告警，将其与事先建立的告警预测模型进行模式匹 配，若匹配成功，则在，时刻预测t a r g e t 将要发生：预警期，长度为，其作用 在于保证在t a 唱e t 发生前留给用户一定的时间以采取必要的保护措施。因此，时 刻，预测的t a 唱e t 应该发生在f + 之后才有意义；预测期，长度为p ，就是预 测t a 昭e t 所应出现的时间区间( 精确到时间点的预测可以通过调整预警期和预测期 的长度实现) 。如果时刻f 的预测结果与预测期的实际情况( 喇在预测期发生或 不发生) 相吻合，则认为是一次正确的预测，反之则认为是错误的预测。 按照上述定义，如果b ，点屯，必是发生在f 一肼时刻与f 时刻之间的告警序 列，即s o 一膨，) ，那么对t a 唱e t 的预测可以归纳为如下二分类的决策函数： 鸺鳓渺 _ 1 = i 嚣：z ：篇 枷 称式( 1 - 1 ) 中预测t a 唱e t 发生为“正预测”，预测t a r 苫c t 不发生为“负预测”。为便 于讨论，本文定义“预测模式”就是决策函数厂( ) ，可以是显式的规则，也可以 是抽象的分类函数。预测模式挖掘的任务就在于基于历史告警数据构造决策函数 ，( ) ，使之具有尽可能好的预测性能。 作为对预测性能的评估手段，【5 】中主要提出了“准确率”( p r c c i s i o n ) 和“召 回率”限e c a l l ) 两种指标，分别衡量了对t 鹕e t 预测的准确性和全面性，具体定义 为： 胁砌= 鼎r e 蒯= 襞糌如仞 7 1 p + f p 全部的幼，驻f 数量 、 其中，r 尸为判断t a r g e t 发生且结果正确的预测数，f p 为判断t 鹕e t 发生但结果错 误的预测数。后来为了进一步细化准确性的指标，提出了a c c a c c + 和a c c 三个 指标，分别定义为：a c c 是全部预测中正确预测的比例；a c c + ( a c c - ) 是正( 负) 预测 中正确预测的比例。可见，a c c + 和p r e c i s i o n 的物理含义是相同的，二者是同一个 指标。 北京邮电人学硕：卜学位论文遗传算法在网络告警预测中的应用 1 3 论文内容及安排 本文尝试将改进的遗传算法应用到实际的电信网络告警关联规则挖掘系统 中，以提高电信网络告警关联规则挖掘的性能【2 5 1 ，主要是作为其他网络告警关 联规则挖掘算法的补充，以发现其他算法无法发现的潜在关联规则。本文所阐述 的算法设计是基于为某移动运营商实际开发的网络告警关联规则挖掘平台为基 础，以实际的网络告警数据库作为挖掘对象，以适应度函数作为评价准则，对挖 掘结果进行比较分析，以确定遗传算法对于电信网络告警关联规则挖掘具有的优 势。 首先本文在第一章简要介绍了网络告警预测问题并提出其数学模型。在接下 来的第二章里，详细介绍了网络告警预测技术研究现状，包括候选预测模式挖掘 算法，分类挖掘算法，支持向量机的挖掘算法，以及在本文中将详细介绍的基于 遗传算法的挖掘算法。在第三章里，将对遗传算法的原理和应用进行详细说明和 介绍，包括遗传算法的基本原理，特点，收敛性等等。在第四章里，我们根据电 信网络告警预测问题的实际情况，分析并设计出在电信网络环境中可行的基于遗 传算法的告警关联规则挖掘算法。在第五章里，对本文提出并实现的算法的实验 结果进行分析并进行尝试性的算法改进和探讨。最后，对本文的工作进行总结和 展望。 4 北京邮电大学硕士学位论文遗传算法在网络告警预测中的应用 第二章网络告警预测技术研究现状 数据挖掘是通过分析，从大量的历史数据中发现各种各样的模式，它是基于 过去事例的泛化的一种归纳学习【6 j 。将数据挖掘中的关联规则发现技术用于分析 历史告警数据，可发现告警相关性规则。根据发现的规则，来分析和预测网络元 件可能出现的故障，可减轻了网络管理员的工作强度，提高了工作效率。数据挖 掘可以通过分析已有的警告信息的正确处理方法以及警告之间的前后关系的记 录，得到网络告警之间的关联规则，这些有价值的信息可用于网络故障的定位检 测和严重故障的预测等等任务中。根据当前的警告信息，就可以得到其后续发生 各种情况的可能性，对危险事件可以起到预防的作用，从而使通信网络得以安全 运转。 数据挖掘方法用的优点是不需要知道网络拓扑结构关系，当网络拓扑结构发 生变化时，可以通过告警的历史记录进行分析，自动发现新的告警相关性规则， 因此基于数据挖掘告警相关性系统能够可以很快调整适应一些变化快的通信网 络，解决通信网络中出现的新问题。 预测模式挖掘的方法通常基于这样一种假设，即如果一个故障是由网络其它 部分的异常引起的，那么它们之间的这种关联性必然反映到告警数据中对应 于该故障的告警t a r g e t 与其预测模式之间也应该存在着相关性( 如图2 一l 所示) ，当 预测模式发生时，诅唱e t 也应该在一个相对较短的时间内发生。下面简要介绍现 有的预测模式挖掘方法。 锋警类型 t 3 t 2 t l 图2 1 预测模式和目标事件 北京邮电大学硕士学位论文遗传算法在网络告警颅测中的应用 2 1 基于序列模式的挖掘 r v i l a l t a 【1 6 j 【1 7 j 等研究了基于序列模式挖掘的告警预测模式挖掘方法( a l a n n p r e d i c t i o np a n e mm i n i n gb a s e do ns e q u e m i a lp a 舵mm i n i n g ，不妨简称为a p p m s p m ) 。其思想是如果一个模式z 能够准确地预测t a 略e t ，那么z 应该频繁地出 现在t a r g e t 之前较短的一段时间内。但是，出现在t a f g e t 之前的频繁模式并不一 定都是真正的预测模式，因为其中有一些模式的发生与t a 唱e t 是否发生并无必然 的联系，从整个时间段上看，这些模式都是频繁发生的，所以这些模式作为噪声 必须滤除。 l 司此，a p p m - s p m 算法包含三个步骤：特征提取，候选预测模式挖掘模式评 价。 1 ) 特征提取 记录每一个t a 唱e t 之前的告警片断，为下一步挖掘候选预测模式做准备。具 体做法是扫描告警序列s ，对于s 中的每一个告警毋，抽取发生在r 之前w 折而 ， 时间窗内的所有告警数据s o w f ”如w ，f ) ( j 加面w 是一个固定值，宽度为监测期 的长度) 。若毋为t a 唱e t ，则将s ( f w 加d b w ，) 作为该t a 唱e t 的特征事务r ，插入到 t a 唱e t 特征数据库d 中，否则将s o w 眺如w r ) 插入非t a r g e t 特征数据库d 。以上 的特征选择没有考虑预警时间形，如果考虑的话，则s ( f w 加面w ，) 改为 s o w 加d b w 一矽，f 一降7 ) ； 2 )候选预测模式挖掘 目的是找出d 中的频繁告警模式作为候选的预测模式。挖掘频繁告警模式可 以采用关联规则挖掘的方法，把特征数据库d 作为事务数据库，利用a p r i o r i 嘲、 f p w m 州等算法挖掘出d 中满足最小支持度的频繁告警模式： 3 )模式评价 作片j 在于评估每一个候选预测模式z 的预测性能，选择预测性能最好的一部 分作为最终的预测模式，其余作为噪声模式滤除。r l a l t a 首先采用置信度 6 北京邮电大学硕士学位论文遗传算法在网络告警预测中的应用 ，孵出艘作为评估标准，令d 和d 中包含z 的事务数分别为而、而，则： ，矿d b n c p ( z ，d ，d = 而( 玉+ 而) 式( 2 一1 ) 所有低于最小置信度的z 被认为是噪声模式加以滤除。为了保证z 与t a 玛e t 是一 种正相关的关系，r v i l a l t a 把z 出现在d 中的概率p ( z l d ) 必须大于出现在d 中 的概率p ( zd 作为第二个评估标准。最后，同时满足两个评估标准的z 组成基 于规贝l l 的预测系统。 2 2 基于分类方法的挖掘 r l a l t a 【】5 】提出的c e ( r m ei i l d u c t i o no fc o m p u t e re v e n 协) 是一种基于分类 的预测模式挖掘方法，r j c e 认为t a 曜e t 与其之前的告警发生情况之间是一种类属 性( t a 唱e t 发生或不发生) 与特征( 胁鲥之前的告警片断) 的关系，因此把预测模式挖 掘的问题转化成一个分类问题，然后由学习样本训练决策树分类器，最后输出对 于t a 唱e t 的分类规则，也就是预测规则。 r j c e 方法包括特征提取分类器训练、规则输出三个主要步骤： 1 ) 特征提取 特征提取的作用是对t a r g r e t 和非t a r g e t 两类形成学习样本，为下一步训练分类 器做准备。具体做法是扫描告警序列s ，对于s 中的每一个喇，形成一个正样 本；若t a r g e t 发生时刻为f ，则抽取发生在f 之前w 加面w 时间窗内的所有告警数据 s ( r w 加面嵋f ) ( w 铆面w 是一个固定值，宽度为监测期的长度) 作为该样本的特 征。同a p p m s p m 一样，如果在特征选择中考虑到预警时间w ，则s ( f w f ，砌w r ) 改为s ( f w 伽砌w 一，一) 。为了使样本的维数固定，用向量z = ( 1 ，2 ，册) 来表示s ( ，一w f 删b w f ) 。其中，m ，f = l ，2 ，埘表示第f 种告警类型在 s ( f w 胁如，) 中的发生次数，m 为全部告警类型的数量，图2 2 显示了全部告警 类型为t l 、t 2 ，t 3 时的正样本形成方式。对于负样本，为了使其数量与正样本平衡， r j c e 采用了一种折衷的方式，若两个相邻的t a 唱e t 发生时刻分别为，2 ，则令最 7 北京邮电人学硕士学位论文遗传算法在网络告警预测中的麻用 靠近( + f ：) 2 时刻的告警为非t a r g e t ，按照与正样本相同的方式构造负样本。 告警娄型 b 1 2 t i z l 。( 1 ，2 ，1 ) z 2 1 ，0 ，l 卜纠 ： ： ： l 饵嘈嚣 时螭 图2 2 全部告警类型为t ，t 。、t 3 时的正样本形成方式 2 ) 分类器训练 对上一步形成的样本集合训练，构造分类模型。由于期望结果是显式的规则 集，所以r j c e 采用决策树的方式学习。 3 ) 规则输出 对训练的树模型生成分类规则，r j c e 取预测性能最好的k 条规则作为预测 规则输出。 2 3 基于支持向量机的挖掘 通过前面的讨论发现，历史告警数据的一个显著特点是t a r g e t 所占的比例很 小。这也就意味着，如果把预测模式挖掘的问题看作是机器学习的问题，那么对 应于t a 曜e t 的正样本很少。因此，需要基于少量的正样本构造性能尽可能好的分 类器。支持向量机( s v m ) 作为一种机器学习方法【2 2 】【2 3 】，由于满足结构风险最小化 原则，即使在较少的样本集上训练也能获得好的推广能力。这一特点，刚好与 t a 唱e t 的稀有性相适应。 另外，非t a r g e t 提供的信息也应得到重视，因为这会显著影响预测的准确性。 从这个角度上看，a p p m s p m 方法和r j c e 方法只是较少利用了非t a 玛e t 的信息： a p p m s p m 方法重点对d 进行了挖掘，而没有进一步分析d 的内容；i u c e 方法 把位于两个相邻t a r g e t 中点的告警作为非t a r g e t 构造负样本，在一定程度上利用了 8 嗨 北京邮电大学硕士学位论文 遗传算法在网络告警预测中的应用 非t a r g c t 的信息，但没有充分利用。为进一步提高准确率，需要增加对非t a l g e t 采 样。 在此，本文也简单介绍基于s v i v i 的告警预测模式挖掘( a j a 衄sp r e d i c t i o n p a t t e mm i n j n gb 勰e do ns v m ，简称a p p m s v m ) 方法，如图2 3 所示，a p p m s v m 主要包括特征提取预处理s v m 分类器训练三个步骤。 r 一一一。一一1 ii 一眚蝴 回圈蝴奉盛引+ ： l 一一j 图2 3 基于s 的告警预测模式挖掘 1 ) 特征提取 特征提取是抽取出现在各监测期内的告警序列( 作为样本特征) 以及对应的 预测期内t a r g e t 是否发生( 作为样本类标号) 的记录，形成原始样本，以便为下一步 生成学习样本做准备。具体来说，就是采用一个滑动的观察窗口明，i 又是 由三个子窗口组成：监测窗一预警窗一预测窗，长度分别对应于图2 1 中监测期 预警期预测期的长度。令矽以单位步长从告警序列的起点向终点滑动，每次 滑动所形成的窗口相当于对告警序列作了一次采样，记录该次采样中出现在监测 窗的告警序列目，e 如，五t 以及预测期内t a r l r e t 是否发生( + 1 或- 1 ) ，作为一个原始 的样本记录。图2 3 反映了告警腓为t 哦渺的特征提取过程。 可以看出，滑动窗口的特征提取方式有别于a p p m s p m 和r j c e ：图2 4 中， 只要有t a r g e t 出现在预测窗内，就形成一个正样本：而a p p m s p m 和r j c e 的方式 则可以理解为，只有t a r g e t 出现在预测窗的起点时才形成一个正样本。显然，滑 动窗口的特征提取方式有助于形成更多的正样本，增加对t a 唱e t 的先验知识。当 然，滑动窗口也会产生更多的负样本，如果数量很大，可以均匀抽取一部分去训 练。 9 北京邮i 乜人学坝l 学位论文遗传算法在网络告警顶测中的应用 cbcefobecefc 蜊 譬= ：7 i le f d ) ii 1 i 一一。? 滑动方向 “ i ! ! 墅! ii ：! i 图2 4 特征提取的过程 2 ) 预处理 预处理是对特征提取后形成的原始样本作进一步处理，以形成便于学习的样 本。首先要将样本的特征变成固定维数的特征向量，这里采用r j c e 的方法， 用( 研，皈，巩) 来表示。其中，矿= 夕p g ( e ) ，巨表示第衍十告警类型f = 1 ，2 ， ，户叼( ) 表示某类告警在当前监测窗内的发生次数，这样就可以把样本的特征 维数固定为全部告警类型的数量。注意，特征向量并没有保存出现在监测窗 内告警i q 的时序关系，这是由于网络延迟的不同会导致各个告警的到达次序具有 一定随机性，不考虑时序因素正是为了屏蔽这种随机性，同时也是为了降低学习 的难度a ( 斫，巩，如) 作为特征的样本已经可以用来训练s v m ，但考虑到个别 高频告警对其它中低频告警的抑制作用，利用信息检索领域的t f i d f 公式对监 测窗内各告警的出现频率做均频处理，特征进一步表示为( w l ，w 2 ，i ) 。计算公 式为： 班爰恭 引2 彩 其中，w ( d ) 为告警f 在监测窗d 中的权值，矿( d ) 为告警f 在监测窗d 中的出现次 数，m 是滑动形成的f 聊的总数，分母是归一化因子。 3 ) s v m 分类器训练 经过特征提取和预处理，假定收集到m 个训练样本，即 _ ，乃) 卅i 。，是第j 个样本的特征向量，”是箭个样本的类标号，取值为l 或一l 。采用标准s v m 方法， 1 0 北京邮电大学硕士学位论文遗传算法在网络告警预测中的应用 为t a r g e t 构造一个非线性的s v m 预测器： 五m o ) = ：。哆乃k ( x ，_ ) + 6 式( 2 3 ) 其中，q 是l 删g e 乘子，通过求解以下二次规划问题得到： 彻咖托棚：q ( 口) = 二q 一三幺。q 乃咒k ( 一t ) 勋够耐f d ：二。乃d 。= oo q sc + ，乃= 1 式2 - 4 o q c ! ，乃= 一l 考虑到正负样本数量不均衡，所以式( 2 - 4 ) 中对正，负两类采用了不同的惩罚 参数e ，e ，根据第三章中的分析，为训练样本少的类分配更大的惩罚参数，本 文取c = 以，+ ) c c - = c ，( t 、，+ 分别是两类训练样本的个数) 。 对于核函数，我们选用比较常用的径向基函数r b f ： 足( ，) = e x p ( 一y 0 _ 一0 2 ) 式( 2 - 5 ) ， 关于c 和，的选择，采用 】中推荐的如d - s e a r c h 方法，即分别列出c 和，可能 的取值，每次各取出一个值构成( c ，) 对训练集做交叉验证，选择效果最好的一 组【c ，) 作为核参数。选择这种方法的理由是：对于不同的实际问题，任何一种 参数估计方法不能保证是最有效的，并且参数估计本身也会占用一定的计算开 销，而鲥d - a r c h 则可以保证找到合理的参数。由式( 2 - 4 ) 式( 2 5 ) ，可解得 t a r g e t 的决策函数为： 五。( 石) = 。，哆乃e x p ( 一，肛一一n + 6 式( 2 6 ) 则s g n ( 石。( x ) ) 构成了t a r g e t 的预测模式a 2 4 基于遗传算法的挖掘 g a r ymw j i s s i l 4 】等从遗传算法的角度研究了预测模式的挖掘问题，提出了 n m e w e a v e r 算法。他们把预测模式的挖掘看作是一个进化的过程，个体就是告警 模式，告警模式的集合构成了进化的群体，而个体的适应度则用告警模式的准确 北京邮电大学硕七学位论文遗传算法在网络告警预测中的应用 率和召回率来综合评价。经过若干代的进化，产生预测性能较好的群体，从中选 出最好的一部分个体构成基于规则的预测系统。t i m e w e a v e r 的算法框架如下： 1 ) 初始化群体： 2 ) w f 据不满足停止条件 3 ) 从群体中选择两个个体： 4 ) 对选出的个体以概率p c 运用交叉算子，以概率p m 运用变异算子； 5 ) 评估新生成的两个个体的性能； 6 ) 用新生成的两个个体代替群体中的两个个体； 7 ) d b 疗p 算法中，停止条件可以是规定的迭代次数，也可以是群体的预测性能达到某 一指标。群体由告警模式组成，模式包括每个告警的数量告警的顺序以及持续 时间三项属性，典型的模式形式为“2 卯m d 叫4p v p 疗捃口耐3bp w 胛捃w f 肪加册 加w ”，最初的群体仅由单事件模式组成。交叉算子在两个个体上分别任选交叉 点，通过交叉形成新的个体，如“a l b c ”和“x y i z ”交叉形成“a z ”和“x y b c ”； 变异算子随机修改组成模式的告警类型，顺序以及持续时间。 个体的选择和替代兼顾两方面内容：既要在预测模式相对集中的空间里搜 索，也要考虑到个体的多样性，以便找到所有的预测模式。前者由f i t n e s s 来保证： 疗加鲫：耸善塑型坐竺! 掣 式( 2 7 ) l ，p r e c l s l o n + r e c n l | 是p r e c i s i o n 相对于r c c a l l 的重要程度，取0 到l 之间的值。 n i c h ec o u n t 则定义了一个个体与其它n 个个体之间的相似性： 竹缸砘c d 堋= ( 1 一咖砌c p ( f ，朋3 式( 2 8 ) j = l d i s t a i l c e 是这样定义的：每个模式具有一个特征向量，每维特征对应于t a r 舛的一 次发生，当该模式准确预测一次t a r g e t 是，该维特征取1 ，否则取0 。两个个体之 间的d i s t a i l c e 则是其特征向量取值不同的维数。 基于f i t n e s s 和i l i c h cc o u m ，t i m e 、e a v e r 提出了“共享适应度”( s h a r e df i t n e s s ) 指标，即f i 协e s s 和n i c h ec o u m 的比值，每次迭代选择s h a r e df i t n e s s 最高的两个个体 生成新的个体，代替s h a r e df i 协e s s 最低的两个个体。 北京邮电大学硕十学位论文遗传算法在网络告警预测中的应用 以上我们描述了基本的使用遗传算法进行网络告警挖掘工作的一般流程，本 论文尝试将遗传算法应用于实际的网络告警预测系统中。基于遗传算法的网络告 警预测技术同前面几节所描述的几种网络告警预测技术：基于序列模式的挖掘方 法，基于分类方法的挖掘方法，以及基于支持向量机的挖掘方法相比较，具有其 自身的特点和优势。以上所介绍的三种网络告警预测方法对于频繁模式的预测是 比较有效的，但是对那些重大网络告警预测模式的发现能力则是有限的。例如， 对于某些导致网络瘫痪的一些重大告警模式，其本身在网络告警数据库当中的发 生次数很少，本身并不是频繁模式，那么如果采用以上三种网络告警预测方法就 不是能够很好地发现这些重要的网络告警预测模式。虽然近年来有很多人提出了 对于这一类问题的解决办法，例如g a r ym w i s s 在预测稀少网络告警方面做了很 多工作，他的工作也是基于遗传算法，但是我们根据g a r ym w e i s s 文章所实现的 算法对于我们为运营商开发电信网络告警关联规则挖掘平台来说，其实际的应用 并不是很理想，主要原因电信网络告警预测模式具有特殊性，虽然遗传算法可以 解决稀少事件的预测问题，但是电信网络中告警关联规则模式的长短对预测算法 性能的影响很大，我们必须要根据实际情况对长预测模式和短预测模式进行处 理，这样才能够达到我们实际应用的要求。因此在本文的工作中，我们将以g a r y mw b i s s 的工作为基础，通过引入一个经验性的适应度函数： f ( f ) = a s ( 咖卜b a ( r ) + c c ( r ) 式( 2 一1 ) 其中，s ( r ) 为规则的支持度，a ( r ) 为规则的置信度，c ( f ) 为规则的覆盖度。在实验 中我们发现，通过选择不同的混和比例系数a ，b 以及c ，可以根据实际应用的 不同情况，达到挖掘频繁模式和稀有模式的目的。同时，由于算法中我们采用的 是变长度编码，通过引入惩罚因子对我们所不希望发生的模式进行惩罚，使种群 状态达到最优。最后，实验结果也初步证明了本文的设想。 北京邮电人学硕十学位论文 遗传算法在嘲络告警预测中的应用 第三章遗传算法的原理和应用 3 1 遗传算法的起源 生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然变异，基因遗传 等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出 的一种全局优化算法。遗传算法的概念最早是由b a g l e yj d 在1 9 6 7 年提出的； 而开始遗传算法的理论和方法的系统性研究的是1 9 7 5 年，这一开创性工作是由 m i c h i g a n 大学的j h h o l l a n d 【1 2 l 【1 3 1 所做出的。当时，其主要目的是说明自然和 人工系统的自适应过程。 遗传算法简称g a ( g e n e t i ca 1 9 0 r i t h i n ) ，其在本质上是一种不依赖具体问题的 直接搜索方法。遗传算法在模式识别，神经网络图像处理机器学习工业优化控 制，自适应控制，生物科学社会科学等方面都得到应用。在人工智能研究中，现 在人们认为“遗传算法自适应系统细胞自动机，混沌理论与人工智能一样，都 是对今后十年的计算技术有重大影响的关键技术”。遗传算法是基于自然选择， 在计算机上模拟生物进化机制的寻优搜索算法。在自然界的演化过程中，生物体 通过遗传( 传宗接代，后代与父辈非常相像) 、变异( 后代与父辈又不完全相像) 来适 应外界环境，一代又一代地优胜劣汰，发展进化。 g a 则模拟了上述进化现象。它把搜索空间( 欲求解问题的解空间) 映射为遗 传空间，即把每一个可能的解编码为一个向量( 二迸制或十进制数字串) ，称为一 个染色体( c h r o m o s o m e ，或个体) ，向量的每一个元素称为基因( g 删。所有染色 体组成群体( p o p u l a t i o n ，或集团) 。并按预定的目标函数( 或某种评价指标，如商 业经营中的利润，工程项目中的最小费用。最短路径等) 对每个染色提进行评价， 根据其结果给出一个适应度的值。 算法开始时先随机地产生一些染色体( 欲求解问题的侯选解) ，计算其适应 度，根据适应度对诸染色体进行选择交换变异等遗传操作，剔除适应度低( 性 能不佳) 的染色体，留下适应度高( 性能优良) 的染色体，从而得到新的群体。由于 1 4 北京邮电大学硕士学位论文遗传算法在网络告警预测中的应用 新群体的成员是上一代群体的优秀者，继承了上一代的优良性态，因而在总体上 明显优于上一代。g a 就这样反复迭代，向着更优解的方向进化，直至满足某种 预定的优化指标。上述g a 的工作过程可用图3 1 简要描述。 图3 一l 遗传算法工作原理示意图 遗传算法的基本思想是基于d 删i n 进化论和m e n d e l 的遗传学说的。d a 刑血 进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物 种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。 在环境变化时，只有那些能适应环境的个体特征方能保留下来。m e n d e l 遗传学 说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式 包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因 产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的 北京邮电丈学硕士学位论文 遗传算法在嘲络告警预测中的应用 后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。 由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在 这个算法中要用到各种进化和遗传学的概念。这些概念如下： 一串( s t r i n g ) 它是个体( i n d i v i d u a l ) 的形式，在算法中为二进制或者十进制串，并且对应于 遗传学中的染色体( c l u d m o s o m e ) 。 二群体( p o p u l a t i o n ) 个体的集合称为群体，串是群体的元素。 三群体大小( p o p u l a t i o ns i z e ) 群体中个体的数量称为群体的大小。 四基因( g e n e ) 基因是串中的元素，基因用于表示个体的特征。例如有一个串s = 1 0 1 l ，则 其中的l ，o ，1 ，1 这4 个元素分别称为基因。它们的值称为等位基因( a 1 1 e t e s ) 。 五，基因位置( g e n ep o s i t i o n ) 一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的 左向右计算，例如在串s = 1 1 0 l 中，0