人工免疫算法在聚类分析中的应用研究m.文件
人工免疫算法在聚类分析中的应用研究m.文件[20200211151950]
摘要
当前对人工免疫算法（Artificial Immune Algorithm）的研究已经成为人工智能的一个重要研究领域。它是受生物免疫系统启发，在原有进化算法理论框架内引入免疫机制，而形成的一种新的进化理论。突出地体现了现代科学发展的多层次、多学科和多领域的相互渗透、相互交叉和相互促进的特点，为工程实践人员提供了许多富有成效的技术和方法。本文首先分析了聚类思想,并通过MATLAB仿真介绍常用的聚类算法。然后介绍遗传算法聚类分析，再将人工免疫原理引入到遗传算法(Genetic Algorithm) 中，并应用于聚类分析, 提出了改进的人工免疫遗传算法(Artificial Immune Genetic Algorithm)。通过MATLAB实例仿真，表明了该算法能很好的实现对样品的聚类，并克服了遗传算法过早收敛的现象，提高了收敛效率。
*查看完整论文请 +Q: 3 5 1 9 1 6 0 7 2
关键字:聚类分析人工免疫免疫遗传算法
Key Words: Cluster analysis; Artificial Immune ; Immune Genetic Algorithm目 录
1. 绪论 1
1.1 课题的研究背景 1
1.2 本文的研究内容及组织结构 1
2. 聚类分析 3
2.1 引言 3
2.2 聚类分析算法原理 3
2.3 基于层次聚类算法的图形识别聚类 4
2.3.1 理论概述 4
2.3.2 最短距离法 5
3. 人工免疫算法 8
3.1 人工免疫系统 8
3.1.1 基本原理 8
3.1.2 人工免疫系统的应用 8
3.1.3 人工免疫与生物免疫的对应关系 8
3.2 遗传算法 9
3.2.1 理论概述 9
3.2.2 控制参数的选择 9
3.2.3 遗传算子 10
3.2.4 基本流程 11
3.2.5 遗传算法聚类流程 11
3.2.6 遗传算法聚类分析效果图 12
3.3 人工免疫遗传算法 13
3.3.1 理论概述 13
3.3.2 人工免疫遗传算法构成要素 14
3.3.3 基本流程 14
3.3.4 遗传算法与人工免疫遗传算法区别 15
4. 聚类分析仿真设计 17
4.1 图形用户界面设计 17
4.2 基于人工免疫遗传算法的聚类分析仿真 18
4.3.1 构造个体 18
4.3.2 聚类过程 19
4.4 对比仿真试验 24
5. 总结及展望 27
5.1 工作总结 27
5.2 今后展望 27
参考文献 28
致谢 29
1. 绪论
1.1 课题的研究背景
聚类分析( Clustering Analysis)属于一种没有监督的模式识别方式，它将各种样品分组成为多个类，能分到同一个类中的样品具有较高的相似度，而分到不同类中的样品差别较大。聚类分析在模式识别、图像分割、目标检测、特征提取等方面都有着广泛的应用。
遗传算法(GA)是一种模拟生物进化机理的优化算法，体现了进化理论中的“适者生存”法则。由美国人Holland教授等提出[1]，该算法具有很强的并行搜索能力,但是容易出现“退化”和局部搜索能力不足等问题。要设计有效的遗传算法应当使用特定问题领域知识，如果直接运用遗传算法来解决聚类问题，聚类的结果不能保证。目前，已经有许多人对遗传算法做了改进例如[2]：设计一种混合遗传算法，以K均值算子代替交叉算子，可以达到全局最优点；采取聚类中心的浮点编码方式，设计了交叉、变异算子，从而提高了搜索效率。由于遗传算法原有的缺点，在进化的过程中出现“退化”的可能性是不可避免，导致算法后期的波动现象以及得到最优解较晚和聚类准确率不高等问题。
近年来，由生物免疫理论启发的人工免疫系统（Artificial Immune System）的研究成为热点。AIS在识别及优化问题上所具有的优良的智能搜寻能力，这让人工免疫的思想在很多应用领域受到广泛应用，使其与现有的人工智能算法相结合，提高了人工智能算法的整体性能。人工免疫遗传算法是一种混合算法，它将人工免疫算法引入到遗传算法中进行聚类分析。人工免疫遗传算法增加了疫苗接种算子、免疫检测算子、免疫平衡算子等功能，在个体更新、选择算子、维持多样性上相比遗传算法有很大改进，成功克服了遗传算法聚类中的原有缺点。
1.2 本文的研究内容及组织结构
本文主要研究的是基于MATLAB的人工免疫算法在聚类分析中的运用。具体的工作内容包括聚类分析，遗传算法，人工免疫遗传算法，人工免疫遗传算法在聚类分析中的运用以及程序的编写和仿真调试。
第一章，简要阐述本文的研究背景和本文的研究内容及组织结构。
第二章，详细分析聚类思想，先介绍聚类方法的基本原理，然后具体介绍一种常用聚类方法即最短距离聚类方法的图形聚类，使用MATLAT仿真。
第三章，首先简要阐述了人工免疫系统的基本原理。然后详细阐述遗传算法和人工免疫算法的基本概念、构成要素以及流程，总结了这两种算法的主要区别。
第四章，运用人工免疫算法设计MATLAB聚类分析仿真。通过多次仿真得到遗传算法和免疫遗传算法聚类分析最优解出现代数。通过比较证明本文的免疫遗传算法聚类效率高于遗传算法聚类。
第五章，对所从事的研究工作进行总结，指出研究完成的任务，并指出所工作尚存在的不足，展望下一步工作的研究方向。
2. 聚类分析
2.1 引言
聚类分析（CA）是指事先并不知道一批样品中的每一个样品的所属类别或其他先验知识，而依据样品的特征进行分类。使用一种适应度测量的方法，把特征相同或相近的样品归为一类，实现聚类划分。聚类算法可以分成下列几类: 层次聚类算法、动态聚类算法、基于密度的聚类算法、基于遗传的聚类算法、基于网格的聚类算法和基于模型的聚类算法。
2.2 聚类分析算法原理
（1）定义
给出一个向量集合 ，假设每个样品 含有m个特征，利用向量方式来表征样品： 。聚类分析就是由样品的特征来分析样品之间的适应程度，然后根据某种聚类方法来得到聚类结果。聚类结果需要满足下列条件： ； ，结果用 表示。一般情况下聚类算法会包含下列四个部分：样品的特征提取；计算适应度；分类；显示聚类结果。
（2）特征提取
模式识别的核心之一就是样品的特征提取。样品输入后根据识别方法的具体要求提取样品特征，以此为识别的依据。一般来说，选择的特征既要能够满足代表这个样品，又要求特征的数量尽可能少，这样就能够比较有效地分类，另外计算量也较小。因为特征提取的好坏会直接影响识别和分类效果，从而影响识别率，所以特征选择是模式识别的关键。但是，目前还没有一个全效的提取特征的方法，因此针对不同的识别问题可以使用不同的方法。
一种常用提取特征的方法是记录每个特征内的黑像素点个数。将一副图像分为n×n的网格，计录每个网格内黑像素点的个数，这样就得到了一个用数值表示的特征值。
（3）计算适应度
样品与样品之间适应度问题是模式识别中最基本的研究领域。计算样品适应度的方法有：欧氏距离、夹角余弦距离、二值夹角余弦距离、Tanimoto测度等如表2-1所示。假设有图像中两个样品 和 的特征向量分别为 ， 。
表2-1 样品间的距离算法
距离函数也称适应度函数，距离的概念并不仅仅指单纯的空间上的距离，还包括形态、语义、状态、密度、时间等产生的差距，用于衡量模式之间的相似程度。进行聚类分析时不同的应用场合需要使用不同的距离函数，现在还没有一个可以通用的距离函数。
（4）分类
通过聚类的方法先确定各类的代表点，然后计算各个样本和每个代表点之间的距离，把与代表点距离相近的样品归入一类。
2.3 基于层次聚类算法的图形识别聚类
2.3.1 理论概述
层次聚类算法有两种分别是合并算法与分裂算法。合并算法是指先将每个样品自成一类，然后根据距离不同合并距离小于阈值的类，例如最短距离法。分裂算法原理相反，它是先将每个样品归为一类，然后根据类间距离的不同，把距离大于阈值的类分裂成不同类，例如最长距离法。
摘要
当前对人工免疫算法（Artificial Immune Algorithm）的研究已经成为人工智能的一个重要研究领域。它是受生物免疫系统启发，在原有进化算法理论框架内引入免疫机制，而形成的一种新的进化理论。突出地体现了现代科学发展的多层次、多学科和多领域的相互渗透、相互交叉和相互促进的特点，为工程实践人员提供了许多富有成效的技术和方法。本文首先分析了聚类思想,并通过MATLAB仿真介绍常用的聚类算法。然后介绍遗传算法聚类分析，再将人工免疫原理引入到遗传算法(Genetic Algorithm) 中，并应用于聚类分析, 提出了改进的人工免疫遗传算法(Artificial Immune Genetic Algorithm)。通过MATLAB实例仿真，表明了该算法能很好的实现对样品的聚类，并克服了遗传算法过早收敛的现象，提高了收敛效率。
*查看完整论文请 +Q: 3 5 1 9 1 6 0 7 2
关键字:聚类分析人工免疫免疫遗传算法
Key Words: Cluster analysis; Artificial Immune ; Immune Genetic Algorithm目 录
1. 绪论 1
1.1 课题的研究背景 1
1.2 本文的研究内容及组织结构 1
2. 聚类分析 3
2.1 引言 3
2.2 聚类分析算法原理 3
2.3 基于层次聚类算法的图形识别聚类 4
2.3.1 理论概述 4
2.3.2 最短距离法 5
3. 人工免疫算法 8
3.1 人工免疫系统 8
3.1.1 基本原理 8
3.1.2 人工免疫系统的应用 8
3.1.3 人工免疫与生物免疫的对应关系 8
3.2 遗传算法 9
3.2.1 理论概述 9
3.2.2 控制参数的选择 9
3.2.3 遗传算子 10
3.2.4 基本流程 11
3.2.5 遗传算法聚类流程 11
3.2.6 遗传算法聚类分析效果图 12
3.3 人工免疫遗传算法 13
3.3.1 理论概述 13
3.3.2 人工免疫遗传算法构成要素 14
3.3.3 基本流程 14
3.3.4 遗传算法与人工免疫遗传算法区别 15
4. 聚类分析仿真设计 17
4.1 图形用户界面设计 17
4.2 基于人工免疫遗传算法的聚类分析仿真 18
4.3.1 构造个体 18
4.3.2 聚类过程 19
4.4 对比仿真试验 24
5. 总结及展望 27
5.1 工作总结 27
5.2 今后展望 27
参考文献 28
致谢 29
1. 绪论
1.1 课题的研究背景
聚类分析( Clustering Analysis)属于一种没有监督的模式识别方式，它将各种样品分组成为多个类，能分到同一个类中的样品具有较高的相似度，而分到不同类中的样品差别较大。聚类分析在模式识别、图像分割、目标检测、特征提取等方面都有着广泛的应用。
遗传算法(GA)是一种模拟生物进化机理的优化算法，体现了进化理论中的“适者生存”法则。由美国人Holland教授等提出[1]，该算法具有很强的并行搜索能力,但是容易出现“退化”和局部搜索能力不足等问题。要设计有效的遗传算法应当使用特定问题领域知识，如果直接运用遗传算法来解决聚类问题，聚类的结果不能保证。目前，已经有许多人对遗传算法做了改进例如[2]：设计一种混合遗传算法，以K均值算子代替交叉算子，可以达到全局最优点；采取聚类中心的浮点编码方式，设计了交叉、变异算子，从而提高了搜索效率。由于遗传算法原有的缺点，在进化的过程中出现“退化”的可能性是不可避免，导致算法后期的波动现象以及得到最优解较晚和聚类准确率不高等问题。
近年来，由生物免疫理论启发的人工免疫系统（Artificial Immune System）的研究成为热点。AIS在识别及优化问题上所具有的优良的智能搜寻能力，这让人工免疫的思想在很多应用领域受到广泛应用，使其与现有的人工智能算法相结合，提高了人工智能算法的整体性能。人工免疫遗传算法是一种混合算法，它将人工免疫算法引入到遗传算法中进行聚类分析。人工免疫遗传算法增加了疫苗接种算子、免疫检测算子、免疫平衡算子等功能，在个体更新、选择算子、维持多样性上相比遗传算法有很大改进，成功克服了遗传算法聚类中的原有缺点。
1.2 本文的研究内容及组织结构
本文主要研究的是基于MATLAB的人工免疫算法在聚类分析中的运用。具体的工作内容包括聚类分析，遗传算法，人工免疫遗传算法，人工免疫遗传算法在聚类分析中的运用以及程序的编写和仿真调试。
第一章，简要阐述本文的研究背景和本文的研究内容及组织结构。
第二章，详细分析聚类思想，先介绍聚类方法的基本原理，然后具体介绍一种常用聚类方法即最短距离聚类方法的图形聚类，使用MATLAT仿真。
第三章，首先简要阐述了人工免疫系统的基本原理。然后详细阐述遗传算法和人工免疫算法的基本概念、构成要素以及流程，总结了这两种算法的主要区别。
第四章，运用人工免疫算法设计MATLAB聚类分析仿真。通过多次仿真得到遗传算法和免疫遗传算法聚类分析最优解出现代数。通过比较证明本文的免疫遗传算法聚类效率高于遗传算法聚类。
第五章，对所从事的研究工作进行总结，指出研究完成的任务，并指出所工作尚存在的不足，展望下一步工作的研究方向。
2. 聚类分析
2.1 引言
聚类分析（CA）是指事先并不知道一批样品中的每一个样品的所属类别或其他先验知识，而依据样品的特征进行分类。使用一种适应度测量的方法，把特征相同或相近的样品归为一类，实现聚类划分。聚类算法可以分成下列几类: 层次聚类算法、动态聚类算法、基于密度的聚类算法、基于遗传的聚类算法、基于网格的聚类算法和基于模型的聚类算法。
2.2 聚类分析算法原理
（1）定义
给出一个向量集合 ，假设每个样品 含有m个特征，利用向量方式来表征样品： 。聚类分析就是由样品的特征来分析样品之间的适应程度，然后根据某种聚类方法来得到聚类结果。聚类结果需要满足下列条件： ； ，结果用 表示。一般情况下聚类算法会包含下列四个部分：样品的特征提取；计算适应度；分类；显示聚类结果。
（2）特征提取
模式识别的核心之一就是样品的特征提取。样品输入后根据识别方法的具体要求提取样品特征，以此为识别的依据。一般来说，选择的特征既要能够满足代表这个样品，又要求特征的数量尽可能少，这样就能够比较有效地分类，另外计算量也较小。因为特征提取的好坏会直接影响识别和分类效果，从而影响识别率，所以特征选择是模式识别的关键。但是，目前还没有一个全效的提取特征的方法，因此针对不同的识别问题可以使用不同的方法。
一种常用提取特征的方法是记录每个特征内的黑像素点个数。将一副图像分为n×n的网格，计录每个网格内黑像素点的个数，这样就得到了一个用数值表示的特征值。
（3）计算适应度
样品与样品之间适应度问题是模式识别中最基本的研究领域。计算样品适应度的方法有：欧氏距离、夹角余弦距离、二值夹角余弦距离、Tanimoto测度等如表2-1所示。假设有图像中两个样品 和 的特征向量分别为 ， 。
表2-1 样品间的距离算法
距离函数也称适应度函数，距离的概念并不仅仅指单纯的空间上的距离，还包括形态、语义、状态、密度、时间等产生的差距，用于衡量模式之间的相似程度。进行聚类分析时不同的应用场合需要使用不同的距离函数，现在还没有一个可以通用的距离函数。
（4）分类
通过聚类的方法先确定各类的代表点，然后计算各个样本和每个代表点之间的距离，把与代表点距离相近的样品归入一类。
2.3 基于层次聚类算法的图形识别聚类
2.3.1 理论概述
层次聚类算法有两种分别是合并算法与分裂算法。合并算法是指先将每个样品自成一类，然后根据距离不同合并距离小于阈值的类，例如最短距离法。分裂算法原理相反，它是先将每个样品归为一类，然后根据类间距离的不同，把距离大于阈值的类分裂成不同类，例如最长距离法。
版权保护: 本文由 hbsrm.com编辑，转载请保留链接: www.hbsrm.com/jxgc/zdh/4257.html
