K-means算法的实现与应用举例.doc

《K-means算法的实现与应用举例.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、K-means算法的实现与应用举例1K-means方法K-means算法如下：S1：初始化，聚类中心，标号集；S2：分类：S3：重新计算聚类中心：S4：迭代S2-S3，直至收敛。其matlab程序见附录1。2实验实验1随机生成300个之间的二维数对，用K-means算法将其分为两类（其matlab程序见附录2），如fig1，由图1(b)可看出，离群点对聚类中心的位置有明显的影响。fig1实验1(b)(a)实验27随机生成600个二维数对，其中300个落于以（0,0）为圆心的单位圆，另外300个落入（2,2）为圆心的单位圆，用K-means算法将其分为两类（其matlab程序

2、见附录2），如fig2(a)，而fig2(b)则为在以上实验的基础上增加了30个干扰点之后的分类图，可见K-means算法不能对其很好的分类，离群点对聚类中心的位置有明显的影响。fig2实验2(b)(a)实验3随机生成600个二维数对，其中300个落于以（0,0）为圆心的单位元，另外300个落入以（0,0）为圆心的单位圆，长半径为3短半径为2的圆盘，用K-means算法将其分为2类（其matlab程序见附录2），结果见fig3，可见K-means算法同样不能对其很好的分类。fig3实验33K-means算法修正修正一：实验2中增加离群点后，K-means算法失效，是因为采用

3、2范数计算距离，使计算出的重心与实际重心存在较大的误差。为减小误差，可以采用1-范数计算距离，或是采用中值代替均值计算新的聚类中心，即通过实验可以知道，7采用1-范数计算距离实验效果并没有很好的改进，而采用中值计算聚类中心取得较好的效果（matlab程序见附录3），采用同实验2增加干扰后相同的实验数据用修正后的K-means算法进行分类，得到实验结果如fig4(a)，而实验3中结果产生的原因则是由于没有考虑数据点自身的结构特征与其他数据点之间关系引起，并且K-means算法只考虑类内间距最小性并没有考虑类间间距的最大性，即只考虑了类内数据的相似性的最大性并没有考虑类间数据的

4、差异性的最大性，所以单纯的改变聚类中心的选取方法，而没有对相关性（距离）进行本质的重新的定义，并不能对实验3的实验结果很好的改进，如fig4(b)：fig4中值修正(b)(a)fig5K-means在图像分割中的应用(c)(d)(b)(a)4附录附录1function[idx,C,D,sumD]=kmeans_mean(X,k)%kmeans2normK-meansclustering.%X:n*p的数据矩阵%k:将X划分为几类%startM:k*p的矩阵，初始类中心%idx:n*1的向量，存储每个点的聚类编号%C:k*p的矩阵，存储k个聚类的中心位置%sumD:1*k的和

5、向量，类间所有点与该类中心的距离之和%D:n*k的矩阵，每一点与所有中心的距离%sumK:1*k的和向量,记录第k个类中点的个数7[n,p]=size(X);idx=zeros(n,1);C=zeros(k,p);startM=zeros(k,p);D=zeros(n,k);%-----------随机生成初始聚类中心fori=1:kbi=ceil(i*n/k*rand);startM(i,:)=X(bi,:);endwhilesum(abs(startM-C))>0C=startM;startM(:)=0;sumD=zeros(1,k);sumK=zeros(1,k);%

6、记录第k个类中点的个数%count=zeros(1,k);%计数器%sortC=zeros(k,n);fori=1:n%------计算每一点与所有中心的距离------forj=1:kD(i,j)=(X(i,:)-C(j,:))*(X(i,:)-C(j,:))';%D(i,j)=sum(abs(X(i,:)-C(j,:)));end%-----------标号------mini=inf;forj=1:kifD(i,j)

7、x(i))=sumK(idx(i))+1;end%---------计算新的聚类中心---------%=======求解质心=======fori=1:n7startM(idx(i),:)=startM(idx(i),:)+X(i,:)/sumK(idx(i));%求解质心endend附录2clearall%------随机生成[-1,1]^2的数%X=[randn(100,2)+ones(100,2);...%randn(100,2)-ones(100,2)];%%%------随机生成圆盘内的数%deg1=(