reduct3.cpp

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

// Reduct3.cpp: implementation of the CReduct3 class.
//
//////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////
//  filename :reduct3.cpp
//	特征选择属性约简实现文件
//	作者：李鄂
//	2000/12
/////////////////////////////////////////////////////
#include "stdafx.h"
#include "fstream.h"
#include "Reduct3.h"
#include "math.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

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

CReduct3::CReduct3()
{
	InfoK=NULL;
	//	m_bAttr=NULL;
}

CReduct3::~CReduct3()
{
	if(InfoK!=NULL)
		delete []InfoK;
//	if(m_bAttr!=NULL)
//		delete []m_bAttr;
}

bool CReduct3::reduct()//算法主程序
{
	int orgK=getK();//条件属性和决策属性的相关程度KB(C,D)
	int attcount=m_nConAttrNum;
	//记录没有被约简的属性总个数,此时为全体条件属性集
    //int *nCMIndex=new int[attcount];
	//double *fCMRecord=new double[attcount];
	while(1)
	{
		InfoTable tab;
		for(int i=0;i<m_nConAttrNum;i++)
			if(m_bAttr[i]) //看有没有被约简
				tab.AddItem(i,getCM(i));//加入约简后的属性集合
		if(tab.GetCount()==1)
			break;//全部属性都约简了.退出
	//	tab.output();
	//	InfoCont* tabp=tab.getHead();
		m_bAttr[tab.getIndexMin()]=false;//约简具有最小上下文价值的属性
		int tem=getK();//计算REDU-{aj}集合的相关程度
		TRACE("相关程度: %d\n--------end----\n",tem);
		if(tem==orgK)//如果约简前后相关程度不变
		{	
			continue;//进行下一次循环.约简
		}
		else 
		{
			m_bAttr[tab.getIndexMin()]=true;//此时不约简,恢复
	 		break;
		}
	}
	return true;
}
	
bool CReduct3::InitTable(CString txtname)
{//初始化数据表,求得各属性的信息容量和决策分类
	int i=0;
	if(CTable::InitTable(txtname)==false)
		return false;
	try
	{
		InfoK=new InfoTable[m_nConAttrNum];//m_nConAttrNum 为条件属性个数
	}
	catch(CMemoryException * e)
	{
		::MessageBeep(MB_ICONHAND);
		AfxMessageBox("Out of the memory!",MB_OK|MB_ICONSTOP);
		e->Delete();
		return 0;
	} 

//	m_bAttr=new bool[m_nConAttrNum+1];
//	for(i=0;i<m_nConAttrNum+1;i++)
//		m_bAttr[i]=true;
	Classify(m_nConAttrNum,devset);//对决策分类
	InitInfoK();//求得各属性的信息容量用以填充infoK中的内容
#ifdef _DEBUG
	TRACE("\n相关程度: %d \n",getK());
	TRACE("上下文价值:\n");

	for(i=0;i<m_nConAttrNum;i++)
		//TRACE(" %f ",getCM(i));
		getCM(i);
	TRACE("----------end---------\n");
#endif
		return true;
}

void CReduct3::InitInfoK()  //求得各属性的信息容量
{//K(D|C=c)=++p(d|c)log(p(d|c)/p(d))
	TRACE("initialize infoK ...\n");
#ifdef _DEBUG
	TRACE(" devesion class\n");
	devset.outset(devset);
	TRACE("\n");
#endif

	for(int i=0;i<m_nConAttrNum;i++)	//对每个属性分别求
	{
		CSet<CSet<int> > attrset;		
		Classify(i,attrset);			//对属性i分类


#ifdef _DEBUG
		TRACE("attribute %d class\n",i);
		attrset.outset(attrset);
		TRACE("\n");
#endif
		setNode<CSet<int> > *p=attrset.getHead();
		//指向条件属性i分类的第一个子集合的临时变量
		while(p)//对条件类的每一个子集合
		{
			double info=0.0;
			double fz,fm;
			setNode<CSet<int> >*temp=devset.getHead();//决策类第一个子集合
			while(temp)//对决策类的每一个子集合
			{
				//fz=P(d|c)  条件概率 p(cd)=(temp->element*p->element).getCount()???
			    //(temp->element*p->element).getCount()交集个数条件分类和决策分类的交集
				fz=(temp->element*p->element).getCount()/(float)p->element.getCount();
				//fm=P(d)	  d概率
				fm=temp->element.getCount()/(float)m_nCount;
				temp=devset.getNext(temp);
				if(fz==0) continue;
				info+=fz*log(fz/fm);//对每个属性值得到的信息容量不同
			}
			TRACE(" %f\n",info);
			InfoK[i].AddItem(p->element.getID(),info);//插入 getID得到当前属性分类的对应的属性值
			p=attrset.getNext(p);//下一个属性分类
		}
	}
}

void CReduct3::Classify(int AttrIndex,CSet<CSet<int> >& set)
{
	int i;
	for(i=0;i<m_nCount;i++)
		CSet<int>::AddEleToSubSet(set,i,m_Record[i][AttrIndex]);
}

bool CReduct3::ClassifyAttr(CSet<CSet<int> >& set)
{ //用户控制比较的条件属性,用m_bAttr[]为true和false
	//
//根据所选择的条件属性对决策表进行分类，得到条件分类集合保存在set中
	//如果不存在条件属性了,就不能分类
	int j=0;
	for(int i=0;i<m_nConAttrNum;i++)
		if(!m_bAttr[i])
			j++;
	if(j==m_nConAttrNum)
		return false; 
	int& n=m_nConAttrNum;     //devision attribute column
	int *cls;
	try
	{
		cls=new int[m_nCount];
	}
	catch(CMemoryException * e)
	{
		::MessageBeep(MB_ICONHAND);
		AfxMessageBox("Out of the memory!",MB_OK|MB_ICONSTOP);
		e->Delete();
		return false;
	} 

	for(i=0;i<m_nCount;i++)
		cls[i]=-1;
	int count=0;

	for (i=0;i<m_nCount;i++)
	{//i表示样例序号
		bool flag=true;

		for(int k=0;k<i;k++)
		{
			if(CompObj(i,k))
			{//仅仅比较条件属性,全部相等返回为true,否则为false
				cls[i]=cls[k];
				flag=false;//已经加入分类,令为false
				break;
			}
		}
		if(flag) { cls[i]=count++;}
	}

	for(int k=0;k<m_nCount;k++)
	{
		CSet<int>::AddEleToSubSet(set,k,cls[k]);
	}
//	TRACE("\n");
//	TRACE("attribute classification:\n");
//	outset(set);
//	TRACE("\n");
	delete []cls;
	return true;
}


double CReduct3::getVD(int attr,int i,int j)	
{//获取值差(属性attr,样本i,j)
	double answer=0.0;					
	answer=InfoK[attr].GetInfo(m_Record[i][attr])-InfoK[attr].GetInfo(m_Record[j][attr]);
	if(answer<0) answer=-answer;//绝对值
	if(InfoK[attr].GetMaxGap()==0)
		return 0.0;
	answer=answer/(float)InfoK[attr].GetMaxGap();
	return answer;
}

double CReduct3::getWFD(int i,int j,int KK)
{ //获得样本i和j之间的加权特征差,KK为非Dl中的样本个数
	if(KK<=1) 
		return 0.0;
	int count=0;
	for(int k=0;k<m_nConAttrNum;k++)
		if(m_bAttr[k] && m_Record[i][k]!=m_Record[j][k])
			count++;
	if(count==0)
		return 0.0;
	
	if((float)count<=log((float)KK)/log(2.0) )//见书142 kK为N
		return 1/((float)count*(float)count);
	else return 0.0;
}

double CReduct3::getCM(int k)		// 属性k的上下文价值
{
	TRACE("get CM %d ...\t",k);
	double answer=0.0;
	setNode<CSet<int> >* devp=devset.getHead();//决策类的第一个分类
	while(devp)//对所有的决策类进行
	{
		setNode<int> *subdevp=devp->element.getHead();//此分类的第一个元素
		while(subdevp)//在一个决策类中,累加,累加 WFDij*VD(Cki,Ckj)
		{
			int KK= m_nCount - (devp->element.getCount());
						//计算Card(-Dl),准备传递给getWFD()
//			TRACE("传递给getWFD的K: %d  ",KK);
			for(int i=0;i<m_nCount;i++)
			{
				if(devp->element.HasMember(i))
					continue;//保证了i不属于此时的决策分类
//				TRACE( "in getCM: i:%d wfd:%f vc:%f \n",i,getWFD(subdevp->element,i,KK),getVD(k,subdevp->element,i));
				answer+=getWFD(subdevp->element,i,KK)*getVD(k,subdevp->element,i);
                //此时subdevp->element样例和i样例的WFD*(属性k的subdevp->element,i样例的值查)
			}
			subdevp=devp->element.getNext(subdevp);
		}
		devp=devset.getNext(devp);
	}
	TRACE(" %f \n",answer);
	return answer;			
}

int CReduct3::getK(void)//计算相关程度(噪音程度为0)
 //计算条件属性和决策属性的相关程度，只计算了正域的部分占全域的比例
{//定义见书37页  如果所有属性都想约简,则返回为-1
	CSet<CSet<int> > attrset;
	if(!ClassifyAttr(attrset))//对用户选择的条件属性分类
		return -1;
#ifdef _DEBUG
	TRACE("按属性集分类:\n");
	attrset.outset(attrset);
#endif
	setNode<CSet<int> > *devp=devset.getHead();//决策类
	setNode<CSet<int> > *attrp=attrset.getHead();//属性分类
	int fz=0;			//统计正域元素的个数
	while(attrp)//对每一个条件分类
	{
		bool flag=true;
		devp=devset.getHead();
		while(devp)//对每一个决策分类
		{
//换成只求正域部分,用下面的代 码
//	/*
			if(attrp->element.BelongTo(devp->element))
			{//属性分类包含于决策分类,即正域
				fz+=attrp->element.getCount();//包含正域元素个数
				break;
			}
			devp=devset.getNext(devp);//下一个决策类
		}
//	*/		
	/*
			int count=(attrp->element*devp->element).getCount();
			if(count>0 && count<attrp->element.getCount() )
							//边界部分
			{
				devp=devset.getNext(devp);
				continue;
			}
			else
			{
				flag=false;
				break;
			}
//	*/	
//只求正域,下句删去
//		if(flag) fz+=attrp->element.getCount();
		attrp=attrset.getNext(attrp);
	}
	return fz;//返回正域元素个数 m_nCount为样本个数
}


#ifdef _DEBUG
void CReduct3::output()
{
//	for(int i=0;i<m_nConAttrNum;i++)
//	{
//		InfoK[i].output();
//	}
/*	TRACE("2,3,5 VD %f \n",getVD(2,3,5));
	TRACE("\n\n reduction finished it's ");
	for(int i=0;i<m_nConAttrNum;i++)
		if(m_bAttr[i])  TRACE("%d ",i);
	CSet<CSet<int> > set;
	ClassifyAttr(set);
	outset(set);
	TRACE("\nK :%d \n",getK());
	*/
}
#endif
bool CReduct3::WriteFile(CString name)
{
	deleteDup();
	return CTable::WriteFile(name);
}