最大最小距离算法实例
10个模式样本点{x1(0 0), x2(3 8), x3(2 2), x4(1 1), x 5(5 3), x6(4 8), x7(6 3), x8(5 4), x9(6 4), x10(7 5)}
第一步:选任意一个模式样本作为第一个聚类中
心,如z 1 = x1;
第二步:选距离z 1最远的样本作为第二个聚类中心。
经计算,|| x6 - z1 ||最大,所以z 2 = x6;
第三步:逐个计算各模式样本{xi , i = 1,2,…,N}与{z1,
z 2}之间的距离,即
D i1 = || xi - z1 ||
D i2 = || xi – z2 ||
并选出其中的最小距离min(Di1, D i2) ,i = 1,2, …,N
第四步:在所有模式样本的最小值中选出最大距
离,若该最大值达到||z1 - z 2 ||的一定比例以上,则相应的样本点取为第三个聚类中心z 3,即:若max{min(Di1, Di2), i = 1,2,…,N} >θ||z1 - z2 ||,则z 3 = xi
否则,若找不到适合要求的样本作为新的聚类中心,则找聚类中心的过程结束。 这里,θ可用试探法取一固定分数,如1/2。 在此例中,当i=7时,符合上述条件,故z 3 = x7
第五步: 若有z 3存在,则计算max{min(Di1, Di2, Di3),
i = 1,2,…,N}。若该值超过||z1 - z2 ||的一定比例,则存在z 4,否则找聚类中心的过程结束。
在此例中,无z 4满足条件。
第六步:将模式样本{x i , i = 1,2,…,N }按最近距离分
到最近的聚类中心:
z 1 = x1:{x1, x3, x4}为第一类
z 2 = x6:{x2, x6}为第二类
z 3 = x7:{x5, x7, x8, x9, x10}为第三类 最后,还可在每一类中计算各样本的均值,得到更具代表性的聚类中心。
最大最小距离算法实例
10个模式样本点{x1(0 0), x2(3 8), x3(2 2), x4(1 1), x 5(5 3), x6(4 8), x7(6 3), x8(5 4), x9(6 4), x10(7 5)}
第一步:选任意一个模式样本作为第一个聚类中
心,如z 1 = x1;
第二步:选距离z 1最远的样本作为第二个聚类中心。
经计算,|| x6 - z1 ||最大,所以z 2 = x6;
第三步:逐个计算各模式样本{xi , i = 1,2,…,N}与{z1,
z 2}之间的距离,即
D i1 = || xi - z1 ||
D i2 = || xi – z2 ||
并选出其中的最小距离min(Di1, D i2) ,i = 1,2, …,N
第四步:在所有模式样本的最小值中选出最大距
离,若该最大值达到||z1 - z 2 ||的一定比例以上,则相应的样本点取为第三个聚类中心z 3,即:若max{min(Di1, Di2), i = 1,2,…,N} >θ||z1 - z2 ||,则z 3 = xi
否则,若找不到适合要求的样本作为新的聚类中心,则找聚类中心的过程结束。 这里,θ可用试探法取一固定分数,如1/2。 在此例中,当i=7时,符合上述条件,故z 3 = x7
第五步: 若有z 3存在,则计算max{min(Di1, Di2, Di3),
i = 1,2,…,N}。若该值超过||z1 - z2 ||的一定比例,则存在z 4,否则找聚类中心的过程结束。
在此例中,无z 4满足条件。
第六步:将模式样本{x i , i = 1,2,…,N }按最近距离分
到最近的聚类中心:
z 1 = x1:{x1, x3, x4}为第一类
z 2 = x6:{x2, x6}为第二类
z 3 = x7:{x5, x7, x8, x9, x10}为第三类 最后,还可在每一类中计算各样本的均值,得到更具代表性的聚类中心。