（信号与信息处理专业论文）基于序列模式挖掘的网络告警关联.pdf

基于序列模式挖掘的网络告警关联 摘要 数据挖掘是从数据库或其他信息库的大量数据中挖掘出有效知 识的过程。它涉及多学科技术的集成，是当前的热点研究领域。现实 世界中的大量数据具有时间或顺序上的关联性，序列模式挖掘是指寻 找在某时间窗约束下，具有某种特征属性的告警事件产生，导致具备 另一种特征属性的告警事件将以某种概率在另一个时间窗内产生的 规则。 本文全面的探讨了序列模式挖掘问题，讨论了该领域的研究现 状、最新技术和进展，对序列模式挖掘的六大类算法进行了综合分析 和评估，提出了这六大类算法的优缺点和适用环境。 同时，作者对移动通信的网络告警关联进行了分析，提出了现有 移动通信网络告警数据挖掘方案的不足，给出了总体解决方案。结合 移动通信网络告警数据的网元数量多、告警数据数量大等特点，作者 创新性的将网络拓扑约束和序列模式挖掘的两个算法相结合，提出了 适用于移动通信网络告警关联的两个新算法。 作者和小组成员一起，开发了b u p t p r i s m i n e r 数据挖掘平台，将 序列模式挖掘的两种算法与数据挖掘平台整合，完成了算法改进、代 码编写、实现和测试对比，利用实验验证出通过网络拓扑约束，序列 模式挖掘算法的执行时间和效率大幅提升，有效提高了挖掘的速度和 精度。 关键词序列模式挖掘告警关联网络拓扑移动通信网络 n e t w o r ka l a r mc o r r e l a t i o nb a s e do ns e q u e n t i a lp a t t e r nm i n i n g a b s t r a c t d a t am i n i n gi st h ep r o c e d u r eo fe x t r a c t i n ga n dm i n i n gk n o w l e d g e f r o ml a r g ea m o u n to fd a t ai nd a t a b a s ea n do t h e ri n f o r m a t i o n r e p o s i t o r y i t i st h ei n t e g r a t i o no fm u l t i p l es u b j e c t so f t e c h n o l o g ya n di t so n eo ft h e h o t t e s tr e s e a r c ha r e a sc u r r e n t l y i nt h er e a lw o r l dw i t hl a r g ea m o u n t so f d a t ao nt h et i m i n go ro r d e ro fr e l e v a n t ，s e q u e n t i a l p a t t e r nm i n i n gi s l o o k i n gf o rac e r t a i nt i m ew i n d o wc o n s t r a i n t sw i t hs o m ea t t r i b u t e so f a l a r me v e n t sh a v el e do t h e ra t t r i b u t e sw i t ht h ei n c i d e n tw i l lb ew a r n i n gi n a n o t h e rp r o b a b i l i t yo fat i m ew i n d o ww i t h i nt h er u l e s t h i sp a p e rf i g u r e so u tac o m p r e h e n s i v es t u d yo nt h es e q u e n c e p a t t e r n ，d i s c u s s e st h er e s e a r c hi nt h ef i e l do ft h es t a t u s ，t h el a t e s t t e c h n o l o g ya n dp r o g r e s s ，a n a l y s e st h es i xt y p e so fm i n i n gs e q u e n t i a l p a t t e r n sa l g o r i t h m s ，w h i c h a l s or a i s e dt h e a l g o r i t h m s a d v a n t a g e s ， d i s a d v a n t a g e sa n da p p l i c a t i o ne n v i r o n m e n t m e a n w h i l e ，a u t h o ra n a l y z e dt h ee x i s t i n gc o m m u n i c a t i o nn e t w o r k a l a r md a t am i n i n ga n dg a v eu st h eo v e r a l ls o l u t i o n t h ea u t h o r i n n o v a t i v e l yc o m b i n e st h en e t w o r kt o p o l o g yc o n s t r a i n t sa n ds e q u e n t i a l p a t t e r nm i n i n gt om a k et w on e wa l g o r i t h m sw h i c ha r eb a s e do nt h el a r g e a m o u n to fn e t w o r ke l e m e n t sa n dd a t a i na d d i t i o n ，t h ea u t h o rd e v e l o p e db u p t p r i s m i n e rd a t am i n i n g p l a t f o r mw i t ht h et e a mm e m b e r sa n di n t e g r a t e dt h es e q u e n t i a lp a t t e r n m i n i n ga l g o r i t h m si n t ot h ep l a t f o r m ，a n dt h r o u g he x p e r i m e n t sp r o v et h a t ， w i t ht h en e t w o r kt o p o l o g yc o n s t r a i n t s ，t h es e q u e n c em i n i n ga l g o r i t h m s c o s tl e s st i m e ，e f f i c i e n c ys u b s t a n t i a l l yi m p r o v e dt h es p e e da n d a c c u r a c y k e y w o r d s ：s e q u e n t i a lp a t t e r nm i n i n g ，a l a r mc o r r e l a t i o n ，n e t w o r k t o p l o g y , c o m m u n i c a t i o nn e t w o r k 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：垄垂塑叠 日期：巡：堡：塑： 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。1 非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名氇蝉一一 导师签名：垂气卜 日期：避：! ：2 墨： 日期：避生：艺五： 基于序列模式挖掘的网络告警关联 1 1研究课题背景 第一章绪论 本课题依托于北京邮电大学模式识别与智能系统实验室和i b m 中国研究院 联合研究的项目基于数据挖掘的智能化移动通信网络故障管理关键技术研究。 基于数据挖掘的智能化移动通信网络故障管理关键技术研究的主要研究 内容是采用数据挖掘等创新方法和技术，进一步提高告警关联分析的速度和精 度，减少对人工专家知识的依赖，最终提高故障定位的准确性和效率，以研制出 一个适用于大规模移动通信网络和海量数据应用环境下的智能化实时故障诊断、 影响分析和故障定位系统。 具体的研究内容u 1 包括： 1 ) 实现大规模网络和大数据量应用环境下的智能化实时事件关联 2 ) 通过智能学习和数据挖掘，发现基础设施、网络业务和用户间的依赖关 系和根源故障分析 3 ) 通过序列模式挖掘寻找网络告警之间的关联关系 基于序列模式挖掘的网络告警关联正是在这一背景下提出的。电信公司 采用大量电信设备构筑了一个大型异构的网络，然后以移动通信网络作为支撑， 向不同类型的用户提供各种移动通信业务。在大的移动通信网中，一个故障产生 很多告警，当若干故障并存时，就产生了大量的告警，这些告警隐藏了故障的原 因，以至难以进行故障诊断和定位。尽管这些告警直接或间接的反映故障现象， 但大量的告警事件形成告警风暴，使迅速、准确定位故障变得很困难。在移动通 信网络中，很多告警具有时序特征，可以使用序列模式挖掘识别告警之间的关系。 序列挖掘模式算法主要分为两步，即发现频繁模式和生成规则。其中，发现 频繁序列模式是生成频繁序列的过程，基于拓扑约束的序列模式挖掘算法主要改 进也主要在这一步骤。由长度为k 1 的频繁序列生成k 候选序列后，对k 候选序 列先进行拓扑约束检查，剔除与拓扑约束不相容的序列，进而在剪枝阶段修剪掉 序列中不满足时间间隔约束的序列，保留既满足时间间隔约束又满足最小支持度 的序列，大幅度的提高了挖掘过程的时效性和序列模式的准确性。 1 2网络管理的概念和现状 1 _ 2 1 网络管理的概念 网络管理，是指网络管理员通过网络管理程序对网络上的资源进行集中化管 北京邮电大学硕士学位论文 理的操作，包括故障管理、配置管理、性能管理、计费管理和安全管理。一台设 备所支持的管理程度反映了该设备的可管理性及可操作性。 网络管理系统是一个复杂的系统，涉及电信技术和计算机技术等各个领域的 内容。目前用于网络管理的技术很多，新的网络管理技术也不断出现。常用的网 络管理技术有1 ：基于t m n 面向电信网的网络管理技术，基于c o r b a 面向网 管系统互联的网络管理技术，基于s n m p 面向数据网和计算机网的网络管理技 术，基于w 曲的网络管理技术等等。 1 2 2 移动通信网络管理的现状 目前我国各移动通信运营商都拥有一个规模宏大的电信网络，随着网络规模 的不断扩大，网上设备的种类和数量也不断地增加，整个网络的复杂性日益提高， 多厂商问题非常突出。由于各种网络和设备缺乏统一的接口标准和规范，给网管 系统的建设带来了很大的困难。 近几年来，各个移动通信运营商都陆续引进和自主开发了众多的网络管理系 统，并负责全国专业网管系统本地节点的维护管理。在网络管理的分层结构上， 有网元管理层( 如交换机集中监控系统) 、网络管理层( 如综合故障管理系统) 、 业务管理层( 如智能业务网管) 和事务管理层( 如运维作业管理系统) 。 然而，由于不同的开发商采用各自不同的技术自行研制且大多采用各自的管 理协议，不可避免地带来网络协议互不兼容、管理信息不能互通、缺乏对整个网 络的综合管理、管理内容庞杂、操作界面多样等问题。 针对上述移动通信网络管理的现状，各运营商都希望能够在目前网络管理系 统的基础上建立综合网管系统，以实现全网的综合管理。这就产生了综合网络管 理系统的需求，即把现有的独立存在的各专业网络系统综合成一个功能齐全、面 向未来的综合网络管理系统。综合网管系统通过一个网管工作站就能够对互连的 不同网络实施各种管理和控制，从而实现对全网的综合管理，包括全网故障分析 和故障定位、全网性能综合分析等功能。这样既便于维护、使用，也可以提高该 系统的利用率。而且更重要的是，以后新的网管需求将可以直接纳入该综合网络 管理系统之中。 1 3数据挖掘概述和过程 数据挖掘即从大量的数据中寻找出有用的信息，其目的是从海量数据中获取 有效的、新颖的、潜在有用的、最终用户可以理解的模式的过程。数据挖掘是一 种决策支持过程，它主要基于人工智能、机器学习、统计学等技术，高度自动化 基于序列模式挖掘的网络告警关联 地分析企业原有的数据，做出归纳性的推理，从中挖掘出潜在的模式，帮助企业 的决策者调整市场策略，减少风险，做出正确的决策。 数据挖掘就是从大量的数据中提取或者“挖掘 知识。将数据挖掘应用于网 络故障管理的研究领域，研究的热点和重点集中在如何通过对告警关联和告警时 序关联的规则挖掘，如何定位根源故障，以最短的时间消除故障。因而告警关联 分析成为研究的重点、难点和热点。 1 4序列模式挖掘概述 时间序列挖掘p 1 是数据挖掘领域一个重要的问题，是指在相同时间间隔或 者变化的时间间隔的记录，记录中用时间戳来显示每个事件发生的具体时间，可 以用于序列模式挖掘、趋势分析及预测和相似性分析。 序列模式挖掘是指寻找在某时间窗约束下，具有某种( 些) 特征属性的告警 ( 联合) 事件产生，导致具备另一种( 些) 特征属性的告警( 联合) 事件将以某 种概率在另一个时间窗内产生的规则。r 给定一个由不同序列组成的集合，其中，每个序列由不同的元素按顺序有序 排列，每个元素由不同项目组成，同时给定一个用户指定的最小支持度阈值，序 列模式挖掘就是找出所有的频繁子序列，即该子序列在序列集中的出现频率不低 于用户指定的最小支持度阈值。它是一类重要的数据挖掘问题，有着非常广泛的 应用前景。 1 4 1 研究的目标和意义 为了提供快速、可靠、有竞争力的服务，移动通信网络管理系统要适应网络 规模扩张、带宽提高、复杂性增强的变化。随着网络结构规模日益复杂，网络故 障管理越来越困难。网络故障不仅会降低客户的满意度，也会导致经济损失。故 障的发生在所难免，快速检测和定位故障是保障网络稳定运行的关键因素，也是 网络管理的首要任务。 故障是网络设备硬件、软件模块的异常状态，网络或设备检测到故障，发出 描述故障现象的消息称为告警，它是从网络设备角度对故障的一个描述。组成网 络的设备( 组成设备的模块) 是相互影响的，一个设备发生异常，相关设备会表 现出故障征兆，导致每一个相关设备都发出告警信息，这种现象称为故障的传播 特性。 在大的通信网中，一个故障产生很多告警，当若干故障并存时，产生大量的 告警，这些告警隐藏了故障的原因，以至难以进行故障诊断和定位，这是当今网 络故障管理的一个难题。网络维护人员感兴趣的不是告警事件本身，而是引起告 北京邮电大学硕士学位论文 警的设备故障。尽管这些告警直接或间接的反映故障现象，但大量的告警事件形 成告警风暴，使迅速、准确定位故障变得很困难。借助告警相关性处理大量的告 警，识别告警之间的关系，用概括的或高层的信息解释故障产生的告警序列，为 故障诊断和定位提供有效的帮助。 i t u t 定义了网络管理的五个管理功能：故障、配置、性能、计费、安全。 告警相关性可以广泛应用到这些管理功能中。就目前的研究和应用看，告警相关 性在故障管理领域应用最为广泛，它是告警相关性最基本，也是最重要的应用。 在故障管理领域，通过分析告警事件之间的相关性，一方面，将多个告警归 结成较少的告警，过滤大量的冗余告警，另一方面，用于实时故障诊断和故障定 位。可见，告警相关性可以辅助网络管理人员过滤冗余信息，准确的定位故障， 及时排除故障，保障网络可靠的运行。序列模式挖掘是时间序列挖掘的一种，也 是解决告警相关性规则提取问题的常用方法。 1 4 2 相关定义 序列模式挖掘问题的相关定义如下： 设d b 是待挖掘数据序歹, j ( d a t as e q u e n c e ) 的集合，数据序列记为( s e q _ i d 、 t r a n s l i s t ) ，其中s e qi d 代表序列标识、t r a n sl i s t 是事务列表，包含多个按时 间或其他顺序排列的事务。t r a n s e sl i s t = ( t r a n s l 、t r a n s 2 、t r a n s n ) ，t r a n s = ( t r a m - t i m e ，i t e m s e t ) ，其中t r a n s t i m e 代表事件发生时间或其它顺序标识，i t e m s e t 是一个项目集。 定义1 ( 序列) ：i = i l i 2 i r a ) 是项集，i k ( 1 = k - - - m ) 是一个项，序列s 记为s = ，其中s j ( 1 - - j - - n ) 为项集( 也称序列s 的元素) ，即s j c _ i 。 每个元素由不同项组成。序列的元素可表示为( i l i 2 i k ) ，若一个序列只有一个 项，则括号可以省略。 序列包含的所有项的个数称为序列的长度。长度为，的序列记为l - 序列。 定义2 ( 子序列) ：序列t = 是另一个序列s = 的子 序列，满足下面条件：对于每一个j ，1 q - m - l ，有i j i j + l 且对于每一个j ， 1 = j 一m ，存在1 = k = 与，则称序列s 为序列数据库d 中的 一个( 频繁) 序列模式。 长度为z 的序列模式称为l 旗式。 定义5 ( 序列关联规则) ：对于给定的项集i = ( i l i 2 i m ) 以及序列s ，t ， 形如s j t 的表达式称为序列关联规则。 序列关联规则s j t 的支持度是支持序列s 和t 的事物数占总事物数之比。 序列关联规则s j t 的置信度记为( a ) ，是支持序列s 和t 的事物数与仅支 持s 的事物数之比。 1 5论文期间所做的工作 本文作者对序列模式挖掘、告警关联产品和移动网络管理系统进行了深入的 研究，并参加了“基于数据挖掘的智能化告警关联关键技术”的研究以及 b u p t p r i s m i n e r 数据挖掘平台的开发。 作者在该系统的设计和研发中的主要工作包括以下三个方面： 1 序列模式挖掘算法的研究 通过查阅大量文献，对序列模式的六大类算法进行综合性能的分析和评估。 2 序列模式挖掘新算法的提出和验证 将网络拓扑约束和序列模式挖掘的适用于移动通信网络的算法相结合，提出 了适用于移动通信网络告警关联的两个新算法，并将这两个算法应用到项目组开 发的平台中，通过分析采集到的移动通信网络的数据，得到最后的结果评测。 3 告警关联产品的调查研究 对市场上的五种主流的告警关联产品进行调研，分析告警关联产品的功能需 求，为项目组开发的产品功能部分提出建设性意见。 具体的工作内容如下： 1 对选题进行考察，系统学习了移动通信网络的概念和架构，对告警关联 产品进行调研，完成了研究生的开题报告。 2 查阅大量文献，对序列模式挖掘的六大类算法进行深入研究，分析六大 类算法中的1 8 种小算法的优缺点和适用环境，并且提交了序列模式挖 掘的关键技术研究报告。 3 对选题进行论证，结合移动通信网络的特点，提出两种新的算法，并撰 写了算法研究报告。 5 北京邮电大学硕士学位论文 4 负责序列模式挖掘部分的系统开发和优化，配合项目组其他成员将算法 集成入b u p t p r i s m i n e r 系统，完成模块测试、代码维护、文档编写等。 5 对参与项目进行完善和总结，完成阶段报告。 6 总结文档，完成研究生学位论文。 7 做答辩准备工作。 6 基于序列模式挖掘的网络告警关联 第二章序列模式挖掘算法 现实世界中的大量数据具有时间或顺序上的关联性，序列模式挖掘是时间序 列挖掘的一种，也是解决告警相关性规则提取问题的常用方法，其基本思想是把 一段时间内发生的告警事件看作一个时间序列，找出数据库中所有的序列模式， 即那些在序列集合中出现频率超过最小支持度( 用户指定最小支持度阈值) 的子 序列。序列模式挖掘是指寻找在某时间窗约束下，具有某种( 些) 特征属性的告 警( 联合) 事件产生，导致具备另一种( 些) 特征属性的告警( 联合) 事件将以 某种概率在另一个时间窗内产生的规则。 本章综合研究了现有序列模式挖掘的算法，并且结合时间序列的特点，提出 了序列模式挖掘算法的具体分类和算法之间的对照分析。 7 北京邮电大学硕士学位论文 2 1 序列模式挖掘算法总体分类 图2 - 1 序列模式挖掘算法组织结构图 序列模式挖掘的算法最早由a g r a w a l 等人提出，主要的算法分为六类： 1 a p r i o r i - l i k e 算法 以相联规则提取为理论基础，a g r a w a l 提出了序列模式发现问题，并给出了 一系列基于a p r i o r i 的改进算法，它的基本思想是通过k 候选集构造k + i 候选项 集，依据强项集的子集都是强项集的原则过滤k + i 候选项集，然后扫描数据库 得到k + i 强项集，该类方法扫描数据库的次数比较多。 基于序列模式挖掘的网络告警关联 2 基于模式前缀的序列生长方法 这类算法是围绕减少数据库扫描次数问题而发展起来的，代表性算法是 p r e f i x s p a n ，它的基本思想是扫描数据库发现频繁1 序列模式，把数据库投影到 前缀序列库，重复序列发现和投影操作，任何一个频繁序列都可以由它的频繁前 缀生长得到。该类算法不需要生成候选项集，聚焦于小搜索空间，寻找频繁模式 的过程更有针对性且高效，映射后的序列库逐渐缩小，在实际情况中，因为只有 很小一部分前缀会生长到长模式，所以映射库缩小很快。算法主要代价在于构造 映射库，当频繁序列模式很多时，代价比较大，采用以空间换时间的策略。 3 基于问题细分的序列挖掘方法 代表算法是s p a d e 算法，它的基本思想是采用格子理论把原始问题分解为 一些小规模的子问题，这些问题可以在内存中单独运行。对于子格子提出宽度和 深度两种搜索策略。该算法采用数据序列的数据存储格式，每一个序列存储它的 时间信息，通过简单的时间连接计算支持度。该算法的效率比a p r i o r i 1 i k e 算法 中的g s p 算法提高一个数量级。以该思想为基础发展的s p a m 算法，算法框架 与s p a d e 类似，支持度借助位图计算。该类算法无需多次扫描原始数据库，运 用高效的搜索方案，支持度的计算完全可以靠i d l i s t 得到，降低了计算代价， 但需要存储大量的由原始数据派生的中间数据，即采用以空间换时间的策略，内 存消耗大。 专4 多维序列模式挖掘 、予一般的序列模式挖掘只是挖掘一个维度即挖掘一个属性和时间戳，多维序列 模式的基本思路是挖掘多个属性，以得到更多的信息和有用的模式p 1 。多维序 列模式挖掘的算法可以归结为两类：将序列模式挖掘算法和多维分析方法集成； 将多维信息并入到序列中然后对新的序列集进行挖掘。 5 增量序列模式挖掘 目前的大多数序列模式挖掘算法一般都分为两个阶段：频繁序列的发现和规 则的产生，算法的计算量主要集中在第一个阶段上。如何快速地确定所有频繁序 列是算法效率的关键部分。对于大多数的实际应用，数据库比较大，序列模式挖 掘算法的时空开销往往非常大；另一方面，数据挖掘过程在应用中是一个反复的 交互式的过程，用户的本次要求和前次要求往往有较大的重复性。增量序列模式 挖掘算法的主要思想是充分利用前次的结果来加速本次挖掘过程，而不是简单地 在整个更新过的数据库上重新运行挖掘算法，整个挖掘过程的效率就会有很大提 高。 6 基于约束的算法 数据挖掘系统可以发现大量的模式，然而其中许多模式是用户己知的、缺乏 9 北京邮电大学硕士学位论文 新颖性或冗余的，这些模式对用户不是有趣的，因此需要通过对模式的约束与评 估，引入用户参与，引导数据挖掘系统对用户感兴趣模式进行搜索，并使模式易 于用户理解和使用。模式的约束和评估的目的是为了提高数据挖掘的实用性与效 率。模式的约束是指在挖掘过程中引入用户约束，指导发现过程和压缩搜索空间； 而模式的评估是指在挖掘过程后，对模式进行分析与评估，使得模式易于用户理 解和使用。 2 2序列模式挖掘算法分析 2 2 1 a p r i o r i 1 i k e 算法 a p r i o r i 1 i k e 类算法是经典的序列模式挖掘算法，该算法的主要思想是由较短 的频繁模式生成较长的候选频繁模式，再经过由支持度进行的剪枝由候选频繁模 式生成频繁模式。该算法的主要优点是思路清晰，实现简单，因而在频繁模式挖 掘领域广泛被各种论文引用。但该算法也有明显的缺点，即在执行过程中为了判 断某个模式是否频繁，需要多次扫描原始数据库，这样便在很大程度上影响了算 法的效率。 2 2 1 1a p r i o r i a i i 算法 在每一次扫描数据库时，利用上一次扫描时产生的大序列生成候选序列，并 在扫描的同时计算它们的支持度( s u p p o r t ) ，满足支持度的候选序列作为下次扫描 的大序列p j 。第一次扫描时，长度为1 的频繁序列模式作为初始的1 序列。 1 排序阶段 利用客户标识c u s t o m e r - i d 作为主关键字以及事务发生的时间t r a n s a c t i o n - t i m e 作为次关键字对数据库d 排序。该步骤将原始的事务数据库转换成客户序列的 数据库。 2 大项目集阶段 在该阶段发现所有的大项目集l 。同时发现所有的大1 序列的集合，因为这 个集合正好是 i l l ) 。大项目集的集合可以映射到一个连续整数的集合上。 由于比较大项目集要花费一定的时间，形成单独的数据库可以减少开销。 3 转换阶段 需要确定哪一个给定的大序列集被包含在顾客序列中，然后将每一个顾客序 列转换成一个替换的代表。在一个已经转换的客户序列中，每一个事务被包含于 该事物中的所有大项目集来替换。如果一个序列不包含任何大项目集，则在已经 l o 基于序列模式挖掘的网络告警关联 转换的序列中就不应该保留这项事务【6 1 。 4 序列阶段 利用大项目集发现所希望的序列。 5 最大阶段 在大序列中发现最大的序列。 设最长序列的长度为n f o r ( k - - mk l ；k 一) d o f o r ( 每一个k 序列) d 0 从s 中删除所有的子序列 2 2 1 2a p r i o r i s o m e 算法 a p d o r i s o m e 算法将序列分成两部分分别计数。前半部分只对一定长度的序 列计数，后半部分跳过已经计数过的序列。在实际过程中两个部分是混合在一起 的，用来减少候选者占用的资源1 。 函数n e x t 取在上一遍已计数序列的长度作为参数，返回在下一遍将要计数 序列的长度。后半部分首先删除包含在某些大序列中的所有序列，跳过已计数过 的序列。 表2 1a p r i o r i a i i 算法与a p r i o r i s o m e 算法对比 寻找最长寻找所有速度速度 占用内存 频繁序列频繁序列( 数据量小时)( 数据量大时) a p r i o r i a l l 优相同优相同劣 a p r i o r i s o m e 劣相同劣相同优 2 2 1 3d y n a m i c s o m e 算法 d y n a m i c s o m e 算法的思路和a p r i o d s o m e 类似，不过比a p r i o d s o m e 多了一 个初始化阶段。该算法预设一个步长s t e p 控制哪些长度的序列开始计数，初始化 阶段小于s t e p 的序列被计数，例如，如果s t e p = 3 ，则长度为1 ，2 ，3 的序列被计 数；前推阶段，所有长度为s t e p 的倍数的序列被计数，也就是长度为6 ，9 ，1 2 的序列被计数；回溯阶段同a p d o r i s o m e 中的回溯阶段p 1 。 算法分成i n i t i a l i z a t i o n 、f o r w a r d 、i n t e r m e d i a t e 及b a c k w a r d 四个阶段： 1 ) i n i t i a l i z a t i o n 阶段：计算从1 - s e q u e n c e 到s t e p s e q u e n c e 的c a n d i d a t e s e q u e n c e 。( 若s t e p 为3 ，剐求出c l ，l l ，c 2 ，l 2 ，c 3 ，l 3 ) 2 ) f o r w a r d 阶段：针算( n s t e p ) 一s e q u e n c e 。( 求出c 6 ，l 6 ，c 9 ，l 9 ) 1 1 北京邮电大学硕士学位论文 3 ) i n t e r m e d i a t e 阶段：计算其他长度的c a n d i d a t es e q u e n c e 。 4 ) b a c k w a r d 阶段：从前三阶段的l k ，找出m a x i m a ls e q u e n c e 。 2 2 1 4g s p 算法 1 g s p 算法的主要思想 g s p 算法是a p r i o r i a l l 算法的扩展算法，是一种宽度优先算法，其算法的执 行过程和a p r i o r i a l l 类似，最大的不同就在于引入了时间约束、滑动时间窗和分 类层次技术，增加了扫描的约束条件，有效地减少了需要扫描的候选序列的数量， 同时还克服了基本序列模型的局限性，更切合实际，减少多余的无用模式的产生 【9 】【1 0 1 。另外g s p 算法利用哈希树来存储候选序列，减小了需要扫描的序列数 量，同时对数据序列的表示方法进行转换，这样就可以有效地发现一个侯选项是 否是数据序列的子序列。 2 g s p 算法描述 扫描序列数据库，得到长度为1 的序列模式l 1 ，作为初始的种子集。 根据长度为i 的种子集l i 通过连接操作和剪切操作生成长度为i + l 的候选序 列模式c i + l ；然后扫描序列数据库，计算每个候选序列模式的支持数，产生长 度为i + l 的序列模式l i + l ，并将l i + l 作为新的种子集。 重复上一步，直到没有新的序列模式或新的候选序列模式产生为止，即l l j c 2jl 2jc 3j l 3jc 4j l 4j g s p 产生候选序列模式步骤： 1 ) 连接阶段： 如果去掉序列模式s 1 的第一个项目与去掉序列模式s 2 的最后一个项目所得 到的序列相同，则可以将s 1 与s 2 进行连接，即将s 2 的最后一个项目添加到s l 中。例如( 1 ，2 ) ( 3 ) 去掉第一个项目与( 2 ) ( 3 ，4 ) 去掉第二个项目所得到的 序列均为( 2 ) ( 3 ) ，因此将两者连接为( 1 ，2 ) ( 3 ，4 ) 。 2 ) 剪切阶段： 若某候选序列模式的某个子序列不是序列模式，则此候选序列模式不可能是 序列模式，将它从候选序列模式中删除。 3 ) 候选序列模式的支持度计算： 利用哈希树的方法，对于给定的候选序列模式集合c ，扫描序列数据库，对 于其中的每一条序列d ，找出集合c 中被d 所包含的所有候选序列模式，并增加 其支持度计数。 3 g s p 算法缺点 1 2 基于序列模式挖掘的网络告警关联 g s p 算法也是一个a p r i o r i 类算法，它存在的主要问题和a p r i o r i a l l 算法相 似。由于约束条件的使用，相应会使算法复杂一些，也会以相应的开销为代价， 但总体来说效率比a p r i o r i a l l 高2 2 0 倍。具体缺点如下： 1 ) 需要对序列数据库进行循环扫描。 2 ) 如果序列数据库的规模比较大，则有可能会产生大量的候选序列模式。 3 ) 对于序列模式的长度比较长的情况，由于其对应的短的序列模式规模太 大，g s p 算法很难处理。 2 2 1 5m e m i s p 算法 m e m i s p ( m e m o r yi n d e x i n gf o rs e q u e n t i a lp a t t e mm i n i n g ) 算法只需要扫描 一次数据库，如果数据库比较大的话需要扫描两次，不产生可能样式和暂时的中 间资料库，通过递归扫描和内存索引产生序列频繁集。 类型1 模式、类型2 模式、主干项、前缀模式给定序列数据库中的一 个序列模式和一个频繁项x ，如果将x 作为一个元素追加到a 的后面形成的模式 称为类型1 模式，记为a x ；如果将x 作为一项添加到序列模式a 的最后一个 元素里形成的模式称为类型2 模式，记为a x ；其中x 称为序列模式a x 或a x 的主干项；a 称为a x 或a x 的前缀模式，记为p - - p a t t e r n 。 例如，给定一个序列模式 和一个频繁项c ，则可形成的类型一1 模式为 ，可形成的类型一2 模式为 。约定空序列为， 是所有频繁1 序列的前缀序列。 2 2 1 6a p r i o r i - l i k e 算法对照分析 a p r i o r i 1 i k e 算法的共同缺点是： 1 ) 容易生成庞大众多的候选序列。 2 ) 需要多次扫描数据库。候选序列的长度增加l ，就需要扫描1 次数据库。 3 ) 不易发现长序列模式，因为随着需要挖掘的序列模式长度的增加，侯选 序列的数量会成指数级增长。 4 ) 在发现序列模式的过程中，每次扫描数据库都要在数据转换中产生很大 的开销。 表2 - 2a p r i o d l i k e 算法对照分析表 算法名称主要特点和改进方法 缺点 在每一次扫描数据库时，利用上一次扫 a p r i o r i a l l 当数据量较大时，速度比较慢。 描时产生的大序列生成候选序列，并在 北京邮电大学硕士学位论文 扫描的同时计算它们的支持度 ( s u p p o r t ) ，满足支持度的候选序列作为 下次扫描的大序列。第1 次扫描时，长 度为l 的频繁序列模式作为初始的1 序 列。 算法将序列分成两部分分别计数。前半 部分只对一定长度的序列计数，后半部 a p r i o r i s o m e 分跳过已经计数过的序列。在实际过程 占用内存较大，寻找所有频繁序列 中两个部分是混合在一起的，用来减少 的能力较弱。 候选者占用的资源。 算法d y n a m i c s o m e的思路和 a p r i o r i s o m e 相似，不过多了一个初始化 比a p r i o r i a u 和a p r i o r i s o m e 效率 d y n a m i c s o m e阶段。该算法预设一个步长s t e p 控制哪 低，主要原因是它在前推阶段产生 些长度的序列开始计数：初始化阶段小 太多的候选，后两者的优点是可以 于s t e p 的序列被计数。 避免计数很多非最大序列。 g s p 算法是a p r i o r i a l l 算法的扩展算法， 是一种宽度优先算法，其算法的执行过 程和a p r i o r i a l l 类似，最大的不同就在 于引入了时间约束、滑动时间窗和分类 层次技术，增加了扫描的约束条件，有如果序列数据库的规模比较大，则 效地减少了需要扫描的候选序列的数有可能会产生大量的候选序列模 量，同时还克服了基本序列模型的局限式。需要对序列数据库进行循环扫 g s p 性，更切合实际，减少多余的无用模式描。对于序列模式的长度比较长的 的产生。另外g s p 利用哈希树来存储候 情况，由于其对应的短的序列模式 选序列，减小了需要扫描的序列数量，规模太大，g s p 算法很难处理。 同时对数据序列的表示方法进行转换， 这样就可以有效地发现一个侯选项是否 是数据序列的子序列。总体来说效率比 a p r i o r i a l l 高2 2 0 倍。 在将序列数据库读入内存并计算 得到频繁项集的时候，没有将非频 繁项排除在外，造成了在以后的算 法运行过程中，多次读取非频繁 m e m i s p 算法只需要扫描一次数据库，项，浪费了不必要的计算机资源和 如果数据库比较大的话需要扫描两次，宝贵的系统运行时间；在第二步和 m e m i s p 不产生可能样式和暂时的中间资料库。第三步的递归操作过程中，重复执 通过递归扫描和内存索引产生序列频繁行主干项的支持度计数和序列模 集。 式索引集的构建，造成了对序列数 据库m d b 或序列模式索引集的重 复读取，也极大地延迟了算法的执 行时间；若某一序列中含有较多的 重复项。 1 4 基于序列模式挖掘的网络告警关联 2 2 2 基于模式的序列生长算法 算法本身不生成大量的候选序列，而是以某种压缩的形式保留了原数据库基 本的数据分组。算法每一次迭代不是扫描完整的原数据库来匹配相应的全部候选 序列，而是限定在投影数据库中，大大节省了算法执行时间。 基于序列数据库投影的算法比常用的基于a p r i o r i 的算法要快且有效得多， 特别是在支持度比较低的情况下更加明显。 2 2 2 1 f r e e s p a n ( f r e q u e n tp a t t e r n - p r o j e c t e ds e q u e n t i a lp a t t e r n m i n i n g ) 算法 1 f r e e s p a n 算法的主要思想 基于数据库投影和分片技术的算法，频繁模式投影的序列模式挖掘。利用频 繁项递归地将序列数据库投影到更小的投影数据库集中，在每个投影数据库中生 成子序列片段。这一过程对数据和待检验的频繁模式集进行了分割，并且将每一 次检验限制在与其相符合的更小的投影数据库中。 2 f r e e s p a n 算法描述 首先给定序列数据库s 及最小支持度阈值。扫描s ，找到s 中的频繁项集， 并以降序排列生成f l i s t 列表。 执行下面步骤： 1 ) 第一遍扫描s ，构造频繁项矩阵； 2 ) 生成长度为2 的序列模式，循环项模式的标记和投影数据库的标记； 3 ) 再次扫描s ，生成循环项模式和投影数据； 4 ) 对生成的投影数据库递归调用矩阵投影挖掘算法挖掘更长的候选模式。 2 , 2 2 2p r e f i x s p a n 算法 1 p r e f i x s p a n 算法的主要思想 p r e f i x s p a n 算法是一种深度优先算法。扫描数据库发现频繁1 序列模式，把 数据库投影到前缀序列库，重复序列发现和投影操作，任何一个频繁序列都可以 由它的频繁前缀生长得到。该类算法不需要生成候选项集，聚焦于小搜索空间， 寻找频繁模式的过程更有针对性且高效，映射后的序列库逐渐缩小，在实际情况 中，映射库缩小很快，因为只有很小一部分前缀会生长到长模式。 2 p r e f i x s p a n 算法描述 1 ) 定义u “： 前缀：设每个元素中的所有项目按照字典序排列。给定序列0 = ， 北京邮电大学硕士学位论文 p = ( 皿鲫，如果e i = e i ( i m 1 ) ，e m e m ，并且( e m - e m ) 中的项目均在e m 中项目的后面， 则称p 是a 的前缀。 投影：给定序列0 l 和p ，如果d 是0 【的子序列，则0 【关于1 3 的投影a 必须 满足：p 是0 【的前缀，a 是0 l 的满足上述条件的最大子序列。 后缀：序列a 关于子序列d = 的投影为a = ( n = m ) ，则序列0 【关于子序列d 的后缀为 ，其中e m ”= ( e r a e m ) 投影数据库：设a 为序列数据库s 中的一个序列模式，则0 【的投影数据库 为s 中所有以0 为前缀的序列相对于仅的后缀，记为s i 仅。 2 ) 算法描述： 扫描序列数据库，生成所有长度为1 的序列模式。 根据长度为l 的序列模式，生成相应的投影数据库。 在相应的投影数据库上重复上述步骤，直到在相应的投影数据库上不能产生 长度为1 的序列模式为止。 3 ) 具体算法 输入：序列数据库s 及最小支持度阈值m i n _ s u p 输出：所有的序列模式 方法：调用子程序p r e f i x s p a n ( ，0 ，s ) 子程序p r e f i x s p a n ( o c _ ，l ，s i a ) 参数：a ：一个序列模式，l ：序列模式0 c 的长度，s 1 0 【：如果a 为空，则为 s ，否则为0 【的投