k-c.txt

这是一个K中心点聚类算法C实现的,希望对大家有用

#include<math.h>
#include<conio.h>
#include<stdio.h>
#include <stdlib.h>
#include <graphics.h>

struct object
{
    int x;
    int y;
    int z;
    int most;
    int second;
} point[20];

int mid[3],nmid[17];

void getData();                            /*获取点坐标*/
void init();                               /*初始化中心点*/
double getminTC(int *i,int *h);                     /*返回交换点的最小代价*/
void printgraph();                         /*画出簇图*/

int main()
{
    int i,m,n,temp;
    int driver=DETECT,mode=0;
    initgraph(&driver,&mode,"c:\\turboc2");

    getData();
    init();

    while(getminTC(&m,&n)<0)                     /*直到无需交换*/
        temp=mid[m],mid[m]=nmid[n],nmid[n]=temp;

    printf("\rThe checked center point are :");
    for(i=0;i<3;i++)
        printf("%2d  ",mid[i]);
    printf("\r\n\r\nPress any key to continue---");
    getch();

    printgraph();

    return 0;
}

void getData()                          /*获取数据*/
{
    FILE *fp;
    int i;
/*  clrscr();*/
    printf("*******************************************\n\n");
    if((fp=fopen("Data.txt","r"))==NULL)            /*随机生成数据*/
    {
        printf("Get the random data---");
        srand((unsigned)time(NULL));             /*初始化种子*/
        for(i=0;i<20;i++)
     {
     point[i].x=rand() % 90 + 10;
     point[i].y=rand() % 90 + 10;
     point[i].z=rand() % 90 + 10;
        }
    }
    else                          /*读取数据*/
    {
        printf("Get the data from the file---");
        for(i=0;i<20 && !feof(fp);i++)
     {
     fscanf(fp,"%d,%d,%d",&point[i].x,&point[i].y,&point[i].z);
            if (point[i].x<10 || point[i].x>100)
                point[i].x=point[i].x % 90+10;
            if (point[i].y<10 || point[i].y>100)
  point[i].y=point[i].y % 90+10;
     if (point[i].z<10 || point[i].z>100)
  point[i].z=point[i].z % 90+10;
     }
        fclose(fp);
    }
    printf("OK!\r\n\r\nThe point are as follows:\r\n");
    for(i=0;i<20;i++)                      /*输出数据*/
    {
 printf("(%2d,%2d,%2d)  ",point[i].x,point[i].y,point[i].z);
 if((i+1)%5==0)
            printf("\r\n");
    }
    printf("\r\nPress any key to continue---");
    getch();
}

void init()                                /*初始化中心点*/
{
    int i,k;
    srand((unsigned)time(NULL));                 /*初始化种子*/
    mid[0]=rand()%20;                      /*获取中心点*/
    do
        mid[1]=rand()%20;
    while(mid[1]==mid[0]);
    do
        mid[2]=rand()%20;
    while(mid[2]==mid[0] || mid[2]==mid[1]);

    for(k=0,i=0;i<20;i++)                           /*获取各个非中心点*/
    {
        if(i!=mid[0]&&i!=mid[1]&&i!=mid[2])
            nmid[k++]=i;
    }

    printf("\rThe random  center point are :");
    for(i=0;i<3;i++)
        printf("%2d  ",mid[i]);
    printf("\r\nPress any key to continue---");
    getch();
}


double getminTC(int *m,int *n)
{
    double dist[20][20];
    double TC[3][17];
    double minTC;

    int i,j,h,b,c,most,second;
    double cjih,djj2,djh,dji,dib,dic;

    for(i=0;i<3;i++)                            /*获取非中心点到中心点的距离矩阵*/
        for(j=0;j<17;j++)
     dist[mid[i]][nmid[j]]=sqrt((point[mid[i]].x-point[nmid[j]].x)*(point[mid[i]].x-point[nmid[j]].x)+
           (point[mid[i]].y-point[nmid[j]].y)*(point[mid[i]].y-point[nmid[j]].y)+
                                       (point[mid[i]].z-point[nmid[j]].z)*(point[mid[i]].z-point[nmid[j]].z));

    for(j=0;j<17;j++)                           /*寻找第一和第二中心点*/
    {
        most=dist[mid[0]][nmid[j]]<=dist[mid[1]][nmid[j]] ? 0 : 1;
        if(dist[mid[most]][nmid[j]]>=dist[mid[2]][nmid[j]])
            most=2;

        switch (most)
     {
        case 0:
            second=dist[mid[1]][nmid[j]]>=dist[mid[2]][nmid[j]] ? 2 : 1;
            break;
        case 1:
            second=dist[mid[0]][nmid[j]]>=dist[mid[2]][nmid[j]] ? 2 : 0;
            break;
        case 2:
            second=dist[mid[0]][nmid[j]]>=dist[mid[1]][nmid[j]] ? 1 : 0;
     }

        point[nmid[j]].most=most;
        point[nmid[j]].second=second;
    }

    for(i=0;i<3;i++)
        for(h=0;h<17;h++)
        {           
            if(i==0)        /*计算中心点i的代价*/
                b=1,c=2;
            else if(i==1)
                b=0,c=2;
            else
                b=0,c=1;
            dib=sqrt((point[mid[i]].x-point[mid[b]].x)*(point[mid[i]].x-point[mid[b]].x)+
                     (point[mid[i]].y-point[mid[b]].y)*(point[mid[i]].y-point[mid[b]].y)+
                     (point[mid[i]].z-point[mid[b]].z)*(point[mid[i]].z-point[mid[b]].z));
            dic=sqrt((point[mid[i]].x-point[mid[c]].x)*(point[mid[i]].x-point[mid[c]].x)+
                     (point[mid[i]].y-point[mid[c]].y)*(point[mid[i]].y-point[mid[c]].y)+
                     (point[mid[i]].z-point[mid[c]].z)*(point[mid[i]].z-point[mid[c]].z));
            TC[i][h]=dib<dic ? dib : dic;
            if(dist[mid[i]][nmid[h]]<TC[i][h])
                TC[i][h]=dist[mid[i]][nmid[h]];

            for(j=0;j<17;j++)            /*计算h替换i的代价*/
      {
                djh=sqrt((point[nmid[j]].x-point[nmid[h]].x)*(point[nmid[j]].x-point[nmid[h]].x)+
                         (point[nmid[j]].y-point[nmid[h]].y)*(point[nmid[j]].y-point[nmid[h]].y)+
                         (point[nmid[j]].z-point[nmid[h]].z)*(point[nmid[j]].z-point[nmid[h]].z));
                if(point[nmid[j]].most==i)
          {
                    djj2=dist[mid[point[nmid[j]].second]][nmid[j]];
                    dji =dist[mid[i]][nmid[j]];
                    cjih=djj2<djh ? djj2-dji : djh-dji;
          }
          else
          {
                    djj2=dist[mid[point[nmid[j]].most]][nmid[j]];
                    cjih=djj2<djh ? 0 : djh-djj2;
          }
                TC[i][h]+=cjih;
      }
     }

    for(minTC=TC[*m=0][*n=0],b=0;b<3;b++)           /*寻找代价最小的替换点*/
        for(c=0;c<17;c++)
     {
            if(TC[b][c]<minTC)
                minTC=TC[*m=b][*n=c];
     }    

    return minTC;
}

void printgraph()
{
    int i;
    int x0=10,y0=230;
    int xk=3,yk=2;

    printf("\rThe graph is as follows:       ");
    line(x0,y0,x0,100*yk+y0);
    line(x0,100*yk+y0,100*xk+x0,100*yk+y0);

    for(i=0;i<17;i++)
    {
        line(point[nmid[i]].x*xk+x0,(100-point[nmid[i]].y)*yk+y0,
      point[mid[point[nmid[i]].most]].x*xk+x0,(100-point[mid[point[nmid[i]].most]].y)*yk+y0);

    }
    printf("\r\n\n\n\n\n\n\n\n\n\n\n\n\n\n\nPress any key to continue---");
    getch();
}