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;

}