一种基于MPI的分布式ADMM垃圾邮件分类方法

一种基于mpi的分布式admm垃圾邮件分类方法
技术领域
1.本发明涉及分布式机器学习领域，具体涉及一种基于mpi的分布式admm垃圾邮件分类方法。


背景技术：

2.分类问题是人类所面临的一个非常重要且具有普遍意义的问题。它是基于已知训练集识别一个新的实例属于哪个类别的有监督的学习问题。将事物正确的分类，有助于人们认识世界，使杂乱无章的现实世界变得有条理。例如自动文本分类就是对大量的自然语言文本按照一定的主题类别进行自动分类，它是自然语言处理的一个十分重要的问题；文本分类主要应用于信息检索，机器翻译，自动文摘，信息过滤，邮件分类等任务。
3.交替方向乘子法(alternating direction method of multipliers,admm)最早由stephen boyd等人于2010年提出，作为一种求解优化问题的计算框架，适用于求解分布式凸优化问题。admm算法为机器学习中的约束最优化问题的高效分布式求解提供了可能。原始的admm算法在统计机器学习、数据挖掘和计算机视觉等领域中得到了广泛应用。作为能够有效地协调若干个节点之间子全局模型变量优化的强有力工具，admm在分布式优化和统计学习中扮演着举足轻重的角色，受到了研究学者的极大关注。admm发展至今，己经被广泛地应用到机器学习、数据挖掘和信号处理等领域。
4.mpi(massage passing interface，信息传递接口)是一个跨语言的通信协议，基于消息传递的编程模型，单机模式下用于不同进程间的通信，集群模式下用于不同机器的通信。在linux、windows、mac os上都可以安装运行，有mpich、openmpi等若干个版本可以使用，可以使用c++、python等多种编程语言开发，由python实现的mpi4py库可以很好地结合numpy库，保证程序运行速度的同时实现高效开发。mpi可以实现点对点通信，一对多的广播通信，以及多对一的规约等多种通信方法。mpi既可以完成阻塞通信，也可以完成非阻塞通信。目前在学术界分布式计算领域得到广泛应用。


技术实现要素：

5.本发明的目的在于提出一种基于mpi的分布式admm垃圾邮件分类方法，用于解决大数据环境下的垃圾邮件分类问题，并针对这一问题提出合适的基于admm的分布式框架，以提高性能和减少时间。
6.本发明将所要研究的问题分为若干个可并行计算的子问题，每个子问题用改进的随机梯度下降算法来解决，使用分布式admm框架交替优化逐步达到全局最优共识。
7.实现本发明的技术解决方案：一种基于mpi的分布式admm垃圾邮件分类方法，包括如下步骤：
8.步骤1、将文本数据向量化为数字格式的数据集；
9.步骤2、将数据集分割为训练集和测试集，对训练集进行过采样处理，再分割为若干份分别保存在若干个从节点上；
10.步骤3、mpi并行执行所有节点上的代码，从节点并行更新局部模型；
11.步骤4、主节点通过mpi规约功能汇总从节点的局部模型；
12.步骤5、主节点更新全局模型，并利用mpi广播功能将全局模型分发到各个从节点；
13.步骤6、循环交替更新从节点和主节点的模型，直到满足终止条件；
14.步骤7、保存主节点的全局模型作为分类器模型；
15.步骤8、利用训练得到的分类器模型对测试集进行分类，输出分类结果。
16.进一步地，本发明步骤1中利用nlp(natural language processing)技术，如word2vec算法，将文本数据向量化为数字格式的数据集。处理后的数据集可以表示为n为样本数量，x为d维的样本数据向量，y为样本标签。本发明使用l2正则化的l2损失支持向量机(svm)作为主要的线性分类模型。该方法的目标函数可表示为:
[0017][0018]
其中c》0是一个超参数，用来控制正则项和损失项比重关系，防止过拟合，w是模型的参数向量，且w∈rd；l2正则化表示上述目标函数中正则项‖w‖2带有平方，l2损失表示损失项max(1-yiw
t
xi,0)2带有平方。
[0019]
由于垃圾邮件在数据集中属于少数类，使用smote算法对训练集过采样处理来解决不平衡数据分类问题，使得训练集中正样本和负样本数量相当，接着再分割为若干份分别保存在若干个从节点上。smote算法的基本思想是对少数类样本进行分析并根据少数类样本人工合成新样本添加到数据集中。
[0020]
进一步地，将数据集按照4：1的比例分割为训练集和测试集，并分割为若干份分别保存在若干台从节点上。假设数据被存在了m个节点(d1,d2,
…
,dm)上，(9)式改写为：
[0021][0022]
s.t.w
j-z＝0,j＝1,
…
,m
[0023]
其中ρ是一个超参数，wj是第j个节点的局部模型参数，z是在主节点上更新的全局变量，且z∈rd。
[0024]
将原函数(10)改写成增广拉格朗日形式，即原问题的对偶问题：
[0025][0026]
其中θj是第j个节点的对偶变量。
[0027]
进一步地，mpi并行执行所有节点上的代码，通过mpiexec命令完成。首先主节点上随机初始化全局模型变量z，各从节点上随机初始化局部模型变量wj及其对偶变量θj，方便起见，一般初始化为全零。接着从节点并行更新局部模型变量。由admm算法更新规则可知，
w,z,θ按如下公式迭代更新：
[0028][0029][0030][0031]
其中k是迭代次数。因为拉格朗日函数l(w,z,θ)对于wj是可分解的，所以本发明在各个从节点上并行地解决问题(12)来更新局部模型变量wj：
[0032][0033]
进一步地，主节点通过mpi规约功能汇总从节点的局部模型，首先本发明通过如下代码创建mpi的通信子comm：
[0034]
comm＝mpi.comm_world
[0035]
接着利用通信子实现规约功能，表示如下：
[0036]
comm.reduce(sendbuf,recvbuf,op,root)
[0037]
其中sendbuf表示从节点发送的内容，这里具体传入局部模型变量及其对偶变量recvbuf表示主节点用于接收的变量，op表示具体规约的操作函数，这里本发明使用mpi.sum函数，表示将从节点的值相加后传给主节点，root表示根节点序号，这里本发明传入主节点序号0。
[0038]
进一步地，主节点收集整合各从节点的局部模型变量及其对偶变量，更新全局变量，并将更新后的值发送给各从节点。(13)可以写为闭式解来更新全局变量z：
[0039][0040]
接着利用通信子实现广播功能，表示如下：
[0041]
comm.bcast(buf,root)
[0042]
其中buf表示被广播的数据，这里本发明传入主节点的全局模型变量z
k+1
，root表示根节点序号，这里本发明传入主节点序号0。
[0043]
进一步地，本发明令θj＝ρuj，可以得到wj,z,uj的更新公式：
[0044][0045][0046]
[0047]
其中uj代替θj成为本发明的对偶变量，并在各个从节点上迭代更新。
[0048]
进一步地，本发明使用方差缩减的梯度下降算法在从节点上具体解决(9)中的优化问题。单独拿出svm损失函数部分，并定义：
[0049]fi
(w)＝max(1-yiw
t
xi,0)2(12)
[0050]
在第k次迭代中，先计算样本的平均梯度
[0051][0052]
其中nj是第j个从节点的训练集样本数量。接着令开始内迭代t-1次，其中第t次迭代对变量的一步更新公式为：
[0053][0054]
其中η是学习率。完成t-1次内迭代后取均值作为第k+1次迭代的更新值：
[0055][0056]
进一步地，本发明用(15)在从节点更新局部模型变量wj，接着主节点收集各个从节点的局部模型变量wj和对偶变量uj，主节点用(10)更新全局变量z，接着主节点将更新后的全局模型变量z分发到各个从节点，接着从节点用(11)更新对偶变量uj，不断循环执行以上步骤直到满足终止条件，即两次迭代更新变量的残差足够小，则表明算法收敛，停止迭代，方便起见，本发明设置最大迭代次数k。
[0057]
经过步骤1至步骤6本发明模型训练阶段结束，在步骤7保存主节点的全局模型变量z作为分类器模型。
[0058]
进一步地，步骤8为测试阶段，利用训练得到的分类器模型对测试集进行分类，设(xi,yi)是测试集的第i个样本数据，xi∈rd,yi∈{-1,+1}，则预测值为：
[0059][0060]
其中z是算法最后一次迭代输出的全局变量，z
t
的上标t是转置的意思，sign()是符号函数，即：
[0061][0062]
由于更关注不平衡问题中的少数类，即垃圾邮件是否被分类正确，所以预测值时判定该样本为正样本，即为垃圾邮件，否则判定为负样本，即为正常邮件。
[0063]
本发明与现有技术相比，其显著优点在于：大多数随机admm方法在一般凸问题上只能达到比o(1/t)慢的收敛速度，这里t是迭代次数，o是形容算法快慢的一种记法。本发明可以在一般凸问题上获得与批量admm相同的收敛速度o(1/t)，可以用于大规模优化和学习问题，快速解决垃圾邮件分类问题。
附图说明
[0064]
图1为本发明实施例提供的一种基于mpi的分布式admm垃圾邮件分类方法流程图。
[0065]
图2为本发明实施例提供的实验准确率、召回率、f1评分随模型训练时间变化的曲线图。
具体实施方式
[0066]
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述。
[0067]
本发明公开了一种基于mpi的分布式admm垃圾邮件分类方法，本发明探索了分布式admm框架，并将分布式分类问题划分为一些小问题，采用一主多从的分布式架构，这些小问题可以通过分散资源并行解决。本发明包含以下步骤：将文本数据向量化为数字格式的数据集；将数据集分割为训练集和测试集，对训练集进行过采样处理，再分割为若干份分别保存在若干个从节点上；mpi并行执行所有节点上的代码，从节点并行更新局部模型；主节点通过mpi规约功能汇总从节点的局部模型；主节点更新全局模型，并利用mpi广播功能将全局模型分发到各个从节点；循环交替更新从节点和主节点的模型，直到满足终止条件；保存主节点的全局模型作为分类器模型；利用训练得到的分类器模型对测试集进行分类，输出分类结果。本发明在mpi分布式框架下使用admm并行方法求解优化问题，使得模型训练更加快速，适合大数据场景下垃圾邮件分类任务，有效提升了分类的效率和精度。
[0068]
如图1所示，本发明提供了一种基于mpi的分布式admm垃圾邮件分类方法，包括如下步骤：
[0069]
步骤1、将文本数据向量化为数字格式的数据集；
[0070]
步骤2、将数据集分割为训练集和测试集，对训练集进行过采样处理，再分割为若干份分别保存在若干个从节点上；
[0071]
步骤3、mpi并行执行所有节点上的代码，从节点并行更新局部模型；
[0072]
步骤4、主节点通过mpi规约功能汇总从节点的局部模型；
[0073]
步骤5、主节点更新全局模型，并利用mpi广播功能将全局模型分发到各个从节点；
[0074]
步骤6、循环交替更新从节点和主节点的模型，直到满足终止条件；
[0075]
步骤7、保存主节点的全局模型作为分类器模型；
[0076]
步骤8、利用训练得到的分类器模型对测试集进行分类，输出分类结果。
[0077]
为了验证本发明，本发明进行了如下实验：
[0078]
本发明采用了来自libsvm网站的公开数据集webspam的unigram版本，可以从https://www.csie.ntu.edu.tw/～cjlin/libsvmtools/datasets/binary.html获取该数据集。该数据集已经被预处理过，即如步骤1中将文本数据向量化为数字格式的数据集，处理后包含350000个样本，其中正样本137811个，负样本212189个，每个样本包含254个特征，以及每个样本对应取值为+1或-1的标签值。数据集预处理阶段使用第三方库imblearn的smote库函数来对训练集进行过采样处理，使得正、负样本数量相当。
[0079]
实验参数设置为k＝100,t＝nj,c＝10-5
,ρ＝1,η＝4,m＝24，本发明使用了24台linux服务器，均安装mpich以及mpi4py库，使用python编程语言开发。
[0080]
接着如步骤2将数据集按照4：1的比例分割为训练集和测试集，并分割为若干份分
别保存在若干台从节点上，将上述算法伪代码编写为python代码，并将该文件命名为admm-mpi.py，将其复制若干份保存在24台服务器的同目录下，在命令行通过执行如下命令来并行执行：
[0081]
mpiexec-n 24python admm-mpi.py
[0082]
主节点上初始化全局模型变量z0，各从节点上初始化局部模型变量及其对偶变量按照算法的伪代码流程迭代更新各个变量，完成步骤3至步骤6，最终本发明获得输出zk作为分类器模型参数，在测试集上按照公式：
[0083][0084]
对每个测试样本进行预测分类，预测值时判定该样本为正样本，即为垃圾邮件，否则判定为负样本，即为正常邮件，完成步骤7、步骤8。
[0085]
对于不平衡数据分类问题，本发明采用准确率、召回率(recall)、f1评分来衡量实验效果。下面给出以上评价指标的定义：tp(true positive)表示正类预测为正类的数量，fn(false negative)表示正类预测为负类的数量，fp(false positive)表示负类预测为正类的数量，tn(true negative)表示负类预测为负类的数量，则准确率定义为(tp+tn)/(tp+tn+fn+fp)，表示了所有预测正确的总数占预测的总数的比例，召回率定义为tp/(tp+fn)，表示样本中的正例被预测正确的比例，查准率(precision)定义为tp/(tp+fp)，表示预测为正的样本中有多少是真正的正样本，f1评分定义为2
×
precision
×
recall/(precision+recall)，表示查准率和召回率的调和平均数。
[0086]
在算法执行的过程中不断统计分类模型在测试集上的准确率、召回率、f1评分，如图2，本发明获得了实验准确率、召回率、f1评分随模型训练时间变化的曲线图。可以发现，本发明提出的发明拥有较快的收敛速度，即可以很快达到稳定，并获得了92.92％的准确率，91.57％的召回率以及90.44％的f1评分，完成了垃圾邮件的分类任务。
[0087]
具体算法流程的伪代码总结如下：
[0088]
[0089][0090]
本发明提供了一种基于mpi的分布式admm垃圾邮件分类方法，具体实现该技术方案的方法和途径很多，以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。本实施例中未明确的各组成部分均可用现有技术加以实现。

技术特征：
1.一种基于mpi的分布式admm垃圾邮件分类方法，其特征在于，包括如下步骤：步骤1、将文本数据向量化为数字格式的数据集；步骤2、将数据集分割为训练集和测试集，对训练集进行过采样处理，再分割为若干份分别保存在若干个从节点上；步骤3、mpi并行执行所有节点上的代码，从节点并行更新局部模型；步骤4、主节点通过mpi规约功能汇总从节点的局部模型；步骤5、主节点更新全局模型，并利用mpi广播功能将全局模型分发到各个从节点；步骤6、循环交替更新从节点和主节点的模型，直到满足终止条件；步骤7、保存主节点的全局模型作为分类器模型；步骤8、利用训练得到的分类器模型对测试集进行分类，输出分类结果。2.根据权利要求1所述的一种基于mpi的分布式admm垃圾邮件分类方法，其特征在于，步骤1利用nlp技术，将文本数据向量化为数字格式的数据集；处理后的数据集表示为其中n为样本数量，x
i
为第i个d维的样本数据向量，y
i
为第i个样本标签，r
d
表示d维的实数集，i取值1～n；使用l2正则化的l2损失支持向量机svm作为线性分类模型，目标函数表示为:其中c>0是一个超参数，用来控制正则项和损失项比重关系，w是分类模型变量，且w∈r
d
；使用smote算法对训练集过采样处理使得训练集中正样本和负样本数量相当，接着再分割为若干份分别保存在若干个从节点上。3.根据权利要求2所述的一种基于mpi的分布式admm垃圾邮件分类方法，其特征在于，步骤2将数据集按照4：1的比例分割为训练集和测试集，并分割为若干份分别保存在若干台从节点上，同时复制代码文件到若干个从节点，假设数据被存在了m个节点(d1,d2,
…
,d
m
)上，式(1)改写为：s.t.w
j-z＝0,j＝1,
…
,m其中ρ是一个超参数，w
j
是第j个从节点的局部模型变量，z是在主节点上更新的全局模型变量，且z∈r
d
；将式(2)改写成增广拉格朗日形式得到式(3)，即：
其中θ
j
是第j个从节点的模型对偶变量。4.根据权利要求3所述的一种基于mpi的分布式admm垃圾邮件分类方法，其特征在于，步骤3中mpi并行执行所有节点上的代码，通过mpiexec命令完成；主节点上随机初始化全局模型变量z，各从节点上随机初始化局部模型变量w
j
及其对偶变量θ
j
，初始化为全零；从节点并行更新局部模型变量，由admm算法更新规则得到，w,z,θ按如下公式迭代更新：如下公式迭代更新：如下公式迭代更新：其中k是迭代次数，拉格朗日函数l(w,z,θ)对于w
j
可分解；在各个从节点上并行地解决公式(4)来更新局部模型变量w
j
：5.根据权利要求4所述的一种基于mpi的分布式admm垃圾邮件分类方法，其特征在于，步骤4中主节点通过mpi规约功能汇总从节点的局部模型，通过如下代码创建mpi的通信子comm：comm＝mpi.comm_world，其中comm_world是mpi的内置对象，接着利用通信子实现规约功能，表示如下：comm.reduce(sendbuf,recvbuf,op,root)其中reduce是规约函数，sendbuf表示从节点发送的内容，传入局部模型变量及其对偶变量recvbuf表示主节点用于接收的变量，op表示具体规约的操作函数，使用mpi.sum函数，表示将从节点的值相加后传给主节点，root表示根节点序号，传入主节点序号0。6.根据权利要求5所述的一种基于mpi的分布式admm垃圾邮件分类方法，其特征在于，步骤5主节点更新全局模型，并利用mpi广播功能将全局模型分发到各个从节点；公式(5)写为闭式解来更新全局变量z：接着利用通信子实现广播功能，表示如下：comm.bcast(buf,root)其中bcast是广播函数，buf表示被广播的数据，传入主节点的全局模型变量z
k+1
，root表示根节点序号，传入主节点序号0。7.根据权利要求6所述的一种基于mpi的分布式admm垃圾邮件分类方法，其特征在于，令θ
j
＝ρu
j
，得到w
j
,z,u
j
的更新公式：
其中u
j
代替θ
j
成为对偶变量，并在各个从节点上迭代更新。8.根据权利要求7所述的一种基于mpi的分布式admm垃圾邮件分类方法，其特征在于，使用方差缩减的梯度下降算法在从节点上针对公式(9)优化，单独拿出svm损失函数部分，并定义：f
i
(w)＝max(1-y
i
w
t
x
i
,0)2(12)在第k次迭代中，先计算样本的平均梯度先计算样本的平均梯度其中n
j
是第j个从节点的训练集样本数量；接着令开始内迭代t-1次，其中第t次迭代对变量的一步更新公式为：其中η是学习率，完成t-1次内迭代后取均值作为第k+1次迭代的更新值：9.根据权利要求8所述的一种基于mpi的分布式admm垃圾邮件分类方法，其特征在于，使用公式(15)在从节点更新局部模型变量w
j
，接着主节点收集各个从节点的局部模型变量w
j
和对偶变量u
j
，主节点用公式(10)更新全局变量z，接着主节点将更新后的全局模型变量z分发到各个从节点，接着从节点用公式(11)更新对偶变量u
j
，不断循环执行以上步骤直到满足终止条件，即两次迭代更新变量的残差足够小，则表明算法收敛，停止迭代，设置最大迭代次数k；步骤6中循环执行步骤3至步骤5，交替更新从节点和主节点的模型变量，直到满足终止条件，即两次迭代更新变量的残差足够小至收敛，停止迭代，模型训练阶段结束，在步骤7保存主节点的全局模型变量z作为分类器模型。10.根据权利要求9所述的一种基于mpi的分布式admm垃圾邮件分类方法，其特征在于，步骤8为测试阶段，利用训练得到的分类器模型对测试集进行分类，设(x
i
,y
i
)是测试集的第i个样本数据，x
i
∈r
d
,y
i
∈{-1,+1}，则预测值为：
其中z是算法最后一次迭代输出的全局变量z
k
，z
t
的上标t是转置，sign()是符号函数，即：预测值时判定该样本为正样本，即为垃圾邮件，否则判定为负样本，即为正常邮件。

技术总结
本发明公开了一种基于MPI的分布式ADMM垃圾邮件分类方法，包含以下步骤：将文本数据向量化为数字格式的数据集；将数据集分割为训练集和测试集，对训练集进行过采样处理，再分割为若干份分别保存在若干个从节点上；MPI并行执行所有节点上的代码，从节点并行更新局部模型；主节点通过MPI规约功能汇总从节点的局部模型；主节点更新全局模型，并利用MPI广播功能将全局模型分发到各个从节点；循环交替更新从节点和主节点的模型，直到满足终止条件；保存主节点的全局模型作为分类器模型；利用训练得到的分类器模型对测试集进行分类，输出分类结果。本发明适合大数据场景下垃圾邮件分类任务，有效提升了分类的效率和精度。有效提升了分类的效率和精度。有效提升了分类的效率和精度。


技术研发人员：肖明霏 刘龙恩 王慧慧 周沧琦
受保护的技术使用者：南京理工大学
技术研发日：2021.12.06
技术公布日：2022/3/8