《模式识别》实验报告 动态聚类法
姓名：滕超淋 学号：3112037009 专业：生物医学工程
k -均值算法
一、实验原理
实验数据：IRIS 数据。分为三种类型，每种类型中包括50个4维的向量。 实验方法：K-均值算法 算法步骤：
1. 选择K 个初始聚类中心Z1(1),Z2(1),...,Zk(1).聚类中心随迭代次数而变，括号中的数字表示迭代次序。
2. 逐个将待分类样本{X}按最小距离准则分配到K 个中心的某一个中心，以下公式进行判断：
，
中k 为迭代次数，Zj(k)为聚类中心。
3. 分配完后，下来计算每个聚类的新中心Zj(k+1)。计算公式如下：
Zj k +1 =1/Ni X
x ∈Sj(k)
其
Ni 是j 类样本的个数，以均值向量作为新的中心。
4. 如果Zj(k+1)≠Zj(k)，则回到第二步，将模式样本重新逐个划分，继续迭代计算。如果Zj(k+1) =Zj(k)，则算法收敛，结束。
二、实验步骤
（1）从IRIS_DATA.txt文件中读取估计参数用的样本，并任意选取三个样本作为初始聚类中心。
（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
第五步：计算各聚类域Sj 中诸聚类中心间的平均距离： 第六步：计算全部模式样本对其相应聚类中心的总平均距离： 第七步：判别分裂、合并及迭代运算等步骤：
① 如迭代运算次数已达I 次，即最后一次迭代，置θc = 0（无需新中心）, 跳到第十四步，运算结束。
② 如Nc ≤K/2，即聚类中心的数目等于或不到规定值的一半，则进入第八步，将已有的聚类分裂。
③ 如迭代运算的次数是偶次，或Nc ≥2K，不进行分裂处理，跳到第十一步(合并处理) ；
如不符合以上两个条件（即既不是偶次迭代，也不是≥2K），则进入第八步，进行分裂处理。 分裂处理：
第八步：计算各个聚类中样本到聚类中心距离的标准差向量： 第九步：求每一标准差向量{σj}中的最大分量
第十步：在任一最大分量集{σj=1,2, …，}中，如有σj>θS（该值给定），同
时又满足以下二条件中之一：
(a) Djmean>Dmean和即Sj 中样本总数超过规定值一倍以上， （b ）N c≤K/2，则将Zj 分裂为两个新的聚类中心Zj+和Zj−, 且类别数加
Nc+1。
分裂方法是在Zj+相应分量加上k* σjmax，在Zj−的相应分量减去k*σjmax，其中k=0.5；。如果本步完成了分裂运算，则跳回第二步；否则，继续。 第十一步：计算全部聚类中心的距离：Dij =||Zi−Zj||, 其中i=1,2, …, Nc-1
j=i+1, …,Nc
第十二步：比较Dij 与θc值，将Dij
{ Di1j1, Di2j2, …, Diljl },假设Di1j1
第十三步：将距离为Di1j1的两个聚类中心zi1和zj1合并，得新中心为
Zl∗=N
1
il+Njl
NilZil+NjlZjl , l=1,2,…，L
式中，被合并的两个聚类中心向量，分别以其聚类域内的样本数加权，使其成为真正的平均向量。
第十四步：如果是最后一次迭代运算（即第I 次），算法结束。否则回到第一步由操作者改变输入参数；或回到第二步继续迭代，不改变参数。
三．实验步骤 （1）主程序如下：
(2) 分类函数
四. 实验结果
下列各表中，K 为预期的聚类数目；theta_N为每一聚类样本域的最小数目；theta_S为每一聚类样本域距离分布的标准差；theta_C为两个聚类中心的最小距离；L 为一次迭代运算中可以合并的聚类中心的最多数，I 为迭代次数。 1、[K theta_N theta_S theta_C L I]=[6 8 0.5 1 3 8]时，
类别数Nc
类别 类别 正确分类个数 正确率
第一类 第一类 50 1
第二类 第二类 45 0.90
第三类 第三类 41 0.82
总体正确率
总体正确率
0.91
类别数Nc
3
4、[K theta_N theta_S theta_C L I]=[6 8 1 1 3 8]时，
类别数Nc
类别 类别 类别 类别 类别 第一类 第一类 第一类 第一类 第一类 第二类 第二类 第二类 第二类 第二类 第三类 第三类 第三类 第三类 第三类 总体正确率
总体正确率
总体正确率
总体正确率
总体正确率
类别数Nc
类别数Nc
类别数Nc
类别数Nc
从上面的表格可以看到，对于不同的参数设置ISODATA 算法总能将样本正确的分为三类。但是，分类结果却与参数的设置有关。由表1、2、3可以看出，当改变theta_N、theta_C和theta_S时，对分类结果影响不大。但当I 变化时，对分类结果的影响大，说明迭代次数结果有一定的影响。当迭代次数达到合适的值时，在增加次数对分类结果没有影响。
在实验中，我们可以随时调整K 、theta_N、theta_S、theta_C和L 的值来改变实验的分类率，比较灵活。 五. 总结
与K-均值算法的比较，K-均值算法初始聚类中心的选择对结果影响很大，而ISODATA 算法则更加灵活；从算法角度看， ISODATA算法与K-均值算法相似，但是 ISODATA算法加入了一些试探步骤，并且可以结合成人机交互的结构，使其能利用中间结果所取得的经验更好地进行分类。
《模式识别》实验报告 动态聚类法
姓名：滕超淋 学号：3112037009 专业：生物医学工程
k -均值算法
一、实验原理
实验数据：IRIS 数据。分为三种类型，每种类型中包括50个4维的向量。 实验方法：K-均值算法 算法步骤：
1. 选择K 个初始聚类中心Z1(1),Z2(1),...,Zk(1).聚类中心随迭代次数而变，括号中的数字表示迭代次序。
2. 逐个将待分类样本{X}按最小距离准则分配到K 个中心的某一个中心，以下公式进行判断：
，
中k 为迭代次数，Zj(k)为聚类中心。
3. 分配完后，下来计算每个聚类的新中心Zj(k+1)。计算公式如下：
Zj k +1 =1/Ni X
x ∈Sj(k)
其
Ni 是j 类样本的个数，以均值向量作为新的中心。
4. 如果Zj(k+1)≠Zj(k)，则回到第二步，将模式样本重新逐个划分，继续迭代计算。如果Zj(k+1) =Zj(k)，则算法收敛，结束。
二、实验步骤
（1）从IRIS_DATA.txt文件中读取估计参数用的样本，并任意选取三个样本作为初始聚类中心。
（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
第五步：计算各聚类域Sj 中诸聚类中心间的平均距离： 第六步：计算全部模式样本对其相应聚类中心的总平均距离： 第七步：判别分裂、合并及迭代运算等步骤：
① 如迭代运算次数已达I 次，即最后一次迭代，置θc = 0（无需新中心）, 跳到第十四步，运算结束。
② 如Nc ≤K/2，即聚类中心的数目等于或不到规定值的一半，则进入第八步，将已有的聚类分裂。
③ 如迭代运算的次数是偶次，或Nc ≥2K，不进行分裂处理，跳到第十一步(合并处理) ；
如不符合以上两个条件（即既不是偶次迭代，也不是≥2K），则进入第八步，进行分裂处理。 分裂处理：
第八步：计算各个聚类中样本到聚类中心距离的标准差向量： 第九步：求每一标准差向量{σj}中的最大分量
第十步：在任一最大分量集{σj=1,2, …，}中，如有σj>θS（该值给定），同
时又满足以下二条件中之一：
(a) Djmean>Dmean和即Sj 中样本总数超过规定值一倍以上， （b ）N c≤K/2，则将Zj 分裂为两个新的聚类中心Zj+和Zj−, 且类别数加
Nc+1。
分裂方法是在Zj+相应分量加上k* σjmax，在Zj−的相应分量减去k*σjmax，其中k=0.5；。如果本步完成了分裂运算，则跳回第二步；否则，继续。 第十一步：计算全部聚类中心的距离：Dij =||Zi−Zj||, 其中i=1,2, …, Nc-1
j=i+1, …,Nc
第十二步：比较Dij 与θc值，将Dij
{ Di1j1, Di2j2, …, Diljl },假设Di1j1
第十三步：将距离为Di1j1的两个聚类中心zi1和zj1合并，得新中心为
Zl∗=N
1
il+Njl
NilZil+NjlZjl , l=1,2,…，L
式中，被合并的两个聚类中心向量，分别以其聚类域内的样本数加权，使其成为真正的平均向量。
第十四步：如果是最后一次迭代运算（即第I 次），算法结束。否则回到第一步由操作者改变输入参数；或回到第二步继续迭代，不改变参数。
三．实验步骤 （1）主程序如下：
(2) 分类函数
四. 实验结果
下列各表中，K 为预期的聚类数目；theta_N为每一聚类样本域的最小数目；theta_S为每一聚类样本域距离分布的标准差；theta_C为两个聚类中心的最小距离；L 为一次迭代运算中可以合并的聚类中心的最多数，I 为迭代次数。 1、[K theta_N theta_S theta_C L I]=[6 8 0.5 1 3 8]时，
类别数Nc
类别 类别 正确分类个数 正确率
第一类 第一类 50 1
第二类 第二类 45 0.90
第三类 第三类 41 0.82
总体正确率
总体正确率
0.91
类别数Nc
3
4、[K theta_N theta_S theta_C L I]=[6 8 1 1 3 8]时，
类别数Nc
类别 类别 类别 类别 类别 第一类 第一类 第一类 第一类 第一类 第二类 第二类 第二类 第二类 第二类 第三类 第三类 第三类 第三类 第三类 总体正确率
总体正确率
总体正确率
总体正确率
总体正确率
类别数Nc
类别数Nc
类别数Nc
类别数Nc
从上面的表格可以看到，对于不同的参数设置ISODATA 算法总能将样本正确的分为三类。但是，分类结果却与参数的设置有关。由表1、2、3可以看出，当改变theta_N、theta_C和theta_S时，对分类结果影响不大。但当I 变化时，对分类结果的影响大，说明迭代次数结果有一定的影响。当迭代次数达到合适的值时，在增加次数对分类结果没有影响。
在实验中，我们可以随时调整K 、theta_N、theta_S、theta_C和L 的值来改变实验的分类率，比较灵活。 五. 总结
与K-均值算法的比较，K-均值算法初始聚类中心的选择对结果影响很大，而ISODATA 算法则更加灵活；从算法角度看， ISODATA算法与K-均值算法相似，但是 ISODATA算法加入了一些试探步骤，并且可以结合成人机交互的结构，使其能利用中间结果所取得的经验更好地进行分类。