模式识别第二章
2. K-均值分类算法
1. 实验原理和步骤
以初始化聚类中心为1x 和10x 为例。
第一次迭代:
第一步:取K=2,并选T x z )00()1(11==,T x z )67()1(102==。
第二步:因)1()1(2111z x z x -<-,故)1(11S x ∈
因)1()1(2212z x z x -<-,故)1(12S x ∈
因)1()1(2313z x z x -<-,故)1(13S x ∈
……
得到:},,,,,,,{)1(876543211x x x x x x x x S =
},,,,,,,,,,,{)1(201918171615141312111092x x x x x x x x x x x x S =。
第三步:计算新的聚类中心:
⎪⎪⎭
⎫ ⎝⎛=+⋯⋯++==∑∈125.1250.1)(811)2(821)1(111x x x x N z S x ⎪⎪⎭⎫ ⎝⎛=+⋯⋯++==∑∈333.7663.7)(1211)2(20109)1(2
22x x x x N z S x (1N 和2N 分别为属于第一类和第二类的样本的数目)。
第四步:因)2()1(z z ≠,返回第二步。
第二次迭代(步骤同上):
第二次迭代得到的⎪⎪⎭⎫ ⎝⎛=125.1250.1)3(1z ,⎪⎪⎭
⎫ ⎝⎛=333.7663.7)3(2z ,)3()2(z z ≠,结束迭代,得到的最终聚类中心为:⎪⎪⎭⎫ ⎝⎛=125.1250.11z ,⎪⎪⎭
⎫ ⎝⎛=333.7663.72z 。
2. 实验结果截图
(1)初始化聚类中心为1x 和10x 时:
(2)初始化聚类中心为1x 和2x 时:
(3)初始化聚类中心为12x 和20x 时:
3. 程序代码
%程序功能:实现K-均值分类
%作者:赵晓梅 201428014628066
%时间:2014.10.3
clc;
clear all ;
fprintf('K-均值分类算法\n');
k=0;%记录迭代次数
x=[0,0;1,0;0,1;1,1;2,1;1,2;2,2;3,2;6,6;7,6;8,6;6,7;7,7;8,7;9,7;7,8;8,8;9,8;8,9;9,9];%输入样本
[N n]=size(x);%N 表示样本数目;n 表示样本维度
m=[12,20];
z=[x(m(1),:);x(m(2),:)];%初始化聚类中心
fprintf('初始聚类中心选:x%d 和x%d\n',m(1),m(2));%显示初始化聚类中心 D=size(z);
K=D(1);%获取聚类数目
d=zeros(1,K);%用于保存一个样本到K 个聚类中心的距离
label=zeros(1,N);%用于标记每个样本属于哪个类,取值为1-K 之间的整数
flag_end=0;%迭代结束标志,当为1时,迭代结束
while(~flag_end)
for i=1:N
for j=1:K
d(j)=norm(x(i,:)-z(j,:));%计算第i个样本到第j个聚类中心的距离end
min_d=d(1);
for j=1:K
if d(j)<=min_d%选取最短的距离,并用最短距离的索引标记样本,记样本为第j类
min_d=d(j);
label(i)=j;
end
end
end
z_new=zeros(K,n);%用于保存更新的聚类中心的坐标
for j=1:K%更新聚类中心坐标
num=0;
for i=1:N
if label(i)==j
z_new(j,:)=z_new(j,:)+x(i,:);
num=num+1;
end
end
z_new(j,:)=z_new(j,:)/num;%新的聚类中心的坐标为第j类样本的均值向量end
if z==z_new%如果原聚类中心与更新的聚类中心相等,则迭代结束,迭代结束标志置1 flag_end=1;
end
z=z_new;
k=k+1;%迭代次数加1
end
fprintf('经过 %d次迭代\n',k);%显示迭代次数
for j=1:K
fprintf('第 %d类的聚类中心坐标为:(%f,%f)\n',j,z(j,1),z(j,2));%显示聚类中心坐标
end。