（计算机科学与技术专业论文）数据挖掘在综合网管告警相关性分析中的研究和应用.pdf

中文摘要 中文摘要 摘要：随着电信事业的发展，电信网开始逐渐由许多独立的专网互联组成，从而 使网络资源之间，网络资源和业务之间更加紧密的结合在了一起。电信网管理的 综合化，智能化成为电信网网络管理系统的发展方向。综合网络管理系统的目标 之一是实现对多个子网的集中监控。但是由于电信网络规模越来越大，结构越来 越复杂，这样在同一时间产生的告警信息不仅类型多，而且数量也很庞大。这样 要想有效的分析告警的根源，定位故障源将是很困难的。告警相关性分析的引入 可以较好的解决这一问题。其中规则是进行告警相关性分析的必要条件，因此规 则的获取成为解决这一问题的关键点之一。 通过人为总结获取的规则，不能较好的适应电信网络不断变更的需求。因此 需要对网络管理数据库中的告警数据进行更准确的非人工的分析和处理来获取规 则。本文在研究告警相关性分析和规则挖掘的理论和算法基础上，引入层次分析 法和序列模式技术，力求改进经典的关联规则挖掘算法的挖掘质量，减少对数据 库扫描次数和减轻i o 负荷。基于上述改进方案，本文从告警数据的预处理，频繁 集和规则的挖掘以及挖掘规则的后处理三个阶段出发，设计和实现了关联规则挖 掘系统，实现了规则学习的自动化。关联规则挖掘系统和基于规则引擎的相关性 分析系统的集成应用，使告警相关性分析在综合网络管理系统中的应用更加的完 善。最后本系统将应用在朔黄铁路综合网络管理系统中，实现告警过滤，告警源 的分析和故障定位，提高网络运维的效率，保障网络畅通。 关键词：告警相关性分析；关联规则；数据挖掘；层次分析法；序列模式 分类号：t p 3 9 a b s t r a c t a b s t r a c t ：w i t ht h eh i g h - s p e e dd e v e l o p m e n to ft e l e c o m m u n i c a t i o n s i n d u s t r y , t e l e c o m m u n i c a t i o n sn e t w o r ki sc o n s i s to fm a n yo f p r i v a t en e t w o r k sw h i c ha g e i n t e r c o n n e c t e d ，s ot h a tn e t w o r kr e s o u r c e sa n db u s i n e s sa g eb e c o m i n gm o r ea n dm o r e c l o s e l yi n t e r l i n k e d a sar e s u l lt h ed e v e l o p m e n to ft e l e c o m m u n i c a t i o nn e t w o r k m a n a g e m e n tt e n d st ob ec o m p r e h e n s i v ea n di n t e l l i g e n t i n t e g r a t e dn e t w o r km a n a g e m e n t s y s t e ma c h i e v e st om o n i t o rt h es u b n e t w o r km a n a g e m e n ts y s t e m st o g e t h e r h o w e v e r , d u et ot h ei n c r e a s i n gs c a l eo ft e l e c o m m u n i c a t i o nn e t w o r k sa n dm o r ea n dm o r ec o m p l e x c o n s t r u c t i o n , t h et y p eo fa l a r mi sr i c ha n dal a r g ea m o u n to fa l a r mi sg e n e r a t e da tt h e s a m et i m e i ti sv e r yd i f j f i c u l tt of i n dt h er o o t a l a r ma n dl o e a l i z et h ef a u l ts o u r c e a c c u r a t e l y i no r d e rt os o l v et h i sp r o b l e m ，a l a r mc o r r e l a t i o na n a l y s i sn e e d st ob e i n t r o d u c e d a l a r me o r r e l a t i o nr u l ei sn e c e s s a r yf o ra l a r mc o r r e l a t i o na n a l y s i s s oi ti s o n eo ft h ek e y p o i n t st og e tt h er u l e st oa c h i e v ea l a r mc o r r e l a t i o na n a l y s i ss y s t e m b e c a u s et h ea l a r mm l ew h i c hi sg o tb yn e t w o r km a n a g e m e n ts t a f f se x p e r i e n c ei s n o tg o o de n o u g ht oa d a p tt ot h ef r e q u e n tc h a n g eo ft e l e c o m m u n i c a t i o nn e t w o r k ，a l a r m d a t ai nt h en e t w o r km a n a g e m e n ts y s t e mn e e d st ob ea n a l y z e da n dp r o c e s s e db yo t h e r a c , e u r a t em e t h o d si no r d e rt oo b t a i na l a r mr u l e b a s e do nr e s e a r c ho ft h e o r i e sa n d a l g o r i t h m sa b o u ta l a r mc o r r e l a t i o na n a l y s i sa n dr u l em i n i n g , t h ep a p e rp r e s e n t st h e m e t h o do fi m p r o v i n ge f f i c i e n c yo fr u l em i n i n ga l g o r i t h m ，r e d u c i n gt h en u m b e ro f d a t a b a s es c a n n i n ga n di 0l o a db yi n t r o d u c i n gt h et e c h n o l o g i e so fa n a l y t i ch i e r a r c h y p r o c e s s ( a h p ) a n dt i m es e r i e s t h e n , t h i sp a p e rd e s i g na n di m p l e m e n tt h er u l em i n i n g s y s t e mw h i c hb s e st h ei m p r o v e da l g o r i t h ma n dr e a l i z e st h ef u n c t i o no fr u l es e l f - l e a r n i n g t h ep r o c e s so f a c h i e v i n gt h es y s t e mi sd i v i d e di n t ot h r e ep h a s e s ，i n c l u d i n ga l a r md a t a p r e p r o c e s s ，r u l em i n i n ga n dp o s t - p r o c e s so fr u l e s a p p l i c a t i o no fa l a r mc o r r e l a t i o n a n a l y s i sw i l lb ep e r f e c ti nt h en e t w o r km a n a g e m e n ts y s t e m ，i fb o t hr u l em i n i n gs y s t e m a n dr u l ee n g i n es y s t e ma r ea c h i e v e di nt h es a m es y s t e m f i n a l l y , t h es y s t e mw i l lb e u s e db yt h es h u o h u a n g r a i l w a yi n t e g r a t e dn e t w o r km a n a g e m e n ts y s t e m ，i no r d e rt o f i l t e ra l a r m ，a n a l y z er o o t a l a r m ，l o c a l i z ef a u l ts o u r c e ，i m p r o v et h ee f f i c i e n c yo fn e t w o r k o p e r a t i o na n de n s u r et h en e t w o r kt ob en o r m a l k e y w o r d s ：a l a r mc o r r e l a t i o na n a l y s i s ；c o r r e l a t i o nr u l e ；d a t am i n i n g ；a h p ； s e q u e n c ep a t t e r n c l a s s n o ：t p 3 9 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。 同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 忌或鸸 签字日期：z 一7 年月，字日 一名：糖咖 礓 签字日期： 。 年厂月( 8 日 独创性声明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：速嚷嘴 签字日期：z 们c 年 6 月it ? n 致谢 本论文的工作是在我的导师杨芳南老师的悉心指导下完成的，杨芳南老师严 谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢两年来 杨芳南老师对我的关心和指导。 杨芳南老师同时指导我完成了实验室的科研项目工作，在生活和学习上都给 予了我很大的关心和帮助。特别在科研项目学习上，杨芳南老师给予我很好的学 习和实践的机会，让我得到了系统的科研实践机会，培养了我将理论和实践紧密 结合的能力，让我对科研开发和工程项目有了全面的认识，并树立信心。在此再 次向杨芳南老师表示衷心的谢意。 在实验室工作及撰写论文期间，刘真老师、孙延涛老师、刘强老师提供了热 情的帮助，在此对他们表示感谢。 感谢网络管理研究中心的刘峰、李红辉、宋晓红、李秋莎等老师，感谢他们 在我生活、学习、工作上给予的关心、指导和帮助，从他们的身上，我学习到很 多。 马飞、刘涛、彭丽娟、陈晋鹏、张贝贝、杨光、尚云云等同学对我论文中的 研究工作给予了热情帮助，在平时生活中互相关心互相帮助，使我的研究生生涯 有了美好的回忆，在此向他们表达我的感激之情。 另外也感谢我的家人，他们的理解和支持以及对我无微不至的关怀，使我能 够在学校专心完成我的学业。 引言 1 引言 1 1研究背景和意义 通信业务需求的全面扩张，造成了网络规模的扩大，复杂性的提高和带宽需 求的显著增长。因此对网络管理的综合化、自动化、智能化已经成了综合网络管 理的趋势【lj 。 综合网络管理系统对网络进行统一的、一体化的管理，它是收集、传输、处 理和存储有关网络维护、运营和管理信息的一个综合管理系统。建立综合网管系 统的目的，就是要最大限度地利用网络资源，提高网络的运行质量和效率，简化 多厂商混合网络环境下的管理以及控制网络的运行成本，提高维护手段，并提供 网络的长期规划。因此，综合网络管理系统需要与各专业子网网管系统按定义的 规范和接口交换管理信息，形成一个综合管理平台。综合网管系统管理的通信网 络有成千上万的通过多种传输媒质互联的节点构成。因此当一个网络故障或者问 题发生时，可能会有大量的告警信息产生。因此故障管理作为综合网管系统中五 大基本功能模块之一，其智能化显得尤其重要。在故障管理中，告警信息通常被 用于故障诊断，但当告警信息多的将网管中心淹没起来时，急需要一种技术来减 少告警数据。协助网管人员分析故障信息和进行故障定位，网络故障时间将被大 大缩减。 告警相关性分析是用于管理大量事件消息的首选技术，通过过滤掉不必要的 或者不相关的告警，可以减少呈献给操作人员的信息，同样，通过相关性分析， 能够增加信息的语义内容，从而有助于判断内部问题或者时间根源。如果能够实 现告警相关性分析，则提高潜在收益，因为故障可以被更快地诊断和定位，从而 可以更快地恢复业务。规则是告警相关性分析的必要条件，如果规则能非人工获 取的话，将进一步提高网络运维效率。 本课题来源于朔黄铁路综合网络管理系统，本系统所管理的网络涉及多厂商 多设备。本文在对告警相关性分析理论和技术进行了深入对比研究之后，提出了 基于数据挖掘的告警相关性规则发现系统，通过分析数据库中的告警信息，达到 规则的自学习，将获取的规则保存到规则引擎，然后规则引擎动利用这些规则动 态分析实时告警，对比规则实现告警转故障和根告警分析，为系统的故障管理智 能化提供解决方案。不管是从理论研究还是实际工程研究应用方面都有着很强的 意义和价值。 北京交通大学硕士学位论文 1 2国内外研究现状 关联规则挖掘是数据挖掘中最活跃的研究方法之一，利用数据挖掘技术来实 现网络管理中故障管理的智能化，规则学习的自动化。近年来，智能化网络管理， 包括智能化的网络故障诊断与定位等技术发展迅猛，告警相关性分析已成为网络 故障诊断的重要手段，尤其是挖掘算法的引入更加加快告警相关性分析在综合网 管系统中的应用。 国外市场上相继出现了一些告警相关性分析产品【2 】，按照采用的技术不同分类 如下：基于数据挖掘方法，以t a s a ( t h et e l e c o m m u n i c a t i o nn e t w o r ka l a r m s e q u e n c ea n a l y z e r ) 系统和a t & t 的s c o u t 系统为代表；基于规则的方法，以h p 公司的产品e c s ( e v e n tc o r r e l a t i o ns e r v i c e s ) 、a t & t 公司的产品4 e s s e s ( 4 e s s e x p e r ts y s t e m ) 和i l o g 公司的j r u l e s 为代表；基于事例推理的方法，以i b m 公 司的n e t f a c t ( n e t w o r kf a u l ta n da l a r mc o r r e l a t i o na n dt e s t 砷产品为代表；基于模 型推理的方法，以g t e 公司的i m p a c t ( i n t e l l i g e n tm a n a g e m e n tp l a t f o r m sf o ra l a r m c o r r e l a t i o nt a s k s ) 为代表。以上提及的产品由于使用的方法不同而各有优缺点。例 如，基于事例的方法是与某个特定应用领域紧密相关，而不存在一个通用的事例 方法，因此它对于网络变化处理反映不敏感；基于规则的方法由于需要人工来维 护大量告警规则，因此在适应大规模和技术复杂的通信网络模型会很困难等等。 目前，我国告警相关性产品总体上还处于不成熟的阶段，在国内还没有得到 广泛的应用。但实际原因在于综合网管系统在国内电信行业仍处在发展完善阶段。 在告警相关性分析方面，虽然也有了一定的发展，但在规则获取方面，却是少之 又少。同国际市场相比，这方面的应用差距更大。在目f i i 我国的综合网络管理市 场上，大部分相关产品，都提出了告警相关性分析的支持功能，也有许多产品说 实现了告警相关性的分析，但其实只是实现了一些比较基础的告警过滤、告警规 避等功能，规则的获取功能更有待考虑。即使有较强大的功能，也大部分是集成 了国外的同类产品。基于数据挖掘判断的专家系统技术强化了复杂问题诊断处理 机制。如在故障管理过程中，为了能对全网告警做到全程的、端到端的、多层次 的、复杂的相关性分析，需要引入基于数据挖掘的关联规则挖掘算法，获取适合 综合网的关联规则，这种技术在理论研究方面己经取得比较成熟的发展，但是目 前在网络管理系统中的应用相对较少。国内网络管理软件这种应用还是处在起步 阶段，且多为集成国外软件同类产品。告警相关性分析产品可能在专网的网络管 理方面需求较低，但是面对电信网络综合化发展的今天还是有着一定发展前景。 因此在综合网管系统中将数据挖掘技术应用到告警相关性分析中获取关联规则存 在着较好的应用前景。 2 引言 1 3研究内容 本文重点研究的内容为综合网管中告警相关性分析中的规则发现功能，并将 其应用在朔黄铁路综合网络管理系统中。 首先本文研究了告警相关性分析和规则挖掘算法的理论与算法，提出了基于 数据挖掘的规则发现的系统模型。在阅读了大量相关文献的基础上，本文设计并 实现了基于数据挖掘的规则发现系统，实现告警相关性分析系统中规则的自学习。 最后本文将规则挖掘系统和基于规则引擎的相关性分析系统进行集成实现综合网 络管理中真正的告警相关性分析系统，目前该告警相关性分析系统已经应用在朔 黄铁路综合网络管理系统中。 1 4论文结构 本文以告警相关性分析在综合网络管理中的应用背景出发，利用数据挖掘技 术对告警相关性分析中规则发现系统进行设计和实现。本文分六章对所研究的问 题进行了讨论： 第一章：介绍了本文研究的课题背景和来源，提出本文的研究内容。一： 第二章：研究了告警相关性分析的相关理论和算法，分析了告警相关性分析 的需求。 第三章：研究了数据挖掘技术及其用于告警相关性分析中规则发现的关联规轧 则挖掘算法，提出将加权和时序的思想引入到关联规则算法中，同时分析设计了 该算法在综合网管中的应用。 第四章：本文的设计部分，介绍了整个综合网络管理系统的框架设计和告警 相关性分析模块设计。设计了规则发现模块框架，处理对象模型，规则发现数据 库和规则发现相关参数。 第五章：本文的实现部分，分别介绍了规则发现系统三阶段的功能，类图和 实现的用户界面，通过实验测试分析了引入加权和时序思想算法的有效性，最后 整体介绍了综合网络管理中的告警相关性分析系统。 第六章：总结了全文，并提出本文需要进一步研究的内容和方向。 北京交通大学硕士学位论文 2 告警相关性分析研究 2 1告警相关性分析中的告警 告警相关性分析【2 】【3 】中是对告警信息进行分析，因此首先来解释一下什么是告 警，以及告警的特点。 ( 1 ) 告警的定义 在综合网络管理领域，故障被定义为产生功能异常的原因。故障是产生告警 事件的原因。告警是在特定事件发生时被管对象发生的通报构成的一种事件报告， 用于传递告警信息。告警是一个系统发生的短消息，表示其发生了某些事情或者 异常。告警只是表示可能有故障发生，但并不一定有故障发生。资源的被管对象 可以发生告警事件作为对系统当前发生异常的响应。 告警事件包含被管对象状态异常的信息，一个告警消息通常包含以下信息： 有关发出告警设备的信息，故障的征兆，以及告警产生的时间等。但是告警通常 并不明显包含网络中故障和问题根源的确切位置信息，当网络中出现故障时，会 引发一系列告警，但并不是所有告警都表明故障原因，这就需要通过分析网络产 生所有告警来判断故障的根本原因。需要注意的是，告警仅仅是反应网络状况发 生改变的征兆，这就是说，通常是故障产生了告警，一个故障可能是另一个故障 的根源，但一个告警绝对不会产生其他告警。告警按照严重程度划分为：严重告 警，主要告警，次要告警，提示告警，不确定告警和清除告警。 ( 2 ) 告警的特点 综合网管管理系统中告警信息的特点主要表现如下： 时间不同步：在大型、异构通信网络中没有统一的网络时间，导致告警事件 的时间存在一定的误差，这为告警事件的分析和比较带来困难。 重复告警：单独一个告警可能己经被多个网络部件检测到，每个部件都发送 告警事件，导致告警信息的重复。 c j j 断告警：当网络业务量陡增时，很容易引发网络阻塞，或者硬件处理能力 的滞后，对于网管系统通常表现为非j 下常状态，但是这并不是网络或者网络设备 的真实状态，可能在一个随机时川后恢复正常。另外，因为通过设备的实际! i k 务 量具有一定的随机性，所以其处理器的负荷也会产生波动，从而导致网管系统与 设备管理进程通信时会随机地产生超时错误，进而导致闪断告警。 告警扩散：网络故障是通过网络中被管对象的状态变化表现出来的。而网络 中，部分被管对象之间是相互关联、相互影响的，当一个或多个对象的状态发生 4 告警相关性分析研究 变化，网络中出现某个故障时，可能引起相关对象的状态变化，进而引起网络中 其他故障的发生，造成告警扩散现象。 从以上告警的特点出发来处理告警信息，进行告警数据的过滤，消除告警的 冗余数据，从而可以针对性的处理专业的告警数据，提高告警相关性分析效率。 2 2告警相关性分析理论研究 告警相关性分析是指对告警进行合并和转化，将多个告警合并成一条具有更 多信息量的告警，这样可以通过发送一条告警来代替多条告警。对于告警相关性 知识，从原则上讲可以从设备涉及人员或丰富操作经验的工程师获得，但这个过 程相当繁琐，而且单从工程师那里获取告警相关性知识，已无法满足网络维护的 需要，因此迫切需要新的方法分析网络中的告警相关性，辅助网络管理人员查明 产生故障的原因。因此告警相关性分析是目前网络管理领域的一个热点问题【1 】【2 】。 2 2 1告警相关陛的定义 告警的“相关性 表示了两个告警或者更多告警实体之间具有相互联系的 情况，相关性分析的结果有两种：一是信息的语义内容被增加了；二是独立单元 的总数缩减了。因此，告警相关性分析可以被定义为：针对多个告警的分析解释， 从而提高了一个数量缩减后的告警集合的语义信息内容。这给最初定义的告警事 件增加了新的含义。 对告警相关性的形式化定义是：告警事件a 与告警事件集合相关 口。，a ，a 。 ， 表示为口j 口，口，口。 。告警相关性分析可以用于网络故障定位和告警过滤。 故障处理过程可以分为三个阶段：告警相关性，故障定位和故障验证。前两 个阶段通常认为是故障定位的处理过程，通过对告警相关性进行分析，提出各种 对故障情况的假设。最后一个阶移是验证各种故障假设是否正确。例如，在网络 监测方面，接收到两个告警事件：服务器连接失败和客户端连接失败，故障的原 因可能是路由器故障或者交换机故障，此时网络管理员无法判断是路由器故障， 还是交换机故障。如果知道告警相关性规则，如只有路由器可以造成上述告警， 就可以直接判断是路由故障。网络管理员可以直接检查路由器的工作情况，不需 要再对交换机进行检查，这样减少了网络管理员的劳动强度，同时提高工作效率。 告警过滤是用柬将非故障告警过滤掉，保留主要的，根本性原因告警。例如： 上例如果知道告警相关性规则，就可以直接过滤掉服务器理解失败告警和客户端 理解失败告警，报告路由器告警事件。 北京交通大学硕士学位论文 2 2 2告警相关性的类型 通常告警相关性分析系统中告警事件的关联类型主要有以下几种： ( 1 ) 告警泛化：通过用更笼统的告警信息对原来的告警信息进行替代，其公 式描述为：用告警的超类代替该告警： a ，ac 脚j b 。 ( 2 ) 告警特化：通过用更详细的告警信息对原来的告警信息进行替代，其公 式描述为：用告警的特定子集代替告警：即，a3b ) j b 。 ( 3 ) 告警时序关系：时间相关联的告警信息，如果在一个时问范围内发生， 只涉及到一个被管理设备单元并且具有和时间相关的次序，关联的告警依赖于告 警发生时间顺序，使用t 表示时间顺序，告警a ，告警b 顺序发生时，则会发生 告警c 。表示为： a t b ) jc 。 ( 4 ) 告警过滤：由于一个故障涉及到多个告警产生，但告警信息可能是虚假 的，告警描述的不一定是真实的故障，虚假告警可以剔除，其描述公式为：如果 告警a 的p ( a ) 值不属于合法集合u ，则过滤掉告警a ： 彳，p _ m i n c o n f ) t h e nb e g i n ； 5 ) p r i n tt h er o l e “一lj ( 一一1 ) ，w i t hs u p p o r t = s u p p o r t ( 1 ) ，c o n f i d e n c e = c o n f ； 6 ) i f ( m - 1 1 ) t h e ng e n r u l e s ( 1 i ，一1 ) ； 7 ) e n d ； 8 ) e n d ； 以上给出的频繁项目集和规则生成算法，从理论上了解了数据挖掘技术是如 何应用到告警相关性规则当中的实现规则挖掘，接下来给出一个例子来说明。 3 2 3关联规则挖掘的应用实例 下面给出一个例子来进一步说明关联规则挖掘的经典算法的应用原理，如下 是一个告警样本事务数据库，看一下它的频繁项目集和规则的生成过程。 表3 - 1 样本事务数据库 t a b l e3 - 1s a m p l ed a t a b a s e t i di t e m s e t a ，b ，c ，d b ，c ，e a ，b ，c ，e b ，d ，e a ，b ，c ，d 频繁项目集的生成步骤如下： 1 ) l ，生成：生成候选集并通过数据库得到它们的支持数，c l = ( a ，3 ) ，( b ，5 ) ，( c ，4 ) ， ( d ，3 ) ，( e ，3 ) ) ；挑选m i n s u p _ c o u n t 2 的项目集成l - 频繁项目集l l = a ，b ，c ，d ，e ) 。 2 ) 厶生成：由厶生成2 候选集并通过扫描数据库得到它们的支持数 g = ( a b ，3 ) ，( a c ，3 ) ，( a d ，2 ) ，( a e ，1 ) ，( b c ，4 ) ，( b d ，3 ) ，( b e ，3 ) ，( c d ，2 ) ，( c e ，2 ) ，( d e ，1 ) ) ；挑选 m i n s u pc o u n t 2 的项目集组成2 频繁项目集l 2 = a b ，a c ，a d ，b c ，b d ，b e ，c d ，c e 。 3 ) 厶生成：有，生成3 候选集并通过扫描数据库得到它们的支持数 1 8 数据挖掘中关联规则挖掘理论和算法研究 c 3 = ( ( a b c ，3 ) ，( a b d ，2 ) ，( a c d ，2 ) ，( b c d ，2 ) ，( b c e ，2 ) ) ；挑选m i n s u pc o u n t 3 的项目集 组成3 一频繁项目集l ，= a b c ，a b d ，a c d ，b c d ，b c e 。 4 ) l 。生成：由厶生成4 ，候选集并通过扫描数据库得到它们的支持数 c 4 = ( a b c d ，2 ) ) ；挑选m i n s u p _ c o u n t 4 的项目集组成4 频繁项目集4 = a b c d 。 5 ) 厶生成：由厶生成5 候选集g = ，厶= ，算法停止。 因此可以得到最大频繁项目集为 a b c d ，b c e ) 。利用最大频繁项目集生成的部 分规则如下表： 表3 - 2 关联规则生成过程表 t a b l e3 - 2m i n i n gp r o c e s so f c o r r e l a t i o nr u l et a b l e 壁呈生血= !里竺里堑璺竺! ! 璺竺2 里竺璺塑型! 垄查墨塑塑型1 1a b c d a b c6 7 4 0 a b c = ，d ( 是) 2a b c da b6740 a b j c d ( 是) 3a b c da6740 a j b c d ( 是) 4a b c db4 0 4 0 b a c d ( 否) ； ； ； ； ； 1 7b c ec5040c j b e ( 否) 1 8b c eb e6740 b e c ( 是) 1 9 b c ee6740 e j b c ( 是) 2 0b c ec e1 0 0 4 0 c e j b ( 是) 生成关联规则的一些相关定理表明，我们只需要从所有最大频繁项目集出发 来寻找可能的关联规则即可，就可以挖掘出满足需要的告警关联规则。 3 3关联规则算法改进分析 3 3 1分割和采样关联规则挖掘 经典a p r i o r i 算法在效率问题上，出现了系列的改进算法【1 0 】【l i 】f l2 1 。在遵循 a p r i o r i 基本理论的基础上，引入了一些技术像数据分割和抽样等，在一定程度上 改善了a p r i o d 算法效率。 1 ) 基于数据分割的挖掘算法 基本思想：首先把大容量数据库从逻辑上分成几个互不相交的块，每块应用 1 9 北京交通大学硕士学位论文 数据挖掘算法及a p f i o f i 算法生成局部的频繁项目集，然后把这些局部的频繁项目 集作为候选的全局频繁项目集，通过测试它们的支持度来得到最终的全局频繁项 目集。 优点：一方面表现为：合理利用主存空问，大容量数据一次性导入内存，这 样一些算法必须支持较大的f o 代价。数据分割分块内数据为一次性导入内存提供 了机会，因而可以提高对大容量数据集的挖掘效率。另一方面表现为：支持并行 挖掘，由于引入数据分割技术，每个分块的局部频繁项目集是独立生成的，这样 可以把块内的局部频繁项目集的生成工作分配给不同的处理器完成。 还有一种是基于散列的挖掘算法，它的基本思想是把扫描的项目放到不同的 h a s h 桶中，每对项目最多只可能在一个特定的桶中，这样可以对每个桶中的项目 子集进行测试，减少了候选集生成的代价，通过此种方式扩展到任何的k 频繁项 目集生成上。 优点在于：由于实验表明频繁项目集的主要计算是在生成2 频繁项目集厶 上，引入散列技术改进了产生2 频繁项目集的方法。 2 ) 基于采样的数据挖掘算法 基本思想：先使用数据库的抽样数据得到一些可能成立的规则，然后利用数 据库的剩余部分验证这些规则的正确性。 优缺点表现为：关联规则算法相当简单，可以显著地降低因为挖掘所付出的 f o 代价。问题在于，抽样数据的选取而产生的结果偏差过大，存在数据扭曲的问 题。但是如果使用适当可以得在满足一定精度程度下提高挖掘效率。 以上给出了提高规则挖掘算法的效率的一些方法，在一些程度上，引入上面 的思想方便算法的工程实现需要。 3 3 2约束关联规则挖掘 下面介绍改善关联规则挖掘质量的方法，在数据挖掘和知识发现中使用约束 可己提高挖掘的精度。约束在数据挖掘中的关键作用表现为： 1 ) 聚焦挖掘任务，提高挖掘效率 实验表明简单的挖掘工具很难取得预期的效果。利用约束，可以把具体的挖 掘任务转换成对工作的控制，从而使挖掘上作按着预期的方向发展。约束可以使 用在知识发现的任何阶段进行，通过人机交互，可以快速聚焦挖掘任务，进而提 高挖掘效率。 2 ) 保证挖掘的精确度 数据挖掘本身是一个不可预测的工作，很难将问题考虑周全。需要作不断的 数据挖掘中关联规则挖掘理论和算法研究 改进。有些知识是正确的，但是未必是感兴趣的。挖掘结果的精确性，不仅体现 在可信程度上，而且决定于它是否对我们有用。约束的使用可以帮助发现问题， 并及时的调整，使发现的各个阶段按着正确的方向发展。 3 ) 控制系统的使用模式 在数据挖掘的过程中，最常犯的错误就是无限制地扩大规模。约束数据挖掘 的思想为系统的增量式扩充提供条件。当基本的原则和目标确定后，可以把一些 优化和有待验证的问题以约束参数形式交互式输入，通过试验找到最佳值。在数 据预处理阶段，可以通过设置与任务相关的数据选择约束，数据过滤条件等，保 证数据质量的前提下，尽量减少数据规模。 不同类型的约束条件，可以帮助解决特定的问题。弄清一个约束的类型，可 以帮助更好的使用约束。因此接下来我们介绍一下时问约束对于关联规则挖掘的 影响。 对于约束关联规则的挖掘，目前的研究和时间大多数集中在某种形态的约束 和特定问题上。时间是现实世界的重要属性，大容量数据中的时间属性对用户来 说是很重要的。用户往往关注的是某一时间区域的数据而不是整个数据，而特定 时间区域的数据又可能导致特定的数据间的关联规则。时态约束可以很好的应用 到数据挖掘的规则发现中，并且可以起到很好的过滤过时数据，聚焦用户目标以 及加速形成关联规则生成等作用。 主要应用到的对象是对含有时态区间属性的事务数据库进行相关性研究。也 就是说数据库表中至少包括事务号，时态区间和项目集三个阶段。这罩的时态区 间反映了对应的项目集发生或被收集的时间范围。 首先从时态区问隔空间的代数形式化丌始，定义两个基本时念区问操作。然 后把他们应用到数据库的过滤和时态区间的合并等预处理工作上。做这些工作的 主要目的有两个：其一是通过对数据库的过滤减少数据集的容量；其二是通过时 态区间合并使过滤后可能生成的时态区间碎片合并成互不相交的挖掘时区集，并 对每个挖掘时区单独通过内存演算来生成关联规则。这样就可以大幅度减少进入 内存的数据集的大小，进而增加处理大型数据库的能力。也就是晚，关联规则挖 掘可以利用时态约束来进行预处理等工作，可以过滤掉用户不关心的时段上的数 据。过滤数据库以减少扫描空i 日j ，是降低输入输出代价，减少内存需求进而提高 挖掘效率的关键。 对大型数据库而言，利用约束条件过滤数据库是减少i o 代价和提高主机效率 的重要途径。对事务数据库进行过滤和挖掘时区合并等预处理，以使挖掘过程集 中在较小的用户感兴趣的数据上，可以提高挖掘效率和增强对大型数据库挖掘的 能力。 2 l 北京交通大学硕+ 学位论文 利用时态约束对数据库进行过滤等预处理，便于支持度的计算，使得被挖掘 数据的质量得到改善。进一步的工作是通过合适的算法生成频繁项目集和关联规 则，这些规则可以和确定的时态区间联系起来，使关联规则正确地反映特定时间 段的项目之间的联系。 3 4关联规则挖掘算法的设计分析 3 4 1关联规则挖掘算法设计分析 a p r i o r i 作为经典的频繁项目集生成算法，在规则挖掘算法中的作用举足轻重。 在对其进行深入研究后，会发现这样一些缺点，表现在以下几方面：一方面，多 次的扫描事务数据库，需要很大的i o 负载；另一方面，可能产生庞大的候选集； 再则，生成一些不必要的规则。 根据以上给出的缺点，我们应该给出一些方法来解决或者是优化算法【9 】【2 6 】【2 8 】， 使它在时间上，效率和质量等方面有所提高。其中，改善关联规则的挖掘质量是 一件很困难的工作。必须采用事先预防，过程控制以及事后评估等多种方法。一 种合适的机制就是让用户主动参与到挖掘工作中来，也就是说可以在用户主观和 系统客观两个层面上考虑关联规则挖掘的质量问题。 在常规的数据挖掘中，很多关联规则挖掘算法都是以数据库中各项记录是平 等的，其属性具有相同的权值为前提的，而通信网络中的告警数据由很多属性组 成，一些属性具有不同的级别。因此告警的不同属性和不同级别就意味着进行关 联规则挖掘的时候不能将各项告警记录之间的关系看作是平等的。这时我们就需 要引入加权【1 3 】【1 4 】【1 5 】的观念来突显属性之间的相关性和强调彼此之间的轻重。综合 考虑影响告警属性的各种属性，为告警信息分配一个权值是必要的。告警权值直 观地反映告警之间的相对重要程度，科学的确定权值对加权关联规则挖掘和告警 相关性分析都有着及其重要的影响。如果单凭网管人员的经验和主观判断来确定 权值，其主观因素太重，缺乏科学依据，而且当影响告警权值的因素很多时，这 样确定的权值很难体现出不同因素组合的差别，其合理性也值的商榷。科学的确 定告警权值是目f j 玎通信告警相关性分析的一个罩要研究方向。本文中用于确定告 警权值的方法是层次分析、法【1 6 】，它可以将定性问题定量化为权值的确定提供了有 力的理论背景和科学依据。 如第二节所述关联规则挖掘普遍使用“支持度可信度”度量机制。一般地讲， 不加额外的限制条件会产生大量的规则。这些规则并不是对用户都是有用或感兴 趣的。衡量关联规则挖掘结果的有效性应该从多种综合角度来考虑，像准确性， 数据挖掘中关联规则挖掘理论和算法研究 实用性，新颖性，使发觉的规则是反映数据的实际情况，是简洁可用的，为用户 提供新的有价值的信息。因此引入序列模式的时间跨度约束，以数组的方式记录 序列的起始时间和持续时间，这种数据组织方式方便支持度的计算，优势表现为 数据库扫描次数少，计算量小。 针对引入加权和时序约束的思想，接下来我们来介绍一下需要用到的技术和相 关理论。 3 4 2层次分析法 层次分析法1 1 7 】【1 8 】于7 0 年代提出，8 0 年代初引入我国，已得到广泛的应用。 层次分析法是一种解决多目标，多指标复杂问题的定性与定量相结合的决策分析 方法。层次分析法根据经验判断各衡量目标能否实现的标准之间的相对重要程度， 并合理地给出每个决策的每个标准的权数，利用权数求出各方案的优劣次序。 1 ) 层次分析法的原理 层次分析是将复杂问题分解为若干层，在最低层通过两两对比得出各因素的 权重，通过由低到高的层次分析计算，最后计算出各方案对总目标的权数，权数 最大方案即为最优方案。求最优方案的过程实质就是进行比较，通过比较做出选， 择。但对于缺乏公度性的多目标决策问题来说，唯一可行的办法就是进行两两比 较，通过将两两比较后的结果填入判断矩阵，求解判断矩阵的特征值和特征向量， 然后确定目标重要性的加权值。 2 ) 层次分析法的解题原理步骤 ( 一) 建立层次结构模型： 建立层次模型，首先要对所解决问题有明确的认识，弄清它涉及哪些因素，如 目标，准则，方案等，其次将评价问题层次化，将决策问题划分为若干层次，第 一层为总目标层，即要想达到的目标；中间层常为标准层，准则层等；最低层一 般是解决方案，称为方案层。在下文中n 为准则即原始指标个数，m 为方案即评 价对象的个数，且见层次结构模型的示意图3 1 ： 北京交通大学硕士学位论文 图3 - l 层次结构模型 f i g u r e3 - 1m o d e lo f a h p ( 二) 构造判断矩阵 建立层次模型后，可以在各层次元素中进行两两比较，判断其相对重要性， 构造出判断矩阵。判断矩阵是定性过度到定量的重要环节。设彬表示反映第i 个方 案对于某个最低层目标的优越性或某层第i 个目标对于上层某一目标的重要性权 重，以每两个方案的相对重要性为元素的矩阵称为判断矩阵。 设口矿= 形，则判断矩阵的元素具有如下性质： ( 1 ) a 茚= 1 ； ( 2 ) a l ，= 1 a 一； ( 3 ) a = a 让a 砖。 判断矩阵如下： a = 彬彬彬 彬呒 彤睨 ； 岷呒睨 彬 判断矩阵爿中元素口 可以利用决策者的知识和经验估计出来，由于决策者的 估计并不是很精确，因此第三条性质不一定成立。判断矩阵的标度及其含义见 表3 3 ： 数据挖掘中关联规则挖掘理论和算法研究 表3 3 判断矩阵的标度及其含义表 t 拍1 e3 - 3s c a l ea n dm e a n i n go fd e t e r m i n em a t r i xt a b l e 标度口， 含义( 两个目标相对重要性比较) l i 因素与j 因素相比，同样重要 3 i 因素与j 因素相比，略微重要 5 i 因素与i 冈素相比，明显重要 7 i 因素与j 因素相比，非常重要 9 i 因素与j 因素相比，绝对重要 2 ，4 ，6 ，8 为以上两判断之间中间状态对应的标度值 倒数 若因素与冈素比较，得到的判断值为口。= 1 口。 ( 三) 层次单排序及一致性检验 层次单排序是通过求解判断矩阵的特征值和特征向量，对本层次的所有因素 相对于上一层次而言的重要性进行排序，即对判断矩阵彳，计算满足下式的特征。 值与特征向量： a w = m 。矿 ( 2 - 1 ) 式中兄一为a 的最大特征值；w 为对应于五峨的正规化特征向量，i , v 的分量形 即是相应因素的单排序的权值。计算判断矩阵的最大特征值旯。及其相对应的特征 向量矿，从而确定权重形，可以有多种方法。下面我们将介绍一种算法的步骤： 1 将判断矩阵每一列正规化 五扩：口口窆口舻 ( f ，：1 ，2 ，刀) ( 2 2 ) k = l 2 是将每一列j 下规化的判断矩阵按行相加 莎产窆云 ，( f ：l ，2 ，疗) ( 2 3 ) i = 1 3 将向量= ( l ，2 ，。) tj 下规化 = 谚窆矿，