基于凸和非凸優化低秩矩估計的大數據處理算法

劉曉霞 王鈺寧 陳 霞

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

關鍵詞：凸優化;非凸優化;低秩矩陣;估計;大數據處理

中圖分類號：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）

各類數據信息形成的大規模高維數據正在以每年ZB（Zetta Byte，ZB）級海量遞增，為處理和存儲帶來巨大的機遇和嚴峻的挑戰。而各種數據的采集與處理過程中，幾乎都是高維數據且相互關聯，需要進行數據優化。而凸優化由于其在凸集、凸函數的結構和特性，具有不確定性，已應用于信號處理、生物信息學、機器學習和大數據等。

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

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

2? ?相關優化方法（Related optimization method）

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

2.1? ?凸優化和非凸優化

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

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

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

且為定義在（為凸集）上的凸函數，則該優化問題稱為凸優化。

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

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

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

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

且為定義在（為非凸集）上的非凸函數，則該優化問題稱為非凸優化。

2.2? ?低秩矩陣優化

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

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

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

因此，低秩矩陣優化問題可形式化描述為：

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

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

3? ?大數據處理算法（Big data processing algorithm）

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

3.1? ?算法設計

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

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

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

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

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

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

對式（13）無法直接進行求解或優化，在此利用迭代加權最小二乘法對式（13）進行優化，其算法如算法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）的求解式困難的，因此需要對其用拉格朗日函數進行輔助，即在忽略變量的條件下，得到：

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

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

由上，得到：

對任意i，有：

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

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

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

3.2? ?算法收斂性分析

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

則搜索迭代停止。

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

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

其中，為函數在處的次梯度，且有

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

即算法1的收斂速度為。

4? ?實驗（Experiment）

4.1? ?實驗數據采集

使用深圳億道電子技術有限公司的物聯網數據采集系統，如圖1所示。

圖1 實驗數據采集系統

Fig.1 Experimental data acquisition system

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

圖2 數據采集處理流程

Fig.2 Data acquisition process flow

4.2? ?數據處理

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

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

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

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

圖3 數據處理參數正則化曲線

Fig.3 Data processing parameter regularization curve

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

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

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

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

5? ?結論（Conclusion）

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

參考文獻（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] 孫夢璐，唐起超.基于低秩矩陣完備的大規模MIMO系統信道估計研究[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-），女，碩士，副教授.研究領域：大數據處理與應用，物聯網技術.

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

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