kmeans.cpp

人工智能、模式识别中经常要用到的K均值聚类算法

#include <iostream>
#include <vector>
#include "math.h"
using namespace std;

struct pixel
{ short int R;
  short int G;
  short int B;
  int belong;
};

struct Group
{ float R;
  float G;
  float B;
  long n;
};

double chance(Group *group,Group *groupbefore,int K)
{
	double dis=0.0;
	for (int i=0;i<K;i++)
		dis+=fabs(group[i].B-groupbefore[i].B)+fabs(group[i].G-groupbefore[i].G)+fabs(group[i].R-groupbefore[i].R);
    return dis;
}

void chosegroup(vector <pixel> &a,Group *group,int K)
{
	for (int i=0;i<a.size();i++)
	{
		double dismin=255*3;
		double dis;
		for(int j=0; j<K; j++)
		{
		  dis=fabs(group[j].B-a[i].B)+fabs(group[j].G-a[i].G)+fabs(group[j].R-a[i].R);
		  if (dis<dismin) 
		  {
			  dismin=dis;
			  a[i].belong=j;
		  }
		}
	}
}


void getmean(vector <pixel> &a,Group *group,int K)
{
	memset(group,0,sizeof(Group)*K);

	for (int i=0;i<a.size();i++)
	{
		group[a[i].belong].B=(group[a[i].belong].B*group[a[i].belong].n+a[i].B)/(group[a[i].belong].n+1);
		group[a[i].belong].G=(group[a[i].belong].G*group[a[i].belong].n+a[i].G)/(group[a[i].belong].n+1);
		group[a[i].belong].R=(group[a[i].belong].R*group[a[i].belong].n+a[i].R)/(group[a[i].belong].n+1);
		group[a[i].belong].n++;

	}
}




void Kmeans(vector <pixel> &a,int K,double delta)
{
	
	
	Group *group,*groupbefore;
	group=new Group[K];	
	memset(group,0,sizeof(Group)*K);
	groupbefore=new Group[K];
	memset(groupbefore,0,sizeof(Group)*K);


	int k=0;
	for (int i=0;i<a.size();i++)
	{
		a[i].belong=k;
		group[k].B=(group[k].B*group[k].n+a[i].B)/(group[k].n+1);
		group[k].G=(group[k].B*group[k].n+a[i].G)/(group[k].n+1);
		group[k].R=(group[k].B*group[k].n+a[i].R)/(group[k].n+1);
		group[k].n++;

		if (i<K-1) k++;
	}

	
	for(;chance(group,groupbefore,K)>delta;)
	{
		memcpy(groupbefore,group,sizeof(Group)*K);
		chosegroup(a,group,K);
		getmean(a,group,K);

	}



};

main()
{
vector <pixel> a;
a.reserve(400);
pixel temp;
for (int i=0;i<8;i++)
{
cout<< "Please input R,G,B:";
cin>>temp.R>>temp.G>>temp.B;
a.push_back(temp);
}
int K=3;
double dalta=0.1;
Kmeans(a,K,dalta);
return 0;
}