基于倒转二叉树的FSVM入侵检测算法研究
|
摘要
支持向量机是建立在统计学习理论之上的机器学习方法,它将最大间隔与核函数理论结合在一起,有效的解决了长期困扰机器学习领域的小样本、高维数、非线性、过学习和局部最优解等难题。
随着网络技术的发展和应用范围的扩大,人们越来越依赖于网络进行信息处理,信息系统已成为一个单位、一个行业、乃至一个国家持续发展的基础设施,网络安全也就成为国家与国防安全的重要组成部分。入侵检测技术是一种重要的动态安全防护技术,有效的弥补了传统静态防御技术的不足,已成为信息技术的一个重要研究方向。入侵检测本质上是一种模式识别问题,将支持向量机应用于入侵检测,可以提高检测性能。
本文在研究入侵检测系统和支持向量机的基础上,做了以下工作和创新:
1、提出了适合于入侵检测数据的分步特征选择算法,首先利用ReliefF算法删除不相关特征,然后利用KNN算法删除冗余特征,解决了传统ReliefF方法无法取出冗余特征的问题。
2、提出了一种倒转二叉树的构造方法,一定程度上抑制了传统构造方法中的“误差积累”问题;提出了一种基于特征空间类间分离的分离判据,能够更好反映可分离性,具有更好的几何意义。
3、结合基于二叉树的支持向量机和模糊支持向量机的优点,在二叉树的多类支持向量机中引入了模糊因子,提出了一种基于二叉树的模糊多类支持向量机入侵检测算法;同时结合传统的类中心距离隶属度函数和KNN算法思想,提出一种混合隶属度函数,解决了传统的基于类中心距离隶属度确定方法中无法有效区分支持向量与噪声孤立点的问题。
SVM is a machine learning method based on statistical learning theory, which combines the maximum interval and the kernel function theory together and effectively solves the problems of small sample size, high dimension, nonlinear, over learning, local optimal solution and so on.
With the development of network technology and the expansion of the scope of application, network is becoming the main method of information processing. Information systems have become a infrastructure of a country and network security has become an important component of the national security. Intrusion detection technology is an important dynamic security protection technology, and has become an important research direction of the information technology. Intrusion detection is essentially a pattern recognition problem, the applications of support vector machine in intrusion detection can improve the detection performance.
Based on the study on intrusion detection system and support vector machines, we do the following work and innovation:
1. A new feature selection algorithm to intrusion detection data is proposed.It’s that using ReliefF algorithm to remove irrelevant features, and then remove the redundant features using KNN algorithm;
2. A new binary tree structure is proposed to solve the "error accumulation" problem; A new criterion of class separation based on Kernel function is proposed.It has the better effective to reflect the separability and has a better geometric significance;
3. Considering the advantages of support vector machines based on binary tree and fuzzy support vector machine, a fuzzy factor is introduced to multi-class support vector machine based on binary tree; a new fuzzy membership function is proposed based on class center distance and the KNN algorithm to distinguish support vector and the noises more effectively.
随着网络技术的发展和应用范围的扩大,人们越来越依赖于网络进行信息处理,信息系统已成为一个单位、一个行业、乃至一个国家持续发展的基础设施,网络安全也就成为国家与国防安全的重要组成部分。入侵检测技术是一种重要的动态安全防护技术,有效的弥补了传统静态防御技术的不足,已成为信息技术的一个重要研究方向。入侵检测本质上是一种模式识别问题,将支持向量机应用于入侵检测,可以提高检测性能。
本文在研究入侵检测系统和支持向量机的基础上,做了以下工作和创新:
1、提出了适合于入侵检测数据的分步特征选择算法,首先利用ReliefF算法删除不相关特征,然后利用KNN算法删除冗余特征,解决了传统ReliefF方法无法取出冗余特征的问题。
2、提出了一种倒转二叉树的构造方法,一定程度上抑制了传统构造方法中的“误差积累”问题;提出了一种基于特征空间类间分离的分离判据,能够更好反映可分离性,具有更好的几何意义。
3、结合基于二叉树的支持向量机和模糊支持向量机的优点,在二叉树的多类支持向量机中引入了模糊因子,提出了一种基于二叉树的模糊多类支持向量机入侵检测算法;同时结合传统的类中心距离隶属度函数和KNN算法思想,提出一种混合隶属度函数,解决了传统的基于类中心距离隶属度确定方法中无法有效区分支持向量与噪声孤立点的问题。
SVM is a machine learning method based on statistical learning theory, which combines the maximum interval and the kernel function theory together and effectively solves the problems of small sample size, high dimension, nonlinear, over learning, local optimal solution and so on.
With the development of network technology and the expansion of the scope of application, network is becoming the main method of information processing. Information systems have become a infrastructure of a country and network security has become an important component of the national security. Intrusion detection technology is an important dynamic security protection technology, and has become an important research direction of the information technology. Intrusion detection is essentially a pattern recognition problem, the applications of support vector machine in intrusion detection can improve the detection performance.
Based on the study on intrusion detection system and support vector machines, we do the following work and innovation:
1. A new feature selection algorithm to intrusion detection data is proposed.It’s that using ReliefF algorithm to remove irrelevant features, and then remove the redundant features using KNN algorithm;
2. A new binary tree structure is proposed to solve the "error accumulation" problem; A new criterion of class separation based on Kernel function is proposed.It has the better effective to reflect the separability and has a better geometric significance;
3. Considering the advantages of support vector machines based on binary tree and fuzzy support vector machine, a fuzzy factor is introduced to multi-class support vector machine based on binary tree; a new fuzzy membership function is proposed based on class center distance and the KNN algorithm to distinguish support vector and the noises more effectively.
引文
[1] Cortes C, Vapnik V.Support-Vector Networks”, Machine Learning J., vol. 20, No. 3, pp. 273-297, 1995.
[2] John S,Peter L.A framework for structural risk minimization.In Proceedings,9th Annual Conference on Computational Learning Theory.1996:68-76
[3] Wang An-Na, Zhao Yue, A novel construction of SVM compound kernel function ,2010 International Conference on Logistics Systems and Intelligent Management, ICLSIM 2010, January 9, 2010 - January 10, 2010 pp:1462~1465
[4] Zhang Lipu,XuYinghong, A new kernel function and complexity analysis for linear optimization, 3rd International Conference on Information and Computing, ICIC 2010:247-250
[5] P.S.Hiremath, Prabhakar C.J ,“A New Kernel function to extract Non Linear Interval type Features Using Symbolic Kernel Fisher Discriminant Method with Application to Face Recognition”, IEEE, 2008
[6] Ying Tan, Senior Member, and Jun Wang, Senior Member,“A Support Vector Machine with a Hybrid Kernel and Minimal Vapnik-Chervonenkis Dimension”, IEEE Transactions on Knowledge and Data Engineering, VOL. 16, NO. 4, pp. 385-395, April 2004
[7] Chih-Cheng Yang, Wan-Judi Lee, and Shie-Jue Lee,“Learning of Kernel Functions in Support Vector Machines”, 2006 International Joint Conference on Neural Networks Sheraton Vancouver Wall Centre Hotel, Vancouver, BC, Canada, pp. 1150-1155, July16-21, 2006
[8]杨义先,钮心忻入侵检测理论与技术[M]高等教育出版社
[9]胡昌振网络入侵检测原理与技术北京理工大学出版社[M]:8~10
[10]蒋盛益基于聚类的入侵检测算法研究[M]科学出版社
[11]曹元大,入侵检测技术[M]人民邮电出版社pp:141~145
[12]丁亚丽基于数据挖掘的入侵检测算法研究[D]南京邮电大学2009
[13] Anderson J P. Computer security threat monitoring and surveillance.Technical Report,James P Anderson Co., Fort Washington,Pennsylvania,1980,4
[14] Dorothy Denning E. An intrusion-detection model. IEEE Transactions on Software Engineering,1987,13(2):222-232.
[15] Yuancheng Li, Zhongqiang Wang, Yinglong Ma AN INTRUSION DETECTION METHOD BASED ON KICA AND SVM Proceedings of the 7th World Congress on Intelligent Control and Automation June 25- 27,2008, Chongqing, China
[16] Chi-Fong Tsai,Yu-Feng Hsu,Chia-Ying Lin,Intrusion detection by machine learning: A review, Expert Systems with Applications 36(2009)11994-12000
[17]边肇祺,张学工.模式识别[M].清华大学出版社,2000
[18] Liu H, Yu L. Towards integrating feature selection algorithms for classification and clustering[J]. IEEE Trans on Knowledge and Data Engineering, 2005,17(4):491-502.
[19] Pabitra Miltra Unsupervised Feature Selection Using Feature Similarity IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,VOL 24,NO 3,MARCH 2002
[20] Hong Xia,“Feature Selection based on Fuzzy SVM”, Fifth International Conference on Fuzzy Systems and Knowledge Discovery, pp. 586-589, 2008.
[21]张昊,陶然基于KNN算法及禁忌搜索算法的特征选择方法电子学报2009年第07期[J]
[22]肖立中,刘云翔适合于入侵检测的分布入侵检测算法,计算机工程与应用,2010,46(11)pp:81~84
[23]朱永宣,单莘,郭军,入侵检测系统中基于变量相似性特征选择微电子学与计算机系统,2005年第22卷第10期,pp:34~39
[24]高隽人工神经网络原理及仿真实例[M]机械工业出版社
[25]吕晓丽,李雷,人脸识别中基于二叉树的支持向量机多类分类算法研究:[D]南京:南京邮电大学,2008
[26]刘海涛,黄敏,一种新的二叉树SVM多分类算法[J]江南大学学报Vo1. 8 No.2 Apr. 2009 pp:145~148
[27] Gang Kou,Yi Peng,Zhengxin,Chen,Multiple criteria mathematical programming for multi-class classification and application in network intrusion detection, Information Sciences 179(2009)371-381
[28] Weston J. and Watkins C.,“Multi-class Support Vector Machines”, Proceedings of ESANN99, M. Verleysen, Brussels, Belgium, 1999
[29] Zhu Yanwei Zhang Yongli Improved support vector machine multi-classification algorithm International Conference on Information Computing and Applications, ICICA 2010: 119-126
[30] Li Kun-Lun, Huang Hou-Kuan, Fuzzy Multi-Class support vector machine and application in intrusion detection, CHINESE JOURNAL OF COMPUTERS Vol. 28 No. 5 Feb. 2005
[31] Takuya Inoue,“Fuzzy Support Vector Machines for Pattern Classification”, IEEE, pp. 1449-1454, 2001.
[32]王耀南智能信息处理技术[M]高等教育出版社
[33] Joanna Czajkowska, Marcin Rudzki, and Zbigniew Czajkowski,“A New Fuzzy Support Vectors Machine for Biomedical Classification”, 30th Annual International IEEE EMBS Conference Vancouver, British Columbia, Canada, pp. 4476-4479, August 20-24, 2008.
[34] ERIC C. C. TSANG, DANIEL S. YEUNG, PATRICK P.K.CHAN,“Fuzzy Support Vector Machines for solving two-class problems”, Proceedings of the Second International Conference on Machine Learning and Cybernetics, Xi’an, pp. 1080-1083, November 2003
[35] L.A. Zadeh,“Fuzzy sets”, Information and Control, 1965.
[36] D. Dubois and H. Prade, Fwzy Sets and Systems, Academic Press, New York, 1980.
[37] C.F. Lin, and S.D. Wang, Fuzzy Support Vector Machines, IEEE Transactions on Neural Networks, pp. 466-471, 2002
[38] Danisuke Tsujinishi and Shigeo Abe,“Fuzzy least squares support vector machines for multiclass problems”, Neural Nehuorks, pp. 785-792, 2003.
[39] T. Inoue and S. Abe,“Fuzzy support vector machines for pattem classification”, International Joint Conference on Neural Networks, pp. 1449-1454, July 2001.
[40] Xuehua Li, LanShu,“Fuzzy Theory Based Support Vector Machine Classifier”, Fifth International Conference on Fuzzy Systems and Knowledge Discovery, pp. 600-604, 2008.
[41] Bai-Xing li, Qian Xu,“Medical Image Classification based on Fuzzy Support Vector Machines”, 2008International Conference on Intelligent Computation Technology and Automation, pp:145-149, 2008.
[42]阳爱民模糊分类模型及其集成方法[M]科学出版社: 13~15.
[43]李雷,周蒙蒙,鲁延玲基于密度法的双隶属度模糊支持向量机[J],计算机技术与发展2009年12期,pp:44~46
[44]李雷,鲁延玲,周蒙蒙基于核方法的一种新的模糊支持向量机[J].计算机技术与发展。2010.2,20(2),pp:9~15.
[45]郑恩辉基于支持向量机的代价敏感数据挖掘与应用[D]浙江:浙江大学2006,pp:64~67
[46] http://kdd.ics.uci.edu/pub/databases/kddcup99/kddcup99.html
[47] V.Vapnik.Statistical learning theory,New York:J.Wiley,1998
[48]张学工,关于统计学习理论与支持向量机,自动化学报,2000,26(1):32~42.
[49]许建华,张学工,李衍达.支持向量机的新发展.控制与决策, 2004,19(5): 481～484
[50]刘宜萍基于特征选择的多因素时间序列预测模型研究平[D]合肥工业大学
[2] John S,Peter L.A framework for structural risk minimization.In Proceedings,9th Annual Conference on Computational Learning Theory.1996:68-76
[3] Wang An-Na, Zhao Yue, A novel construction of SVM compound kernel function ,2010 International Conference on Logistics Systems and Intelligent Management, ICLSIM 2010, January 9, 2010 - January 10, 2010 pp:1462~1465
[4] Zhang Lipu,XuYinghong, A new kernel function and complexity analysis for linear optimization, 3rd International Conference on Information and Computing, ICIC 2010:247-250
[5] P.S.Hiremath, Prabhakar C.J ,“A New Kernel function to extract Non Linear Interval type Features Using Symbolic Kernel Fisher Discriminant Method with Application to Face Recognition”, IEEE, 2008
[6] Ying Tan, Senior Member, and Jun Wang, Senior Member,“A Support Vector Machine with a Hybrid Kernel and Minimal Vapnik-Chervonenkis Dimension”, IEEE Transactions on Knowledge and Data Engineering, VOL. 16, NO. 4, pp. 385-395, April 2004
[7] Chih-Cheng Yang, Wan-Judi Lee, and Shie-Jue Lee,“Learning of Kernel Functions in Support Vector Machines”, 2006 International Joint Conference on Neural Networks Sheraton Vancouver Wall Centre Hotel, Vancouver, BC, Canada, pp. 1150-1155, July16-21, 2006
[8]杨义先,钮心忻入侵检测理论与技术[M]高等教育出版社
[9]胡昌振网络入侵检测原理与技术北京理工大学出版社[M]:8~10
[10]蒋盛益基于聚类的入侵检测算法研究[M]科学出版社
[11]曹元大,入侵检测技术[M]人民邮电出版社pp:141~145
[12]丁亚丽基于数据挖掘的入侵检测算法研究[D]南京邮电大学2009
[13] Anderson J P. Computer security threat monitoring and surveillance.Technical Report,James P Anderson Co., Fort Washington,Pennsylvania,1980,4
[14] Dorothy Denning E. An intrusion-detection model. IEEE Transactions on Software Engineering,1987,13(2):222-232.
[15] Yuancheng Li, Zhongqiang Wang, Yinglong Ma AN INTRUSION DETECTION METHOD BASED ON KICA AND SVM Proceedings of the 7th World Congress on Intelligent Control and Automation June 25- 27,2008, Chongqing, China
[16] Chi-Fong Tsai,Yu-Feng Hsu,Chia-Ying Lin,Intrusion detection by machine learning: A review, Expert Systems with Applications 36(2009)11994-12000
[17]边肇祺,张学工.模式识别[M].清华大学出版社,2000
[18] Liu H, Yu L. Towards integrating feature selection algorithms for classification and clustering[J]. IEEE Trans on Knowledge and Data Engineering, 2005,17(4):491-502.
[19] Pabitra Miltra Unsupervised Feature Selection Using Feature Similarity IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,VOL 24,NO 3,MARCH 2002
[20] Hong Xia,“Feature Selection based on Fuzzy SVM”, Fifth International Conference on Fuzzy Systems and Knowledge Discovery, pp. 586-589, 2008.
[21]张昊,陶然基于KNN算法及禁忌搜索算法的特征选择方法电子学报2009年第07期[J]
[22]肖立中,刘云翔适合于入侵检测的分布入侵检测算法,计算机工程与应用,2010,46(11)pp:81~84
[23]朱永宣,单莘,郭军,入侵检测系统中基于变量相似性特征选择微电子学与计算机系统,2005年第22卷第10期,pp:34~39
[24]高隽人工神经网络原理及仿真实例[M]机械工业出版社
[25]吕晓丽,李雷,人脸识别中基于二叉树的支持向量机多类分类算法研究:[D]南京:南京邮电大学,2008
[26]刘海涛,黄敏,一种新的二叉树SVM多分类算法[J]江南大学学报Vo1. 8 No.2 Apr. 2009 pp:145~148
[27] Gang Kou,Yi Peng,Zhengxin,Chen,Multiple criteria mathematical programming for multi-class classification and application in network intrusion detection, Information Sciences 179(2009)371-381
[28] Weston J. and Watkins C.,“Multi-class Support Vector Machines”, Proceedings of ESANN99, M. Verleysen, Brussels, Belgium, 1999
[29] Zhu Yanwei Zhang Yongli Improved support vector machine multi-classification algorithm International Conference on Information Computing and Applications, ICICA 2010: 119-126
[30] Li Kun-Lun, Huang Hou-Kuan, Fuzzy Multi-Class support vector machine and application in intrusion detection, CHINESE JOURNAL OF COMPUTERS Vol. 28 No. 5 Feb. 2005
[31] Takuya Inoue,“Fuzzy Support Vector Machines for Pattern Classification”, IEEE, pp. 1449-1454, 2001.
[32]王耀南智能信息处理技术[M]高等教育出版社
[33] Joanna Czajkowska, Marcin Rudzki, and Zbigniew Czajkowski,“A New Fuzzy Support Vectors Machine for Biomedical Classification”, 30th Annual International IEEE EMBS Conference Vancouver, British Columbia, Canada, pp. 4476-4479, August 20-24, 2008.
[34] ERIC C. C. TSANG, DANIEL S. YEUNG, PATRICK P.K.CHAN,“Fuzzy Support Vector Machines for solving two-class problems”, Proceedings of the Second International Conference on Machine Learning and Cybernetics, Xi’an, pp. 1080-1083, November 2003
[35] L.A. Zadeh,“Fuzzy sets”, Information and Control, 1965.
[36] D. Dubois and H. Prade, Fwzy Sets and Systems, Academic Press, New York, 1980.
[37] C.F. Lin, and S.D. Wang, Fuzzy Support Vector Machines, IEEE Transactions on Neural Networks, pp. 466-471, 2002
[38] Danisuke Tsujinishi and Shigeo Abe,“Fuzzy least squares support vector machines for multiclass problems”, Neural Nehuorks, pp. 785-792, 2003.
[39] T. Inoue and S. Abe,“Fuzzy support vector machines for pattem classification”, International Joint Conference on Neural Networks, pp. 1449-1454, July 2001.
[40] Xuehua Li, LanShu,“Fuzzy Theory Based Support Vector Machine Classifier”, Fifth International Conference on Fuzzy Systems and Knowledge Discovery, pp. 600-604, 2008.
[41] Bai-Xing li, Qian Xu,“Medical Image Classification based on Fuzzy Support Vector Machines”, 2008International Conference on Intelligent Computation Technology and Automation, pp:145-149, 2008.
[42]阳爱民模糊分类模型及其集成方法[M]科学出版社: 13~15.
[43]李雷,周蒙蒙,鲁延玲基于密度法的双隶属度模糊支持向量机[J],计算机技术与发展2009年12期,pp:44~46
[44]李雷,鲁延玲,周蒙蒙基于核方法的一种新的模糊支持向量机[J].计算机技术与发展。2010.2,20(2),pp:9~15.
[45]郑恩辉基于支持向量机的代价敏感数据挖掘与应用[D]浙江:浙江大学2006,pp:64~67
[46] http://kdd.ics.uci.edu/pub/databases/kddcup99/kddcup99.html
[47] V.Vapnik.Statistical learning theory,New York:J.Wiley,1998
[48]张学工,关于统计学习理论与支持向量机,自动化学报,2000,26(1):32~42.
[49]许建华,张学工,李衍达.支持向量机的新发展.控制与决策, 2004,19(5): 481～484
[50]刘宜萍基于特征选择的多因素时间序列预测模型研究平[D]合肥工业大学