（电路与系统专业论文）基于序列模式挖掘的告警相关性研究.pdf

摘要 告警相关性问题的关键是提取相关性规则，本文在采用时序模式挖掘方法提敬告 警相关性规则方面作了一些探索性工作，创新点体现在： 1 时序模式挖掘研究方面 提出了单序列时序模式挖掘问题较完备的数学模型，在模型中引入了两类约束条件： 时间跨度约束和项属性约束。 提出了引入时间跨度约束的时序模式挖掘的f s p t m 算法，该算法提出了方便支持度 计算的数据存储结构和计算操作，提高了算法效率。 首次提出了从优化角度入手研究序列模式挖掘问题的新思路，提出拱卡最优极大模式 发现有意义序列模式的新思想，提出了最优极大序列模式与相容序列模式的概念与思想， 构造了确定最优极大序列模式的g a 算法与确定频繁相容模式的o p m 算法。算法的特点 在十降低了噪音数据的影响得到的频繁序列模式是相容的，且需要确认的序列模式个 数要远小于a p r i o r i 类算法需要判定的序列模式个数。 2 告警相关性研究方面 提出了告警时序模型，提出了考虑告警时问跨度约束的告警时序模式挖掘问题的模 型。提出的f s p t m 算法能够高效的从大量的告警集合中发现柏关性规则，o p m 算法在 很大程度上滤除噪音数据的影响，剔除了大量无意义的告警模式。 提出了引入网络拓扑约束的告警相关性i 口j 题的一种新的研究思路。定义了描述网络拓 扑关系的网元相连关系矩阵，提出了引入告警时间跨度约束和网j e 相连关系约束的告警 序列模式挖掘问题的模型，从而剔除了不相关网元告警对告警序列的影响，根据网络配 置模型构造的关系矩阵体现了网络结构的变化。提出的t c a s m 算法缩小1 r 告警相关性 规划集的规模，挖掘出的规则实时性强、业务意义明显。 此外，本文还系统的分析了目前告警相关性领域所采月】的主要研究方法和实际系统的 席刚状况。概述了时序模式挖掘领域的研究进展，分析了用时序模式挖掘方法提取告警 丰日关性规则的研究和应用状况。 最后，以“四川网络安全预警系统”为例，阐述了项目开发的设计思想和实现技术 总结了作者在数据仓库项目开发上的经验。 关键词：告警相关性，时序模式，关联规则，数据挖掘 a b s t r a c t e x t r a c t i n gc o r r e l a t i o nr u l e si st h ek e yp r o b l e mo fa l a r mc o r r e l a t i o n t h i sd i s s e r t a t i o n u s e st h em e t h o do fs e q u e n t i a lp a t t e r n sm i n i n gt oe x t r a c tc o r r e l a t i o nr u l e s ，a n dt h em a i n r e s u l t si n c l u d e da r es u m m a r i z e da sf o l l o w s i nt h ea s p e c to fs e q u e n t i a lp a t t e r nm i n i n g ，t h i sd i s s e r t a t i o nc r e a t e sam a t h e m a t i c a l m o d e lf o rs e q u e n c ep a t t e r nm i n i n gp r o b l e mo f s i n g l es e q u e n c e ，w h i c hi n c l u d e st w ok i n d s o f c o n s t r a i n t s ，t i m es p a na n di t e ma t t r i b u t ec o n s t r a i n t s w ep r e s e n tf s p t m ，a na l g o r i t h m f o rf a s td i s c o v e r yo f s e q u e n t i a lp a t t e r n s ，u s i n gas p e c i a ls t r u c t u r et or e c o r ds e q u e n t i a lt i m e a n du s i n gas i m p l ec o m p a r eo p e r a t i o n f s p t md e c r e a s ed a t a b a s e ss c a n s ，a n di n c r e a s et h e c o m p u t i n ge f f i c i e n c y f u r t h e r m o r e ，an e w i d e af o rd i s c o v e r yo f s e q u e n t i a lp a t t e r n si sp r e s e n t e d ，w h i c hb a s e s o no p t i m a lm a x i m u ms e q u e n t i a l p a t t e r nt od i s c o v e r yt h em e a n i n gs e q u e n t i a lp a t t e r n s d e v e l o pt h ed e f i n i t i o no fo p t i m a lm a x i m u ms e q u e n t i a lp a t t e r na n dc o n s i s t e n ts e q u e n t i a l p a t t e m ，c r e a t e t h em a t h e m a t i cm o d e lo f s o l v i n go p t i m a lm a x i m u ms e q u e n t i a lp a t t e r n ，a n d p r o p o s eg aa l g o r i t h mt os o l v eo p t i r e a lm a x i m u ms e q u e n t i a lp a t t e r n ，a n do p m a l g o r i t h m t od i s c o v e r yc o n s i s t e n ts e q u e n t i a lp a t t e r n t h ea l g o r i t h md e c r e a s e st h ei n f l u e n c eo fn o i s e d a t a ，g e t sc o n s i s t e n tf r e q u e n ts e q u e n t i mp a t t e r n ，a n dv a l i d a t e sl e s sc a n d i d a t es e q u e n t i a l p a t t e r n s t h a n a p f i o r ia l g o r i t h m i nt h ea s p e c to f a l a r mc o r r e l a t i o n ，w ec r e a t eas e q u e n t i a lm o d e lo f a t a r m s e q u e n c e ，a n d p r o p o s e am o d e lw i t ha l a r mt i m es p a ne o n s t r a i n tf o rd i s c o v e r yo fa l a r mc o r r e l a t i o nr u l e s p r o p o s et h ef s p t ma l g o r i t h m w h i c hf i n d sa s s o c i a t i o nr u l e sf r o ml a r g ea m o u n to fa l a r m s e f f i c i e n t l y i ng r e a tm e a s u r e ，t h eo p m d e c r e a s et h ei n f l u e n c eo fn o i s ed a t a ，g e tr i do f m a n y m e a n i n g l e s s a l a r m p a t t e r n s an e wr e s e a r c h i n gi d e ai s p r o p o s e di n a l a r ma s s o c i a t i o nw i t l ln e t w o r kt o p o l o g i c a l r e l a t i o n d e v i c ec o n n e c t e d r e l a t i o n s h i pm a t r i xi sd e f i n e d ，t od e s c r i b i n gt o p o l o g i c a lr e l a t i o n c r e a t eam o d e lo fa l a r n l s e q u e n t i a lm i n i n gp r o b l e mw i t ha l a r mt i m es p a na n dd e v i c e c o n n e c t e dr e l a t i o n s h i pc o n s t r a i n s t h i sm o d e lr e f l e c t st h ec h a n g eo fn e t w o r ks t r u c t u r e ，a n d w e e d st h ej n f l u e n c eo fd e v i c ed e t a c h e dr e l a t i o n p r e s e n tt c a s ma l g o r i t h m w h i c h d e c r e a s et i l ec o r r e l a t i o nr u l es e t a n dg e tc o r r e l a t i o nr u l e sw i t hm o r er e a lt i m ea n dm o r e m e a n i n g a d d i t i o n a l l y , w ep r o v i d e a p a n o r a m i cv i e w o fa l a r mc o r r e l a t i o ni nt e l e c o m m u n i c a t i o n s n e t w o r k ，t h r o u g ht h eg a t h e r i n go ft h em a i na p p r o a c h e se x i s t i n gi nl i t e r a t u r e ，o u t l i n et h e d e v e l o p m e n t o f r e s e a r c h i n g i n s e q u e n t i a lp a t t e r nm i n i n g ，a n da n a l y z e t h e m e t h o d s ， a l g o r i t h m sa n ds y s t e m u t i l i z e di ne x t r a c t i n ga s s o c i a t i o nr u l e sw i t 1t h em e t h o do f s e q u e n t i a l p a t t e r nm i n i n g d e s c r i b eap r o j e c tn a m e d s i c h a nn e t w o r ks e c u r i t ye a r l yw a r n i n gs y s t e m i n t r o d u c e t h ed e s i g np r o j e c ta n dr e a l i z a t i o nt e c h n i q u e ，s u m m a r i z et h ee x p e r i e n c eo f d e v e l o p i n gd a t a w a r e h o u s ep r o j e c t k e y w o r d s ：a l a r mc o r r e l a t i o n ，s e q u e n t i a lp a t t e r n ，a s s o c i a t i o nr u l e ，d a t am i n i n g i l 第一蘸绪论 第一章绪论 1 1 问题的研究意义 为了提供快速、可靠、有竞争力的服务，通信网络管理系统要适应删络规模扩张、 带宽提高、复杂性增强的变化。随着网络结构规模f i 益复杂，刚络故障管理越来越困 难。网络故障不仅会降低客户的满意度，也会导致经济损失。故障的发生在所难免， 快速检测和定位故障是保障网络稳定运行的关键因素，也是网络管理的茸要任务。 故障是网络设备硬件、软件模块的异常状态，网络或设备检测到故障，发出描述 故障现象的消息称为告警，它是从网络设备角度对故障的一个描述。组成网络的设备 ( 组成设备的模块) 是相互影响的，一个设备发生异常，相关设备会表现出故障征兆， 导致每一个相关设备都发出告警信息，这种现象称为故障的传播特性。在大的通信网 中，个故障产生很多告警，当若干故障并存时，产生大量的告警，这些告蟹隐藏了 故障的原因，以至难以进行故障诊断和定位，这是当今网络故障管理的一个难题。 网络维护人员感兴趣的不是告警事件本身，而是引起告警的设备故障。尽管这些 告警矗接或间接的反映故障现象，但大量的告警事件形成告警风暴，使迅速、准确定 位故障变得很困难。借助告警相关性处理大量的告警，识别告警之删的关系，用概括 的或高层的信息解释故障产生的告警序列，为故障诊断和定位提供有效的帮助。 i t u t 定义了网络管理的五个管理功能：故障、配置、性能、记赞、安全 i t u t _ 1 9 9 2 i ，告警相关性可以广泛应用到这些管理功能中。就目前的研究和应用看，告警 相关性在故障管理领域应用最为广泛，它是告警相关性最基本，也是最重要的应用。 在故障管理领域，通过分析告警事件之间的相关性，一方面，将多个告警归结成较少 的告警，过滤大量的冗余告警，另一方面，用于实时故障诊断和故障定位。可见，告 警相关性可以辅助网络管理人员过滤冗余信息，准确的定位故障，及时排除故障，保 障网络可靠的运行。 1 2 1 问题描述 1 2 告警相关性问题 相关性描述两个或多个实体之间有相互关系。具有相关性的实体可以分为组或 看作一个独立单元，因此，相关性分析产生两个结果：1 增加信息语义上的内容， 2 单元总量减少。告警相关性是对具有一定关系的多个告警的解释，目的是增加信 息语义的内容并且缩减消息集 m k 9 9 1 。j a k o b s e na n dw e i s s m a n 给出类似的定义，告 警相关性是从概念上解释多个告警，给多个告警赋以新的含义【j w 9 3 。 博j ：后 l 站撒告 告警相关性在网络故障管理中起到举足轻重的作h ，具体表现在： 1 删除冗余的告警信息。 2 过滤告警，当高层告警发生时，过滤掉低层高警。 3 信息转换，把告警或告警集转换成新的信息。 4 实时故障诊断和故障定位。 5 预测网络行为。 在通信网巾，建立作为同一故障的结果或条件的告警关联，删除和过滤冗余告警信 息，以减少操作维护人员接受的告警量，同时，提供概括的信息可以辅助维护者定位故 障源。嵌入告警相关性的故障管理系统可以在没有领域专家知识的前提下确定问题的原 因，采取正确的行动并且自动发出维护请求，告警相关性还可以预测网络行为、辅助网 络配置。 1 2 2 问题的难度 告警相关性问题的关键是提取相关性规则，提取相关性规则问题是n p 完金问题， 对该问题不存在多项式的解，只能采取启发式方法获得问题的近似解。而且，相关性 问题解决的程度依赖于对网络信息的掌握程度，如：当故障发生时被管网的配置信息 以及在配- 冒信息中故障组件对相邻组件的影响。告警相关性分析可能需要其他的信 息，如：故障测试的结果，来自网络维护人员的经验等。g s m 网络是由多个设备厂 家提供的异构网络，网络结构复杂多变。增加了获取上述信息的难度，这些因素成为 实现商业化告警相关性系统所面临的主要障碍，事实上，在已有的一些系统中，很少 的系统实际应用在集成的g s m 网络管理系统上。 问题本身固有的复杂性、求解的难度、信息的不完备都增加了告警相关性问题处 理难度，此外，告警信息固有特点，网络的复杂依赖关系又增加了求解的难度。 噪音，包含无意义的信息。冗余的信息，偶然的峰值、重复发生等。 隐含关系，告警相关性分析通常需要网络结构模型，简化的网络模型，使些发 生在隐含网元上的故障，可能被转嫁到其他的网元上。 复杂关系，相关性分析采用的网络模型通常假定，当一个组件发生故障时，所有 相关的组件都发出告警，这种假定不常成立。 数据缺失，相关性分析假定，获取网元发出的所有告警信息，但可能山于传输链 路的故障使一些信息丢失 m e i r a 9 7 1 。 问题的难度和复杂的应用环境并没有使研究者望而却步，研究者提出很多处理告 警相关性问题的方法和系统，下面分类研究了几类主要的方法和系统，并进行比较分 析。 2 第一蘸绪论 1 3 研究现状、存在的问题 1 3 1 模型研究 模型是对问题的抽象，告警相关性问题建模方砸的研究可归纳为二个方向：基寸 序列分析的建模，基于贝叶斯网络建模网络结构模型。 13 11 基于序列分析的建模 g w 9 5 1 提出了满足最小发生时间约束的事件序列的模型，采用二元谓词描述事 件之间的约束关系，二元谓词可以描述事件的多个属性之间的关系。i g l 0 提 b 了用布 尔表达式表示复杂的时序关系，事件的时间约束和其他属性的约束关系在模谨的条件 部分给出，该模型可描述较复杂的时序关系，但算法设计复杂。目前尚缺少对序列模 式挖掘问题较完整的模型描述。 1 3 1 2 基于贝叶斯网络建模 从严格意义来讲，我们所研究的具有相关性的告警集合包含错误信息、不完整信 息、延迟的信息或缺失信息，产生这种情况可能源于以下原因：发出故障的被管网元 自身的原因、网络传输延迟、传输故障、管理网自身原因等。此外，从相关性分析角 度，多个故障同时发生时产生的告警模式是一种不确定性模式。因此，不确定性是告 警相关性系统固有的属性。由于贝叶斯网络是处理不确定性问题的有效方法，有签于 此，出现一些基于贝叶斯网络对告警相关性问题建模的方法。f d l w 9 3 通过贝叶斯信 念网络对光纤网络的故障进行分析；f r s 9 7 利用信念网络构建告警相关性的模型。贝 叶斯网络的优点是有效处理不完整和带有噪声的数据，但建造贝叶斯网络模型是一个 复杂的任务，需要知识工程师和领域专家的参与，在实际中需要反复修f 而不断完善。 13 1 3 网络结构模型 从管理网络的角度，网元层采用层次结构的概念模型，层次关系体现了网元之间 信息传递和控制关系。f m m 9 8 ，a g s 0 1 ，b l b w 9 9 专注于用网络分层模型进行告警相 关性分析，m a l h e i r o s 和m a r c o s m m 9 8 提出一个将网络予网分层的电信网络模型，并 用非循环的有向图表示网络模型，用来分析告警相关性。a p p l e b y 等人 a g s o i 针对 多层故障分析，设计了命名为y e m a n j a 的告警相关性系统，y e m a n j a 系统使用实体模 型来封装设备和系统的概念层。b a r r o s 等人 b l b w 9 9 提出基于网络配置模型的诊断 方法。采用配置模型不适合结构经常变化的网络，网元的分层概念模型很好的体现了 网元之间管理域关系，但不能完整的表述告警传播关系。 基于告警相关性的网络结构模型从领域知识的角度，对告警集合中相关告警作了 约束，合适的模型能够方便的找出告警相关性规则、便于故障定位。因此，从告警相 关性角度建立合适的网络结构模型是必要的。 博 + 后 i i 站 f 告 1 3 2 方法研究 目前告警相关性问题的研究方法可分为四类：1 基于专家经验的方法，2 基 j 模型的方法，3 神经网络的方法，4 数据挖掘的方法。下面分别介绍这四类方法的 研究进展及应用中存在的问题： 1 ，3 2 1 基于专家经验的方法 这类方法的特点是利用领域专家的经验 1 ) 基于规则的方法( r u i eb a s e dr e a s o n i n g ，r b r ) 基于规则的推理方法将特定领域知识归纳为一组规则，通常从故障清单或从专家 经验中提取描述系统告警行为的规则【c d m t 8 8 】。规则存储在知识库中，形如：i f c o n d i t i o naa n dn o tc o n d i t i o nbt h e na c t i o nc ，每条规则包含控制逻辑，决定条件满足 时，系统所采取的行为，这种机制称为推理机。 基于) i 9 | l 则的方法的优点是它符合人的思维，便于理解。缺点在于规则中隐含了系 统结构、行为和设备功能的描述，因此，系统结构、行为发生变化，规则就需要调整： 舰则的获取和维护都比较困难，使得基于规则的系统适应性较差【w z h 8 8 ，y k s 8 9 ； 系统在推理过程中无法利用过去的经验，即系统没有“记忆”。 2 ) 基于范例的方法( c a s eb a s e dr e a s o n i n g ，c 隙) 在基于范例的系统中，知识的基本单元是范例( c a s e ) ，过去发生的问题及其解决 力。案构成范例 s l a d e 9 1 】 w t m 9 5 。范例被存储、检索，并用来解决新问题，新问题及 其解决方案构成新的范例，存储在范例库中，这样系统就具有处理该类问题的能力。 f b h m i 提出用基于范例的方法在g s m 网络中进行故障检修。采集的告警和故障的处 理信息存储在故障清单中。当网络中发生故障时，系统在已经存在的故障清单中奄找， 如果范例库中存在当前故障的范例，把范例的知识提供给维护人员。当范例库中不存 在当前故障的范例，找出近似的范例，然后将该范例的解决方法应用到新问题，最后 将陔问题的解决方案加到范例集中。 基于范例的系统的优点是可以通过经验解决新问题，c b r 和范例库在故障诊断和 故障处理方面非常有效，但不是一种有效的处理告警相关性的方法。 3 ) 模糊逻辑( f u z z yl o g i c f l ) 被管网络复杂；故障和告警之间的因果关系不明确，同一故障在不同的情况下会 触发不同的告警；传输延迟和数据丢失会导致在一个时间段内没有接收到故障产生的 些告警信息；配鼍的频繁变化。由于上述原因，很难建立网络告警事件和故障( 给 定的告警集合标识某一设备故障) 的精确模型。 从专家那里获得的知识大多是模糊、不确定的，例如：“告警a 发生通常预示模 块b 的接口故障”，这种不精确的表述不能直接应用到基于规则的系统中。模糊逻辑 是处理不确定信息的有效方式，模糊逻辑的基本概念是模糊集，模糊集中任何一个元 素归属于某个集合的可能性是【o ，1 1 的值。文 a d 9 9 应用模糊逻辑确定告警相关性规 第一章绪论 则。 模糊逻辑是一种采用离散化的方式解决信息不确定的方法 z a d e h 8 8 i ，通常和其他 的方法共同解决复杂问题。 4 ) 贝叶斯网络方法( b a y e si a nn e t w o r k s ，b n ) 贝叶斯网络又被称为信念网络( b e l i f n e t w o r k s ) 或者因果网络( c a u s a ln e t w o r k s ) ， 是描述数据变量之间依赖关系的一种图形模式，是一种用米进行推理的模型 h m w 9 5 。贝叶斯网络为人们提供了一种方便的框架结构来表示因果关系，这使得 不确定性推理在逻辑上更为清晰、可理解性强。目前贝叶斯网络在故障诊断领域已有 成功应用。 一个贝叶斯网络是一个有向无 ( d i r e c t e da c y c l i cg r a p h ，d a g ) ，由节点及连接 这些节点的有向边构成。节点代表随机变量，节点闯的有向边代表r 节点问的相互关 系( 由父节点指向其后代节点) ，用条件概率表达关系的强度，没有父节点的用先验概 率表达 c h a r n i a k 9 1 p e a r l 9 1 。节点变量可以是任何问题的抽象，如故障的征兆和故障 原因等。 b n 的优点是有效处理不完整和带有噪声的数据，但建造贝叶斯网络模型是一个 复杂的任务。 1 3 2 2 基于模型的方法 1 ) 基于模型的方法( m o d e i b a s e dr e a s o nin g ，m b r ) 模型诊断的方法依赖于系统结构和功能模型渗断故障、预测网络的行为。在电信 网络中，系统结构模型是网络拓扑关系的描述，功能模型描述告警的传播特性和告警 相关，| 生 j w 9 5 1 。模型诊断的目标是识别故障设备，因此，模型要精确的考虑设备的所 有模块、及其状态和模块间的相豆关系，借助模型比较实际的告警模式，定位设备故 障 f r o h l i c h 9 8 f j n 9 7 。 m b r 方法的优点是可以较准确的定位故障、效率高，但该方法依赖于精确的设 备模型和网络拓扑关系，而由多个设备厂商的设备构建的复杂网络，建立设备模型和 故障传播模型比较困难，限制了m b r 方法的实用性。 2 ) 编码的方法( o o d e b o o km e t h o d o b ) 编码的方法是将可观测到的告警事件视为产生故障原因的一个编码，告警相关性 分析是对观测到的告警事件集进行解码，来确定故障的原因。描述故障的告警事件排 成一个向量，所有的告警向量建立编码集。当故障产生突发告警序列时，突发告警序 列和编码集比较，遁过计算当前的突发告警序列和编码集合中的故障编码向量的哈明 距离，确定故障为具有最小哈明距离的故障编码对应的故障 k y 9 5 。 编码方法要建立告警事件和故障对应的编码手煅，算法效率受编码手册大小的制 约，而且对于复杂的网络建立故障编码比较困难，因此，对于简单的网络c b 是一个 高效、鲁棒性好的方法，对于复杂的网络不建议使用c b 。 博七后出站报告 1323 神经网络的方法 人工神经网络是一个并行、分布处理结构，它由处理单元及其称为联接的无向信 号通道互连而成。这些处理单元( p r o c e s s i n ge l e m e n t ) 具有局部内存，并可以完成局 部操作。每个处理单元有一个单一的输出联接，这个输出可以根据需要被分支成若干 并行联接，且这些并行联接都输出相同的信号，即相应处理单元的信号，信号的大小 不凶分支的多少而变化 m k 9 4 】 w t j 9 7 】 w i e t g r e f e 。 应用人丁神经网络的优势：不需要专家知识训练神经网络，当网络配置变化，神 经网络的输入和输出层发生变化，需要根据告警数据训练新的故障模式。神经网络由 于自身良好的学习能力，即使输入数据包含噪音，也能较好的识别出相关性模式。神 经网络需要大量的训练，由于电信网络复杂多变，很难找到较好的训练数掘集，给实 际应用该方法带来困难。 1 32 4 数据挖掘的方法( d a t am i n i n g ) 数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据集中识别有效 的、新颖的、潜在有用的，以及最终可理解的模式的过程。它是一门涉及面很广的交 叉学科，包括机器学习、数理统计、神经网络、数据库、模式识别、粗糙集、模糊数 学等相关技术。 数据挖掘的过程包括三个步骤：数据准备、数据挖掘，以及结果的解释评估。根 据不i 司的目标，数据挖掘的任务分为如下几类：数据总结、分类或预测、数据聚类、 关联规则挖掘、序列模式挖掘等。 在】4 节集中介绍两类数据挖掘方法：关联规则、序列模式挖掘的研究进展，下 面对数据挖掘的几类方法作以简要介绍。 1 1 数据总结 数据总结是从数据集中提炼出概要的、浓缩的信息。传统的数据总结方法是对数 据库数值字段求和、求平均值、方差值等统计值，或者用直方图、饼状图等图形方式 表示。数据挖掘从数据泛化的角度实现数据总结。数据泛化是一种把数据库中的有关 数据从低层次抽象到高层次的过程。由于数据库中的数据或对象所包含的信息是最原 始、基本的信息( 这是为了不遗漏任何可能有用的数据信息) 。人们有时希望能从较 商层次的视图上处理或浏览数据，因此需要对数据进行不同层次上的泛化以适应各种 查询要求。数据泛化目前主要有两种技术，多维数据分析方法和面向属性的归纳方法。 应用数据总结的方法可以对告警数据进行简单的统计分析，可以和其他方法结合 进行告警相关性分析。 2 ) 分类 分类是构建个分类函数或分类模型( 也常常称作分类器) ，该模型能把数据库中 | e f 匀数据项映射到某一类别。分类和回归都可用于预测，和回归方法不同的是，分类的 输出是离散的类别值，而回归的输出则是连续数值 w k 9 1 。 6 第一章绪沦 3 ) 聚类 聚类是把一组个体按照相似性归成若干类别，即”物以类聚”。它的目的是使得属 于同一类别的个体之间的距离尽可能的小，而不同类别上的个体 i j 的距离尽可能的 人。 告警聚类的思想源自同一类故障的告警是摺似的，告警聚类按照告警的相似性进 行分类，并且假定这些告警有相同的原因 j u l is c h 。 4 ) 关联规则 设1 = ( f 1 ，i ：，a ， 是项的集合，其中的元素称为项( i t e m ) 。汜d 为交易 ( t r a n s a c t i o n ) t 的集合，这取交易r 是项的集合，并且t ，。对应每一个交易有唯一 的标识，如交易号，记作t i d 。设是，中项的一个集合，如果t ，那么称交易 丁包含并。 一个关联规则是形式x y 的蕴含式，这里x c ，y c ，并且搿n y ：m 。规则 x j y 在交易数据库d 中的支持度( s u p p o r t ) 是交易集合包含和y 的交易数与所 有交易数之比，记为s u p p o r t ( x 令y 1 ，即 s u p p o r t ( x = ，r ) = | 丁| u y 互t ，t d ) i 门d l 如果项集x ，有s u p p o r t ( x ) 大于用户给定的最小支持度，则称x 为频繁集或大 项集。 规则等y 在交易集中的可信度( c o n f i d e n c e ) 是指包含和y 的交易数与包含x 的交易数之比，记为c o n f i d e n c e ( z y ) ，即 c o n f i d e n c e ( x j y ) = | r f x u y 互t ，t d l l r ：工t ，t d “ 给定一个交易集d ，挖掘关联规则问题就是产生支持度和置信度分别大于用户给 定的最小支持度( m i n s u p p ) 和最小置信度( m i n c o n f ) 的关联规则。关联规则挖掘的 经典算法是a p r i o r i 算法 a i s 9 3 b 】( a s 9 4 a 】 a s 9 4 b p c y 9 5 1 h f 9 5 t o i 9 6 。 关联规则的概念和算法框架是研究序列模式发现的基础。 5 ) 序列模式 关联规则挖掘项集之间蕴含的规则，构成项集的项的一个有序组合构成序列，在 关联规则所研究问题的基础上引入序约束，构成序列模式挖掘问题。 序列是项的有序组合，不失般性，我们把项集映射到连续自然数的集合，项集 i 表示为( ，f 2 ，a ，) ，其中为一个项。序列s 表示为( s 1s ：，a ，s 。) ，其中s ，是一个项。 博l 后h 站报告 个序列( q ，4 ：，a ，吒) 包含另一个序列( b l , b 。，a ，b 。) 如果存在自然数 i l f 2 a k ) ，扫 描数据库时不再需要它们。 f p 一增长算法，h a n 和f u1 9 9 5 提出，采取分治策略，将提供频繁项集的数据压 缩到一棵频繁模式树，但仍保留项集关联信息；然后，将这种压缩后的数据库分成一 组条件数据库，每个关联一个频繁项，并分别挖掘每个数据库。性能研究表明，f p 增长算法比a p d o n 算法快一个数量级 h f 9 5 1 。 1 4 2 序列模式挖掘 序列模式挖掘是数据挖掘领域一个重要的问题，最早由a g r a w a l a s 9 5 提出，目 前序列模式发现问题的研究集中在设计发现频繁模式的算法上，主要的算法分为三 类： a p f i o f i - l i k e 算法：以相联规则提取为理论基础，a g r a w a l 提出了序列模式发现问 题 a s 9 5 1 ，并给出了系列基于a p f i o f i 的算法 a s 9 5 s a 9 6 ，此外，文【m t v 9 5 】提 出了从单一序列中发现频繁序列的算法，文 m t 9 6 提出了m i n e p i 算法，电都是以 博i - 后出站报告 a p r i o r i 算法为框架，我们称这类算法为a p r i o r i l i k e 算法。它的基本思想是通过k 强 项集构造k + 1 候选项集，依据强项集的子集都是强项集的原则过滤k + l 候选项集， 然后扫描数据库得到k + 1 强项集，该类方法扫描数据库的次数多。 基于模式| i 缀的序列生长方法：围绕减少数据库扫描次数问题而发展的一类算 法，代表性算法p r e f i x s p a n p h m o i ，它的基本思想：扫描数据库发现频繁l 。序列模 式，把数据库投影到前缀序列库，重复序列发现和投影操作，任何一个频繁序列都可 以由它的频繁前缀生长得到。该类算法不需要生成候选项集，聚焦于小搜索空间，寻 找频繁模式的过程更有针对性且高效，映射后的序列库逐渐缩小，在实际情况中，映 射库缩小很快，因为只有很小一部分前缀会生长到长模式。主要代价在于构造映射库， 当频繁序列模式很多时，代价比较大，采用以空问换时间的策略。 基于问题细分的序列挖掘方法：代表算法是s p a d e 算法 z a k i 0 1 1 ，它的基本思想： 采用格子理论把原始问题分解为一些小规模的予问题，这些问题可以在内存中单独运 行。对于子格子，提出宽度和深度两种搜索策略。该算法采用数据序列的数据存储格 式，每一个序列存储它的时间信息，通过简单的时间连接计算支持度。该算法的效率 比6 s p 算法提高一个数量级。以该思想为基础发展的s p a mf a y r e s 0 2 算法，算法框架 与s p a d e 类似，支持度借助位图计算。该类算法无需多次扫描原始数据库，运用高 效的搜索方案，支持度的计算完全可以靠i d 1 i s t 得到。降低了计算代价，但需要存储 大量的由原始数据派生的中间数据。即采用以空间换时间的策略，该类方法内存消耗 火， 1 4 3 规则价值的衡量 当我们用数据挖掘方法得出一些结果之后，数据挖掘系统如何知道哪些规则对于 用户来说是有用的、有价值的。规则价值的衡量就是对规则的价值进行系统的、客观 的评价的理论和方法。这里有两个层面：用户主观的层面和系统客观的层面 w a n 9 0 3 1 。 下面分别予以说明： 1 4 3 1 系统客观层面 使用支持度一置信度框架对于很多应用是有用的。然而，支持度一置信度框架可 能产生误导，我们看下面的例子： 假定我们分析1 0 0 0 0 个涉及购买计算机游戏和录像的事务，数据显示6 0 0 0 个顾 客事务包含计算机游戏，7 5 0 0 个事务包含录像，4 0 0 0 个事务同时包含计舞机游戏和 录像。设m i n s u p 为3 0 ，r n i n c o n f 为6 0 ，发现这样的规则： b u y s ( 计算机游戏) jb u y s ( 录像) 【s u p p o r t = 4 0 ，c o n f i d e n c e 2 6 6 这条规则是一个强关联规则，然而该规则是一个误导，因为购买录像的可能性是7 5 ， 比6 6 还大。事实上，计算机软件和录像是负相关的，买其中一种实际上减少了买另 一种的可能性。 1 4 第一章结论 上面的例子表明了规则ajb 的置信度有一定的欺骗性，它只是给定a ，b 的条 件概率的估计，并不度量a 和b 之间蕴含的实际强度 h a n 0 2 。于是，人们引入了兴 趣度，用来修剪无趣的规则。一般来说，一条规则的兴趣度是存基于统计独立性假设 下真正强度与期望的强度之比。然而，在许多应用中已经发现，只要人们仍把支持度 作为最初项集产生的主要因素，那么要么把支持度设得足够低以使得不丢失任何有意 义的舰则，或者冒丢失一些重要规则的风险：对前一种情形计算效率是一个问题，而 后一种情形可能丢失从用户观点来看是有意义的j 3 l l 则。 针对此问题，s a 9 5 给出感兴趣规则的定义。除了利用兴趣度作为修剪无价值规 则的手段外，f b m u t 9 7 提出相联规则和蕴含规则。详细的讨论见文献 e m s 。 1 4 3 2 用户主观层面 上面的讨论只是基于系统方顽的考虑，一个规则的有用与否最终取决于用户的感 觉。只有用户可以决定规则的有效性、可行性。所以我们应浚将用户的需求和系统更 加紧密的结合起来，这样才能真正满足用户的需求。 同用户需求相结合的方法之是采用一种基于约束( c o n s t r a i n t b a s e d ) 的挖掘， 具体的约束有： 数据约束，用户可以指定对哪些数据进行挖掘，而不是全部的数据。 维、层次约束，用户指定对哪些维以及在这些维的那个层次上挖掘。 规则约束，用户指定哪些类型的规则是我们所需要的，k l e m e t t i n e n k m r 9 4 1 引入 规则模板的概念，用户使用它决定哪些规则是感兴趣的，哪些规则是不感兴趣的。 业务约束，建立业务模型可以有效的剪掉大量无意义的规则。在基于约束的挖掘 过程中，一些约束条件可以和算法紧密结合，从而提高算法效率和规则的可用性。 1 , 5 本文的研究工作 本文采用序列模式挖掘的方法进行告警相关性规则提取问题的研究。目前采用数 据挖掘方法提取告警相关性规则的算法都是以告警级别为研究对象研究不同级别告 警模式之间的相关性。我们认为，告警相关性分析的目标是故障分析，告警级别只是 反映故障的严重程度，并不包含体现故障原因的信息，为此，我们采用告警标题作为 研究对象，研究告警标题中蕴含的频繁模式能够更好的体现故障的传播特性和告警的 因果关系。 从告警序列中提取告警相关性规则问题是一个n p h a r d 问题，对复杂问题的求解 建立在简化模型的基础上，本文提出较完备的告警相关性时序模型，提出了单序列时 序模式挖掘问题的模型，在模型中引入了两类约束条件：时间跨度约束和网络拓扑约 束，使所分析的结果更真实的反映告警序列的内在特征。建模是后续算法设计的基础 工作。 以a p r i o r i 算法为框架的序列模式挖掘算法需要多次扫描数据库，算法效率低。 博士后出站报告 而本文提出的f s p t m 算法，采取以空间换取时间的策略，该算法用二元数组记录告警 序列的时间信息，减少了数据库的扫描次数，提高了支持度的计算效率。以某省四个 月的告警数据为例，分析了算法参数( 支持度、置信度和时f 日j 跨度) 对规则数最的影 响。 目前序列模式挖掘算法的特性决定了在取较小支持度、置信度和较大时间跨度的 情况下，挖掘出的频繁模式数量大，这些模式中包含了很多噪音模式，有意义和有趣 的模式淹没在其中，难以分辨，降低了序列模式挖掘算法的实用性。本文提出了序列 模式挖掘的新思路，从优化角度入手研究序列模式挖掘问题，引入了最优极大序列模 式及相容序列模式的概念，建立了求解最优极大序列模式的数学模型，并给出了求解 最优极大序列模式的算法。基于最优极大序列模式可确认出所有与之相容的频繁序列 模式。算法的特点在于降低了噪音数据的影响，得到的频繁序列模式是相容的，且需 要确认的序列模式个数要远小于a p r i o r i 类算法需要判定的序列模式个数。 告警相关性规则中体现故障的传播特性，故障的传播取决与网络结构模型，在序 列模式挖掘中引入网络结构模型，一方面可以剔除噪音数据的影响，提高算法效率， 另一方面，过滤噪音模式，使输出的相关规则更好的体现业务意义，为确定故障原因 提供帮助。为此，本文研究引入g s m 网络模型约束的告警相关性问题。首先，从告警 相关性管理角度，本文重新定义了管理对募之间的关系，把关系分为：连接关系、管 理关系、包含关系，分析这些关系对告警传播特性的影响，并把它们概括为网元之涮 的相连关系，定义了网元相连关系矩阵，构造了引入网元关系约束的序列模式挖掘模 型，从而剔除了不相关设备告警对告警序列的影响，根据网络配置模型构造的关系矩 阵体现了最新的网络结构，所发现的规则实时性强，关系矩阵全面的反映网络的拓扑 关系。本文提出了考虑上述约束的序列模式挖掘问题的模型和算法。 本文的工作思路源于作者参与开发的项目：“基于数据仓库的四川网络预警系 统”，该系统包括两大模块：o l a p 分析模块和数据挖掘模块。o l a p 分析模块提供了告 警和性能数据的多角度、多层次的钻取，数据的相关分析，告警和性能数据的预测； 在数据挖掘模块提供了告警和性能数据的关联分析、闽值分析。该系统帮助用户分析 网