K-MEANS算法的C++實作

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#define NA 4 /* 資料維數 */

#define K 3 /* 聚類數 */

#define Psize 50 /* 種群大小 */

#define T 30 /* 最大疊代數 */

#define ED 0.0000001 /* 結束條件 */

typedef struct {

double p[NA];

double distance[K];

}Point;

typedef struct {

Point clu_cent[K]; /* 即cluster_center 簇類中心 */

int cluster[K][Psize]; /* 簇類數組 */

int cluster_num[K]; /* 簇類中一組資料的編号 */

double fitness; /* 樣本适應度值,用于判斷結束條件 */

double old_fitness; /* 前一次疊代的适應度值 */

double Je; /* 所有樣本的平方誤差和 */

}Pop;

/* 聲明函數 */

int Is_equal(int a[], int n, int b);

double Euclid(int x, int y);

void input_data();

void Init_center();

void calculate_distance();

void Make_new_cluster();

void Make_new_center();

void output_info(int flag);

Point all_data[Psize]; /* 資料大小 */

Pop pop;

/************************************************

* 從外部檔案導入資料，對于沒有資料檔案将報錯， *

* 資料檔案的格式根據 NA 決定，例如NA = 4時，測 *

* 試資料為四維，則test.data 為： *

* 1 2 3 4 *

* 1.0 1.2 1.3 1.4 *

* ...... *

* ...... *

***********************************************/

void input_data()

{

FILE *infile;

int i, j;

double data;

if((infile = fopen("test.data", "r")) == NULL){

printf("沒有test.data這個檔案，無法導入資料/n");

exit(1);

}

for(i = 0; i < Psize; i++)

for(j = 0; j < NA; j++){

fscanf(infile, "%lf", &data);

all_data[i].p[j] = data;

// printf("%d --%d %lf/n", i, j, all_data[i].p[j]);

}

fclose(infile); /* 關閉檔案描述符 */

}

/***************************************************

* 随機初始化聚類質心，當随機數有相同時跳過繼續執行*

**************************************************/

void Init_center()

{

int i, j;

int num = 0;

int rand_num;

int rand_num_tmp[K];

/* 随機産生三個0～Psize的數 */

while(num < K){

rand_num = rand() % Psize;

if(!Is_equal(rand_num_tmp, num, rand_num))

rand_num_tmp[num++] = rand_num;

}

for(i = 0; i < K; i++){

// printf("初始化質心%d:/n", i + 1);

for(j = 0; j < NA; j++){

pop.clu_cent[i].p[j] = all_data[rand_num_tmp[i]].p[j];

// printf("%lf ",pop.clu_cent[i].p[j]);

}

printf("/n");

}

}

/**********************************

* 檢查資料是否有相等,相等傳回1 *

*********************************/

int Is_equal(int a[], int n, int b)

{

int i;

for(i = 0; i < n; i++)

if(a[i] == b) return 1;

return 0;

}

/********************************************

* 計算Psize組資料到K個質心的歐幾裡德距離*

*******************************************/

void calculate_distance()

{

int i, j;

for(i = 0; i < Psize; i++)

for(j = 0; j < K; j++){

all_data[i].distance[j] = Euclid(i, j);

// printf("%d---%d--- %lf /n", i, j, all_data[i].distance[j]);

}

}

/************************************************

* 此函數為歐幾裡德距離公式函數,此處用于計算*

* 一組資料到對應簇中心的歐幾裡德距離。 *

***********************************************/

double Euclid(int x, int y)

{

int i;

double distance = 0;

for(i = 0; i < NA; i++){

distance += pow((all_data[x].p[i] - pop.clu_cent[y].p[i]), 2);

}

distance = sqrt(distance);

return distance;

}

/************************

* 将資料進行簇集歸類 *

***********************/

void Make_new_cluster()

{

int i, j;

double min;

for(i = 0; i < K; i++) /* 初始化編号 */

pop.cluster_num[i] = 0;

for(i = 0; i < Psize; i++){

int index = 0;

min = all_data[i].distance[0];

for(j = 1; j < K; j++){ /* 篩選到簇心歐幾裡德最小的 */

if(all_data[i].distance[j] < min){

min = all_data[i].distance[j];

index = j;

}

}

/* 劃分簇集 */

pop.cluster[index][pop.cluster_num[index]++] = i;

}

/* 計算所有樣本的平方誤差和 */

pop.Je = 0;

for(i = 0; i < K; i++)

for(j = 0; j < pop.cluster_num[i]; j++){

/* 樣本到簇心的值即為其歐幾裡德距離 */

pop.Je +=pow(all_data[pop.cluster[i][j]].distance[i],2);

}

pop.old_fitness = pop.fitness; /* 前一次疊代适應度值 */

// printf("old_fitness = %lf/n", pop.old_fitness);

pop.fitness = pop.Je; /* 所有樣本平方誤差和即為适應度值 */

}

/*************************************************

* 更新簇心，即求其群類的平均距離為新的簇心 *

************************************************/

void Make_new_center()

{

int i, j, n;

double tmp_sum;

for(i = 0; i < K; i++)

for(j = 0; j < NA; j++){

tmp_sum = 0;

for(n = 0; n < pop.cluster_num[i]; n++){

/* 第i個簇的第j維數的所有資料和 */

tmp_sum += all_data[pop.cluster[i][n]].p[j];

}

/* 取平均數得到新的簇中心 */

pop.clu_cent[i].p[j] = tmp_sum / pop.cluster_num[i];

}

}

/********************************

* 輸出資訊函數 *

* 顯示格式為： *

* 質心K: *

* NA維的質心資料 *

* 簇類K： *

* NA維屬于簇類K的資料 *

* ...... *

* ...... *

*******************************/

void output_info(int flag)

{

int i, j, n;

for(i = 0; i < K; i++){

if(flag == 0){

printf("初始化質心%d:/n", i + 1);

for(n = 0; n < NA; n++)

printf("%lf ",pop.clu_cent[i].p[n]);

} else if(flag == 1){

printf("最終質心%d:/n", i + 1);

for(n = 0; n < NA; n++)

printf("%lf ",pop.clu_cent[i].p[n]);

}

printf("/n簇類%d:/n", i + 1);

for(j = 0; j < pop.cluster_num[i]; j++){

for(n = 0; n < NA; n++){

printf("%lf ",

all_data[pop.cluster[i][j]].p[n]);

}

printf("/n");

}

}

}

/********************************

* 主函數 *

*******************************/

int main()

{

int i;

double differ = 1; /* 适應度內插補點 */

int flag = 0; /* 用來标示是顯示初始資料還是聚類後的資料 */

input_data(); /* 導入資料 */

Init_center(); /* 初始化質心 */

for(i = 0; (i < T) && (differ > ED); i++){

calculate_distance(); /* 計算歐幾裡德距離 */

Make_new_cluster(); /* 産生新的聚類 */

if(flag == 0){

output_info(flag); /* 輸出第一次聚類後的結果 */

flag = 1;

}

Make_new_center(); /* 對新的聚類産生新的質心 */

differ = pop.old_fitness - pop.fitness; /* 判斷條件 */

differ = fabs(differ);

// printf("differ = %lf/n", differ);

// printf("old_fitness = %lf/n", pop.old_fitness);

// printf("fitness = %lf/n", pop.fitness);

}

printf("+++++++++++++++++++++++++++++++++++++++++++++++++++++++/n");

output_info(flag); /* 聚類後顯示結果 */

return 0;

}