1.   引言

随着物联网(Internet of Things, IoT)技术的广泛应用，物联网节点数目不断增加，然而由于资源所限，节点无法完成计算密集型任务。因此面向物联网数据分析的传统机器学习通常基于集中式算法，由具备超强存储和计算能力的专用服务器对数据进行集中式地处理^[1]。然而进入万物互联和大数据时代^[2]以来，节点数量急剧增加的同时产生海量实时数据，基于集中式算法的传统机器学习对如此大规模的物联网数据进行分析处理时，主要面临3方面挑战：首先，直接将节点的海量数据上传至服务器，会造成网络带宽压力过大和计算资源的浪费^[1]；其次，传统的集中式算法在应用于求解大规模机器学习问题时可扩展性较差^[3]；最后，物联网数据若直接上传至服务器或其他设备进行训练，会面临数据隐私泄露的风险^[4]。事实上，为了解决大数据下传统机器学习面临的问题，各分布式数据并行平台纷纷研发分布式机器学习库，然而由于资源限制^[5]和隐私问题^[6]，它们并不适用于资源受限且异构的物联网节点。因此分布式优化算法逐渐涌现出来，将服务器难以完成的计算任务拆分成多个小计算任务分布式地部署到多个物联网节点上执行，然后将各节点的执行结果整合成最终结果并返回。相比于传统的集中式算法，分布式优化算法能够减轻网络带宽压力、降低通信成本，保护数据的隐私性。

本文主要研究如何利用分布式优化算法对物联网数据进行回归分析，重点研究目标是弹性网络回归^[7]这一典型的线性回归技术。本文提出一种基于多个物联网节点的协同弹性网络回归问题模型。针对该模型，引入交替方向乘子法(Alternating Direction Method of Multipliers, ADMM)算法^[1]，提出一种基于ADMM的分布式弹性网络回归学习算法，将需要由服务器集中式求解的目标优化问题分解成多个可以由物联网节点进行分布式独立求解的子问题。该算法并不要求节点将原始数据上传至服务器，而是由节点独立处理数据，仅仅向服务器传递中间结果，再由服务器整合并返回最终结果。服务器与节点之间以这种协作方式进行多次迭代直至模型收敛。为了验证所提算法的有效性以及评估该算法的性能，本文在两个典型数据集上进行大量的仿真实验，结果表明：所提算法可在几十轮内快速收敛到最优解；相比于本地化算法，提高了结果的有效性和准确性；相比于集中式算法，目标函数值和预测精度可逼近集中式算法的最优值，而且可降低网络传输带宽压力，提高计算的可扩展性，保护隐私数据的安全性。

2.   问题模型

2.1   弹性网络回归

弹性网络回归作为一种典型的线性回归技术，所解决的优化问题基本形式为

其中，$\left\{ {{{{x}}_i},{y_i}} \right\}$是数据样本，${{{x}}_i} \in {R^n}$是特征向量，${y_i}$是相应的因变量，特征权重向量${{w}} \in {R^n}$，截距$b \in R$，正则化参数${u_1},{u_2} > 0$。当${u_1} = 0$时，弹性网络回归退化为岭回归；当${u_2} = 0$时，则退化为Lasso回归

弹性网络回归模型建立的目标是通过训练求解得到的$({{w}},b)$的值，根据式(2)，对于给定的特征向量${{x}} \in {R^n}$能准确地预测出因变量y的值。虽然弹性网络回归具备很好的预测性能^[8]，但集中式算法增大网络带宽压力和隐私数据泄露的风险。即使采用网络安全机制，服务器端仍然存在泄露用户隐私数据的可能。

2.2   问题模型

基于弹性网络回归问题模型的基本形式(1)，本文进一步研究基于多个物联网节点的协同弹性网络回归学习问题。考虑由一个中心服务器与N个物联网节点组成的物联网系统，其中每个节点拥有相同的传感器组。首先，物联网节点$i \in \left\{ {1,2,···,N} \right\}$在一定时间内将通过板载传感器生成的原始数据转换为特征向量，每个特征向量包含n个预测变量，即${{{x}}_{ij}} \in {R^n}$，并对应于一个因变量${y_{ij}} \in R$，其中$j \in \left\{ {1,2,···,{M_i}} \right\}$, ${M_i}$是节点i提供的数据样本个数；其次，物联网节点i将数据样本${D_i} = \{ ({{{x}}_{ij}},{y_{ij}}), j = 1,2,···,{M_i}\}$由本地上传至服务器，由服务器对收集到的数据进行回归分析；最后，通过建立特征向量与因变量之间的回归模型，可以通过特征向量准确地预测出因变量的值。此时弹性网络回归解决的优化问题形式为

其中，特征向量${{{x}}_{ij}} \in {R^n}$，对应的因变量${y_{ij}} \in R$，特征权重向量${{w}} \in {R^n}$，截距$b \in R$，正则化参数${u_1},{u_2} > 0$。训练所得回归模型可以根据给定的新的特征向量${{{x}}_{ij}}$预测出因变量${y_{ij}}$的值。

3.   基于ADMM的分布式弹性网络回归学习算法

3.1   ADMM算法概述

ADMM算法是一个简洁高效的分布式优化算法，它独特的分布式架构而非常适用于分布式环境下的并行求解^[1]。它解决的优化问题形式为

其中，F和G是凸函数，X和Y是非空凸集，x和y是两个需要优化的原始变量，A, B, C是等式约束的参数。目标函数关于原始变量x, y可以分解成两个函数之和的形式，因此可使用ADMM算法求得最优解。

利用增广拉格朗日法^[9]对原问题式(4)进行求解，可得到增广拉格朗日函数形式为

其中，$\lambda \ge 0$是对偶变量，$\rho > 0$是惩罚参数。

原始的最小化问题式(4)转化为拉格朗日函数式(5)中原始变量$x$, $y$最小化，对偶变量$\lambda$最小化问题。在每轮迭代过程中，首先原始变量x, y进行交替优化，然后再更新对偶变量$\lambda$。求解过程总结为

文献[10]给出了ADMM算法收敛性的证明，在中等精度要求下，经过几十次迭代后即可收敛^[1]。

3.2   基于ADMM的分布式弹性网络回归学习算法

由于问题模型式(3)无法根据两个变量分解成两个函数之和的形式，不能使用ADMM算法进行求解。本文引入一组辅助变量$\left\{ {({{{w}}_i},{b_i}),i = 1,2,···,N} \right\}$，由此可转化为与原问题等价的新的优化问题，具体形式为

其中，$\{ ({{{w}}_i},{b_i}),i = 1,2,···,N\}$是物联网节点i的中间参数，$\left\{ {({{w}},b)} \right\}$是服务器整合节点的中间参数得到的全局参数。目标函数可以根据两个参数$\left\{ {({{w}},b)} \right\}$和$\{ ({{{w}}_i},{b_i}),i = 1,2,···,N\}$分解成两个函数之和的形式，因此可使用ADMM算法进行求解。利用增广拉格朗日法对问题式(9)进行求解，可得增广拉格朗日函数形式为

其中，$\alpha = \left\{ {({{w}},b)} \right\}$, $\beta = \{ ({{{w}}_i},{b_i}),i = 1,2,···,N\}$, $\gamma = \{ ({\gamma _{i,w}},{\gamma _{i,b}}),i = 1,2,···,N\}$。通过对拉格朗日函数式(10)中的参数$\alpha$, $\beta$和$\gamma$的迭代更新，可最终求得原问题的最优解，接下来将分别介绍各参数的更新过程。

(1) ${{\alpha}}$-更新部分：$\alpha$更新时需要解决的优化问题具有如式(11)的形式

其中，${\overline \theta ^k}$为在第k次迭代时，向量${\theta _i}(i = 1,2,···,N)$的均值。该优化问题由于包含L1范数而不可微，因此本文采用次梯度演算法(subgradient algorithm)对其进行求解。

令$\eta = \dfrac{{\rho N}}{{\rho N + {u_2}}}\left({\overline w ^k} + \dfrac{{{{\overline {{\gamma _w}} }^k}}}{\rho }\right)$, $\varphi = \dfrac{{{u_1}}}{{\rho N + {u_2}}}$，求解结果具有如式(12)的形式

(2) ${{\beta}}$-更新部分：当$\alpha$通过更新得到${\alpha ^{k + 1}}$即$\left\{ ({{{w}}^{k + 1}}, {b^{k + 1}}) \right\}$后，$\beta$更新时需要解决的优化问题具有如式(14)的形式

问题式(14)可以分解成N个独立的子问题，并部署到多个物联网节点求解，节点i

问题式(15)是一个典型的非线性规划问题，本文引入PRP(Polak, Ribiere and Polyar)共轭梯度法^[11]对其进行求解，具体流程详见表1。首先，将问题式(15)看作关于${{{w}}_i}$的函数$F({{{w}}_i})$，令${b_i} = b_i^t$求得使函数$F({{{w}}_i})$最小化的最优解${{w}}_i^*$；其次，固定${{{w}}_i} = {{w}}_i^*$，将问题式(15)看作关于${b_i}$的函数$F({b_i})$，求得使函数$F({b_i})$最小化的最优解$b_i^*$；最后，两组变量以这种方式多次交替更新可以求得最优解${{w}}_i^{t + 1} = {{w}}_i^*$, $b_i^{t + 1} = b_i^*$。篇幅所限，本文仅介绍${{{w}}_i}$的求解方法，对${b_i}$的求解同理。物联网节点i关于${{{w}}_i}$的目标优化问题为

表 1  PRP共轭梯度算法流程

输入：特征向量${{{x}}_{ij}}$；相应变量${y_{ij}}$；服务器提供的参数$\alpha = \left\{ {({{{w}}^{k + 1}},{b^{k + 1}})} \right\}$；对偶变量${\gamma ^k} = \{ ({\gamma _{i,w}}^k,{\gamma _{i,b}}^k)\}$; $b_i^*$；
输出：物联网节点i的局部最优解${{{w}}_i}^*$；
(1) 初始迭代次数$t = 0$，初始向量${{{w}}_i}^0 = 0$，收敛精度$\varepsilon = 1e - 5$，初始搜索方向${{{p}}^0} = - g({{{w}}_i}^0)$；
(2) repeat /*算法进行迭代*/
(3) 　　 for j = –1:2:1
(4) 　　　　 if $F({w_i}^t + {\lambda ^t}{{{p}}^t}) > F({{{w}}_i}^t + j * {{{p}}^t})$ then
(5) 　　　　　　 ${\lambda ^t} \leftarrow j$;
(6) 　　　　 end if
(7) 　　 end for
(8) 　　 ${{{w}}_i}^{t + 1} \leftarrow {{{w}}_i}^t + {\lambda ^t}{{{p}}^t}$; 　(9) 　　 ${\beta ^t} \leftarrow \dfrac{ {g{ {({ {{w} }_i}^{t + 1})}^{\rm{T} } }(g({ {{w} }_i}^{t + 1}) - g({ {{w} }_i}^t))} }{ {g{ {({ {{w} }_i}^t)}^{\rm{T} } }g({ {{w} }_i}^t)} }$;
(10) 　　${{{p}}^{t + 1}} = - g({{{w}}_i}^{t + 1}) + {\beta ^t}{{{p}}^t}$;
(11) $t \leftarrow t + 1$;
(12) until $\left\| {g({ {{w} }_i}^t)} \right\| \le \varepsilon$; /*算法达到收敛准则，停止迭代*/
(13) ${{{w}}_i}^* \leftarrow {{{w}}_i}^t$;

下载: 导出CSV 

| 显示表格

(3) ${{\gamma}}$-更新部分：$\alpha$和$\beta$通过更新得到${\alpha ^{k + 1}} = \left\{ {\left( {{{{w}}^{k + 1}},{b^{k + 1}}} \right)} \right\}$, ${\beta ^{k + 1}} = \left\{ {\left( {{{{w}}_i}^{k + 1},{b_i}^{k + 1}} \right)} \right\}$后，$\gamma$更新为

图1说明了分布式弹性网络回归学习算法的计算流程。本文采用原始残差${r^k}$和对偶残差${s^k}$共同作为算法的收敛标准^[1]，记${\varepsilon ^{{\rm{rel}}}}$和${\varepsilon ^{{\rm{abs}}}}$分别是原始残差和对偶残差的偏差阈值，取经验值为${\varepsilon ^{{\rm{rel}}}} = 1{\rm{e}} - 2$, ${\varepsilon ^{{\rm{abs}}}} = 1{\rm{e}} - 4$。当${\left\| {{r^k}} \right\|_2} \le {\varepsilon ^{{\rm{rel}}}}{\rm{,}} {\left\| {{s^k}} \right\|_2} \le {\varepsilon ^{{\rm{abs}}}}$时，则视为算法达到收敛准则^[1]。分布式弹性网络回归学习算法的具体流程详见表2。该算法的收敛性及收敛速度证明可参考文献[12,13]，考虑到其复杂性和版面限制，本文不再赘述。

图 1  分布式弹性网络回归学习算法计算流程

下载: 全尺寸图片 幻灯片

表 2  分布式弹性网络回归学习算法流程

输入：物联网节点的样本数据，包括特征向量${{{x}}_{ij}}$；相应因变量${y_{ij}}$;
输出：最终结果$\alpha = \left\{ {({{{w}}^*},{b^*})} \right\}$;
(1) 服务器初始参数设置：$k = 0,\;\;\overline w = 0,\;\;{\overline b ^0} = 0,\;\;{\varepsilon ^{{\rm{rel}}}} = 1e - 2,\;\;{\varepsilon ^{{\rm{abs}}}} = 1e - 4$;
(2) 物联网节点i参数设置: $k = 0,\gamma _{i,w}^0 = 0,\gamma _{i,b}^0 = 0$;
(3)Repeat /*算法进行迭代*/
(4) 　　服务器整合物联网节点上传的中间参数$\left( {{{w}}_i^k,b_i^k} \right)$及$\left( {\gamma _{i,w}^k,\gamma _{i,b}^k} \right)$，求得各变量均值${\overline {{w}} ^k},{\overline b ^k},{\overline {{\gamma _w}} ^k},{\overline {{\gamma _b}} ^k}$，根据式(12)和式(13)更新参数 　　 　　$\left( {{{{w}}^{k + 1}},{b^{k + 1}}} \right)$，并将结果广播给物联网节点;
(5) 　　物联网节点i根据服务器提供的参数$\left( {{{{w}}^{k + 1}},{b^{k + 1}}} \right)$对问题式(14)进行求解得到参数$\left( {{{w}}_i^{k + 1},b_i^{k + 1}} \right)$;
(6) 　　物联网节点i根据式(17)和式(18)更新对偶变量$\left( {\gamma _{i,w}^{k + 1},\gamma _{i,b}^{k + 1}} \right)$;
(7) 　　物联网节点i向服务器发送新的中间参数$\left( {{{w}}_i^{k + 1},b_i^{k + 1}} \right)$及$\left( {\gamma _{i,w}^{k + 1},\gamma _{i,b}^{k + 1}} \right)$;
(8) $k \leftarrow k + 1$;
(9) until ${\left\| { {r^k} } \right\|_2} \le {\varepsilon ^{ {\rm{rel} } } }{\rm{,} }{\left\| { {s^k} } \right\|_2} \le {\varepsilon ^{ {\rm{abs} } } }$; /*算法达到收敛准则，停止迭代*/

下载: 导出CSV 

| 显示表格

4.   实验与分析

4.1   实验设置

为了验证分布式弹性网络回归学习算法的有效性及其性能，本文在两个典型数据集上进行了仿真实验，其中拟合数据集根据文献[1]的描述生成，包括1500个数据样本，每个样本包含9维特征向量和1个相应的因变量。通过使用数据集，不仅可以验证所提算法的有效性，而且能够在不考虑数据质量的前提下评估各参数对算法性能的影响以及与其它方法进行性能比较。然而由于该拟合数据集数据质量高且分布均匀，缺乏真实性。因此为了进一步评估该算法在实际应用中的性能，本文在真实数据集上进行了仿真实验。该真实数据集则为文献[14]中提到的公开疾病数据集，包含442个患者的数据样本，每个样本包含10个生理特征以及1年以后疾病级数指标。在本文实验中，将数据集按照7:3的比例划分为训练集和测试集。除特殊说明外，实验参数均设置为：$\rho = 1.0,{u_1} = 0.01,{u_2} = 0.01,$ ${\varepsilon ^{{\rm{rel}}}} = 1{\rm{e}} - 2, {\varepsilon ^{_{{\rm{abs}}}}} = 1{\rm{e}} - 4$^[1]。为了进一步评估所提算法的性能，本文设计了相关实验将其与传统的集中式算法以及本地化算法两种方法进行比较。

4.2   实验结果

4.2.1   算法的有效性

首先，为了验证所提算法的收敛性，本文采用拟合数据集，在物联网节点数量N的不同取值下进行了多组实验，并观察到对于不同的N值，算法均具有良好的收敛性。采用集中式算法计算的目标函数值作为最优值，并以此为基准与分布式算法所得目标函数值进行对比。当$N = 20$时算法的收敛性如图2所示。图2说明随着迭代次数的增加，目标函数值在前50次迭代过程中快速下降，迭代次数为100次时接近集中式算法求得的目标函数值。图3则表示${\left\| r \right\|_2}$和${\left\| s \right\|_2}$随迭代次数的变化，最终当迭代次数为227次时，算法达到收敛准则。实验结果表明，本文所提分布式算法可以在有限的迭代次数内收敛并接近集中式算法的目标函数值。

图 2  目标函数值随迭代次数变化

下载: 全尺寸图片 幻灯片

图 3  原始残差和对偶残差随迭代次数变化

下载: 全尺寸图片 幻灯片

其次，为了进一步评估所提算法的性能，本文采用校正复相关系数(${R^2_a}$)^[15]和均方根误差(Root Mean Square Error, RMSE)分别评估算法模型的拟合效果和预测精度。图4和图5说明在大约前100次迭代过程中，所提算法RMSE值持续降低，${R^2_a}$值不断增加。当算法达到收敛准则时，RMSE的值为0.03987，逼近集中式算法的预测精度；${R^2_a}$的值为0.998307趋近于1，表示算法模型具备较好的拟合效果。实验结果表明本文所提算法可以在有限迭代次数内收敛得到接近集中式算法的拟合效果和预测精度。

图 4  RMSE值随迭代次数变化

下载: 全尺寸图片 幻灯片

图 5  调整复相关系数${R^2_a}$值随迭代次数变化

下载: 全尺寸图片 幻灯片

4.2.2   参数对算法性能的影响

为研究各参数的设置对算法性能的影响，本文在拟合数据集上进行了8组实验，以目标函数值和RMSE值作为算法性能的评价指标，在保证其他参数固定不变的条件下，分别评估参数$N,\rho,{u_1},{u_2}$对算法性能的影响。其中参数N对算法性能的影响如图6所示，可以发现当N取不同值时，算法均能收敛，而且N值越小时，算法的收敛速度越快，但最终均能得到相同的目标函数值和RMSE值，表明算法具备较好的可扩展性。参数$\rho$对算法性能的影响如图7所示，可以发现$\rho$值较小时，算法可以更快地收敛，目标函数值和RMSE值较大。参数${u_1}$和${u_2}$对算法性能的影响分别如图8和图9所示，说明${u_1}$对算法的收敛速度影响较小，但对目标函数值和RMSE值影响较大，${u_1}$值越小，目标函数值和RMSE值就越小；与${u_1}$相似，${u_2}$值越小，目标函数值和RMSE值也越小，不同的是，${u_2}$对算法的收敛速度影响较大，${u_2}$值越大，算法的收敛速度越快。

图 6  参数N对算法性能的影响

下载: 全尺寸图片 幻灯片

图 7  参数$\rho$对算法性能的影响

下载: 全尺寸图片 幻灯片

图 8  参数${u_1}$对算法性能的影响

下载: 全尺寸图片 幻灯片

图 9  参数${u_2}$对算法性能的影响

下载: 全尺寸图片 幻灯片

4.2.3   与其它方法性能比较

相比于分布式算法，本地化算法的性能很大程度上与单个物联网节点处理的本地数据集规模大小相关，因此将数据集随机均匀地划分为N个训练子集，即由N个节点独立训练，并以${R^2_a}$和RMSE值作为评价指标，比较在N的不同取值下两种算法的性能。值得注意的是，当$N = 1$时本地化算法等同于集中式算法。

图10(a)、图10(b)分别表示不同N值下两种算法的RMSE值和${R^2_a}$值比较。由图10(a)可以发现，所提算法RMSE均值基本不随N值变化，始终维持在0.03左右，而本地化算法随着N值的增大，RMSE均值不断增大。同时，RMSE值之间的差值也在增加，说明由于单个物联网节点本地数据集规模较小，不同节点之间的训练结果差异较大。由图10(b)可以发现，所提算法${R^2_a}$值始终稳定在0.98左右，基本不随N值变化。相比之下，本地化算法${R^2_a}$值受N值的影响较大。在$N < 60$时${R^2_a}$值非常接近本文所提算法，然而当$N > 60$时，${R^2_a}$值显著下降，当$N = 80$时，其值已经降为负数，表明此时该模型对数据集并没有拟合效果。实验结果表明，在单个物联网节点的本地数据集规模较小且缺乏多样性的情况下，本地化算法训练得到的弹性网络回归模型性能较差，不仅预测精度降低而且拟合效果也显著下降。相比之下，本文所提算法可以利用多个物联网节点提供的样本数据，因而始终可以收敛到接近最优的状态并获得接近集中式算法性能的模型。

图 10  分布式算法与本地化算法之间的性能比较

下载: 全尺寸图片 幻灯片

4.2.4   应用于真实数据集的实验结果

为了进一步评估分布式算法在真实场景下的性能表现，本文使用相同的评价指标在疾病数据集^[14]上进行了相关实验。由于篇幅所限，本文只列出相比于拟合数据集表现出显著不同的实验结果如图11—图13所示。

图 11  目标函数值随迭代次数变化

下载: 全尺寸图片 幻灯片

图 12  RMSE随迭代次数变化

下载: 全尺寸图片 幻灯片

图 13  分布式算法与本地化算法之间的性能比较

下载: 全尺寸图片 幻灯片

首先，如图11和图12所示，当$N = 20$时，本文所提分布式算法的目标函数值和RMSE值在大约前5次迭代中快速下降，大约40次迭代后就已经接近集中式方法的最优解，这种快速收敛的现象与真实数据集的规模较小有关。其次，图13说明本地化算法是3种算法中性能表现最差的。当$N = 15$时，本地化算法的RMSE值远远大于集中式算法和本文所提分布式算法，而且其${R^2_a}$值已经降为负数，由此可以发现，当样本数据规模较小且数据缺乏多样性时，单个物联网节点很难通过对本地数据进行独立训练得到一个好的模型。最后，实验结果说明，在应用于真实数据集时，所提算法仍然能够得到接近集中式算法性能的模型。

5.   结束语

本文面向物联网数据提出一种分布式弹性网络回归学习算法，该算法基于ADMM算法，将需要集中式求解的弹性网络回归目标优化问题分解为多个可以由物联网节点利用本地数据进行独立求解的子问题。该算法不要求节点向服务器上传原始数据，仅需上传中间结果，由服务器进行简单整合得到最终结果并返回。本文在两个典型数据集上的实验结果表明：该算法能够在几十轮迭代内快速收敛到最优解；所得目标函数值和预测精度接近集中式算法，相比于集中式算法，既减轻带宽压力又保护数据隐私性；相比于本地化算法，提高了计算结果的有效性和准确性。接下来的研究工作中，我们将进一步研究分布式优化算法在其他机器学习问题中的应用，以及在物联网实验中采用该算法解决实际问题，进一步评估它在实际应用中的性能表现。