attentropyreducetwo.cpp

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

		return 0;// IND_Attrb[i][0]=K i号分内的个数为K
    for(i=1;i<=rec_num;i++)
	{
		if((IND_Attrb[i]=new int[rec_num+1])==0)
			return 0;
	}
	return 1;
}

bool CAttEntropyReduceTwo::Reduct_Table()  //计算结果属性组合
{  
	double  H_DR,H_DR_a;
    int i,j,count=0,ncount=0;//循环变量
    decreductset= new  int[2];
	if((resultset= new int[con_num+1])==0)
		return false; //con_num:条件属性数
	if((attreductset= new int[con_num+1])==0)
		return false;
  	redu_num=con_num;

    attreductset[0]=redu_num;
    decreductset[0]=1;	
	decreductset[1]=con_num;
//初始化约简结果的值  resultset[i]装结果的 	
    resultset[0]=0;
	
////////////////排序决策表的属性重要性////////////应用熵的重要性进行属性排序
   double  *SGFH;
   double  *paixu;
 if((SGFH=new double[con_num+1])==0)//定义属性重要性的熵数组；
    return false;
 if((paixu=new double[con_num+1])==0)
	 return false;
 attreductsetxu=new int[2];
 attreductsetxu[0]=1;
  for(i=1;i<=con_num;i++)
  {   
      attreductsetxu[1]=i-1;
	 
	  SGFH[i-1]=Entropytwo(decreductset,1,attreductsetxu,1);
      if(SGFH[i-1]==-1)
		  return false;
	  paixu[i]=SGFH[i-1];//i从1...con_num
  }//算得各条属性的条件熵
  for(i=1;i<=con_num;i++)
  {
	for(j=1;j<=con_num-i;j++)//冒泡法排序各个属性的熵：从小到大
	{
		double t;
		if(paixu[j]>paixu[j+1])
		{
			t=paixu[j];
			paixu[j]=paixu[j+1];
			paixu[j+1]=t;
		}
	}//end for (j
  }//end for( i

///////////////END/////////////////
//建立一种等价和转换关系
  int *flag;
  if((flag= new int[con_num])==0)
	  return false;
  for(i=0; i<con_num;i++)  // 初始化FLAG=0
	flag[i]=0;
  for(i=1;i<=con_num;i++)
  {//循环完一次，又一个属性被标记
    for(j=0;j<con_num;j++)
    {  
	    if(paixu[i]==SGFH[j])
		{   
			 if(flag[j]==0)
			 {
				 attreductset[i]=j;//标志属性在熵值排序中的位置
				 //i从1开始取，j从0开始取
				 flag[j]=1;//以后不再比较
				 break;
			 }
		}
	}//end for j
  }//end for i
delete  []SGFH;
delete  []attreductsetxu;
delete  []paixu;
delete  []flag;
/////////////////////////////////////
  result_num=0;
//计算全局决策表的相对D的条件熵
  H_DR=Entropytwo(decreductset,1,attreductset,redu_num);
  if(H_DR==-1)
	  return false;
  //比较条件熵的大小，进行决策表的约简
  for(i=1;i<=con_num;i++)
  {
    H_DR_a=Entropytwo(decreductset,1,attreductset,redu_num-1);
	//H(D|(R-a))的条件熵// H_DR_a减一个最后属性后的条件熵
	//看能不能去掉最后一个属性
	//attreductset:约简条件属性集
    if(H_DR==-1)
		return false;
	if(0<i&&i<(con_num-1))//对i＝con_num 和i=con_num另行处理
    {
  	  if(H_DR!=H_DR_a)//熵不等时，表明最后一个属性不能去掉
	 {	  //将最后一个条件属性与约简属性集的前第ncount位交换
     //如果都不能约简，这样可以对所有前面redu_num－1个条件属性进行测试
	//attredictset中的元素是按照重要性从高到低排列的，从后向前
  //这样可替换可保持信息系统的完备性
		  ncount++;//最开始为0
		int t;
		t=attreductset[redu_num-ncount];
        attreductset[redu_num-ncount]=attreductset[redu_num];
		//con_num-i;//首尾交换
	    /*   if(attreductset[redu_num]==attreductset[1])
		   {
            attreductset[redu_num]=attreductset[1];
		    attreductset[1]=0;
		   }
 	       else*/
		attreductset[redu_num]=t;//con_num-1-i;
	  }//end if(H_DR!=H_DR_a)
	 if(H_DR==H_DR_a)//计算得到的熵相等时，说明最后属性可以约掉
	 {    
       redu_num--;//得到的约简属性的总数减一
	   count++;
	   if(i!=count)//防止是熵值小的不能被约简的情况
	   {//如开始是abcd,//i=1,d不能约掉，变成abdc//i=2,c可以约掉
		  //redu_num 变为3,将d移到b之前，为adc
		//如果是i==count,则说明是最后一个属性可以约掉，redu_num已经
		   //表示约掉最后一个属性了，所以不必处理
		 	int k;
			k=attreductset[redu_num-ncount];
            attreductset[redu_num-ncount]=attreductset[redu_num];
            attreductset[redu_num]=k;//con_num-i-1;
	   }
       if(redu_num==1)//我觉得这句不可能被执行，因为i还没循环到最后两个属性
		 break;
	 }//end if(H_DR==H_DR_a)
	}//end if(0<i&&i<(con_num-1))
   else//此时i=con_num-1或者是con_num 最后两个属性处理
   {
    if(H_DR!=H_DR_a)
	{ /* if(attreductset[redu_num]!=attreductset[1])
		{    
			int k;
			k=attreductset[redu_num];
			attreductset[redu_num]=attreductset[1];
            attreductset[1]=k;
			// attreductset[con_num-i]=con_num-i;
             //attreductset[redu_num]=con_num-i-1;
		}*/
	   if(i==con_num-1)//倒数第二个属性
	   {//接上,con_num=4,i=3,去掉b后如果ad算出来的熵不等于总体的熵，
	//说明b不可以约掉,将a和adb中的d交换，看a能不能约简
            int k;
			k=attreductset[redu_num];
			attreductset[redu_num]=attreductset[1];
            attreductset[1]=k;
	   }
	   else//说明是最后一个属性，因为熵不相等，所以退出，得到结果
         break;
	}//end if(H_DR!=H_DR_a)
	else if(H_DR==H_DR_a)//熵相等时if i=3 adb和abcd算出来的熵一样
	{    //说明adb中b可以约掉
       redu_num--;//i＝3约简数目减一 变为2；
	   //如果是i＝4时相等表示da中a可以去掉，此时约简数目变为1
	   if(i!=con_num)//不是最后一个属性，即是倒数第二个属性
        {   
		    count++;//is 2
	 	    if(i!=count)//判断是否有错位,错位表示例如：abcd可以依次约掉dcb等
			{//只要不是一直约简，有一定有错位 adb中b可以约掉
	          /*if(attreductset[redu_num]!=attreductset[1])//0)
			  {
		        //attreductset[redu_num-ncount]=attreductset[redu_num];
               // attreductset[redu_num]=con_num-i-1;
             //attreductset[redu_num-ncount]=attreductset[redu_num];
	    	 int k;
			 k=attreductset[redu_num];
			 attreductset[redu_num]=attreductset[1];
             attreductset[1]=k;//con_num-i-1;*/	
	     	//将最后一个属性和第一个属性交换，d和a交换，变为da
	            int k;
			    k=attreductset[redu_num];
			    attreductset[redu_num]=attreductset[1];
                attreductset[1]=k;//con_num-i-1;*/
			}//end if(i!=count)
	   }//end if(i!=con_num)
	   if(redu_num==1)
		     break;
	}//end else if(H_DR==H_DR_a)
   }//end else	if(0<i&&i<(con_num-1))
 } //end for(i=1;i<=con_num;i++)
//约简结果	
       result_num=redu_num;
       resultset[0]=result_num;
       reduct_num=1;
	   result=new int * [1];
	   result[0]=new int[result_num+1];
	   result[0][0]=result_num;
	   for(i=0;i<result_num;i++)
		  result[0][i+1]=attreductset[i+1];//得到约简属性位置
	   SelectSort(result[0]);//按照原先顺序排序
	   delete  []attreductset; //非核条件属性集
	   delete  []decreductset;//决策属性集
	    
      return true;
}
 
bool CAttEntropyReduceTwo::Get_Att(int ** att,int num)//得到属性表
{
	int i,j;
	result_num=att[0][0];//att[0][0]中存储着属性数目
	int **attredu;
	if((attredu=new int * [reduct_num])==0)//reduct_num:共有几组属性约简结果
	{
		AfxMessageBox("分配内存时出现错误"); 
	    return false;
	}
	for(i=0;i<num;i++)
	{
		if((attredu[i]=new int[result_num+1])==0)
		{
		  AfxMessageBox("分配内存时出现错误"); 
	      return false;
		} 	
		for(j=0;j<result_num+1;j++)
			attredu[i][j]=att[i][j];
	}    
	if((reduct_att=new char ** [reduct_num])==0)
		return false;	
	for(i=0;i<reduct_num;i++)
	{
		if((reduct_att[i]=new char * [att[i][0]])==0)
			return false;
		for(j=0;j<att[i][0];j++)
			if((reduct_att[i][j]=new char[MAX])==0)
				return false;
		for(j=0;j<att[i][0];j++)
			strcpy(reduct_att[i][j],pAttName[att[i][j+1]]);
	}
	return true;
}
double CAttEntropyReduceTwo::Entropytwo(int *q , int Q,int *p ,int P)//H(q|p)
{	 //error:return -1; success:return >0
    
    double H,y;
	int m,n,i,j,pyx;
	int rownum=rec_num;
    int  **IND_Y;
	if((IND_Y=new int*[rec_num+1])==0)
		return -1;
	for(i=1;i<=rec_num;i++)
		if((IND_Y[i]=new int[rec_num+1])==0)
			return -1;
	for(i=1;i<=rec_num;i++)
		for(j=0;j<=rec_num;j++)
			IND_Y[i][j]=0;
/*
	if((IND_Attrb= new  int*[rec_num+1])==0)
		return -1;// IND_Attrb[i][0]=K i号分内的个数为K
    for(i=1;i<=rec_num;i++)
	{
		if((IND_Attrb[i]=new int[rec_num+1])==0)
			return -1;
	}       
*/
  //求q集的划分--------------------------
	IND(q,Q,rownum);
	m=IND_Order;
	for (i=1;i<=m;i++)
	{
	  for (j=1;j<=IND_Attrb[i][0];j++)
	   
		  IND_Y[i][j]=IND_Attrb[i][j];
	      IND_Y[i][0]=IND_Attrb[i][0];
	}
  //清零	//求p集的划分-------------------------------------
	IND(p,P,rownum);
	n=IND_Order;//不分辨关系的个数
   	//求条件熵H(q|p)
	H=0;
	for (i=1;i<=n;i++)//n是第几个不分辩关系n=89
	{
		for(j=1;j<=m;j++)//M是决策属性的个数m=8
		{	
			pyx = YX_Jiao(j,i,IND_Y);
            if (pyx!=0)
			{	
				y=(double ) IND_Attrb[i][0]/pyx;  //条件概率的倒数
			    H=(double)  pyx*log10(y)/log10(2)+H; 
				 
			}
		}
	}	
     H=H/rownum;
    for(i=1;i<=rec_num;i++)
   {
	   delete []IND_Y[i];
   }
   delete []IND_Y;
 /*
   for(i=1;i<=rec_num;i++)
   {	
	 delete 	[]IND_Attrb[i];
   }      
   delete  []IND_Attrb;	
   */
   return H;	
}
void CAttEntropyReduceTwo::SelectSort(int * att)
{ //用选择法对约简后的属性重新排列,对数组att中的元素按从小到大排序
	int i,j;                                 //循环变量
	int min_item;                            //具有最小值的项
	int transfer;       
	for(i=0;i<att[0]-1;i++)
	{//每进行完一次循环，选出最小值放于开头
		min_item=i;
		for(j=i+1;j<att[0];j++)
			if(att[j+1]<att[min_item+1])
				min_item=j;
		if(min_item!=i)
		{
			transfer=att[i+1];
			att[i+1]=att[min_item+1];
			att[min_item+1]=transfer;
		}
	}
}

//任意的属性组合的划分记录及个数
 void CAttEntropyReduceTwo::IND(int *b, int B, int rownum)//划分
 {
	int ind_order;
	int ind_num,num_colattrsame=0,j,k,m;
	int p,q,i,number=0;

	int *flag= new int[rownum] ;
	for (i=0; i<rownum;i++)  // 初始化FLAG=0；
		flag[i]=0;
	for (i=1;i<=rec_num;i++)//初始化IND_Attrb
	   for(j=0;j<=rec_num;j++)
		  IND_Attrb[i][j]=0; 
  //---------------------------
	i=0;	
	ind_order=0;
    IND_MaxNum = 0;
	while(i<rownum)
	{   
	
		ind_order += 1;
		ind_num = 1; 
		IND_Attrb[ind_order][0]=1;//
		IND_Attrb[ind_order][1]=i+1;
		flag[i]=1;

		for (j=i+1; j<rownum ; j++)
		{
			if (flag[j]==1) 
				continue;

			for (k=1; k<=B; k++)
			{
				p = info[i][b[k]];
				q = info[j][b[k]];
                                  
				if (p == q) 
					num_colattrsame +=1;
			 }
			if (num_colattrsame == B)
			{
				ind_num +=1;
				IND_Attrb[ind_order][ind_num]=j+1;
				flag[j]=1;
				IND_Attrb[ind_order][0]=ind_num;//记录第ind_order划分中对象的个数
			}
			num_colattrsame = 0;
		}
		
		//确定i值
		number=0;
		for(m=1;m<rownum;m++)
		{
			if (flag[m] == 0) 
		       number +=1;
			if (number==1 && flag[m]==0) 
			{//找第一个满足条件的值
				i=m; 
				break;
			}
		}
		if (number==0)//都已经被归类，需要退出
			i=rownum+1;//不满足while条件，可以退出
		if (ind_num>IND_MaxNum) 
			IND_MaxNum = ind_num;
	}
    IND_Order = ind_order;
	ind_order=0;
    delete []flag;
}

    
 ////////////X 与Y的交集个数//Yj与Xi交的个数
 int CAttEntropyReduceTwo::YX_Jiao(int j, int i, int **IND_Y )
{
	 int pyx=0;
	 int p,q,a,b;
	 for(p=1;p<=IND_Attrb[i][0];p++)
	 {
		a=IND_Attrb[i][p];
		for (q=1;q<=IND_Y[j][0];q++)
		{
			b=IND_Y[j][q];
		    if (a==b) 
		    	pyx +=1;
		}
	}
    return pyx;
}  
void CAttEntropyReduceTwo::FreeContent()
{
	int i;
	for(i=0;i<iRecordNum;i++)
		delete []pIntTable[i];
	delete []pIntTable;

    for(i=1;i<=rec_num;i++)
	{	
 	   delete 	[]IND_Attrb[i];
    }      
    delete  []IND_Attrb;	

	for (i=0;i<rec_num;i++)
		delete []info[i];
	delete []info;

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

 //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;
	}

}