indval.cpp

某个实验事编写粗糙集智能信息处理的程序

	for(i=0;i<iConNum+1;i++)
	{
		delete []pDataType[i];
		delete []pAttName[i];
	}
	delete []pDataType;
	delete []pAttName;
	delete []pSameRec;

	for(i=0;i<iRecNum;i++)
		delete []pRules[i];
	delete []pRules;

	//free struWCutRecord
	struct WCutRecord* pHead=NULL;
	while(struWCutRecord != NULL)
	{
		pHead = struWCutRecord->next;
		for(int i = 0;i < struWCutRecord->iCuts;i++)
			delete[] struWCutRecord->cpCut[i];
		delete[] struWCutRecord->cpCut;
		delete struWCutRecord;
		struWCutRecord = pHead;
	}
}

void IndValRed::FindSameRec()//求每条规则能覆盖的记录数
{
	if((pSameRec=new int[iRulesNum])==0)
	{
		AfxMessageBox("内存分配错误!");
		return;
	}
	for(int i=0;i<iRulesNum;i++)
		pSameRec[i]=0;//初始化规则覆盖的记录为零
	for(i=0;i<iRulesNum;i++)
	{
		for(int j=0;j<ipriRecNum;j++)
		{
			int flag=1;
			for(int k=0;k<iConNum+1;k++)
			{
				if((pRules[i][k]!=-1)&&(pIntTable[j][k]!=pRules[i][k]))
				{//规则中该属性不为'-'且规则属性值和原始表中值不等时,说明规则不匹配该记录
					flag=0;
					break;//后面的记录不用比较了
				}
			}
			if(flag==1)
				pSameRec[i]++;
		}
	}
}

void IndValRed::UindCoreVal(int iRecNo,PosD* &CoreValSet,PosD* &UindCoreValX)
{ //求[x]core(dx)   //CoreValSet:记录的核值属性
	for(int i=0;i<iRecNum;i++)
	{
		int flag=1;
		for(int j=0;j<CoreValSet->PosNum;j++)
		{//PosSet核值属性的位置;PosNum:核值属性的数目
			if(pInfo[i][CoreValSet->PosSet[j]]!=pInfo[iRecNo][CoreValSet->PosSet[j]])
			{//对应核值属性值不等
				flag=0;
				break;
			}
		}
		if(flag==1)//加入等价类集合
			UindCoreValX->PosSet[UindCoreValX->PosNum++]=i;
	}
}

void IndValRed::CoreDx(int iRecNo,PosD* RuleCoreVal)
{	//决策分类  求规则的核值属性类  iRecNo 为样例号 对应的核值属性为RuleCoreVal
	PosD* sameRecAdv=new PosD(iRecNum);//sameRecAdv->PosNum=0
	if(sameRecAdv==NULL)
	{
		AfxMessageBox("内存分配失败!");
		return;
	}
	for(int i=0;i<iRecNum;i++)
		if(pInfo[i][iConNum]==pInfo[iRecNo][iConNum])//决策相同的类
			sameRecAdv->PosSet[sameRecAdv->PosNum++]=i;
	for(i=0;i<iConNum;i++)
	{	//去掉一个条件属性i后的分类
		//如果属性i是被约掉的，继续；
		int tflag=0;
		for(int p=0;p<pNoValCon->PosNum;p++)//pNoValCon属性被约掉
			if(pNoValCon->PosSet[p]==i)
			{
				tflag=1;
				break;
			}
		if(tflag==1)
			continue;
		PosD* sameRecCi=new PosD(iRecNum);
		if(sameRecCi==NULL)
		{
		   AfxMessageBox("内存分配失败!");
		   return;
		}
		for(int j=0;j<iRecNum;j++)
		{//对每个记录j
			int flag=1;
			for(int k=0;k<i;k++)
			{
				if(pInfo[j][k]!=pInfo[iRecNo][k])
				{
					flag=0;
					break;
				}
			}
			for(k=i+1;k<iConNum;k++)
			{
				if(pInfo[j][k]!=pInfo[iRecNo][k])
				{
					flag=0;
					break;
				}
			}
			if(flag==1)//找到条件属性都相同的记录j,加入iRecNo的分类中
				sameRecCi->PosSet[sameRecCi->PosNum++]=j;
		}
		//判断是否和决策分类有包含关系
		int flag=1;
		for(j=0;j<sameRecCi->PosNum;j++)
		{//j为条件分类中第j个样例
			int tempflag=0;
			for(int k=0;k<sameRecAdv->PosNum;k++)
			{//在样例的决策类中找是否存在样例条件分类中的样例
				if(sameRecAdv->PosSet[k]==sameRecCi->PosSet[j])
				{//找到
					tempflag=1;
					break;
				}
			}
			if(tempflag==0)
			{//在决策类中没找到
				flag=0;
				break;
			}
		}
		if(flag==0)//至少有一个条件类的样例不包含于其决策类中
			RuleCoreVal->PosSet[RuleCoreVal->PosNum++]=i;//属性i为核属性
		sameRecCi->DeletePos();
		delete sameRecCi;
	}//end for 
	sameRecAdv->DeletePos();
	delete sameRecAdv;
}

void IndValRed::CoreY(PosD* RuleClass,PosD* AdvCoreVal)
{	//每求出一个core(dx),都求并集置为AdvCoreVal
	for(int i=0;i<RuleClass->PosNum;i++)
	{
		PosD* RuleCoreDxi=new PosD(iConNum);
		if(RuleCoreDxi==NULL)
		{
		   AfxMessageBox("内存分配失败!");
		   return;
		}
		int iRecNoi=RuleClass->PosSet[i];
		CoreDx(iRecNoi,RuleCoreDxi);//求每条规则的核值属性集
		for(int j=0;j<RuleCoreDxi->PosNum;j++)
		{	//并集
			int flag=0;
			for(int k=0;k<AdvCoreVal->PosNum;k++)
			{
				if(AdvCoreVal->PosSet[k]==RuleCoreDxi->PosSet[j])
				{
					flag=1;
					break;
				}
			}
			if(flag==0)
				AdvCoreVal->PosSet[AdvCoreVal->PosNum++]=RuleCoreDxi->PosSet[j];
		}
		RuleCoreDxi->DeletePos();
		delete RuleCoreDxi;
	}
}

bool IndValRed::OrderCoreA(PosD* CoreA1,PosD* CoreA2,PosD* &CoreA)
{//由测度函数得有序集OA-->CoreA
	//将A1,A2并到A中
	for(int i=0;i<CoreA1->PosNum;i++)
		CoreA->PosSet[CoreA->PosNum++]=CoreA1->PosSet[i];
	for(i=0;i<CoreA2->PosNum;i++)
	{
		int flag=0;
		for(int j=0;j<CoreA->PosNum;j++)
		{//看是否CoreA中已经包含了CoreA2中的第i元素
			if(CoreA->PosSet[j]==CoreA2->PosSet[i])
			{
				flag=1;
				break;
			}
		}
		if(flag==0)//不包含,插入
			CoreA->PosSet[CoreA->PosNum++]=CoreA2->PosSet[i];
	}
	//求CoreA中各个核值的权
	int* wightA=new int[CoreA->PosNum];
	if(wightA==NULL)
		return false;
	for(i=0;i<CoreA->PosNum;i++)
	{
		int XNum=0;
		int* XSet=new int[iConNum];
		if(XSet==0)
			return false;
		//如果属性不是被约掉了，且不是i属性，加入,得到C'-{Ci}属性集
		for(int j=0;j<iConNum;j++)
		{
			int flag=0;
			if(j==CoreA->PosSet[i])
				flag=1;
			for(int k=0;k<pNoValCon->PosNum;k++)
				if(pNoValCon->PosSet[k]==j)
				{
					flag=1;
					break;
				}
			if(flag==0)
				XSet[XNum++]=j;
		}

		PosD* PosCiD=new PosD(iRecNum);
		if(PosCiD==0)
			return false;
		PosXD(XNum,XSet,PosCiD);//得到正域PosCiD
		wightA[i]=PosCiD->PosNum;//测度.没有除以|U|,因为|U|为常量
		PosCiD->DeletePos();
		delete PosCiD;
		delete []XSet;
	}
	//按照测度函数从大到小的顺序对属性排序
	for(i=0;i<CoreA->PosNum-1;i++)
	{
		int tempcore;
		int tempwight;
		int temp=i;
		for(int k=i+1;k<CoreA->PosNum;k++)
		{
			if(wightA[temp]<=wightA[k])
				temp=k;
		}
		if(temp!=i)
		{//exchange wight i和temp测度交换
			tempwight=wightA[i];
			wightA[i]=wightA[temp];
			wightA[temp]=tempwight;
			//exchange core i和temp属性交换
			tempcore=CoreA->PosSet[i];
			CoreA->PosSet[i]=CoreA->PosSet[temp];
			CoreA->PosSet[temp]=tempcore;
		}
	}
	delete []wightA;
	return true;
}

void IndValRed::SetNoValCon()
{
	pNoValCon=new PosD(iConNum);
	for(int i=0;i<iConNum;i++)
		if(pInfo[0][i]==-1)//该属性被约简了
			pNoValCon->PosSet[pNoValCon->PosNum++]=i;
}

bool IndValRed::MinRules()
{//算法主程序
	//求u|D
	iClassUindDNum=0;
	int XNum=1;
	int *XSet=new int[1];
	XSet[0]=iConNum;
	if((pUindD=new int*[iRecNum])==0)
		return false;
	for(int i=0;i<iRecNum;i++)
		if((pUindD[i]=new int[iRecNum+1])==0)
			return false;
	UindX(XNum,XSet,iClassUindDNum,pUindD);//计算决策分类
	delete []XSet;
	//init
	iRulesNum=0;
	if((pRules=new int*[iRecNum])==0)
		return false;
	for(i=0;i<iRecNum;i++)
		if((pRules[i]=new int[iConNum+1])==0)
			return false;
	for(i=0;i<iClassUindDNum;i++)
	{	//对于每一个决策分类y
		PosD* DRCy=new PosD(pUindD[i][0]);
		if(DRCy==0)
			return false;
		DRCy->PosNum=pUindD[i][0];
		for(int j=0;j<DRCy->PosNum;j++)
			DRCy->PosSet[j]=pUindD[i][j+1];//将第i个等价类中的元素拷贝
		//标记dx是否被运算中delete了
		int* signDx=new int[DRCy->PosNum];
		if(signDx==0)
			return false;
		for(j=0;j<DRCy->PosNum;j++)
			signDx[j]=1;
		//求每一个y的CoreY
		PosD* AdvCoreVal=new PosD(iConNum);//核值属性
		if(AdvCoreVal==0)
			return false;
		CoreY(DRCy,AdvCoreVal);//求core(y)
		//1)
		for(j=0;j<DRCy->PosNum;j++)
		{//对每一个决策类中的样例
			if(signDx[j]==0)
				continue;
			//求[x]core(dx)
			int iRecNo=DRCy->PosSet[j];//取第一个未输出规则的样例
			PosD* RuleCoreVal=new PosD(iConNum);
			if(RuleCoreVal==0)
				return false;
			CoreDx(iRecNo,RuleCoreVal);//计算样例的条件属性核
			PosD* UindCoreValX= new PosD(iRecNum);
			if(UindCoreValX==0)
				return false;
			UindCoreVal(iRecNo,RuleCoreVal,UindCoreValX);//求[x]core(dx),结果放于UindCoreValX
			//2)
			int flag=1;
			for(int k=0;k<UindCoreValX->PosNum;k++)
			{//看是否[x]core(dx)包含于决策分类y
				int oneflag=0;
				for(int l=0;l<DRCy->PosNum;l++)
					if(DRCy->PosSet[l]==UindCoreValX->PosSet[k])
					{
						oneflag=1;
						break;
					}
				if(oneflag==0)
				{
					flag=0;//说明不包含
					break;
				}
			}
			//2)<<<<<<<<<<<<<
			if(flag==1)//包含
			{	//outout one rule
				int tempNo=UindCoreValX->PosSet[0];
				for(int l=0;l<iConNum;l++)
				{//l表示属性代号
					int tempflag=0;
					for(int m=0;m<RuleCoreVal->PosNum;m++)
					{//规则的核值属性 RuleCoreVal
						if(l==RuleCoreVal->PosSet[m])
						{//l是核值属性
							tempflag=1;
							break;
						}
					}
					if(tempflag==1)//用[x]core(dx)中的记录的值 核值,保存原值
						pRules[iRulesNum][l]=pInfo[tempNo][l];//iRulesNum初值为0
					else//非核值,对应输出为'- '
						pRules[iRulesNum][l]=-1;
				}
				pRules[iRulesNum][iConNum]=pInfo[tempNo][iConNum];//决策值写入
				iRulesNum++;//规则数加一
				//delete [x]core(dx) from DRCy
				for(int m=0;m<UindCoreValX->PosNum;m++)
				{
					for(int n=0;n<DRCy->PosNum;n++)
					{
						if(DRCy->PosSet[n]==UindCoreValX->PosSet[m])
							signDx[n]=0;
					}
				}
			}//endof 2)
			//3)
			else//[x]core(dx)不包含于y
			{
				PosD* CoreA =new PosD(iConNum);
				PosD* CoreA1=new PosD(iConNum);
				PosD* CoreA2=new PosD(iConNum);
                if(!(CoreA && CoreA1 && CoreA2))//分配内存有误
					return false;
				//A1
				for(int m=0;m<AdvCoreVal->PosNum;m++)
				{//AdvCoreVal为core(y)
					int tempflag=0;
					for(int n=0;n<RuleCoreVal->PosNum;n++)
					{//RuleCoreVal为该规则的核值属性 core(dx)
						if(RuleCoreVal->PosSet[n]==AdvCoreVal->PosSet[m])
						{
							tempflag=1;
							break;
						}
					}
					if(tempflag==0)//core(y)-core(dx)
						CoreA1->PosSet[CoreA1->PosNum++]=AdvCoreVal->PosSet[m];
				}
				//A2
				for(m=0;m<iConNum;m++)
				{		
					int tflag=0;
					for(int p=0;p<pNoValCon->PosNum;p++)
					{
						if(pNoValCon->PosSet[p]==m)
						{
							tflag=1;
							break;
						}
					}
					if(tflag==1)//如果是被约掉的就继续
						continue;
					int tempflag=0;
					for(int n=0;n<AdvCoreVal->PosNum;n++)
					{
						if(AdvCoreVal->PosSet[n]==m)
						{
							tempflag=1;
							break;
						}
					}
					if(tempflag==0)//C-core(y)
						CoreA2->PosSet[CoreA2->PosNum++]=m;
				}
				//A=A1 U A2 并排序
				OrderCoreA(CoreA1,CoreA2,CoreA);
				//4)
				for(m=1;m<=CoreA->PosNum;m++)
				{//m阶
					//求CoreA的m介幂集,注意求出的仅仅是序列号
					int iDemSetNum;
					iDemSetNum=CoreA->PosNum;
					max1=CoreA->PosNum*CoreA->PosNum*iDemSetNum+1;
		//			max1=CoreA->PosNum*iDemSetNum+1;
					int **pDemSet=new int*[max1];
					for(int n=0;n<max1;n++)
						pDemSet[n]=new int[iConNum];
					//一阶的不用求了
				//	iDemSetNum=CoreA->PosNum;
					for(n=0;n<iDemSetNum;n++)
						pDemSet[n][0]=n;
					//call DemSet()
					DemSet(m,2,iDemSetNum,CoreA->PosNum,&pDemSet);//m阶幂子集
					//5)
					for(n=1;n<=iDemSetNum;n++)
					{//子集数目
						//6)
						//B
						PosD* CoreB=new PosD(iConNum);
						if(CoreB==0)
							return false;
						for(int p=0;p<RuleCoreVal->PosNum;p++)//得到core(dx)
							CoreB->PosSet[CoreB->PosNum++]=RuleCoreVal->PosSet[p];
						for(p=0;p<m;p++)
						{//m为阶数
							int tempflag=0;
							for(int q=0;q<CoreB->PosNum;q++)
							{//看core(dx) 中是否包含T(OA)中的属性
								if(CoreA->PosSet[pDemSet[n-1][p]]==CoreB->PosSet[q])
								{
									tempflag=1;
									break;
								}
							}
							if(tempflag==0)//不包含
								CoreB->PosSet[CoreB->PosNum++]=CoreA->PosSet[pDemSet[n-1][p]];
						}
						//[x]B是否包含于y
						PosD* UindCoreB=new PosD(iRecNum);
						if(UindCoreB==0)
							return false;
						UindCoreVal(iRecNo,CoreB,UindCoreB); //求[x]core(dx)						
						int flagb=1;
						for(int k=0;k<UindCoreB->PosNum;k++)
							{
								int oneflag=0;
								for(int l=0;l<DRCy->PosNum;l++)
									if(DRCy->PosSet[l]==UindCoreB->PosSet[k])
									{//看[x]B是否包含于y
										oneflag=1;
										break;
									}
								if(oneflag==0)
								{//不包含
									flagb=0;
									break;
								}
							}
						if(flagb==1)//包含,输出规则dx
						{
							//outout one rule
							int tempNo=UindCoreB->PosSet[0];
							for(int l=0;l<iConNum;l++)
							{
								int tempflag=0;
								for(int m1=0;m1<CoreB->PosNum;m1++)
								{
									if(l==CoreB->PosSet[m1])
									{//l为约简属性集
										tempflag=1;
										break;
									}
								}
								if(tempflag==1)//用[x]core(dx)中的记录的值
									pRules[iRulesNum][l]=pInfo[tempNo][l];
								else
									pRules[iRulesNum][l]=-1;
							}
							pRules[iRulesNum][iConNum]=pInfo[tempNo][iConNum];//决策
							iRulesNum++;//规则数加一
							//delete [x]core(dx) from DRCy
							for(int m1=0;m1<UindCoreB->PosNum;m1++)
							{
								for(int n=0;n<DRCy->PosNum;n++)
								{
									if(DRCy->PosSet[n]==UindCoreB->PosSet[m1])
										signDx[n]=0;
								}
							}
							n=iDemSetNum+1;//退出一个m阶子集内部循环
                            m=CoreA->PosNum+1;//退出所有有序集循环,进行最外层的下一次循环,取下一个dx
					//	    goto end9;	
						}//endof if(flagb==1)
			//			else//[x]B不包含于y时
			//			{
						//	goto end9;
			//			} 
						CoreB->DeletePos();
						delete CoreB;
						UindCoreB->DeletePos();
						delete UindCoreB;
					//7)
					}//end for(n=1;n<=iDemSetNum;n++)结束m阶有序集内部循环
        			for(int i=0;i<max1;i++)
						delete[] pDemSet[i];
					if(pDemSet)
						delete pDemSet;
				//8)
				}//结束所有有序集循环
				CoreA->DeletePos();
				CoreA1->DeletePos();
				CoreA2->DeletePos();
				delete CoreA;
				delete CoreA1;
				delete CoreA2;
			}//end  else 3)
			RuleCoreVal->DeletePos();
			delete RuleCoreVal;
			UindCoreValX->DeletePos();
			delete UindCoreValX;
		}//endof 1>  选择下一条决策
		DRCy->DeletePos();
		delete DRCy;
		delete []signDx;
		AdvCoreVal->DeletePos();
		delete AdvCoreVal;
	}//endof for对每一个y
	return true;
}//endof function
	
bool IndValRed::myindvalred()
{
//	try{

	if(!InitTable())
		return false;
	if(!DelOverlap())//删除冗余属性
		return false;
	SetNoValCon();
	if(!MinRules())
		return false;
	FindSameRec();
	return true;
//	}
/*	catch(...)
	{
		AfxMessageBox("运行算法失败!\n清检查输入文件格式是否正确!",MB_ICONSTOP|MB_OKCANCEL );
	    return false;
	}		
*/
}