《空间分析》系统聚类算法及编程实现学院：地质工程与测绘学院专业：遥感科学与技术班级：2011260601学号：学生姓名：指导老师：李斌目录第1章前言 (3)第2章算法设计背景 (3)2.1 聚类要素的数据处理 (3)2.2距离的计算 (5)第3章算法思想与编程实现 (5)3.1 算法思想 (5)3.2 用Matlab编程实现 (7)3.2.1 程序代码 (7)3.2.2 编程操作结果 (12)第4章K-均值算法应用与优缺点 (13)4.1 K-均值聚类法的应用 (13)4.2 K-均值聚类法的优缺点 (14)第5章课程设计总结 (14)主要参考文献 (15)第一章前言本课题是根据李斌老师所教授的《空间分析》课程内容及要求而选定的，是对于系统聚类算法的分析研究及利用相关软件的编程而实现系统聚类。

研究的是系统聚类算法的分析及编程实现，空间聚类的目的是对空间物体的集群性进行分析，将其分为几个不同的子群（类）。

子群的形成的是地理系统运作的结果，根据此可以揭示某种地理机制。

此外，子群可以作为其它分析的基础，例如，公共设施的建立一般地说是根据居民点群的分布，而不是具体的居民住宅的分布来布置的，因此需要对居民点群进行聚类分析以形成若干居民点子群，这样便于简化问题，突出重点。

空间聚类可以采用不同的算法过程。

在分析之初假定n个点自成一类，然后逐步合并，这样在聚类的过程中，分类将越来越少，直至聚至一个适当的分类数目，这一聚类过程称之为系统聚类。

常见的聚类分析方法有系统聚类法、动态聚类法和模糊聚类法等。

下面主要介绍系统聚类算法，并基于Matlab软件用K-means算法(即k-均值算法)来实现系统聚类的算法编程。

第二章算法设计背景2.1聚类要素的数据处理假设有m 个聚类的对象，每一个聚类对象都有个要素构成。

它们所对应的要素数据可用表3.4.1给出。

在聚类分析中，常用的聚类要素的数据处理方法有如下几种。

①总和标准化②标准差标准化③极大值标准化经过这种标准化所得的新数据，各要素的极大值为1，其余各数值小于1。

④极差的标准化经过这种标准化所得的新数据，各要素的极大值为1，极小值为0，其余的数值均在0与1之间。

2.2距离的计算距离是事物之间差异性的测度，差异性越大，则相似性越小，所以距离是系统聚类分析的依据和基础。

选择不同的距离，聚类结果会有所差异。

在地理分区和分类研究中，往往采用几种距离进行计算、对比，选择一种较为合适的距离进行聚类。

第三章算法思想与编程实现3.1算法思想我们已经指出系统聚类方法首先将n个空间点看做是n个子群，然后根据所选用的聚类统计量来计算n个子群之间的关系。

对于距离，计算n个子群两两之间的距离，首先选择距离最近的两个子群（点）归为一个新的子群，这样就得到n-1个子群两两之间的聚类统计量，继续选择距离最近的子群合并，再得到n-2个子群……，依此类推，直到所有的子群全部合并。

K-means算法是硬聚类算法，是典型的局域原型的目标函数聚类方法的代表，它是数据点到原型的某种距离作为优化的目标函数，利用函数求极值的方法得到迭代运算的调整规则。

K-means算法以欧式距离作为相似度测度，它是求对应某一初始聚类中心向量V最有分类，使得评价指标J最小。

算法采用误差平方和准则函数作为聚类准则函数。

K-均值算法的聚类准则是使每一聚类中，多模式点到该类别的中心的距离的平方和最小。

其基本思想是：通过迭代，主次移动各类的中心，直到得到最好的聚类为止。

其算法框图如图所示。

开始选择m个中心Z1,Z2，···Zm所有像元分到m个集群中心计算新的集群中心聚类中心不变结束具体的计算步骤如下：假设图像上的目标要分为m 类，m 为已知数。

第一步：适当地选取m 个类的初始中心Z 1(1),Z 2(1),···，Z M (1)，初始中心的选择对聚类结果有一定的影响，初始中心的选择一般有如下几种方法：1）根据问题的性质和经验确定类别数m ，从数据中找出直观上看来比较适合的m 个类的初始中心。

2） 将全部数据随即地分为m 个类型，计算每类的重心，将这些重心作为m 个类的初始中心。

第二步：在第k 次迭代中，对任一样本X 按如下的方法把它调整到m 个类别中的某一类别中去。

对于所有的i ≠ j, i = 1,2,···，m, 如果∥X-Z j (k)∥﹤∥X-Z i (k)∥，则X ∈S j (k)其中S j (k)是以Z i (k)为中心的类。

第三步：由第二步得到S j (k)类新的中心Z j (k),Z j (k)=∑∈)(1K j S X j X N式中，N j 为S j (k)类中的样本数。

Z j (k+1)是按照使J 最小的原则确定的，J 的表达式为： J=21)1()(∑∑=∈+-m j S X k j k j Z X第四步：对于所有的i=1,2···，m ，如果Z i (k+1)=Z i (k),则迭代结束，否则转到第二步继续迭代。

这种算法的结果受到所选聚类中心的数目和其初始位置以及模式分布的几何性质和读入次序等因素的影响，并且在迭代过程中又没有调整类数的措施，因此可能产生不同的初始分类得到不同的结果，这是这种方法的缺点。

可以通过其他的简单的聚类中心试探方法，如最大距离法，找出初始中心，提高分类效果。

3.2用 Matlab 编程实现3.2.1程序代码对于上述的K-mean 算法用Matlab 软件实现编程并调用数据小的图片进行聚类分析及编程是否正确性的检测。

具体程序代码如下：%%读取图片Imag = imread('hand.jpg'); %%只能读取三个波段sample = rgb2gray(Imag); %%将彩色图片转换为灰度图片[m n] = size(sample); %%读取图片的维数sample = reshape(sample,m*n,1); %%将矩阵变换为m*n行1列的向量k = 4; %%分成4类t = 0; %%控制循环次数flag = 0; %%一个和sample等维数的标记向量ocentre1 = 80; %%选取第1类聚类中心ocentre2 = 160; %%选取第2类聚类中心ocentre3 = 220; %%选取第3类聚类中心ocentre4 = 255; %%选取第4类聚类中心sample = double(sample); %%将uint8类型转换为double型while t == 0%fsample1 = 0;%fsample2 = 0;%fsample3 = 0;%fsample4 = 0;fsample = zeros(4,1);num = zeros(4,1);dis = zeros(1,4);for i = 1:m*n%a = 5 - 2;%b = 2 - 5;dis(1) = abs(sample(i) - ocentre1); %%求到第1个聚类中心距离 dis(2) = abs(sample(i) - ocentre2); %%求到第2个聚类中心距离 dis(3) = abs(sample(i) - ocentre3); %%求到第3个聚类中心距离 dis(4) = abs(sample(i) - ocentre4); %%求到第4个聚类中心距离 mindis = min([dis(1) dis(2) dis(3) dis(4)]); %%求最小的距离%选取最小值，第一个值给dis1，第二个值给dis2，判断dis2<dis1，则给dis2值于dis1，计算第三个距离给dis2，返回第三步，循环switch mindiscase dis(1)%flag = cat(1,flag,1); %%将标记数组赋值1，该点属于第1类%fsample1 = cat(1,fsample1,sample(i));flag(i) = 1;fsample(1) = fsample(1) + sample(i);num(1) = num(1) + 1;case dis(2)%flag = cat(1,flag,2); %%将标记数组赋值2，该点属于第2类%fsample2 = cat(1,fsample2,sample(i));flag(i) = 2;fsample(2) = fsample(2) + sample(i);num(2) = num(2) + 1;case dis(3)%flag = cat(1,flag,3); %%将标记数组赋值3，该点属于第3类%fsample3 = cat(1,fsample3,sample(i));flag(i) = 3;fsample(3) = fsample(3) + sample(i);num(3) = num(3) + 1;case dis(4)%flag = cat(1,flag,4); %%将标记数组赋值4，该点属于第4类%fsample4 = cat(1,fsample4,sample(i));flag(i) = 4;fsample(4) = fsample(4) + sample(i);num(4) = num(4) + 1;endend%%重新计算聚类中心%[m1 n1] = size(fsample1);%[m2 n2] = size(fsample2);%[m3 n3] = size(fsample3);%[m4 n4] = size(fsample4);%ncentre1 = sum(fsample1)/(m1 - 1);%ncentre2 = sum(fsample2)/(m2 - 1);%ncentre3 = sum(fsample3)/(m3 - 1);%ncentre4 = sum(fsample4)/(m4 - 1);%flag%fsamplencentre1 = fsample(1)/num(1);ncentre2 = fsample(2)/num(2);ncentre3 = fsample(3)/num(3);ncentre4 = fsample(4)/num(4);%flag(1) = [];if ncentre1 == ocentre1 && ncentre2 == ocentre2... && ncentre3 == ocentre3 && ncentre4 == ocentre4 for i = 1:m*nswitch flag(i)case 1sample(i) = 60;case 2sample(i) = 120; case 3sample(i) = 180; case 4sample(i) = 240; endendt = 1;elseocentre1 = ncentre1;ocentre2 = ncentre2;ocentre3 = ncentre3;ocentre4 = ncentre4;endendsample = uint8(sample);sample = reshape(sample,m,n); imshow(sample);3.2.2编程操作结果实验调用前图片：实验调用后结果截图图片：第四章 K-均值算法应用与优缺点4.1K-均值聚类法的应用①在机械设备铁路监测技术中的应用。