刘屹成，刘晓燕，严 馨

(昆明理工大学 信息工程与自动化学院，云南 昆明 650500)

支持向量机（Support Vector Machines,SVM）[1]由Vapnik 提出，是一种常见而有效的机器学习方法.它以统计学习理论为基础，利用核方法针对结构化风险最小化得到支持向量.因为其拥有坚实的理论基础和良好的泛化性能，SVM 已经被广泛应用于模式分类和回归领域[2-4].其优势有：①SVM基于小规模样本统计学习理论，避免了传统方法在样本趋于无穷时追求渐近性能的问题，从而更符合实际应用；②与传统的基于经验风险最小化的机器学习方法相比，SVM 遵循了结构风险最小化的原则，即不追求训练样本的最小分类误差，而是使训练误差概率的上界最小，该方法避免了过拟合问题；③SVM 的本质在理论上是解决一个凸二次优化问题获得全局最优解，克服了其他机器学习方法的局部极值问题；④利用核方法，将原空间中的非线性可分问题转化为高维空间中的线性可分问题，该方法避免了求解显式非线性映射函数，保证了泛化性能，解决了维数灾难问题，可应用于图像、文本等高维数据的求解.SVM 的训练结果只依赖于少数支持向量而与非支持向量无关[5]，具有良好的自适应能力和鲁棒性.

SVM 训练过程的本质是求解一个凸二次优化问题，需要计算并存储一个核矩阵.因此，当训练数据集规模较大时，时间和空间复杂度很高.针对这一问题，已有一些早期的数学改进方法，如梯度投影法、约梯度法、活动集法、内点算法等，以及一些通用的优化软件包，如MINOS、CPLEX、LOQO、QP Routine 等.然而，对于大规模数据集，这些方法的学习效率是有限的.因此，如何结合其他方式，提高训练效率，是一个重要的问题.

近年来，张鹏翔等[6]、刘泽燊等[7]、Nie 等[8]、白玉辛等[9]分别在MapReduce、Spark、Hadoop 和Flink 平台以级联支持向量机（Cascade SVM,CSVM）[10]为基础实现了相应的训练算法.这些方法与传统的直接训练方式相比，训练速度有了较大的提升，但因为分组训练会丢失部分支持向量而导致其得到的模型精度有所下降.同时，这些方法并没有对训练节点进行合理的资源配置，导致训练节点的资源浪费.这在集群规模较小的情况下可能不会有太大的影响，但在集群规模较大的情况下，这些资源的浪费则是个不可忽视的问题.

Apache Flink 作为新一代的分布式计算框架，具有低延迟、高吞吐等优势，与其他主流框架相比，Flink 具有极高的迭代计算效率[11-13].但Flink 需要用户进行初始资源配置，该配置在作业开始后不再改变[14].所以需要辅以面向Flink 的动态资源分配策略[15]，以达到更好的资源利用率.而以级联支持向量机为基础的平衡级联支持向量机（Balanced Cascade SVM,BCSVM），通过平衡子数据集中样本类别的比例，再对子数据集的训练参数进行放缩的方式，有效降低分布式训练时全局支持向量的丢失概率，从而提高分布式训练得到模型的预测精度.

为了加快训练速度，同时提高模型预测精度和减少资源占用，文中将平衡级联支持向量机算法与Apache Flink 相结合，再利用动态资源分配策略对Flink 集群的资源进行细粒度管理.采用这种方法进行训练，其训练时间为传统方式的1/S（S为单次分组的最大子集数），资源利用率较以往实现有所提高，并且预测精度与传统方式相比差距在0.1%以内.

1 平衡级联支持向量机

支持向量机的原问题如下：

式中：C代表惩罚参数，C取值越大，分类器就越接近硬间隔分类器，C取值越接近0，对错误分类的接受能力就越大；ξi是非负松弛变量.其对偶问题如下，α为Lagrange 乘子，K(xi,xj)代表核函数.

由于SVM 只依赖训练样本集中的支持向量进行决策，非支持向量不起作用，只是一种无用信息，将其剔除完全不影响训练结果.正是对这种无用信息的处理占据了算法的主要时间，因此加快SVM 训练速度的其中一个思想就是“分组”.所谓分组就是将原样本集分成许多子集，每一步只对一个子集用SMO（Sequential Minimal Optimization）算法优化，利用训练后能将非支持向量剔除的特性加快训练速度.

级联支持向量机就是采用分组的思想对数据集进行处理，从而减少训练时间.算法首先将整个数据集分成若干个子数据集，之后对每个子集并行训练，将得到的局部支持向量（从训练子集得到的模型中提取的支持向量）两两合并作为下一层的输入.如果前几层能够过滤掉绝大部分的非支持向量，那么最后一层只需处理很少的样本.

该算法的优点是每个子集仅需处理部分数据，且每个子集间的训练是独立的，能够很好地进行并行计算，所以与直接训练整个数据集相比，级联支持向量机极大地加快了训练速度.分组并行SVM 算法特别适用于样本个数多、支持向量少的数据集，在此种情形下训练时间和内存占用都表现出非常明显的优势，因为每次分组都能将大部分的样本过滤.但其缺点也同样明显，对于支持向量在数据集中占绝大部分的情形，因为每次分组训练基本不能起到过滤样本的作用，极端情况下其训练速度甚至会比直接训练要慢.以往在大数据框架下实现基于级联支持向量机的算法，其分组方式都依赖框架提供的API（Application Program Interface）将数据集随机地发送到各个节点，该方式未考虑到各类样本的规模比例对最终训练结果的影响，所以其更容易丢失全局支持向量（不分组训练情况下，从训练得到的模型中获得的支持向量），从而导致最终得到的模型精度与直接训练相比存在一定的误差.

平衡级联支持向量机是指级联支持向量机中的一种特定分组方式，平衡级联支持向量机平衡了分组后子数据集中的样本比例，即每个子数据集中的样本比例都与原数据集相同.此外，在训练子数据集时还对原定的训练参数进行了缩放，以获取更多的局部支持向量，降低全局支持向量在子数据集中丢失的概率.与以往的随机分组方式相比，采用该分组方式能较大概率保留全局支持向量，从而有更好的泛化性能.其有效性的简要说明如下：给定数据集L，其存在P={Pi|i=1,2,···,n}种分组方式，每种分组方式都是由任意个子集sj组成的集合，即Pi={sj|j=1,2,···,m}，其中s1∪s2∪···∪sm=L，且∀j1≠j2,sj1∩sj2=∅.由于最终结果仅与支持向量有关，故不论是何种分组方式，其保留全部全局支持向量的样本组合方式都是相同的.假设其中存在k种分组方式 |P1,P2,···,Pk|∈P，其中的任意一个分组方式Pk中的任意一个子集都能保留全部的全局支持向量，所以在这k种情况下，分组训练最终得到的模型与直接训练相比是毫无差别的.用TR、TB分别表示随机分组和平衡分组的总分组数，则得到无损模型的概率分别为：k/TR、k/TB.因为平衡分组为随机分组的子集，所以显然有TR≥TB，故平衡子集能以较大概率保留全部的全局支持向量.

2 Flink 下平衡级联SVM 的实现

算法的训练过程如图1 所示，在训练之前，需要对数据集进行平衡分组及统计样本数量的预处理.分块后的子数据集中，各类样本所占比例始终与原数据集相同.由于Flink 集群中的TaskManager（类似于一台机器，也被称为Worker）属性需要在启动前配置好，在启动后基本无法更改，真正用于执行任务的Task Slot（相当于TaskManager 上的一个执行任务的容器）在默认情况下是根据配置平分TaskManager 中的所有资源.故此处需要采用动态资源分配策略，对TaskManager 中的资源进行细粒度管理，与默认的粗粒度资源管理的对比如图2所示.在动态资源分配策略下，各节点所需最小资源集的计算方法为存储样本所需内存加上核函数矩阵所需内存，如在LibSVM[16]中，其计算方法如下：

图2 不同粒度下的资源管理Fig.2 Resource management at different granularity

式中：n为分配到各节点的样本数量，di为各样本的实际有效维度(即取值不为0的维度)，4表示float类型的占用空间，220表示所需内存空间的单位为MB.该方法可以根据样本数量决定节点所需的实际内存大小，也可以根据节点的资源属性为不同规模的数据集采取相应的任务调度策略[17].

算法工作需要提供3 个参数：dataSet 代表需要训练的数据集；classifyNum 指每层训练时的子数据集个数；param 表示训练所需的参数，如惩罚参数C.算法首先使用Flink 所提供的API 得到对应的执行环境env；其次，预处理部分采用自定义的方法splitDataSet()对数据集平衡分组；接着，将子数据集转换为可由Flink 处理的DataStream 数据模型dataStream；随后，通过calculateMemory()方法计算slot 所需要的最少资源，并通过clip()方法对计算结果进行裁剪，防止超出上限；再使用计算结果配置节点属性，并将其注册到集群中；之后，训练子数据集时利用scale()方法放缩参数；最后，调用Flink 提供的mapPartition()并行训练.当第1 层训练过后，子数据集中的大量非支持向量都被过滤，同时保留局部支持向量V.第1 层训练过后将局部支持向量合并，合并后的局部支持向量作为数据集进入下一次训练流程.如果实践过程中发现数据集在第一次训练得到的局部支持向量个数在能接受的范围内，则可直接进行最终的训练.子数据集训练完成后合并所有的局部支持向量得到一个数据集G，最后在该数据集上用原定参数训练得到最终的模型GModel 该算法的描述如算法 1 所示.

该算法与以往的不同之处在于数据集的分组方式、子数据集的参数选择以及训练节点的生成方式.在以往的实现过程中，子集由原数据集随机分组得到，且子集的训练参数与原数据集完全相同.该算法将随机分组修改为平衡分组，子数据集的参数则是通过放缩原数据集的参数得到，以此降低全局支持向量丢失的概率.此外，之前的实现方式中，对子数据集的训练节点分配是将任务提交到集群中后就由集群自行分配节点，而集群的通用分配策略难免会对资源造成浪费.因此在此算法中，采用了一种细粒度的资源管理策略，即将任务提交到集群中后，由任务规模来决定节点所需资源的大小，这样能最大限度地减少资源浪费.

算法 1Flink 下平衡级联SVM 的实现

3 实验与结果分析

3.1 实验环境与数据集实验使用的数据集包括a9a（样本数：32 561，特征维度：123），ijcnn1（样本数：49 990，特征维度：22），codma-rna（样本数：59 535，特征维度：8），covtype.binary（样本数：581 012，特征维度：24）.4 个二分类数据集（数据集来源：https://www.csie.ntu.edu.tw/～cjlin/libsvmtools/datasets/）.训练前对数据集进行了归一化处理，同时将数据集中的类别标号统一修改为-1 和+1.详细的软件配置如表1 所示，任务调度模式采用standalone.硬件则是利用4 台云服务器构建的集群，每台服务器有双核CPU 和2 GB 内存.Flink 中每个Woker 配置了2 个Slot，训练时的缓存大小设置为300 MB.各数据集所应用的参数如表2 所示，其中子集训练参数C和 γ的缩放倍数为0.5.

表1 所使用的软件版本Tab.1 The software version used

表2 各数据集参数设置Tab.2 Parameter settings of each dataset

3.2 不同算法在训练时间、内存及准确率方面的表现为了与该算法进行比较，在相同的软硬件配置下实现了以往基于Flink 的并行SVM 算法FLSVM(Flink SVM)[9]，以及提出的Flink 平台下的平衡级联SVM 算法FL-BCSVM (Flink Balanced Cascade SVM)，FL-BCSVM 包含了与FL-SVM 使用相同参数组合的FL-BCSVM-S 以及不同参数组合的FL-BCSVM-D，同时把不分组直接训练整个数据集的训练方式称为Direct，其中直接训练是在训练集群的任意一台服务器上完成的.实验所采用的训练集为a9a、ijcnn1 和codma-rna 3 个标准数据集，训练时都仅用了2 层训练，第1 层的分组数为8.

图3 评价了不同算法在训练这些数据集时所消耗的时间和内存占用，以及得到模型的预测准确率.由图3(a)可见，FL-SVM、FL-BCSVM 这两种训练方式所需时间相差无几，但从图3(b)可以明显看出FL-BCSVM 较FL-SVM 的内存占用更低.而如图3(c)所示，FL-BCSVM 得到的模型预测准确率仅次于直接训练，此外采用缩放策略的FLBCSVM-D 得到的模型预测准确率要高于未使用缩放策略的FL-BCSVM-S.FL-SVM 和FL-BCSVM两种训练方式与直接训练相比，内存占用普遍更高，但从图3(a)中可以看到直接训练一个非常明显的缺点是训练时间较长.之所以会出现这种现象，是因为这3 个数据集经过分组之后，其样本数对于每一个节点而言，属于小数据集，故而其核函数矩阵能完整地存储在内存中，所以FL-SVM 和FLBCSVM 的训练时间都相差不大，而FL-BCSVM 则能根据样本数进行细粒度的资源管理，从而实现比FL-SVM 更低的内存占用.对于直接训练而言，一个训练节点的内存显然不能将所有的核函数矩阵存入内存中，所以存在重复计算样本间的核函数的现象，这就导致其训练时间会远大于其他算法.在准确率方面，直接训练通常最高，采取分组训练的其他算法的准确率与之相比均有所降低.但因为测试集的原因，也会偶尔出现分组训练得到的模型预测准确率比直接训练高的情况.从图3(c)中也可以看到，采用相同参数组合的FL-BCSVM-S 算法的准确率较FL-SVM 算法有所提高，其原因为采取平衡分组能够降低全局支持向量丢失的概率，所以FL-BCSVM算法能在分组训练时保留更多的支持向量，从而减少分组训练的误差.而采用的参数调整策略的FL-BCSVM-D 算法可以在训练子数据集时进一步保留更多的支持向量，所以其得到的模型预测准确率有所提高，准确率与Direct 训练方式相比差距在0.1%以内，但代价则是训练速度较FLBCSVM-S 算法有所降低.

图3 不同算法的训练时间、内存占用及准确率Fig.3 Training time,memory usage and accuracy of different algorithms

3.3 数据规模对算法的影响为了研究数据规模对算法的影响，本文采用了在covtype.binary 数据集中随机抽取部分数据作为训练的方法.图4 显示的是在不同数据规模下FL-SVM，FL-BCSVM，Direct的训练时间和内存占用对比.从图4(a)可以看出，FL-SVM 和FL-BCSVM 算法的训练时间最初相差无几，但是随着训练样本的增加，FL-BCSVM 的训练时间明显比FL-SVM 更少；图4(b)显示FLBCSVM 的内存占用也随着样本数的增加而增加.FL-SVM 与Direct 内存占用也在增加，不过其增加的内存为存储样本集所需的内存，故增势不明显.当样本数较少时，FL-SVM 能在一开始指定的内存中完整存储所有的核函数矩阵，但随着数据规模的增加，FL-SVM 逐渐需要对样本间的核函数结果进行重复计算，从而导致训练时间的延长.FL-BCSVM则通过动态调整资源，增大内存占用来降低训练时间.但随着样本数的进一步增加，FL-BCSVM 也会达到节点的资源上限，所以与其他两种算法相比，其训练时间的减少速度也会放缓.

图4 不同数据集规模下训练时间和内存占用情况Fig.4 Training time and memory usage under different dataset sizes

4 结论

文章提出的算法利用平衡分组的对数据集进行分组，同时调整了子集的参数.实验结果证明，利用该方式得到的模型精度和以往相比有明显的提高.同时算法能根据样本规模动态调节训练节点所需资源，或是根据训练节点的资源属性，灵活地分配与训练节点对应规模的数据集.在样本规模较小时，分配较小的资源给训练节点，避免集群资源的浪费；在样本规模较大时将其分配到有足够资源的训练节点上，减少训练时间.该方法的不足之处在于集群资源是有限的，所以样本规模大到一定程度时，同样会因为资源的不足导致训练时间变长，而资源上限的设置与训练时间之间的关系需要用户自己去权衡.此外，参数放缩的倍数也依赖于以往经验，若设置得不当，可能会出现无法过滤子集中的样本，从而出现训练时间过长的情况.极端情况下，分组训练完全不能过滤非支持向量，其训练时间为直接训练方式的L倍（L为训练层数-1）.当然，因为其并没有改变SMO 算法的时间复杂度，所以最佳情况下每个子集训练后都能过滤绝大部分非支持向量，最后处理唯一数据集时只需训练非常少的样本，在此情况下训练时间为直接训练的1/S倍（S为单次分组的最大子集数）.