首页 > 代码库 > K-means算法C++实现

K-means算法C++实现

#include<bits/stdc++.h>
#define dimense 10
//10维数据
#define N 5005
#define MAX 0xffffff
#define clr(a) memset(a,0,sizeof(a))
using namespace std;
struct Point{
    double dir[dimense];
    int belong;
};
int num=5000;//数据量
int k=10;//k个中心
Point center[15];
Point data[N];
Point save[15][N];
int ct[15];

Point Mid(Point a[],int Num){
    Point mid;
    clr(mid.dir);
    for(int ii=0;ii<Num;ii++)
        for(int iii=0;iii<dimense;iii++){
            mid.dir[iii]+=a[ii].dir[iii];
        }
    for(int iii=0;iii<dimense;iii++)
        mid.dir[iii]/=Num;
    return mid;
}
double dis(Point a,Point b){
    double ret=0;
    for(int ii=0;ii<dimense;ii++){
        ret+=(a.dir[ii]-b.dir[ii])*(a.dir[ii]-b.dir[ii]);
    }
    return sqrt(ret);
}

int signate(Point a){
    double tmp=MAX;
    int pos;
    for(int ii=0;ii<k;ii++){
        if(dis(a,center[ii])<tmp)pos=ii,tmp=dis(a,center[ii]);
    }
    return pos;
}

double rec[N][15];
int sig[15];
int vis[N];

int main(){
    int i,j;
    clr(vis);
    clr(ct);
    freopen("In.txt","r",stdin);
    freopen("Out.txt","w",stdout);
    for(i=0;i<num;i++)
        for(j=0;j<dimense;j++)
            scanf("%lf",&data[i].dir[j]);
    srand(time(NULL));
    int tmp,cnt=0;
    while(cnt<k){
        tmp=rand()%num;
        if(vis[tmp])continue;
        else vis[tmp]=1,center[cnt++]=data[tmp];
    }
    for(i=0;i<k;i++){
        printf("第%d个中心:",i+1);
        for(j=0;j<dimense;j++){
            printf("%lf%c",center[i].dir[j],j==dimense-1?'\n':' ');
        }
    }

    for(i=0;i<num;i++){
        data[i].belong=signate(data[i]);
        save[data[i].belong][ct[data[i].belong]++]=data[i];
    }
    for(i=0;i<k;i++)
        printf("第%d个簇到底有多少个点%d\n",i+1,ct[i]);

    for(i=0;i<k;i++)
        center[i]=Mid(save[i],ct[i]);

    for(i=0;i<k;i++){
        printf("第%d个中心:",i+1);
        for(j=0;j<dimense;j++){
            printf("%lf%c",center[i].dir[j],j==dimense-1?'\n':' ');
        }
    }
    Point Last[15];
    for(i=0;i<k;i++)
        for(j=0;j<dimense;j++)
            Last[i].dir[j]=center[i].dir[j];
    int bre=1;
    int nnn=0;
    while(bre){
        nnn++;
        bre=0;
        clr(save);
        clr(ct);
        for(i=0;i<num;i++){
            data[i].belong=signate(data[i]);
            save[data[i].belong][ct[data[i].belong]++]=data[i];
        }
        for(i=0;i<k;i++)
            printf("第%d个簇到底有多少个点%d\n",i+1,ct[i]);

        for(i=0;i<k;i++)
            center[i]=Mid(save[i],ct[i]);

        for(i=0;i<k;i++){
            for(j=0;j<dimense;j++)
                if(Last[i].dir[j]!=center[i].dir[j]){
                    bre=1;
                    break;
                };
            if(bre==1)break;
        }
        for(i=0;i<k;i++)
            for(j=0;j<dimense;j++)
                Last[i].dir[j]=center[i].dir[j];

        for(i=0;i<k;i++){
            printf("第%d个中心:",i+1);
            for(j=0;j<dimense;j++){
                printf("%lf%c",center[i].dir[j],j==dimense-1?'\n':' ');
            }
        }
    }
    for(i=0;i<num;i++){
        printf("第%d个点属于第%d个簇\n",i+1,data[i].belong+1);
    }
    printf("次数%d\n",nnn);
    return 0;
}

复制去Google翻译翻译结果

K-means算法C++实现