基于SVM的训练算法-hslogic算法

3.2参数设置和训练算法3.2.1参数的设置与传统的神经网络方法相比，支持向量机具有出色的性能，它运用结构风险最小化原则，能在经验风险与模型复杂度之间作适当的折衷，从而获得更好的推广能力。但是，支持向量机在实际应用中，关于参数选择的问题仍然没有得到很好地解决，如多项式学习机器的阶数问题、径向基机器中的函数宽度，以及Sigmoid机器中函数的宽度和偏移等。统计学习理论目前对这些问题给出了一些建议和解释，但还没有给出实际可行的方案。目前也只有通过实验方法来确定最佳参数。因此，在使用支持向量机进行分类和预测时，如何选择适当的参数就成了个非常重要的问题]12[。由上面的SVM基本算法可以看出，支持向量机的判决函数的依据是支持向量和偏移值，而支持向量是由训练集中的一部分组成，而不同的训练集中训练出来的支持向量和偏移是不一致的，所以SVM分类器性能对训练集数据选取是敏感的。为了提高支持向量机的分类性能，通常需要不断调整训练集，并对其进行多次反复的训练，对一个具体分类器找到最佳训练集，即找到分类中用于判别的支持向量，这就是系统的再学习过程。为了选择一个SVM分类器较优的参数，前提是要确定一个好的训练集。比较常用的方法是先用训练集一部分训练，通过实验得到SVM对这个训练集的最佳参数，找出对这个训练集中分类错误的样本，这时候把那些分类错误的样本加到训练集中，重新使用新的样本集训练测试SVM到最佳参数，若分类结果不满意再重复上述过程。对于确定了的训练样本集，训练分类器的时候我们可以尝试的核函数可以有几种，实验中可以调试的参数有惩罚系数C和核函数的其他参数，关于这些参数的选择，只能根据个人经验来选择，然后不断的测试更改这二个值并达到最优效果。而使用交叉选择的办法可以快速达到最优解，一般来说，以高斯核为例C的取值一般不超过92，其最小取值一般超过2。的取值一般也不超过32，最小取值一般也超过3-2，所以可以先把C的值确定为9个)2,,2,2(921，同样的值确定为几个，这样再根据经验选择以上组合可以快速达到比较优化的结果，达到结果后可以固定其中一个值，然后微调另一个值，看得到分类结果，调好一个参数后再固定它，微调另一个参数，直到达到最佳而怎样从理论上保证选择最优的核函数仍是一个有待解决的问题，目前多是通过实验来决定。3.3.2SVM的训练算法支持向量机的最终求解问题归结为一个有约束的二次型规划(QP,QuadraticProgramming)问题。二次规划是一种常见的优化问题，从数学角度分析，SVM是一个求约束条件的极值问题。在二次规划中，条件极值问题的通常解法有罚函数法和单纯行法。但是，这些方法只适合小样本情况，当样本数目较大时，算法复杂度会急剧增加，占用极大的系统内存，如计算4000个样本的核函数矩阵就需要128M内存，而且由于迭代误差的积累，也会导致算法精度无法接受。为降低计算资源、提高算法效率，已经提出许多针对大规模样本集的训练算法，多数算法的思想是将大规模的原问题分解为若干小规模的子问题，按照某种迭代策略，反复求解子问题，得到原问题的近似解，并能逐渐收敛到原问题的最优解。这就是分解算法(decomposition)的一般作法，下面给出一般性的分解算法步骤：(1)令b为子集大小((bn，n为样本总数)，对于所有的样本，令0i。(2)从训练集选择b个样本，形成子集B。(3)用标准程序求解子集B所定义的二次规划问题。(4)将模型应用十数据集中的所有样本上。(5)如果存在不满足Karush-Kuhn-Tucker(KKT)条件的样本，则用这些样本及期i代替B中的所有样本及相应的i值。(6)如果不收敛，转向第(3)步。根据从训练集中选择工作样本集B的作法不同，分别演化出不同的分解算法来。1)分块算法(Chunking)1995年，Comes和Vapnik给出了一种求解支持向量机二次规划(QP)问题的分块算法。其依据是支持向量机的最终求解结果只与支持向量有关，与非支持向量无关。其实现过程是将初始QP问题分解为一系列小规模的QP子问题，然后找到所有非零的Lagrange乘子并删除所有为零的agrange乘子。在算法的每步中Chunking都解决一个QP问题，其工作样本为上一步所剩的具有非零Lagrange乘子的样本以及M个不满足KKT条件的最差样本。如果在某一步中，不满足KKT条件的样本不足M个，则这些样本全部加入到新的QP问题中，每个QP子问题都采用上一个QP子问题的结果作为初始值。在算法进行到最后一步时，所有非零Lagrange乘子都被找到，从而解决初始的大型QP问题。Chunking算法将矩阵规模从识训练样本数的平方减少到具有非零Lagrange乘子的样本数的平方：但是在训练集的支持向量数很大时，Chunking算法仍然会受到内存大小的约束。2)子集选择算法(SubsetSelectionAlgorithms)为加快支持向量机的训练速度，Osuna于1997年提出了子集选择算法。该方法其基本思想是首先建立一个工作集，保持其大小不变，在解决每个QP子问题时，先从工作集中移走一个样本，并加入一个不满足KKT条件的样本，再进行优化但是该算法的效率较低，因为每一步进行QP问题的最优化只能使一个样本符合KKT条件。因此算法的关键在十选择一种最优的工作集选择算法。Joachimsl于1998年提出了一种解决大型SVMs学习的算法，称为SVMlight。该算法的基本思想是，如果存在不满足Kuhn-Tucker条件的样本，则以某种方法选择q个样本作为工作集，其他样本保持不变，在这个工作集上解决QP问题。重复这一过程直到所有样本都满足KKT条件。看得出来该算法实际上是Osuna方法的推广。3)序列最小优化算法(SMO，SequentialMinimaloptimization)1998年，Platt提出了更为有效的支持向量机训练算法，即序列最小优化算法。其基本思想是把一个大数据量的QP分解为一系列最小的QP子优化问题。该算法是分解算法的一个极端特例。其实现过程为，每次针对两个样本的二次规划问题，直接采用解析方法求其最优解，以提高QP问题的求解速度。Platt设计了一个两层嵌套循环过程实现其算法。在外环中采用启发式方法寻找违背KKT最优条件的样本，在内环中对该样本的相应Lagrange乘子进行分析求解，完成一次优化。不断重复此过程，直至所有样本都满足KKT条件。序列最小优化算法将工作样本集的规模减少为两个，直接导致了迭代次数的增加。所以序列最小优化算法实际上是将求解优化问题的耗费转嫁到迭代运算上。Platt指出，通过核优化方法可以大幅提高序列最小优化算法的性能。该算法在训练线性支持向量机时，可以获得非常好的性能，但在训练非线性支持向量机时，算法速度会大大减慢。由于每一个子规划问题的解可以精确地给出，因此序贯极小优化算法既不需要额外的矩阵存储，二而且不用调用求解二次规划的数值迭代程序，从而使它的收敛速度显著提高。SMO算法已成为训练支持向量机使用稳定的算法。4)LIBSVM算法Chih-ChungChang及Chin-JenLin于2001年提出了LIBSVM算法，该算法结合SMO算法和SVMlight算法，工作集选取满足SVMlight工作集条件，选取好工作集后采用SMO两点优化。在LIBSVM算法中还采用了收缩和缓存技术，本质上来讲仍然属于SMO算法。对于SVM，支持向量的点(Ci0)数目是少量的，收缩技术不考虑哪些0i和Ci的点，并且可以在每次循环结束时判断支持向量的点的位置。对于终止条件LIBSVM算法在不使用收缩技术时采用和SVMlight算法一样。当采用收缩技术时，误差系数为，终止条件变为ig和ig，在原始循环时没有考虑iigg，当)(iigg小于时，收缩循环终止。本文选择libsvm算法。3.3LIBSVM软件包LIBSVM是台湾大学林智仁(Chih-JenLin)博士等开发设计的一个操作简单、易于使用、快速有效的通用SVM软件包，可以解决分类问题（包括C-SVC、n-SVC）、回归问题（包括e-SVR、n-SVR）以及分布估计（one-class-SVM）等问题，提供了线性、多项式、径向基和S形函数四种常用的核函数供选择，可以有效地解决多类问题、交叉验证选择参数、对不平衡样本加权、多类问题的概率估计等。LIBSVM是一个开源的软件包，他不仅提供了LIBSVM的C++语言的算法源代码，还提供了Python、Java、R、MATLAB、Perl、Ruby、LabVIEW以及C#.net等各种语言的接口，可以方便的在Windows或UNIX平台下使用，也便于科研工作者根据自己的需要进行改进（譬如设计使用符合自己特定问题需要的核函数等）。另外还提供了WINDOWS平台下的可视化操作工具SVM-toy，并且在进行模型参数选择时可以绘制出交叉验证精度的等高线图。LIBSVM在给出源代码的同时还提供了Windows操作系统下的可执行文件，包括：进行支持向量机训练的svmtrain.exe；根据已获得的支持向量机模型对数据集进行预测的svmpredict.exe；以及对训练数据与测试数据进行简单缩放操作的svmscale.exe。它们都可以直接在DOS环境中使用。如果下载的包中只有C++的源代码，则也可以自己在VC等软件上编译生成可执行文件。LIBSVM使用的一般步骤是：(1)按照LIBSVM软件包所要求的格式准备数据集；(2)对数据进行简单的缩放操作；(3)考虑选用RBF核函数2),(yxeyxK；(4)采用交叉验证选择最佳参数C与；(5)采用最佳参数C与对整个训练集进行训练获取支持向量机模型；(6)利用获取的模型进行测试与预测。LIBSVM使用的训练数据和测试数据文件格式如下：labelindex1：value1index2：value2…其中label是训练数据集的目标值，对于分类，它是标识某类的整数(支持多个类)；对于回归，是任意实数。index是以1开始的整数，表示特征的序号；value为实数，也就是我们常说的特征值或自变量。当特征值为0时，特征序号与特征值value都可以同时省略，即index可以是不连续的自然数。label与第一个特征序号、前一个特征值与后一个特征序号之间用空格隔开。测试数据文件中的label只用于计算准确度或误差，如果它是未知的，只需用任意一个数填写这一栏，也可以空着不填。例如：+11:0.7082:13:14:-0.3205:-0.1056:-18:1.21为了使用的方便，可以编写小程序，将自己常用的数据格式按照这种数据格式要求转换成这种格式供LIBSVM直接使用。1)svmscale的用法对数据集进行缩放的目的在于：(1)避免一些特征值范围过大而另一些特征值范围过小；(2)避免在训练时为了计算核函数而计算内积的时候引起数值计算的困难。因此，通常将数据缩放到[-1,1]或者是[0,1]之间。用法：svmscale[-llower][-uupper][-yy_lowery_upper][-ssave_filename][-rrestore_filename]filename（缺省值：lower=-1，upper=1，没有对y进行缩放）其中，-l：数据下限标记；lower：缩放后数据下限；-u：数据上限标记；upper：缩放后数据上限；-y：是否对目标值同时进行缩放；y_lower为下限值，y_upper为上限值；-ssave_filename：表示将缩放的规则保存为文件save_filename；-rrestore_filename：表示将缩放规则文件restore_filename载入后按此缩放；filename：待缩放的数据文件（要求满足前面所述的格式）。缩放规则文件可以用文本浏览器打开，看到其格式为：lowerupperindex1lval1uval1index2lval2uval2其中的lower与upper与