📄 indval.cpp
字号:
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "../rset.h"
#include "indval.h"
#include "stdio.h"
#include "stdlib.h"//function atoi();
#include "string.h"
#define MAX 1000
/////////////////////
// indattred class //
/////////////////////
IndValRed::IndValRed()
{
pFileName=NULL; //待处理的文件名
pIntTable=NULL; //原始表,为int类型，中间对象，转化为info表,最后处理用到
pInfo=NULL; //原始表,已转化为int,处理中主要对象，约简对象
cStyle=NULL; //数据集基本类型
pAttName=NULL; //属性名称（安列分）
pDataType=NULL; //数据类型（安列分）
struWCutRecord=NULL; //断点链表
pUindD=NULL; //u|d
pRules=NULL; //规则集
pSameRec=NULL; //每条规则能覆盖的记录数
pNoValCon=NULL; //被约掉的条件属性
max1=0;
}
IndValRed::~IndValRed()
{
FreeContent();
}
////////////////////////////////////////////////////////
//the implementation of the public methods
/////////////////////////////////////////////////////////
bool IndValRed::GetInfo(char* FileName)//get the privilege pInformation from the file given.
{//success:return true; else return false
FILE* fp;
//return when fail to read the file
if((fp = fopen(FileName,"r")) == NULL)
{
AfxMessageBox("打开文件失败!");
return false;
}
if((cStyle= new char[MAX])==0)
return false;
fscanf(fp,"Style:%s\n",cStyle);
fscanf(fp,"Stage:%d\n",&iStage);
//return if not the result of the attribute reduce
/* if ((stricmp(cStyle,"train")!=0)||(iStage!=3))
{
printf("The unfit data set!\n");
return false;
}
*/
fscanf(fp,"Condition attributes number:%d\n",&iConNum);
fscanf(fp,"The Number of Condition attributes deleted: %d\n",&atbcount);
fscanf(fp,"The position of Condition attributes deleted:");
if(atbcount!=0)
{
if((atb=new int[atbcount])==0)
return false;
for(int n=0;n<atbcount;n++)
fscanf(fp," %d\n",&atb[n]);
}
// char *s;
fscanf(fp,"\n");
fscanf(fp,"Records number:%d\n",&iRecNum);
ipriRecNum=iRecNum;//读入样本数目
SetAttName(fp,iConNum+1);
SetDataType(fp,iConNum+1);
SetIntegerTable(fp,iConNum+1,iRecNum);//fill the integertable
SetCutResult(fp);
fclose(fp);
return true;
}
bool IndValRed::InitTable()//初始化决策表,得到int类型的表
{ //从文件中得到数据，得到int型表
int i,j;
if((pInfo=new int *[iRecNum])==0)
{
AfxMessageBox("内存分配错误!");
return false;
}
for (i=0;i<iRecNum;i++)
if((pInfo[i]=new int [iConNum+1])==0)
{
AfxMessageBox("内存分配错误!");
return false;
}
for (i=0;i<iRecNum;i++)
{
for (j=0;j<iConNum+1;j++)
{
pInfo[i][j] = pIntTable[i][j];
}
}
return true;
}
int IndValRed::DelOverlap()//删除重复的记录 生成新的表
{//success:return 1 ;else 0
int i,j,k,t; //循环变量
int ** pInfoset; //删除重复记录后的信息表
int new_iRecNum=0; //新信息表中的记录数
int sum=0; //统计属性值相同的个数
bool find=false;
int * same_rec;
if((same_rec=new int[iRecNum])==0)
return 0;
int same_num=0;
//把重复记录编号存在same_rec数组中,same_num中为重复记录数目
for(i=0;i<iRecNum-1;i++)
for(j=i+1;j<iRecNum;j++)
{
//比较两条记录是否完全相等
for(k=0;k<iConNum+1;k++)
if(pInfo[i][k]==pInfo[j][k])
sum++;
else
break;
//表示完全相等
if(sum==(iConNum+1))
{
for(t=0;t<same_num;t++)
//如果记录中有i,说明第j条记录已存在same_rec中了
if(same_rec[t]==i)
{
find=true;
break;
}
if(find==false)
same_rec[same_num++]=j;
}
find=false;
sum=0;
}
//如果有重复记录
if(same_num>0)
{ //为新表分配空间
if((pInfoset=new int * [iRecNum-same_num])==0)
return 0;
for(i=0;i<(iRecNum-same_num);i++)
{
if((pInfoset[i]=new int[iConNum+1])==0)
return 0;
}
for(i=0;i<iRecNum;i++)
{
for(j=0;j<same_num;j++)
if(i==same_rec[j])//i为重复样例
break;
else
sum++;
if(sum==same_num)
{ //说明第i条记录不在same_rec中
for(j=0;j<iConNum+1;j++)
{
pInfoset[new_iRecNum][j]=pInfo[i][j];//new_iRecNum初始为0
}
new_iRecNum++;
}//拷贝到新表
sum=0;
}
for(i=0;i<iRecNum;i++)
delete []pInfo[i];
if(pInfo) delete []pInfo;
pInfo=pInfoset;//得到pInfoset的一个拷贝:pInfo
iRecNum-=same_num;//为新的记录数目,用来推到规则用
}
delete []same_rec;
return 1;
}
bool IndValRed::SetIntegerTable(FILE* fp,int column, int row)
{//success:return true; else false
int i,j;
char* string;
if((string=new char[MAX])==0)
return false;
if((pIntTable = new int*[row])==0)
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;
}
bool IndValRed::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;
if(fscanf(fp,"%s",temp) == -1)
{
delete[] temp;
return false;
}
if(strcmp(temp,"[Cuts]") != 0)
{
delete[] temp;
return false;
}
// bCuts = true;
while(fscanf(fp,"%d\n",&iColumn) != -1)
{//iColumn为列数
fscanf(fp,"%d",&iCuts);//iCuts为断点数
pEnd = new WCutRecord;
if((pEnd->cpCut=new char*[iCuts])==0)
return false;
for(int i=0;i<iCuts;i++)
{
if((pEnd->cpCut[i] = new char[MAX])==0)
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;
pHead = pEnd;
}//end if
else
{
pHead->next = pEnd;
pHead = pEnd;//移到下一个断点结构
}//end else
}//end while
delete[] temp;
return true;
}
bool IndValRed::SetAttName(FILE* fp, int count)
{
int i;
if((pAttName = new char*[count])==0)
return false;
for(i=0;i < count;i++)
{
if((pAttName[i]=new char[MAX])==0)
return false;
}//end for
for(i=0;i < count;i++)
fscanf(fp,"%s",pAttName[i]);
return true;
}
bool IndValRed::SetDataType(FILE *fp, int count)
{
int i;
pDataType = new char*[count];
for(i = 0;i < count;i++)
{
if((pDataType[i]=new char[MAX])==0)
return false;
}//end for
for(i = 0;i < count;i++)
fscanf(fp,"%s",pDataType[i]);
return true;
}
bool IndValRed::SaveFile(char *pFileName)
{
int i,j;
FILE* fp;
if((fp = fopen(pFileName,"w")) == NULL)
{
AfxMessageBox("不能打开写文件!\n");
return false;
}//end if
cStyle="rule";
fprintf(fp,"Style:%s\n",cStyle);
fprintf(fp,"Stage:%d\n",0);
fprintf(fp,"Condition attributes number:%d\n",iConNum);
fprintf(fp,"The Number of Condition attributes deleted: %d\n",atbcount);
fprintf(fp,"The position of Condition attributes deleted:");
for(i=0;i<atbcount;i++)
fprintf(fp," %d ",atb[i]);
fprintf(fp,"\n");
fprintf(fp,"Rules number:%d\n",iRulesNum);
fprintf(fp,"Blocks number:%d\n",0);
for(i = 0;i < iConNum+1;i++)
fprintf(fp,"%s ",pAttName[i]);
fprintf(fp,"\n");
for(i = 0;i < iConNum+1;i++)
fprintf(fp,"%s ",pDataType[i]);
fprintf(fp,"\n");
struct WCutRecord* pHead = NULL;
for(i=0;i<iRulesNum;i++)
{
for(j=0;j<iConNum;j++)
{
if(pRules[i][j]==-1)//约简该属性值
fprintf(fp,"- ");
else
{
pHead=struWCutRecord;
while((pHead!=NULL)&&(pHead->iColumn!=j))
pHead=pHead->next;
if((pHead!=NULL)&&(pHead->iCuts>pRules[i][j]))
{
fprintf(fp,"%s ",pHead->cpCut[pRules[i][j]]);
}
else
fprintf(fp,"%d ",pRules[i][j]);
}
}
fprintf(fp,"%d ",pRules[i][iConNum]);//决策属性单独处理
fprintf(fp,"%.2f ",1.0);
fprintf(fp,"%d ",pSameRec[i]);
fprintf(fp,"%d\n",pSameRec[i]);
}
fclose(fp);
return true;
}
//首先求U|ind(xset),再求U|D,然后求Pos(X)D
bool IndValRed::PosXD(int XNum,int* XSet,PosD* PosXD)
{ //求U|D,结果放在iClassNumD,UindD 中
int iClassNumD=0;
int DNum=1;
int *DSet=new int[1];
DSet[0]=iConNum;
int **UindD;
if((UindD=new int*[iRecNum])==0)
{
AfxMessageBox("内存分配错误!");
return false;
}
for(int j=0;j<iRecNum;j++)
if((UindD[j]=new int[iRecNum+1])==0)
{
AfxMessageBox("内存分配错误!");
return false;
}
//call UindX()
UindX(DNum,DSet,iClassNumD,UindD);
delete []DSet;
//求U|ind(X),结果放在iClassNumX,UindX中
int iClassNumX=0;
int **pUindX;
if((pUindX=new int*[iRecNum])==0)
{
AfxMessageBox("内存分配错误!");
return false;
}
for(j=0;j<iRecNum;j++)
if((pUindX[j]=new int[iRecNum])==0)
{
AfxMessageBox("内存分配错误!");
return false;
}
//call UindX()
UindX(XNum,XSet,iClassNumX,pUindX);
//求pos(x)D
//就是包含在u|d中的uindX的并集
//简化算法，如果uindx的某一类的元素全在U\D的同一类中，那么就是了。
for(int i=0;i<iClassNumX;i++)//对uindx中的每一类
{
int flag=1;//全部元素都是同一类的sign
int tempsame=-1;//统一的类
int sameclass=-1;//临时的类
for(int k=0;k<pUindX[i][0];k++)//每一类中的元素，与uindd中的每一类比较
{
for(int j=0;j<iClassNumD;j++)
{
int oneflag=0;
for(int l=0;l<UindD[j][0];l++)
{
if(pUindX[i][k+1]==UindD[j][l+1])
{//修改
oneflag=1;
break;
}
}
if(oneflag==1)
{
sameclass=j;//找到条件子类中的一个元素属于决策集合的类
break;
}
}
if(tempsame<0)
{
tempsame=sameclass;
}
else
{
if(tempsame!=sameclass)
{//属于不同的决策类
flag=0;
break;
}
}
}//end for
if(flag==1)//同类，加入到PosXD中
{
for(int j=0;j<pUindX[i][0];j++)
PosXD->PosSet[PosXD->PosNum+j]=pUindX[i][j+1];
PosXD->PosNum+=pUindX[i][0];
}
}//end for
for(j=0;j<iRecNum;j++)
{ delete []UindD[j];
delete []pUindX[j];
}
delete []pUindX;
delete []UindD;
return true;
}
//求Unid(X)
void IndValRed::UindX(int XNum,int* XSet,int& iClassNumX,int**&pUindX)
{
iClassNumX=0;
//将第一条记录归入第一类
pUindX[0][0]=1;
pUindX[0][1]=0;
iClassNumX++;//iClassNumX为1
//比较其他的类，对于剩下的每一条记录，如果相等归入同一类，不同就开辟新类
for(int i=1;i<iRecNum;i++)
{//第i个记录
int flag=0;
int sameClass=0;
for(int j=0;j<iClassNumX;j++)//比较每一个已经存在的类
{
int oneflag=1;
for(int k=0;k<XNum;k++)//对所有属性
{//XSet[k]表示属性位置
if(pInfo[i][XSet[k]]!=pInfo[pUindX[j][1]][XSet[k]])
{//最开始时后面的记录和第一条记录属性比较
oneflag=0;
break;//有一个属性值不等，说明不属于一类
}
}
if(oneflag==1)//属于一类
{
flag=1;
sameClass=j;//此时记录i属于类j
break;
}
}
if(flag==1)//同类
{
pUindX[sameClass][0]++;//类中的元素数目加一
pUindX[sameClass][pUindX[sameClass][0]]=i;//增加一个元素
}
else//开辟一个新类
{
pUindX[iClassNumX][0]=1;
pUindX[iClassNumX][1]=i;
iClassNumX++;
}
}//endof for
}
//求negcoreCD的Xnum阶幂集，用递归算法
//首先求一阶的，再求2阶的，再求3阶，慢慢地递归调用而已
//当XNum降到2阶时，DemNum也恰好增大到最初XNum的值
//注意：求得的结果不是属性在原集合中的排列位置，其值是相对negCoreCD而言
bool IndValRed::DemSet(int XNum,int DemNum,int& iDemSetNum,
int XCoreNum,int*** pDemSet)
{//XNum：阶数 //结果放在DemSet,iDemSetNum中 // DemNum最小为2
////pDemSet:pCoreCD的幂集 iDemSetNum:pCoreCD幂集的元素个数
/*
二阶时 tempDemSetNum最终为：1/2*CoreNum*(CoreNum-1)
i=0: tempDemSet[0][0]=0 [0][1]=1 //一个二阶幂
[1][0]=0 [1][1]=2//一个二阶幂
[2][0]=0 [2][1]=3
i=1: [XCoreNum-1][0]=1 [..][1]=2
[..+1][0]=1 [..+1][1]=3
[..+2][0]=1 [..+2][1]=4
...
*/
if(XNum<2)//只计算高于2阶的幂子集
return true;
int tempDemSetNum=0;
int** tempDemSet;//存储临时的DemNum阶幂集
if((tempDemSet=new int*[iDemSetNum*XCoreNum])==0)
return false;
for(int i=0;i<iDemSetNum*XCoreNum;i++)
if((tempDemSet[i]=new int[iConNum])==0)
return false;
for(i=0;i<iDemSetNum;i++)
{
for(int j=(*pDemSet)[i][DemNum-2]+1;j<XCoreNum;j++)
{
for(int k=0;k<DemNum-1;k++)
tempDemSet[tempDemSetNum][k]=(*pDemSet)[i][k];
tempDemSet[tempDemSetNum++][DemNum-1]=j;
}
}
// for(i=0;i<iDemSetNum*XCoreNum;i++)
// delete [](*pDemSet)[i];
// delete [](*pDemSet);
for(i=0;i<tempDemSetNum;i++)
for(int j=0;j<DemNum;j++)
(*pDemSet)[i][j]=tempDemSet[i][j];
iDemSetNum=tempDemSetNum;
//递归调用
if(!DemSet(XNum-1,DemNum+1,iDemSetNum,XCoreNum,pDemSet))
return false;
return true;
}
/*
//求CoreA的Xnum阶幂集
//首先求一节的，再求2节的，慢慢地递归调用而已。
//结果放在pDemSet,iDemSetNum中。
//注意：求得的结果不是属性在原集合中的排列位置，其值是相对
//CoreA而已的。
void IndValRed::DemSet(int XNum,int DemNum,int& iDemSetNum,int XCoreNum,int*** pDemSet)
{
if(XNum<2)
return;
int tempDemSetNum=0;
int** tempDemSet=new int*[MAX];
for(int i=0;i<MAX;i++)
tempDemSet[i]=new int[iConNum];
for(i=0;i<iDemSetNum;i++)
{
for(int j=(*pDemSet)[i][DemNum-2]+1;j<XCoreNum;j++)
{
for(int k=0;k<DemNum-1;k++)
tempDemSet[tempDemSetNum][k]=(*pDemSet)[i][k];
// tempDemSet[tempDemSetNum]=DemSet[i];
tempDemSet[tempDemSetNum++][DemNum-1]=j;
}
}
for(i=0;i<MAX;i++)
delete [](*pDemSet)[i];
delete [](*pDemSet);
(*pDemSet)=tempDemSet;
iDemSetNum=tempDemSetNum;
//递归调用
DemSet(XNum-1,DemNum+1,iDemSetNum,XCoreNum,pDemSet);
}
*/
void IndValRed::FreeContent()
{
for(int i=0;i<ipriRecNum;i++)
delete []pIntTable[i];
delete []pIntTable;
for (i=0;i<iRecNum;i++)
delete []pInfo[i];
delete []pInfo;
for(i=0;i<iRecNum;i++)
delete []pUindD[i];
delete []pUindD;
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -