train.cpp

网页分类器

/*==========================================================   
    *   
    *         Copyright   (c)   2008   
    *         All   rights   reserved.   
    *   
    *         文件名称：   Train.cpp 
    *         摘    要：   训练得到支持向量   
    *   
    *         当前版本：   1.0   
    *         作    者：   祝美莲   
    *         创建日期：   2008-5-10   
    *   
    *==========================================================   
*/ 
// Train.cpp: implementation of the CTrain class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "DeTreeSVM.h"
#include "Train.h"
#include "math.h"
#include "DeTreeSVMDlg.h"

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

extern CDeTreeSVMDlg   *p;
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////


/********************************************************************
       // 创建日期   :  2008-5-19 21:02:33
	   // 作    者	  : 祝美莲<[e-mail]> 
       // 函数名称	  : CTrain::CTrain
       // 函数功能	  : 构造函数
       // 返回类型	  : 
       // 函数参数	  : CPageInfo *P
       // 函数参数	  : int nKindNumber
       // 函数参数	  : int nItemNumber
       // 函数参数	  : int nPNumber
********************************************************************/
CTrain::CTrain(CPageInfo *P, int nKindNumber, int nItemNumber, int nPNumber)
{
	tolerance = 0.001;
	eps	= 0.001;
	delta_b	= 0;
	b = 0;
	Page = P;
	dPenalty = 5;
	dSigma = 4;
	this->nKindNumber = nKindNumber;
	nVectorItemNumber = nItemNumber;
	nPageNumber = nPNumber;
}

CTrain::~CTrain()
{

}

/********************************************************************
       // 创建日期   :  2008-5-19 21:02:48
	   // 作    者	  : 祝美莲<[e-mail]> 
       // 函数名称	  : CTrain::SetKind
       // 函数功能	  : 函数设置标签设置为1和-1两类
       // 返回类型	  : void 
       // 函数参数	  : int nKind
********************************************************************/
void CTrain::SetKind( int nKind )
{
	for( int i = 0;i < nPageNumber; i++ )
	{
		if( nKind == Page[i].GetType() )//相同的话y值设为1
			nType[i] =  1;
		else
			nType[i] = -1;//不同，设置为-1
	}

}

/********************************************************************
       // 创建日期   :  2008-5-19 21:03:02
	   // 作    者	  : 祝美莲<[e-mail]> 
       // 函数名称	  : CTrain::Transform
       // 函数功能	  : 将数据转化为密集数据来简化计算
       // 返回类型	  : void 
       // 函数参数	  :  int i
       // 函数参数	  : double VX[VECTORITEMNUMBER]
********************************************************************/
void CTrain::Transform( int i, double VX[VECTORITEMNUMBER] )
{
	int n = 0;
	VectorItem vi;//特征向量的一个分量

	vi = Page[i].GetCharacterVector( n );//从第一个开始转化

	//将所有没有的索引补充上，权值设为0
	for( int j= 0; j< nVectorItemNumber; j++)
	{		
		if( j== vi.nIndex )
		{
			VX[j] = vi.dPower;
			n++;
			if( n < Page[i].GetSize() )
				vi = Page[i].GetCharacterVector( n );//取下一个数据
		}
		else
			VX[j] = 0;//没有出现的权值赋为0
	}
}

/********************************************************************
       // 创建日期   :  2008-5-19 21:03:43
	   // 作    者	  : 祝美莲<[e-mail]> 
       // 函数名称	  : CTrain::DotMetrix
       // 函数功能	  : 计算两个向量的点积
       // 返回类型	  : double 
       // 函数参数	  : double VX1[VECTORITEMNUMBER]
       // 函数参数	  : double VX2[VECTORITEMNUMBER]
********************************************************************/
double CTrain::DotMetrix(double VX1[VECTORITEMNUMBER],double VX2[VECTORITEMNUMBER])
{
	double sum = 0;//初值
	//两个向量计算点积的方法计算
	for( int i = 0; i < nVectorItemNumber; i++ )
		sum += VX1[i] * VX2[i];

	return sum;
}

/********************************************************************
       // 创建日期   :  2008-5-19 21:03:57
	   // 作    者	  : 祝美莲<[e-mail]> 
       // 函数名称	  : CTrain::Kernel
       // 函数功能	  : RBF核函数
       // 返回类型	  : double 
       // 函数参数	  :  int i
       // 函数参数	  : int j
********************************************************************/
double CTrain::Kernel( int i, int j )
{
	double VX1[VECTORITEMNUMBER],VX2[VECTORITEMNUMBER];
	double dTemp[VECTORITEMNUMBER];
	Transform( i, VX1 );//转换存放的形式
	Transform( j, VX2 );
	for( int k = 0; k < nVectorItemNumber; k++ )
		dTemp[k] = VX1[k] - VX2[k];
	return exp( - (DotMetrix( dTemp, dTemp ) / ( dSigma * dSigma )));//求得核函数的值
}

/********************************************************************
       // 创建日期   :  2008-5-19 21:04:10
	   // 作    者	  : 祝美莲<[e-mail]> 
       // 函数名称	  : CTrain::ObjectFunc
       // 函数功能	  : 计算第K个特征向量当前的目标函数
       // 返回类型	  : double 
       // 函数参数	  : int k
********************************************************************/
double CTrain::ObjectFunc(int k)
{
	double sum = 0;
	//f(x) = ∑yi*ai*K(i,j) - b 
	for( int i = 0; i < nPageNumber; i++ )
		if( dAlph[i] > 0 )
			sum += dAlph[i] * nType[i] * Kernel(i,k);//求和
	sum -= b;

	return sum;
}

/********************************************************************
       // 创建日期   :  2008-5-19 21:05:34
	   // 作    者	  : 祝美莲<[e-mail]> 
       // 函数名称	  : CTrain::ExamineExample
       // 函数功能	  : 该函数检查第一个变量是否违背KKT条件，如果不满足KKT条件，则
						寻找第二个权向量，调用takeStep函数，更新两个权值,
						如果有权向量被更新，则返回1否则返回0 
       // 返回类型	  : int 
       // 函数参数	  : int i1  待优化的因子
********************************************************************/
int CTrain::ExamineExample( int i1 )
{
	int y1;			//标记值
	double alph1;	//Lagrange乘子
	double E1;		//错误率
	double r1;		//y1*E1的临时变量,判断KKT条件的变量

	//设置初值
	y1 = nType[i1];
	alph1 = dAlph[i1];

	//设置E1的初值
	if( alph1 > 0 && alph1 < dPenalty )
		E1 = dErrorCache[i1];
	else
		E1 = ObjectFunc(i1) - y1;
	
	r1 = y1 * E1;//设置r1的值

	if(( r1 < - tolerance && alph1 < dPenalty ) || ( r1 > tolerance && alph1 > 0 ))//不满足KKT条件
	{
		//寻找第二个权值更新，并返回，寻找|E1-E2|最大的
		{
			int k, i2;//k,循环变量,i2,第二个待优化的Lagrange乘子
			double tmax;//存放最大的|E1-E2|的值
			
			//赋初值
			i2	 = -1;
			tmax =  0;

			//循环以找到要优化的第二个Lagrange乘子的下标
			for( k = 0; k < nPageNumber; k++ )
				if( dAlph[k] > 0 && dAlph[k] < dPenalty )
				{
					double E2;	//错误率
					double temp;//临时变量,存放两个错误率的差的绝对值
					
					E2 = dErrorCache[k];//赋值
					temp = fabs( E1 - E2 );
				
					if( temp > tmax )	//查找最大的temp
					{
						tmax = temp;
						i2 = k;
					}
				}
			
			if( i2 >= 0 )//表示找到了第二个Lagrange乘子
			{
				if( TakeStep( i1, i2 ) )//优化第i1,i2个Lagrange乘子
					return 1;
			}
		}
		//从随机位置开始寻找非边界样本
		{
			int k;	//循环变量,
			int k0;	//随机产生的访问位置
			int i2;	//第i2个Lagrange乘子

			//产生k0
			k0 = (int)(( rand() / RAND_MAX ) * nPageNumber );

			//循环查找i2
			for( k = k0; k < nPageNumber + k0; k++ )
			{
				i2 = k % nPageNumber;
				if( dAlph[i2] > 0 && dAlph[i2] < dPenalty )//非边界样本的条件
				{
					if( TakeStep(i1, i2) )//优化第i1,i2个Lagrange乘子
						return 1;
				}
			}
		}
		//从随机位置开始寻找整个样本
		{
			int k0;	//随即产生的查询位置
			int k;	//循环变量
			int i2;	//第i2个Lagrange乘子

			k0 = (int)( ( rand() / RAND_MAX ) * nPageNumber );//产生k0
		
			for( k = k0; k < nPageNumber + k0; k++ )//循环查找i2
			{
				i2 = k % nPageNumber;
				if( TakeStep( i1, i2 ) )//找到,优化第i1,i2个Lagrange乘子
					return 1;
			}
		}
	}
	return 0;
}

/********************************************************************
       // 创建日期   :  2008-5-19 21:06:11
	   // 作    者	  : 祝美莲<[e-mail]> 
       // 函数名称	  : CTrain::TakeStep
       // 函数功能	  : 优化两个拉格朗日乘子