参数并行：一种基于群启发式算法的机器学习参数寻优方法

杨艳艳， 李雷孝*， 林浩， 王永生 ， 王慧， 高静

(1.内蒙古工业大学数据科学与应用学院， 呼和浩特 010080； 2.内蒙古自治区基于大数据的软件服务工程 技术研究中心， 呼和浩特 010080; 3.内蒙古农业大学计算机与信息工程学院， 呼和浩特 010010)

随着大数据时代的到来，越来越多的机器学习算法被应用于数据处理和分析中[1]。为了训练出准确率较高的模型，模型训练者不可避免地要对机器学习算法中可调整的参数寻优。如果参数取值不当，将会严重影响模型的性能[2]。而在进行机器学习的参数寻优时，需将多组参数输入机器学习算法中，利用训练得到的模型的准确率和泛化能力作为参数寻优的标准评价指标。这就意味着机器学习的参数寻优是一个极其耗时的过程，每评价一次参数就需要训练一次模型。基于数据并行的并行训练方法是目前提高机器学习训练效率的主流方法，该方法将训练数据划分后分配到各个工作节点上，各节点使用分到的数据对模型按照某种优化方法进行更新[3]。但在考虑参数寻优时，它的训练效率常常不尽如人意。目前为止，如何提高机器学习的参数寻优效率仍是一个棘手问题。

近几年来，针对机器学习参数寻优的问题，大量学者进行了研究。首先用于实践的是人为的手动调参。但由于手动调参不确定性大且耗时耗力，因此新的方法被应用到机器学习参数寻优。比如Cui 等[4]、李瀚等[5]提出利用改进的网格搜索算法来提高机器学习最优参数的搜索效率。李坤等[6]提出了基于Spark并行计算框架进行网格搜索的并行计算，以找到支持向量机(support vector machines， SVM)的最优参数。但网格搜索算法实际上是对固定范围内的所有参数取值进行遍历搜索，且传统的网格搜索仅仅是通过改变步长来提高搜索效率。网格搜索的并行计算虽然在一定程度上提高了参数寻优的效率，但参数寻优的范围和步长会直接影响参数的优化程度。另一方面，网格搜索算法只适用于参数较少以及参数范围较小的情况下。在参数多，取值范围较广的情况下使用网格搜索算法，将会存在计算复杂、耗时长等问题[7]。

针对使用网格搜索算法对机器学习算法的参数寻优时精度较低的问题，群启发式算法被广泛应用于机器学习的参数寻优中。王丽婷等[8]提出了利用乌鸦搜索算法求SVM的最优参数组合，实验证明此模型具有较高的分类准确度。Wang 等[9]采用遗传算法(genetic algorithm， GA)求解SVM最优参数，实验结果表明此模型预测效果较好。潘成胜等[10]针对K-means算法在文本聚类过程中易陷入局部最优解的问题，提出了一种基于灰狼优化算法的K-means文本聚类方法。实验结果表明，该方法的准确率、召回率和F值都有明显提高，文本聚类结果更可靠。依据经验调整参数会导致随机森林模型性能不佳，邹宗民等[11]提出基于粒子群优化支持向量回归的方法。基于具有较强搜索能力的粒子群算法来获取支持向量回归模型的最优参数组合。除此之外，还有生物地理学优化算法(biogeography-based optimization，BBO)[12]、布谷鸟搜索算法(cuckoo search，CS)[13]、磷虾群(improved krill herd，IKH)[14]算法等群启发式算法被用于机器学习的参数寻优中。目前基于各种改进或者未改进的群启发式算法用于机器学习算法的参数寻优的研究，虽然解决了机器学习参数寻优精度的问题，在一定程度上耗时也有所降低。但是机器学习参数寻优的效率依然没有达到质的提升。基于数据并行机制的训练方式可以用来解决群启发式算法进行机器学习参数寻优效率低的问题，但是基于数据并行的机制只有在大数据量下，优势才会逐渐体现出来。因此目前仍然没有一个很好的方案来解决基于群启发式算法的机器学习参数寻优效率低的问题，参数寻优效率仍有上升空间[15]。

现通过对比实验验证在机器学习参数寻优方面，群启发式算法相较于网格搜索算法的优越性。另外对群启发式算法应用于机器学习参数寻优时的各部分耗时进行分析。针对使用数据并行机制来解决求解种群个体适应度耗时问题时的不足，提出一种基于参数并行机制的机器学习参数寻优方法。该方法利用Spark并行计算框架将群启发算法中的种群转化为Spark所支持的弹性分布式数据集(resilient distributed dataset，RDD)，然后将RDD切分并分发到各个节点，各个节点并行计算种群个体适应度。使用GA和RF算法验证了基于参数并行机制的机器学习参数寻优方法的先进性、效率以及可扩展性。

1 相关技术

1.1 机器学习算法及其参数

机器学习是一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。机器学习研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构，使之不断改善自身的性能。

机器学习算法的参数可以分为模型参数和模型超参数。模型参数是可以通过数据学习过程进行初始化和更新的一种参数，不需要手动设置。模型超参数是无法直接从数据学习中估计出来的参数，必须在训练机器学习模型之前进行设置。比如训练神经网络的学习速率、SVM的惩罚参数c和RBF核参数g等。学习速率太大会导致神经网络的权重更新的幅度大，梯度下降法可能会越过最低点，导致权重在极值点两端不断发散或者剧烈震荡。学习速率设置太小，则会使神经网络的权重更新速度太慢，导致无法快速找到好的下降的方向。对于SVM来说，c的取值直接影响SVM模型的泛化能力。c太大，容易出现过拟合，c太小，容易出现欠拟合。g越大支持向量越少，g越小支持向量越多。而支持向量的个数会影响SVM模型训练与预测的速度。因此机器学习模型超参数的选择将会直接影响训练好的机器学习模型的性能。

1.2 机器学习参数寻优形式化描述

利用群启发式算法进行机器学习算法的参数寻优，将其寻得的参数用作机器学习算法训练模型的超参数。设er为机器学习训练模型的误差，P为超参数集合，则机器学习参数寻优问题定义为

miner=F(P)

(1)

(2)

式中：k为需要寻优的机器学习算法超参数的个数；pimin、pimax为超参数pi的变化范围。种群中的一个个体对应一组P。P的更新依赖于种群的更新。例如，GA通过种群个体的交叉、变异等操作来更新种群，经过解码更新过后的个体得到新的P；PSO根据找到的当前个体极值和整个粒子群共享的当前全局最优解来更新自己的速度和位置，经过解码更新过后的粒子得到更新过后的P。当满足终止条件时，终止算法。终止条件为

(3)

式(3)中：fitnessbest为拥有最优解的个体适应度；fitnessmin为算法设置的最小适应度；T为迭代次数；Tmax为算法设置的最大迭代次数。当种群最优个体的适应度大于算法设置的最小适应度或者迭代次数大于算法设置的最大迭代次数时，终止迭代，返回最优参数作为机器学习算法的模型超参数。

1.3 Spark平台

Spark是专门基于大数据而设计的通用计算引擎[15]，可以完成包括SQL查询、文本处理、机器学习等各种运算[16]，能够解决由于单机计算资源不足而导致运行速度慢、检测效率低等问题[17]。Spark基于内存的运算速度比Hadoop MapReduce快100倍以上，而且拥有Hadoop MapReduce具有的所有的优点。Spark将数据抽象为其特有的RDD。在Spark中，对数据的操作主要有创建RDD，转化已有RDD以及调用RDD操作进行求值，Spark会自动将RDD中的数据分发到集群上，进行并行化计算[18]。

Spark还提供了很多程序库，包括Spark SQL、Spark Streaming、MLib、GraphX。其中MLib库是Spark提供的可扩展的机器学习库。Mlib库是专为在集群上并行运行的情况而设计的，提供了很多种机器学习算法，包括分类、回归、聚类、协同过滤等。Mlib的设计理念就是把数据以RDD的形式表示，然后在分布式数据集上调用Mlib库所提供的机器学习算法。

2 基于参数并行的机器学习参数寻优

2.1 参数寻优耗时分析

在群启发式算法中，其操作都可分为初始化种群、计算种群个体适应度、种群更新3个部分。初始化种群部分包括种群参数的设置、种群个体初始化以及种群个体适应度的初始化。种群更新部分为根据种群的更新规则进行种群的更新。计算种群个体适应度的部分为遍历种群中的所有个体，并调用机器学习算法来计算种群中每一条个体的适应度。以GA为例，运行GA 5次，其中最大迭代次数为50，种群规模为20，数据量为2万条，计算并记录各部分耗时的平均值。各部分耗时情况如图1所示。

图1 GA各部分耗时Fig.1 Time consuming parts of GA

由图1可知，计算个体适应度的部分耗时最长，占总体算法运行时间的96.6%，种群初始化和种群更新部分分别占2.4%和1%。计算适应度部分耗时较长的原因是因为种群中的每一个个体都需要训练一次机器学习模型。若种群规模为20，最大迭代次数为50，则要进行1 000次机器学习算法模型的训练，加上种群个体适应度初始化部分，算法总共要进行1 020次机器学习算法模型的训练。

针对群启发式算法在机器学习参数寻优问题中计算个体适应度耗时较长的问题，采用Spark平台对种群进行并行化处理来提高计算种群个体适应度的效率。

2.2 参数并行

根据上述GA各部分操作耗时分析，可以通过并行化计算个体适应度来提高机器学习参数寻优的效率。在Spark平台上通过parallelize()方法将种群转换为RDD，将整个种群切分为子种群，然后分发给不同的Worker节点。由Worker节点中的Executor并行进行计算子种群个体适应度，最终Executor将计算结果返回给Driver。参数并行如图2所示。

图2中，Driver负责资源的申请、RDD的转换、任务的生成等；Master负责资源调度，与Worker进行RPC通信，让Worker启动Executor；Executor负责真正的逻辑计算。

在参数并行的并行化实现中，Driver首先向Master申请需要的资源，Master收到Driver的请求后与Worker进行RPC通信，让Worker启动Executor。Executor启动之后，Driver端将切分之后的RDD和一些计算逻辑等生成具体的任务通过网络发送给不同Worker中的Executor来实现并行化计算。当Executor将任务计算完后，向Driver端返回计算结果。Driver端汇总所有种群个体适应度，然后根据种群个体适应度来进行种群的更新，更新之后保留最优个体，得到种群一次迭代的最优参数组合。

通过将种群切分为子种群，并行化计算种群个体的适应度来提高机器学习参数寻优的效率。

2.3 基于参数并行的并行化算法设计

并行化算法的设计主要依赖Spark所特有的RDD来对种群或者数据进行读取、切分和并行化处理。针对计算适应度耗时较长的问题，现有的方法是基于数据并行的机器学习参数寻优方法，其将数据切分为多个子数据，并行计算种群内个体的适应度。基于参数并行机制的机器学习参数寻优方法，将种群切分为多个子种群，并行计算子种群内个体的适应度。基于数据并行和参数并行的并行化设计流程图如图3所示。

图3中，左侧是数据并行的流程图，右侧是参数并行流程图。在Spark平台进行并行化计算首先应进行Spark参数初始化，包括节点个数的设置，并行度的设置以及节点内存的设置等，用于Spark集群应用的提交。然后将所需要并行处理的部分转化为Spark所支持的RDD。RDD支持两种操作：转化操作和行动操作。RDD的转化操作返回一个新的RDD操作，它只是封装了逻辑，但并未真正开始计算。而行动操作是向驱动器程序返回结果或者把结果写入外部系统的操作，触发真正的计算。

图2 参数并行Fig.2 Parallel parameters

图3 基于数据并行和参数并行的并行化设计流程图Fig.3 Parallel design flow chart based on data parallelism and parameter parallelism

种群初始化完成后，将包含着参数、适应度、编码等信息的种群个体存放在一个列表中，形成一个包含所有个体信息的种群列表。将种群个体携带的参数信息作为训练机器学习算法模型的超参数，把模型的准确率作为种群个体的适应度。

由图3可知，数据并行操作是先随机初始化种群，然后再读取数据，只将数据转化为RDD，然后基于数据并行来计算种群内个体的适应度。参数并行是初始化种群的同时就读取数据，将数据和种群一起存放在列表中，然后将列表转化为RDD。当数据和种群转换为RDD时，并未触发真正的计算，只是定义了一个RDD。用行动操作collect()合并计算的所有个体适应度时，才真正开始计算。所有种群个体的适应度计算完成后，根据每个个体的适应度来进行种群的更新。不同的种群更新的规则也是不同的。进行完种群更新操作后，保留更新过后的个体最优值。如果满足式(3)所示的终止条件，则返回最优参数作为机器学习算法模型的超参数，否则，将继续执行并行化计算个体适应度、合并所有个体适应度、更新种群、保留最优个体的操作。

3 相关实验与结果分析

3.1 实验环境

采用随机森林作为机器学习算法的代表，选用GA作为群启发式算法的代表。二者均是各自应用场景中的主流算法。随机森林依靠Scikit-learn实现。Scikit-learn是针对Python编程语言的免费软件机器学习库，它有各种分类、回归和聚类算法，是GitHub上最受欢迎的机器学习库之一。实验数据为广州市公交车的IC卡交易数据。经过归一化后，将其处理为时间序列数据，利用随机森林进行回归预测。Scikit-learn中的随机森林需要调节的参数为：n_estimators、max_depth、max_features。分别为决策树的个数、决策树的深度、单个决策树使用特征的最大数量。由于使用的数据中，数据段总共只有6个，因此选取了所有特征。所以只对n_estimators、max_depth两个参数进行寻优。其中n_estimators参数的取值范围为[100，200]， max_depth参数的取值范围为[2，30]。

通过构建Spark集群来验证并行化计算算法的效率。Spark集群详细配置为：CentOS-6.10-x64，spark-2.1.1-bin-hadoop2.7，hadoop-2.7.2，py4j- 0.10.4，jdk1.8.0_261，scikit-learn-0.24.0，pyspark-2.3.2。根据经验设置Spark集群节点个数为8，节点运行参数配置如表1所示。

GA的参数设置如表2所示。

表1 节点运行参数配置Table 1 Node’s operating parameter configuration

表2 GA参数设置Table 2 GA parameter settings

3.2 实验结果分析

3.2.1 网格搜索算法与群启发式算法对比实验

实验的目的是通过和文献[6]提出的并行化网格搜索算法进行对比，来验证群启发式算法作为机器学习算法参数寻优的方法，不仅可以提高机器学习参数寻优的效率，而且还能保证机器学习算法模型的准确率。

(1)第一个实验。在上述实验环境以及参数范围内，通过给网格搜索算法设置不同的步长，来实现不同步长下的参数寻优。将每一次得到的最优参数组合作为机器学习算法训练模型的最终的参数。记录网格搜索算法不同步长下的机器学习模型的准确率。实验结果如表3所示。

(2)第二个实验。在第一个实验的基础上，选取机器学习算法模型准确率最高时所对应网格搜索算法的步长作为此次实验的步长。在相同的数据量和并行度下，将基于网格搜索算法的参数寻优实验和基于群启发式算法的参数寻优实验分别进行了5次，统计每一次参数寻优实验的耗时以及最优参数模型的准确率，计算5次实验的平均值。实验结果如表4和表5所示。

表3 不同步长下的网格搜索算法的参数寻优的模型准确率Table 3 Model accuracy rate of parameter optimization of grid search algorithm under asynchronous length

表4 不同算法参数寻优的模型准确率Table 4 Model accuracy of different algorithm parameter optimization

表5 不同算法参数寻优耗时Table 5 Time consuming to optimize the parameters of different algorithms

由表3可以看出，基于网格搜索算法的参数寻优的模型精度受网格搜索算法的步长影响。随着网格搜索算法步长的增加，模型的准确率出现了一定程度的下降。另外，从表3还可以看出，当参数n_estimators和参数max_depth的步长都为1时，得到的最优参数组合的模型的准确率是最高的。这是由于网格搜索算法遍历了参数取值范围内的所有参数组合，没有遗漏任何一组参数，但搜索效率很低。随着步长的增加，网格搜索算法会根据步长来进行参数的选择，这就极其容易跳过最优参数组合导致寻优精度不高。

由表4可以看出，基于群启发式算法的机器学习参数寻优，得到的最优参数组合的模型准确率的平均值为0.819 99；基于网格搜索算法且搜索步长为1的机器学习参数寻优得到的模型平均准确率为0.811 557。两者的模型准确率相差不多，在误差范围内。从表5可以看出，基于网格搜索算法的机器学习参数寻优的耗时约是群启发式算法的1.49倍。由此可以看出，在确保模型准确率不相上下的基础上，群启发式算法作为机器学习算法的参数寻优方法效率要高于网格搜索算法。

和网格搜索算法相比，群启发算法作为机器学习参数寻优的方法，不仅在效率上得到了提升，而且并不会使机器学习算法模型的准确率下降。因此，群启发式算法作为机器学习参数寻优的方法在寻优能力和效率上都要优于网格搜索算法。

3.2.2 参数并行与数据并行对比实验

实验的目的是验证参数并行机制相较于数据并行机制的效率优势。在上述实验环境下，采用Python语言实现了基于数据并行机制和参数并行机制的并行化RF，并记录算法在不同数据量下所用的运行时间。在实验中，最大迭代次数设为50，种群规模设为20和100。为验证数据量对并行效率的影响，在2万、4万、8万、16万、32万数据量下进行实验。种群规模为20和100的实验结果分别如图4和图5所示。

图4 种群规模为20时的两种并行机制的运行时间Fig.4 Running time of the two parallel mechanisms with a population size of 20

图5 种群规模为100时的两种并行机制的运行时间Fig.5 Running time of the two parallel mechanisms with a population size of 100

由图4、图5可以看出，当数据量为20万左右的时候，两种并行机制的运行时间出现了交点。当数据量小于20万时，参数并行优势较为明显，参数并行相较于数据并行来说，参数寻优效率提高了42.8%。当数据量大于20万时，参数并行的运行时间出现显著增长。此时，数据并行的优势显现出来，所用时间较短。这是因为在小数据量下，每个任务的计算量越大，效率越高，每个任务切分越细，效率越低。参数并行是将种群切分成若干份，训练数据不进行切分。在相同数据量下，对于参数并行而言，每一个个体都需要一份数据量计算个体适应度，种群规模为20时，这个种群就对应20份数据。本实验中参数并行根据分区度将种群切分为6份，则每一个任务就对应3.333份数据。对于数据并行来说，是根据分区度把训练数据切分为6份，种群不进行切分。则每一个任务所对应的训练数据为0.167份。所以在小数据量下，数据并行每一个任务的数据量要小于参数并行。由于每个任务的计算量越大，效率越高。即在数据量小于20万时的小数据量下，参数并行的效率要高于数据并行。随着数据量的增大，每一个任务对应的计算量越来越大，则运行时间相应的会越来越长。由于参数并行每一个任务对应的数据量是数据并行每一个任务对应的数据的20倍左右，在大于20万时的大数据量下，数据并行要比参数并行有优势。

由图5可知，在数据量为2万的时候，参数并行和数据并行运行时间相差不大。其原因在于Spark集群模式下，各个节点之间需要进行资源分配、任务划分、任务调度以及节点之间的通信，这些操作也要消耗时间。当数据量较小时，Spark之间的资源调度等操作会占一大部分时间，所以此时参数并行和数据并行之间的差距并不明显。

另外，根据图4、图5还可以看出，数据量为8万时，是数据并行的一个拐点。在数据量大于8万时，运行时间出现了下降趋势。此时对于数据并行来说，其优势开始显现出来。数据量较小时，每一个任务对应的计算量小，每个任务切分的细，因此效率较低。

通过上述结果分析可得，在小数据量下，基于参数并行的机器学习并行化训练方法效率更高。但这并不意味着小数据量下并行训练是无意义的。由图5可知，在数据量为8万时，使用参数并行可节省将近2 h的可观的训练时间。

3.2.3 可扩展性实验

可扩展性实验是指是否能够通过增加结点的数量来提高算法运行速度。实验基于单节点、2个节点、4个节点以及8个节点，在数据量为1万，迭代次数为20的基础上将参数并行算法运行5次，计算算法运行时间并记录平均值。参数并行运行结果如图6所示。

由图6可以看出，算法运行时间随着种群规模的增加而增长。当种群规模为50时，4个节点和8个节点的算法运行时间差别较小。这是因为多个节点运行程序时，节点之间需要进行资源分配、任务

图6 参数并行算法可扩展性实验Fig.6 Parametric parallel algorithm scalability experiment

划分、任务调度以及节点之间的通信等操作。这些操作也要消耗时间。随着种群规模的增大，8个节点时算法运行效率逐渐高于其他节点。这是因为节点数越多，算法并行度就越高，即每个节点计算量就越小。

通过上述实验结果分析，参数并行算法具有良好的可扩展性。

3.2.4 节点个数与分区度实验

节点个数与分区度实验是指在确定的分区度下，不同的节点个数对参数并行算法运行效率的影响。在节点个数为2、4、6、8个，分区度为6，迭代次数为20的基础上分别将参数并行算法运行5次，计算并记录算法运行时间的平均值。参数并行算法运行结果如图7所示。

由图7可以看出，在节点个数为6和8时的算法运行时间低于节点个数为2和4时参数并行算法运行时间。这是因为本实验节点的个数决定算法每一轮并行执行的任务数的多少。实验分区度为6，即有6个任务需要计算。节点个数为2或4时，

图7 分区度为6时不同节点个数运行时间Fig.7 Running time of different nodes when the partition degree is 6

算法每一轮并行执行的任务数为2个或4个，则需要两轮才能将所有任务计算完毕。当节点个数为6时，刚好一轮就能计算完所有的任务。当节点个数为8时，算法运行时间要稍稍高于节点个数为6时。这是由于只有6个任务，并行度为8，会有两个节点不计算任务，但这2个节点之间还是会被分配资源，进行节点间的通信。在一定程度上，算法运行时间会加长。

由以上分析可知，尽管可以通过增加结点的数量来提高算法运行效率，但是节点个数并不是越多越好，应当根据分区度的大小来设置节点个数。

4 结论

在对机器学习的参数寻优问题进行深度分析研究的基础上，针对群启发式算法提出了一种基于参数并行机制的机器学习参数寻优方法。设计了数据并行与参数并行对比实验、可扩展性实验、节点个数与分区度实验来验证参数并行机制的优势，得到以下结论。

(1)提出的方法在机器学习参数寻优精度和效率上都要优于主流的并行化网格搜索算法。

(2)参数并行机制在小数据量下能显著提高参数寻优的效率，进而可以提高机器学习的训练效率，并具有良好的可扩展性。

只是把GA算法作为群启发式算法的代表来进行机器学习算法超参数寻优。但基于群启发式算法进行机器学习算法超参数的寻优问题仍有很多可以研究的方面。在接下来工作中，将会着力研究更适合机器学习算法超参数寻优的群启发式算法。例如，可以将参数并行机制应用于基于混合式群启发式算法的机器学习算法超参数的寻优；对群启发式算法进行优化，使之能在不影响机器学习算法模型性能的前提下减少计算个体适应度的次数等。