LibSVM-2.8程序代碼注釋

1、數(shù)據(jù)挖掘平臺(tái)文檔ConfidentialLibSVM-2.8程序代碼注釋劉國(guó)平(ahphone)2005-08-06我不經(jīng)心地，服下你調(diào)好的毒 我知道今后我將萬劫不復(fù) 但是你的紅唇仍讓我屈服 四月的櫻花火紅滿天 我和你的夢(mèng)，卻要一以何處去繾綣？ 雖然人間的情愛萬萬千千 世上已有太多崩毀的誓言 七個(gè)黑夜，七個(gè)白天 我為你寫下的歌，彩繪的紙箋 卻只能隨著晚風(fēng) 飄在大海的岸邊 我仍愿服下你精心為我調(diào)好的毒 從你那深情的吻 吞下我與你在人間 最后的流光萬千輾轉(zhuǎn)朱顏第一章 LibSVM結(jié)構(gòu)一、文件結(jié)構(gòu)整個(gè)LibSVM由兩個(gè)文件組成，svm.h, svm.cpp。其中svm.h中定義了使用LibSVM所需

2、要的數(shù)據(jù)結(jié)構(gòu)和函數(shù)。數(shù)據(jù)結(jié)構(gòu)：struct svm_node ：數(shù)據(jù)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)只是單個(gè)樣本矢量中的一個(gè)特征。struct svm_problem ：數(shù)據(jù)集，存放所有樣本矢量的數(shù)據(jù)結(jié)構(gòu)。struct svm_parameter ： SVM參數(shù)。其實(shí)應(yīng)該還有一個(gè)數(shù)據(jù)結(jié)構(gòu)存放在頭文件中：struct svm_model ： 訓(xùn)練好的訓(xùn)練模型。二、類結(jié)構(gòu)圖其中有兩組關(guān)鍵的類：1、 QMatrix類： 包括QMatrix, Kernel, SVC_Q, SVR_Q, ONE_CLASS_Q;2、 Solver類： 包括Solver, Solver_NU;(矢量圖，可以調(diào)整放大倍數(shù))第二章： 頭文件S

3、VM.h本文件只是定義了若干個(gè)結(jié)構(gòu)體，和若干接口函數(shù)。嚴(yán)格的來說，它們并不是接口函數(shù)，因?yàn)閷?shí)際上整個(gè)代碼里面，可以直接訪問的函數(shù)還有其他。但事實(shí)上，如果僅僅是應(yīng)用一下這份代碼的話，只要知道這幾個(gè)函數(shù)就可以了。2.1 struct svm_nodestruct svm_nodeint index;double value;struct svm_node用來存儲(chǔ)單一向量中的單個(gè)特征，例如：向量 x1= 0.002, 0.345, 4, 5.677;那么用struct svm_node來存儲(chǔ)時(shí)就使用一個(gè)包含5個(gè)svm_node的數(shù)組來存儲(chǔ)此4維向量，內(nèi)存映象如下：123410.0020.345400

4、05.677空其中如果value為0.00,該特征將不會(huì)被存儲(chǔ)，其中(特征3)被跳過：124510.0020.34540005.677空0.00不保留的好處在于，做點(diǎn)乘的時(shí)候，可以加快計(jì)算速度，對(duì)于稀疏矩陣，更能充分體現(xiàn)這種數(shù)據(jù)結(jié)構(gòu)的優(yōu)勢(shì)。但做歸一化時(shí)，操作就比較麻煩了。（類型轉(zhuǎn)換不再說明）2.2 struct svm_problemstruct svm_problemint l;double *y;struct svm_node *x;struct svm_problem存儲(chǔ)本次參加運(yùn)算的所有樣本（數(shù)據(jù)集），及其所屬類別。在某些數(shù)據(jù)挖掘?qū)崿F(xiàn)中，常用DataSet來實(shí)現(xiàn)。int l;記錄樣本總

5、數(shù)double *y;指向樣本所屬類別或者回歸值的數(shù)組。在多類問題中，因?yàn)槭褂昧薿ne-agianst-one方法，可能原始樣本中yi的內(nèi)容是1.0，2.0，3.0，,也就是屬于類別1，2，3，但但參與多類計(jì)算時(shí)，參加分類的兩類所對(duì)應(yīng)的yi內(nèi)容是+1,和1。Struct svm_node *x;指向一個(gè)存儲(chǔ)內(nèi)容為指針的數(shù)組；如下圖,最右邊的四個(gè)長(zhǎng)條格同上表，存儲(chǔ)三維數(shù)據(jù)。(黑邊框的是最主要的部分)Y3Y2Y1Y0L=4Y*X*這樣的數(shù)據(jù)結(jié)構(gòu)有一個(gè)直接的好處，可以用xij來訪問其中的某一元素（如果value為0.00的也全部保留的話）。私下認(rèn)為其中有一個(gè)敗筆，就是把svm_node* x_spa

6、ce放到結(jié)構(gòu)外面去了。2.3 enumsenum C_SVC, NU_SVC, ONE_CLASS, EPSILON_SVR, NU_SVR ;/* svm_type */enum LINEAR, POLY, RBF, SIGMOID ;/* kernel_type */支持向量機(jī)類型以及若干文獻(xiàn)：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 :(

7、待補(bǔ)充)2.4 struct svm_parameterstruct svm_parameterint svm_type;/SVM類型，見前enumint 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

8、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 estim

9、ates */;部分參數(shù)解釋,(附核函數(shù))1、2、3、4、double degree;/就是2式中的ddouble gamma; /就是2,3,4式中的gammadouble coef0;/就是2,4式中的rdouble cache_size;/* in MB */ 制定訓(xùn)練所需要的內(nèi)存，默認(rèn)是40M，LibSVM2.5中是4M,所以自己做開發(fā)選LibSVM2.5還是不錯(cuò)的！double eps;見參考文獻(xiàn)1中式3.13double C;/沒什么好說的，懲罰因子，越大訓(xùn)練的模型越那個(gè),當(dāng)然耗的時(shí)間越多int nr_weight;/權(quán)重的數(shù)目,目前在實(shí)例代碼中只有兩個(gè)值，一個(gè)是默認(rèn)0，另外一個(gè)是

10、svm_binary_svc_probability函數(shù)中使用數(shù)值2。int *weight_label;/權(quán)重，元素個(gè)數(shù)由nr_weight決定double nu;沒什么好說的,看代碼中的注釋,toodouble p;沒什么好說的,看代碼中的注釋,threeint shrinking;指明訓(xùn)練過程是否使用縮減int probability;指明訓(xùn)練過程是否需要預(yù)報(bào)概率。/ 2.5 struct struct svm_modelstruct svm_modelsvm_parameter param;/ parameterint nr_class;/ number of classes, = 2

11、 in regression/one class svmint l;/ total #SVsvm_node *SV;/ SVs (SVl)double *sv_coef;/ coefficients for SVs in decision functions (sv_coefn-1l)double *rho;/ constants in decision functions (rhon*(n-1)/2)double *probA; / pariwise probability informationdouble *probB;/ for classification onlyint *labe

12、l;/ label of each class (labeln)int *nSV;/ number of SVs for each class (nSVn)/ nSV0 + nSV1 + . + nSVn-1 = l/ XXXint 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)然原來的訓(xùn)練參數(shù)也必須保留。本來這個(gè)結(jié)構(gòu)體應(yīng)該是在svm.cpp中，為統(tǒng)一起見，一起描述。svm_parameter para

13、m;訓(xùn)練參數(shù),這里使用的是svm_param的實(shí)例，而不是指針。這樣訓(xùn)練完成后，原來參數(shù)被完全保留，再去預(yù)報(bào)時(shí)，就不用擔(dān)心下次訓(xùn)練會(huì)把參數(shù)沖掉int nr_class;類別數(shù)int l;支持向量數(shù)svm_node *SV;保存支持向量的指針，至于支持向量的內(nèi)容，如果是從文件中讀取，內(nèi)容會(huì)額外保留；如果是直接訓(xùn)練得來，則保留在原來的訓(xùn)練集中。如果訓(xùn)練完成后需要預(yù)報(bào)，原來的訓(xùn)練集內(nèi)存不可以釋放。double *sv_coef;相當(dāng)于判別函數(shù)中的alphadouble *rho;相當(dāng)于判別函數(shù)中的bdouble *probA;pariwise probability informationdoubl

14、e *probB;int *label;label of each class (labeln)int *nSV;number of SVs for each class (nSVn)int free_sv;1 if svm_model is created by svm_load_model； 0 if svm_model is created by svm_train2.6 接口函數(shù)/以下接口函數(shù)設(shè)計(jì)得非常合理，最后一節(jié)詳細(xì)說明/最主要的驅(qū)動(dòng)函數(shù)，訓(xùn)練數(shù)據(jù)struct svm_model *svm_train(const struct svm_problem *prob, const st

15、ruct 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(

16、const char *model_file_name);/得到數(shù)據(jù)集的SVM類型（必須經(jīng)過訓(xùn)練得到模型后才可以用）int svm_get_svm_type(const struct svm_model *model);/得到數(shù)據(jù)集的類別數(shù)（必須經(jīng)過訓(xùn)練得到模型后才可以用）int svm_get_nr_class(const struct svm_model *model);/得到數(shù)據(jù)集的類別標(biāo)號(hào)（必須經(jīng)過訓(xùn)練得到模型后才可以用）void svm_get_labels(const struct svm_model *model, int *label);/LibSvm2.6新增函數(shù)double

17、 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 sv

18、m_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)行。const char *svm_check_parameter(const struct sv

19、m_problem *prob, const struct svm_parameter *param);/ LibSvm2.6新增函數(shù)int svm_check_probability_model(const struct svm_model *model);第三章： SVM.cpp文件3.1 宏.頭文件：從整個(gè).cpp文件來看，感覺有些頭文件是多余的，不知何故，反正多包含頭文件不會(huì)犯錯(cuò)。后面的typedef,特別是typedef float Qfloat,是為了方便控制內(nèi)存存儲(chǔ)的精度。#include <math.h>#include <stdio.h>#includ

20、e <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ù)，這里的處理是為了兼容Microsoft VC+編譯器。因?yàn)閂C對(duì)標(biāo)準(zhǔn)模板庫

21、(STL)支持得不是很好。下面對(duì)min, max的處理方法非常經(jīng)典。#ifndef mintemplate <class T> inline T min(T x,T y) return (x<y)?x:y; #endif#ifndef maxtemplate <class T> inline T max(T x,T y) return (x>y)?x:y; #endif/這里的克隆函數(shù)是完全克隆，不同于一般的復(fù)制。操作結(jié)束后，內(nèi)部的所有數(shù)據(jù)和指針完全一樣。template <class T> inline void swap(T& x,

22、T& y) T t=x; x=y; y=t; template <class S, class T> inline void clone(T*& dst, S* src, int n)dst = new Tn;memcpy(void *)dst,(void *)src,sizeof(T)*n);/這里使用了define，非內(nèi)聯(lián)函數(shù)#define Malloc(type,n) (type *)malloc(n)*sizeof(type)一般來說，在cpp中使用delete比較正規(guī)，在c中使用malloc比較正規(guī)。LibSVM比較好地貫徹了這點(diǎn)，malloc用在接口函數(shù)

23、中。/以下的函數(shù)用作調(diào)試。跳過#if 1void 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)系)，更正規(guī)的圖例見第一章。CacheKernelONE_CLASS_QSVC_QSVR_QSolverSolver_NU3.2 類Cache本類主要負(fù)責(zé)運(yùn)

24、算所涉及的內(nèi)存的管理，包括申請(qǐng)、釋放等。本類對(duì)理解核心代碼關(guān)系不大，如果弄不清楚影響也不大?？梢蕴^。類定義:class Cachepublic:Cache(int l,int size);Cache();int get_data(const int index, Qfloat *data, int len);void swap_index(int i, int j);/ future_optionprivate:int l;int size;struct head_thead_t *prev, *next;/ a cicular listQfloat *data;int len;/ data

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

26、總數(shù)。int size; /所指定的全部?jī)?nèi)存，據(jù)說用Mb做單位。成員函數(shù)：void lru_delete(head_t *h); /從雙向環(huán)形鏈表中刪除某個(gè)元素的鏈接，不刪除、不釋放該元素所涉及的內(nèi)存。一般是刪除當(dāng)前所指向的元素。void lru_insert(head_t *h); /在鏈表后面插入一個(gè)新的鏈接；其實(shí)就是在lru_head后添加。（環(huán)形的嘛）HeadNewCache(int l,int size); 構(gòu)造函數(shù)。該函數(shù)根據(jù)樣本數(shù)L，申請(qǐng)L個(gè)head_t的空間。根據(jù)說明，該區(qū)域會(huì)初始化為0。Lru_head因?yàn)樯袥]有head_t中申請(qǐng)到內(nèi)存，故雙向鏈表指向自己。至于size的處理

27、，先將原來的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_tindex中至少有l(wèi)en個(gè)float的內(nèi)存，并且將可以使用的內(nèi)存塊的指針放在data指針中。返回值為申請(qǐng)到的內(nèi)存。函數(shù)首先將head_tindex從鏈表中斷開,如果head_tindex原來沒有分配內(nèi)存，則跳過斷開這步。計(jì)算當(dāng)前head_tindex已經(jīng)申請(qǐng)到的內(nèi)存，如果不夠，釋放部分內(nèi)存（懷疑這樣做的動(dòng)機(jī)：老數(shù)據(jù)為什么

28、就可以釋放，而不真的另外申請(qǐng)一塊？老數(shù)據(jù)沒用了？），等內(nèi)存足夠后，重新分配內(nèi)存。重新使head_tindex進(jìn)入雙向鏈表。并返回申請(qǐng)到的內(nèi)存的長(zhǎng)度。/返回值不為申請(qǐng)到的內(nèi)存的長(zhǎng)度，為head_tindex原來的數(shù)據(jù)長(zhǎng)度h->len。調(diào)用該函數(shù)后，程序會(huì)計(jì)算的值，并將其填入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

29、 i, int j); 交換head_ti 和head_tj的內(nèi)容，先從雙向鏈表中斷開，交換后重新進(jìn)入雙向鏈表中。對(duì)后面的處理不理解，可能是防止中head_ti 和head_tj可能有一方并未申請(qǐng)內(nèi)存。但h->len > i和 h->len > j無法解釋。for(head_t *h = lru_head.next; h!=&lru_head; h=h->next)if(h->len > i)if(h->len > j)swap(h->datai,h->dataj);else/ give uplru_delete(h);

30、free(h->data);size += h->len;h->data = 0;h->len = 0;后注：這部分內(nèi)容我?guī)状巫x過，都不太清楚，如果有誰弄懂了，請(qǐng)告知。3.3 類QMatrixclass 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;純虛類。理論上用戶只要能在需要的時(shí)候，提供必要的數(shù)據(jù)，就可以實(shí)現(xiàn)其它的

31、變形支持向量機(jī)。用戶可以自己實(shí)現(xiàn)數(shù)據(jù)矩陣（很大的哦），然后直接提供給Solver。3.4 類Kernelclass 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

32、 = 0;virtual void swap_index(int i, int j) const/ no so const.swap(xi,xj);if(x_square) swap(x_squarei,x_squarej);protected:double (Kernel:*kernel_function)(int i, int j) const;private:const svm_node *x;double *x_square;/ svm_parameterconst int kernel_type;const double degree;const double gamma;const

33、 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; /用來指向樣本數(shù)據(jù)，每

34、次數(shù)據(jù)傳入時(shí)通過克隆函數(shù)來實(shí)現(xiàn)，完全重新分配內(nèi)存，主要是為處理多類著想。double *x_square; /使用RBF核才使用。const int kernel_type; /核函數(shù)類型.const double degree; / kernel_functionconst double gamma; / kernel_functionconst double coef0; / kernel_function成員函數(shù)：Kernel(int l, svm_node * const * x, const svm_parameter& param);構(gòu)造函數(shù)。初始化類中的部分常量、指定核函

35、數(shù)、克隆樣本數(shù)據(jù)。如果使用RBF核函數(shù)，則計(jì)算x-sqarei.static double dot(const svm_node *px, const svm_node *py);點(diǎn)乘兩個(gè)樣本數(shù)據(jù)，按svm_node中index (一般為特征)進(jìn)行運(yùn)算，一般來說，index中1，2，直到-1。返回點(diǎn)乘總和。例如：x1 = 1,2,3 , x2 = 4, 5, 6 總和為sum = 1*4 + 2*5 + 3*6 ;在svm_node3中存儲(chǔ)index = -1時(shí)，停止計(jì)算。static double k_function(const svm_node *x, const svm_node *y

36、, 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ì)算做完。virtual Qfloat *get_Q(int column, int len) const = 0;virtual Qfloat *get_QD() const = 0;純虛函數(shù)，將來在子類中實(shí)現(xiàn)。相當(dāng)重要的函數(shù)。virtual vo

37、id swap_index(int i, int j)虛函數(shù)，xi和xj中所存儲(chǔ)指針的內(nèi)容。如果x_square不為空，則交換相應(yīng)的內(nèi)容。double (Kernel:*kernel_function)(int i, int j) const;函數(shù)指針，根據(jù)相應(yīng)的核函數(shù)類型，來決定所使用的函數(shù)。在計(jì)算矩陣Q時(shí)使用。1、2、3、4、3.4 類Solverclass Solver public:Solver() ;virtual Solver() ;struct SolutionInfo double obj;double rho;double upper_bound_p;double upper

38、_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 functionenum LOWER_BOUND, UPPER_BOUND, F

39、REE ;char *alpha_status;/ LOWER_BOUND, UPPER_BOUND, FREEdouble *alpha;const Kernel *Q;double eps;double Cp,Cn;double *b;int *active_set;double *G_bar;/ gradient, if we treat free variables as 0int l;bool unshrinked;/ XXXdouble get_C(int i)void update_alpha_status(int i)bool is_upper_bound(int i) ret

40、urn alpha_statusi = UPPER_BOUND; bool is_lower_bound(int i) return alpha_statusi = LOWER_BOUND; bool is_free(int i) return alpha_statusi = 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 voi

41、d do_shrinking();成員變量：int active_size; / 計(jì)算時(shí)實(shí)際參加運(yùn)算的樣本數(shù)目，經(jīng)過shrink處理后，該數(shù)目會(huì)小于全部樣本總數(shù)。schar *y; /樣本所屬類別，該值只取+1/-1 。雖然可以處理多類，最終是用兩類SVM完成的。double *G; /梯度，計(jì)算公式如下(公式3.5)1：在代碼實(shí)現(xiàn)中，用bi來代替公式中的p。char *alpha_status; /的狀態(tài)，根據(jù)情況分為 , 和，分別對(duì)應(yīng)內(nèi)部點(diǎn)(非SV)，錯(cuò)分點(diǎn)(BSV)和支持向量(SV)。double *alpha; /const Kernel *Q; /指定核。核函數(shù)和Solver相互結(jié)合

42、，可以產(chǎn)生多種SVC,SVRdouble eps; /誤差限double *b; /見double *G的說明。int *active_set; /double *G_bar; / ,（這名字取的）。計(jì)算公式如下：該值可以在對(duì)樣本集做shrink時(shí)，減小重建梯度的計(jì)算量。int l; /樣本總數(shù)bool unshrinked; /成員函數(shù)：double get_C(int i)返回對(duì)應(yīng)于樣本的C。 設(shè)置不同的Cp和Cn是為了處理數(shù)據(jù)的不平衡。見 6 Unbalanced data1，有時(shí)Cp=Cn。void swap_index(int i, int j);完全交換樣本i和樣本j的內(nèi)容，包括所

43、申請(qǐng)的內(nèi)存的地址。void reconstruct_gradient();重新計(jì)算梯度。G_bari在初始化時(shí)并未加入bi，所以程序首先增加bi。Shrink后依然參加運(yùn)算的樣本位于active_size和L-1位置上。在0active_size之間的alphai如果在區(qū)間(0,c)上，才有必要更新相應(yīng)的active_size和L-1位置上的樣本的梯度。virtual int select_working_set(int &i, int &j)選擇工作集。公式如下：virtual void do_shrinking();對(duì)樣本集做縮減。大致是當(dāng)時(shí)，(還有兩種情況)程序認(rèn)為該樣本

44、可以不參加下次迭代。（時(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來的樣本也被檢查一次。如果程序在縮減一次后沒有達(dá)到結(jié)束條件，就重新構(gòu)造梯度矢量，并再縮減一次（總覺得這里不太嚴(yán)密）。virtual double calculate_rho();計(jì)算值。見3.71節(jié)，The calculation of or void Solve(int l, const Kernel& Q, const double

45、 *b_, const schar *y_, double *alpha_, double Cp, double Cn, double eps, SolutionInfo* si, int shrinking);/程序較大，逐步分解part 1/ initialize alpha_statusalpha_status = new charl;for(int i=0;i<l;i+)update_alpha_status(i);更新一下alpha的狀態(tài)part 2/ initialize active set (for shrinking)active_set = new intl;for(

46、int i=0;i<l;i+)active_seti = i;active_size = l;為縮減做準(zhǔn)備，將來要做交換part 3/ initialize gradientG = new doublel;G_bar = new doublel;int i;for(i=0;i<l;i+)Gi = bi;G_bari = 0;for(i=0;i<l;i+)if(!is_lower_bound(i)Qfloat *Q_i = Q.get_Q(i,l);double alpha_i = alphai;int j;for(j=0;j<l;j+)Gj += alpha_i*Q_i

47、j;if(is_upper_bound(i)for(j=0;j<l;j+)G_barj += get_C(i) * Q_ij;G_barj的生成公式如下：（注意，其中不包含bi的值）因?yàn)榈谝淮谓(i),所以沒有判斷alpha的狀態(tài)。而是按公式，全部計(jì)算了一遍。get_Q(i,l)返回的值是矩陣中的第i列，而不是第i行，這是需要注意的地方。再往下是大循環(huán)：如果有必要，先進(jìn)行篩選，使部分?jǐn)?shù)據(jù)不再參加運(yùn)算；選擇工作集；更新alpha_i, alpha_j,其更新的思路是保證：;對(duì)于邊界情況，有特殊處理，主要是考慮的要求。當(dāng)某一alpha小于0時(shí)，做適當(dāng)調(diào)整,調(diào)整的結(jié)果是alpha_i, a

48、lpha_j仍然在范圍內(nèi)，同時(shí)其和同原來一樣。對(duì)于推導(dǎo)過程，可以參考Sequential Minimal Optimization for SVMpart 4更新G(i),根據(jù)的變化更新；/ update Gdouble delta_alpha_i = alphai - old_alpha_i;double delta_alpha_j = alphaj - old_alpha_j;for(int k=0;k<active_size;k+)Gk += Q_ik*delta_alpha_i + Q_jk*delta_alpha_j;part 5以下是更新alpha_status 和,ahph

49、a狀態(tài)更新較簡(jiǎn)單，根據(jù)alpha狀態(tài)前后是否有變化，適當(dāng)更新，更新的內(nèi)容參考公式/ update alpha_status and G_barbool 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的影響Q_i = Q.get_Q(i,l);if(ui)for(k=0;k<l;k+)G_bark -= C_i * Q_ik;elsefor(k=0;k<l

50、;k+)G_bark += C_i * Q_ik;if(uj != is_upper_bound(j) /更新alpha_j的影響Q_j = Q.get_Q(j,l);if(uj)for(k=0;k<l;k+)G_bark -= C_j * Q_jk;elsefor(k=0;k<l;k+)G_bark += C_j * Q_jk;part 6以下計(jì)算目標(biāo)函數(shù)值，因?yàn)椋繕?biāo)值為，故：/ calculate objective valuedouble v = 0;int i;for(i=0;i<l;i+)v += alphai * (Gi + bi);si->obj =

51、v/2;part 7回送結(jié)果。/ put back the solutionfor(int i=0;i<l;i+)alpha_active_seti = alphai;2.3 類Solver_NUclass Solver_NU : public Solverpublic: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 shrink

52、ing)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)部變量訪問的限制而添加。成員函數(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_shri