libsvm代码阅读：关于Kernel类分析

比眉伴天荒 2022-08-25 08:26 181阅读 0赞

*update：2014-2-27 LinJM @HQU 『 libsvm专栏地址：[http://blog.csdn.net/column/details/libsvm.html][http_blog.csdn.net_column_details_libsvm.html] 』*

这一篇博文来分析下Kernel类，代码上很简单，一般都能看懂。Kernel类主要是为SVM的核函数服务的，里面实现了SVM常用的核函数，通过函数指针来使用这些核函数。

其中几个常用核函数如下所示：（一般情况下，使用RBF核函数能取得很好的效果）

![SouthEast][]

关于基类QMatrix在Kernel中的作用并不明显，只是定义了一些纯虚函数，Kernel继承这些函数，Kernel只对swap\_index进行了定义。其余的get\_Q和get\_QD在Kernel并没有用到。

class QMatrix {
    public:
    	virtual Qfloat *get_Q(int column, int len) const = 0;//纯虚函数，在子类中实现，important！
    	virtual double *get_QD() const = 0;
    	virtual void swap_index(int i, int j) const = 0;
    	virtual ~QMatrix() {}
    };

Kernel类的定义函数，比较简单就不细说。

class Kernel: public QMatrix {
    public:
    	Kernel(int l, svm_node * const * x, const svm_parameter& param);
    	virtual ~Kernel();
    
    	static double k_function(const svm_node *x, const svm_node *y,
    				 const svm_parameter& param);
    	virtual Qfloat *get_Q(int column, int len) const = 0;
    	virtual double *get_QD() const = 0;
    	virtual void swap_index(int i, int j) const	// no so const...
    	{
    		swap(x[i],x[j]);
    		if(x_square) swap(x_square[i],x_square[j]);
    	}
    protected:
    
    	double (Kernel::*kernel_function)(int i, int j) const;
    
    private:
    	const svm_node **x;//用来指向样本数据，每次数据传入时通过克隆函数来实现，完全重新分配内存，主要是为处理多类着想
    	double *x_square;//使用RBF 核才使用
    
    	// svm_parameter
    	const int kernel_type;
    	const int degree;
    	const double gamma;
    	const double coef0;
    
    	static double dot(const svm_node *px, const svm_node *py);
    
    	double kernel_linear(int i, int j) const
    	{
    		return dot(x[i],x[j]);
    	}
    	double kernel_poly(int i, int j) const
    	{
    		return powi(gamma*dot(x[i],x[j])+coef0,degree);
    	}
    	double kernel_rbf(int i, int j) const
    	{
    		return exp(-gamma*(x_square[i]+x_square[j]-2*dot(x[i],x[j])));
    	}
    
    	double kernel_sigmoid(int i, int j) const
    	{
    		return tanh(gamma*dot(x[i],x[j])+coef0);
    	}
    	double kernel_precomputed(int i, int j) const
    	{
    		return x[i][(int)(x[j][0].value)].value;
    	}
    };

这个Kernel类的函数比较清晰，我直接把它的全部代码贴出。

**全部代码如下：**

//
    // Kernel evaluation
    //
    // the static method k_function is for doing single kernel evaluation
    // the constructor of Kernel prepares to calculate the l*l kernel matrix
    // the member function get_Q is for getting one column from the Q Matrix
    //
    class QMatrix {
    public:
    	virtual Qfloat *get_Q(int column, int len) const = 0;
    	virtual double *get_QD() const = 0;
    	virtual void swap_index(int i, int j) const = 0;
    	virtual ~QMatrix() {}
    };
    
    class Kernel: public QMatrix {
    public:
    	Kernel(int l, svm_node * const * x, const svm_parameter& param);//构造函数
    	virtual ~Kernel();
    
    	static double k_function(const svm_node *x, const svm_node *y,
    				 const svm_parameter& param);
    	virtual Qfloat *get_Q(int column, int len) const = 0;
    	virtual double *get_QD() const = 0;
    	virtual void swap_index(int i, int j) const	// no so const...
    	{
    		swap(x[i],x[j]);
    		if(x_square) swap(x_square[i],x_square[j]);
    	}
    protected:
    
    	double (Kernel::*kernel_function)(int i, int j) const;
    
    private:
    	const svm_node **x;//用来指向样本数据，每次数据传入时通过克隆函数来实现，完全重新分配内存，主要是为处理多类着想
    	double *x_square;//使用RBF 核才使用
    
    	// svm_parameter
    	const int kernel_type;
    	const int degree;
    	const double gamma;
    	const double coef0;
    
    	static double dot(const svm_node *px, const svm_node *py);
    
    	double kernel_linear(int i, int j) const
    	{
    		return dot(x[i],x[j]);
    	}
    	double kernel_poly(int i, int j) const
    	{
    		return powi(gamma*dot(x[i],x[j])+coef0,degree);
    	}
    	double kernel_rbf(int i, int j) const
    	{
    		return exp(-gamma*(x_square[i]+x_square[j]-2*dot(x[i],x[j])));
    	}
    
    	double kernel_sigmoid(int i, int j) const
    	{
    		return tanh(gamma*dot(x[i],x[j])+coef0);
    	}
    	double kernel_precomputed(int i, int j) const
    	{
    		return x[i][(int)(x[j][0].value)].value;
    	}
    };
    
    //构造函数，初始化类中的部分常量，指定核函数，克隆样本数据。如果使用RBF核函数，则计算x_square[i]
    Kernel::Kernel(int l, svm_node * const * x_, const svm_parameter& param)
    :kernel_type(param.kernel_type), degree(param.degree),
     gamma(param.gamma), coef0(param.coef0)
    {
    	switch(kernel_type)
    	{
    		case LINEAR:
    			kernel_function = &Kernel::kernel_linear;
    			break;
    		case POLY:
    			kernel_function = &Kernel::kernel_poly;
    			break;
    		case RBF:
    			kernel_function = &Kernel::kernel_rbf;
    			break;
    		case SIGMOID:
    			kernel_function = &Kernel::kernel_sigmoid;
    			break;
    		case PRECOMPUTED:
    			kernel_function = &Kernel::kernel_precomputed;
    			break;
    	}
    
    	clone(x,x_,l);//void clone(T*& dst, S* src, int n)
    
    	if(kernel_type == RBF)
    	{
    		x_square = new double[l];
    		for(int i=0;i<l;i++)
    			x_square[i] = dot(x[i],x[i]);
    	}
    	else
    		x_square = 0;
    }
    
    Kernel::~Kernel()
    {
    	delete[] x;
    	delete[] x_square;
    }
    
    double Kernel::dot(const svm_node *px, const svm_node *py)
    {
    	double sum = 0;
    	while(px->index != -1 && py->index != -1)
    	{
    		if(px->index == py->index)
    		{
    			sum += px->value * py->value;
    			++px;
    			++py;
    		}
    		else
    		{
    			if(px->index > py->index)
    				++py;
    			else
    				++px;
    		}			
    	}
    	return sum;
    }
    
    double Kernel::k_function(const svm_node *x, const svm_node *y,
    			  const svm_parameter& param)
    {
    	switch(param.kernel_type)
    	{
    		case LINEAR:
    			return dot(x,y);
    		case POLY:
    			return powi(param.gamma*dot(x,y)+param.coef0,param.degree);
    		case RBF:
    		{
    			double sum = 0;
    			while(x->index != -1 && y->index !=-1)
    			{
    				if(x->index == y->index)
    				{
    					double d = x->value - y->value;
    					sum += d*d;
    					++x;
    					++y;
    				}
    				else
    				{
    					if(x->index > y->index)
    					{	
    						sum += y->value * y->value;
    						++y;
    					}
    					else
    					{
    						sum += x->value * x->value;
    						++x;
    					}
    				}
    			}
    
    			while(x->index != -1)
    			{
    				sum += x->value * x->value;
    				++x;
    			}
    
    			while(y->index != -1)
    			{
    				sum += y->value * y->value;
    				++y;
    			}
    			
    			return exp(-param.gamma*sum);
    		}
    		case SIGMOID:
    			return tanh(param.gamma*dot(x,y)+param.coef0);
    		case PRECOMPUTED:  //x: test (validation), y: SV
    			return x[(int)(y->value)].value;
    		default:
    			return 0;  // Unreachable 
    	}
    }

本文地址：[http://blog.csdn.net/linj\_m/article/details/19574623][http_blog.csdn.net_linj_m_article_details_19574623]

微博：[林建民-机器视觉][-]

[http_blog.csdn.net_column_details_libsvm.html]: http://blog.csdn.net/column/details/libsvm.html
[SouthEast]: /images/20220824/858f4bd772b949d28a9040c8d8568033.png
[http_blog.csdn.net_linj_m_article_details_19574623]: http://blog.csdn.net/linj_m/article/details/19574623
[-]: http://weibo.com/cengineer