基于缺失信號的圖重構(gòu)

韓詩期 王俊義,2 李 然

1(桂林電子科技大學(xué)信息與通信學(xué)院 廣西 桂林 541004)2(“認(rèn)知無線電與信號處理”教育部重點(diǎn)實(shí)驗(yàn)室 廣西 桂林 541004)3(西安電子科技大學(xué)通信工程學(xué)院 陜西 西安 710071)

0 引 言

如何處理不規(guī)則域中的數(shù)據(jù)已經(jīng)成為信號處理領(lǐng)域中的研究熱門。這些數(shù)據(jù)通常具有維度高、空間結(jié)構(gòu)復(fù)雜的特點(diǎn)。由于極少考慮數(shù)據(jù)自身的空間結(jié)構(gòu)和數(shù)據(jù)之間的交互，經(jīng)典數(shù)字信號處理(Digital Signal Processing，DSP)方法在處理這類數(shù)據(jù)已經(jīng)暴露出自身的局限性。處理不規(guī)則結(jié)構(gòu)化數(shù)據(jù)的需求催生了圖信號處理[1-2](Graph Signal Processing，GSP)。在GSP中，信號的空間結(jié)構(gòu)用由頂點(diǎn)和邊組成的圖來表示。圖的頂點(diǎn)表示實(shí)際結(jié)構(gòu)中的實(shí)體，邊權(quán)重表示頂點(diǎn)之間的關(guān)系。定義在頂點(diǎn)上的標(biāo)量值就是圖信號，對應(yīng)于實(shí)際網(wǎng)絡(luò)中的觀測值。當(dāng)前GSP領(lǐng)域的主要研究課題包括圖學(xué)習(xí)(Graph Learning)[3]、圖信號采樣[4]、圖信號重構(gòu)[5]、圖信號降噪及濾波[6]等。GSP在許多具體任務(wù)中也取得顯著進(jìn)展，如特征提取[7]、圖像處理[8]、視頻編碼[9]、聚類[10]和大數(shù)據(jù)分析[11]等。

許多基于圖的方法都假設(shè)圖是已知的或者可根據(jù)實(shí)際應(yīng)用場景進(jìn)行定義的，但是這些圖未必能真實(shí)反映數(shù)據(jù)的空間結(jié)構(gòu)。而且對于許多數(shù)據(jù)而言，圖并非都是已知的。此外，傳統(tǒng)的圖學(xué)習(xí)方法通常都是在信號完備的情況下進(jìn)行，而在實(shí)際應(yīng)用中信號丟失的現(xiàn)象時(shí)有發(fā)生。因此，有必要對缺失信號的圖學(xué)習(xí)進(jìn)行探究。使用缺失信號進(jìn)行圖學(xué)習(xí)需要考慮兩個(gè)方面：1) 使用缺失信號學(xué)習(xí)圖，2) 利用學(xué)到的圖進(jìn)行信號重構(gòu)。每次迭代重構(gòu)的信號都作為下一次學(xué)習(xí)圖的輸入。由于信號缺失，有必要對信號進(jìn)行進(jìn)一步約束，降低重構(gòu)誤差，再反哺到圖學(xué)習(xí)中。傳統(tǒng)涉及到信號重構(gòu)的圖學(xué)習(xí)中僅考慮了圖信號的空間光滑性。而在實(shí)際場景中，存在同時(shí)滿足空間光滑性和時(shí)間光滑性的信號。一個(gè)直觀的例子是溫度傳感器網(wǎng)絡(luò)，相鄰傳感器所采集到的溫度較為相似，同一傳感器在相鄰時(shí)刻采集到的溫度通較為相似。因此本文的創(chuàng)新性在于利用了圖信號在時(shí)間上的光滑性對圖學(xué)習(xí)中涉及到的信號重構(gòu)問題進(jìn)行修正。本文同時(shí)在合成數(shù)據(jù)和美國國家海洋和大氣管理局(National Oceanic and Atmospheric Administration，NOAA)官網(wǎng)溫度數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，結(jié)果表明在信號缺失的情況下，本文的圖學(xué)習(xí)模型依然能合理推測信號的空間結(jié)構(gòu)并進(jìn)行信號重構(gòu)。

1 相關(guān)工作

高斯圖模型是十分經(jīng)典的圖學(xué)習(xí)模型。高斯圖模型學(xué)習(xí)的是變量的精度矩陣，即協(xié)方差矩陣的逆矩陣，因此也可以將其稱為協(xié)方差選擇問題。Dempster[12]為了能得到正態(tài)總體的稀疏結(jié)構(gòu)，將精度矩陣中最小的值直接置零。而后，利用1罰函數(shù)實(shí)現(xiàn)稀疏學(xué)習(xí)的圖Lasso[13]成為了概率圖問題中廣泛使用的稀疏化學(xué)習(xí)模型。

GSP的發(fā)展為圖學(xué)習(xí)提供了新的思路。基于GSP的圖學(xué)習(xí)方法通常先建立圖信號的表示模型，再結(jié)合圖的稀疏性對模型進(jìn)行優(yōu)化。文獻(xiàn)[14]就信號處理的角度對圖學(xué)習(xí)進(jìn)行詳細(xì)的闡述，將GSP的圖學(xué)習(xí)問題分為三類，分別是基于光滑信號[15-16]、譜濾波器[17-18]和圖上因果關(guān)系[19-20]的圖學(xué)習(xí)問題?；谛盘柟饣缘膱D學(xué)習(xí)問題的前提條件是信號在相連的頂點(diǎn)上緩慢地變化。文獻(xiàn)[15]假設(shè)頂點(diǎn)度之和等于頂點(diǎn)數(shù)，借助因子分析法，從圖信號表示的角度構(gòu)建了高斯圖模型。文獻(xiàn)[16]提出了一種新的模型，通過對數(shù)函數(shù)除去了Dong對于頂點(diǎn)度的約束，并使用原始對偶算法對模型進(jìn)行求解，提升了計(jì)算效率。文獻(xiàn)[17-18]學(xué)習(xí)的是平穩(wěn)圖信號的底層結(jié)構(gòu)，濾波器是圖移位算子的高次冪，并用圖移位算子表示圖。圖信號的經(jīng)驗(yàn)方差就是圖濾波器的特征向量，再對濾波器特征值矩陣降冪、恢復(fù)特征值符號，最終得到圖移位算子。文獻(xiàn)[19]借助稀疏向量自回歸(Sparse Vector Autoregressive，SVAR)模型表示圖上的因果過程。文獻(xiàn)[20]使用結(jié)構(gòu)化方程模型(Structural Equation Model，SEM)表示信號變化過程。

信號重構(gòu)也廣泛使用了基于圖的方法，包括帯限信號重構(gòu)[5，21]、低秩信號重構(gòu)[22]和時(shí)變信號重構(gòu)[23-24]等。許多圖信號重構(gòu)的方法都充分利用了信號在空間圖上的光滑性。為降低信號重構(gòu)誤差，部分研究者開始考慮同時(shí)利用信號空間和時(shí)間兩個(gè)維度的信息。文獻(xiàn)[25]在進(jìn)行矩陣填充時(shí)根據(jù)矩陣的行和列構(gòu)造了行圖和列圖，同時(shí)利用了信號矩陣行和列的光滑性。文獻(xiàn)[26-27]則提出了聯(lián)合圖傅里葉變換，其中根據(jù)信號矩陣的列向量構(gòu)成的圖就是頂點(diǎn)圖或空間圖，根據(jù)行向量構(gòu)造的圖就是時(shí)間圖，并證明了聯(lián)合圖就是空間圖和時(shí)間圖的笛卡爾積。實(shí)際上存在涉及到信號重構(gòu)的圖學(xué)習(xí)問題[15，20]，其中的保真項(xiàng)可以看作是采樣率為1時(shí)的聯(lián)合圖學(xué)習(xí)和信號重構(gòu)問題。

2 圖學(xué)習(xí)模型

2.1 基本概念

文獻(xiàn)[27]提出聯(lián)合圖傅里葉變換(Joint Time-Vertex Transform，JFT)就是分別對信號矩陣的列向量做GFT，對行向量做DFT，聯(lián)合圖就是時(shí)間圖和空間圖的笛卡爾積，即直積。假設(shè)存在信號矩陣X=[x0,x1,…,xT-1]∈RN×T，空時(shí)圖的組合拉普拉斯矩陣L和JFT分別定義為:

L=L?L=L?IN+IT?L=

(1)

(2)

vec(X)TLvec(X)=tr(XTLX)+tr(XLXT)

(3)

顯然，圖信號的空間光滑性和時(shí)間光滑性是相互獨(dú)立的。衡量信號在聯(lián)合圖L上的光滑性就是分別衡量其在空間圖L和時(shí)間圖L上的光滑性。

2.2 缺失信號的圖學(xué)習(xí)模型

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

ht關(guān)于yt的條件分布滿足:

p(ht|yt)∝p(yt|ht)p(ht)

(12)

因此ht關(guān)于yt的最大后驗(yàn)估計(jì)為：

(13)

(14)

其矩陣形式為:

(15)

式中：Y=[y0,y2,…,yT-1]∈RN×T為觀測值，即缺失信號，N為頂點(diǎn)數(shù)，T為時(shí)間序列長度。X∈RN×T為待恢復(fù)的信號。J∈RN×T為采樣矩陣，Jij∈{0,1}，i=1，2,…，N，j=0，1,…，T-1。式(3)表明空間變分與時(shí)間變分是可分離的，再考慮圖的稀疏性和信號的時(shí)間變分，式(15)可以進(jìn)一步寫為：

(16)

2.3 模型求解

為保證解的有效性，有必要向式(16)中的目標(biāo)函數(shù)添加約束條件，最終需要求解的目標(biāo)函數(shù)為:

(17)

(18)

圖信號重構(gòu)問題為:

(19)

可以將全部求解過程概括為算法1。

算法1模型求解

輸入：Y，J，α，β，γ，迭代次數(shù)，容許誤差。

1.初始化：X0=Y，k=1

2.重復(fù)

5.3)k=k+1

(20)

式(20)中目標(biāo)函數(shù)的梯度和Hessian矩陣可得：

2.3.2信號重構(gòu)

信號重構(gòu)的目標(biāo)函數(shù)為:

(21)

vec(Y-J°X)Tvec(Y-J°X)+

vec(Y-X)TQvec(Y-X)+

(22)

Hessian是半正定矩陣，矩陣因此信號重構(gòu)問題是無約束凸優(yōu)化問題。

(23)

(24)

共軛梯度法見算法2。

算法2共軛梯度法

輸出：重構(gòu)的圖信號Xm。

1.初始化：X0=0N×T，ΔX0=0N×T，m=0

2.重復(fù)

3.1) 根據(jù)式(24)選擇合適的更新步長τ

4.2) 共軛梯度方向更新步驟

5.Xm+1=Xm+τΔXm

8.m=m+1

9：‖ΔXm‖F(xiàn)≤δ或到達(dá)最大迭代次數(shù)時(shí)停止

3 實(shí)驗(yàn)結(jié)果分析

3.1 合成數(shù)據(jù)

表1 不同采樣率圖信號的圖學(xué)習(xí)效果

表2 本文圖學(xué)習(xí)模型和已知圖的信號重構(gòu)效果對比

3.2 實(shí)測溫度數(shù)據(jù)

對于實(shí)測數(shù)據(jù)，由于原圖未知而無法直接進(jìn)行對比。拉普拉斯矩陣的一個(gè)重要應(yīng)用就是譜聚類，所以可以根據(jù)譜聚類性能來間接判斷所學(xué)習(xí)拉普拉斯矩陣的好壞。評價(jià)聚類性能使用的指標(biāo)包括蘭德系數(shù)(Rand Index，RI)、純度(Purity)和NMI，上述三項(xiàng)指標(biāo)值越大，譜聚類性能越好。聚類效果越好，說明學(xué)到的圖越準(zhǔn)確。由于是在信號缺失的情況下進(jìn)行圖學(xué)習(xí)，因此評價(jià)模型性能還需要考慮圖信號重構(gòu)誤差。當(dāng)聚類性能越優(yōu)越，圖信號重構(gòu)MAE越低，模型性能越好。

本文所使用的溫度數(shù)據(jù)來自于NOAA官網(wǎng)，采集了中國大陸60個(gè)不同地區(qū)氣象站在2018年1月至8月共243天的日均溫，信號矩陣大小為60×243。由于溫度在時(shí)域上是均勻采樣，所以可以認(rèn)為溫度在時(shí)域內(nèi)是光滑信號，因此可以使用時(shí)間變分法的約束。同時(shí)，相鄰氣象站之間采集到的溫度更為接近，因此該數(shù)據(jù)集同樣滿足空間光滑性，也可以將其看作是在傳感器個(gè)數(shù)為60的溫度傳感器網(wǎng)絡(luò)以相等時(shí)間間隔采集了243次數(shù)據(jù)。在進(jìn)行實(shí)驗(yàn)前根據(jù)氣象站所在的氣候帶對其進(jìn)行標(biāo)簽分類。所涉及的氣候帶包括溫帶大陸性氣候、高原山地氣候、溫帶季風(fēng)氣候和亞熱帶季風(fēng)氣候，因此將樣本簇的個(gè)數(shù)定為4，不同氣候帶上的氣象站個(gè)數(shù)均為15。

一種重構(gòu)無線溫度傳感器網(wǎng)絡(luò)信號的方法是根據(jù)傳感器坐標(biāo)選擇合適的k值構(gòu)造kNN圖，再利用kNN圖進(jìn)行圖信號重構(gòu)[24]。文章利用氣象站坐標(biāo)分別構(gòu)造了k=2，3，5，8時(shí)的kNN圖，并給出了不同kNN圖和本文圖學(xué)習(xí)模型對氣象站進(jìn)行譜聚類與圖信號重構(gòu)結(jié)果進(jìn)行對比，見圖1。如圖1至圖3所示，對于kNN圖而言，k=2時(shí)的聚類效果最好，RI、Purity和NMI值均最高。在采樣率不低于0.5時(shí)，圖學(xué)習(xí)模型譜聚類各項(xiàng)指標(biāo)基本達(dá)到k=2時(shí)kNN圖的效果。隨著采樣率的增加，圖學(xué)習(xí)的方法各項(xiàng)性能指標(biāo)逐漸優(yōu)于k=2時(shí)的kNN圖。其中圖學(xué)習(xí)模型的RI值和NMI值略優(yōu)于kNN圖，而Purity值遠(yuǎn)勝于kNN圖。從圖4可以看出，圖學(xué)習(xí)模型的信號重構(gòu)MAE值最小，效果最佳?？梢哉J(rèn)為在信號缺失時(shí)，本文圖學(xué)習(xí)模型學(xué)到的圖比kNN圖更客觀地反映了不同位置氣象站之間的關(guān)系。

圖1 RI值

圖2 Purity值

圖3 NMI值

圖4 MAE值

4 結(jié) 語

本文構(gòu)造了缺失信號的圖學(xué)習(xí)模型，同時(shí)利用信號的時(shí)間變分和空間變分對信號進(jìn)行重構(gòu)，并通過數(shù)值實(shí)驗(yàn)證明了在信號殘缺的情況下，本文的圖學(xué)習(xí)模型依然能夠合理地學(xué)習(xí)數(shù)據(jù)的空間結(jié)構(gòu)，圖信號重構(gòu)效果也略優(yōu)于直接構(gòu)造圖的方法。下一步的研究可以分為兩部分：一是開發(fā)適用于大規(guī)模圖的圖學(xué)習(xí)算法；二是將缺失信號圖學(xué)習(xí)模型應(yīng)用到實(shí)際場景中，如信號重構(gòu)、數(shù)據(jù)異常檢測等。