zssbreakpointscaler.cpp

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

// ZssBreakPointScaler.cpp: implementation of the CZssBreakPointScaler class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "ZssBreakPointScaler.h"

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

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


CZssBreakPointScaler::CZssBreakPointScaler()
{
}


CZssBreakPointScaler::~CZssBreakPointScaler()
{
}


//基于断点重要性的离散化
BOOL CZssBreakPointScaler::BreakPointScaler(CString str_sfile, CString str_dfile)
{		//str_sfile:需要离散化的源文件名
		//str_dfile:离散化后要存储结果的目标文件名
	fpos_t file_pos;
	FILE *file_source,*file_dest;
	if ((file_pos=ReadFileHead((LPCTSTR)(str_sfile),1))==0)//读取文件头,1即还没有离散化
		return FALSE;//失败返回
			//ReadFileHead() post:
			//m_iConAttrNum   属性个数
			//m_iRecordNum    含有记录个数
			//m_AttrName[]    属性名(index: 0 至 m_iConAttrNum)
			//m_AttrType[]    属性类型(index: 0 至 m_iConAttrNum)
			//file_pos位于第一条记录的第一个属性前
	if ((file_source=fopen(str_sfile,"r"))==NULL)//打开文件
		return FALSE;
	if ((file_dest=fopen((LPCTSTR)(str_dfile),"w"))==NULL)//打开文件
		return FALSE;

	//得到字符串属性和非字符串属性的个数
	int i_str_Attr_Num,i_Nonstr_Attr_Num;
	GetStrAndNonStrNum(i_str_Attr_Num, i_Nonstr_Attr_Num);
			//GetStrAndNonStrNum() post:
			//i_str_Attr_Num       字符串属性个数
			//i_Nonstr_Attr_Num    非字符串属性个数

	CStringArray *p_str_Attr=NULL;//保存字符串条件属性的断点信息
		//p_str_Attr的每一个节点都是一个字符串数组
		//在完成离散化以后,每一个节点保存一个条件属性的所有可能值
	if ((p_str_Attr=new CStringArray[i_str_Attr_Num+1])==NULL)
		return FALSE;
	CArray<float, float> *p_nonstr_Attr=NULL;//保存非字符串条件属性的断点信息
		//p_nonstr_Attr的每一个节点都是一个链表,这个链表的节点也是一个链表
		//在完成离散化以后,每一个节点保存一个条件属性的所有等价类
	if ((p_nonstr_Attr=new CArray<float,float>[i_Nonstr_Attr_Num+1])==NULL)
	{
		delete []p_str_Attr;
		return FALSE;
	}

	int i_Str_Attr_Index=0, i_Nonstr_Attr_Index=0;//字符串属性索引和非字符串属性索引
	for (int i=0; i<m_iConAttrNum; i++)
	{
		if (0==stricmp(m_AttrType[i], "String"))//对字符串条件属性的处理
		{
			GetBreakPoint_InStrAttr(file_source, i, p_str_Attr[i_Str_Attr_Index], file_pos);
									//file_source:文件名
									//i:属性索引
									//p_str_Attr[i_StrAttr_Index]
									//file_pos:文件指针所处位置
			i_Str_Attr_Index++;
		}
		else
		{
			if (!GetBreakPoint_InNonStrAttr(file_source,i,p_nonstr_Attr[i_Nonstr_Attr_Index],file_pos))
				return FALSE;
			i_Nonstr_Attr_Index++;
		}
	}
	//post:
	//p_str_Attr[i_Str_Attr_Index]中含有第i_Str_Attr_Index个String类型属性的所有可能值
		//可以根据这些值在p_str_Attr[i_Str_Attr_Index]中的索引来把它离散化成Integer类型
	//p_nonstr_Attr[i_Nonstr_Attr_Index]中,含有第i_Nonstr_Attr_Index个非String属性的所有等价类集合

	WriteFileHead(file_dest,1,2);//写文件头
	WriteResult(file_dest,file_source, file_pos,p_nonstr_Attr, p_str_Attr);//写离散化后的结果
	WriteFileTail(file_dest,p_nonstr_Attr,p_str_Attr);//写入断点信息
	fclose(file_source);
	fclose(file_dest);
	if (p_str_Attr!=NULL)
		delete []p_str_Attr;
	if (p_nonstr_Attr!=NULL)
		delete []p_nonstr_Attr;	
	return TRUE;
}

//得到一个非字符串属性的断点信息
BOOL CZssBreakPointScaler:: GetBreakPoint_InNonStrAttr(FILE *pfile,int i_attr,
		CArray<float,float> &breakpoint_array,fpos_t file_pos)
{
	CArray<float,float> temp_array;//存放候选属性
	CObList *p_list=NULL;//存放等价类集合
	if((p_list=new CObList)==NULL)
		return FALSE;

	breakpoint_array.RemoveAll();
	if (!Read_Attr(pfile, i_attr, temp_array, p_list, file_pos))//读取属性(候选属性已经排序)
		return FALSE;
	//post:
	//temp_array中存放的是所有可能的断点(升序)
	//p_list中存放的是当前条件属性的所有值和它对映的决策属性值
	while(0!=temp_array.GetSize())//考查所有的候选属性
	{
		GetBreakImportance(p_list,breakpoint_array,temp_array);
		if (CanEnd(p_list))//判断是否满足结束条件
			break;		
	}
	//post:
	//p_nonstr_Attr中存放已经根据断点重要性划分后的等价类集合
	//breakpoint_array中存放所有断点集合

	//释放内存
	POSITION pos=p_list->GetHeadPosition();
	int i_len=p_list->GetCount();
	CList<TAG_INSTANCE,TAG_INSTANCE> *p_element;
	for(int i=0;i<i_len;i++)
	{
		p_element=(CList<TAG_INSTANCE,TAG_INSTANCE> *)(p_list->GetNext(pos));
		if (p_element!=NULL)
			delete p_element;
	}
	delete p_list;
	return TRUE;
}


//读取由i_attr指定的条件属性
BOOL CZssBreakPointScaler:: Read_Attr(FILE *pfile,int i_attr,
		CArray<float,float> &attr_array,CObList *p_list,fpos_t file_pos)
{
	fsetpos(pfile,&file_pos);
	char str_temp[ZSSLEN];
	TAG_INSTANCE _tag1;
	float f_temp;
	CList<TAG_INSTANCE,TAG_INSTANCE> *p_list_attr;
	if ((p_list_attr=new CList<TAG_INSTANCE,TAG_INSTANCE>)==NULL)
		return FALSE;
	for(long i=0; i<m_iRecordNum; i++)
	{
		MoveFilePoint(pfile, i_attr);//移动文件指针
		fscanf(pfile,"%s",str_temp);
		f_temp=(float)atof(str_temp);
		MoveFilePoint(pfile, m_iConAttrNum-i_attr-1);
			//文件指针转移到决策属性处
		fscanf(pfile,"%s",str_temp);
		_tag1.f_con_attr=f_temp;
		_tag1.str_d_attr=str_temp;
		p_list_attr->AddTail(_tag1);
			//把该条件属性值和决策属性值(String型)加入链表结尾
		AddToArrayByOrder(f_temp,attr_array);
			//把条件属性的值(升序排序后)加入数组中(去掉重复值)
	}
	//post:
	//p_list_attr中存放的是条件属性值和对映的决策属性值
	//attr_array中存放的是升序排序后的条件属性值
	int i_len=attr_array.GetSize();
	float f_ave;
	for( i=0; i<i_len-1; i++)
	{
		f_ave=(attr_array[i]+attr_array[i+1])/2;
		attr_array.SetAt(i,f_ave);
	}
	//attr_array中存放的是所有可能断点的集合
	attr_array.RemoveAt(i_len-1);//去掉最后一个条件属性值(不是断点)
	p_list->AddTail(p_list_attr);
	return TRUE;
}

//从候选集中选取断点重要性最大的断点
BOOL CZssBreakPointScaler::GetBreakImportance(CObList *p_list, CArray<float,float> &break_array,
	 CArray<float,float> &temp_array)
{
	long l_len=p_list->GetCount();
		//l_len是等价类的个数
	int i_breakcount=temp_array.GetSize();
		//i_breakcount是断点个数
	float f_break;
	CList<TAG_INSTANCE,TAG_INSTANCE> *p_instance;
		//p_instance中存放当前等价类的链表
	POSITION pos;
	int i_importance=0, i_temp ,i_index=0,i_local;

	//得到重要性最大的断点
	for (int i_break=0; i_break< i_breakcount; i_break++)//对每一个候选断点
	{
		f_break=temp_array[i_break];
		pos=p_list->GetHeadPosition();
		i_temp=0;
		for(int i=0;i<l_len; i++)//对每一个可区分的实例集合
		{
			p_instance=(CList<TAG_INSTANCE,TAG_INSTANCE> *)(p_list->GetNext(pos));
			i_local=GetNumber(p_instance,f_break);
			i_temp+=i_local;
		}
		if (i_temp>i_importance)
		{
			i_importance=i_temp;
			i_index=i_break;
		}
		//i_index保存当前所有计算过的断点中,断点重要性最大的断点在temp_array[]中的位置(索引值)
		//i_importance保存当前所有计算过的断点中,最大的断点重要性的值
	}
	f_break=temp_array[i_index];//断点值
	AddToArrayByOrder(f_break,break_array);//加入该断点到断点集合	
	temp_array.RemoveAt(i_index);//从候选断点集合中删除该断点
	ReDefine(p_list,f_break);//根据得到的断点对等价类集合重新划分
	return TRUE;
}

//得到对于给定断点f_break将实例集合(保存在p_instance)区分开的实例对的个数
int CZssBreakPointScaler::GetNumber(CList<TAG_INSTANCE,TAG_INSTANCE> *p_instance, float f_break)
{
	int i_l=0, i_r=0;
	CStringArray str_temp;
	POSITION pos=p_instance->GetHeadPosition();
	int i_len=p_instance->GetCount();
		//i_len为当前等价类中的记录个数
	str_temp.RemoveAll();
	for(int i=0; i<i_len; i++)
	{
		TAG_INSTANCE &tag=p_instance->GetNext(pos);
		if (tag.f_con_attr<f_break)//如果当前记录的条件属性值小于断点值
			i_l++;
		if (tag.f_con_attr>f_break)//如果当前记录的条件属性值大于断点值
			i_r++;
		if (!IsStringInStringArray(tag.str_d_attr,str_temp))
			str_temp.Add(tag.str_d_attr);//所有决策属性值都加入str_temp中
	}
	//post:
	//i_l为条件属性值小于当前断点的记录个数
	//i_r为条件属性值大于当前断点的记录个数
	
	int i_strlen=str_temp.GetSize();
		//i_strlen为决策属性个数所
	CString str_d;
	int i_l1, i_r1, j ,i_other=0;
	for(i=0; i<i_strlen; i++)
	{
		pos= p_instance->GetHeadPosition();
		str_d= str_temp[i];
		i_l1=0;
		i_r1=0;
		for (j=0; j<i_len; j++)
		{
			TAG_INSTANCE &tag1=p_instance->GetNext(pos);
			if(0==strcmp(str_d, tag1.str_d_attr))
			{
				if (tag1.f_con_attr<f_break)
					i_l1++;
				if (tag1.f_con_attr>f_break)
					i_r1++;
			}//在决策属性相同时,比较条件属性值与当前断点值的大小
		}
		//post:
		//i_l1为决策属性与当前记录的决策属性相同的记录中,条件属性值小于当前断点的记录个数
		//i_r1为决策属性与当前记录的决策属性相同的记录中,条件属性值大于当前断点的记录个数
		i_other+=i_l1*i_r1;
	}
	return i_r*i_l- i_other;//返回当前断点的断点重要性
}

//根据断点f_break对等价类集合重新划分
BOOL CZssBreakPointScaler::ReDefine(CObList *p_list,float f_break)
{
	int i_len=p_list->GetCount(), i_len1;
		//i_len为等价类的数量
	POSITION pos=p_list->GetHeadPosition(),pos3;
	CList<TAG_INSTANCE,TAG_INSTANCE> *p_other=NULL,*p_temp;
	TAG_INSTANCE tag;
	for(int i=0; i<i_len; i++)
	{
		if((p_other=new CList<TAG_INSTANCE,TAG_INSTANCE>)==NULL)
			return FALSE;
		pos3=pos;
			//pos3,pos为当前等价类在整个链表中的位置
		p_temp=(CList<TAG_INSTANCE,TAG_INSTANCE> *)(p_list->GetNext(pos));
			//p_temp中存放当前等价类
		i_len1=p_temp->GetCount();
			//i_len1为当前等价类中含有的记录数量
		POSITION pos1=p_temp->GetHeadPosition(),pos2;
			//pos1,pos2为当前节点在等价类中的位置
		for(int j=0; j<i_len1; j++)
		{
			pos2=pos1;
			tag=p_temp->GetNext(pos1);
			if (f_break<tag.f_con_attr)
			{
				p_temp->RemoveAt(pos2);
				p_other->AddTail(tag);
			}
		}
		//post:
		//条件属性值小于断点值的属性存在与p_temp中
		//条件属性值大于断点值的属性存在于P_other中
		if (p_temp->GetCount()==0)
		{
			p_list->SetAt(pos3,p_other);
			if (p_temp!=NULL)
				delete p_temp;
			continue;
		}//如果所有属性值都大于断点值,则删掉原来的等价类
		if (p_other->GetCount()==0&&p_other!=NULL)
		{
			delete p_other;
			continue;
		}//如果所有属性值都大于断点值,则删掉p_other
		p_list->AddTail(p_other);
	}
	return TRUE;
}

//判断是否能够结束，即使排断等价类集合中的各个实例是否都具有相同的决策
BOOL CZssBreakPointScaler::CanEnd(CObList *p_list)
{
	if(p_list==NULL)
		return TRUE;
	POSITION pos=p_list->GetHeadPosition(),pos1;
	int i_len=p_list->GetCount(),i_len1;
	CList<TAG_INSTANCE, TAG_INSTANCE> *p_instance;
	for(int i=0;i<i_len;i++)
	{
		p_instance=(CList<TAG_INSTANCE, TAG_INSTANCE> *)(p_list->GetNext(pos));
		i_len1=p_instance->GetCount();
		pos1=p_instance->GetHeadPosition();
		TAG_INSTANCE &tag1=p_instance->GetNext(pos1);
		CString f_temp=tag1.str_d_attr;
		for(int j=1;j<i_len1;j++)
		{
			TAG_INSTANCE &tag=p_instance->GetNext(pos1);
			if(strcmp(f_temp,tag.str_d_attr)!=0)
				return FALSE;
			//当同一个等价类中的决策属性值不相等的时候,不能停止,返回false
		}
	}
	return TRUE;
}