k-means.cpp

这是K均值算法,采用c语言编写,K的取值为2,大家可以改变K的值来进行测试

// 作者: 李刚
// 学号: 0720080195
// 学校: 同济大学模式识别

#include "stdafx.h"


///////////////////////////////////K-means 算法////////////////////////////////////////////////////////
//第一步：选K个初始聚类中心，z1(1)，z2(1)，…，zK(1)，其中括号内的序号为寻找聚类中心的迭代运算的次序号。
//聚类中心的向量值可任意设定，例如可选开始的K个模式样本的向量值作为初始聚类中心。
//
//第二步：逐个将需分类的模式样本{x}按最小距离准则分配给K个聚类中心中的某一个zj(1).
//
//第三步：计算各个聚类中心的新的向量值，zj(k+1)，j=1,2,…,K求各聚类域中所包含样本的均值向量：
//
//第四步: 迭代直到收敛
/////////////////////////////////////////////////////////////////////////////////////////////////////


#define MAX_COL 4
#define MAX_ROW 150
#define K 3

typedef struct Cluster
{
	bool data[MAX_ROW];
	float center[MAX_COL];
	int count;
}Cluster;


typedef struct Data
{
	float data[MAX_ROW][MAX_COL];
}Data;


// 计算簇的聚类中心值.
// cluster 表示被传入的聚类
void RefreshCenter(Cluster *cluster, Data* data)
{
	int i = 0; 
	int j = 0;
	int count;
	for(j = 0; j < MAX_COL; j++)
	{
		float result = 0;
		count = 0;

		for(i = 0;i < MAX_ROW; i++)
		{
			if(cluster->data[i])
			{
				result = result + data->data[i][j];
				count++;
			}
		}
		if(count ==0)
		{
			printf("Error.");
			return;
		}
		cluster->center[j] = result / count;
		cluster->count = count;
	}
}

// 计算第i个向量到cluster聚类中心的距离
float GetDistance(int i, Cluster* cluster, Data* data)
{
	float dis = 0;
	int col =0;
	for(;col < MAX_COL; col++)
	{
		dis = dis + (data->data[i][col] - cluster->center[col])*(data->data[i][col] - cluster->center[col]);
	}
	return dis;
}

// 从文件中读取原始数据
void ReadFile(char* path, Data* data)
{
	FILE* file;
	if((file = fopen(path,"rt")) == NULL)
	{
		printf("Can not open file.\n");
		return;
	}
	int i = 0;
	char *name = "";
	for(; i < MAX_ROW; i++)
	{
		char buffer[150];
		fgets(buffer,150,file);
		sscanf(buffer,"%f,%f,%f,%f",&data->data[i][0],&data->data[i][1],&data->data[i][2],&data->data[i][3]);
	}
	fclose(file);
}

// 把结果数据写到文件.
void WriteFile(char* path, Cluster* clusters[], Data* data)
{
	FILE* file;
	if((file = fopen(path,"wb")) == NULL)
	{
		printf("Can not open file.\n");
		return;
	}

	int i = 0;
	for(i =0; i< K; i++)
	{
		int j = 0;
		for(j = 0;j < MAX_ROW; j++)
		{
			if(clusters[i]->data[j])
			{
				char buffer[100];
				sprintf(buffer,"%f,%f,%f,%f,\n",data->data[j][0],data->data[j][1],data->data[j][2],data->data[j][3]);
				fputs(buffer,file);

				//printf("%1.1f,  %1.1f,  %1.1f,  %1.1f\n",data->data[j][0],data->data[j][1],data->data[j][2],data->data[j][3]);
			}
		}
		printf("\n\n",file);
	}
	fclose(file);
	
}

int _tmain(int argc, _TCHAR* argv[])
{
	// read data file.
	Data* data = new Data();
	ReadFile("iris.txt",data);

	// initialize the struct.
	Cluster* clusters[K];
	int i =0;
	for(;i< K;i++)
	{
		clusters[i] = new Cluster();
		clusters[i]->data[i] = true;
		RefreshCenter(clusters[i],data);
	}

	int aa = 0;
	bool isChanged = true;
	while(isChanged)
	{
		isChanged = false;
		for(i = 0; i < MAX_ROW; i++)
		{
			int nc = 0;
			float min = 1000;
			int index = -1;
			//找到第i个向量应该放到哪个聚类中
			for(; nc < K; nc++)
			{
				// 首先计算得到该向量到聚类中心的距离
				float distance = GetDistance(i,clusters[nc],data);
				if(distance < min)
				{
					// 找到最小距离
					min = distance;
					index = nc;
				}
			}
			// index 表示应该放到的那个聚类
			for(nc = 0; nc < K; nc++)
			{
				// 如果向量i在聚类nc中,则修改该聚类,并重新计算聚类中心.
				if(nc != index)
				{
					// 如果该向量不属于聚类nc中则删除该标识,并重新计算聚类中心
					clusters[nc]->data[i] = false;
					RefreshCenter(clusters[nc],data);
				}
				else if(!clusters[nc]->data[i])
				{
					// 如果向量i不在聚类index中,则加入到该聚类,然后重新计算聚类中心.
					clusters[nc]->data[i] = true;
					isChanged = true;
					RefreshCenter(clusters[nc],data);
				}
			}
		}
	}

	// 写入到文件
	WriteFile("result.txt",clusters,data);
	return 0;
}