基于快速上下文感知张量分解的噪声推断方法

2017-12-29 21:43王辉
科技视界 2017年26期

王辉

【摘 要】针对目前基于张量分解的噪声推断算法中对于数据本身特征信息考虑不足使得分解速度不够快的问题,提出一种引入平滑约束的上下文感知张量分解方法—基于快速上下文感知张量分解的噪声推断算法(F-CATD)。该方法为了加快分解过程将平滑约束与上下文感知张量分解方法相结合,在张量分解成低维矩阵过程中做近似处理。实验结果表明,该算法与基于上下文感知张量分解的噪声推断算法(CATD)相比,推断填补噪声张量模型中缺失数据的均方根误差几乎相同,运行时间减小了近4倍。该算法能够有效地进行噪声推断。

【关键词】城市噪声;张量分解;平滑约束;推断填补

中图分类号: TP391.3 文献标识码: A 文章编号: 2095-2457(2017)26-0050-002

A Noise Inference Method Based on Fast Context-aware Tensor Factorizations

WANG Hui

(Xuzhou Medical University ,Xuzhou Jiangsu 221004,China)

【Abstract】Existing noise inference algorithms based on tensor decomposition neglected noise data has the character of smooth, which results in a slower rate of noise inference. Aiming to the problem, we present a noise inference algorithm based on fast context-aware tensor decomposition F-CATD. F-CATD is improved based on context-aware tensor decomposition algorithm. It combines smoothness constraint with context-aware tensor decomposition to do approximation when tensor is decomposed into low-dimensional matrix to speed up the process of decomposition. Finally, we conduct experiments on real urban noise data to demonstrate the advantages of the proposed noise inference algorithm.

【Key words】Urban noises; Tensor factorizations; Smoothness constraint; Data filling

0 引言

当今城市化的飞速发展带来了城市的噪声污染问题[1],对于城市噪声情况及分布成为当前研究的一个热点。一些国家已经开始监测噪声污染,它们通常使用基于诸如交通流量数据的噪声地图来评估噪声污染水平。但是这样的输入数据收集是非常昂贵的,随后Luca等人[2]提出了通过部署无线传感器网络监控噪声污染,但在大型城市空间部署专用的传感器网络实际测量成本也是很昂贵的。近年来,噪声测量移动终端设备有了较大的发展,NoiseTube[3]和Ear-phone[4]是两款比较受欢迎的用于监测噪音污染应用软件产品。然而,由于城市噪声通常是多个声源的混合物,即使可以随处部署声音传感器,诊断完全基于传感器数据的城市噪声污染是不彻底的。分析噪声的组成是解决噪声污染的关键。

为了解决这一问题,郑宇等人[5]提出了基于上下文感知的张量分解噪声推断方法(CATD)。CATD结合纽约市311投诉数据[6]与社会媒体,路网数据,兴趣点数据,通过上下文感知的张量分解方法补充缺失数据,以此推断全市各区域的噪声情况(包含噪声污染的指标和噪声的组成)。

然而,此方法在噪声推断过程中对于数据本身平滑性特征信息考虑不足降低了分解速度,针对此问题本文提出基于快速上下文感知张量分解的噪声推断算法(F-CATD)。将平滑约束与上下文感知张量分解方法相结合,在张量分解成低维矩阵过程中做近似处理以加快分解过程。

1 噪声推断

1.1 噪声张量模型构建

为表示城市中每个地区的噪声情况使用一个张量来构建城市噪声模型,Y∈RN×M×L三维分别表示N个区域,M种噪声种类,L个时间节点。

地区维:第一维表示划分后的各地区r=[r1,r2…ri…rN]。

时间段维:将一天等分成相同的时间段,每个时间段表示一段时期。t=[t1,t2…tk…tL]结果是在时间维度上的时隙数目是固定的。

噪声种类维:这一维度表示c=[c1,c2…cj…cM]噪声的种类。各项元素:元素Y(i,j,k)存储在时间节点tk地区ri的噪声种类为cj的311数据投诉的数目。

填补张量中的缺失数据方法是基于张量Y的非零项将张量Y分解成几个低秩的矩阵和一个核心张量。使用塔克分解模型[7]将Y分解成一个核心张量G∈R 和三个矩阵,R∈R ,C∈R ,T∈R 。目标函数为公式1:

其中‖.‖2表示欧几里得距离,第一部分控制分解的误差,第二部分为正规惩罚部分控制过度拟合。使目标函数最小化可以得到最優化的R,C,T。最后可以通过公式2恢复张量Y中的缺失数据:

公式中的×表示矩阵相乘;×k表示张量矩阵相乘,其中下标k表示张量的模为k。每一项Yre的值表示噪声污染的指标即在某个地区某个时间段内的某种噪声的投诉数目。通过Yre可以获得地区ri时间段内不同噪声种类的噪声分布情况。endprint

但是,構建的噪声张量中的数据过于稀疏。例如,如果设定1小时为时隙,构建的张量中只有5.18%的项具有值。只根据其自身的非零项分解Y是不够准确的。因此,寻求加入其他信息源。为了应对数据稀疏的问题,引入三种相关数据信息特征,从POI/道路网数据、用户签到、311的数据中提取地域特征,人才流动的特征和噪声类型相关的特征(由矩阵X,D和Z表示)。这些特征在分解过程用作上下文来减少推断误差。

1.2 上下文感知张量分解

为了获得更高的填补张量Y中缺失项准确率,分解张量Y时与特征矩阵X,D,Z协作。可以分解成两个矩阵的乘法,X=R×U,其中R∈R 和U∈R 分别为地区和地理特征低秩的潜在因素。同样地,矩阵D可以分解成两个矩阵乘法的,D=T×RT,其中T∈R 是时隙低秩的潜在因子矩阵。目标函数定义为公式3:

其中(‖X-RU‖2)控制X分解的误差; tr(C L C)控制噪声种类之间的相似度;(‖D-TRT‖2)控制D分解的误差;λ1,λ2,λ3,λ4是在协同分解的过程中控制各部分的贡献参数。最后可以通过公式2恢复张量Y中的缺失数据。然而,此方法忽略了噪声数据在相邻时间段或区域是具有平滑性的,降低了分解速度。

1.3 快速上下文感知张量分解

平滑是指在某些域中相邻值之间的差异是很小的。考虑到平滑特性本文将高斯径向基函数(GRBF-NTD)[8]引入到上下文感知张量分解算法中,在张量分解成低维矩阵过程中做近似处理以提高算法的性能。目标函数定义为公式4:

其中W是一个非负矩阵,矩阵Φ的元素使用GRBF和一个标准差σ表示成公式5:

其中σ是表示高斯函数带宽的折衷参数,Δt表示时间段。F-CATD算法描述如下:

输入:噪声张量Y,矩阵X,矩阵D,矩阵Z,平滑约束矩阵Φ,核张量G的大小为R1,R2,R3。误差阈值ε。

输出:矩阵R,C,T,核张量G

由于对目标函数F没有固定的解析方法,本文采用梯度下降方法求解。引入GRBF-NTD方法目的是用ΦW近似代替R。而其中最关键的问题是W的更新。步骤6-14是W的更新过程,[x]+=max(x,ε),ε很小(ε=10-16通常),和表示元素乘法和元素除法,?茚表示克罗内克积。步骤15-20通过梯度下降求解目标矩阵R,C,T,G。最后通过公式2推测填充张量中的缺失项。使用F-CATD方法可以加速噪声推断过程。

2 实验及分析

为了测试F-CATD的性能,进行实验验证。实验硬件环境为:CPU为四核Core i5 2.3GHz,内存为4GB。

2.1 实验数据

本文采用的数据集共有四个数据源:311 nosie data、Road Networks、Check-ins、POIs数据。

2.2 实验分析

评价本文的基于平滑数据的上下文感知张量分解模型实验方法,我们随机从张量中移除一部分(20%,30%,40%)的非零项作为测试数据,随后使用本文的实验方法模型对张量中的移除缺失项进行填补。最后,使用这些项的原始值作为基础事实来衡量推断值。

评价指标:均方根误差(Root Mean Square Error,RMSE)。

定义6均方根误差。RMSE可以计算为以下公式:

从图1中可以看出,在参数lambda为0.00001时,当张量中的非零项为60%和70%(移除张量中40%和30%的非零项作为测试数据)时两种方法得到的RMSE结果几乎相同,张量中的非零项为80%时本文的RMSE略小于CATD。

从图2可以看出,在参数lambda为0.00001时,两种方法法所消耗的时间相差很大。本文的方法耗时在50s左右,CATD耗时在200s到250s之间,整体来说,在时间方面F-CATD方法加快了4-5倍,大大提升了算法的性能。

3 结语

本文针对目前基于稀疏噪声数据的张量分解算法中数据本身特征考虑不足的问题,提出一种基于快速上下文感知张量分解的噪声推断方法。该方法在上下文感知张量分解方法的基础上,考虑到噪声数据具有平滑性,引入平滑约束。实验表明,本文方法在噪声张量模型中有效地进行缺失噪声数据的填补同时大大减小了的时间消耗。

【参考文献】

[1]W.Phil, “European Commission Green Paper on Future Noice Policy,” com (96) 540 final, 04 Nov. 1996.

[2]L. Filipponi S. Santini and A. Vitaletti, “Data Collection in Wireless Sensor Networks for Noise Pollution Monitoring,” Proc. 2008 IEEE Int. Conf. on Distributed Computing in Sensor Systems(DCOSS) Santorini Island, Greece, pp. 11-14, June 2008.

[3]N. Maisonneuve, M. Stevens, M. E. Niessen and L. Steels, “NoiseTube: Measuring and mapping noise pollution with mobile phones,” J. Environmental Science \& Engineering, vol.2, no.6, pp.215-228, 2009.

[4]R. K. Rana, C. T. Chou, S. S. Kanhere, N. Bulusu and W. Hu, “Ear-phone: an end-to-end participatory urban noise mapping system,” Proc. 9th IEEE Int. Conf. on Information Processing in Sensor Networks(IPSN), pp. 105-116, Stockholm, Sweden, April 2010.

[5]Y. Zheng, T. Liu, Y.L. Wang, Y.M. Zhu, Y.C. Liu and E. Chang, “Diagnosing New York city's noises with ubiquitous data,” Proc. 2014 ACM Int. Conf. on Pervasive and Ubiquitous Computing (UbiComp), Seattle, US, pp.715-725, September 2014.

[6]http://research.microsoft.com/apps/pubs/?id=217236.

[7]T.G. Kolda and B.W. Bader, “Tensor decompositions and applications,” J. Siam Review, vol.51, no.3, pp.294-310, 2005.

[8]T. Yokota, R. Zdunek, A. Cichocki and Y. Yamashita, “Smooth nonnegative matrix and tensor factorizations for robust multi-way data analysis,” J. Signal Processing, vol.113, pp.234-249, 2015.endprint