K-means算法的C++实现

本工程文件实现了K-means算法，对输入的样本数据实现了聚类分析，其中测试的样本数据在工程文件下的K-means文件夹下

#include “StdAfx.h“
#include    //输入输出流
#include     //字符串流
#include     //文件流
#include     //向量
#include 
#include 
#include 
#define k 5//簇的数目
using namespace std;
//存放元组的属性信息
typedef vector Tuple;//存储每条数据记录

int dataNum;//数据集中数据记录数目
int dimNum;//每条记录的维数

//计算两个元组间的欧几里得距离
double getDistXY（const Tuple& t1 const Tuple& t2） 
{
	double sum = 0;
	for（int i=1; i<=dimNum; ++i）
	{
		sum += （t1[i]-t2[i]） * （t1[i]-t2[i]）;
	}
	return sqrt（sum）;
}

//根据质心，决定当前元组属于哪个簇
int clusterOfTuple（Tuple means[]const Tuple& tuple）{
	double dist=getDistXY（means[0]tuple）;    //元组与第0簇的距离
	double tmp;
	int label=0;//标示属于哪一个簇
	for（int i=1;i		tmp=getDistXY（means[i]tuple）;       //元组与第1簇的距离
		if（tmp	}
	return label;	
}
//获得给定簇集的平方误差
double getVar（vector clusters[]Tuple means[]）{   //给定簇，给定质心
	double var = 0;
	for （int i = 0; i < k; i++）
	{
		vector t = clusters[i];
		for （int j = 0; j< t.size（）; j++）
		{
			var += getDistXY（t[j]means[i]）;      //实现了误差的公式
		}
	}
	//cout<<“sum:“<	return var;

}
//获得当前簇的均值（质心）
Tuple getMeans（const vector& cluster）{
	
	int num = cluster.size（）;
	Tuple t（dimNum+1 0）;
	for （int i = 0; i < num; i++）
	{
		for（int j=1; j<=dimNum; ++j）
		{
			t[j] += cluster[i][j];   //先把簇中第一个样本点4个维度值全部加上
		}
	}
	for（int j=1; j<=dimNum; ++j）
		t[j] /= num;
	return t;
	//cout<<“sum:“<}

void print（const vector clusters[]）   //输出各个簇的样本
{
	for（int lable=0; lable	{
		cout<<“第“<		vector t = clusters[lable];
		for（int i=0; i		{
			cout<			for（int j=0; j<=dimNum; ++j）
			{
				cout<			}
			cout<<“）\n“;
		}
	}
}

void KMeans（vector& tuples）{
	vector clusters[k];//k个簇
	Tuple means[k];//k个中心点
	int i=0;
	//一开始随机选取k条记录的值作为k个簇的质心（均值）
	srand（（unsigned int）time（NULL））;
	for（i=0;i		int iToSelect = rand（）%tuples.size（）;   //实现了0～150之间随机取数
		if（means[iToSelect].size（） == 0）
		{
			for（int j=0; j<=dimNum; ++j）
			{
				means[i].push_back（tuples[iToSelect][j]）;
			}
			++i;
		}
	}
	int lable=0;
	//根据默认的质心给簇赋值
	for（i=0;i!=tuples.size（）;++i）{
		lable=clusterOfTuple（meanstuples[i]）;
		clusters[lable].push_back（tuples[i]）;
	}
	double oldVar=-1;
	double newVar=getVar（clustersmeans）;
	cout<<“初始的的整体误差平方和为：“<	int t = 0;
	while（abs（newVar - oldVar） >= 1） //当新旧函数值相差不到1即准则函数值不发生明显变化时，算法终止
	{
		cout<<“第 “<<++t<<“ 次迭代开始：“<		for （i = 0; i < k; i++） //更新每个簇的中心点
		{
			means[i] = getMeans（clusters[i]）;
		}
		oldVar = newVar;
		newVar = getVar（clustersmeans）; //计算新的准则函数值
		for （i = 0; i < k; i++） //清空每个簇，因为要重新聚类
		{
			clusters[i].clear（）;
		}
		//根据新的质心获得新的簇
		for（i=0; i!=tuples.size（）; ++i）{
			lable=clusterOfTuple（meanstuples[i]）;
			clusters[lable].push_back（tupl

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件     151040  2016-04-24 09:48  k-means\Debug\k-means.exe

     文件    1080228  2016-04-24 09:48  k-means\Debug\k-means.ilk

     文件    1502208  2016-04-24 09:48  k-means\Debug\k-means.pdb

     文件    2359296  2016-05-08 10:49  k-means\ipch\k-means-ca3ed5be\k-means-c0adf4d8.ipch

     文件       1562  2016-04-24 09:48  k-means\k-means\Debug\cl.command.1.tlog

     文件       7610  2016-04-24 09:48  k-means\k-means\Debug\CL.read.1.tlog

     文件        978  2016-04-24 09:48  k-means\k-means\Debug\CL.write.1.tlog

     文件        406  2016-04-23 14:31  k-means\k-means\Debug\k-means.exe.embed.manifest

     文件        472  2016-04-23 14:31  k-means\k-means\Debug\k-means.exe.embed.manifest.res

     文件        381  2016-04-24 09:48  k-means\k-means\Debug\k-means.exe.intermediate.manifest

     文件         78  2016-04-24 09:48  k-means\k-means\Debug\k-means.lastbuildstate

     文件       2498  2016-04-24 09:48  k-means\k-means\Debug\k-means.log

     文件     562700  2016-04-24 09:48  k-means\k-means\Debug\k-means.obj

     文件    1179648  2016-04-23 11:48  k-means\k-means\Debug\k-means.pch

     文件        204  2016-04-23 14:31  k-means\k-means\Debug\k-means_manifest.rc

     文件          2  2016-04-24 09:48  k-means\k-means\Debug\link-cvtres.read.1.tlog

     文件          2  2016-04-24 09:48  k-means\k-means\Debug\link-cvtres.write.1.tlog

     文件          2  2016-04-24 09:48  k-means\k-means\Debug\link.10272-cvtres.read.1.tlog

     文件          2  2016-04-24 09:48  k-means\k-means\Debug\link.10272-cvtres.write.1.tlog

     文件          2  2016-04-24 09:48  k-means\k-means\Debug\link.10272.read.1.tlog

     文件          2  2016-04-24 09:48  k-means\k-means\Debug\link.10272.write.1.tlog

     文件          2  2016-04-24 09:48  k-means\k-means\Debug\link.11776-cvtres.read.1.tlog

     文件          2  2016-04-24 09:48  k-means\k-means\Debug\link.11776-cvtres.write.1.tlog

     文件          2  2016-04-24 09:48  k-means\k-means\Debug\link.11776.read.1.tlog

     文件          2  2016-04-24 09:48  k-means\k-means\Debug\link.11776.write.1.tlog

     文件       1790  2016-04-24 09:48  k-means\k-means\Debug\link.command.1.tlog

     文件       3068  2016-04-24 09:48  k-means\k-means\Debug\link.read.1.tlog

     文件       1040  2016-04-24 09:48  k-means\k-means\Debug\link.write.1.tlog

     文件        412  2016-04-24 09:48  k-means\k-means\Debug\mt.command.1.tlog

     文件        366  2016-04-24 09:48  k-means\k-means\Debug\mt.read.1.tlog

............此处省略30个文件信息