支持向量机算法的研究

支持向量机算法的研究

现在，许多搜索算法已经被分解。WEKA1支持向量机算法序列最小化算法即SMO算法是支持向量机（SupportVectorMachine）算法中的一种，而支持向量机是分类算法中的一种，它在解决小样本、非线性及高位模式识别问题中表现出许多特有的优势，主要用来解决二值分类的模式识别问题。1.1svm训练算法支持向量机（SVM）方法是建立在统计学习理论的VC维理论和结构风险最小化原理基础上的，根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷，以期获得最好的推广能力。SVM是从线性可分情况下的最优分类面发展而来的。最优分类面是指分类面不但能将两类正确分类，而且使分类间隔最大。设样本集：此时分类间隔等于2/||W||。满足条件(1)且使2/||W||在该条件下对αα式中的求和实际上只对支持向量。b为分类阈值，可以通过任一个支持向量求出或通过两类中任意一对支持向量取中值求得。通过对对偶问题的最优解推导可以求出：上式为KKT条件。由于KKT条件是最优解应满足的充要条件-公式(3)，所以目前提出的一些算法几乎都是以是否违反KKT条件作为迭代策略的准则。由于SVM方法有较好的理论基础，它在一些领域的应用中表现出来了优秀的推广性能，但是该算法在计算上存在着一些问题，包括训练算法速度慢、算法复杂而难以实现以及检测阶段运算量大等等。SVM训练算法慢的主要原因首先是它需要计算和存储核函数矩阵，当样本点数目较大时，需要很大的内存，其次它在寻优过程中要进行大量的矩阵运算，多数情况下，寻优算法是占用算法时间的主要部分。因而，近年来提出的许多算法来解决对偶寻优问题。大多数算法的一个共同思想就是循环迭代：将原问题分解为若干子问题，通过反复求解子问题，构成原问题的近似解，并且使该近似解逐渐收敛到原问题的最优解。代表的算法有选块算法（chunking）1.2基于smo算法的乘子协同优化SMO算法将原问题分解为若干子问题，而且子问题的规模最小-两个样本，即每次迭代过程中只调整相应于两个样本点，它只求解一个具有两个变量的最优化问题假定工作集B={i,j}，每一步选择出来优化的两个Lagrange乘子分别为α只要变动其中一个乘子，就必须同时调整另外一个乘子来保证不违反该约束。因而α假定选择α然后将α其中：然后根据(4)式可以得出另外一个乘子更新后的值：SMO算法使用双层循环这样一种启发式方法来选择乘子进行优化。外层循环用来挑选第一个用于优化的乘子，内层循环用来挑选与第一个乘子协同优化的第二个乘子。外层循环主要在界内样本（0<α其中：根据更新后的乘子以及阈值来更新Еi的值，从而完成了一次优化过程。1.3训练大规模数据集子问题的规模和整个算法需要迭代的次数是矛盾的，SMO算法将工作集的规模减到最小，一个直接的后果就是迭代次数的增加。虽然该算法的优点在于通过两个变量的最优化问题来解析求解，得到这两个变量的最优值，然后来改进相应的向量的分量，但是好的算法却难在实现手法上。实现的手法不一样，达到的效果不同甚至是差别巨大。事实上，SMO算法对二进制数据以及稀疏数据比较敏感，比较适用于多值分类，在二值分类时，训练大规模数据集时效率低下。在WEKA中用SMO训练大规模数据集时由于训练样本的线性增加，迭代次数增加，用于搜索乘子以及更新乘子和相应值的时间花费巨大，而且所需的内存空间剧增，常常要经过多次尝试后才能确定一个适合当前样本集的JavaHeap。以48842个样本集为例，经过实验，采用十折交叉验证1.4利用五个工作集提供大量的空间在WEKA中，SMO算法主要通过以下方式来实现对整个训练集和界内样本中违反KKT条件的乘子的查找：采取五个工作集这样一种策略：I算法实现的主要步骤如表1所示：更新函数的主要步骤如表2所示：在这种策略下，当训练样本集规模大时，最直接的后果就是需要为这五个工作集开辟大量的存储空间，每次搜索违反KKT条件的样本需要遍历五个工作集，而更新一对乘子后需要将更新后的值分别放入五个工作集中，浪费了大量的时间和空间。综上所述，用五个工作集来分别存放样本并不是最好的方式。因而，可以尝试用另外的三个工作集来代替五个工作集：分别是I这样做的好处有如下几点：初始化时节省了40%的存储空间；在搜索乘子和更新乘子时大量的减少了判断次数，大大降低了算法的复杂度，节省了时间；在能保持原算法的分类效果不变的情况下，提高了训练效率，从而使算法的性能得到优化。在另外一方面，又使得WEKA软件的运用更加广泛。2实验数据集与分析本实验采用改进前后的SMO算法分类效果以及效率的对比来得出相关结论。在进行该实验时，为了有对比性，采用公共数据集，并且在相同的软硬件环境下，使实验结果更可靠。Adult数据集是美国埃威尔分校UCI官网分享的一个数据集，该数据集有48842个实例。在进行预处理后，为了证明改进后的算法对小样本有同样的效果，随机挑选了796个样本以及3215个样本共同实验，采用十折交叉验证的方法评价算法的好坏，选择Poly核函数，下表为算法改进前后对比的实验结果。从表3可知，改进后的算法在时间上比标准版的SMO算法相比，减少了一半以上，在分类正确率上与原来相比相差无几。而且，改进后的算法在内存上，比原来的要求低得多。以48842个样本为例，改进后的算法跟原来的相比，存储空间的要求降低了40%。3改进的smo算法的对比本文通过对SMO分类算法的研