kmeans算法c语言实现,能对不同维度的数据进行聚…

2018-06-18 04:14:18来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

  最近在苦于思考kmeans算法的MPI并行化,花了两天的时间把该算法看懂和实现了串行版。

 

  聚类问题就是给定一个元素集合V,其中每个元素具有d个可观察属性,使用某种算法将V划分成k个子集,要求每个子集内部的元素之间相异度尽可能低,而不同子集的元素相异度尽可能高。

  下面是google到该算法的一个流程图,表意清楚:

  1、随机选取数据集中的k个数据点作为初始的聚类中心:

  

  2、分别计算每个数据点到每个中心的距离,选取距离最短的中心点作为其聚类中心:

  

  3、利用目前得到的聚类重新计算中心点:

  

  4、重复步骤2和3直到收敛(达到最大迭代次数或聚类中心不再移动): 

   

  code:

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <math.h>
  4 #include <time.h>
  5 
  6 int K,N,D;  //聚类的数目,数据量,数据的维数
  7 float **data;  //存放数据
  8 int *in_cluster;  //标记每个点属于哪个聚类
  9 float **cluster_center;  //存放每个聚类的中心点
 10 
 11 float **array(int m,int n);
 12 void freearray(float **p);
 13 float **loadData(int *k,int *d,int *n);
 14 float getDistance(float avector[],float bvector[],int n);
 15 void cluster();
 16 float getDifference();
 17 void getCenter(int in_cluster[]);
 18 
 19 int  main()
 20 {
 21     int i,j,count=0;
 22     float temp1,temp2;
 23     data=loadData(&K,&D,&N);
 24     printf("Data sets:\n");
 25     for(i=0;i<N;i++)
 26         for(j=0;j<D;j++){
 27             printf("%-8.2f",data[i][j]);
 28             if((j+1)%D==0)    putchar('\n');
 29         }
 30     printf("-----------------------------\n");
 31 
 32     srand((unsigned int)(time(NULL)));  //随机初始化k个中心点
 33     for(i=0;i<K;i++)
 34         for(j=0;j<D;j++)
 35             cluster_center[i][j]=data[(int)((double)N*rand()/(RAND_MAX+1.0))][j];
 36 
 37     cluster();  //用随机k个中心点进行聚类
 38     temp1=getDifference();  //第一次中心点和所属数据点的距离之和
 39     count++;
 40     printf("The difference between data and center is: %.2f\n\n", temp1);
 41 
 42     getCenter(in_cluster);
 43     cluster();  //用新的k个中心点进行第二次聚类
 44     temp2=getDifference();
 45     count++;
 46     printf("The difference between data and center is: %.2f\n\n",temp2);
 47 
 48     while(fabs(temp2-temp1)!=0){   //比较前后两次迭代,若不相等继续迭代
 49         temp1=temp2;
 50         getCenter(in_cluster);
 51         cluster();
 52         temp2=getDifference();
 53         count++;
 54         printf("The %dth difference between data and center is: %.2f\n\n",count,temp2);
 55     }
 56 
 57     printf("\nThe total number of cluster is: %d\n",count);  //统计迭代次数
 58     //system("pause");  //gcc编译需删除 
 59     return 0;
 60 }
 61 
 62 
 63 //动态创建二维数组
 64 float **array(int m,int n)
 65 {
 66     int i;
 67     float **p;
 68     p=(float **)malloc(m*sizeof(float *));
 69     p[0]=(float *)malloc(m*n*sizeof(float));
 70     for(i=1;i<m;i++)    p[i]=p[i-1]+n;
 71     return p;
 72 }
 73 
 74 //释放二维数组所占用的内存
 75 void freearray(float **p)
 76 {
 77     free(*p);
 78     free(p);
 79 }
 80 
 81 //从data.txt导入数据,要求首行格式:K=聚类数目,D=数据维度,N=数据量
 82 float **loadData(int *k,int *d,int *n)
 83 {
 84     int i,j; 
 85     float **arraydata;
 86     FILE *fp;
 87     if((fp=fopen("data.txt","r"))==NULL)    fprintf(stderr,"cannot open data.txt!\n");
 88     if(fscanf(fp,"K=%d,D=%d,N=%d\n",k,d,n)!=3)        fprintf(stderr,"load error!\n");
 89     arraydata=array(*n,*d);  //生成数据数组
 90     cluster_center=array(*k,*d);  //聚类的中心点
 91     in_cluster=(int *)malloc(*n * sizeof(int));  //每个数据点所属聚类的标志数组
 92     for(i=0;i<*n;i++)
 93         for(j=0;j<*d;j++)
 94             fscanf(fp,"%f",&arraydata[i][j]);  //读取数据点
 95     return arraydata;
 96 }
 97 
 98 //计算欧几里得距离
 99 float getDistance(float avector[],float bvector[],int n)
100 {
101     int i;
102     float sum=0.0;
103     for(i=0;i<n;i++)
104         sum+=pow(avector[i]-bvector[i],2);
105     return sqrt(sum);
106 }
107 
108 //把N个数据点聚类,标出每个点属于哪个聚类
109 void cluster()
110 {
111     int i,j;
112     float min;
113     float **distance=array(N,K);  //存放每个数据点到每个中心点的距离
114     //float distance[N][K];  //也可使用C99变长数组
115     for(i=0;i<N;++i){
116         min=9999.0;
117         for(j=0;j<K;++j){
118             distance[i][j] = getDistance(data[i],cluster_center[j],D);
119             //printf("%f\n", distance[i][j]);
120             if(distance[i][j]<min){
121                 min=distance[i][j];
122                 in_cluster[i]=j;
123             }
124         }
125         printf("data[%d] in cluster-%d\n",i,in_cluster[i]+1);
126     }
127     printf("-----------------------------\n");
128     free(distance);
129 }
130 
131 //计算所有聚类的中心点与其数据点的距离之和
132 float getDifference()
133 {
134     int i,j;
135     float sum=0.0;
136     for(i=0;i<K;++i){
137         for(j=0;j<N;++j){
138             if(i==in_cluster[j])
139                 sum+=getDistance(data[j],cluster_center[i],D);
140         }
141     }
142     return sum;
143 }
144 
145 //计算每个聚类的中心点
146 void getCenter(int in_cluster[])
147 {
148     float **sum=array(K,D);  //存放每个聚类中心点
149     //float sum[K][D];  //也可使用C99变长数组
150     int i,j,q,count;
151     for(i=0;i<K;i++)
152         for(j=0;j<D;j++)
153             sum[i][j]=0.0;
154     for(i=0;i<K;i++){
155         count=0;  //统计属于某个聚类内的所有数据点
156         for(j=0;j<N;j++){
157             if(i==in_cluster[j]){
158                 for(q=0;q<D;q++)
159                     sum[i][q]+=data[j][q];  //计算所属聚类的所有数据点的相应维数之和
160                 count++;
161             }
162         }
163         for(q=0;q<D;q++)
164             cluster_center[i][q]=sum[i][q]/count;
165     }
166     printf("The new center of cluster is:\n");
167     for(i = 0; i < K; i++)
168         for(q=0;q<D;q++){
169             printf("%-8.2f",cluster_center[i][q]);
170             if((q+1)%D==0)    putchar('\n');
171     }
172     free(sum);
173 }

 

  

  该程序支持不同维度的数据集,一个示例的数据集 data.txt如下:

  K=3,D=3,N=15

  -25 22.2 35.34
  31.2 -14.4 23
  32.02 -23 24.44
  -25.35 36.3 -33.34
  -20.2 27.333 -28.22
  -15.66 17.33 -23.33
  26.3 -31.34 16.3
  -22.544 16.2 -32.22
  12.2 -15.22 22.11
  -41.241 25.232 -35.338
  -22.22 45.22 23.55
  -34.22 50.14 30.98
  15.23 -30.11 20.987
  -32.5 15.3 -25.22
  -38.97 20.11 33.22 

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:modelsim如何使用tcl脚本来写编译文件

下一篇:undefined reference to `omp_get_max_threads&#39;