文献标识码:A
文章编号: 0258-7998(2014)10-0131-03
0 引言
随着科技的发展,大规模数据的分析和处理在当今的社会生活中占据着越来越重要的地位。然而,常常因为数据保存不当或条件有限等原因导致最终得到的数据是缺失的,不完整的。为了得到完整的数据,需要对高维大规模数据的处理与分析。如何利用数据间的相关性,挖掘出主要信息[1],利用有限的信息得到完整的数据成为近年来研究的热点问题。
温度场是物质系统内部各个点上温度的集合,包含大量的数据。已有研究[2-6]介绍了用声学法测量,用不同算法拟合温度场的方法,但是关于温度场含有缺失点后的重建问题,目前的研究还比较少。本文针对含有缺失点的温度场,提出了一种基于核范数凸优化的矩阵填充理论的方法,为含有缺失点的温度场重建提供了新的思路,并与模拟的温度场进行比较,验证该方法的可行性。
1 问题建模
以二维的稳态温度场为研究对象,系统模型如图1所示。
图1中,白框代表已知的温度场的值,黑框代表未知的值。本文需要解决的问题是,如何通过已知温度场的数据构造未知的部分,从而重建整个温度场。图中的P和Q分别为二维温度场的长和宽。
2 矩阵填充理论
矩阵填充考虑的是矩阵的一部分或者大部分元素由于各种原因丢失或无法得知的情况下,如何准确地将这些元素合理地填充。该理论是由CANDES E J等人在2009年在压缩感知的基础上提出[7]。CANDES E J详细证明了待填充矩阵的特征以及在一定条件下的重建概率[8]。为了解决矩阵的填充问题,假设待填充的矩阵是冗余的,即其数据可以用一个低位的线性子空间表示[9]。矩阵填充的优化问题表示为:
其中M是观测到的含有缺失点的矩阵,X是待重建的矩阵,Ω是观测到的已知元素的下标的集合。此模型的意义在于,将空缺的元素填充后,使矩阵的结构尽可能好,即秩尽可能低。然而,这是一个NP-hard问题。由于矩阵的秩r与它非奇异值的个数相同,所以用矩阵的奇异值的和(即核范数)来近似代替矩阵的秩,于是式(1)优化为:
然而二维稳态温度场数值构成的矩阵是非稀疏的,如果直接对缺失点进行填充,不仅会花费大量的时间,而且重建出来的温度场误差很大。实验表明,温度场数值构成的矩阵通过DCT(即离散傅里叶)变换后,表现出较好的稀疏性。在DCT域下,通过矩阵填充理论,采用奇异值迭代[11]的方法对缺失点进行重构,然后再对重构后的矩阵作逆变换,最终得到完整的温度场。
3 温度场缺失值填充算法
3.1 DCT变换
DCT即离散傅里叶变换,属于正交变换,它将空间域变换到频域,把能量集中到少数几个低频系数上,高频分量占其中的比重相当小,因此将高频取出后,仍然可以使原数据保持较高的准确性,具体公式为:
DCT正变换:
3.2 SVD分解
通过SVD(奇异值分解)将一个非常复杂的矩阵用更小更简单的几个子矩阵相乘来表示,分解后的奇异值越大,表明对应的元素越重要[12]。奇异值分解描述为:
a11 … a1n
其中r为矩阵A的秩。
3.3 算法设计如下
输入:含有缺失值的矩阵EM×N,
输出:完整的矩阵X。
(1)初始化,令矩阵EM×N缺失点处的值为零,Y0=0。
(2)计算:Xk=Dτ(Yk-1),Yk=Yk-1+δkPΩ(E-Xk)。其中Dτ为收缩算子,δk为迭代步长,PΩ为投影算子。
(3)根据计算结果,若满足的最优解,则跳出;若不满足,跳到步骤(2)继续运算,L为拉格朗日函数。
(4)矩阵填充结束,得到结果为X。
上述算法中,每一次迭代都使Xk最小化,最终收敛到最优解,并且设置迭代的最大次数为N。然后根据得到的最优解,通过DCT逆变换,实现温度场的重建。
4 仿真结果及分析
4.1 仿真结果
在长P=10 m、宽Q=10 m的二维空间中,构建一个如下的模拟的典型单峰对称温度场[5]:
在温度场重建过程中各取长宽M=N=100。文中采用随机均匀去掉温度值的方式,分别对不同缺失率的温度场进行重建,重建结果用均方根误差[5]评价,仿真实验在内存为3 GB、处理器为2 GHz的计算机上进行。为了保证数据准确性,以10次结果的平均值作为实验依据。均方根误差定义为:
4.2 仿真分析
从表1中可以看出,随着缺失率的提高,均方根误差不断增大,即便在缺失率高达20%的情况下,均方根误差依然在误差较小的范围内,并且重构温度场的时间仅为3.12 s。但是从图5可以看出,此时在温度场的若干点上,误差相对较大。因此实验表明:仅在缺失率处于较低水平时,该方法能够精确快速地重构出原来的温度场。另外从表1中可以看出,当缺失率变大时,重建时间并不一定会变大,这与温度场缺失数据后形成的矩阵的自由度有关[8],矩阵自由度反映了数据的可降维性,处理后的矩阵自由度越小,重建时间和迭代次数会越小,反之亦然,因此实验结果符合矩阵填充理论。
5 结论
在大规模数据处理与分析占据着社会生活和科学研究主流的时代,如何充分利用数据间的冗余性对数据进行有效地提取成为研究的重点。本文以含有缺失点的复杂的温度场为研究对象,利用核范数凸优化的矩阵填充理论,对温度场数据进行稀疏化处理,对不同缺失率下温度场的重建进行了仿真分析,验证了该方法在低缺失率下的可行性,为研究含有缺失点的温度场的重构问题提供了新的方向。
参考文献
[1] HAN J,KAMBER M,PEI J.Data mining:concepts and techniques[M].Morgan Kaufmann,2006.
[2] TIAN F,LIU S,ZHANG C,et al.Study on reconstruction algorithm of two-dimensional temperature field based on simulation of sound propagation path[C].Electronic Measurement & Instruments, 2009.ICEMI′09.9th International Conference on.IEEE,2009:3-844-3-847.
[3] WAN X,GAO Y,WANG Y.3-D flame temperature field reconstruction with multi objective neural network[J].Chinese Optics Letters,2003,1(2):78-81.
[4] Tian Feng,Sun Xiaoping, Shao Fuqun,et al.A study on complex temperature field reconstruction algorithm based on combination of gauss functions with regularization method[J].Proceedings of the Csee,2004,24(5):041.
[5] 周献,王强,缪志农,等.基于RBF神经网络的三维温度场重建算法[J].仪表技术与传感器,2013(5):99-102.
[6] 田丰,孙小平,邵富群,等.基于高斯函数与正则化法的复杂温度场图像重建算法研究[J].中国电机工程学报,2004,24(5):212-215.
[7] 彭义刚,索津莉,戴琼海,等.从压缩传感到低秩矩阵恢复:理论与应用[J].自动化学报,2013,39(7):981-994.
[8] CAND?魬S E J,RECHT B.Exact matrix completion via convex optimization[J].Foundations of Computational mathematics,2009,9(6):717-772.
[9] 陈敏铭.矩阵重建的算法与实现[D].北京:中国科学院研究生院,2010.
[10] RECHT B.A simpler approach to matrix completion[J].The Journal of Machine Learning Research,2011(12):3413-3430.
[11] CAI J F,CAND?魬S E J,SHEN Z.A singular value thresholding algorithm for matrix completion[J].SIAM Journal on Optimization,2010,20(4):1956-1982.
[12] DE LATHAUWER L,DE MOOR B,VANDEWALLE J.A multilinear singular value decomposition[J].SIAM Journal on Matrix Analysis and Applications,2000,21(4):1253-1278.