（计算机应用技术专业论文）序列模式挖掘在网络告警中的应用研究.pdf

摘要 摘要 随着网络规模不断扩大，网络结构日益复杂，如何保证网络高效、稳定运行， 已经成为网络管理的重要问题。正确的网络告警相关性分析可以提高网络管理效 率，辅助网络管理人员过滤无关告警，删除冗余告警，定位和预测网络故障。 本文将序列模式挖掘方法应用到网络告警分析中，研究基于频繁模式增长的 告警序列模式挖掘，以及网络情景规则更新挖掘等重要问题，本文研究重点及其 研究成果主要体现在以下几方面： 1 、数据预处理对数据后续挖掘效率以及挖掘结果影响很大，本文针对告警 数据特点，研究并设计告警数据预处理模型，能够将冗余、含噪音的原始告警数 据转化为适合序列模式挖掘的告警序列数据库。 2 、深入分析基于频繁模式增长的告警挖掘算法一f s p m f p ，针对其存在的 告警序列偏序关系难确定的问题，提出一种改进的模式树构造方法，同时修改告 警挖掘过程，降低了树的存储空问。 3 、针对目前告警序列选择条件单一( 支持度和置信度) 情况，提出一种带 拓扑关系判断的网络情景规则挖掘算法m n e r t p ，算法引入告警序列拓扑关 系判断，可过滤掉频繁但相关性小的告警序列，只保留频繁又相关性大的告警序 列，提高了挖掘结果精度。 4 、在分析基于频繁模式更新挖掘算法基础上，研究基于顺序模式的告警更 新挖掘算法，对所有告警采用统一排序，能够减少模式树更新过程中频繁的节点 交换操作，以此提高更新效率；最后分别给出了支持数和数据变化两种情况的更 新挖掘方法。 关键词：告警相关性；频繁序列模式；顺序模式树；更新挖掘 a b a t r a c t a b s t r a c t a st h en e t w o r kb e c o m e sl a r g es c a l ea n di t sc o n s t r u c t i o ng o e sc o m p l e x ，i th a s b e c o m ea ni m p o r t a n tp r o b l e mh o wt oe n s u r et h en e t w o r kr u nw i t hh i g h e f f e c ta n d s t a b il i z a t i o n a l a r mc o r r e l a t i o na n a ly s i si sk e yi s s u ef o rn e t w o r km a n a g e m e n t ，w h i c h c a na s s i s tn e t w o r ka d m i n i s t r a t o r sf i l t e ru s e l e s sa l a r m ，d e l e t e r e d u n d a n c ya l a r m ， o r i e n t a t ea n df o r e c a s tn e t w o r kf a u l t ，i m p r o v e st h ee f f i c i e n c yo fn e t w o r k m a n a g e m e n t i nt h i st h e s i s ，w ea p p l ys e q u e n c ep a t t e r nm i n i n gt e c h n o l o g yt on e t w o r ka l a r m c o r r e l a t i o na n a l y s i sa n ds t u d ya l a r ms e q u e n c ep a t t e r nm i n i n gb a s e do nf r e q u e n t p a t t e r ng r o w t ha n dn e t w o r ke p i s o d er u l e su p d a t ee t ci m p o r t a n ti s s u e s t h er e s e a r c h a n di n n o v a t i o na r ed e s c r i b e di nd e t a i l sa sf o l l o w s ： 1 、d a t ap r e t r e a t m e n th a sd e e pi n f l u e n c eo nm i n i n ge f f i c i e n c ya n dr e s u l t a m i n g a tt h ec h a r a c t e ro fa l a r md a t a ，w eb r i n gf o r w a r dad a t ap r e t r e a t m e n tm o d e lf o r t r a n s l a t i n gt h er e d u n d a n c ya n dn o i s eo r i g i n a la l a r md a t ai n t oa l a r ms e q u e n c ed a t a b a s e t h a ti ss u i t a b l ef o rs e q u e n c ep a t t e r nm i n i n g 2 、a n a l y s ea l a r mm i n i n ga l g o r i t h m f s p m f pd e e p l yw h i c hb a s e do nf r e q u e n t p a t t e r ng r o w t h ，o w i n gt ot h ep r o b l e mo fa l a r ms e q u e n c ep a r t i a lo r d e rd o u b t f u l l y , a n m o d i f i c a t i o nm e t h o df o rp a t t e r nt r e ec o n s t r u c t i o ni sp r e s e n t e d a tt h es a m et i m e ，w e a l s om a k es o m em o d i f i c a t i o n si nm i n i n gp r o c e s s ，i tc a nn o to n l yr e s o l v et h i sp r o b l e m ， m o r e o v e rm e m o r ys p a c eo ft r e ei sb e e nr e d u c e d 3 、t od e a lw i t ht h ep r o b l e mt h a tt h es i n g l es u p p o r t - c o n f i d e n c ec o n d i t i o nt os e l e c t f r e q u e n ta l a r ms e q u e n c em o d e s ，b r i n gf o r w a r dan e wm i n i n ga l g o r i t h m - m n e r t p w h i c hb a s e do nn e t w o r kt o p o l o g yr e l a t i o n s h i p d u et ot h ea l g o r i t h mi n t r o d u c et h e j u d g e m e n to fa l a r ms e q u e n c et o p o l o g yr e l a t i o n s h i p ，s oi tc a nf i l t eh i g hf r e q u e n c eb u t l e s sr e l a t i v i t y , a n dr e s e r v eh i g hf r e q u e n c ea n dm u c hm o r er e l a t i v i t ya l a r ms e q u e n c e s ， i m p r o v et h ep r e c i s eo fm i n i n gr e s u l t 4 、r e s e a r c ht h eu p d a t af r e q u e n ts e q u e n c ep a t t e r nm i n i n ga l g o r i t h m ，t h e nw e b r i n gf o r w a r da l la l a r mu p d a t em i n i n ga l g o r i t h mb a s e do no r d e rp a t t e r nt r e e i ta d o p t a nu n i f i c a t i o no r d e rf o ra l lt h ea l a r m ss oa st oi m p r o v et h ee f f i c i e n c yo fu p d a t i n g ， w h i c hc a na v o i de x c h a n g i n gn o d e sc o n t i n u a l l yi nm i n i n gp r o c e s s t h ea l g o r i t h mi s a b l et od e a lw i t hs u p p o r tc o u n tc h a n g ea n da l a r md a t ar e n o v a t et w ok i n d sc o n d i t i o n k e yw o r d ：a l a r mc o r r e l a t i o n ；f r e q u e n ts e q u e n c ep a t t e r n ；o r d e rp a t t e r nt r e e ；u p d a t i n g m i n i n g i i 学何论文独创性卢明 学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得直昌太堂或其他教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名( 手写) ：诈评签字日期：妒分牵i 明矽日 1 学位论文版权使用授权书 本学位论文作者完全了解直昌太堂有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权直昌太堂可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编本学位论文。同时授权中国科学技术信息研究 所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：弘薛导师签名：白乙一伤 签字日期： 游l 瑚习日签字日期：加咿湃，月r 日 | 第一章引言 1 1 研究背景和意义 第一章引言 随着网络技术r 益提升，现代网络正朝高速化、开放化、综合化的特点发展。 首先，网络传输的速率越来越快，容量也越来越大；其次，网络中多种技术走向 融合，多种业务并存；再次，不同厂商的设备和传输介质源源不断地涌入，不同 体系结构的网络互联在一起，这些特点使得对整个网络的管理和维护变的相当复 杂，同时也决定故障管理是网络管理的一个十分重要的方面。 故障管理是网络管理系统的重要组成部分，主要是用于进行告警分析和故障 诊断。当网络中的设备发生故障时，快速发现、排除故障是保证网络安全、可靠 运行的关键，也是网络管理的首要任务。在复杂、异构的网络结构中，各个网元 设备之间相互影响，如果一个网元发生故障，与其相关的一系列网元也会发出相 关告警，同时显示其故障状态。当网络中出现故障或性能出现瓶颈时，网络管理 员经常会被一系列突发的、大量的无关告警事件所淹没。因此，为了更好地诊断 故障，需要对网络故障告警信息进行相关性分析，挖掘告警情景规则，从而帮助 网络管理员准确定位故障。 本文针对网络故障管理的需求，将数据挖掘应用于网络告警相关性分析，由 于网络中故障数据库是具有时间特征的线性序列，各个相互关联的告警事件之间 有一定的时序关系，所以本文采用序列模式挖掘方法对告警数据进行关联分析，j 挖掘出对网络管理员有用的情景规则集，提高网络管理的效率。 1 2 网络告警研究现状 告警相关性分析是指对告警进行合并和转化，将多个告警合并成一条具有更 多信息量的告警，从而确定反映故障的根源告警、定位故障或者对当前告警可能 预示的故障做出预测。目f ； 网络告警相关性分析可以分为以下几种： 1 基于规则的相关性分析 基于规则( r u l e b a s e d ) 的分析方法【l j 是将特定领域相关知识( 如告警相关性知 识) 存放于一组规则集合中，然后利用这些知识通过推理机制对各种问题进行判 断分析。系统一般由工作存储区、相关性规则库、推理引擎三部分组成。工作存 储区存放关于被管网络的实时的状念信息和拓扑结构信息，从而形成对被管网络 的实时监控；相关性规则库存放已知的告警相关性规则；推理引擎是系统的核心 部分，它担任完成对输入的告警信息进行相关性分析的功能。 第一章引言 基于规则的方法的优点是直观，便于人们理解。存在的问题是当规则数目达 到一定程度时，规则库的维护将变得十分困难；由于相关1 j 牛规则主要由专业的网 络管理员完成，系统本身没有自学习的能力，所以规则的获取是基于规则的相关 性分析系统的主要瓶颈，而且基于规则的系统无法处理一些由于网络拓扑或配置 变化而出现的新情况；此外，由于没有充分利用过去的经验以及缺乏记忆，即使 出现同样的情况，系统也要从成千上万的规则中去查找，严重影响系统的工作效 率。 e c s i 列( e v e n tc o r r e l a t i o ns e r v i c e ) 就是l i p 公司开发的基于规则系统的告警相 关性分析系统，主要应用在高速传输网络如s d h ，a t m 网络中。 2 基于事例推理的告警分析 基于事例的推理f 3 l ( c a s e b a s e dr e a s o n i n g ) 就是直接利用过去的经验和方法 来解决当前出现的问题。在处理一个新问题时，首先在告警事例库中查找相似的 事例；然后将该事例的解决方案应用到新问题中；通过测试来修改建议的解决方 法；最后保存有可能被未来使用的经验。在此知识的单位不再是规则，而是事例。 按照遗：忘曲线理论来维护事例库，即长期不用的信息将会被遗忘，因此需要删除 长期不用的事例，增加新事例，完成事例库的更新。 基于事例的推理的一个显著特点是系统具有自学能力，而不必通过专业网络 管理员获取相关性知识。而且它可以根据出现的错误来对将来的行为自动纠正， 通过调整过去的事例来构建新的方法，对新出现的情况做出处理。该方法的缺点 是拘泥于某个特定的应用领域，缺乏通用的事例方法；对于网络变化不敏感，分 析处理过程复杂、费时，难以适应实时性要求高的告警分析处理问题。文献【3 】 提出了一种基于事例推理的算法，并将其应用于g s m 网络故障检测中。 3 基于因果模型的相关性分析 因果模型法( c a s u a lm o d e la p p r o a c h ) 4 , s 】是一种常用的告警相关性分析方法， 它的优点是可以比较准确进行故障定位并且效率高；缺点是需要建立精确的模 型，从而需要熟悉网络中所有设备及其网络拓扑关系，但是网络是一个多厂商、 多设备、多规格的异构环境，建立这种复杂的设备模型和故障传播模型十分困难， 因此限制了该方法的实用性。 4 基于数据挖掘的告警分析 数据挖掘( d a t am i n i n g ) 是从大量不完整的、有噪音的、模糊的、随机的数 据集中识别有效的、新颖的、潜在有用的，以及最终可以被用户理解的模式挖掘 过程。它是对过去事例泛化的种归纳学习，可以解决分类、聚类、时间序列分 析、关联规则挖掘等问题。为了减少对网络管理员和专家的依赖，通过挖掘历史 告警数据来获得相关性知识已成为目前网络管理领域的一个研究热点。m a n n i l a 2 第一章引言 等较早地进行了这方面的尝试，在文_ 献【6 】中提出了w n i e p i 算法，能够从时序数 据中提取出形如“如果a 事件发生，那么6 0 秒内b 事件发生的可能性为8 0 ” 的告警相关性规则，称之为“情景规则”。刘康平等【7 】研究企业网络告警数据中 的知识发现问题，设计并实现了以a p r i o r i 算法为核心的网络告警关联规则发现 系统，该系统能够有效发现隐藏在海量告警数据背后、不易为网络管理人员所知 的告警及故障模式知识，将发现的新知识应用到告警关联、故障诊断专家系统， 有效突破了专家系统“知识获取”瓶颈，显著增强了专家系统推理和诊断网络故 障的能力。王新苗等【8 】提出一种基于“最小发生的双时i 训窗口约束”时序舰则挖 掘新方法，该方法依据“双时间窗口”约束和“最小发生”判断，可判别在一个 时间窗内的哪些告警事件导致了另一个时间窗内告警集合事件的产生，快速找出 不同网络设备告警与其它网络设备告警之间的关联知识。徐前方等一j 此提出了一 种具有时序特征的告警关联挖掘算法，该方法解决了以往算法中无法发现告警序 列之间时序关系的问题，能够快速、准确地从海量数据中挖掘出具有时序特征地 关联规则。单莘等【lo 】提出了一种基于时间窗约束的增量式频繁情景挖掘算法，算 法的执行效率在一定条件下比原有w i n e p i 算法有显著提高。 5 其它方法【i l 】 除了上述方法外，还有基于编码告警相关性分析，基于贝叶斯网络的告警相 关性分析，基于模糊逻辑的告警相关性分析，基于神经网络的告警相关性分析。 1 3 本文主要工作 由于网络中各告警事件的发生通常具有一定的时序关系，故将序列模式挖掘 应用到网络告警分析之中，本文对此做了深入研究，主要工作包括： 1 、了解数据挖掘概念以及相关方法，分析序列模式两类算法原理、过程。 2 、通过分析网络告警数据特点，提出了告警数据预处理模型，将冗余、含 噪音的原始告警数据转换成适合于序列模式挖掘的告警序列数据库，提高告警挖 掘效率。 3 、深入分析f s p m f p 算法，针对算法中告警序列偏序关系难确定问题，提 出了一个改进方法。 4 、针对目前判断选择频繁告警模式条件单一，告警情景规则精确度不高等 问题，引入拓扑相近关系判断，提出基于网络拓扑关系的频繁情景规则挖掘算法 ( m n e r - t p ) 。 5 、随着网络的不断运行，每天都会产生大量告警，为了适应网络的这种动 态变化，本文提出了基于顺序模式的更新挖掘算法。 第一章引言 1 4 论文组织安排 本文主要介绍序列模式挖掘在网络告警挖掘中的应用研究，文章分为6 章， 具体如下： 第一章引言 简要介绍网络告警挖掘的研究背景、意义，以及国内外的研究现状。 第二章序列模式挖掘概念与算法介绍 概述数据挖掘，介绍序列模式挖掘概念及相关定义，并重点分析了基于 a p r i o r i 的侯选代码生成一测试方法和基于投影的模式增长算法，以及序列模式增 量挖掘算法。 第三章网络告警数据预处理 分析网络告警数据特点，介绍常用数据预处理方法，最后针对告警数据的具 体特点，提出了告警数据预处理模型。 第四章网络告警序列模式挖掘 介绍告警相关性分析有关概念，分析f s p m f p 算法存在的问题，并提出了 改进方法，最后针对目前告警序列选择条件单一问题，引入网络拓扑关系判断， 提出带拓扑关系判断的网络情景规则挖掘算法m n e r t p 。 第五章告警序列模式更新挖掘 介绍告警数据更新挖掘方法，分析频繁模式挖掘算法特点，针对其存在的问 题，引入告警顺序模式树概念，然后给出顺序模式树的更新方法，最后提出了基 于顺序模式的告警增量挖掘算法。 第六章结论 1 5 论文实验数据 实验数据1 实验数据l 是来自南昌大学网络中心整个校园网的告警记录，共采集了1 9 天的实验数据，告警发生时间从2 0 0 8 年6 月8 日到2 0 0 8 年6 月2 6 日，共包括 5 5 4 5 7 条记录，3 0 2 种告警类型。其中每一告警包含多个字段，重点选取与本实 验内容有关的4 个字段：网元标识( n e ti d ) ，告警元i p ( a l a r mi p ) ，告警原因 描述( a l a r ma n a l y s i s ) ，告警发生时间( a l a r mt i m e ) 。 实验数据2 实验数据2 来自某网络公司2 0 天的原始告警数据，共6 4 0 0 0 条记录，5 5 0 种告警类型。每条告警记录含有多个告警字段，为了保证实验结果的精确性，只 4 第一章引言 保留与本实验有关的字段：网元标识( n e t i d ) ，告警元i p ( a l a r m i p ) ，告警原 因描述( a l a r m _ a n a l y s i s ) ，告警发生时间( a l a r m t i m e ) ，潮员拓扑关系 ( n e t w o r kt p ) 。 5 第二：章序列模式挖捌概念与算法介纠 第二章序列模式挖掘概念与算法介绍 2 1 数据挖掘概述 随着计算机网络技术在各个领域的推广使用，使得收集到的关于本领域的数 据一以惊人的速度，爆炸性的增长，远远超过了人的理解能力。“数据丰富但知 识贫乏”问题同益突出。面对如此海量数据，采用手工方法根本无法从中发现有 用的知识。而数据挖掘正是这样一种从大量数据中挖掘知识的工具，它集数据收 集、数据清理、降维、规则归纳、模式识别、结果分析与评价、可视化输出等多 种过程为一体，是统计学、计算机科学、模式识别、人工智能等多个学科相结合 的产物( 12 1 。 简单地浼，数据挖掘就是从大型数据库或数据仓库中储存的大量的、不完整 的、有噪音的原始数据中发现有价值的、潜在的、有趣的知识的过程。提取的知 识一般可以表示为概念、规则、模式等形式。经过数据挖掘得到的知识，不要求 是全新的科学定律或普遍适用的规律。其实它所发现的知识都是相对的，具有特 定前提和约束条件，同时发现的知识还要易于被用户所理解。按照史忠植教授的 定义，知识发现是从数据集中抽取和精化新的模式。如通过对超市顾客购物数据 的挖掘，得到 牛奶一面包 ， 啤酒一尿布) 等知识，如此超市可以按照顾客的这 种购买习惯合理摆放各种商品，从而超市提高赢利。 数据挖掘常用的分析方法【13 。1 5 】有：关联分析( a s s o c i a t i o nr u l e sa n a l y s i s ) 、聚类 分析( c l u s t e r i n ga n a l y s i s ) 、序列分析( s e q u e n c e sa n a l y s i s ) 、分类分析( c l a s s i f y i n g a n a l y s i s ) 。 2 2 序列模式相关概念及定义 序列模式挖掘【m 1 8 1 ( s e q u e n c ep a t t e r nm i n i n g ) 是指挖掘相对时间比其他序列 出现频率高的序列模式，它是数据挖掘的一个重要研究方向，而且应用十分广泛， 包括顾客购买习惯分析，网络告警分析，自然灾害的预测，d n a 序列模式分析 等。序列模式挖掘是对关联规则挖掘的进一步推广应用，很多关联规则挖掘研究 成果经过一定修改可用于序列模式挖掘。序列模式的一个典型例子是“九个月以 前购买奔腾p c 的客户很有可能在个月内订购新的c p u 芯片 。 1 、基本概念 设i = i b i 2 ，i n 为一个非空项目集合( i t e m s e t s ，以下简称项集) ，每个i k ( n k 1 ) 称为项。序列就是有项组成的有序列表，一个序列可以表示为 6 第二章序列模式挖掘概念与算法介针 ，其中s j 为项集，也称作s 的元素。元素有不同的项组成，可以表示 成( x l ，x 2 ，x n ) 。元素之间是有顺序的，但元素内的项是无序的，一般定义为字 典序。序列的长度即为项的个数，用i s i s 示。长度为k 的序列记为k 一序列。序 列数据库( s e q u e n c ed a t a b a s e ) 由元组 组成，s 词是该序列的序列号，s 是 序列，序列数据库的大小用i s d b i 表示。如表2 1 ，数据库大小为5 ，其中 是该数据库的第一个序列，长度为7 。 表2 - 1 序列数据库样例 s i d s e q u e n c e 1 2 3 ( a ，c ) ( b ，c ) ( d ，驴 4 ( c ) ( a ，c ) ( d ) ( d ，护 5 2 、基本定义 定义1 子序列和超序列 假设存在两个序列q 和1 3 = ，当满足条件1 i l i 2 i m m 和a 1 b j l ，a 2 互b j 2 ，a i i b j n 时，则称序列q 为序列1 3 的子序列，序 列1 3 为序列a 的超序列( 1 3 三a ) 。如表2 一l ，序列 为例，其 中 ， 都是 的子序列， 是 ， 的超序列。 定义2 序列支持度 序列数据库是由元组 组成，如果序列t 是s 的子序列( t s ) ，即元 组 包含序列t ，序列数据库中包含子序列t 的元组数称为t 的支持数， 即s u p p o r t c o u n t ( t ) = i i s d b 八丁互s ) i 。把支持数与序列数据 库大小( f s d b ) 之比称为支持度( s u pp ( t ) ) ，s u pp ( t ) = s u p p o r t c o u n t ( t ) s d bl 。 如表2 1 中子序列 支持数为3 ，支持度为0 6 ，子序列 支持数为2 ，支 持度为o 4 。 定义3 频繁序列 设最小支持度阈值为m i n _ s u p p ，称支持度超过m i n _ s u p p 的子序列s 为频 繁序列，反之称作非频繁序列。同样如表2 1 ，设m i ns u p p 为0 3 ，由于子序列 ， 支持度均超过o 3 ，故把子序列 ， 称作序列数据库的频 繁序列，子序列 支持度为0 2 ，没有超过0 3 ，故把子序列 称作序列 数据库的非频繁序列。 7 第二章序列模式挖掘概念与算法介绍 2 3 序列模式挖掘算法 根据算法的不同研究方向，可以将序列模式挖掘算法大致分为模式挖掘一般 算法、模式增量挖掘算法、多维模式挖掘算法、约束序列模式挖掘算法等研究方 向。 2 3 1 基于a p r i o r i 的侯选代码生成。测试算法 序列模式挖掘足对关联规则挖掘的进一步的推广，它挖掘出序列数据库中项 集的时序关联舰则。序列模式挖掘算法可以分为2 类：基于a p r i o r i 的侯选代 码生成测试方法；基于模式增长的方法。基于a p r i o r i 特性的算法中有采用水 平数据格式( h o r i z o n t a ld a t af o r m a t ) 的算法，如g s p 算法【1 9 】等；有采用垂直数据 格式( v e r t i c a ld a t af o r m a t ) 的算法，如s p a d e 算法【2 0 1 等；基于模式增长 ( p a t t e r n g r o w t h ) 策略的算法，如p r e f i x s p a n 算法【l6 】等。同时在此基础上提出了挖 掘闭合频繁模式，最大频繁模式，约束模式挖掘等算法。 基于a p f i o f i 性质的序列模式挖掘算法是采用逐层产生和测试序列的方式进 行。算法基本思想框架如下： 扫描数据库一次，找出频繁1 序列集合l l ； 对l 1 中各序列作自我连接，产生候选2 一序列集合c 2 ，再次扫描数据库 给候选序列计数，找出满足最小支持度的频繁2 序列集合l 2 ； 对l k 中各序列作自我连接，产生侯选k + l 一序列集合c k + l ，再次扫描数据 库给候选序列计数，找出满足最小支持度的频繁k + 1 序列集合l k + l ； 重复，直到没有候选序列产生为止。 它是一种发现频繁序列模式的经典算法，能找到所有频繁序列模式，但是从 算法描述分析，其存在三个不足之处： ( 1 ) 侯选序列集合庞大。因为序列项目之间有顺序，所以不同项目交换就 会产生很多不同的序列，而且项目可以重复出现，这足以说明侯选序列数目非常 庞大。比如频繁1 一序列 、 和 可以产生9 个侯选2 序列 、 、 、 、 、 、 、 、 。 ( 2 ) 需要对序列数据库进行多次循环扫描。在挖掘过程中，侯选序列长度 每增加l ，就必须扫描序列数据库1 次，要找出长度为l 的频繁序列，至少要扫 描l 次数据库。当要发现长频繁模式时，这种多次扫描数据库的方法是很费时。 ( 3 ) 由于长模式包含很多子模式，每个子模式都需要生成测试，这将导致 侯选序列的数量随着需要挖掘的序列模式长度呈指数级增长。比如序列数据库中 只包含一个长度为5 0 的序列，且支持数阈值为1 ，那么将要产生 8 第二：章序列模式挖掘概念与算法介绍 5 0 x 5 0 + ( 5 0 x 4 9 ) 2 = 3 7 2 5 个侯选2 序列，( 5 0 4 9 4 8 ) ( 1 2 3 ) = 1 9 6 0 0 个侯选 3 序列，总共产生罗：o t 。= 2 5 0 一l 1 0 b 个侯选序列。 针对a p f i o f i 算法的上述缺点，不少学者提出了改进方法，如文献1 2 1 提出了 一种基于二进制形式的模式矩阵的高效改进算法( p m a t r i x ) ，算法分成两个步骤， 首先扫描数据库一遍，得到二进制形式的模式矩阵并对他进行转置，其次对转置 的模式矩阵各行按位作与运算，直接产生频繁项目集。新算法只需扫描数据库一 次，同时不产生侯选项目集而直接产生频繁项目集，大大降低了算法的时间复杂 度和空间复杂度。 2 3 2 基于投影的模式增长算法 基于投影的模式增长算法，首先将序列数据库投影为多个投影数据库，然后 在小投影数据库中采用模式增长方法进行递归挖掘。以文献f 2 2 1 提出的p r e f i x s p a n 算法为例进行描述说明。它是通过前缀投影来挖掘序列模式，进行投影时，并不 考虑所有出现的频繁子序列，而是找出前缀序列，把相应的后缀投影成一系列的 投影数据库。对每一个投影数据库，只须找出局部频繁模式，且不产生侯选码。 算法基本框架如下： 扫描数据库一次，找出频繁1 序列，假设为k 个； 划分研究空间：把完整的序列模式划分为k 个研究空间，分别以频繁1 序列为前缀； 构造相应的数据库，也就是对应前缀的后缀集合； 在这些后缀集合中递归地发现频繁模式的子集。 下面给出算法步骤： 、 输入：序列数据库d ，最小支持度闽值m i ns u p ； 输出：所有序列模式； 方法：调用子程序p r e f i x s p a n ( ，0 ，s ) 子程序p r e f i x s p a n ( q ，l ，s lq ) 参数说明： q ：一个序列模式；l ：序列模式c i 的长度；s lq ：如果c i 为空，则为s ，否则 为q 的投影数据库 扫描s iq ，找到满足下述要求的长度为l 的序列模式b ； a b 可以添加到q 的最后一个元素中并为序列模式 b 可以作为a 的最后一个元素并为序列模式 对每个生成的序列模式b ，将b 添加到q 形成序列模式q ，并输出q ； 对每个c i ，构造q 的投影数据库s ic i ，并调用子程序p r e f i x s p a n ( c t ，l + i ， 9 第二章序列模式挖掘概念与算法介绍 s iq ) 。 相比基于a p r i o r i1 j 牛质算法，频繁模式增长算法有以下特点： ( 1 ) 模式增长算法不需要产生侯选码，大大减少了搜索空阳j 。 ( 2 ) 对于一个序列，由于挖掘时前缀不断增长，后缀不断减少，即投影数据 库的规模随着挖掘过程向更长的序列模式进行越来越小，但包含着同样模式的必 要信息，可见基于投影的分治策略有效地减少数据，减少算法的代价。 ( 3 ) 该类算法的代价主要在于投影数据库的构造上，当序列模式数据库很大， 存在很多序列模式时，那么就要构造很多的投影数据库，丌销相当大。 目前已有不少学者在模式增长挖掘算法基础上，为了进一步减少模式生成数 量，做了不少改进，其中包括加入时间限制，挖掘近似模式基，具体可以参考文 献【2 3 , 2 4 1 。 2 4 序列模式增量挖掘 对于现实序列数据库，数据是随时间而不断更新变化的，使得当前已发现的 频繁序列模式可能不再生效，而可能存在新的频繁序列模式有待于进一步去发 现。同时在一次挖掘过程中，用户一般也会不断地调整算法参数( 如最小支持度、 最小置信度等) ，通过反复调整，从而挖掘得到真正感兴趣的序列模式。由于上 述两种类型算法都是基于静态数据库的，不适合数据库的动态更新，因此研究序 列模式的增量更新挖掘十分必要。 1 、基于数据库动态变化的增量挖掘 设原事务数据库d ，相应的序列数据库为s d ，新增事务数据集为d ，相应 的序列数据库为s d 。考虑最小支持度不变，序列数据库s d ( 事务数据集d ) 追加到 序列数据库s d ( 事务数据库d ) 中去时，如何生成最新序列数据库s u ( s u = s du s d ) 中的频繁序列模式。 该类算法的关键技术是要充分利用初始挖掘结果，减少对原始数据库的重复 挖掘，能够只对发生变化的那部分数据进行扫描处理，进而找到更新数据库的频 繁序列模式，这已经成为衡量增量挖掘算法的性能的一项重要指标。 最初提出的一些增量挖掘算法，并没有利用原始挖掘结果，而只是重复扫描 数据库，发现频繁序列模式，不能满足增量挖掘算法的性能要求。有不少学者对 此进行了深入研究，提出了一些新方法，新思路，从而提高增量挖掘的效率。陶 再萍等提出的s p i u 算法【l7 】充分利用原始交易数据集的扫描结果，对更新数据集 和新增数据集进行多次扫描，并对候选频繁序列进行充分的剪枝，从而提高了算 法的效率。陆介平等提出的i s p b p 算、法【1 8 】引入序列数据库结构来存储从原始数 l o 第二章序列模式挖掘概念与算法介绍 据库中挖掘出的所有项、最大频繁模式以及它们的支持数，采用间接拼接方法， 只需处理增量数据库，避免了对更新后数据库的重新计算。对于因增量数据库新 产生的频繁模式，利用了在增量数据库中出现的频繁项集来减小投影数据库，进 一步提高了算法的效率。在分析了频繁序列模式更新算法关键技术的基础上，陈 健美等提出了一种快速的增量式更新频繁序列模式挖掘算法f u f s p a l 2 5 j ，该算法 将充分利用先前挖掘过程中所产生的信息来减少本次挖掘过程中的时问开销。另 外，针对频繁序列模式挖掘中支持数计算的复杂性，提出了一种基于二进制形式 的支持数计算方法，该方法只需进行一些“或”逻辑运算操作，将该方法用于序 列模式挖掘中支持度的计算，可以进一步提高算法的执行效率。其他有关增量挖 掘算法，可以参考文献【2 6 , 2 7 。 2 、基于用户交互的动态挖掘 交互式挖掘是指在挖掘过程中，为了得到最有价值的模式，用户往往会不断 调整参数值( 支持度，置信度，告警时问窗口，滑动步长等) ，进行反复挖掘。 在提高支持度阈值时，些原本频繁的序列模式，变成了非频繁的序列模式， 要解决的问题就是如何利用上次的挖掘结果，高效率地找出这些非频繁模式。同 样对于支持度阈值降低的情况，原本不频繁的模式，变成了频繁的模式，如何在 先前挖掘的基础上，尽可能低开销的挖掘出那些模式。对于告警时间窗口和滑动 步长发生改变同样存在上述问题。单莘等【lo 】在电信网告警数据库中的增量式挖掘 技术研究中，基于w i n e p i 思想，讨论时间窗宽度改变情况下对候选集规模削减 的两个约束条件，基于此提出了一种基于时间窗约束的增量式频繁情景挖掘算 法，即选出一个可能的最小时问窗w i n r n i n 和最大时间窗w 氓嗍，使得用户感兴趣 的窗口宽度w i n 一般满足w i n m i n w i n w i n m a 。条件，保存w i n m i n 和w i n m 积下的候 选情景集的计算结果，从而配合前次挖掘结果得到更新模式集。 2 5 序列挖掘其他研究方向 针对不同的挖掘要求，序列模式挖掘也朝着不同的方向发展，根据文献【2 8 】 主要有以下几个发展方面： ( 1 ) 多维( m u l t i d i m e n s i o n ) 序列模式挖掘 在挖掘序列模式时，除了考虑事件发生的时问属性外，同时添加了与之相关 的其他维度属性。多维序列模式挖掘是为了根据不同维的属性得到对用户更加有 用的的序列模式。 ( 2 ) 约束( c o n s t r a i n e d ) 序列模式挖掘 在多数序列模式挖掘任务中，用户并不对所有的序列模式感兴趣，因而增加 第：蕈序列模式挖掘概念与算法介绍 一定的约束条件，这样可以有效减少序列模式的生成数量，有利于用户找出对自 己有用的序列模式。 ( 3 ) 闭合( c l o s e d ) 序列模式挖掘 当序列模式很长时，由于每个序列模式包含了大量的频繁子序列，挖掘出全 部可能模式，将导致挖掘丌销过大，然而实际应用中经常要挖掘长模式，如d n a 序列。闭合序列模式是不包含具有相同支持度的频繁超模式，即如果一个模式和 它的支持度能够通过具有相同支持度的超模式得到，那么它就是多余的。闭合序 列模式挖掘能够得到同样表达能力的最精简模式集合。 ( 4 ) 最大( m a x i m a l ) 频繁序列模式挖掘 由于应用领域的不同，没有必要完全的频繁序列集，最大频繁序列和频繁闭 序列集拥有与完全频繁序列集相同的表达能力，却有着形式简洁和数量较少的优 点，充分减少结果集的冗余度。 ( 5 ) 分布式( d i s t r i b u t e d ) 序列模式挖掘 随着计算机应用不断推广和深入，海量数据使得传统的单机系统在性能和功 能上不能满足数据处理的需求，实际应用中很多大型数据库都是分布存储的，因 此挖掘分布式环境下的全局频繁模式具有十分重要的意义。 2 6 本章小节 本章主要介绍序列模式挖掘相关定义，序列模式挖掘两类代表算法和更新算 法，然后给出序列模式挖掘的其他研究方向。 1 2 第二章网络告警数据顶处理 第三章网络告警数据预处理 3 1 网络告警数据特点 网络故障是指被管理网络及其部件在运行期间出现硬件或软件问题，使之不 能正常提供服务，从而产生告警，它是网络故障的外在表现。当网络部件出现完 全瘫痪状态时，则产生硬故障，如服务器崩溃、链路断开、路由器失效等。当网 络部件运行出现低能状态时，可能足软件故障引起的。 根据故障的不同表现状态，可以将它分成以下几种2 9 , 3 0 】： 1 、硬件故障 硬件故障指网络运行设备出现永久性瘫痪，需要系统对其进行手动恢复，无 法自我修复的故障。 2 、瞬间故障 瞬间故障指故障持续时间很短，对服务性能影响是暂时的、微小的。当瞬问 故障发生过于频繁时，才需要系统对其进行维护。 3 、软件故障 软件故障指系统中的任何软件在运行当中出现问题而产生的故障，通常是由 网管软件自身的错误引起的。 4 、信息报告 信息报告指一些硬件或软件差错，不需对其进行恢复、处理，仅仅报告给操 作员，如设备测试中的一些错误信息等。 在网络实际运行过程中，很多网络告警没有包含故障产生的直接原因，并且 一个故障通常会导致相关设备向网管系统发送多个告警。由于这些原因，通常收 到的告警信息中含有很多冗余信息，所以准确分离和定位故障是相当困难的。网 络故障一般有以下几个特点： 1 、告警信息量大，告警存在突发性，告警类型种类多且格式不统一，采用 人工告警分析、故障诊断效率低，并且实现起来极不方便。 2 、由于网络协议和拓扑关系复杂，网络中的某个故障可能会影响多个相关 设备，导致故障传递和扩散。 3 、很多告警信息中一般不包括定位故障的根源，所以必须对告警信息进行 相关性分析才能准确定位告警发生源。 4 、在多个故障同时发生的情况下，会出现告警事件的重叠。 5 、大型、异构的通信网络中一般网络时间不统一，增加了对告警信息分析、 比较的复杂性。 第三章网络告警数据预处理 原始告警数据的这些特点对告警挖掘增加了难度，所以为了得到较好的挖掘 结果和效率，告警数据预处理显的十分必要且重要。 3 2 常用数据预处理方法 现实世界的数据一般是脏的，不完整的和不一致的。数据预处理技术可以改 进数据质量，进而提高挖掘结果的精确度和挖掘效率。p y l e 3 l 】强调了数据预处 理的重要性：数据预处理过程在数据挖掘过程中占据了6 0 的时间。对于网络告 警数据存在同样问题，由于网络设备运行失常，或者线路传输时延等问题，如果 把原始告警数据直接用于告警序列模式挖掘，则会严重影响挖掘效率以及结果精 度，甚至产生错误结果。为此，有必要对告警数据预处理进行研究分析，提高挖 掘结果的准确度。根据文献【3 ，目前数据预处理方法主要有以下几种：数据清洗、 数据集成、数据变换、数据简化。 3 2 1 数据清洗 数据清洗( d a t ac l e a n i n g ) ：数据清洗的目的是平滑噪音数据，识别、删除 孤立点，同时要把按不同的、不兼容的规则所得的各种数据集中起来。数据清洗 主要采用回溯思想，从产生脏数据的源头开始分析，对数据集每一流经过程进行 分析考察，从中提取清洗算法、规则和策略，然后利用这些算法、规则和策略来 发现“脏数据”和清洗“脏数据 。基本原理【3 2 1 如图3 1 所示： 同一数值的不同表示 上 脏数据 卜 图 例j 轸 彩 数据清理策略、规 1 贝l j 函 满足数据清理质量要求的数据 图3 - 1 数据清洗原理 1 4 不合法值 窄值 异常处理 重复操作 第三