信息安全评估日志数据的一种混合聚类算法.pdf

收藏

编号:20181110221756264424    类型:共享资源    大小:414.72KB    格式:PDF    上传时间:2019-02-16
  
2
金币
关 键 词:
PDF 信息安全 pdf 评价信息安全 的一个 聚类算法 聚类的安全 评估方法 的聚类方法 数据的聚类 数据聚类 聚类的 混合数据 数据聚类算法 信息数据
资源描述:
第23卷第10期 重庆.Y-学院学报(自然科学) 2009年10月 V01.23 No.10 Journal of Chongqing Institute of Technology(Natural Science) Oct.2009 信息安全评估日志数据的一种混合聚类算法 陈庆枝1,陈国龙2,郭文忠2,陈仕涛2 (1.莆田学院电子信息工程学系,福建莆田351100;2.福州大学数学与计算机科学学院,福州350108) 摘 要:首先引入能够处理混合型数据的K.prototypes聚类算法,在此基础上构造了一种基 于粒子群优化算法和K—prototypes方法的混合聚类算法.利用粒子群优化算法良好的全局搜索能 力,克服K.prototypes容易陷入局部最优值的不足.实验结果表明,该算法能够避免陷入局部最优 值,具有较好的全局收敛性,并且提高了聚类的正确率和算法的稳定性. 关键词:聚类;信息安全;安全评估;粒子群优化;K—prototypes 中图分类号:TP393 文献标识码:A 文章编号:1671—0924(2009)10-0077一06 A Hybrid Clustering Algorithm for Information Security Evaluation Log Data CHEN Qing.zhil,CHEN Guo.10n92'+,GUO Wen-zhon92,CHEN Shi·ta02 (1.Department of Electronic Information and Engineering,Putian University,Putian 35 1 100,China; 2.College of Mathematics and Computer Sciences,Fuzhou University,’Fuzhou 350108,China) Abstract:There are many categorical and numerical attributes in source data of information security evaluation.When dealing with mixed data,the traditional cluster algorithms tend to converge to a local optimum or can only process numerical data.In order to solve these problems,this paper employs the K—prototypes cluster algorithm to deal with mixed numerical data,and a hybrid cluster algorithm is designed based on particle swam'!optimization algorithm and K-prototypes algorithm, combing the K—prototypes algorithm’s ability on local search and fast convergence and the particle swami optimization algorithm’S ability on global search.Experimental results show that the hybrid algorithm has better performance,strong robustness and fast convergence speed. Key words:clustering;information security;security evaluation;particle swarnl optimization; K—prototypes 在企业信息系统运行过程中,各种网络安全 设备会产生大量的日志数据,这些日志数据是信 息系统安全评估重要的威胁信息来源.如何从海 量的日志数据中快速、有效地提取安全威胁信息, 是信息系统安全评估的重要研究内容.目前,人们 已将各种数据挖掘技术引人到信息系统安全评估 ·收稿日期:2009一04—09 基金项目:国家自然科学基金资助项目(60673161);福建省自然科学基金重点项目(A0820002). 作者简介:陈庆枝(1968一),男,福建仙游人,高级工程师,主要从事计算智能、计算机网络信息安全、CAD等方面 研究;陈国龙(1965一),男,福建莆田人,博士,教授,博士生导师,主要从事人工智能、计算机网络、网 络与信息安全等方面研究. 万方数据 78 重庆工学院学报 研究当中,其中对日志数据进行聚类分析,是当前 研究的一个热点. 聚类分析是将一组事物按照事物之间的相似 性程度归结到不同的类别中,同一类别的事物具 有较高的相似性,不同类别的事物具有较低的相 似性.聚类分析已被广泛应用到数据挖掘、模式识 别、机器学习、图象处理等领域【l。J.目前常用的 聚类算法有层次化聚类算法、划分式聚类算法、基 于密度和网格的聚类算法等№J. 在划分式聚类算法中,K—means是常用的方 法.K—means方法将聚类问题转化成一个组合优化 问题,在给定的聚类数目和目标函数下,将一组数 据集合划分成几个组,使得目标函数在此划分下 达到最优.传统的K—Means方法的优点是算法效 率高,收敛速度快;不足是只能对数值型数据进行 聚类、对初始值敏感以及只对球型分布的数据有 效等.针对K—Means方法存在的问题,人们提出了 各种改进的算法.为了避免聚类算法陷入局部最 优解,人们将各种启发式寻优方法,如遗传算法 (Genetic Algorithm)“q1、粒子群优化算法 (Particle Swarm Optimization)一。¨、免疫规划 (Immune Programming)‘12】、蚁群算法‘131等应用到 聚类分析中,而为了同时处理符号型和数值型混 合数据,人们提出了K.modes【14]和K.prototypes【15】 等算法. 由于安全评估日志数据中同时存在大量符号 型和数值型属性数据,其中部分符号型属性还是 相对重要的属性,如网络协议类型、网络服务类型 等,在聚类过程中,不能简单地将这些符号型属性 去除.因此,本文中提出一种基于粒子群优化和K. Prototypes方法的聚类分析算法,利用K—prototypes 算法对同时含有符号型和连续型的混合日志数据 进行聚类分析,同时利用粒子群优化算法良好的 全局搜索能力,克服K—prototypes方法容易陷入局 部最优值的不足.仿真实验结果表明,该算法能够 避免陷入局部最优值,具有较好的伞局收敛性,并 且提高r聚类的正确率和算法的稳定性. 1 K-prototypes算法 K—means算法是一种常用的基于迭代的聚类 算法,其核心思想是对于一组给定的数据对象集 合D,给定聚类数目K和目标函数F,将D划分成 一组聚类{C。,c2,…,Cx},使得目标函数F在此 划分下达到最优.K.means算法将一个数据对象最 多只归于一个聚类,每个聚类都是全体对象集合 的一个子集. K—Means算法【161的优点是能对大型数据集进 行高效分类,算法效率高、收敛速度快,但是它仅 适合处理数值型数据,同时由于采用的是爬山算 法,使得算法容易收敛于局部最优值.为此,为了 能够处理符号型数据,K-prototypes算法对K— means算法进行了扩展.与K.means算法相比,K- prototypes算法的主要不同点在于对象相似性的度 量方法,为了叙述方便,下面给出聚类分析的一些 基本概念‘15。1 71. 定义1 设JD为一组对象的集合,{A,,A:, …,A。}为D的属性集合,其中A。,A:,…,A。是 数值型属性,A川,.A,+2,…,A。是符号型属性,A, (1吲≤m)的值域记为Dom(Aj).数值型属性的值 域是一个连续且有序的实数区间,符号型属性的 值域是一个离散且有限的取值集合.若算i E D,则 戈;可以表示为一个m维向量{戈¨x乜,…,石拥},其 中菇Ⅱ∈Dom(A_,).若戤,菇『∈D,则戈i,戈f之间的距离 定义为 d(xf,石,)=d,(菇i,菇f)+y d。(髫i,髫,)= ∑(%一和)2+y∑8(x。一%) (I) 其中‰一唧)=0 i…fx.=x.f扩,;· 在式(1)中,将数值型属性和符号型属性分别 进行距离计算,d,(菇i,菇,)是数值型属性计算部分, d。(菇;,髫,)是符号型属性计算部分,y是协调2类距 离的参数. 定义2聚类目标甬数定义如下: 以:至竖号竺些业(2) 其中:K为给定的聚类数目;Z,是第P个数据对 象;Ci是第i个聚类的中心;I cj I是分配到第i个 聚类的数据对象数目. 定义3聚类中心更新公式 万方数据 陈庆枝,等:信息安全评估日志数据的一种混合聚类算法 79 c。=而1 v警P (3) 个常量‰来限制粒子的速度’改善搜索结果 K—prototypes聚类算法的执行步骤: Stepl从数据对象集合D中随机选择K个 对象作为K个初始的聚类中心. Step2对每个数据对象,按照式(1)计算其 与每个聚类中心的距离,按照最近邻法则将其分 配到距离最近的聚类中心. Step3对于数值型属性按照式(3)更新每个 聚类的聚类中心,对于符号型属性,统计在聚类中 出现频率最高的那个属性值作为该聚类中心新的 属性值. Step4按照公式(2)计算聚类的目标函数, 若目标函数值优于最优目标函数值,更新最优目 标函数值,并更新最优聚类中心.’ Step5重复步骤2和3直到聚类中心不再变 化或达到最大的迭代次数. Step6输出最优聚类中心. K·prototypes算法可以同时处理符号型和数值 型的混合数据,但是仍然存在容易陷入局部最优 值、算法聚类效果依赖于初始聚类中心选择等 问题. 2基本粒子群优化算法 PSO最初由Kennedy和Eberhart提出¨引,其 数学描述如下:假设在一个D维的目标搜索空间 中,由Ⅳ个粒子组成一个群体,其中每个粒子可表 示为一个D维向量菇i={菇¨舅也,…,髫珊},粒子i(i =l,2,…,Ⅳ)的速度定义为每次迭代中粒子移动 的距离,用%=h。,%,…,秽珊}表示.于是,粒子z (i=l,2,…,』、r)在第d(d=l,2,…,Ⅳ)维子空间中 的飞行速度%以及位置茗甜可以根据式(4)进行 调整: 口讨=埘×秽耐+Cl×rl(P讨一菇“)+c2 x/'2(P“一髫耐) (4) 菇讨=茗讨十秽讨 (5) 其中:加称为惯性权值;c。,c:是2个正常数,称为 加速因子;r。和r:是2个0—1的随机数;pi为粒 子历史最优位置;p。为全局最优位置.通常使用一 3 基于粒子群优化和K—prototypes方法的 混合聚类算法(PSO.KP) 利用粒子群优化算法进行聚类分析的关键在 于粒子的编码方式以及适应度函数的选择,粒子 编码通常根据聚类问题的实质以及粒子所处的搜 索空间来确定,适应度函数体现了聚类问题和优 化算法之间的内在联系. 3.1粒子编码方式 在粒子群优化算法中,一个粒子表示问题空 间中的一个解.聚类问题的目标是得到一组聚类 中心,使得聚类目标函数值最小,因此,一个粒子 代表一组的聚类中心集合.第i个粒子置的编码 方式为 Xi=(C订,…,Cd,…,C坼) (6) 其中:K为聚类的数目;C。表示第i个粒子的第_『 个聚类的聚类中心向量.设样本数据集的属性数 目为D,则C。为一个D维向量,粒子五的编码长 度为K×n 3.2适应度函数 适应度函数是用来评价粒子质量的函数.粒 子的适应度越高,粒子质量就越好.对于数据聚类 问题,其目标是使聚类目标函数的值最小,因此, 对于第i个粒子置,定义适应度函数为:。删:星堕型警幽 (7) 其中:K为给定的聚类数目;ZP是第P个数据对 象;C。是第f个粒子的第,个聚类的聚类中心向 量;J c。J表示分配到第i个聚类的样本数目. 3.3算法描述 基于粒子群优化和K-prototypes方法的}昆合 聚类算法(PSO.KP算法)的执行步骤: Stepl 载入测试样本数据,设置算法初始参 数(种群规模、迭代次数,算法参数等); Step2初始化种群,为每个粒子随机产生K 个聚类中心向量,作为粒子的初始位置;随机初始 化每个粒子的速度.根据公式(7)计算每个粒子的 万方数据 重庆工学院学报 适应值; Step3更新粒子的历史最优位置和全局最优 位置; Step4根据粒子的位置和速度更新公式更新 速度和位置; Step5对更新过的粒子采用K—prototypes方 法进行优化,并根据粒子对应的聚类中心重新计 算粒子的适应值; Step6若迭代次数达到最大迭代次数,算法 终止;否则转Step3. 4仿真实验与结果分析 4.1 实验数据与参数设置 本文中的实验数据来自KDD99的IDS数据 集120 J,该数据库与真实环境相似性很大,因此被 广泛用于对IDS Et志数据进行分析研究.数据库 中每条记录包含42个属性,最后一个属性由专家 标识该记录是正常的连接,还是属于某种类型的 攻击;其余41个属性里,有9个是字符型的属性, 32个是数值型的属性.由于41个测试属性中很多 属性是属于无用的属性,这些属性的存在会降低 数据聚类的效果,并且增加算法的处理时间.因而 在进行数据聚类分析之前,必须先去除这些无用 的属性.本文中采用文献[21]中的特征选择算法, 最终选择到14个属性,其中有4个符号型属性、 10个数值型属性. 由于完整的KDD数据库数据量庞大,本文中 的实验从KDD数据库中选择一部分数据用于算 法测试.为了使选择的测试数据与现实网络环境 的13志数据保持相对一致,从10%的训练数据库 (含有49 4021条样本数据)中一共选取55 285条 样本数据作为测试数据集,其中正常的连接数据 (类别为Normal)有40 000条;异常攻击数据有 15 285条:Dos(denial of service)攻击数据10 000 条,U2R(user to root)攻击数据52条,R2L(remote to local)攻击数据1 126条,Probe攻击数据4 107 条.测试数据集中的所有数据都是从10%的训练 数据库中根据各个类别的样本数目要求随机选择 生成的. 为了避免样本距离计算中由于各个属性最纲 不一致对实验结果产生的影响,所有数值型属性 的属性值都先进行标准化处理,处理方法: y—yE=≠‘_÷≯ (8)AM—Amin 其中:置和置’表示属性的初始值和标准化处理 后的值;x。;。和x。。分别表示该属性的最小值和最 大值. 算法的聚类效果一般以类的目标值、聚类内 紧密度(即聚类的类内距离)、聚类间的分离度(即 聚类的类间距离)3个指标作为评价标准,即:聚 类目标函数值越小,聚类效果越好;聚类的类内距 离越小,聚类效果越好;聚类的类间距离越大,聚 类效果越好. 为了便于进行实验结果的对比,PSO.KP的粒 子个数和GA—KP的染色体个数都设为20,其他相 关调整和控制参数也采用算法常用的设置方法, 具体为:PSO—KP算法中,惯性权值采用线性调整 加的策略¨9|,初始值埘,=0.9,埘:=0.2,加速因子 Cl=c2=2.0,最大速度限制k=0.5;GA-KP算 法中,交叉概率Pc=0.6,变异概率Pm=0.05. 4.2结果分析 为了说明算法的有效性,实验中K—prototypes 算法、GA—KP算法和PSO—KP算法各运行30次,每 次迭代次数为100次.表1是30次运行得到的算 法目标函数值、类内距离、类间距离的平均值、标 准方差、最小值和最大值. 万方数据 陈庆枝,等:信息安全评估日志数据的一种混合聚类算法 81 表l 各种算法聚类结果比较 从表l可以知道:对于聚类目标函数值K. prototypes算法得到的目标函数值的平均值、标准 方差是最差的,GA—KP算法得到的值次优,PSO— KP算法的值最优;对于聚类的类内距离(即聚类 内的紧密度),3种算法得到的类内距离值相差不 是很大.相对而言,K—prototypes算法的平均值和标 准方差都较大,类内聚合度较低;GA.KP算法和 PsO—KP算法的平均值和标准方差较小,类内聚合 度较高;对于聚类的类间距离(即聚类间的分离程 度),无论是类间距离的平均值、标准方差、最小 值、最大值。GA—KP算法的结果略优于K-prototypes 算法,而PSO.KP算法的结果又优于GA·KP算法. 因而,PSO.KP算法可以保证聚类之间低耦合.这 也进一步说明了K.prototypes算法存在容易陷入 局部最优值,遗传算法和粒子群优化算法在一定 程度上都能克服K—prototypes陷入局部最优值,但 是粒子群优化算法能够更为有效地避免陷入局部 最优值,具有较好的全局收敛性. 由此,与传统的K-prototypes算法相比,PSO— KP算法结合了PSO算法和K-prototypes算法的优 点,PSO算法良好的全局寻优能力保证了算法在 产生下一代种群时有较大的随机性,克服了 K-prototypes算法容易陷入局部最优值的不足;在 产生新一代个体时使用K-prototypes方法对粒子 进行优化处理,利用K.prototypes算法局部搜索能 力强、收敛速度快的特点,加快算法的搜索过程. 图l是3种算法各自运行30次过程中分别得 到的最优聚类目标函数值的收敛曲线.从图1中 可以看到:K-prototypes算法具有最快的收敛速度, 图l 各种算法最优聚类目标函数收敛曲线 口一口。一勺目,函蛊。量岳 万方数据 82 重庆工学院学报 但是收敛的目标函数值较大,即容易陷入局部最 优值;GA.KP算法的收敛速度较慢,但收敛的目标 函数值比K—prototypes算法小;PSO-KP算法的收 敛速度比K—prototypes算法稍微慢一些,但比GA- KP算法快,并且能够收敛到最优的适应值,而且 相对于GA—KP而言具有更好稳定性. 由于本文中选择的测试数据是带有类别标识 的数据,因此可以通过聚类结果表(confusion matrix)得到聚类结果的准确度.表2是3种算法 聚类结果的正确率.从表2中可以看出,GA-KP算 法的正确率比K—prototypes算法略有提高,但是 PSO.KP算法的正确率比其他2种算法都有较大 的提高,并且算法每次运行的正确率都落在 [82.94%,88.23%],正确率变化很小,这也再次 表明PSO—KP算法具有更好的聚类性能和更高的 稳定性. 表2聚类正确率 5结束语 本文中提出一种基于粒子群优化和K— prototypes方法的混合聚类算法,该算法结合了粒 子群优化算法和K—prototypes算法的优点,克服了 K—prototypes算法聚类效果依赖于初始聚类中心的 选择以及容易陷人局部最优值的不足,提高了算 法的聚类性能和稳定性.实验结果表明,该算法是 一种有效的聚类算法. 参考文献: [I】 [2] 田小林,焦李成,缑水平. 聚类的SAR图像分割[J]. 453—457. 缑水平,焦李成,田小林. 神经网络的图像识别[J]. 30(2):263—266. 基于PSO优化空间约束 电子学报,2008,36(3): 基于免疫克隆聚类协同 电子与信息学报,2008。 [3] 李伦波,马广富.基于PNN的退化交通标志图像的 识别算法研究[J].电子与信息学报,2008,30(7): 1703一1707. [4] 黄平牧,刘刚,郭军.一种新颖的基频包络聚类方法 [J].计算机研究与发展,2008,45(8):1362—1370. [5]KimD M,Kim K S,Park K H,et a1.A Music Recommendation System with a Dynamic K-mealllS Clustering Algorithm[c]//Sixth International Conference on Machine Learning and Applications (ICMLA 2007).Cincinnati,OH,USA:[s.n.】, 2007:399—403. [6] 孙吉责,刘杰,赵连字.聚类算法研究[J].软件学 报,2008,19(1):48—61. [7] Krishna K, Narasimha M M. Genetic K.means Algorithm[J].IEEE Transactions Oil Systems,Man, and Cybernetics—Part B:Cybernetics,1999,29(3): 433—439. [8] Malyszko D,Wierzchon S T.Standard and Genetic k. mealllS Clustering Techniques in Image Segmentation [c]//6“Intemational Conference on Computer Information Systems and Industrial Management Applications(CISIM 2007).Minneapolis,MN,USA: [S.n.],2007:299—304. [9] Vander Merwe D W,Engelbrecht A P.Data Clustering Using Particle Swarm Optimization[C]//Proceedings of IEEE Congress on Evolutionary Computation 2003(CEC 2003).Canbella Australia:[s.n.],2003:215—220. [10]周鲜成,申群太,王俊年.基于微粒群的K均值聚 类算法在图像分类中的应用[J].小型微型计算机 系统,2008,29(2):333—336. [11]Pei Z K,Hua X,Han J F.The Clustering Algorithm Based on Particle Swarm Optimization Algorithm[C]// 2008 Internationsd Conference on Intelligent Computation Technology and Automation(ICICTA 2008).Changsha:[s.n.],2008:148—151. [12]行小帅,潘进,焦李成.基于免疫规划的K一Ⅱ瑚惜聚类 算法[J].计算机学报,2003,26(5):605—610. [13]Meng Y,Liu X Y.Application of K-means Algorithm Based on Ant Clustering Algorithm in Macroscopic Planning of Highway Transportation Hub[c]//First IEEE International Symposium on Information Technologies and Apphcations in Education(ISITAE 2007).Kunming:[s.n.],2007:483—488. (下转第118页) 万方数据 1 I 8 重庆工学院学报 ■II■■●■——■■————■■●■■——■——■——■■■—■—■—■——■■■——■■■■●—■●——■———■——■—●———■——■—●———●—————■■■■—■●●●—■■■■■■■————■■■——■■■●——●●一 由表3可知,除个别数据外,BP网络模型的 输出值与期望值的偏差均小于5%,说明利用BP 神经网络进行室内热舒适度PMV值融合具有较 高的准确性和可行性. 4结束语 热舒适度PMV指标与其影响因素之间存在 着非常复杂的非线性关系,很难通过计算精确得 到.本文中采用具有并行输入、高容错性、自学习 能力强的BP神经网络方法对PMV指标的6个影 响因素进行智能化融合,综合考虑了这6个因素 与PMV指标的关系.仿真结果表明,该BP神经网 络模型具有良好的性能,能精确顶测PMV值.因 此,完全可以将其应用于室内环境的信息融合处 理,并且将结果应娟于室内宅调控制系统,使窄调 控制系统根据融合结果,自动对室内温度、湿度等 (上接第82页) [14】Huang z x.Clustering Large Data Sets with Mixed Numeric and Categorical Values[c]//First Pacific— Asia Conference on Knowledge Discovery and Data Mining.Singapore:[s.n。],1997:21—34. [15]Huang Z x.Extensions to the K-meang Algorithms for Clustering Large Data Sets with Categorical Values[J】. Data Mining and Knowledge Discovery.1998,2:283 —304. [1 6]Huang z X.A Fast Clustering Algorithm to Cluster Very Large Categorical Data Sets in Data Mining[c]∥ Proceedings of the SIGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery (SIGMOD 1997).Tucson:[s.n.],1997:146—151. [17]陈宁,陈安,周龙骧.数值型和分类型混合数据的 模糊K—Prototypes聚类算法[J].软件学报,2001, 12(8):1107一1119. [1 8]Kennedy J,Eberhart R C.Particle Swarm Optimization 空调参数进行调节,从而达到提供良好的室内环 境,降低能耗的目的. 参考文献: [I] [2] [3] [4] [5] [19] [20] [21] 吴金洪,金才富.影响空调列车车厢内热舒适性的因 素分析[J].制冷空调与电力机械。2006,27(5):7l 一72. 申欢迎,秦萍,董军.环境因素对PMV指标的影响分 析[J].制冷与空调,2003(4):29—39. 杨露箐。余华.多源信息融合理论与应用[M].北京: 北京邮电大学出版社.2005. 马丽娜.基于神经网络的建筑环境信息融合方法研 究[D].西安:西安建筑科技大学,2008. 董长虹.Matlab神经网络与应用[M].北京:国防工 业出版社,2005. (责任编辑陈松) [c]//Proceedings of IEEE International Conference on Neural Networks。Piscataway:[s.n.],1995:1942 —1948. Shi Y H.Eberhart R C.A MMiffed Particle Swarm Optimizer[C]//IEEE International Conference of Evolutionary Computation.Piscataway:[S.n.],1998: 69—73. 1999 KDD Cup competition[EB/OL].[1999—10— 28].In:http://kdd.ics.uci.edu/databases/ kddcup99/kddcup99.html 郭文忠,陈国龙,陈庆良,等.基于粒子群优化算法 和相关性分析的特征子集选择[J].计算机科学, 2008,35(2):144—146. (责任编辑刘舸) 万方数据
展开阅读全文
  皮皮文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:信息安全评估日志数据的一种混合聚类算法.pdf
链接地址:http://www.ppdoc.com/p-10914212.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

copyright@ 2008-2018 皮皮文库网站版权所有
经营许可证编号:京ICP备12026657号-3 

收起
展开