valreductiontwo.cpp

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

// ValReductionTwo.cpp: implementation of the ValReductionTwo class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
//#include "Rset.h"

#include "ValReductionTwo.h"
#include"stdlib.h"
#include<stdio.h>
#include"string.h"
#ifndef NULL
#define NULL 0
#endif
#ifndef TRUE
#define TRUE 1
#endif
#ifndef FALSE
#define FALSE 0
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

/////////////////////////////////////////////////////////////////////////////
// ValReductionTwo

/////////////////////////////////////////////////////////////////////////////
// CValReductOne message handlers

bool ValReductionTwo::del_line()
{  //删去原决策表中无效的属性  success:return true;
	int i,j;
	int **table=NULL;
	int count=0;
	if((pDelTable = new int[con_num+1])==0)
	{
		AfxMessageBox("内存分配错误!");
		return false;
	}
	for(i = 0;i < con_num+1;i++)
		pDelTable[i] = 0;
	for (i=0;i<con_num+1;i++)
	{
		if (info[0][i]!=-1)
           count++;
	}
    if((table=new int *[rec_num])==0)
	{//rec_num为记录数
		AfxMessageBox("内存分配错误!");
		return false;
	}
	for (i=0;i<rec_num;i++)
		if((table[i]=new int [count])==0)
		{
		   AfxMessageBox("内存分配错误!");
		   return false;
		}
	count=0;//记录未被约简的属性数目
	for (i=0;i<con_num+1;i++)
	{	
		if (info[0][i]!=-1)
        {   
			for (j=0;j<rec_num;j++)
				table[j][count]=info[j][i];
            count++;
			pDelTable[i] = 1;
		}
	}
    for (i=0;i<rec_num;i++)
		if(info[i]!=NULL) delete []info[i];
	delete []info;
	info=NULL;
/*	if((info=new int *[rec_num])==0)
		{
		   AfxMessageBox("内存分配错误!");
		   return false;
		} 		
	for (i=0;i<rec_num;i++)
		if((info[i]=new int [count])==0)
		{
		   AfxMessageBox("内存分配错误!");
		   return false;
		}
  */
	info=table;
	con_num=count-1;//非约简的条件属性数目
	return true;
}


int ** ValReductionTwo::generate_rule()
{//得到规则 wrong :return NULL;else return flag_info(规则)???
	int i,j,k;                      //循环变量
	int * att=NULL;                 //除所选属性外的其它属性
	int * att_val=NULL;             //除所选属性外的其它属性值
	int val;                      //属性值累计
	int att_num;                  //属性累计
	int ** flag_info=NULL;          //除去一条属性的决策表
	int conflict;                   //冲突类型标志
	int find=FALSE;                //检查是否有被标记的记录
	int findone=FALSE;             //检查是否有需将"?"改为"*"的记录
	int * tuple=NULL;               //保存多余的规则
	int * record=NULL;              //保存重复的记录	
	int same=0;
	int sum=0;
	int rec=0;   //统计新的规则数
//	del_line();//删除已经约简的属性 去除相关属性列后得到新表info
	//info:信息表; rec_num记录数
    find_overlap(info,rec_num,record);//查找重复记录 保存在record中
	if(record!=NULL)//重复的记录不为空,得到删除重复记录后的表
	{
		rule_num=rec_num-record[0];//规则数为去除了重复样例后的样例数目
		int ** rule=NULL;
		if((rule=new int * [rule_num])==0)
			return NULL;
		for(i=0;i<rule_num;i++)
			if((rule[i]=new int[con_num+1])==0)
				return NULL;
		//rule为删除重复记录后的规则表
		for(i=0;i<rec_num;i++)
		{
			same=0;
			for(j=0;j<record[0];j++)
				if(i!=record[j+1])
					same++;
			if(same==record[0])//该记录i不为重复记录
			{//写入rule
				for(j=0;j<con_num+1;j++)
					rule[rec][j]=info[i][j];//rec初始化是0
				rec++;
			}
		}
		for(i=0;i<rec_num;i++)
			delete []info[i];
		delete []info;
		info=rule;//info变为规则表
		rec_num=rule_num;//记录数为规则数
		delete []record;
	}
	else//record=NULL
    	rule_num=rec_num;

   	if((att=new int[con_num])==0)
		return NULL;
   	if((att_val=new int[con_num])==0)
		return NULL;

	 //给flag_info数组分配空间，它是info数组的一个拷贝，用来做中间处理
   	if((flag_info=new int * [rule_num])==NULL)
		return NULL;  //flag_info:除去一条属性的决策表??copy rule table
    for(i=0;i<rule_num;i++)
	{
        if((flag_info[i]=new int[con_num+1])==0)
			return NULL;
   		for(j=0;j<con_num+1;j++)
	    	flag_info[i][j]=info[i][j];
	}// end copy info to flag_info

   	for(i=0;i<con_num;i++)
	{//除去i属性 
//步骤1：对信息表中的条件属性进行逐列考察。若删除该列后产生冲突，则保留
//冲突记录的原该属性值；否则，如果出现重复记录，我们可将该记录的原属性
//值标为"*"；对于其他记录，将该属性值标为"?"
//将每次考察的属性编号存入att数组中(每次均考虑con_num-1个属性，
//第i次不考虑第i个属性
		att_num=0;
		for(k=0;k<i;k++)//att存储去除i属性后的条件属性集
        	att[att_num++]=k;  //属性累计 att_num初始为零 初始化att
    	for(k=i+1;k<con_num+1;k++)
	    	att[att_num++]=k;
    	for(j=0;j<rule_num;j++)//rule_num为不重复样例数
		{//对每条规则考察去除该i属性后的情况,进行相应处理  
			//将每次考察的属性值存入att_val数组中
			val=0;
     		for(k=0;k<i;k++)
     			att_val[val++]=info[j][k];//val初始化为0
	    	for(k=i+1;k<con_num+1;k++)
	    		att_val[val++]=info[j][k];//att_val存储j样例
			//检查去掉属性i后决策表中是否有第j条记录冲突的记录存在
	    	conflict=find_conflict(att,att_val);//看是否存在冲突:冲突时返回1
  	//不冲突,且没有重复时返回0.有多个重复样本,返回-1
			if(conflict==-1)
			{//表示有重复记录
			   	flag_info[j][i]=-1;//标记j样例i属性为'*'
			   	find=TRUE; //find:检查是否有被标记的记录
			}
	    	else if(conflict==0)//不冲突,且没有重复时
			{
		    	flag_info[j][i]=-2;//标为'?'
		    //	find=TRUE;
		    	findone=TRUE; //检查是否有需将"?"改为"*"的记录
			}
		}
	}//标记结束
	delete []att;
	delete []att_val;
//步骤2：删除可能产生的重复记录，并考察每条含有标为"?"的记录 。
//如果仅由未被标记的属性值即可以判断出决策，我们将符号"?"改为"*"，
//否则将"?"改为原来的属性值。若某条记录的所有条件属性均被标记，
//则标记"?"修改为原属性值;
	bool flag;
   	if(findone==TRUE)//有'?'
    	trans_flag(flag_info,flag);//第二步处理:将"?"改为"*"或原值
  	if(find==TRUE||(flag==true))
	{//表中有'*'
//步骤3：删除所有条件属性均被标记"*"的记录及可能产生的重复记录
//（card(T')=n'）
		int mark;
		int count=0;
		int num=0;
		mark=check_conflict(flag_info);// 返回条件属性全被标为"*"的个数 失败:返回-1
   		if(mark>0)        //说明含有条件属性全为"*"的记录,删除
		{
            int ** tab=NULL;
			if((tab=new int * [rule_num-mark])==0)
				return NULL;
			for(i=0;i<rule_num-mark;i++)
				tab[i]=new int[con_num+1];
			for(i=0;i<rule_num;i++)
			{
				count=0;
				for(j=0;j<con_num;j++)
					if(flag_info[i][j]==-1)//找到'*'
						count++;
			    if(count<con_num)//条件属性不全为"*"
				{//copy 该规则到tab表中
				    for(j=0;j<con_num+1;j++)
						tab[num][j]=flag_info[i][j];
					num++;				
				}
			}//得到去除了所有条件属性均为'*'的规则
			for(i=0;i<rule_num;i++)
				delete []flag_info[i];
			delete []flag_info;
			flag_info=tab;//规则表flag_info改为tab
			rule_num-=mark;//规则数等于原规则数减去属性全为'*'的记录个数
		}//end if(mark>0)
		//还需要减去可能产生的重复记录???(未完成)

		record=NULL;
		find_overlap(flag_info,rule_num,record);//查找重复记录,记录在record中
		if(record!=NULL)
		{
			same=0;
			rec=0;
    		int ** rule=NULL;
			if((rule=new int * [rule_num-record[0]])==0)
				return NULL;
			for(i=0;i<rule_num-record[0];i++)
	     		rule[i]=new int[con_num+1];
    		for(i=0;i<rule_num;i++)
			{
	    		for(j=0;j<record[0];j++)
		    		if(i!=record[j+1])
			    		same++;
	    		if(same==record[0])
				{//不是重复记录
		    		for(j=0;j<con_num+1;j++)
			    		rule[rec][j]=flag_info[i][j];
					rec++;
				}
				same=0;
			}
	    	for(i=0;i<rule_num;i++)
		    	delete []flag_info[i];
    		delete []flag_info;
			flag_info=rule;
			rule_num=rec;
			delete []record;
		}
	}

//步骤4：如果两条记录仅有一个条件属性值不同，且其中一条记录该属性被
//标记为"*"，那么，对该记录如果可由未被标记的属性值判断出决策，
//则删除另外一条记录，否则，删除本记录
		tuple=del_superflous(flag_info);//删除多余的规则,返回多余的规则指针
	//删去表中多余的规则，同时更新flag_info，rule_num，same_rec
		if(tuple!=NULL)
		{//有冗余规则
			same=0;
			int sum=0;
			rec=0;                        
			int ** rule=NULL;
			if((rule=new int * [rule_num-tuple[0]])==0)
				return NULL;
			for(i=0;i<rule_num-tuple[0];i++)
				rule[i]=new int[con_num+1];
			for(i=0;i<rule_num;i++)
			{//从规则表中去除冗余规则得到新的规则表:rule
				for(j=0;j<tuple[0];j++)
					if(i!=tuple[j+1])//看i规则是否是冗余规则
						same++;
				if(same==tuple[0])
				{//不是冗余规则,重置规则表
					for(j=0;j<con_num+1;j++)
						rule[rec][j]=flag_info[i][j];
                    rec++;
				}//end if(same==tuple[0])
				same=0;
			}
			for(i=0;i<rule_num;i++)
				delete []flag_info[i];
			delete []flag_info;
			flag_info=rule;
			rule_num=rec;
			delete []tuple;
		}
	return flag_info;
}
bool ValReductionTwo::find_overlap(int ** tab,int number,int* &same_rec)
{//查找重复记录 并把重复记录的编号保存在数组中，返回该数组
	//决策表的值保存在tab中，number表示表中记录的个数 
//找到重复样例,返回:true  否则,返回false
	int i,j,k,t;                     //循环变量
	int count=0;                     //统计属性值相同的个数
	int find=FALSE;                 //查找是否已经被列为重复记录
//	int * same_rec=NULL;             //保存重复的记录
	same_rec=NULL; 
	int same_num=0;                  //重复记录的个数
	for(i=0;i<number-1;i++)
	{
		find=false;
	    for(t=0;t<same_num;t++)
          if(same_rec[t]==i)//看i是否为重复样例
	      {
			  find=true;
			  break;
		  }
        if(find)
			continue;
		for(j=i+1;j<number;j++)
		{
			find=false;
		    for(t=0;t<same_num;t++)
              if(same_rec[t]==j)//看j是否为重复样例
			  {
			  find=true;
			  break;
			  }
			if(find)
			  continue;
			count=0;
			for(k=0;k<con_num+1;k++)//比较i和j样例各个属性
                 if(tab[i][k]==tab[j][k])//tab为原始表
					count++;
				else
					break;			
			if(count==(con_num+1))//说明i和j两条记录完全相等
			{
				if(same_rec==NULL)//为same_rec分配内存空间
                 	if((same_rec=new int[number])==0)
						return false;
		/*		for(t=0;t<same_num;t++)
                    if(same_rec[t]==i)//看i是否为重复样例
					{//是,则j
					    find=TRUE;
					    break;
					}
		*/
				if(find==FALSE)//将和i样例相同的j样例标价为重复
			    	same_rec[++same_num]=j;//从第一个元素开始赋值
			}
		}
	}
	if(same_rec!=NULL)
    	same_rec[0]=same_num;//第0个元素存储重复样例的个数
	if(same_rec==NULL)
		return false;
	else return true;
}

int ValReductionTwo::find_conflict(int * att, int * val)
{//对删除重复样例后的表
	//检查除去一个属性后的信息表是否存在冲突 冲突:返回1 ;
	//不冲突,且没有重复时返回0.有多个重复样本,返回-1
	int i,j;                                     //循环变量
	int count=0;                                 //相同属性值数目统计
	int sum=0;
	int find=FALSE;
	for(i=0;i<rule_num;i++)
	{
		for(j=0;j<con_num-1;j++)
			if(info[i][att[j]]==val[j])
			    count++;
			else
				break;
		if(count==(con_num-1))//条件属性相同
			if(info[i][con_num]!=val[con_num-1])
			{//决策不同,冲突
				find=TRUE;
				break;
			}
			else
				sum++;
		count=0;
	}
	if(find==TRUE)
		return 1;
	else if(sum==1)//只有样例本身 
		return 0;
	else
		return -1;
}

void ValReductionTwo::trans_flag(int ** &tab,bool &flag)
{//考察每个含有?的记录，根据情况修改它的属性值(第二步中)
	int i,j;                  //循环变量
	int find=FALSE;         //查找被标为"?"的属性值
	int count=0;        //统计信息表一条记录中非-2及非-1的个数
	int conflict;
	int * att=NULL;
	flag=false;
	if((att=new int[con_num])==0)
	{
		AfxMessageBox("内存分配错误!");
		return;
	}
	int * att_val=NULL;
	if((att_val=new int[con_num])==0)
	{
		AfxMessageBox("内存分配错误!");
		return;
	}	
	for(i=0;i<rule_num;i++)
	{//对每个样例判断'?'
		for(j=0;j<con_num;j++)
			if(tab[i][j]==-2)//找到i记录第一个标'?'的j属性,退出
			{//说明i记录含有'?'
				find=TRUE;//TRUE=1
				break;
			}
		if(find==TRUE)
		{//对含有'?'的记录进行处理