libsvm-2[2].8程序代码导读

数据挖掘平台文档Confidential上海交通大学图像处理与模式识别研究所－1－LibSVM-2.8程序代码注释刘国平([e-mail])2005-08-06数据挖掘平台文档Confidential上海交通大学图像处理与模式识别研究所－2－我不经心地，服下你调好的毒我知道今后我将万劫不复但是你的红唇仍让我屈服四月的樱花火红满天我和你的梦，却要一以何处去缱绻？虽然人间的情爱万万千千世上已有太多崩毁的誓言七个黑夜，七个白天我为你写下的歌，彩绘的纸笺却只能随着晚风飘在大海的岸边我仍愿服下你精心为我调好的毒从你那深情的吻吞下我与你在人间最后的流光万千辗转朱颜……数据挖掘平台文档Confidential上海交通大学图像处理与模式识别研究所－3－第一章LibSVM结构一、文件结构整个LibSVM由两个文件组成，svm.h,svm.cpp。其中svm.h中定义了使用LibSVM所需要的数据结构和函数。数据结构：structsvm_node：数据节点，每个节点只是单个样本矢量中的一个特征。structsvm_problem：数据集，存放所有样本矢量的数据结构。structsvm_parameter：SVM参数。其实应该还有一个数据结构存放在头文件中：structsvm_model：训练好的训练模型。二、类结构图其中有两组关键的类：1、QMatrix类：包括QMatrix,Kernel,SVC_Q,SVR_Q,ONE_CLASS_Q;2、Solver类：包括Solver,Solver_NU;
cdLogicalModelstructsvm_node+index:int+value:doublestructsvm_problem+l:int+y:double*+structx:svm_node**enumerationanonymous+C_SVC:int+NU_SVC:int+ONE_CLASS:int+EPSILON_SVR:int+NU_SVR:intenumerationanonymous+LINEAR:int+POLY:int+RBF:int+SIGMOID:intstructsvm_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:intstructanonymousCache+Cache(int,int)+~Cache()+get_data(int,Qfloat**,int):int+swap_index(int,int):void-lru_delete(head_t*):void-lru_insert(head_t*):voidstructCache::head_t+prev:head_t*+*:head_t*+data:Qfloat*+len:intQMatrix+pureget_Q(int,int):Qfloat*+pureget_QD():Qfloat*+pureswap_index(int,int):voidKernel+Kernel(int,svm_node*,svm_parameter&)+~Kernel()+k_function(svm_node*,svm_node*,svm_parameter&):double+pureget_Q(int,int):Qfloat*+pureget_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):doubleSolver+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():voidstructSolver::SolutionInfo+obj:double+rho:double+upper_bound_p:double+upper_bound_n:double+r:doubleenumerationSolver::anonymous+LOWER_BOUND:int+UPPER_BOUND:int+FREE:intSolver_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():voidSVC_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()ONE_CLASS_Q+ONE_CLASS_Q(svm_problem&,svm_parameter&)+get_Q(int,int):Qfloat*+get_QD():Qfloat*+swap_index(int,int):void+~ONE_CLASS_Q()SVR_Q+SVR_Q(svm_problem&,svm_parameter&)+swap_index(int,int):void+get_Q(int,int):Qfloat*+get_QD():Qfloat*+~SVR_Q()structdecision_function+alpha:double*+rho:doublestructsvm_model+param:svm_parameter+nr_class:int+l:int+SV:svm_node**+sv_coef:double**+rho:double*+probA:double*+probB:double*+label:int*+nSV:int*+free_sv:intstructanonymous+si+Q+prev+head+cache+cache+cache+param(矢量图，可以调整放大倍数)数据挖掘平台文档Confidential上海交通大学图像处理与模式识别研究所－4－第二章：头文件SVM.h本文件只是定义了若干个结构体，和若干接口函数。严格的来说，它们并不是接口函数，因为实际上整个代码里面，可以直接访问的函数还有其他。但事实上，如果仅仅是应用一下这份代码的话，只要知道这几个函数就可以了。2.1structsvm_nodestructsvm_node{intindex;doublevalue;};structsvm_node用来存储单一向量中的单个特征，例如：向量x1={0.002,0.345,4,5.677};那么用structsvm_node来存储时就使用一个包含5个svm_node的数组来存储此4维向量，内存映象如下：1234－10.0020.3454．0005.677空其中如果value为0.00,该特征将不会被存储，其中(特征3)被跳过：1245－10.0020.3454．0005.677空0.00不保留的好处在于，做点乘)(yx的时候，可以加快计算速度，对于稀疏矩阵，更能充分体现这种数据结构的优势。但做归一化时，操作就比较麻烦了。（类型转换不再说明）2.2structsvm_problemstructsvm_problem{intl;double*y;structsvm_node**x;};structsvm_problem存储本次参加运算的所有样本（数据集），及其所属类别。在某些数据挖掘实现中，常用DataSet来实现。intl;记录样本总数double*y;指向样本所属类别或者回归值的数组。在多类问题中，因为使用了one-agianst-one方法，可能原始样本中y[i]的内容是1.0，2.0，3.0，…,也就是属于类别1，2，3，但但参与多类计算时，参加分类的两类所对应的y[i]内容是+1,和－1。Structsvm_node**x;指向一个存储内容为指针的数组；数据挖掘平台文档Confidential上海交通大学图像处理与模式识别研究所－5－如下图,最右边的四个长条格同上表，存储三维数据。(黑边框的是最主要的部分)这样的数据结构有一个直接的好处，可以用x[i][j]来访问其中的某一元素（如果value为0.00的也全部保留的话）。私下认为其中有一个败笔，就是把svm_node*x_space放到结构外面去了。2.3enumsenum{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.Atutorialonsupportvectormachinesforpatternrecognition.DataMiningandKnowledgeDiscovery,2(2):955-974,1998.NU_SVC:(待补充)2.4structsvm_parameterstructsvm_parameter{intsvm_type;//SVM类型，见前enumintkernel_type;//核函数doubledegree;/*forpoly*/doublegamma;/*forpoly/rbf/sigmoid*/doublecoef0;/*forpoly/sigmoid*//*thesearefortrainingonly*/doublecache_size;/*inMB*/doubleeps;/*stoppingcriteria*/doubleC;/*forC_SVC,EPSILON_SVRandNU_SVR*/intnr_weight;/*forC_SVC*/int*weight_label;/*forC_SVC*/double*weight;/*forC_SVC*/doublenu;/*forNU_SVC,ONE_CLASS,andNU_SVR*/Y[3]Y[2]Y[1]Y[0]L=4Y*X**数据挖掘平台文档Confidential上海交通大学图像处理与模式