面向物聯(lián)網(wǎng)隱私數(shù)據(jù)分析的分布式彈性網(wǎng)絡(luò)回歸學(xué)習(xí)算法
doi: 10.11999/JEIT190739
-
1.
北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 北京 100044
-
2.
社會(huì)安全風(fēng)險(xiǎn)感知與防控大數(shù)據(jù)應(yīng)用國(guó)家工程實(shí)驗(yàn)室 北京 100041
-
3.
中國(guó)科學(xué)院計(jì)算技術(shù)研究所 北京 100190
A Distributed Elastic Net Regression Algorithm for Private Data Analytics in Internet of Things
-
1.
School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044, China
-
2.
National Engineering Laboratory for Public Safety Risk Perception and Control, Beijing 100041, China
-
3.
Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
-
摘要: 為了解決基于集中式算法的傳統(tǒng)物聯(lián)網(wǎng)數(shù)據(jù)分析處理方式易引發(fā)網(wǎng)絡(luò)帶寬壓力過(guò)大、延遲過(guò)高以及數(shù)據(jù)隱私安全等問(wèn)題,該文針對(duì)彈性網(wǎng)絡(luò)回歸這一典型的線性回歸模型,提出一種面向物聯(lián)網(wǎng)(IoT)的分布式學(xué)習(xí)算法。該算法基于交替方向乘子法(ADMM),將彈性網(wǎng)絡(luò)回歸目標(biāo)優(yōu)化問(wèn)題分解為多個(gè)能夠由物聯(lián)網(wǎng)節(jié)點(diǎn)利用本地?cái)?shù)據(jù)進(jìn)行獨(dú)立求解的子問(wèn)題。不同于傳統(tǒng)的集中式算法,該算法并不要求物聯(lián)網(wǎng)節(jié)點(diǎn)將隱私數(shù)據(jù)上傳至服務(wù)器進(jìn)行訓(xùn)練,而僅僅傳遞本地訓(xùn)練的中間參數(shù),再由服務(wù)器進(jìn)行簡(jiǎn)單整合,以這樣的協(xié)作方式經(jīng)過(guò)多輪迭代獲得最終結(jié)果?;趦蓚€(gè)典型數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明:該算法能夠在幾十輪迭代內(nèi)快速收斂到最優(yōu)解。相比于由單個(gè)節(jié)點(diǎn)獨(dú)立訓(xùn)練模型的本地化算法,該算法提高了模型結(jié)果的有效性和準(zhǔn)確性;相比于集中式算法,該算法在確保計(jì)算準(zhǔn)確性和可擴(kuò)展性的同時(shí),可有效地保護(hù)個(gè)體隱私數(shù)據(jù)的安全性。
-
關(guān)鍵詞:
- 物聯(lián)網(wǎng) /
- 隱私保護(hù) /
- 彈性網(wǎng)絡(luò)回歸 /
- 分布式算法 /
- 交替方向乘子法
Abstract: In order to solve the problems caused by the traditional data analysis based on the centralized algorithm in the IoT, such as excessive bandwidth occupation, high communication latency and data privacy leakage, considering the typical linear regression model of elastic net regression, a distributed learning algorithm for Internet of Things (IoT) is proposed in this paper. This algorithm is based on the the Alternating Direction Method of Multipliers (ADMM) framework. It decomposes the objective problem of elastic net regression into several sub-problems that can be solved independently by each IoT node using its local data. Different from traditional centralized algorithms, the proposed algorithm does not require the IoT node to upload its private data to the server for training, but rather the locally trained intermediate parameters to the server for aggregation. In such a collaborative manner, the server can finally obtain the objective model after several iterations. The experimental results on two typical datasets indicate that the proposed algorithm can quickly converge to the optimal solution within dozens of iterations. As compared to the localized algorithm in which each node trains the model solely based on its own local data, the proposed algorithm improves the validity and the accuracy of training models; as compared to the centralized algorithm, the proposed algorithm can guarantee the accuracy and the scalability of model training, and well protect the individual private data from leakage. -
表 1 PRP共軛梯度算法流程
輸入:特征向量${{{x}}_{ij}}$;相應(yīng)變量${y_{ij}}$;服務(wù)器提供的參數(shù)$\alpha = \left\{ {({{{w}}^{k + 1}},{b^{k + 1}})} \right\}$;對(duì)偶變量${\gamma ^k} = \{ ({\gamma _{i,w}}^k,{\gamma _{i,b}}^k)\} $; $b_i^*$; 輸出:物聯(lián)網(wǎng)節(jié)點(diǎn)i的局部最優(yōu)解${{{w}}_i}^*$; (1) 初始迭代次數(shù)$t = 0$,初始向量${{{w}}_i}^0 = 0$,收斂精度$\varepsilon = 1e - 5$,初始搜索方向${{{p}}^0} = - g({{{w}}_i}^0)$; (2) repeat /*算法進(jìn)行迭代*/ (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$; /*算法達(dá)到收斂準(zhǔn)則,停止迭代*/ (13) ${{{w}}_i}^* \leftarrow {{{w}}_i}^t$; 下載: 導(dǎo)出CSV
表 2 分布式彈性網(wǎng)絡(luò)回歸學(xué)習(xí)算法流程
輸入:物聯(lián)網(wǎng)節(jié)點(diǎn)的樣本數(shù)據(jù),包括特征向量${{{x}}_{ij}}$;相應(yīng)因變量${y_{ij}}$; 輸出:最終結(jié)果$\alpha = \left\{ {({{{w}}^*},{b^*})} \right\}$; (1) 服務(wù)器初始參數(shù)設(shè)置:$k = 0,\;\;\overline w = 0,\;\;{\overline b ^0} = 0,\;\;{\varepsilon ^{{\rm{rel}}}} = 1e - 2,\;\;{\varepsilon ^{{\rm{abs}}}} = 1e - 4$; (2) 物聯(lián)網(wǎng)節(jié)點(diǎn)i參數(shù)設(shè)置: $k = 0,\gamma _{i,w}^0 = 0,\gamma _{i,b}^0 = 0$; (3)Repeat /*算法進(jìn)行迭代*/ (4) 服務(wù)器整合物聯(lián)網(wǎng)節(jié)點(diǎn)上傳的中間參數(shù)$\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}$,根據(jù)式(12)和式(13)更新參數(shù)
$\left( {{{{w}}^{k + 1}},{b^{k + 1}}} \right)$,并將結(jié)果廣播給物聯(lián)網(wǎng)節(jié)點(diǎn);(5) 物聯(lián)網(wǎng)節(jié)點(diǎn)i根據(jù)服務(wù)器提供的參數(shù)$\left( {{{{w}}^{k + 1}},{b^{k + 1}}} \right)$對(duì)問(wèn)題式(14)進(jìn)行求解得到參數(shù)$\left( {{{w}}_i^{k + 1},b_i^{k + 1}} \right)$; (6) 物聯(lián)網(wǎng)節(jié)點(diǎn)i根據(jù)式(17)和式(18)更新對(duì)偶變量$\left( {\gamma _{i,w}^{k + 1},\gamma _{i,b}^{k + 1}} \right)$; (7) 物聯(lián)網(wǎng)節(jié)點(diǎn)i向服務(wù)器發(fā)送新的中間參數(shù)$\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} } } }$; /*算法達(dá)到收斂準(zhǔn)則,停止迭代*/ 下載: 導(dǎo)出CSV
-
BOYD S, PARIKH N, CHU E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends? in Machine Learning, 2011, 3(1): 1–122. doi: 10.1561/2200000016 邵振峰, 蔡家駿, 王中元, 等. 面向智能監(jiān)控?cái)z像頭的監(jiān)控視頻大數(shù)據(jù)分析處理[J]. 電子與信息學(xué)報(bào), 2017, 39(5): 1116–1122. doi: 10.11999/JEIT160712SHAO Zhenfeng, CAI Jiajun, WANG Zhongyuan, et al. Analytical processing method of big surveillance video data based on smart monitoring cameras[J]. Journal of Electronics &Information Technology, 2017, 39(5): 1116–1122. doi: 10.11999/JEIT160712 DHAR S, YI C R, RAMAKRISHNAN N, et al. ADMM based scalable machine learning on spark[C]. 2015 IEEE International Conference on Big Data (Big Data), Santa Clara, USA, 2015: 1174–1182. doi: 10.1109/BigData.2015.7363871. 趙海濤, 朱銀陽(yáng), 丁儀, 等. 車(chē)聯(lián)網(wǎng)中基于移動(dòng)邊緣計(jì)算的內(nèi)容感知分類(lèi)卸載算法研究[J]. 電子與信息學(xué)報(bào), 2020, 42(1): 20–27. doi: 10.11999/JEIT190594ZHAO Haitao, ZHU Yinyang, DING Yi, et al. Research on content-aware classification offloading algorithm based on mobile edge calculation in the internet of vehicles[J]. Journal of Electronics &Information Technology, 2020, 42(1): 20–27. doi: 10.11999/JEIT190594 SHI Weisong, ZHANG Xingzhou, WANG Yifan, et al. Edge computing: State-of-the-art and future directions[J]. Journal of Computer Research and Development, 2019, 56(1): 69–89. doi: 10.7544/issn1000-1239.2019.20180760 CHOUDHURY T, GUPTA A, PRADHAN S, et al. Privacy and security of cloud-based Internet of Things (IoT)[C]. The 3rd International Conference on Computational Intelligence and Networks (CINE), Odisha, India, 2017: 40–45. doi: 10.1109/CINE.2017.28. ZOU Hui and HASTIE T. Regularization and variable selection via the elastic net[J]. Journal of the Royal Statistical Society: Series B (Statistical Methodology) , 2005, 67(2): 301–320. doi: 10.1111/j.1467-9868.2005.00503.x SHEN Yi, HAN Bing, and BRAVERMAN E. Stability of the elastic net estimator[J]. Journal of Complexity, 2016, 32(1): 20–39. doi: 10.1016/j.jco.2015.07.002 LUO Hezhi, SUN Xiaoling, and LI Duan. On the convergence of augmented lagrangian methods for constrained global optimization[J]. SIAM Journal on Optimization, 2007, 18(4): 1209–1230. doi: 10.1137/060667086 BERTSEKAS D P and TSITSIKLIS J N. Parallel and Distributed Computation: Numerical Methods[M]. London: Prentice Hall, 1989. ZHANG Yueqin, ZHENG Hao, and ZHANG Chuanlin. Global convergence of a modified PRP conjugate gradient method[J]. Procedia Engineering, 2012, 31: 986–995. doi: 10.1016/j.proeng.2012.01.1131 HE Bingsheng and YUAN Xiaoming. On the O(1/n) convergence rate of the Douglas-Rachford alternating direction method[J]. SIAM Journal on Numerical Analysis, 2012, 50(2): 700–709. doi: 10.1137/110836936 NISHIHARA R, LESSARD L, RECHT B, et al. A general analysis of the convergence of ADMM[C]. The 32nd International Conference on International Conference on Machine Learning, Lille, France, 2015: 343–352. EFRON B, HASTIE T, JOHNSTONE I, et al. Least angle regression[J]. Annals of Statistics, 2004, 32(2): 407–451. doi: 10.1214/009053604000000067 SPENCER B, ALFANDI O, and AL-OBEIDAT F. A refinement of lasso regression applied to temperature forecasting[J]. Procedia Computer Science, 2018, 130: 728–735. doi: 10.1016/j.procs.2018.04.127 -