attentropyreduce.cpp

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

// AttEntropyReduce.cpp: implementation of the CAttEntropyReduce class.
//
//////////////////////////////////////////////////////////////////////

#include "StdAfx.h"
#include "RSet.h"
#include "AttEntropyReduce.h"
#include "stdio.h"
#include"math.h"
#include "stdlib.h"
#include "string.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

#define MAX 100
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CAttEntropyReduce::CAttEntropyReduce()
{

	pIntTable = NULL;
    pBlockTable = NULL;
    pAttName = NULL;
	pDataType = NULL;
	pAttReduce = NULL;
	struWCutRecord = NULL;
    iInteger = 0;
	iRecordNum = 0;
	iAttNum = 0;
    iBlockNum = 0;
    iStage = -1;
    bSaveTempResult = FALSE;
	bCuts = FALSE;//表示是否存在断点集合
	bBlock = FALSE;
}

CAttEntropyReduce::~CAttEntropyReduce()
{
   FreeContent(); 
}
bool CAttEntropyReduce::AttEntropyReduce()
{
    //double duration;
//	CString str;
   // clock_t  finish	,start;
//	start = clock();
    InitTable();
 //把字符型表转化为int类型
//建立可辨识矩阵与array中，其中不保存重复的属性组合，也没有
//保存该属性组合是属于哪两个记录的，并且对于每个属性组合只保
//留了前两个使他们不同的属性，因为计算核属性既是只有一个属性
//能区分这两个记录的属性，所以不用全部记录下来
//array[i][0]保存的是第i个属性组合的个数(不是1就是2)
   if(Create_Table()==0)//建立决策初始表//建立可辨识矩阵或决策矩阵
      return false;
	if( Create_Array()==1)//success
	{
		if(!Reduct_Table())//计算核属性的表格
	      return false; 
	}
	else 
		return false;
    if(!Get_Att(result,reduct_num))//得到属性值
		return false;
   // finish = clock();
	//duration = (double)(finish - start) / CLOCKS_PER_SEC;
	//str.Format (" 约简运行时间:%f 秒",duration);
    //AfxMessageBox(str);  
	return true;
}

bool  CAttEntropyReduce::GetData(char* FileName)
{//get the privilege pInformation from the file given.
	FILE* fp;

	//return when fail to read the file
	if((fp = fopen(FileName,"r")) == NULL)
	{
//		printf("Can't open the File!\n");
		AfxMessageBox("Can't open the File!");
		return false; 
	}
   // cStyle= new char[100];
	fscanf(fp,"Style:%s\n",cStyle);
	fscanf(fp,"Stage:%d\n",&iStage);
	fscanf(fp,"Condition attributes number:%d\n",&iAttNum);
	fscanf(fp,"Records number:%d\n",&iRecordNum);
	//ipriRecNum=iRecNum;
	SetAttName(fp,iAttNum+1);
	SetDataType(fp,iAttNum+1);
	SetIntegerTable(fp,iAttNum+1,iRecordNum);//fill the integertable
	if(!SetCutResult(fp))
		return false;
	fclose(fp);
	return  true;
}



bool CAttEntropyReduce::SetAttName(FILE* fp, int count)//count是总共的属性数目
{
	int i;
	if(pAttName == NULL)//还没有赋值
	{
		try
		{
			pAttName = new char*[count];
		}
		catch(CMemoryException* e)
		{
			::MessageBeep(MB_ICONHAND);
			AfxMessageBox("Out of the memory!",MB_OK|MB_ICONSTOP);
			e->Delete();
			return FALSE;
		}

		for(i=0;i < count;i++)
		{
			try
			{
				pAttName[i]=new char[100];
			}
			catch(CMemoryException* e)
			{
				::MessageBeep(MB_ICONHAND);
				AfxMessageBox("Out of the memory!",MB_OK|MB_ICONSTOP);
				e->Delete();
				return FALSE;
			}
		}//end for
	}//end if

	for(i=0;i < count;i++)
		fscanf(fp,"%s",pAttName[i]);
	return true;
}

bool CAttEntropyReduce::SetDataType(FILE *fp, int count)
{
	int i;
	try
	{
		pDataType = new char*[count];
	}
	catch(CMemoryException* e)
	{
		::MessageBeep(MB_ICONHAND);
		AfxMessageBox("Out of the memory!",MB_OK|MB_ICONSTOP);
		e->Delete();
		return FALSE;
	}
	for(i = 0;i < count;i++)
	{
		try
		{
		  pDataType[i]=new char[MAX];
		}
		catch(CMemoryException* e)
		{
		  ::MessageBeep(MB_ICONHAND);
		  AfxMessageBox("Out of the memory!",MB_OK|MB_ICONSTOP);
		  e->Delete();
		  return FALSE;
		}
	}//end for

	for(i = 0;i < count;i++)
		fscanf(fp,"%s",pDataType[i]);
	return true;
}

bool CAttEntropyReduce::SetCutResult(FILE* fp)//读入属性断点
{
	int n;
	int iColumn;
	int iCuts;
	struct WCutRecord* pHead = NULL;
	struct WCutRecord* pEnd = NULL;
	char* temp;
	if((temp= new char[MAX])==0)
		return false;//MAX=100
	if(fscanf(fp,"%s",temp) == -1)
	{
		delete[] temp;
		return true;
	}
	if(strcmp(temp,"[Cuts]") != 0)
	{
		delete[] temp;
		return false;
	}
//	bCuts = true;
	while(fscanf(fp,"%d",&iColumn) != -1)//iColumn为属性所在的列
	{
		fscanf(fp,"%d",&iCuts);//iCuts断点数
		pEnd = new WCutRecord;//WCutRecord为断点链表
		if((pEnd->cpCut=new char*[iCuts])==0)
			return false;
		for(int i=0;i<iCuts;i++)
		{
			if(0==(pEnd->cpCut[i] = new char[MAX]))
				return false;
		}//end for
		pEnd->iColumn=iColumn;
		pEnd->iCuts=iCuts;
		pEnd->next=NULL;//下一个断点集
		for(i=0;i<iCuts;i++)
		{
			fscanf(fp,"%s",temp);//[*,*]当成字符串处理
			fscanf(fp,"%d",&n);//离散化值
			strcpy(pEnd->cpCut[n],temp);
		}//end for
		if(pHead == NULL)
		{
			struWCutRecord = pEnd;
			//struWCutRecord为放置断点的链表的入口
			pHead = pEnd;//指向同一个节点
		}//end if
		else
		{
			if(pHead->iColumn>=pEnd->iColumn)
			{
				AfxMessageBox("断点表设置有误!");
                struWCutRecord =NULL;
				return false;
			}
			pHead->next = pEnd;//加入断点链表
			pHead = pEnd;
		}//end else
	}//end while

	delete[] temp;
	return true;
}
bool CAttEntropyReduce::SetIntegerTable(FILE* fp,int column, int row)
{
	int i,j;
	char* string;
	if((string=new char[100])==0)
		return false;
	try
	{
	  pIntTable = new int*[row];
	}
	catch(CMemoryException* e)
	{
	  ::MessageBeep(MB_ICONHAND);
	  AfxMessageBox("Out of the memory!",MB_OK|MB_ICONSTOP);
	  e->Delete();
	  return FALSE;
	}
	for(i = 0;i<row;i++)
	{
	  if((pIntTable[i] = new int[column])==0)
			return false;
	}//end for

	for(i=0;i<row;i++)
	{
		for(j=0;j<column;j++)
		{
			fscanf(fp,"%s",string);
			if(strcmp(string,"-") == 0)
				pIntTable[i][j] = -1;
			else
				pIntTable[i][j] = atoi(string);
		}//end for
	}//end for
	delete []string;
	return true;
}


void CAttEntropyReduce::InitTable()//输入离散后的初始化决策表
{
	int i,j;
    rec_num = iRecordNum;//记录对象数   
	con_num = iAttNum;//条件属性数
	if((info=new int *[rec_num])==0)//原始表,以转化为int指针
	{
        AfxMessageBox("Out of the memory!",MB_OK|MB_ICONSTOP);
    	return;
	}
	for (i=0;i<rec_num;i++)
	{
		try
		{
			info[i]=new int [con_num+1];
		}
		catch(CMemoryException* e)
		{
	     ::MessageBeep(MB_ICONHAND);
	     AfxMessageBox("Out of the memory!",MB_OK|MB_ICONSTOP);
	     e->Delete();
	     return;
		}
	}
	for (i=0;i<rec_num;i++)
	   for (j=0;j<con_num+1;j++)
		info[i][j] = pIntTable[i][j]; 
}

int CAttEntropyReduce::Create_Table()//初步简化决策表，删除多余的行
{//成功:1  失败:0
	int i,j,k,t;          
	int ** infoset;     //删除重复记录后的信息表//新的决策表
	int new_rec_num=0;  //新信息表中的记录数.对象数
	int sum=0;          //统计属性值相同的个数
	bool find=FALSE;//缺省的BOOL值
   	int * same_rec;//指向相同对象的指针编号
	if((same_rec=new int[rec_num])==0)
		return 0;//成功时返回1,失败返回0
    int same_num=0;
	//把重复记录编号存在same_rec中,same_num中为重复记录数目
    for(i=0;i<rec_num-1;i++)//i表示记录数
		for(j=i+1;j<rec_num;j++)
		{	//比较两条记录是否完全相等
			for(k=0;k<con_num+1;k++)
			{    //··········！！##修改过的地方
				if(info[i][k]==info[j][k])
					sum++;
				else
					break;
			}
			if(sum==(con_num+1))//完全相同的属性值
			{
				for(t=0;t<same_num;t++)  
			//same_num是相同的数量,与T的量分开
            //如果记录中有i,说明第j条记录已存在same_rec中了
					if(same_rec[t]==i)
					{
					    find=TRUE;
					    break;
					}
				if(find==FALSE)//缺省值
					//same_num指相同的条件属性的个数
			    	same_rec[same_num++]=j;
			}
			find=FALSE;
			sum=0;
		}//浏览整个决策表如果有重复记录，采取的措施
	if(same_num>0)
	{
    	//为新表分配空间
		if((infoset=new int * [rec_num-same_num])==0)
			return 0;//分配新的决策表
		for(i=0;i<(rec_num-same_num);i++)
		{
			if((infoset[i]=new int[con_num+1])==0)
				return 0;
		}
		bool a;//判断标志
    	for(i=0;i<rec_num;i++)
		{
			a=false;
	    	for(j=0;j<same_num;j++)
	    		if(i==same_rec[j])//此时在same_rec中，
				{
					a=true;
					break;
				}
			if(!a)  //说明第i条记录不在same_rec中
			{
		        for(j=0;j<con_num+1;j++)
				{//new_rec_num初始值为0
					infoset[new_rec_num][j]=info[i][j];
				}
				new_rec_num++;
			}
		}
		for(i=0;i<rec_num;i++)
			delete []info[i];
    	delete []info;
		info=infoset;//重新初始化
		rec_num-=same_num;//决策表改变得到互不相同的记录的数目
	}
	delete []same_rec;
	if((IND_Attrb= new  int*[rec_num+1])==0)//为IND_Attrb分配内存
		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;
}
int CAttEntropyReduce:: Create_Array()//建立可辩识矩阵
{
	int i,j,k,l,n;         //循环变量
    int * att;            //条件属性组合
	int find=FALSE;
	int m=0,num=0;
	element=0;//可辩识(决策)矩阵中的元素个数
    if((att=new int[con_num+1])==0)
		return 0;//不成功返回为0,成功返回为1
    for(i=0;i<rec_num-1;i++)
		for(j=i+1;j<rec_num;j++)
			if(info[i][con_num]!=info[j][con_num])
			{//如果决策属性不相等  con_num为条件属性数
			//把不相等的条件属性记录下来,放在att中
			   for(k=0;k<con_num;k++)
				{
				   if(m>1) //m初始化为0  最多只记录两个不一致属性
					 break;
					if(info[i][k]!=info[j][k])
					{
						att[++m]=k;//k为不一致的属性位置
					}            
			    }
			    att[0]=m;//att[0]表示不一致属性数目 m＝1或2  
			    m=0;
			    for(l=0;l<element;l++)//在可辨识矩阵中寻找满足该不一致属性位置和大小的记录
				{//array 表示可辨识矩阵
				    if(array[l][0]==att[0])
					{//array[l][0]存储区别属性的数目
			 	       for(n=1;n<=att[0];n++)
						   if(array[l][n]==att[n])
                                 num++;//num初始化是0
				       if(num==att[0])
					   {
				            find=TRUE;//表示在可辨识矩阵中找到此差异属性
						   	break;//退出
					   }
					}
					num=0;
				}
			   	if(find==FALSE)
				{
					int ** newarray;
					//建立新表来存储决策表的样例的差异属性
					if((newarray=new int *[element+1])==0)
						return 0;
					for(l=0;l<element;l++)
					{
					    if((newarray[l]=new int[array[l][0]+1])==0)
							return 0;
						for(n=0;n<array[l][0]+1;n++)
							newarray[l][n]=array[l][n];//拷贝原表到暂时表中
					}
			    	if(element>0)
			       		delete []array;//删除原表
			    	array=newarray;//重新初始化
				
			    	if((array[element]=new int[att[0]+1])==0)//再分配一行
						return 0;
			       	for(l=0;l<att[0]+1;l++)
				       	array[element][l]=att[l];//写入新行中
				   	element++;
				}
				find=FALSE;
				num=0;
			}
    delete []att;
    return 1;
}

bool CAttEntropyReduce::Reduct_Table() //计算结果属性组合
{   
	double  H_DR_ALL;
	int count=0;
	int ncount=0;
	int i,j,k; //循环变量
 
   	redu_att_num=0;
	redu_num=0;
    red_dec_num=1;
   	if((attallreductset=new int[con_num+1])==0)
		return false;//全局熵的计算指针,con_num:条件属性数
    if((reductset=new int[con_num+1])==0)
		return false;//*计算核属性 con_num =7 rec_num=89 是
    if((attreductset= new int[con_num+1])==0)
		return false;///约简条件属性集
    if((decreductset= new int[2])==0)
		return false;//约简后的决策属性集
	if((resultset= new int[con_num+1])==0)
		return false;//约简结果
	if((attreductsetxu=new int[2])==0)
		return false;
    attreductsetxu[0]=1;//计算单个条件熵
	reductset[0]=0;
	attreductset[0]=0;
 //找出核属性/约简后的核属性数:redu_att_num=5 核属性数为 0 1 4 5 6 
    for(i=0;i<element;i++)//element:可辩识(决策)矩阵中的元素个数
		if(array[i][0]==1)
		{
			reductset[++redu_att_num]=array[i][1];//取第一个属性
			reductset[0]=redu_att_num;//核属性数目redu_att_num
		} 
  //找出非核属性//redu_att_num=2 核属性为 2 3
    for(k=0;k<con_num;k++)////条件属性数con_num
	{
   	  for(j=1;j<=redu_att_num;j++)
		{
			if(k!=reductset[j])
				   count++;//用count是否为核属性数目来判断是否是非核属性
		}
        if(count==redu_att_num)//此时属性k为非核属性
		{
			 attreductset[++redu_num]=k;//加入非核条件属性集
			 attreductset[0]=redu_num;//非核条件属性数目
		}
			count=0;//清零，为下次循环准备
	}
    //决策属性数的个数及属性号码
     decreductset[0]=1;	//约简后的决策属性集
	 decreductset[1]=con_num;
     //初始化约简结果的值（核属性）
	result_num=redu_att_num;//初始化为核属性数目
	resultset[0]=result_num;
	attreductset[0]=redu_num;//attreductset为约简结果集
	for(i=1;i<=result_num;i++)
	{  
		resultset[i]=reductset[i];
	}
    for(i=1;i<=con_num;i++)
	{  
		attallreductset[i]=i-1;//为了求entropy
	}
   ////////全集条件熵的计算
   //Entropy(int *q,int Q,int *p,int P)求条件熵H(q|p)
	H_DR_ALL=Entropy(decreductset,1, attallreductset,con_num);
    if(H_DR_ALL==-1)//计算失败