covernn.cpp

thank you for using this software,which is fugai method,when you can t catch it,please ask me for my

// CoverNN.cpp: implementation of the CoverNN class.
//
//////////////////////////////////////////////////////////////////////

#include "CoverNN.h"
#include <math.h>
#include <fstream.h>
#include <time.h>

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

CoverNN::CoverNN()
{
	InnPro = false;//采用内积

	Covers = new CovCell;//建立一个头结点，便于连接链表
}

CoverNN::~CoverNN()
{
	CovCell * p ;
	p = Covers;
	while(p!=NULL)
	{
		Covers = Covers->next;
		delete[] p->center;
		delete p;
		p = Covers;
	}
}

////////////////////////////////////////////////////////////
//  学习样本数据的格式：
//  LINE1：训练样本总数  样本输入维数
//  LINEi：样本值  类别
////////////////////////////////////////////////////////////
//////////////根据文件名载入学习数据或测试数据/////////////////
int CoverNN::LoadData( const char * fn_dat, const bool train)
{
	int i,j;
	ifstream inf( fn_dat );

	inf>>Num>>Dim_in;
	Data = new double*[Num];
	Target = new int[Num];
	for(i=0;i<Num;i++)
	{
		Data[i] = new double[Dim_in+1];
		for(j=0;j<Dim_in;j++)
		{
			inf>>Data[i][j];
		}
		inf>>Target[i];
	}

	inf.close();

	if(train)
	{
		NoCov = new bool[Num];
		for(i=0;i<Num;i++)
		{
			NoCov[i] = true;
		}
	}

	return 0;
}

/////////训练网络////////////////
void CoverNN::Train()
{
	int i,j;

	R = 0;
	for(i=0;i<Num;i++)
	{
		Data[i][Dim_in] = 0;
		for(j=0;j<Dim_in;j++)
		{
			Data[i][Dim_in] += Data[i][j] * Data[i][j];
		}
		if(R < Data[i][Dim_in])
		{
			R = Data[i][Dim_in];
		}
	}
	R = sqrt(R) * 1.5;
	//将样本数据进行投影
	for(i=0;i<Num;i++)
	{
		Data[i][Dim_in] = sqrt(R*R - Data[i][Dim_in]);
	}

	//------------开始循环求覆盖------------------
	Num_C = 0;
	CovCell * p;
	p = Covers;
	CovCell * pcell;

	int kind = -1;
	while( !IsFinished( kind ) )
	{
		//----------------跳过已经被覆盖的样本---------------
		i = 0 ;
		while(!NoCov[i] && i<Num)
		{
			i++;
		}
		//----------------初始化覆盖的中心------------------
		pcell = new CovCell;
		pcell->center = new double[Dim_in+1];
		for(j=0;j<=Dim_in;j++)
		{
			pcell->center[j] = Data[i][j];
		}
		pcell->kind = Target[i];
		//
		GetCovCell(*pcell);//得到一个覆盖
		p->next = pcell;
		p = p->next;
		Num_C++;//覆盖数加1
		kind = -1;
	}
	//--------------对最后一个覆盖的处理------------
	pcell = new CovCell;
	pcell->center = new double[Dim_in+1];
	for(i=0;i<Dim_in;i++)
	{
		pcell->center[i] = 0;
	}
	pcell->center[Dim_in] = R;//覆盖中心在半球面的最顶端
	pcell->kind = kind;//覆盖类别为剩余的样本点的类别
	if(InnPro)//覆盖阈值分情况取值
	{
		pcell->threshold = 0;
	}
	else
	{
		pcell->threshold = R;
	}
	p->next = pcell;
	Num_C++;
	//----------学习完毕后，清理学习数据所占的内存------------
	delete[] NoCov;
	delete[] Data;
	delete[] Target;
}

/////判断训练是否可以结束///////////
bool CoverNN::IsFinished(int &kind)
{
	bool yes = true;
	for(int i=0;i<Num;i++)//遍历所有样本点
	{
		if(NoCov[i])//寻找未被覆盖的样本
		{
			if(kind == -1)
			{
				kind = Target[i];
			}
			else if(kind != Target[i])//如果还有不同类的样本，则不能结束
			{
				yes = false;
				break;
			}
		}
	}

	return yes;
}

///////判断样本是否被覆盖/////////
bool CoverNN::IsCovered( const CovCell &cell, double * dat)
{
	double tmp = 0;
	int i;
	if(InnPro)//------采用内积-------
	{
		for(i=0;i<=Dim_in;i++)
		{
			tmp += cell.center[i] * dat[i];
		}

		return (tmp > cell.threshold);
	}
	else///--------采用距离---------
	{
		for(i=0;i<=Dim_in;i++)
		{
			tmp += pow( (cell.center[i] - dat[i]) , 2);
		}
		tmp = sqrt( tmp );

		return (tmp < cell.threshold);
	}
}

////////判断前一个集合是否为后一个的真子集///////////
bool CoverNN::IsRealSubset(const bool * subset, const bool * superset)
{
	bool yes = true;
	int i,k = 0;
	for(i=0;i<Num;i++)
	{
		if(subset[i] && !superset[i])
		{
			yes = false;
			break;
		}
		else if(superset[i] && !subset[i])
		{
			k++;
		}
	}

	return (yes && k>0);
}

//////求一个覆盖//////////////////
int CoverNN::GetCovCell(CovCell &cell)
{
	CovCell cell_old;
	cell_old.center = new double[Dim_in+1];
	cell_old.kind = cell.kind;
	double temp;
	double farthest,nearest;//farthest代表本类样本，nearest代表非本类样本
	int covd_num[] = { 0 , 0 };
	double * cen_tmp = new double[Dim_in];//求覆盖的样本个数,同时保存得到覆盖的临时中心(只需要前Dim_in维)
	int i;
	bool * sfx[2];
	sfx[0] = new bool[Num];//用来保存sfx[1]
	sfx[1] = new bool[Num];//用来标记本次被覆盖的点的下标，被覆盖标记为true
	for(i=0;i<Num;i++)
	{
		sfx[0][i] = sfx[1][i] = false;
	}

	bool isrealsub;
	bool end_tag = true;
	bool needtrans = true;
	while(end_tag)
	{
		nearest = Nearest_non(cell);
		farthest = Farthest_kin(cell,nearest);

		cell.threshold = (nearest + farthest)/2;//原算法的阈值求法
//		cell.threshold = nearest - 3.1415926535*7/19.0;//修改算法

		covd_num[1] = GetDomain( cell, cen_tmp, sfx[1]);
		isrealsub = IsRealSubset(sfx[0],sfx[1]);//前一次覆盖的点是后一次的真子集也就代表点数增多

		if(covd_num[1]<covd_num[0])
		{
			if(needtrans)//如果还没有平移过
			{
				GetTranslationpoint(cell);
				needtrans = false;
			}
		}

		if(isrealsub)
		{
			//------------保存本次的数据,同时求得重心---------------
			temp = 0;
			for(i=0;i<Dim_in;i++)
			{
				cell_old.center[i] = cell.center[i];
				cell.center[i] = cen_tmp[i];
				temp += cen_tmp[i] * cen_tmp[i];
			}
			cell_old.center[Dim_in] = cell.center[Dim_in];//保存本次的覆盖中心
			cell.center[Dim_in] = sqrt( R*R - temp);//投影后得到完整的新的覆盖中心（重心）
			cell_old.threshold = cell.threshold;//保存本次的阈值
			covd_num[0] = covd_num[1];//保存本次的覆盖样本数
			for(i=0;i<Num;i++)
			{
				sfx[0][i] = false;//先要将原来的全部清零，再重新赋值
				if(sfx[1][i])
				{
					sfx[0][i] = true;
					sfx[1][i] = false;
				}
			}
			needtrans = true;//置标志位：可平移
			//--------不求重心，而改求中心------
			GetMidpoint(cell.center,sfx[0]);//结果：原始算法得到10个覆盖
		}
		else if(needtrans)
		{
			//------------先保存本次的数据---------------
			for(i=0;i<Dim_in;i++)
			{
				cell_old.center[i] = cell.center[i];
			}
			cell_old.center[Dim_in] = cell.center[Dim_in];//保存本次的覆盖中心
			cell_old.threshold = cell.threshold;//保存本次的阈值
			covd_num[0] = covd_num[1];//保存本次的覆盖样本数
			for(i=0;i<Num;i++)
			{
				sfx[0][i] = false;//先要将原来的全部清零，再重新赋值
				if(sfx[1][i])
				{
					sfx[0][i] = true;
					sfx[1][i] = false;
				}
			}
			//-------------再进行平移----------------
			GetTranslationpoint(cell);
			needtrans = false;//置标志位：下次不可平移
		}
		else
		{
			end_tag = false;
		}
	}
	//-----------得到一个覆盖--------------
	for(i=0;i<=Dim_in;i++)
	{
		cell.center[i] = cell_old.center[i];//保存当前覆盖的中心（权值）
	}
	cell.threshold = cell_old.threshold;//保存当前覆盖的阈值
	for(i=0;i<Num;i++)
	{
		if(sfx[0][i])
		{
			NoCov[i] = false;//标记已覆盖样本
		}
	}

	delete[] sfx[0];
	delete[] sfx[1];
	delete[] cen_tmp;
	delete[] cell_old.center;
	return 0;
}

///////求本次覆盖盖住的样本数，并附带求中心（即新的覆盖中心）/////////////
int CoverNN::GetDomain(const CovCell &cell, double * cen, bool * sfx)
{
	int result = 0;
	int i,j;
	for(i=0;i<Dim_in;i++)
	{
		cen[i] = 0;
	}

	for(i=0;i<Num;i++)
	{
		if(NoCov[i] && Target[i]==cell.kind)//属于本类且未被覆盖
		{
			if( IsCovered(cell, Data[i]) )
			{
				result++;
				sfx[i] = true;
				for(j=0;j<Dim_in;j++)
				{
					cen[j] += Data[i][j];
				}
			}
		}
	}
	for(i=0;i<Dim_in;i++)//加和平均求得重心，只求得前Dim_in维的值，最后一维需投影
	{
		cen[i] = cen[i] / result;
	}

	return result;
}

////////////求非本类的距cen最近的样本与cen的内积（或距离）////////////
double CoverNN::Nearest_non(const CovCell &cen)
{
	double result , temp;
	int i;

	if(InnPro)//------采用内积-----
	{
		result = 0;
		for(i=0;i<Num;i++)
		{
			if( NoCov[i] && Target[i]!=cen.kind )//未被覆盖 且 非本类
			{
				temp = GetInnerProduct(cen.center,Data[i],Dim_in+1);
				if(result < temp)
				{
					result = temp;
				}
			}
		}
	}
	else//-------采用距离-------
	{
		result = 2*R;
		for(i=0;i<Num;i++)
		{
			if( NoCov[i] && Target[i]!=cen.kind )//未被覆盖 且 非本类
			{
				temp = GetDistance(cen.center,Data[i],Dim_in+1);
				if(result > temp)
				{
					result = temp;
				}
			}
		}
	}

	return result;
}

///////////求本类的距cen最远的样本与cen的内积（或距离）////////////
double CoverNN::Farthest_kin(const CovCell &cen, const double max)
{
	double result , temp;
	int i;

	if(InnPro)//------采用内积-----
	{
		result = R * R;
		for(i=0;i<Num;i++)
		{
			if( NoCov[i] && Target[i]==cen.kind )//本类 且 未被覆盖
			{
				temp = GetInnerProduct(cen.center,Data[i],Dim_in+1);
				if(temp > max && result > temp)
				{
					result = temp;
				}
			}
		}
		if(result == R*R)//如果未找到同类的其他样本点，则设max=R*R*cos(2a)，result取R*R*cos(a)
		{
			result = result * sqrt( (result+max) / (2*result) );
		}
	}
	else//-------采用距离-------
	{
		result = 0;
		for(i=0;i<Num;i++)
		{
			if( NoCov[i] && Target[i]==cen.kind )//本类 且 未被覆盖
			{
				temp = GetDistance(cen.center,Data[i],Dim_in+1);
				if( temp < max && result < temp )
				{
					result = temp;
				}
			}
		}
		if(result==0)//如果未找到同类的其他样本点，则取距离max的一半
		{
			result = max / 2;
		}
	}

	return result;
}

//////////////求内积的内联函数///////////////////////////////
inline double CoverNN::GetInnerProduct(const double* a, const double* b, const int dim)
{
	double result = 0;

	for(int i=0; i<dim; i++)
	{
		result += a[i]*b[i];
	}

	return result;
}

/////////////求距离的内联函数/////////////////////////////////
inline double CoverNN::GetDistance(const double* a, const double* b, const int dim)
{
	double result = 0;

	for(int i=0; i<dim; i++)
	{
		result += pow( (a[i]-b[i]) , 2);
	}

	return sqrt(result);
}

//////////求平移点//////////////
int CoverNN::GetTranslationpoint( CovCell &cen )
{
	int i,j,k = 0;
	int * P_B = new int[Dim_in+1];
	int allpt = 0, times = 0;
	double d;
	double * pt_proj = new double[Dim_in+1];//投影点（垂足）
	double * temp = new double[Dim_in+1];
	double ** Ei = new double*[Dim_in+1];
	for(i=0;i<=Dim_in;i++)//Ei[0]并未使用
	{
		Ei[i] = new double[Dim_in+1];
	}

	k = GetSet_minDist(cen, P_B);//求与oldPt距离最近的非本类的样本点集，返回值为样本点的个数

	if(k==0)//如果k==0则平移出错，函数返回
		return 1;

	for(i=0;i<Num;i++)//-----------如果无法找到足够的点，将终止循环--------------
	{
		if(NoCov[i] && Target[i] != cen.kind)
		{
			allpt++;
		}
	}