2021, Vol. 44
使用大规模样本数据训练SVM模型时存在计算效率问题，对样本进行稀疏化，能有效减少SVM模型的训练时间，但样本稀疏化后，一些支持向量也会被删除，数据会出现失真，进而影响模型的准确度。如何在尽量保证模型准确度的情况下进行样本数据的稀疏化，是一个待研究问题。现在有使用随机采样的方法，也有使用全局代表点替代的方法，但都会造成支持向量的缺失。通过研究SVM算法的特点，利用支持向量点和凸包顶点的相似性，引入计算机图形学的凸包算法，通过求解训练数据集的凸包点，获取最多的SVM分类支持向量，排除非支持向量，在尽可能保证训练样本数据特征的情况下，实现样本数据的稀疏化，进而降低SVM模型的训练时间。
同时使用径向基核函数(RBF, radial basis function)的SVM模型分类精度受到核参数g和惩罚因子c的影响较大，如果参数设置不当，SVM分类的精度将会下降[1]。如何获取最优参数是一个优化求解问题，现在常采用交叉验证法，这种方法需要同时验证g和c的在给定取值范围中的所有组合，算法的时间复杂度高，效率低，为了快速获取SVM分类的最优参数，引入遗传算法进行g和c的优化求解，进一步降低了SVM模型的训练时间。
通过上面2方面的创新和改进，提出了改进优化的SVM训练算法，在保证SVM模型分类精度的情况下，提高SVM模型训练效率。
1 SVM算法SVM支持向量机是一种二分类模型，在机器学习分类算法中，SVM是应用很广的一种算法[2]，其算法的本质，是通过将样本数据映射到一个高维空间中，然后在空间中寻找一个超平面，这个超平面能够准确地分开2类数据样本并使得其间隔最大化。这个超平面称为分离超平面。
如图 1所示，分离超平面可以使用公式表示为
| $H: \boldsymbol{W}^{\mathrm{T}} \cdot \boldsymbol{X}+b=0 , $ |
|
图 1 SVM算法示意图 Fig. 1 Schematic diagram of SVM algorithm |
其中，WT是权重向量，b是偏移。这样位于分离超平面两侧的点可以表示为
| $\boldsymbol{W}^{\mathrm{T}} \cdot \boldsymbol{X}+b>0 或者 \boldsymbol{W}^{\mathrm{T}} \cdot \boldsymbol{X}+b<0 , $ |
可以调整权重使得2个边缘超平面定义为
| $H 1: \boldsymbol{W}^{\mathrm{T}} \cdot \boldsymbol{X}+b=-1 ,\\ H 2: \boldsymbol{W}^{\mathrm{T}} \cdot \boldsymbol{X}+b=1 。$ |
这样所有位于H1平面上方的点都被归类为-1类型，所有位于H2平面下方的点都被归类为1类型，所有位于H1或者H2平面上面的样本点被称为支持向量。从分离超平面到H1的距离是
| $\left\{\begin{array}{l}\min \mathit{\Phi}(\omega)=\frac{1}{2}\|\omega\|^{2}+c\left(\sum\limits_{i=1}^{N} \xi_{i}\right) , \\ y_{i}\left(\omega \mathit{\Phi}\left(x_{i}\right)+b\right)>=1-\xi_{i}, \xi_{i}>=0 。\end{array}\right.$ |
使用拉格朗日公式和KTT条件优化公式，最后问题转换为求解L最大值问题
| $\left\{\begin{array}{l}L_{\max }=\sum\limits_{i=1}^{N} a_{i}-\frac{1}{2} \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} y_{i} y_{j} a_{i} a_{j} exp \left(-g\left\|x_{i}-x_{j}\right\|^{2}\right), \\ \sum\limits_{i=1}^{N} a_{i} y_{i}=0, a_{i}>=0 。\end{array}\right.$ |
核参数g的取值影响模型的分类精度，惩罚因子c影响模型的推广能力，如果c取值过大SVM分类模型将会过拟合[1-6]。
2 Convex Hull凸包(convex hull)是一个源自于计算机图形学的概念，其数学定义为：在一个N维向量空间Q中，对于一个给定的集合P，所有包含P的凸集的交集C就是P的凸包[7-10]。
如图 2所示，在二维平面空间中，凸包就是过集合中的一些点，做凸多边形，使得这个凸多边形能包围所有集合中的点，这个多边形就是凸包。
|
图 2 二维凸包示意 Fig. 2 Two dimensional convex hull diagram |
遗传算法(GA, genetic algorithm)，是一种模仿达尔文生物进化论的自然选择原则和遗传学原理的计算模型，是一种寻找最优解的方法。
如图 3所示，遗传算法首先对要求解的问题值进行编码，然后初始化种群，对种群中的个体进行适应度评估，淘汰适应度不满足的个体，然后从现存的种群中，随机选择一些个体进行交叉和变异，产生新的种群，然后判断是否满足终止条件，如果满足就结束流程，如果不满足则继续进行演化[11-14]。
|
图 3 遗传算法流程图 Fig. 3 Flow chart of genetic algorithm |
针对SVM处理大规模训练数据集存在性能问题和参数优化问题，提出使用凸包算法进行样本数据集稀疏化以及遗传算法进行参数优化的改进SVM算法(CH-GA-SVM)。
4.1 凸包样本稀疏化由于进行超平面求解所使用的支持向量都在训练数据集的最边缘，所以使用凸包算法进行训练数据集的边缘识别，并使用凸包中的样本点作为训练数据集，这样就对SVM模型训练数据集进行了稀疏化[8-10]。
4.2 遗传算法参数化SVM参数优化问题主要是对核参数g和惩罚因子c进行最优值的求解，通常的做法是进行循环验证，所谓循环验证就是把参数g和c在取值空间中的所有组合进行验证，寻找出最佳的参数组合。这种方法算法的时间复杂度高，需要耗费大量的计算时间。遗传算法参数优化使用遗传算法进行最优g和c的求解，通过对g和c进行编码，产生初始种群，然后进行演化迭代，可以快速计算出最优的g和c[11-14]。
4.3 CH-GA-SVM算法流程如表 1所示CH-GA-SVM算法大致分为6个主要步骤：
|
表 1 CH-GA-SVM算法 Table 1 Algorithm CH-GA-SVM |
步骤1：载入原始的训练样本集，并把数据进行归一化处理，对于每个属性值，归一化处理的公式为：Vnew=
步骤2：把归一化后的样本集作为点集，求解N维空间中点集的凸包，维数N为输入样本集的属性个数。
步骤3：将凸包求解中返回的样本点进行唯一化处理，使得一个样本点只有一条记录，把唯一化后的凸包点集作为新的训练样本集。
步骤4：定义核参数g和惩罚因子c的上下界，并进行值的编码，编码采用二级制编码法。
步骤5：初始化染色体基于g和c参数的种群，开始进行遗传算法迭代，求解最优值。
步骤6：获取遗传算法返回的最优个体，使用最优个体对应的模型进行分类预测，如图 4。
|
图 4 4特征数据下各算法对比 Fig. 4 Comparison of algorithms under 4-features data |
硬件环境：Intel(R) Core(TM) i7-6700 3.4 GHz CPU及16 GB内存。
软件环境：Windows 10 OS及MATLAB R2019b[15-16]。
实验数据：脱敏后学校贫困生测试数据，包含8个特征，为了进行算法特征数量维度上面的性能分析，取包含其中的4个特征的全量数据作为数据集A，取包含全部的8个特征的全量数据作为数据集B。
数据A：训练数据集1 200条，测试数据集200条，特征数量为4个，分类数为2，贫困和非贫困。
数据B：训练数据集1 200条，测试数据集200条，特征数量为8个，分类数为2，贫困和非贫困。
|
|
表 2 数据集描述 Table 2 Description of datasets |
|
|
表 3 数据集A示例 Table 3 Example of dataset A |
|
|
表 4 数据集B示例 Table 4 Example of dataset B |
算法1：NCH-NGA-SVM，未进行训练数据稀疏化，使用循环验证法优化参数的SVM训练算法。
算法2：NCH-GA-SVM，未进行训练数据稀疏化，使用遗传算法优化参数的SVM训练算法。
算法3：CH-NGA-SVM，使用凸包算法进行训练数据稀疏化，使用循环验证法优化参数的SVM训练算法。
算法4：CH-GA-SVM，使用凸包算法进行训练数据集稀疏化，使用遗传算法优化参数的SVM训练算法。
5.3 实验指标及方法使用训练SVM模型消耗的平均计算时间、方差和模型的分类平均准确率、方差作为实验的指标。在相同数量的样本的对比实验中，采用5-折交叉验证法，分5次替换数据，每次替换样本中20%的数据，然后每次替换后样本测试3次，取总共15次的平均值和方差作为最后实验结果。
5.4 实验结果与分析|
|
表 5 实验结果数据 Table 5 Experimental data |
在模型训练计算时间上，由于各个算法计算时间差别很大，计算平均时间图和方差图纵坐标采用对数坐标。如图 4、5所示，在不同的样本数量和特征数量下面，传统的NCH-NGA-SVM算法模型计算时间最长，通过单独采用凸包或者遗传算法后，计算的时间都明显减少，凸包和遗传算法都使用的CH-GA-SVM模型计算的时间最短，效率最高。
|
图 5 8特征数据下各算法对比 Fig. 5 Comparison of algorithms under 8-features data |
在模型准确率方面，在样本的较少的训练数据下，采用凸包算法的CH-GA-SVM和CH-NGA-SVM准确率相对较低，这是因为凸包算法对数据做了稀疏化，输入的训练数据有失真造成的，但是当训练样本逐渐增多后，CH-GA-SVM算法的准确率也逐步提高，在1 000训练样本数据下准确率可以达到90%以上。同时随着训练样本数据的增加，模型准确率的标准差，也越来越小，表明模型稳定性越来越高。不同的特征数量下，特征越多各算法的计算时间都会相应增加，准确率方面差别不大。
6 结论笔者提出的CH-GA-SVM算法，通过凸包算法进行样本稀疏化，使用遗传算法进行核参数g和惩罚因子c优化，确实能显著改善SVM训练效率，缩短计算时间。同时凸包算法进行样本稀疏化后，模型准确度仍然能维持在一个较高水平，证明凸包算法稀疏化的样本集能很大程度保留原始数据的特征，使用凸包算法进行SVM训练样本稀疏化，具有一定的可行性。但是进行凸包稀疏化后，造成训练数据的部分失真，模型准确度下降，如何进行算法上的进一步改进，解决这个问题，后续还需要进行专门的研究。
| [1] |
Imbault F, Lebart K. A stochastic optimization approach for parameter tuning of Support vector machines[C]//Proceeding of the 17th International Conferenceon Pattern Recognition. Cam bridge, United Kingdom: [s.n.], 2004: 981-984.
|
| [2] |
Han J W, Micheline K B, Pei J. Data mining:concepts and techniques (third edition)[M]. San Francisco: Morgan Kauf mann, 2011: 211-286.
|
| [3] |
De Brabanter K, De Brabanter J, Suykens J A K, et al. Optimized fixed-size kernel models for large data sets[J]. Computational Statistics & Data Analysis, 2010, 54(6): 1484-1504. |
| [4] |
Huang K Z, Zheng D N, Sun J, et al. Sparse learning for support vector classification[J]. Pattern Recognition Letters, 2010, 31(13): 1944-1951. DOI:10.1016/j.patrec.2010.06.017 |
| [5] |
Theodorids S, Koutroumbas K. Pattern recognition, third edition[EB/OL]. 2006. https://www.researchgate.net/publication/258023950_Pattern_Recognition_Third_Edition.
|
| [6] |
Bao T Q, Mordukhovich B S. Relative pareto minimizers for multiobjective problems:existence and optimality conditions[J]. Mathematical Programming, 2010, 122(2): 301-347. DOI:10.1007/s10107-008-0249-2 |
| [7] |
周培德. 计算几何-算法分析与设计[M]. 北京: 清华大学出版社, 2003. Zhou P D. Computational geometry-algorithm analysis and design[M]. Beijing: Qinghua University Press, 2003. |
| [8] |
Ding S G, Nie X L, Qiao H, et al. A fast algorithm of convex hull vertices selection for online classification[J]. IEEE Transactions on Neural Networks and Learning Systems, 2018, 29(4): 792-806. DOI:10.1109/TNNLS.2017.2648038 |
| [9] |
Gu X Q, Chung F L, Wang S T. Fast convex-hull vector machine for training on large-scale ncRNA data classification tasks[J]. Knowledge-Based Systems, 2018, 151: 149-164. DOI:10.1016/j.knosys.2018.03.029 |
| [10] |
Wang D, Qiao H, Zhang B, et al. Online support vector machine based on convex hull vertices selection[J]. IEEE Transactions on Neural Networks and Learning Systems, 2013, 24(4): 593-609. DOI:10.1109/TNNLS.2013.2238556 |
| [11] |
Royachka K, Karova M. High-performance optimization of genetic algorithms[C]//200629th International Spring Seminar on Electronics Technology, May 10-14, 2006. Germany: IEEE, 2006.
|
| [12] |
Srinivas M, Patnail L M. Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE Transactions on Systems, Man and Cybernetics, 1994, 24(4): 656-667. DOI:10.1109/21.286385 |
| [13] |
Chuang Y C, Chen C T, Hwang C. A simple and efficient real-coded genetic algorithm for constrained optimization[J]. Applied Soft Computing, 2016, 38: 87-105. DOI:10.1016/j.asoc.2015.09.036 |
| [14] |
Michalewicz Z. Evolution programs and heuristics[M]. Berlin, Heidelberg: Springer Berlin Heidelberg, 1996: 307-327.
|
| [15] |
Chang C C, Lin C J. "LIBSVM:A library for support vector machines[J]. ACM Transactions on Intelligent Systems & Technology, 2011, 2(3): 389-396. |
| [16] |
Gong C, Wang Z L. Proficient optimization with mailab[M]. Beijing: Publishing House uf Electronics Industry, 2009: 315-320.
|