最大最小距离算法函数：
function [pattern]=maxmin(x)
maxdistance=0;
index=1;%相当于指针指示新中心点的位置
k=1;%中心点计数，也即是类别
center=zeros(size(x));%保存中心点
patternnum=size(x,1);%输入的数据数
distance=zeros(patternnum,3);%求距离
min=zeros(patternnum,1);%取较小距离
pattern=(patternnum);%表示类别
center(1,:)=x(1,:);
pattern(1)=1;
for i=2:patternnum
distance(i,1)=sqrt((x(i,:)-center(1,:))*(x(i,:)-center(1,:))');%欧氏距离min(i,1)=distance(i,1);
pattern(i)=1;
if(maxdistance maxdistance=distance(i,1); index=i; end end k=k+1; center(k,:)=x(index,:); pattern(index)=2; min(index,1)=0; while 1 for i=2:patternnum if(min(i,1)~=0) distance(i,k)=sqrt((x(i,:)-center(k,:))*(x(i,:)-center(k,:))'); if(min(i,1)>distance(i,k)) min(i,1)=distance(i,k); pattern(i)=k; end end end max=0; for i=2:patternnum if((max max=min(i,1); index=i; end end if(max>(maxdistance*) k=k+1; center(k,:)=x(index,:); pattern(index)=k; min(index,1)=0; else break; end end 程序界面截图如下： 程序框图如下： x=[0,0;3,8;2,2;1,1;5,3;4,8;6,3;5,4;6,4;7,5] pattern=maxmin(x) （1）当选用第一点为中心，用matlab得出各点与中心点的距离，并分类，将运行结果保存在EXCEL中如下： （2）与X1距离最远的X6为第二个中心点，用matlab得出各点与中心点的距离，离得较近的中心点归为一类，将运行结果保存在EXCEL中如下： （3）与个中心距离最远的X7为第三个中心点，用matlab得出各点与中心点的距离，离得较近的中心点归为一类，将运行结果保存在EXCEL中如下： （4）由于阈值T=最大距离maxdistance的，而各点与各自中心点的距离min都大于阈值T，所以聚类循环工作结束。 运行结果为： pattern = 1 2 1 1 3 2 3 3 3 3 表明：对于样本x1=(0,0);x2=(3,8); x3=(2,2); x4=(1,1); x5=(5,3); x6=(4,8); x7=(6,3); x8=(5,4); x9=(6,4); x10=(7,5); 运行界面截图如下： Neighbor Search with Global Geometry:A Minimax Message Passing Algorithm 基于全局数据集合结构的近邻搜索：极大极小信息传递算法 人脸识别简介： 人脸识别技术是基于人的脸部特征，对输入的人脸图象或者视频流 . 首先判断其是否存在人脸 , 如果存在人脸，则进一步的给出每个脸的位置、大小和各个主要面部器官的位置信息。并依据这些信息，进一步提取每个人脸中所蕴涵的身份特征，并将其与已知的人脸进行对比，从而识别每个人脸的身份。 广义的人脸识别实际包括构建人脸识别系统的一系列相关技术，包括人脸图像采集、人脸定位、人脸识别预处理、身份确认以及身份查找等；而狭义的人脸识别特指通过人脸进行身份确认或者身份查找的技术或系统。 人脸识别技术中被广泛采用的区域特征分析算法，它融合了计算机图像处理技术与生物统计学原理于一体，利用计算机图像处理技术从视频中提取人像特征点，利用生物统计学的原理进行分析建立数学模型,即人脸特征模板。利用已建成的人脸特征模板与被测者的人的面像进行特征分析，根据分析的结果来给出一个相似值。通过这个值即可确定是否为同一人。 基本算法：1.基于人脸特征点的识别算法（Feature-based recognition algorithms ）。 2.基于整幅人脸图像的识别算法（Appearance-based recognition algorithms ）。 3.基于模板的识别算法（Template-based recognition algorithms ）。 4.利用神经网络进行识别的算法（Recognition algorithms using neural network ）。 5.利用线性回归进行识别的算法。 6.利用稀疏表示进行识别的算法。 我的课题是利用最小最大距离进行人脸识别的算法（ Neighbor with Global Geometry ：A Minimax Message Passing Algorithm ） 核心算法： 1. k-Nearest Neighbor algorithm （k 邻近算法） K 最近邻(k-Nearest Neighbor ，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k 个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN 算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN 方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN 方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN 方法较其他方法更为适合。 具体来说就是在N 个已知样本中，找出X 的k 个近邻。设这N 个样本中，来自1w 类的样本有1N 个，来自2w 类的有2N 个，…，来自c w 类的有c N 个，若12,,...,c k k k 分别是k 个近邻中属于12,...,c w w w 类 第六章 基础知识： ◆遥感数字图像的基本单位为像素（像元），是成像过程的采样点，也是计算机图像处理的最小单元。 像素具有空间特征和属性特征。 ◆遥感数字图像的特点： 1）便于计算机处理与分析；2）图像信息损失低；3）抽象性强。 ◆遥感数字图像的类型： 1）二值数字图像；2）单波段数字图像；3）多波段数字图像。 ◆遥感数字图像的计算机分类是通过模式识别理论，利用计算机将遥感图像自动分成若干地物类别的方 法。 ◆遥感图像分类的基本原理：不同的地物具有不同的光谱特征，同类地物具有相同或相似的光谱特征。 图像分类是基于数字图像中反映的同类地物的光谱相似性和异类地物的光谱差异性。依据是遥感图像像素的相似度。常用距离和相关系数衡量相似度。 问题： 1.监督分类和非监督分类的区别，各自有什么方法，各有什么优缺点，适用条件？ ●监督分类：通过选择代表各类别的已知样本（训练区）的象元光谱特征，事先取得个类别的参数，确 定判别函数，从而进行分类。（在监督分类中，先定义信息类，然后检验它们的光谱可分性。） ●非监督分类：根据事先制定的某一准则，而进行计算机自动判别归类，无须人为干预，分类后确定地 面类别。（在非监督分类中，先确定光谱可分的类别，然后定义它们的信息类。）主要采用聚类法，使同一类别的像素之间的距离尽可能的小而不同类别上的像素间的距离尽可能的大。（From PDF第6章） ●监督分类和非监督分类的根本区别在于是否利用训练场地来获取先验的类别知识，监督分类根据训练 场提供的样本选择特征参数，建立判别函数，对待分类点进行分类。 ●监督分类中常用的具体分类方法：①最小距离分类法：（其中包含两点）⑴最小距离分类法，⑵最近 邻域分类法；②多级切割分类法；③特征曲线窗口法；④最大似然比分类法。 ●非监督分类中常用的具体分类方法：①分类集群法；②动态聚类法。 ●非监督分类的好处：不需要更多的先验知识，根据地物的光谱统计特性进行分类，方法简单，具有一 定的精度。不足：精度有限。 ●监督分类的好处：分类精度高；不足：训练场地要求有代表性，训练样本的选择要考虑到地物光谱特 性，样本数目要能满足分类的要求，有时这些不容易做到。 ●适用条件：光谱特征类与地物信息类一一对应，非监督分类效果好；两个地物类型对应的光谱特征类 差异很小时，监督分类效果好。（From 课本201页） 2.简述波谱分类原理和应用条件。 同物异谱：同类地物具有不同的光谱特性。 同谱异物：不同的地物可能具有相似的光谱特征。 如：同一作物，生长状态不同，光谱特征有差异；不同的植被类型可能有相似的光谱特征。（From PPT 第6章28页） 3.简述聚类分析，分类方法过程，通常有哪些方法来控制分类过程结束（就是分类过程结束的条件）。 在初始状态给出图像粗糙的分类，然后基于一定原则在类别间重新组合样本，直到分类比较合理为止，这种聚类方法就是动态聚类。下面给出分类过程： a)按照某个原则选择一些初始类聚类中心； b)计算像素与初始类别中心的距离，把该像素分配到最近的类别中； 最大最小距离算法实例 10个模式样本点{x1(0 0), x2(3 8), x3(2 2), x4(1 1), x5(5 3), x6(4 8), x7(6 3), x8(5 4), x9(6 4), x10(7 5)} 第一步：选任意一个模式样本作为第一个聚类中心，如z1 = x1； 第二步：选距离z1最远的样本作为第二个聚类中心。 经计算，|| x6 - z1 ||最大，所以z2 = x6； 第三步：逐个计算各模式样本{x i, i = 1,2,…,N}与{z1, z2}之间的距离，即 D i1 = || x i - z1 || D i2 = || x i – z2 || 并选出其中的最小距离min(D i1, D i2)，i = 1,2,…,N 第四步：在所有模式样本的最小值中选出最大距 离，若该最大值达到||z1 - z2 ||的一定比例以 上，则相应的样本点取为第三个聚类中心 z3，即：若max{min(D i1, D i2), i = 1,2,…,N} > θ||z1 - z2 ||，则z3 = x i 否则，若找不到适合要求的样本作为新的 聚类中心，则找聚类中心的过程结束。 这里，θ可用试探法取一固定分数，如1/2。 在此例中，当i=7时，符合上述条件，故 z3 = x7 第五步：若有z3存在，则计算max{min(D i1, D i2, D i3), i = 1,2,…,N}。若该值超过||z1 - z2 ||的一定 比例，则存在z4，否则找聚类中心的过程 结束。 在此例中，无z4满足条件。 第六步：将模式样本{x i, i = 1,2,…,N}按最近距离分到最近的聚类中心： z1 = x1：{x1, x3, x4}为第一类 z2 = x6：{x2, x6}为第二类 z3 = x7：{x5, x7, x8, x9, x10}为第三类最后，还可在每一类中计算各样本的均值，得到更具代表性的聚类中心。 最短距离型问题的建模方法 生活中经常会涉及到许多最优化的数学应用问题，实践上升为理论就需建立正确的数学模型进行求解。求最短距离是初中数学应用中最赏见的数学建模问题，很具有代表性。以下是我积累的一些教学资源，仅供参考。 1、 两点之间，线段最短。 （1）举一生活中实例：A 、B 两村在河的两侧，要修一供水管道为两村供水，问河的何处修建水泵站，可使铺设的管道长度最少？ 教师引导建立何种数学模型是这一问题解决的关键。平面几何中我们把两村庄作为点A 、B ，河看作是一条直线l ，连结AB 与直线交于点P ，点P 就是所求的水泵站修建位置。 （2）往下推广，如果点A 、B 在河l 的同侧，如何确定水泵站修建位置呢？ 学习完轴对称变换之后，我们可把图2转化为图1的情形来解决。 （3）继续往下推广，初中人教版教材书中有几个这样的习题，如原一条河改为两条河，打台球中如何击中球的设计问题等，都可类似这样去转化解决。 2、不在一线上的三个村庄集中打一眼井修建水塔提供自来水，这眼井 打在何处可使铺设通往三个村庄的自来水主管道长度最少？ 教师引导学生建立数模时，可化归为：不在同一直线上的三个点 之间，如何确定一点到这三点的距离之和最短。这就是著名的费尔马 问题。 （1）三个点连结可构成一等边三角形，不难引导学生发现要求 的点P 是这一等边三角形的中心。 （2）从∠APB=∠BPC=∠CPA=120°，猜想点P 是锐角三角形 内部一点，与三顶点所成张角为120°时，就是所求点。 （3）把三角形ABC 变为直角三角形及钝角三角形，情形又是怎么样的结果？ 3、一只蚂蚁从20×30×40规格纸箱的一角A 处到C ’处取食,求它走 的最短路线的长度? 教师可放开，让学生自我设计，再分组讨论，集思广益，是一很好 的化立体几何问题为平面几何求最短距离的数学建模问题。学生可 得出不同的答案，如下图： l l 最大最小距离算法函数： function [pattern]=maxmin(x) maxdistance=0; index=1;%相当于指针指示新中心点的位置 k=1;%中心点计数，也即是类别 center=zeros(size(x));%保存中心点 patternnum=size(x,1);%输入的数据数 distance=zeros(patternnum,3);%求距离 min=zeros(patternnum,1);%取较小距离 pattern=(patternnum);%表示类别 center(1,:)=x(1,:); pattern(1)=1; for i=2:patternnum distance(i,1)=sqrt((x(i,:)-center(1,:))*(x(i,:)-center(1,:))');%欧氏距离min(i,1)=distance(i,1); pattern(i)=1; if(maxdistance 监督分类中常用的具体分类方法包括： 最小距离分类法（minimum distance classifier）：最小距离分类法是用特征空间中的距离作为像元分类依据的。最小距离分类包括最小距离判别法和最近邻域分类法。最小距离判别法要求对遥感图像中每一个类别选一个具有代表意义的统计特征量（均值），首先计算待分象元与已知类别之间的距离，然后将其归属于距离最小的一类。最近邻域分类法是上述方法在多波段遥感图像分类的推广。在多波段遥感图像分类中，每一类别具有多个统计特征量。最近邻域分类法首先计算待分象元到每一类中每一个统计特征量间的距离，这样，该象元到每一类都有几个距离值，取其中最小的一个距离作为该象元到该类别的距离，最后比较该待分象元到所有类别间的距离，将其归属于距离最小的一类。最小距离分类法原理简单，分类精度不高，但计算速度快，它可以在快速浏览分类概况中使用。 多级切割分类法（multi-level slice classifier）： 是根据设定在各轴上值域分割多维特征空间的分类方法。通过分割得到的多维长方体对应各分类类别。经过反复对定义的这些长方体的值域进行内外判断而完成各象元的分类。这种方法要求通过选取训练区详细了解分类类别（总体）的特征，并以较高的精度设定每个分类类别的光谱特征上限值和下限值，以便构成特征子空间。多级切割分类法要求训练区样本选择必须覆盖所有 的类型，在分类过程中，需要利用待分类像元光谱特征值与各个类别特征子空间在每一维上的值域进行内外判断，检查其落入哪个类别特征子空间中，直到完成各像元的分类。 多级分割法分类便于直观理解如何分割特征空间，以及待分类像元如何与分类类别相对应。由于分类中不需要复杂的计算，与其它监督分类方法比较，具有速度快的特点。但多级分割法要求分割面总是与各特征轴正交，如果各类别在特征空间中呈现倾斜分布，就会产生分类误差。因此运用多级分割法分类前，需要先进行主成分分析，或采用其它方法对各轴进行相互独立的正交变换，然后进行多级分割。 最大似然分类法(maximum likelihood classifier)：最大似然分类法是经常使用的监督分类方法之一，它是通过求出每个像元对于各类别归属概率（似然度）（likelihood），把该像元分到归属概率（似然度）最大的类别中去的方法。最大似然法假定训练区地物的光谱特征和自然界大部分随机现象一样，近似服从正态分布，利用训练区可求出均值、方差以及协方差等特征参数，从而可求出总体的先验概率密度函数。当总体分布不符合正态分布时，其分类可靠性将下降，这种情况下不宜采用最大似然分类法。 最大似然分类法在多类别分类时，常采用统计学方法建立起一个判别函数集，然后根据这个判别函数集计算各待分象元的归 算法导论求n个点的最小距离 在中文算法导论649页算法： 0：把所有的点按照横坐标排序 1：用一条竖直的线L将所有的点分成两等份 2：递归算出左半部门的这段两点距离d1，右半部门的这段两点距离d2，取d=min(d1,d2) 3：算出"1个在左半部分，另外1个在右半部分"这样的点对的最短距离d3 4：结果=min(d1,d2,d3) 关键就是这第3步貌似这需要n^2的时间，把左边每1个点以及右面每1个点都相比较一下，其实奥秘就在这里。 首先，两边的点，与分割线L的距离超过d的，都可以扔掉了，其次，纵然两个点P1,P2(不妨令P1在左边，P2在右面)与分割线L的距离(程度距离)都小于d，如果它们的纵坐标之差大于d，也没戏了。 就是这两点使得搜索范围大大减小：对左半部分的，与L的距离在d之内的，每1个P1来讲：右半部分内，切合以上两个条件的点P2至多只有六个！ 原因就是： d是两个半平面各自内，任意两点的最小距离，因此在同一个半平面内，任何两点距离都不有可能超过d。 咱们又要求P1以及P2的程度距离不能超过d，垂直距离也不能超过d，在这个d*2d 的小方块内，至多只能放下六个距离不小于d的点。 因此，第3步总的比较距离的回数不超过n*6 第3步的具体做法是： 3.1删除所有到L的距离大于d的点O(n) 3.2把右半平面的点按照纵坐标y排序O(nlogn) 3.3对左半平面内的每个点P1，找出右半平面内纵坐标与P1的纵坐标的差在d以内的点P2，计算距离取最小值，算出d3 O(n*6)=O(n) 改进：咱们对3.2这个排序的O(nlogn)不太满意. 既然全部算法是递归的，咱们可以哄骗第2步的子递归中已经排好序的序列，在第3.2部合并这两个子列，这样3.2的复杂度变成了O(n)。 这样，全般算法就是O(nlogn)的。 代码如下：VC6.0下编译通过 #include"stdafx.h" #include stdio.h #include stdlib.h #include math.h #define MAX 10000 typedef struct point{ int x,y； }POINT； double delta=MAX； int totalnum； 算法导论求n个点的最小距离 2010-01-20 17:23 在中文算法导论649页 算法： 0：把所有的点按照横坐标排序 1：用一条竖直的线L将所有的点分成两等份 2：递归算出左半部分的最近两点距离d1，右半部分的最近两点距离d2，取 d=min(d1,d2) 3：算出“一个在左半部分，另一个在右半部分”这样的点对的最短距离d3。4：结果＝min(d1,d2,d3) 关键就是这第3步。貌似这需要n^2的时间，把左边每个点和右边每个点都对比一下。其实不然。秘密就在这里。 首先，两边的点，与分割线L的距离超过d的，都可以扔掉了。 其次，即使两个点P1,P2（不妨令P1在左边，P2在右边）与分割线L的距离（水平距离）都小于d，如果它们的纵坐标之差大于d，也没戏。 就是这两点使得搜索范围大大减小： 对于左半部分的，与L的距离在d之内的，每个P1来说：右半部分内，符合以上两个条件的点P2最多只有6个！ 原因就是： d是两个半平面各自内，任意两点的最小距离，因此在同一个半平面内，任何两点距离都不可能超过d。 我们又要求P1和P2的水平距离不能超过d，垂直距离也不能超过d，在这个d*2d 的小方块内，最多只能放下6个距离不小于d的点。 因此，第3步总的比较距离的次数不超过n*6。 第3步的具体做法是： 3.1 删除所有到L的距离大于d的点。 O(n) 3.2 把右半平面的点按照纵坐标y排序。 O(nlogn) 3.3 对于左半平面内的每个点P1，找出右半平面内纵坐标与P1的纵坐标的差在d以内的点P2，计算距离取最小值，算出d3。 O(n*6) = O(n) 因为3.2的排序需要O(nlogn)， 所以整个算法的复杂度就是O(n((logn)^2))。 改进： 任意两点间最短距离-floyd算法matlab程序 %Floyd's Algorithm 通过一个图的权值矩阵求出它的任意两点间的最短路径矩阵。 %Floyd算法适用于APSP(All Pairs Shortest Paths)，是一种动态规划算法， %稠密图效果最佳，边权可正可负。 %此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。 %a为图的带权邻接矩阵 %从图的带权邻接矩阵A=[a(i,j)] n×n开始，递归地进行n次更新， %即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)； %又用同样地公式由D(1)构造出D(2)；……； %最后又用同样的公式由D(n-1)构造出矩阵D(n)。 %矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵， %同时还可引入一个后继节点矩阵path来记录两点间的最短路径。 %采用的是松弛技术，对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3); matlab函数文件为： function [D,path]=floyd1(a) a(find(a==0))=inf; n=size(a,1); %计算出a的规模的大小. D=a;path=zeros(n,n);%设置D和path的初值. for i=1:n for j=1:n if D(i,j)~=inf path(i,j)=j; end end end %做n次迭代，每次迭代均更新D(i,j)和path(i,j) for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j) 第三讲最短距离问题 一、知识梳理 几何模型1 条件：如图，、是直线同旁的两个定点． 问题：在直线上确定一点，使的值最小． 方法：作点关于直线的对称点，连结交于点， 则的值最小 几何模型2 条件：如图，、是直线异侧的两个定点．且A、 B到距离不相等 问题：在直线上确定一点，使的值最 大 方法：作点关于直线的对称点，连结交于点，则 的值最小 二、方法归纳 对于几何模型1，近年来，除了常见的“一个动点”外，出现了“两个动点”、“三个动点”等变式问题的问题，而解决此类问题的关键在于：找点关于线的对称点，实现“折”转“直”。 对于几何模型2，近年出现的中考题都是直接应用。 三、课堂精讲例题 （一）、题中出现一个动点。 例1、在正方形ABCD中，点E为BC上一定点，且 BE=10,CE=14,P为BD上一动点，求PE+PC最小值。 【难度分级】A类 〖试题来源〗经典例题 〖选题意图〗使学生掌握几何模型1的应用 〖解题思路〗作关于对称点,可以证明在上， 易求 解：作关于对称点 四边形ABCD是正方形 在上，且 即是的最小值 【搭配课堂训练题】 1、已知：抛物线的对称轴为x=-1与轴交于两点，与 轴交于点其中、 （1）求这条抛物线的函数表达式． （2）已知在对称轴上存在一点P，使得的周长最小．请 求出点P的坐标 【难度分级】A类 〖试题来源〗2009年山东济南中考真题。 〖答案〗 解：（1）由题意得解得 ∴此抛物线的解析式为 （2）连结、.因为的长度一定，所以周长最小，就是使最小.点关于对称轴的对称点是点，与对称轴的交点即为所求的点. 设直线的表达式为则 解得 ∴此直线的表达式为 把代入得 ∴点的坐标为 例2：已知：直线与轴交于A，与轴交于 D，抛物线与直线交于A、E两点，与 轴交于B、C两点，且B点坐标为（1，0）． （1）求抛物线的解析式； （2）在抛物线的对称轴上找一点M，使的值最大，求出点M的坐标． 【难度分级】A类 〖试题来源〗2009眉山中考数学真题 〖选题意图〗使学生掌握几何模型2的应用 徐老师： 您好！ 我周六日休息了所以今天才看到您的邮件，抱歉没有及时答复您。 您的问题: 我不明白，如果您的row total不是理解成相加的含义，改如何理解？我想知道它是由哪些数值得到的100％? 我支持您的观点，row total是应该理解成相加的含义，但是这个地方横向相加确实不得100,也不可能都是100，具体什么原因我找了好久也没有找出来，我确实不是很清楚，我需要向美国ITT公司确认一下，非常抱歉。 最小距离分类的时候要设定两个阈值，这两个阈值是必须设定的，那么范围是否在0～255之间？书上写的以DN值的方式输入一个值是否是这个意思？ 您知道，您选择了一类感兴趣区，就有了这类感兴趣区影像DN值在各波段的均值，最小距离分类时，影像中每一个像素归为哪一类就是由像元DN值与该均值的距离来确定的。 如果您不设定任何阈值也是可以的（选择NONE），系统将默认将所有的像元全部按最小距离分类。 如果要对所有的类别使用同一个阈值（选择Single Value），在“Max stdev from Mean”文本框中您可以输入一个标准差。这个标准差是可以按照像元DN值和类别在各波段的均值来计算的，并不是DN值，范围也不是在0~255之间。或者在“Max Distance Error”文本框中输入一个值。这个值就是待分类像元与类别在各波段的均值之间的欧式距离，也不是DN 值，范围也不是在0~255之间，同样是需要计算的。 如果在“Set Max Stdev From Mean”和“Set Max Distance Error”文本框中都设定了阈值，分类就用两者中较小的一个来判定哪些像元将被分类。 一般来说最小距离法误差还是比较大的，这个方法在实际应用中不是很好，建议使用其他方法，如最大似然法、支持向量机分类法等。 best wishes! 仰满荣(Miss Yang ) 实验一 最大最小距离法 一．实验目的 本实验的目的是使学生了解最大最小距离法聚类方法，掌握最大最小距离聚类分析法的基本原理，培养学生实际动手和思考能力，为数据分析和处理打下牢固基础。 二．最大最小距离聚类算法 该算法以欧氏距离为基础，首先辨识最远的聚类中心，然后确定其他的聚类中心，直到无新的聚类中心产生。最后将样本按最小距离原则归入最近的类。 例：样本分布如图所示。 最大最小距离聚类算法步骤如下： ① 给定θ，10<<θ，并且任取一个样本作为第一个聚合中心，11x Z =。 ② 寻找新的集合中心： 计算其它所有样本到1Z 的距离1i D ： 若}{max 11i i k D D =，则取k x 为第二个聚合中心2Z ，62x Z =。 计算所有样本到1Z 和2Z 的距离1i D 和2i D ： 若)},max{min(21i i l D D D =，n i ,....,2,1=，并且12D D l ?>θ，12D 为1Z 和2Z 间距离，则取l x 为第三个集合中心3Z ，73x Z =。【注意：∑=-= -=d i i i i z x Z x D 1 21 11||||||， ||||22Z x D i i -=】 如果3Z 存在，则计算)},,max{min(321i i i j D D D D =，n i ,....,2,1=，若12D D j ?>θ，则建立第四个聚合中心。依次类推，直到最大最小距离不大于12D ?θ时，结束寻找聚合中心的计算。 注意7x 所在第列，29在),min(21i i D D 中为最大的，而且8029?>=θl D ，一 般取2 1 = θ。所以，73x Z =。 这里的例中只有三个集合中心，11x Z =，62x Z =，73x Z =。 ③ 按最近邻原则把所有样本归属于距离最近的聚合中心，得： 1431},,{Z x x x ∈， 262},{Z x x ∈，3109875},,,,{Z x x x x x ∈。 ④ 按照某聚类准则考查聚类结果，若不满意，则重选θ，第一个聚合中心1Z ，返回到②，直到满意，算法结束。 该算法的聚类结果与参数θ和起始点1Z 的选取关系重大。若无先验样本分布知识，则只有用试探法通过多次试探优化，若有先验知识用于指导θ和1Z 选取，则算法可很快收敛。 三．实验内容 见右图所示，为二维点集。 四．实验步骤 1、提取分类特征，确定特征值值域，确定特征空间； 2、编写聚类程序； 3、将所提取的样本的加以聚类； 4、用误差平方和准则（也可选用其他准则）加以评价，直到满意为止。 课程设计任务书 目录 第1章概要设计 (1) 1.1题目的内容与要求 (1) 1.2总体结构 (1) 第2章详细设计 (2) 2.1主模块 (2) 2.2构建城市无向图 (3) 2.3添加城市 (4) 2.4修改城市距离 (5) 2.5求最短路径 (6) 第3章调试分析 (7) 3.1调试初期 (7) 3.2调试中期 (7) 3.3调试末期 (7) 第4章测试及运行结果 (7) 附页（程序清单） (10) 第1章概要设计 1.1题目的内容与要求 内容：给出一张无向图，图上的每个顶点表示一个城市，顶点间的边表示城市间存在路径，边上的权值表示城市间的距离。试编写程序求解从某一个城市出发到达任意其他任意城市的最短路径问题。 要求： 1)能够提供简单友好的用户操作界面，可以输入城市的基本信息，包括城市名 称，城市编号等； 2)利用矩阵保存城市间的距离； 3)利用Floyd算法求最短路径； 4)独立完成系统的设计，编码和调试； 5)系统利用C语言完成； 6)按照课程设计规范书写课程设计报告。 1.2总体结构 本程序主要分为四个模块（功能模块见图1.1）：主模块对整个程序起一主导作用，开始构建一城市无向图，对其进行添加城市顶点，以及对原来的距离数据进行修改，整体构建结束可以实现求一城市到其他城市的最短路径问题。 图1.1 功能模块图 第2章详细设计 2.1主模块 用户根据屏幕上显示的操作提示输入要进行操作的模块，通过调用相对应的模块程序，达到用户所想进行操作。程序的总框架大致分为四个模块：1.建立城市无向图2.添加城市模块3.修改城市距离4.求最短路径。具体实现过程见2.2：建立城市无向图2.3：添加城市2.4：修改城市距离2.5：求最短路径。流程图中通过输入n，由n的值来选择调用相对应子函数，实现所选择的功能，调用完后可以返回调用主函数进行下一次选择，从而实现反复调用子函数而实现四个模块的功能等。 图2.1 主模块流程图 遥感原理与应用 1.试述遥感图像分类的方法，并简单分析各种分类方法的优缺点。答：监督分类：1、最大似然法；2、平行多面体分类法:这种方法比较简单，计算速度比较快。主要问题 是按照各个波段的均值为标准差划分的平行多面体与实际地物类别数据点分布的点群形态不一致，也就造成俩类的互相重叠，混淆不清的情况；3、最小距离分类法:原理简单，分类精度不高，但计算速度快，它可以在快速浏览分类概况中使用。通常使用马氏距离、欧氏距离、计程距离这三种判别函数。主要优点：可充分利用分类地区的先验知识，预先确定分类的类别；可控制训练样本的选择，并可通过反复检验训练样本，以提高分类精度（避免分类中的严重错误）；可避免非监督分类中对光谱集群组的重新归类。主要缺点：人为主观因素较强；训练样本的选取和评估需花费较多的人力、时间；只能识别训练样本中所定义的类别，对于因训练者不知或因数量太少未被定义的类别，监督分类不能识别，从而影响分结果（对土地覆盖类型复杂的地区需特别注意）。 非监督分类：1、ISODATA； 2、K-Mean：这种方法的结果受到所选聚类中心的数目和其初始位置以及模式分布的几何性质和读入次序等因素的影响，并且在迭代的过程中又没有调整类别数的措施，因此不同的初始分类可能会得到不同的分类结果，这种分类方法的缺点。可以通过其它的简单的聚类中心试探方法来找出初始中心，提高分类结果；主要优点：无需对分类区域有广泛地了解，仅需一定的知识来解释分类出的集群组；人为误差的机会减少，需输入的初始参数较少（往往仅需给出所要分出的集群数量、计算迭代次数、分类误差的阈值等）；可以形成范围很小但具有独特光谱特征的集群，所分的类别比监督分类的类别更均质；独特的、覆盖量小的类别均能够被识别。主要缺点：对其结果需进行大量分析及后处理，才能得到可靠分类结果；分类出的集群与地类间，或对应、或不对应，加上普遍存在的“同物异谱”及“异物同谱”现象，使集群组与类别的匹配难度大；因各类别光谱特征随时间、地形等变化，则不同图像间的光谱集群组无法保持其连续性，难以对比。 蚂蚁爬行的最短路径 正方体 4．如图，一只蚂蚁从正方体的底面A点处沿着表面爬行到点上面的B点处，它爬行的最短路线是（） A．A?P?B B．A?Q?B C．A?R?B D．A?S? B 解：根据两点之间线段最短可知选A． 故选A． 2. 如图，边长为1的正方体中，一只蚂蚁从顶点A出发沿着正方体的外表面爬到顶点B的 最短距离是 . 解：如图将正方体展开，根据“两点之间，线段最短”知，线段AB即为最短路线． AB= 5 1 22 2= +． 8. 正方体盒子的棱长为2，BC的中点为M，一只蚂蚁从A点爬行到M点的最短距离为. 解：将正方体展开，连接M、D1， 根据两点之间线段最短， MD=MC+CD=1+2=3， 第6题 第7题 A B 12 1 MD1 =13 2 32 2 2 1 2= + = +DD MD． 5．如图，点A的正方体左侧面的中心，点B是正方体的一个顶点，正方体的棱长为2，一蚂蚁从点A沿其表面爬到点B的最短路程是（） 解：如图，AB=()10 1 2 12 2= + +．故选C． 9．如图所示一棱长为3cm的正方体，把所有的面均分成3×3个小正方形．其边长都为1cm，假设一只蚂蚁每秒爬行2cm，则它从下底面点A沿表面爬行至侧面的B点，最少要用 2.5秒钟． 解：因为爬行路径不唯一，故分情况分别计算，进行大、小比较，再从各个路线中确定最短的路线． （1）展开前面右面由勾股定理得AB= = cm； （2）展开底面右面由勾股定理得AB= =5cm； 所以最短路径长为5cm，用时最少：5÷2=2.5秒． 长方体 10．（2009?恩施州）如图，长方体的长为15，宽为10，高为20，点B离点C的距离为5，一只蚂蚁如果要沿着长方体的表面从点A爬到点B，需要爬行的最短距离是。 解：将长方体展开，连接A、B，根据两点之间线段最短，AB= =25． #include 最短距离算法（Dijkstra）设计与编程实现 所在系（院）： 专业： 班级： 学号： 姓名： 绪论 随着知识经济的到来，信息将成为人类社会财富的源泉，网络技术的飞速发展与广泛应用带动了全社会对信息技术的需求，最短路径问题作为许多领域中选择最有问题的基础，在电子导航，交通旅游，城市规划以及电力、通讯等各种管网、管线的布局设计中占有重要地位。 最短路径，顾名思义就是在所有的路径中找到距离最短的路径，而我们所说的最短路径通常不仅仅指地理意义的距离最短，还可以引申到其他的度量，如时间、费用、路线容量等。相应地，最短路径问题就成为最快路径问题，最低费用问题等，所以我们所说的最短路径也可以看做是最优路径问题。 最短路径问题在交通网络结构的分析，交通运输线路的选择，通讯线路的选择与维护，运输货流的最小成本分析，城市公共交通网络的规划等，都有直接应用的价值。最短路径问题在实际中还应用于汽车导航系统以及各种应急系统等，这些系统一般要求计算出到出事点的最佳线路，在车辆行驶过程中还需要实时的计算出车辆前方的行驶路线，这就决定了最短路径问题的实现应该是高效的。 最短路径问题一直是计算机学科，运筹学，交通工程学，地理信息学等学科的一个研究热点。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断的涌现。 1 定义概览 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。 问题描述：在无向图G=(V,E) 中，假设每条边E[i] 的长度为w[i]，找到由顶点V0 到其余各点的最短路径。（单源最短路径） 2 概要设计和数据结构选择 按路径长度递增的顺序产生最短路径。通过以上对问题的分析和任务的理解，设计出一个大体的模块和程序流程。 2.1程序中涉及到的结构体及子函数： 2.1.1结构体： 本程序设计使用了以下结构体： struct vertex { int num; //顶点编号 int data; //顶点信息 }; //顶点类型 typedef struct graph { int n; //图中顶点个数 int e; //图中边的个数 struct vertex vexs[MAXVEX]; //顶点集合 int edges[MAXVEX][MAXVEX]; //边的集合 }AdjMaxix; //图的邻接矩阵类型 2.1.2子函数： 设计本程序需分成几个模块，要用到以下几个子函数： AdjMaxix creatmgraph() //通过用户交互产生一个有向图的邻接矩阵； void dispmgraph(AdjMaxix adj)//用于输出一个有向图的邻接矩阵； 初中数学“最短距离”问题分类及解题策略 绵阳市游仙区新桥中学数学教研组 何道华 最短距离问题贯穿于初中几何学习的整个过程，由初一上册的“两点之间的距离”，初一下册的“点到直线的距离”、“平移”等基本问题开始，到初二上册的轴对称，初二下册的直角三角形的有关计算，再到初三上册的旋转等，都涉及到研究距离最短的问题。虽然解决此类问题的依据很简单，主要是线段最短、垂线段最短以及三角形中的三边大小关系等原理，但图形千变万化，经常与三角形、四边形、圆及抛物线等问题综合考察，涉及的知识背景多，动点、动线的位置不确定，往往需要作平移、对称、旋转等辅助线才能发现线段之间的联系，找到最短距离的位置后，通常还需要进行准确的计算。通过这类问题的解决，能培养学生动手操作、逻辑思考、严密计算等能力，是各类考试的热点同时也是难点问题。 一、最短距离的基本原理 1、两点间的距离是指连接两点的 的长度。 在连接两点的所有线中， 最短。简称 。 2、点到直线的距离是指点到直线的 的长度。 在连接直线外一点与直线上一点的所有线段中， 最短。 简称 。 3、两平行线间的距离是指平行线中一条直线上的任意一点到另一直线的 的长度。 4、三角形中，两边之和大于第三边，两边只差小于第三边。 由任意三点连接的三条线段中，另两边之差≤第三边≤另两边之和。 二、题型及解题策略 最短时的图形。 求一只蚂蚁从点沿正方体表面爬到 两小区居民散步。怎样规划路线，才能使所建的道路之和最短？ 在 值最小。 如图 CB=4 ⊙ CB 的值最小。 在△ABC 中找一点P ，使它到三顶点的距离之和最短（即费马点）。 三、典型例题 1、如图，直线33 3 -= x y 与x 轴、y 轴分别交于点A 、B ，请在x 轴上求一点C ，使点C 到点B 和直线AB 的距离之和最短。 分析：虽然线段CB 和CD 同在一个三角形，但这个三角形三边都不固定。把线段BC 翻折到B ′C ，从而当B ′、C 、D 三点在同一直线上，且该直线垂直于AB 时，点C 到点B 和直线AB 的距离之和最短。 解：作点B 关于x 轴的对称点B ′，再作B ′E ⊥AB 于E ，交x 轴于点F ，连接B ′C ， ∴B ′C=BC ， ∴CB+CD=B ′C+CD 三角形平面上到三个顶点距离之和最小问题 △ABC平面上到三个顶点距离之和PA+PB+PC最小的P点，必满足： （1）当△ABC最大内角小于120°时，则P满足∠BPC=∠CPA=∠APB=120°； P点寻找方法在△ABC外作正三角形△ABD和△AEC，这两个正三角形的外接圆交点就是所求之点P（事实上该点也恰好是直线BE和CD的交点）。 （2）当△ABC最大内角不小于120°时，最大角的顶点就是使到三个顶点距离之和 PA+PB+PC最小的P点。 【证明】这里首先我们看三个基本结论： （一）若A、B为直线MN同侧两点，直线MN上使PA+PB最小的P点满足满足光学反射原理（费尔马反射定律）：入射角=反射角。（如果是加权的问题：直线MN上使 a PA+ b PB 最小的P点满足满足光学折射原理（费尔马折射定律） （二）椭圆的光学性质：椭圆某焦点A处发出的光线经椭圆周任一点P“反射”后，必到达另一个焦点B， （三）P点必在△ABC形内（包括边界），不可能在形外。若P在形外： ①P到离它最近一条边的投影点不在这条边内。比如下图，当然是不合适的。取A为P 就更好，PB+PC＞AB+AC，PA+PB+PC＞0(即AA)+AB+AC。 ②P到离它最近一条边的投影点在这条边上（可以是端点），例如下图P在AB上的投影P'在AB上，则 PA＞P'A，PB+PC＞P'B+P'C ? PA+PB+PC＞P'A+P'B+P'C。 现在，着手证明。 （1）假如△ABC最大内角小于120°，为证明∠BPC=∠CPA=∠APB=120°，我们就先来证明 ∠APB=∠APC。 当PB+PC值确定时，P点在以B、C为焦点的椭圆上，在椭圆上使PA最小的Ｐ点应该使PA垂直于椭圆在P点处的切线MN（即：就是圆A与椭圆相切于P），根据椭圆的光学性质，必有∠APB=∠APC。（更充分的理由是反证法，任取另一点P2，显然AP＜AP2，而PB+PC=P2B+P2C，所以PA+PB+PC＜P2A+P2B+P2C）基于最大最小距离的人脸识别
遥感概述考试6第六章
最大最小距离算法以及实例
最短距离型问题的建模方法
最大最小距离算法
监管分类中常用的具体分类方法
算法导论求n个点的最小距离
算法导论求n个点的最小距离
数学建模任意两点间最短距离
第三讲 最短距离问题
31.ENVI 最小距离分类阈值
实验1 最大最小距离法
弗洛伊德算法求解最短路径
试述遥感图像分类的方法,并简单分析各种分类方法的优缺点。
(完整版)勾股定理--最短距离问题
最大最小距离算法
最短路径算法
初中数学最短距离问题分类及解题策略
三个顶点距离之和最小问题
相关主题
文本预览