基于随机k-近邻集成算法的网络流量入侵检测.pdf

第2 2 卷第3 期2023年9 月doi:10.12194/j.ntu.20221205003引文格式：张承烨，李卓轩，曹进德.基于随机k-近邻集成算法的网络流量入侵检测 J.南通大学学报（自然科学版），2 0 2 3，22(3):26-32.南通大学学报（自然科学版）Journal of Nantong University(Natural Science Edition)Vol.22No.3Sept.2023基于随机K-近邻集成算法的网络流量入侵检测张承烨1，李卓轩2,3，曹进德2,3*（1.东南大学人工智能学院，江苏南京2 1118 9;2.东南大学数学学院，江苏南京2 1118 9；3.江苏省网络群体智能重点实验室，江苏南京2 1118 9)摘要：为了提高网络入侵检测模型的准确率与泛化性，提出基于随机k-近邻集成算法的网络流量入侵检测模型。首先，该模型提出一种集成赋权距离，来提高预测精度；其次，采用一种随机策略的集成方法对k-近邻模型进行集成，从而提高了其在异常检测过程中的全局和局部优化能力；然后，利用并行计算的方法提高了算法运行的效率；最后，构建了基于随机k-近邻集成算法的网络入侵检测模型，并采用KDD99数据集进行实验。实验结果表明，基于随机k-近邻集成算法相对于其他模型具有更好的检测效果，准确率和召回率分别达到9 9.0 5%和9 1.9 6%。关键词：网络入侵检测；k-近邻模型；集成赋权距离；随机子空间；并行计算中图分类号：TP181based on random k-nearest neighbor ensemble algorithm(1.School of Artificial Intelligence,Southeast University,Nanjing 211189,China;2.School of Mathematics,Southeast University,Nanjing 211189,China;3.Jiangsu Provincial Key Laboratory of Networked Collective Intelligence,Southeast University,Nanjing 211189,China)Abstract:To improve the accuracy and generalization of network intrusion detection models,a model based on therandom k-nearest neighbor(k-NN)ensemble algorithm is proposed for network flow intrusion detection.Firstly,themodel introduces an ensemble weighting distance to enhance prediction accuracy.Secondly,a random strategy is em-ployed to integrate the k-NN models,thereby improving their global and local optimization capabilities in the anoma-ly detection process.Furthermore,parallel computing techniques are utilized to enhance algorithm efficiency.Lastly,a network intrusion detection model based on the random k-nearest neighbor ensemble algorithm is constructed andexperimented with using the KDD99 dataset.Experimental results demonstrate that the random k-nearest neighbor en-semble algorithm outperforms other models,achieving accuracy and recall rates of 99.05%and 91.96%,respectively.Key words:network intrusion detection;k-nearest neighbor model;integrated weighted distance;random subspace;parallel computing文献标志码：ANetwork intrusion detectionZHANG Chengye,LI Zhuoxuan?3,CAO Jinde2.3文章编号：16 7 3-2 3 40(2 0 2 3)0 3-0 0 2 6-0 7收稿日期：2 0 2 2-12-0 5接受日期：2 0 2 3-0 3-2 7基金项目：江苏省网络集体智能重点实验室项目（BM2017002）第一作者简介：张承烨（2 0 0 1一），男，本科生。*通信联系人：曹进德（19 6 3 一），男，教授，博士，博士生导师，主要研究方向为复杂网络、群体智能算法、系统科学等。E-mail:张承烨，等：基于随机k-近邻集成算法的网络流量入侵检测随着互联网技术的快速发展与普及，网络安全问题变得日益突出，木马程序、蠕虫病毒、DDOS(distributed denial of service)攻击等大量的威胁与安全隐患扰乱了社会正常情况的运作与经济的可持续发展。随着人工智能技术应用的发展-2 1,网络流量异常检测方法作为网络安全系统中人侵检测技术实现的核心，受到国内外学者的广泛关注。熊钢等3针对网络空间安全中面临的威胁进行了综述，将入侵检测系统功能分为两大类：异常检测软件系统和签名检测系统。异常检测软件系统在检测未知攻击方面表现更理想，然而会产生很高的误报率。因此，提高人侵检测系统的检测精度和学习速度仍然是一项艰巨的任务。Papamartzivanos等提出了名为Dendron的人侵检测系统,通过遗传算法对决策算法进行优化，旨在生成准确且无偏的决策树,能够检测常见和罕见的侵人性攻击。生龙等5为了提高网络入侵检测模型的准确率与泛化性,采用核主成分分析提取人侵性攻击的特征，通过改进的引力搜索算法对混合核极限学习机进行优化。徐国天回提出一种基于裁剪树方法优化的k-近邻（k-nearest neighbor,k-NN)的入侵检测模型,维持较高查询效率。王月等7 提出名为imTk-NN的网络入侵检测模型，采用改进的三元组网络和k-近邻算法进行组合预测，精度和效率都有大幅提升。综上，本文提出一种新的k-NN集成算法随机 k-NN(random k-nearest neighbor,Rk-NN)算法，应用于网络异常流量检测。主要包含以下部分：1)提出一种基于熵权法与变异系数法的集成赋权欧氏距离;2)采用一种随机策略的集成方法,首先采用bootstrap再抽样技术,对抽样后的数据集随机选取特征构成随机子空间，然后生成多个组件k-NN分类器，最后对整个集成方法进行并行优化；3)对每一个子k-NN分类器按照均匀分布随机生成k值。1相关理论基础1.1k-NN算法k-NN分类算法8 简单、易于实现，是机器学习领域的一个经典机器学习算法，引起了人们的广泛关注9 。k-NN算法模型已广泛应用于文本挖掘、模27式识别等领域，它是一种基于实例的学习法，可以根据被预测对象与已知对象之间的相似度进行归类，并不能显式地构建模型,k-NN算法模型过于依赖待分类具体实例与训练集中最近的k个邻居。对于训练集D=(;,y,）li=1,2,n),待分类实例z=（x,y），表1给出k-NN的分类过程。表1k-NN算法Tab.1k-NN algorithm算法1k-NN算法输人：训练集D，待分类实例z，近邻值k；输出：分类结果h-NNo计算z与训练集D中每个数据之间的距离根据k值确定出k近邻集D计算类别 he-NN=argmax,Z(ai)eD,V(l=y)retun he-N算法1中：l为类标签；y,是第i个近邻的类标签；V()为一个指示函数，当条件为真时返回1,当条件为假时返回0。与神经网络和决策树分类器有许多参数不同，k-NN分类器只有两个参数，即用于计算给定测试样本与训练样本的距离度量和邻居k的数量，这使得k-NN的优化研究具有挑战性。k-NN可以根据与该实例最近的k个实例进行归类，然而的优与劣将完全决定着k-NN分类的使用效果。诚然,k-NN算法的关键之一在于如何采纳一个合理的k值。如果k值取得过小，则算法易受噪声的影响，使分类结果不稳定；k值取得过大，则近邻集中含有太多其他类别的实例，导致分类错误，同时，过大的k值也会增加算法的时间总开销。理论上可以通过采用枚举法，循环遍历所有可能的k值,最后从中选出最好的k值作为近邻数。但在实际应用中，枚举法带来的时间总开销一般说来是根本无法接受的。1.2bagging集成方法1996年,Breimanl提出bagging集成方法，它是最早也最简单的集成算法之一。借助bootstrap抽样从原始训练集得到多个同等规模的训练集合的子集，接着使用相同学习算法模型在这些训练集上训练出多个基分类算法，最终以多数投票方式组合所28有分类结果。相对于新的未见实例，由训练阶段得到的个体分类算法分别对其所属类别投票，总票数最大的类别即是最终的决策结果。所提出的bagging集成算法具体直观有效，尤其适用于数据集很小的情景。表2 给出了提出bagging算法描述2。表 2 bagging 算法Tab.2 bagging algorithm算法 2 bagging 算法输人：训练集D,组件分类器L,组件个数M；输出：分类结果H。form=0,1,2,3,M doDm.=bootstrap-sample(D)hu=L(Dm)end forretum H(x)=argmax,Z%-,(h.(a)=y)虽然bagging集成方法在决策树(decision tree,DT)12和神经网络(neural network,NN)13上取得了巨大的成功，但它很难在k-NN分类器上很好地工作。因为k-NN是一个稳定的分类器，而bag-ging使用bootstrap再抽样技术来生成准确但多样的组件分类器，这对不稳定的机器学习方法如决策树和类感知机算法的工作是更有效的。2 Rk-NN算法2.1集集成赋权距离为了更合理地分析各个数据对象之间的差异程度，本文利用一种信息熵与变异系数结合的集成赋权法来计算各数据对象的赋权欧式距离。变异系数法通过利用各项特征反映的信息计算得到特征的权重，它反映的是特征值的差异程度及数据的分布情况，假设数据集X有m个对象和n个特征,变异系数权重计算方法为U;=8,/x,w,=0/Z-1U,其中：,为第i项指标的标准差；x,为第i项指标的平均数;w,为变异系数法确定的第i个特征权重。在信息论中,熵是对数据不确定性的一种度量南通大学学报（自然科学版）和描述，熵值越大，数据不确定性越小；反之亦然，熵值越小，不确定性则越大。一个方案的无序性和随机性的程度可以由熵特性来确定。此方法可以消除单位或平均值不同对多种数据变异程度的影响。假设数据集X有m个对象和n维属性,设标准化后的数据为x，熵权计算方法为P,=x/2-1g,e,=-kZ-P,ln(P,),g:=1-ei,uj=g/2,j-1g,其中:e,为第j个特征的熵值,k0,e,0,h与样本量m有关，一般令k=1/ln(m）,则0 e,1;对于第j项指标，指标值x,差异越大，熵值越小，g,越大，在计算距离时占比越大；权重w,为熵权法确定第j个特征的权重。本文通过线性加权组合的方法，综合值法与变异系数法的权重确定结果,增加权重确定的科学性。其计算公式为其中w,为组合权重。最终通过集成赋权法，确定赋权欧氏距离为d(x,x,)=VZj-ij(am-x)加权欧氏距离可以用来判断不同数据对象之间的相似程度，可以提高分类精度。2.2阳随机策略优化为了提高k-NN的预测精度，首先进行随机特征（输入变量)选取，在引入特征随机性的同时，减小相关系数而保持强度不变。本文对训练集的输人属性进行随机扰动，从最初训练集的属性集中抽取出若干个属性子集，基于每个子集训练一个k-NN组件分类器，不同的“子空间”提供了观察数据的不同视角。本文通过设定特征抽取比例，对训练集的原始输人特征进行按比例随机选取，再进行boot-strap抽样,最终生成随机特征空间,过程如表3所示。显然，上述方案能解决bagging算法对于k-NN这种稳定分类器优化效果差的问题。2023年张承烨，等：基于随机k-近邻集成算法的网络流量入侵检测表3RS算法Tab.3RS algorithm算法3RS算法输人：训练集D，特征抽取比例；输出：随机训练集%。按照特征抽取比例，对训练集D进行特征抽取，生成子集D。对D。进行bootstarp抽样，得到随机训练集return.通常选取超参k值进行k-NN算法的优化，为数据集找到最优k，并依此进行分类。因为没有先验知识,直接指定k值具有很大的盲目性，同时,穷举法又由于时间开销过大而不可取。本文提出一种对多个k-NN组件分类器k值的选取方法，按照区间Q=N,2N+1均匀分布生成单一k-NN组件分类器的值,为k,U(2),i=1,2,.,M,其中：i为k-NN组件分类器编号;M为k-NN组件分类器总个数。算法过程如表4所示。表4Rk-NN算法Tab.4Rk-NN algorithm算法4Rk-NN算法输人：训练集D,k-NN组件分类器L，组件个数M,特征抽取比例，待分类实例%；输出：分类结果H。K=(k,k,U(2),i=1,2,M)for m=0,1,2,3,.,M dok=kmEK=R(D,)hm=Lm(m,h,2)end for计算类别:H=argmax,Zm=I V(hm=y)return H由于算法有良好的并行性，本文对Rk-NN算法分别实现数据处理的并行化，实现模型训练的并行化。2.3基于Rk-NN算法的网络入侵检测模型基于以上内容,本文提出了一种新型的网络人侵检测模型Rk-NN算法的网络入侵检测模型，29.结构如图1所示。数据集数据集拆分图1基于Rk-NN算法的网络入侵检测模型5Fig.1 Network intrusion detection model based onRk-NN algorithml5该模型的具体步骤如下：Step1车输人数据集，初始化Rk-NN算法；Step2对数据集进行划分,拆分成训练集和测试集；Step3使用预处理的训练数据集生成历史数据搜索空间；Step4使用测试数据集评估获得的最佳Rk-NN模型的性能;Step5输出模型检测结果的评估指标。3实验与分析3.1实验数据为了验证Rk-NN算法的有效性,选取6 组 UCI数据集中的公开测试数据（见表5)和KDD99数据集进行实验。表 5 UCI 数据集6Tab.5UCI datasetla数据集类别数量wine3ZOO7sonar2ionosphere2diabites2balance-scale3KDD99数据集中共包含2 3种攻击类型，可以分为四大攻击类别:DoS、PRB、U 2 R和R2L15。由于利用KDD99完整的数据集在进行机器学习算法训练时很复杂,因此大多数研究人员都使用了KDD99数据集中10%子集作为实验数据。表6 给出了KDD99数据集的详细信息，其中训练数据集和两个测试数据集分别表示为To、T I 和T2。训练数据集 T。与测试数据集T一起用来验证Rk-NN算法的有效性。此外，本文还利用测试数据集T进行Rk-NN算法与其他研究模型的性能比较。Rh-NN模型样本数量178101208351768625预测结果数据维度141861359530.Tab.6KDD dataset division/7类别T。Normal200Dos60PRB40U2R30R2L603.2实验结果评价指标为了评估Rk-NN算法的性能，采用准确率(accuracy,Acc)和F-score值,对算法在UCI数据集上的表现进行评价。为了评估Rk-NN算法在网络人侵检测中的效果，采用精准率（precision）和F-score值作为每类攻击的评估指标；准确率（ac-curacy，A c c）、召回率（recall）、平均F-score（me a nF-score,MF)作为数据集整体的评估指标。在数据集中的网络连接可以分为正常（标记为0）、攻击（标记为1,2,3,4)两大类。计算方式如表7 所示。表7 评价指标Tab.7Evaluation index名称计算公式准确率(TP+TN)/(TP+TN+FP+FN)精准率TPI(TP+FP)召回率TPI(TP+FN)F-score(1+)precisionxrecal(precision+recall)平均F-score其中：TP(真阳性)为正样本被正确预测为正样本；TP（假阳性)为负样本被错误预测为正样本；TN(真阴性)为负样本被正确预测为负样本;FN(假bgk-NN数据集Accwine98.15ZOO90.32sonar88.89ionosphere93.40diabites73.61balance-scale89.36南通大学学报（自然科学版）表6KDD数据集划分I7T1 000500500521000(Z,F-.score,)/nTab.8Comparison of different algorithms on UCI datasetRk-NNMF98.3371.4388.3192.7869.8162.182023年阴性)为正样本被错误预测为负样本,在F-score中令=1。T23.3实验结果分析对比10.0003.3.1Rk-NN算法在UCI数据集上的表现40.000在UCI数据集上将Rk-NN算法与同类变种算400法进行对比（见表8）,对比算法分别为：k-NN算法、52bagging集成的k-NN算法和改进距离的k-NN算100法，其中k-NN算法，bagging集成的k-NN算法采用欧氏距离，Rk-NN算法采用集成赋权距离。由表8 可看出,Rk-NN算法具有更好的分类精度。相比欧式距离,Rk-NN算法采用集成赋权距离能有效挖掘数据之间的联系,即Rk-NN通过权重计算能更有效描述不同样本之间的联系，具有更好的分类性能；不仅保持bgk-NN集成算法的优点，能有效描述样本之间的联系，而且通过随机集成策略构建随机子空间,Rk-NN算法能有效利用数据集上的信息形成分类器间的差异，强化不同分类器中信息的重要性,提高集成的效果,具有更高的分类性能。Rk-NN算法相较k-NN算法在准确率上平均提升了13.00%，在平均F-score指标上平均提升了15.2 0%。3.3.2Rk-NN算法在KDD99数据集上的表现本文利用训练数据集T。和测试数据集T对Rk-NN算法性能进行分析，对于不同攻击类别进行比较，如图2 所示，性能如表9 所示。如表9 所示,Rk-NN算法整体达到了一个较高水平，针对Normal类别，召回率达到9 9.40%，但精准率只有9 0.8 6%,存在误报的情况；对于Dos攻击能够精准识别，精准率达到9 9.6 0%，同时F-score和召回率也分别达到了9 9.7 0%和9 9.8 0%；对R2L,U2R和PRB的识别，本文算法也达到了一个表8 在UCI数据集上的不同算法比较改进距离的k-NNAccMF74.0773.3183.8767.5374.6073.4784.9181.7671.4368.9787.2360.84%k-NNAccMF75.9375.1787.1070.6776.1975.9785.8583.6371.4367.4286.1760.63Acc74.0783.8774.6083.9671.0085.64MF72.6162.6073.4780.4468.2459.88张承烨，等：基于随机k-近邻集成算法的网络流量入侵检测较高的水平。precisionF-scorerecall1.0r0.80.60.20DosPRBR2LU2RNormal攻击类别图2 Rk-NN算法检测结果Fig.2Rk-NN algorithm detection results表9 不同攻击的检测性能比较Tab.9Comparison of detection performance ofdifferent attacks%攻击精准率Normal90.86Dos99.60PRB99.78U2R94.00R2L99.363.3.3Rk-NN算法与其他算法的对比对于在测试数据集T2上，将本文提出的基于Rk-NN算法的网络入侵检测模型与其他常用的机器学习算法如：支持向量机（supportvectormachine，SVM)算法、k-近邻(k-nearest neighbor,k-NN)随机森林（random forests,RF）模型、决策树（decisiontree,DT)算法、极限梯度树（extrme gradient boost-ing,XGBoost)模型算法分别进行测试,结果如表10所示。表10 本文算法与其他算法比较结果Tab.10 Compare with other algorithms算法Acc本文算法99.05SVM97.67k-NN97.87RF98.68DT96.59XCBoost97.87Rk-NN模型检测结果的评估指标准确率、平均F-score和召回率的值分别为9 9.0 5%、9 7.44%和91.96%。本文算法相较SVM算法在准确率、平均F-score、召回率分别提升了1.41%、2.0 4%和42.9 5%；31.相较DT算法在准确率、平均F-score、召回率分别提升了2.55%、1.2 9%和51.2 5%；相较XGBoost算法在准确率、平均F-score、召回率分别提升了1.2 1%、0.15%和2 7.6 5%；相较RF算法在平均F-score没有提升，在准确率、召回率分别提升了0.37%、12.16%。可以看出，与其他方法相比，本文算法在流量入侵检测上具有更高的分类精度并且有更高的召回率。这充分说明Rk-NN模型在KDD99数据集上具有更好的性能。4结论本文所提的Rk-NN模型在计算距离时引入一F-score召回率94.9499.4099.7099.8095.7392.0092.1690.3896.6194.00%MF召回率97.4491.9695.4964.3365.5186.5997.5681.9996.2060.8097.2972.04种集成赋权的欧式距离，采用权法和变异系数法计算不同特征之间的权值差异性，使得能够有效识别出关键特征。加人集成赋权欧式和随机策略优化方法，提升各个子分类器差异程度，提高了在网络人侵检测中的识别精度。Rk-NN模型有良好的并行性，本文通过并行优化，提升算法运行效率。下一步将通过对Rk-NN模型进行模型剪枝，提升模型精度和算法效率，建立更加实时高效的检测模型，完善网络流量人侵的检测体系。参考文献：1李卓轩，赵璇，曹进德，等.政务服务中群众留言答复意见评价模型J.南京信息工程大学学报（自然科学版),2 0 2 2,14(2):17 8-18 5.LI Z X,ZHAO X,CAO J D,et al.Evaluation of repliesto public consultations in government serviceJ.Journal ofNanjing University of Information Science and Technology(Natural Science Edition),2022,14(2):178-185.(inChinese)【2 李卓轩，林凯迪，郭建华，等.基于车联网数据的运输车辆安全评价模型J.南通大学学报（自然科学版），2020,19(1):26-32.LI Z X,LIN K D,GUO J H,et al.Transportation vehiclesafety evaluation model based on vehicle network data.Journal of Nantong University(Natural Science Edition),2020,19(1):26-32.(in Chinese)3熊钢，葛雨玮，褚衍杰，等.基于跨域协同的网络空间威胁预警模式J.网络与信息安全学报，2 0 2 0，6(6)：88-96.XIONG G,GE Y W,CHU Y J,et al.Model of cy-32berspace threat early warning based on cross-domain andcollaborationJ.Chinese Journal of Network and Informa-tion Security,2020,6(6):88-96.(in Chinese)4PAPAMARTZIVANOS D,GOMEZ MARMOL F,KAM-BOURAKIS G.Dendron:genetic trees driven rule induc-tion for network intrusion detection systemsJ.FutureGeneration Computer Systems,2018,79:558-574.【5】生龙，袁丽娜，武南南，等.基于CSA与DE优化混合核ELM的网络异常检测模型J.计算机工程，2 0 2 2，48(6):146-153.SHENG L,YUAN L N,WU N N,et al.Network anomalydetection model based on GSA and DE optimizing hybridkernel ELMJ.Computer Engineering,2022,48(6):146-153.(in Chinese)6徐国天.网络入侵检测中K近邻高速匹配算法研究信息网络安全，2 0 2 0，2 0(8）：7 1-8 0.XU G T.Research on K-nearest neighbor high speedmatching algorithm in network intrusion detectionJ.Net-info Security,2020,20(8):71-80.(in Chinese)【7】王月，江逸茗，兰巨龙.基于改进三元组网络和K近邻算法的入侵检测J.计算机应用，2 0 2 1，41（7)：19 9 6-2002.WANG Y,JIANG Y M,LAN J L.Intrusion detectionbased on improved triplet network and K-nearest neighboralgorithmJ.Journal of Computer Applications,2021,41(7):1996-2002.(in Chinese)8 COVER T,HART P.Nearest neighbor pattern classifica-tionJ.IEEE Transactions on Information Theory,1967,南通大学学报（自然科学版）13(1):21-27.9 WU X D,KUMAR V,QUINLAN J R,et al.Top 10 algo-rithms in data miningJJ.Knowledge and Information Sys-tems,2008,14(1):1-37.10 GATES G.The reduced nearest neighbor rule(corresp.).IEEE Transactions on Information Theory,1972,18(3):431-433.11 BREIMAN L.Baging predictorsJ.Machine Learning,1996,24(2):123-140.12 KOCEVD,VENS C,STRUYF J,et al.Tree ensemblesfor predicting structured outputsJ.Pattern Recognition,2013,46(3):817-833.13 TIAN J,LI M Q,CHEN F Z,et al.Coevolutionary learn-ing of neural network ensemble for complex classificationtasksJJ.Pattern Recognition,2012,45(4):1373-1385.14杜磊，杜星，宋擒豹.一种k-NN分类器k值自动选取方法.控制与决策，2 0 13，2 8(7)：10 7 3-10 7 7.DU L,DU X,SONG QB.An automatic selection methodof k in k-NN classifierJJ.Control and Decision,2013,28(7):1073-1077.(in Chinese)15 TAVALLAEE M,BAGHERI E,LUW,et al.A detailedanalysis of the KDD CUP 99 data setCJ/Proceedings ofthe 2009 IEEE Symposium on Computational Intelligencefor Security and Defense Applications,July 8-10,2009,Ottawa,ON,Canada.New York:IEEE Xplore,2009:1-6.（责任编辑：仇慧）2023年