序列模式挖掘在网络告警中的应用研究
|
摘要
随着网络规模不断扩大,网络结构日益复杂,如何保证网络高效、稳定运行,已经成为网络管理的重要问题。正确的网络告警相关性分析可以提高网络管理效率,辅助网络管理人员过滤无关告警,删除冗余告警,定位和预测网络故障。
本文将序列模式挖掘方法应用到网络告警分析中,研究基于频繁模式增长的告警序列模式挖掘,以及网络情景规则更新挖掘等重要问题,本文研究重点及其研究成果主要体现在以下几方面:
1、数据预处理对数据后续挖掘效率以及挖掘结果影响很大,本文针对告警数据特点,研究并设计告警数据预处理模型,能够将冗余、含噪音的原始告警数据转化为适合序列模式挖掘的告警序列数据库。
2、深入分析基于频繁模式增长的告警挖掘算法—FSPM-FP,针对其存在的告警序列偏序关系难确定的问题,提出一种改进的模式树构造方法,同时修改告警挖掘过程,降低了树的存储空间。
3、针对目前告警序列选择条件单一(支持度和置信度)情况,提出一种带拓扑关系判断的网络情景规则挖掘算法—MNER-TP,算法引入告警序列拓扑关系判断,可过滤掉频繁但相关性小的告警序列,只保留频繁又相关性大的告警序列,提高了挖掘结果精度。
4、在分析基于频繁模式更新挖掘算法基础上,研究基于顺序模式的告警更新挖掘算法,对所有告警采用统一排序,能够减少模式树更新过程中频繁的节点交换操作,以此提高更新效率;最后分别给出了支持数和数据变化两种情况的更新挖掘方法。
As the network becomes large scale and its construction goes complex, it has become an important problem how to ensure the network run with high-effect and stabilization. Alarm correlation analysis is key issue for network management, which can assist network administrators filter useless alarm, delete redundancy alarm, orientate and forecast network fault, improves the efficiency of network management.
In this thesis, we apply sequence pattern mining technology to network alarm correlation analysis and study alarm sequence pattern mining based on frequent pattern growth and network episode rules update etc important issues. The research and innovation are described in details as follows:
1、Data pretreatment has deep influence on mining efficiency and result. Aming at the character of alarm data, we bring forward a data pretreatment model for translating the redundancy and noise original alarm data into alarm sequence database that is suitable for sequence pattern mining.
2、Analyse alarm mining algorithm-FSPM-FP deeply which based on frequent pattern growth, owing to the problem of alarm sequence partial order doubtfully, an modification method for pattern tree construction is presented. At the same time, we also make some modifications in mining process, it can not only resolve this problem, moreover memory space of tree is been reduced.
3、To deal with the problem that the single support-confidence condition to select frequent alarm sequence modes, bring forward a new mining algorithm-MNER-TP which based on network topology relationship. Due to the algorithm introduce the judgement of alarm sequence topology relationship, so it can filte high frequence but less relativity, and reserve high frequence and much more relativity alarm sequences, improve the precise of mining result.
4、Research the updata frequent sequence pattern mining algorithm, then we bring forward an alarm update mining algorithm based on order pattern tree. It adopt an unification order for all the alarms so as to improve the efficiency of updating, which can avoid exchanging nodes continually in mining process.The algorithm is able to deal with support count change and alarm data renovate two kinds condition.
本文将序列模式挖掘方法应用到网络告警分析中,研究基于频繁模式增长的告警序列模式挖掘,以及网络情景规则更新挖掘等重要问题,本文研究重点及其研究成果主要体现在以下几方面:
1、数据预处理对数据后续挖掘效率以及挖掘结果影响很大,本文针对告警数据特点,研究并设计告警数据预处理模型,能够将冗余、含噪音的原始告警数据转化为适合序列模式挖掘的告警序列数据库。
2、深入分析基于频繁模式增长的告警挖掘算法—FSPM-FP,针对其存在的告警序列偏序关系难确定的问题,提出一种改进的模式树构造方法,同时修改告警挖掘过程,降低了树的存储空间。
3、针对目前告警序列选择条件单一(支持度和置信度)情况,提出一种带拓扑关系判断的网络情景规则挖掘算法—MNER-TP,算法引入告警序列拓扑关系判断,可过滤掉频繁但相关性小的告警序列,只保留频繁又相关性大的告警序列,提高了挖掘结果精度。
4、在分析基于频繁模式更新挖掘算法基础上,研究基于顺序模式的告警更新挖掘算法,对所有告警采用统一排序,能够减少模式树更新过程中频繁的节点交换操作,以此提高更新效率;最后分别给出了支持数和数据变化两种情况的更新挖掘方法。
As the network becomes large scale and its construction goes complex, it has become an important problem how to ensure the network run with high-effect and stabilization. Alarm correlation analysis is key issue for network management, which can assist network administrators filter useless alarm, delete redundancy alarm, orientate and forecast network fault, improves the efficiency of network management.
In this thesis, we apply sequence pattern mining technology to network alarm correlation analysis and study alarm sequence pattern mining based on frequent pattern growth and network episode rules update etc important issues. The research and innovation are described in details as follows:
1、Data pretreatment has deep influence on mining efficiency and result. Aming at the character of alarm data, we bring forward a data pretreatment model for translating the redundancy and noise original alarm data into alarm sequence database that is suitable for sequence pattern mining.
2、Analyse alarm mining algorithm-FSPM-FP deeply which based on frequent pattern growth, owing to the problem of alarm sequence partial order doubtfully, an modification method for pattern tree construction is presented. At the same time, we also make some modifications in mining process, it can not only resolve this problem, moreover memory space of tree is been reduced.
3、To deal with the problem that the single support-confidence condition to select frequent alarm sequence modes, bring forward a new mining algorithm-MNER-TP which based on network topology relationship. Due to the algorithm introduce the judgement of alarm sequence topology relationship, so it can filte high frequence but less relativity, and reserve high frequence and much more relativity alarm sequences, improve the precise of mining result.
4、Research the updata frequent sequence pattern mining algorithm, then we bring forward an alarm update mining algorithm based on order pattern tree. It adopt an unification order for all the alarms so as to improve the efficiency of updating, which can avoid exchanging nodes continually in mining process.The algorithm is able to deal with support count change and alarm data renovate two kinds condition.
引文
[1]R.Cronk,P.Callahan,and L.Bemstein.Rule-Based Expert Systems for Network Management and operations:an Introduction[J].IEEE Network,1988,2(5):7-21.
[2]Harrison,K.A.INCL,Hewlett-Packard(Bristol)Labs.Event Correlation in Telecommunication Network Management.1994.9.
[3]Lewis,L.A.Case-Based Reasoning Approach to the Management of Faults in Communication Networks[C].Proceeding IEEE Infocom' 93,vol.3.San Francisco 1993:114-120.
[4]Malheiros Meira D,Mareos Silva NogueiraJ.Modelling a Telecommunication Network for Fault Management Applications Network Operations and Management Symposium[C],NOMS 1998(3):723-732.
[5]Bums,L.,Hellerstein,J.L.,Ma,S.,Perng,C.S.,Rabenhorst,D.A.,Taylor,D.J.Towards Discovery of Event Correlation Rules[C].In IFIP/IEEE International Symposium on Integrated Network Management,Seattle,WA,USA 2001:345-359.
[6]Mannila H,Toivonen H,Vekramo Al.Disocvey of frequent episodes in event sequenecs[J].Data Mining and Knowledge Discovery,1997(1):259-289.
[7]刘康平,李增智.网络告警序列中的频繁情景规则挖掘算法[J].小型微型计算机系统.2003,24(5):891-894.
[8]王新苗,晏蒲柳,黄天锡.网络管理告警数据库中时序规则挖掘的一种新方法[J].小型微型计算机系统.2001,22(11):1311-1314.
[9]徐前方,阚建杰,李永春等.一种具有时序特征的告警关联规则挖掘算法[J].微电子学与计算机.2007,24(3):23-26.
[10]单莘,朱永宣,郭军.电信网告警数据库中的增量式挖掘技术研究[J].计算机应用研究.2006(3):257-260.
[11]单莘.基于知识发现的告警相关性分析关键问题研究[D].北京邮电大学,2006.
[12]史忠植.知识发现[M].清华大学出版社,2002:2-7.
[13]Manganaris.A data mining analysis of RTID alarms.computer networks[J].2000,34(4):571-577.
[14]Jeawei Han,Micheline Kamber著.数据挖掘概念与技术[M].范明,孟小峰等译.北京:机械工业出版社,2006.
[15]Hand,D.数据挖掘原理[M],张银奎译.北京:机械工业出版社,2005.05.
[16]R.Agrawal,R.Srikant.Mining Sequential Patterns[A].In:11th Int.Conf.on Data Engineefing,Taipei,Taiwan,1995.
[17]陶再萍,俞瑞钊.序列模式增量式更新的快速算法[J].计算机应用.2006,26(12).
[18]陆介平,刘月波,倪巍伟等.基于投影数据库的序列模式挖掘增量式更新算法[J].东南大学学报(自然科学版).2006,36(3):457-462.
[19]R.Srikant,R.Agrawal.Mining Sequential Patterns:Generalizations and Performance Improvements[A].In:5th Int.Conf.Extending Database Technology,Avignon,France,1996:3-17.
[20]M.Zaki.SPADE:An Efficient Algorithm for Mining Frequent Sequences[J].Machine Learning,2001,42(1):31-60.
[21]戴新喜,白似雪.一种高效的基于模式矩阵的Apriori改进算法[J].广西师范大学学报(自然 科学版).2007,25(4):176-179.
[22]J.Pei,J.Han,H.Pinto,et al.PrefixSpan:Mining Sequential Patterns Efficiently by Prefix-projected Pattern Growth[A].Proc.of the 17th Int.Conf.on Data Engineering,Heidelberg,Germany,2001:215-224.
[23]Ming-Yen Lin,Suh-Yin Lee.Efficient mining of sequential patterns with time constraints by delimited pattern growth[J].Knowledge and Information Systems.2005,7:499-514.
[24]Jian Pei,Guozhu Dong,Wei Zou,et al.Mining Condensed Frequent-Pattern Bases[J].Knowledge and Information Systems.2004(6):570-594.
[25]陈健美,宋顺林,朱全玉等.频繁序列模式更新算法[J].江苏大学学报(自然科学版).2007,28(3):250-253.
[26]Jia-Dong Ren,Xiao-Lei Zhou.A New Incremental Updating Algorithm for Mining Sequential[J].Journal of Computer Science.2006,2(4):318-321.
[27]Ben Kao,Minghua Zhang,Chilap Yip,et al.Efficient Algorithms for Mining and Incremental Update of Maximal Frequent Sequences[J].Data Mining and Knowledge Discovery.2005(10):87-116.
[28]宗俊省.基于约束的序列模式挖掘算法的研究[D].燕山大学,2006.
[29]张坤.基于关联规则的数据挖掘在电信告警中的应用[D].电子科技大学,2006.
[30]王伟,芦东昕,唐英.基于专家系统的网络故障管理系统的设计[J].计算机工程与设计.2005,26(11):3031-3033.
[31]Pyle D.Data Preparation for Data Mining[M].Morgan Kaufmann Publishers Inc,San Francisco,CA,1999.
[32]Rahm,E.,Do,H.H.Data cleaning:problems and current approaches[J].IEEE Data Engineering Bulletin,2000,23(4):3-13.
[33]朱振华.分布式关联规则在电信告警相关性分析中的应用[D].电子科技大学,2007.
[34]徐前方.基于数据挖掘的网络故障告警相关性研究[D].北京邮电大学,2007.
[35]端义峰,胡谷雨,丁力.序列模式挖掘在网络告警分析中的应用[A].2004年全国通信软件学术会议论文集[C],2004.
[36]孙蕾,朱玉全.频繁序列模式挖掘中关键技术的研究[J].计算机工程,2006,32(11):95-99.
[37]Ann Devitt,Joseph Duffin,Robert Moloney.Topographical Proximity for Mining Network Alarm Data[A].Joint International Conference on Measurement and Modeling of Computer Systems.2005:179-184.
[38]Jia-Wei Han,Jian Pei,Yi-Wen Yin,et al.Mining Frequent Patterns without Candidate Generation:A frequent-Pattern Tree Approach[J].Data Mining and Knowledge Discovery,2004(8):53-87.
[39]Cheung W,Zaiane OR.Incremental.mining of frequent patterns without candidate generation or support constraint[J].Proceedings of the IDEAS,2003.2003:111-116.
[40]KohJ-L,ShiehS-F.An efficient approach for maintaining association rules based on adjusting FP-tree structures[J].Proceedings of the DASFAA 2004.2004,417-424.
[41]Carson Kai-Sang Leung,Quamrul I.Khan,ZhanLi,et al.CanTree:a canonical-order tree for incremental frequent-pattern mining.Knowledge and Information Systems.2007,11(3):287-311.
[42]朱天,白似雪.基于模式距离度量的时间序列相似性搜索[J].微计算机信息,2007,23(10-3):216-217.
[2]Harrison,K.A.INCL,Hewlett-Packard(Bristol)Labs.Event Correlation in Telecommunication Network Management.1994.9.
[3]Lewis,L.A.Case-Based Reasoning Approach to the Management of Faults in Communication Networks[C].Proceeding IEEE Infocom' 93,vol.3.San Francisco 1993:114-120.
[4]Malheiros Meira D,Mareos Silva NogueiraJ.Modelling a Telecommunication Network for Fault Management Applications Network Operations and Management Symposium[C],NOMS 1998(3):723-732.
[5]Bums,L.,Hellerstein,J.L.,Ma,S.,Perng,C.S.,Rabenhorst,D.A.,Taylor,D.J.Towards Discovery of Event Correlation Rules[C].In IFIP/IEEE International Symposium on Integrated Network Management,Seattle,WA,USA 2001:345-359.
[6]Mannila H,Toivonen H,Vekramo Al.Disocvey of frequent episodes in event sequenecs[J].Data Mining and Knowledge Discovery,1997(1):259-289.
[7]刘康平,李增智.网络告警序列中的频繁情景规则挖掘算法[J].小型微型计算机系统.2003,24(5):891-894.
[8]王新苗,晏蒲柳,黄天锡.网络管理告警数据库中时序规则挖掘的一种新方法[J].小型微型计算机系统.2001,22(11):1311-1314.
[9]徐前方,阚建杰,李永春等.一种具有时序特征的告警关联规则挖掘算法[J].微电子学与计算机.2007,24(3):23-26.
[10]单莘,朱永宣,郭军.电信网告警数据库中的增量式挖掘技术研究[J].计算机应用研究.2006(3):257-260.
[11]单莘.基于知识发现的告警相关性分析关键问题研究[D].北京邮电大学,2006.
[12]史忠植.知识发现[M].清华大学出版社,2002:2-7.
[13]Manganaris.A data mining analysis of RTID alarms.computer networks[J].2000,34(4):571-577.
[14]Jeawei Han,Micheline Kamber著.数据挖掘概念与技术[M].范明,孟小峰等译.北京:机械工业出版社,2006.
[15]Hand,D.数据挖掘原理[M],张银奎译.北京:机械工业出版社,2005.05.
[16]R.Agrawal,R.Srikant.Mining Sequential Patterns[A].In:11th Int.Conf.on Data Engineefing,Taipei,Taiwan,1995.
[17]陶再萍,俞瑞钊.序列模式增量式更新的快速算法[J].计算机应用.2006,26(12).
[18]陆介平,刘月波,倪巍伟等.基于投影数据库的序列模式挖掘增量式更新算法[J].东南大学学报(自然科学版).2006,36(3):457-462.
[19]R.Srikant,R.Agrawal.Mining Sequential Patterns:Generalizations and Performance Improvements[A].In:5th Int.Conf.Extending Database Technology,Avignon,France,1996:3-17.
[20]M.Zaki.SPADE:An Efficient Algorithm for Mining Frequent Sequences[J].Machine Learning,2001,42(1):31-60.
[21]戴新喜,白似雪.一种高效的基于模式矩阵的Apriori改进算法[J].广西师范大学学报(自然 科学版).2007,25(4):176-179.
[22]J.Pei,J.Han,H.Pinto,et al.PrefixSpan:Mining Sequential Patterns Efficiently by Prefix-projected Pattern Growth[A].Proc.of the 17th Int.Conf.on Data Engineering,Heidelberg,Germany,2001:215-224.
[23]Ming-Yen Lin,Suh-Yin Lee.Efficient mining of sequential patterns with time constraints by delimited pattern growth[J].Knowledge and Information Systems.2005,7:499-514.
[24]Jian Pei,Guozhu Dong,Wei Zou,et al.Mining Condensed Frequent-Pattern Bases[J].Knowledge and Information Systems.2004(6):570-594.
[25]陈健美,宋顺林,朱全玉等.频繁序列模式更新算法[J].江苏大学学报(自然科学版).2007,28(3):250-253.
[26]Jia-Dong Ren,Xiao-Lei Zhou.A New Incremental Updating Algorithm for Mining Sequential[J].Journal of Computer Science.2006,2(4):318-321.
[27]Ben Kao,Minghua Zhang,Chilap Yip,et al.Efficient Algorithms for Mining and Incremental Update of Maximal Frequent Sequences[J].Data Mining and Knowledge Discovery.2005(10):87-116.
[28]宗俊省.基于约束的序列模式挖掘算法的研究[D].燕山大学,2006.
[29]张坤.基于关联规则的数据挖掘在电信告警中的应用[D].电子科技大学,2006.
[30]王伟,芦东昕,唐英.基于专家系统的网络故障管理系统的设计[J].计算机工程与设计.2005,26(11):3031-3033.
[31]Pyle D.Data Preparation for Data Mining[M].Morgan Kaufmann Publishers Inc,San Francisco,CA,1999.
[32]Rahm,E.,Do,H.H.Data cleaning:problems and current approaches[J].IEEE Data Engineering Bulletin,2000,23(4):3-13.
[33]朱振华.分布式关联规则在电信告警相关性分析中的应用[D].电子科技大学,2007.
[34]徐前方.基于数据挖掘的网络故障告警相关性研究[D].北京邮电大学,2007.
[35]端义峰,胡谷雨,丁力.序列模式挖掘在网络告警分析中的应用[A].2004年全国通信软件学术会议论文集[C],2004.
[36]孙蕾,朱玉全.频繁序列模式挖掘中关键技术的研究[J].计算机工程,2006,32(11):95-99.
[37]Ann Devitt,Joseph Duffin,Robert Moloney.Topographical Proximity for Mining Network Alarm Data[A].Joint International Conference on Measurement and Modeling of Computer Systems.2005:179-184.
[38]Jia-Wei Han,Jian Pei,Yi-Wen Yin,et al.Mining Frequent Patterns without Candidate Generation:A frequent-Pattern Tree Approach[J].Data Mining and Knowledge Discovery,2004(8):53-87.
[39]Cheung W,Zaiane OR.Incremental.mining of frequent patterns without candidate generation or support constraint[J].Proceedings of the IDEAS,2003.2003:111-116.
[40]KohJ-L,ShiehS-F.An efficient approach for maintaining association rules based on adjusting FP-tree structures[J].Proceedings of the DASFAA 2004.2004,417-424.
[41]Carson Kai-Sang Leung,Quamrul I.Khan,ZhanLi,et al.CanTree:a canonical-order tree for incremental frequent-pattern mining.Knowledge and Information Systems.2007,11(3):287-311.
[42]朱天,白似雪.基于模式距离度量的时间序列相似性搜索[J].微计算机信息,2007,23(10-3):216-217.