基于ReliefF的入侵特征选择方法

杨志伟,努尔布力,贾 雪,胡 亮

(1.新疆大学 信息科学与工程学院,乌鲁木齐 830046；2.吉林大学 计算机科学与技术学院,长春 130012)



基于ReliefF的入侵特征选择方法

杨志伟1,努尔布力1,贾 雪1,胡 亮2

(1.新疆大学 信息科学与工程学院,乌鲁木齐 830046；2.吉林大学 计算机科学与技术学院,长春 130012)

基于ReliefF的入侵特征选择方法,结合入侵检测数据集类内紧密和类外差距大的特点,通过对入侵特征权重计算的优化,提出一种改进算法:Re-ReliefF算法,解决了网络安全领域数据维度导致处理效率较低的问题.实验结果表明,在安全测试数据集下,改进算法相对传统算法在性能上有一定提高.

入侵检测；特征选择；ReliefF算法

随着互联网的快速发展,网络安全问题日益恶化.因此,快速提高入侵检测系统的性能是目前互联网领域内亟待解决的问题之一.本文针对目前海量网络数据量导致入侵检测系统压力过大的问题,尤其针对数据维度中噪声属性影响检测效率的问题,通过分析特征选择的特性,结合针对入侵检测领域攻击数据集的特点,提出一种新算法----Re-ReliefF算法.该算法可得到低维度、少冗余数据的优良特征子集.实验结果表明,改进算法可有效降低入侵检测数据中的噪声属性,通过低维度的有效特征维度提升检测效率,从而有效降低资源消耗,减少检测时间.

1 入侵检测与特征选择

1.1入侵检测

入侵是指未经授权就尝试访问信息、篡改信息,使系统不可靠或无法使用的行为[1].入侵检测是指能够发现和识别入侵行为.入侵检测系统主要用于收集和分析主机系统或若干网络关键节点的异常行为,一旦发现,主动记录并发出警报,以保证主机系统和网络资源的机密性、完整性和可用性.根据数据来源可分为主机型、网络型和混合型入侵检测系统;根据检测的时效性可分为实时和离线入侵检测系统;根据检测方法可分为异常检测和误用检测.

目前,入侵检测技术已将数据挖掘、机器学习、模式识别和分布式等方法与入侵检测相结合,使入侵检测进入智能化时代.如Zhang等[2]针对智能电网的安全问题,提出了用于智能电网分析的分布式入侵检测系统;Ahmad等[3]将遗传算法和PCA(principal component analysis)算法相结合,提出了一种新的应用于入侵检测领域的特征选择方法;Ganapathy等[4]分析了智能特征选择方法在入侵检测领域的应用;杨杰明等[5]提出一种新的特征选择方法,该方法从两方面综合度量某个特征对于分类的程度,结果表明了算法的有效性;朱琳等[6]通过对高速网络环境下进行实时入侵检测技术的研究,提出了基于滑动窗口数据流聚类算法,并构建了基于该算法的IDS(intrusion detection systems)网络安全防御模型.

1.2特征选择

图1 特征选择框架Fig.1 Feature selection framework

数据采集和存储技术的发展,出现了信息爆炸的现象,特别是在网络检测、生物科学和金融分析等领域,不断涌现大规模、高维度、高噪声的数据.如何快速处理这些数据,已引起人们的广泛关注,特征选择方法是解决该问题的方法之一.例如一些机器学习问题,通常要处理的数据特征维度较高,因此采用特征选择方法能降低数据维度,并提高算法效率.文献[7]利用机器学习的思想提出一个通用的特征选择框架,如图1所示.该框架的思想是在不显著降低分类精度和尽量接近原始类别分布的前提下,从原始特征空间中选择出尽可能小的特征子集,并在该特征子集上采用学习方法,选择出最优特征子集.

特征选择在文本分类、图像识别、医疗、入侵检测和基于生物特征的身份识别等领域应用广泛.Shang等[8]为解决文本分类中的维数灾难问题,提出了一种全局信息增益特征选择算法MGIG,结果表明MGIG比其他高阶算法在处理速度上有较大提升；Rashedi等[9]将特征降维方法应用到图像处理中,提出了一种混合的特征选择方法;在人脸识别方面,Zhang等[10]利用稀疏化表示方法提出一种新的特征选择方法;文献[11]运用特征选择算法,使得当基因表达数据很少时,也可提供一个合适的特征选择组合,使分类算法精确率较高;陈友等[12]对基于特征选择的轻量级入侵检测系统进行分类比较,通过分析和总结各种系统的优缺点及其各自的适用条件,给出了入侵检测领域特征选择的发展趋势.

1.3ReliefF特征选择算法

Relief算法[13]是一种适用于二类问题的有监督特征选择算法,基于距离度量计算特征权重,利用统计学方法选择相关特征.算法中特征和类别的相关性是基于特征对近距离样本的区分能力判断的,按照一定的规则赋予每个特征一个权重值,以权重值的大小识别各特征对不同类别的区分能力.Kononenko[14]对Relief算法进行扩展,提出了可应对多类别数据集分类情况及噪声数据与数据缺失问题的ReliefF算法.Relief系列算法通常被视为应用于模型学习前预处理步骤中的特征子集选择方法.

ReliefF算法在处理多类问题时,每次先从训练集随机抽取一个样本R,再从R同类样本集中找出R的k个近邻样本H,从每个R不同类样本集中找出k个近邻样本M,然后更新每个特征的权值w[A],权值更新公式为

(1)

其中:m表示样本抽样次数;Mj(C)表示不同类别C中的第j个最近邻样本;P(C)表示C类目标样本数占样本总数的比例;class(Ri)表示Ri所属的类别;函数diff(A,Ri,Rj)用于计算样本实例Ri和Rj关于某个特征A间的距离：

(2)

由式(1)可见,对于某个特征A,同类的两个样本在A上的距离diff(A,Ri,Hj)越小,或者不同类的两个样本在A上的距离diff(A,Ri,Mj(C))越大,特征A越有利于分类,w[A]越大.

ReliefF算法易扩展,稳定性好,目前已有多种改进算法,如Jia等[15]提出一种面向对象高维分辨图像特征选择的改进Relief算法,避免了高维带来的运算困难,也提高了分类精度和速度;Wang等[16]通过结合DDNA和SOEKS RELIEF-F特征选择学习算法,得到一个通用的、可拓展的增强型学习算法,提高了预测精度.

2 Re-ReliefF算法

2.1算法设计

图2 基于ReliefF入侵特征选择算法的逻辑结构Fig.2 Logical structure of ReliefF-based intrusionfeature selection algorithm

网络数据的大规模和高维度,为入侵检测系统实时、快速、准确地分析网络数据带来了巨大挑战.本文将特征选择方法应用到入侵检测领域,解决对高维数据处理的问题.将ReliefF算法应用到入侵检测领域,通过实验分析其有效性.ReliefF入侵特征选择算法逻辑结构如图2所示.

2.2定义

定义1基于ReliefF入侵特征选择算法的输入矩阵定义为D：(A,F).其中:A表示网络数据特征,包括协议类型、持续连接时间及目标主机的网络服务类型等41个特征；F表示攻击数据类别标签,如Normal,DOS,U2R等.

定义2基于ReliefF入侵特征选择算法的参数模型定义为R(m,k,N).其中：m表示初始随机选择的样本个数,即随机选取输入矩阵D的若干行；k表示在m个网络数据样本中选取一个样本后选择其最近邻样本的数量,包括同类的最近邻样本H和不同类的最近邻样本M；N表示攻击数据特征维度,N=41.

定义3基于ReliefF入侵特征选择算法的特征权值定义为w[A],表示m个网络数据样本在特征A上的距离间隔累加结果,数值越大表示特征A区分攻击类别的能力越强.

定义4基于ReliefF入侵特征选择算法的特征子集定义为S(D),其为根据定义3中w[A]大小选择较大值的w[A]所对应特征的特征子集.

定义5基于ReliefF入侵特征选择算法的最优特征子集定义为S′,其为定义4中众多特征子集S中通过SVM分类预测,由时间和准确率等指标选出的最优子集.

2.3算法描述

输入：网络数据集D;输出：最优特征子集S.

1)数值化D：num(D)；归一化A：nor(A)∈[-1,1]；

2)抽样产生训练集trainD及预测集testD；

3)初始化w[A]=0；

4)确定特征选择参数模型k,m值,随机选择m个样本实例；

5)Fori=1 tomdo；

6)计算选择k个最近邻样本：H,M；

7)Fori=1 toNdo；

8)计算特征A的权值w[A]；

9)产生特征子集S=generate(D)；

10)产生目标系统的分类模型model=train(trainD,S)；

11)对测试集进行分类预测,predict(testD,model),选择最优子集S′,算法结束.

在该算法中,步骤1)和2)为数据的预处理过程;步骤3)～9)是对trainD特征选择的过程;步骤10),11)是对算法性能的验证过程.

2.4改进算法

由于网络安全数据中有些类别不易区分,如KDD CUP99数据集中,包含5大类,有些大类又有许多小类,因此如何突出类内紧密、增大类间差距是一个亟待解决的问题.针对该问题,本文参考文献[17]修改了特征权值的更新,提出ReliefF算法针对入侵检测特征选择的改进算法：Re-ReliefF.其中更新特征权值公式为

(3)

Re-ReliefF算法采用样本与不同类最近邻样本间的距离,与样本和同类最近邻样本间的距离比值评估特征权值.为类间差异性较大、类内差异性较小的特征赋以较高权重；为类间差异较小、类内差异较大的特征赋以较小权重.以突出类内紧密性强、类间差距大的特征,从而达到降低有效特征数量的目的.

3 实验与分析

实验环境：操作系统Windows 7；CPU 16×2.1 GHz；内存64 GB；软件环境MATLAB R2010b 64位.实验数据是KDD CUP99数据集,其提供5类数据集:Normal,Denial-of-Service(DOS),Surveillance or probe(Probe),User to Root(U2R),Remote to Local(R2L).其中,Normal类占19.69%；Probe大类包含4小类,共占0.83%；DOS大类包含6小类,共占79.24%；U2R包含4小类,共占0.01%；R2L大类包含8小类,共占0.23%.数据集里每一行表示一个记录,每条记录有41个特征值,最后一个是攻击类型.实验包括两部分：算法参数模型的建立和算法性能指标对比.

实验1模型构建.

由算法描述步骤5)可见,实验需要选择合适的参数m和k,本文通过Re-ReliefF入侵特征选择算法选择合适的值.

1)m值的选择.当k=1时,m分别为50,100,500,1 000,5 000次迭代时,统计训练时间、预测时间、准确率、误报率和漏报率,结果列于表1.

表1 Re-ReliefF算法取不同m值时的相关参数Table 1 Parameters of Re-ReliefF algorithm for different m values

由表1可见,在较小迭代次数下与较大迭代次数下的实验结果相差较小.表明当样本规模较大时,迭代次数在远小于样本总数时,可得到较准确的评估结果.综合表1的数据,选择m=500.

2)k值的选择.当m=500,k=1,20,40时,统计训练时间、预测时间、准确率、误报率和漏报率,结果列于表2.由表2可见,k=1与k=40相比,预测时间更短.所以,可选择k=20.

实验2Re-ReliefF算法与传统ReliefF算法对比结果.

通过实验1的参数选定,结合SVM分类算法,比较ReliefF入侵特征选择算法和Re-ReliefF入侵特征选择算法中每个特征权值大小,结果如图3所示.ReliefF算法和Re-ReliefF算法的训练时间、预测时间和准确率对比结果分别如图4～图6所示.

表2 Re-ReliefF算法取不同k值时的相关参数Table 2 Parameters of Re-ReliefF algorithm for different k values

图3 ReliefF算法与Re-ReliefF算法下的特征权值比较Fig.3 Comparison of feature weights ofReliefF and Re-ReliefF

图4 ReliefF算法与Re-ReliefF算法训练时间对比Fig.4 Comparison of training time ofReliefF and Re-ReliefF

图5 ReliefF算法与Re-ReliefF算法预测时间对比Fig.5 Comparison of predicting time ofReliefF and Re-ReliefF

图6 ReliefF算法与Re-ReliefF算法准确率对比Fig.6 Comparison of accuracy ofReliefF and Re-ReliefF

由图3可见,大部分Re-ReliefF入侵特征选择算法的特征值比ReliefF入侵特征选择算法的特征值都大,根据对算法的理论分析,实验证明了Re-ReliefF入侵特征选择算法类内差异减小,类间差异增大,可更方便地选择最优特征子集.由图4～图6可见:1)ReliefF入侵特征选择算法和Re-ReliefF入侵特征选择算法训练时间均随着特征维数的减少而减少；预测时间在维数少于34时明显增多；准确率在维数小于34时显著下降,所以两种算法都适合取34个特征作为最优特征子集的集合数量.2)Re-ReliefF算法相对于原始的ReliefF算法,可在分类准确率相对稳定的情况下降低训练和预测时间.

通过对ReliefF算法和Re-ReliefF算法的实验结果对比可见:

1)当类间差异较大,类内差异较小时,改进后的特征权值w(A)相对于原有ReliefF算法的权值大,此时能够区分原有ReliefF算法中较相近的入侵特征,从而减少有效区分入侵攻击类别的入侵特征数量,达到降低有效特征数量的目的;

2)当类间差异较小,类内差异较大时,改进后的特征权值w(A)相对于原有ReliefF算法的权值小,此时将原有ReliefF算法中已判为能进行入侵分类的有效特征,重新计算判别为非有效特征,从而减少非有效区分入侵攻击类别的入侵特征数量,达到降低有效特征数量的目的.

综上所述,论文通过对特征选择算法的研究,明确与入侵特征指标模型间的映射关系提出了基于ReliefF的入侵特征选择方法;并进一步根据入侵检测数据集类内紧密和类外差距大的特点,结合已有工作对ReliefF的权重计算方法进行优化.实验结果表明,改进的Re-ReliefF算法结合SVM能更有效地区分入侵的特征差异,在降低数据维度后,特征子集能保障较好的正确率并有效减少时间复杂度.

[1] James P A.Computer Security Threat Monitoring and Surveillance [R].Fort Washington,Pennsylvania:Anderson Company,1980.

[2] ZHANG Yichi,WANG Lingfeng,SUN Weiqing,et al.Distributed Intrusion Detection System in a Multi-layer Network Architecture of Smart Grids [J].IEEE Transactions on Smart Grid,2011,2(4):796-808.

[3] Ahmad I,Hussain M,Alghamdi A,et al.Enhancing SVM Performance in Intrusion Detection Using Optimal Feature Subset Selection Based on Genetic Principal Components [J].Neural Computing and Applications,2014,24(7/8):1671-1682.

[4] Ganapathy S,Kulothungan K,Muthurajkumar S,et al.Intelligent Feature Selection and Classification Techniques for Intrusion Detection in Networks:A Survey [J/OL].EURASIP Journal on Wireless Communications and Networking,2013,2013(1):doi:10.1186/1687-1499-2013-271.

[5] 杨杰明,刘元宁,曲朝阳,等.文本分类中基于综合度量的特征选择方法 [J].吉林大学学报:理学版,2013,51(5):887-893.(YANG Jieming,LIU Yuanning,QU Zhaoyang,et al.Feature Selection Algorithm Based on Comprehensive Measurement for Text Categorization [J].Journal of Jilin University:Science Edition,2013,51(5):887-893.)

[6] 朱琳,朱参世.滑动窗口数据流聚类算法在IDS中的应用 [J].计算机工程与应用,2014,50(1):87-90.(ZHU Lin,ZHU Canshi.Data Stream Sliding Window Clustering Algorithm Applied in IDS [J].Computer Engineering and Applications,2014,50(1)：87-90.)

[7] LIU Ling,Tamerözsu T.Encyclopedia of Database Systems [M].New York:Springer,2009:1119-1125.

[8] SHANG Changxin,LI Ming,FENG Shengzhong,et al.Feature Selection via Maximizing Global Information Gain for Text Classification [J].Knowledge-Based Systems,2013,54:298-309.

[9] Rashedi E,Nezamabadi-Pour H,Saryazdi S.A Simultaneous Feature Adaptation and Feature Selection Method for Content-Based Image Retrieval Systems [J].Knowledge-Based Systems,2013,39:85-94.

[10] ZHANG Haichao,ZHANG Yanning,Huang T S.Pose-Robust Face Recognition via Sparse Representation [J].Pattern Recognition,2013,46(5):1511-1521.

[11] Alonso-Gonzlez C J,Moro-Sancho Q I,Simon-Hurtado A,et al.Microarray Gene Expression Classification with Few Genes:Criteria to Combine Attribute Selection and Classification Methods [J].Expert Systems with Applications,2012,39(8):7270-7280.

[12] 陈友,程学旗,李洋,等.基于特征选择的轻量级入侵检测系统 [J].软件学报,2007,18(7):1639-1651.(CHEN You,CHENG Xueqi,LI Yang,et al.Lightweight Intrusion Detection System Based on Feature Selection [J].Journal of Software,2007,18(7):1639-1651.)

[13] Kira K,Rendell L A.The Feature Selection Problem:Traditional Methods and a New Algorithm [C]//Proceeding of the 10th National Conference on Artifical Intelligence.San Jose:DBLP,1992:129-134.

[14] Kononenko I.Estimating Attributes:Analysis and Extensions of RELIEF [C]//Machine Learning:ECML-94.Berlin:Springer,1994:171-182.

[15] JIA Jianhua,YANG Ning,ZHANG Chao,et al.Object-Oriented Feature Selection of High Spatial Resolution Images Using an Improved Relief Algorithm [J].Mathematical and Computer Modelling,2013,58(3/4):619-626.

[16] WANG Peng,Sanín C,Szczerbicki E.Prediction Based on Integration of Decisional DNA and a Feature Selection Algorithm RELIEF-F [J].Cybernetics and Systems,2013,44(2/3):173-183.

[17] 齐滨.高光谱图像分类及端元提取方法研究 [D].哈尔滨:哈尔滨工程大学,2012.(QI Bin.Research on Hyperspectral Image Classification and Endmember Extraction Methods [D].Harbin:Harbin Engineering University,2012.)

(责任编辑：韩 啸)

IntrusionFeatureSelectionMethodsBasedonReliefF

YANG Zhiwei1,Nurbol1,JIA Xue1,HU Liang2

(1.CollegeofInformationScienceandEngineering,XinjiangUniversity,Urumqi830046,China;2.CollegeofComputerScienceandTechnology,JilinUniversity,Changchun130012,China)

The authors analyzed the intrusion feature selection methods and algorithms based on ReliefF.Combining with the characteristics,in which data points have high similarity in the same class and nonsimilarity in different classes,and optimizing the compute method of intrusion feature weight,we proposed an improved algorithm Re-ReliefF.It resolved the problems about processing efficiency with the data dimensions in network security.Experiments on the network security test datasets showed the effectiveness of the proposed algorithms,and the improved algorithm has advantages on performance compared to the traditional one.

intrusion detection;feature selection;ReliefF algorithm

10.13413/j.cnki.jdxblxb.2015.03.30

2014-08-04.

杨志伟(1989—),男,汉族,硕士研究生,从事云计算和网络安全的研究,E-mail:758408528@qq.com.通信作者:努尔布力(1981—),男,哈萨克族,博士,副教授,从事数据挖掘和网络安全的研究,E-mail:nurbol_mail@163.com.

国家自然科学基金(批准号:61163052;61303231)、国家自然科学基金重点项目(批准号:61433012)、国家自然科学基金联合基金(批准号:U1435215)、新疆维吾尔自治区青年科技创新人才培养工程项目(批准号:2014731002)、新疆大学多语种实验室开放课题和新疆大学校级创新团队资助项目.

TP309

：A

：1671-5489(2015)03-0505-06