liedynamicreduct.cpp

来自「某个实验事编写粗糙集智能信息处理的程序」· C++ 代码 · 共 281 行

// LieDynamicReduct.cpp : implementation file
//

#include "stdafx.h"
#include "LieDynamicReduct.h"
#include <list>
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
#include <ctime>
#include <cstdlib>
/////////////////////////////////////////////////////////////////////////////
// CLieDynamicReduct


CLieDynamicReduct::CLieDynamicReduct()
{
	srand((unsigned)time(0));//初始化为0
	num_of_del_every_time=1;
	times_of_del=40;
}

CLieDynamicReduct::~CLieDynamicReduct()
{
}

/////////////////////////////////////////////////////////////////////////////
// CLieDynamicReduct message handlers

bool CLieDynamicReduct::CreateDescMatrix(Contain& table)
{//先用list容器构建可辨识矩阵,再约简
	table.clear();
	//一个属性一个位标志，该属性上值不同就把该位置1
	CLieBitArray array(m_nConAttrNum);
	for(int i=0;i<m_nCount-1;i++)
	{
		if(!m_bObj[i]) continue;
		for(int j=i+1;j<m_nCount;j++)
		{
			if(!m_bObj[j]) continue;	//记录是否被删掉m_bObj为false表示被删掉
			array.ClearAll();
			//			TRACE("object %d,%d :",i,j);
			if( m_Record[i][m_nConAttrNum] != m_Record[j][m_nConAttrNum] )
			{//  决策不同
				bool bCollision=true;
				for(int m=0;m<m_nConAttrNum;m++)
					if( m_Record[i][m] != m_Record[j][m] )//判断此时是否存在相异属性
					{
						bCollision=false;
						//	TRACE(" %d",m);
						array.SetBit(m);//存在时,加入队列
					}
					if(bCollision)//决策不同,所有条件属性相同,冲突!
					{
						TRACE("collision\n");
						//					AfxMessageBox("collision");
						continue;
					}
					
			}
			else //  the decision  value is equal
				continue;
			bool shouldbeinsert=true;//应该被插入标志
			for(Contain::iterator it_i=table.begin();it_i!=table.end();it_i++)
			{//iterator 迭代器  begin()返回指向容器第一个元素的迭代器 
				 //             end()返回指向容器最后一个元素后面一位的迭代器(是个不存在的元素)
				//++i指向下一个元素 *i指向i所指的元素  ==比较元素的相等性
				if ( ( array & *it_i )== *it_i )
				{
					shouldbeinsert=false;
					break;
				}
			}
			
			if(shouldbeinsert)//负责对差异矩阵的各个元素插入
			{
				table.push_back(array);//将array插入table队列的最后
				ASSERT(m_nConAttrNum == array.GetBitLength());
			}
			
		}//end for
		if(table.size()!=0)
		  ReductMatrix(table);//当决策表中全为相同记录时,此时table为空
	}
	if(table.size()!=0)
		return true;
	else 
		return false;
}

bool CLieDynamicReduct::reduct()
{
	clock_t begin,end;	//记录计算时间
	double duration;
	begin=clock();	
	//table为可辨识矩阵,reducts为约简结果集.均为临时变量
	Contain table,reducts;	
	//记录最后结果,即约简及他们出现的次数.
	//std::list<CLieOutBitArray> result;
	
	//删除重复的记录
	deleteDup();
	
	//创建可辨识矩阵.(原始矩阵,所有记录都参与计算)
	if(!CreateDescMatrix(table))
	{
		 AfxMessageBox("约简结果集合为空\n不可约简!");
		 return false;
	}
	//根据原始可辨识矩阵计算约简,结果在reducts中
	GetReductsFromMatrix(table,reducts);
	//化简约简结果
	ReductMatrix(reducts);

    //static_cast<int>强制类型转换运算符,转换为int  设置每次删除的样例数目
	//对样例总数的60%分times_of_del次删除,最后剩下40%.num_of_del_every_time为每次删除的个数
	num_of_del_every_time= static_cast<int>(m_nCount*3/5 /times_of_del);//times_of_del=40

	for(Contain::iterator it_i=reducts.begin();it_i!=reducts.end();it_i++)
		result.push_back( Result_Node(*it_i,0) );//插入约简结果,有多少个属性就插入多少次
    int j=m_nCount;
	if(num_of_del_every_time==0)//保证在记录数小的时候每次删除一个记录
		num_of_del_every_time=1;
//	for(int i=0;i<times_of_del;i++)
	while((j=j-num_of_del_every_time)>=m_nCount*2/5)//剩下的记录数目大于原记录的40%时,继续删除记录
	{//从信息系统中随机删除若干条记录。
    //再次计算所得到的新系统的约简结果集。
		RandomDelete(num_of_del_every_time)	;//随机删除num_of_del_every_time个记录
		table.clear();
		reducts.clear();
		CreateDescMatrix(table);
		//	ReductMatrix(table);
		GetReductsFromMatrix(table,reducts);
		ReductMatrix(reducts);//得到约简reducts

		for(it_i=reducts.begin();it_i!=reducts.end();it_i++)
		{//对新系统的约简结果集中的每一个约简结果,统计次数的目的,就是为了找一个最稳定的约简
			for(Result_Contain::iterator it_j=result.begin();it_j!=result.end();it_j++)
				if ( (it_j->first) ==( *it_i) )//统计得到的约简在原约简中出现的次数
					it_j->second++;//出现次数加一
		}
		
	}
	end=clock();
	duration=(end-begin)/(double)CLOCKS_PER_SEC;
	char time[128];
	sprintf(time,"%f second.",duration);
	AfxMessageBox(time);

#ifdef _DEBUG
	for(Result_Contain::const_iterator it_j=result.begin();it_j!=result.end();it_j++)
		TRACE("xxx: %x, num: %d\n",it_j->first.getdata(),it_j->second);
#endif //_DEBUG
	return true;
}

bool CLieDynamicReduct::Initialize(CString FileName)
{
	return CTable::InitTable(FileName);
}

bool CLieDynamicReduct::GetReductsFromMatrix(const Contain& matrix,Contain& reducts)
{//从matrix中得到约简结果reducts
	try
	{
		int add=0;
		reducts.clear();
		CLieBitArray BitArrayTemp(m_nConAttrNum);;
		TRACE("\nFunction getreductsfrom matrix %d\n",matrix.size());
		for ( Contain::const_iterator it_i=matrix.begin();it_i!=matrix.end();it_i++)
		{
			add++;
			int _1s=it_i->Get1s();
			if (reducts.size()==0)  //the first
			{
				for (int i=0;i<it_i->GetBitLength();i++)
				{
					if ( (*it_i)[i] )
					{//只有i位为差异矩阵元素时才为一
						BitArrayTemp.ClearAll();
						BitArrayTemp.SetBit(i);//i位置一
						reducts.push_back(BitArrayTemp);//插入约简属性集
					}
				}
			}
			else       // not the fist one
			{
				Contain ContainTemp(reducts.size());   //save reducts
				std::copy(reducts.begin(),reducts.end(),ContainTemp.begin());
				reducts.clear();
				
				for(int i=0;i<it_i->GetBitLength();i++)
				{
					add++;
					if( !(*it_i)[i] )
						continue;
					for(Contain::iterator it_j=ContainTemp.begin();it_j!=ContainTemp.end();it_j++)
					{
						add++;
						reducts.push_front(*it_j);//list::push_front将元素置于队列头
						reducts.begin()->SetBit(i);//把位串的第i位赋为1
					}
				}//end for(i)				
			}//end else
		}//end for(Contain::const_iterator ..)
	}//end try
	catch(...)
	{
		//error occured
		return true;
	}

	TRACE("getreductsfrommatrix: reducts size %d\n",matrix.size());
	ASSERT(reducts.size()==0 || m_nConAttrNum == reducts.begin()->GetBitLength());
	return true;
}

//针对可辨识矩阵约简算法原理,对可辨识矩阵进行约简.
void CLieDynamicReduct::ReductMatrix(Contain& matrix)
{
	if (matrix.size()<=1) return;
	ASSERT(m_nConAttrNum == matrix.begin()->GetBitLength());

	for(Contain::iterator it_i=matrix.begin();it_i!=matrix.end();it_i++)
	{
		Contain::iterator it_j=matrix.begin();
		while(it_j!=matrix.end())
		{
			if (it_i==it_j)
			{
				it_j++;
				continue;
			}
			//如果( *it_i )属于( *it_j ), 则删除( *it_j )
			if( (*it_j & *it_i)== *it_i )
			{
				Contain::iterator it_tmp=it_j;
				it_j++;
				matrix.erase(it_tmp);
				continue;
			}
			it_j++;
		}
	}
}

void CLieDynamicReduct::RandomDelete(long num)
{//随机删除num个记录
	for(int i=0;i<num;i++)
	{
		int a= rand() % m_nCount;
		while( !m_bObj[a] && a<m_nCount-1)//当样例被删除并且a小于样例总数减1时
			a++;//知道a样例没有被删除时停止while
		m_bObj[a]=false;//删除对应样例
		TRACE(" %d was deleted \n",a);
	}
}

bool CLieDynamicReduct::WriteFile(CString name)
{	//result 中为各约简结果及其出现次数. 基于可辨识矩阵的约简会可能得到多种结果
	//寻找出现次数最多的所对应的约简结果作为最后结果
	Result_Contain::const_iterator it_max=result.begin();
	//Result_Contain::const_iterator指向容器中的常量迭代器,只能读取容器中的元素
	for(Result_Contain::const_iterator it_i=result.begin();it_i!=result.end();it_i++)
	{
		if ( it_i->second > it_max->second )//位串比较,second表示出现次数
			it_max=it_i;//求取最大值
	}
	const CLieBitArray* result_bitarray=& (it_max->first);
	ASSERT( m_nConAttrNum == result_bitarray->GetBitLength());
	for(int i=0;i<m_nConAttrNum;/*result_bitarray->GetBitLength()*/i++)
	{
		if(! (*result_bitarray)[i] )
			m_bAttr[i]=false;
		else
			m_bAttr[i]=true;
	}
	return CTable::WriteFile(name);
}