1、聚类分析课程设计空间分析系统聚类算法及编程实现学院:地质工程与测绘学院专业:遥感科学与技术班级:2011260601学号:学生姓名:指导老师:第1章前言 3第2章 算法设计背景 32.1聚类要素的数据处理 32.2距离的计算 5第3章算法思想与编程实现 53.1 算法思想 53.2用Matlab编程实现 6第4章课程设计总结 10主要参考文献 11第一章 前言本课题是根据李斌老师所教授的空间分析课程内容及要求而选定的, 是对于系统聚类算法的分析研究及利用相关软件的编程而实现系统聚类。研 究的是系统聚类算法的分析及编程实现,空间聚类的目的是对空间物体的集 群性进行分析,将其分为几个不同的子群(类
2、)。子群的形成的是地理系统运 作的结果,根据此可以揭示某种地理机制。此外,子群可以作为其它分析的 基础,例如,公共设施的建立一般地说是根据居民点群的分布,而不是具体 的居民住宅的分布来布置的,因此需要对居民点群进行聚类分析以形成若干 居民点子群,这样便于简化问题,突出重点。空间聚类可以采用不同的算法过程。在分析之初假定 n个点自成一类,然后逐步合并,这样在聚类的过程中,分类将越来越少,直至聚至一个适当的分 类数目,这一聚类过程称之为系统聚类。常见的聚类分析方法有系统聚类法、 动态聚类法和模糊聚类法等。下面主要介绍系统聚类算法,并基于 Matlab软件来实现算法的编程。第二章算法设计背景2.1聚
3、类要素的数据处理假设有m个聚类的对象,每一个聚类对象都有个要素构成。它们所对应的 要素数据可用表3.4.1给出。在聚类分析中,常用的聚类要素的数据处理方 法有如下几种。聚类对象要 素阳 也 A , 心 A ,1殆知 A 切h * g2忑21 “22 A 兀J A f 孟2抑kM M M M M M兀L X垢 八 龙扩 h、xinkM M M M M M0 g A , % A f g总和标准化殆= = 12A,淤;j = 1,2,A ,方)2i/i-l且乞对i (7 = 12A E)i-l极大值标准化经过这种标准化所得的新数据,各要素的极大值为 1,其余各数值小于i经过这种标准化所得的新数据,各
4、要素的极大值为 1,极小值为0,其余的数值 均在0与1之间。2.2距离的计算距离是事物之间差异性的测度,差异性越大,则相似性越小,所以距离是系统 聚类分析的依据和基础。(D巨离3明科夫斯基距禽应材=221爲取_現隅L.j4切比雪夫距离当明科夫斯基距戸T8时裏有选择不同的距离,聚类结果会有所差异。在地理分区和分类研究中,往往采用 几种距离进行计算、对比,选择一种较为合适的距离进行聚类第三章算法思想与编程实现3.1算法思想我们已经指出系统聚类方法首先将 n个空间点看做是n个子群,然后根据所选用的聚类统计量来计算n个子群之间的关系。对于距离,计算 n个子群两两之间的距离,首先选择距离最近的两个子群(
5、点)归为一个新的子群, 这样就得到n-1个子群两两之间的聚类统计量,继续选择距离最近的子群合 并,再得到n-2个子群,依此类推,直到所有的子群全部合并。3.2用Matlab编程实现运用Matlab中的一些基本矩阵计算方法,通过自己编程实现聚类算法,在 此只讨论根据最短距离规则聚类的方法。调用函数:minl.m求矩阵最小值,返回最小值所在行和列以及值的大小min2.m 比较两数大小,返回较小值stdl.m 用极差标准化法标准化矩阵dsl.m 用绝对值距离法求距离矩阵cluster.m 应用最短距离聚类法进行聚类分析prin tl.m 调用各子函数,显示聚类结果聚类分析算法假设距离矩阵为vecto
6、r ,a阶,矩阵中最大值为max,令矩阵上三角元素等于max聚类次数=a-1,以下步骤作a-1次循环:求改变后矩阵的阶数,计作c求矩阵最小值,返回最小值所在行 e和列f以及值的大小gfor l=1:c, 为 vector(c+1,l) 赋值,产生新类令第c+1列元素,第e行和第f行所有元素为,第e列和第f列所有元素 为max源程序如下:%std1.m,用极差标准化法标准化矩阵fun cti on std=std1(vector)max=max(vector); %对歹U求最大值min=mi n(vector);a,b=size(vector); %巨阵大小,a为行数,b为列数for i=1:a
7、for j=1:bstd(i,j)= (vector(ij)-mi n(j)/(max(j)-mi n(j);endend%ds1.m用绝对值法求距离fun cti on d=ds1(vector);a,b=size(vector);d=zeros(a);for i=1:afor j=1:afor k=1:bd(i,j)=d(i,j)+abs(vector(i,k)-vector(j,k);endendendfprintf( 绝对值距离矩阵如下:n);disp(d)%mi nl.m求矩阵中最小值,并返回行列数及其值function v1,v2,v3=min1(vector);%v1 为行数,v
8、2 为列数,v3 为其值v,v2=mi n( mi n(vector);v,v1=mi n( mi n(vector);v3=min(min( vector);%min2.m比较两数大小,返回较小的值fun cti on v仁 min( v2,v3);if v2v3v1=v3;elsev仁 v2;end%cluster.m,最短距离聚类法function result=cluster(vector);a,b=size(vector);max=max(max(vector);for i=1:afor j=i:bvector(i,j)=max;endend;for k=1:(b-1)c,d=siz
9、e(vector);fprintf(第%g 次聚类:n,k);e,f,g=mi n1(vector);fprintf( 最小值=%g將第%g区和第%g区并为一类,记作G%gnn,g,e,f,c+1);for l=1:cif l=mi n2(e,f)vector(c+1,l)=mi n2(vector(e,l),vector(f,l);elsevector(c+1,l)=mi n2(vector(l,e),vector(l,f);endend;vector(1:c+1,c+1)=max;vector(1:c+1,e)=max;vector(1:c+1,f)=max;vector(e,1:c+1)
10、=max;vector(f,1:c+1)=max;end%printl,调用各子函数function print=print1(filename,a,b); %a 为地区个数,b 为指标数fid=fope n(filen ame,r)vector=fsca nf(fid,%g,a b);fprintf( 标准化结果如下:n)v1=std1(vector)v2=ds1(v1);cluster(v2);%输出结果prin t1(fname,9,7)第四章课程设计总结通过此次课程设计,对空间分析中的聚类分析有了更一步的了解和体会,尤 其是对系统聚类分析有了深刻的掌握,基于 Matlab软件的方便性和
11、语言的简洁 易懂性,基本完成了该次课程设计的程序编写。当然,在课程设计主要是依据空间分析该书中聚类分析章节中的系统聚 类分析来,空间聚类可以采用不同的算法过程。在分析之初假定n个点自成一类, 然后逐步合并,这样在聚类的过程中,分类将越来越少,直至聚至一个适当的分 类数目,这一聚类过程称之为系统聚类。显然,距离是事物之间差异性的测度, 差异性越大,则相似性越小,所以距离是系统聚类分析的依据和基础。 设计算法 思想和选用其中的最短距离的原则来进行系统聚类, 我们已经指出系统聚类方法 首先将n个空间点看做是n个子群,然后根据所选用的聚类统计量来计算 n个子 群之间的关系。对于距离,计算n个子群两两之
12、间的距离,首先选择距离最近的 两个子群(点)归为一个新的子群,这样就得到n-1个子群两两之间的聚类统计 量,继续选择距离最近的子群合并,再得到 n-2个子群,依此类推,直到所 有的子群全部合并。设计的程序也有不足之处,对于数据量大的空间聚类显得不实用, 仅仅较适 合数据小的系统聚类,即一般数据量的空间聚类分析,对于提高程序空间聚类分 析能力,还待进一步的研究。主要参考文献1郭仁忠,空间分析,北京:高等教育出版社, 20012张强,王正林,精通 MATLAB图像处理,电子工业出版社,20093张克权,组合指标分类方法简介与分析,北京:测绘出版社, 19804郭仁忠,张克权.q型聚类分析中变量相关性的处理方法分析,武汉测绘科技 大学报,1987,12 (3)5薛山,MATLABS础教程,北京:清华大学出版社,2011