面向机器学习任务的调度方法研究

孙景玉 石振国

摘 要：为了提高机器学习任务执行效率并实现资源与任务的最佳匹配，在传统调度问题理论基础上对调度概念进行拓展，提出一种新的问题解决方案。该解决方案包括基于任务数据相似性原理，对任务集进行特征属性提取，构建以调度算法资源准确率较高为评价目标的数学模型。在考虑资源和任务匹配程度的前提下设计一种基于改进的简化粒子群优化的模糊C均值聚类算法，根据任务聚类结果设计新的基于机器学习任务聚类的任务调度算法。实验结果表明，构建的数学模型在大多数情况下性能良好，优化的聚类算法调用算法准确率比传统方法约高0.3～0.8个百分点，能够有效提高任务调度有效性。

关键词：机器学习;任务调度算法;特征属性;C均值聚类算法

DOI：10. 11907/rjdk. 192349 开放科学（资源服务）标识码（OSID）：

中图分类号：TP301文献标识码：A 文章编号：1672-7800（2020）005-0009-05

0 引言

近年来，随着计算机计算能力的不断提升，机器学习作为人工智能的核心技术之一，在越来越多的领域取得了令人瞩目的成果。作为一门涉及概率论、统计学、凸分析等多领域的交叉学科[1-2]，其具有非常广泛的应用范围。与此同时，飞速发展的互联网也迎来了如何对大量闲置资源加以合理利用的巨大挑战。在相对较低调度成本以及相对较高资源利用率的前提下实现任务的合理高效管理，并对任务进行准确、有效、高质量的调度执行已成为越来越多领域不断追求的目标。

通常而言，调度问题指在一定约束条件和优化目标函数约束下，将相关任务排列后利用有限资源完成一系列任务的过程。它广泛存在于现实生活的各行各业，例如人力调度、卫星调度[3]、负载均衡调度[4]等。在生产中就是组织执行生产进度计划的工作，在车辆运输中就是在一定约束条件下制定行车路线使车辆有序到达指定地点[5]。

本文在现有理论基础上对任务调度策略进行研究，对调度概念加以创新拓展，打破以往仅凭借经验处理机器学习任务并匹配适用资源的局限，将机器学习任务与调度相结合构造一种针对机器学习任务与适用资源之间的调度方法模型。机器学习任务形式多样，但是追根究底都是对数据的处理与学习。不同的样本数据即为不同的机器学习任务，如何为提交任务调度适用资源即为本文研究目标所在。本文首先介绍基于任务的数据相似性原理，提取能够反映数据集内部结构特点的特征属性，构建以调度算法资源准确率较高为评价目标的数学模型;然后在考虑资源和任务匹配程度的前提下设计一种基于改进简化粒子群优化的模糊C均值聚类算法，根据任务聚类结果设计新的基于机器学习任务聚类的任务调度算法;最后通过实验分析验证该解决方案的可行性。

1 调度算法资源数学模型构建

调度算法资源数学模型构建是机器学习任务在执行过程中的重要步骤。Schaffer[6]提出每个机器学习任务依次调用可供选择的算法，然后选取准确率较高的算法;Brodley[7]提出以专家知识为基础的算法选择方案。本文对样本数据进行分析，提取能够反映样本数据内部结构的特征属性[8]，从而得到一种衡量新任务与样本库中数据集之间关系的度量数学模型。该模型主要由二进制化向量、属性统计特征向量以及平均互信息量[9]3部分组成。通过与样本库中的数据集进行对比，考量该任务与样本库中样本集之间的关系，帮助机器学习任务调用适用算法，在一定程度上优化了任务与资源匹配合理性，能够有效提高调度算法资源效率。

1.1 属性向量二值化

二值化算法只能针对离散数据进行处理，因此需对连续数据加以转换。为了尽可能地保持数据的内在结构，本文采用基于集成学习的无监督离散化算法[10]和Song等[11]提出的离散化方法相结合的方式提取特征向量。该方法利用集成方式将CAIM算法离散化后的结果集成并得到最小子区间，采用保持近邻特征的方式合并子区间，直到合并过程波动最大时离散化停止。算法离散化的样本数据在不同维度上的區间可视为不同属性，将原始样本数据D转换到属性空间，并将属性值转换为0和1，构成样本数据的二值化空间DB。在二进制化过程中，为保证没有语义信息丢失，需对属性个数予以扩充，并根据式（1）进行转换。

其中，[ValueAi]是样本数据中第i维的属性，[CAi]为该维度上不同的属性值。将每个实例属性或者类标签按照式（1）进行转换，然后统计每个属性值出现的频率可得一项集，对两个不同属性取异或操作得到二项集合向量。二项集求取如式（2）所示。

1.3 平均互信息量

在概率论和信息论中，两个随机变量的互信息（Mutual Information，MI）是变量间相互依赖性的量度。Jakulin等[14-16]的研究表明可通过属性间的交互分析数据集;Pritam等[17-18]也指出统计交互信息有助于深入分析数据集的潜在结构以及属性之间的关系。不同于相关系数，互信息并不局限于实值随机变量，它决定着联合分布p（X，Y）和分解边缘分布乘积 p（X）p（Y） 的相似程度。两个离散随机变量X和Y的互信息定义如式（7）所示。

其中，[d{Vi，Vj}]、[d{Ai，Aj}]、[d{Ii，Ij}]分别为任务样本数据集的二进制化属性、统计特征属性和平均互信息量属性向量距离，Pa1、Pa2和Pa3分别为各属性向量距离参数。通过此数学模型，对比任务集与历史样本库中数据集之间的相似性程度以及映射关系，找到最佳适用资源。

2 任务聚类

除通过分析任务集内部特征构建调度算法资源数学模型外，还需考虑任务需求及资源类型多样，例如CPU、内存等。任务类型有计算型任务、存储型任务及网络型任务等。因此，提出对任务端进行聚类分析，设计一种基于改进简化粒子群优化的模糊C均值聚类算法对任务进行聚类处理，提高任务调度匹配程度。

2.1 简化粒子群优化算法

PSO算法是1995年由Kennedy & Eberhart首次提出的一种模拟鸟的群体智能优化算法。它首先初始化一群随机粒子，然后通过不断迭代找到问题最优解，具有收斂速度快、容易实现、调整参数少等优点。

迭代过程中，粒子速度及位置更新如式（10）所示。

其中，[χid]是粒子当前位置，[Pid]是搜索历史中最优点位置，[pgd]是整个种群中当前最优解位置，[c]为学习因子，[ω]表示粒子移动快慢程度。虽然目前大多数PSO改进算法都是基于“位置”与“速度”概念，但是粒子移动速度大小并不能有效地趋近最优解位置，反而可能造成粒子进化方向偏离，从而导致后期收敛缓慢、收敛精度低。文献[19]与文献[20]证明基本粒子群优化算法在进化过程中与粒子速度无关，简化粒子群算法结构使得搜索过程仅由位置向量控制，避免了人为确定参数而影响粒子收敛速度和收敛精度。简化后的粒子群算法更新如式（11）所示。

其中，[Pad]为所有个体最优位置的均值。

2.2 基于改进的简化粒子群优化模糊C均值聚类算法

FCM算法是基于目标函数的聚类过程，能够更加真实地反映客观世界，但也存在对初始值敏感和容易陷入局部最优的缺陷。针对FCM算法缺点，本文提出基于拉普拉斯加权系数[21]和PSO算法的优化搜索能力对此进行改进，通过计算样本元素与聚类中心的距离获得权系数，有效提高聚类性能。目标函数改为如式（12）所示。

为了达到自适应效果，从模糊矩阵u中分离出样本矩阵[C=[cij，0]]，[cij]表示模糊矩阵每列的最小值，矩阵C的映射函数[A=（Ai，icci-Ai）] 。求取两个簇中心的欧式距离[dij=Ai-Aj]，[lij=i-1nMjk-Aji=1nMik-Ai]，若[dij]、[lij]小于事先给定参数值，则进行合并，随机生成新的聚类中心，重新进行迭代计算。

在利用PSO算法进行优化求解时，算法中个体确定、编码以及适应度函数是解决问题的关键。选取每个粒子由K个聚类中心组成，维数为[w]。对聚类中心[Mi（i=1，2，？k）]进行编码，编码长度可表示为[K×w]。个体适应度函数定义为[f=1（1+Jm）]，其中[Jm]为样本点到聚类中心的距离和，[Jm]值越小，个体适应度越高，适应度值大小代表了选取此聚类中心后聚类效果好坏。当算法满足最优解对应的目标值保持不变或者小于设定的阈值[ε]时，算法终止。

综上所述，改进的简化粒子群优化模糊C均值聚类算法（ISPO）求解过程如下：

Step1：初始化聚类中心V，并对算法相关参数，如聚类数目c、模糊因子m的值，迭代误差[ε]等参数赋值。

Step2：按照编码原则生成初始种群。

Step3：根据适应度函数计算种群个体适应值，计算权重系数S，更新隶属度矩阵并修正新的聚类中心。

Step4：计算目标函数[JLFCM（U，S，V）]。

Step5：判断是否满足终止条件，否则迭代执行过程。

3 基于任务聚类的任务调度算法设计

任务调度算法设计如下：对每一个历史样本数据集进行属性计算，获得对应调度算法资源的度量值，将两者对应关系保存到数据库中;然后依次应用算法库中的算法，对算法性能进行评估，将评估结果最好的算法列为适用算法并保存到数据库中，当有新的任务需要执行时，根据精确度、执行时间、CPU占用以及内存使用情况等需求特性，对数据库中调度算法资源度量值进行排序后调用适用算法;再利用改进的简化粒子群优化的模糊C均值聚类算法对任务进行聚类处理。任务调度算法步骤如图1所示。

4 实验及结果分析

4.1 实验准备

本文实验数据采用UCI标准评测数据集，并采用交叉验证方法进行实验。算法库采用最常见的3种任务类型：分类模型算法包括决策树模型、概率统计模型、懒惰模型等;回归模型算法包括线性回归、回归树、随机森林等;聚类模型算法包括基于划分聚类、基于层次聚类和基于密度聚类等。

4.2 实验过程与结果分析

4.2.1 样本数据集特征向量

表2表示选取的部分样本数据集概要信息。

4.2.2 调度算法资源数学模型评价

针对同一任务可能适用多种不同算法资源的情况，实验基于K最近邻算法思想，从数据库中选出k个与输入任务数据集最相似的数据集，再根据数据库中数据集与算法之间的映射关系选出适用算法。k值的不同可能导致最终结果不同，因此设置邻居个数k为1～9，计算所有测试数据集调用适用算法后的准确率均值并记录实验结果。由图2发现，准确率随着邻居个数k的不断增大先迅速上升后趋于平缓。由此可知，当邻居个数超过某一界限时，调度算法的准确率变化趋于稳定。因此，为了节约成本，邻居个数k值选择图2中趋于平缓的界值即可。

测试任务集调用算法准确率如图3所示，包括最佳、最差以及平均推荐准确率。可以看出，测试任务集平均最佳调度准确率约为82.15%，除个别任务数据集调度准确结果不理想外，大部分测试数据集调用准确率均能达到80%及以上。而且，与传统“Win-Draw-Loss”策略（WDL）相比，该算法平均精度约高出0.3%～0.8%。

4.2.3 改进的简化粒子群模糊C均值聚类评价

为了测试算法性能，本文利用UCI数据库中经典Iris和Wine数据集，将改进的简化粒子群模糊C均值聚类算法IPFCM与传统FCM算法以及传统PSO算法优化的模糊聚类算法PFCM进行比较。在实验中设置粒子群规模为50，聚类数目为3，模糊因子为2，对每种算法做30次实验并取平均值，结果如表5所示。

从整体角度分析，传统FCM算法方差较大，容易受初值选取影响，而且目标函数值下降迅速，容易陷入局部最小值，聚类效果较差。PFCM算法采用了优化处理，聚类效果较好，但是可能出现早熟收敛情况。本文改进的IPFCM算法提高了优化搜索能力，避免了人为确定参数而影响粒子收敛速度和收敛精度，从而在准确率方面优于传统FCM算法和PFCM算法。由图4和表5实验结果可以发现，不同搜索过程适应度函数不同，目标函数也会不同。并且，IPFCM算法在精确到一定程度时，搜索速度相对较快，聚类效果更好。

5 结语

本文通过构建调度算法资源数学模型并设计一种基于改进的简化粒子群优化的模糊C均值聚类算法对任务内部结构特征及任务性能特点进行分析，让具有不同偏好的任务与具有相应性能特点的资源进行匹配，從而在一定程度上提高任务执行效率。通过调用算法资源数学模型，为提交的任务数据集选择算法库中的适用算法。实验结果表明，大多数情况下该调度算法是有效可行的，改进的聚类算法也能够在一定程度上弥补FCM算法缺陷，从而有效提高任务调度有效性。

参考文献：

[1] 陈凯，朱钰. 机器学习及其相关算法综述[J]. 统计与信息论坛， 2007， 22（5）：105-112.

[2] TOM M.MITCHELL. 机器学习（计算机科学丛书）[M]. 北京：机械工业出版社，2014.

[3] 陈宇. 基于典型任务的多星协同调度关键问题研究[D]. 武汉：武汉大学，2012.

[4] 马亮，李晓. 基于改进粒子群算法的云计算任务调度策略[J]. 计算机与现代化，2013， 11（9）：78-81.

[5] 李静梅，王雪，吴艳霞. 一种改进的优先级列表任务调度算法[J]. 计算机科学，2014， 41（5）：20-23.

[6] SCHAFFER C. Selecting a classification method by cross validation[J].  Machine Learning， 1993，13（1）：135-143.

[7] BRODLEY C E. Recursive automatic bias selection for classifier construction[J]. Machine Learning，1995，20（1/2）：63-94.

[8] 曾子林，张宏军，张睿，等. 基于元学习思想的算法选择问题综述[J]. 控制与决策，2014（6）：961-968.

[9] 刘娟，朱翔鸥，刘文斌. 基于交互信息的数据集特征结构研究[J]. 模式识别与人工智能，2014， 27（1）：82-88.

[10] 徐盈盈，钟才明. 基于集成学习的无监督离散化算法[J]. 计算机应用，2014， 34（8）：2184-2187.

[11] SONG Q，WANG G，WANG C. Automatic recommendation of classification algorithms based on data set characteristics[J].  Pattern Recognition， 2012，45（7）：2672-2689.

[12] 代明，钟才明，庞永明，等. 基于数据集属性相似性的聚类算法推荐[J]. 南京大学学报（自然科学版），2016，52（5）：908-917.

[13] GOMES D，CASTRO L N D. Clustering algorithm selection by meta-learning systems： a new distance-based problem characterization and ranking combination methods[M]. Elsevier Science Inc. ，2015.

[14] YIN Z，LI J，ZHANG Y，et al. Functional brain network analysis of schizophrenic patients with positive and negative syndrome based on mutual information of EEG time series[J].  Biomedical Signal Processing and Control，2017（31）：331-338.

[15] JAKULIN A，BRATKO I. Testing the significance of attribute interactions[C]. New York：Proceedings of The 21th International Conference on Machine Learning，2004：52-59.

[16] JAKULIN A，BRATKO I. Analyzing attribute dependencies[C]. The 7th European Conference on Principles and Practice of Knowledge Discovery in Databases（PKDD），2003：229-240.

[17] CHANDA P，CHO Y R，ZHANG A，et al. Mining of attribute interactions using information theoretic metrics[C]. Miami：IEEE International Conference on Data Mining Workshops，2009：350-355.

[18] 贾平，代建华，潘云鹤，等. 一种基于互信息增益率的新属性约简算法[J]. 浙江大学学报（工学版），2006，40（6）：1041-1044.

[19] 胡旺，李志蜀. 一种更简化而高效的粒子群优化算法[J]. 软件学报，2007，18（4）：861-868.

[20] 熊众望，罗可. 基于改进的简化粒子群聚类算法[J]. 计算机应用研究，2014，31（12）：3550-3552.

[21] 黄鹏飞. 拉普拉斯加权聚类算法的研究[D]. 南京：南京航空航天大学，2009.

（责任编辑：孙 娟）