semiminione.cpp

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

// SemiMiniOne.cpp: implementation of the CSemiMiniOne class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "String.h"
#include "../RSet.h"
#include "fstream.h"
#include "SemiMiniOne.h"

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

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

CSemiMiniOne::CSemiMiniOne()
{

}

CSemiMiniOne::~CSemiMiniOne()
{

}

void CSemiMiniOne::ComputeCutCore(int** &X,int &N)
{
	int i,j;
	CutCore=new int* [iNonStrAttNum];
    for(i=0;i<iNonStrAttNum;i++)//属性i  
	{
		CutCore[i]=new int[MidCut[i][0]+1];
        for(j=1;j<=(int)MidCut[i][0];j++)//i属性断点个数
			CutCore[i][j]=0;
		CutCore[i][0]=MidCut[i][0];
	}
    for(i=0;i<iNonStrAttNum;i++)//属性i    
  	   for(j=1;j<=(int)MidCut[i][0];j++)//i属性断点个数
	   {//得到每个属性每个断点能够区分的实例对的个数
		   if(MidCut[i][j]!=0)//在每个等价类内部计算.不考虑等价类之间.
			   if(IsCore(X,X[0][0],MidCut[i][j],i))
				   CutCore[i][j]=1;
	   }
	  //根据断点核划分等价类
     for(int m=0;m<iNonStrAttNum;m++)//属性i    
  	   for(int n=1;n<=(int)MidCut[m][0];n++)//i属性断点个数
	   {
		   if(CutCore[m][n]==1)
		   {
              Cut[m][n]=MidCut[m][n];//得到断点 Cut初始化为0
			  MidCut[m][n]=0;//对应列清零
			  ++Cut[m][0];//断点个数加一
	//把被MidCut[m][n]划分为两部分的X分为两个等价类 不考虑决策,只考虑断点
              if(!(X=SplitSet(X,N,Cut[m][n],m)))//相当于去掉了该列为1的行
			  {
				  AfxMessageBox(" 分配内存出错!");
				  return;//返回等价类
			  }
		   }//end for(j)
	   }//end for(i)
     for(i=0;i<iNonStrAttNum;i++)//属性i  
		   delete[] CutCore[i];
     delete[] CutCore;
}

bool CSemiMiniOne::IsCore(int **X,int N,double midcut,int m)
//判断是否midcut为断点核，m为属性序号，返回1：是断点核；0：非断点核
{
	int i,j,k1,k2;
	bool tt=false;
	for(i=1;i<N-1;i++)
		for(j=i;j<N;j++)
		{
			tt=false;
			if(pNonStringTable[X[0][i]][iNonStrAttNum]!=pNonStringTable[X[0][j]][iNonStrAttNum])
			   if(pNonStringTable[X[0][i]][m]>midcut &&pNonStringTable[X[0][j]][m]<midcut
				   ||pNonStringTable[X[0][i]][m]<midcut &&pNonStringTable[X[0][j]][m]>midcut)
			   {
				  tt=false;
				  for(k1=0;k1<iNonStrAttNum;k1++)//属性i
				  {//对样列i，j判断是否该断点为唯一区分此样列对的断点
					  if(k1!=m)
						  for(k2=1;k2<=(int)MidCut[k1][0];k2++)//i属性断点个数
						  {
							 if( pNonStringTable[X[0][i]][k1]>MidCut[k1][k2] &&pNonStringTable[X[0][j]][k1]<MidCut[k1][k2]
				       || pNonStringTable[X[0][i]][k1]<MidCut[k1][k2] &&pNonStringTable[X[0][j]][k1]>MidCut[k1][k2])
							{ 
							   tt=true;
							   break;
							} 
						  }
					  else
						  for(k2=1;k2<=(int)MidCut[k1][0];k2++)//i属性断点个数
						  {
							 if(MidCut[k1][k2]!=midcut && pNonStringTable[X[0][i]][k1]>MidCut[k1][k2] &&pNonStringTable[X[0][j]][k1]<MidCut[k1][k2]
				       || MidCut[k1][k2]!=midcut && pNonStringTable[X[0][i]][k1]<MidCut[k1][k2] &&pNonStringTable[X[0][j]][k1]>MidCut[k1][k2])
							{ 
							   tt=true;
							   break;
							} 
						  }
				  }
				  if(!tt)
					  return true;
			   }
		}
		return false;
}

void CSemiMiniOne::GetMinCutNum(int **X,int N,int **Cut,int &tt1,int &tt2)
//得到几个具有相同区分样列对数目的断点中具有最小行断点数的断点，坐标为tt1，tt2
{
   int m,n,min,i,j,j1,minNum,k1,k2;
   bool tt=true;
   for(m=0;m<iNonStrAttNum;m++)//第m个属性
  	  for(n=1;n<=Wp[m][0];n++)//第n个断点值
		  if(Cut[m][n]==1)
		  {//Cut[m][n]说明m属性n断点此时都取得最大断点值
			  for(i=0;i<N;i++)
				  for(j=1;j<X[i][0];j++)//比较在同一个划分中的实例j，j1
					  for(j1=j+1;j1<=X[i][0];j1++)
						  if((pNonStringTable[X[i][j]][m]-MidCut[m][n])//属性值在断点两边
							  *(pNonStringTable[X[i][j1]][m]-MidCut[m][n])<0 
					&& pNonStringTable[X[i][j]][iNonStrAttNum]!=pNonStringTable[X[i][j1]][iNonStrAttNum])
						  {//说明此时该属性对的该列有1
							  min=0;
							  for(k1=0;k1<iNonStrAttNum;k1++)//属性k1
								  for(k2=1;k2<=(int)MidCut[k1][0];k2++)//k1属性断点个数k2
									  if(MidCut[k1][k2]!=0)
										  if((pNonStringTable[X[i][j]][k1]-MidCut[k1][k2])
							                 *(pNonStringTable[X[i][j1]][k1]-MidCut[k1][k2])<0)
			   		            		      min++;//统计此时的该行的断点数目
							   if(tt)
							   {
								   tt1=m;
								   tt2=n;//标示取得最小行的断点坐标
								   tt=false;
								   minNum=min;
							   }
							   else
							   {
								   if(minNum>min)
								   {
									   tt1=m;
									   tt2=n;
									   minNum=min;
								   }
							   } 
						  }
		  }   
}

void CSemiMiniOne::GetCut()//得到实际选取的断点集
{
  int **X=NULL; //X为等价类的集合
  int N=1; //N 为等价类的个数，初始时未划分等价类，等价类的个数为1
  int i,j;
  int m,n;
  int max=0;
  if(iNonStrAttNum==0)
	  return;
  //下面为初始化等价类,X的每一个元素的值代表的是实例
  X=new int	*[1];
  if((X[0]=new int [iRecordNum+1])==0)
  {
	  AfxMessageBox("分配内存失败!",MB_OK|MB_ICONSTOP);
	  return;
  }
  for(i=1;i<iRecordNum+1;i++)
	  X[0][i]=i-1;
  X[0][0]=iRecordNum;
  //X[0][0]代表的是此等价类中的元素的个数，初始时未划分等价类，
  //所以个数为信息表中的记录数。
  GetMidCut();//计算出所有的候选断点，并存入MidCut数组中
  ComputeCutCore(X,N);//计算断点核并消除之
  while(judge(X,N))   //判断X中的集合是否全部由决策相同的等价类组成,N为等价类的个数
  {   //N为X中的集合的个数 true:return 0，else return 1；
     for(i=0;i<iNonStrAttNum;i++)//属性i    
  	   for(j=1;j<=(int)MidCut[i][0];j++)//i属性断点个数
	   {//得到每个属性每个断点能够区分的实例对的个数
		   if(MidCut[i][j]!=0)//在每个等价类内部计算.不考虑等价类之间.
			   Wp[i][j]=ComputeWp(X,N,MidCut[i][j],i);//根据X，返回midcut断点所能区分
		   //出的实例对个数  Wp初始化为0
	   }
	   max=0;
	   for(m=0;m<iNonStrAttNum;m++)//列
		   for(n=1;n<=Wp[m][0];n++)
		   {//得到所有断点中区分样例对最多的数目,既算法中找出列中1个数最多的断点
			   if(Wp[m][n]>max)
			     max=Wp[m][n];
		   }
	  if(max==0)
		  break;
	  int flag=0;
	  int i_NumMax=0;
	  int **Cutt=new int *[iNonStrAttNum];
	  //初始化集合，以便表示哪几个断点同时取得最大值
      for(m=0;m<iNonStrAttNum;m++)//第m个属性
	  {
		  Cutt[m]=new int [Wp[m][0]+1];
		  for(n=1;n<=Wp[m][0];n++)//第n个断点值
			  Cutt[m][n]=0;
	  }
	  int tt1,tt2;
      for(m=0;m<iNonStrAttNum;m++)//第m个属性
	  	  for(n=1;n<=Wp[m][0];n++)//第n个断点值
			  if(Wp[m][n]==max)
			  {
				  i_NumMax++;
				  Cutt[m][n]=1;
				  if(i_NumMax==1)
				  {
					  tt1=m;
					  tt2=n;
				  }
			  }
	  if(i_NumMax>1)//得到最小行的断点
		  GetMinCutNum(X,N,Cutt,tt1,tt2);
      if(Cutt!=NULL)
	  {// 析构
	    for(i=0;i<iNonStrAttNum;i++)
		  delete []Cutt[i];
	    delete []Cutt;
	    Cutt=NULL;
	  }  

	  for(m=0;m<iNonStrAttNum;m++)//第m个属性
	  { 
		  for(n=1;n<=Wp[m][0];n++)//第n个断点值
		   {
			   if(tt1==m && tt2==n)//Wp[m][n]==max)//找到区分能力最大的断点值--列
			   {	     
				   Cut[m][n]=MidCut[m][n];//得到断点 Cut初始化为0
				   MidCut[m][n]=0;//对应列清零
				   ++Cut[m][0];//断点个数加一
	//把被MidCut[m][n]划分为两部分的X分为两个等价类 不考虑决策,只考虑断点
                   if(!(X=SplitSet(X,N,Cut[m][n],m)))//相当于去掉了该列为1的行
					   return;//返回等价类
				   flag=1;
				   break;
			   }
		   }//end for(n)
		   if(flag==1)
			   break;
		  }//end for(m)
	      for(m=0;m<iNonStrAttNum;m++)
		     for(n=1;n<=Wp[m][0];n++)
		        Wp[m][n]=0;
		  //置Wp为0，开始下一个找最大区分值的断点的循环
  }//end while(judge(X,N))
  if(X!=NULL)
  {
	  for(i=0;i<N;i++)
		  delete []X[i];
	  delete []X;
  }
}