基于Fisher-FCBF的入侵特征选择算法的研究

王浩，石研

（1.新疆大学信息科学与工程学院，乌鲁木齐 830046；2.新疆大学软件学院，乌鲁木齐 830008）

基于Fisher-FCBF的入侵特征选择算法的研究

王浩1，石研2

（1.新疆大学信息科学与工程学院，乌鲁木齐 830046；2.新疆大学软件学院，乌鲁木齐 830008）

大量的冗余和噪音数据混合于网络入侵数据中，从而影响到检测的性能和响应。因此，提出基于Fisher-FCBF算法。通过对特征的Fisher分值排序，再使用FCBF算法去冗余，结合SVM，建立分类特征模型，在不降低准确率的前提下，选出最优特征子集，结果表明所提出的方法能够在保证分类准确率的情况下，降低至少11%-21%的计算时间。

入侵检测；特征选择；Fisher分；FCBF

0 引言

高吞吐量技术的快速发展导致数据的维度和样本大小成指数增长[1]。高维的数据使得入侵检测将会消耗巨大的资源和时间，而如何进行快速有效的检测，将会成为网络入侵检测亟待解决的问题。是以，为解决入侵检测系统的性能和准确性，将特征选择引入了入侵检测中[2]。

特征选择作为一种常见的降维方法是模式识别的研究热点之一。它是指从原始的特征集合中，去除不相关和冗余的特征，使选择后的特征子集为较优的特征子集。在原始数据中，每一个特征的重要程度都不相同，重要的是找到对分类器影响较大的特征，去掉影响不大或者是相关性不大的特征[3]。Fisher分是一种有效的特征选择方法，可以很好地去除噪声数据，有效地降低特征空间。

本文通过将特征选择引入到入侵检测当中，在减少了安全数据的维度的同时降低了计算时间。本文将Fisher分和FCBF相结合，提出一个新的算法Fisher-FCBF，该算法通过特征的重要度对特征进行评估，从而得到较优的特征子集。实验将SVM（Support Vector Machine）作为分类算法，从准确度、漏报率、预测时间、误报率等四方面对实验数据进行评价，最终说明所提的算法有效降低了运行的时间。

1 特征选择方法

1.1 Fisher分

Fisher分是一种基于距离度量的特征选择方法［4］。其主要思想是按照Fisher准则计算特征的比值，并将该比值作为该特征的Fisher分，比值愈大，说明该该特征对分类器越重要，分类的能力越强，在分类时，可以使得其在类内的距离尽量的小，而类间的距离尽量的大[4]。Fisher分在文本处理、图像识别等领域有相关的应用，但主要还是应用于预处理。Jiang L等[5]将半监督核边界Fisher分析用于仪表误差诊断中的特征提取，由于Fisher方法同时考虑类内和类间的散度，能够清晰的发现数据集的内部结构。Lu JC等[6]将Fisher判别准则应用于隐藏分析特征选择中，用于有效地减少数值特征的维度。

首先假定存在训练集样本 {(x1,y1),(x2,y2),(xi,yi),…(xl,yl)}，其中，l为样本数量；xi∈Rn，i=1,2,…,l,n为特征向量维数；yi={-1,1}l为类别标号，1——正类，-1——负类。而正类样本的集合X1，个数为l1；负类样本集合记为X2，个数记为l2。以Fk表示Fisher分，则：

式中：Sb——类间离散度，表示不同类样本间的距离；Sw——类内离散度，表示同类样本间的距离，计算公式如下：

通过运行Fisher分，我们可以得到该算法的特征比值，为了进一步选出较优的特征子集，将会结合SVM算法以检测率和误报率为指标来选择，因此我们定义了特征分类值[4]。

式中：i为第i维特征或第i组特征；DRi为特征的检测率；FDi为特征的误报率。

1.2 FCBF 算法

基于快速关联的过滤算法（FCBF）是一种快速过滤的特征选择算法，使用对称的不确定行来度量两个特征的相关性，通过度量特征-类别以及特征-特征之间的关联，来选择最优的特征。其主要思想是根据定义的 C-相关（SUi,c，特征与类的关系）和 F-相关（SUi,j，特征与特征的关系），从原始特征集合中去除C-相关值小于δ（由用户定义）的特征，然后对剩余的特征进行冗余分析，最后得到一个较优的特征子集。算法的伪代码如下所示：

FCBF通过选择所有主要特征和删除其余特征来进行近似相关性和冗余分析。它使用C-相关和F-相关来确定特征冗余，适用于多分类问题中。在应用方面，Gharavian D等人将FCBF和GA优化的GA优化的基于FAMNN的情感识别器，显著地改善了语音处理系统中语音情感的识别[7]。Liu Y等将改进的FCBF和相关矢量机（RAM）相结合，有效地提取了相关但非冗余的故障特征，并准确的识别柴油机的故障类型[8]。

2 Fisher-FCBF特征选择方法

2.1 方法模型

Fisher分可用于特征选择与特征提取，是特征降维的一种有效的方法。其主要思想是通过对样本的变换，将样本投影到一条直线上，使样本的投影能更好地分类[3]，将多维问题简化为一维问题来解决。Fisher分需选出在同一特征下，其类内的距离尽量小，类间距离尽量大的特征，这样的特征为强鉴别的特征，可提高类别间的区分能力。Fisher算法可以删除不相关和辨别性能较差的特征，但是却不能剔除数据中的冗余特征。FCBF算法更注重特征与类别、特征与特征之间的关系，能够有效地去除冗余特征，同时在处理高维数据时该算法更加高效。因此，本文提出了Fisher-FCBF算法，选择两个算法的优点，从而实现了一种组合式的特征选择方法。算法的流程图如图1所示。

图1 Fisher-FCBF算法流程图

通过Fisher分去除不相关或者相关性较小的的特征，对特征进行初选。然后使用FCBF对特征进行更进一步的筛选，剔除冗余特征，最终得到较优的特征子集。最终，采用准确率、预测时间、误报率等作为评价指标，利用SVM分类器来评估得到的较优的特征子集。

2.2 Fisher-FCBF算法的基本定义

定义1：Fisher-FCBF的算法矩阵，可以表示为二元组D:(Fn,Cm)。其中Fn表示数据的特征维度为n维。Cm表示该数据共有m类。

定义2：Fisher-FCBF中Fisher算法的特征分类值FTRi和特征子集S。其中，N代表原始特征的维度。FTRi代表特征分类值，特征的检测率越高，误报率越低，其特征的分类值越大，就越重要。S即将FTRi按大小进行排序，选取FTRi值较大的对应的特征作为特征子集S。

定义3：C-相关：任何一个特征Fi与类之间的关系，记为SUi,c；F-相关：任意两个特征Fi与Fj之间的关系，记为SUi,j。

定义4：Fisher-FCBF中FCBF的参数有：不确定性SU(X ,Y )、启发式参数Spi，S+pi，S-pi特征子集Sbest[9]。 δ由用户自定义，X表示为特征，Y为类别标签，C-相关性的值越大，而F-相关的值越小，则该特征为优越特征。如果特征Fj满足SUj,i≥SUi,c≥δ，则Fj为Fi的冗余特征，构成冗余特征集 Spi再判断，如果SUj,i>SUi,c，则构成S+pi，剩下的特征构成S-pi。

2.3 算法描述

输入：训练集、原始特征集D。

输出：特征子集S'。

（1）输入KDD99数据集，特征个数为N，初始化的FTRi=0；

（2）根据公式计算特征集D上的每维特征Fisher值Fki，并对其进行降序排列，使用SVM，测试并计算模型的正确率和误报率，最后计算FTRi，形成一个去相关性的特征子集S；

（3）将子集S作为FCBF的输入，选取合适的参数值δ；

（4）计算每个特征的C-相关（即SUi,c）；

（5）根据参数Spi，S+pi，S-pi来剔除数据中的冗余特征；

（6）当{S}→∅，输出子集S'。

3 实验

环境：6×2.6GHz CPU，32GB内存，64位Windows 8系统，算法的实现采用64位MATLAB R2012a[10]。

数据集：采用KDD CUP 1999［11］作为入侵检测数据，其中包含一种正常数据和四种攻击数据。

3.1 评估指标

使用IDS的常用指标漏报率[12]、正确率[12]、误报率[12]、检测时间[12]作为本次的评价准则。表1为混淆矩阵[12]。

表1 混淆矩阵

其中，TN表示正常数据被误认为异常，TP表示将异常数据归类到正常类。根据表1，给出了以下的一些计算方式：

3.2 实验过程

将Fisher-FCBF算法与Fisher分、FCBF、SVM算法做一个对比。实验室用KDD99数据集，并5类指标作对比，过程如下：

（1）特征选择：采用最佳参数对KDD99[11]数据进行数据的预处理，然后将利用算法所获得的特征权值进行结果对比与选取，从而得到较优的特征子集；不同的得到对应的特征子集。

（2）结果验证：SVM采用5折交叉验证的方法和同样参数将，将获得的不同的结果用得出的四种评估指标进行结果的对比与分析。

3.3 实验结果与分析

（1）Fisher分的特征选择

按照公式（1）计算各个特征的Fisher值并对其进行排序，并查看单个特征Fisher分值对分类器的影响，计算了特征的漏报率，如图2所示。

图2 Fisher分的漏报率情况

从图2可以看出，随着Fisher分值的下降，特征对分类器的影响逐渐减小，相关的特征也越来越少；并且按照Fisher比值的排序，可以看出在22个特征之后的特征对分类器的影响不大，可以视为不相关或相关性较小的特征，可以将其去掉。

根据公式（5）计算了特征集的Fisher分，并查看特征集的特征分类对分类的影响，如图3所示。

从图3可以看出，当特征维度为7、18、27时都达到了一个峰值，但是在维度为27时，特征测度值达到最大，因此进一步建立了特征模型，通过对7、18、27个特征进行正确率、误报率、测试时间的比较，随着特征数的增加，正确率和测试时间也随之增长，而误报率在逐渐降低，因而当特征维度为27时，这时的特征子集的正确率最高，误报率最低，同时测试时间也最大，最后，将特征子集的特征维度定为27。

图3 特征集的特征分类影响

（2）FCBF的参数选择

本文通过选取不同的δ值进行多次实验对比，从而选择出相对较优的δ值。

表2 FCBF算法δ值得选择

从表4中可以看出，随着δ的增加，准确率保持恒定，再此情况下，δ选取0.01最佳，漏报率、误报率最小。

3.4 实验结果与分析

以下为四种评价

通过以下四种指标对四种算法进行比较，结果如表3所示。

表3 四种算法的比较

图4 四种算法的特征数、准确率和预测时间的对比

根据图4可知，Fisher-FCBF算法在一定程度上减少了特征选择的数量，明显的提高了预测时间。其中SVM的准确率最高，FCBF的最低。图5为四种算法在漏报率和误报率之间的对比。

实验结果表明这4种算法的漏报率都是比较低的，而改进的Fisher-FCBF算法，在误报率方面有一定的降低。

通过以上实验的对比分析，可以得出Fisher-FCBF在准确率只是轻微下降的情况下，数据的特征维度有明显的减少，在分类算法的时间上有显著地降低，有较好的鲁棒性。

图5 四种算法的误报率和漏报率的对比

4 总结

大量的冗余和噪音数据混合于网络入侵的数据中，影响了系统的检测效率和检测速率。因此本文提出了Fisher-FCBF特征选择方法，去除了数据集中的不相关与冗余数据，在保证准确率的情况下，不仅降低了数据的维度、计算复杂与时间复杂，同时减少了误报率和预测时间。因次改进的Fisher-FCBF算法是一种有效的特征选择算法。

[1]Tang J,Alelyani S,Liu H.Feature Selection for Classification:A Review[J].Documentación Administrativa,2014:313-334.

[2]杨杰明.文本分类中文本表示模型和特征选择算法研究[D].吉林大学,2013.

[3]张润莲,张昭,彭小金,等.基于Fisher分和支持向量机的特征选择算法[J].计算机工程与设计,2014（12）:4145-4148.

[4]Jiang L,Xuan JP,Shi TL.Feature Extraction Based on Semi-supervised Kernel Marginal Fisher Analysis and Its Application In Bearing Fault Diagnosis[J].Mechanical Systems and Signal Processing,2013,41（1）:113-126.

[5]Lu JC,Liu FL,Luo XY.Selection of Image for Steganalysis Based on the Fisher Criterion[J].Digital Investigation,2014,11（1）:57-66.

[6]Hossain M A,Jia X,Pickering M.Subspace Detection Using a Mutual Information Measure for Hyperspectral Image Classification[J].Geoscience&Remote Sensing Letters IEEE,2014,11（2）:424-428.

[7]Jixiang Y E,Wang C.Application of Improvement of F-score Algorithm in Speech Emotion Recognition[J].Computer Engineering&Applications,2013,49（16）:137-141.

[8]Gharavian D,Sheikhan M,Nazerieh A,et al.Speech Emotion Recognition Using FCBF Feature Selection Method and Ga-optimized Fuzzy Artmap Neural Network[J].Neural Computing and Applications,2012,21（8）:2115-2126.

[9]Liu Y,Zhang J,Ma L.A Fault Diagnosis Approach for Diesel Engines Based on Self-adaptive WVD,Improved FcBF and PECOC-RVM[J].Neurocomputing,2016,177（C）:600-611.

[10]黄春虎,努尔布力,解男男,等.基于Re—FCBF的入侵特征选择算法研究[J].激光杂志,2016（1）:103-107.

[11]The UCI KDD Archive.KDD Cup 99 DataSet[EB/OL].http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html.

[12]郭春.基于数据挖掘的网络入侵检测关键技术研究[D].北京邮电大学,2014.

Research on Feature Selection Algorithm in Intrusion Detection Based on Fisher-FCBF

WANG Hao1，SHI Yan2

（1.School of Information Science and Technology，Xinjiang University，Urumqi 830046；2.School of Software，Xinjiang University，Urumqi 830008）

A large amount of redundancy and noise data are mixed in the network intrusion data,thus affects the performance and re⁃sponse of the detection.By sorting the Fisher scores of the feature,uses the FCBF algorithm to reduce the redundancy and us⁃es SVM to establish the classification feature model.The optimal feature subset is selected without reducing the accuracy. The results show that the proposed method can reduce at least 11%-21%of the calculation time in the case of classification accuracy to ensure.

王浩（1991-），女，湖北黄冈人，硕士研究生，研究方向为网络安全、特征选择

2017-03-16

2017-05-10

国家自然科学基金项目（No.61163052、No.61303231、No.61433012）、国家自然科学基金联合基金项目（No.U1435215）

1007-1423（2017）15-0007-06

10.3969/j.issn.1007-1423.2017.15.002

石研（1991-），女，河南商丘人，硕士研究生，研究方向为无线传感器网络节点定位和网络安全

Intrusion Detection;Feature Selection;Fisher Score;FCBF