wkmeans.h

加权k均值算法

bool wkmeans(double *X,long &N,int &p,int &C,int *clusters,double *v,long &iter,double *w=NULL)
//X为样本数组,N为样本个数,p为样本维数,C为聚类数,w为样本权值,clusters聚类结果,v聚类中心,iter为迭代次数
{
	if(C<2||X==NULL||N<=C)//判断输入有无错误
	{
		AfxMessageBox("类别数小于2,无需分类!");
		return false;
	}
	int i,j,k,tmpi,tmpj,tmpn;//循环变量
	long llltmp,iiitmp,jjjtmp;
	double temp,sumwtmp;
	bool tempdeletew=false,tempdeletev=false,changable=TRUE;
	if(w==NULL)//判断是否需要为w分配内存空间
	{
		tempdeletew=TRUE;
		w=new double[N];
		for(i=0;i<N;i++)
			w[i]=1.0/N;
	}
	else//权值归一化
	{
		sumwtmp=0;
		for(i=0;i<N;i++)
			sumwtmp=sumwtmp+w[i];
		for(i=0;i<N;i++)
			w[i]=w[i]/sumwtmp;
	}
	if(clusters==NULL)//为分类结果clusters开辟内存空间
	{
		clusters=new int[N];
	}
	if(v==NULL)//为聚类中心v分配内存空间
	{
		v=new double[C*p];
		tempdeletev=true;
	}
	for(i=p;i<C*p;i++)
		v[i]=0;
	for(i=0;i<p;i++)//第0类的聚类中心为第0个样本
		v[i]=X[i];

	double *dd=new double[N];		
	for(k=1;k<C;k++)//求第k类的聚类中心
	{
		for(i=0;i<N;i++)
		{
			dd[i]=0;
		}
		
		//求每个样本特征与前k-1个聚类中心的距离之和
		for(j=0;j<k;j++)//第j类
		{
			jjjtmp=j*p;
			for(i=0;i<N;i++)//第i个样本
			{
				temp=0;
				llltmp=i*p;
				for(tmpi=0;tmpi<p;tmpi++)
				{
					temp=temp+(X[llltmp+tmpi]-v[jjjtmp+tmpi])*(X[llltmp+tmpi]-v[jjjtmp+tmpi]);
				}
				dd[i]=dd[i]+w[i]*sqrt(temp);
			}
		}


		i=0;
		temp=dd[0];
		for(tmpj=1;tmpj<N;tmpj++)//寻找距离最大的样本
		{
			if(dd[tmpj]>temp)
			{
				temp=dd[tmpj];
				i=tmpj;
			}
		}
		iiitmp=i*p;
		llltmp=k*p;
		for(tmpi=0;tmpi<p;tmpi++)//第k类聚类中心赋值
		{
			v[llltmp+tmpi]=X[iiitmp+tmpi];
		}
	}
	delete []dd;//初始化聚类中心完毕
	
	
	
	//////////////////进行初始划分///////////////////////////
	double *vsum=new double[C*p];
	double *wsum=new double[C];
	double *d=new double[C];
	for(i=0;i<C;i++)
		wsum[i]=0;

	llltmp=C*p;
	for(iiitmp=0;iiitmp<llltmp;iiitmp++)
		vsum[iiitmp]=0;

	for(i=0;i<N;i++)//基于初始聚类中心，进行初始划分
	{
		iiitmp=i*p;//第i个样本的起始地址
// 		for(tmpi=0;tmpi<C;tmpi++)
// 			d[tmpi]=0;
		for(k=0;k<C;k++)
		{
			temp=0;
			llltmp=k*p;//第k类聚类中心的起始地址
			for(tmpi=0;tmpi<p;tmpi++)
			{
				temp=temp+(X[iiitmp+tmpi]-v[llltmp+tmpi])*(X[iiitmp+tmpi]-v[llltmp+tmpi]);
			}
			d[k]=sqrt(temp);
		}
		j=0;
		temp=d[0];
		for(tmpj=1;tmpj<C;tmpj++)//距离第i个样本最近的聚类j
		{
			if(d[tmpj]<temp)
			{
				temp=d[tmpj];
				j=tmpj;
			}
		}
		clusters[i]=j;
		jjjtmp=j*p;//第j类聚类中心的起始地址
		for(tmpj=0;tmpj<p;tmpj++)
		{
			vsum[jjjtmp+tmpj]=vsum[jjjtmp+tmpj]+w[i]*X[iiitmp+tmpj];
		}
		
		wsum[j]=wsum[j]+w[i];
	}

	for(i=0;i<C;i++)//计算聚类中心
	{
		iiitmp=i*p;//聚类中心起始地址
		for(j=0;j<p;j++)
		{
			v[iiitmp+j]=vsum[iiitmp+j]/wsum[i];
		}
	}
	///////////////////////////初始划分完毕////////////////////////////////






	iter=0;
	while(changable)
	{
		iter=iter+1;
		changable=false;
		for(i=0;i<N;i++)//对第i类进行分类
		{
			iiitmp=i*p;
// 			for(tmpi=0;tmpi<C;tmpi++)
// 				d[tmpi]=0;
			for(k=0;k<C;k++)
			{
				temp=0;
				llltmp=k*p;
				for(tmpi=0;tmpi<p;tmpi++)
				{
					temp=temp+(X[iiitmp+tmpi]-v[llltmp+tmpi])*(X[iiitmp+tmpi]-v[llltmp+tmpi]);
				}
				d[k]=sqrt(temp);
			}
			j=0;
			temp=d[0];
			for(tmpj=1;tmpj<C;tmpj++)//距离第i个样本最近的聚类j
			{
				if(d[tmpj]<temp)
				{
					temp=d[tmpj];
					j=tmpj;
				}
			}
			if(clusters[i]!=j)//更新有变化的类的向量和以及权值和
			{
				tmpn=clusters[i];
				clusters[i]=j;
				jjjtmp=j*p;
				llltmp=tmpn*p;
				for(tmpj=0;tmpj<p;tmpj++)
				{
					vsum[jjjtmp+tmpj]=vsum[jjjtmp+tmpj]+w[i]*X[iiitmp+tmpj];
					vsum[llltmp+tmpj]=vsum[llltmp+tmpj]-w[i]*X[iiitmp+tmpj];
				}
				wsum[j]=wsum[j]+w[i];
				wsum[tmpn]=wsum[tmpn]-w[i];
				changable=TRUE;
			}	
		}
		if(changable)
		{
			for(i=0;i<C;i++)//计算聚类中心
			{
				iiitmp=i*p;
				for(j=0;j<p;j++)
				{
					v[iiitmp+j]=vsum[iiitmp+j]/wsum[i];
				}
			}
		}
	}
	delete []d;
	delete []wsum;
	delete []vsum;
	if(tempdeletev)
		delete []v;
	if(tempdeletew)
		delete []w;
	return TRUE;
}