cvm.h

Ball Vector Machine (BVM)支撑向量机C++程序项目代码

#ifndef _CVM_H_
#define _CVM_H_

#include "random.h"
#include "svm.h"
#include "utility.h"

#define RELEASE_VER 1
//#define COMP_STAT 1

#define SMO_EPS			1e-3
#define PREDICT_BND		4e-6
#define E_NUM_CV		15000
#define INITIAL_CS		20
#define INITIAL_EPS		0.1
#define EPS_SCALING		0.5

// API for CVDD (MEB)
void solve_cvdd(
	const svm_problem *prob, const svm_parameter* param,
	double *alpha, Solver::SolutionInfo* si);

// API for CVM (CCMEB)
void solve_cvm(
	const svm_problem *prob, const svm_parameter* param,
	double *alpha, Solver::SolutionInfo* si, double Cp, double Cn);

// API for CVR (CCMEB)
void solve_cvr(
	const svm_problem *prob, const svm_parameter* param,
	double *alpha, Solver::SolutionInfo* si);


//------------------------------------------------------------------------------------------------------------------

//
// Sparse caching for kernel evaluations
//
// l is the number of total data items
// size is the cache size limit in bytes
//
class sCache
{
public:
	sCache(const svm_parameter* param_, int num);
	virtual ~sCache();

	Qfloat* get_data(int idx, int basisNum, int& numRet);
	bool has_data(int idx) { return (head[idx].len > 0); } 

protected:		
	struct shead_t
	{
		shead_t *prev, *next;	// a cicular list
		Qfloat *data;
		int len;		// data[0,len) is cached in this entry
		int max_len;
		int refcount;
	};

	shead_t *head;
	shead_t lru_head;
	void lru_delete(shead_t *h);
	void lru_insert(shead_t *h);

	int numData;
	int maxItem;	
};

//------------------------------------------------------------------------------------------------------------------

//
// Gram matrix of CVDD
//
class CVDD_Q : public Kernel
{
public:
	CVDD_Q(const svm_problem* prob_, const svm_parameter* param_) : Kernel(prob_->l, prob_->x, *param_)
	{
		// init
		int i;
		prob  = prob_;
		param = param_;
		QD    = new Qfloat[prob->l];
		C_inv = (Qfloat)(1.0/(param->C));
		
		// get diagonal
		if (Kernel::IsSelfConst(*param))
		{	
			Eta = (Qfloat)((this->*kernel_function)(0,0) + C_inv);
			for (i=0; i< prob->l; i++)
				QD[i] = Eta;
		}
		else
		{	
			Eta = 0.0;
			for (i=0; i< prob->l; i++)	
			{
				QD[i] = (Qfloat)((this->*kernel_function)(i, i) + C_inv);
				if (QD[i] > Eta)
					Eta = QD[i];
			}	
		}		

		kernelCache = new sCache(param_, prob->l);
		kernelEval  = 0;
	}

	~CVDD_Q()
	{
		delete kernelCache;
		delete [] QD;		
	}

	Qfloat* get_Q(int idx, int basisNum, int* basisIdx) const
	{
		int numRet;
		Qfloat *Q = kernelCache->get_data(idx, basisNum, numRet);
		if (Q != NULL)
		{	
#ifdef COMP_STAT
			kernelEval += (basisNum - numRet);
#endif

			// fill remaining		 
			for(int i = numRet; i < basisNum; i++)
			{
				int idx2 = basisIdx[i];
				if (idx != idx2)		
					Q[i] = (Qfloat)((this->*kernel_function)(idx, idx2));
				else				
					Q[i] = QD[idx];
			}						
		}
		return Q;
	}
	
	double dist2c_wc(int idx, int basisNum, int* basisIdx, double *coeff, double cNorm)
	{
		double dist = 0.0;		
		Qfloat *Q_i = get_Q(idx, basisNum, basisIdx);			
		if (Q_i != NULL)
		{
			for (int j=0; j<basisNum; j++)
				dist += Q_i[j]*coeff[j];		
			dist  = cNorm - 2.0 * dist;				
		}		
		return dist;
	}
	
	Qfloat* get_QD() const { return QD; }	
	Qfloat get_Eta() const { return Eta; }
	Qfloat get_Kappa() const { return Eta-C_inv; }
	void swap_index(int i, int j) const { printf("CVDD_Q::swap_index is not implemented!\n"); }

private:
	const svm_parameter* param;
	const svm_problem* prob;	
	Qfloat C_inv;

	Qfloat Eta;	
	Qfloat *QD;

	sCache *kernelCache;
	mutable int kernelEval;	
};

//------------------------------------------------------------------------------------------------------------------


//
// Gram matrix of CVM
//
class CVC_Q : public Kernel
{
public:
	CVC_Q(const svm_problem* prob_, const svm_parameter* param_, schar *y_) : Kernel(prob_->l, prob_->x, *param_)
	{
		// init
		int i;
		prob  = prob_;
		param = param_;
		y     = y_;
		QD    = new Qfloat[prob->l];		
		C_inv = (Qfloat)(1.0/(param->C));

		// get diagonal
		if (Kernel::IsSelfConst(*param))
		{	
			Eta = (Qfloat)((this->*kernel_function)(0,0) + 1.0 + C_inv);
			for (i=0; i< prob->l; i++)
				QD[i] = Eta;
		}
		else
		{
			double tmp = 1.0 + C_inv;
			Eta        = 0.0;
			for (i=0; i< prob->l; i++)	
			{
				QD[i] = (Qfloat)((this->*kernel_function)(i, i) + tmp);
				if (QD[i] > Eta)
					Eta = QD[i];
			}	
		}		

		kernelCache = new sCache(param_, prob->l);
		kernelEval  = 0;
	}

	~CVC_Q()
	{
		delete kernelCache;
		delete [] QD;		
	}

	Qfloat* get_Q(int idx, int basisNum, int* basisIdx) const
	{
		int numRet;
		Qfloat *Q = kernelCache->get_data(idx, basisNum, numRet);
		if (Q != NULL)
		{	
#ifdef COMP_STAT
			kernelEval += (basisNum - numRet);
#endif

			// fill remaining		 
			for(int i = numRet; i < basisNum; i++)
			{
				int idx2 = basisIdx[i];
				if (idx != idx2)		
					Q[i] = y[idx]*y[idx2]*(Qfloat)((this->*kernel_function)(idx, idx2) + 1.0);			
				else				
					Q[i] = QD[idx];
			}						
		}
		return Q;
	}
	
	double dist2c_wc(int idx, int basisNum, int* basisIdx, double *coeff, double cNorm)
	{
		double dist = 0.0;		
		Qfloat *Q_i = get_Q(idx, basisNum, basisIdx);			
		if (Q_i != NULL)
		{
			for (int j=0; j<basisNum; j++)
				dist += Q_i[j]*coeff[j];		
			dist  = cNorm - 2.0 * dist;				
		}		
		return dist;
	}
	
	Qfloat* get_QD() const { return QD; }	
	Qfloat get_Eta() const { return Eta; }
	Qfloat get_Kappa() const { return Eta-C_inv; }
	void swap_index(int i, int j) const { printf("CVC_Q::swap_index is not implemented!\n"); }

private:
	const svm_parameter* param;
	const svm_problem* prob;	
	schar* y;
	Qfloat C_inv;

	Qfloat Eta;	
	Qfloat *QD;

	sCache *kernelCache;
	mutable int kernelEval;	
};

//------------------------------------------------------------------------------------------------------------------

//
// Gram matrix of CVM
//
class CVR_Q : public Kernel
{
public:
	CVR_Q(const svm_problem* prob_, const svm_parameter* param_) : Kernel(prob_->l, prob_->x, *param_)
	{
		// init
		int i;
		int numVar = 2*prob_->l;
		prob	   = prob_;
		param      = param_;
		QD         = new Qfloat[numVar];
		LinCoef    = new double[numVar];
		C_MU_inv   = (Qfloat)(param->mu*prob->l/param->C);	
		double tmp = 2.0/param->C;
		
		// get diagonal
		if (Kernel::IsSelfConst(*param))
		{
			Kappa         = (Qfloat)((this->*kernel_function)(0,0) + 1.0);		
			double Kappa2 = Kappa + C_MU_inv;
			Eta           = 0.0;
			for (i=0; i < prob->l; i++)
			{
				QD[i]              =  (Qfloat)Kappa2;
				QD[i+prob->l]      =  (Qfloat)Kappa2;
				double tmpLinCoef  =  prob->y[i]*tmp;				
				LinCoef[i]		   =  tmpLinCoef;
				LinCoef[i+prob->l] = -tmpLinCoef;
				Eta                =  max(Eta, Kappa2+tmpLinCoef);
				Eta                =  max(Eta, Kappa2-tmpLinCoef);
			}
		}
		else
		{
			double tmp = 1.0 + C_MU_inv;
			Eta        = 0.0;
			Kappa      = 0.0;
			for (i=0; i < prob->l; i++)	
			{
				double Kappa2	   =  (this->*kernel_function)(i, i) + tmp;
				QD[i]			   =  (Qfloat)Kappa2;
				QD[i+prob->l]	   =  (Qfloat)Kappa2;
				double tmpLinCoef  =  prob->y[i]*tmp;			
				LinCoef[i]		   =  tmpLinCoef;
				LinCoef[i+prob->l] = -tmpLinCoef;
				Eta                =  max(Eta, Kappa2+tmpLinCoef);
				Eta                =  max(Eta, Kappa2-tmpLinCoef);
				if (Kappa2 > Kappa)
					Kappa = (Qfloat)Kappa2;
			}	
			Kappa -= C_MU_inv;
		}		
		for (i=0; i < numVar; i++)	
			LinCoef[i] += Eta;
				
		buffer[0]   = new Qfloat[numVar];
		buffer[1]   = new Qfloat[numVar];
		next_buffer = 0;
		kernelCache = new sCache(param_, prob->l);
		kernelEval  = 0;
	}

	~CVR_Q()
	{
		delete kernelCache;		
		delete [] QD;		
		delete [] LinCoef;
		delete buffer[0];