第30章基于PSO的聚类算法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三十章,MATLAB,优化算法案例分析与应用,第,30,章,基于,PSO,的聚类算法,第三十章,MATLAB,优化算法案例分析与应用,30.1,聚类分析,法,聚类分析指将物理或抽象对象的集合分组成为由类似的对象组成的多个类的分析过程。聚类分析的目标就是在相似的基础上收集数据来分类。聚类源于很多领域，包括数学，计算机科学，统计学，生物学和经济学。在不同的应用领域，很多聚类技术都得到了发展，这些技术方法被用作描述数据，衡量不同数据源间的相似性，以及把数据源分类到不同的簇中。,聚类分析作为数据挖掘中的一个很重要的研究领域，有着许多不同的聚类算法。传统的聚类算法一般分为五类：层次方法、划分方法、基于网格方法、基于密度方法和基于模型方法。,第三十章,MATLAB,优化算法案例分析与应用,30.1,聚类分析,法,传统的聚类算法已经足够成熟，能够解决低维数据的聚类问题。但因为实际应用中数据的复杂性，处理许多问题时，现有的算法容易失效，特别是对高维数据和大型数据等情况。因此传统聚类在高维数据集中进行聚类时，主要存在以下两个问题：,（,1,）高维数据集中大量存在无关的属性使得在所有维中存在簇的可能度几乎为零；,（,2,）高维空间中数据较低维空间中数据分布要稀疏，其中数据间距离几乎相等是普遍现象，而传统聚类方法是基于距离进行聚类的，因此传统聚类方法在高维空间数据分析较吃力。,基于人工免疫粒子群的聚类算法，这将使得聚类算法具有很好的全局收敛性，不仅能够有效地克服传统聚类算法对初始值敏感和易陷入局部极小值的问题，并且使得算法具有更快的收敛速度。,第三十章,MATLAB,优化算法案例分析与应用,30.2 PSO,优化算法分析,粒子群优化算法（,Particle Swarm Optimization,，,PSO,）又翻译为粒子群算法、微粒群算法、或微粒群优化算法。是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法。通常认为它是群集智能（,Swarm intelligence,SI,）的一种。它可以被纳入多主体优化系统（,Multiagent Optimization System,MAOS,）。,个体极值为,全局极值为,速度更新为,位置更新为,第三十章,MATLAB,优化算法案例分析与应用,30.2 PSO,优化算法分析,PSO算法执行步骤如下：,Step1：初始化一个规模为,m,的粒子群，设定初始位置和速度。,Step2：计算每个粒子的适应值。,Step3：对每个粒子将其适应值和其经历过的最好位置 的适应值进行比较，若较好，则将其作为当前的最好位置。,Step4：对每个粒子将其适应值和全局经历过的最好位置 的适应值进行比较，若较好，则将其作为当前的全局最好位置。,Step5：对粒子的速度和位置进行更新。,Step6：如果满足终止条件，则输出解；否则返回Step2。,第三十章,MATLAB,优化算法案例分析与应用,30.3,人工免疫特性分析,30.3.1,生物免疫系统及其特性,多样性：免疫系统的重要特征之一，研究表明，通过细胞分裂分化作用，抗体的可变区与不变区基因重组，体细胞超变异等方式，免疫系统可产生大量的不同抗体来抵御各种抗原，从而使免疫抗体库具有丰富的多样性。,在使用人工免疫系统来求最优解的问题时，一般用抗原表示满足约束条件的最优解，抗体表示候选解，用抗体和抗原之间的亲和力来表示候选解和最优解的接近程度，也就是在约束条件下候选解对于目标函数的满足程度；而抗体和抗体之间的亲和力可反映出不同候选解之间的差异，即抗体的多样性。从而防止算法陷入局部最优。,通过比较抗体与抗原间的亲和力来选择有效抗体更好地体现了“优胜劣汰”的原则，特别是当待选抗体之间相差不明显时，“优胜劣汰”的效果更能得到体现，搜索效率会更高,.,而免疫记忆的引入能够有效地抑制进化算法优化过程中出现的退化现象，提高进化算法的性能。免疫接种即是免疫记忆引入的一个方面，有选择、有目的地利用待求问题中的一些特征信息或知识，提取“疫苗”并接种“疫苗”，从而达到引进的目的。,第三十章,MATLAB,优化算法案例分析与应用,30.3,人工免疫特性分析,30.3.2 种群分布熵,粒子群进化寻优的过程，实际上是不确定性不断减少的过程。算法的早熟收敛，可理解为熵的过度损失。,种群分布熵一般用来表达搜索空间中各区域粒子的分布情况，反映种群中不同类型个体的散乱程度。但实际计算过程中，算法无法得知某代种群内个体的不同类属情况，因此种群每进化一代，算法都必须重新对种群内的个体做聚类分析，这样才能得到新的种群分布熵，这样计算量较大。,而过早收敛现象的发生，一般是因为那些粒子适应度暂时最优的个体相互趋同，而那些适应度较小的个体依然是分散的，这时的种群分布熵无法及时下降，而等到种群分布熵明显下降时，种群却已经严重地早熟收敛。这说明从进化计算的角度来看，分布熵这一指标在实际运用过程中使用率较低。,第三十章,MATLAB,优化算法案例分析与应用,30.3,人工免疫特性分析,30.3.3 平均粒距,平均粒距指种群中各个个体相互间的分散程度，平均粒距描述种群的多样性的方法存在许多不足之处。首先是计算量大，种群每代进化，都要计算整个种群各个个体分布方差，在中却规模和粒子维度较大是，计算量明显过大；再者是方差仅能达到反映种群个体分布离散程度的目的，并不能有效刻划出种群的多样性。,30.3.4,精英均值偏差,精英均值偏差使用适应度分布离散程度来表现种群内个体分布的多样性程度。研究分析粒子群的进化过程中发现，种群过早收敛的主要表现是,:,种群存在迅速向适应度暂时最优个体趋近的趋势，因此导致寻优过程十分缓慢，从而降低搜索效率。因此，一般通过观察该种群当前适应度暂时最大的那部分个体是否重复或者相互趋同来判断一个种群会否发生过早收敛,。,第三十章,MATLAB,优化算法案例分析与应用,30.4,基于人工免疫粒子群优化算法,多样性和免疫记忆是免疫系统的重要特性，把生物免疫系统中的多样性和免疫记忆特性引入到人工免疫系统粒子群优化算法中，可提高算法的全局搜索能力使其不易陷入局部最优。抗体（粒子）的浓度越大，则选择的概率越小，反之，则选择概率越大。这样，不仅保留了高适应度个体，也进一步确保了抗体（粒子）的多样性，达到避免早熟收敛的目的。,图,30-1,免疫细胞等位基因的信息熵,第三十章,MATLAB,优化算法案例分析与应用,30.4,基于人工免疫粒子群优化算法,衡量个体之间差异性用平均信息熵,第,i,个符号出现在基因座,j,上的概率,相似度,群体总相似度,第三十章,MATLAB,优化算法案例分析与应用,30.4,基于人工免疫粒子群优化算法,抗体浓度：指相似抗体占总群体的比重，即：,聚合适应度：,对于最大优化问题，一般,k,取负数。当进行选择操作时，抗体被选中的概率正比于聚合适应度。即当浓度一定时，适应度越大，被选择的概率越大；而当适应度一定时，抗体浓度越高，被选择的概率越小。,第三十章,MATLAB,优化算法案例分析与应用,30.4,基于人工免疫粒子群优化算法,30.4.1 PSO,在函数极值求解,图,30-2 PSO 2D,函数最小值图,图,30-3 PSO 3D,曲面最小值寻优,第三十章,MATLAB,优化算法案例分析与应用,30.4,基于人工免疫粒子群优化算法,30.4.2,粒子群聚类算法理论分析,聚类问题就是要找到一个划分 来使得类内离散度总和达到最小。,当聚类中心确定时，聚类的划分可由最近邻法则决定。,表示样品到对应聚类中心距离，聚类准则函数 即为各类样品到对应聚类中心距离的总和。,第三十章,MATLAB,优化算法案例分析与应用,30.4,基于人工免疫粒子群优化算法,30.4.2,粒子群聚类算法理论分析,在粒子群算法求解聚类问题中，每个粒子作为一个可行解组成粒子群（即解集）。根据解的含义不同，通常可以分为两种：一种是以聚类结果为解；一种是以聚类中心集合为解。基于人工免疫粒子群算法讨论的方法采用的是基于聚类中心集合作为粒子对应解，也就是每个粒子的位置是由,M,个聚类中心组成，,M,为已知的聚类数目。,粒子,i,结构,表示为：,Particle(i)=location,，,velocity,，,fitness,粒子的位置编码结构表示为：,Particle(i).location=,每个粒子还有一个速度，其编码结构为：,Particle(i).velocity=,第三十章,MATLAB,优化算法案例分析与应用,30.4,基于人工免疫粒子群优化算法,粒子群经历的最有位置和适应度,更新粒子的速度和位置,第三十章,MATLAB,优化算法案例分析与应用,30.4,基于人工免疫粒子群优化算法,基于人工免疫的粒子群聚类算法，以数字,0-9,图形数据为例。,第三十章,MATLAB,优化算法案例分析与应用,30.4,基于人工免疫粒子群优化算法,人工免疫粒子群算法流程图如图所示。,第三十章,MATLAB,优化算法案例分析与应用,30.4,基于人工免疫粒子群优化算法,30.4.4 种群多样性聚类分析,function result=GetDistance(patttern1,pattern2,type),result=0;,%global Nwidth;%,在本程序中取,7,7*7,矩阵；,Nwidth=7;,%type,选择变量,switch(type),case 1%,欧氏距离,result=sum(patttern1.feature(:)-pattern2.feature(:).2);,result=sqrt(result);,case 2%,夹角余弦,a=0;,b1=0;,b2=0;,for i=1:Nwidth,for j=1:Nwidth,a=a+patttern1.feature(i,j)*pattern2.feanture(i,j);,第三十章,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);,b2=b2+pattern2.feature(i,j)*pattern2.feature(i,j);,end,end,if(b1*b2=0),result=1-a/sqrt(b1*b2);,else,result=-1;,end,end,第三十章,MATLAB,优化算法案例分析与应用,30.4,基于人工免疫粒子群优化算法,图,30-6,训练样本,第三十章,MATLAB,优化算法案例分析与应用,30.4,基于人工免疫粒子群优化算法,%,计算粒子适应度,for i=1:particleNum,temp=0.01;%,计算群体中每个个体的适应度,newpop=selection(pop,temp);%,选择,newpop=crossover(newpop,pc,i);%,交叉,newpop=mutation(newpop,pm);%,变异,for j=1:patternNum%,译码！,temp=decodechrom(newpop,1+(j-1)*length,length);%,将,newpop,每行,(,个体）每列（每段基因）转化成十进制数,temp=temp+GetDistance(m_pattern(j),Particle(i).location(ptDitrib(i,j),disType);,end,if(temp=0.1)%,如果最大值小于设定阀值，停止进化,iter=iterNum+1;,break;,end,Particle(i).fitness=1/temp;,end,w=w_max-iter*(w_max-w_min)/iterNum;%,更新权重系数,第三十章,M