上一篇博文中介绍了聚类算法中的kmeans算法.
无可非议kmeans由于其算法简单加之分类效率较高
已经广泛应用于聚类应用中.
然而kmeans并非十全十美的.其对于数据中的噪声和
孤立点的聚类带来的误差也是让人头疼的.
于是一种基于Kmeans的改进算法kmediod应运而生.
kmediod和Kmeans算法核心思想大同小异,但是最大
的不同是在修正聚类中心的时候,kmediod是计算
类簇中除开聚类中心的每点到其他所有点
的聚类的最小值来优化新的聚类中心.正是
这一差别使得kmediod弥补了kmeans算法的缺点.
kmediod对噪声和孤立点不敏感.
但是事情都具有两面性.这种聚类准确性的提高是牺牲聚类
时间来实现的.不难看出.kmediod需要不断的找出每个点到
其他所有点的距离的最小值来修正聚类中心,这大大加大
了聚类收敛的时间.所有Kmediod对于大规模数据聚类
就显得力不从心,只能适应较小规模的数值聚类.
接下来我再对kmediod的算法描述一遍:
1.设样本为X{x(1),x(2)........}
2.首先在样本中随机选取k个聚类中心.
3.然后对除开聚类中心外的样本点计算到每个聚类中心的距离.
将样本归类到距离样本中心最近的样本点.这便实现了最初的聚类
4.再对每个类中除类中心的点外的其他样本点计算到其他所有点的距离和的最小值.
将该最小值点作为新的聚类中心便实现了一次聚类优化.
5.重复步骤四,直到两次聚类中心的位置不再变化,这便完成了最终的聚类
注：步骤4正体现了kmeans和kmediod的核心差异
k-mediod的matlab实现代码如下：
clc;clear;ClomStatic=[1,2,3,25,26,27,53,54,55];len=length(ClomStatic);%求向量ClomStatic的长度k=3; %给定的类别数目%产生三个随机整数，随机聚类中心p=randperm(len);Temp=p(1:k);Center=zeros(1,k);for i=1:k Center(i)=ClomStatic(Temp(i));end%计算除聚类中心外的样本数据到聚类中心的距离,然后进行聚类TempDistance=zeros(len,3); while 1 Circulm=1; p1=1; p2=1; p3=1; JudgeEqual=zeros(1,k); if(Circulm~=1) clear Group1 Group2 Group3; end for i=1:len for j=1:3 TempDistance(i,j)=abs(ClomStatic(i)-Center(j)); end [RowMin RowIndex]=min(TempDistance(i,:)); if(RowIndex==1) Group1(p1)=ClomStatic(i); p1=p1+1; elseif(RowIndex==2) Group2(p2)=ClomStatic(i); p2=p2+1; elseif(RowIndex==3) Group3(p3)=ClomStatic(i); p3=p3+1; end end len1=length(Group1); len2=length(Group2); len3=length(Group3); %计算Group1,Group2,Group3的均值 MeanGroup1=mean(Group1); MeanGroup2=mean(Group2); MeanGroup3=mean(Group3); %分别计算每个类中除开类中心的点到其他所有点的距离和E,E最小时为该类新的聚类中心. E=zeros(1,len1-1); q1=1; for j=1:len1 for i=1:len if(Group1(j)~=Center(1)&&i~=j) E(q1)=floor(abs(Group1(j)-ClomStatic(i))); q1=q1+1; end end end NewCenter(1)=min(E); E=zeros(1,len2-1); q2=1; for j=1:len2 for i=1:len if(Group2(j)~=Center(2)&&i~=j) E(q2)=floor(abs(Group2(j)-ClomStatic(i))); q2=q2+1; end end end NewCenter(2)=min(E); E=zeros(1,len3-1); q3=1; for j=1:len3 for i=1:len if(Group3(j)~=Center(3)&&i~=j) E(q3)=floor(abs(Group3(j)-ClomStatic(i))); q3=q3+1; end end end NewCenter(3)=min(E); %判断新的类和旧类的聚类中心是否不同,不同则继续聚类,否则聚类结束 JudgeEqual=zeros(1,k); for i=1:k JudgeEqual=(NewCenter==Center); end S=0; for i=1:k if(JudgeEqual(i)==1) S=S+1; end end if(S==3) break; end Circulm=Circulm+1; end
结果如下：
转载请注明作者:小刘