（计算机软件与理论专业论文）人工免疫系统研究及其在数据聚类中的应用.pdf

人工免疫系统研究及其在数据聚类中的应用 摘要 生物免疫系统是一种高度并行的自适应信息学习系统，它能自适应地识别和 排除侵入机体的抗原性异物，并且具有学习、记忆和自适应调节能力，能够维护 机体内环境的稳定。近年来，人们逐渐意识到生物免疫机制对开发新的计算智能 的启示意义，人工免疫系统( a r t i f i e i a li m m u n es y s t e m ，a i s ) 即是受生物免疫 系统启示而设计的新型算法和模型的统称，己经用于机器学习、异常和故障诊断、 机器人行为仿真、机器人控制、网络入侵检测等领域，表现出较卓越的性能和效 率，它已经成为计算智能大家庭的卓有成效的新成员。 但是由于人工免疫系统只是近些年发展起来的新的研究领域，虽然关于它的 研究己被越来越多的人所重视，并逐渐成为关于新的进化计算和模式识别方法研 究的一个热点，但是，整个研究工作仍然显得比较零乱，缺乏系统性，有些方法 名为人工免疫方法，实质是对原有方法的改造，失去了应用免疫系统的意义；另 外，对于人工免疫系统的模型和应用缺乏深入的探讨，许多模型和方法并未真正 体现出人工免疫系统的应用特点。 并且近年来在人工免疫系统应用研究中，关于人工免疫系统应用于数据聚类 方面的研究逐渐多起来，但是目前的人工免疫系统应用于数据聚类的过程中存 在有许多不足，例如：聚类方法中的很多参数需要人们根据经验判断手工输入， 而不能根据聚类过程的进行自适应地变化；参数的设置不合理而造成参数对于网 络的变化过于敏感；对网络中的参数分析不充分等等。 本文正是基于这样的认识，希望在免疫系统模型构造，算法实现以及应用于 数据聚类方法的参数设置问题作深入的探讨。 首先有针对性的介绍了生物免疫系统的一些基本概念、系统组成、功能原理 等；概述了人工免疫系统的一些主要原理及应用，在此基础上，提出了人工免疫 系统的一般模型框架。然后，对现有的典型的人工免疫系统应用于数据聚类的 算法进行详细分析，并在现有算法的基础上，针对其不足，提出了改进算法，通 过仿真实验进行了验证。总的来说，本文的主要研究集中于： 1 在认真分析和总结现有人工免疫系统的各种形式的基础上，提出了人工 免疫系统的一般模型框架及其应用方向； 2 以人工免疫系统的一般模型为指导，对现有的聚类分析方法进行研究， 人工免疫系统研究及其在数据聚类中的应用 针对现有的人工免疫系统在解决聚类问题时的缺陷，提出了一种新型的自适应聚 类人工免疫算法，在该算法中网络抗体间的抑制闽值、抗体的克隆数目、抗体的 选择和再选择数目、抗体的变异的大小都随网络进化而自适应变化，使最终网络 结构更加符合原始数据的内在结构，同时，对算法的参数进行了细致深入的分析 和优化，减弱了算法对问题的依赖性并且重要参数可随运算过程自适应确定，减 轻了用户需自行预定重要参数的负担，最后进行了仿真实验进行验证。 关键词：人工免疫系统数据挖掘聚类分析免疫算法 i l 人工免疫系统研究及其在数据聚类中的应用 a b s t r a c t b i o l o g i c a ll l n l n u n es y s t e mi sah i g h l yp a r a l l e la d a p t i v ei n f o r m a t i o nl e a r n i n g s y s t e m ，w h i c hc a ri d e n t i f ya n dr e m o v et h ea n t i g e n i ce y c w i n k e r si n v a d i n gt h eb o d y t h i ss y s t e mc a nl e a r n ，r e m e m b e ra n da d j u s ta d a p t i v e l yt ok e e pt h es t a b i l i z a t i o ni n s i d e t h eb o d y d u r i n gr e c e n ty e a r s , p e o p l eb e g i nt or e a l i z et h er e v e l a t o r ys i g n i f i c a n c eo f t h eb i o l o g i c a li m m u n em e c h a n i s mt oi n t e l l i g e n ta l g o r i t h m a r t i f i c i a li m m u n es y s t e m ( a i s ) i st m sk i n do ff l e wa l g o r i t h mw h i c hi si n s p i r e db yt h eb i o l o g i c a li m m u n e s y s t e m t h i sk i n do fa l g o r i t h mh a sb e e nu s e di nm a n yf i e l d s ，s u c ha sm a c h i n e r ys t u d y , u n c o n v e n t i o n a l i t ya n dm a l f u n c t i o nd i a g n o s i s ，s i m u l a t i o no ft h eb e h a v i o ro fr o b o t s ， c o n t r o lo fr o b o t s ，i n b r e a kd e t e c t i o no fn e t w o r k sa n de t c i th a sb e e nan e we f f e c t i v e m e m b e ro ft h ef a m i l yo fi n t e l l i g e n ta l g o r i t h m s h o w e v e r , a r t i f i c i a li m m u n es y s t e m ( a i s ) i san c wr e s e a r c ha r e a , t h er e s u l t sa r c i nd i s o r d e ra n ds h o r to fs y s t e m a t i z a t i o n e s p e c i a l l y , s o m es o - c a l l e da i se s s e n t i a l l ya r e m o d i f i e df o r m so ft r a d i t i o n a lm e t h o d s ，n o tr e a l l ys y s t e m sb a s e di m m u n es y s t e m f u r t h e r m o r e ，b o t hm o d e l i n ga n da p p l i c a t i o no fa i sa r en o ts ot h o r o u g ha n dp e r f e c t t h a tt h ei m p o r t a n tc h a r a c t e r i s t i c so fn a t u r a li m m u n es y s t e ma r en o tf u l l yr e a l i z e da n d u t i l i z e d n o wi nt h ea i sa p p l i c a t i o nr e s e a r c h e s ，t h er e s e a r c ha b o u ta i sa p p l y i n gt od a t a c l u s t e r i n gi sm o r ea n dm o r e b u ts o m eq u e s t i o n sh a v ep r o d u c e dd u r i n ga i sa p p l y i n g t od a t ac l u s t e r i n g f o re x a m p l e ，s o m ep a r a m e t e r sm u s tb ei n p u tb yo u r s e l f p a r a m e t e r s a r es e n s i t i v ef o rn e t w o r kc h a n g i n g p a r a m e t e r si nn e t w o r ka r en o te n o u g l lt oa n a l y z e i nt h i sp a p e f ，s o m eb a s i cc o n c e p t s ，f r a m e w o r k , f u n c t i o n sa n dp r i n c i p l e so ft h e b i o l o g i c a li m m u n es y s t e ma r ei n t r o d u c e & t h e nt h er e s e a r c hw o r k sa n a l y z es o m e m a i nm e t h o d s b a s e do nf o r m e rw o r k s ，p u tf o r w a r dac o m m o nf r a m eo fa i s l a s t e x i t e dm e t h o d sa r ea n a l y z e da n db a s e do nt h e m ，p u tf o r w a r dan e wa l g o r i t h m t h e a l g o r i t h mi sv a l i d a t e db ys i m u l a t i o ns t u d y i naw o r d ，t h em a i n l yr e s u l to fo u rw o r k s a r e ： 1 p u tf o r w a r dac o m m o nf r a m e0 f a i s 珊 人工免疫系统研究及其在数据聚类中的应用 2 t h e na n a l y z et h ee x i s t i n ga r t i f i c i a li m m u n ea l g o r i t h mf o rd a t ac l u s t e r i n g a c c o r d h gt ot h ec o m m o nf r a m eo fa i s p r o p o s ean o v e la d a p t i v ea r t i f i c i a lh h n u n e a l g o r i t h mf o rd a t ac l u s t e r i n g a n a l y z ea n do p t i m i z et h ep a r a m e t e r sc a r e f u l l ya n d d e e p l y t h e r e f o r ed e c r e a s eo fd e p e n d e n c eo ft h ea l g o r i t h mo nt h ep r o b l e m sa n d a l l e v i a t et h ec u s t o m e r sb u r d e nb e t 强u s cs o m ei m p o r t a n tp a r a m e t e r sc a nb ea d a p t i v e l y o b t a i n e di nt h ec o u r s eo ft h eo p e r a t i o n l a s tt h ea l g o r i t h mi sv a l i d a t e db ys i m u l a t i o n s t u d y k e yw o r d s ：a r t i f i c i a li m m u n es y s t e m ；d a t am i n i n g ；c l u s t e r i n ga n a l y s i s ； i m m u n ea l g o r i t h m ； i v 华南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文 的研究做出重要贡献的个人和集体，均己在文中以明确的方式标明。 本人完全意识到本声明的法律结果由本人承担。 论文作者签名： e l 期：7 。t 刁年 学位论文使用授权声明 幺聩鹤 f 月ze t 本人完全了解华南师范大学有关收集、保留和使用学位论文的规 定，即：研究生在校攻读学位期间论文工作的知识产权单位属华南师 范大学。学校有权保留并向国家主管部门或其指定机构送交论文的电 子版和纸质版，允许学位论文被检索、查阅和借阅。学校可以公布学 位论文的全部或部分内容，可以允许采用影印、缩印、数字化或其他 复制手段保存、汇编学位论文。( 保密的论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密范围，在后解密适用 本授权书。非保密论文注释：本学位论文不属于保密范围，适用本授权 书。 论文作者签名： e t 期： 。0 年月弓日 导师签名：葛! 工 日期：z 中占月多日 人工免疫系统研究及其在数据聚类中的应用 1 1 引言 第一章绪论 数据挖掘和数据仓库作为决策支持新技术在近十年来得到了迅速的发展。数 据挖掘的市场份额正日益扩大，越来越多的大中型企业开始利用数据挖掘来分析 公司的数据，以辅助决策，数据挖掘正在逐渐成为他们在市场竞争中立于不败之 地的法宝。 数据挖掘本身是一个发展历史较为悠久的领域，并且也形成了一些比较有 效的数据分析技术和工具，例如模式识别、机器学习等。但是随着社会和科技的 发展，越来越产生大量的、复杂的、多样的数据，尤其是i n t e r n e t 的流行，出现 了海量的，异构的半结构化的数据等等，因此人们在不断的探索新的、更加高效 的数据分析方法。随着计算机技术和其它各个科研领域的发展，学科之间的交叉 作用越来越大，许多新技术、新方法不断涌现。于是，人们也将相应的成果应用 于数据分析领域，例如人工智能、模糊系统、遗传算法、神经网络等技术在数据 分析技术中的应用以及数据挖掘概念的提出和研究，使得数据分析领域的研究取 得了重大进展。人工免疫系统就是在这样的形式下出现并且成为当前研究热点 的。 1 2 人工免疫系统 1 2 1 概述 生物信息系统分为脑神经系统( 神经网络) 、遗传系统、免疫系统和内分泌系 统四种类型。脑神经系统和遗传系统已经分别提出了工程模型，并在很多领域得 到成功的应用，后两种免疫系统和内分泌系统则还没有建立完整的学科理论。免 疫系统的复杂功能堪与大脑相比较，医学上的研究还在发展中，所以人工免疫的 研究也只是初步发展。但由于免疫系统具有许多有用的性能，得到了越来越多研 究者的关注和研究。 自然免疫系统是复杂的自适应系统，具有如下特点： ( 1 ) 己与非已：免疫系统的反向选择原理表明，免疫系统能够识别体内分子 人工免疫系统研究及其在数据聚类中的应用 与外来分子 ( 2 ) 学习与优化：免疫网络和克隆选择理论解释了免疫应答过程的机理，表 明抗体的产生是免疫系统的学习过程。 ( 3 ) 联想记忆：免疫系统消灭抗原后，产生记忆细胞，当与该细胞相似的抗 原再次入侵肌体时，免疫系统能够产生更快速，更强烈的二次应答，免疫记忆是 一种联想记忆。 ( 4 ) 自适应网络：免疫网络学说表明，免疫系统中的b 细胞通过识别与被识 别组成一个网络，对抗原的识别是网络中b 细胞相互作用的结果，免疫网络与神 经网络一样。是一个能够学习与记忆的自适应网络。 ( 5 ) 分布系统：免疫网络的淋巴细胞分布于全身，根据周围的环境自适应地 确定自身的行为，是一个没有中心的控制的并行的分布自治系统。 所谓人工免疫系统就是研究借鉴、利用生物免疫系统( 主要是人类的免疫系 统) 各种原理和机制而发展的各类信息处理技术、计算技术及其在工程和科学中 应用而产生的各种智能系统的统称。人工免疫网络具有与神经网络类似的自适应 性和学习能力，但它是建立在多个进程动态合作的基础上的；免疫算法具有与遗 传算法类似的进化机制，但是它能实现惊奇控制群体多样性和特异性所以人工 免疫系统具有与人工神经网络，进化理论不同的性质和功能，是一门潜在的新兴 科学技术。基于免疫学原理的新型技术不断发展，目的不仅是为了更好理解免疫 系统本身，更重要的在于解决工程问题。事实证明，人工免疫系统的发展不仅不 是多余的，而且极大的促进着智能系统，计算机科学，计算智能等多个领域的发 展，并正在成为一个应用日益广泛的新领域。 由于免疫系统的复杂性及其与医学免疫性的密切关系，1 9 9 8 年以煎，免疫 系统并没有引起相关人员的注意自1 9 9 8 年w c c i 第一次在美国召开人工免疫系 统专题会议后，在过去的几年中，各类研究人员对免疫系统的研究兴趣不断增加。 计算机科学家，工程师，数学家，哲学家，其他研究人员，从各个不同学科和角 度展开研究。其研究成果涉及到控制，数据处理，优化学习和故障诊断等领域， 已经成为继神经网络，模糊逻辑和进化计算后人工智能的又一研究热点“1 。 1 2 2 人工免疫研究概况 人工免疫系统包括算法，数学模型，混合智能系统等，大体可分为两类：一 2 人工免疫系统研究及其在数据聚类中的应用 类是从生物学角度模拟研究人工免疫系统。例如：形态空间模型嘲伽，主要思想是 抗体和抗原之问相互作用的程度是通过距离测量的方法来实现，它虽然是为了研 究免疫系统而建立的，但也正是许多目前出现的人工免疫系统技术的基础；j a m e y 提出的人工免疫网络理论，阐述了免疫系统具有大量独特型及抗体独特型的抗 体，由此形成了细胞问相互制约关系，而基于免疫系统中b 细胞和t 细胞之间的 相互反应可被借签用于建立人工免疫网络模型。例如：多值免疫网络，p d p 网 络嘲，a i n e t 咖，动态识别免疫网络模型“1 等等 另一类是从研究免疫系统某些机制出发，从而加深对免疫系统的理解，对建 立某些工程问题的人工免疫系统很有启发总之。人工免疫系统已经应用于不 同的工程领域。目前关于人工免疫系统的主要应用成果集中在异常和故障诊断、 计算机网络安全和病毒检测、机器人、机器学习图像处理、自动控制等领域。 1 2 3 人工免疫研究应用方向 a i s 正引起人们的极大重视，基于免疫系统机理的模型在科学和工程上将会 取得越来越多的应用。目前a i s 的应用主要体现在以下几个方面： ( 1 ) 计算机安全 计算机安全是免疫系统一个重要的应用领域。基于免疫的计算机系统比当前 操作系统支持的系统更有辨别和保护能力，其安全性检测依赖于所使用计算机设 备的权限，维护数据文件的完整性及阻止计算机病毒的传播“” ( 2 ) 智能优化 作为一种智能优化搜索策略， i s 在函数优化、组合优化、调度问题等方面 得到应用并取得了很好的效果。基于免疫原理实现的免疫算法在组合优化求解中 显示了强大的能力，多数情况下，免疫算法取得了比现有启发式算法更好的求解 结果，尤其在求解的效率方面，显示出a i s 在智能优化领域具有广阔的应用前景 f 圳 ( 3 ) 数据挖掘 数据挖掘是从巨量数据中获取有效的、新颖的，潜在有用的、最终可理解模 式的非平凡过程。采用a i s 模型的数据挖掘任务目前主要集中在数据聚类分析、 数据浓缩、归类任务等方面“”。 ( 4 ) 故障诊断 3 人工免疫系统研究及其在数据聚类中的应用 在一些大规模和复杂系统中，有效的故障诊断非常重要，若某一设备出现了 故障，会波及整个系统，从而引起严重后果i s h i d a 研究了一种基于相关识别 特性的免疫网络模型用于故障诊断的方法：i s h i g u r o 将免疫网络模型用于在线设 备系统故障诊断：t a n g 将人工免疫网络模型用于交流驱动和u p s 的控制和诊断。 故障诊断是继信息安全之后，另一个从免疫系统直接映射而来的a i s 应用领域 n 耵 除了上述四个方而的应用，a i s 在模式识别、图像处理、机器人控制等方而 都有广泛的应用。由于a i s 具有独特的分布式、自适应、自组织系统功能和并行、 鲁棒的信息处理能力，因此是个重要且非常有意义的研究方向。它一方面提供人 们智能地解决许多实际问题的有效途径，为从生物免疫系统新的研究成果，概括 更为完善的免疫计算智能模型开辟途径；另一方面开发基于生物免疫系统的计算 机模型有助于免疫系统操作的研究，用计算机程序明晰地模拟免疫系统等，可促 进人们在计算机上模拟人体免疫系统，在加快新药研制等方而具有重要应用价 值。总之，a i s 的研究将在各个领域发挥重大的作用，从而带给人类社会更大的 进步。 1 3 数据聚类的概况 1 3 1 聚类分析的定义 聚类分析( c l u s t e r i n ga n a l y s i s ) 主要是根据实体的特征对其进行聚类或分 类，按一定的距离或相似测度在大型多维空间数据集中标识出聚类或稠密分稚的 区域。将数据分成一系列相互区分的组，以期从中发现数据集的整个空间分布规 律和典型模式。聚类分析是统计学的一个分支，与规则归类不同的是，聚类算法无 需背景知识，能直接从空间数据库中发现有意义的空间聚类结构 根据被分类对象的维数，可将聚类问题分成三类：一维聚类、二维聚类、多 维聚类。依据模式类的结构特点可将模式类分为；分离结构、覆盖结构、层次结 构、双极结构。 一般来说，在完成聚类分析之后，应给出对各个模式类的描述，对模式类的 描述方式有： 1 选取模式类的质量中心或最接近质量中心处的样品作为对模式类的描 述： 4 人工免疫系统研究及其在数据聚类中的应用 2 选取模式类中n 个最特殊的耳标作为对该模式类的描述； 3 确定模式类之间的对称轴或转动轴作为对模式类的描述； 4 用各模式类的正态分布函数作为对模式类的描述； 5 采用分类树的形式对模式类进行描述； 6 采用逻辑合取式对模式类进行描述。 1 3 2 聚类算法概况 数据挖掘从狭义上讲就是信息处理问题，很多都属于模式识别所研究的范 畴。模式的分类和识别可以由分类器来实现。为了设计分类器必须首先对分类器 进行训练，即分类器首先要进行学习，从而使分类器具有自动识别能力就分类 器的训练学习方法来说，又可分为两种：一种叫做预分类的训练试验，即监督 训练；另一种口q 做未分类的训练试验，即无监督训练数据挖掘中的聚类与分类 从训练学习的角度来看分别属于监督训练和无监督训练，而人工免疫系统在训练 学习等方面具有其它系统无可比拟的优点，于是人们便开展了人工免疫系统应用 于数据挖掘的研究。 数据挖掘根据发现的知识类别分类可分为描述性挖掘和预测性挖掘两类。描 述性挖掘又包括特征与比较描述、关联规则挖掘、聚类分析等。聚类分析就是根 据数据对象的属性信息或对象间的关系，将数据对象分组成为类或簇，使在同一 簇中的对象之间具有较高的相似度，而不同簇中的对象彼此差别较大聚类分析 与数据挖掘中的分类不同，在分类模型中，存在样本数据，这些样本数据的类别 是已知的，分类的目的是从训练样本集中提取出分类的规则，用于对其他类别未 知的对象进行分类。而聚类分析预先不知道目标数据的有关类的信息，需要以某 种度量为标准将所有的数据对象划分到各个簇中因此，聚类分析有时又称为无 指导的学习或观察式学习，而不是示例学习。 目前常用的聚类算法主要可以划分为：划分方法( p a r t i t i o n i n gm e t h o d ) 、 层次的方法( h i e r a r c h i c a lm e t h o d ) 、基于密度的方法( d e n s i t y - b a s e dm e t h o d ) 、 基于网格的方法( g r i d b a s e dm e t h o d ) 和基于模型的方法( m o d e l b a s e dm e t h o d ) 。 但是随着社会和科技的发展，越来越产生大量的，复杂的，多样的数据，尤其是 i n t e r n e t 的流行，出现了海量的，异构的半结构化的数据等等，原来的数据聚 5 人工免疫系统研究及其在数据聚类中的应用 类方法也越来越不能适应新形势的发展，例如对于小规模，静态数据聚类的效果 较好，而大规模、动态时变数据问题的处理都不理想算法的稳定性差，运行效 率不高，参数设置较多，计算复杂等等。因此人们在不断的探索新的，更加高效 的数据分析方法。随着计算机技术和其它各个科研领域的发展，学科之间的交叉 作用越来越大，许多新技术、新方法不断涌现于是，人们也将相应的成果应用 于数据分析领域，例如人工智能、模糊系统、遗传算法、神经网络等技术在数据 分析技术中的应用以及数据挖掘概念的提出和研究，使得数据分析领域的研究取 得了重大进展免疫系统应用于数据聚类分析就是在这种形势下提出的“” 1 4 研究的目标和意义 关于生物免疫系统的功能及其机理的大量的医学和仿真研究表明，免疫系统 是一个性能优良的信息处理系统。其突出的信息处理特性有识别多样性、分布式 并行处理、自适应学习、联想记忆等。 当今社会是一个信息爆炸的年代，由于计算机网络的迅猛发展，信息处理技 术己成为各个领域不可回避的关键技术，怎样从海量的信息中找到有意义的特 征、规律和趋势，是我们面对大量信息时首先要想到的问题，也是数据分析和数 据挖掘的主要任务。数据挖掘是信息技术自然演化的结果，它是在模式识别、机 器学习、神经网络、数据分析等信息技术基础上发展起来的综合信息分析技术。 数据挖掘技术是现代信息处理研究的重要方向，而数据的聚类分析正是数据挖掘 的基础。因此，聚类分析方法的研究是信息处理技术研究的一个重点，免疫系统 的强大信息处理能力，无疑给人们指出了构造数据分析新方法的方向。 基于以上对免疫系统的特性和功能的认识以及实际应用需求的分析，本文的 研究目标集中在以下两个方面： 由于人工免疫系统只是近几年发展起来的新的研究领域。虽然关于它的研究 已被越来越多的人所重视，并逐渐成为关于新的进化计算和模式识别方法研究的 一个热点，但是，整个研究工作仍然显得比较零乱，缺乏系统性，有些方法名为 人工免疫方法，实质是对原有方法的改造，失去了应用免疫系统的意义；另外， 对于人工免疫系统的模型和应用缺乏深入的探讨，许多模型和方法并未真正体现 出人工免疫系统的应用特点，通过本文的研究提出人工免疫系统模型的一般模型 6 人工免疫系统研究及其在数据聚类中的应用 框架，为人工免疫系统理论及应用增添新的内涵，为人工免疫模型的进一步理论 探讨提供新的思想方法 在提出的一般模型框架的指导下，通过对r l a i s 系统和a i n e t 算法进行研究， 在此基础上提出新的a i s 聚类模型，克服传统的聚类方法中样本一旦划分到某个 类别后就不变，造成计算量大的缺点，利用人工免疫系统的自适应的特性，从原 始数据集中提取出有代表性的数据，因而大大缩小了原始数据的规模，从而使得 我们在面对大规模数据聚类的时候变得更加容易，从而更好地服务于实际问题， 更好地解决实际问题。 因此本文的任务是： 一基于免疫系统的构成和相关机理，通过对人工免疫系统模型、基本组件 及相关模型和算法进行分析，提出人工免疫系统的设计框架 二在结合r l a i s 系统和a i n e t 算法基础上提出改进的a i s 聚类模型，并进 行仿真实验。 1 5 本文研究的主要内容以及结构 本文在阅读大量文献的基础上，首先有针对性的介绍了生物免疫系统的一些 基本概念、系统组成、功能原理等；概述了人工免疫系统的一些主要原理及应用， 在此基础上，提出了人工免疫系统的一般模型框架。然后，对现有的典型的人工 免疫系统应用于数据聚类的算法进行详细分析，并在现有算法的基础上，针对其 不足，提出了改进算法，通过仿真实验进行了验证。 全文共分了六章，具体安排如下： 第一章绪论部分，简要论文的研究背景，研究目标和意义，以及论文的内容 与组织结构。其中，通过综述人工免疫系统和数据聚类的概况，提出本文的主要 任务是基于免疫系统的构成和相关机理，通过对人工免疫系统模型、基本组件及 相关模型和算法进行分析，提出人工免疫系统的设计框架。在结合r l a i s 系统和 a i n e t 算法基础上提出改进的a i s 聚类模型，并进行仿真实验。 第二章提出了人工免疫系统的一般模型框架。本章从信息处理的角度对生物 免疫系统一些特性机理的研究作了迸一步的总结和讨论，并结合前面关于现有的 人工免疫系统的模型和应用的综述，提出了人工免疫系统构造的一般框架，明确 7 人工免疫系统研究及其在数据聚类中的应用 了人工免疫系统的主要应用是通过上述的算法步骤产生反映问题解的特征值的 优良抗体。 第三章对人工免疫系统应用于数据聚类分析的典型算法进行详细分析，尤其 是指出现有算法在应用实际问题的不足，为第四章撮出新的改进算法作好铺垫。 第四章在前面分析的基础上提出新的自适应数据聚类算法，并对算法的变量 和实现过程进行详细分析。 第五章通过实验仿真的方法对提出的新的自适应的算法进行了验证，最后对 实验得出的结论进行了分析，从而证明了该算法的有效性。 第六章结论，是对本文的主要工作和贡献进行总结，并对今后工作提出展望。 8 人工免疫系统研究及其在数据聚类中的应用 第二章人工免疫系统的一般模型框架 生物免疫系统是分布式的自适应的动态平衡系统，具有学习、记忆和识别的 功能，近年来众多学者开始模仿免疫系统的作用机制用于其它领域的研究。下面 将现有的关于人工免疫系统的开发和应用划分为三个主要方向：免疫算法、人工 免疫网络以及人工免疫系统。在此基础上，提出了人工免疫系统的一般模型框架 2 1 生物免疫系统的相关概念及特性机理 2 1 1 生物免疫系统的相关概念 1 ) 免疫( i m m u n e ) 。是机体识别。已”与“非已”抗原，对自身形成天然 免疫耐受，对“非已”抗原产生排异作用的一种生理功能。 2 ) 抗原( a n t i g e n ) ：一种能够被抗体识别的分子。 3 ) 抗体( a n t i b o d y ) ：机体免疫细胞被抗原激活后，由分化成熟的b 细胞一 浆细胞合成分泌的一类能与相应抗原特异性结合的具有免疫功能的球蛋白。 4 ) 抗原的表位( e p i t o p e ) ：抗原表面所带的能被淋巴抗体所识别的物质 5 ) 抗体一受体( p a r a t o p e ) ：抗体表面可与抗原的表位结合产生识别作用的 物质。 6 ) b 细胞( b - c e l l ) ：一种主要的免疫细胞，骨髓依赖性淋巴细胞，在被抗 原刺激后产生抗体，可消灭抗原。 7 ) 抗体的独特型( i d i o t o p e ) ：在抗体的可变区的胺酸类物质，可与抗独特 型结合 8 ) 亲和力( a f f i n i t y ) ：抗原的表位与抗体的受体之间的结合力 9 ) 匹配( m a t c h ) ：抗原的表位与抗体的受体之间的结合，结合得越紧，亲和 力就越大。 2 1 2 抗体的基因型和表现型 抗体的基因型是抗体的基本遗传物质的构成。通常免疫系统存在几个抗体的 基因库( 人体是七个) ，每个基因库包含有同型而不同种类的基因，每个抗体的 9 人工免疫系统研究及其在数据聚类中的应用 基因型就是这些基因的组合 抗体的表现型就是不同型的基因型( 来源于不同的基因库) 所表现出来的不 同特性，即是一个实际的抗体较少量的基因库通过这种组合方式可构造出数量 十分庞大的不同类型的抗体( 即表现型) 。 2 1 3 免疫应答 免疫应答( i m m u n er e s p o n s e ) 指机体受抗原性异物刺激后。体内免疫细胞 发生一系列反应以排除抗原性异物的生理过程免疫系统有两种免疫应答的类 型：一种是遇病原体后，首先并迅速起防卫作用的称为固有性免疫应答( i n n a t e i m m u n er e s p o n s e ) ；另一种是适应性免疫应答( a d a p t i v ei m m u n er e s p o n s e ) 固有免疫应答中，执行固有免疫功能的有皮肤和黏膜的物理阻挡作用及局部 细胞分泌的抑菌、杀菌物质的化学作用等。固有免疫在感染早期执行防卫功能 适应性免疫应答的执行者是t 及b 淋巴细胞，是t 及b 细胞对特性抗原的应 答过程，故又称为抗原特异性免疫应答( a n t i g e n s p e c i f i ci m m u n er e s p o n s e ) 。 适应性免疫应答是继固有性免疫应答之后发挥效应的，在最终清除病原体、促进 疾病治愈及防止再感染中起主导作用。 适应性免疫应答又分为初次免疫应答和二次免疫应答两类。 初次免疫应答( p r i m a r yr e s p o n s e ) 的过程是由多种免疫细胞和免疫因子相 互作用共同完成的复杂过程，可人为地分为三个阶段。 感应阶段：抗原呈递细胞捕获、加工、呈递抗原和抗原特异性淋巴细胞( b 细胞和t 细胞) 识别抗原后启动活化的阶段。 反应阶段：抗原特异性淋巴细胞( t 、b 细胞) 接受抗原刺激后，在细胞因 子参与下活化、增生、分化为效应t 细胞和浆细胞( 由b 细胞产生) 的阶段，又 称为增生分化阶段。在该阶段，有部分淋巴细胞中途停止分化，成为静止状态的 免疫淋巴细胞，这些细胞为长命淋巴细胞。在间隔相当长时间后，当它们与相同 抗原再次相遇时，可迅速增生分化为效应t 细胞和浆细胞，这种淋巴细胞称为记 忆细胞。 效应阶段：浆细胞分泌抗体，抗体可与抗原特异性结合，从而杀灭抗原，产 生体液免疫效应；效应t 细胞发挥特异性细胞杀伤作用，产生细胞免疫效应的过 1 0 人工免疫系统研究及其在数据聚类中的应用 程。 在初次免疫应答后，免疫系统首次遭遇异体物质并将其清除体外，但免疫系 统中仍保留一定数量的b 细胞作为免疫记忆细胞，这使得免疫系统能够在再次遭 遇异物后仍能迅速反应并反击抗原，这个过程称为二次免疫应答。这种二次免疫 应答要归功于免疫系统内存留的b 细胞，这样当抗原或类似抗原再次入侵时，不 用再重新生成抗体，因为已经有抗体存在了，这意味着身体准备抗击一切再感染 2 1 4 联想记忆及再次应答 免疫系统及对于它所遇到过的抗原有记忆。如上所述，在免疫应答的反应阶 段，被某一抗原激活的免疫细胞会增殖分化，最后成为可以杀灭抗原的成熟细胞， 但有一部分这样的免疫细胞在中途停止分化，处于静止状态，成为对该抗原有记 忆的长命细胞当记忆细胞再次与周一种抗原相遇时，就会直接进入反应阶段， 快速、准确、高效地杀灭抗原，即发生所谓的“再次应答( s e c o n d a r y r e s p o n s e ) 匕 另外，免疫记忆是联想记忆。这是因为免疫的识别不要求抗原和抗体完全匹 配，所以对某一抗原的记忆细胞，也可能对与该抗原相似的另一抗原做出反应。 2 1 6 免疫调节及免疫网络 免疫系统作为人体重要组成部分，在防御病菌的同时，还通过免疫调节作用 保证身体的正常生理机能不受影响，即保持身体内环境的稳定，保持抗体种类的 多样性。免疫调节作用的发生主要源于三个方面：一是随着抗体的产生，将会与 免疫细胞竞争结合抗原，因而阻止了更多免疫细胞的活化二是在免疫应答过程 中，抑制性免疫细胞在被激活后会对应答过程产生抑制作用三是抗体及免疫细 胞本身具有的独特型也会被其他的免疫细胞所识别，并产生抗独特型抗体，这样 一来，某些免疫细胞受抗原刺激而激活和增生，则其他识别这种独特型的免疫细 胞也被激活并增生，如此形成的抗原、免疫细胞和抗体之间的相互作用。使它们 连成为独特型网络或称j e r n e 网络，就会对免疫细胞的活化和抗体的产生起到抑 制作用。 免疫调节作用的发挥与抗原和抗体的浓度以及亲和力密切相关。因此，免疫 调节是免疫系统内部各种免疫细胞和免疫分子通过相互促进、相互制约而使机体 l l 人工免疫系统研究及其在数据聚类中的应用 对抗原刺激产生最适应答、同时保持抗体多样性以防止有害的病理反应的复杂生 理过程 研究表明，免疫网络作为免疫系统中一个重要的动态调节机制，也是实现免 疫记忆的机制。在免疫系统中存在着动态的生死过程，经常受到刺激的免疫细胞 类型会较长期地存在，而那些长期得不到刺激的细胞就会死亡。而免疫记忆的存 在就是因为记忆细胞在免疫网络中与相邻细胞相互作用，从而得以长期生存。由 于每与一种抗原相遇，免疫网络中相应的抗体就会增加，因此可以说，免疫网络 的构成反映了免疫系统与抗原的相遇经历，或者说，免疫网络学习并且记住了免 疫系统所遇到过的抗原 综上所述，免疫系统是非常复杂的系统，其复杂程度不亚于大脑。在医学上 免疫学也是一门独立的学科。免疫学现在已经发展出许多分支，包括基础免疫学、 临床免疫学、分子和细胞免疫学等等，与内分泌系统、神经系统、d n a 遗传等其 他生物系统之间的关系也得到重视和研究。关于免疫现象还有许多问题没有搞清 楚，有许多还处在理论研究阶段，即理论免疫学但是，由目前的研究我们可知 免疫系统是一个并行的、分布式的、自组织自适应的鲁棒性系统它具有许多其 他研究和应用领域所追求的优良特性。深入研究免疫系统各种特性及其机理，并 构造出相应的人工免疫系统模型用于不同问题，确实是一个值得引起关注的研究 方向。 2 2 人工免疫系统现有算法研究 对免疫系统的识别多样性的研究，表明免疫系统的这一特性主要源于三个方 面：免疫细胞生长过程中形成的对“自己”和“非已”的认识；通过长期物种遗 传进化所形成的对抗原的共性的基于基因级的识剐；在免疫细胞与抗原相遇，发 生免疫反应时的克隆选择理论，即“细胞选择克隆”和“细胞超变异”所形成的 对入侵的特异性识别能力及“免疫网络”的免疫记忆能力 人们基于对免疫应答和识别多样性的认识以及应用的实际问题的需要，构造 出各种基于免疫的算法模型，大多数免疫算法都是针对优化问题提出的，而优化 问题与免疫系统的对应关系表达在下表中： 人工免疫系统研究及其在数据聚类中的应用 免疫系统免疫算法 抗原要求解的问题 抗体最优解向量 抗原的识别 问题的分析 记忆细胞产生抗体对过去的成功解的回忆 淋巴细胞分化优良解的保留( 记忆) t 细胞的抑制作用剩余候选解的删除 抗体的繁殖用遗传算子创造新的抗体 表2 1 优化问题与免疫系统的对应关系 接下来介绍几种具有代表性的免疫算法模型、特点及应用。 2 2 1 基于信息熵的免疫算法 t o y o of u k u d a 啪1 等在文中提出了一种基于信息熵概念的免疫算法，用来寻找 多模态函数的峰值优化问题的解算法中的问题的解( 即抗体) 用二进制数串表 示，抗原即是问题本身，抗体和抗体的相互作用用信息熵来表达，抗体与抗原的 相互作用用适应度来表达。然后，以每个解的刺激度为基础，执行选择复制、交 叉、变异等遗传操作，从而改变整个群体的性能，最终求得优化解。算法的流程 如图2 2 所示： 人工免疫系统研究及其在数据聚类中的应用 图2 2 基于信息熵的免疫算法流程图 与一般的遗传算法比较而言，这种免疫算法的特点在于： ( 1 ) 采用信息熵作为评价群体中解的相似度的指标，比采用海明威距离等指 标更能客观地反映其真实含义。 ( 2 ) 模拟免疫系统克隆选择中的抑制作用，在刺激度的计算式中引入基于浓 度的惩罚机制，既鼓励适应值高的解，又抑制浓度高的解，从而保证了算法的收 敛及解群体的多样性，更适合多峰值函数的寻优。 因此，这种免疫算法是一种有效的多峰值函数寻优算法，且具有保持全局多 样性及快速收敛的特性。但算法中存在多个参数要预先确定，给算法的性能带来 很大的变数。 基于上述算法模型，文o ”中做了仿真实验，将这一算法应用于两个典型的多 峰值函数，并与标准遗传算法进行了比较，得出结论：该算法在多峰值函数的寻 优中，比遗传算法更为有效，它包含了遗传算法随机启发式搜索的优点，同时又 具有遗传算法所不具有的多样性维持和学习机制 文嘲在此基础上设计的算法对解的选择率的计算做了简化，并将改进后的算 1 4 人工免疫系统研究及其在数据聚类中的应用 法应用于电磁设备形状的优化，证实了算法的有效性。 而文嘲依据免疫应答的超变异特性，改进了算法中的遗传操作，删去了交叉 算子。并用改进的免疫算法对五种典型的多峰值函数的全局优化问题作了仿真实 验，并与遗传算法和遗传规划的实验结果做了比较，表明改进的免疫算法在对具 有复杂的形状的多峰值函数寻优时，比其他算法效果要好，而对于形状比较平滑 的多峰值函数寻优时，遗传规划的效果更好一些 2 2 2 免疫规划( i m m u n ep r o g r a m m e 。i p ) 文羽中提出一种新的优化方法一“免疫规划”算法，该算法通过引入“免 疫算子”接种疫苗和免疫选择，在算法中模拟了人体免疫系统所特有的自适 应性和人工免疫这一加强人体免疫系统的手段，使构造出的算法具有快速全局收 敛的良好性能。文中详细阐述了疫苗的选取、免疫算子的操作方法以及整个免疫 规划算法的步骤，提出了免疫系统在工程中的应用新思路。算法的基本步骤如下 图所示： 图2 3 免疫规划流程图 人工免疫系统研究及其在数据聚类中的应用 ( 1 ) 采用接种疫苗的方式，加入了对问题的先验知识，可有效地加快算法 收敛速度和提高解的质量； ( 2 ) 采用基于退火选择的免疫选择方式，可防止“早熟”现象，又可保证 寻优过程朝着全局最优的方向进行； ( 3 ) 算法存在着突出的缺点：疫苗的选取和接种方式要求具体问题具体分 析，加大了算法实现的复杂程度。 文蜘中提出了这一新型的算法，并详细地描述免疫算子一接种疫苗和免 疫选择的具体实现方法，同时理论证明了算法的收敛性。文中都就t s p 问题介绍 了疫苗的选择方法及免疫算子的构造方法，在文嘲1 中将用进化规划和用遗传算法 对t s p 问题的解进行了比较，表明该算法可有效地减少遗传算法后期的波动现象， 同时使收敛的速度有较大的提高。文晦1 在讨论t s p 问题的同时，还用算法对个 典型的多峰值函数进行了优化，结果显示：疫苗