动态聚类法—实验报告.docx

《模式识别》实验报告(3) 动态聚类法姓名:滕超淋学号: 3112037009 专业:生物医学工程 k - 均值算法一、实验原理实验数据: IRIS 数据。分为三种类型,每种类型中包括 50个4维的向量。实验方法: K-均值算法算法步骤: K个初始聚类中心 Z1(1),Z2(1),...,Zk(1). 聚类中心随迭代次数而变, 括号中的数字表示迭代次序。 {X} 按最小距离准则分配到 K个中心的某一个中心,以下公式进行判断: ,其中k为迭代次数, Zj(k) 为聚类中心。 ,下来计算每个聚类的新中心 Zj(k+1) 。计算公式如下: Ni是j类样本的个数,以均值向量作为新的中心。 4. 如果 Zj(k+1) ≠ Zj(k) ,则回到第二步,将模式样本重新逐个划分,继续迭代计算。如果 Zj(k+1) =Zj(k) ,则算法收敛,结束。二、实验步骤(1 )从 文件中读取估计参数用的样本,并任意选取三个样本作为初始聚类中心。(2)计算距离,按最小距离原则进行分类。(3 )计算新的聚类中心,并判断新的聚类中心是否与本次迭代的聚类中心一样。如果一样则计算结束,否则继续迭代。三、实验结果及分析选取不同的初始聚类中心对结果影响较大,特别是选取同一类的样本作为初始聚类中心的时候分类结果不理想。由于第一类与第二类、第三类区别较大,所以能很好的分类出来,但是第二类和第三类的样本很近,而且有一些点相重叠, 致使分类结果不理想。以下是实验结果: 通过与原数据比较,第一类即 t1 分类完全正确,然而 t2,t3 不理想。算法需要进一步改进和完善。 ISODATA 算法一、原理介绍 Isodata ,迭代自组织分析,通过设定初始参数而引入人机对话环节,并使用归并与分裂的机制,当某两类聚类中心距离小于某一阈值时,将它们合并为一类,当某类标准差大于某一阈值或其样本数目超过某一阈值时,将其分为两类。在某类样本数目少于某阈值时,需将其取消。如此,根据初始聚类中心和设定的类别数目等参数迭代,最终得到一个比较理想的分类结果。二、算法设计第一步:将个模式样本{ ,i=1,2,3, …,}读入,确定 C个初始聚类中心和 6个初始参数( K,θN,θc,θs,L,I)。第二步:将 N个模式样本分给最近的聚类,假如 Dj=min( ‖ x-zj ‖,i=1,2, …,), 即‖ x-zj ‖的距离最小,则 x∈ Sj。第三步:如果 Sj中的样本数 Nj< θ N, 取消样本子集。第四步:修正聚类中心值 j=1,2, …, 第五步:计算各聚类域 Sj中诸聚类中心间的平均距离: 第六步:计算全部模式样本对其相应聚类中心的总平均距离: 第七步:判别分裂、合并及迭代运算等步骤: 1如迭代运算次数已达 I次,即最后一次迭代,置θc=0(无需新中心) ,跳到第十四步,运算结束。 2如 Nc ≤ K/2 ,即聚类中心的数目等于或不到规定值的一半,则进入第八步,将已有的聚类分裂。 3如迭代运算的次数是偶次,或 Nc ≥ 2K ,不进行分裂处理,跳到第十一步(合并处理); 如不符合以上两个条件(即既不是偶次迭代,也不是≥ 2K ),则进入第八步, 进行分裂处理。分裂处理: 第八步:计算各个聚类中样本到聚类中心距离的标准差向量: 第九步:求每一标准差向量{σ j}中的最大分量第十步:在任一最大分量集{σ j=1,2, …,}中,如有σ j> θS(该值给定),同时又满足以下二条件中之一: (a) Djmean>Dmean 和即 Sj中样本总数超过规定值一倍以上, (b) Nc ≤ K/2 ,则将 Zj分裂为两个新的聚类中心,且类别数加 Nc+ 1。分裂方法是在加上 k* σ jmax ,在的相应分量减去 k* σ jmax ,其中 k= ;。如果本步完成了分裂运算,则跳回第二步;否则,继续。第十一步:计算全部聚类中心的距离: ,其中 i=1,2, …, Nc-1 j=i+1, …, Nc 第十二步:比较与θc值,将<θc的值按最小距离次序递增排列,即{,,…,},假设< 第十三步:将距离为 Di1j1 的两个聚类中心 zi1 和 zj1 合并,得新中心为, l=1,2, …,L式中,被合并的两个聚类中心向量,分别以其聚类域内的样本数加权, 使其成为真正的平均向量。第十四步:如果是最后一次迭代运算(即第 I次),算法结束。否则回到第一步由操作者改变输入参数;或回到第二步继续迭代,不改变参数。(1)主程序如下: (2) 分类函数(3) 合并函数(4) ,K为预期的聚类数目;theta_N 为每一聚类样本域的最小数目; theta_S 为每一聚类样本域距离分布的标准差; theta_