C语言中K-means算法实现代码

#include<stdio.h> #include<stdlib.h> #include<string.h> #include<time.h> #include<math.h>  #define DIMENSIOM  2    //目前只是处理2维的数据 #define MAX_ROUND_TIME 100   //最大的聚类次数  typedef struct Item{   int dimension_1;    //用于存放第一维的数据   int dimension_2;    //用于存放第二维的数据   int clusterID;     //用于存放该item的cluster center是谁 }Item; Item* data;  typedef struct ClusterCenter{   double dimension_1;   double dimension_2;   int clusterID; }ClusterCenter; ClusterCenter* cluster_center_new;  int isContinue;  int* cluster_center;    //记录center double* distanceFromCenter; //记录一个“点”到所有center的距离 int data_size; char filename[200]; int cluster_count;  void initial(); void readDataFromFile(); void initial_cluster(); void calculateDistance_ToOneCenter(int itemID, int centerID, int count); void calculateDistance_ToAllCenter(int itemID); void partition_forOneItem(int itemID); void partition_forAllItem_OneCluster(int round); void calculate_clusterCenter(int round); void K_means(); void writeClusterDataToFile(int round); void writeClusterCenterToFile(int round); void compareNew_OldClusterCenter(double* new_X_Y); void test_1();  int main(int argc, char* argv[]){   if( argc != 4 )   {     printf("This application need other parameter to run:"         "/n/t/tthe first is the size of data set,"         "/n/t/tthe second is the file name that contain data"         "/n/t/tthe third indicate the cluster_count"         "/n");     exit(0);   }   srand((unsigned)time(NULL));   data_size = atoi(argv[1]);   strcat(filename, argv[2]);   cluster_count = atoi(argv[3]);    initial();   readDataFromFile();   initial_cluster();   //test_1();   //partition_forAllItem_OneCluster();   //calculate_clusterCenter();   K_means();   return 0; }  /*  * 对涉及到的二维动态数组根据main函数中传入的参数分配空间  * */ void initial(){   data = (Item*)malloc(sizeof(struct Item) * (data_size + 1));   if( !data )   {     printf("malloc error:data!");     exit(0);   }   cluster_center = (int*)malloc(sizeof(int) * (cluster_count + 1));   if( !cluster_center )   {     printf("malloc error:cluster_center!/n");     exit(0);   }   distanceFromCenter = (double*)malloc(sizeof(double) * (cluster_count + 1));   if( !distanceFromCenter )   {     printf("malloc error: distanceFromCenter!/n");     exit(0);   }   cluster_center_new = (ClusterCenter*)malloc(sizeof(struct ClusterCenter) * (cluster_count + 1));   if( !cluster_center_new )   {     printf("malloc cluster center new error!/n");     exit(0);   } }  /*  * 从文件中读入x和y数据  * */ void readDataFromFile(){   FILE* fread;   if( NULL == (fread = fopen(filename, "r")))   {     printf("open file(%s) error!/n", filename);     exit(0);   }   int row;   for( row = 1; row <= data_size; row++ )   {     if( 2 != fscanf(fread, "%d %d ", &data[row].dimension_1, &data[row].dimension_2))     {       printf("fscanf error: %d/n", row);     }     data[row].clusterID = 0;   } }  /*  * 根据从主函数中传入的@cluster_count(聚类的个数)来随机的选择@cluster_count个  * 初始的聚类的起点  * */  void initial_cluster(){   //辅助产生不重复的数   int* auxiliary;   int i;   auxiliary = (int*)malloc(sizeof(int) * (data_size + 1));   if( !auxiliary )   {     printf("malloc error: auxiliary");     exit(0);   }   for( i = 1; i <= data_size; i++ )   {     auxiliary[i] = i;   }      //产生初始化的cluster_count个聚类   int length = data_size;   int random;   for( i = 1; i <= cluster_count; i++ )   {     random = rand()%length + 1;     //printf("%d /n", auxiliary[random]);     //data[auxiliary[random]].clusterID = auxiliary[random];     cluster_center[i] = auxiliary[random];     auxiliary[random] = auxiliary[length--];   }      for( i = 1; i <= cluster_count; i++ )   {     cluster_center_new[i].dimension_1 = data[cluster_center[i]].dimension_1;     cluster_center_new[i].dimension_2 = data[cluster_center[i]].dimension_2;     cluster_center_new[i].clusterID = i;     data[cluster_center[i]].clusterID = i;   } }  /*  * 计算一个点(还没有划分到cluster center的点)到一个cluster center的distance  *   @itemID:  不属于任何cluster中的点  *   @centerID: center的ID  *   @count:   表明在计算的是itemID到第几个@center的distance，并且指明了结果放在distanceFromCenter的第几号元素  * */ void calculateDistance_ToOneCenter(int itemID,int centerID){   distanceFromCenter[centerID] = sqrt( (data[itemID].dimension_1-cluster_center_new[centerID].dimension_1)*(double)(data[itemID].dimension_1-cluster_center_new[centerID].dimension_1) + (double)(data[itemID].dimension_2-cluster_center_new[centerID].dimension_2) * (data[itemID].dimension_2-cluster_center_new[centerID].dimension_2) ); }  /*  * 计算一个点(还没有划分到cluster center的点)到每个cluster center的distance  * */ void calculateDistance_ToAllCenter(int itemID){   int i;   for( i = 1; i <= cluster_count; i++ )   {     calculateDistance_ToOneCenter(itemID, i);   } }  void test_1() {   calculateDistance_ToAllCenter(3);   int i;   for( i = 1; i <= cluster_count; i++ )   {     printf("%f ", distanceFromCenter[i]);   } }  /*  * 在得到任一的点(不属于任一cluster的)到每一个cluster center的distance之后，决定它属于哪一个cluster center,即取距离最小的  *   函数功能：得到一个item所属的cluster center  * */ void partition_forOneItem(int itemID){   //操作对象是 distanceFromCenter和cluster_center   int i;   int min_index = 1;   double min_value = distanceFromCenter[1];   for( i = 2; i <= cluster_count; i++ )   {     if( distanceFromCenter[i] < min_value )     {       min_value = distanceFromCenter[i];       min_index = i;     }   }    data[itemID].clusterID = cluster_center_new[min_index].clusterID; }  /*  * 得到所有的item所属于的cluster center , 在一轮的聚类中  * */ void partition_forAllItem_OneCluster(int round){        //changed!!!!!!!!!!!!!!!!!!!!!!!!   int i;   for( i = 1; i <= data_size; i++ )   {     if( data[i].clusterID != 0 )       continue;     else     {       calculateDistance_ToAllCenter(i);  //计算i到所有center的distance       partition_forOneItem(i);    //根据distance对i进行partition     }   }    //把聚类得到的数据写入到文件中   writeClusterDataToFile(round); }  /*  * 将聚类得到的数据写入到文件中，每一个类写入一个文件中  *   @round: 表明在进行第几轮的cluster，该参数的另一个作用是指定了文件名字中的第一个项.  * */ void writeClusterDataToFile(int round){   int i;   char filename[200];   FILE** file;   file = (FILE**)malloc(sizeof(FILE*) * (cluster_count + 1));   if( !file )   {     printf("malloc file error!/n");     exit(0);   }   for( i = 1; i <= cluster_count; i++ )   {     sprintf(filename, ".//ClusterProcess//round%d_cluster%d.data", round, i);     if( NULL == (file[i] = fopen(filename, "w")))     {       printf("file open(%s) error!", filename);       exit(0);     }   }      for( i = 1; i <= data_size; i++ )   {     //sprintf(filename, ".//ClusterProcess//round%d_cluster%d.data", round, data[i].clusterID);     fprintf(file[data[i].clusterID], "%d/t%d/n", data[i].dimension_1, data[i].dimension_2);   }   for( i = 1; i <= cluster_count; i++ )   {     //sprintf(filename, ".//ClusterProcess//round%d_cluster%d.data", round, i);     fclose(file[i]);   } }  /*  * 重新计算新的cluster center  * */ void calculate_clusterCenter(int round){          //changed!!!!!!!!!!!!!!!!!!!!!!   int i;   double* new_X_Y;  /*           用来计算和保存新的cluster center的值，同样的，0号元素不用。1,2号元素分别用来           存放第一个聚类的所有的项的x和y的累加和。3,4号元素分别用来存放第二个聚类的所有           的项的x和y的累加和......         */   new_X_Y = (double*)malloc(sizeof(double) * (2 * cluster_count + 1));   if( !new_X_Y )   {     printf("malloc error: new_X_Y!/n");     exit(0);   }   //初始化为0   for( i = 1; i <= 2*cluster_count; i++ )     new_X_Y[i] = 0.0;    //用来统计属于各个cluster的item的个数   int* counter;   counter = (int*)malloc(sizeof(int) * (cluster_count + 1));   if( !counter )   {     printf("malloc error: counter/n");     exit(0);   }   //初始化为0   for( i = 1; i <= cluster_count; i++ )     counter[i] = 0;    for( i = 1; i <= data_size; i++ )   {     new_X_Y[data[i].clusterID * 2 - 1] += data[i].dimension_1;     new_X_Y[data[i].clusterID * 2] += data[i].dimension_2;     counter[data[i].clusterID]++;   }    for( i = 1; i <= cluster_count; i++ )   {     new_X_Y[2 * i - 1] = new_X_Y[2 * i - 1] / (double)(counter[i]);     new_X_Y[2 * i] = new_X_Y[2 * i] / (double)(counter[i]);   }      //要将cluster center的值保存在文件中，后续作图   writeClusterCenterToFile(round);      /*    * 在这里比较一下新的和旧的cluster center值的差别。如果是相等的，则停止K-means算法。    * */   compareNew_OldClusterCenter(new_X_Y);    //将新的cluster center的值放入cluster_center_new   for( i = 1; i <= cluster_count; i++ )   {     cluster_center_new[i].dimension_1 = new_X_Y[2 * i - 1];     cluster_center_new[i].dimension_2 = new_X_Y[2 * i];     cluster_center_new[i].clusterID = i;   }   free(new_X_Y);   free(counter);    //在重新计算了新的cluster center之后，意味着我们要重新来为每一个Item进行聚类，所以data中用于表示聚类ID的clusterID   //要都重新置为0。   for( i = 1; i <= data_size; i++ )   {     data[i].clusterID = 0;   } }  /*  * 将得到的新的cluster_count个cluster center的值保存在文件中。以便于观察聚类的过程。  * */ void writeClusterCenterToFile(int round){   FILE* file;   int i;   char filename[200];   sprintf(filename, ".//ClusterProcess//round%d_clusterCenter.data", round);   if( NULL == (file = fopen(filename, "w")))   {     printf("open file(%s) error!/n", filename);     exit(0);   }    for( i = 1; i <= cluster_count; i++ )   {     fprintf(file, "%f/t%f/n", cluster_center_new[i].dimension_1, cluster_center_new[i].dimension_2);   }    for( i = 1; i <= cluster_count; i++ )   {     fclose(file);   } }  /*  * 比较新旧的cluster center的差异  * */ void compareNew_OldClusterCenter(double* new_X_Y){   int i;   isContinue = 0;       //等于0表示的是不要继续   for( i = 1; i <= cluster_count; i++ )   {     if( new_X_Y[2 * i - 1] != cluster_center_new[i].dimension_1 || new_X_Y[2 * i] != cluster_center_new[i].dimension_2)     {       isContinue = 1;   //要继续       break;     }   } }  /************************************************************************************************  *         K-means算法            *     ***********************************************************************************************/ void K_means(){   int times_cluster;   for( times_cluster = 1; times_cluster <= MAX_ROUND_TIME; times_cluster++ )   {     printf("/n            times : %d             /n", times_cluster);     partition_forAllItem_OneCluster(times_cluster);     calculate_clusterCenter(times_cluster);     if( 0 == isContinue )     {       break;       //printf("/n/nthe application can stop!/n/n");     }   } }