zssentropyscaler.cpp

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

// ZssEntropyScaler.cpp: implementation of the CZssEntropyScaler class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "math.h"
#include "ZssEntropyScaler.h"

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

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

CZssEntropyScaler::CZssEntropyScaler()
{

}

CZssEntropyScaler::~CZssEntropyScaler()
{

}

//基于信息熵的离散化算法
BOOL CZssEntropyScaler::EntropyScaler(CString str_s_file, CString str_d_file)
{
	fpos_t file_pos;
	FILE *file_s,*file_d;
	if ((file_pos=ReadFileHead((LPCTSTR)(str_s_file),1))==0)//读取文件头
		return FALSE;//失败返回
	if ((file_s=fopen(str_s_file,"r"))==NULL)//打开文件
		return FALSE;
	if ((file_d=fopen((LPCTSTR)(str_d_file),"w"))==NULL)//打开文件
	{
		return FALSE;
	}	
	//得到字符串属性和非字符串属性的个数
	int i_str_Attr_Num,i_Nonstr_Attr_Num;
	GetStrAndNonStrNum(i_str_Attr_Num, i_Nonstr_Attr_Num);

	CStringArray *p_str_Attr=NULL;//保存字符串条件属性的断点信息
	if ((p_str_Attr=new CStringArray[i_str_Attr_Num+1])==NULL)
	{
		delete []p_str_Attr;
		return FALSE;	
	}
	CArray<float, float> *p_nonstr_Attr=NULL;//保存非字符串条件属性的断点信息
	if ((p_nonstr_Attr=new CArray<float,float>[i_Nonstr_Attr_Num+1])==NULL)
	{
		delete []p_str_Attr;
		return FALSE;
	}

	CArray<TAGSTATINFO,TAGSTATINFO>statinfo;
	int low,high;
	//开始对每一个属性进行信息熵的离散化
	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_s, i, p_str_Attr[i_Str_Attr_Index], file_pos);
			i_Str_Attr_Index++;
		}
		else//对非字符串处理
		{			
			GetStatInfo(i,statinfo, file_s, file_pos);
			low=0;
			high=statinfo.GetSize();//属性值个数
			p_nonstr_Attr[i_Nonstr_Attr_Index].RemoveAll();//清空
			GetBreakPoint_InNonStrAttr(p_nonstr_Attr[i_Nonstr_Attr_Index], statinfo, low, high-1);
			//取得该属性的断点信息	写入p_nonstr_Attr[i_Nonstr_Attr_Index]中			
			i_Nonstr_Attr_Index++;
		}
	}
	WriteFileHead(file_d,1,2);//写文件头
	WriteResult(file_d, file_s, file_pos, p_nonstr_Attr, p_str_Attr);
	//写信息表离散结果
	WriteFileTail(file_d,p_nonstr_Attr,p_str_Attr);//写入断点信息
	fclose(file_s);
	fclose(file_d);
	if (p_str_Attr!=NULL)
		delete []p_str_Attr;
	if (p_nonstr_Attr!=NULL)
		delete []p_nonstr_Attr;	
	return TRUE;
}

//得到一个指定属性的统计信息即属性的值和该属性值出现的次数
//i_attr:是第几个属性
//statinfo:保存统计信息
void CZssEntropyScaler::GetStatInfo(int i_attr, CArray<TAGSTATINFO,TAGSTATINFO> &statinfo, FILE *pfile,fpos_t file_pos)
{
	statinfo.RemoveAll();//请空队列
	char str_temp[ZSSLEN];
	fsetpos(pfile, &file_pos);
	MoveFilePoint(pfile, i_attr);//移动文件指针
	double d_val;
	for(long i=0; i<m_iRecordNum; i++)
	{
		fscanf(pfile,"%s",str_temp);
		d_val=atof(str_temp);
		AddToArray(d_val, statinfo);
		MoveFilePoint(pfile,m_iConAttrNum);		
	}
}

//将一个属性值加入到统计信息的数组中在加入的过程中已经排序（从小到大）
void CZssEntropyScaler::AddToArray(double d_val,CArray<TAGSTATINFO,TAGSTATINFO>&statinfo)
{	
	int i_size=statinfo.GetSize();
	double d_tempval;
	for (int i=0;i<i_size; i++)//i为所设断点
	{
		d_tempval=statinfo.GetAt(i).d_value;
		if (d_tempval==d_val)
		{
			statinfo[i].i_num++;//出现的次数加一
			return;
		}
		if (d_val<d_tempval)//找到合适位置，插入
		{
			TAGSTATINFO tag;
			tag.d_value=d_val;
			tag.i_num=1;
			statinfo.InsertAt(i,tag);
			return;
		}
	}
	TAGSTATINFO tag1;
	tag1.d_value=d_val;
	tag1.i_num=1;
	statinfo.Add(tag1);//没找到，插到最后
}

//基于信息熵来求断点，采用递归的方法来求。快速排序法
void CZssEntropyScaler::GetBreakPoint_InNonStrAttr(CArray<float,float> &breakpoint_array,
		CArray<TAGSTATINFO,TAGSTATINFO> &statinfo, int low, int high)
{
	if (low>=high)
		return;
	float d_entopy,d_temp;
	int i_index=low,i_total;//i_index表示断点以下的最大值
	i_total=GetTotal(statinfo, low, high);
	d_entopy=GetEntopy(statinfo,low,low,high,i_total);
	//计算信息以low位置为断点时的信息熵值
	for (int i=low+1;i<high;i++)
	{
		d_temp=GetEntopy(statinfo,i,low,high,i_total);
		//获得以i位置为断点是的信息熵值
		if(d_temp<d_entopy)//比较信息熵，取最小值
		{
			i_index=i;		
			d_entopy=d_temp;
		}
	}
	float d_val=float((statinfo.GetAt(i_index).d_value+statinfo.GetAt(i_index+1).d_value)/2);
	//得到断点值；；（信息熵值最小的属性值）
	AddToArrayByOrder(d_val,breakpoint_array);//按照从小到大的顺序插入断点队列
	if(CanStop(statinfo,i_index,low,high))//判断是否达到递归的停止条件
	{
		return;
	}
	//继续
	GetBreakPoint_InNonStrAttr(breakpoint_array,statinfo,low,i_index);
	//对左边的划分递归
	GetBreakPoint_InNonStrAttr(breakpoint_array,statinfo,i_index+1,high);
	//对右边的划分递归
}

//计算信息以i_break位置为断点时的信息熵值
float CZssEntropyScaler::GetEntopy(CArray<TAGSTATINFO,TAGSTATINFO> &statinfo,
                        int i_break,int low, int high, int total)
{
	int total1,total2;
	total1=GetTotal(statinfo,low,i_break);
	total2=GetTotal(statinfo,i_break+1,high);
	float d_ent1,d_ent2,d_entropy;
	d_ent1=GetEnt(statinfo,low,i_break,total1);//计算的熵都是条件熵
	d_ent2=GetEnt(statinfo,i_break+1,high,total2);
	d_entropy=total1*d_ent1/total+total2*d_ent2/total;
	//E(A,T;S)=|S1|/|S|·Ent(S1)+ |S2|/|S|·Ent(S2)
	return d_entropy;
}

/*看是否满足递归停止条件(stop criteria)
*/
BOOL CZssEntropyScaler::CanStop(CArray<TAGSTATINFO,TAGSTATINFO> &statinfo,int i_break,int low, int high)
{
	double f_gain,f_delta,f_ent,f_ent1,f_ent2;
	int i_N,i_total1,i_total2;

	i_N=GetTotal(statinfo,low,high);
	i_total1=GetTotal(statinfo,low,i_break);
	i_total2=GetTotal(statinfo,i_break+1,high);//计算各部分的实例个数

	f_ent=GetEnt(statinfo,low,high,i_N);//S的信息熵
	f_ent1=GetEnt(statinfo,low,i_break,i_total1);//S1的信息熵
	f_ent2=GetEnt(statinfo,i_break+1,high,i_total2);//S2的信息熵
	f_gain=f_ent-GetEntopy(statinfo,i_break,low,high,i_N);//计算Gain(A,T;s)

	int i_k,i_k1,i_k2;
	i_k=high-low+1;//
	i_k1=i_break-low+1;//
	i_k2=high-i_break;//
	//?????????????????????????????????????
	//Gain(A,T;S)<lg(N-1/N)/lg2+delta/N
    //Gain(A,T;S)=Ent(S)-E(A,T;S);   
    //delta=log(3(k次方)-2)/lg2-[k*Ent(S)-k1*Ent(S2)-k2*Ent(S2)]
	//?????????????????????????????????????/?
	//问题:公式中的k是什么意思k=|S| k1=|S1| k2=|S2|
	//原文：number of class labels represented inf the set Si
	//暂时理解为:在划分的集合S中属性值（是指不同的属性值）的个数
	//（不是instance的个数）
	f_delta=log(pow(3,i_k)-2)/log(2.0)-i_k*f_ent+i_k1*f_ent1+i_k2*f_ent2;
	f_delta+=log(i_N-1)/log(2.0);
	f_delta=f_delta/i_N+log((i_N-1)/i_N)/log(2.0);
	if (f_gain<f_delta)
		return TRUE;
	return FALSE;
}

//计算区间中的实例个数
int CZssEntropyScaler::GetTotal(CArray<TAGSTATINFO,TAGSTATINFO> &statinfo,int low, int high)
{
	int total=0;
	for(int i=low;i<=high;i++)
		total+=statinfo.GetAt(i).i_num;
	return total;
}

//计算Ent(熵)见张弋论文
float CZssEntropyScaler::GetEnt(CArray<TAGSTATINFO,TAGSTATINFO> &statinfo, int low, int high,int total)
{
	float d_ent=0,d_probability;
	for (int i=low;i<=high; i++)
	{
		d_probability=(statinfo.GetAt(i).i_num)/(float)(total);//计算概率
		d_ent=d_ent-float((d_probability*log(d_probability)/log(2.0)));
	}
	return d_ent;
}