《挖掘电信告警关联模式方法.pdf》由会员分享，可在线阅读，更多相关《挖掘电信告警关联模式方法.pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、347?357.85第 2期?赵传强等:面向吞吐量效率的无线 M esh网络机会主义路由2011年 4月第 34卷 第 2期北 京 邮 电 大 学 学 报Journal of Beijing University of Posts andTelecommunicationsApr.2011Vo.l 34 No.2?文章编号:1007?5321(2011)02?0085?05挖掘电信告警关联模式方法徐前方,?肖?波,?郭?军(北京邮电大学 信息与通信工程学院,北京 100876)摘要:关联模式挖掘算法通常受到最小支持度的限制,仅能得到频繁告警序列间的关联模式,针对这一问题,基于图论思想提出了一种
2、挖掘电信网络告警间关联模式的方法.首先在单遍扫描数据库的条件下挖掘网络中的二项关联模式,然后直接发现其最大关联模式,从而避免大量中间项集的产生.基于实际网络告警数据的实验结果表明,该方法不仅具有较高的效率,而且有效.关?键?词:故障管理;告警关联;数据挖掘中图分类号:TN929?53?文献标志码:AAn Approach on Association PatternsM ining inTeleco mmunication Alarm DatabaseXU Q ian?fang,?XI AO Bo,?GUO Jun(School of Infor mation and Communicatio
3、n Eng ineering,Beijing University of Posts and Telecommunications,Beijing 100876,China)Abstract:Currently li m iting to them ini mal suppor,tthe algorithms used in alarm association rulesm in?ing are al most applied in the frequently occurring alar m events.A new algorithm based on graph theory tom
4、ine telecommunication alar m pattern is proposed.It firstm ines network?s 2?ite m s association pattern byscanning the database only once,and then gets the maxi mal association mode,so that it can avoid gener?ating lots ofm iddle ite m s.Experi ments based on the actual net work alar m data de monst
5、rate the efficiencyand the effectiveness of the algorithm.Key words:faultmanagemen;talar m association;datam ining收稿日期:2010?05?10基金项目:国家自然科学基金项目(60905017);高等学校学科创新引智计划项目(B08004);中央高校基本科研业务费专项资金资助项目(2011RC0119)作者简介:徐前方(1975?),女,讲师,博士,E?mai:l xuqf123 gmai.l com;郭?军(1959?),男,教授,博士生导师.?告警相关性分析可将多个告警事件归结
6、为较少的告警事件,过滤无意义的告警,从海量告警数据中找出故障的根本原因,准确定位故障.目前大多数研究都是基于最小支持度-最小置信度框架挖掘关联模式,如文献 1 中的贝叶斯网络方法;文献 2中的基于滑动窗口的挖掘算法.近年来,一些学者又提出了改进算法,如文献 3中采用了决策树的方法;文献 4提出的针对数据流的序列模式挖掘方法.这些算法都存在难以确定合适支持度阈值的问题.文献 5提出利用相关度挖掘告警关联规则方法;文献 6 提出挖掘极大超团模式的算法;文献 7提出基于极大团挖掘告警关联规则.这些算法都没有针对电信网络中的告警特点挖掘,效率较低.本文分析了电信网络中告警的特点,提出了挖掘告警模式(M
7、TAP,m ining telecommunication alar m pat?tern)算法.1?告警影响范围的分析定义 1?告警窗口宽度 2告警序列 s=?(a1,t1),(a2,t2),?,(an,tn)?,其中,告警类型 ai?,1?i?n,n为告警类型数,?为告警类型集合;ti(i=1,2,?,n)为告警发生时间.告警窗口 W 指告警序列 s上的一个子序列,可表示成 W=(w,ts,te),其中,ts、te分别为告警窗口的起始和结束时间;w 为告警窗口中发生的告警.告警窗口宽度为 te-ts.告警窗口宽度实质是相关告警事件的最大时间间隔,即某告警的影响范围,告警持续时间内的所有告警
8、都可能与其相关.在实际网络中,告警的清除有 3种情况:1)网管系统或设备自身检测系统发现后自动恢复;2)运维人员发现故障后清除;3)各种原因上报的无意义告警,告警持续时间较长.以文献 5中 3种告警类型为例,其告警持续时间如图 1所示.网络中告警不同,其相关窗口也不同,即使同一告警类型也有多种持续时间.因此,选择告警相关窗口时,应依据告警持续时间主要集中(如 90%)的范围.从图 1可知,告警 A、B、C的最大持续时间分别约为 10、250 和 600 s,但 大 部 分 告 警 仅持 续1(91?84%)、50(97?14%)和 300 s(97?21%),因此相关窗口应分别设为 1、50和
9、 300 s.从图 1还可见,告警的影响范围与告警类型有关,采用文献 5?7提出的挖掘算法对全网告警采用统一的相关窗口是不合理的,若窗口选取过小,会丢失相关告警信息;若选取过大,不仅会引入虚假规则,而且由于引入了无关数据,降低了算法效率.因此,为便于挖掘,可利用告警窗口宽度对告警数据库进行时间跨度的约束,即针对不同的告警设置不同的时间约束参数,告警 ai的相关窗口宽度为Wai=m in Wai+Waie-(Te-Ts)2?2,Wm ax(1)其中,Ts、Te分别为 1次告警的起始和结束时间;?为衰减常数;Wmax为最大相关窗口,其目的是为了进行最大时间跨度约束.由此可根据实际告警数据动态调整相
10、关窗口,从而避免采用单一相关窗口的问题.2?告警关联挖掘算法2?1?相关定义定义 2?告警关联模式相关度衡量 2个向量间的相关性通常采用 Pearson相关系数,如文献 5提出的关联规则挖掘算法.但实图 1?告警持续时间与告警频度关系际网络中的告警频度分布不均匀,对于大量低频度告警,其期望近似为 0,因此存在无法分析它们之间相互关系的问题.研究 2个告警向量时更注重告警是否同时发生,即告警向量在方向上是否一致,因此本文采用夹角余弦 Raiaj来衡量,有Raiaj=ai?ajaiaj=aijaiaj(2)根据统计学原理,Raiaj越大,告警的相关性越强,这样可避免以往算法中无法选取合适支持度的问
11、题.定义 3?告警关联模式置信度在支持度-置信度框架下的算法中采用的置信87第 2期?徐前方等:挖掘电信告警关联模式方法度都是针对频繁项集定义的,但其在针对频度分布不均匀的告警数据挖掘时会产生虚假规则,因此本文采用 h?置信度(ch)6方式度量,有ch(X)=s(X)max1?i?ns(ai)(3)其中,X=a1,a2,?,am(m?2)为告警关联模式;s(X)为其支持度;s(ai)为告警 ai的支持度.性质 1?反单调性:ch(a1,a2,?,ak)?ch(a1,a2,?,ak,ak+1).证明?设X1=a1,a2,?,ak,X2=a1,a2,?,ak,ak+1,显然 s(X1)?s(X2)
12、.1)若 s(ak+1)max1?i?ks(ai),则 max1?i?k+1s(ai)=s(ak+1),因此 ch(X1)ch(X2).2)若 s(ak+1)?max1?i?ks(ai),则 max1?i?k+1s(ai)=m ax1?i?ks(ai),因此 ch(X1)=ch(X2).由 1)和 2)可知 ch(X1)?ch(X2).h?置信度表明,告警关联模式之间是强相关,如 ch(X)=90%,表示若 X 中任一告警发生,则 X 中其他告警发生的概率是 90%.定义 4?最大告警关联模式对于告警关联模式 X,若每对告警之间都满足Raiaj?Rm in(最小相关度)和 ch(X)?chm
13、i n(最小置信度),且 X 的任意超集 Y不满足 Raiaj?Rmin或 ch(X)?chm in,则称 X 为最大告警关联模式.由性质 1可知,最大告警关联模式的子集均为关联模式,因此可直接挖掘最大模式.2?2?算法描述告警关联模式挖掘算法基于图论的思想,首先利用相关度和置信度产生 2项集,并由此构建告警关联图,从而直接产生 k项集.2?2?1?生成告警 2项关联模式利用相关窗口建立告警频度共现关联图.以?为图的顶点,生成集合 V=a1,a2,?,an,V?;以不同告警类型间的共现关系构成边,生成告警集合 E,边的权值为不同类型告警在窗口内同时发生的强度 eij,用邻接矩阵表示为E=e11
14、e12?e1ne21e22?e2n?en1en2?enn(4)其中,eij=?mk=1rkij(i=j)为顶点 Vi的权值,表示 ai发生的频度;eij(i?j)为顶点 Vi与 Vj间边的权值,即 ai与 aj间的共现强度.rkij=m in(fki,fkj)表示在第 k 个相关窗口内 ai与 aj的共现频度.eij(i?j)?0,表示顶点 Vi和 Vj间存在一条权值为 eij的边,即 ai和 aj共现的频度;否则边不存在.利用式(2)生成 2项告警相关集,根据统计学原理,相关系数直接反映 2个项集间的相关性.如Rm in?0?8为极强相关;0?5?Rm in 0?8为强相关;0?3?Rm i
15、n 0?5为弱相关;Rmin 0?3为不相关.因此在本算法中设 Rm i n=0?5.与文献 2?4相比,采用 MTAP算法可更加合理地选择参数.最后利用式(3)产生 2项告警关联模式.算法 1?M ine2alar mPattern()1)初始化共现强度矩阵 E和 2项关联模式集LRS2,i=1.2)扫描数据库,对任意告警 ai将其相关窗口中的告警写入 E,同时按式(1)更新其相关窗口.3)在 E中按式(2)计算 2个告警间相关度,若大于 Rm i n执行 4);否则进入 6).4)利用式(3)计算置信度,若大于 chm in执行 5);否则进入 6).5)添加到 2项关联模式 LRS2中,
16、并排序.6)i=i+1,若 i?n,执行 3);否则程序结束.在算法 1中,通过调整告警相关窗口的宽度适应实际网络的变化.另外,基于最小相关度和最小置信度挖掘 2项告警关联模式,可避免文献 2?4无法选择合适支持度的问题.与文献 5相比,减少了2次方运算,因此降低了计算复杂度.2?2?2?由 2项关联模式生成最大项集关联模式目前,生成最大项集算法及其改进算法大都采用逐项产生的方法,即要生成一个含有 k个项目的最大项集,需依次产生 1项集,2项集,?,(k-1)项集,k项集,会产生大量中间项集,算法效率不高.本文提出从 2项集直接生成 k项集的算法.定理 1?若依据告警 2项关联模式构造告警关联
17、图 G,则告警最大关联模式一定构成完全图.证明?可用归纳法证明.1)2项告警关联模式生成 2阶完全图将任意 2项告警关联模式中的 2个告警作为图的顶点 Vi和 Vj,顶点间的边为其共现强度权值 eij.根据图论的理论,若 G 的任何 2个不同顶点都是邻接的,则 G为完全图,因此必然生成 2阶完全图.88北 京 邮 电 大 学 学 报?第 34卷2)k项告警关联模式生成 k阶完全图设 k-1项告警关联模式时,定理 1成立.增加1个告警节点 Vi构成 k阶关联图 G.G 依据 2项告警关联模式产生,因此 Vi与 G 中其他顶点间有且仅有 1条边相连,则 k阶无向图为 k阶完全图.结论 1?若简单图
18、 G 为 k阶完全图,则该图边的总数为 k(k-1)/2,每个顶点的度数为 k-1.由结论 1可知,若要寻找最大告警关联模式 X,可通过挖掘其完全图 G 实现,也可分析其所有顶点的度数,即通过发现告警关联图 G 中各告警 2项关联模式数来实现.算法 2?M ineK?A lar mPattern()1)i=1,j=0,LRS2模式数为 m.2)LRS2(i)是否可与 LRS2(i+1)合并为最大模式候选项X,若可以,i=i+1,执行 2);否则进入 3).3)根据结论 1判断 X 是否为完全图,若是,则X 为最大关联模式,写入告警关联模式集 LRS,j=j+1,进入 5);否则执行 4).4)
19、利用式(3)计算 X 的 h?置信度,并判断其是否大于等于 chm in,若满足,写入 LRS,j=j+1;否则进入 5).5)i=i+1,i?m,执行 2);否则程序结束.2?3?算法有效性分析算法 1中,仅需扫描 1次数据库生成共现强度权值矩阵,然后对其进行相关度和置信度判断,则算法 1的复杂度为 O(n(n-1)/2)?O(n2).算法 2中,设最大模式数为 l,平均长度为 k,即完全图平均有 k 个节点(一般 k 10),则时间复杂度为 O(lk).由于电信网络告警间关联规则的判决依据是告警间的共现强度,这些告警可构成一个完全图,所以可采用结论 1的方法将时间复杂度最低降至 O(l).
20、3?实验及分析实验数据为某运营商连续 1个月的 79万条告警记录,将告警类型标识和告警发生、结束时间作为关键字进行挖掘.选取 3个典型的挖掘关联模式算法,即相关矩阵算法 5、h?置信度(h?confidence)算法 6和极大团挖掘算法 7,比较各算法的效率和规则数.根据统计学原理,Rmin=0?5;将文献 6?7 支持度设为 0?002.改变置信度,各算法的比较分别如图2和图 3所示.图 2?执行效率比较图 3?规则数比较图 2所示为 4种算法在不同置信度条件下的时间开销.随着置信度增加,各算法的效率都在提高.由于 h?置信度算法基于 Apriori算法 2,需多次遍历数据库,所以耗时最大;
21、MTAP算法只需扫描 1次数据库,由此产生 2项集,然后直接生成最大项集,因此时间开销最小;而其他算法需由 2项集依次递增产生最大项集,因此有大量中间项集产生.图 3所示为 4种算法在不同置信度条件下产生的规则数.随着置信度增加,各算法产生的规则数都在下降,其中 h?置信度算法产生的规则数远大于其他算法;极大团挖掘算法产生的规则数虽然比MTAP算法和相关矩阵算法多,但挖掘出的规则可能存在虚假规则.因此本文通过告警压缩比来分析告警关联规则的有效性.定义 5?告警压缩比设原告警数为 N,经告警相关性处理后的告警数为 N?,则告警压缩比为 Ccomp=N/N?.定义 5表明了经关联规则处理后的告警相对于原始告警数的减少量.例如,原始告警记录 N=100,经相关处理后剩余告警数 N?=10,则其压缩比为 Ccomp=10,表明通过挖掘算法可减少网络中 90%的告警.因此,这是89第 2期?徐前方等:挖掘电信告警关联模式方法