基于凸和非凸優(yōu)化低秩矩估計(jì)的大數(shù)據(jù)處理算法

劉曉霞 王鈺寧 陳 霞

摘? 要：針對(duì)大數(shù)據(jù)處理中存在的優(yōu)化問題，提出一種基于凸和非凸優(yōu)化低秩矩估計(jì)的大數(shù)據(jù)處理算法，并利用物聯(lián)網(wǎng)采集與感知的大數(shù)據(jù)進(jìn)行算法的實(shí)驗(yàn)驗(yàn)證與對(duì)比分析。在簡(jiǎn)單描述凸優(yōu)化、非凸優(yōu)化和低秩矩陣優(yōu)化基礎(chǔ)上，設(shè)計(jì)了基于凸和非凸優(yōu)化低秩矩估計(jì)的大數(shù)據(jù)處理算法，并對(duì)算法收斂性進(jìn)行了分析;然后利用物聯(lián)網(wǎng)感知設(shè)備，進(jìn)行數(shù)據(jù)感知與采集，然后利用所設(shè)計(jì)的算法進(jìn)行對(duì)比實(shí)驗(yàn)。通過實(shí)驗(yàn)表明，本文算法在訓(xùn)練時(shí)和測(cè)試時(shí)，在歸一化平均絕對(duì)誤差和運(yùn)行時(shí)間上，具有較好的結(jié)果。

關(guān)鍵詞：凸優(yōu)化;非凸優(yōu)化;低秩矩陣;估計(jì);大數(shù)據(jù)處理

中圖分類號(hào)：TP309? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

Processing Algorithm for Big Data Based on Convex Optimization，Non-convex Optimization and Low-Rank Matrix Estimation

LIU Xiaoxia，WANG Yuning，CHEN Xia

（Department of Information Engineering，Sichuan Water Conservancy Vocational College，Chongzhou 611231，China）

Abstract：Aiming to the optimization problem in big data processing，a big data processing algorithm based on convex optimization，non-convex optimization and low rank matrix estimation is proposed，and the experimental verification and comparative analysis of the algorithm are carried out by means of the big data collected and perceived by Internet of Things.On the basis of convex optimization，non-convex optimization and low rank matrix optimization，the big data processing algorithm is designed and the convergence of the algorithm is analyzed.Then data perception and collection are performed by using the Internet of Things perception devices and the proposed algorithm is used to conduct comparative experiments.Experiments show that the proposed algorithm has good results in normalized mean absolute error and running time during training and testing.

Keywords：convex optimization;non-convex optimization;low rank matrix;estimation;big data processing

1? ?引言（Introduction）

各類數(shù)據(jù)信息形成的大規(guī)模高維數(shù)據(jù)正在以每年ZB（Zetta Byte，ZB）級(jí)海量遞增，為處理和存儲(chǔ)帶來巨大的機(jī)遇和嚴(yán)峻的挑戰(zhàn)。而各種數(shù)據(jù)的采集與處理過程中，幾乎都是高維數(shù)據(jù)且相互關(guān)聯(lián)，需要進(jìn)行數(shù)據(jù)優(yōu)化。而凸優(yōu)化由于其在凸集、凸函數(shù)的結(jié)構(gòu)和特性，具有不確定性，已應(yīng)用于信號(hào)處理、生物信息學(xué)、機(jī)器學(xué)習(xí)和大數(shù)據(jù)等。

對(duì)于凸優(yōu)化、非凸優(yōu)化和低秩矩陣優(yōu)化等，國(guó)內(nèi)外研究者們進(jìn)行了諸多研究，取得了一定成果。文獻(xiàn)[1]對(duì)復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)選擇問題進(jìn)行研究，提出一種基于凸優(yōu)化的維度不精確乘法器交替向量算法。文獻(xiàn)[2]利用非凸優(yōu)化理論研究航站間路徑規(guī)劃的編碼問題，提出一種基于非凸優(yōu)化的非連續(xù)時(shí)間的航站間約束滿足的非凸路徑規(guī)劃編碼算法。文獻(xiàn)[3]對(duì)低秩矩陣優(yōu)化中的全局最優(yōu)性問題進(jìn)行研究，分析一般目標(biāo)函數(shù)下的最多矩陣的最小化問題。文獻(xiàn)[4]利用隨機(jī)方法對(duì)大規(guī)模矩陣進(jìn)行低秩近似研究，提出了一個(gè)稀疏的正交變換矩陣來減少數(shù)據(jù)維數(shù)的算法。文獻(xiàn)[5]用低秩矩陣完備的大規(guī)模通信估計(jì)。以上研究，將凸優(yōu)化、非凸優(yōu)化和低秩矩陣優(yōu)化應(yīng)用于不同場(chǎng)景，僅文獻(xiàn)[6]利用凸優(yōu)化、非凸優(yōu)化和低秩序矩陣估計(jì)來處理大數(shù)據(jù)結(jié)構(gòu)性問題。

綜上，應(yīng)用凸優(yōu)化和非凸優(yōu)化，結(jié)合低秩序矩陣優(yōu)化的優(yōu)越優(yōu)化性能，研究大數(shù)據(jù)的處理算法，提出一種基于凸和非凸優(yōu)化低秩矩估計(jì)的大數(shù)據(jù)處理算法，并利用物聯(lián)網(wǎng)采集與感知的大數(shù)據(jù)進(jìn)行算法的實(shí)驗(yàn)驗(yàn)證與對(duì)比分析。

2? ?相關(guān)優(yōu)化方法（Related optimization method）

本部分，簡(jiǎn)單介紹凸優(yōu)化、非凸優(yōu)化和低秩矩陣優(yōu)化的概念。

2.1? ?凸優(yōu)化和非凸優(yōu)化

凸優(yōu)化的目標(biāo)函數(shù)為凸函數(shù)，同時(shí)變量所屬集合為凸集。在變量所屬集合中的任意兩點(diǎn)，連線得到的直線段，如直線段上的所有點(diǎn)，均分布于變量所屬集合內(nèi)，則該變量所屬集合為凸集。即假定集合，若和，有：

成立，則稱集合為凸集。假設(shè)給定集合為凸集，若使得：

成立，則稱函數(shù)為定義在凸集上的凸函數(shù)。因此，若滿足：

且為定義在（為凸集）上的凸函數(shù)，則該優(yōu)化問題稱為凸優(yōu)化。

而不能直接用凸優(yōu)化進(jìn)行優(yōu)化的問題即為非凸優(yōu)化。而現(xiàn)實(shí)世界的大部分優(yōu)化問題為非凸優(yōu)化，非凸優(yōu)化是可解決如機(jī)器學(xué)習(xí)、信號(hào)處理等，直接對(duì)非凸問題進(jìn)行直接優(yōu)化，得到全局最優(yōu)解。

對(duì)應(yīng)于凸優(yōu)化之定義與描述，可形式化得到非凸優(yōu)化的描述。如式（1）、（2）和（3）所示，若目標(biāo)函數(shù)不是凸函數(shù)，則該問題為非凸優(yōu)化;若變量中包含離散變量或0-1變量或整數(shù)變量，則該問題為非凸優(yōu)化;約束條件，不是凸函數(shù)，則該問題為非凸優(yōu)化。即假定集合，若和，有：

成立，則稱集合為非凸集。假設(shè)給定集合為非凸集，若使得：

成立，則稱函數(shù)為定義在非凸集上的非凸函數(shù)。因此，若滿足：

且為定義在（為非凸集）上的非凸函數(shù)，則該優(yōu)化問題稱為非凸優(yōu)化。

2.2? ?低秩矩陣優(yōu)化

矩陣的秩描述矩陣行（列）向量極大無關(guān)組的個(gè)數(shù)。低秩矩陣是指給定矩陣的秩遠(yuǎn)小于矩陣的行數(shù)或列數(shù)。

對(duì)秩為的矩陣進(jìn)行奇異值分解，可描述為：

其中，為對(duì)應(yīng)的奇異值和奇異向量。由此，低秩矩陣的集合可描述為：

因此，低秩矩陣優(yōu)化問題可形式化描述為：

其中，矩陣變量，函數(shù)為變量的損失函數(shù);為矩陣的秩，作為正則化項(xiàng)描述，以確保矩陣的低秩特性;為平衡因子，以使損失函數(shù)和低秩間平衡。

低秩矩陣優(yōu)化問題就轉(zhuǎn)化為目標(biāo)函數(shù)式（9）最小化問題，即通過優(yōu)化算法，求解一個(gè)最優(yōu)化矩陣，使得在給定平衡因子下，損失函數(shù)和矩陣的秩均為最小。

3? ?大數(shù)據(jù)處理算法（Big data processing algorithm）

本節(jié)將利用凸優(yōu)化、非凸優(yōu)化和低秩矩陣優(yōu)化方法，設(shè)計(jì)一種基于凸優(yōu)化和非凸優(yōu)化低秩矩陣估計(jì)的大數(shù)據(jù)處理算法，并對(duì)算法的收斂性進(jìn)行分析。

3.1? ?算法設(shè)計(jì)

對(duì)海量大數(shù)據(jù)進(jìn)行處理，其處理問題大多為非凸問題，需要使用一定理論和方法進(jìn)行凸問題轉(zhuǎn)化。在快速有效地處理大數(shù)據(jù)方面，提出一種非凸正則化凸優(yōu)化的低秩矩陣估計(jì)算法，并構(gòu)建一種有效的解決方法來求解最優(yōu)解。

給定缺少值的矩陣，其秩最小化的矩陣完備一般公式為：

其中，為矩陣中已知元素索引集合。因矩陣秩最小化問題為NP-hard（Non-deterministic Polynomial hard，NP-hard）問題，故需要用其他方法進(jìn)行凸松弛優(yōu)化，即：

通過廣義奇異值閾值非凸逼近問題時(shí)，其較大奇異值為需保留的信息，而較小奇異值通常為零處罰函數(shù)的噪聲信息。實(shí)際中，期望矩陣為近似低秩矩陣，并為秩最小化的矩陣。因此，引入弛豫函數(shù)進(jìn)行正則化，以實(shí)現(xiàn)矩陣的最小化秩和核范數(shù)，對(duì)一個(gè)非凸正則化重構(gòu)矩陣完備問題可描述為：

其中，;是具有的矩陣，否則;表示矩陣的Hadamard乘積。對(duì)式（12）增加較小的懲罰值并減少大值的懲罰，即對(duì)式（12）進(jìn)行秩最小化和核范數(shù)的折中處理;假設(shè)，則式（12）可重新描述為：

其中，，顯然是非凸函數(shù);為正定矩陣。

對(duì)式（13）無法直接進(jìn)行求解或優(yōu)化，在此利用迭代加權(quán)最小二乘法對(duì)式（13）進(jìn)行優(yōu)化，其算法如算法1所示。

算法1 示意代碼

Algorithm 1 Iterative Weighted Least Squares Optimization Algorithm

input：Incomplete data matrix

ouput：low rank matrix

init：initialize? by

for （i=1;i<=n1;i++）

{

Eigenvalue split：? ? ? ? （14）

Update? by：? ? ? ? ?（15）

Update? by solving：

（16）

Convergence checking.

}

算法1迭代時(shí)，用當(dāng)前加權(quán)矩陣進(jìn)行更新，而后用當(dāng)前更新的來更新。但算法1中的式（16）的求解式困難的，因此需要對(duì)其用拉格朗日函數(shù)進(jìn)行輔助，即在忽略變量的條件下，得到：

其中，為拉格朗日乘數(shù)。對(duì)式（17）進(jìn)行求導(dǎo)，并令其一階導(dǎo)數(shù)為零，即：

其中，為正定矩陣，為可逆矩陣。

由上，得到：

對(duì)任意i，有：

其中，為對(duì)角矩陣。式（20）可改寫為：

由于式（21）中，是一個(gè)奇異矩陣，導(dǎo)致式（21）的求解變得非常困難，因此由的結(jié)構(gòu)特點(diǎn)，得到：

其中，為矩陣中非零元素的子向量;是對(duì)應(yīng)的非奇異子矩陣。由此得到的最優(yōu)解可通過求解得到。因此，的最優(yōu)解即為的最優(yōu)解。

3.2? ?算法收斂性分析

算法1中，在給定完備矩陣時(shí)，其迭代步長(zhǎng)具有有界性。因在線性搜索過程中，迭代步長(zhǎng)具有單調(diào)性，使得搜索條件式（14）得到滿足，而且迭代步長(zhǎng)不會(huì)無限增長(zhǎng)，當(dāng)?shù)介L(zhǎng)增長(zhǎng)滿足：

則搜索迭代停止。

定義1：若序列存在收斂的子序列，則該子序列收斂到的點(diǎn)稱為累積點(diǎn)，其中。

定義2：若0屬于在X*處次梯度集合，則稱是式（10）中目標(biāo)函數(shù)的穩(wěn)定點(diǎn)。即：

其中，為函數(shù)在處的次梯度，且有

由上定義1和定義2可知，算法1產(chǎn)生的更新序列，使式（10）的目標(biāo)函數(shù)單調(diào)下降，且序列所有累積點(diǎn)皆為穩(wěn)定點(diǎn)。因此，算法1能夠收斂于穩(wěn)定點(diǎn)，且更新序列，為序列的任一累積點(diǎn)，則有：

即算法1的收斂速度為。

4? ?實(shí)驗(yàn)（Experiment）

4.1? ?實(shí)驗(yàn)數(shù)據(jù)采集

使用深圳億道電子技術(shù)有限公司的物聯(lián)網(wǎng)數(shù)據(jù)采集系統(tǒng)，如圖1所示。

圖1 實(shí)驗(yàn)數(shù)據(jù)采集系統(tǒng)

Fig.1 Experimental data acquisition system

實(shí)驗(yàn)時(shí)，還需要建立實(shí)驗(yàn)采集系統(tǒng)軟件，如圖2所示，按照客戶端、服務(wù)端和PC端來進(jìn)行構(gòu)建。所采集的數(shù)據(jù)有大氣壓、溫度、光照和火災(zāi)，運(yùn)行一段時(shí)間，采集到的數(shù)據(jù)如表1所示，每個(gè)感知數(shù)據(jù)的單位分別為帕斯卡、攝氏度、勒克斯和百萬分之一（parts per million，ppm）。其中火災(zāi)傳感器采用紫外感知CO/CO2的綜合濃度。實(shí)驗(yàn)共采集50000次數(shù)據(jù)，由于篇幅限制，表1中僅給出10次。

圖2 數(shù)據(jù)采集處理流程

Fig.2 Data acquisition process flow

4.2? ?數(shù)據(jù)處理

對(duì)上述感知到的數(shù)據(jù)進(jìn)行初步處理，然后用s.dat存儲(chǔ)。對(duì)s.dat里面的數(shù)據(jù)進(jìn)行處理，劃分為訓(xùn)練集sa.dat和測(cè)試集sat.dat。設(shè)表示s.dat中數(shù)據(jù)構(gòu)成的不完整矩陣，并用表示s.dat中包含的所有可用數(shù)據(jù)的索引集。因此，和是的矩陣，每個(gè)。又設(shè)、分別描述訓(xùn)練和測(cè)試時(shí)不相交的數(shù)據(jù)集，且存在。

矩陣數(shù)據(jù)處理時(shí)，使用訓(xùn)練數(shù)據(jù)集作為矩陣完備輸入算法1中，代替算法1的，由此用未得到的估計(jì)測(cè)試數(shù)據(jù)集，并將其存儲(chǔ)于。對(duì)算法1，對(duì)少量數(shù)據(jù)進(jìn)行調(diào)整，以便于對(duì)誤差進(jìn)行度量，故使用訓(xùn)練集和測(cè)試集上的歸一化平均絕對(duì)誤差（Normalized Mean Absolute Error，Nmae）進(jìn)行數(shù)據(jù)的評(píng)判。

定義3若給定矩陣為矩陣完備，則定義訓(xùn)練矩陣和測(cè)試矩陣的Nmae分別為：

由定義3和矩陣的數(shù)據(jù)，在inteli76700處理器上，運(yùn)行Apachespark模擬軟件進(jìn)行數(shù)據(jù)處理，并用文獻(xiàn)[7]、[8]的算法對(duì)矩陣的數(shù)據(jù)進(jìn)行處理，得到正則化處理比較曲線，如圖3所示。

圖3 數(shù)據(jù)處理參數(shù)正則化曲線

Fig.3 Data processing parameter regularization curve

圖4 矩陣的數(shù)據(jù)處理Nmae和運(yùn)行時(shí)間比較曲線

Fig.4 Matrix? data processing Nmae and runtime?comparison curve

由圖3可知，運(yùn)行同樣字節(jié)數(shù)的矩陣M中的數(shù)據(jù)，在訓(xùn)練時(shí)返回的正則化矩陣的秩如圖3（a）所示，由此可知，本文算法返回的秩較參比算法低;同樣，圖3（b）可知，在訓(xùn)練時(shí)和測(cè)試時(shí)進(jìn)行正則化，得到的Nmae值，本文算法曲線變化比較平緩，僅開始隨曲線變化較為陡峭，在矩陣M中的數(shù)據(jù)量達(dá)到5kB后，較參比算法而言，其變化趨勢(shì)較為平緩穩(wěn)定。由圖4（a）可知，在訓(xùn)練時(shí)，隨著矩陣M正則化得到的秩的增加，本文算法的Nmae變化趨近于線性，較參比算法而言，變化趨勢(shì)較為平緩穩(wěn)定。在測(cè)試時(shí)，隨著秩的增加，本文算法得到的Nmae值在呈現(xiàn)下降趨勢(shì)，其趨勢(shì)接近于線性，而參比算法則波動(dòng)較大。同樣，由圖4（b）可知，本文算法隨著秩的增加，其運(yùn)行時(shí)間增加比較平緩光滑，而參比算法無論在訓(xùn)練時(shí)還是測(cè)試時(shí)，其運(yùn)行時(shí)間波動(dòng)較大。

由上實(shí)驗(yàn)可知，本文提出的算法，無論時(shí)在訓(xùn)練時(shí)還是測(cè)試時(shí)，其Nmae值和運(yùn)行時(shí)間，都具有較平穩(wěn)的特性，且可近似于線性。

5? ?結(jié)論（Conclusion）

在大數(shù)據(jù)處理中存在的優(yōu)化問題，提出一種基于凸和非凸優(yōu)化低秩矩估計(jì)的大數(shù)據(jù)處理算法，并利用物聯(lián)網(wǎng)采集與感知的大數(shù)據(jù)進(jìn)行算法的實(shí)驗(yàn)驗(yàn)證與對(duì)比分析。在簡(jiǎn)單描述凸優(yōu)化、非凸優(yōu)化和低秩矩陣優(yōu)化基礎(chǔ)上，設(shè)計(jì)了基于凸和非凸優(yōu)化低秩矩估計(jì)的大數(shù)據(jù)處理算法，并對(duì)算法收斂性進(jìn)行了分析;然后利用物聯(lián)網(wǎng)感知設(shè)備，進(jìn)行數(shù)據(jù)感知與采集，然后利用所設(shè)計(jì)的算法進(jìn)行對(duì)比實(shí)驗(yàn)。通過實(shí)驗(yàn)表明，本文算法在訓(xùn)練時(shí)和測(cè)試時(shí)，在歸一化平均絕對(duì)誤差和運(yùn)行時(shí)間上，具有較好的結(jié)果。

參考文獻(xiàn)（References）

[1] Ding Jie，Wen Changyun，Li Guoqi，et al.Key Nodes Selection in Controlling Complex Networks via Convex Optimization[J].IEEE Transactions on Cybernetics，2019，PP（99）：1-12.10.1109/TCYB.2018.2888953.

[2] Arantes M D S，Toledo C F M，Williams B C，et al.Collision-Free Encoding for Chance-Constrained Nonconvex Path Planning[J].IEEE Transactions on Robotics，2019，35（2）：433-448.

[3] Zhu Zhihui，Li Qiuwei，Tang Gongguo，et al.Global Optimality in Low-rank Matrix Optimization[J].IEEE Transactions on Signal Processing，2018，66（13）：3614-3628.

[4] Hatamirad S，Pedram M M.Low-rank approximation of large-scale matrices via randomized methods[J].The Journal of Supercomputing，2018（74）830-844.

[5] 孫夢(mèng)璐，唐起超.基于低秩矩陣完備的大規(guī)模MIMO系統(tǒng)信道估計(jì)研究[J].計(jì)算機(jī)應(yīng)用研究，2018，35（6）：247-250.

[6] Yudong C，Yuejie C.Harnessing Structures in Big Data via Guaranteed Low-Rank Matrix Estimation： Recent Theory and Fast Algorithms via Convex and Nonconvex Optimization[J].IEEE Signal Processing Magazine，2018，35（4）：14-31.

[7] NieFeiping，Hu Zhanxuan，Li Xuelong.Matrix Completion Based on Non-convex Low Rank Approximation[J].IEEE Transactions on Image Processing，2019，28（5）：2378-2388.

[8] Oh T H，Matsushita Y，Tai Y W，et al.Fast Randomized Singular Value Thresholding for Low-rank Optimization[J].IEEE Transactions on Pattern Analysis & Machine Intelligence，2015（99）：376-391.

作者簡(jiǎn)介：

劉曉霞（1976-），女，碩士，副教授.研究領(lǐng)域：大數(shù)據(jù)處理與應(yīng)用，物聯(lián)網(wǎng)技術(shù).

王鈺寧（1982-），女，本科，講師.研究領(lǐng)域：大數(shù)據(jù).

陳? ?霞（1971-），女，本科，副教授.高級(jí)工程師.研究領(lǐng)域：土木工程材料，施工應(yīng)用，計(jì)算機(jī)技術(shù)應(yīng)用.