在生命科学领域中，人们已经对遗传(Heredity)与免疫(Immunity)等自然现象进行了广泛深入的研究。六十年代Bagley和Rosenberg等先驱在对这些研究成果进行分析与理解的基础上，借鉴其相关内容和知识，特别是遗传学方面的理论与概念，并将其成功应用于工程科学的某些领域，收到了良好的效果。时至八十年代中期，美国Michigan大学的Hollan教授不仅对以前的学者们提出的遗传概念进行了总结与推广，而且给出了简明清晰的算法描述，并由此形成目前一般意义上的遗传算法(GeneticAlgorithm)GA。由于遗传算法较以往传统的搜索算法具有使用方便、鲁棒性强、便于并行处理等特点，因而广泛应用于组合优化、结构设计、人工智能等领域。另一方面，Farmer和Bersini等人也先后在不同时期、不同程度地涉及到了有关免疫的概念。遗传算法是一种具有生成+检测(generate and test)的迭代过程的搜索算法。从理论上分析，迭代过程中，在保留上一代最佳个体的前提下，遗传算法是全局收敛的。然而，在对算法的实施过程中不难发现两个主要遗传算子都是在一定发生概率的条件下，随机地、没有指导地迭代搜索，因此它们在为群体中的个体提供了进化机会的同时，也无可避免地产生了退化的可能。在某些情况下，这种退化现象还相当明显。另外，每一个待求的实际问题都会有自身一些基本的、显而易见的特征信息或知识。然而遗传算法的交叉和变异算子却相对固定，在求解问题时，可变的灵活程度较小。这无疑对算法的通用性是有益的，但却忽视了问题的特征信息对求解问题时的辅助作用，特别是在求解一些复杂问题时，这种忽视所带来的损失往往就比较明显了。实践也表明，仅仅使用遗传算法或者以其为代表的进化算法，在模仿人类智能处理事物的能力方面还远远不足，还必须更加深层次地挖掘与利用人类的智能资源。从这一点讲，学习生物智能、开发、进而利用生物智能是进化算法乃至智能计算的一个永恒的话题。所以，研究者力图将生命科学中的免疫概念引入到工程实践领域，借助其中的有关知识与理论并将其与已有的一些智能算法有机地结合起来，以建立新的进化理论与算法，来提高算法的整体性能。基于这一思想，将免疫概念及其理论应用于遗传算法，在保留原算法优良特性的前提下，力图有选择、有目的地利用待求问题中的一些特征信息或知识来抑制其优化过程中出现的退化现象，这种算法称为免疫算法(ImmuneAlgorithm)IA。下面将会给出算法的具体步骤，证明其全局收敛性，提出免疫疫苗的选择策略和免疫算子的构造方法，理论分析和对TSP问题的仿真结果表明免疫算法不仅是有效的而且也是可行的，并较好地解决了遗传算法中的退化问题。
immune.m
%这是免疫算法。这个算法几乎与遗传算法一样，只是多用了一个免疫函数
%免疫算法是遗传算法的变体，它不用杂交，而是采用注入疫苗的方法。
%疫苗是优秀染色体中的一段基因，把疫苗接种到其它染色体中
%注意：标准遗传算法的一个重要概念是，染色体是可能解的2进制顺序号，由这个序号在可能解的集合(解空间)中找到可能解
%这是免疫算法的主程序，它需要调用的函数如下。
%接种疫苗函数：
%function
inoculateChromosome=immunity(chromosomeGroup,bacterinChromosome,parameter)
%parameter:1,随机制取染色体接种。2，每个染色体都接种。3，每个染色体都接种，但接种的位置是随机的
%这个函数实现对染色体的疫苗接种
%由染色体(可能解的2进制)顺序号找到可能解：
%x=chromosome_x(fatherChromosomeGroup,oneDimensionSet,solutionSum);
%把解代入非线性方程组计算误差函数：functionError=nonLinearSumError1(x);
%判定程是否得解函数：[solution,isTrue]=isSolution(x,funtionError,solutionSumError);
%选择最优染色体函数：
%[bestChromosome,leastFunctionError]=best_worstChromosome(fatherChromosomeGroup,fun ctionError);
%误差比较函数：从两个染色体中，选出误差较小的染色体
%[holdBestChromosome,holdLeastFunctionError]...
% =compareBestChromosome(holdBestChromosome,holdLeastFunctionError,...
% bestChromosome,leastFuntionError)
%为染色体定义概率函数，好的染色体概率高，坏染色体概率低
%p=chromosomeProbability(functionError);
%按概率选择染色体函数：
%slecteChromosomeGroup=selecteChromome(fatherChromosomeGroup,p);
%父代染色体杂交产生子代染色体函数
%sonChrmosomeGroup=crossChromosome(slecteChromosomeGroup,2);
%防止染色体超出解空间的函数
%chromosomeGroup=checkSequence(chromosomeGroup,solutionSum)
%变异函数
?therChromosomeGroup=varianceCh(sonChromosomeGroup,0.8,solutionN);
%通过实验有如下结果：
%1。染色体应当多一些
%2。通过概率选择染色体，在迭代早期会有效选出优秀的染色体，使解的误差迅速降低，%但随着迭代的进行，概率选择也会导致某种染色体在基因池中迅速增加，使染色体趋同，%这就减少了物种的多样性，反而难以逼近解
%3。不用概率选择，仅采用染色体杂交，采用保留优秀染色体，也可以得到解
%4。单纯免疫效果不好，杂交+免疫效果比较好%%%%%%%%%%%%%%%%%%%%%%%%程序开始运行
clear,clc;%清理内存，清屏
circleN=200;%迭代次数
format long
%%%%%%%%%%%%%%%构造可能解的空间，确定染色体的个数、长度
solutionSum=4;leftBoundary=-10;rightBoundary=10;
distance=1;chromosomeSum=500;solutionSumError=0.1;
%solutionSum:非线性方程组的元数(待解变量的个数)；leftBoundary:可能解的左边界；
%rightBoundary:可能解的右边界；distance:可能解的间隔，也是解的精度
%chromosomeSum:染色体的个数；solveSumError:解的误差
oneDimensionSet=leftBoundary:distance:rightBoundary;
%oneDimensionSet:可能解在一个数轴(维)上的集合
oneDimensionSetN=size(oneDimensionSet,2);%返回oneDimensionSet中的元素个数solutionN=oneDimensionSetN^solutionSum;%解空间(解集合)中可能解的总数
binSolutionN=dec2bin(solutionN);%把可能解的总数转换成二进制数
chromosomeLength=size(binSolutionN,2);%由解空间中可能解的总数(二进制数)计算染色体的长度
%%%%%%%%%%%%%%%%程序初始化
%随机生成初始可能解的顺序号,+1是为了防止出现0顺序号
solutionSequence=fix(rand(chromosomeSum,1)*solutionN)+1;
for i=1:chromosomeSum%防止解的顺序号超出解的个数
if solutionSequence(i)>solutionN;
solutionSequence(i)=solutionN;
end
end
%染色体是解集合中的序号,它对应一个可能解
%把解的十进制序号转成二进制序号
fatherChromosomeGroup=dec2bin(solutionSequence,chromosomeLength); holdLeastFunctionError=Inf;%可能解的最小误差的初值
holdBestChromosome=0;%对应最小误差的染色体的初值%%%%%%%%%%%%%%%%%%开始计算
compute=1;
circle=0;
while compute%开始迭代求解
%%%%%%%%%%%%%1:由可能解的序号寻找解本身(关键步骤)
x=chromosome_x(fatherChromosomeGroup,oneDimensionSet,solutionSum); %%%%%%%%%%%%%2：把解代入非线性方程计算误差
functionError=nonLinearSumError1(x);%把解代入方程计算误差
[solution,minError,isTrue]=isSolution(x,functionError,solutionSumError);
%isSolution函数根据误差functionError判定方程是否已经解开，isTrue=1,方程得解。solution 是方程的解
if isTrue==1
'方程得解'
solution
minError
return%结束程序
end
%%%%%%%%%%%%%3：选择最好解对应的最优染色体
[bestChromosome,leastFunctionError]=best_worstChromosome(fatherChromosomeGroup,functi onError);
%%%%%%%%%%%%%4：保留每次迭代产生的最好的染色体
%本次最好解与上次最好解进行比较，如果上次最好解优于本次最好解，保留上次最好解；%反之，保留本次最好解。保留的最好染色体放在holdBestChromosome中[holdBestChromosome,holdLeastFunctionError]...
=compareBestChromosome(holdBestChromosome,holdLeastFunctionError,... bestChromosome,leastFunctionError);
circle=circle+1
%minError
%solution
holdLeastFunctionError
if circle>circleN
return
end
%%%%%%%%%%%%%%5:把保留的最好的染色体holdBestChromosome加入到染色体群中
order=round(rand(1)*chromosomeSum);
if order==0
order=1;
end
fatherChromosomeGroup(order,:)=holdBestChromosome;
functionError(order)=holdLeastFunctionError;
%%%%%%%%%%%%%%%6:为每一条染色体(即可能解的序号)定义一个概率(关键步骤) %%%%%%%%%%%%%%%好的染色体概率高，坏的概率低。依据误差functionError计算概率[p,trueP]=chromosomeProbability(functionError);
if trueP =='Fail'
'可能解严重不适应方程，请重新开始'
return%结束程序
end
%%%%%%%%%%%%%%%7：按照概率筛选染色体(关键步骤)
?=bin2dec(fatherChromosomeGroup)%显示父染色体
%从父染体中选择优秀染色体
%selecteChromosomeGroup=selecteChromosome(fatherChromosomeGroup,p); %%%%%%%%%%%%%%%8：染色体杂交(关键步骤)
%sle=bin2dec(selecteChromosomeGroup)%显示选择出来的解的序号(染色体)
%用概率筛选出的染色体selecteChromosomeGroup进行杂交，产生子代染色体
%sonChromosomeGroup=crossChromosome(selecteChromosomeGroup,2);
%不用概率筛选出的染色体selecteChromosomeGroup进行杂交，而直接用上一代(父代)的sonChromosomeGroup=crossChromosome(fatherChromosomeGroup,2);
%sonChromosomeGroup=immunity(fatherChromosomeGroup,holdBestChromosome,3);
%把疫苗接种到其它染色体中
sonChromosomeGroup=immunity(sonChromosomeGroup,holdBestChromosome,3);
%cro=bin2dec(sonChromosomeGroup)%显示杂交后的子代染色体sonChromosomeGroup=checkSequence(sonChromosomeGroup,solutionN);%检查杂交后的染色体是否越界
%%%%%%%%%%%%%%%9：变异
%不杂交直接变异
?therChromosomeGroup=varianceCh(fatherChromosomeGroup,0.1,solutionN);
%杂交后变异
fatherChromosomeGroup=varianceCh(sonChromosomeGroup,0.5,solutionN); fatherChromosomeGroup=checkSequence(fatherChromosomeGroup,solutionN);%检查变异后的染色体是否越界
end
接种疫苗函数，这是和遗传算法唯一不同的函数，可以用它代替染色体的交叉操作。
%chromosomeGroup:染色体组
?chterinChromosome:疫苗染色体，即最好的染色体。从这个染色体上取疫苗
%parameter:接种疫苗的参数，即用什么方法接种
%inoculateChromosome:接种疫苗后的染色体
function inoculateChromosome=immunity(chromosomeGroup,bacterinChromosome,parameter)
[chromosomeGroupSum,chromosomeLength]=size(chromosomeGroup); [row,bacterinChromosomeLength]=size(bacterinChromosome);
%chromosomeGroupSum:染色体的条数；chromosomeLength：染色体的长度switch parameter
case 1%随机选择染色体进行接种
for i=1:chromosomeGroupSum
%%%%%%%%%%%%从疫苗染色体上定位疫苗
headDot=fix(rand(1)*bacterinChromosomeLength);
%疫苗在染色体上左边的点位
if headDot==0%防止出现0点位
headDot=1;
end
tailDot=fix(rand(1)*bacterinChromosomeLength);
%疫苗在染色体上右边的点位
if tailDot==0%防止出现0点位
tailDot=1;
end
if tailDot>headDot%防止右边的点位大于左边的点位
dot=headDot;
headDot=tailDot;
tailDot=dot;
end
%%%%%%%%%%%%%接种
randChromosomeSequence=round(rand(1)*chromosomeGroupSum);
%随机产生1条染色体的序号，对这条染色体进行接种
if randChromosomeSequence==0%防止产生0序号randChromosomeSequence=1;
end
inoculateChromosome(i,:)...%先把输入染色体传给输出
=chromosomeGroup(randChromosomeSequence,:);
%执行免疫，即从疫苗染色体上取出一段基因做疫苗，再注入到其它染色体中inoculateChromosome(i,headDot:tailDot)...
=bacterinChromosome(1,headDot:tailDot);
end
case 2 %所有染色体挨个接种
for i=1:chromosomeGroupSum
%%%%%%%%%%%%从疫苗染色体上定位疫苗
headDot=fix(rand(1)*bacterinChromosomeLength);
%疫苗在染色体上左边的点位
if headDot==0%防止出现0点位
headDot=1;
end
tailDot=fix(rand(1)*bacterinChromosomeLength);
%疫苗在染色体上右边的点位
if tailDot==0%防止出现0点位
tailDot=1;
end
if tailDot>headDot%防止右边的点位大于左边的点位
dot=headDot;
headDot=tailDot;
tailDot=dot;
end
%%%%%%%%%%%%%接种
inoculateChromosome(i,:)=chromosomeGroup(i,:);%先把输入染色体传给输出
%执行免疫，即从疫苗染色体上取出一段基因做疫苗，再注入到其它染色体中inoculateChromosome(i,headDot:tailDot)...
=bacterinChromosome(1,headDot:tailDot);
end
case 3 %接种位置是随机的
for i=1:chromosomeGroupSum
%%%%%%%%%%%%从疫苗染色体上定位疫苗
headDot=fix(rand(1)*bacterinChromosomeLength);
%疫苗在染色体上左边的点位
if headDot==0%防止出现0点位
headDot=1;
end
tailDot=fix(rand(1)*bacterinChromosomeLength);
%疫苗在染色体上右边的点位
if tailDot==0%防止出现0点位
tailDot=1;
end
if tailDot>headDot%防止右边的点位大于左边的点位
dot=headDot;
headDot=tailDot;
tailDot=dot;
end
%%%%%%%%%%%%%在染色体上随机定位接种位置
inoculateDot=fix(rand(1)*chromosomeLength);%随机选择染色体的接种点位
if inoculateDot==0
inoculateDot=1;
inoculateChromosome(i,:)=chromosomeGroup(i,:);
inoculateChromosome(i,inoculateDot:tailDot-headDot+1)...
=bacterinChromosome(1,headDot:tailDot);
elseif inoculateDot<=headDot
inoculateChromosome(i,:)=chromosomeGroup(i,:);
inoculateChromosome(i,inoculateDot:inoculateDot+tailDot-headDot)...
=bacterinChromosome(1,headDot:tailDot);
elseif (chromosomeLength-inoculateDot)>=(tailDot-headDot)
inoculateChromosome(i,:)=chromosomeGroup(i,:); inoculateChromosome(i,inoculateDot:inoculateDot+tailDot-headDot)... =bacterinChromosome(1,headDot:tailDot);
else
inoculateChromosome(i,:)=chromosomeGroup(i,:); inoculateChromosome(i,headDot:tailDot)...
=bacterinChromosome(1,headDot:tailDot);
end
end
end
图论算法及其MATLAB 程序代码 求赋权图G =(V ,E ,F )中任意两点间的最短路的Warshall-Floyd 算法： 设A =(a ij )n ×n 为赋权图G =(V ,E ,F )的矩阵,当v i v j ∈E 时a ij =F (v i v j ),否则取a ii =0,a ij =+∞(i ≠j ),d ij 表示从v i 到v j 点的距离,r ij 表示从v i 到v j 点的最短路中一个点的编号. ①赋初值.对所有i ,j ,d ij =a ij ,r ij =j .k =1.转向② ②更新d ij ,r ij .对所有i ,j ,若d ik +d k j ＜d ij ,则令d ij =d ik +d k j ,r ij =k ,转向③. ③终止判断.若d ii ＜0,则存在一条含有顶点v i 的负回路,终止;或者k =n 终止;否则令k =k +1,转向②. 最短路线可由r ij 得到. 例1求图6-4中任意两点间的最短路. 解：用Warshall-Floyd 算法,MATLAB 程序代码如下： n=8;A=[0281Inf Inf Inf Inf 206Inf 1Inf Inf Inf 8607512Inf 1Inf 70Inf Inf 9Inf Inf 15Inf 03Inf 8 Inf Inf 1Inf 3046 Inf Inf 29Inf 403 Inf Inf Inf Inf 8630];%MATLAB 中,Inf 表示∞ D=A;%赋初值 for (i=1:n)for (j=1:n)R(i,j)=j;end ;end %赋路径初值 for (k=1:n)for (i=1:n)for (j=1:n)if (D(i,k)+D(k,j) 2. Matlab程序 2.1 一次聚类法 X=[11978 12.5 93.5 31908;…;57500 67.6 238.0 15900]; T=clusterdata(X,0.9) 2.2 分步聚类 Step1 寻找变量之间的相似性 用pdist函数计算相似矩阵，有多种方法可以计算距离，进行计算之前最好先将数据用zscore 函数进行标准化。 X2=zscore(X); %标准化数据 Y2=pdist(X2); %计算距离 Step2 定义变量之间的连接 Z2=linkage(Y2); Step3 评价聚类信息 C2=cophenet(Z2,Y2); //0.94698 Step4 创建聚类，并作出谱系图 T=cluster(Z2,6); H=dendrogram(Z2); Matlab提供了两种方法进行聚类分析。 一种是利用 clusterdata函数对样本数据进行一次聚类，其缺点为可供用户选择的面较窄，不能更改距离的计算方法； 另一种是分步聚类：（1）找到数据集合中变量两两之间的相似性和非相似性，用pdist函数计算变量之间的距离；（2）用 linkage函数定义变量之间的连接；（3）用 cophenetic函数评价聚类信息；（4）用cluster函数创建聚类。 1．Matlab中相关函数介绍 1.1 pdist函数 调用格式：Y=pdist(X,’metric’) 说明：用‘metric’指定的方法计算 X 数据矩阵中对象之间的距离。’ X：一个m×n的矩阵，它是由m个对象组成的数据集，每个对象的大小为n。 metric’取值如下： ‘euclidean’：欧氏距离（默认）；‘seuclidean’：标准化欧氏距离； ‘mahalanobis’：马氏距离；‘cityblock’：布洛克距离； ‘minkowski’：明可夫斯基距离；‘cosine’： ‘correlation’：‘hamming’： ‘jaccard’：‘chebychev’：Chebychev距离。 1.2 squareform函数 调用格式：Z=squareform(Y,..) 说明：强制将距离矩阵从上三角形式转化为方阵形式，或从方阵形式转化为上三角形式。 1.3 linkage函数 调用格式：Z=linkage(Y,’method’) 说明：用‘method’参数指定的算法计算系统聚类树。 Y：pdist函数返回的距离向量； Floyd算法Matlab程序第一种: %floyd.m %采用floyd算法计算图a中每对顶点最短路 %d是矩离矩阵 %r是路由矩阵 function ,d,r,=floyd(a) n=size(a,1); d=a; for i=1:n for j=1:n r(i,j)=j; end end r for k=1:n for i=1:n for j=1:n if d(i,k)+d(k,j) end k d r end 第二种: %Floyd算法 %解决最短路径问题，是用来调用的函数头文件 %[D,path]=floyd(a) %输入参数a是求图的带权邻接矩阵，D(i,j)表示i到j的最短距 离,path(i,j)i,j之间最短路径上顶点i的后继点 %[D,path,min1,path1]=floyd(a,i,j) %输入参数a是所求图的带权邻接矩阵，i,j起点终点,min1表示i与j最短距离，path1为最短路径function [D,path,min1,path1]=floyd(a,start,terminal) D=a;n=size(D,1);path=zeros(n,n); for i=1:n for j=1:n if D(i,j)~=inf path(i,j)=j; end end end for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j) 本文在阐述聚类分析方法的基础上重点研究FCM 聚类算法。FCM 算法是一种基于划分的聚类算法，它的思想是使得被划分到同一簇的对象之间相似度最大，而不同簇之间的相似度最小。最后基于MATLAB实现了对图像信息的聚类。 第 1 章概述 聚类分析是数据挖掘的一项重要功能，而聚类算法是目前研究的核心，聚类分析就是使用聚类算法来发现有意义的聚类，即“物以类聚” 。虽然聚类也可起到分类的作用，但和大多数分类或预测不同。大多数分类方法都是演绎的，即人们事先确定某种事物分类的准则或各类别的标准，分类的过程就是比较分类的要素与各类别标准，然后将各要素划归于各类别中。确定事物的分类准则或各类别的标准或多或少带有主观色彩。 为获得基于划分聚类分析的全局最优结果，则需要穷举所有可能的对象划分，为此大多数应用采用的常用启发方法包括：k-均值算法，算法中的每一个聚类均用相应聚类中对象的均值来表示；k-medoid 算法，算法中的每一个聚类均用相应聚类中离聚类中心最近的对象来表示。这些启发聚类方法在分析中小规模数据集以发现圆形或球状聚类时工作得很好，但当分析处理大规模数据集或复杂数据类型时效果较差，需要对其进行扩展。 而模糊C均值(Fuzzy C-means, FCM)聚类方法，属于基于目标函数的模糊聚类算法的范畴。模糊C均值聚类方法是基于目标函数的模糊聚类算法理论中最为完善、应用最为广泛的一种算法。模糊c均值算法最早从硬聚类目标函数的优化中导出的。为了借助目标函数法求解聚类问题，人们利用均方逼近理论构造了带约束的非线性规划函数，以此来求解聚类问题，从此类内平方误差和WGSS(Within-Groups Sum of Squared Error)成为聚类目标函数的普遍形式。随着模糊划分概念的提出，Dunn [10] 首先将其推广到加权WGSS 函数，后来由Bezdek 扩展到加权WGSS 的无限族，形成了FCM 聚类算法的通用聚类准则。从此这类模糊聚类蓬勃发展起来，目前已经形成庞大的体系。 第 2 章聚类分析方法 2-1 聚类分析 聚类分析就是根据对象的相似性将其分群，聚类是一种无监督学习方法，它不需要先验的分类知识就能发现数据下的隐藏结构。它的目标是要对一个给定的数据集进行划分，这种划分应满足以下两个特性：①类内相似性：属于同一类的数据应尽可能相似。②类间相异性：属于不同类的数据应尽可能相异。图2.1是一个简单聚类分析的例子。 题目：matlab实现Kmeans聚类算法 姓名吴隆煌 学号41158007 背景知识 1.简介： Kmeans算法是一种经典的聚类算法，在模式识别中得到了广泛的应用，基于Kmeans的变种算法也有很多，模糊Kmeans、分层Kmeans 等。 Kmeans和应用于混合高斯模型的受限EM算法是一致的。高斯混合模型广泛用于数据挖掘、模式识别、机器学习、统计分析。Kmeans 的迭代步骤可以看成E步和M步，E：固定参数类别中心向量重新标记样本，M：固定标记样本调整类别中心向量。K均值只考虑（估计）了均值，而没有估计类别的方差，所以聚类的结构比较适合于特征协方差相等的类别。 Kmeans在某种程度也可以看成Meanshitf的特殊版本，Meanshift 是一种概率密度梯度估计方法（优点：无需求解出具体的概率密度，直接求解概率密度梯度。），所以Meanshift可以用于寻找数据的多个模态（类别），利用的是梯度上升法。在06年的一篇CVPR文章上，证明了Meanshift方法是牛顿拉夫逊算法的变种。Kmeans 和EM算法相似是指混合密度的形式已知（参数形式已知）情况下，利用迭代方法，在参数空间中搜索解。而Kmeans和Meanshift相似是指都是一种概率密度梯度估计的方法，不过是Kmean选用的是特殊的核函数（uniform kernel），而与混合概率密度形式是否已知无关，是一种梯度求解方式。 k-means是一种聚类算法，这种算法是依赖于点的邻域来决定哪些 点应该分在一个组中。当一堆点都靠的比较近，那这堆点应该是分到同一组。使用k-means，可以找到每一组的中心点。 当然，聚类算法并不局限于2维的点，也可以对高维的空间（3维，4维，等等）的点进行聚类，任意高维的空间都可以。 上图中的彩色部分是一些二维空间点。上图中已经把这些点分组了，并使用了不同的颜色对各组进行了标记。这就是聚类算法要做的事情。 这个算法的输入是： 1：点的数据（这里并不一定指的是坐标，其实可以说是向量） 2：K，聚类中心的个数（即要把这一堆数据分成几组） 所以，在处理之前，你先要决定将要把这一堆数据分成几组，即聚成几类。但并不是在所有情况下，你都事先就能知道需要把数据聚成几类的。但这也并不意味着使用k-means就不能处理这种情况，下文中会有讲解。 把相应的输入数据，传入k-means算法后，当k-means算法运行完后，该算法的输出是： 1：标签（每一个点都有一个标签，因为最终任何一个点，总会被分到某个类，类的id号就是标签） 2：每个类的中心点。 标签，是表示某个点是被分到哪个类了。例如，在上图中，实际上 最短距离聚类的matlab实现-1 【2013-5-21更新】 说明：正文中命令部分可以直接在Matlab中运行， 作者(Yangfd09)于2013-5-21 19:15:50在MATLAB R2009a(7.8.0.347)中运行通过 %最短距离聚类（含距离计算，含聚类图） %说明：此程序的优点在于每一步都是自己编写的，很少用matlab现成的指令， %所以更适合于初学者，有助于理解各种标准化方法和距离计算方法。 %程序包含了极差标准化（两种方法）、中心化、标准差标准化、总和标准化和极大值标准化等标准化方法， %以及绝对值距离、欧氏距离、明科夫斯基距离和切比雪夫距离等距离计算方法。 %==========================>>导入数据<<============================== %变量名为test（新建一个以test变量，双击进入Variable Editor界面，将数据复制进去即可）%数据要求：m行n列，m为要素个数，n为区域个数（待聚类变量）。 % 具体参见末页测试数据。 testdata=test; %============================>>标准化<<=============================== %变量初始化，m用来寻找每行的最大值，n找最小值，s记录每行数据的和 [M,N]=size(testdata);m=zeros(1,M);n=9999*ones(1,M);s=zeros(1,M);eq=zeros(1,M); %为m、n和s赋值 for i=1:M for j=1:N if testdata(i,j)>=m(i) m(i)=testdata(i,j); end if testdata(i,j)<=n(i) n(i)=testdata(i,j); end s(i)=s(i)+testdata(i,j); end eq(i)=s(i)/N; end %sigma0是离差平方和，sigma是标准差 sigma0=zeros(M); for i=1:M for j=1:N sigma0(i)=sigma0(i)+(testdata(i,j)-eq(i))^2; end end sigma=sqrt(sigma0/N); 实验四：Floyd 算法 一、实验目的 利用MATLAB 实现Floyd 算法，可对输入的邻接距离矩阵计算图中任意两点间的最短距离矩阵和路由矩阵，且能查询任意两点间的最短距离和路由。 二、实验原理 Floyd 算法适用于求解网络中的任意两点间的最短路径：通过图的权值矩阵求出任意两点间的最短距离矩阵和路由矩阵。优点是容易理解，可以算出任意两个节点之间最短距离的算法，且程序容易实现，缺点是复杂度达到，不适合计算大量数据。 Floyd 算法可描述如下： 给定图G 及其边(i , j )的权w i, j (1≤i≤n ,1≤j≤n) F0：初始化距离矩阵W(0)和路由矩阵R(0)。其中： F1：已求得W(k-1)和R(k-1)，依据下面的迭代求W(k)和R(k) F2：若k≤n，重复F1；若k>n，终止。 三、实验内容 1、用MATLAB 仿真工具实现Floyd 算法：给定图G 及其边(i , j )的权 w i , j (1≤i≤n ,1≤j≤n) ，求出其各个端点之间的最小距离以及路由。 （1）尽可能用M 函数分别实现算法的关键部分，用M 脚本来进行算法结 果验证； （2）分别用以下两个初始距离矩阵表示的图进行算法验证： 分别求出W(7)和R(7)。 2、根据最短路由矩阵查询任意两点间的最短距离和路由 （1）最短距离可以从最短距离矩阵的ω(i,j)中直接得出； （2）相应的路由则可以通过在路由矩阵中查找得出。由于该程序中使用的是前向矩阵，因此在查找的过程中，路由矩阵中r(i,j)对应的值为Vi 到Vj 路由上的下一个端点，这样再代入r(r(i,j),j)，可得到下下个端点，由此不断循环下去，即可找到最终的路由。 （3）对图1，分别以端点对V4 和V6, V3 和V4 为例，求其最短距离和路由；对图2，分别以端点对V1 和V7，V3 和V5，V1 和V6 为例，求其最短距离和路由。 3、输入一邻接权值矩阵，求解最短距离和路由矩阵，及某些点间的最短路径。 四、采用的语言 MatLab 源代码： 【func1.m】 function [w r] = func1(w) n=length(w); x = w; r = zeros(n,1);%路由矩阵的初始化 for i=1:1:n for j=1:1:n if x(i,j)==inf r(i,j)=0; else r(i,j)=j; end, end end; %迭代求出k次w值 for k=1:n a=w; s = w; for i=1:n 用matlab做聚类分析 Matlab提供了两种方法进行聚类分析。 一种是利用clusterdata函数对样本数据进行一次聚类，其缺点为可供用户选择的面较窄，不能更改距离的计算方法； 另一种是分步聚类：（1）找到数据集合中变量两两之间的相似性和非相似性，用pdist函数计算变量之间的距离；（2）用linkage函数定义变量之间的连接；（3）用cophenetic函数评价聚类信息；（4）用cluster函数创建聚类。1．Matlab中相关函数介绍 1.1pdist函数 调用格式：Y=pdist(X,’metric’) 说明：用‘metric’指定的方法计算X数据矩阵中对象之间的距离。’X：一个m×n的矩阵，它是由m个对象组成的数据集，每个对象的大小为n。 metric’取值如下： ‘euclidean’：欧氏距离（默认）；‘seuclidean’：标准化欧氏距离； ‘mahalanobis’：马氏距离；‘cityblock’：布洛克距离； ‘minkowski’：明可夫斯基距离；‘cosine’： ‘correlation’：‘hamming’： ‘jaccard’：‘chebychev’：Chebychev距离。 1.2squareform函数 调用格式：Z=squareform(Y,..) 说明：强制将距离矩阵从上三角形式转化为方阵形式，或从方阵形式转化为上三角形式。 1.3linkage函数 调用格式：Z=linkage(Y,’method’) 说明：用‘method’参数指定的算法计算系统聚类树。 Y：pdist函数返回的距离向量； method：可取值如下： ‘single’：最短距离法（默认）；‘complete’：最长距离法； ‘average’：未加权平均距离法；‘weighted’：加权平均法； ‘centroid’：质心距离法；‘median’：加权质心距离法； ‘ward’：内平方距离法（最小方差算法） 返回：Z为一个包含聚类树信息的（m-1）×3的矩阵。 1.4dendrogram函数 调用格式：[H，T，…]=dendrogram(Z,p，…) 说明：生成只有顶部p个节点的冰柱图（谱系图）。 1.5cophenet函数 调用格式：c=cophenetic(Z,Y) 说明：利用pdist函数生成的Y和linkage函数生成的Z计算cophenet相关系数。 1.6cluster函数 调用格式：T=cluster(Z,…) 说明：根据linkage函数的输出Z创建分类。 精心整理 图论算法matlab实现 求最小费用最大流算法的 MATLAB 程序代码如下： n=5;C=[0 15 16 0 0 0 0 0 13 14 for while for for(i=1:n)for(j=1:n)if(C(i,j)>0&f(i,j)==0)a(i,j)=b(i,j); elseif(C(i,j)>0&f(i,j)==C(i,j))a(j,i)=-b(i,j); elseif(C(i,j)>0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end;end;end for(i=2:n)p(i)=Inf;s(i)=i;end %用Ford 算法求最短路, 赋初值 for(k=1:n)pd=1; %求有向赋权图中vs 到vt 的最短路 for(i=2:n)for(j=1:n)if(p(i)>p(j)+a(j,i))p(i)=p(j)+a(j,i);s(i)=j;pd=0;end ;end;end if(pd)break;end;end %求最短路的Ford 算法结束 if(p(n)==Inf)break;end %不存在vs 到vt 的最短路, 算法终止. 注意在求最小费用最大流时构造有 while if elseif if if pd=0; 值 t=n; if elseif if(s(t)==1)break;end %当t 的标号为vs 时, 终止调整过程 t=s(t);end if(pd)break;end%如果最大流量达到预定的流量值 wf=0; for(j=1:n)wf=wf+f(1,j);end;end %计算最大流量 zwf=0;for(i=1:n)for(j=1:n)zwf=zwf+b(i,j)*f(i,j);end;end%计算最小费用 matlab实现Kmeans聚类算法 1.简介： Kmeans和应用于混合高斯模型的受限EM算法是一致的。高斯混合模型广泛用于数据挖掘、模式识别、机器学习、统计分析。Kmeans 的迭代步骤可以看成E步和M步，E：固定参数类别中心向量重新标记样本，M：固定均值只考虑（估计）了均值，而没有估计类别的方差，所以聚类的结构比较适合于特征协方差相等的类别。 Kmeans在某种程度也可以看成Meanshitf的特殊版本，Meanshift 是所以Meanshift可以用于寻找数据的多个模态（类别），利用的是梯度上升法。在06年的一篇CVPR文章上，证明了Meanshift方法是牛顿拉夫逊算法的变种。Kmeans和EM算法相似是指混合密度的形式已知（参数形式已知）情况下，利用迭代方法，在参数空间中搜索解。而Kmeans和Meanshift相似是指都是一种概率密度梯度估计的方法，不过是Kmean选用的是特殊的核函数（uniform kernel），而与混合概率密度形式是否已知无关，是一种梯度求解方式。 k-means是一种聚类算法，这种算法是依赖于点的邻域来决定哪些点应该分在点，也可以对高维的空间（3维，4维，等等）的点进行聚类，任意高维的空间都可以。 上图中的彩色部分是一些二维空间点。上图中已经把这些点分组了，并使用了不同的颜色对各组进行了标记。这就是聚类算法要做的事情。 这个算法的输入是： 1：点的数据（这里并不一定指的是坐标，其实可以说是向量） 2：K，聚类中心的个数（即要把这一堆数据分成几组） 所以，在处理之前，你先要决定将要把这一堆数据分成几组，即聚成几类。但并不是在所有情况下，你都事先就能知道需要把数据聚成几类的。意味着使用k-means就不能处理这种情况，下文中会有讲解。 把相应的输入数据，传入k-means算法后，当k-means算法运行完后，该算法的输出是： 1：标签（每一个点都有一个标签，因为最终任何一个点，总会被分到某个类，类的id号就是标签） 2：每个类的中心点。 标签，是表示某个点是被分到哪个类了。例如，在上图中，实际上有4中“标签”，每个“标签”使用不同的颜色来表示。所有黄色点我们可以用标签以看出，有3个类离的比较远，有两个类离得比较近，几乎要混合在一起了。 当然，数据集不一定是坐标，假如你要对彩色图像进行聚类，那么你的向量就可以是(b,g,r)，如果使用的是hsv颜色空间，那还可以使用(h,s,v),当然肯定可以有不同的组合例如(b*b,g*r,r*b) ，(h*b,s*g,v*v)等等。 在本文中，初始的类的中心点是随机产生的。如上图的红色点所示，是本文随机产生的初始点。注意观察那两个离得比较近的类，它们几乎要混合在一起，看看算法是如何将它们分开的。 类的初始中心点是随机产生的。算法会不断迭代来矫正这些中心点，并最终得到比较靠5个中心点的距离,选出一个距离最小的(例如该点与第2个中心点的距离是5个距离中最小的),那么该点就归属于该类.上图是点的归类结果示意图. 经过步骤3后,每一个中心center(i)点都有它的”管辖范围”,由于这个中心点不一定是这个管辖范围的真正中心点,所以要重新计算中心点,计算的方法有很多种,最简单的一种是,直接计算该管辖范围内所有点的均值,做为心的中心点new_center(i). 如果重新计算的中心点new_center(i)与原来的中心点center(i)的距离大于一定的阈值（该阈值可以设定），那么认为算法尚未收敛，使用new_center(i)代替center(i)（如图，中心点从红色点 一、实验目的 利用MATLAB实现Floyd算法，可对输入的邻接距离矩阵计算图中任意两点间的最短距离矩阵和路由矩阵，且能查询任意两点间的最短距离和路由。 二、实验原理 Floyd 算法适用于求解网络中的任意两点间的最短路径：通过图的权值矩阵求出任意两点间的最短距离矩阵和路由矩阵。优点是容易理解，可以算出任意两个 节点之间最短距离的算法，且程序容易实现，缺点是复杂度达到，不适合计算大量数据。 Floyd 算法可描述如下： 给定图G及其边(i , j ) 的权w, j (1 < i < n ,1 function varargout = lljuleifenxi(varargin) % LLJULEIFENXI MATLAB code for lljuleifenxi.fig % LLJULEIFENXI, by itself, creates a new LLJULEIFENXI or raises the existing % singleton*. % % H = LLJULEIFENXI returns the handle to a new LLJULEIFENXI or the handle to % the existing singleton*. % % LLJULEIFENXI('CALLBACK',hObject,eventData,handles,...) calls the local % function named CALLBACK in LLJULEIFENXI.M with the given input arguments. % % LLJULEIFENXI('Property','Value',...) creates a new LLJULEIFENXI or raises the % existing singleton*. Starting from the left, property value pairs are % applied to the GUI before lljuleifenxi_OpeningFcn gets called. An % unrecognized property name or invalid value makes property application % stop. All inputs are passed to lljuleifenxi_OpeningFcn via varargin. % % *See GUI Options on GUIDE's Tools menu. Choose "GUI allows only one % instance to run (singleton)". % % See also: GUIDE, GUIDATA, GUIHANDLES % Edit the above text to modify the response to help lljuleifenxi % Last Modified by GUIDE v2.5 07-Jan-2015 18:18:25 % Begin initialization code - DO NOT EDIT gui_Singleton = 1; gui_State = struct('gui_Name', mfilename, ... 'gui_Singleton', gui_Singleton, ... 'gui_OpeningFcn', @lljuleifenxi_OpeningFcn, ... 'gui_OutputFcn', @lljuleifenxi_OutputFcn, ... 'gui_LayoutFcn', [] , ... 'gui_Callback', []); if nargin && ischar(varargin{1}) gui_State.gui_Callback = str2func(varargin{1}); end if nargout [varargout{1:nargout}] = gui_mainfcn(gui_State, varargin{:}); else gui_mainfcn(gui_State, varargin{:}); end % End initialization code - DO NOT EDIT % --- Executes just before lljuleifenxi is made visible. function lljuleifenxi_OpeningFcn(hObject, eventdata, handles, varargin) % This function has no output args, see OutputFcn. % hObject handle to figure % eventdata reserved - to be defined in a future version of MATLAB 图论算法及其MATLAB程序代码 求赋权图G = (V, E , F )中任意两点间的最短路的Warshall-Floyd算法： 设A = (a ij )n×n为赋权图G = (V, E , F )的矩阵, 当v i v j∈E时a ij= F (v i v j), 否则取a ii=0, a ij = +∞(i≠j ), d ij表示从v i到v j点的距离, r ij表示从v i到v j点的最短路中一个点的编号. ①赋初值. 对所有i, j, d ij = a ij, r ij = j. k = 1. 转向② ②更新d ij, r ij . 对所有i, j, 若d ik + d k j＜d ij, 则令d ij = d ik + d k j, r ij = k, 转向③. ③终止判断. 若d ii＜0, 则存在一条含有顶点v i的负回路, 终止; 或者k = n终止; 否则令k = k + 1, 转向②. 最短路线可由r ij得到. 例1求图6-4中任意两点间的最短路. 图6-4 解：用Warshall-Floyd算法, MA TLAB程序代码如下： n=8;A=[0 2 8 1 Inf Inf Inf Inf 2 0 6 Inf 1 Inf Inf Inf 8 6 0 7 5 1 2 Inf 1 Inf 7 0 Inf Inf 9 Inf Inf 1 5 Inf 0 3 Inf 8 Inf Inf 1 Inf 3 0 4 6 Inf Inf 2 9 Inf 4 0 3 Inf Inf Inf Inf 8 6 3 0]; % MATLAB中, Inf表示∞ D=A; %赋初值 for(i=1:n)for(j=1:n)R(i,j)=j;end;end%赋路径初值 for(k=1:n)for(i=1:n)for(j=1:n)if(D(i,k)+D(k,j) 本文在阐述聚类分析方法的基础上重点研究FCM聚类算法。FCM算法是一种基于划分的聚类算法，它的思想是使得被划分到同一簇的对象之间相似度最大，而不同簇之间的相似度最小。最后基于MATLAB实现了对图像信息的聚类。 第1章概述 聚类分析是数据挖掘的一项重要功能，而聚类算法是目前研究的核心，聚类分析就是使用聚类算法来发现有意义的聚类，即“物以类聚”。虽然聚类也可起到分类的作用，但和大多数分类或预测不同。大多数分类方法都是演绎的，即人们事先确定某种事物分类的准则或各类别的标准，分类的过程就是比较分类的要素与各类别标准，然后将各要素划归于各类别中。确定事物的分类准则或各类别的标准或多或少带有主观色彩。 为获得基于划分聚类分析的全局最优结果，则需要穷举所有可能的对象划分，为此大多数应用采用的常用启发方法包括：k-均值算法，算法中的每一个聚类均用相应聚类中对象的均值来表示；k-medoid算法，算法中的每一个聚类均用相应聚类中离聚类中心最近的对象来表示。这些启发聚类方法在分析中小规模数据集以发现圆形或球状聚类时工作得很好，但当分析处理大规模数据集或复杂数据类型时效果较差，需要对其进行扩展。 而模糊C均值(Fuzzy C-means,FCM)聚类方法，属于基于目标函数的模糊聚类算法的范畴。模糊C均值聚类方法是基于目标函数的模糊聚类算法理论中最为完善、应用最为广泛的一种算法。模糊c均值算法最早从硬聚类目标函数的优化中导出的。为了借助目标函数法求解聚类问题，人们利用均方逼近理论构造了带约束的非线性规划函数，以此来求解聚类问题，从此类内平方误差和WGSS(Within-Groups Sum of Squared Error)成为聚类目标函数的普遍形式。随着模糊划分概念的提出，Dunn[10]首先将其推广到加权WGSS函数，后来由Bezdek扩展到加权WGSS的无限族，形成了FCM聚类算法的通用聚类准则。从此这类模糊聚类蓬勃发展起来，目前已经形成庞大的体系。 第2章聚类分析方法 2-1聚类分析 聚类分析就是根据对象的相似性将其分群，聚类是一种无监督学习方法，它不需要先验的分类知识就能发现数据下的隐藏结构。它的目标是要对一个给定的数据集进行划分，这种划分应满足以下两个特性：①类内相似性：属于同一类的数据应尽可能相似。②类间相异性：属于不同类的数据应尽可能相异。图2.1是一个简单聚类分析的例子。 Dijkstra 算法Matlab 实现。 %求一个点到其他各点的最短路径 function [min,path]=dijkstra(w,start,terminal) %W 是邻接矩阵 %start 是起始点 %terminal 是终止点 %min 是最短路径长度 %path 是最短路径 n=size(w,1); label(start)=0; f(start)=start; for i=1:n if i~=start label(i)=inf; end end s(1)=start; u=start; while length(s) function [center, U, obj_fcn] = FCMClust(data, cluster_n, options) % FCMClust.m 采用模糊C均值对数据集data聚为cluster_n类 % 用法： % 1. [center,U,obj_fcn] = FCMClust(Data,N_cluster,options); % 2. [center,U,obj_fcn] = FCMClust(Data,N_cluster); % 输入： % data ---- nxm矩阵,表示n个样本,每个样本具有m的维特征值 % N_cluster ---- 标量,表示聚合中心数目,即类别数 % options ---- 4x1矩阵，其中 % options(1): 隶属度矩阵U的指数，>1 (缺省值: 2.0) % options(2): 最大迭代次数(缺省值: 100) % options(3): 隶属度最小变化量,迭代终止条件(缺省值: 1e-5) % options(4): 每次迭代是否输出信息标志(缺省值: 1) % 输出： % center ---- 聚类中心 % U ---- 隶属度矩阵 % obj_fcn ---- 目标函数值 % Example: % data = rand(100,2); % [center,U,obj_fcn] = FCMClust(data,2); % plot(data(:,1), data(:,2),'o'); % hold on; % maxU = max(U); % index1 = find(U(1,:) == maxU); % index2 = find(U(2,:) == maxU); % line(data(index1,1),data(index1,2),'marker','*','color','g'); % line(data(index2,1),data(index2,2),'marker','*','color','r'); % plot([center([1 2],1)],[center([1 2],2)],'*','color','k') % hold off; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%% if nargin ~= 2 & nargin ~= 3, %判断输入参数个数只能是2个或3个 error('Too many or too few input arguments!'); end data_n = size(data, 1); % 求出data的第一维(rows)数,即样本个数 in_n = size(data, 2); % 求出data的第二维(columns)数，即特征值长度 % 默认操作参数 default_options = [2; % 隶属度矩阵U的指数 100; % 最大迭代次数 1e-5; % 隶属度最小变化量,迭代终止条件 基于matlab的floyd算法 matlab计算最短路径 function [d,path]=floyd(a,sp,ep) % floyd - 最短路问题 % % Syntax: [d,path]=floyd(a,sp,ep) % % Inputs: % a - 距离矩阵是指i到j之间的距离，可以是有向的 % sp - 起点的标号 % ep - 终点的标号 % % Outputs: % d - 最短路的距离 % path - 最短路的路径 % a =[ 0 50 inf; 50 0 15 ; Inf 15 0 ];% a(i,j)，从节点i到j之间的距离 % [d,path]=floyd(a,2,5) sp=3; ep=1; n=size(a,1); D=a; path=zeros(n,n); for i=1:n for j=1:n if D(i,j)~=inf path(i,j)=j; %j是i的后续点 end end end for k=1:n for i=1:n for j=1:n if D(i,j)>D(i,k)+D(k,j) D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k); end end end end p=[sp]; mp=sp; for k=1:n if mp~=ep d=path(mp,ep); p=[p,d]; mp=d; end end d=D(sp,ep) path=p 试计算下图的最短路径， 1.起点C点，终点A点。 2.起点A点，终点G点。 3.起点D点，终点F点。 试计算下图的最短路径， 1.起点F点，终点A点。 2. 起点E点，终点C点。聚类分析Matlab程序实现
Floyd算法Matlab程序
MATLAB实现FCM 聚类算法
matlab实现Kmeans聚类算法
最短距离聚类的matlab实现-1(含聚类图-含距离计算)
Floyd算法_计算最短距离矩阵和路由矩阵_查询最短距离和路由_matlab实验报告
数学实验05聚类分析---用matlab做聚类分析
matlab图论程序算法大全
matlab实现Kmeans聚类算法
Floyd算法_计算最短距离矩阵和路由矩阵_查询最短距离和路由_matlab实验报告
聚类分析matlab程序设计代码
图论算法及其MATLAB程序代码
MATLAB实现FCM 聚类算法
Dijkstra、Floyd算法Matlab_Lingo实现
FCMClust(模糊c均值聚类算法MATLAB实现)
基于matlab的floyd算法+matlab计算最短路径
相关主题
文本预览