系统聚类分析课程设计
《空间分析》
系统聚类算法及编程实现
学院：地质工程与测绘学院
专业：遥感科学与技术
班级：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 类，m 为已知数。 第一步：适当地选取m 个类的初始中心Z 1(1),Z 2(1), ···，Z M (1)，初始中心的选
择对聚类结果有一定的影响，初始中心的选择一般有如下几种方法：
1）
2） 根据问题的性质和经验确定类别数m ，从数据中找出直观上看来比较适合的m 个类的初始中心。 将全部数据随即地分为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)=1N j X ∈S (j K ) ∑X
式中，N j 为S j (k)类中的样本数。Z j (k+1)是按照使J 最小的原则确定的，J 的表达式
为： J=∑j =1m 2X ∈S (j k ) ∑X -Z j (k +1)
第四步：对于所有的i=1,2···，m ，如果Z i (k+1)=Zi (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
switch mindis
case 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;
end
end
%%重新计算聚类中心
%[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
%fsample
ncentre1 = 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*n
switch flag(i)
case 1
sample(i) = 60;
case 2
sample(i) = 120;
case 3
sample(i) = 180; case 4
sample(i) = 240;
end
end
t = 1;
else
ocentre1 = ncentre1;
ocentre2 = ncentre2;
ocentre3 = ncentre3;
ocentre4 = ncentre4;
end
end
sample = uint8(sample);
sample = reshape(sample,m,n);
imshow(sample);
3.2.2编程操作结果
实验调用前图片：
实验调用后结果截图图片：
第四章 K-均值算法应用与优缺点
4.1K-均值聚类法的应用
① 在机械设备铁路监测技术中的应用。
② 在人力资源管理中的应用。
③ 在商业银行客户分类中的应用。 4.2K-均值聚类法的优缺点 缺点
① 在 K-means 算法中 K 是事先给定的，这个 K 值的选定是非常难以估计的。
② 在 K-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。
③ 从 K-means 算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。 优点：
本算法确定的K 个划分到达平方误差最小。当聚类是密集的，且类与类之间区别明显时，效果较好。对于处理大数据集，这个算法是相对可伸缩和高效的，计算的复杂度为O(NKt)，其中N 是数据对象的数目，t 是迭代的次数。一般来说，K
第五章 课程设计总结
通过此次课程设计，对空间分析中的聚类分析有了更一步的了解和体会，尤其是对系统聚类分析有了深刻的掌握，基于Matlab 软件的方便性和语言的简洁易懂性，基本完成了该次课程设计的程序编写。
当然，在课程设计主要是依据《空间分析》及《模式识别导论》两本所学课程教材中的聚类分析章节来参考编写的，空间聚类可以采用不同的算法过程。在分析之初假定n 个点自成一类，然后逐步合并，这样在聚类的过程中，分类将越来越少，直至聚至一个适当的分类数目，这一聚类过程称之为系统聚类。显然，距离是事物之间差异性的测度，差异性越大，则相似性越小，所以距离是系统聚类分析的依据和基础。设计算法思想和选用其中的最短距离的原则来进行系统聚类，我们已经指出系统聚类方法首先将n 个空间点看做是n 个子群，然后根据所选用的聚类统计量来计算n 个子群之间的关系。对于距离，计算n 个子群两两之间的距离，首先选择距离最近的两个子群（点）归为一个新的子群，这样就得到
n-1个子群两两之间的聚类统计量，继续选择距离最近的子群合并，再得到n-2个子群……，依此类推，直到所有的子群全部合并。
设计的程序也有不足之处，对于数据量大的空间聚类显得不实用，仅仅较适合数据小的系统聚类，如上述小数据量的图片的聚类分析，对于提高程序空间聚类分析能力，还待进一步的研究。
主要参考文献
1 郭仁忠，空间分析，北京：高等教育出版社，2001
2 范久伦，赵凤，等. 模式识别导论，西安：西安电子科技大学出版社，2012.5 3 张强，王正林，精通 MATLAB 图像处理，电子工业出版社，2009
4 张克权，组合指标分类方法简介与分析，北京：测绘出版社，1980
5 郭仁忠，张克权.q 型聚类分析中变量相关性的处理方法分析，武汉测绘科技大学报，1987，12（3）
6 薛山，MATLAB 基础教程，北京：清华大学出版社，2011