（计算机应用技术专业论文）人工免疫的图像聚类算法的研究.pdf

太原理工大学工学硕士研究生学位论文 人工免疫的图像聚类算法的研究 摘要 随着2 0 世纪9 0 年代多媒体技术及h 他m e t 网络的发展，多媒体信息的 广泛使用将极大地方便和丰富人们的生活、学习和工作。如何组织、表达、 存储、管理、查询和检索这些海量的数据，是对传统数据库技术的一个重 大挑战。所以，传统图像数据库的检索方法经历了从基于文本( t e s t ) 方式 到基于内容( c o m e t ) 方式的改进，目前基于内容的图像检索技术在国内 外已经取得了不少成就。同时，对图像数据库的组织和管理是否合理成为 用户检索的关键所在，为此在用户检索之前将图像数据库中的所有图像进 行聚类是很有必要的。随着图像检索系统的不断改善，基于图像情感语义 的聚类会成为进一步的研究课题。 另一方面，很多生物机体在动态竞争的环境中展现出了强大而复杂的 学习和问题处理能力，生物机体的这些特性，激发了人们的思维，促进了 人类科学技术的发展，近年来兴起的人工免疫系统的研究又是一个崭新的 应用领域。其中，基于免疫原理的聚类算法，可以对包含数值属性和符号 属性的数据进行聚类，具有较强的适应性。 在进行聚类之前应该先提取图像特征并进行量化处理，量化后所得到 的数据将作为聚类分析的输入数据。 基于上面提到的几个问题，本文主要进行了以下几方面的工作，首先， 在简单介绍了图像的低层物理特征和图像颜色特征提取的典型方法的基础 i 太原理工大学工学硕士研究生学位论文 上提出了一种综合图像颜色、空间信息的特征提取方法：空间直方图度量 法。该方法的主要思想是：利用颜色直方图来统计整幅图像色彩的信息； 用分块颜色中心矩来统计色彩的空间分布信息。最后对两种特征失量以某 种权值加权累加。本文还总结了主要颜色所蕴含的情感语义信息，以便今 后进一步研究工作的展开。 其次，分析了传统聚类方法所存在的一些典型问题，提出了将人工免 疫算法运用到图像聚类中，并对算法设计步骤进行了详细的描述。 最后，实验部分主要包括四个模块，即图像获取、图像特征提取、免 疫聚类分析和结果分析。本文主要提取图像的颜色特征，进行量化后作为 聚类的输入数据，同时，本文还实现了传统k 均值聚类算法，经过比较， 证明本文将人工免疫算法应用到图像聚类中性能优于k 均值算法，同时证 实通过聚类能更好地改善图像检索系统的检索效率。 关键字：颜色特征提取，图像分块，人工免疫系统，聚类分析，情感语义 太原理工大学工学硕士研究生学位论文 r e s e a r c ho fi 队g ec l u s t e r i n ga l g o r i 田团 b a s e do na i u i f i c l 气li a 心小 a b s ，i r a c t w i t ht h ed e v e l o p m e n to f m u l t i m e d i at e c h n o l o g ya n di n t e m e ti n1 9 9 f f s ，o u g l i f e 、s t u d ya n dw o r kh a sb e c o m ec o n v e n i e n c e a n da b u n d a n c eb yu s i n g m u l t i m e d i ai n f o r m a t i o n s oh o wt oo r g a n i z e 、e x p r e s s 、s t o r a g e 、m a n a g e 、q u e r y a n dr e t r i e v et h e s ea b u n d a n td a t ah a sb e e nai m p o r t a n tc h a l l e n g et ot h e t r a d i t i o n a ld a t a b a s et e c h n o l o g y a n dt h e nt h er e t r i e v a lw a y so ft h et r a d i t i o n a l i m a g ed a t a b a s eh a v eb e e ni m p r o v e df r o mt e s tb a s e d t oc o n t e n tb a s e d ，n o wt h e i m a g er e t r i e v a lt e c h n i q u eh a sg a i n e dm a n yi n t e m a t i o n a ls u c c e s s e s a tt h es a n e t i m e ，i th a sb e c o m ea k e yf o ru s e r s r e t r i e v a lt h a ti si tr e a s o n a b l et oo r g a n i z ea n d m a n a g ei m a g ed a t a b a s e ，s oi ti sv e r yi m p o r t a n tt oc l u s t e ra l li m a g e si nd a t a b a s e b e f o r eu s e r s r e t r i e v i n g w i t ht h ei m p r o v e m e n to fi m a g e s r e t r i e v a ls y s t e m ，i t w i l lb eaf a r t h e rr e s e a r c hf i e l dt h a tc l u s t e r i n gb a s e do ni m a g e se m o t i o n s e m a n t i c 一 o nt h eo t h e rh a n d ，i nt h ee n v i r o n m e n to fd y n a m i cc o m p e t i n gm a n y b i o l o g yo r g a n i s m ss h o wag r e a ta n dc o m p l e xa b i l i t yo fs t u d y i n ga n ds o l v i n g s o m eq u e s t i o n s ，w h i c hi n s p i r e sh u m a n st h o u g h t ，a n da c c e l e r a t eh u m a ns c i e n c e t e c h n o l o g y ，l a t e l y ，t h ea r i s e na r t i f i c i a li m m u n es y s t e mh a sb e e nan e w 太原理工大学工学硕士研究生学位论文 a p p l i c a t i o nf i l e d t h e r e i n t o ，t h ec l u s t e r i n ga l g o r i t h mb a s e do ni m m u n et h e o r y c a nb eu s e dt oc l u s t e rd a t ac o n t a i n i n gn u m e r i c a lv a l u ea n d s y m b o la t t r i b u t e ，a n d t h i sa l g o r i t h mh a sg r e a t e ra d a p t a b i l i t y i m a g ef e a t u r e ss h o u l db ee x t r a c t e da n dt h e nq u a n t i f i e db e f o r eb e i n g c l u s t e r e d ，t h ed a t aq u a n t i f i e dw i l lb et h ei n p u td a t ao f c l u s t e r i n ga n a l y s i s b a s e do na b o v es e v e r a lq u e s t i o n s ，s o m ew o r k sw i l lb ep r o g r e s s e di nt h i s p a p e r f i r s t l y ，an e wf e a t u r ee x t r a c t i o nm e t h o ds y n t h e s i z e di m a g ec o l o ra n d s p a c ei n f o r m a t i o nw i l lb ea d v a n c e d ，w h i c hb a s e do ni n t r o d u c i n gi m a g e s v i s u a l i z a t i o nf e a t u r e sa n ds o m et r a d i t i o n a lm e t h o d so fi m a g ec o l o rf e a t u r e e x t r a c t i o n ，t h i sn e wm e t h o dc a nb en a m e ds p a c eh i s t o g r a mm e a s u r e m e n t t h e m a i ni d e ao ft h i sm e t h o di st h a tf i r s tt h ew h o l ed o l o ri n f o r m a t i o no f i m a g ew i l l b ec o u n t e du s i n gc o l o rh i s t o g r a m ；s e c o n dt h es p a c ed i s t r i b u t i n gi n f o r m a t i o no f c o l o rw i l lb ec o u n t e du s i n gc e n t r a l i t ym a t r i xo fp a r t i t i o n e dc o l o r ；f i n a l l y ，t h e t w of e a t u r ev e c t o r sw i l lb ea d d e d t o g e t h e rw i t hs o m ew e i g h t e m o t i o ns e m a n t i c i n f o r m a t i o no fs o m em a i nc o l o r sw i l lb ea l s os u m m a r i z e di nt h i sp a p e r ，w h i c hi s c o n v e n i e n tf o ra f t e r t i m em o r e r e s e a r c h e s e x p a n d i n g s e c o n d l y ，a f t e ra n a l y z i n g t h el i m i t a t i o n so ft r a d i t i o n a l c l u s t e r i n g a l g o r i t h m s ，t h ec l u s t e r i n ga l g o r i t h mb a s e do na r t i f i c i a li m m u n eh a sb e e n p r o p o s e di nt h i sp a p e r ，a n dt h ed e s i g n i n gs t e p so ft h i sn e wa l g o r i t h mh a sb e e n d e s c r i b e di nd e t a i l f i n a l l y ，f o u rm o d u l e si sc o n t a i n e di no u re x p e r i m e n t ，n a m e l y ，i m a g e o b t a i n i n g 、i m a g ef e a t u r ee x w a c t i n g 、i m m u n ec l u s t e ra i l a l y z i n ga n dr e s u l t s 太原理工大学工学硕士研究生学位论文 a n a l y z i n g i nt h i sp a p e r ，i m a g e s c o l o rf e a t u r e i se x t r a c t e dp d m a d l y ，a l t e r q u a n t i f y i n g ，t h e s ed a t aw i l lb et h ei n p u td a t ao fc l u s t e r i n g ，a tt h es a n l et i m e ， t h ek - m e a na l g o r i t h mh a sb e e nu s e df o ri m a g ec l u s t e r i n g ，t h a tt h en e w c l u s t e r i n ga l g o r i t h mb a s e da r t i f i c i a li n l m u n ei sb e t t e rt h a nk - m e a nc l u s t e r i n g a l g o r i t h mh a sb e e np r o v e db yc o m p a r i n g t h e i rp e r f o r m a n c e s ，a n dt h ee f f i c i e n c y o fi m a g er e t r i e v a ls y s t e mh a sb e e ni m p r o v e db yi m a g e s c l u s t e r i n gb e f o r e r e t r i e v i n g k e yw o r d s ：c o l o rf e a t u r ee x t r a c t i o n ，i m a g ep a r t i t i o n i n g ，a r t i f i c i a li m m u n e s y s t e m ，c l u s t e r i n ga n a l y s i s ，e m o t i o n s e m a n t i c v 声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下。 独立进行研究所取得的成果。除文中已经注明引用的内容外。本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名： & 茎2 e i i 事i ： 3 赴 。噬fe # 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的， 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) 。 e t l t l l ：丛2 ，堕if 墅 日期： 二囱。立if z 太原理工大学工学硕士研究生学位论文 第一章绪论 1 1 研究课题的来源、目的和意义 随着2 0 世纪9 0 年代多媒体技术及i n t e r a c t 网络的发展，可获取的图像和其它多媒 体数据越来越多，数据库容量不断增大。多媒体信息的广泛使用将极大地方便和丰富人 们的生活、学习和工作，为社会创造巨大的经济效益，并逐渐改变人们的生活和交流方 式。如何组织、表达、存储、管理、查询和检索这些海量的数据，是对传统数据库技术 的一个重大挑战。如果没有对多媒体数据自动和有效的描述，大量信息将被淹没在信息 的海洋之中，无法在需要时被检索出来。 早期图像数据库的检索方法主要是基于文本( t e x t ) 方式，通过对每一幅图像建立 关键词等描述信息作为图像索引，采用传统数据库来满足图像检索的要求。但是一些图 像的文本信息难以描述，不同人对同一幅图像有不同的理解，这样文本描述信息就存在 着多义性，因而不能取得满意的检索效果。为此人们提出了基于内容的图像检索( c b m ， c o n t e n tb a s e di m a g er e u i e v a l ) 方法，根据图像所包含的色彩、纹理、形状以及对象的 空间关系等信息，建立图像的特征矢量作为其索引，检索方法目前主要是对于图像的多 维特征进行相似查询。基于内容的图像检索把图像处理、图像识别、数据库三个领域的 技术成果结合起来，融合了图像理解技术，提供了更加有效的检索途径。目前，基于内 容的图像检索技术在国内外已经取得了不少成就：技术上各种方法层出不穷；学术上一 些较为知名的学术期刊已有了专刊介绍；应用上也取得了初步成果并得到了社会的广泛 关注和支持；并且在i n t e m e t 上已有许多关于基于内容的图像检索原型系统，最为著名 的有i b m 的q b i c 系统和哥伦比亚大学开发的v i s u a ls e e k 等，其应用领域涉及对媒体 数据库、电子图书馆、商标管理、医疗图像管理、公安系统、卫星图像管理等多反面的 图像检索。但基于内容的图像检索的初衷是希望根据图像的内容来衡量图像之间的相似 度，这里的内容主要是人对图像的理解和认识，即图像的高层语义，由于目前计算机视 觉及人工智能等技术还不完善，计算机对图像内容的建解与入对图像内容的理解存在着 巨大客观差距，这种差距造成了当前c b i r 系统中必然会存在“语义鸿沟( s e m a n t i c g a p ) ” 问题1 1 。而对图像数据库的组织和管理是否合理成为用户检索的关键所在，为此在用户 检索之前将图像数据库中的所有图像进行聚类是很有必要的。进一步，为便于用户进行 】 太原理工大学工学硕士研究生学位论文 基于语义的图像检索，对图像数据库中的所有图像进行语义分析和聚类分析同样是非常 有必要的。 在数据挖掘中，聚类( c l u s t e r i n g ) 分析方法【2 】是其重要的研究内容和基本形式之一。 聚类是一个将数据集划分为若干个组( c l a s s ) 或类( c l u s t e r ) 的过程，并使得同一个组 的数据对象具有较高的相似度，而不同组中的数据对象则不相似，其中相似或不相似的 度量是基于数据对象描述属性的取值来决定的。数据聚类方法主要有划分类方法、分层 类方法、基于密度类方法、基于网格方法和基于模型类方法等。同时，很多生物机体在 动态竞争的环境中展现出了强大而复杂的学习和问题处理能力，生物机体的这些特性， 激发了人们的思维，促进了人类科学技术的发展。人工神经元网络的产生和应用，进化 计算的发展都充分展示了这方面的成就和美好的应用前景，近年来兴起的人工免疫系统 的研究又是一个崭新的应用领域。人工免疫系统强大的信息处理能力使得它可用于数据 挖掘。应用人工免疫系统进行数据挖掘，可对训练数据进行建模，对输入空间的大区域 有泛化能力，从而获得更有效的信息。 进一步，基于免疫原理的聚类算法，可以对包含数值属性和符号属性的数据进行聚 类，具有较强的适应性。同时，图像的视觉特征( 颜色、形状、纹理等) 在进行量化之 后，我们可以将基于免疫原理的聚类算法应用到图像检索系统中，即根据图像的视觉特 征将图像分为不同的类，这样会更加有利于用户进行检索。 1 2 图像检索系统的关键技术 图像检索白7 0 年代以来便成为了一个非常活跃的领域，其动力主要来源于两大研 究领域：计算机视觉和数据库系统。传统的基于文本的图像检索，其研究主要在数据库 领域中进行，其典型框架是，首先对图像用文本进行注解，然后用基于文本的数据库管 理系统来进行图像检索。这种方法在图像库中的图像数量不大和图像的内容比较单一时 不失为一种简单易行的方法，但是，当图像的数萤非常大时，基于文本的图像检索存在 着两大困难：一是手工对图像进行标注所需的工作量太大，其二是图像内容的丰富性， 使得对于同样的图像，不同的人有不同的理解，图像注解的主观性和不精确性可能导致 后继的检索过程中的失配。 近年来，基于内容的检索已经成为一个研究热点，并成为多媒体数据库、数字图书 馆等重大研究项目中的关键技术。所谓基于内容的图像检索( c b i r ) ，是指直接根据图 2 太原理工大学工学硕士研究生学位论文 像媒体对象内容进行的各种特征检索，它能从数据库中直接找到具有指定特征或含有特 定内容的图像，它区别于传统的基于关键字的检索手段，融合了图像理解、模式识别等 技术，具有如下特点： 。 ( 1 ) 直接从图像媒体内容中提取信息线索。它突破了传统的基于表达式检索的局 限，直接对图像进行分析和抽取特征。利用描述图像的内容特征来建立索引。 ( 2 ) 基于内容的图像检索实质上是一种近似匹配的技术。在数据库中，需使用模 式识别的方法对图像库中的图像按不同索引特征分类。在检索过程中，它采 用某种相似性度量对图像库中的图像进行匹配，以获得查询结果。 ( 3 ) 特征提取和索引的建立，可由计算机自动实现，避免了人工描述的主观性， 也大大减少了工作量。 ( 4 ) 整个过程是一个逐步逼近和相关反馈的过程。基于内容的图像检索系统应具 有很强的交互能力，用户参与整个检索的过程，它是图像数据库的一个重要 的方面。交互性增加了用户表达查询、评价查询结果和基于这些评价上进一 步检索的能力，是一个闭反馈结构。 按照检索时所基于的不同图像特征，可将基于内容的图像检索技术分为如下四种类 型：基于颜色特征的检索、基于纹理特征的检索、基于形状及区域的检索、基于空间约 束关系的检索。 图像检索系统即由两个子系统构成，库生成子系统和查询子系统，库生成子系统主 要以离线的方式工作，而查询子系统提供在线的图像检索功能。 库生成子系统完成的主要功能是图像预处理和特征提取。图像预处理包括对入库前 的图像进行的一系列处理，如色彩空间转换、图像去噪等。基于内容检索是建立在图像 视觉特征提取的基础上的，特征提取是库生成子系统的核心模块，它主要完成图像视觉 特征的提取。 图像查询子系统完成基于内容的检索功能。由查询接口、结果浏览器、检索引擎三 个模块组成。图像检索的一般过程为：首先通过图像库生成子系统生成图像特征库及图 像库，此操作可以脱机执行；然后用户通过查询接1 2 1 进行参数设置，包括显示的图像的 数目，用户感兴趣的图像特征以及一些阈值；在用户提交了检索请求( 如范例、草图) 后，检索引擎主要是完成图像的相似性匹配工作，并按照相似度的大小对图像进行排序； 最后结果浏览器主要用来显示查询的结果；一个典型的图像检索系统结构图如图1 - 1 所 3 太原理工大学工学硕士研究生学位论文 承： i 。j ；i ：l ；：i j ；i i 。j 图l 一1 图像检索系统结构图 f i g 1 1t h e $ ( n l c t t t r oc h a r to f i m a g er e t r i c v a ls y s t e m 一般而言，基于内容的图像检索系统涉及到以下几项技术： 图像视觉特征的提取及利用 特征( 内容) 提取是基于内容图像检索的基石，广义上讲，特征既包 括文本特征( 关键字、标注等) ，又包括视觉特征( 颜色、纹理、形状等) 就视觉特征范畴而言，又可分为一般特征和领域特定特征。前者包括颜色、 纹理、形状和物体间方位关系等，而后者根据不同的应用有所不同( 如人 脸识别、指纹识别) 。本文只涉及视觉特征范畴中的一般特征。 有效的特征表示及识别 由于感知的主观性，许多特征具有从不同角度来描述此特征的多种表 示，对一个给定的特征不存在一个最优的特征表示。对于特定领域的图像 检索，选取哪一种或哪几种特征表示，通常需要做具体的尝试。 空间区域特征的自动提取 对于基于形状及区域的图像检索，如何提取空间区域特征( 如边缘、 方位关系等) ，如何表示与利用这些特征成为关键问题。 高效的特征索引技术 4 太原理工大学工学硕士研究生学位论文 许多检索算法的实验数据仅仅几百个或上千个，虽然采用顺序搜索， 但感觉不出检索的响应时间。而对于大型图像库，则肯定需要建立索引。 因为内容特征，尤其是在集成多特征的检索中，特征矢量高达1 0 2 量级， 大大超过了常规数据库的索引能力，因此，需要研究新的索引结构和算法， 以适应快速检索的要求。 综上所述，我们可以用分类树形式将基于内容的图像检索主要研究技术表示如下： 图1 - 2 基于内容图像检索的主要研究问题分类树 f i g 1 - 2c l a s s i f i c a t i o nt r e eo f d o m i n a n tr e s e a r c hq u e s t i o n so f c o n t e n tb a s e di m a g er e u i e v a l 1 3 国内外的研究现状 1 3 1 人工免疫系统的研究现状 人工免疫系统是继人工神经网络、遗传算法和蚁群系统f 4 1 之后，又一个从生物系统 中获得灵感，并与计算机技术相结合用于解决工程实际闯题的计算机模型。人工免疫系 统是生物免疫学与计算机科学相结合的产物，生物免疫系统是人工免疫系统的结构和工 作原理的重要思想来源。 5 臁呋 ，i i i 十扑索索索索索索教翻 去 征征征征征征滇谤 懿 特特特特特特偶消 勤 色色廓域构计 玛缘 魅 颜颜轮区结绕胁对 舳 局部状状理理 埔问去伽 一一一一一一一一撤一 结结征 征 征 征 厂l q 鬈一一一吖一 检的 像 黻 舨 嫩 籼融 醐耋| 枞 袱 酶 蝻瓣 舳；| 霎 脯 醐 舳 拍黼 黼刺 黼 舰 黼 新徽 髂臁 昭 鳙 熔 基于内容的图像检索主要研究技术 太原理工大学工学硕士研究生学位论文 大约从2 0 世纪中叶开始，人们就已经开始注意到生物系统，尤其是人类自身功能 及结构的模仿，由此产生了许多新的研究领域。如人工神经网络i s 、模糊控制、进化计 算、遗传算法嘲及免疫算法口1 等。 2 0 世纪7 0 年代，蛔m 踊】首先提出了免疫系统的网络假说，并以此开创了人工免疫 系统的基础理论独特型网络理论【9 】。p e r e l s o n e l 0 1 在独特型网络理论的基础上进一步给 出了免疫网络的数学框架，从而加快了人工免疫系统在计算机科学方面的发展。1 9 8 6 年， f a r m e r l l l 】基于免疫网络的假说，构造了一个免疫系统的动态模型，并提出了一些学习算 法的构造思想，这些为人工免疫系统的实际应用指明了方向。他的工作对于人工免疫系 统的发展尤其是在信息安全领域应用的发展具有十分重要意义。 人工免疫系统继承了生物免疫系统的许多优良特性，这些特性使得人工免疫系统很 快的成为学术界研究的热点，并成为计算智能研究的一个崭新的分支。e v o l u t i o n a r y c o m p u t a t i o n ，i e e et r a n s a c t i o no ne v o l u t i o n a r yc o m p u t a t i o n 等许多国际期刊将人工免疫 系统作为重要议题。在2 0 0 1 年和2 0 0 2 年i e e et r a n s a c t i o no ne v o l u t i o n a r yc o m p u t a t i o n 还相继出版了人工免疫系统专辑。此外，人工免疫系统也已成为计算机国际学术会议的 热点议题，如i e e es y s t e m ，m a na n dc y b e m e t i c s 国际会议从1 9 9 7 年开始每年组织专门 的人工免疫系统研讨会，还有g e c c o ( g e n e t i ca n de v o l u t i o n a r yc o m p u t a t i o n c o n f e r e n c e ) ，c e c ( c o n g r e s so ne v o l u t i o n a r yc o m p u t a t i o n ) 等国际会议也将人工免疫系 统作为讨论的主题之一。2 0 0 2 年9 月在英国k e n t 大学还成功召开了第一届人工免疫系 统国际学术会议i c a r i s ( 1 s t i n t e r n a t i o n a l c o n f e r e n c e o n a r t i f i c i a l i i n i n u n es y s t e m s ) 。 1 人工免疫系统理论研究 目前，在计算机学术界，对于人工免疫系统定义的还不统一，存在若干种对人工免 疫系统的不同定义。s t a r l a b 提出的人工免疫系统的定义为“人工免疫系统是一种数据处 理、归类、表示和推理策略，一该模型依据一种似是而非的生物范式，即人体免疫系统”。 d a s g u p t a 随后也对人工免疫系统下了定义，他认为“人工免疫系统由生物免疫系统启发 而来的智能策略所组成，主要用于信息处理和问题求解”。此外，t n n m i s 也给出了人工 免疫系统的定义：“人工免疫系统是一种由理论生物学启发而来的计算范式，它借鉴7 一些免疫系统的功能、原理和模型并用于复杂问题的解决”1 1 2 | 。 按照目前人们普遍接受的观点，人工免疫系统是在生物免疫学的相关原理和概念的 基础上，面向解决工程实际应用问题提出的具有智能性的计算机模型。它的主要特点包 6 太原理工大学工学硕士研究生学位论文 括：自适应性( 学习性) 、记忆性、鲁棒性、并行性、可扩展性和多样性等。目前，基 于生物免疫系统仿生机理开发的人工免疫系统的理论研究主要在人工免疫网络模型和 人工免疫算法两个方面。 1 ) 人工免疫网络模型 免疫网络学说最早是由j e m e s l 在基于生物免疫学的基础上提出的。随着免疫网络 学说的发展，免疫网络模型也随之诞生了，并且在不断的发展和完善。s t a , a e r t ”1 在j e m e 的工作的基础上提出了一种独特型免疫网络的数学模型，模型中b 细胞的繁殖由一个 非负的、对称的函数控制，用动态方程来描述免疫网络的动态行为。h i r a y a m a 1 叼用数学 方程描述独特型免疫网络在短时间内的动态行为。免疫网络学说和免疫网络模型为人工 免疫后来的发展提供了重要的理论基础。 随着人工免疫系统研究的不断发展，开始出现多种针对于不同应用领域的免疫网络 模型。目前除了独特型网络模型以外，免疫网络模型主要还包括：抗体网络模型1 5 1 、多 值免疫网络模型【1 6 1 、免疫联想记忆模型【1 7 1 和互联耦合网络模型等。虽然，这些模型 的应用和功能各不相同，但它们都是建立在免疫网络学说的基础上的。对于众多的免疫 网络模型来说，人工免疫系统都被视为一个由若干节点组成的网络结构，节点之间是通 过相互的信息传递和相互作用来达到动态平衡的，从而实现免疫识别、免疫响应和免疫 记忆等免疫系统功能。其中，免疫网络的动态平衡特性则是人工免疫网络模型的重点研 究部分。 在近十几年中，人工免疫网络模型引起了众多研究人员的关注，对各种人工免疫网 络模型的深入研究也在激烈的进行着，目前，人工免疫网络模型已从计算角度得到了实 际的应用。 2 ) 人工免疫算法 计算机科学研究工作者在研究免疫网络模型的同时，又通过学习和模仿生物免疫系 统的学习机理，设计出多种面向不同应用领域的人工免疫算法。这些人工免疫算法也成 为人工免疫系统理论研究的主要组成部分。 ， f o n e s t 1 明根据生物免疫系统具有否定选择机制( n e g a t i v es e l e c t i o n ) 提出了否定选 择算法( n e g a t i v es e l e c t i o na l g o r i t h m ) ，并将其成功的应用到网络安全领域。k i m 2 0 l 】 又在f o r r e s t 的基础上对否定选择算法进行了理论研究。 7 太原理工大学工学硕士研究生学位论文 克隆选择算法( c l o n a ls e l e c t i o n a l g o r i t h m ，c s a ) 是由d ec a s 臼o 2 2 基于生物免疫 系统的克隆选择理论提出的进化算法，该算法具有较好的噪声容忍性和更强的柔性。克 隆选择算法已经被成功应用到模式识别等领域吲。 免疫算法( i m m u n e a l g o r i t h m ，i a ) 2 4 5 1 是在抽取和反映人工免疫理论的基础上， 结合遗传算法提出一个用于求解科学研究和工程技术中各种组合搜索和优化计算问题 的计算模型，它已经在求解诸如组合优化、智能优化和数据挖掘等问题中显示了强大的 数据搜索能力。 随着人工免疫系统理论研究的不断发展，研究者不断从生物免疫系统中汲取精髓， 并将其与计算机科学相结合，不断提出新算法。目前，已经提出算法主要包括：免疫目 标算法 2 0 3 、免疫a g e n t 算法1 2 7 1 、免疫d n a 算法 2 5 1 、基于免疫网络的学习算法【4 】、基于 人工免疫系统的无监督学习策略口明等。这些新算法的提出也将不断地丰富人工免疫系统 的理论研究。 2 人工免疫系统应用研究 随着人工免疫系统理论研究的不断发展，基于人工免疫系统原理开发的各种模型和 算法逐渐被广泛地应用到科学研究和工程实践中。网络安全领域是人工免疫系统最早的 应用领域，也是目前比较成功的应用领域之一。此外，由于人工免疫系统强大的信息处 理和问题求解能力，它的应用领域也已逐渐扩展到模式识别、智能优化、数据挖掘、机 器人学、自动控制和故障诊断等诸多领域。 1 ) 网络安全领域应用 计算机的网络安全问题与生物免疫系统所遇到的问题具有惊人的相似性，两者都要 在不断交化的环境中维持系统的安全性。免疫系统所采用分布的、灵活的、自适应的解 决问题的方式是计算机安全领域中期望得到的。 ， f o r r e s t 根据生物免疫系统自我识别与非我识别的原理，建立了人工免疫网络安全模 型并给出了模型的基础算法否定选择算法。随后，基于人工免疫网络安全模型的开发 的主机身份认证系统p 0 取得了巨大的成功，这使得人工免疫网络安全模型成为网络安全 界关注和研究的热点。k i m 2 1 培于克隆选择和反向选择机理研究了网络的入侵检测问 题，指出了影响入侵模式检测的几个因素，并通过实验证明嵌入式阴性检测算子对于维 持较低的误报检测率是十分关键的。 8 太原理工大学工学硕士研究生学位论文 人工免疫网络安全模型已成为人工免疫系统最主要的研究和应用领域，人工免疫网 络安全模型的发展也将反过来促进人工免疫系统的发展。 2 ) 其他应用 人工免疫系统继承了生物免疫系统的许多不同的特性，主要包括有多样性、分布性、 容错性、动态学习性和自适应性等。因此，人工免疫系统特别适合于解决具有鲁棒性、 自适应性和动态性等要求的实际工程应用问题。许多面对以上的问题计算机应用领域已 经从人工免疫系统中得到许多有益的帮助，并取得了成效。 在病毒检测方面，d h a e s e l e 护1 1 使用反向选择算法来检测被保护数据和程序文件的 变化，以检测原来没有被发现的新病毒。k o p h a l t 3 2 - 电提- k 了一种病毒检测方法，它采 用已知病毒的特征代码序列来检测已知病毒，而未知病毒则通过系统中发现的异常行为 加以检测。 在模式识别方面，f o r f e s t 1 9 】给出了人工免疫系统的二进制模型，研究了模式识别问 题和免疫系统中个体与群体水平上的学习机制。d a s g u p t a 研究了光谱识别问题，采用二 进制对光谱识别的对象进行了具体描述，同时还给出了相应的匹配函数以及识别算法。 d ec a s t r 0 1 2 3 研究了基于克隆选择机理的字符识别问题，采用状态空间表示待识别的模 式。h u n t p 3 】给出了基于j a v a 实现的人工免疫系统框架j i s y s ，并将其用于模式识别。 在数据挖掘p 4 方面，h u n t 和c o o k e 3 5 谚f 究了基于人工免疫系统模型的无监督学习 算法，将其用到了d n a 序列的分类任务中。在分析人工免疫系统与聚类分析( c l u s t e r a n a l y s i s ) 、科赫网络( k o h o n en e t w o r k ) 剧1 2 1 ，t m a m i s 提出了用于数据分析的有限资源 人工免疫系统模型r l a i s 跚1 。d ec a s t r o 提出了基于人工免疫网络模型a l _ n c t 的高维原 始数据的聚类分析方法嘲。 在机器人学方面，人工免疫系统在机器人行为控制、行为仲裁和路径规划等方面得 到了很好的应用。m i t s u m o t o p r j 基于人工免疫系统的“自我”和“非我”识别网络，研 究了基于免疫的自组织多机器人系统群体控制策略。i s h i g u r o 1 明构造了一个基于免疫网 络的机器人行为规划框架i m m u n o i d 。 在故障诊断方面，d a s g u p t a 提出了一个用于检测系统和进程中稳态特征的变化的高 效检测算法，并将该检测算法用于铣削刀具断裂检测中p s ) 。i s h i d a 研究了基于p d p 网 络模型的学习算法在分布式故障诊断中的应用，将免疫网络模型用于故障诊断的相互特 征识别。 9 太原理工大学工学硕士研究生学位论文 此外，人工免疫系统还在其它一些方面有一定的应用，如噪声控制、联想记忆、决 策支持系统、基于智能主体的策略等。由于人工免疫系统具有许多优良特性，因此它正 在被越来越多的应用到各种不同领域中去，这些应用也将反过来促进人工免疫系统的发 展。 由于人工免疫系统的研究还处于一个起步阶段，学者们对a i s 算法和模型的研究还 不完善，a i s 的实际应用也比较肤浅，所以就人工免疫系统的研究我们还需在以下几个 方面展开： 进一步挖掘生物人工免疫系统中可用于a i s 的相关机理。然后进一步根据新的 计算机理设计出新的a i s 算法。 迸一步改进已有的人工免疫算法和模型。很多人工免疫系统模型还比较简单， 不能满足人工智能应用的需要，就是利用模型深入理解算法的执行过程，分析 算法的收敛性，计算量，进而改进相应的算法。 进一步将人工免疫算法与其他仿生计算的算法相结合，例如和遗传算法、神经 网络算法等结合。 努力开辟人工免疫系统新的应用领域。 1 3 2 图像聚类算法的研究现状 聚类分析是知识发现( k d d ) 中一项重要研究内容，旨在将数据集和划分成为若 干类的过程，市的类内差异小，类间差距大。通常用数据之间的距离来描述相似度，距 离越大，相似度越小，反之则越大。理想的聚类算法应该具有可扩展性、能发现任意形 状、用户输入参数少、对噪声不敏感、能处理高维数据、可解释性和可用性【3 9 】。国内外 学者已经提出了不少相关的算法，大体上可分为划分方法、层次方法、基于密度的方法、 基于网格的方法和基于模型的方法。 其中，基于划分的典型聚类算法有：k - m e a n s 算法，在该算法中，每个簇用该 簇中对象的平均值来表示；馒) k - m e d o i d s ，在该算法中，每个簇用接近聚类中心的一个 对象来表示。这些启发式聚类方法适用于处理小规模的数据集并从中发现较规则形状如 球状簇，为了对大规模的数据集进行聚类，以及处理复杂形状的聚类，基于划分的方法 需要进一步的扩展。 层次的方法对给定数据对象集合进行层次的分解。根据层次的分解如何形成，层 1 0 太原理工大学工学硕士研究生学位论文 次的方法可以分为凝聚的和分裂的。层次方法的缺陷在于，一旦一个步骤( 凝聚或分裂) 完成，它就不能被撤消。这个严格规定是有用的，由于不用担心组合数目的不同选择， 计算代价会较小。但是，该技术的一个主要问题是它不能更正错误的决定。有两种方法 可以改进层次聚类的结果：在每层划分中，仔细分析对象间的“联接”；合层次凝 聚和迭代的重定位方法。首先用自底向上的层次算法，然后用迭代的重定位来改进结果。 基于密度的聚类算法主要有d b s c a n 算法和o p t i c s 算法，前者是一个有代表性 的基于密度的方法，它根据一个密度阈值来控制簇的增长。后者是另一个基于密度的方 法，它为自动的和交互的聚类分析计算一个聚类顺序。 基于网格的方法把对象空间量化为有限数目的单元，形成了一个网格结构。所有的 聚类操作都在这个网格结构( 即量化的空间) 上进行。这种方法的主要优点是它的处理 速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。 基于模型的方法为每个聚类假定了一个模型，寻找数据对给定模型的最佳拟合。一 个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类。它也基于 标准的统计数字自动决定聚类数目，考虑“噪声”数据或孤立点，从而产生健壮的聚类 方法。 聚类方法在图像检索中也已有较多的应用，o e r s h o 和c - r a y 采用色彩的聚类方法对 图像数据库进行检索，它将所有颜色聚类为n 类，这n 类颜色的集合称为色彩簿，图 像中任意像素的色彩值可以聚类为色彩簿中的一种色彩，然后统计色彩出现的次数，形 成颜色直方图，樊昀等提出一种自淬火编码聚类算法，利用编码的复杂度来确定类别的 数目，并采用自淬火机制克服聚类算法对聚类的初始中心选择的敏感问题，陈希超等提 出h s v 空间的颜色统计聚类的检索方法，在结肠镜图像检索系统中得到应用。 2 0 世纪5 0 年代以来，图像聚类一直是同