（计算机软件与理论专业论文）数据挖掘及其在电信告警中的应用.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：翌蔓日期：竺兰尘兰 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：! 蔓导师签名：窆至! 些日期：兰! ：! ! ：主 山东大学硕士学位论文 摘要 网络故障管理是电信网络管理的重点和难点，当前电信网络的故障管理非 常被动，它是在网络发生故障后，网络管理人员根据故障告警来发现并排除故 障。要改变这一状况，就需要网管人员善于发现和运用网络运行的规律。 电信告警数据库中保存了大量历史告警信息，在这些历史告警信息中蕴涵 了许多有用的信息，这些信息反应了网络运行的规律，利用这些信息可以改善 网络故障管理。针对这一状况，作者提出用数据挖掘技术来分析电信告警数据， 以发现有用信息。 本文对两种数据挖掘算法进行了研究，并对这些算法作了改进，其中包括： 关联规则挖掘算法、事件序列中频繁情节挖掘算法。 对于关联规则挖掘问题，针对当前挖掘算法需要对数据库进行多次扫描， 以及在识别频繁项目集时采取模式匹配等问题，提出采用新的数据结构，使得 通过简单的数据库操作就可识别频繁项目集，而且算法在计算时所需访问的数 据库在不断减小，从而提高了挖掘的速度。 对于事件序列数据的挖掘问题。针对h e i k k im a n n i l a 等人的算法没有考虑 大数据集，且只可挖掘两类情节等问题，论文提出了一种改进的算法，该算法 能挖掘所有可能的频繁情节，使得该算法具有更强的适用性。 最后，论文对数据挖掘技术在电信告警分折中的应用作了研究，并结合电 信业务的实际特点以频繁情节挖掘算法为例介绍了数据挖掘全过程，找到一个 分析电信告警、发现告警发生规律的方法，该方法也对今后的实际应用研究有 较大的参考价值。 关键字：数据挖掘、关联规则、事件序列、频繁情节。 山东大学硕士学位论文 a b s t r a c t f a u l tm a n a g e m e n ti sa ni m p o r t a n tb u td i f f i c u l ta r e ao ft e l e c o m m u n i c a t i o n n e t w o r km a n a g e m e n t t h ec u r r e n tf a u l tm a n a g e 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 i s v e r yp a s s i v i t y ，n e t w o r km a n a g e rf i n da n de l i m i n a t et h e f a u l t a c c o r d i n gt o t h e f a u l ta l a r m sa f t e rn e t w o r kg ow r o n g n e t w o r km a n a g e ri sn e e dt oa c q u a i n t a n c et h e r u nr u l eo ft e l e c o m m u n i c a t i o nn e t w o r ki no r d e rt oc h a n g et h i ss t a t u s t h e r ea r el o t so fa l a r md a t a i nt e l e c o m m u n i c a t i o na l a r md a t a b a s e ，a n dt h e r e a r e m a n yu s a b l e i n f o r m a t i o ni sc o n t a i n e di n t h i s h i s t o r y a l a r md a t a ，t h e ya r e r e s p o n s et h er u nr u l eo f t e l e c o m m u n i c a t i o nn e t w o r k ，w ec a nu s et h e mt oi m p o r v e f a u l tm a n a g e m e n to fn e t w o r k i no r d e rt of i n dt h o s eu s a b l e i n f o r m a t i o n ，t h e a u t h o rd i s c u s st ou s e d a t a m i n i n gt e c h n i q u e t oa n a l y s et e l e c o m m u n i c a t i o ma l a r md a t a t h i s p a p e r f o c u s e so nt w o d a t a m i n i n ga l g o r i t h m s ，a n di m p r o v e t h o s e a l g o r i t h m s i t i si n c l u d ea s s o c i a t i o nd a t a m i n i n ga l g o r i t h m 、f r e q u e n te p i s o d e si n e v e n ts e q u e n c ed a t a m i n i n ga l g o r i t h m s i n c et h ec u r r e n ta s s o c i a t i o nd a t a m i n i n ga l g o r i t h mn e e da c c e s st h ed a t a b a s e m a n yt i m e sa n da d o p tp a t t e r nm a t c h i n gt or e c o g n i s ef r e q u e n ti t e m s e t ，t h e a u t h o r d i s c u s sn e wd a t as t r u c t u r e ，t h e nc a nr e c o g n i s ef r e q u e n ti t e m s e ta c c o r d i n gt os i m p l e d a t a b s eo p e r a t i o n ，a n dt h ed a t a b a s et h a tt h ea l g o r i t h mn e e dt oa c c e s si sm i n i s hb i t b yb i t f o re v e n t s e q u e n c e d a t a d a t a m i n i n g ，t h ep a p e r a i ma th e i k k im a n n i l a s a l g o r i t h md on o tt h i n ko v e rg r e a td a t a s e ta n do n l ym i n et w ok i n de p i s o d e s t h i s p a p e rg i v eo n ei m p r o v e da l g o r i t h m ，i tc a nm i n em o r ef r e q u e n te p i s o d e s ，a tt h es a m e t i m ei ta d o p td a t ap a r t i t i o nt e c h n i q u es oa st os u i tm i n e g r e a td a t a s e t t h i sp a p e ra i ma ti d 3a l g o r i t h m 。sd e f e c t ，a d v a n c ea ni m p o r v ea l g o r i t h m ，i tc a l l d e a lw i t hc o n t i n u o u s a t t r i b u t e ，a n d i tn o t et h er e c o r dn u m b e rt h a t s a t i f y t h e c o n d i t i o nw h e nb r i n gt h ed e c i s i o n t r e e ，t h e r e b y i ti n c r e a s et h et r e e sf o r e c a s t a b i l i t y k e yw o r d s ：d a t a m i n i n g 、a s s o c i a t i o n 、 e v e n ts e q u e n c e 、 f r e q u e n te p i s o d e s 4 山东大学硕士学位论文 1 绪论 1 1 论文的选题及其研究意义 电信网络的规模曰趋庞大，结构也日趋复杂。这些网络由许多相互连接的 设备组成，它们每天产生大量告警信息，告警的类型多达数百种，使得屯信告 警数据库中保存了大量的历史告警信息。在这些历史告警信息中蕴含着一些有 价值的信息，如电信告警发生的规律。可以利用这些信息辅助网络管理，如在 严重故障发生前预测告警，以便在故障未发生前就发现并排除故障。由于电信 历史告警数据量很大，使得从历史告警中提取有价值的信息十分困难。特别是 网络及其部件更新得十分快，导致告警信息不断发生变化，而且告警信息的出 现经常是爆发式的，这些情况都加大了分析告警信息的难度。 数据库中知识发现( k n o w l e d g ed i s c o v e r y i nd a t a b a s e ，简称k d d ) ，又称为 数据挖掘( d a t am i n i n g ) ，它是由数据库、机器学习、统计学等多门学科形成 的一门新兴学科。其目标是从大量原始数据中挖掘出隐含的、有用的、未知的 知识，所发现的知识可以是描述数据特性的规则、频繁出现的模式、数据集中 目标的聚类、预测模型等。目前数据挖掘技术被认为具有广阔的研究前景。国 外，在大型商业、金融、保险、民航、电信等大型企业都开始得到应用。国内 方面，目前总体上仍处于起步研究阶段。 本课题针对电信网络管理的需求，将数据挖掘应用于电信网络的告警分 析，采用新的数据挖掘技术分析告警信息，从大量原始告警信息中获得网络告 警的频繁情节知识，为电信告警信息的分析提供一个可行的解决方案。挖掘的 结果可以帮助网络管理员更好的了解电信网络( 如发现网络告警产生的规律) ， 辅助网络管理员进行网络故障的管理。结合网络管理员以及网络专家的经验用 于网络故障的实时监控，以实现对网络故障的预测。因此，本课题具有较强实 用价值和理论意义。 1 2 国内外研究现状 对于频繁情节的挖掘，h e i k k im a n n i l a 1 , 2 , 3 , 4 】等人首先提出在事件序列 中滑动窗口的技术。该技术利用滑动窗口来指定事件在时间上的相邻程度并发 现事件序列中事件间在时间上的偏序关系，算法将情节分为并行情节和串行情 节两类。对不同类型的情节采用不同的算法，使得数据库扫描次数倍增，同时 算法只考虑两类情节，无法挖掘其它类型的情节。 当前国内对数据挖掘的研究总体上处于理论探讨、应用试验阶段，对算法 山东大学硕士学位论文 研究得较多，实际应用还很少，对电信网络告警数据的挖掘尤其如此。 除了频繁情节挖掘算法，还可采用其它挖掘技术挖掘电信网络告警数据， 如关联规则挖掘技术、决策树挖掘算法。关联规则发现由r a g r a w a l 等人3 】 首先提出( s e t m 、a p r i o r i 、a p r i o r i t i d ) ，它是数据挖掘研究的重要内容，对这 问题人们提出许多不同的挖掘方法，如r a g r a w a l 提出的挖掘多层次关联规 则的c u l m u l a t e ，s t r a t i f y 等算法【3 1 ，j s p a r k 等提出了d h p 算法【2 4 1 ，d h p 利用 在前一轮产生的h a s h 表来减小c k 的大小以提高算法的效率。a s h o ks a v a s e r e 等提出了p a r t t i i o n 算法，该方法是将数据库划分为若干能在内存中加以处理的 小块。在第一次遍历中，它生成在各自划分块中是频繁的所有局部频繁集。然后 在第二次遍历中，收集各局部频繁集的全局支持，从而确定全局频繁集。j h a n 等 提出了面向属性归纳( a t t r i b u t eo r i e n t e d i n d u c t i o n ) 的关联规则挖掘算法 m lt 2 l 1 等【2 ” ，j o n gs o op a r k 等对并行关联规则挖掘进行了研究，并提出 了p d m 并行挖掘算法【2 。国内的研究人员在关联规则挖掘方面也作了大量研 究，李力、朱天翔、许占文1 2 0 1 对关系数据库多项集关联规则问题进行了研究， 它将数据集分为主题项集和分类项集，通过分类项集将数据库分解为多个小的 交易子集，再在子集的主题项集中挖掘关联规则，从而可挖掘出“办公人员中， 购买食品的人9 5 会购买纸巾”这样的规则。程继华、施鹏飞、郭建生【2 1 】研究 了模糊关联规则挖掘问题，提出模糊关联规则挖掘算法f a r m a 。程继华、魏 暑生、施鹏飞【2 2 】研究了基于概念的关联规则的挖掘，并提出算法a r c o n c e p t ， 该算法是对基于分类的挖掘算法的拓展。涂星原1 2 3 研究了基于数值属性 ( q u a n t i t a t i v ea t t r i b u t e ) 的关联规则的挖掘问题，给出了挖掘基于数值属性的关 联规则的算法：基本算法q b a s i c 和改进算法q _ a r 。 1 3 论文研究内容及组织 在后面的章节中，我们将研究数据挖掘技术及其在电信网络故障管理中的 应用。 首先在第二章中，我们分析了关联规则挖掘问题。论文针对当前挖掘算法 需要对数据库进行多次扫描，以及在识别频繁项目集时采取模式匹配等问题， 论文提出并采用新的数据结构，使得通过简单的数据库操作就可识别频繁项目 集，而且算法在计算时所需访问的数据库在不断减小，从而提高了挖掘的速度。 接着论文在第三章中对事件序列数据的挖掘问题进行研究，介绍了h e i k k i m a n n i l a 等人在这一问题的研究成果。针对他们的算法本文提出一种改进的算 6 山东大学硕士掌位论文 法，该算法能挖掘所有可能的频繁情节集。 在第四章中论文对数据挖掘技术在电信告警分析中的应用作了预研究，以 频繁情节挖掘算法为例介绍了数据挖掘全过程，找到一个分析电信告警、发现 告警发生规律的方法，该方法也对今后的实际应用研究有参考意义。 最后，在第五章中我们对全文进行总结，并指出下一步的工作。 1 4 论文的研究背景 本论文的研究对象是临沂电信公司告警数据。临沂电信公司的网络规模 大、结构复杂，这些网络设备每天产生大量的告警信息，这些告警中隐含许多 有价值的信息，如告警产生的规律。利用这些信息可以改善电信故障管理。临 沂电信公司希望从其历史告警数据中找到这些隐含的有用信息，本课题是在间 临沂电信公司有协议的情况下进行的。 1 5 小结 在本章中我们介绍了本论文的选题及其研究意义，分析了k d d 当前国内 外的研究现状，对论文的主要研究内容及组织作了介绍，并且对论文的实验背 景作了简要说明。 2 关联规则挖掘算法 2 1 引言 关联规则发现是r a g r a w a l 等人【1 ，2 ，3 1 首先提出的。关联规则是形式如下的 一种规则，“在购买面包和黄油的顾客中，有9 0 的人同时也买了牛奶”( 面包 + 黄油牛奶) 。用于关联规则挖掘的主要对象是事务型数据库( t r a n s a c t i o n a l d a t a b a s e s ) ，个事务一般由如下几个部分组成：事务标识符，事务中包含的项 目集( i t e m s ) 。 由于数据库技术的广泛应用，商场及超市在其数据库中存储了大量的销售 数据。如果对这些历史数据进行分析，则可对顾客的购买行为提供极有价值的 信息。例如。可以对货架上的商品进行规划摆放( 如把顾客经常同时买的商品 放在一起) ，帮助如何规划市场( 怎样相互搭配进货) 。由此可见，从事务数据 中发现关联规则，对于改进零售业等商业活动的决策非常重要。 关联规则挖掘技术可用于挖掘电信告警数据。这是因为每一条告警中包含 许多属性信息，如产生告警的设备、告警产生时间、告警类别、告警级别等。 我们可将每一个告警看作是一个事务，将告警类别等属性信息看作是物品。这 7 山东大学硕士学位论文 样我们就可以用关联规则挖掘技术对告警数据进行挖掘，从而发现告警的属性 信息在一起出现的情况。如： i f ( o f f i c eh o u r s ) a n d ( b a s es t a t i o n ) a n d ( a l a r ma ) a n d ( a l a r mb ) t h e na l a r m c w i t h e o n f f 0 9 ) ，f r e q ( 0 0 5 ) 其意思是如果在工作时间段上，且设备类型为基站，那么设备如果发生告 警a 和告警b ，则在某时间段内会发生告警c ，这一规则的信任度为0 9 ，支 持度为0 0 5 ，也就是说如果某告警有规则的前部所示事件的发生，那么9 0 的 情况下该告警也有规则后部对应事件的发生，有这一属性特征的告警在所有告 警中的比例为0 0 5 。 2 2 关联规则的形式描述一 设，= 小f ：，f 。 是一组物品集( 项目集) ，d 为事务数据库t 每一个事务可 表示为 t i d ，t ) ，其中t = ( f 。，f ：，i k ) ，f ，l ( j = 1 , 2 ，七) ，它表示该事务中涉及 的项目集，t i d 为事务标识符，它唯一标识一个事务。 定义2 2 1 ：如果项目集互r ，我们说事务 t i d ，t ) 包含项目集x 。 定义2 2 + 2 ：关联规则是形如z 等y 的逻辑蕴含式，其中x c ，y c ，。 定义2 2 3 ：如果事务数据库中有s 的事务包含x ，那么我们说项目集x 的支持度为s ，即s u p p o r t ( x ) = s ； 定义2 2 4 ：如果事务数据库中包含x 的事务中有c 的事务同时也包含y 。 那么我们说关联规则x jy 的信任度为c ，即c o n f i d e n c e ( x 等y ) = s u p p o r t ( x u y ) s u p p o r t ( x ) 2 c a 如果不考虑关联规则的支持度和信任度，那么在事务数据库中存在无穷多 的关联规则。事实上，人们一般只对满足一定的支持度和信任度的关联规则感 兴趣。因此，为了发现有意义的关联规则，需要给定两个阂值：最小支持度 ( m i n i m u ms u p p o r t ) 和最小信任度( m i n i m u mc o n f i d e n c e ) 。前者规定关联规则 必须满足的最小支持度，简称为m i n s u p ；后者规定关联规则必须满足的最小信 任度，简称为m i n e o n f 。 定义2 。2 ，5 ：如果项目集x 中有k 个项目，称x 长度或大小为k ，此时项 目集x 又可记作k 项集。 定义2 2 6 ：如果项目集x 的支持度s u p p o r t ( x ) 大于最小支持度m i n s u p ，那 么称项目集x c ，是频繁项目集。 3 山东大学硕士学位论文 2 3 关联规则挖掘方法 关联规则发现任务或问题是：给定一个事务数据库d ，求出所有满足最小 支持度m i n s u p 和最小信任度m i n c o n f 的关联规则。该问题可以分解为两个子问 题： 求出d 中满足最小支持度m i n s u p 的所有频繁项目集； 利用频繁项目集生成满足最小信任度的所有关联规则。 其中子问题的解决方法较为简单，对每个频繁项目集，对f 的每个非空 子集a ，考察规则a j ( ，一a ) ，如果该规则的信任度大于最小信任度m i n c o n f ，则 输出此规则。 予问题的求解是关联规则发现的关键部分。为了描述这一问题，我们引 入以下引理： 引理2 3 1 ：如果项目集x 是频繁项目集，则x 的任一子集必定也是频繁 项目集；反过来说，如果x 的任一子集不是频繁项目集，则x 肯定不是频繁项 目集。 由该引理，我们就得到求频繁项目集的方法： ( 1 ) 先生成长度为1 的频繁项目集，记为l 1 】。 ( 2 ) 在l 【k 】的基础上生成候选项目集( c a n d i d a t ei t e m s e t ) c k + l 】，要求 候选项目集的所有的子集均为频繁项目集。 ( 3 ) 扫描事务数据库d ，计算每个候选项目集的支持度，如果大于m i n s u p ， 则加入到l k + l 】中( l 【k + 1 初始为空集) 。 ( 4 ) 如果l k + 1 为空集，则结束，所求结果即为l 1 】y l 2 】y ；否则转2 ， 继续。 2 4 a p r io ri 算法 a p r i o r i 是a g r a w a l 等提出的算法”1 ，其求频繁项目集是通过迭代方法，先 生成较小的频繁项目集l e k ，由它产生较大的侯选频繁集c k + l 】，再查询事务 数据库，以确定哪些侯选项目集是频繁的，如此反复，直到无法生成候选集为 止。 a l g o r i t h m ：a p r i o r i i n p u t ：( 1 ) 格式为( t i d ，i t e m s e t ) 的事务数据库d ，其中t i d 为事务标识符， i t e m s e t 为该事务所对应项目集； ( 2 ) 用户最低支持m i n _ s u p ； 山东大学硕士学位论文 o u t p u t ：所有的频繁项目集； b e g i n 1 ) l 1 = f i n d f r e q u e n t _ 1 i t e m s e t s ( d ) ； 2 ) f o r ( k = 2 ；l k i 中；k + + ) 3 ) c k = a p r o i g e n ( l k 一1m i n s u p ) ； 4 )f o re a c ht r a n s a c t i o nt d s c a ndf o rc o u n t s 5 ) c t = s u b s e t ( c k ，t ) ；h g e t t h es u b s e t so f tt h a ta r ec a n d i d a t e s 6 )f o re a c hc a n d i d a t ec c t 7 ) c c o u n t + + ； 8 ) 9 ) l k = c c k l c c o u n t m i n s u p ) 1 0 ) ) 1 1 、r e t u r n l = u k l k e n d 其中，a p r i o r i - g e n 是以频繁( k 一1 ) - 项目序列集l 。为自变量的候选生成函数t 该函数返回所有频繁k 项目集的超集，分链接和修剪两步执行： ( 1 )链接o o i n ) 1 ) f o re a c hi t e m s e tl l l k 1 2 1f b re a c hi t e m s e t1 2 l k i 3 )i f ( 1 l 1 = 1 2 1 ) 八( 1 1 1 2 = 1 2 1 2 】) 八八( 1 1 【k 2 】。1 2 k 一2 】) ( i l k - 1 1 ) 的支持度时，我们仅需要对数据库中频 繁( k - 1 ) 一项目集的信息进行访问即可，而随着k 的增大，频繁( k 1 ) 项目集的数 目不断减小，因此我们需要访问的数据量在不断减小。另外，在计算侯选项目 集的支持度时，我们避免了模式匹配。这样使得改进的算法提高了速度。 下面对新数据库的结构及包含侯选项目集的事务的确定进行描述： 定义2 5 1 给定项目集1 和交易数据库d ，垂直数据库d 为 x ，m ) ，其 中x c i ，m 2 刀d 。，刀d ：，刀d 。) ，d 中t i d 为刀d ，( j 2 1 ，2 ，n ) 的事务包含项目集x 。 推论2 5 2 给定项目集a 2 ( f 。，f ：，f ，f 。) 和项目集b 。( i ，f ：，f 。，f 。) ， m 。和m 。分别为包含项目集a 和b 的事务标识符集，由项目集a 与b 组成 的侯选项目集a b 2 ( f 。，f ：，f 。，f ，f 。) 的事务标识符集m 。= m 。im 。 这是因为如果一个事务包含项目集a 和b ，即该事务同时包含项目集 ( f ，f ：，f 。，f 。) 和( f 。，f ：，f 。，f 。) ，那么它必定包含项目集( f 。，i ：，f 。，f 。，f 。) ，它 即为项目集a 与b 组成的候选项目集，因此项目集a 和b 的事务标识符集中 相同的事务标识符对应的事务即为包含侯选项目集a b 的的事务，这就是我们 发现频繁项目集及其支持度的方法。 从上面的分析我们知道，垂直数据结构由项目及包含该项目的事务标识符 构成。这种数据结构不存在水平数据库的问题，其原因主要是： ( 1 ) 频繁项目集的发现可通过数据库查询操作得到 如识别由项目集a 与b 组成的侯选项目集a b 是否为频繁项目集时， 我们通过计算项目a 的事务集与项目b 的事务集中相同事务的个数来得到 2 山东大掌硕士学位论文 项目集a b 的支持度，避免模式匹配。 ( 2 ) 对整个数据库只需访问一次 只开始时要对整个数据库进行访问，当k 1 时，计算r 。中侯选项目集 的支持度时，我们只需对频繁( k 1 ) 项目集，进行访问即可。而且随着k 的增大，频繁( k 1 ) 项目集在不断减小，这样算法访问的数据量不断减小。 假设支持度为o 5 ，下图说明了利用项目事务对应关系数据库进行挖掘的 过程，首先我们对数据库中的每一个项目，我们搜索其事务列表，以确定其支 持度，这样我们就得到频繁1 项目集l 1 ，不满足最低支持的项目的数据将不参 加下一循环的计算；由l 1 我们可得到侯选2 项目集c 2 ，在计算c 2 中侯选项 目集的支持时，我们不需对整个数据库进行访问，只需对频繁1 项目集l l 进 行访问即可，显然每循环之后，我们访问的数据库都在减小。 另外，在识别频繁项目集时，我们也不需要对整个数据库进行访问，而只 需要对数据库中该项目集的两个子集的事务列表数据进行访问即可，如计算侯 选集a b 时，我们只需取出项目a 、b 的事务列表数据即可，对候选集b c e ， 我们只需取出其两个子集b c 、b e 的事务列表即可。以图2 1 的数据为例，图 2 3 说明了改进算法的挖掘过程。 abce 圈1 0 1 圉1 0 2 圉1 0 1l 剑l 划 1 0 2 1 0 3 1 0 4 频繁1 项目集l 1 c a n d i d a t ei t e m s e t a b a c a e b c b e c e 侯选2 项目集c 2 山东大学硕士学位论文 a cb cb e c e 圈1 0 1 圈1 0 2 圈1 0 2 圈1 0 2 频繁2 项目集l 2 侯选3 项目集c 3 b c e 圈 频繁3 项目集l 3 图2 3 在项目事务对应数据库中的挖掘过程 从图2 3 的挖掘过程我们可以发现，我们需访问的数据量在不断减小。改 进的算法适合于处理平均包含项目较多的事务数据集。 2 5 2 改进的算法 a l g o r i t h m ：a p r i o r i n e w i n p u t ：( 1 ) 格式为( t i d ，i t e m s e t ) l 拘事务数据库d ，其中t i d 为事务标识符， i t e m s e t 为该事务所对应项目集； ( 2 ) 用户最低支持r a i n s u p ； o u t p u t ：所有的频繁项目集； b e g i n fg e n f l ( r a i n s u p ) k = 1 d ow h i l ei l k 1 频繁项目集的项目数递增 b e g i n 1 4 山东大学硕士学位论文 k + + f _ g e n f ( k 一1 ，m i n s u p ) e n d e n d 其中fg e n f l 为产生1 - 频繁项目集的函数，它首先对事务数据库d 进行转 换，得到项目事务对应关系数据库。然后在转换后的数据库中通过数据库查询 操作得到所有项目的支持度，将满足条件的项目加入频繁集中，将不满足条件 的项目的所有信息从转换后的数据库中删除。 a l g o r i t h m ：f g e n f l i n p u t ：( 1 ) 格式为( t i d ，i t e m s e t ) 的事务数据库d ，其中t i d 为事务标识符， i t e m s e t 为该事务所对应项目集； ( 2 ) 用户最低支持度m i n s u p ； o u t p u t ：所有的1 - 频繁项目集，项目事务对应关系数据库； b e g i n f o ra l lt r a n s a c t i o nti ndd o f o ra l li t e m1 一i t e mi nt i t e m s e td o d = d u ( 1 _ i t e m ，一t r a n s ，1 ) ； f o ra l li t e ml i t e r nd o l e tl _ cb en u m b e ro fr e c o r di nd w h e r ei t e m s e t 一一i t e m l _ s u p p o r t ；1 一c i c o u n t i f l _ s u p p o r t 2m i n _ s u p t h e n l i = l 1 u ( 1 _ i t e m s ，l s u p p o r t ，1 ，0 ，l - i t e m s ) ； e l s e m o v er e c o r df r o md w h e r ei t e m s e t 2 l _ i t e m ； e n d 在产生了1 频繁项目集之后，通过迭代逐渐生成更长的频繁项目集，这 一步是在函数f _ _ g e n f 中完成。 a l g o r i t h m ：f _ _ g e n f i n p u t ( 1 ) 项目事务对应关系数据库； ( 2 ) 用户最低支持度m i n s u p ： o u t p u t ：所有的( k + 1 ) - 频繁项目集； 山东大掌硕士学位论文 b e g i n l _ b l o e k = 0 ； f o ra l lk - i t e m s e t1 一s e tli nf r e q u e n ti t e m s e tl k - 1 l _ u l o c k + + ； f o ra l lk - i t e m s e t 1 一s e t 2 i nl k 一1t h a t ( 1 一s e t l b l o c k2 l s e t 2 b l o c ka n dl s e t l t a i l 2m i n s u pt h e n l k = l k u ( 1 _ i t e m s e t ，1 一s u p p o r t ，k ，l b l o c k ，l s e t 2 t a i l ) ； f o ra l lt r a n s a c t i o ni ti nsd o d - d u ( 1 一i t e m s e t ，l j ，k ) ； e n d i f ) e n d 算法中的侯选集的产生采用了新方法，我们的办法是在产生频繁项目集时 为具有相同前缀的频繁项目集给定一相同的段号”1 。因此候选集也就在段号相 同的频繁集中产生，加快了侯选集的产生。 初始时，我们将频繁1 项目集( 按字典排序) 的段号均设为0 ，表明任意 两个项目可以组成一个长为2 的侯选项目集。对同一段内的项目集( 按字典排 序) ，我们取最前的项目集，所有跟它组成的侯选项目集的段号均相同，组成侯 选集的前一项目集发生改变，段号就加一。 例如l i = “a ) ， b ， c ) ， e ) ，先取a ，生成( a b ) ， a c ) ， a e ，它 们的段号为1 ，之后选b ，段号加l ，这样生成的侯选集的段号就为2 ，下表说 明了这一方法的计算结果。 1 6 f 项目 abce 1i集 i 段号 o0 o0 l 山东大学硕士学位论文 絮 a ba ca eb cb ec el 段号 lll223 l 另外，在算法的实现中，我们不是先生成所有的侯选项目集，再确定频繁 项目集，而是生成一个候选项目集后就计算其频繁度，减少内存占用，提高算 法的效率。 2 6 小结 在本章我们对关联规则挖掘问题进行了介绍，对关联规则挖掘问题作了形 式化描述，对a p r i o r i 算法进行了分析，针对该算法的缺点，我们提出改进算法 a p r i o r in e w ，该算法避免了模式匹配，其所需访问的数据库是不断减小，从而 提高了算法的运行速度。 3 频繁情节知识发现算法 3 1 引言 许多应用的数据由事件序列组成，考察一个事件序列( e ，t ) ，其中e 为事 件类型，t 为该类型的事件发生时间。电信告警就是这种形式的数据。图3 1 就 是一个事件序列的例子。其中a ，b ，c ，d ，e 和f 为事件类型，它对应着电 信网络的不同告警类型，它4 1 被标在一个时间簇上。表明事件类型在不同时间 的出现情况。 edfabcefcdb adcefcbe aecfad t i m e 图3 1 ：事件的序列 分析该事件序列的基本目的是为了找到频繁情节，即频繁地在一起出现的 事件集合。例在图3 1 的事件序列中，情节“e 后面跟着f ”出现了多次，即使 我们在很小的时间片上观察该序列也是如此。情节通常是事件的偏序集合，如 图3 1 ，当a 和b 出现时，很快c 会出现。这些频繁情节体现的是告警发生的 规律，这种规律可用于电信网络故障管理，如解释发生告警的原因，预测故障 等。本章将研究事件序列数据的挖掘，以发现其中的频繁情节。 3 2 事件序列及情节 我们的最终目标是通过分析事件序列，从中找出多次重复出现的事件组 合，即我们所说的频繁情节，下面我们首先介绍几个基本概念。 定义3 2 1 ：给定一个事件类型的集合e ，事件是一个形如( a ，t ) 的二元组， 山东大学硕士学位论文 其中a e ，t 为一个整数，它对应为事件的发生时间。 定义3 2 2 ：给定一个事件类型的集合e ，事件序列是e 上的三元组 ( s ，t s ，t e ) ，其中s 是有序的事件集合s = ( ( 4 。，t ) ，( 4 ：，t ：) 。，( 4 。，f 。) ) ，a ，e ( i 21 t on ) ，f ，f ( ) ( i 2 1t on 一1 ) ，t ，t ， r 。( i 2 1 n ) ，t 。 丁。，t 。是事 件序列的起始时间，t 。是事件序列的结束时间。 e df abcefcdb adcefcbeaecfad 3 0“3 5 一。4 04 55 05 56 06 57 0 t i m e 图3 2 ：标有两个长度为5 的窗口的事件序列 例如在图3 2 中，事件序列s = ( s ，2 9 ，7 0 ) ，其中：s = ( ( e ，3 1 ) ，( d ，3 2 ) ， ( f ，3 3 ) ，( a ，3 5 ) ，( b ，3 8 ) ，( a ，7 0 ) ) 在事件的序列上观察发生时间在2 9 到7 0 之间的事件发现，发生时间在区 间【2 9 ，7 0 ) 上的所有事件都记录在事件序列s 中，其中( e ，3 1 ) 为事件，e 为事 件类型，3 l 为事件发生的时间。 定义3 2 3 ：情节( e p i s o d e s ) a 是一个三元组( v ，s ，g ) ，其中v 是节点集， 是v 上的偏序关系，g 为节点到事件类型的映射( g ：v - ) e ) 。如果 v x , y ，0 y ) ，石甚y ( x ，y 间不存在严格的偏序关系) ，那么称情节a 为并行的 ( p a r a l l e d ) ；如果地，y ( x y ) ，x y 或y x ( x ，y 间存在严格的偏序关系) ，那么 称情节a 为串行的( s e r i a l ) ；否则，称情节a 为混合情节。 图3 3 ：情节，b ，y 例在图3 _ 3 中的情节d = ( v ，曼，g ) ，节点集v 包含两个节点，分别记为x 和y ，映射g 则表示节点与事件的对应，如图示，g ( x ) = e ，g ( y ) = f ，假设事件e 在事件f 之前发生，则有节点x 先于节点y ，我们将之记为x 1 ，2 ，n ) ， 使得h v ，有：g ( x ) 2 a 、，且对于v 中觇y 的两个节点x ，y ，当x y 时， 有：如 如，我们就称情节a 在事件序列s 中出现。 例图3 3 的情节q 、0 、y ，我们观察图3 2 的事件的序列的时间区间 3 5 ，4 0 ) ，在这一区间上包含的事件有a 、b 、c 、e ，并且可发现情节t 3 、y 在 该区间上出现，而a 没有在该区间上出现。 在分析事件序列时，我, f f 关心的是在一起出现的事件，为了定量描述一起 出现这一特性，h e i k k im a n n i l a 6 , 10 提出滑动窗口的概念，情节中的所有事件要 在同一时间窗口中出现才说明该情节在该时间窗口中出现，也就是说，对该窗 口而言情节中的事件是在一起出现的。这样就可以通过调整时间窗口的大小来 限制情节中的事件在出现时间上的相近程度。 定义3 2 6 ：时间窗口w = ( m ，f 。，t 。) ，其中t ， t ，n l 由事件序列 s 中的事件( a ，t ) 组成，t s f t o , ( f 。一f 。) 就是时间窗1 2 的宽度，记作w i d t h ( w ) 。 给定事件序列s 和整数w i n ，事件序列s 上w i d t h ( w ) = w i n 的所有窗口的集合记 作w ( s ，w i n ) 。 通过窗口的定义，我们知道第一个窗口仅包含事件序列的第一个时间点， 最后一个窗口仅包含事件序列的最后一个时间点。给定事件序列s = ( j ，t s ，t e ) 1 9 山东大学硕士学位论文 和时间窗口的宽度w i n ，不难计算事件序列中的窗口数为死一n + w i n + 1 。 在分析事件序列时，我们另外要关心的是情节的频繁情况，我们只对频繁 情节感兴趣。只有当情节在事件序列中出现足够多次，我们才说该情节是频繁 的。我们是用频繁度来来描述情节在事件序列中出现的频繁情况，给定一个阀 值c ，事件序列中包含情节的窗口数与事件序列所包含的窗口数之比大于c 时， 该情节才是频繁的。 给定一个事件序列s 和一个窗口宽度w i n ，情节a 在事件序列s 中出现的 频繁度为： f r ( a ，s ，w i n ) = l w w ( s ，w i n ) l a 在w 中出现 i i w ( s ，w i n ) i 频繁情节挖掘算法的基本思想与关联规则挖掘算法相同，首先确定长度为 1 的候选情节集，记之为候选1 - 情节集r 。，接着根据实际事件序列计算各个候 选情节的出现频繁度，形成频繁l - 情节集l ，然后用l 。生成候选2 - 情节集c ：， 接着根据实际事件序列计算各个候选情节的出现频繁度，形成频繁2 情节集 正，如此反复执行到没有新的候选情节产生时为止。 3 3 相关工作 对于事件数据，h e i k k im a n n i l a 1 0 , 1 1 , 1 2 , 1 3 , 1 4 等人首先提出在事件序列中的 频繁情节发现。该技术利用滑动窗口来指定事件在时间上的相邻程度并发现事 件序列中事件间在时间上的偏序关系，其发现的规则为： i fe v e n ta e v e n tb t h e ne v e n tc w i t h 【w 】c o n f ( c ) f r e q ( f ) 该规则体现了情节发生的规律，其意思是如果事件e v e n ta 和e v e n tb 在时