（计算机应用技术专业论文）基于免疫机制的模糊聚类方法的研究.pdf

摘要 论文题目：基于免疫机制的模糊聚类方法的研究 学科专业：计算机应用技术 研究生：吉欢 指导教师：王磊教授 摘要 签名：盔起 签名：艺盏： 本文针对经典聚类算法对初值敏感和易陷入局部极小值的问题，借鉴免疫细胞从不成 熟到成熟，进而转变为记忆细胞和抗体这一基本原理来指导数据对象聚类，提出了一种基 于人工免疫细胞模型的c 均值聚类算法。该算法一方面以亲和力为评判标准的二重选择 法，力求所选个体更具代表性：另一方面，通过引入一种自适应变异策略对选出的个体进 行变异操作，提高计算效率；并根据抗体浓度抑制原理选择最佳抗体组合，以达到优化的 目的。在整个寻优过程中，充分利用免疫记忆机制，保存优秀个体，替换较差个体，保证 算法的良性进化。通过与遗传指导算法( g g a ) 和人工免疫c 一均值算法进行比较，初步显 示新算法有利于提高其获得全局最优解的概率，在精度方面也有很好表现。 在上述工作的基础上，本文进一步研究了基于免疫粒子群优化的聚类算法。针对粒子 群优化算法和传统聚类算法易产生“早熟 现象的不足，把人工免疫系统的免疫信息进化 处理机制引入到粒子群优化算法( v s o ) 中，提出一种基于免疫进化粒子群的动态聚类算法。 算法中粒子适应度的高低有效表明粒子所对应分类方案下聚类效果的优劣，在此基础上选 择部分粒子进行多点均匀突变；初始聚类数遵循经验规则尼。，行0 为空间样本数) ，并 以性能代价函数为评判标准逐级递减寻找最优k 值，实现动态聚类。仿真实验证明，将具 有较强全局寻优能力的p s o 与局部搜索能力较强的免疫进化机制相结合，可以提高它们 各自处理问题的能力，避免“早熟”现象，同时使收敛精度较粒子群聚类明显提高。 通过理论分析和实验论证，我们可以认识到利用免疫思想改进聚类算法进而提高聚类 质量是可行的，文中所提出的混合聚类算法对解决实际聚类问题有一定的参考价值和实用 意义。 关键词：人工免疫系统；聚类；免疫细胞模型；信息进化 本研究得到国家自然科学基金( 编号：6 0 6 0 3 0 2 6 ) 的资助 a b s tr a c t t i t l e ：t h er e s e a r c ho ff u z z yc l u s t e rm e t h o d sb a s e do n l m m u n et h e o r y m a j o r ：c o m p u t e r a p p l i c a t i o nt e c h n o l o g y n a m e ：h u a nj i s u p e r v i s o r ：p r o f l e iw a n g a b s t r a c t s i g n a t u r e ：出f 塑。l 互 s i g n a t u r e ：驻 f o rt h ep r o b l e mt h a tt h ec l a s s i c a lc l u s t e r i n ga l g o r i t h mi su s u a l l ys e n s i t i v et oi n i t i a lv a l u eo r e a s yt ob r i n ga b o u tl o c a lo p t i m a ，an o v e lc l u s t e r i n ga l g o r i t h mi sp r o v i d e dw h i c hi sb a s e do n m o d e lo fc - m e a n sa n dt h ea r t i f i c i a li m m u n ec e l l s n a m e l y , w ei m i t a t ea ni m m u n ep r i n c i p l et o e x e c u t ec l u s t e r t h ep r i n c i p l ei st h a ti m m u n ec e l l sf i r s tc h a n g ei n t om a t u r ec e l l s ，a n dt h e n p o l a r i z ei n t oa n t i b o d i e so rm e m o r yc e l l s i m p o r t a n t l y , t h en e w a r i t h m e t i cp u tf o r w a r dad o u b l e s e l e c t i o nm e t h o db a s e do na f f i n i t yb e t w e e nc e l l st oe n s u r es e l e c t e dc e l l sm o r et y p i c a l ；b r i n g i n t oas e l f - a d a p t i n gm u t a t i o nm e t h o dt oa c c e l e r a t es p e e do fg l o b a lc o n v e r g e n c e ；s e l e c tt h eb e s t a n t i b o d yg r o u pa c c o r d i n gt oa n t i b o d yi n h i b i t i o np r i n c i p l e ；u s ei m m u n em e m o r ym e c h a n i s m k e e pg o o dc e l l sa n dg i v ea w a yb a dc e l l s i ns i m u l a t i o n ，w em a k eac o m p a r i s o n b e t w e e nt h e n e wa r i t h m e t i ca n dt h et w oa l g o r i t h m s ：g e n e t i cg u i d a n c ea r i t h m e t i c ( g g a ) a n da r t i f i c i a l i m m u n ec m e a n sa r i t h m e t i c t h er e s u l ts h o w st h a tn e wa r i t h m e t i ca p p e a r ss e v e r a lf e a t u r e s s u c ha sh i 曲a c c u r a c yo fc l u s t e r i n ga n db e t t e rc l u s t e r i n gc a p a b i l i t y b a s e do nt h ea b o v e m e n t i o n e d ，t h i sp a p e rr e s e a r c h e st h ec l u s t e r i n ga l g o r i t h mb a s e do n p a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m t h ei m m u n ei n f o r m a t i o ne v o l u t i o n a r ym e c h a n i s mo f a r t i f i c i a li m m u n es y s t e mi su s e di n t op a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m ( p s o ) ，an e w d y n a m i cc l u s t e r i n ga l g o r i t h mb a s e do nc - m e a n sa n di m p r o v e dp s oi sp r e s e n t e da n di tc a n a v o i d “e a r l yr i p e ”o fp s oa n dt r a d i t i o n a lc l u s t e r i n ga l g o r i t h m t h ep a r t i c l es u f f i c i e n c yc a n j u d g et h ec l u s t e r i n gs c h e m ei tc o r r e s p o n d i n gt o ，a n dt h e nw e c a l ls e l e c tp a r t so fp a r t i c l e si n t o m u l t i p l e p o i n tm u t a t i o n w ec a ng e tt h ei n i t i a lc l u s t e r i n gn u m b e r sa c c o r d i n gt ot h ee x p e r i e n t i a l r u l e 后。n0 i st h en u m b e ro fs a m p l e ) o fc l a s s i c a lc l u s t e r i n gt h e o r ya n df i n dt h eb e s tk v a l u et h r o u g hs w a r mp e r f o r m a n c ec o s tf u n c t i o n s i m u l a t i o ns h o w st h a tt h ec o m b i n a t i o no fp s o h a sh i g hg l o b a lc o n v e r g e n c ea b i l i t ya n dt h ei m m u n ee v o l u t i o n a r ym e c h a n i s mh a sh i g hl o c a l c o n v e r g e n c ea b i l i t yc a ne f f i c i e n t l yr a i s et h e i rr e s p e c t i v eh a n d i n gp r o b l e ma b i l i t y t h en e w 3 西安理工大学硕士学位论文 a r i t h m e t i cc a l la v o i d “e a r l yr i p e ”a n dh a sh i g h e ra c c u r a c yo fc l u s t e r i n gt h a nc l u s t e r i n go n l y b a s e do np s 0 t h r o u g ht h e o r ya n a l y s i sa n de x p e r i m e n tp r o o f , w ec a no b t a i nt h a ti m m u n ei d e ac a ni m p r o v e c l u s t e rq u a l i t ye f f e c t i v e l y t h en e wc l u s t e ra l g o r i t h mp r o p o s e di n t h i sp a p e ri su s e f u la n d v a l u a b l ef o rp r a c t i c a lc l u s t e rp r o b l e m s 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 ； c l u s t e r i n g ； i m m u n ec e l l sm o d e l ； i n f o r m a t i o ne v o l u t i o n a r y 4 独刨性声明 。秉承祖国优良道德传统和学校的严谨学风郑重申明l = v 本入所呈交的学位论文是我 l 个人在导师指导下进行的研究工作及取得的成果：尽我所知。除特别加以标注和致谢 的地方外j 论文中不包含其他人的研究成果；与我一同工作的同志对本文所研究的工 阼和成果的任何贡献均已在论文中作了明确的说明并已致谢。 。 7 本论文及其相关资料若有不实之处：，由本人承担一切相关责任j 语支作者签名；：盔建。如g 年弓月一日 学位论文使用授权声明 本人鱼缝：在导师的指导下创作完成毕业论文；，本人已通过论文的答辩， 并已经在西安理工大学申请博士一硕士学位一本人作为学位论文著作权拥有者，同意 授权西安理工大学拥有学位论文的部分使用权，1 即：j 【) 已获学位的研究生按学校规定 提交印刷版和电子版学位论文卜学校可以采用影印q 缩印或其他复制手段保存研究生 上交的学位论文，1 可以将学位论文的全部或部分内容编入有关数据库进行检索；2 ) 。为 教学和科研目的，学校可以将公开的学位论文或解密后的学位论文作为资料在图书馆、 资料室等场所或在校园网上供校内师生阅读、测览。 本人学位论文全部或部分内容的公布( 包括刊登) 授权西安理工大学研究生部办 。 理。 ( 保密的学位论文在解密后，适用本授权说明) 论文作者签名： 二殳鼓导师签名：二二匕醢，如g 等多月刀日 前言 1 前言 1 1 选题背景和意义 赖以支撑生物体复杂生命现象和高级智能行为的各种神奇法则一直是人类悠然神往 的奥秘和不竭的技术思想方法源泉，不断启迪着科学和工程技术向前发展。不论是从结构 模拟的人工神经网络，还是从功能模拟的模糊逻辑系统，还是着眼于生物进化微观机理和 宏观行为的进化算法，都是人们模仿生物智能行为，借鉴其智能机理来寻找解决复杂问题 的方法。这些方法被广泛应用于工程实践，涉及计算机安全、模式识别、数据挖掘和分析、 机器学习、联想记忆、优化等许多领域，产生了巨大的科研经济效用。 生物系统中的信息处理系统可分为脑神经系统( 神经网络) 、遗传算法( 进化计算) 、 免疫系统( 人工免疫系统) 和内分泌系统四种类型。免疫系统是复杂自适应系统，有效地 使用多种机制防御外部病原体。免疫系统得主要作用是识别所有色身体内的细胞，并将其 分类自体和非自体。通过进化学习，免疫系统在外部病原体和自身细胞之间进行辨别。免 疫系统具有许多研究主题，在局部层次提供了相当出色的自适应处理模型；在全局层次， 凸现出优化性能。现有许多理论和数学模型解释了免疫学现象，也有许多计算机模型仿真 各种免疫系统成分，从生物学角度研究免疫系统的整体性能，找到解决实际工程和科学问 题的智能方法。基于免疫学理建立的人工免疫网络具有与神经网络类似的自适应性和学习 能力，但它是建立在多个进程动态合作基础上；基于免疫学的免疫算法具有与遗传算法类 似的进化机制，但是它能实现精确控制群体多样性和特异性。从生物信息处理系统这个角 度讲，人工免疫系统可以归为信息科学，是与人工神经网络、模糊理论等智能计算和系统 并列的，但又不同的性质、功能以及潜在的新兴科学技术，可用于研究解决多种实际问题。 1 9 8 9 年举办的第十一届国际联合人工智能学术会议上提出基于数据库的知识发现 ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，简称r , g d ) ，它是指从大量数据中提取有效的、新颖的、 潜在有用的和最终可被理解的模式的非平凡过程乜1 。这个反复迭代的人机交互处理过程包 括多个步骤，主要有数据整理、数据挖掘( d a t am i n i n g ) 和结果的解释评估。其中数据挖掘 是整个k d d 过程中最核心的步骤，数据挖掘的目的就是运用特定的数据挖掘算法，从数 据库中提取用户感兴趣的知识，并以一定的方式表示出来，如树、表、规则、图等。 聚类是数据挖掘中的一种重要技术，也是分析数据并从其中发现有用信息的一种有效 手段3 1 。基于“物以类聚”的朴素思想，它将数据对象分组成为若干个类或簇，使得在同 一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别很大，通过聚类，人们能 够识别密集和稀疏的区域，发现全局的分布模式以及数据属性之间有趣的相互关系。聚类 分析在客户分类、基因识别、w w w 文本分类、空间数据处理、卫星照片分析、医疗图 像自动检测等领域有着广泛的应用，而其本身的研究也是一个蓬勃发展的领域，数据挖掘、 统计学、机器学习、空间数据库技术、生物学和市场学的发展推动着聚类分析研究的进展， 使它已成为数据挖掘研究中的一个热点。 西安理工大学硕士学位论文 2 0 0 0 年，d ec a s t r o 等人提出了用进化免疫网络来解决数据聚类分析问题 4 12 0 0 1 年 又明确提出了用a i n e t 免疫网络来解决该i u j 题“，并做了深入研究，指出免疫系统基本原 理可用于研究未标识数据集合的聚类和过滤问题，表明免疫系统具有强大的计算能力，可 以利用免疫的概念发展强大的数据处理计算工具。在深入了解此理论基础上，本文提出基 于免疫机制的c 均值聚类方法，不仅保持原有免疫算法考虑环境( 非己) 和主体( 自己) 之间的相互作用的思想，而且和优化算法相结合，引入“优胜劣汰”和基于“浓度 的选 择机制，在强调如何保持种群多样性的同时也注重提高种群的质量。免疫算法独有的信息 处理机制可以用于系统的优化搜索，改善传统聚类算法易陷入局部极值和“早熟”问题， 是一个非常重要且非常有意义的研究方向。 1 2 人工免疫系统的研究内容和应用领域 人工免疫系统涉及的研究内容和应用范围较为广泛，已超出了仅仅作为计算工具研究 的范围。从目前的研究和应用来看，多数仍以发展基于免疫原理的计算方法为主，包括各 种免疫算法、人工免疫网络和免疫计算系统和模型。 根据生物免疫系统原理发展新的算法，主要有阴性选择算法、克隆选择算法1 、免疫 遗传算法、免疫优化算法，以及为完成特定任务而设计的基于免疫原理的算法等，可统称 为免疫算法。目前这方面的研究和发展较活跃和迅速，本文所研究的算法就属于这一类。 各种免疫网络学说，如独特型网络、互联耦合免疫网络、免疫反应网络和对称网络等，可 借鉴用于建立人工免疫网络( a r t i f i c i a li m m u n en e t w o r k ，a i n ) 认知模型( 比如机器人系 统) ，目前应用最广泛的是独特型网络。免疫计算系统即利用免疫系统自身特性建立智能 计算系统，免疫系统具有动态保持自组织记忆能力，并允许信息遗忘，这些进化学习机制 和学习外界物质的自然防御机制可用于建立解决机器学习等问题的新型机器学习系统，还 可以发展用于解决数据分析等人工免疫系统，这方面整体发展比较慢，目前研究主要集中 在与神经网络的混合应用。 人工免疫系统的应用涉及多个领域，包括医学免疫学、计算机科学技术、计算智能、 模式识别、智能系统、控制理论与控制工程等，是比较典型的交叉学科，其理论极为广泛 和丰富，发展出的人工免疫系统形式也是多种多样的。国内外的专家一般在以上多个领域 都有所涉猎，先从事计算机科学研究而后从事人工免疫系统研究的专家居多。 1 3 人工免疫系统在数据挖掘中的研究现状 数据挖掘( d a t am i n i n g ) 是从大量数据中提取“挖掘 知识，其目的是帮助有关人员 寻找信息数据之间的内在关系，发现数据项之间新的要素或联系d 1 。因此，从生物免疫系 统中接受启发，其特征抽取、快速进化、学习和记忆特性，正是人们在进行数据挖掘时所 孜孜以求的。分类和聚类问题是数据挖掘的主要任务，在讨论之前，我们先简要地介绍一 下分类和聚类问题。 2 前言 1 3 1 分类问题 数据分类( d a t ac l a s s i f i c a t i o n ) 是一种数据分析形式，用于提取描述重要数据类的模型， 它是一个两步过程：第一步，建立一个模型，描述预定的数据类集或概念集；第二步，使 用模型进行分类。数据分类的最终目的是提出一个分类函数或者分类模型( 也常常称作分 类器) ，该模型能把数据库中的数据项映射到给定类别中的一个。 分类器的构造方法有统计方法、机器学习方法、神经网络方法等。统计学方法包括贝 叶斯法和非参数法( 近邻学习和基于范例的学习) ，对应的知识表示为判别函数和原型事 例。机器学习方法包括决策树和规则归纳法，前者对应得表示为决策树或判别树，后者一 般为产生式规则。神经网络方法本质上是一种非线性判别函数，此外还有粗糙集方法的知 识表示是产生式规则。分类器的效果一般和数据特点有关：有的数据噪声大，有的缺值， 有的分布稀疏，有的属性相关性强，目前普遍认为不存在某种方法适合于各种特点的数据。 1 3 2 聚类问题 聚类( c l u s t e r i n g ) 是按照一定的要求和规律对事物进行区分和分类的过程。与分类不 同的是，它要划分的类是未知的，它把一个没有类别标记的样本集按照某种准则划分成若 干个子集( 类别) ，使相似的样本尽可能归为一类，而不相似的样本尽量划分到不同类别 中。在这一过程中没有任何关于类别的先验知识，也没有教师的指导，仅靠事物间的相似 性作为类别划分的准则。通过聚类，我们能够识别密集的和稀疏的区域，因而发现全局的 分布模式以及数据属性之间有趣的相互关系。 数据聚类属于无监督模式识别，有贡献的研究领域包括数据挖掘、统计学、机器学习、 空间数据库学习、生物学以及市场营销。在商务上，聚类能帮助市场分析人员从客户基本 库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。在生物学上，聚类 能用于推导植物和动物的分类，对基因进行分类，获得对种群中固有结构的认识。聚类在 地球观测数据库中相似地区的确定，汽车保单持有者的分组，及根据房子的类型、价值和 地理位置对一个城市中房屋的分组上也可以发挥作用。聚类也能用于对w e b 上的文档进 行分类，以发现信息。作为一个数据挖掘的功能，聚类分析能作为一个独立的工具来获得 数据分布的情况，观察每个子集的特点，集中对特定的某些子集做进一步的分析。此外， 聚类分析可以作为其他算法( 如分类) 的预处理步骤，这些算法再在生成的子集上进行处 理。可见，数据聚类正在蓬勃发展，它已经成为数据挖掘研究领域中一个非常活跃的研究 课题。 1 3 3 人工免疫系统用于聚类问题的研究现状 各种传统的分类和聚类方法都有自己的优点和缺点，如模糊c 一均值方法将聚类问题 转化为非线性规划问题简单通用，但它需要输入需要聚类的类别数目，实际上通常我们是 不可估计的，而且对初值敏感。大多数方法都无法判别任意形状的类别，迄今为止，还没 3 西安理工大学硕士学位论丈 有一一种统一的方法可以取代其它方法。因此，不断地丌发新的方法，是这个领域的主要任 务之一。 受免疫机制启发，很多学者提出了不同的人工免疫算法模型，用于数据聚类分析、数 据浓缩、归类任务，取得了不少有益的成果。h u n t 和c o o k e u l 研究了基于a i s 模型的无 监督学习算法，将其用到了d n a 序列的分类任务中。c o o k e 构造的a i s 无监督学习算法 在执行聚类任务方面取得比决策树、a n n 和最d , l l 筒近法更好的效果，其误差率仅为3 。 在对人工免疫算法与聚类分析、k o h o n e n 网络进行对比分析后，j t i m m i s 1 指出，a i s 用 于数据分析是可行且有效的，可对训练数据进行建模，对输入空间的大区域有泛化能力， 并能对得到的进化网络提供更好的解释，获取更多的有用信息。他构造出一种与领域无关 的无监督机器学习方法用j 于二实验数据的聚类分析，进一步给出用于数据分析的有限资源 a i s 模型r l a i s 幻1 ，该模型在多谱影像的深入数据分析和网络故障预测中得到应用。l n d e c a s t r o 们借助人工免疫网络的进化实现对冗余数据的去除，深入研究数据的结构表示和 空间分布，基于免疫网络模型a i n e t 对高维原始数据进行聚类分析，进一步揭示出数据簇 内的相互关系。实验证明，该方法是一种非常有效的数据聚类分析方法。t a n g 应用a i n e t 并结合p c a 的方法对复杂的文本聚类问题进行了研究，与经典的层次聚类和k 一均值方法 相比，取得了更好的效果。 国内方面，王磊 1 2 1 郑建国“3 1 等人把人工免疫原理与小波神经网络相结合用于数据 挖掘中数据库规则的获取。李洁、焦李成“4 1 提出了一种有限资源的模糊神经网络结构聚 类方法，并将其用于混合属性特征大数据集聚类算法，取得了不错的效果。莫宏伟在 a i n e t 和a i r s 的基础上提出了人二 免疫网络记忆分类器，并将其成功地用于网络文本聚 类。 1 4 论文的研究内容和组织结构 1 4 1 论文研究内容 本文针对经典聚类算法对初值敏感和易陷入局部极小值的问题，借鉴人工免疫基本原 理，提出并研究了基于人工免疫细胞模型的c 一均值聚类算法和基于免疫进化粒子群的聚 类算法。 ( 1 ) 免疫算法的理论研究。作为一种仿生智能算法，免疫算法具有深刻的生物背景和 广泛的应用前景。因此，在解决实际问题时，将免疫算法或免疫模型不断完善，并与实际 问题流程相对应，对深刻认识免疫算法的性能，有效指导实际应用具有重要意义。本文考 虑到聚类算法中聚类中心迭代优化产生和其唯一性，在免疫细胞模型基础上引入免疫记忆 机制和抗体浓度抑制原理，改进现有免疫细胞模型。 ( 2 ) 基于免疫细胞模型的聚类算法的提出与研究。在第一步基础之上，将改进后的免 疫细胞模型应用指导聚类过程，提出新的基于人工免疫细胞模型的c 均值聚类算法，并 进一步确定算法涉及到的各个算子，提出一种更加有效的选择策略二重选择策略，结 4 前言 合抗体组合机制，不仅使各个聚类中心具有代表性，还保证了聚类质量。最后，本文利用 三组不同维数的数据集对算法进行验证，并与传统c 一均值聚类算法和一些已有的聚类算 法进行比较，证实了本文所提算法具有收敛精度高、聚类能力强等诸多特点。 ( 3 ) 基于免疫进化粒子群的聚类算法的提出与研究。针对已有粒子群聚类算法易产生 “早熟”现象的不足，引入免疫信息进化处理机制，增强算法局部搜索能力，同时定义一 个性能代价函数并以此为依据实现动态聚类。仿真实验表明，与已有粒子群聚类算法相比 较，此算法聚类正确率明显提高。 1 4 2 论文组织结构 在其后的介绍方面，首先，在第二章，对研究工作所依据的生物免疫系统的基本概念 进行了简要介绍，并详细地分析了人工免疫系统的一些仿生机理，在此基础上总结人工免 疫系统对聚类研究的启示。随后，在第三章，简要分析了聚类的机理和一些主要方法，特 别是对模糊c 一均值聚类算法( f c m ) 的优缺点进行了分析。在此工作的基础上，一方面， 在第四章，针对常用c 一均值算法尚且存在的一些不足，比较了免疫细胞成长周期和聚类 过程的相似性，提出基于人工免疫细胞模型的聚类算法，并对算法做出详细的理论分析和 实验论证；另一方面，在第五章，针对传统的粒子群聚类算法，同样从免疫学的基本原理 出发，提出一种基于免疫信息进化处理机制的、具有较高运行效率的粒子群聚类算法，并 对算法做出详细的理论分析和实验论证。最后，在第六章，对所从事的研究工作进行了总 结，并对下一步工作的可行方向提出了一些展望。 生物免疫系统和人工免疫系统 2 生物免疫系统和人工免疫系统 2 1 生物免疫系统 生物一生始终处于复杂多变、充满伤害的自然环境中，能够平安无事、进行正常的生 命活动，免疫系统在其中起着重要的作用。生物免疫系统以其有限的资源，有效地应付数 量庞大得接近无限的不同种类的病毒的侵害，其中蕴含的许多优良特性无疑引起了人们特 别的关注。从计算的角度来看，生物免疫系统是一个高度并行、分布、自适应和自组织的 系统，具有很强的学习、识别、记忆和特征提取能力，因此更好地了解免疫系统的运行机 制，有助于开发面向应用的免疫系统计算模型一人工免疫系统( a i s ) ，用于解决工程实际 问题。 图2 - 1 生物免疫系统组成 f i g 2 1t h ec o m p o s i t i o no f b i o l o g i c a li n l m u n es y s t e m 本章首先介绍生物免疫系统的基本概念，在此基础上阐述人工免疫系统的一些仿生机 理，从中得到对聚类研究的一些启示。 7 西安理工大学硕士学位论文 2 1 1 生物免疫系统组成 在自然界中，免疫是指机体对感染具有抵抗能力而不患疫病或传染病。免疫系统6 1 是由免疫分子、免疫细胞、免疫组织和器官组成的复杂系统，具有识别机制，能够从人体 自体细胞或自体分子和外因感染的微组织( 病原体或非自体元素) 中检测并消除病毒等病 原体本身以及因感染而引起的机体不良、功能紊乱、功能障碍等症状。如图2 1 所示。 免疫细胞 免疫细胞是指所有参与免疫应答或与免疫应答有关的细胞。免疫细胞主要有两大类， 一类为淋巴细胞，主要为t 淋巴细胞和b 淋巴细胞，它们分布于整个身体，对抗原的反 应有明显的专一性，在免疫中起主要作用，b 细胞的主要功能是在其表面产生抗体 ( a n t i b o d y ，a b ) ，t 辅助或抑制细胞防同刺激或抑制b 细胞抗体的分泌。第二类是单核巨 噬细胞，它具有摄取抗原、处理抗原，并将处理后的抗原通过一定方式呈递给淋巴细胞的 功能。淋巴细胞是免疫系统中最重要的免疫细胞，它在免疫应答过程中起核心作用，是人 体内数量较多的细胞群体之一。 免疫分子 免疫分子在机体免疫系统的发育，免疫细胞的活化和免疫应答中起着十分重要的作 用。免疫分子主要包括免疫细胞膜分子，如抗原识别受体分子、分化抗原分子、主要组织 相容性分子及一些其它受体分子等。它们在诱导和调节免疫方面也发挥着重要作用。 抗原、抗体、亲和力 抗原( a n t i g e n ，a 曲是指能刺激机体免疫系统引发免疫应答而产生抗体，并能与之发 生特异性结合而产生免疫效应的物质。这些物质对机体来说是非自身的，但在特定条件下， 机体某些自身成分也能被免疫系统当成抗原来识别。抗原有以下两种特性：免疫原性，指 抗原进入免疫机体后能促使机体产生抗体或者激活淋巴细胞产生免疫应答的特性，具有这 种特性的物质称为免疫原；特异反应性，是指抗原与抗体特异性结合的特性，抗原表面能 被抗体识别的特异性结构称为抗原决定簇( 表位e p i t o p e ) 。 抗体( a n t i b o d y ，a b ) 是b 细胞识别抗原后克隆扩增分化为浆细胞时所产生的一种蛋白 质分子，其主要功能是识别、清除机体内各种病原性异物( 抗原) ，也具有独特性( i d i o t o p e ) ， 即每个b 细胞只分泌一种类型的抗体。抗体是具有两种截然不同功能区的分子，部分 是保持相对静态的稳定区( c o n s t a n t ) ，简称c 区；另一部分是负责与多种感染抗原结合的分 子变化区( v a r i a b l e ) ，简称v 区，也称为抗体决定簇( 对位p a r a t o p e ) 。对免疫应答期间产生 的抗体多样性的研究已经证明v 区的体细胞变异随时间增加，正是可变区为免疫系统提供 了大部分鲁棒性和自适应能力。 抗体根据其对位与抗原表位的分子排列相互匹配情况识别抗原，两者的匹配度称为亲 和力。亲和力的大小同时取决于抗原和抗体两方面，特定的抗体分子对不同的相关抗原具 有不同的亲和力。一个抗体分子的平均亲和力可通过重复免疫而增强，这一现象称为亲和 力的成熟( a f f i n i t ym u t a t i o n ) 。图2 - 2 为带有几个不同表位的抗原，图2 - 3 为抗体及其独特 8 生物免疫系统和人工免疫系统 型和对位。 图2 - 2 抗原结构 f i g 2 2s t r u c t u r eo f a n t i g e n 免疫器官 a b ) 图2 3 抗体结构 f i g 2 3s t r u c t u r eo f a n t i b o d y 免疫器官包括中枢免疫组织和外周淋巴组织，以及由它们产生的多种淋巴因子和抗 体。中枢免疫器官是免疫细胞发生、分化和成熟的场所。包括脊髓和胸腺。外周免疫器官 不仅是成熟淋巴细胞和b 淋巴细胞定居的场所，而且还是这些细胞受抗原刺激后，发生 免疫应答的部位。 2 1 2 免疫识别和免疫应答 免疫识别 为了保护生物体，免疫系统面临的第一个问题就是区分“自我”( 自己体内组织) 和 “非我”( 外界入侵物质) 。只有那些不能与自我( 即机体本身组织) 发生应答的t 细胞 才可以离开胸腺，执行免疫应答的任务，从而防止免疫细胞对机体造成错误攻击，该过程 称为阴性选择( n e g a t i v es e l e c t i o n ) 。抗原进入体内选择具有相应受体的淋巴细胞系并与其 表面的抗原受体发生特异性结合，导致该克隆的淋巴细胞活化、繁殖、分化，从而引起特 异性免疫应答。另外，抗体本身具有“抗原决定簇 ，它能够被机体本身产生的其他抗体 所识别并引起反应，这样，抗体便具有识别抗原而又被其他抗体所识别的双重性。 f o r r e s t 等仿照阴性选择原理，提出了阴性选择算法，其核心是根据识别的对象特征 进行编码，定义一个自我集合并随机产生一系列检测器，用于检测自我集合的变化。根据 阴性选择原理，若检测集合与自我集合匹配，则完成匹配任务。免疫识别机理在图像识别 1 1 1 网络入侵检测 1 8 1 异常检测n ”中得到了广泛的应用。 免疫应答 免疫应答( i m m u n er e s p o n s e ) 是免疫细胞对抗原分子的识别、活化、分化和产生免疫 效应的全过程。它分为固有免疫应答和适应免疫应答两种，前者为机体先天获得，可对病 原进行快速清除；后者能适应或学习以识别特异抗原，并对其保持记忆，以便下次更快速 地应答。 适应免疫应答分为初次应答和二次应答两个阶段。初次应答发生在抗原初次进入机体 9 西安理工大学硕士学位论文 后，需首先刺激有限的特异性克隆扩增，才能达到足够的亲和力闽值，免疫系统爿能将首 次遭遇的异体物质清除出体外，但并不彻底，免疫系统中仍然保留一定数量的b 细胞作 为免疫记忆细胞，这使得免疫系统能够在再次遭遇到相同病原时快速反应并反击病原，称 为二次应答。二次应答更迅速，无需重新学习，且比初次应答具有更高的亲和力。可见， 适应性免疫应答具有特异性、记忆、区分自我与 e 我、多样性和自我调节等优良特性，这 些优良特性也是人工免疫系统隐喻机制的不竭之源。 抗体 0 r 暂抗原 图2 4 免疫应答 f i g 2 4i m m u n er e s p o n s e 2 2 人工免疫系统的基本概念和仿生机理 1 0 01 1 0 天数 2 2 1 人工免疫系统 人工免疫系统是借鉴、利用生物免疫系统( 主要是人类免疫系统) 各种原理和机制而 发展的各类信息处理技术、计算技术及其在工程和科学中应用而产生的各种智能系统的统 称。它实现了一种受生物免疫系统启发，通过学习自然防御机理的学习技术，提供了新颖 的解决问题的方法和途径。人体免疫系统所具有的免疫耐受、分布式并行处理、多样性、 自组织、自学习、自适应和鲁棒性等特点，激发人们探索其运行机理，并构造人工系统来 模拟人体免疫系统的优良特性。 从信息处理的角度来看，免疫系统具备强大的识别、学习和记忆的能力及分布式、自 组织和多样性特性，这些显著的特性不断地吸引着研究人员从免疫系统中抽取有用的隐喻 机制，开发相应的a i s 模型和算法用于信息处理和问题求解。下面对一些典型的a i s 仿 生隐喻机理进行讨论。 2 2 2 免疫学习和记忆 免疫识别过程也是一个学习的过程，学习的结果是免疫细胞的个体亲合度提高、群体 规模扩大，并且最优个体以免疫记忆的形式得到保存。免疫学习大致可分为两种：一种发 生在初次应答阶段，即免疫系统首次识别一种新的抗原时，其应答时间相对较长；而当机 1 0 生物免疫系统和人工免疫系统 体重复遇到同一抗原时，由于免疫记忆机制的作用，免疫系统对该抗原的应答速度大大提 高，并且产生高亲合度的抗体去除病原，这个过程是一个增强式学习( r e i n f o r c e m e n t l e a r n i n g ) 过程，对应于再次应答。免疫系统不仅可以实现对同一种抗原的识别，而且可以 对结构类似的抗原进行识别，这被称为交叉式应答。 免疫记忆对应于再次免疫应答和交叉免疫应答，下面以免疫系统对牛痘和天花的应答 为例，说明免疫记忆机制的作用( 见图2 - 5 ) ，该过程体现了疫苗免疫的思想。经过对牛 痘的初次应答后，免疫系统保存了对该病原的记忆信息，而当蛋白质结构与牛痘相似的天 花病毒出现时，由于联想记忆机制的作用，免疫系统同样可以对其进行识别和效应。免疫 记忆属于联想式记忆，是a i s 区别于其它进化算法的重要特性之一。 f a r m e r 脚1 首先指出了免疫记忆可以看作一种联想式记忆( a s s o c i a t i v em e m o r y ) 模型。 s m i t h 2 对免疫记忆模型与稀疏分布记忆( s p a r s ed i s t r i b u t e dm e m o r y ，s d m ) 模型进行了 对比，指出初次免疫应答对应着s d m 向记忆中存储信息的过程，而再次和交叉免疫应答 则可以看作是s d m 读取记忆信息的过程。免疫记忆机制目前在智能优化和增强学习方面 得到了具体应用，它可以大大加速优化搜索过程，加快学习进程并提高学习质量。总之， 免疫记忆是提高算法执行效率的一种非常有效的手段。 抗体 细胞 牛疲 再次成答 答 百而丽 数 天花 图2 - 5 免疫记忆机制示意图 f i g 2 - 5t h ei m m u n em e m o 巧m e c h a n i s m 2 2 3 免疫细胞模型 免疫细胞主要在骨髓和胸腺中形成，从其产生到成熟并进入免疫循环，需要经历一系 列复杂的变化。基于生物免疫系统构建的人工免疫细胞模型吻1 ，主要包括自体耐受、克 隆、变异、记忆及死亡等过程。 如图2 6 所示，免疫细胞在骨髓中产生，其需要经历一个耐受过程( 这里的免疫细胞 包含了b 细胞、t 细胞和抗体的特征) 。如果在耐受期内与自体发生匹配，就会死亡并被 新的免疫细胞所代替。 西安理工大学硕士学位论文 l 譬 图2 - 6 免疫细胞生命周期 f i g 2 6l i f ep e r i o do fi m m u n em e m o r y 免疫细胞经过耐受期后成熟，成熟的免疫细胞被排出骨髓，进入免疫循环。在免疫循 环过程中，若遇抗原产生匹配，且积累足够的亲和力( 亲和力成熟) ，则被激活转变为记 忆细胞，并进行克隆扩增，产生大量类似的免疫细胞，以低于更多抗原的入侵。 如果成熟免疫细胞在其生命周期内未能积累足够的亲和力，则走向死亡，并被新的成 熟的免疫细胞所取代。该过程和未成熟免疫细胞的死亡机制确保了免疫细胞的多样性，保 证了其对抗原空间的持续搜索能力，并能保留那些最好的免疫细胞。同时，对一个成熟的 免疫细胞，协同刺激也是需要的，这样可以降低错误肯定率。一个被证实为有效的免疫细 胞将导致一种对应的应答产生。 记忆细胞具有更长的生命周期( 甚至是无限长) ，记忆细胞在再次匹配抗原后就会被 再次激活并克隆自己，产生一个再次应答，在此过程中，系统能对以前识别过的抗原做出 迅速的反应。克隆生成的新细胞加入成熟细胞集。一部分符合条件的免疫细胞还能进行变 异，使系统具有了学习进化的能力。 2 2 4 亲和力计算 抗原一抗体( a g a b ) 之间的亲和力基于抗原抗体之间结构的相似性n 2 1 。常见抗体抗 原亲和力的计算方式包括抗体抗原之间的距离、匹配度等，以下介绍几种常见的亲和力计 算方法，需要注意的是，这几种方式也同样适用于抗体与抗体之间亲和力计算。 设实数坐标集合m ：( m 。，m 9 9o - ，m ：) ，m s sr 工，其中s 表示形态空间，三表示维数。 抗原a g m ，抗体a b m 。 1 2 生物免疫系统和人工免疫系统 ( 1 ) 距离 抗体抗原的亲和力和它们时间的距离有关，如e u c l i d e a n 距离( 见式2 1 ) 、m a n h a t t a n 距离( 见式2 2 ) 及h a m m i n g 距离( 见式2 3 ) 等。 n 一 d = ( 口阢一a g ，) 2 ( 2 1 ) 几一 d = 一昭一 ( 2 2 ) d ：壹万，6 = 1 , a b i a g ( 2 3 ) 智7i 。一0 ，o t h e r w i s e 、7 上式中抗体的坐标用 表示，抗原坐标用 3 1 f r 示。 当两个序列之间的距离最大时，分子问构成一个理想的互补，分子之间的亲和力最大。在 具体的应用中，也可能正好相反，即距离越小，则两者越匹配，亲和力越大。这要依据具 体的情况而定。本文后面所提算法中的亲和力就是这种情况。 ( 2 ) 结合强度 基于抗体抗原之间的结合强度，可以计算抗体抗原的亲和力为： ( 纠t = 击 其中，( a g ) k 表示抗体k 和抗原之间的亲和力， 在0 和1 之间。 ( 3 ) 匹配度 ( 2 ，4 ) 玖是抗体k 与抗原的结合强度，( a g ) k 的值 两个等长字符串之间每一个位置上的字符都相同，这种匹配叫完整匹配。但完整的匹 配在免疫系统中很少见，更多的是局部匹配，包括上面所说的h a m m i n g 距离等。 1 9 9 4 年，f o r r e a 提出了，_ 连续位匹配规则( r - c o n t i n u o u sb i t s ) ，它反映了两个字符串 之间的一种相似性。若r = 0 ，则无条件匹配；若严1 ，则只要有1 位相同，就能发生匹配； 若产字符串长度，则当且仅当两个字符串每一位均完全相同才会发生匹配。，值较大，其 分类较细，而厂值太小，将导致分类太粗。 2 2 5 抗体浓度抑制原理 生物体内存在成千上万种抗体，可以对多种多样的病原体或异源性蛋白甚至人工合成 的抗原产生应答反应，大量生成抗体，执行免疫功