数据挖掘K-平均值(K-means)程序C实现

    k平均聚类发明于1956年， 该算法最常见的形式是采用被称为劳埃德算法(Lloyd algorithm)的迭代式改进探索法。劳埃德算法首先把输入点分成k个初始化分组，可以是随机的或者使用一些启发式数据。然后计算每组的中心点，根据中心点的位置把对象分到离它最近的中心，重新确定分组。继续重复不断地计算中心并重新分组，直到收敛，即对象不再改变分组（中心点位置不再改变）。 　　劳埃德算法和k平均通常是紧密联系的，但是在实际应用中，劳埃德算法是解决k平均问题的启发式法则，对于某些起始点和重心的组合，劳埃德算法可能实际上收敛于错误的结果。（上面函数中存在的不同的最优解） 　　虽然存在变异，但是劳埃德算法仍旧保持流行，因为它在实际中收敛非常快。实际上，观察发现迭代次数远远少于点的数量。然而最近，David Arthur和Sergei Vassilvitskii提出存在特定的点集使得k平均算法花费超多项式时间达到收敛。 　　近似的k平均算法已经被设计用于原始数据子集的计算。 　　从算法的表现上来说，它并不保证一定得到全局最优解，最终解的质量很大程度上取决于初始化的分组。由于该算法的速度很快，因此常用的一种方法是多次运行k平均算法，选择最优解。 　　k平均算法的一个缺点是，分组的数目k是一个输入参数，不合适的k可能返回较差的结果。另外，算法还假设均方误差是计算群组分散度的最佳参数。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef struct point{
	double x;//x坐标 
	double y;//y坐标 
	int n;//属于哪个簇
	char label[10];//点标号 
}Point;

int main(){
	int n;
	int i, j, k = 0, l = 0;
	int m;//点的个数 
	double sq;
	double min = 65535;//存储最小的点距离
	int pos;//标记最小点集 
	char c;
	Point *center;//存储中心点 
	Point *pot;//存储坐标点 
	double *dis;//存储距离的
	
	printf("输入中心点的个数：\n");
	scanf("%d", &n);
	getchar();
	for(i = 0; i < n; i++){//分配空间 
		center = calloc(n, sizeof(struct point));	
		dis = calloc(n, sizeof(double)); 
		if(center == NULL || dis == NULL){
			printf("calloc() error\n");
			exit(1);
		}
	}
		
	for(i = 0; i < n; i++){
		printf("输入第%d个中心点的坐标,usage:a1 (4.2,5.3)\n", (i + 1));
		scanf("%s (%lf,%lf)", &(center[i].label), &(center[i].x), &(center[i].y));
		getchar();
	}
	for(i = 0; i < n; i++){
		printf("%s(%.2f,%.2f)\n", center[i].label, center[i].x, center[i].y);
	}
		
	printf("请输入一共有几个点：\n");
	scanf("%d", &m);
	getchar();
	for(i = 0; i < m; i++){//分配空间 
		pot = calloc(m, sizeof(struct point));	
		if(pot == NULL){
			printf("error\n");
			exit(1);
		}
	}
	
	for(i = 0; i < m; i++){
		printf("请输入第%d个点的坐标usage:a1 (4.2,5.3)\n", i+1);
		scanf("%s (%lf,%lf)", &pot[i].label, &pot[i].x, &pot[i].y);
		getchar();
	}
		
	for(i = 0; i < m; i++){
		printf("%s(%.2f,%.2f)\n", pot[i].label, pot[i].x, pot[i].y);
	}
	while(k < 3){//迭代3次 	
		printf("第%d次迭代\n", k+1); 
		for(i = 0; i < m; i++){
			min = 65535;
			printf("%s", pot[i].label);
			for(j = 0; j < n; j++){
				dis[j] = sqrt(pow((pot[i].x - center[j].x), 2) + pow((pot[i].y - center[j].y), 2));
				//printf("点(%.2lf,%.2lf)距离中心点为(%.2lf,%.2lf)的距离为%.3lf\n", pot[i].x, pot[i].y, center[j].x, center[j].y, dis[j]);
				printf("  和%s相距%.3lf", center[j].label, dis[j]);
				if(min > dis[j]){
					min = dis[j];
					pos = j;
					pot[i].n = j;//存储他的分类 
				}
			}
			printf("\n");
		}
		
		//计算新的中心点
		for(i = 0; i < n; i++){//清空原先的中心点的值 
			center[i].x = 0;
			center[i].y = 0;
			center[i].n = 0;
		}
		for(i = 0; i < m; i++){
			center[pot[i].n].x += pot[i].x;
			center[pot[i].n].y += pot[i].y;
			center[pot[i].n].n++;//记下有几个属于自己的点
		}
		for(i = 0; i < n; i++, l = 0){
				printf("\n%s集的元素:(", center[i].label);
				for(j = 0; j < m; j++){
					if(i == pot[j].n){
						printf("%s", pot[j].label);
						l++;
						if(center[i].n > l){
							printf(", ");
						}
					}
				}//end for
				printf(")");	
		}
		printf("\n");
		for(i = 0; i < n; i++){
			center[i].x = center[i].x/center[i].n;
			center[i].y = center[i].y/center[i].n;
		}
		k++;
		getchar(); 
	}
	return 0;
} 

运行结果为

：