kcluster.cpp

K-均值聚类算法 vc++图形演示程序

#include "StdAfx.h"
#include "KCluster.h"

// 构造器
KCluster::KCluster(int dataNum, int dimension, int clusterNum, double *DataSet)	:
	OldCluster(NULL)
{
	int i;

	DataNum = dataNum;
	Dimension = dimension;
	ClusterNum = clusterNum;

	DataMember = new DataType[DataNum];
	ClusterMember = new ClusterType[ClusterNum];

	for(i=0; i<DataNum; i++)
	{
		DataMember[i].Data = new double[Dimension];	

		DataMember[i].Uncle = new double[ClusterNum];
	}	
	for(i=0; i<ClusterNum; i++)
		ClusterMember[i].Center = new double[Dimension];

	GetDataSet(DataMember, DataSet, DataNum, Dimension);
}

// 析构器
KCluster::~KCluster(void)
{
	int i;
	for(i=0; i<DataNum; i++)
	{
		delete[] DataMember[i].Data;	
		delete[] DataMember[i].Uncle;
	}
	delete[] DataMember;

	for(i=0; i<ClusterNum; i++)
		delete[] ClusterMember[i].Center;
	delete[] ClusterMember;

	if (OldCluster)
	{
		for(i=0; i<ClusterNum; i++)
			delete[] OldCluster[i].Center;
		delete[] OldCluster;
	}
}

void KCluster::NewCenterPlus(ClusterType *pData, int Idx, double *pValue, int Dimension)
{
	int i;
	double Center;
	for(i=0; i<Dimension; i++)
	{
		Center = pData[Idx].Center[i];
		Center = Center + (pValue[i] - Center) / (pData[Idx].Sonnum);
		pData[Idx].Center[i] = Center;
	}
}


void KCluster::NewCenterReduce(ClusterType *pData, int Idx, double *pValue, int Dimension)
{
	int i;
	double Center;
	for(i=0; i<Dimension; i++)
	{
		Center = pData[Idx].Center[i];
		Center = Center + (Center - pValue[i]) / (pData[Idx].Sonnum);
		pData[Idx].Center[i] = Center;
	}
}


// 设置数据集
void KCluster::GetDataSet(DataType *pData, double *pValue, int DataNum, int Dimension)
{
	int i, j;
	for(i=0; i<DataNum; i++)
	{
		for(j=0; j<Dimension; j++)
			pData[i].Data[j] = pValue[i*Dimension+j];
	}
}

// 设置数据
void KCluster::GetValue(double *pValue1, double *pValue2, int Dimension)
{
	int i;
	for(i=0; i<Dimension; i++)		
		pValue1[i] = pValue2[i];
}

// 找到最近点
int KCluster::FindFather(double *pValue, int ClusterNum)
{
	int i, Ret = 0;
	double Min = 30000000;

	for(i=0; i<ClusterNum; i++)	
	{
		if(pValue[i]<Min)
		{
			Min = pValue[i];
			Ret = i;
		}
	}
	return Ret;
}

// 计算距离
double KCluster::SquareDistance(double *pValue1, double *pValue2, int Dimension)
{
	int i;
	double Distance = 0;
	for(i=0; i<Dimension; i++)
		Distance = Distance + (pValue2[i]-pValue1[i])*(pValue2[i]-pValue1[i]);
	return Distance;
}

// 比较
int	KCluster::Compare(double *pValue1, double *pValue2, int Dimension)
{
	int i;
	for(i=0; i<Dimension; i++)
		if(pValue1[i]!=pValue2[i])
			return 1;
	return 0;
}	

// 目标函数
double KCluster::AimFunction()
{
	int i,j;
	double *Temp = new double[ClusterNum];
	for(i=0; i<ClusterNum; i++) Temp[i]=0;
	for(i=0; i<ClusterNum; i++)
	{
		for(j=0; j<DataNum; j++)
		{
			if(DataMember[j].Father==i)
			{
				Temp[i] = Temp[i] + SquareDistance(ClusterMember[i].Center, DataMember[j].Data, Dimension);
			}
		}
	}
		
	double AimFunc = 0;
	for(i=0; i<ClusterNum; i++)
		AimFunc = AimFunc + Temp[i];

	return AimFunc;

}
// 开始聚类，生成初始簇中心
void KCluster::StartClustering()
{
	int i, j;
	OldCluster = new ClusterType[ClusterNum];

	for(i=0; i<ClusterNum; i++)
	{
		GetValue(ClusterMember[i].Center, DataMember[i].Data, Dimension);
		ClusterMember[i].Sonnum = 1;

		OldCluster[i].Center = new double[Dimension];
		GetValue(OldCluster[i].Center, ClusterMember[i].Center, Dimension);
	}

	for(i=0; i<DataNum; i++)
	{
		for(j=0; j<ClusterNum; j++)
		{
			DataMember[i].Uncle[j] = SquareDistance(DataMember[i].Data, ClusterMember[j].Center, Dimension);
		}
		
		ClusterIdxA = DataMember[i].Father = FindFather(DataMember[i].Uncle, ClusterNum);
		if(i>=ClusterNum)
		{
			ClusterMember[ClusterIdxA].Sonnum += 1;
			NewCenterPlus(ClusterMember, ClusterIdxA, DataMember[i].Data, Dimension);
			GetValue(OldCluster[ClusterIdxA].Center, ClusterMember[ClusterIdxA].Center, Dimension);
		}
		
	}

	ClusteringCompleted = false;
}

// 一个聚类步
bool KCluster::SetupClustering()
{
	int i, j, Ret = 0;
	int Father;

	if (ClusteringCompleted) return true;

	//一次聚类循环：1.重新归类；2.修改类中心
	for(i=0; i<DataNum; i++)  
	{
		for(j=0; j<ClusterNum ;j++)
		{
			DataMember[i].Uncle[j] = SquareDistance(DataMember[i].Data, ClusterMember[j].Center, Dimension);
		}
			
		Father = DataMember[i].Father;

		if(Father!=FindFather(DataMember[i].Uncle, ClusterNum) && ClusterMember[Father].Sonnum>1)
		{
			ClusterIdxA = DataMember[i].Father;
			ClusterMember[ClusterIdxA].Sonnum -= 1;

			ClusterIdxB = DataMember[i].Father = FindFather(DataMember[i].Uncle, ClusterNum);
			ClusterMember[ClusterIdxB].Sonnum += 1;

			NewCenterReduce(ClusterMember, ClusterIdxA, DataMember[i].Data, Dimension);
			NewCenterPlus(ClusterMember, ClusterIdxB, DataMember[i].Data, Dimension);
				
		}					

	} 

	//判断聚类是否完成，ClusteringCompleted=true,聚类停止
	for(j=0; j<ClusterNum; j++)
		if(Compare(OldCluster[j].Center, ClusterMember[j].Center, Dimension))
			break;

	if(j==ClusterNum)
		ClusteringCompleted = true;

	for(j=0; j<ClusterNum; j++)
		GetValue(OldCluster[j].Center, ClusterMember[j].Center, Dimension);

	return ClusteringCompleted;
}

int KCluster::GetClusterData(int Cluster, double *DataSet)
{
	int i, Counter = 0;

	if (Cluster<0 || Cluster>ClusterNum) return -1;

	for(i=0; i<DataNum; i++)
	{
		if(DataMember[i].Father == Cluster)
		{	
			GetValue(&DataSet[Counter*Dimension], DataMember[i].Data, Dimension);
			Counter++;
		}	
	}

	return Counter;
}

int KCluster::GetClusterCenter(double *Center)
{
	int i;
	for(i=0; i<ClusterNum; i++)
	{
		GetValue(&Center[i*Dimension], ClusterMember[i].Center, Dimension);
	}
	return ClusterNum;
}