K-MEANS算法

1. [代码][C/C++/Objective-C]代码    

001	#include <stdio.h>

002	#include <stdlib.h>

003	#include <math.h>

004

005	#define NA  4       /* 数据维数 */

006	#define K   3       /* 聚类数 */

007	#define Psize   50      /* 种群大小 */

008	#define T   30      /* 最大迭代数 */

009	#define ED  0.0000001   /* 结束条件 */

010

011	typedef struct {

012	double p[NA];

013	double distance[K];

014

}Point;

015

016	typedef struct {

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

018	int cluster[K][Psize];  /* 簇类数组 */

019	int cluster_num[K]; /* 簇类中一组数据的编号 */

020	double fitness;     /* 样本适应度值,用于判断结束条件 */

021	double old_fitness; /* 前一次迭代的适应度值 */

022	double Je;      /* 所有样本的平方误差和 */

023

}Pop;

024

025	/* 声明函数 */

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

027	double Euclid(int x, int y);

028	void input_data();

029	void Init_center();

030	void calculate_distance();

031	void Make_new_cluster();

032	void Make_new_center();

033	void output_info(int flag);

034

035

036	Point all_data[Psize];      /* 数据大小 */

037

Pop pop;

038

039	/************************************************

040	* 从外部文件导入数据，对于没有数据文件将报错， *

041	* 数据文件的格式根据 NA 决定，例如NA = 4时，测 *

042	* 试数据为四维，则test.data 为：     *

043	*  1   2   3   4       *

044	*  1.0 1.2 1.3 1.4     *

045	*      ......              *

046	*      ......              *

047	***********************************************/

048	void input_data()

049

{

050	FILE *infile;

051

int i, j;

052	double data;

053

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

055	printf("没有test.data这个文件，无法导入数据\n");

056

exit(1);

057

}

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

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

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

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

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

063

}

064	fclose(infile);     /* 关闭文件描述符 */

065

}

066

067	/***************************************************

068	* 随机初始化聚类质心，当随机数有相同时跳过继续执行*

069	**************************************************/

070	void Init_center()

071

{

072

int i, j;

073	int num = 0;

074	int rand_num;

075	int rand_num_tmp[K];

076	/* 随机产生三个0～Psize的数 */

077	while(num < K){

078	rand_num = rand() % Psize;

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

080	rand_num_tmp[num++] = rand_num;

081

}

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

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

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

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

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

087

}

088	printf("\n");

089

}

090

}

091

092	/**********************************

093	* 检查数据是否有相等,相等返回1 *

094	*********************************/

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

096

{

097

int i;

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

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

100

return 0;

101

}

102

103	/********************************************

104	* 计算Psize组数据到K个质心的欧几里德距离*

105	*******************************************/

106	void calculate_distance()

107

{

108

int i, j;

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

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

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

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

113

}

114

}

115

116	/************************************************

117	* 此函数为欧几里德距离公式函数,此处用于计算*

118	* 一组数据到对应簇中心的欧几里德距离。   *

119	***********************************************/

120	double Euclid(int x, int y)

121

{

122

int i;

123	double distance = 0;

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

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

126

}

127	distance = sqrt(distance);

128	return distance;

129

}

130

131

132	/************************

133	* 将数据进行簇集归类 *

134	***********************/

135	void Make_new_cluster()

136

{

137

int i, j;

138

139	double min;

140

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

142	pop.cluster_num[i] = 0;

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

144	int index = 0;

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

146	for(j = 1; j < K; j++){      /* 筛选到簇心欧几里德最小的 */

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

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

149	index = j;

150

}

151

}

152	/* 划分簇集 */

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

154

}

155	/* 计算所有样本的平方误差和 */

156	pop.Je = 0;

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

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

159	/* 样本到簇心的值即为其欧几里德距离 */

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

161

}

162	pop.old_fitness = pop.fitness;  /* 前一次迭代适应度值 */

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

164	pop.fitness = pop.Je;   /* 所有样本平方误差和即为适应度值 */

165

}

166

167	/*************************************************

168	* 更新簇心，即求其群类的平均距离为新的簇心  *

169	************************************************/

170	void Make_new_center()

171

{

172	int i, j, n;

173	double tmp_sum;

174

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

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

177	tmp_sum = 0;

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

179	/* 第i个簇的第j维数的所有数据和 */

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

181

}

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

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

184

}

185

}

186

187	/********************************

188	*  输出信息函数      *

189	* 显示格式为：       *

190	* 质心K:         *

191	* NA维的质心数据     *

192	* 簇类K：         *

193	* NA维属于簇类K的数据      *

194	*  ......          *

195	*  ......          *

196	*******************************/

197	void output_info(int flag)

198

{

199	int i, j, n;

200

201

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

203	if(flag == 0){

204	printf("初始化质心%d:\n", i + 1);

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

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

207	} else if(flag == 1){

208	printf("最终质心%d:\n", i + 1);

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

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

211

}

212	printf("\n簇类%d:\n", i + 1);

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

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

215	printf("%lf ",

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

217

}

218	printf("\n");

219

}

220

}

221

}

222

223	/********************************

224	*      主函数     *

225	*******************************/

226	int main()

227

{

228

int i;

229	double differ = 1;  /* 适应度差值 */

230	int flag = 0;       /* 用来标示是显示初始数据还是聚类后的数据 */

231	input_data();       /* 导入数据 */

232	Init_center();      /* 初始化质心 */

233

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

235	calculate_distance();       /* 计算欧几里德距离 */

236	Make_new_cluster();     /* 产生新的聚类 */

237	if(flag == 0){

238	output_info(flag);  /* 输出第一次聚类后的结果 */

239

flag = 1;

240

}

241	Make_new_center();      /* 对新的聚类产生新的质心 */

242	differ = pop.old_fitness - pop.fitness; /* 判断条件 */

243	differ = fabs(differ);

244

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

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

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

248

}

249

250	printf("+++++++++++++++++++++++++++++++++++++++++++++++++++++++\n");

251	output_info(flag);  /* 聚类后显示结果 */

252

253

return 0;

254

}