#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");     }   } }