趙金偉,劉杰東,邱萬力,黑新宏*

(1.西安理工大學(xué) 計算機科學(xué)與工程學(xué)院,陜西 西安 710048;2.網(wǎng)絡(luò)計算與安全技術(shù)陜西省重點實驗室,陜西 西安 710048)

0 引 言

對水廠管道瞬時水流量數(shù)據(jù)的合理利用和分析是構(gòu)建城市科學(xué)供水系統(tǒng)的基礎(chǔ),是城市用水生產(chǎn)調(diào)度的科學(xué)依據(jù),是解決城市用水供求關(guān)系的關(guān)鍵。然而,在瞬時水流量數(shù)據(jù)的采集、存儲、整理等階段容易引入缺失值。這將直接影響到水流量分析和預(yù)測等下游任務(wù)的準(zhǔn)確性、有效性、科學(xué)性。城市供水系統(tǒng)、水網(wǎng)系統(tǒng)的搭建也會失去來自于數(shù)據(jù)的有效參考。國內(nèi)外在時間序列數(shù)據(jù)缺失值插補問題的研究非常多,但專門針對上游任務(wù)中水流量數(shù)據(jù)連續(xù)缺失值的插補問題的研究工作相對較少。因此,急需更為有效的水流量連續(xù)缺失值的解決方案,為水流量分析與挖掘等下游任務(wù)和工業(yè)應(yīng)用提供準(zhǔn)確、完整的數(shù)據(jù)。

從數(shù)據(jù)采集的過程可知,瞬時水流量數(shù)據(jù)具有較強的時間序列特性,但同時它也與地域、人口密度、風(fēng)土人情、氣候特點有很大關(guān)系。如果只考慮時間特征,會發(fā)現(xiàn)它具有非線性和隨機波動的特點,這就為瞬時水流量缺失值的插補帶來了困難[1]。近年來,Kabir等人[2]提出用單一均值插補、多重插補等方法插補水流量數(shù)據(jù)中的缺失值。王志良等人[3]提出采用各種時間序列插補方法對水文站流量缺失數(shù)據(jù)進行補全。吳若景等人[4]從時空分布的角度構(gòu)建網(wǎng)絡(luò)模型插補水文監(jiān)測站徑流量數(shù)據(jù)的缺失值。對瞬時水流量數(shù)據(jù)缺失值處理方法的研究,大致可分為三類。第一類,直接采用零值、均值或中位數(shù)代替瞬時水流量數(shù)據(jù)中的缺失值。第二類,采用經(jīng)典的機器學(xué)習(xí)或深度學(xué)習(xí)方法插補缺失值。第三類,利用基于時間序列的經(jīng)典算法、機器學(xué)習(xí)和深度學(xué)習(xí)方法對瞬時水流量數(shù)據(jù)中的缺失值進行插補。然而,第一類方法相對其它兩類簡單粗糙,容易造成統(tǒng)計特征和分布特征的偏差,其結(jié)果往往易于陷入局部最優(yōu)[5-6]。第二類方法未考慮瞬時水流量數(shù)據(jù)時間序列特性,將其看作常規(guī)缺失值進行處理,無法有效利用數(shù)據(jù)本身的特點,導(dǎo)致插補結(jié)果不準(zhǔn),甚至欠擬合或過擬合。第三類方法雖然充分考慮到了瞬時水流量數(shù)據(jù)的時間序列特性,強化了數(shù)據(jù)之間的時間依賴性,但弱化了特征之間的其它相關(guān)性。

基于瞬時水流量數(shù)據(jù)集的低秩假設(shè),該文提出一種基于非凸低秩張量補全模型(Nonconvex Low-Rank Tensor Completion Model-Truncated Nuclear Norm,LRTC-TNN)的瞬時水流量連續(xù)缺失值插補方法。創(chuàng)新如下:第一,在低秩張量補全模型(Low-Rank Tensor Completion Model,LRTC)的基礎(chǔ)上引入了適用于瞬時水流量數(shù)據(jù)集的截斷核范數(shù)(Truncated Nuclear Norm,TNN),該引入不僅能使LRTC很好地保留重要信息,也不會導(dǎo)致次要信息的丟失,這樣LRTC便能更有效地提取到空間信息,掌握數(shù)據(jù)的特征相關(guān)性。第二,重新定義了瞬時水流量數(shù)據(jù)的時空關(guān)系,并利用提出的LRTC-TNN模型對含有連續(xù)缺失值的瞬時水流量數(shù)據(jù)進行處理。這些改進不僅能使LRTC-TNN完美地兼容瞬時水流量數(shù)據(jù)集,而且能充分發(fā)揮LRTC-TNN方法高維特性的優(yōu)勢,很好地利用時間序列特性把握數(shù)據(jù)的時間依賴性,同時可以有效地提取數(shù)據(jù)的特征相關(guān)性,一定程度上解決了第三類方法中存在的問題,為處理含有連續(xù)缺失值的瞬時水流量數(shù)據(jù)提供了有效方案。

1 基本原理

1.1 符號定義與標(biāo)注

1.2 非凸低秩張量補全模型

非凸低秩張量補全模型(Nonconvex Low-Rank Tensor Completion Model,LRTC)與低秩矩陣補全的原理類似,LRTC本質(zhì)上是建立在輸入張量的低秩假設(shè)上,是一種張量處理模型。對于有部分觀測值的三階張量Y∈RM×N×T,LRTC模型表示為:

(1)

(2)

1.3 LRTC-TNN

雖然核范數(shù)最小化在矩陣和張量數(shù)據(jù)的插補任務(wù)中很有效,但研究發(fā)現(xiàn),通過基于奇異值的某些非凸函數(shù)有更好的效果[9-11]。由于截斷核范數(shù)(Truncated Nuclear Norm,TNN)[10,12]具有更高的靈活性,不但能保留大的奇異值還會引入較小的奇異值,避免信息丟失,所以引入TNN來替換式(2)中的核范數(shù),得到式(3)。

(3)

1.4 算法求解

(4)

(5)

(6)

(7)

1.5 瞬時水流量數(shù)據(jù)時空關(guān)系

該文將二維瞬時水流量數(shù)據(jù)轉(zhuǎn)換成滿足“日期塊×日期×?xí)r間”關(guān)系的三階張量數(shù)據(jù),用Y表示轉(zhuǎn)換后含有缺失值的瞬時水流量張量數(shù)據(jù),X表示最終填補缺失值后的張量。將Y作為輸入,通過張量補全任務(wù)式(3)求解X,其本質(zhì)是張量補全過程。利用算法1中的ADMM將張量補全任務(wù)式(3)分解成迭代求解Xk,M,T的三個子問題。其中Xk是X(k)經(jīng)過基于TNN的奇異值分解處理后重構(gòu)的張量,k可以取1,2,3,意味著能從不同的方向上提取Xk的各種特征。M用來保留觀察信息,然后將這些信息廣播到張量Xk中,并對Xk進行迭代更新。T在ADMM中用來進行對偶更新。每次迭代都會通過解Xk得到X,再判斷X是否達到收斂條件,若達到則輸出,若未達到,則不斷迭代更新X。

1.6 基于LRTC-TNN的瞬時水流量數(shù)據(jù)插值算法

正如圖1所示,為了利用LRTC-TNN模型將帶有缺失值的瞬時水流量數(shù)據(jù)插補成完整張量,給出以下預(yù)處理步驟:

第一步,依據(jù)1.5節(jié)的方法通過張量展開和折疊結(jié)合奇異值分解的方式將原始瞬時水流量數(shù)據(jù)調(diào)整為具有特定規(guī)則的張量結(jié)構(gòu);

第二步,基于LRTC-TNN模型將張量補全任務(wù)式(3)分解為3個子問題,通過迭代收斂求解這些子問題預(yù)測缺失水流量數(shù)據(jù);

第三步,進行缺失值填補。

圖1 LRTC-TNN模型進行插補的主要過程

該算法的偽碼如下:

算法1:基于LRTC-TNN的瞬時水流量數(shù)據(jù)插值算法。

說明:YD×T:含缺失值的矩陣 XD×T:缺失值被填充后的矩陣

YM×N×T:含缺失值的張量 XM×N×T:最后補全的張量

輸入:y

數(shù)據(jù)關(guān)系轉(zhuǎn)換:y→Y

初始化:α,ρ,θ,ε,max_inter

It=0

While true:

ρ=min{ρ×1.05,ρmax}

forkin (1,2,3):

由Y和X計算tol

it++

if(tol<ε)or(it≥max_iter):

break

return X

數(shù)據(jù)關(guān)系轉(zhuǎn)換:X→x

輸出:x

2 實 驗

2.1 實驗概述

在本節(jié)中,將傳統(tǒng)的均值插補、常用的兩種機器學(xué)習(xí)方法(K近鄰和XGBoost)、近期新提出的深度學(xué)習(xí)方法(GAIN和HyperImpute)以及BTMF(Bayesian Temporal Matrix Factorization, BTMF)[13]、TRMF(Temporal Regularized Matrix Factorization,TRMF)[14]和該文提出的方法應(yīng)用于瞬時水流量數(shù)據(jù)缺失值插補問題中。最后利用MAPE(Mean Absolute Percentage Error,MAPE)和RMSE(Root Mean Square Error,RMSE)分數(shù)對這些算法進行評估。

2.2 數(shù)據(jù)集說明

實驗中采用的數(shù)據(jù)集采集于某水廠管道183天從第0時刻開始至第22時刻結(jié)束每隔15分鐘記錄一次的瞬時水流量。每天共記錄88個數(shù)據(jù)項,組成一個樣本,即每個樣本中有88個特征變量,數(shù)據(jù)集中0代表缺失值。由于一些不可控因素,采集的數(shù)據(jù)中有多個樣本中存在連續(xù)缺失值或獨立缺失值。從采集過程可知,該數(shù)據(jù)具有極強的時間序列數(shù)據(jù)特性。表1對該數(shù)據(jù)集進行了簡要表示。

表1 瞬時水流量數(shù)據(jù)集

在實驗中,人為地對數(shù)據(jù)設(shè)置缺失率,分別為0.3、0.6、0.8。特別需要說明的是,Jafraste等人在研究[15]中將數(shù)據(jù)缺失模式分為三類:完全隨機缺失(Missing Completely At Random,MCAR)、隨機缺失(Missing At Random,MAR)和非隨機缺失(Missing Not At Random,MNAR)。目前,大多研究是針對MCAR[16-17]和MAR[18-19]兩種模式。該文將數(shù)據(jù)缺失模式總結(jié)為兩類,將MCAR和MAR歸為一類并記作RM(Random Missing),用以泛指隨機出現(xiàn)的獨立缺失值,取MNAR中連續(xù)缺失形式作為特例,并記作CM(Continuous Missing),表示連續(xù)缺失值。

2.3 基線模型

將引入以下基線模型與LRTC-TNN模型進行對比:

·貝葉斯時態(tài)矩陣分解(Bayesian Temporal Matrix Factorization,BTMF[13]):2021年Chen X等人將向量自回歸(vector autoregressive,VAR)合并到傳統(tǒng)的貝葉斯矩陣分解(Bayesian Matrix Factorization,BMF)模型中提出了BTMF模型,通過處理VAR中的系數(shù)矩陣識別和解釋不同時間因素之間的因果關(guān)系,因此BTMF能有效處理時間序列中的缺失值。

·時態(tài)正則化矩陣分解(Temporal Regularized Matrix Factorization,TRMF[14]):2016年Rao N等人運用多重自回歸過程對潛在的時間因素進行建模,用一個動態(tài)模型增強時間平滑性。BTMF和TRMF都是由貝葉斯時間張量分解模型[20]推廣得到。

·均值插補:該方法將缺失值用該時刻下其它采集到的可觀測數(shù)據(jù)的平均值進行填充,數(shù)據(jù)集規(guī)模大小對插補性能有直接影響。

·中值插補:該方法將缺失值用該時刻下其它采集到的可觀測數(shù)據(jù)的中值進行填充,插補性能同樣受到來自數(shù)據(jù)集規(guī)模大小的直接影響。

·最頻繁數(shù)值插補:該方法將缺失值用該時刻下其它采集到的可觀測數(shù)據(jù)中出現(xiàn)次數(shù)最多的數(shù)進行填充。

·K近鄰(K Nearest Neighbor,KNN):該方法會參考缺失值附近的可觀測數(shù)據(jù)的k個值,并用這k個值的均值填充缺失值。

·XGBoost(eXtreme Gradient Boosting):對于含有缺失值的特征,通過枚舉所有缺失值在當(dāng)前節(jié)點是進入左子樹還是右子樹來決定缺失值的處理方式。

·HyperImpute[21]:2022年Jarrett等人提出了一種通用的迭代插補框架,用于自適應(yīng)和自動配置模型及其超參數(shù)?；诰€性模型、樹、XGBoost、CatBoost和神經(jīng)網(wǎng)絡(luò)的回歸和分類方法對缺失值進行迭代插補,其本質(zhì)是一種集成學(xué)習(xí)方法。該方法在大量公共數(shù)據(jù)集上進行缺失值插補實驗并取得了SOTA效果。

·生成對抗插值網(wǎng)絡(luò)(Generative Adversarial Imputation Networks,GAIN[22]):2018年Yoon等人提出了一種基于GAN模型,通過生成器對缺失值進行估算,利用判別器確定實際觀察到哪些成分以及哪些成分被估算,并以提示向量的形式向判別器提供額外信息的缺失值插補模型。

該文對基線模型的選擇做出了如下考慮,一方面選取遵循矩陣結(jié)構(gòu)的方法,該類方法多是基于低秩時間矩陣分解的模型,它們的插值估算能充分利用時間信息和數(shù)據(jù)的低秩性,如BTMF、TRMF。另一方面選取遵循張量結(jié)構(gòu)的方法,此類方法能利用更多維度的信息進行插值估算,如文中方法。最后,還對比了傳統(tǒng)方法、基于機器學(xué)習(xí)的方法和基于神經(jīng)網(wǎng)絡(luò)的方法。

2.4 超參數(shù)設(shè)置

參考文獻[8]并結(jié)合文中數(shù)據(jù)集情況,對模型中的超參數(shù)進行合理設(shè)置。將α1、α2、α3均設(shè)置為1/3,用以捕捉模型處理過程中三個關(guān)鍵張量展開的權(quán)重。設(shè)置學(xué)習(xí)率參數(shù)ρ=10-4,ρ的大小會影響模型的收斂速度,ρ過大會增加學(xué)習(xí)時的迭代次數(shù)從而減慢模型的收斂速度,可能會導(dǎo)致過度學(xué)習(xí),ρ過小又會因為迭代次數(shù)過少使模型收斂速度過快,可能導(dǎo)致學(xué)習(xí)不足。設(shè)置θ=0.3,θ是一個通用速率參數(shù),又稱核范數(shù)截斷率參數(shù),用于控制輸入在按某模式張量展開時的整個截斷。θ和ρ的設(shè)置直接決定了模型性能。設(shè)置ε=10-4,ε是用于求解模型的迭代收斂條件。設(shè)置模型最大迭代次數(shù)為200。在以上超參均不變的情況下,分別設(shè)置缺失率0.3、0.6、0.8用于對模型性能進行評估,同時也可作為對照實驗。將183×88的數(shù)據(jù)集轉(zhuǎn)換成3×61×88的輸入張量,即是將二階張量數(shù)據(jù)集進行抽象的升維形成三階張量,使原數(shù)據(jù)集由1個水廠183天的瞬時水流量記錄抽象成3個日期塊61天的瞬時水流量記錄,虛擬出了一個“日期塊”維度,使之符合LRTC-TNN模型的輸入層要求。對于BTMF和TRMF中的參數(shù),分別參照了文獻[13-14]中實驗進行合理設(shè)置。將K近鄰法中的K值設(shè)置為3,XGBoost中參數(shù)依照數(shù)據(jù)集情況合理設(shè)置。GAIN和HyperImpute中的參數(shù)均由文獻[21]中框架自動配置。以上實驗在同一隨機數(shù)種子下進行。

2.5 實驗結(jié)果分析

由于數(shù)據(jù)集中的缺失值是完全隨機出現(xiàn)的,有些缺失值只單獨出現(xiàn),稱為獨立缺失值,有些缺失值則相鄰出現(xiàn),稱為連續(xù)缺失值。鑒于文中方法插值效果在整個數(shù)據(jù)集上的良好表現(xiàn)且獨立缺失值在瞬時水流量數(shù)據(jù)集中只占0.000 3,該文只對不同缺失率下連續(xù)缺失值的樣本進行實驗,用于說明連續(xù)缺失值插補情況,具體參閱圖2～圖4,橫軸表示第幾次采集,縱軸表示瞬時水流量,左邊面板代表連續(xù)缺失值出現(xiàn)在中間時刻樣本的插補情況,右邊面板代表連續(xù)缺失值出現(xiàn)在采集開始時刻樣本的插補情況,圖中曲線中平行于橫軸的線段即為缺失值?？芍?隨著數(shù)據(jù)集中缺失率的提高,插值曲線與真實曲線的重疊越來越少,且波動越來越劇烈,意味著隨著可用信息的減少,文中方法的插值效果也會變差。其次,還能看到在缺失率低于0.6的情況下,文中方法對連續(xù)缺失值的插補效果都比較穩(wěn)定,無劇烈波動,當(dāng)缺失率達到0.8的時候,插值曲線在真實曲線附近上下波動劇烈,此時的插值效果已經(jīng)差強人意。除此之外,右邊面板插值曲線與真實曲線的重疊情況在不同的缺失率情況下都要比左邊面板好,間接說明了文中方法并不完全依賴之前時間步這一單獨因素對缺失值進行插補,還會綜合其它維度信息對缺失值進行插補。

圖2 0.3數(shù)據(jù)缺失率

圖3 0.6數(shù)據(jù)缺失率

圖4 0.8數(shù)據(jù)缺失率

表2展示了不同缺失率下各算法的MAPE和RMSE值,得分的右上角標(biāo)代表了性能排名,1為最優(yōu)。除了傳統(tǒng)的均值、中值、最頻繁插值方法外,可以了解到其它所有算法的缺失率越高,MAPE和RMSE值也越高,揭示了模型的誤差也越大。在缺失率為0.3的時候,可見KNN的MAPE和RMSE值都要比文中方法和基于神經(jīng)網(wǎng)絡(luò)方法的低,有更好的性能,但隨著缺失率的增大,KNN的各項也急劇變大,性能明顯變差,這也符合KNN方法的特點。在不同缺失率下,文中方法的插值性能都能進入前三且接近甚至優(yōu)于一些基于神經(jīng)網(wǎng)絡(luò)方法的SOTA模型。此外,發(fā)現(xiàn)傳統(tǒng)的缺失值插補方法在不同缺失率下,MAPE和RMSE值都遠高于其它方法,且?guī)缀鯚o變化,這也暗示了此類插補方法并不適合瞬時水流量數(shù)據(jù)的連續(xù)缺失值插補任務(wù),下文將不再對其進行討論。

表2 各模型的表現(xiàn)比較(MAPE/RMSE)

圖5中揭示了各插補方法在不同缺失率下MAPE和RMSE值的變化趨勢。顯然,在不同缺失率下文中方法都有接近基于神經(jīng)網(wǎng)絡(luò)方法的先進表現(xiàn),尤其是在高缺失率下,MAPE和RMSE值都是平穩(wěn)變化,表現(xiàn)出了與HyperImpute方法同樣的穩(wěn)定性。而TRMF、KNN和XGBoost的各項值會隨著缺失率的提高出現(xiàn)劇烈的變化,當(dāng)缺失率達到0.6的時候,斜率明顯增大,各項值的變化幅度急劇變大,在高缺失率下,性能明顯變差。與文中方法類似,雖然BTMF在不同缺失率下各項值的變化都較為平穩(wěn),但整體而言,MAPE和RMSE值都高于文中方法,性能差于文中方法。另外值得一提的是,文中方法在缺失率為0.3和0.8的時候,各項值都低于GAIN方法,性能略優(yōu)于GAIN方法,其次,GAIN方法隨著缺失率的增加,其斜率明顯變大,而文中方法斜率變化卻非常小,基本接近SOTA模型HyperImpute方法,這也說明了文中方法具有較強的穩(wěn)定性。從本質(zhì)上進行分析,HyperImpute方法是一種網(wǎng)絡(luò)式的集成學(xué)習(xí)方法,主要依靠數(shù)據(jù)驅(qū)動,且需人為設(shè)置的超參以及網(wǎng)絡(luò)訓(xùn)練過程中需要更新的參數(shù)較多,極易受到超參和數(shù)據(jù)量大小的影響,而提出的LRTC-TNN方法是一種基于一定數(shù)學(xué)先驗知識構(gòu)建數(shù)學(xué)模型解決問題的單一算法,對數(shù)據(jù)和超參的依賴并不如HyperImpute那般明顯。通過實驗可知,LRTC-TNN方法性能接近HyperImpute模型性能,也反映了所構(gòu)建的數(shù)學(xué)模型的合理性和科學(xué)性。

圖5 MAPE和RMSE值變化

3 結(jié)束語

通過實驗展示了含有連續(xù)缺失值的瞬時水流量數(shù)據(jù)在不同缺失率情況下的插補情況,論證了基于LRTC-TNN的瞬時水流量數(shù)據(jù)插值方法在數(shù)據(jù)集低缺失率情況下的良好性能,在較高缺失率情況下仍有較強的穩(wěn)定性,體現(xiàn)在MAPE和RMSE分數(shù)隨缺失率的提高沒有出現(xiàn)強烈波動?；贚RTC-TNN的瞬時水流量數(shù)據(jù)插值方法在瞬時水流量數(shù)據(jù)缺失值插補任務(wù)中的良好表現(xiàn)也間接說明了對瞬時水流量數(shù)據(jù)集的低秩假設(shè)是合理的且能高效捕捉數(shù)據(jù)的時間依賴性和特征相關(guān)性,進而對缺失值進行有效估算。該方法取得了較好的插值效果,一方面說明了該方法對低維時間序列數(shù)據(jù)具有很好的兼容性,另一方面也為處理瞬時水流量數(shù)據(jù)的連續(xù)缺失值問題提供了有效方案。