核极化的核参数选择算法

张文兴，陈肖洁，王建国

（内蒙古科技大学 机械工程学院，内蒙古 包头 014010）

1 引言

支持向量机（support vector machine，SVM）是在1992年的计算学习理论会议上由文献[1]引进机器学习领域的新一代智能算法。SVM广泛应用于模式识别和回归估计，如金属结构安全评估[2]、铆接力的回归预测[3]。SVM是基于核的学习机器，其核心是通过核函数隐式定义非线性变换，即不必显式地计算从输入空间到高维特征空间的非线性变换，而是在高维特征空间中隐式地高效计算内积。显然，通过核函数所构建的核矩阵包含了训练数据和高维特征空间隐含的信息，SVM的泛化能力在很大程度上依赖于核函数的确定，而核参数直接影响着核函数的构建。因而，选择一个适当的核参数是求解的第一步。

目前，常用的参数选择方法有以下几种：（1）根据问题的先验信息来选择参数，但该方法仅对一些特殊问题如图像识别有效，并不适用于一般问题；（2）k-折交叉验证法[4]（在实际应用中10折交叉验证应用最广）是参数选择经典的方法，其本质是用参数空间中每一组可能的参数组合去训练和测试SVM，找出效果最好的参数组合，其特点是经验性强，计算量大，且不适用于优化参数多于两个的情况；（3）通过梯度下降法最小化泛化误差来进行多参数选取[5]，但该方法需要迭代求解对偶问题，计算量较大；（4）一些精度较高，但计算复杂性也较高的优化算法，如基于Bayesian方法；（5）基于优化核度量标准的方法，其主要出发点是如何衡量核函数和学习任务（分类）的一致性[6]。其基础是一系列独立于算法的核度量标准的提出，如核排列（kernelalignment）[7-8]、核极化（kernelpolarization）[9]等。核度量标准着力于捕捉训练数据集在高维特征空间中的可分离特性，在不考虑核函数计算复杂度的前提下，计算复杂度为o（l2），其中，l是训练样本的个数，因而计算是高效率的。遵循上述核度量标准的思路，将核极化直接最大化算法应用于Gaussian核和Polynomial核的核参数的选择中，以使多类SVM获得更好的分类性能。

2 支持向量机（SVM）

2.1 二分类SVM提出及求解

样本集 D=（xi，yi），xi∈Rn，yi∈｛+1，-1｝，i=1，…，l，能将 D正确地分为两类的最优分类超平面＜ω·x＞+b=0的求解等价于解l1-SVM或C-SVM，其原始问题为：

式中：C—正则化参数（权衡调和最大化平面间隔和最小化训练错误两个目标）；ξi—松弛变量；φ（x）—从输入空间到高维特征空间的映射。

拉格朗日乘子法求解（1）式，得到Wolfe对偶问题：

式中：αi—拉格朗日乘子，解中αi≠0所对应的xi称为支持向量，即对最优分类超平面有贡献的样本，αi≠0称为支持向量值。解上述优化问题（2）可以得到如下决策函数：

2.2 多分类SVM的求解

多分类SVM的求解主要分为两种[10]：（1）将多分类问题转化为二分类问题，如one-versus-rest（1-v-r）和one-versus-one（1-v-1）算法；（2）用一个最优化问题一次求解所有的超平面实现多分类分类。1-v-r算法：此方法简单、有效，但当类别较大时，某一类的训练样本将大大少于其他类训练样本的总和，这种训练样本间的不均衡将明显地影响测试精度。1-v-1算法：测试时采用投票法，类别输出为得票数最多的那一类，在实际应用中，一般推荐使用1-v-1方法。而对于在一个最优化问题中求解多个分类面的参数的方法，乍看起来简洁快捷高效，但是在实际操作过程中，过多的变量和过于复杂的目标函数导致过高的计算复杂度，在分类准确率上也毫无优势可言。因此，该算法在实际问题中并不适用。

3 核函数

在SVM中，核函数的构造和选择尤其重要。在满足Mercer条件的情况下，在SVM理论研究与实际应用中，最常使用的有以下4类基本核函数：线性核、多项式核、Gaussian核和Sigmoid核。采用Polynomial核和Gaussian核，其形式如下：

式中：γ、r、d—核参数。

4 核极化及核参数选择算法

Baram在2005年，针对于二分类问题，提出了一种核函数度量标准—核极化，核极化体现了核矩阵G与理想核矩阵yyT之间的相似度，其形式为：

式中：y=（y1，…yi）T，G—核矩阵，即是理想核矩阵，＜·，·＞F表示具有同样维数的一对矩阵之间的Frobenius内积。针对多分类问题，文献[9]提出了一个新的适应于多分类（也适应二分类）情形的核函数度量标准：

式（7）清楚地显示，核极化是一个标量值，其值越大意味着在特征空间中同类的数据点相互靠近，而异类的数据点相互远离[9]。P可以度量多分类样本的可分性，P值越大说明其数据集样本在设定的核函数下具有越好的可分性，以此建立的SVM模型，具有越强的泛化能力。值得关注的另一点是，其计算复杂度为O（l2），具有高效计算性。采用核极化P来指导Gaussian核和Polynomial核的核参数的选择，选择使得Pmax（γ）的γ值，此时，γ值对应的最大值P说明其数据集样本在该γ值时具有较好的可分性。较优γ值的选取我们采用网格搜索法，其算法步骤如下：（1）（初始化）核函数的 Pmax及 γ 值，设置 γ1=γmin=2-8，γmax=28，r=1，d=3；（2）（迭代）对于每一个 γi=γi-1·4，计算其对应的 Pi；（3）若 Pi≥Pmax时，更新 Pmax和γ值；（4）转到第2步，直到满足停机条件。实验对应的算法流程图，如图1所示。

图1 核参数选择算法流程图Fig.1 The Flow Chart of Kernel Parameter Selection Algorithm

5 实验

5.1 数据处理

UCI数据库中的 7 个数据集：Breast Cancer Wisconsin，Iris，Wine，Car，glass，Zoo，Balance。其中 Breast Cancer Wisconsin 为二分类数据集，其余均为多分类数据集。数据集的基本情况，如表1所示。每个数据集都经过归一化（0，1）预处理，即：

式中：i—样本的某个输入特征。选取总样本数的70%为训练集和30%为测试集，采用libsvm软件包（该软件包采用1-v-1的方法）实现了多类SVM分类。

表1 实验使用的数据集Tab.1 Data Sets for Experiments

5.2 评价指标

实验中选用分类正确率（又称为分类精度）作为算法的评价指标。其表达式为Acc=Cor/Tot，Cor为分类正确的样本点数，Tot为总样本点数，Acc为分类正确率。

5.3 实验方法

设置Gaussian核和Polynomial核的核参数γ的取值范围为γmin=2-8，γmax=28。首先，利用前面所介绍的核参数选择方法，选择出Pmax（γ）的γ值。然后，用选择出的γ和设置惩罚系数C=80，训练和测试SVM。为验证所提出基于核极化的核参数选择算法的有效性，选择目前SVM最常用经典的10折交叉验证法作为比较。设置惩罚系数 C=｛2-8，2-6，…，28｝和 γ=｛2-8，2-6，…，26，28｝，利用 10折交叉验证法选择出最优参数组合和进行测试。所有实验的平台为Intel（R）Core（TM）2 Duo CPU E8200@2.66GHz 2.00GB RAM的个人计算机，Win732位操作系统。实验流程图，如图2所示。

图2 实验方法流程图Fig.2 The Flow Chart of Experimental Methods

5.4 实验结果及其分析

实验方法的多类SVM分类准确率的平均值（采用10次实验的平均值），如表2所示。对应于表2各数据集实验结果的运行时间，如表3所示。

表2 数据集上的实验结果Tab.2 Experimental Results of Data Sets

表3 实验结果的运行时间Tab.3 Running Time of Experimental Results

表2的2～3列或4～5列的数据显示，对于Gaussian核或Polynomial核采用方法的SVM的泛化能力并不弱于10折交叉验证法，大部分数据集的准确率高于10折交叉验证法。表3说明采用方法计算的高效性。表2的第2列与第4列和第3列与第5列说明，只有一个核参数r的Gaussian核比有三个核参数的Polynomial核在分类方面具有更高的准确率，但是，不可忽视的是，在分类准确率上略逊于Gaussian核的Polynomial核的运行时间远小于Gaussian核。以上分析说明，所提出的基于核极化的核参数选择算法的有效性，计算的高效性。同时，也说明了Polynomial核虽然没有Gaussian核的调整核参数少，分类精度高等优点，但是其运行速度的高效性也同样值得我们关注。

6 结论

在深入分析核极化这个核度量标准的基础上，提出了利用直接最大化核极化来选择核参数值的算法，并将其运用到Gaussian核和Ploynomial核的核参数r选择中，提升了多类SVM的分类性能。在整个核函数的核参数选择过程中无须反复地训练和测试SVM，也不需要求解一个额外的、复杂的二次规划问题，因而计算是高效的。

［1］Boser B E，Guyon I M，Vapnik V N.A training algorithm for optimal margin classifiers［C］.5th Annual ACM Conference on Computational Learning Theory.Pittsburgh，PA，ACM Press，1992：144-152.

［2］舒文杰，徐桂芳，魏国前.SVM的起重机金属结构安全评估研究［J］.机械设计与制造，2014（12）：269-272.（Shu Wen-jie，Xu Gui-fang，Wei Guo-qian.Metal structure safety assessment of crane based on SVM［J］.Machinery Design＆Manufacture，2014（12）：269-272.）

［3］陈健飞，蒋刚，杨剑锋.改进ABC-SVM的参数优化及应用［J］.机械设计与制造，2016（1）：24-28.（Chen Jian-fei，Jiang Gang，Yang Jian-feng.Improved ABC-SVM parameter optimizationand application［J］.MachineryDesign ＆ Manufacture，2016（1）：24-28.）

［4］Duan K B，Keerthi S S，Poo A N.Evaluation of simple performance measures for tuning SVM hyperparameters［J］.Neurocomputing，2003（51）：41-59.

［5］常群，王晓龙，林沂蒙.支持向量分类和多宽度高斯核［J］.电子学报，2007，35（3）：484-487.（Chang Qun，Wang Xiao-long，Lin Qi-meng.Support vector classification and Gaussain kernel with multiple widths［J］.Acta Electronica Sinica，2007，35（3）：484-487.）

［6］汪廷华，陈峻婷.核函数的度量研究进展［J］.计算机应用研究，2011，28（1）：25-28.（Wang Ting-hua，Chen Jun-ting.Survery of research on kernel function evaluation［J］.Application Research of Computers，2011，28（1）：25-28.）

［7］Cortes C，Mohri M，Rostamizadeh A.Algorithms for learning kernel based on centered alignment［J］.J Mach Learn Res，2012（13）：795-828.

［8］Wang Ting-hua，Zhao Dong-yan，Tian Shen-feng.An overview of kernel alignment and its applications［J］.Artif Intell Rev，2015（43）：149-192.

［9］汪廷华，赵东岩，张琼.多类核极化及其在多宽度RBF核参数选择中的应用［J］.北京大学学报：自然科学版，2012，48（5）：727-731.（Wang Ting-hua，Zhao Dong-yan，Zhang Qiong.Multiclass kernel polarization and its application to parameter selection of RBF kernel with multiplewidths［J］.ActaScientiarumNaturaliumUniversitatisPekinensis，2012，48（5）：727-731.）

［10］Hsu C W，Lin C J.A comparison of methods for multiclass support vector machines［J］.IEEETransactions on Neural Networks，2002，13（2）：415-425.