劉曉霞 王鈺寧 陳 霞

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

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

中圖分類號：TP309? ? ?文獻標識碼：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ù)據信息形成的大規(guī)模高維數(shù)據正在以每年ZB（Zetta Byte，ZB）級海量遞增，為處理和存儲帶來巨大的機遇和嚴峻的挑戰(zhàn)。而各種數(shù)據的采集與處理過程中，幾乎都是高維數(shù)據且相互關聯(lián)，需要進行數(shù)據優(yōu)化。而凸優(yōu)化由于其在凸集、凸函數(shù)的結構和特性，具有不確定性，已應用于信號處理、生物信息學、機器學習和大數(shù)據等。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

對秩為的矩陣進行奇異值分解，可描述為：

其中，為對應的奇異值和奇異向量。由此，低秩矩陣的集合可描述為：

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

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

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

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

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

3.1? ?算法設計

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

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

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

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

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

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

對式（13）無法直接進行求解或優(yōu)化，在此利用迭代加權最小二乘法對式（13）進行優(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迭代時，用當前加權矩陣進行更新，而后用當前更新的來更新。但算法1中的式（16）的求解式困難的，因此需要對其用拉格朗日函數(shù)進行輔助，即在忽略變量的條件下，得到：

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

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

由上，得到：

對任意i，有：

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

由于式（21）中，是一個奇異矩陣，導致式（21）的求解變得非常困難，因此由的結構特點，得到：

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

3.2? ?算法收斂性分析

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

則搜索迭代停止。

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

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

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

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

即算法1的收斂速度為。

4? ?實驗（Experiment）

4.1? ?實驗數(shù)據采集

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

圖1 實驗數(shù)據采集系統(tǒng)

Fig.1 Experimental data acquisition system

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

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

Fig.2 Data acquisition process flow

4.2? ?數(shù)據處理

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

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

定義3若給定矩陣為矩陣完備，則定義訓練矩陣和測試矩陣的Nmae分別為：

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

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

Fig.3 Data processing parameter regularization curve

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

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

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

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

5? ?結論（Conclusion）

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

參考文獻（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] 孫夢璐，唐起超.基于低秩矩陣完備的大規(guī)模MIMO系統(tǒng)信道估計研究[J].計算機應用研究，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.

作者簡介：

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

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

陳? ?霞（1971-），女，本科，副教授.高級工程師.研究領域：土木工程材料，施工應用，計算機技術應用.