数据挖掘十大经典算法[0]-K-Means算法

K-Means算法的输入N,K和一个size为N的向量组vector.输出K个两两互不相交的向量组.其本质是将给定的向量组划分成K个类别,使得同类别的向量相似度比较大,而不同类别的向量之间的相似度较小.
    比如以下这个图,人肉眼能看出有四个点团,但计算机不知道,为了让计算机明白这一点,可以将点的坐标提取到向量组中,而向量之间的相似度定义为点之间的距离的相反数或者倒数.从而将这些点分开.
    实现过程:
    (1)从n个数据对象任意选择k个对象作为初始聚类中心;
    (2)根据每个聚类对象的均值(中心对象),计算每个对象与这些中心对象的距离,并根据最小距离重新对相应对象进行划分;
    (3)重新计算每个(有变化)聚类的均值(中心对象);
    (4)计算标准测度函数,当满足一定条件,如函数收敛时,则算法终止,如果条件不满足则回到步骤(2).
    实际应用中的问题:
    事实上,我是一个做ACM的选手,所以我比较感兴趣的是K-Means能否求得一个最优解.对于这样一个问题:从N个点取出K个作为核心,定义两个向量之间的相似度函数f(vector1,vector2),使得所有点与其所对应的核心的相似度之和最大.然而事实让我大失所望,K-Means算法对种子点的选取十分敏感,不同的种子会导致不同的解.

#include<math.h>

#include<stdio.h>

#include<string.h>

#define Convergence (fabs(last-cur)<1e-8)

#define dist(a,b) (sqrt((x[a]-px[b])*(x[a]-px[b])+(y[a]-py[b])*(y[a]-py[b])))

int x[],y[],qx[],qy[],px[],py[],assign[];

int main()

{

 freopen("data.txt","r",stdin);

 FILE *fp=fopen("output.txt","w");

 int N,K,i,j,k;

 double ave=,MIN=1e15;

 scanf("%d%d",&N,&K);

 for (i=;i<=N;i++) scanf("%d%d",&x[i],&y[i]);

 for (int asd=;asd<N;asd++)

 {

 printf("Executing case #%d\n",asd);

 if (asd) printf("Current Average:%.6lf\n",ave/asd);

 printf("Current Minimize:%.6lf\n",MIN);

 printf("----------------------------------------\n");

 fprintf(fp,"Executing case #%d\n",asd);

 if (asd) fprintf(fp,"Current Average:%.6lf\n",ave/asd);

 fprintf(fp,"Current Minimize:%.6lf\n",MIN);

 fprintf(fp,"----------------------------------------\n");

 for (i=;i<=K;i++)

 {

  px[i]=x[(i+asd)%N+];

  py[i]=y[(i+asd)%N+];

 }

 double last=1e15,cur=;

 while (!Convergence)

 {

  printf("%.6lf\n",last);

  last=cur;

  for (i=;i<=N;i++)

  {

   double Min=1e15;

   int v;

   for (j=;j<=K;j++)

   {

    double d=dist(i,j);

    if (d<Min)

    {

     Min=d;

     v=j;

    }

   }

   assign[i]=v;

  }

  for (i=;i<=K;i++)

  {

   int cnt=;

   for (j=;j<=N;j++)

    if (assign[j]==i)

    {

     qx[++cnt]=x[j];

     qy[ cnt ]=y[j];

    }

   double Min=1e15;

   int v;

   for (j=;j<=cnt;j++)

   {

    double tmp=;

    for (k=;k<=cnt;k++)

     tmp+=(sqrt((qx[j]-qx[k])*(qx[j]-qx[k])+(qy[j]-qy[k])*(qy[j]-qy[k])));

    if (tmp<Min)

    {

     Min=tmp;

     v=j;

    }

   }

   px[i]=qx[v];

   py[i]=qy[v];

  }

  cur=;

  for (i=;i<=N;i++) cur+=dist(i,assign[i]);

 }

 ave+=cur;

 MIN=MIN<cur ? MIN:cur;

 }

 printf("Total average:%.6lf\n",ave/N);

 printf("Total MIN:%.6lf\n",MIN);

 fprintf(fp,"Total average:%.6lf\n",ave/N);

 fprintf(fp,"Total MIN:%.6lf\n",MIN);

 return ;

}

运行结果如图所示:

另一个问题是算法的收敛速度,重新算了一下,结果如下图所示:

这个结果让我大吃一惊啊,每次迭代之后更新量都很小,而且最终的值(9259914.963696)跟第一个有意义的值(10352922.175732)相差并不是很多.后来我仔细想了一下,应该是跟输入数据有关,我的数据完全是在一定范围内随机生成的,分布比较均匀,所以即使随便选也可以得到相当不错的效果,这是我生成数据的程序:

program makedata;

var i,N,K:longint;

begin

assign(output,'data.txt');

rewrite(output);

    randomize;

    N:=random();

    K:=random();

    writeln(N,' ',K);

    for i:= to N do

        writeln(random(),' ',random());

close(output);

end.

于是我重新写了makedada程序,想法是先随机生成K个核心,再在其周围生成其他的点:

#include<stdio.h>

#include<time.h>

#include<math.h>

#include<stdlib.h>

int main()

{

 srand(unsigned(time()));

 freopen("data.txt","w",stdout);

 printf("15000 15\n");

 for (int i=;i<=;i++)

 {

  int X=rand()%,Y=rand()%;

  for (int j=;j<=;j++)

  {

   int dx=rand()%,dy=rand()%;

   if (rand()&) dx*=-;

   if (rand()&) dy*=-;

   printf("%d %d\n",X+dx,Y+dy);

  }

 }

 return ;

}

再重新运行一下,得到如下结果:

可以看出,收敛的速度还是可以的,而且最终结果几乎只有最初解得一半.
初除此之外,还有一个重要问题,核心数K是作为输入给定的,而在实际应用中是无法预知的.对此可以用ISODATA算法作为补充.

巴特西

数据挖掘十大经典算法[0]-K-Means算法

最新文章

热门文章