這是我在網(wǎng)上找的pdf轉(zhuǎn)成txt的。希望對(duì)觸svm的新手有點(diǎn)幫助.

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

LibSVM-2.6 程序代碼注釋

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

我不經(jīng)心地，服下你調(diào)好的毒
我知道今后我將萬(wàn)劫不復(fù)
但是你的紅唇仍讓我屈服
四月的櫻花火紅滿天
我和你的夢(mèng)，卻要一以何處去繾綣？
雖然人間的情愛萬(wàn)萬(wàn)千千
世上已有太多崩毀的誓言
七個(gè)黑夜，七個(gè)白天
我為你寫下的歌，彩繪的紙箋
卻只能隨著晚風(fēng)
飄在大海的岸邊
我仍愿服下你精心為我調(diào)好的毒
從你那深情的吻
吞下我與你在人間
最后的流光萬(wàn)千輾轉(zhuǎn)朱顏……

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

第一節(jié)： SVM.h 文件

struct svm_node

{
int index;
double value;

}
;

struct svm_node 用來(lái)存儲(chǔ)單一向量中的單個(gè)特征，例如
：
向量x1={ 0.002, 0.345, 4, 5.677}
;
那么用struct svm_node 來(lái)存儲(chǔ)時(shí)就使用一個(gè)包含5 個(gè)svm_node 的數(shù)組來(lái)存儲(chǔ)此4 維向量，內(nèi)
存
映象如下
：

1 2 3 4 －1
0.002 0.345 4．000 5.677 空

其中如果value 為0.00,該特征將不會(huì)被存儲(chǔ)，其中(特征3)被跳過(guò)：

1 2 4 5 －1
0.002 0.345 4．000 5.677 空

0.00 不保留的好處在于，做點(diǎn)乘的時(shí)候，可以加快計(jì)算速度，對(duì)于稀疏矩陣，更能充分體現(xiàn)這種
數(shù)據(jù)結(jié)構(gòu)的優(yōu)勢(shì)。但做歸一化時(shí)，操作就比較麻煩了。
（類型轉(zhuǎn)換不再說(shuō)明）
struct svm_problem

{
int l;
double *y;
struct svm_node **x;

};

struct svm_problem 存儲(chǔ)本次參加運(yùn)算的所有樣本（數(shù)據(jù)集），及其所屬類別。在某些數(shù)據(jù)挖掘
實(shí)現(xiàn)中，常用DataSet來(lái)實(shí)現(xiàn)。
int l; 記錄樣本總數(shù)
double *y; 指向樣本所屬類別的數(shù)組。在多類問(wèn)題中，因?yàn)槭褂昧薿ne-agianst-one 方法，可能原始
樣本中y[i] 的內(nèi)容是1.0，2.0，3.0，…,但參與多類計(jì)算時(shí)，參加分類的兩類所對(duì)應(yīng)的y[i] 內(nèi)容是+1,
和－1。
Struct svm_node **x;指向一個(gè)存儲(chǔ)內(nèi)容為指針的數(shù)組；
如下圖,最右邊的四個(gè)長(zhǎng)條格同上表，存儲(chǔ)三維數(shù)據(jù)。(黑邊框的是最主要的部分)

L=
4

Y[3]
Y[2]
Y[1]
Y[0]
Y*

X*
*

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

這樣的數(shù)據(jù)結(jié)構(gòu)有一個(gè)直接的好處，可以用x[i][j] 來(lái)訪問(wèn)其中的某一元素（如果value 為0.00
的也全部保留的話）
私下認(rèn)為其中有一個(gè)敗筆，就是把svm_node* x_space 放到結(jié)構(gòu)外面去了。

enum { C_SVC, NU_SVC, ONE_CLASS, EPSILON_SVR, NU_SVR };/* svm_type */
enum { LINEAR, POLY, RBF, SIGMOID }; /* kernel_type */

struct svm_parameter

{
int svm_type;//SVM類型，見前enum
int kernel_type;//核函數(shù)
double degree; /* for poly */
double gamma;/* for poly/rbf/sigmoid */
double coef0; /* for poly/sigmoid */

/* these are for training only */

double cache_size; /* in MB *
/
double eps; /* stopping criteria *
/
double C; /* for C_SVC, EPSILON_SVR and NU_SVR *
/
int nr_weight; /* for C_SVC *
/
int *weight_label; /* for C_SVC *
/
double* weight; /* for C_SVC *
/
double nu; /* for NU_SVC, ONE_CLASS, and NU_SVR *
/
double p; /* for EPSILON_SVR *
/
int shrinking; /* use the shrinking heuristics *
/
int probability; /* do probability estimates *
/

}
;
部分參數(shù)解釋,(附核函數(shù)
)

1、K (xi , xj )
=
xiT x j

2、K (xi , xj )
=
(γxiTx j
+
r)d ,γ>
0

2

3、K (xi , xj )
=
exp(.
γ

xi
.
xj

),γ>
0

4、K (xi , xj )
=
tanh(γxiT x j
+
r)

double degree;//就是2式中的d
double gamma; //就是2,3,4式中的gamma
double coef0;//就是2,4式中的r

double cache_size; /* in MB */ 制定訓(xùn)練所需要的內(nèi)存，默認(rèn)是40M，LibSVM2.5 中是4M, 所以自

己做開發(fā)選LibSVM2.5 還是不錯(cuò)的！

double eps;見參考文獻(xiàn)[1]中式3.13
double C;//沒什么好說(shuō)的，懲罰因子，越大訓(xùn)練的模型越那個(gè)…,當(dāng)然耗的時(shí)間越多

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

int nr_weight;//權(quán)重的數(shù)目,目前在實(shí)例代碼中只有兩個(gè)值，一個(gè)是默認(rèn)0，另外一個(gè)是
svm_binary_svc_probability 函數(shù)中使用數(shù)值2。
int *weight_label;//權(quán)重，元素個(gè)數(shù)由nr_weight 決定.
double nu;// 沒什么好說(shuō)的,too
double p;// 沒什么好說(shuō)的,three

int shrinking;//指明訓(xùn)練過(guò)程是否使用壓縮。
int probability;//新增，指明是否要做概率估計(jì)

struct svm_model

{
svm_parameter param; // parameter
int nr_class; // number of classes, = 2 in regression/one class svm
int l; // total #SV
svm_node **SV; // SVs (SV[l])
double **sv_coef; // coefficients for SVs in decision functions (sv_coef[n-1][l])
double *rho; // constants in decision functions (rho[n*(n-1)/2])
double *probA; // pariwise probability information
double *probB;

// for classification only

int *label; // label of each class (label[n])
int *nSV; // number of SVs for each class (nSV[n])
// nSV[0] + nSV[1] + ... + nSV[n-1] = l
// XXX
int free_sv; // 1 if svm_model is created by svm_load_model
// 0 if svm_model is created by svm_train
};

結(jié)構(gòu)體svm_model 用于保存訓(xùn)練后的訓(xùn)練模型，當(dāng)然原來(lái)的訓(xùn)練參數(shù)也必須保留。
svm_parameter param; // 訓(xùn)練參數(shù)
int nr_class;// 類別數(shù)
int l; // 支持向量數(shù)
svm_node **SV; // 保存支持向量的指針，至于支持向量的內(nèi)容，如果是從文件中讀取，內(nèi)容會(huì)
額外保留；如果是直接訓(xùn)練得來(lái)，則保留在原來(lái)的訓(xùn)練集中。如果訓(xùn)練完成后需要預(yù)報(bào)，原來(lái)的
訓(xùn)練集內(nèi)存不可以釋放。
double **sv_coef;//相當(dāng)于判別函數(shù)中的alpha
double *rho; //相當(dāng)于判別函數(shù)中的b
double *probA; // pariwise probability information
double *probB;//均為新增函數(shù)
int *label; // label of each class (label[n])
int *nSV; // number of SVs for each class (nSV[n])
int free_sv;//見svm_node **SV的注釋

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

//以下接口函數(shù)設(shè)計(jì)得非常合理，最后一節(jié)詳細(xì)說(shuō)
明
//最主要的驅(qū)動(dòng)函數(shù)，訓(xùn)練數(shù)
據(jù)
struct svm_model *svm_train(const struct svm_problem *prob, const struct svm_parameter *param)
;

//用SVM做交叉驗(yàn)
證
void svm_cross_validation(const struct svm_problem *prob, const struct svm_parameter *param, int
nr_fold, double *target)
;

//保存訓(xùn)練好的模型到文
件
int svm_save_model(const char *model_file_name, const struct svm_model *model)
;

//從文件中把訓(xùn)練好的模型讀到內(nèi)存
中
struct svm_model *svm_load_model(const char *model_file_name)
;

/
/

int svm_get_svm_type(const struct svm_model *model)
;

//得到數(shù)據(jù)集的類別數(shù)（必須經(jīng)過(guò)訓(xùn)練得到模型后才可以用
）
int svm_get_nr_class(const struct svm_model *model)
;

//得到數(shù)據(jù)集的類別標(biāo)號(hào)（必須經(jīng)過(guò)訓(xùn)練得到模型后才可以用
）
void svm_get_labels(const struct svm_model *model, int *label)
;

//LibSvm2.6 新增函
數(shù)
double svm_get_svr_probability(const struct svm_model *model)
;

//用訓(xùn)練好的模型預(yù)報(bào)樣本的值，輸出結(jié)果保留到數(shù)組中。（并非接口函數(shù)
）
void svm_predict_values(const struct svm_model *model, const struct svm_node *x, double*
dec_values)
;

//預(yù)報(bào)某一樣本的
值
double svm_predict(const struct svm_model *model, const struct svm_node *x)
;

// LibSvm2.6 新增函
數(shù)
double svm_predict_probability(const struct svm_model *model, const struct svm_node *x, double*
prob_estimates)
;

//消除訓(xùn)練的模型，釋放資
源
void svm_destroy_model(struct svm_model *model)
;

// LibSvm2.6 新增函
數(shù)
void svm_destroy_param(struct svm_parameter *param)
;

//檢查輸入的參數(shù)，保證后面的訓(xùn)練能正常進(jìn)行。

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

const char *svm_check_parameter(const struct svm_problem *prob, const struct svm_parameter
*param)
;

// LibSvm2.6 新增函
數(shù)
int svm_check_probability_model(const struct svm_model *model)
;

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

第二節(jié)： SVM.cpp 文件

.頭文件：
從整個(gè).cpp 文件來(lái)看，感覺有些頭文件是多余的，不知何故，反正多包含頭文件不會(huì)犯錯(cuò)。
后面的typedef, 特別是typedef float Qfloat, 是為了方便控制內(nèi)存存儲(chǔ)的精度。

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <float.h>
#include <string.h>
#include <stdarg.h>
#include "svm.h"
typedef float Qfloat;
typedef signed char schar;

//.以下是定義的幾個(gè)主要的模板，主要是為了比較大小，交換數(shù)據(jù)和完全復(fù)制數(shù)據(jù)。
Min() 和Max() 在<math.h>中提供了相應(yīng)的函數(shù)，這里的處理，估計(jì)是為了使函數(shù)內(nèi)聯(lián)，執(zhí)行速度
會(huì)相對(duì)快一些，而且不同的數(shù)據(jù)類型，存儲(chǔ)方式不同，使用模板會(huì)更有針對(duì)性，也從另外一方面
提高程序性能。

#ifndef min
template <class T> inline T min(T x,T y) { return (x<y)?x:y; }
#endif

#ifndef max
template <class T> inline T max(T x,T y) { return (x>y)?x:y; }
#endif

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

//這里的克隆函數(shù)是完全克隆，不同于一般的復(fù)制。操作結(jié)束后，內(nèi)部的所有數(shù)據(jù)和指針完全一
樣。

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

{
dst = new T[n];
memcpy((void *)dst,(void *)src,sizeof(T)*n);

}

//這里使用了define ，非內(nèi)聯(lián)函數(shù)

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

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

//以下的函數(shù)用作調(diào)試。跳過(guò)～

#if 1
void info(char *fmt,...)
{

va_list ap;
va_start(ap,fmt)
;
vprintf(fmt,ap)
;
va_end(ap)
;

}
void info_flush()
{

fflush(stdout);
}
#elsevoid info(char *fmt,...) {}
void info_flush() {}
#endif

//以下部分為svm.cpp 中的類繼承和組合圖: (實(shí)線表示繼承關(guān)系，虛線表示組合關(guān)系)

Cache
Kernel
ONE_CLASS_
Q

SVC_
Q

SVR_
Q

Solver

Solver_NU

2.1 類Cache
本類主要負(fù)責(zé)運(yùn)算所涉及的內(nèi)存的管理，包括申請(qǐng)、釋放等。
類定義:

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

private:
int l;
int size;
struct head_t

 {

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

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

Qfloat *data;

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

 };

head_t* head;

head_t lru_head;

void lru_delete(head_t *h);

void lru_insert(head_t *h);
};

成員變量：

head_t* head; // 變量指針，該指針用來(lái)記錄程序所申請(qǐng)的內(nèi)存，單塊申請(qǐng)到的內(nèi)存用struct
head_t來(lái)記錄所申請(qǐng)內(nèi)存的指針，并記錄長(zhǎng)度。而且通過(guò)雙向的指針，形成鏈表，增加尋址的速
度。記錄所有申請(qǐng)到的內(nèi)存，一方面便于釋放內(nèi)存，另外方便在內(nèi)存不夠時(shí)適當(dāng)釋放一部分已經(jīng)
申請(qǐng)到的內(nèi)存。

head_t lru_head; //雙向鏈表的頭。

int l; //樣本總數(shù)。

int size; //所指定的全部?jī)?nèi)存，據(jù)說(shuō)用Mb做單位。

成員函數(shù)：

void lru_delete(head_t *h); //從雙向鏈表中刪除某個(gè)元素的鏈接，不刪除、不釋放該元素所
涉及的內(nèi)存。一般是刪除當(dāng)前所指向的元素。

void lru_insert(head_t *h); //在鏈表后面插入一個(gè)新的鏈接；

Head
Lru_head
Cache(int l,int size);

構(gòu)造函數(shù)。該函數(shù)根據(jù)樣本數(shù)L，申請(qǐng)L 個(gè)head_t 的空間。根據(jù)說(shuō)明，該區(qū)域會(huì)初始化為0，
（表示懷疑）。Lru_head 因?yàn)樯袥]有head_t 中申請(qǐng)到內(nèi)存，故雙向鏈表指向自己。至于size 的
處理，先將原來(lái)的byte 數(shù)目轉(zhuǎn)化為float 的數(shù)目，然后扣除L 個(gè)head_t 的內(nèi)存數(shù)目。size 為程序
指定的內(nèi)存大小4M/40M 。size 不要設(shè)得太小。

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

該函數(shù)保證head_t[index] 中至少有l(wèi)en 個(gè)float 的內(nèi)存，并且將可以使用的內(nèi)存塊的指針放在
data 指針中。返回值為申請(qǐng)到的內(nèi)存。

函數(shù)首先將head_t[index] 從鏈表中斷開,如果head_t[index] 原來(lái)沒有分配內(nèi)存，則跳過(guò)斷開這
步。計(jì)算當(dāng)前head_t[index] 已經(jīng)申請(qǐng)到的內(nèi)存，如果不夠，釋放部分內(nèi)存（懷疑這樣做的動(dòng)機(jī)：
老數(shù)據(jù)為什么就可以釋放，而不真的另外申請(qǐng)一塊？老數(shù)據(jù)沒用了？），等內(nèi)存足夠后，重新分
配內(nèi)存。重新使head_t[index] 進(jìn)入雙向鏈表。并返回申請(qǐng)到的內(nèi)存的長(zhǎng)度。

//返回值不為申請(qǐng)到的內(nèi)存的長(zhǎng)度，為head_t[index] 原來(lái)的數(shù)據(jù)長(zhǎng)度h->len 。

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

調(diào)用該函數(shù)后，程序會(huì)計(jì)算Q =
∑
yiy jK (xi , xj ) 的值，并將其填入data 所指向的內(nèi)存區(qū)

域，如果下次index 不變，正常情況下，不用重新計(jì)算該區(qū)域的值。若index 不變，則get_data()
返回值len 與本次傳入的len 一致，從Kernel::get_Q( ) 中可以看到，程序不會(huì)重新計(jì)算。從而提
高運(yùn)算速度。

While 循環(huán)內(nèi)的部分基本上難得用到一次。

void swap_index(int i, int j);

交換head_t[i] 和head_t[j] 的內(nèi)容，先從雙向鏈表中斷開，交換后重新進(jìn)入雙向鏈表中。對(duì)后
面的處理不理解，可能是防止中head_t[i] 和head_t[j] 可能有一方并未申請(qǐng)內(nèi)存。但h->len > i 和
h->len > j 無(wú)法解釋。

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

{
if(h->len > i)
{

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

else

 {

// give up

lru_delete(h)
;
free(h->data)
;
size += h->len;
h->data = 0;
h->len = 0;

}
}
}

2.2 類Kernel
class Kernel {

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 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;

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

private:
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)

};

成員變量：

const svm_node **x; // 用來(lái)指向樣本數(shù)據(jù)，每次數(shù)據(jù)傳入時(shí)通過(guò)克隆函數(shù)來(lái)實(shí)現(xiàn)，完全重新

分配內(nèi)存，主要是為處理多類著想。
double *x_square; //使用RBF 核才使用。
const int kernel_type; //核函數(shù)類型.
const double degree; // kernel_function
const double gamma; // kernel_function
const double coef0; // kernel_function

成員函數(shù)：

Kernel(int l, svm_node * const * x, const svm_parameter& param);
構(gòu)造函數(shù)。初始化類中的部分常量、指定核函數(shù)、克隆樣本數(shù)據(jù)。如果使用RBF 核函數(shù)，
則計(jì)算x-sqare[i].

static double dot(const svm_node *px, const svm_node *py);
點(diǎn)乘兩個(gè)樣本數(shù)據(jù)，按svm_node 中index ( 一般為特征)進(jìn)行運(yùn)算，一般來(lái)說(shuō)，index 中1，2，…
直到-1。返回點(diǎn)乘總和。
例如：x1 = { 1,2,3} , x2 = {4, 5, 6} 總和為sum = 1*4 + 2*5 + 3*6 ; 在svm_node[3] 中存儲(chǔ)index
= -1 時(shí)，停止計(jì)算。

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

核函數(shù)。但只有在預(yù)報(bào)時(shí)才用到。

其中RBF 部分很有講究。因?yàn)榇鎯?chǔ)時(shí)，0 值不保留。如果所有0 值都保留，第一個(gè)while
就可以都做完了；如果第一個(gè)while 做不完，在x，y 中任意一個(gè)出現(xiàn)index ＝ -1，第一個(gè)while
就停止，剩下的代碼中兩個(gè)while 只會(huì)有一個(gè)工作，該循環(huán)直接把剩下的計(jì)算做完。

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

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

純虛函數(shù)，將來(lái)在子類中實(shí)現(xiàn)。相當(dāng)重要的函數(shù)。

virtual void swap_index(int i, int j)
虛函數(shù)，x[i] 和x[j]中所存儲(chǔ)指針的內(nèi)容。如果x_square 不為空，則交換相應(yīng)的內(nèi)容
。

double (Kernel::*kernel_function)(int i, int j) const;
函數(shù)指針，根據(jù)相應(yīng)的核函數(shù)類型，來(lái)決定所使用的函數(shù)。在計(jì)算矩陣Q 時(shí)使用
。

Q =
∑
yiy jK(xi , xj )

1、K (xi , xj )
=
xiT x j

2、K (xi , xj )
=
(γxiTx j
+
r)d ,γ>
0

2

3、K (xi , xj )
=
exp(.
γ

xi
.
xj

),γ>
0

4、K (xi , xj )
=
tanh(γxiT x j
+
r)

2.2 類Solver
class Solver {

public:
Solver() {};
virtual ~Solver() {};

struct SolutionInfo
{
double obj;
double rho;
double upper_bound_p;
double upper_bound_n;
double r; // for Solver_NU

 };

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)
;

protected:
int active_size;
schar *y;
double *G; // gradient of objective function
enum { LOWER_BOUND, UPPER_BOUND, FREE };
char *alpha_status; // LOWER_BOUND, UPPER_BOUND, FREE
double *alpha;

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

const Kernel *Q;
double eps;
double Cp,Cn;
double *b;
int *active_set;
double *G_bar; // gradient, if we treat free variables as 0
int l;
bool unshrinked; // XXX

double get_C(int i) {
}
void update_alpha_status(int i) {
}
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()
;
virtual void do_shrinking()
;

};

成員變量：

int active_size; // 計(jì)算時(shí)實(shí)際參加運(yùn)算的樣本數(shù)目，經(jīng)過(guò)shrink 處理后，該數(shù)目會(huì)小于全部

樣本總數(shù)。
schar *y; //樣本所屬類別，該值只取+1/-1 。雖然可以處理多類，最終是用兩類SVM 完成的。
double *G; //梯度，計(jì)算公式如下(公式3.5)[1]
：

(Qα+
p)t =.f (α)t
=
Gt

在代碼實(shí)現(xiàn)中，用b[i] 來(lái)代替公式中的p。
char *alpha_status; //α[i]的狀態(tài)，根據(jù)情況分為α[i]
≤
0, α[i]
≥
c 和0 <α[i]
<
0 ，分別

對(duì)應(yīng)內(nèi)部點(diǎn)(非SV)，錯(cuò)分點(diǎn)(BSV)和支持向量(SV)。

double *alpha; //αi

const Kernel *Q; //指定核。核函數(shù)和Solver 相互結(jié)合，可以產(chǎn)生多種SVC,SVR
double eps; //誤差限
double *b; //見double *G 的說(shuō)明。
int *active_set; //

.

double *G_bar; // G ,（這名字取的）。計(jì)算公式如下：

.

G
=
C ΣQij ,i
=
1,...,l

α
j =C

該值可以在對(duì)樣本集做shrink 時(shí)，減小重建梯度的計(jì)算量。

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

G
=
G
_
+
∑
Qijαj =Σ(l) Qijα
j
0<α<Cj=1

int l; //樣本總
數(shù)
bool unshrinked; /
/

成員函數(shù)：

double get_C(int i)
返回對(duì)應(yīng)于樣本的C。設(shè)置不同的Cp 和Cn 是為了處理數(shù)據(jù)的不平衡。見《 6 Unbalanced
data 》[1]，有時(shí)Cp=Cn 。

void swap_index(int i, int j)
;
完全交換樣本i 和樣本j 的內(nèi)容，包括所申請(qǐng)的內(nèi)存的地址
。

void reconstruct_gradient();

重新計(jì)算梯度。G_bar[i] 在初始化時(shí)并未加入b[i] ，所以程序首先增加b[i] 。Shrink 后依然參
加運(yùn)算的樣本位于active_size 和L-1 位置上。在0～active_size 之間的alpha[i] 如果在區(qū)間(0,c) 上，
才有必要更新相應(yīng)的active_size 和L-1 位置上的樣本的梯度。

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

選擇工作集。公式如下：

i
≡
argmax({..f (α)t | yt
=
1,αt
<
C},{.f (α)t | yt =.1,αt
>
0}
j
≡
argmin({.f (α)t | yt =.1,αt
<
C},{..f (α)t | yt
=
1,αt
>
0}

virtual void do_shrinking();

對(duì)樣本集做縮減。大致是當(dāng)0 <
α <
C 時(shí)，(還有兩種情況)程序認(rèn)為該樣本可以不參加下次
迭代。（0 <
α <
C 時(shí)，為內(nèi)部點(diǎn)）程序會(huì)減小active_size，為（內(nèi)部點(diǎn)）增加位置。active_size
表明了不可以參加下次迭代的樣本的最小標(biāo)號(hào)，在active_size 與L 之間的元素都對(duì)分類沒有貢
獻(xiàn)。

程序中k--是為了消除交換后的影響，使重新?lián)Q來(lái)的樣本也被檢查一次。
如果程序在縮減一次后沒有達(dá)到結(jié)束條件，就重新構(gòu)造梯度矢量，并再縮減一次（總覺得這
里不太嚴(yán)密）。

virtual double calculate_rho();

計(jì)算
ρ
值。見3.7[1]節(jié)，The calculation of b or
ρ

Σ0 C yi 1.f (α)i

r1
=

1

ΣαC, yi=<<
=<<
0,
α1

ρ=
r1
+
r2

2

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

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_status = new char[l];
for(int i=0;i<l;i++)

update_alpha_status(i);
}
更新一下alpha 的狀態(tài)

part 2

// initialize active set (for shrinking)

 {
active_set = new int[l];
for(int i=0;i<l;i++)

active_set[i] = i;
active_size = l;
}

為縮減做準(zhǔn)備，將來(lái)要做交換

part 3

// initialize gradient

 {
G = new double[l];
G_bar = new double[l];
int i;
for(i=0;i<l;i++)
{

G[i] = b[i];

G_bar[i] = 0;
}
for(i=0;i<l;i++
)

if(!is_lower_bound(i))

{
Qfloat *Q_i = Q.get_Q(i,l)
;
double alpha_i = alpha[i]
;
int j;
for(j=0;j<l;j++
)

G[j] += alpha_i*Q_i[j];
if(is_upper_bound(i))
for(j=0;j<l;j++)

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

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

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

G(.) =
C ΣQij ,i
=
1,...,l

α
j =C

因?yàn)榈谝淮谓(i),所以沒有判斷alpha 的狀態(tài)。而是按公式，全部計(jì)算了一遍。

get_Q(i,l)返回的值是Qij 矩陣中的第i 列，而不是第i 行，這是需要注意的地方。

再往下是大循環(huán)：
如果有必要，先進(jìn)行篩選，使部分?jǐn)?shù)據(jù)不再參加運(yùn)算；選擇工作集；更新alpha_i, alpha_j, 其更新

new new old old

的思路是保證：αi yi +
α
j yj =αi yi +
α
j yj ;對(duì)于邊界情況，有特殊處理，主要是考慮

0 ≤αi
≤
Ci 的要求。當(dāng)某一alpha 小于0時(shí)，做適當(dāng)調(diào)整,調(diào)整的結(jié)果是alpha_i, alpha_j 仍然在

0 ≤αi
≤
Ci 范圍內(nèi)，同時(shí)其和同原來(lái)一樣。對(duì)于推導(dǎo)過(guò)程，可以參考Sequential Minimal

Optimization for SVM

part 4

更新G(i),根據(jù)α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<active_size;k++
)
{
G[k] += Q_i[k]*delta_alpha_i + Q_j[k]*delta_alpha_j;
}

part 5

_

以下是更新alpha_status 和G ,ahpha 狀態(tài)更新較簡(jiǎn)單，根據(jù)alpha 狀態(tài)前后是否有變化，適

.

當(dāng)更新，更新的內(nèi)容參考公式G
=
C ΣQij ,i
=
1,...,l

α
j =C

// update alpha_status and G_bar

{
bool ui = is_upper_bound(i)
;
bool uj = is_upper_bound(j)
;
update_alpha_status(i)
;

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

update_alpha_status(j)
;
int k;
if(ui != is_upper_bound(i))//更新alpha_i 的影
響
{

Q_i = Q.get_Q(i,l)
;
if(ui)
for(k=0;k<l;k++
)
G_bar[k] -= C_i * Q_i[k]
;

else
for(k=0;k<l;k++
)

G_bar[k] += C_i * Q_i[k]
;
}
if(uj != is_upper_bound(j)) //更新alpha_j 的影
響
{

Q_j = Q.get_Q(j,l)
;
if(uj)
for(k=0;k<l;k++
)
G_bar[k] -= C_j * Q_j[k]
;

else
for(k=0;k<l;k++)
G_bar[k] += C_j * Q_j[k];
}
}

part 6

以下計(jì)算目標(biāo)函數(shù)值，因?yàn)镚t
=
(Qα+
p)t ，而目標(biāo)值為
12
α
TQα+
pT
α
，故：

// calculate objective value

 {
double v = 0;
int i;
for(i=0;i<l;i++)

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

si->obj = v/2;
}

part 7

回送結(jié)果。

// put back the solution

 {
for(int i=0;i<l;i++)
alpha_[active_set[i]] = alpha[i];
}

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

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,
double *alpha, double Cp, double Cn, double eps,
SolutionInfo* si, int shrinking)

{
this->si = si;
Solver::Solve(l,Q,b,y,alpha,Cp,Cn,eps,si,shrinking)
;

}

private:
SolutionInfo *si;
int select_working_set(int &i, int &j);
double calculate_rho();
void do_shrinking();

};

其中函數(shù)void Solve()完全調(diào)用了Solve::Solve(),this->si = si;一句是因?yàn)镃++內(nèi)部變量訪問(wèn)的限制
而添加。

成員函數(shù)：

int select_working_set(int &i, int &j)
;
選擇工作集，參考[1],[4],[5], 同時(shí)可以參考Solver::select_working_set
。

double calculate_rho();
計(jì)算
ρ
值，參考[1],[4],[5] （對(duì)應(yīng)libsvm 論文[1] ，其實(shí)返回值是b,這可以從后面預(yù)測(cè)目標(biāo)值
可以看出。與Solver::calculate_rho 相比，增加了另外一個(gè)返回值，r，該值才是真正的
ρ
值。

void do_shrinking()
;
對(duì)樣本進(jìn)行剪裁，參考[1],[4],[5] , 同時(shí)可以參考Solver::do_shrinking()
。

2.4 類SVC_Q
class SVC_Q: public Kernel
{
public:

SVC_Q(const svm_problem& prob, const svm_parameter& param, const schar *y_
)
:Kernel(prob.l, prob.x, param)
{

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

clone(y,y_,prob.l)
;
cache = new Cache(prob.l,(int)(param.cache_size*(1<<20)))
;
}

Qfloat *get_Q(int i, int len) const

{
Qfloat *data;
int start;
if((start = cache->get_data(i,&data,len)) < len)
{

for(int j=start;j<len;j++)

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

}

void swap_index(int i, int j) const

{
cache->swap_index(i,j)
;
Kernel::swap_index(i,j)
;
swap(y[i],y[j])
;

}

~SVC_Q()

{
delete[ ] y;
delete cache;

}

private:
schar *y;
Cache *cache;

};

說(shuō)明：

SVC_Q(const svm_problem& prob, const svm_parameter& param, const schar *y_)
:Kernel(prob.l, prob.x, param)
該構(gòu)造函數(shù)利用初始化列表Kernel(prob.l, prob.x, param)將樣本數(shù)據(jù)和參數(shù)傳入(非常簡(jiǎn)潔)。

get_Q(int i, int len)函數(shù)與其他同類相比，在于核函數(shù)不同。
swap_index(int i, int j) //交換的東西太多了點(diǎn)

2.5 類ONE_CLASS_Q
class ONE_CLASS_Q: public Kernel
{

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

public:
ONE_CLASS_Q(const svm_problem& prob, const svm_parameter& param)
:Kernel(prob.l, prob.x, param)
{

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

Qfloat *get_Q(int i, int len) const

{
Qfloat *data;
int start;
if((start = cache->get_data(i,&data,len)) < len)
{

for(int j=start;j<len;j++)

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

}

void swap_index(int i, int j) const

{
cache->swap_index(i,j)
;
Kernel::swap_index(i,j)
;

}

~ONE_CLASS_Q()
{
delete cache;
}
private:
Cache *cache;
};

ONE_CLASS_Q 只處理1 類分類問(wèn)題(?) ，故不保留y[i] 。編號(hào)只有1 類。
get_Q(int i, int len)函數(shù)中缺少了y[i],y[j] ，這與One_Class 本身特點(diǎn)有關(guān)，只處理一類。
swap_index(int i, int j)少swap(y[i],y[j]); 這句，因?yàn)楦緵]有y[i] 可供交換。

2.5 類SVR_Q
class SVR_Q: public Kernel
{
public:

SVR_Q(const svm_problem& prob, const svm_parameter& param)
:Kernel(prob.l, prob.x, param)

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

{
//skipped
}

void swap_index(int i, int j) const

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

}

Qfloat *get_Q(int i, int len) const
{
//skipped
}

~SVR_Q(
)
{
//skipped
}

private:
int l;
Cache *cache;
schar *sign;
int *index;
mutable int next_buffer;
Qfloat* buffer[2];

};
本類主要是用于做回歸，同分類有許多不同之處。參考[1],[5]

//以下的函數(shù)全為靜態(tài)函數(shù)，只能在本文件范圍內(nèi)被訪問(wèn)。對(duì)照[1] 中公式查看。

2.6 函數(shù)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
α
TQα+
pTα
中，pT 為全-1,另外alpha[i]=0, 保證yT α=
0 的限制條件，在將來(lái)選
2

擇工作集后更新alpha 時(shí)，仍能保證該限制條件。

2.7 函數(shù)solve_nu_svc
static void solve_nu_svc( const svm_problem *prob, const svm_parameter *param,
double *alpha, Solver::SolutionInfo* si)

pT 為全0,alpha[i] 能保證eT α=
0, yTα=
0.

2.8 函數(shù)solve_one_class

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

static void solve_one_class(const svm_problem *prob, const svm_parameter *param,
double *alpha, Solver::SolutionInfo* si)

限制條件eTα=
vl ，前vl 個(gè)alpha 為1，此后的alpha 全為0，初始條件滿足限制條件eTα=
vl

pT 為全0，y 為全1

2.9 函數(shù)solve_epsilon_svr
static void solve_epsilon_svr(const svm_problem *prob, const svm_parameter *param,
double *alpha, Solver::SolutionInfo* si)

2.10 函數(shù)solve_nu_svr
static void solve_nu_svr( const svm_problem *prob, const svm_parameter *param,
double *alpha, Solver::SolutionInfo* si)

第三節(jié)：接口函數(shù)、流程

decision_function svm_train_one(const svm_problem *prob, const svm_parameter *param,
double Cp, double Cn)

訓(xùn)練一組樣本集，通常參加訓(xùn)練的樣本集只有兩類。
程序根據(jù)相應(yīng)的參數(shù)，選擇所使用的訓(xùn)練或者擬合算法。(這個(gè)地方的代碼居然如此少)，最后統(tǒng)
計(jì)SV和BSV，最后輸出決策函數(shù)。

void sigmoid_train( int l, const double *dec_values, const double *labels,

double& A, double& B)
LibSVM2.6 新增函數(shù)

根據(jù)預(yù)報(bào)值來(lái)確定A,B rij
≈
1+
e
1
Af. +B
見第8 節(jié)[1], 其中A,B 的確定就由本函數(shù)確定。

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

LibSVM2.6 新增函數(shù)

可以看看，里面的公式很簡(jiǎn)單。

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

LibSVM2.6 新增函數(shù)

(好像比較復(fù)雜哦. )

void svm_binary_svc_probability(const svm_problem *prob, const svm_parameter *param,
double Cp, double Cn, double& probA, double& probB)

LibSVM2.6 新增函數(shù)

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

先做交叉驗(yàn)證，然后用決策值來(lái)做概率估計(jì)。需要調(diào)用sigmoid_train 函數(shù)。

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

LibSVM2.6 新增函數(shù)

先做交叉驗(yàn)證，然后函數(shù)經(jīng)過(guò)計(jì)算后，輸出概率值。

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

根據(jù)選擇的算法，來(lái)組織參加訓(xùn)練的分樣本，以及進(jìn)行訓(xùn)練結(jié)果的保存。其中會(huì)對(duì)樣本進(jìn)行初步
的統(tǒng)計(jì)。
一、分類部分：

→統(tǒng)計(jì)類別總數(shù),同時(shí)記錄類別的標(biāo)號(hào)，統(tǒng)計(jì)每個(gè)類的樣本數(shù)目
→將屬于相同類的樣本分組，連續(xù)存放
→計(jì)算權(quán)重C
→訓(xùn)練n(n-1)/2個(gè)模型
→初始化nozero數(shù)組，便于統(tǒng)計(jì)SV
→//初始化概率數(shù)組
→訓(xùn)練過(guò)程中，需要重建子數(shù)據(jù)集，樣本的特征不變，但樣本的類別要改為+1/-1
→//如果有必要，先調(diào)用svm_binary_svc_probability
→訓(xùn)練子數(shù)據(jù)集svm_train_one
→統(tǒng)計(jì)一下nozero,如果nozero已經(jīng)是真，就不變，如果為假，則改為真
→輸出模型
→主要是填充svm_model,
→清除內(nèi)存
二、回歸部分：

→類別數(shù)固定為2
→//選擇性地做svm_svr_probability, one-class不做概率估計(jì)
→訓(xùn)練
→輸出模型
→清除內(nèi)存
訓(xùn)練過(guò)程函數(shù)調(diào)用：
svm_train→svm_train_one→solve_c_svc(fox example)→

→Solver s;//這里調(diào)用構(gòu)造函數(shù)，但啥也沒有做。
→s.Solve(l, SVC_Q(*prob,*param,y), minus_ones, y, alpha, Cp, Cn, param->eps, si,
param->shrinking);
→調(diào)用SVC_Q(Kernel) 類的構(gòu)造函數(shù)，同時(shí)也會(huì)調(diào)用Kernel類的構(gòu)造函數(shù)。在SVC_Q
類的構(gòu)造函數(shù)中復(fù)制目標(biāo)值(y), 同時(shí)申請(qǐng)內(nèi)存，此時(shí)激發(fā)Cache類,申請(qǐng)內(nèi)存，構(gòu)造雙向列表等。
→Solve函數(shù)做完其他部分工作，主要是算法的實(shí)現(xiàn)。
void svm_cross_validation(const svm_problem *prob, const svm_parameter *param, int nr_fold,
double *target)

LibSVM2.6 新增函數(shù),LibSVM2.5中為示例函數(shù)。

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

先隨機(jī)打亂次序，然后根據(jù)n折的數(shù)目，留一份作為測(cè)試集，其他的作為訓(xùn)練集，做n次。
隨機(jī)打亂次序使用的非標(biāo)準(zhǔn)的撲克洗牌的算法。(LibSVM2.5 里面隨機(jī)排序的結(jié)果很亂)
For example:
樣本集被分為10份；第一次，將樣本集的第2～10部分作為整體進(jìn)行訓(xùn)練，得到一個(gè)模型，然后
對(duì)樣本集的第1部分進(jìn)行預(yù)報(bào)，得到一個(gè)精度；第二次，將樣本集的第1，3～10作為整體訓(xùn)練，
對(duì)第二部分進(jìn)行預(yù)報(bào)，得到又一個(gè)精度，…。最后對(duì)10個(gè)精度做一下處理（方法很多，不逐一列
出）。

int svm_get_nr_class(const svm_model *model)

獲得樣本類別數(shù)；本函數(shù)為典型的馬后炮。

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

某類樣本的標(biāo)號(hào)（樣本并不按編號(hào)排列，通過(guò)標(biāo)號(hào)，可以循序訪問(wèn)樣本集）。

double svm_get_svr_probability(const svm_model *model)

訪問(wèn)訓(xùn)練好的模型中的概率值。

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

預(yù)測(cè)樣本數(shù)據(jù)目標(biāo)值；
如果是做分類問(wèn)題，返回一大堆值，供后續(xù)的函數(shù)做決策；如果是回歸問(wèn)題，返回一個(gè)值。
其中one-v-one 方法需要做n(n-1)/2 次，產(chǎn)生n(n-1)/2 個(gè)預(yù)報(bào)值。

double svm_predict(const svm_model *model, const svm_node *x)
預(yù)測(cè)，分類問(wèn)題主要使用了One-to-One方法組織n*(n-1)/2 種方法。
如果是分類問(wèn)題，對(duì)預(yù)測(cè)的n*(n-1)/2 個(gè)值，做投票處理，票數(shù)最高的是預(yù)報(bào)的類。
如果是One-Class,根據(jù)預(yù)報(bào)值的符號(hào)，返回+1/-1
如果是回歸問(wèn)題，直接返回該double 類型的值。

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

LibSVM2.6 新增函數(shù)

跳過(guò)。

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 個(gè)函數(shù)均為L(zhǎng)ibSVM2.5 示例程序中的函數(shù)，現(xiàn)成為L(zhǎng)ibSVM2.6 的一部分
。
看看名字就知道是干什么的了，不介紹了
。

void svm_destroy_param(svm_parameter* param)

LibSVM2.6 新增函
數(shù)

釋放權(quán)重系數(shù)數(shù)組的內(nèi)存。

//檢查數(shù)據(jù)

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

const char *svm_check_parameter(const struct svm_problem *prob, const struct svm_parameter
*param);
該段代碼檢查參數(shù)的合理性。凡對(duì)LibSVM 進(jìn)行增加SVC 類型和核函數(shù)，都必須修改該文件。
LibSVM2.5 在該部分代碼會(huì)存在內(nèi)存泄漏，LibSVM2.6 中已經(jīng)修正。
其中需要注意的是，nu 的取值的范圍，

nMin
×
2

nu
<

nMax
+
nMin

其中nMax 為樣本數(shù)最多的類的樣本數(shù)，nMin 為樣本數(shù)最少的類的樣本。

int svm_check_probability_model(const svm_model *model)

LibSVM2.6 新增函數(shù)

檢查概率模型，主要是檢查一些限制條件。

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

Class 1

f3(x)

f1(x)

Class 2
Class 3
f2(x)
Figure 2: One-against-rest SVM separation of three data classes

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

f1,2(x)

Class 1

f2,3(x)

f1,3(x)

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

3
4

43 21

Figure 4: Decision DAG SVM

其他
：
一、One-v-Rest 多類方
法
http://www.csie./~cjlin/libsvmtools/1vsall/

二、DDAG 多類方
法
http://www.csie./~cjlin/libsvmtools/libsvm-2.3dag.zip

1V4
2V4 1V3
2V3 1V2 3V4
1
2
3
4
1
2
3
2
3
4
1
2
2
3
Not 1 Not 4
Not 4
Not 1
Not 3
Not 2

上海交通大學(xué)模式分析與機(jī)器智能實(shí)驗(yàn)室

參考文獻(xiàn)：

[1]Chih-Chung Chang and Chih-Jen Lin, LIBSVM : a library for support vector machines, 2001.
Software available at http://www.csie./~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
http://www.datalab./people/xge/svm/smo.pdf
[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.