（计算数学专业论文）基于免疫聚类的异常检测算法研究.pdf

独创性声明 】7 21s7 ! ! l l i l 而i lf l l f l l i i fi l l li i ifl l 衄 y 17 4 016 7 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示谢意。 签名：卑企隰形年月夕日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名： 导师签名：燃导师签名：型场咝 日期：矽厉年月驴曰 摘要 摘要 基于人工免疫网络的数据聚类技术借鉴生物免疫系统的免疫识别、免疫记忆、 免疫调节等机理，能够对大规模的数据自学习分类。将该技术对网络数据做聚类 分析，定义正常和异常数据，为入侵检测提供了新的技术路线。基于人工免疫网 络的数据聚类技术已成为网络安全新的热门研究课题。 目前免疫聚类算法存在聚类复杂度高、对参数敏感、收敛速度慢、对大规模数 据流处理低效等问题。相应的应用于入侵检测存在智能化程度低，检测率不高， 误报率高等缺陷。 本文在深入分析研究免疫机理和数据聚类技术的基础上，将免疫机理及数据挖 掘技术中的关联规则结合提出新的聚类算法和检测方法。本文主要研究内容： 1 研究人工免疫机理及数据聚类技术，分析目前几种常用的聚类技术，总结 这些聚类技术的优缺点及适用范围。 2 提出新的聚类算法( s a a i n e t 算法) 。为解决网络数据多种类型属性描述及 量纲对聚类结果的影响问题，该算法中引入权重矢量及相关度的概念来度量数据 间的亲和度。为更好地体现聚类抗体网络的动态性及简化性，引入模拟退火算法 实现变异，通过概率准则来接受新解，实现数据最优化。通过实验仿真表明在小 规模数据聚类上该算法比a i n e t 聚类算法具有更好的聚类效果。 3 为解决s a a i n e t 在大规模数据上的低效性，引入关联规则，提出新的聚类 算法( a r 。a i n e t 算法) 。该算法第一阶段采取分而治之的思想对整个数据集聚类得 到若干子簇，第二阶段应用关联规则将各个子簇合并得到最终的抗体网络集。采 用大规模的k d d 数据集作仿真测试，用d b 准则对聚类结果评估，结果表明该算 法的运行时间比s a a i n e t 和a i n e t 算法显著减少。 4 通过异常因子标记正常与异常，建立异常检测流程，将上文提出的算法应 用于异常检测，实验仿真验证其有效性。 关键词：免疫聚类，人工免疫网络，异常检测，关联规则 a b s t r a c t t h ed a t ac l u s t e r i n gt e c h n o l o g yb a s e do nt h ea r t i f i c i a li m m u n en e t w o r ki sa s i m u l a t i o no ft h eb i o l o g i c a li m m u n es y s t e m ，w h i c hu s e st h et h e o r yo fi m m u n e r e c o g n i t i o n ，i m m u n em e m o r ya n di m m u n er e g u l a t i o n i ti s u s e dt o c l a s s i f yt h e 1 a r g e - s c a l ed a t as e l f - l e a r n i n g i tp r o v i d e san e ww a y f o ri n t r u s i o nd e t e c t i o nb yd e f i n i n g n o r m a la n da b n o r m a ld a t ao ft h en e t w o r k t h ed a t ac l u s t e r i n gt e c h n o l o g yb a s e do n i m m u n en e t w o r ki sb e c o m i n gan e wr e s e a r c hf o rt h es e c u r i t yo fn e t w o r k i nt h ep r e s e n t ，t h e r ea r em a n yp r o b l e m si nt h ed a t ac l u s t e r i n ga l g o r i t h m sb a s e do n t h ei m m u n ec l u s t e r i n g , s u c ha sh i g hd e g r e eo fc o m p l e x i t y , b es e n s i t i v et oi n p u t p a r a m e t e r , l o wr a t eo fc o n v e r g e n c e ，i n e f f i c i e n tf o rl a r g e - s c a l ed a t as t r e a mp r o c e s s i n g a n ds oo n a l s ot h e r ea r em a n yp r o b l e m so ft h ei n t r u s i o nd e t e c t i o ns y s t e m sb a s e do n t h e s ea l g o r i t h m s ，s u c ha sl o wl e v e lo fi n t e l l i g e n c el o wl e v e lo fd e t e c t i o nr a t e ，h i g hf a l s e a l a r mr a t ea n ds oo n id e s c r i b et h em e c h a n i s mo ft h ei m m u n es y s t e ma n dt h ed a t ac l u s t e r i n gt e c h n i q u e s i n - d e p t hi nt h i sp a p e r , p r o p o s ean e wc l u s t e r i n ga l g o r i t h ma n dd e t e c t i o nm e t h o d s t 1 i s p a p e r sm a i n w o r ka n dt h er e s e a r c hc a nb es u m m a r i z e da sf o u o w s ： 1 h 1t h i sp a p e r , s t u d yt h em e c h a n i s mo ft h ea r t i f i c i a li m m u n ea n dt h et e c h n i q u e so f d a t ac l u s t e r i n g ，a n a l y z es e v e r a lc o m m o n l yu s e dt e c h n i q u e so fd a t ac l u s t e r i n g ，s u mu p t h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h e s ec l u s t e r i n gt e c h n o l o g i e s 2 p r o p o s ean e wc l u s t e r i n ga l g o r i t h m ( s a - a i n e ta l g o r i t h m ) i nt h ea l g o r i t h m ，iu s e t h ew e i g h tv e c t o ra n dt h er e l e v a n c eo fac o n e e d tt om e a s u r et h ed e g r e eo fa f f i n i t y b e t w e e nt h e d a t a ；s o l v et h ep r o b l e m so fm a n yt y p e so fn e t w o r kd a t a a t t r i b u t e d e s c r i p t i o na n dt h ed i m e n s i o no ft h ei m p a c to fc l u s t e r i n gr e s u l t s i n0 r d e rt or e f l e c tt h e d y n a m i c so ft h en e t w o r kc l u s t e r i n ga n t i b o d i e s iu s es i m u l a t e da n n e a l i n ga l g o r i t h m v a r i a t i o nw h i c ha c c e p tan e ws o l u t i o nf o rd a t ao p t i m i z a t i o nt h r o u g hap r o b a b i l i t y c r i t e r i o n t h es i m u l a t i o ns h o w st h a ti th a sb e t t e rc l u s t e r i n gr e s u l t st h a nt h ea i n e t c l u s t e r i n ga l g o r i t h mi nt h es m a l l s c a l ed a t a 3 p r o p o s e an e wc l u s t e r i n ga l g o r i t h m ( a r a i n e ta l g o r i t h m ) b a s e do nt h e a s s o c i a t i o nr u l e st os o l v et h ei n e f f i c i e n c yo ft h es a a i n e ta l g o r i t h mi nt h el a r g e s c a l e d a t a t h ef i r s tp h a s e so ft h ea l g o r i t h mt a k i n gt h ei d e ao fd i v i d ea n dr u l eo nt h ee n t i r e d a t ac l u s t e r i n gg e t san u m b e ro fs u b c l u s t e r s i nt h es e c o n dp h a s eo ft h ea l g o r i t h mb a s e d o nt h ea s s o e i a t i o nr u l ec o m b i n e sv a r i o u ss u b c l u s t e ro fn e t w o r kt og e taf i n a ls e to f a n t i b o d i e s t e s ti nt h ek d dd a t as e t u s et l l ed bc r i t e r i at oe v a l u a t et h ec l u s t e r i n g r e s u l t s t h er e s u l t ss h o wt h a tr u n n i n gt i m eo ft h ea l g o r i t h mi sl e s st h a nt h es a a i n e t a n dt h ea i n e ta l g o r i t h m s 4 b u i l da na n o m a l yd e t e c t i o nm o d e l u s et h eo u t l i e rf a c t o rt om a r kt h en o r m a la n d a b n o r m a li n d i v i d u a l s t h e a l g o r i t h m i s a p p l i e d t ot h ea n o m a l yd e t e c t i o n t h e i i a b s t r a c t e x p e r i m e n t a lr e s u l t ss h o w i t se f f e c t i v e n e s s k e yw o r d s ：i m m u n ec l u s t e r i n g ，a r t i f i c i a li m m u n en e t w o r k ( a i n e t ) ，a n o m a l yd e t e c t i o n ， a s s o c i a t i o nr u l e s i i i 目录 目录 第一章绪论1 1 1 研究的背景及意义1 1 1 1 网络安全与入侵检测1 1 1 2 基于免疫的网络安全2 1 2 本文研究内容及创新点3 1 3 本文组织结构4 第二章生物免疫系统理论5 2 1 生物免疫系统概述5 2 2 免疫系统组成5 2 3 免疫机制7 2 3 1 免疫应答7 2 3 2 免疫记忆7 2 3 3 否定选择7 2 3 4 克隆选择8 2 4 免疫系统的基本特征9 2 5 本章小结1 0 第三章人工免疫及免疫模型1 1 3 1 人工免疫系统概述1 1 3 2 人工免疫的基本术语1 1 3 3 生物免疫系统与人工免疫系统的对照1 2 3 4 免疫模型1 3 3 4 1 独特型免疫网络理论1 4 3 4 2 资源受限人工免疫( r l a i s ) 网络模型1 5 3 4 3a i n e t 网络模型1 6 3 4 4 免疫网络的应用与发展前景1 7 3 5 本章小结1 8 第四章聚类分析基础1 9 i v 目录 4 1 概述19 4 2 相似度度量1 9 4 2 1 对象间的相似性度量1 9 4 2 2 簇之间相似度度量2 2 4 3 聚类算法性能评估2 2 4 4 经典聚类方法2 3 4 5 聚类分析中的难题2 5 4 6 本章小结2 5 第五章基于免疫的动态聚类分析2 6 5 1 基于免疫聚类的发展2 6 5 1 1 基于群体的免疫聚类2 6 5 1 2 基于网络的免疫聚类2 7 5 2 基于a i n e t 的聚类算法2 7 5 3 改进a i n e t 的聚类算法( s a a i n e t ) 3 0 5 4 试验与结果分析3 3 5 5 基于关联规则的免疫聚类算法( a n a i n e t ) 3 5 5 5 1 关联规则简介3 5 5 5 2 基于关联规则的免疫聚类算法3 6 5 5 3 试验仿真结果3 7 5 6 本章总结3 9 第六章免疫聚类在异常检测中的应用4 0 6 1 一种新的入侵检测模型4 0 6 2 基于免疫聚类的异常检测一4 1 6 2 1 异常簇的标记4 2 6 2 2 异常检测算法4 2 6 2 3 试验设计及结果分析4 3 6 3 本章总结4 4 第七章总结展望4 5 致谢4 6 参考文献4 7 读研期间的成果5 0 v 第一章绪论 1 1 研究的背景及意义 1 1 1 网络安全与入侵检测 第一章绪论帚一早三百。比 计算机及网络技术快速发展，电子商务、政务、虚拟社区等建立在网络上的 在线服务呈现快速增长的趋势，计算机网络已成为社会生活不可或缺的一部分。 网络给人们带来了很大便利的同时也带来了很多的安全隐患，网络信息安全成为 刻不容缓的课题，需要人们给予高度的重视。据0 8 年全国信息网络安全状况调 查分析报告的1 2 0 2 2 份有效调查问卷显示，我国网络信息安全事件发生比例今 年略有下降，网络信息安全事件发生比例为6 2 7 ，同比下降了3 ：病毒感染率 为8 5 5 ，下降了6 个百分点【l 】。说明我国网络安全状况稍有好转，人们越来越重视 网络信息安全，但整体情况仍不容乐观，新病毒、木马等攻击行为不断出现，通 过各种方式快速传播，盗取个人隐私引起一系列社会问题，窃取企业及政府等部 门机要信息谋取利益，造成经济损失不可估量。个人及社会应对发生网络安全事 件应给予更高的重视。 国家发展与信息技术密切相关，只有做好信息的安全保障工作，才能保护网 络用户的合法权益不受侵犯，才能维持经济秩序的稳定，才能保护国家安全不受 威胁。信息化程度越高，暴露的可能性越大，被攻击的几率就越大，面临风险就 越大，信息安全已成为制约社会发展的关键技术之一，对网络入侵攻击的检测与 防范、保障网络信息的安全已成为刻不容缓的研究课题。 入侵检测系统i d s ( i n t r u s i o nd e t e c t i o ns y s t e m ) 是继密码技术、防火墙、鉴别 与认证、访问控制、虚拟专用等网络保护措施后的新一代热门网络安全保障技术。 传统的技术大多是采用专家知识的保护系统，将用户行为与专家知识库做匹配来 检测行为的合法性，是一种被动式防御系统，需要人工定期更新系统，无法检测 未知入侵或已知攻击变种。入侵检测是一种主动的安全防护技术，对被监控系统 的日志记录或用户行为进行分类，按一定的准则划分出异常的类，对应采取措施 解决问题。 电子科技大学硕士学位论文 入侵检测是- - i q 年轻的学科，1 9 8 0 年a n d e r s o n 首先提出其基本思想，pp o r r a s 于1 9 9 7 年建立了入侵检测系统模型( e m e r l d 模型) 。二十多年的发展，学者在入 侵检测技术研究方向取得了一定成果，但网络攻击层出不穷、变化多端，仍需要 不断完善现有入侵检测技术和进行新的思路、技术的研究。目前i d s 研究的关键 技术包括性能评估、构建大规模、分布式网络的i d s 系统以及在新的智能技术领 域的应用。研究i d s 检测技术主要方法有专家系统技术，状态转换分析，神经网 络，统计分析，智能代理，生物免疫，数据挖掘，模糊技术，模式匹配技术等。 1 1 2 基于免疫的网络安全 入侵检测的前提是系统可监控记录，并且正常行为和异常行为有不同的特征。 这两点分别可以通过系统日志和特征提取来实现。对行为进行特征提取，行为数 据映射到某种特征模式空间，通过一定的策略使相同模式( 包括正常和异常) 的 数据聚合成一个类，正常和入侵行为对应的数据彼此分离开。若把正常行为对应 数据看作自我，入侵异常行为对应的数据看作非我，入侵检测的工作就是一个识 别自我与非我的过程，这与生物的免疫系统的免疫应答过程非常相似。免疫系统 的本质功能也就是识别自我与非我，正常的组织细胞属于自我，异常的组织属非 我。生物免疫系统具有记忆性，即能记住曾经感染过的病原体的特征，当第二次 感染同样的病原体时能快速的清除病原体，且还具有自适应性、自学习性、鲁棒 性等特性，这正是入侵检测系统需要具备的基本特性。 新墨西哥大学的s t e p h a n i ef o r r e s t 研究小组根据入侵检测和免疫系统的相似性 提出了计算机免疫学概念并进行长期的研究，为基于免疫的入侵检测技术研究做 了开创性工作，为后来学者提供了很好的技术路线和理论基础。与其他入侵检测 技术相比，基于生物免疫机理的技术能很好的满足基于网络的i d s 必须具备的三 个系统特征：分布性、自组织性和低消耗性。目前入侵检测系统研究分为误用检 测( m i s u s ed e t e c t i o n ) 和异常检测( a n o m a l yd e t e c t i o n ) 瞄j 。 误用检测系统是基于知识的系统，入侵行为借助已知的系统漏洞进行攻击，检 测系统将这些漏洞做一个模式库，然后将入侵模式和库中模式匹配，匹配成功就 判别为攻击行为，如常见的蠕虫攻击就是利用这种方式来检测。典型的误用检测 方法有模式匹配、状态转换法和专家系统方法。优点在于针对性强，反应迅速， 检测准确率高。缺陷是对未知的或已知入侵行为的变种无能为力，需要人为定期 不断的更新入侵模式库，移植性不好。 2 第一章绪论 异常检测是基于行为的，根据一定的评定准则来自学习、自组织式的将行为标 记为正常和异常，分辨系统或用户行为的合法性。这种方法相对与系统无关，移 植性好，不受知识的限制，能检测未知的攻击行为。 现有入侵检测系统大都基于已知攻击的特征( s i g n a t u r e b a s e d ) ，几乎没有基于 异常检测的入侵检测系统，检测效率低下，误报率高，无法识别未知攻击。而基 于免疫系统的方法综合了基于特征和基于异常的检测方法，既能检测偏离正常的 模式，也能从病原体中提取特定未知的攻击模式。免疫系统能够在一个分布式的、 资源受限的环境中抵御变化无穷的病原体，成为构造智能入侵检测系统的研究热 点之一。 国外比较有影响力的基于免疫机制的入侵检测模型研究小组主要有3 个： f o r r e s t 、h o f m e y r 小组、d a s g u p t a 小组、k i m 、b e n t l e y 小组。f o r r e s t 小组提出的 基于网络的入侵检测模型不仅考虑了抗体抗原间的作用还考虑了抗体间相互作用 更符合免疫系统的生物原理。d a s g u p t a 小组提出基于免疫的入侵检测系统多a g e n t 系统模型，具有分布性、流动性、合作性和适应性，利用网络级、系统级、用户 级和进程级的a g e n t ，协同实现入侵检测，但该模型实现的难度较大。k i m 小组， 提出的模型描述了否定选择、克隆选择和检测子基因库进化3 种免疫机制的应用。 基于免疫的入侵检测系统还处在不断发展中，还有很多亟待解决的难题。且现在 的研究大多是理论上研究，需要研制具体实用的产品来验证这些理论。 1 2 本文研究内容及创新点 本文以聚类算法研究为线，将免疫机理与聚类算法相结合提出新的聚类算法， 并将其应用于异常检测，作理论分析和仿真测试。主要研究内容如下： 1 研究基于免疫的聚类算法 分析目前免疫聚类算法的不足，将免疫机理与模拟退火算法相结合提出新的 基于免疫网络的聚类算法( s a a i n e t 算法) 。在算法中定义相关度的概念来度量抗 体与抗原之间的亲和度，这克服传统的基于距离的度量方式中量纲对整个聚类的 影响性。通过模拟退火实现免疫网络进化的动态过程，能更进一步的缩小网络集。 在人工数据集和m s 数据集上作模拟测试，验证了算法的有效性。 2 研究异常检测算法 将数据挖掘技术中的关联规则与免疫聚类算法相结合，提出新的聚类算法 电子科技大学硕士学位论文 ( a r a i n e t 算法) 。针对目前算法对大规模数据处理的低效缺陷，采取分而治之的 思想对数据集聚类，然后用关联规则对各个子簇作操作，计算簇间的支持度、置 信度及兴趣度，对达到阈值的簇进行合并，最后留下的簇构成整个抗体网络集。 算法中引入异常因子的定义来度量聚类结果簇的异常性，比传统单纯根据数据的 规模来判定异常的方法有很大提高，这更好的考虑了数据的全局分布情况。在大 规模的k d d 数据集上仿真，结果验证了算法的有效性。 3 研究基于免疫的异常检测 提出一种新的基于免疫的两阶段入侵检测方法，第一阶段采用基于专家系统 的误用检测，具有快速响应的能力。第二阶段采用异常检测，能更好的实现对未 知或已知异常变种的检测。通过试验仿真，并与同类算法作比较研究，验证了模 型的检测效率。 1 3 本文组织结构 第一章绪论介绍了研究课题的背景及意义，介绍了目前基于免疫的异常检测研究 现状及未来研究的难题。 第二章第三章是理论基础部分，介绍了免疫系统和人工免疫系统的机理及常见的 人工免疫模型，分析模型的可行性及缺陷。 第四章对聚类算法的基础知识做深入研究，分析经典聚类方法的优缺点，阐述聚 类算法的关键技术，总结比较聚类算法面临的挑战。 第五章在分析a i n e t 算法缺陷的基础上，引入相关度及模拟退火等理论提出新的 基于免疫的聚类算法( s a a i n e t 算法) ，分析算法时间复杂度，试验仿真验证算法的 有效性。 第六章将前文算法用于异常检测中去，提出新的基于免疫的异常检测模型，试验 仿真验证算法的检测效率。 第七章是对本文所做工作的总结及未来研究的展 4 第二章生物免疫系统理论 第二章生物免疫系统理论 2 1 生物免疫系统概述 免疫学( i m m u n o l o g y ) 主要研究生物体免疫系统组成结构和功能【3 】。它与 神经生物学、分子生物学并列为生命科学的三大支柱学科。在现代免疫学研 究中，生物免疫系统的功能是抗体对抗原刺激的免疫应答过程，在机体中体 现为免疫系统对自己( s e l f ) 识别和非己( n o n s e l f ) 的识别处理功能。主要 功能体现在：免疫防御，即抵制对外来异物( 抗原) 的入侵；免疫自稳定， 即祛除低劣及损伤细胞，保持体内细胞健壮性并不断更新，达到自身机体细 胞的平衡；免疫监视，识别祛除畸变和基因变异细胞【4 】。 2 2 免疫系统组成 免疫分子、细胞和器官组成整个复杂的免疫系统( i m m u n es y s t e m ) 。其组织 结构如图2 1 所示。免疫系统是生物受病原体长期刺激，与致病因子做斗争进化， 在机体发育中不断完善【4 】。 在免疫学的研究中，常用的以下几个基本概念： ( 1 ) 抗体( a n t i b o d y ) ：抗体是相对抗原来定义的，是一种能识别并清除抗原的 免疫蛋白质分子。抗体具有特异性，即能根据不同的特性与相应的抗原结合，同 时抗体具有抗原性，即抗体与抗体之间相互刺激作用也会引发免疫效应。 ( 2 ) 抗原( a n t i g e n ) ：抗原是外来刺激源，本身并不是免疫系统的有机组成部 分。外来抗原是非自身的，但在免疫耐受阶段，机体自身的某些部分也会转化成 抗原。 ( 3 ) t 细胞：t 淋巴细胞是免疫系统的主要组成部分，有抑制性、调节性和杀伤 性t 细胞。具有识别病原体、激活b 细胞、调节细胞浓度等功能。 ( 4 ) b 细胞：受抗原刺激后b 细胞能产生抗体浆细胞，是体液免疫调节的主要 免疫细胞，t 细胞和b 细胞机体产生抗体的主要结构。 5 电子科技大学硕士学位论文 ( 5 ) 自组织复合体( m h c ) ：是一种能引发抗体免疫应答和免疫调节的抗原， 可作为自身或同种反应的抗原，主要功能是搜集细胞内需要处理的多肤，并运送 到细胞表面。 ( 6 ) 造血肝细胞( h s c ) ：造血干细胞是存在于造血组织的一种原始造血细胞， 不是组织固定细胞，可存在于造血组织和血液中。淋巴细胞中的b 细胞等由造血 干细胞分化发育而来。 ( 7 ) 淋巴细胞：淋巴细胞是具有特异免疫识别功能的细胞系，由形态相似、功 能各异的细胞群所组成。分为b 细胞和t 细胞两个亚群，每个亚群又分为不同的 亚类。 干细胞系 淋巴细胞系 单核吞噬细胞系 其他免疫细胞 模型分子：t 细胞抗原受体 分泌型分子：抗体，补体，细胞因子 中枢免疫器官：骨髓，胸腺 外周免疫器官： 脾，淋巴结，黏膜等 图2 1 生物免疫系统结构图吲 6 厂，、l厂，、l r a d 的克隆； 计算克隆内部的抗体的亲和力s 睹； 消除所有相似度过高的记忆克隆体s t k a ，； 把剩下的记忆克隆体加入到网络中； e n d ； 计算4 中所有的记忆抗体的亲和力； 消除网络中过于相似的抗体s 披 a ，； 选取一定的新的随机抗体建立新的网络； e n d ； e n d 。 算法结果是一个记忆抗体细胞集，用来识别和描述数据，实现数据的压缩过程， 细胞差异越小越好。通过抑制阈值来控制细胞克隆、变异水平及迭代循环代数。 电子科技大学硕士学位论文 算法很好的模拟免疫系统的自适应性，能快速实现二次应答，在低维的基于距离 的数据集上有很好的聚类效率，但是从算法流程看算法存在很多的局限性： 1 该学习算法是通过单一的距离公式来度量网络数据中抗体与抗原、抗体与抗体 间的亲和度，而随现在新领域的应用，数据集的属性不能靠单一的距离类衡量， 需要更好的度量准则来实现。 2 算法参数过多，需要人为定义的参数有克隆规模、变异概率、自然死亡阈值、 抑制阈值等参数，结果网络对参数选择比较敏感。 3 结果不是原数据的聚类，是经过克隆变异后得到的免疫细胞集来实现的间接聚 类方法，只是对原数据的一个影像表示。不能完整描述出原数据集的聚类效果。 4 对二三维的数据具有很好的聚类效果，但是对高维数据、边界模糊数据的聚类 功效不是很明显。 5 算法的时间复杂度是d 妒。j 级的，抗原刺激抗体的搜索空间比过大，导致时间复 杂度也比较高，不是增量级的聚类方法。 5 3 改进a i n e t 的聚类算法( s a a i n e t ) = l ，2 ，z ，1 ，；0 。定义v = ( e ，呓，以) 为群体x 中第i 个成员的权重矢量， 咿，= 一 2 ， 其中1 p o o ，1 o ，y o ，土+ 三= 1 ，记彰= 形一，= 巧，一矿；，当a , - , 6 ；- 0 时结论显然成立。 当不全为0 时有 3 2 第五章基于免疫的动态聚类分析 掣t = l ：幽i ：窆 一 睁i ，俐9 r 打 f = l 阿 p 倍：一 例 阿主1 0 ：1 _ 将耐，带入定义式即得定理等式成立。 5 4 试验与结果分析 ：土+ ! ：1 一 = 一+ 一2 pq 为验证算法的有效性，首先在二维的数据上做实验仿真，5 0 次随机生成1 5 0 个数据点，下图是其中一次的数据分布情况，以整个数据聚类的簇数目不再变化 为终止条件，将本算法迭代次数与a i n e t 算法迭代次数做比较，其他多次的实验效 率与此次相似。算法中参数有相关度阈值，- ，迭代次数k ，由于数据计算相关度时 已抽象为多维的矢量，这里采用前章介绍的2 范数值来度量抗体间亲和度，其阈 值为d ，参数分别初始化为( o 5 ，k ，0 8 ) ，在m a t l a b 7 0 的环境下编程实现， 聚类结果通过上章介绍的d b 指标来衡量，。= 0 4 5 。用a i n e t 算法在这个规模 数据上聚类要2 0 次才能达到稳定，而本算法平均在1 6 次左右就达到稳定的聚类 簇。 电子科技大学硕士学位论文 图5 1 初始二维数据集 图5 - 2 迭代次数与聚类簇数目变化 在数据集i r i s 数据集上做算法测试，i r i s 数据集是u c i 机器学习中常用数据。 该数据集由三种花的数据样本组成，样本规模是1 5 0 ，每一种植物都有其属性的4 个特征，其中第二类和第三类数据相互覆盖。对4 个属性作预处理，为直观的描 述，将样本数据和聚类中心做映射处理，将第1 属性和第2 属性的和作为x 轴，第 3 属性作y 轴，第4 属性作z 轴。试验参数r = 0 5 ，d = 0 8 ，v d b = o 4 5 在m a t l a b 7 0 的编程环境下实现算法，最后得到图示三维立体图，其中三个圆的圆心分别代表 了聚类簇的中心坐标。多次试验表明通过不仅能准确的将数据聚类成3 类，且聚 类结果正确率达到10 0 06 图5 3i r i s 数据集的聚类结果 在前两种数据集上s a a i n e t 都能很好的达到聚类效果，且准确度和时间复杂 3 4 5 2 5 ， s 0 8 2 ， n 第五章基于免疫的动态聚类分析 度相比a i n e t 都有所提升，但在大规模的数据处理时结果显示是低效的，现在二维 数据上随机的增加大量数据，分别通过两种算法聚类来实现聚类，图示5 - 4 反应 a s a i n e t 和a i n e t 算法最后收敛的时间对照。其中参数仍采用i r i s 数据集的参数 r = o 5 ，d = 0 8 ，v o b 2 u 4 5 ，试验发现a s a i n e t 比a i n e t 算法的时间有所改进， 但是仍然没有从实质上改变其时间高消耗性，基于对大规模的数据聚类时s a a i n e t 和a i n e t 都有时间花费比较高的问题，结合数据挖掘技术中的有效方法关联规则在 下面的章节提出新的算法一基于关联规则的算法( a s a i n e t ) 。 e 厘 套 餐 娶 燃 蜮 图5 4 数据规模与算法收敛时间 5 5 基于关联规则的免疫聚类算法( a r a i n e t ) 5 5 1 关联规则简介 关联规则是数据挖掘技术中比较有效的算法，能发觉数据集中有价值的数据间 相互的关系。其主要设计以下一些定义和理论： 设i = p l ，i ：，1 坍j 使一些项的集合，任务的相关数据d 有 d = d l ，d 2 ，乜) ，其中b = 亿。，：，k ) ，毛j ，么，b 是，中的两个或多个项 组成的两个子项集，na c 、b 关联规则就是形如ajb 的一个蕴含式【3 8 】。 定义1 支持度( s u p p o r t ( ajb ) ) 3 8 】支持度是形如s u p p o r t ( aj 艿) = e ( a u b ) 表达 式表现的一个百分率等式。 定义2 置信度( c d 妒比以c e 0jb ”3 8 】置信度是形如c o n f i d e n c e ( ajb ) = e ( a i b ) 的 3 5 电子科技大学硕士学位论文 百分比表达式。 定义3 兴趣度胞凇f 0jb ”3 即兴趣度是通过下式来计算： 砌胞m r 0 j b ) 2 瓦荔荔s u p 瓦p 万o r i t ( a 瓦u 瓦b 万) 两 ( 5 - 7 ) 、 7 勋卯d 形i 么) 砌即d 以( b ) 形象的描述如在一个班学生选英语和音乐课程的人数目如下表所示： 表5 - 1 班级选课情况 选音乐 不选音乐 选英语3 0l o4 0 不选英语1 3 03 01 6 0 1 6 04 02 0 0 关联规则 选英语 j 选音乐 的支持度和置信度分别兰1 0 0 = 1 5 和 。 2 0 0 = 3 0 1 0 0 ：7 5 ，兴趣度为j 竺l ：堕。此处规则就是选英语的人也选 4 0 4 0 2 0 0 x1 6 0 2 0 0 1 6 音乐，单纯从支持度和置信度看都比较高，结论是成立的。但实际上从表中分析 是不成立的，就好比计算机运算中大数吃小数的规则一样，这里第一个高比例把 第二个低比例综合了，而忽略了规则类别属性项的支持度，对整个评估产生误导， 因此引入兴趣度来评判，兴趣度小于1 说明其中的s u p p o r t 是同时包含彳和召的百 分比，是该规则重要性的衡量指标，c o n f i d e n c e 是包含彳的同时也包含刀的百分比， 是衡量规则准确性的指标。i n t e r e s t 是衡量关联的两则间相互独立性的偏度，其值 越接近1 说明两者越独立，越小于1 说明两者相互抑制，越大于1 说明规则越好。 5 5 2 基于关联规则的免疫聚类算法 基于上