《第30章基于PSO的聚类算法》由会员分享，可在线阅读，更多相关《第30章基于PSO的聚类算法（22页珍藏版）》请在金锄头文库上搜索。
1、 第三十章第三十章MATLAB优化算法案例分析与应用优化算法案例分析与应用第第30章章 基于基于PSO的聚类算法的聚类算法攀妥字翅越早愚摹炕颠煮裙讹敬鹏嫉捶与哇浊唬炳揣级浑厌免侈盐怜跪盯第30章基于PSO的聚类算法第30章基于PSO的聚类算法 第三十章第三十章MATLAB优化算法案例分析与应用优化算法案例分析与应用30.1 聚类分析法聚类分析法 聚类分析指将物理或抽象对象的集合分组成为由类似的对象组成的多个类的分析过程。聚类分析的目标就是在相似的基础上收集数据来分类。聚类源于很多领域，包括数学，计算机科学，统计学，生物学和经济学。在不同的应用领域，很多聚类技术都得到了发展，这些技术方法被用作描
2、述数据，衡量不同数据源间的相似性，以及把数据源分类到不同的簇中。 聚类分析作为数据挖掘中的一个很重要的研究领域，有着许多不同的聚类算法。传统的聚类算法一般分为五类：层次方法、划分方法、基于网格方法、基于密度方法和基于模型方法。走奢武虹烩岿眼定沫枣避倘抖指凤非遥捌拎轮弄侩籍写搅色秩桌壮糜微铺第30章基于PSO的聚类算法第30章基于PSO的聚类算法 第三十章第三十章MATLAB优化算法案例分析与应用优化算法案例分析与应用30.1 聚类分析法聚类分析法 传统的聚类算法已经足够成熟，能够解决低维数据的聚类问题。但因为实际应用中数据的复杂性，处理许多问题时，现有的算法容易失效，特别是对高维数据和大型数据
3、等情况。因此传统聚类在高维数据集中进行聚类时，主要存在以下两个问题： （1）高维数据集中大量存在无关的属性使得在所有维中存在簇的可能度几乎为零； （2）高维空间中数据较低维空间中数据分布要稀疏，其中数据间距离几乎相等是普遍现象，而传统聚类方法是基于距离进行聚类的，因此传统聚类方法在高维空间数据分析较吃力。 基于人工免疫粒子群的聚类算法，这将使得聚类算法具有很好的全局收敛性，不仅能够有效地克服传统聚类算法对初始值敏感和易陷入局部极小值的问题，并且使得算法具有更快的收敛速度。柠踌如娠死根锅储犁责法率厕蓝拂行霹涣并秦遂鳞袱触惩耽淬喝能旺既社第30章基于PSO的聚类算法第30章基于PSO的聚类算法 第
4、三十章第三十章MATLAB优化算法案例分析与应用优化算法案例分析与应用30.2 PSO优化算法分析优化算法分析 粒子群优化算法（Particle Swarm Optimization，PSO）又翻译为粒子群算法、微粒群算法、或微粒群优化算法。是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法。通常认为它是群集智能（Swarm intelligence, SI）的一种。它可以被纳入多主体优化系统（Multiagent Optimization System, MAOS）。个体极值为全局极值为速度更新为位置更新为陪考设峙犊蹬曙梗拍靛想筐黍讶狠汉多承深览逆译企梧厘历击宙颊乳砸葱第30章
5、基于PSO的聚类算法第30章基于PSO的聚类算法 第三十章第三十章MATLAB优化算法案例分析与应用优化算法案例分析与应用30.2 PSO优化算法分析优化算法分析PSO算法执行步骤如下：Step1：初始化一个规模为m的粒子群，设定初始位置和速度。Step2：计算每个粒子的适应值。Step3：对每个粒子将其适应值和其经历过的最好位置的适应值进行比较，若较好，则将其作为当前的最好位置。Step4：对每个粒子将其适应值和全局经历过的最好位置的适应值进行比较，若较好，则将其作为当前的全局最好位置。Step5：对粒子的速度和位置进行更新。Step6：如果满足终止条件，则输出解；否则返回Step2。搀更弯
6、夸蛛弗召浑嘲霸咕追塘辅篙俐嚷歪孰蔗解孜迢锈侯髓闹诲狱浩慕目第30章基于PSO的聚类算法第30章基于PSO的聚类算法 第三十章第三十章MATLAB优化算法案例分析与应用优化算法案例分析与应用30.3 人工免疫特性分析人工免疫特性分析30.3.1 生物免疫系统及其特性生物免疫系统及其特性 多样性：免疫系统的重要特征之一，研究表明，通过细胞分裂分化作用，抗体的可变区与不变区基因重组，体细胞超变异等方式，免疫系统可产生大量的不同抗体来抵御各种抗原，从而使免疫抗体库具有丰富的多样性。 在使用人工免疫系统来求最优解的问题时，一般用抗原表示满足约束条件的最优解，抗体表示候选解，用抗体和抗原之间的亲和力来表示
7、候选解和最优解的接近程度，也就是在约束条件下候选解对于目标函数的满足程度；而抗体和抗体之间的亲和力可反映出不同候选解之间的差异，即抗体的多样性。从而防止算法陷入局部最优。 通过比较抗体与抗原间的亲和力来选择有效抗体更好地体现了“优胜劣汰”的原则，特别是当待选抗体之间相差不明显时，“优胜劣汰”的效果更能得到体现，搜索效率会更高.而免疫记忆的引入能够有效地抑制进化算法优化过程中出现的退化现象，提高进化算法的性能。免疫接种即是免疫记忆引入的一个方面，有选择、有目的地利用待求问题中的一些特征信息或知识，提取“疫苗”并接种“疫苗”，从而达到引进的目的。镜林屹到估赣酵澎判心诌氓场厢乓叮愤迪枚燕四谋炬廊撂尧
8、铆俱团抿兴香第30章基于PSO的聚类算法第30章基于PSO的聚类算法 第三十章第三十章MATLAB优化算法案例分析与应用优化算法案例分析与应用30.3 人工免疫特性分析人工免疫特性分析30.3.2 种群分布熵种群分布熵粒子群进化寻优的过程，实际上是不确定性不断减少的过程。算法的早熟收敛，可理解为熵的过度损失。种群分布熵一般用来表达搜索空间中各区域粒子的分布情况，反映种群中不同类型个体的散乱程度。但实际计算过程中，算法无法得知某代种群内个体的不同类属情况，因此种群每进化一代，算法都必须重新对种群内的个体做聚类分析，这样才能得到新的种群分布熵，这样计算量较大。而过早收敛现象的发生，一般是因为那些粒
9、子适应度暂时最优的个体相互趋同，而那些适应度较小的个体依然是分散的，这时的种群分布熵无法及时下降，而等到种群分布熵明显下降时，种群却已经严重地早熟收敛。这说明从进化计算的角度来看，分布熵这一指标在实际运用过程中使用率较低。侗具饯季十素到死饶害税扭忌惟望叶琼安垮撑翟铰灵粕摊荷镐薄煽决欢沏第30章基于PSO的聚类算法第30章基于PSO的聚类算法 第三十章第三十章MATLAB优化算法案例分析与应用优化算法案例分析与应用30.3 人工免疫特性分析人工免疫特性分析30.3.3 平均粒距平均粒距平均粒距指种群中各个个体相互间的分散程度，平均粒距描述种群的多样性的方法存在许多不足之处。首先是计算量大，种群每
10、代进化，都要计算整个种群各个个体分布方差，在中却规模和粒子维度较大是，计算量明显过大；再者是方差仅能达到反映种群个体分布离散程度的目的，并不能有效刻划出种群的多样性。30.3.4 精英均值偏差精英均值偏差 精英均值偏差使用适应度分布离散程度来表现种群内个体分布的多样性程度。研究分析粒子群的进化过程中发现，种群过早收敛的主要表现是:种群存在迅速向适应度暂时最优个体趋近的趋势，因此导致寻优过程十分缓慢，从而降低搜索效率。因此，一般通过观察该种群当前适应度暂时最大的那部分个体是否重复或者相互趋同来判断一个种群会否发生过早收敛。惶捉晃烛捡原斜怯依孔躺绑息匹景戴周滁胃档放盗萧诽惋铲瑶帮莲呕睁沫第30章基
11、于PSO的聚类算法第30章基于PSO的聚类算法 第三十章第三十章MATLAB优化算法案例分析与应用优化算法案例分析与应用30.4 基于人工免疫粒子群优化算法基于人工免疫粒子群优化算法 多样性和免疫记忆是免疫系统的重要特性，把生物免疫系统中的多样性和免疫记忆特性引入到人工免疫系统粒子群优化算法中，可提高算法的全局搜索能力使其不易陷入局部最优。抗体（粒子）的浓度越大，则选择的概率越小，反之，则选择概率越大。这样，不仅保留了高适应度个体，也进一步确保了抗体（粒子）的多样性，达到避免早熟收敛的目的。图30-1 免疫细胞等位基因的信息熵汀恫驰乌钒烤监初雪接窗颤煞呸恬换誉入妄惊彩袜柔砰避琉屈白詹岂唱永第3
12、0章基于PSO的聚类算法第30章基于PSO的聚类算法 第三十章第三十章MATLAB优化算法案例分析与应用优化算法案例分析与应用30.4 基于人工免疫粒子群优化算法基于人工免疫粒子群优化算法衡量个体之间差异性用平均信息熵第i个符号出现在基因座j上的概率相似度群体总相似度营辆臣娥投锣琅均惕扫朗琐症矣列作徘舷旱随仑绰牧队汹独马允酪溅淋蓝第30章基于PSO的聚类算法第30章基于PSO的聚类算法 第三十章第三十章MATLAB优化算法案例分析与应用优化算法案例分析与应用30.4 基于人工免疫粒子群优化算法基于人工免疫粒子群优化算法抗体浓度：指相似抗体占总群体的比重，即：聚合适应度：对于最大优化问题，一般k
13、取负数。当进行选择操作时，抗体被选中的概率正比于聚合适应度。即当浓度一定时，适应度越大，被选择的概率越大；而当适应度一定时，抗体浓度越高，被选择的概率越小。瓜怠球宋掺阮祭扣铱添竭缅寐冲榆硷遏耽腐怔赃贺藩揣典藩在又捌姆消壬第30章基于PSO的聚类算法第30章基于PSO的聚类算法 第三十章第三十章MATLAB优化算法案例分析与应用优化算法案例分析与应用30.4 基于人工免疫粒子群优化算法基于人工免疫粒子群优化算法30.4.1 PSO在函数极值求解在函数极值求解图30-2 PSO 2D函数最小值图图30-3 PSO 3D曲面最小值寻优脐噬改楞胯俞况排耿潜恋哉罢邦摄耳诧叭菱溢枷摊统订噎拌旧桌药垒局侧第
14、30章基于PSO的聚类算法第30章基于PSO的聚类算法 第三十章第三十章MATLAB优化算法案例分析与应用优化算法案例分析与应用30.4 基于人工免疫粒子群优化算法基于人工免疫粒子群优化算法30.4.2 粒子群聚类算法理论分析粒子群聚类算法理论分析聚类问题就是要找到一个划分来使得类内离散度总和达到最小。当聚类中心确定时，聚类的划分可由最近邻法则决定。表示样品到对应聚类中心距离，聚类准则函数即为各类样品到对应聚类中心距离的总和。区戎荧沼娥寅描杨亏中饲擒艳怕坏挎坤齐琴风吠妊匹耀贺核戎妆近头曝葫第30章基于PSO的聚类算法第30章基于PSO的聚类算法 第三十章第三十章MATLAB优化算法案例分析与应
15、用优化算法案例分析与应用30.4 基于人工免疫粒子群优化算法基于人工免疫粒子群优化算法30.4.2 粒子群聚类算法理论分析粒子群聚类算法理论分析在粒子群算法求解聚类问题中，每个粒子作为一个可行解组成粒子群（即解集）。根据解的含义不同，通常可以分为两种：一种是以聚类结果为解；一种是以聚类中心集合为解。基于人工免疫粒子群算法讨论的方法采用的是基于聚类中心集合作为粒子对应解，也就是每个粒子的位置是由M个聚类中心组成，M为已知的聚类数目。粒子i结构表示为：Particle(i)=location，velocity，fitness粒子的位置编码结构表示为：Particle(i).location=每个粒
16、子还有一个速度，其编码结构为：Particle(i).velocity=芦盘袱龟痰嫉惜碴鲜斥著雕蹦沦饮坟膏彼钠缘酵团归亢扎镰谜籽纵李禽澡第30章基于PSO的聚类算法第30章基于PSO的聚类算法 第三十章第三十章MATLAB优化算法案例分析与应用优化算法案例分析与应用30.4 基于人工免疫粒子群优化算法基于人工免疫粒子群优化算法粒子群经历的最有位置和适应度更新粒子的速度和位置卞碍摆呵朋较告然装索磨侈诵吗专摄汽狙胃航摔熔肝椒箔亚筑哈闪裂等潦第30章基于PSO的聚类算法第30章基于PSO的聚类算法 第三十章第三十章MATLAB优化算法案例分析与应用优化算法案例分析与应用30.4 基于人工免疫粒子群优
17、化算法基于人工免疫粒子群优化算法基于人工免疫的粒子群聚类算法，以数字0-9图形数据为例。管辗咯逆张刮撂链抖勿憾握搪尤墟逗券孔譬引醛弥舞票苑仅勺发幽模俯猿第30章基于PSO的聚类算法第30章基于PSO的聚类算法 第三十章第三十章MATLAB优化算法案例分析与应用优化算法案例分析与应用30.4 基于人工免疫粒子群优化算法基于人工免疫粒子群优化算法人工免疫粒子群算法流程图如图所示。耕踊瞅狮倦汞筒宣秀淖抗嗓帜吮秋窝都倦雍长枪篷饯衡圃感评销金笺锻糜第30章基于PSO的聚类算法第30章基于PSO的聚类算法 第三十章第三十章MATLAB优化算法案例分析与应用优化算法案例分析与应用30.4 基于人工免疫粒子群
18、优化算法基于人工免疫粒子群优化算法30.4.4 种群多样性聚类分析种群多样性聚类分析functionresult=GetDistance(patttern1,pattern2,type)result=0;%globalNwidth;%在本程序中取7,7*7矩阵；Nwidth=7;%type选择变量switch(type)case1%欧氏距离result=sum(patttern1.feature(:)-pattern2.feature(:).2);result=sqrt(result);case2%夹角余弦a=0;b1=0;b2=0;fori=1:Nwidthforj=1:Nwidtha=a+
19、patttern1.feature(i,j)*pattern2.feanture(i,j);颁咨选秤任赚涕索逮龋裙诊闷陇峙耀牺眼岔艺箩萤洁怪镀前彝甄萎稚匹堑第30章基于PSO的聚类算法第30章基于PSO的聚类算法 第三十章第三十章MATLAB优化算法案例分析与应用优化算法案例分析与应用30.4 基于人工免疫粒子群优化算法基于人工免疫粒子群优化算法30.4.4 种群多样性聚类分析种群多样性聚类分析a=a+patttern1.feature(i,j)*pattern2.feanture(i,j);b1=b1+patttern1.feature(i,j)*pattern1.feature(i,j);
20、b2=b2+pattern2.feature(i,j)*pattern2.feature(i,j);endendif(b1*b2=0)result=1-a/sqrt(b1*b2);elseresult=-1;endend若惧乍壹单气掘庙遏诱香辜波吟咽扒瘁滤枷扫偶表誉况僧哼盯丽骚署根骡第30章基于PSO的聚类算法第30章基于PSO的聚类算法 第三十章第三十章MATLAB优化算法案例分析与应用优化算法案例分析与应用30.4 基于人工免疫粒子群优化算法基于人工免疫粒子群优化算法图30-6 训练样本悲嗅骏泥红毙噬咖塌衡妨憨褐懈殃邑蚜午躲馁韶缆昨沟寿豆髓你渔李构淹第30章基于PSO的聚类算法第30章基于
21、PSO的聚类算法 第三十章第三十章MATLAB优化算法案例分析与应用优化算法案例分析与应用30.4 基于人工免疫粒子群优化算法基于人工免疫粒子群优化算法%计算粒子适应度fori=1:particleNumtemp=0.01;%计算群体中每个个体的适应度newpop=selection(pop,temp);%选择newpop=crossover(newpop,pc,i);%交叉newpop=mutation(newpop,pm);%变异forj=1:patternNum%译码！temp=decodechrom(newpop,1+(j-1)*length,length);%将newpop每行(个体
22、）每列（每段基因）转化成十进制数temp=temp+GetDistance(m_pattern(j),Particle(i).location(ptDitrib(i,j),disType);endif(temp=0.1)%如果最大值小于设定阀值，停止进化iter=iterNum+1;break;endParticle(i).fitness=1/temp;endw=w_max-iter*(w_max-w_min)/iterNum;%更新权重系数帐士兽誉吝藏睁戳截嵌哨渊学咽烩灸硒涝忽脾摊选跳牺骚棉粟丫胖呢兴替第30章基于PSO的聚类算法第30章基于PSO的聚类算法 第三十章第三十章MATLAB优化算法案例分析与应用优化算法案例分析与应用30.4 基于人工免疫粒子群优化算法基于人工免疫粒子群优化算法图30-7 群体最优适应度曲线监选谜橙敝耐霄眶捡械搞水唱搬傈腹俩耍抽抹拽痊趁袍汾机上炮邹耘牌唉第30章基于PSO的聚类算法第30章基于PSO的聚类算法
