（信号与信息处理专业论文）基于数据挖掘的网络故障告警相关性研究.pdf

北京邮电大学博士学位论文摘要 基于数据挖掘的网络故障告警相关性研究 摘要 现代电信网络管理的主要任务是对网络进行实时监控，确保电信 网络高效、可靠、经济和安全的运行。随着现代电信网络的规模越来 越大，结构日益复杂，对电信网络的告警数据进行相关性分析尤其重 要，因为从告警数据分析出的相关性知识，可以帮助网络管理人员及 时定位故障，保证电信网络的正常运行。传统的相关性分析方法由于 过多地依赖专家知识而难以适应网络复杂、多变的情况，采用数据挖 掘的方法则可以弥补这方面的不足。随着网络规模的增大，告警数量 的增加，如何从海量告警数据中发现电信网络中的告警相关性知识， 帮助网络管理人员处理网络故障，是当前网络故障管理所面临的主要 问题。 本文将数据挖掘技术应用到网络故障告警相关性分析中，研究了 频繁告警序列和非频繁告警序列关联规则的挖掘方法，取得了一定的 成果。本文的具体工作与创新包括以下几个方面： l 、告警序列模式( 频繁告警序列) 的挖掘 研究了电信网络中告警序列模式的挖掘问题。序列模式挖掘是在 关联规则挖掘的基础上发展起来的。目前序列模式挖掘方法大多基于 w i n e p i 的算法框架，由于该算法需要多次遍历数据库，执行效率较 低，因此本文基于f p g r o w t h 算法框架，提出一种基于f p 一树的序列 模式挖掘f s p m f p 算法。并且分别对其重要参数( 最小支持度) 和数 据库发生变化的情况，提出了相应的增量式挖掘算法s f s p m 即 和d f s p m f p ，并通过实验证明了算法的有效性。 2 、非频繁告警关联规则挖掘 针对目前告警序列模式挖掘算法受到最小支持度的限制，仅能够 得到高支持度、高置信度条件下频繁发生的告警关联规则的问题。本 北京邮电人学博士学位论文摘要 文结合实际电信网络告警的特征，提出了一种以高相关度、高置信度 为条件，基于相关度统计的告警关联规则挖掘算法a a r s c ；同时为 了适应告警数据动态增加的特点，提出了其改进算法一增量式挖掘 算法i7 a a r s c 。实验表明a a r s c 和u a a r s c 算法可以同时发现频 繁和非频繁发生告警序列间的关联规则，从而提高了告警关联规则的 完整性和准确性。 3 、告警模式的可视化 由于电信运营商经常会根据业务需求，对网络进行优化，为了有 利于网管人员对设备进行维护，可以将当前网络中存在的告警以可视 化的方式呈现给网管人员，他们根据可视化的结果，有效地发现故障 的告警模式，进而预测告警，定位故障。本文提出一种基于谱图理论 的a c a s g 算法。该算法基于谱图理论发现高维数据空间中潜在的低维 映射结构；通过分析低维空间中点结构之间的相似性，实现告警模式 挖掘的目的。实验结果表明，该算法不仅可以发现告警间的相关性， 而且还可以通过分析谱图的变化，预测、定位网络故障。 关键词：告警相关性序列模式挖掘数据挖掘增量式挖掘 统计相关谱图理论多维尺度分析 北京邮电大学博上学位论文摘要 s t u d yo fn e l 、 o r kf a u l ta l a r mc o r r e l 芦汀i o n b a s e do nd a t am i n i n g a b s t r a c t t h et a s ko ft e l e c o m m u n i c a t i o nn e t w o r k sm a n a g e m e n tf b c u s e so n m o n i t o r i n gt h es t a t u so fn e t w o r i 【w h i c he n s u r c st h en e t w o r kt om n r e a l i a b l e l va n de f f i c i e n v a st h em o d e mt c l e c o mn e t w o r kb e c o m e sl a r g e s c a l ea n di t sc o n s t n l c t i 伽g o e sc o m p l e x ，i ti sm u c hm o r ci m p o r t a n tt o a n a l v s i st h ea l r a mc o r 佗l a t i o n b c c a u s et h er e s u l tc 柚h e l pt h en e 咖r k a d m i n i s t r a t 0 硌k a t et h cf a u l tt 0 s u f et h cn e t 、】l ，o r km i l n i n gs m o o t h l y h o w e v e f ，t r a d i t i o n a la l 锄c o r r c l a t i o na n a l y s i sm e t h o d sc a nh a r d l yw o r l 【 w e uw h e nn e t w o r k sa 化c o m p l 甑锄dc h a n g e f i l ld u ct 0i t sf c l y i n g e x p e nk n o w l e d g c ，h ed a t am i n i n gm e t h o dc 柚o v e 瑚m et h es h o r t a g eo f t r a d i t i o n a lm e t h o d s w i t ht h ed e v e l o p m e n to fl e l e c o m m u n i c a t i o n n e t w o r k s i ti sk e yi s s u ef o fn e “】l ，o f km a n a g e m e n tt oe x t f a c tt h ea l a m c o e l a t i o nm l e sf r o mm a s s i v ca 王a 蛐d a t at oh e l pn e t w o r ka d m i n i s t r a t o r t oh a n d l et h ef h u l t i nt h i st h e s i s ，w ea p p l yd a t am i n i n gt e c h l o g yt 0n e t 、) l ，o r kf a u l t a l a mc o r r e l a t i o n 锄a 重y s i s 柚ds t l l d ym i n i n gm e t h o d si n 矗e q u e n t l ya n d n o n f r e q u e n t l va l a 咖s e q u e n c e t h e f e s e a r c h柚di n i l o v a t i o n sa r e d e s c r i b e di nd e t a i l sa sf b l l o w s ： 1 a 瑚s e q u e n c ep a t t e mi n i n i n go l i g t i - f r c q u e n c ya l a 咖s e q u e n c e ) w er e s e a r c ha l a 蚰s e q u e n p a t t e mm i n i n gi nt e l e c o mn e t w o r k 。 s e q u e n c cp a n e mi n i n i n gi sd c v e l o p e db a s e do n 鹬s o c i a t i o nm l e sm i n i n g n o w a d a y s ，m o s ts e q u e n c ep a t t e l mm i n i n gm e l h o d sa 化b a do nw i n e p i a l r i t h m 丘a m e b u tw i n e p ia l g o r i m mn e e d st ot r ；l v e 啪lt h cd a t a b 弱e f b rm a n vt i m e ss ot h a ti ti sn o tv e f ve f ! f i c i e n t l v i no r d e rt oo v e r m e 北京邮电大学博士学位论文 摘要 t h i s s h o n a g e ，w ep r o p 0 辩d as e q u e n c ep a t t e mm i n i n gf s p m - f p a l g o r i t h i n w h i c hi s b a s e do nf p - t r e e ，a n dt h w ep r o p o s e dt w o i n c r e 眦n t sm i n i n ga l g o r i t h mw h i c h 撇s f s p m 一即a l g o r i t h mb a do n t h cm i n i m a l 蛐p p o r tc h a n g e d 锄dd f s p m f pa l g o r i t h mb 弱e do nt h e d a i a b a c h a n 暑脚e x p e r i m e n t a lr 懿u l t sd e m o n s t m t ct h ev a l i d i t yo ft h e a i g o f i m m 2 1 0 w 。f r e q u e n c ca l a 皿a s s o c i a t i 伽m i e sm i n i n g q l f f e n t l yt h o s ea 培o r i t h m st om i n et h ea l a m 够s o d a t i o nm l e sa r c l i m i t e dt 0t h em i i l i i n a ls u p p o n ，t h a tt h e y no n l y0 b t a i nt h e 船s 0 _ c i a t i o nm l e sa m o n gt h ef k q u e n t l yo c c u r r i n ga l a me v e n t sb a s e d 伽 l l i g l ls u p p o na n dh i g h n f d e n c e i nt h et h e s i st h ca l a ma s s o c i a t i o nn l l e s m i n i n ga l g o r i t h m 丸r s ci sp 他s c n t e d ，w r h i c hi su 辩dh i g hc 0 仃e l a t i v i t y 柚dt h eh i g hc o n f i d e n c e a tt h es a m et i m e ，w ep r o p o s e di t si m p r o v e d a i g o r i t h mu a a r s c t oa d 叩tt h ed a t a b a s ei n c r e a s i n g e x p e r i m e n t a lr e s u l t s b o w sa a r s ca l g o r i t h m 柚du a a r s ca l g o r i t h mc a nd i s c o v e r yb o t h h i g h f r e q u e n c ya n dl o w - f r c q u e n c ya l a ma s s o d a t i o nm l ss ot h a ti t c a n m a k et h em l e sa r em u c hm o r cc o m p l e t l ya n d n c c n y 3 、a l a 姗p a t t e mv i s u a l i z a t i 伽 ，i b l e c o mn e t w o r ko f k nc h a n 星r c sa st h es e r v i c ec h a n g c s a l a 蛐 v 姗a l i z a t i o n 啪h c l pa d m i i l i s t r a t 0 俗m a i n t a i l l t w o r kd e v i c e s ，s ot h a t t h e yc 姐d i s c 0 v e r yt h ea l a 姗p a me f ! f i c i e n t l ya n dl d h c a t e 柚dp r e d i c tt h e a l a 姗勰df a u l t an e wa c a s ga l g o r i t h mi si l l t r o d i l c c d ，w h i c hi sb 弱e d s p e c 仃a lg r a p ht h e o r y t h ca 1 9 0 r i t h i 璐d i s c o v e r t h e u n d e d y i n g 啪p p i n gs t m c t i l r el y i n g o nal o w d i m e 船i o n a ls 佃j 咖r eb 蹴do ns p e c 仃a l 舯p ht i l r y 觚dm i n ea l a mp a t t e mb y 柚a l y z i n gp o i i l tc o n s t m c t i o n s i n l i l a r i t y e x p e f i m e n t a lr c s u l t sd e m o n s t f a t et h a tt b ea l g o f i t h mn o to n l y d i s c o v e r e dc o r r c l a t i a m o n ga l a 加晦b u ta l a c q u i r et h ef a u l ti i it h e t c l e c o m 皿毗n i c a t i o n sm ；t 、| i ，0 i _ kb a s c do nt h es p e c t r a l 鲫ht m s f 0 加a t i 仰 k e yw o r d s ：舢a 珊c 0 仃e l a t i o n s c q u e n p a i t e mm i l l 吨 d a t ai i l i n i n g i n c m e n t a im i n 吨 r e l a c e ds t a t i s t 豳 s p e c t r o g m mt h c o f y m u l t i d i m e 璐i o n a ls c a l i n g 创新性声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：丝i 翕垄日期：缓乏塑 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。 本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名： r 期：2 丝z 垂兰主 日期：与u _ 卜 北京邮电大学博士学位论文第一章绪论 第一章绪论 1 1 网络故障告警相关性研究的意义 随着信息技术的飞速发展，人们对电信网络系统的依赖程度越来越高。每天 都有数以千万的用户通过网络获取各种各样的服务，这就要求支持这些服务和应 用的电信网络系统具有高可靠性和高可用性，以确保业务永不间断的运行。与此 同时，随着各种新业务的涌现，电信网络也正在发生着变化，传统上以话音业务 为主、以电路交换为基础的电信网络，正逐步向以数据业务为主，以分组交换为 基础的新电信网络框架过渡，出现了电信网络、数据网络和广播网络三网融合的 情况。面对规模巨大、结构复杂、多种技术并存的电信网络，为了保障其高效、 经济、可靠、安全地运行，更大限度地利用网络资源，降低运营成本，向用户提 供高质量、高可靠性的服务，国内外电信运营商相继建立了各种网络管理系统。 随着网络管理系统建设的逐步深入和网管系统日益发挥的重大作用，网络的运行 维护工作对网络管理系统的依赖性也与日俱增 故障管理是网络管理系统的重要组成部分，主要是用于进行告警分析和故障 诊断。当网络中的设备发生故障时，快速发现、排除故障是保证网络安全、可靠 运行的关键，也是网络管理的首要任务。在实际网络中，当故障发生后很难确定 真正出现故障的位置。因为在复杂、异构的网络结构中，各个网元设备之间相互 影响，如果一个网元发生故障，与其相关的一些网元也会发出告警，同时显示其 处于故障状态。当电信网络中出现故障或性能出现瓶颈时，网管人员经常被一系 列突发的、对确定故障原因无意义的大量告警事件所淹没。因此，为了更好的诊 断故障，需要对故障告警信息进行分析，也就是需要对网络故障告警信息进行相 关性分析，压缩冗余告警、定位故障。 通过网络故障告警相关性分析，可以将多个告警事件归结成较少的告警事 件，过滤掉无意义的告警事件，辅助网络管理人员删除衍生的冗余告警，从海量 告警数据中找出故障的根原因，准确定位故障。帮助网管人员采用合理的解决方 案，及时排除故障，确保网络正常、可靠的运行。因此，采用告警关联分析方法 挖掘电信网络中海量告警数据是电信网络管理的重要内容。 北京邮电大学博士学位论文第一章绪论 1 2 网络故障告警研究现状 网络故障告警相关性分析作为网络管理系统中重要的关键技术，其目的是通 过对告警信息进行挖掘，获取隐含在大量告警中的根源故障。 网络故障告警相关性分析的思路为：依赖某种算法模型，主动地获取新告警 信息，根据已建立的告警知识库快速准确地对新告警进行分析推理，获取根源故 障，从而确定最大可能的网络设备或网络功能服务故障，完成故障定位。在相关 性处理中主要涉及到推理算法和告警知识库的建立；如何保证在极短的时间内， 获得高准确度的故障信息也是告警相关性算法的主要研究内型。 目前告警相关性分析研究的算法主要有以下几种： 1 2 1 基于规则的告警分析 基于规则( r u l e b a s c d ) 的分析方法【2 l 是将特定领域知识( 如告警相关性知 识) 包含在一组规则集中，通过推理机制对各种问题进行分析判断。规则的形式 为：mc o n d i t i 衄t h e na c t i o n 该方法通常由三部分组成：工作存储区、相关性 规则库、推理引擎，其中核心部分是推理引擎。 其工作原理是：利用规则分析系统，对网络中实时产生的告警与规则库中的 规则进行比较，从而实现对故障原因的判断。它在工作存储区存放关于被管网络 的拓扑结构信息以及一些实时的告警信息，从而形成对被管网络的实时监控；在 相关性规则区存放已知的告警规则；在推理引擎部分，实现对告警信息的相关性 分析 基于规则的算法优点是符合人们的思维，直观，便于理解。主要的应用系统 有：( 1 ) h p 公司开发的告警相关性分析系统e i 筠【3 】( e v e mc 唧e h t i s c r v i ) ， 主要应用在高速传输网络如s d h ，a 1 m 网络中。( 2 ) p 蛐i 舻公司研制出s d h 网络管理系统中智能过滤器h t e l l i 萨n tf 丑钯】r i n g l 4 】。( 3 ) s i n 喇a 系统【5 1 ，用于定 位传输网络数字电路故障，应用于意大利电信网故障诊断中。 但该方法的缺点在于：( 1 ) 当规则数量达到一定程度时，规则库的维护变 得越来越困难；( 2 ) 由于规则主要来自于专业的网管人员，系统没有自身的学 习能力，所以规则的获取是该方法主要瓶颈；( 3 ) 由于规则中隐含了系统结构、 设备功能描述，当网络拓扑结构或配置信息发生变化时，规则的调整和维护非常 2 北京邮电大学博上学位论文第一章绪论 困难，难以适应经常变化的网络；( 4 ) 该方法缺乏记忆，无法充分利用过去的 经验知识，即使发生同样的故障，系统也需要从成千上万的规则中查找，影响了 系统的效率。 1 2 2 基于事例推理的告警分析 基于事例推理( q 雠b 姻目r 鲫洳g ) i q 分析方法将过去发生的问题及其解 决方案构成范例( q 睇) 。过去解决问题的经验都是以事例的形式存放在事例库 中，遇到新的问题就从事例库中寻找相同或相似的事例，用该事例的解决方法来 解决新的问题，而解决新问题的经验又作为新的事例被添加到数据库中 其工作原理是四个过程的循环系统，如图1 1 所示。 建议解决方案 图卜1 基于案例推理的系统结构 当遇到一个新问题，首先在告警事例库中查找相似的事例；然后将该事例的 解决方案应用到新问题中；通过测试来修改建议的解决方法；最后保存有可能被 未来使用的经验。在该方法中，知识的单位不再是规则，而是事例。事例库的维 护主要按照遗忘曲线理论，即长期不用的信息将会被遗忘，所以需要删除长期不 用的事例。 基于事例推理方法的优点是它具有自学习能力川，而不必通过专业人员获取 知识；另外它可以根据出现的错误来自动改正将来的行为，可以通过调整过去的 事例，来构建新的方法，用于处理新的故障。主要的应用系统有：( 1 ) c a s c a d e 8 l 用来分析操作系统的崩溃原因并提出相应解决方案的建议。( 2 ) k 啊i s 设计实 3 北京邮电大学博士学位论文第一章绪论 现了基于事例推理的故障追踪系统c r f r 淑【9 一，用于网络故障管理。( 3 ) b u m s 等提出了一种基于事例推理的算法1 1 1 i ，应用于g s m 网络故障检测中。 该方法的缺点：拘泥于某个特定的应用领域，缺乏通用的事例方法；对于网 络变化不敏感，分析处理过程复杂、费时，难以适应实时性要求高的告警分析处 理问题。 1 2 3 基于模型推理的告警分析 基于模型的推理m b r ( m o d c b a s c dr c 蜘n i l i g ) 【1 2 1 分析方法是一种基于知识 的推理模型，依赖于系统结构和功能模型进行推理，分析诊断故障、预测网络行 为 在电信网络中，系统结构模型描述网络的拓扑关系，功能模型描述告警的传 播特性和告警的相关性【埘。模型诊断的目标是识别故障设备，因此，在建立模 型时需要精确考虑设备中所有模块及其状态，各模块间的相互关系，实现识别故 障、定位故障的目的。 基于模型推理分析方法的优点是可以比较准确的定位故障、效率较高。目前 主要的应用系统有：( 1 ) g t e 实验室开发的i m p a c 一1 4 j ( i n t e l l i g c n tm a n a g c m e m p l a 响岫s6 。fa l 锄c ，e h t i 伽1 弧b ) 系统，主要用于固网和移动通信网络的告 警相关性分析。 ( 2 ) f r o h l i c h 等1 1 5 】设计了一个针对g s m 网络的故障诊断系统。 该方法的缺点是需要建立精确的模型。模型的建立需要熟悉网络中所有设备 及其网络拓扑关系，而电信网络是一个多厂商、多设备的异构环境，建立这种复 杂的设备模型和故障传播模型是非常困难的，因此限制了该方法的实用性。 1 2 4 基于编码的告警分析 基于编码的相关性( c c ，d c b o o ka p p 瑚c h ) 1 1 6 1 分析方法是将观察到的告警事 件看作产生故障原因的一个编码；而告警分析是通过对观测到的告警事件集进行 解码，来确定故障原因。 对于每一种故障所触发的告警，可以将其看作该故障的特征，并将其编码成 该故障的特征向量。特征向量的每一维元素对应于该故障下某类告警( 或症状) 是否出现，用o 或1 表示。所有故障的特征向量一起构成了代码本，其实就是一 个关于故障的症状矩阵。建立代码本后，相关性分析本质上就是一个解码的过程， 4 北京邮电大学博士学位论文第一章绪论 对于当前的故障，系统也建立其特征向量，然后与代码本上的各个特征向量进行 比较，计算当前特征向量与已知故障的特征向量之间的汉明距离，选择距离最小 的特征向量对应的故障作为当前的故障。 基于编码相关性分析方法的优点是通过对事件知识模型的预处理，减少了实 时告警相关性分析的复杂度，提高了系统的效率。故障的确定是基于最小距离， 这在一定程度上提高了对告警信息丢失和被破坏的容忍程度，增强了系统的鲁棒 性。s m a n s 公司开发的h a l a r g c 系统，用于通信和数据网络中自动故障诊断系 统，具有处理噪音，丢失、虚假、不完全告警的能力 但该方法的问题是对网络对象模型的构建要求很高，尤其针对大型、复杂的 电信网络难以建立准确的模型。 1 2 - 5 基于贝叶斯网络的告警分析 贝叶斯网络( b a y sn c 啊o r l 噶) 【1 7 l 是处理不确定性问题的有效方法，贝叶斯网 络是一个有向无环图，每个节点代表一个随机变量，通过前序节点代表变量值的 所有可能组合。可以计算出该节点上的相关条件概率。通过该方法可以清晰的描 述变量间的相互影响程度。 告警模式也是一种不确定情况。在通信网络中发生的告警，可能会由于某种 原因发生丢失，如由于被管网元自身的原因、网络传输延迟、传输故障、网络系 统自身原因等造成收集到的相关告警是不确定的；除此之外某些激发相关性告警 的故障原因也是不确定的，在多个故障同时发生时产生的告警模式也是一种不确 定情况。 贝叶斯网络分析方法的优点是可以有效处理不完整和带有噪声的数据。在分 析通信网络中的告警相关性时，可以有效克服告警事件的不确定性。文【1 8 】采用 贝叶斯网络对光纤网络进行故障分析。 该方法的主要缺点：边界概率的计算效率是一个需要解决的难题；另外与编 码的相关性分析方法类似，对网络中的对象进行建模，从实际环境中获取先验知 识比较困难，这些限制了其有效应用 1 2 基于模糊逻辑的告警分析 由于电信网络结构复杂，几乎无法建立精确的网络模型，所以可以采用基于 5 北京邮电大学博士学位论文第一章绪论 模糊逻辑( f i 比yl o g i c ) 【1 9 】分析方法来解决一些问题。模糊逻辑的基本概念是 模糊集，模糊集中任何一个元素都归属于某个集合，在【o 1 】区间内的一个值，即 为t i 哪或蹦两者之一。 在电信网络中，被管网络非常复杂；配置信息经常处于不断变化之中；故障 和告警之间的关系通常是不确定的，同一种故障在不同情况下可能会触发不同的 告警，因此根据一些告警事件很难精确判断故障原因。另外，从专家那里所获得 的知识通常也是模糊、不确定的。所以可以利用模糊逻辑的分析方法来描述网络 模型，挖掘告警间关联规则。 虽然文【1 9 】中采用该方法分析告警相关性规则，但在实际中通常与其他方法 相结合使用。 1 2 7 基于神经网络的告警分析 神经网络( a i c u r a ln e 岍o r l 【s ) 幽l 是由很多相互连接的神经元构成，这些元素 之间存在着简单的输入、输出关系。该方法可以实现并行计算，避免了串行计算 带来的瓶颈问题。利用该方法可以有效的处理不完全和不明确的告警数据。 神经网络分析方法是基于对过去系统的观察和系统的当前状态来预测系统 的行为。在告警分析中，将网络中的故障作为神经网络的输出，与故障相关的告 警信息作为输入，网络通过多层前馈神经网络和反向传播的方法调整权值。这样 神经网络可以根据当前的告警信息判断出可能出现的故障。 神经网络分析方法的优点是具有良好的自学习能力，而且在输入数据包含噪 音时，也能够较好地识别出相关性模式。w i e t g r e f c 【2 l l 等利用神经网络方法对g s m 网络中的告警相关性问题进行了研究。苏利敏阎等利用神经网络分析告警相关 性问题，主要对告警的不确定性和抑止噪声方面进行了研究。王新苗等瞄】提出 了一种改进的自适应遗传算法训练多层前向神经网络，用于网络中故障识别和告 警相关性分析。m a r i u y 等l 刎通过神经网络把告警信息转换为信号形式，采用信 息处理方法提取相关故障信息。 该方法的缺点是在应用之前要经过大量的训练，而电信网络是复杂多变的， 无法从电信网络中找到较好的训练数据集合，这给实际电信网络管理带来了一定 的困难。 6 北京邮电大学博士学位论文第一章绪论 1 2 - 8 基于数据挖掘的告警分析 上述传统方法对告警相关性分析主要通过人工分析出相关性规则，然后再加 入到系统当中。这对于网络规模较小的情况下，还可以满足需要。但当网络规模 越来越大时，仅仅通过专家获得告警相关性知识，已经无法满足网络维护的需要。 因此，很多研究人员专注于通过数据挖掘的方法来分析告警事件序列，挖掘告警 相关性规则。 数据挖掘( d a l am i n i n g ) 是从大量的、不完整的、有噪音的、模糊的、随机 的数据集中识别有效的、新颖的、潜在有用的，以及最终可以理解的模式挖掘过 程。它是基于对过去事例泛化的一种归纳学习，可以解决分类、聚类、时间序列 分析、关联规则挖掘等问题。 数据挖掘基于电信网络中的历史告警数据，发现告警问相关性规则，再根据 发现的规则来分析和预测网络设备可能出现的故障。通过数据挖掘方法进行网络 故障告警关联分析的框架如图1 2 所示。 图卜2 基于数据挖掘的故障告警告警关联通用模型 数据挖掘方法的优点：( 1 ) 相关性分析所需的知识可以通过数据挖掘来获 得，减少了对网管专家的依赖；( 2 ) 无需知道网络拓扑结构。尤其是当网络拓 扑结构发生改变时，可以通过分析历史记录，自动发现新的告警关联规则，适应 电信网络变化快的需求，减轻了网管人员的工作负担，提高了工作效率。 基于数据挖掘方法获取告警相关性知识是当前网络管理中的一个研究热点， 国内外很多学者提出了各种基于数据挖掘的方法，提高了相关性分析的效率和准 确性。h c i l 【l 【im 蛐l i i l a 等研究如何从大量历史告警数据中挖掘频繁出现的关联规 则，提出了w 附e p i 算法【御，并将其应用于t a s a 闭系统中。g a r v m w e i 豁掣2 7 l 研究如何从通信告警数据库中发现、预测小概率时间序列模式，提出了t i m e w c a v c 7 北京邮电大学博士学位论文 第一章绪论 算法，并将其应用到a n s w e r 故障预测系统闭中。g a f d n c r 【2 9 】等通过数据挖掘 方法分析模拟s d h 网络的告警数据，提出基于数据挖掘的告警相关系统框架。 郑庆国印l 基于w 眦p i 算法框架，针对告警数据中的噪声问题提出了改进算法， 并应用于g s m 网络告警数据的分析中；姚伟力p 1 j 针对告警时阃跨度约束，提出 了告警时序模型，该算法可以删除大量无意义的告警模式。单莘p 2 】提出了一种 基于支持向量机的算法，对网络中发生的重大告警进行了研究。 1 3 网络故障告警研究存在的问题 目前，网络故障告警相关性分析由早期主要针对物理设备和物理链路故障分 析，逐步向更加智能化的方向发展。 上述基于规则、事例推理、模型推理、编码、贝叶斯网络、模糊逻辑和神经 网络算法在进行网络故障告警分析时，普遍存在只能适应某种拓扑结构的网络系 统，或者只适应某一种、某一类网络设备和系统服务的问题。而基于数据挖掘的 算法虽然能部分解决上述问题，但仍有一些新的问题需要研究，如： 1 、序列模式挖掘 目前告警序列模式挖掘都是基于内埘嘶算法的思想，由长度为k 的频繁序 列模式，构造长度为“1 的频繁候选序列模式。但该类算法需要多次遍历数据库 和产生大量候选项集，因此存在效率较低的问题。 2 、增量式挖掘 目前网络故障告警的研究主要考虑在对告警数据一次挖掘的情况下如何提 高挖掘效率，但事实上，在网络运行中，由于各种原因( 新业务，网络拓扑改变 等) 会有新的告警数据产生，如何利用以往的挖掘结果对新告警数据进行挖掘； 或者在改变挖掘参数时，为了提高算法的效率，利用当前的挖掘结果，进行增量 式挖掘，也是实际网络管理中需要关注的问题。 3 、非频繁告警关联规则的挖掘 目前网络故障告警的研究都是针对频繁告警序列挖掘，由于受到最小支持度 限制，无法挖掘出网络中存在的大量非频繁告警序列。而这部分告警间可能存在 8 北京邮电大学博士学位论文 第一章绪论 大量有意义的关联关系，对其进行挖掘具有重要的意义，挖掘非频繁告警间关联 规则也是一个新的挑战。 4 、故障告警模式的挖掘 目前网络故障告警的研究都是针对单独告警进行挖掘，得出与其相关的关联 规则。但从实际应用的角度来看，网管人员更希望看到当前运行的网络中存在的 故障，以及新增加的故障告警模式，从而及时定位、排除故障，这也是一个需要 研究的新问题。 1 4 论文主要研究内容 随着电信网络规模越来越大，网络结构日益复杂，采用数据挖掘方法进行相 关性分析可以减轻网管人员的工作负担，提高工作效率，帮助维护人员及时发现 网络故障，准确定位故障，提高电信网络的服务质量。因此本文采用数据挖掘方 法研究故障管理中告警关联的热点和难点问题。 本文主要从三个方面针对网络故障告警相关性分析进行了研究，即针对告警 序列模式( 频繁告警序列) 挖掘和非频繁告警关联规则挖掘，以及通过可视化的 方式发现告警问的关联关系。论文的主要贡献包括： l 、告警序列模式的挖掘 目前序列模式( 频繁告警序列) 挖掘方法大多基于a p f i o r i 的算法框架，由 于该算法存在产生大量候选项集以及需要多次遍历数据库的问题，执行效率比 f p - 孕o w t h 算法低，因此本文基于f p - 印w t l i 算法框架，提出一种序列模式挖掘 f s p m f p 算法，该算法将告警信息压缩存储到频繁模式树中，然后针对该树进 行挖掘。 另外针对挖掘序列模式过程中需要不断调整最小支持度；以及在告警数据库 变化的情况下，为了提高算法的效率，避免重复挖掘造成的大量系统开销，充分 利用已有的挖掘结果，提出了相应的增量式挖掘s f s p m f p 算法和d f s p m f p 算法。 2 、非频繁告警关联规则挖掘 9 北京邮电大学博士学位论文第一章绪论 目前告警序列模式挖掘算法受到最小支持度的限制，仅能够得到一些频繁发 生告警序列问的关联规则。在分析电信网络实际数据时，发现网络中存在大量非 频繁告警，因此为了提高网络中告警关联规则的完整性和准确性，提出了一种以 高相关度、高置信度为框架，基于相关度统计的告警关联规则挖掘a a r s c 算法。 由于告警数据具有动态增加的特点，为了提高算法效率，提出了一种增量式 挖掘u a a r s c 算法。 3 、故障告警模式的可视化 针对电信网络中告警数据增加和配置数据的变化时，导致部分关联规则失效 的问题，提出了一种基于谱图理论的告警模式挖掘a c a s g 算法。该算法采用可 视化的手段，通过分析谱图的变化，动态的显示当前网络中存在的告警模式以及 故障信息。 1 5 论文结构安排 论文各章节的组织安排如下： 第二章给出全文的相关技术研究背景，对告警关联挖掘技术的相关背景研究 进行了较为详细的分类、比较和分析，主要介绍了告警相关性的分类以及分析难 点：然后介绍了当前两种基于数据挖掘的关联规则方法一a 两o r i 和f p 掣咖h 算法；最后阐述了基于谱图理论挖掘的基本概念和理论 第三章讨论了电信网络中告警的特性。首先简述了电信网络的基本结构；然 后对故障、告警的概念和特点进行了分析；最后讨论了告警分析处理的流程，重 点讨论了告警的预处理过程。 第四章集中讨论了序列模式挖掘问题。首先介绍了序列模式挖掘的基本概 念，然后在分析f p 翻) w 恤算法框架的基础上，提出了一种基于f p 树的序列模 式挖掘f s p m f p 算法。最后分别针对最小支持度和数据库改变的情况，提出了 两种增量式挖掘算法_ s f s p m f p 和d f s p m f p 。 第五章集中讨论了电信网络中大量非频繁告警的挖掘问题。首先分析了当前 非频繁告警关联规则挖掘的现状：然后提出一种基于相关度和置信度框架下的告 警关联规则挖掘a a r s c 算法；最后提出当告警数据增加时的一种增量式挖掘 1 0 北京邮电大学博：l 学位论文第一章绪论 1 i a a r s c 算法 第六章通过可视化方法研究告警模式的挖掘问题。首先介绍了基于全局的谱 图理论基本算法；然后提出一种基于谱图理论的a c a s g 算法，实现告警数据的 可视化显示。 最后是结束语，对全文进行了总结，指出了目前研究中还存在的一些问题和 不足，并给出了今后进一步研究的方向。 ! ! 壅坚皇盔兰竖r 圭兰竺堡苎 箜= 皇堕堡 本章参考文献 1 1 】陈清金告警管理系统的关键技术研究【博士论文】北京邮电大学2 0 0 4 犯】r q o n k ，p ( l a h a n 孤dlb e m 吼e i n r u l c - b a s c de 】【p c ns y s t 锄s 蠡d fn c 呐o r k m 蝴g c m e n t 姐d0 p c m t i o 岫：柚l n 删u c t i 阴砸e en c t 啪咄1 9 8 8 ，2 ( 5 ) ： 7 2 1 【3 】h a f r i n ，k a ，矾c lh 哪i c n p 利国r d ( b f i s l o i ) l a b s e v 龃tc o 眦h t i o ni n t c l e m m u n i c a t i n e t w o f km 卸a g 啪c n t 1 9 9 4 9 1 4 】m ，m o c r ，s 1 c n 盯，彻db f j l l j 【b t c j l j g 如lf 豇t c 嘲gj nn e t w o f km 锄g c m c n t s y s t 啪s 【q h il f 】栅eh i t c m a t i o n a is y m p o s i 哪蛐h n c 孕a t c dn e t w o r k m 锄g c m e n t ，( i s m 9 5 ) ，l o n d 咖：c l l a p m a n 柚dh a l l ，1 9 9 5 ：3 0 4 3 1 5 【5 】s i l l i 蚰ab m 鲫o i l i ，g u i d ob m ，r o b e n 0m a n i 伽c e n 一m o n t a r i o l o ，e l i o p a s c h e t t a 柚dl u i n as i s t o a ne x p c r ts y s t c mf b rr e a lt i m cf a u l td i a 驴o s i so f t h cn a l i 锄t e l e c o m m u n i c a t i s n c t 、 ，o r k 【c 】h 睨p i e e eh t e m a t i o n a l s y m p o s i u m 伽i n t c g r a t c dn c t w o r km a n a g c m e 嵋i ( i s m m 9 3 ) ，s a l lf r 锄c i s o ， c i l i f o r n i a u s 八1 9 9 3 ：6 1 7 6 2 8 【6 】l l o d 肿f ，j ( k e - b 舔cr e 瑚n i n 辱s 蹰m 砷鸭c 气m o r g a nk a u 细她，1 9 9 7 【刁s s l a d e c 黜b a s e dr 咖i g ：ar 嘲珊hp a r a d i 肿【j j a lm a g a z i ，v o i 1 2 ，1 ，1 9 9 1 ：4 2 5 5 1 8 】e s i n l d i s u s i n g 溉c dr c h j e v a l 衙c u s 幻m 甜t 如n i 龆ls u p p o n 川 m e e 叫，0 州b 盯1 9 9 1 2 ，7 ：7 - 1 2 【9 jh 嘶s lac a - l i a s e dr l 组n i n ga p p a c ht ot h cm 柚a g c m c mo ff 眦l t sj n m 邶j c 砒i o nn e t i 舳f bi q p m e d i 雌髓e h 蠡d m 9 3 ，v 0 1 3 s 姐 f i 砸吣i s 1 9 9 3 ：1 1 4 1 2 0 【1 0 】l c 响， l b p l 锄c n t i n gp o l i c y i n e n t e l p i i 辩咖妇 们嘲 ( b 呦u n i t i sm a g a z i n e j 锄u a r y1 9 9 6 1 1 1 】b u 璐l ，蹦l e 巧t c i 丑 j i ，m a s ，p 眦舀c s ，l t a l 蝴d a ，t a y l o r d j t o 啪r d sd i s v c r yo fe v c n tc o m l a t i 傩r u l 嚣【q h 删嗍晌巳e h t c m a