资源描述：
《模式识别作业.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第二章主要内容：几种常见的聚类算法已经所使用的准则函数。作业1：对如下5个6维模式样本，用最小聚类准则进行系统聚类分析已知样本如下：x1:0,1,3,1,3,4；x2:3,3,3,1,2,1；x3:1,0,0,0,1,1；x4:2,1,0,2,2,1；x5:0,0,1,0,1,0第1步：将每一样本看成单独一类，得计算各类之间的欧式距离，可得距离矩阵00000第2步：矩阵中最小元素为，它是和之间的距离，将他们合并为一类，得新的分类为计算聚类后的距离矩阵0000第3步：由于中距离最小者为，它是与之间的距离，于是合并和，得新的分类为同样，按最小距离准则计算
2、距离矩阵，得000第4步：同理得满足聚类要求，如聚为2类，聚类完毕。系统聚类算法介绍：第一步：设初始模式样本共有N个，每个样本自成一类，即建立N类。G1(0),G2(0),……,GN(0)为计算各类之间的距离（初始时即为各样本间的距离），得到一个N*N维的距离矩阵D(0)。这里，标号(0)表示聚类开始运算前的状态。第二步：假设前一步聚类运算中已求得距离矩阵D(n)，n为逐次聚类合并的次数，则求D(n)中的最小元素。如果它是Gi(n)和Gj(n)两类之间的距离，则将Gi(n)和Gj(n)两类合并为一类Gij(n+1)，由此建立新的分类：G1(n+1),
3、G2(n+1)……第三步：计算合并后新类别之间的距离，得D(n+1)。计算Gij(n+1)与其它没有发生合并的G1(n+1),G2(n+1)……之间的距离，可采用多种不同的距离计算准则进行计算。第四步：返回第二步，重复计算及合并，直到得到满意的分类结果。（如：达到所需的聚类数目，或D(n)中的最小分量超过给定阈值D等。）作业2：选k=2，z1(1)=x1,z2(1)=x10,，用K-均值算法进行聚类分析第一步：选取第二步：根据聚类中心进行聚类，得到：第三步：计算新的聚类中心第四步：因，故回到第二步第二步：根据新的聚类中心重新进行聚类，得到：第三步：计
4、算新的聚类中心：第四步：，所以算法收敛，得聚类中心为迭代结束。K-均值算法介绍：算法适用于分类数已知。总的思路如下：选定聚类中心——>最小聚类准则归类——>重新计算聚类中心……直到聚类中心不改变为止。第一步：选K个初始聚类中心，z1(1)，z2(1)，…，zK(1)，其中括号内的序号为寻找聚类中心的迭代运算的次序号。聚类中心的向量值可任意设定，例如可选开始的K个模式样本的向量值作为初始聚类中心。第二步：逐个将需分类的模式样本{x}按最小距离准则分配给K个聚类中心中的某一个zj(1)。假设i=j时，，则，其中k为迭代运算的次序号，第一次迭代k=1，Sj
5、表示第j个聚类，其聚类中心为zj。第三步：计算各个聚类中心的新的向量值，zj(k+1)，j=1,2,…,K求各聚类域中所包含样本的均值向量：其中Nj为第j个聚类域Sj中所包含的样本个数。以均值向量作为新的聚类中心，可使如下聚类准则函数最小：在这一步中要分别计算K个聚类中的样本均值向量，所以称之为K-均值算法。第四步：若，j=1,2,…,K，则返回第二步，将模式样本逐个重新分类，重复迭代运算；若，j=1,2,…,K，则算法收敛，计算结束。本章其他知识点：1．距离相似度测量1.1欧氏距离设x和z为两个模式样本，其欧氏距离定义为：D=
6、
7、x-z
8、
9、例：x=
10、(x1,x2)，z=(z1,z2)，则显然，模式x和z之间的距离越小，它们越相似。欧氏距离的概念和习惯上距离的概念是一致的。1.2马氏距离设x是模式向量，m是均值向量，C为模式总体的协方差矩阵，则马氏距离的表达式：1.3一般化的明氏距离模式样本向量xi和xj之间的明氏距离表示为：其中xik和xjk分别表示xi和xj的第k各分量。显然，当m=2时，明氏距离即为欧氏距离。特例：当m=1时，，亦称为街坊距离。2角度相似性函数表达式：，它表示模式向量x和z之间夹角的余弦，也称为x的单位向量与z的单位向量之间的点积。特例：当特征的取值仅为(0,1)两个值时，夹
11、角余弦度量具有特别的含义，即当模式的第i个分量为1时，认为该模式具有第i个特征；当模式的第i个分量为0时，认为该模式无此特征。这时，xTz的值就等于x和z这两个向量共同具有的特征数目。同时，={x中具有的特征数目和z中具有的特征数目的几何平均}因此，在特征取值为0和1的二值情况下，S(x,z)等于x和z中具有的共同特征数目的相似性测度。3．最大最小距离算法实例10个模式样本点：{x1(00),x2(38),x3(22),x4(11),x5(53),x6(48),x7(63),x8(54),x9(64),x10(75)}算法思路：根据最大最小距离准则，
12、确定聚类数；然后按最近最近距离分类。第一步：选任意一个模式样本作为第一个聚类中心，如z1=x1第二步：选距离
