📄 semimini.cpp
字号:
// SemiMiniDoc4.cpp: implementation of the CSemiMiniDoc class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "String.h"
#include "../RSet.h"
#include "fstream.h"
#include "SemiMini.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
//////////////////////////////////////////////////////////////////////
// iAttNumstruction/Destruction
//////////////////////////////////////////////////////////////////////
CSemiMini::CSemiMini()
{
Cut=NULL;
NewTable=NULL;
MidCut=NULL;
Wp=NULL;
pAttName=NULL;
pDataType=NULL;
pStringTable=NULL;
pStringTableResult=NULL;
pStrResult=NULL;
pNonStringTable=NULL;
strCuts=NULL;
}
CSemiMini::~CSemiMini()
{
int i;
if(Cut!=NULL)
{
for(i=0;i<iNonStrAttNum;i++)
delete []Cut[i];
delete []Cut;
Cut=NULL;
}
if(NewTable!=NULL)
{
for(i=0;i<iRecordNum;i++)
delete []NewTable[i];
delete []NewTable;
NewTable=NULL;
}
if(MidCut!=NULL)
{
for(i=0;i<iNonStrAttNum;i++)
delete []MidCut[i];
delete []MidCut;
MidCut=NULL;
}
if(Wp!=NULL)
{
for(i=0;i<iNonStrAttNum;i++)
delete []Wp[i];
delete []Wp;
Wp=NULL;
}
if(pAttName)
{
for(i=0;i<iAttNum+1;i++)
delete []pAttName[i];
delete[] pAttName;
pAttName=NULL;
}
if(pDataType)
{
for(i=0;i<iAttNum+1;i++)
delete []pDataType[i];
delete[] pDataType;
pDataType=NULL;
}
if(pStringTable!=NULL)
{
for(i=0;i<iRecordNum;i++)
{
for(int j=0;j<iStrAttNum;j++)
delete[] pStringTable[i][j];
delete[] pStringTable[i];
}
delete[] pStringTable;
}
if(pStringTableResult!=NULL){
for(i=0;i<iRecordNum;i++)
delete[] pStringTableResult[i];
delete[] pStringTableResult;
}
if(pStrResult){
for(i=0;i<iRecordNum;i++){
for(int j=0;j<iStrAttNum;j++)
delete[] pStrResult[i][j];
delete[] pStrResult[i];
}
delete[] pStrResult;
}
if(pNonStringTable){
for(i=0;i<iRecordNum;i++)
delete[] pNonStringTable[i];
delete[] pNonStringTable;
}
}
BOOL CSemiMini::OnSemiMinidis()
{//具体实现离散化
double duration;//计算约简时间的大小
CString str;
clock_t finish ,start;
start = clock();
GetCut();//得到实际选取的断点集
GetNewTable();// 根据所选取的断点，计算出
//离散化后新的决策表并存入NewTable中
if(iStrAttNum!=0)
doString();
finish = clock();
duration = (double)(finish - start) / CLOCKS_PER_SEC;
str.Format (" 约简运行时间:%f 秒",duration);
// AfxMessageBox(str);
return TRUE;
}
void CSemiMini::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中
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断点所能区分
//出的实例对个数
}
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;
for(m=0;m<iNonStrAttNum;m++)//第m个属性
{
for(n=1;n<=Wp[m][0];n++)//第n个断点值
{
if(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;
}
}
void CSemiMini::GetNewTable()
{ // 根据所选取的断点，计算出集散化后新的决策表并存入NewTable中
int i,j,k;
int m;
Cut=GetLastCut();//根据选出的断点集，求得最终的断点集
if((NewTable=new int *[iRecordNum])==0)
{
AfxMessageBox("Out of Memory!");
return ;
}
for(i=0;i<iRecordNum;i++)
{//每个样例
if((NewTable[i]=new int[iNonStrAttNum+1])==0)
{
AfxMessageBox("Out of Memory!");
return;
}
for(j=0;j<iNonStrAttNum;j++)
{//对每个属性
if((int)Cut[j][0]!=0)
{
m=0;
for(k=0;k<(int)Cut[j][0];k++)
{
if(pNonStringTable[i][j]<Cut[j][k+1])
{//得到i样例j属性离散化后的值
NewTable[i][j]=m;
break;
}
m++;
}
if(pNonStringTable[i][j]>=Cut[j][(int)Cut[j][0]])//大于等于最大的那个断点值
NewTable[i][j]=(int)Cut[j][0];
}
if((int)Cut[j][0]==0)
NewTable[i][j]=0;
}//end for
NewTable[i][iNonStrAttNum]=(int)pNonStringTable[i][iNonStrAttNum];//决策值
}
}
void CSemiMini::GetMidCut()
{//计算出所有的候选断点，并存入MidCut中
int i,j,k;
int num=0;
int num1=0;
int flag=0;
if((MidCut=new double*[iNonStrAttNum])==0)
{
AfxMessageBox("Out of Memory!");
return ;
}
if((Cut=new double*[iNonStrAttNum])==0)
{ //实际所取的断点的集合
AfxMessageBox("Out of Memory!");
return ;
}
if((Wp=new int*[iNonStrAttNum])==0)
{
AfxMessageBox("Out of Memory!");
return;
}
//MidCut为侯选的断点集的集合
//MidCut[i][0]为第i个属性候选断点集的个数
//MidCut[i][j]为第i个属性的第j个后选断点
//MidCut[i]是经过排序的，由小到大排列的断点集的集合
//Wp记录每个断点区分实例值
//Wp[i][j]记录第i个属性的第j个候选断点的区分实例对的数目值,
//和MidCut[i][j]是对应的,每一次循环寻找最大的Wp[i][j]值,
//然后把相应的Cut[i][j]置为MidCut[i][j]的值(断点值),再把相应的MidCut[i][j]置为0;
//下一次循环就不考虑已经选取的MidCut[i][j];
//Mid[i]存储属性i的不同属性值
double **Mid=NULL;
if((Mid=new double*[iNonStrAttNum])==0)
{
AfxMessageBox("Out of Memory!");
return ;
}
for(i=0;i<iNonStrAttNum;i++)
{
Mid[i]=NULL;
if((Mid[i]=new double[iRecordNum+1])==0)
{
AfxMessageBox("Out of Memory!");
return ;
}
}
for(i=0;i<iNonStrAttNum;i++)//i为属性
{
num=0;
num1=0;
flag=0;
Mid[i][++num]=pNonStringTable[0][i];
//num 初始化为0 得到第一行的属性i的值
for(j=1;j<iRecordNum;j++)
{//对后面的记录 对属性i完成不重复属性值的收集
for(k=1;k<=num;k++)
{
if(pNonStringTable[j][i]==Mid[i][k])
{//看是否已有属性值重复
flag=1;
break;
}
}
if(flag==0)
{//不重复,加入
Mid[i][++num]=pNonStringTable[j][i];
}
flag=0;
}
Mid[i][0]=(double)num;//不同属性值个数
MidCut[i]=NULL;
if((MidCut[i]=new double[num])==0)
{//分配断点集
AfxMessageBox("Out of Memory!");
return ;
}
Cut[i]=NULL;
if((Cut[i]=new double[num])==0)
{
AfxMessageBox("Out of Memory!");
return ;
}
Wp[i]=NULL;
if((Wp[i]=new int[num])==0)
{
AfxMessageBox("Out of Memory!");
return ;
}
//指针Wp和指针MidCut结构相同,
for(j=0;j<num;j++)
{//初始化Cut和Wp
Cut[i][j]=0;
Wp[i][j]=0;
}
//开始时把Wp[i][j]和Cut[i][j]的值置0
MidCut[i][0]=Mid[i][0]-1;//断点个数为不同属性值个数减一
Wp[i][0]=num-1;
//Wp[i][0]的值是第i个属性的候选断点的个数,
//但Cut[i][0]的值却由程序选取的断点决定.
//每选取第i个属性的一个断点,则Cut[i][0]加1
SelectSort(Mid[i]);// 对出现的属性值进行排序
for(j=1;j<num;j++)//得到断点值,从小到大排列
MidCut[i][++num1]=(Mid[i][j]+Mid[i][j+1])/2;
}
for(i=0;i<iNonStrAttNum;i++)
delete []Mid[i];
delete []Mid;
}
int CSemiMini::judge(int **X, int N)
//判断X中的集合是否全部由决策相同的等价类组成
//N为X中的集合的个数
//如果全部由相同的等价类组成，return 0，else return 1
{
if(X==NULL)
return 0;
int i,j;
int flag=0;
for(i=0;i<N;i++)
{
for(j=1;j<X[i][0];j++)
{
if(pNonStringTable[X[i][j]][iNonStrAttNum]!=pNonStringTable[X[i][j+1]][iNonStrAttNum])
{//相邻等价类中相邻记录比较决策,不一致时返回1;全部一致是返回0
flag=1;
break;
}
}
if(flag==1)
break;
}
return flag;
}
int CSemiMini::ComputeWp(int **X, int N, double midcut, int m)
{//X为等价类的集合，N为等价类的个数，midcut为候选断点，
//m为指明后选的断点是第几个条件属性的断点
//根据等价类X，计算并返回断点midcut所能区分出的实例对的个数 失败:return -1;
int i,i1,j1;
int num=0;//小于此断点值的实例个数
int num1=0;//大于此断点值的实例个数
int DiscernValue=0;
int mid=0;
for(i=0;i<N;i++)
{ //对每个定价类
for(i1=1;i1<=X[i][0];i1++)
{//统计此集合中小于大于断点的实例个数
if(pNonStringTable[X[i][i1]][m]<midcut)
++num;//小于此断点值的实例个数
if(pNonStringTable[X[i][i1]][m]>midcut)
++num1;//大于此断点值的实例个数
}
if((num>0)&&(num1>0))
{//说明存在此断点区分的实例对
double *DeciSet=NULL;
DeciSet=GetDeciSet();//返回一个数组，记录了决策属性的所有出现的值
int **Set=NULL;
Set=new int*[2];
for(i1=0;i1<2;i1++)
{
Set[i1]=NULL;
if((Set[i1]=new int[(int)DeciSet[0]])==0)
{
AfxMessageBox("内存分配失败!");
return -1;
}
}
//Set[0][i-1]为小于断点集的实例对应的DeciSet[i](为决策值)的个数
//Set[1][i-1]为大于断点集的实例对应的DeciSet[i](为决策值)的个数
//DeciSet[0]为决策值的种类个数,
//DeciSet[i]为对应的决策值.
for(i1=0;i1<2;i1++)
for(j1=0;j1<(int)DeciSet[0];j1++)
Set[i1][j1]=0;//初始化为0,后面要用
int **Mid=NULL;
Mid=new int*[2];
for(i1=0;i1<2;i1++)
{
Mid[i1]=NULL;
if((Mid[i1]=new int[X[i][0]])==0)
{
AfxMessageBox("内存分配失败!");
return -1;
}
}
//因为此集合被断点分割为两部分,一部分为大于断点值实例
//另一部分为小于断点值的实例
//X[i][0]为要被划分的集合的原始个数
//Mid[j]为划分后的集合,被分为两部分
num=num1=0;
for(i1=1;i1<=X[i][0];i1++)
{//根据断点将集合划分为两部分
if(pNonStringTable[X[i][i1]][m]<midcut)//不可能等于,因为断点取得是中值
//把小于此断点值的实例和大于此断点值的实例分开
Mid[0][++num]=X[i][i1];//小于此断点值的实例
if(pNonStringTable[X[i][i1]][m]>midcut)
Mid[1][++num1]=X[i][i1];//大于此断点值的实例
}
Mid[0][0]=num;//num为小于断点值的实例的个数
Mid[1][0]=num1;//num1为大于断点值的实例的个数
for(i1=1;i1<=num;i1++)
for(j1=1;j1<=DeciSet[0];j1++)
{//统计小于断点值的实例重复决策值个数
if(pNonStringTable[Mid[0][i1]][iNonStrAttNum]==DeciSet[j1])
{
++Set[0][j1-1];//自加一. 统计DeciSet[j1]决策出现的次数
break;
}
}
for(i1=1;i1<=num1;i1++)
for(j1=1;j1<=DeciSet[0];j1++)
{//统计大于断点值的实例重复决策值个数
if(pNonStringTable[Mid[1][i1]][iNonStrAttNum]==DeciSet[j1])
{
++Set[1][j1-1];
break;
}
}
for(i1=0;i1<(int)DeciSet[0];i1++)
for(j1=0;j1<(int)DeciSet[0];j1++)
{ //统计要去除的样例对mid
if(i1==j1)//决策相等
{
mid=mid+Set[0][i1]*Set[1][j1];//其中如Set不为实际决策,则为0
break;//mid统计断点能区分的实例对的个数.Set[0][i1]*Set[1][j1]为小于断点的实例
//数目*大于断点的实例数目=>实例对的数目
}
}
DiscernValue=DiscernValue+num*num1-mid;
try{
for(i1=0;i1<2;i1++)
delete []Set[i1];
delete []Set;
for(i1=0;i1<2;i1++)
delete []Mid[i1];
if(Mid!=NULL)
delete []Mid;
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -