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[50000],y[50000],qx[50000],qy[50000],px[100],py[100],assign[50000];

int main()

{

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

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

 int N,K,i,j,k;

 double ave=0,MIN=1e15;

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

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

 for (int asd=0;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=1;i<=K;i++)

 {

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

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

 }

 double last=1e15,cur=0;

 while (!Convergence)

 {

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

  last=cur;

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

  {

   double Min=1e15;

   int v;

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

   {

    double d=dist(i,j);

    if (d<Min)

    {

     Min=d;

     v=j;

    }

   }

   assign[i]=v;

  }

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

  {

   int cnt=0;

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

    if (assign[j]==i)

    {

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

     qy[ cnt ]=y[j];

    }

   double Min=1e15;

   int v;

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

   {

    double tmp=0;

    for (k=1;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=0;

  for (i=1;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 0;

}

运行结果如图所示:

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

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

program makedata;
var i,N,K:longint;
begin
assign(output,'data.txt');
rewrite(output);
randomize;
N:=random(10000);
K:=random(10000);
writeln(N,' ',K);
for i:=1 to N do
writeln(random(10000),' ',random(10000));
close(output);
end.

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

#include<stdio.h>
#include<time.h>
#include<math.h>
#include<stdlib.h>
int main()
{
srand(unsigned(time(0)));
freopen("data.txt","w",stdout);
printf("15000 15\n");
for (int i=1;i<=15;i++)
{
int X=rand()%1000000,Y=rand()%1000000;
for (int j=1;j<=1000;j++)
{
int dx=rand()%10000,dy=rand()%10000;
if (rand()&1) dx*=-1;
if (rand()&1) dy*=-1;
printf("%d %d\n",X+dx,Y+dy);
}
}
return 0;
}

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

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

分类: 数据挖掘

巴特西

K-Means算法

K-Means算法

最新文章

热门文章