2024年4月15日发(作者：)

数据挖掘平台文档 Confidential

LibSVM-2.8程序代码注释

刘国平(*******************)

2005-08-06

上海交通大学图像处理与模式识别研究所 －1－

数据挖掘平台文档 Confidential

我不经心地，服下你调好的毒

我知道今后我将万劫不复

但是你的红唇仍让我屈服

四月的樱花火红满天

我和你的梦，却要一以何处去缱绻？

虽然人间的情爱万万千千

世上已有太多崩毁的誓言

七个黑夜，七个白天

我为你写下的歌，彩绘的纸笺

却只能随着晚风

飘在大海的岸边

我仍愿服下你精心为我调好的毒

从你那深情的吻

吞下我与你在人间

最后的流光万千辗转朱颜……

上海交通大学图像处理与模式识别研究所 －2－

数据挖掘平台文档 Confidential

第一章 LibSVM结构

一、文件结构

整个LibSVM由两个文件组成，

svm.h

,

。其中

svm.h

中定义了使用LibSVM所需要的

数据结构和函数。

数据结构：

struct svm_node ：数据节点，每个节点只是单个样本矢量中的一个特征。

struct svm_problem ：数据集，存放所有样本矢量的数据结构。

struct svm_parameter ： SVM参数。

其实应该还有一个数据结构存放在头文件中：

struct svm_model ： 训练好的训练模型。

二、类结构图

其中有两组关键的类：

1、 QMatrix类： 包括QMatrix, Kernel, SVC_Q, SVR_Q, ONE_CLASS_Q;

2、 Solver类： 包括Solver, Solver_NU;

cd Logical Model

<>

svm_problem

+ l: int

+ y: double*

+ <> x: svm_node**

<>

svm_node

+ index: int

+ value: double

<>

svm_parameter

svm_type: int

kernel_type: int

degree: double

gamma: double

coef0: double

cache_size: double

eps: double

C: double

nr_weight: int

weight_label: int*

weight: double*

nu: double

p: double

shrinking: int

probability: int

<>

+

+

+

+

LINEAR: int

POLY: int

RBF: int

SIGMOID: int

<>

+

+

+

+

+

C_SVC: int

NU_SVC: int

ONE_CLASS: int

EPSILON_SVR: int

NU_SVR: int

+

+

+

+

<>

+

svm_model

+

+ param: svm_parameter+

+ nr_class: int

+param

+

+ l: int+

+ SV: svm_node**+

+ sv_coef: double**+

+ rho: double*+

+ probA: double*+

+ probB: double*+

+ label: int*+

+ nSV: int*

+ free_sv: int

<>

Solver::SolutionInfo

+

+

+

+

+

obj: double

rho: double

upper_bound_p: double

upper_bound_n: double

r: double

+si

Solver_NU

+

+

-

-

-

Solver_NU()

Solve(int, QMatrix&, double*, schar*, double*, double, double, double, SolutionInfo*, int) : void

select_working_set(int&, int&) : int

calculate_rho() : double

do_shrinking() : void

Solver

<>

Cache::head_t

+

+

+

+

prev: head_t*

*: head_t*

data: Qfloat*

len: int

+head

Cache

+

+

+

+

-

-

Cache(int, int)

+cache

~Cache()

get_data(int, Qfloat**, int) : int

swap_index(int, int) : void

lru_delete(head_t*) : void

lru_insert(head_t*) : void

+cache

+cache

+

+

+

+

+

<>

Solver::

+ LOWER_BOUND: int

+ UPPER_BOUND: int

+ FREE: int

+

+

+

#

#

#

#

#

#

#

#

#

#

#

Solver()

~Solver()

Solve(int, QMatrix&, double*, schar*, double*, double, double, double, SolutionInfo*, int) : void

get_C(int) : double

update_alpha_status(int) : void

is_upper_bound(int) : bool

is_lower_bound(int) : bool

is_free(int) : bool

swap_index(int, int) : void

reconstruct_gradient() : void

select_working_set(int&, int&) : int

max_violating_pair(int&, int&) : int

calculate_rho() : double

do_shrinking() : void

+prev

<>

SVR_Q

SVR_Q(svm_problem&, svm_parameter&)

swap_index(int, int) : void

get_Q(int, int) : Qfloat*

get_QD() : Qfloat*

~SVR_Q()

+Q

QMatrix

ONE_CLASS_Q

+ <> get_Q(int, int) : Qfloat*

+ <> get_QD() : Qfloat*

+ <> swap_index(int, int) : void

<>

+

+

+

+

+

ONE_CLASS_Q(svm_problem&, svm_parameter&)

get_Q(int, int) : Qfloat*

get_QD() : Qfloat*

swap_index(int, int) : void

~ONE_CLASS_Q()

+

+

+

+

+

+

#

-

-

-

-

-

Kernel

Kernel(int, svm_node*, svm_parameter&)

~Kernel()

k_function(svm_node*, svm_node*, svm_parameter&) : double

<> get_Q(int, int) : Qfloat*

<> get_QD() : Qfloat*

swap_index(int, int) : void

double(Kernel*)

dot(svm_node*, svm_node*) : double

kernel_linear(int, int) : double

kernel_poly(int, int) : double

kernel_rbf(int, int) : double

kernel_sigmoid(int, int) : double

<>

decision_function

+ alpha: double*

+ rho: double

SVC_Q

-

-

-

+

+

+

+

+

y: schar*

cache: Cache*

QD: Qfloat*

SVC_Q(svm_problem&, svm_parameter&, schar*)

get_Q(int, int) : Qfloat*

get_QD() : Qfloat*

swap_index(int, int) : void

~SVC_Q()

(矢量图，可以调整放大倍数)

上海交通大学图像处理与模式识别研究所 －3－

数据挖掘平台文档 Confidential

第二章： 头文件SVM.h

本文件只是定义了若干个结构体，和若干接口函数。严格的来说，它们并不是接口函数，

因为实际上整个代码里面，可以直接访问的函数还有其他。但事实上，如果仅仅是应用一下这份

代码的话，只要知道这几个函数就可以了。

2.1 struct svm_node

struct svm_node

{

};

struct svm_node用来存储单一向量中的单个特征，例如：

向量 x1={ 0.002, 0.345, 4, 5.677};

那么用struct svm_node来存储时就使用一个包含5个svm_node的数组来存储此4维向量，内

存映象如下：

1

0.002

1

0.002

2

0.345

2

0.345

3

4．000

4

4．000

4

5.677

5

5.677

－1

空

－1

空

int index;

double value;

其中如果value为0.00,该特征将不会被存储，其中(特征3)被跳过：

0.00不保留的好处在于，做点乘

(xy)

的时候，可以加快计算速度，对于稀疏矩阵，更能充分

体现这种数据结构的优势。但做归一化时，操作就比较麻烦了。（类型转换不再说明）

2.2 struct svm_problem

struct svm_problem

{

};

struct svm_problem存储本次参加运算的所有样本（数据集），及其所属类别。在某些数据挖

掘实现中，常用DataSet来实现。

int l;记录样本总数

double *y;指向样本所属类别或者回归值的数组。在多类问题中，因为使用了one-agianst-one

方法，可能原始样本中y[i]的内容是1.0，2.0，3.0，…,也就是属于类别1，2，3，但但参与多类

计算时，参加分类的两类所对应的y[i]内容是+1,和－1。

Struct svm_node **x;指向一个存储内容为指针的数组；

int l;

double *y;

struct svm_node **x;

上海交通大学图像处理与模式识别研究所 －4－

数据挖掘平台文档 Confidential

如下图,最右边的四个长条格同上表，存储三维数据。(黑边框的是最主要的部分)

这样的数据结构有一个直接的好处，可以用x[i][j]来访问其中的某一元素（如果value为0.00

的也全部保留的话）。

私下认为其中有一个败笔，就是把svm_node* x_space放到结构外面去了。

Y[0]

Y[1]

Y[2]

Y[3]

L=4

Y*

X**

2.3 enums

enum { C_SVC, NU_SVC, ONE_CLASS, EPSILON_SVR, NU_SVR }; /* svm_type */

enum { LINEAR, POLY, RBF, SIGMOID }; /* kernel_type */

支持向量机类型以及若干文献：

C-SVC :

C.J.C. Burges. A tutorial on support vector machines for pattern recognition.

Data Mining

and Knowledge Discovery

, 2(2):955-974, 1998.

NU_SVC :

(待补充)

2.4 struct svm_parameter

struct svm_parameter

{

/* these are for training only */

double cache_size; /* in MB */

double eps; /* stopping criteria */

double C; /* for C_SVC, EPSILON_SVR and NU_SVR */

/* for C_SVC */

/* for C_SVC */

int nr_weight;

int svm_type;//SVM类型，见前enum

int kernel_type;//核函数

double degree;

double gamma;

/* for poly */

/* for poly/rbf/sigmoid */

double coef0; /* for poly/sigmoid */

int *weight_label; /* for C_SVC */

double* weight;

double nu; /* for NU_SVC, ONE_CLASS, and NU_SVR */

－5－ 上海交通大学图像处理与模式识别研究所

数据挖掘平台文档 Confidential

};

double p; /* for EPSILON_SVR */

int shrinking; /* use the shrinking heuristics */

int probability; /* do probability estimates */

部分参数解释,(附核函数)

1、

K(x

i

,x

j

)x

i

T

x

j

T

2、

K

(

x

i

,

x

j

)(



x

i

3、

K

(

x

i

,

x

j

)

x

j



r

)

d

,



0

2



exp(





x

i

x

j

),





0

T

4、

K(x

i

,x

j

)



tanh(



x

i

x

j



r)

double degree;//就是2式中的d

double gamma; //就是2,3,4式中的gamma

double coef0;//就是2,4式中的r

double cache_size;

double eps;

double C;

int nr_weight;

int *weight_label;

double nu;

double p;

int shrinking;

int probability;

//

/* in MB */ 制定训练所需要的内存，默认是40M，LibSVM2.5中是4M,

所以自己做开发选LibSVM2.5还是不错的！

见参考文献[1]中式3.13

//没什么好说的，惩罚因子，越大训练的模型越那个…,当然耗的时间越

多

//权重的数目,目前在实例代码中只有两个值，一个是默认0，另外一个

是svm_binary_svc_probability函数中使用数值2。

//权重，元素个数由nr_weight决定

没什么好说的,看代码中的注释,too

没什么好说的,看代码中的注释,three

指明训练过程是否使用缩减

指明训练过程是否需要预报概率。

2.5 struct struct svm_model

struct svm_model

{

svm_parameter param; // parameter

int nr_class;

int l;

// number of classes, = 2 in regression/one class svm

// SVs (SV[l])

// total #SV

svm_node **SV;

double *rho;

double **sv_coef; // coefficients for SVs in decision functions (sv_coef[n-1][l])

// constants in decision functions (rho[n*(n-1)/2])

－6－ 上海交通大学图像处理与模式识别研究所

数据挖掘平台文档 Confidential

};

double *probA; // pariwise probability information

double *probB;

// for classification only

int *label;

int *nSV;

// XXX

int free_sv;

// 1 if svm_model is created by svm_load_model

// 0 if svm_model is created by svm_train

// label of each class (label[n])

// number of SVs for each class (nSV[n])

// nSV[0] + nSV[1] + ... + nSV[n-1] = l

结构体svm_model用于保存训练后的训练模型，当然原来的训练参数也必须保留。本来这

个结构体应该是在

中，为统一起见，一起描述。

svm_parameter

param;

int nr_class;

int l;

svm_node **SV;

训练参数,这里使用的是svm_param的实例，而不是指针。这样训练完成后，

原来参数被完全保留，再去预报时，就不用担心下次训练会把参数冲掉

类别数

支持向量数

保存支持向量的指针，至于支持向量的内容，如果是从文件中读取，内容

会额外保留；如果是直接训练得来，则保留在原来的训练集中。如果训练

完成后需要预报，原来的训练集内存不可以释放。

double **sv_coef;

double *rho;

double *probA;

double *probB;

int *label;

int *nSV;

int free_sv;

相当于判别函数中的

alpha

相当于判别函数中的

b

pariwise probability information

label of each class (label[n])

number of SVs for each class (nSV[n])

1 if svm_model is created by svm_load_model； 0 if svm_model is

created by svm_train

2.6 接口函数

//以下接口函数设计得非常合理，最后一节详细说明

//最主要的驱动函数，训练数据

struct svm_model *svm_train(const struct svm_problem *prob, const struct svm_parameter

*param);

//用SVM做交叉验证

void svm_cross_validation(const struct svm_problem *prob, const struct svm_parameter

上海交通大学图像处理与模式识别研究所 －7－

数据挖掘平台文档 Confidential

*param, int nr_fold, double *target);

//保存训练好的模型到文件

int svm_save_model(const char *model_file_name, const struct svm_model *model);

//从文件中把训练好的模型读到内存中

struct svm_model *svm_load_model(const char *model_file_name);

//得到数据集的SVM类型（必须经过训练得到模型后才可以用）

int svm_get_svm_type(const struct svm_model *model);

//得到数据集的类别数（必须经过训练得到模型后才可以用）

int svm_get_nr_class(const struct svm_model *model);

//得到数据集的类别标号（必须经过训练得到模型后才可以用）

void svm_get_labels(const struct svm_model *model, int *label);

//LibSvm2.6新增函数

double svm_get_svr_probability(const struct svm_model *model);

//用训练好的模型预报样本的值，输出结果保留到数组中。（并非接口函数）

void svm_predict_values(const struct svm_model *model, const struct svm_node *x, double*

dec_values);

//预报某一样本的值

double svm_predict(const struct svm_model *model, const struct svm_node *x);

// LibSvm2.6新增函数

double svm_predict_probability(const struct svm_model *model, const struct svm_node *x,

double* prob_estimates);

//消除训练的模型，释放资源

void svm_destroy_model(struct svm_model *model);

// LibSvm2.6新增函数

void svm_destroy_param(struct svm_parameter *param);

//检查输入的参数，保证后面的训练能正常进行。

const char *svm_check_parameter(const struct svm_problem *prob, const struct

svm_parameter *param);

// LibSvm2.6新增函数

int svm_check_probability_model(const struct svm_model *model);

上海交通大学图像处理与模式识别研究所 －8－

数据挖掘平台文档 Confidential

第三章： 文件

3.1 宏

.头文件：

从整个

.cpp

文件来看，感觉有些头文件是多余的，不知何故，反正多包含头文件不会犯错。

后面的typedef,特别是typedef float Qfloat,是为了方便控制内存存储的精度。

#include

#include

#include

#include

#include

#include

#include

#include "svm.h"

typedef float Qfloat;

typedef signed char schar;

//.以下是定义的几个主要的模板，主要是为了比较大小，交换数据和完全复制数据。

Min()和Max()在中提供了相应的函数，这里的处理是为了兼容Microsoft VC++编译

器。因为VC对标准模板库(STL)支持得不是很好。下面对min, max的处理方法非常经典。

#ifndef min

template inline T min(T x,T y) { return (x

#endif

#ifndef max

template inline T max(T x,T y) { return (x>y)?x:y; }

#endif

//这里的克隆函数是完全克隆，不同于一般的复制。操作结束后，内部的所有数据和指针完全一

样。

template inline void swap(T& x, T& y) { T t=x; x=y; y=t; }

template inline void clone(T*& dst, S* src, int n)

{

}

//这里使用了define，非内联函数

#define Malloc(type,n) (type *)malloc((n)*sizeof(type))

一般来说，在cpp中使用delete比较正规，在c中使用malloc比较正规。LibSVM比较好地贯彻了这

点，malloc用在接口函数中。

上海交通大学图像处理与模式识别研究所 －9－

dst = new T[n];

memcpy((void *)dst,(void *)src,sizeof(T)*n);

数据挖掘平台文档 Confidential

//以下的函数用作调试。跳过～

#if 1

void info(char *fmt,...)

{

}

void info_flush()

{

}

#elsevoid info(char *fmt,...) {}

void info_flush() {}

#endif

//以下部分为中的类继承和组合图: (实线表示继承关系，虚线表示组合关系)，更正规

的图例见第一章。

Solver_NU

Kernel

Cache

SVC_Q

SVR_Q

ONE_CLASS_Q

Solver

fflush(stdout);

va_list ap;

va_start(ap,fmt);

vprintf(fmt,ap);

va_end(ap);

3.2 类Cache

本类主要负责运算所涉及的内存的管理，包括申请、释放等。本类对理解核心代码关系不

大，如果弄不清楚影响也不大。可以跳过。

类定义:

class Cache

{

public:

Cache(int l,int size);

~Cache();

int get_data(const int index, Qfloat **data, int len);

void swap_index(int i, int j); // future_option

int l;

－10－

private:

上海交通大学图像处理与模式识别研究所

数据挖掘平台文档 Confidential

};

int size;

struct head_t

{

};

head_t* head;

head_t lru_head;

void lru_delete(head_t *h);

void lru_insert(head_t *h);

head_t *prev, *next; // a cicular list

Qfloat *data;

int len; // data[0,len) is cached in this entry

成员变量：

head_t* head; //变量指针，该指针用来记录程序所申请的内存，单块申请到的内存用

struct head_t来记录所申请内存的指针，并记录长度。而且通过双向的指针，形成链表，增加寻

址的速度。记录所有申请到的内存，一方面便于释放内存，另外方便在内存不够时适当释放一部

分已经申请到的内存。

head_t lru_head; //双向链表的头。

int l; //样本总数。

int size; //所指定的全部内存，据说用Mb做单位。

成员函数：

void lru_delete(head_t *h); //从双向环形链表中删除某个元素的链接，不删除、不释放该

元素所涉及的内存。一般是删除当前所指向的元素。

void lru_insert(head_t *h); //在链表后面插入一个新的链接；其实就是在lru_head后添加。

（环形的嘛）

Cache(int l,int size);

构造函数。该函数根据样本数L，申请L个head_t的空间。根据说明，该区域会初始化为0。

Lru_head因为尚没有head_t中申请到内存，故双向链表指向自己。至于size的处理，先将原

来的byte数目转化为float的数目，然后扣除L个head_t的内存数目。size为程序指定的内存

大小4M/40M。size不要设得太小。

int get_data(const int index, Qfloat **data, int len);

该函数保证head_t[index]中至少有len个float的内存，并且将可以使用的内存块的指针放

Head

New

上海交通大学图像处理与模式识别研究所 －11－

数据挖掘平台文档 Confidential

在data指针中。返回值为申请到的内存。

函数首先将head_t[index]从链表中断开,如果head_t[index]原来没有分配内存，则跳过断开

这步。计算当前head_t[index]已经申请到的内存，如果不够，释放部分内存（怀疑这样做的动

机：老数据为什么就可以释放，而不真的另外申请一块？老数据没用了？），等内存足够后，重

新分配内存。重新使head_t[index]进入双向链表。并返回申请到的内存的长度。

//返回值不为申请到的内存的长度，为head_t[index]原来的数据长度h->len。

调用该函数后，程序会计算

Q



yyK(x,x)

的值，并将其填入data所指向的内存区

ijij

域，如果下次index不变，正常情况下，不用重新计算该区域的值。若index不变，则get_data()

返回值len与本次传入的len一致，从Kernel::get_Q( )中可以看到，程序不会重新计算。从而

提高运算速度。

While循环内的部分基本上难得用到一次。

void swap_index(int i, int j);

交换head_t[i] 和head_t[j]的内容，先从双向链表中断开，交换后重新进入双向链表中。对

后面的处理不理解，可能是防止中head_t[i] 和head_t[j]可能有一方并未申请内存。但h->len >

i和 h->len > j无法解释。

for(head_t *h = lru_; h!=&lru_head; h=h->next)

{

}

if(h->len > i)

{

}

if(h->len > j)

else

{

}

// give up

lru_delete(h);

free(h->data);

size += h->len;

h->data = 0;

h->len = 0;

swap(h->data[i],h->data[j]);

后注：这部分内容我几次读过，都不太清楚，如果有谁弄懂了，请告知。

3.3 类QMatrix

class QMatrix {

public:

virtual Qfloat *get_Q(int column, int len) const = 0;

virtual Qfloat *get_QD() const = 0;

virtual void swap_index(int i, int j) const = 0;

上海交通大学图像处理与模式识别研究所 －12－

数据挖掘平台文档 Confidential

};

纯虚类。理论上用户只要能在需要的时候，提供必要的数据，就可以实现其它的变形支持向

量机。用户可以自己实现数据矩阵（很大的哦），然后直接提供给Solver。

3.4 类Kernel

class Kernel {

public:

private:

};

成员变量：

const svm_node **x; //用来指向样本数据，每次数据传入时通过克隆函数来实现，完全重

新分配内存，主要是为处理多类着想。

double *x_square; //使用RBF核才使用。

const int kernel_type; //核函数类型.

const double degree; // kernel_function

上海交通大学图像处理与模式识别研究所 －13－

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&

virtual Qfloat *get_Q(int column, int len) const = 0;

virtual void swap_index(int i, int j) const // no

{

}

double (Kernel::*kernel_function)(int i, int j) const;

swap(x[i],x[j]);

if(x_square) swap(x_square[i],x_square[j]);

param);

protected:

const svm_node **x;

double *x_square;

// svm_parameter

const int kernel_type;

const double 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(skipped)

double kernel_poly(int i, int j) const(skipped)

double kernel_rbf(int i, int j) const(skipped)

double kernel_sigmoid(int i, int j) const(skipped)

数据挖掘平台文档 Confidential

const double gamma; // kernel_function

const double coef0; // kernel_function

成员函数：

Kernel(int l, svm_node * const * x, const svm_parameter& param);

构造函数。初始化类中的部分常量、指定核函数、克隆样本数据。如果使用RBF核函数，

则计算x-sqare[i].

static double dot(const svm_node *px, const svm_node *py);

点乘两个样本数据，按svm_node中index (一般为特征)进行运算，一般来说，index中1，

2，…直到-1。返回点乘总和。

例如：x1 = { 1,2,3} , x2 = {4, 5, 6} 总和为sum = 1*4 + 2*5 + 3*6 ;在svm_node[3]中

存储index = -1时，停止计算。

static double k_function(const svm_node *x, const svm_node *y, const svm_parameter&

param);

核函数。但只有在预报时才用到。

其中RBF部分很有讲究。因为存储时，0值不保留。如果所有0值都保留，第一个while

就可以都做完了；如果第一个while做不完，在x，y中任意一个出现index ＝ -1，第一个while

就停止，剩下的代码中两个while只会有一个工作，该循环直接把剩下的计算做完。

virtual Qfloat *get_Q(int column, int len) const = 0;

virtual Qfloat *get_QD() const = 0;

纯虚函数，将来在子类中实现。相当重要的函数。

virtual void swap_index(int i, int j)

虚函数，x[i]和x[j]中所存储指针的内容。如果x_square不为空，则交换相应的内容。

double (Kernel::*kernel_function)(int i, int j) const;

函数指针，根据相应的核函数类型，来决定所使用的函数。在计算矩阵Q时使用。

Q



y

i

y

j

K(x

i

,x

j

)

1、

K(x

i

,x

j

)x

i

T

x

j

T

2、

K

(

x

i

,

x

j

)(



x

i

3、

K

(

x

i

,

x

j

)

x

j



r

)

d

,



0

2



exp(





x

i

x

j

),





0

T

4、

K(x

i

,x

j

)



tanh(



x

i

x

j



r)

上海交通大学图像处理与模式识别研究所 －14－

数据挖掘平台文档 Confidential

3.4 类Solver

class Solver {

public:

double get_C(int i) { }

} void update_alpha_status(int i) {

void Solve(int l, const Kernel& Q, const double *b_, const schar *y_,

double *alpha_, double Cp, double Cn, double eps,

SolutionInfo* si, int shrinking);

struct SolutionInfo {

};

double obj;

double rho;

double upper_bound_p;

double upper_bound_n;

double r; // for Solver_NU

Solver() {};

virtual ~Solver() {};

protected:

int active_size;

schar *y;

double *G; // gradient of objective function

// LOWER_BOUND, UPPER_BOUND, FREE

enum { LOWER_BOUND, UPPER_BOUND, FREE };

char *alpha_status;

double *alpha;

const Kernel *Q;

double eps;

double Cp,Cn;

double *b;

int *active_set;

double *G_bar;

int l;

bool unshrinked; // XXX

// gradient, if we treat free variables as 0

bool is_upper_bound(int i) { return alpha_status[i] == UPPER_BOUND; }

bool is_lower_bound(int i) { return alpha_status[i] == LOWER_BOUND; }

bool is_free(int i) { return alpha_status[i] == FREE; }

void swap_index(int i, int j);

void reconstruct_gradient();

virtual int select_working_set(int &i, int &j);

virtual double calculate_rho();

上海交通大学图像处理与模式识别研究所 －15－

数据挖掘平台文档 Confidential

};

virtual void do_shrinking();

成员变量：

int active_size; // 计算时实际参加运算的样本数目，经过shrink处理后，该数目会小于全

部样本总数。

schar *y; //样本所属类别，该值只取+1/-1 。虽然可以处理多类，最终是用两类SVM完成

的。

double *G; //梯度，计算公式如下(公式3.5)[1]：

(Q



p)

t

f(



)

t

G

t

在代码实现中，用b[i]来代替公式中的

p

。

char *alpha_status; //



[i]

的状态，根据情况分为



[i]0

,



[i]c

和

0



[i]0

，分

别对应内部点(非SV)，错分点(BSV)和支持向量(SV)。

double *alpha; //



i

const Kernel *Q; //指定核。核函数和Solver相互结合，可以产生多种SVC,SVR

double eps; //误差限

double *b; //见double *G的说明。

int *active_set; //

double *G_bar;





//

G

,（这名字取的）。计算公式如下：

GC



Q

ij

,i1,...,l



j

C

该值可以在对样本集做shrink时，减小重建梯度的计算量。

GG

_

0C





Q

ij



j



Q

ij



j

j1

l

int l; //样本总数

bool unshrinked; //

成员函数：

double get_C(int i)

返回对应于样本的C。 设置不同的Cp和Cn是为了处理数据的不平衡。见 《 6 Unbalanced

data》[1]，有时Cp=Cn。

void swap_index(int i, int j);

完全交换样本i和样本j的内容，包括所申请的内存的地址。

void reconstruct_gradient();

重新计算梯度。G_bar[i]在初始化时并未加入b[i]，所以程序首先增加b[i]。Shrink后依然

参加运算的样本位于active_size和L-1位置上。在0～active_size之间的alpha[i]如果在区间(0,c)

上海交通大学图像处理与模式识别研究所 －16－

数据挖掘平台文档 Confidential

上，才有必要更新相应的active_size和L-1位置上的样本的梯度。

virtual int select_working_set(int &i, int &j)

选择工作集。公式如下：

iargmax({f(



)

t

|y

t

1,



t

C},{f(



)

t

|y

t

1,



t

0}

jargmin({f(



)

t

|y

t

1,



t

C},{f(



)

t

|y

t

1,



t

0}

virtual void do_shrinking();

对样本集做缩减。大致是当

0



迭代。（

0



献。

C

时，(还有两种情况)程序认为该样本可以不参加下次

C

时，为内部点）程序会减小active_size，为（内部点）增加位置。active_size

表明了不可以参加下次迭代的样本的最小标号，在active_size与L之间的元素都对分类没有贡

程序中k--是为了消除交换后的影响，使重新换来的样本也被检查一次。

如果程序在缩减一次后没有达到结束条件，就重新构造梯度矢量，并再缩减一次（总觉得这

里不太严密）。

virtual double calculate_rho();

计算



值。见3.7[1]节，

The calculation of

b

or



r

1





0



C,yi1

f(



)

i

1



0



C,yi1





r

1

r

2

2

void Solve(int l, const Kernel& Q, const double *b_, const schar *y_,

double *alpha_, double Cp, double Cn, double eps,

SolutionInfo* si, int shrinking);

//程序较大，逐步分解

part 1

// initialize alpha_status

{

}

更新一下alpha的状态

part 2

// initialize active set (for shrinking)

{

active_set = new int[l];

alpha_status = new char[l];

for(int i=0;i

update_alpha_status(i);

上海交通大学图像处理与模式识别研究所 －17－

数据挖掘平台文档 Confidential

}

for(int i=0;i

active_set[i] = i;

active_size = l;

为缩减做准备，将来要做交换

part 3

// initialize gradient

{

}

G_bar[j]的生成公式如下：（注意，其中不包含b[i]的值）



G = new double[l];

G_bar = new double[l];

int i;

for(i=0;i

{

}

for(i=0;i

if(!is_lower_bound(i))

{

}

Qfloat *Q_i = _Q(i,l);

double alpha_i = alpha[i];

int j;

for(j=0;j

G[j] += alpha_i*Q_i[j];

for(j=0;j

G_bar[j] += get_C(i) * Q_i[j];

if(is_upper_bound(i))

G[i] = b[i];

G_bar[i] = 0;

GC



Q

ij

,i1,...,l



j

C

因为第一次建立G(i),所以没有判断alpha的状态。而是按公式，全部计算了一遍。

get_Q(i,l)返回的值是

Q

ij

矩阵中的第i列，而不是第i行，这是需要注意的地方。

再往下是大循环：

如果有必要，先进行筛选，使部分数据不再参加运算；选择工作集；更新alpha_i, alpha_j,其更

新的思路是保证：



i

new

y

i





new

y

j





i

old

y

i





old

jj

y

j

;对于边界情况，有特殊处理，主要是考

虑

0



i

C

i

的要求。当某一alpha小于0时，做适当调整,调整的结果是alpha_i, alpha_j仍然在

上海交通大学图像处理与模式识别研究所 －18－

数据挖掘平台文档 Confidential

0



i

C

i

范围内，同时其和同原来一样。对于推导过程，可以参考

Sequential Minimal

Optimization for SVM

part 4

更新G(i),根据



i

,



j

的变化更新；

// update G

double delta_alpha_i = alpha[i] - old_alpha_i;

double delta_alpha_j = alpha[j] - old_alpha_j;

for(int k=0;k

{

}

part 5

以下是更新alpha_status 和

G

,ahpha状态更新较简单，根据alpha状态前后是否有变化，

适当更新，更新的内容参考公式

G

// update alpha_status and G_bar

{

bool ui = is_upper_bound(i);

bool uj = is_upper_bound(j);

update_alpha_status(i);

update_alpha_status(j);

int k;

if(ui != is_upper_bound(i))//更新alpha_i的影响

{

}

if(uj != is_upper_bound(j)) //更新alpha_j的影响

{

Q_j = _Q(j,l);

if(uj)

for(k=0;k

Q_i = _Q(i,l);

if(ui)

else

for(k=0;k

G_bar[k] += C_i * Q_i[k];

for(k=0;k

G_bar[k] -= C_i * Q_i[k];



_

G[k] += Q_i[k]*delta_alpha_i + Q_j[k]*delta_alpha_j;

C



Q

ij

,i1,...,l



j

C

上海交通大学图像处理与模式识别研究所 －19－

数据挖掘平台文档 Confidential

}

}

else

G_bar[k] -= C_j * Q_j[k];

for(k=0;k

G_bar[k] += C_j * Q_j[k];

part 6

以下计算目标函数值，因为

G

t

(Q



p)

t

，而目标值为

// calculate objective value

}

part 7

回送结果。

// put back the solution

{

}

2.3 类Solver_NU

class Solver_NU : public Solver

{

public:

Solver_NU() {}

void Solve(int l, const Kernel& Q, const double *b, const schar *y,

{

}

SolutionInfo *si;

int select_working_set(int &i, int &j);

double calculate_rho();

this->si = si;

Solver::Solve(l,Q,b,y,alpha,Cp,Cn,eps,si,shrinking);

double *alpha, double Cp, double Cn, double eps,

SolutionInfo* si, int shrinking)

for(int i=0;i

alpha_[active_set[i]] = alpha[i];

si->obj = v/2;

{

double v = 0;

int i;

for(i=0;i

v += alpha[i] * (G[i] + b[i]);

1

T



Q



p

T



，故：

2

private:

上海交通大学图像处理与模式识别研究所 －20－

数据挖掘平台文档 Confidential

void do_shrinking();

};

其中函数 void Solve()完全调用了Solve::Solve(),this->si = si;一句是因为C++内部变量访问的限

制而添加。

成员函数：

int select_working_set(int &i, int &j);

选择工作集，参考[1],[4],[5],同时可以参考Solver::select_working_set。

double calculate_rho();

计算



值，参考[1],[4],[5]（对应libsvm论文[1]，其实返回值是

b

,这可以从后面预测目标

值可以看出。与Solver::calculate_rho相比，增加了另外一个返回值，

r

，该值才是真正的



值。

void do_shrinking();

对样本进行剪裁，参考[1],[4],[5] ,同时可以参考Solver::do_shrinking()。

3.5 类SVC_Q

class SVC_Q: public Kernel

{

public:

void swap_index(int i, int j) const

{

－21－

SVC_Q(const svm_problem& prob, const svm_parameter& param, const schar *y_)

:Kernel(prob.l, prob.x, param)

{

}

Qfloat *get_Q(int i, int len) const

{

}

Qfloat *data;

int start;

if((start = cache->get_data(i,&data,len)) < len)

{

}

return data;

for(int j=start;j

data[j] = (Qfloat)(y[i]*y[j]*(this->*kernel_function)(i,j));

clone(y,y_,prob.l);

cache = new Cache(prob.l,(int)(_size*(1<<20)));

上海交通大学图像处理与模式识别研究所

数据挖掘平台文档 Confidential

};

}

cache->swap_index(i,j);

Kernel::swap_index(i,j);

swap(y[i],y[j]);

~SVC_Q()

{

}

schar *y;

Cache *cache;

delete[ ] y;

delete cache;

private:

说明：

SVC_Q(const svm_problem& prob, const svm_parameter& param, const schar *y_)

get_Q(int i, int len)函数与其他同类相比，在于核函数不同。

swap_index(int i, int j) //交换的东西太多了点

:Kernel(prob.l, prob.x, param)

该构造函数利用初始化列表Kernel(prob.l, prob.x, param)将样本数据和参数传入(非常简洁)。

3.6 类ONE_CLASS_Q

class ONE_CLASS_Q: public Kernel

{

public:

ONE_CLASS_Q(const svm_problem& prob, const svm_parameter& param)

:Kernel(prob.l, prob.x, param)

{

}

Qfloat *get_Q(int i, int len) const

{

Qfloat *data;

int start;

if((start = cache->get_data(i,&data,len)) < len)

{

}

return data;

－22－

cache = new Cache(prob.l,(int)(_size*(1<<20)));

for(int j=start;j

data[j] = (Qfloat)(this->*kernel_function)(i,j);

上海交通大学图像处理与模式识别研究所

数据挖掘平台文档 Confidential

};

}

void swap_index(int i, int j) const

{

}

~ONE_CLASS_Q()

{

}

Cache *cache;

delete cache;

cache->swap_index(i,j);

Kernel::swap_index(i,j);

private:

说明：

ONE_CLASS_Q只处理1类分类问题(?)，故不保留y[i]。编号只有1类。

get_Q(int i, int len)函数中缺少了y[i],y[j]，这与One_Class本身特点有关，只处理一类。

swap_index(int i, int j)少swap(y[i],y[j]);这句，因为根本没有y[i]可供交换。

3.7 类SVR_Q

class SVR_Q: public Kernel

{

public:

~SVR_Q()

－23－

SVR_Q(const svm_problem& prob, const svm_parameter& param)

:Kernel(prob.l, prob.x, param)

{

}

void swap_index(int i, int j) const

{

}

Qfloat *get_Q(int i, int len) const

{

//skipped

}

swap(sign[i],sign[j]);

swap(index[i],index[j]);

//skipped

上海交通大学图像处理与模式识别研究所

数据挖掘平台文档 Confidential

};

{

//skipped

}

int l;

Cache *cache;

schar *sign;

int *index;

mutable int next_buffer;

Qfloat* buffer[2];

private:

本类主要是用于做回归，同分类有许多不同之处。参考[1],[5]

//以下的函数全为静态函数，只能在本文件范围内被访问。对照[1]中公式查看。

2.6 函数solve_c_svc

static void solve_c_svc(const svm_problem *prob, const svm_parameter* param,

double *alpha, Solver::SolutionInfo* si, double Cp, double Cn)

在公式

1

T



Q



p

T



中，

p

T

为全-1,另外alpha[i]=0,保证

y

T



0

的限制条件，在将来选

2

择工作集后更新alpha时，仍能保证该限制条件。

2.7 函数solve_nu_svc

static void solve_nu_svc(

const svm_problem *prob, const svm_parameter *param,

double *alpha, Solver::SolutionInfo* si)

p

T

为全0,alpha[i]能保证

e

T



0,y

T



0

.

2.8 函数solve_one_class

static void solve_one_class(const svm_problem *prob, const svm_parameter *param,

double *alpha, Solver::SolutionInfo* si)

TT



vl

，前

vl

个alpha为1，此后的alpha全为0，初始条件满足限制条件

e



vl

限制条件

e

p

T

为全0，y为全1

2.9 函数solve_epsilon_svr

static void solve_epsilon_svr(const svm_problem *prob, const svm_parameter *param,

2.10 函数solve_nu_svr

static void solve_nu_svr(

上海交通大学图像处理与模式识别研究所 －24－

double *alpha, Solver::SolutionInfo* si)

const svm_problem *prob, const svm_parameter *param,

double *alpha, Solver::SolutionInfo* si)

数据挖掘平台文档 Confidential

第四章： 接口函数、流程

decision_function svm_train_one(const svm_problem *prob, const svm_parameter *param,

double Cp, double Cn)

训练一组样本集，通常参加训练的样本集只有两类，由程序将参与训练的样本重新分为两类(+1,

-1)。

程序根据相应的参数，选择所使用的训练或者拟合算法。(这个地方的代码居然如此少)，最后统

计SV和BSV，最后输出决策函数。

Cp, Cn这里可以使用不同的权重系数。

void sigmoid_train(

LibSVM2.6新增函数

根据预报值来确定A,B

r

ij



double sigmoid_predict(double decision_value, double A, double B)

LibSVM2.6新增函数

可以看看，里面的公式很简单。

void multiclass_probability(int k, double **r, double *p)

LibSVM2.6新增函数

(好像比较复杂哦☺ )

void svm_binary_svc_probability(const svm_problem *prob, const svm_parameter *param,

double Cp, double Cn, double& probA, double& probB)

LibSVM2.6新增函数

先做交叉验证，然后用决策值来做概率估计。需要调用sigmoid_train函数。

double svm_svr_probability( const svm_problem *prob, const svm_parameter *param)

LibSVM2.6新增函数

先做交叉验证，然后函数经过计算后，输出概率值。

svm_model *svm_train(const svm_problem *prob, const svm_parameter *param)

根据选择的算法，来组织参加训练的分样本，以及进行训练结果的保存。其中会对样本进行初步

的统计。

一、分类部分：

→统计类别总数,同时记录类别的标号，统计每个类的样本数目

→将属于相同类的样本分组，连续存放

→计算权重C

→训练n(n-1)/2个模型

→初始化nozero数组，便于统计SV(nozero和SV关联)

int l, const double *dec_values, const double *labels,

double& A, double& B)

1

1e

ˆ

BAf

见第8节[1],其中A,B的确定就由本函数确定。

上海交通大学图像处理与模式识别研究所 －25－

数据挖掘平台文档 Confidential

→//初始化概率数组

→训练过程中，需要重建子数据集，样本的特征不变，但样本的类别要改为+1/-1

→//如果有必要，先调用svm_binary_svc_probability

→训练子数据集svm_train_one

→统计一下nozero,如果nozero已经是真，就不变，如果为假，则改为真

→输出模型

二、回归部分：

→类别数固定为2

→//选择性地做svm_svr_probability, one-class不做概率估计

→训练

→输出模型

→清除内存

分类说明：

一对一(One-Against-One,1v1):对n类数据，每次选择其中两类，其余的类不考虑。被选择

的两类数据，数据所属的类标号被重新标记为+1/-1，针对该两类训练出一个模型，这样就可以

训练出n*(n-1)/2个模型。预报时，将测试样本用所有训练好的模型进行预报，得到n(n-1)/2个预

报值，根据预报值对n类进行投票，得票最多的为最终的预报值，表明测试样本的归属。如果存

在一个以上的类别得票相同，将随机选择一个。（图3）

一对多(One-Against-Rest,1vr)对n类数据，每次选择一类，剩下的所有类作为一类。训练时，

对数据所属类别标号重新标记。训练完毕时可以得到n个模型。预报时，将测试样本进行预报，

共n个预报值。(预报值如果全部是+1/-1的话，就麻烦了)可以根据预报值的大小来判别属于某一

类。（图2）

训练过程函数调用：

svm_train→svm_train_one→solve_c_svc(fox example)→

void svm_cross_validation(const svm_problem *prob, const svm_parameter *param, int

nr_fold, double *target)

LibSVM2.6新增函数,LibSVM2.5中为示例函数。

先随机打乱次序，然后根据n折的数目，留一份作为测试集，其他的作为训练集，做n次。

随机打乱次序使用的非标准的扑克洗牌的算法。(LibSVM2.5里面随机排序的结果很乱)

→Solver s;//这里调用构造函数，但啥也没有做。

→(l, SVC_Q(*prob,*param,y), minus_ones, y,

alpha, Cp, Cn, param->eps, si,

DAG（有向无环图），训练过程同 1v1，判别总是只涉及类别序列的首尾类，见后图4

→主要是填充svm_model,

→清除内存

param->shrinking);

→调用SVC_Q(Kernel) 类的构造函数，同时也会调用Kernel类的构造函数。在SVC_Q

→Solve函数做完其他部分工作，主要是算法的实现。

类的构造函数中复制目标值(y),同时申请内存，此时激发Cache类,申请内存，构造双向列表等。

For example:

上海交通大学图像处理与模式识别研究所 －26－

数据挖掘平台文档 Confidential

样本集被分为10份；第一次，将样本集的第2～10部分作为整体进行训练，得到一个模型，然后

对样本集的第1部分进行预报，得到一个精度；第二次，将样本集的第1，3～10作为整体训练，

对第二部分进行预报，得到又一个精度，…。最后对10个精度做一下处理（方法很多，不逐一列

出）。

int svm_get_nr_class(const svm_model *model)

获得样本类别数；本函数为典型的马后炮。

void svm_get_labels(const svm_model *model, int* label)

某类样本的标号（样本并不按编号排列，通过标号，可以循序访问样本集）。

double svm_get_svr_probability(const svm_model *model)

访问训练好的模型中的概率值。

void svm_predict_values(const svm_model *model, const svm_node *x, double* dec_values)

预测样本数据目标值；

如果是做分类问题，返回一大堆值，供后续的函数做决策；如果是回归问题，返回一个值。

其中one-v-one方法需要做n(n-1)/2次，产生n(n-1)/2个预报值。

double svm_predict(const svm_model *model, const svm_node *x)

预测，分类问题主要使用了One-to-One方法组织n*(n-1)/2种方法。

如果是分类问题，对预测的n*(n-1)/2个值，做投票处理，票数最高的是预报的类。n*(n-1)/2

个值来自函数void svm_predict_values()。

如果是One-Class,根据预报值的符号，返回+1/-1

如果是回归问题，直接返回该double类型的值。

double svm_predict_probability(

const svm_model *model, const svm_node *x, double *prob_estimates)

LibSVM2.6新增函数

跳过。

int svm_save_model(const char *model_file_name, const svm_model *model)

svm_model *svm_load_model(const char *model_file_name)

void svm_destroy_model(svm_model* model)

以上3个函数均为LibSVM2.5示例程序中的函数，现成为LibSVM2.6的一部分。

看看名字就知道是干什么的了，跟训练好的模型相关的，就不介绍了。

void svm_destroy_param(svm_parameter* param)

LibSVM2.6新增函数

释放权重系数数组的内存。

//检查数据

const char *svm_check_parameter(const struct svm_problem *prob, const struct

svm_parameter *param);

上海交通大学图像处理与模式识别研究所 －27－

数据挖掘平台文档 Confidential

该段代码检查参数的合理性。凡对LibSVM进行增加SVC类型和核函数，都必须修改该文件。

LibSVM2.5在该部分代码会存在内存泄漏，LibSVM2.6中已经修正。

其中需要注意的是，nu的取值的范围，

nu

nMin2

nMaxnMin

其中nMax为样本数最多的类的样本数，nMin为样本数最少的类的样本。

int svm_check_probability_model(const svm_model *model)

LibSVM2.6新增函数

检查概率模型，主要是检查一些限制条件。

附图：

Margin

Figure 1: SVM separation of two data classes - SV points circled.

Class 1

f2(x)

Class 2

f3(x)

f1(x)

Class 3

Figure 2: One-against-rest SVM separation of three data classes

上海交通大学图像处理与模式识别研究所 －28－

数据挖掘平台文档 Confidential

f1,2(x)

Class 1

Class 2

f2,3(x)

f1,3(x)

Class 3

Figure 3: One-against-one SVM separation of three data classes

1

2

3

4

Not 1

2

3

4

1V4

Not 4

1

2

3

Not 3

2V4

Not 4

2

3

1V3

Not 1

Not 2

3

4

3V4

3

2V3

2

1V2

1

2

4

1

Figure 4: Decision DAG SVM

其他：

一、One-v-Rest多类方法

/~cjlin/libsvmtools/1vsall/

二、DDAG多类方法

/~cjlin/libsvmtools/

上海交通大学图像处理与模式识别研究所 －29－

数据挖掘平台文档 Confidential

参考文献：

[1]Chih-Chung Chang and Chih-Jen Lin, LIBSVM : a library for support vector machines, 2001.

Software available at /~cjlin/libsvm

[2]J. Platt. Fast training of support vector machines using sequential minimal

optimization. In B. Scholkopf, C. Burges, and A. Smola, editors, Advances in

kernel methods: support vector learning. MIT Press, 1998.

[3] Sequential Minimal Optimization for SVM

/people/xge/svm/

[4]Chang, C.-C. and C.-J. Lin (2001). Training



_-support vector classifiers: Theory and

algorithms. Neural Computation 13 (9), 2119–2147.

[5]Chang, C.-C. and C.-J. Lin (2002). Training



_support vector regression: Theory and

algorithms. Neural Computation 14 (8), 1959–1977.

上海交通大学图像处理与模式识别研究所 －30－

数据挖掘平台文档 Confidential

后记：

很久没有更新这份文档了，

上海交通大学图像处理与模式识别研究所 －31－