聚类分析算法文档.docx
《聚类分析算法文档.docx》由会员分享，可在线阅读，更多相关《聚类分析算法文档.docx（12页珍藏版）》请在冰点文库上搜索。
聚类分析算法文档
聚类算法
1.引言
在古老的分类学中，人们主要靠经验和专业知识进行定性分析，如黑人，白人，黄种人，我们凭视觉感观就能做出分类，很少利用数学方法，随着科学的发展，分类要求越来越高以致靠经验和专业知识不能进行确切的科学分类；于是数学这个定量化的有力工具便被引进分类科学中来，形成了数值分析学，近20年来，多元统计分析技术被引进到分类学中，于是从数值分析学中逐渐地分离出来聚类分析这个新的分支。
聚类分析方法应用广泛，已经被广泛应用于考古学，地质学，天气预报，作物品种分类，土壤分类，微生物分类，就是在经济管理，社会统计部门，也用到聚类分析进行定量分类。
如何对事物进行分类呢？
我们知道，同类事物具有很强的相似性，因此我们可以用相似性统计量这个度量标准来作为事物分类的依据，等价说法就是同类事物之间的距离应该很小，因此我们可以用距离统计量来作为分类的依据。
若样品是一个向量则可以用相似系数统计量来进行分类。
根据研究的关系不同我们可以选取不同的方法。
当研究样品与样品之间的关系时我们选取距离系数统计量或者相似系数统计量作为分类依据，称为Q型聚类法。
当研究的是变量之间的关系时可以采用相关系数统计量作为分类依据，这种方法称为R型聚类。
2.距离系数发聚类的基本原理
设有n个样品，分别测定了m个特征变量。
如果将n个样品看成m维空间的一个点或者看成m维空间的n个点失。
则在m维空间可以定义一种距离，该距离应满足如下四个条件，若dij表示第i个样品和第j个样品之间的距离，则有
a）dij==0时，样品i与j恒等；
b）对一切i与j，dij>=0;
c）dij=dji;
d）dij<=dik+djk;
由此可知样品之间的距离越小，他们之间的相似程度越高；反之，距离越大，则表明两样品之间的相似程度越低，由此，可以用样品之间的距离来分类。
3.聚类分析算法流程
3.2程序实现步骤
（1）对数据进行正规化处理
（2）计算出距离系数矩阵
（3）开始聚类
（4）重复第一步找出出最小值
（5）合并最小值所对应的列数据重复第二步
（6）循环前面几步直到所有的样品合成一类
3.3数据准备与预处理
将要处理的数据进行整理按同种样品同种特征变量表格化
4聚类算法的程序实现
4.1程序的使用说明
1．程序采用Matlab语言，样品间关系可采用欧氏距离、标准化欧氏距离、马氏距离、布洛克距离、明可斯基距离，类间距离可应用最短距离法进行聚类；
2．gg1data——Matlabdatafile（Mat文件），存放原始数据矩阵XM×N；
3．Matlab函数：
pdist（X,‘metric’）——使用metric指定的方法计算数据矩阵X中对象之间的距离。
metric可以是下面字符串中的任意一个：
①’Euclid’——欧氏距离（默认选项）；
②’Seuclid’——标准化欧氏距离;
③’Mahal’——马氏距离；
④’CityBlock’——布洛克距离；
⑤’Minkowski’——明可斯基距离；
Y=pdist（X,’minkowski’,p）——使用明可斯基距离计算X数据矩阵中对象之间的距离。
P为明可斯基距离计算过程中的幂次，默认值为2。
dendrogram（Z）——输出冰状图。
4.2程序源代码
functionggl（x,M,N）
Rmin=min（x'）;%变量初始化
Gmax=max（x'）;
A=M;
u=1;
%进行数据标准化
XXX=（x'-Rmin（ones（A,1）,:
））./（Gmax（ones（A,1）,:
）-Rmin（ones（A,1）,:
））;%用书上公式5.3对数据进行标准化
X=XXX'
XX（1,:
）=1:
M;%矩阵XX的第一行为系数
XX（2:
N+1,:
）=X;%从第二行开始矩阵XX为标准化矩阵X的数据
w=zeros（4,A）;%定义一个新矩阵
t=1;
YY=pdist（X'）/sqrt（N）;%计算距离系数矩阵
SS=squareform（YY）;%将yy强制转化成上三角矩阵
%输出距离系数矩阵
S=SS（:
1:
A）%将矩阵SS赋给S
while（M~=1）
fori=1:
M
j=i;
S（j,j）=1000000;
end%将对角线元素赋值成一个比较大的值这样在矩阵求最小值的时候避免对角线元素为零带来的错误
r=A;
s=A;
[y,a]=min（S）;%求矩阵最小元素及其所在的行
[ymin,L]=min（y）;
fori=1:
M;
if（y（i）==ymin）
R=a（i）;
break
end%求出矩阵最小值所在的列
end
%输出距离系数矩阵中最小元素所在的行和列
L=min（L,R）%将行和列的最小值赋值给L
G=max（L,R）%将行和列的最大值赋值给G
A1=（XX（1,L）~=w（1,r））;%最小值说对应得元素不等于w第一行最后一个中的元素时为1
B1=（r>1）;%r>1时B等于l
whileand（A1,B1）%计算当AB为真时计算最小元素不等于w中的元素时若等于计录出最后一次循环的r
r=r-1;
A1=（XX（1,L）~=w（1,r））;
B1=（r>1）;
end
AA=（XX（1,G）~=w（1,s））
w（1,s）
B2=（s>1）
whileand（AA,B2）%当AAB为真时计算最大元素不等于w中的元素若等于最后一次循环时候的s
s=s-1;
AA=0;
AA=（XX（1,G）~=w（1,s））;
B2=（s>1）;
end
s
E=（r==1）%当r==1时E=1与上面的rs对应即若上面循环不能循环到最后一次即r==1时E=0
F=（s==1）%当s==1时F=1
C=and（A1,E）%当AE为真时C=1
D=and（AA,F）%当AAF为真时D=1
ifand（C,D）%假如CD都为真时执行
X（:
L）=（X（:
L）+X（:
G））/2;%求两列距离系数矩阵的平均值
w（1,u）=XX（1,L）%最小值元素赋值给W的第一个元素第二次运算的时候赋值给第二个元素以此类推
w（2,u）=XX（1,G）%最大值赋值给第二行元素
w（3,u）=2%将权值赋值给第三行个元素
w（4,u）=A+u%将新归类的数命名并赋值给第四行
ZZ=[w（1,u）,w（2,u）,ymin]%将最小元素的最小值最大值和值赋值给w第四行
Z（t,:
）=ZZ%将zz赋值给z
t=t+1
u=u+1
elseif（D）%当C假D真时执行
X（:
L）=（X（:
L）*w（3,r）+X（:
G））/（w（3,r）+1）;%当最小元素所在的行是新归成类的时候乘以该类的数目即权数
w（1,u）=XX（1,L）;%同上
w（2,u）=XX（1,G）;
w（3,u）=w（3,r）+1;
w（4,u）=A+u;
Z（t,:
）=[w（4,r）,w（2,u）,ymin];
t=t+1;
u=u+1;
elseif（C）
X（:
L）=（X（:
L）+X（:
G）*w（3,s））/（w（3,s）+1）;%同上但是是最大值所在位置是已归类的
w（1,u）=XX（1,L）;%同上
w（2,u）=XX（1,G）;
w（3,u）=w（3,s）+1;
w（4,u）=A+u;
ZZ=[w（1,u）,w（4,s）,ymin];
Z（t,:
）=ZZ;
t=t+1;
u=u+1;
else
X（:
L）=（X（:
L）*w（3,r）+X（:
G）*w（3,s））/（w（3,r）+w（3,s））;%最大值最小值所在处都是已经归了类的时候最大最小值元素都要乘以前面各自归类的个数
w（1,u）=XX（1,L）;%同上
w（2,u）=XX（1,G）;
w（3,u）=w（3,r）+w（3,s）;
w（4,u）=A+u;
Z（t,:
）=[w（4,r）,w（4,s）,ymin];
t=t+1;
u=u+1;
end
forq=G:
M-1%将最大值所在的行向前移一位
X（:
q）=X（:
q+1）
XX（:
q）=XX（:
q+1）;
end
X（:
M）=0;%最后一行的元素赋值为零
M=M-1;%将M减1用于下一步计算
if（M~=1）
X=X（:
1:
M）
YY=pdist（X'）/sqrt（N）;%计算合并标准化矩阵的距离系数矩阵
SS=squareform（YY）;%将得到的矩阵强制转化成上三角矩阵
%输出每次聚类以后的距离系数矩阵
S=SS（:
1:
M）%将SS赋值给S对应前面的程序
end
end
Z
dendrogram（Z）%画冰状图
4.3程序运行
4.3.1程序运行及环境说明
windows系统matlab软件中运行
4.3.2输入数据
>>loadgg1data%以例5.2的数据为例,这里M=7，N=3
>>gg1（x,7,3）
4.3.2输出数据
计算机运行结果
X=
0.68271.00000.457300.08650.63680.8722
0.00370.08510.10770.055201.00000.9241
0.15130.29110.25880.126100.71641.0000
S=
00.20560.15620.39560.35510.66190.7311
0.205600.31420.58540.55570.61910.6384
0.15620.314200.27660.26840.58820.6802
0.39560.58540.276600.09390.74090.8717
0.35510.55570.26840.093900.77810.9076
0.66190.61910.58820.74090.778100.2172
0.73110.63840.68020.87170.90760.21720
S=
00.20560.15620.37300.66190.7311
0.205600.31420.56880.61910.6384
0.15620.314200.26840.58820.6802
0.37300.56880.268400.75820.8886
0.66190.61910.58820.758200.2172
0.73110.63840.68020.88860.21720
S=
00.25380.31540.62120.7018
0.253800.56880.61910.6384
0.31540.568800.75820.8886
0.62120.61910.758200.2172
0.70180.63840.88860.21720
S=
00.25380.31540.6538
0.253800.56880.6194
0.31540.568800.8188
0.65380.61940.81880
S=
00.39980.6313
0.399800.8188
0.63130.81880
S=
00.6848
0.68480
Z=
4.00005.00000.0939
1.00003.00000.1562
6.00007.00000.2172
9.00002.00000.2538
11.00008.00000.3998
12.000010.00000.6848
4.3.4输出图像
参考文献
[1]郭科龚灝多元统计方法及其应用
[2]Appiledmultivariatestastisticalanalysis应用多元统计分析李卫东北京大学出版社2008.11
[3]numbericalAnalysisandGraphicVisualizationwithmatlabsecondedition[美]shoichiroNakamura电子工业出版社
升级会员 