续前篇---数据挖掘之聚类算法k-mediod(PAM)原理及实现

上一篇博文中介绍了聚类算法中的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

结果例如以下：