offlineclustering.cpp

对数据流,按指数递增方式,形成汇总信息,在离线层,根据用户需求,进行聚类

		}
		fprintf(g_POutFile,"\n\n");
	}

	return EvaluateCluster(cluster,cnum);
}

//
//功能:判断是否为中心点
//
bool isInCenterArray(int dt,CLUSTER cluster[],int cnum)
{
	bool result=false;
	for(int i=0;i<cnum;i++)
		if(dt==cluster[i].center)
		{
			result=true;
			break;
		}
	return result;
}

//
//功能:获得非中心点所属的中心点
//
int getOwnerCenterPoint(int p,CLUSTER cluster[],int cnum)
{
	for(int i=0;i<cnum;i++)
	{
		for(int j=0;j<cluster[i].num;j++)
		{
			if(cluster[i].member[j]==p)
				return cluster[i].center;
		}
	}
	return -1;
}

//
//功能:以非中心代替中心重新聚类
//
bool CalcNewClustCenters(CLUSTER cluster[],int cnum,int winlen)
{
	bool converged=true;
	int i,icenter,j;
	CLUSTER tcluster[INIT_CLUSTER_NUM];

	//
	//fprintf(g_POutFile,"\n");

	for(i=0;i<DATAFLOW_NUM;i++)
	{
		if(isInCenterArray(i,cluster,cnum)) continue; //找非中心点
		icenter=getOwnerCenterPoint(i,cluster,cnum);

		fprintf(g_POutFile,"Try substitute non-center to center:\n");

		for(j=0;j<cnum;j++)
			tcluster[j]=cluster[j];
		for(j=0;j<cnum;j++)
		{
			if(tcluster[j].center==icenter)
			{
				tcluster[j].center=i;
			}
		}
		double tssq=DistributeSamples(tcluster,cnum,winlen);
		fprintf(g_POutFile,"ssq=%.24f.\n",tssq);
		if(tssq>g_ssq)
		{
			fprintf(g_POutFile,"\nSubstitute.\n");

			g_ssq=tssq;
			for(j=0;j<cnum;j++)
				cluster[j]=tcluster[j];
			converged=false;
			break;
		}
	}

	//
	//if(converged)
	//	fprintf(g_POutFile,"The cluster centers are now converged.\n");

	return converged;
}

//
//k-medoids 聚类
//
void Runkmedoids(CLUSTER cluster[],int cnum,int winlen)
{
	bool converged;
	converged=false;
	g_ssq=DistributeSamples(cluster,cnum,winlen);
	fprintf(g_POutFile,"ssq=%.24f.\n",g_ssq);
	while(!converged)
	{
		converged=CalcNewClustCenters(cluster,cnum,winlen);
	}
}

//
//
//
void UpdateWindowCoeffi(int windowlen,int *pDataLen)
{
	int iInfoNumCount=0;
	for(int i=0;i<M+1;i++)
	{
		iInfoNumCount+=OFFLINEDATA[0][i].infoNum;
		if(iInfoNumCount>=windowlen)
			break;
	}

	*pDataLen=iInfoNumCount*PIECE_DIM;

	for(int j=0;j<DATAFLOW_NUM;j++)
	{
		/*
		g_ArrDataFlowAndSegmentCoeffi[j].sumxi=OFFLINEDATA[j][i].blockEffi.sumxi;
		g_ArrDataFlowAndSegmentCoeffi[j].sumxi2=OFFLINEDATA[j][i].blockEffi.sumxi2;
		for(int k=0;k<DATAFLOW_NUM;k++)
			g_ArrDataFlowAndSegmentCoeffi[j].sumxyi[k]=OFFLINEDATA[j][i].blockEffi.sumxyi[k];
		*/
		memcpy(&g_ArrDataFlowAndSegmentCoeffi[j],&OFFLINEDATA[j][i].blockEffi,sizeof(BLOCK_COEFFICIENT));

		for(int m=i-1;m>=0;m--)
		{
			g_ArrDataFlowAndSegmentCoeffi[j].sumxi=g_ArrDataFlowAndSegmentCoeffi[j].sumxi*TABLE_INDEX_TIMEVALUE[OFFLINEDATA[j][m].infoNum*PIECE_DIM]+OFFLINEDATA[j][m].blockEffi.sumxi;
			g_ArrDataFlowAndSegmentCoeffi[j].sumxi2=g_ArrDataFlowAndSegmentCoeffi[j].sumxi2*pow(TABLE_INDEX_TIMEVALUE[OFFLINEDATA[j][m].infoNum*PIECE_DIM],2)+OFFLINEDATA[j][m].blockEffi.sumxi2;
			for(int k=0;k<DATAFLOW_NUM;k++)
				g_ArrDataFlowAndSegmentCoeffi[j].sumxyi[k]=g_ArrDataFlowAndSegmentCoeffi[j].sumxyi[k]*pow(TABLE_INDEX_TIMEVALUE[OFFLINEDATA[j][m].infoNum*PIECE_DIM],2)+OFFLINEDATA[j][m].blockEffi.sumxyi[k];
		}
	}
}

//-----------------------------------------------
//入口函数
//
void main()
{
	g_POutFile=fopen("out.txt","w");

	printf("status:> Recording of offline info of dataflows...\n");

	//初始化时间权值索引表
	TABLE_INDEX_TIMEVALUE[0]=1;
	for(int i=1;i<L/2*PIECE_DIM;i++)
	{
		TABLE_INDEX_TIMEVALUE[i]=TABLE_INDEX_TIMEVALUE[i-1]*ATTENUATION;
	}

	//根据给定的L,M计算实际离线存储的BLOCK(包括各个BLOCK的个数及所蕴含的信息量)
	int lnum=int(log(L)/log(2));  //log函数以e为底
	int mtilt=M-lnum;
	int ci,k,tk,tksub1;
	if(mtilt<0)
	{
		printf("M 小于 log2(L)");
		return;
	}
	for(i=lnum;i>0;i--)
	{
		ci=int(pow(2,lnum-i+2))-(lnum-i+4);
		if(mtilt<=ci)
		{
			k=i;
			break;
		}
	}
	tk=ci-mtilt+1;
	tksub1=2*(int(pow(2,lnum-k+1))-tk)-1;

	//更新离线数据蕴含信息个数域
	for(int j=0;j<DATAFLOW_NUM;j++)
	{
		for(i=M;i>=M-tk+1;i--)
		{
			OFFLINEDATA[j][i].infoNum=int(pow(2,k));
			OFFLINEDATA[j][i].isUsed=false;
		}
		for(i=M-tk;i>=M-tk-tksub1+1;i--)
		{
			OFFLINEDATA[j][i].infoNum=int(pow(2,k-1));
			OFFLINEDATA[j][i].isUsed=false;
		}
		for(i=M-tk-tksub1;i>=0;i--)
		{
			OFFLINEDATA[j][i].infoNum=int(pow(2,i));
			OFFLINEDATA[j][i].isUsed=false;
		}
	}

	RecNowTime();
	
	while(ReadOnePieceFromMultiDataFlow()==ERR_SUCCESS)
	{
		//printf("test:> read one piece\n");
		UpdateArrDataFlowAndPieceCoeffi();
		//printf("test:> update one piece\n");
		
		int pos=FindInfoSavePos();
		//printf("test:> pos=%d\n",pos);
		for(j=0;j<DATAFLOW_NUM;j++)
		{
			//printf("test:> %d\n",j);
			if(pos!=-1)  //找到位置
			{
				bool flag=false;
				for(i=pos-1;i>=0;i--)
				{
					if(OFFLINEDATA[j][i].infoNum==OFFLINEDATA[j][pos].infoNum)
					{
						OFFLINEDATA[j][i+1]=OFFLINEDATA[j][i];
						OFFLINEDATA[j][i+1].isUsed=true;
						OFFLINEDATA[j][i].isUsed=false;
						flag=true;
					}
					else
						break;
				}
				if(flag) pos=i+1;  //更正实际保存信息的位置
				//printf("test:> real pos=%d\n",pos);

				//累加信息,保存至pos位置
				BLOCK_COEFFICIENT t_blockCoeffi;
				memset(&t_blockCoeffi,0,sizeof(BLOCK_COEFFICIENT));
				for(i=pos-1;i>=0;i--)
				{
					OFFLINEDATA[j][i].isUsed=false;
					if(i==pos-1)
					{
						t_blockCoeffi.sumxi=OFFLINEDATA[j][i].blockEffi.sumxi;
						t_blockCoeffi.sumxi2=OFFLINEDATA[j][i].blockEffi.sumxi2;
						for(int k=0;k<DATAFLOW_NUM;k++)
							t_blockCoeffi.sumxyi[k]=OFFLINEDATA[j][i].blockEffi.sumxyi[k];
					}
					else
					{
						t_blockCoeffi.sumxi=t_blockCoeffi.sumxi*TABLE_INDEX_TIMEVALUE[OFFLINEDATA[j][i].infoNum*PIECE_DIM]+OFFLINEDATA[j][i].blockEffi.sumxi;
						t_blockCoeffi.sumxi2=t_blockCoeffi.sumxi2*pow(TABLE_INDEX_TIMEVALUE[OFFLINEDATA[j][i].infoNum*PIECE_DIM],2)+OFFLINEDATA[j][i].blockEffi.sumxi2;
						for(int k=0;k<DATAFLOW_NUM;k++)
							t_blockCoeffi.sumxyi[k]=t_blockCoeffi.sumxyi[k]*pow(TABLE_INDEX_TIMEVALUE[OFFLINEDATA[j][i].infoNum*PIECE_DIM],2)+OFFLINEDATA[j][i].blockEffi.sumxyi[k];
					}
				}
				t_blockCoeffi.sumxi=t_blockCoeffi.sumxi*TABLE_INDEX_TIMEVALUE[PIECE_DIM]+g_ArrDataFlowAndPieceCoeffi[j].sumxi;
				t_blockCoeffi.sumxi2=t_blockCoeffi.sumxi2*pow(TABLE_INDEX_TIMEVALUE[PIECE_DIM],2)+g_ArrDataFlowAndPieceCoeffi[j].sumxi2;
				for(int k=0;k<DATAFLOW_NUM;k++)
					t_blockCoeffi.sumxyi[k]=t_blockCoeffi.sumxyi[k]*pow(TABLE_INDEX_TIMEVALUE[PIECE_DIM],2)+g_ArrDataFlowAndPieceCoeffi[j].sumxyi[k];

				memcpy(&OFFLINEDATA[j][pos].blockEffi,&t_blockCoeffi,sizeof(BLOCK_COEFFICIENT));
				OFFLINEDATA[j][pos].isUsed=true;
			}
			else  //离线存储空间已满
			{
				if(OFFLINEDATA[j][0].infoNum==1)
				{
					OFFLINEDATA[j][0].infoNum=2;
					OFFLINEDATA[j][0].blockEffi.sumxi=OFFLINEDATA[j][0].blockEffi.sumxi*TABLE_INDEX_TIMEVALUE[PIECE_DIM]+g_ArrDataFlowAndPieceCoeffi[j].sumxi;
					OFFLINEDATA[j][0].blockEffi.sumxi2=OFFLINEDATA[j][0].blockEffi.sumxi2*pow(TABLE_INDEX_TIMEVALUE[PIECE_DIM],2)+g_ArrDataFlowAndPieceCoeffi[j].sumxi2;
					for(int k=0;k<DATAFLOW_NUM;k++)
						OFFLINEDATA[j][0].blockEffi.sumxyi[k]=OFFLINEDATA[j][0].blockEffi.sumxyi[k]*pow(TABLE_INDEX_TIMEVALUE[PIECE_DIM],2)+g_ArrDataFlowAndPieceCoeffi[j].sumxyi[k];
				}
				else  //信息合并
				{
					//寻找合并位置
					int convpos=FindInfoConvergePos();
					if(convpos!=M)
					{
						OFFLINEDATA[j][convpos].infoNum+=OFFLINEDATA[j][convpos-1].infoNum;
						OFFLINEDATA[j][convpos].blockEffi.sumxi=OFFLINEDATA[j][convpos].blockEffi.sumxi*TABLE_INDEX_TIMEVALUE[OFFLINEDATA[j][convpos-1].infoNum*PIECE_DIM]+OFFLINEDATA[j][convpos-1].blockEffi.sumxi;
						OFFLINEDATA[j][convpos].blockEffi.sumxi2=OFFLINEDATA[j][convpos].blockEffi.sumxi2*pow(TABLE_INDEX_TIMEVALUE[OFFLINEDATA[j][convpos-1].infoNum*PIECE_DIM],2)+OFFLINEDATA[j][convpos-1].blockEffi.sumxi2;
						for(int k=0;k<DATAFLOW_NUM;k++)
							OFFLINEDATA[j][convpos].blockEffi.sumxyi[k]=OFFLINEDATA[j][convpos].blockEffi.sumxyi[k]*pow(TABLE_INDEX_TIMEVALUE[OFFLINEDATA[j][convpos-1].infoNum*PIECE_DIM],2)+OFFLINEDATA[j][convpos-1].blockEffi.sumxyi[k];
						for(int i=pos-2;i>=0;i--)
							memcpy(&OFFLINEDATA[i+1],&OFFLINEDATA[i],sizeof(OFFLINEBLOCK));
					}
					else
					{
						for(int i=pos-1;i>=0;i--)
							memcpy(&OFFLINEDATA[i+1],&OFFLINEDATA[i],sizeof(OFFLINEBLOCK));
					}
					OFFLINEDATA[j][0].infoNum=1;
					OFFLINEDATA[j][0].blockEffi.sumxi=g_ArrDataFlowAndPieceCoeffi[j].sumxi;
					OFFLINEDATA[j][0].blockEffi.sumxi2=g_ArrDataFlowAndPieceCoeffi[j].sumxi2;
					for(k=0;k<DATAFLOW_NUM;k++)
						OFFLINEDATA[j][0].blockEffi.sumxyi[k]=g_ArrDataFlowAndPieceCoeffi[j].sumxyi[k];
				}
			}
		}
	}

	RecNowTime();
	printf("status:> Recording of offline info of dataflows has finished!\n");


	//聚类
	int iWindowLen,iDataflowNum,iWindowDataLen;
	printf("Please input the length of dataflow for clustering:");
	scanf("%d",&iWindowLen);
	printf("Please input the number of dataflow for clustering:");
	scanf("%d",&iDataflowNum);

	//update g_ArrDataFlowAndSegmentCoeffi
	UpdateWindowCoeffi(iWindowLen,&iWindowDataLen);

	//初始化Cluster
	g_iClusterNum=INIT_CLUSTER_NUM;
	for(i=0;i<g_iClusterNum;i++)
	{
		g_Cluster[i].center=i;
		g_Cluster[i].num=0;
	}

	Runkmedoids(g_Cluster,g_iClusterNum,iWindowDataLen);
	
}