网络告警关联规则挖掘系统的研究与设计
|
摘要
故障诊断与定位是网络管理的核心,当网络发生故障时,要求及时找到网络发生故障的位置和原因,以便快速的排除故障,恢复网络的功能。告警相关性分析在网络故障管理中占据着重要的地位,是故障诊断的重要手段之一。数据挖掘为告警相关性分析中知识获取提供了新的途径。在现代网络中,告警的某些属性分为不同的级别,而且,不同QoS要求的业务对告警处理的程度也有所不同。本文以国家自然科学基金项目《基于数据挖掘的通信网告警相关性分析》为背景,重点研究了网络告警加权关联规则挖掘,包括告警预处理、加权关联规则挖掘、规则的后处理以及网络告警关联规则挖掘系统的仿真验证。
本文采用专家系统来完成告警的预处理。用时间窗口和滑动步长的思想解决了告警时间同步问题,将同一时间窗口内的告警看作一个告警事务,提取告警中反映网络故障的告警属性字段组成告警事务项,并用告警压缩的方法删除同一告警事务中的冗余告警信息。专家系统运用层次分析法来确定告警的权值,仿真结果表明运用该方法确定的告警权值能反映用户对不同告警的关注程度和网络的动态变化。
本文针对网络告警信息量大、告警具有突发性等特点,对已有的加权关联规则挖掘算法做了相应的改进,提出了一种基于频繁模式树的网络告警加权关联规则挖掘算法-WFPTA算法。算法的优点是无需重复多次的遍历数据库,无需递归的进行条件频繁模式树的构建。算法的性能测试结果表明:该算法在运行效率和占用内存空间上与MINWAL(O)算法相比都有很大的改善。
最后,本文基于冗余规则和结构化规则涵盖集的概念,提出了一种定量化的关联规则后处理算法。算法能够有效地删除用户给定的最小置信度增量阈值空间集内所有冗余的、信息重复的规则。
网络告警关联规则挖掘系统的仿真验证表明,该系统能够快速有效地挖掘出反映网络故障的告警关联规则,将形式简洁、信息完整的告警规则呈现给用户,对网络告警相关性分析和故障的诊断定位有一定的意义和实用价值。
Fault diagnosis and localization is the vital core of the network management. When the faults take place in the networks, it is necessary to find the locations and the causations of the faults in time in order to get rid of the faults and recover the networks’function rapidly. The alarm correlation analysis, an important approach of fault diagnosis, plays a crucial role in network fault management. Data mining provides a new approach of the knowledge updating during the alarm correlation analyzing. In modern networks, some of the alarm’s attributes has different levels, and services with different QoS requests need different treatment of alarms. With the background of the project, the alarm correlation in communication networks based on data mining, that is supported by National Natural Science Foundation of China, this thesis focused on mining weighted alarm association rules in networks, including the alarm’s pretreatment, mining weighted association rules, the rules’post-treatment and the simulation and validation of the system of mining weighted alarm association rules in networks.
The alarm’s pretreatment was carried out by expert system. The problem of alarm’s synchronization was settled by setting time window and slip length. The alarms in the same time windows were regarded as an alarm transaction. The attributes of the alarm that reflect the faults were picked out to form an item of an alarm transaction. The redundant alarms were got rid of by alarm compressing. The analytic hierarchy process was applied to deciding the weight of the alarm. The simulation result indicates that the weight decided by this method can reflect the users’concentration on different alarms and the dynamic change of the networks.
Based on the existent algorithms of mining weighted association rules, aimed at the networks’characters that are having amount of alarms that can burst out randomly, a pattern tree based algorithm-WFPTA of mining weighted alarm association rules was constructed. The big advantage of the WFPTA algorithm is it is unnecessary to traverse the database repeatedly and to construct the conditional pattern tree recursively. The performance test of the algorithm indicates that compared with MINWAL (O), this algorithm is improved in both the executive time and the used memory.
Based on the concept of redundant rules and structural rule cover, a quantificational algorithm of rule post-treatment was constructed, which can delete the whole redundant and repeated rule effectively by the minimum confidence increment threshold provided by the user.
The simulation and validation of the system of mining weighted alarm association rules in networks indicates that it can find out effective alarm rules which reflect the faults in networks rapidly. It is also validated that the system which provides the user the compact alarm rules with complete information is valuable and useful to the alarm correlation analysis and fault diagnosis and localization in networks.
本文采用专家系统来完成告警的预处理。用时间窗口和滑动步长的思想解决了告警时间同步问题,将同一时间窗口内的告警看作一个告警事务,提取告警中反映网络故障的告警属性字段组成告警事务项,并用告警压缩的方法删除同一告警事务中的冗余告警信息。专家系统运用层次分析法来确定告警的权值,仿真结果表明运用该方法确定的告警权值能反映用户对不同告警的关注程度和网络的动态变化。
本文针对网络告警信息量大、告警具有突发性等特点,对已有的加权关联规则挖掘算法做了相应的改进,提出了一种基于频繁模式树的网络告警加权关联规则挖掘算法-WFPTA算法。算法的优点是无需重复多次的遍历数据库,无需递归的进行条件频繁模式树的构建。算法的性能测试结果表明:该算法在运行效率和占用内存空间上与MINWAL(O)算法相比都有很大的改善。
最后,本文基于冗余规则和结构化规则涵盖集的概念,提出了一种定量化的关联规则后处理算法。算法能够有效地删除用户给定的最小置信度增量阈值空间集内所有冗余的、信息重复的规则。
网络告警关联规则挖掘系统的仿真验证表明,该系统能够快速有效地挖掘出反映网络故障的告警关联规则,将形式简洁、信息完整的告警规则呈现给用户,对网络告警相关性分析和故障的诊断定位有一定的意义和实用价值。
Fault diagnosis and localization is the vital core of the network management. When the faults take place in the networks, it is necessary to find the locations and the causations of the faults in time in order to get rid of the faults and recover the networks’function rapidly. The alarm correlation analysis, an important approach of fault diagnosis, plays a crucial role in network fault management. Data mining provides a new approach of the knowledge updating during the alarm correlation analyzing. In modern networks, some of the alarm’s attributes has different levels, and services with different QoS requests need different treatment of alarms. With the background of the project, the alarm correlation in communication networks based on data mining, that is supported by National Natural Science Foundation of China, this thesis focused on mining weighted alarm association rules in networks, including the alarm’s pretreatment, mining weighted association rules, the rules’post-treatment and the simulation and validation of the system of mining weighted alarm association rules in networks.
The alarm’s pretreatment was carried out by expert system. The problem of alarm’s synchronization was settled by setting time window and slip length. The alarms in the same time windows were regarded as an alarm transaction. The attributes of the alarm that reflect the faults were picked out to form an item of an alarm transaction. The redundant alarms were got rid of by alarm compressing. The analytic hierarchy process was applied to deciding the weight of the alarm. The simulation result indicates that the weight decided by this method can reflect the users’concentration on different alarms and the dynamic change of the networks.
Based on the existent algorithms of mining weighted association rules, aimed at the networks’characters that are having amount of alarms that can burst out randomly, a pattern tree based algorithm-WFPTA of mining weighted alarm association rules was constructed. The big advantage of the WFPTA algorithm is it is unnecessary to traverse the database repeatedly and to construct the conditional pattern tree recursively. The performance test of the algorithm indicates that compared with MINWAL (O), this algorithm is improved in both the executive time and the used memory.
Based on the concept of redundant rules and structural rule cover, a quantificational algorithm of rule post-treatment was constructed, which can delete the whole redundant and repeated rule effectively by the minimum confidence increment threshold provided by the user.
The simulation and validation of the system of mining weighted alarm association rules in networks indicates that it can find out effective alarm rules which reflect the faults in networks rapidly. It is also validated that the system which provides the user the compact alarm rules with complete information is valuable and useful to the alarm correlation analysis and fault diagnosis and localization in networks.
引文
[1] Kimmo hatonen, Mika klemettinen, Heikkei Mannila, et al. TASA: Telecommunication Alarm Sequence Analyzer or How to enjoy faults in your network. In: IEEE/IEIP1996 Network Operations and Management Symposium 1996 (NOMS’96). Kyoto, Janpan: 1996. 520-529
[2] K.Hatonen, M.klemettinen, H.Mannila, et al. Knowledge Discovery from Telecommunication Network Alarm Databases. In: 12th International Conference on Data Engineering (ICDE’96). New Orleans, Louisiana: 1996. 115-122
[3] M.klemettinen, Heikkei Mannila, and Hannu Toivonen. Rule Discovery in Telecommunication Alarm Data. Journal of Network and Systems Management, 1999, 4: 395-423
[4] Robert D.Gardner, David A.Harle. Pattern discovery and specification techniques for Alarm Correlation. In: Proceedings of Network Operations and Management Symposium 1998 (NOMS’98). New Orleans, LA: 1996. 713-722
[5] Marlon Nunez, Rafael Morales, and Francisco Triguero. Automatic Discovery of Rules for Predicting Network Management Events. IEEE Journal of Selected Areas in Communications, 2002, Vol.20, No.4: 736-745
[6] A.T.Bouloutas, S.Calo, and A.Finkel. Alarm Correlation and Fault Identification in Communication Networks. IEEE Transactions on Communications, 1994, Vol.42, No.2/3/4: 523-533
[7] 毛广莉,黄梓龙,罗隆昌.电信网告警数据库的数据挖掘.计算机应用研究,2000,8:98-99
[8] 吴扬扬,陈怀南.基于关联规则的通信网络告警相关性分析模型.通讯和计算机,2004,12,Vol.1,No.1:57-63
[9] 王仲佳.具有动态加权特性的关联规则算法及其在电信故障告警序列模式发掘中的应用:[硕士学位论文].长春:吉林大学,2005
[10] 张坤.基于关联规则的数据挖掘在电信告警管理中的应用:[硕士学位论文].成都:电子科技大学,2006
[11] 石峰.通信网网关告警相关性分析机制的研究与应用:[硕士学位论文].南昌:南昌大学2006
[12] 夏海涛,詹志强.新一代网络管理技术.北京:北京邮电大学出版社,2003.242-250
[13] Heikkei Mannila, Hannu Toivonen and A.Inkeri Verkamo. Discovery of Frequent Episodes in Event Sequences. Data Mining and Knowledge Discovery, 1997.1: 259-289
[14] Rakesh Agrawal, Ramakrishnan Srikant. Fast Algorithm for Mining Association Rules. In: Proceedings of the 20th VLDB Conference. 1994. 487-499
[15] Jiawei Han, Jian Pei, Yiwen Yin, et al. Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach. Data Mining and Knowledge Discovery, 2004, 8: 53-87
[16] Cheng-Fa Tsai, Yi-Chau Lin and Chi-Pin Chen. A new fast algorithm for mining association rules in large databases. In: 2002 IEEE International Conference on Man and Cybernetics. 2002. 251-256
[17] 周晓云,孙志挥,倪巍伟.一种基于加权的高效关联规则挖掘算法的设计与实现.计算机工程与应用,2004,20:17-19
[18] 范明, 李川. 在 FP- 树中 挖 掘频繁 模 式而不生 成条件 FP- 树.计算机研究与发展,2003,8,Vol.40,No.8:1216-1222
[19] 肖海林,李兴明.层次分析法在通信网告警相关性分析中的应用研究.电信科学,2006,11:36-39
[20] 欧阳为民,郑诚,蔡庆生.数据库中加权关联规则的发现.软件学报,2002,12:612-619
[21] C.H.Cai, Ada, W.C.Fu, et al. Ming Association Rules with Weighted Items. In: Proceedings of IEEE International Database Engineering and Applications Symposium (IDEAS’98).1998. 68-77
[22] 陈怀南.通信网络告警相关性规则挖掘方法研究:[硕士学位论文].福建泉州:华侨大学信息科学与工程学院,2004
[23] Jiawei Han,Micheline.数据挖掘概念与技术,范明,孟小峰.北京:机械工业出版社,2005.149-184
[24] 蔡伟杰,张晓辉,朱建秋等.关联规则挖掘综述.计算机工程,2001,5:31-33
[25] 武波,马玉祥.专家系统.北京:北京理工大学出版社,2001.9-20
[26] 张仰森.人工智能原理与应用.北京:高等教育出版社,2004.282-284
[27] Saaty T L. The analytic hierarchy process. New York: McGraw-Hill Company, 1980
[28] 王莲芬,许树柏.层次分析法引论.北京:中国人民大学出版社,1989
[29] 高峰,谢剑英.一种无冗余的关联规则发现算法.上海交通大学学报,2001,2:256-258
[30] 周欣,沙朝 锋,朱扬 勇 等.兴趣 度 —关联 规 则的又一 个阈值. 计算机研 究 与发展,2000,Vo1.37,No.5:627-633
[31] 周皓峰,朱扬勇,施伯乐.一个基于兴趣度的关联规则的采掘算法.计算机研究与发展,2002,4:450-457
[32] Laurentiu Cristofor, Dan Simovici. Generating an informative cover for association rules. In: Proceedings of the IEEE International Conference on Data Mining.2002. 597-600.
[33] Toivonen H, Kelemettinen M, Ronkaine P, et al. Pruning and Grouping Discovered Association Rule. In: Proceedings of ECML-95 Workshop on Statistics, Machine Learning, and Discovery in Databases. Crete, Greece: 1995. 47-52.
[34] N.Pasquier, Y.Bastide, R.Taouil, et al. Closed set based discovery of small covers for association rules. In: Proceedings of .BDA Conference. 1999. 361-381
[35] 陈 玥 , 林 齐 宁 , 涂 志 云 . 关 联 规 则 的 一 种 定 量 分 析 方 法 . 通 信 学报,2003.Vol.24,No.3:119-123
[36] Klemettinen M, Mannila P, Ronkainen P. Finding interesting rules from large sets of discovered association rules. In: Nicholas C, Mayfield J, eds. Proceedings of the 3rd International Conference on Information and Knowledge Management ACM Press, 1994. 401-407
[37] Bing Liu, Wynne Hsu, Yiming Ma. Pruning and summarizing the discovered associations. In: Proceedings of the Fourth International Conference Discovery and Data Mining 1999. CA, USA: IEEE Computer Society, 1999.125-134
[2] K.Hatonen, M.klemettinen, H.Mannila, et al. Knowledge Discovery from Telecommunication Network Alarm Databases. In: 12th International Conference on Data Engineering (ICDE’96). New Orleans, Louisiana: 1996. 115-122
[3] M.klemettinen, Heikkei Mannila, and Hannu Toivonen. Rule Discovery in Telecommunication Alarm Data. Journal of Network and Systems Management, 1999, 4: 395-423
[4] Robert D.Gardner, David A.Harle. Pattern discovery and specification techniques for Alarm Correlation. In: Proceedings of Network Operations and Management Symposium 1998 (NOMS’98). New Orleans, LA: 1996. 713-722
[5] Marlon Nunez, Rafael Morales, and Francisco Triguero. Automatic Discovery of Rules for Predicting Network Management Events. IEEE Journal of Selected Areas in Communications, 2002, Vol.20, No.4: 736-745
[6] A.T.Bouloutas, S.Calo, and A.Finkel. Alarm Correlation and Fault Identification in Communication Networks. IEEE Transactions on Communications, 1994, Vol.42, No.2/3/4: 523-533
[7] 毛广莉,黄梓龙,罗隆昌.电信网告警数据库的数据挖掘.计算机应用研究,2000,8:98-99
[8] 吴扬扬,陈怀南.基于关联规则的通信网络告警相关性分析模型.通讯和计算机,2004,12,Vol.1,No.1:57-63
[9] 王仲佳.具有动态加权特性的关联规则算法及其在电信故障告警序列模式发掘中的应用:[硕士学位论文].长春:吉林大学,2005
[10] 张坤.基于关联规则的数据挖掘在电信告警管理中的应用:[硕士学位论文].成都:电子科技大学,2006
[11] 石峰.通信网网关告警相关性分析机制的研究与应用:[硕士学位论文].南昌:南昌大学2006
[12] 夏海涛,詹志强.新一代网络管理技术.北京:北京邮电大学出版社,2003.242-250
[13] Heikkei Mannila, Hannu Toivonen and A.Inkeri Verkamo. Discovery of Frequent Episodes in Event Sequences. Data Mining and Knowledge Discovery, 1997.1: 259-289
[14] Rakesh Agrawal, Ramakrishnan Srikant. Fast Algorithm for Mining Association Rules. In: Proceedings of the 20th VLDB Conference. 1994. 487-499
[15] Jiawei Han, Jian Pei, Yiwen Yin, et al. Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach. Data Mining and Knowledge Discovery, 2004, 8: 53-87
[16] Cheng-Fa Tsai, Yi-Chau Lin and Chi-Pin Chen. A new fast algorithm for mining association rules in large databases. In: 2002 IEEE International Conference on Man and Cybernetics. 2002. 251-256
[17] 周晓云,孙志挥,倪巍伟.一种基于加权的高效关联规则挖掘算法的设计与实现.计算机工程与应用,2004,20:17-19
[18] 范明, 李川. 在 FP- 树中 挖 掘频繁 模 式而不生 成条件 FP- 树.计算机研究与发展,2003,8,Vol.40,No.8:1216-1222
[19] 肖海林,李兴明.层次分析法在通信网告警相关性分析中的应用研究.电信科学,2006,11:36-39
[20] 欧阳为民,郑诚,蔡庆生.数据库中加权关联规则的发现.软件学报,2002,12:612-619
[21] C.H.Cai, Ada, W.C.Fu, et al. Ming Association Rules with Weighted Items. In: Proceedings of IEEE International Database Engineering and Applications Symposium (IDEAS’98).1998. 68-77
[22] 陈怀南.通信网络告警相关性规则挖掘方法研究:[硕士学位论文].福建泉州:华侨大学信息科学与工程学院,2004
[23] Jiawei Han,Micheline.数据挖掘概念与技术,范明,孟小峰.北京:机械工业出版社,2005.149-184
[24] 蔡伟杰,张晓辉,朱建秋等.关联规则挖掘综述.计算机工程,2001,5:31-33
[25] 武波,马玉祥.专家系统.北京:北京理工大学出版社,2001.9-20
[26] 张仰森.人工智能原理与应用.北京:高等教育出版社,2004.282-284
[27] Saaty T L. The analytic hierarchy process. New York: McGraw-Hill Company, 1980
[28] 王莲芬,许树柏.层次分析法引论.北京:中国人民大学出版社,1989
[29] 高峰,谢剑英.一种无冗余的关联规则发现算法.上海交通大学学报,2001,2:256-258
[30] 周欣,沙朝 锋,朱扬 勇 等.兴趣 度 —关联 规 则的又一 个阈值. 计算机研 究 与发展,2000,Vo1.37,No.5:627-633
[31] 周皓峰,朱扬勇,施伯乐.一个基于兴趣度的关联规则的采掘算法.计算机研究与发展,2002,4:450-457
[32] Laurentiu Cristofor, Dan Simovici. Generating an informative cover for association rules. In: Proceedings of the IEEE International Conference on Data Mining.2002. 597-600.
[33] Toivonen H, Kelemettinen M, Ronkaine P, et al. Pruning and Grouping Discovered Association Rule. In: Proceedings of ECML-95 Workshop on Statistics, Machine Learning, and Discovery in Databases. Crete, Greece: 1995. 47-52.
[34] N.Pasquier, Y.Bastide, R.Taouil, et al. Closed set based discovery of small covers for association rules. In: Proceedings of .BDA Conference. 1999. 361-381
[35] 陈 玥 , 林 齐 宁 , 涂 志 云 . 关 联 规 则 的 一 种 定 量 分 析 方 法 . 通 信 学报,2003.Vol.24,No.3:119-123
[36] Klemettinen M, Mannila P, Ronkainen P. Finding interesting rules from large sets of discovered association rules. In: Nicholas C, Mayfield J, eds. Proceedings of the 3rd International Conference on Information and Knowledge Management ACM Press, 1994. 401-407
[37] Bing Liu, Wynne Hsu, Yiming Ma. Pruning and summarizing the discovered associations. In: Proceedings of the Fourth International Conference Discovery and Data Mining 1999. CA, USA: IEEE Computer Society, 1999.125-134