多區間速度約束下的時序數據清洗方法?

高 菲,宋韶旭,2,3,王建民,2,3

1(清華大學 軟件學院,北京 100084)

2(大數據系統軟件國家工程實驗室,北京 100084)

3(北京信息科學與技術國家研究中心(清華大學),北京 100084)

1 引 言

隨著信息技術的普及和發展,各行各業通過相應的信息系統積累了大量的數據,進一步為大數據以及人工智能技術提供了基礎數據支持.針對大數據以及人工智能技術,為了能更好地發揮其優勢、提升其效率、推廣其應用,數據管理與分析技術作為其基礎性支撐不可或缺.眾所周知:由于傳感器、終端記錄器等設備在數據采集、數據傳輸、數據記錄等過程中會受到主觀和客觀因素的影響,受制于物理和技術上的約束,最終所得到的數據會存在一定的數據質量問題.當數據質量存在問題時,所采集到的數據并不能準確地反映出真實世界的表征,進而無法形成其對人工智能技術的優化促進作用.解決數據中的異常問題、提升數據質量,可以推動數據管理分析對人工智能在數據環節的優化,促進人工智能領域的發展.

1.1 問題背景

目前,數據質量問題所產生的成本和風險不容小覷,有效地識別和修復數據中存在的異常,已經成為數據管理領域中的重要課題.隨著技術的進步,數據的存儲和傳輸成本大幅度下降;同時,由于大數據及人工智能技術的發展,數據驚人的潛能不斷被挖掘,人類社會,尤其是工業領域,更趨向于盡可能地將能夠產生的數據記錄存儲下來.通常情況下,這些數據大多是時間序列數據,也就是包括時間戳在內的一系列數據點.

時間序列數據普遍存在于人們的日常生活以及工業領域中,例如行車路線、溫度變化、股票走勢等.由于大部分時間序列數據中數據點會隨著時間的變化而產生一定的變化規律,Zhang 等人提出了基于速度約束的SCREEN 方法[1]對時間序列數據進行異常修復.該方法采用速度約束范圍[smin,smax]([最小速度,最大速度])來對數據的變化速度進行約束,進一步將超出速度約束范圍的數據點視為異常點并進行修復.但該方法僅適用于單一速度約束區間,即速度變化范圍在一個最大值和一個最小值之間.而實際數據中,數據的速度變化將很可能存在多個速度約束區間.舉例來說,速度變化很可能在或區間中若僅將變化速度約束為,那么所約束的很多正常點將被視作異常點進行修復.同理,若僅將變化速度約束為,那么所約束的正常點同樣會被視作異常點從而產生過度清洗.此外,若將變化速度約束為,那么之間的異常點則會被視作為正常點而不作任何修復.無論是哪種情況,都將大大降低數據的修復質量.

例1:公司對車輛油耗數據進行監督,以分析油耗情況,進一步合理行車,減少成本.在此時間序列數據中,包括耗油和加油兩種行為,如圖1 所示.由于車輛在行駛過程中是一個耗油狀態,所以油箱中的油位整體呈一個下降趨勢.但車輛在行駛過程中不可避免地會存在顛簸,油箱中的油位測量也會存在一定小范圍的振蕩,所以在耗油過程中,油位持動態下降趨勢,具體速度約束為[?1,1],即每單位時間內油位的變化在減少1cm 到增加1cm 的范圍內浮動(根據真實數據情況,該示例中將單位時間設置為5s).而在加油過程中,油位數據為驟然增長態勢,具體速度約束為[20,70],即在加油過程中,每單位時間內油位增加20cm～70cm.若給定時間窗口內兩數據點間的數據變化速度在上述[?1,1]及[20,70]區間范圍外,則該數據變化速度異常,這兩個數據點必然存在異常數據.如圖1所示,藍色數據為異常數據點.

Fig.1 Example of fuel consumption data圖1 油耗數據示例

為了更清晰地表明多區間速度約束和單區間速度約束的區別,本文從上述油耗數據集34 220 個數據點中選取100 個數據點進行修復.在此數據中,若貿然將速度約束定為[?1,1],那么加油行為則被視為異常數據被修復,如圖2 所示,因為15:09 時刻的加油行為,后續較多正常值被誤判為異常值進行過度修復;同理,若速度約束為[20,70],則大量耗油行為將被視為異常數據從而導致過度修復.而若采用速度約束[?1,70],則大部分數據都被視作為正常點,而速度約束在(1,20)內的異常點將無法被有效識別并修復,如圖2 所示,由于15:12 時刻一個異常點的的存在,導致后續多個正確值被誤修.

Fig.2 Repairing with SCREEN and multi-speeds constraints圖2 基于SCRREN 方法及多區間速度約束方法下的修復效果

基于此,本文主要針對時間序列數據的數據質量問題進行研究,進一步通過多區間速度約束對時序數據中的異常進行修復.

1.2 主要貢獻

本文主要貢獻如下:

(1)對多區間速度約束以及修復結果進行了定義.本文所提的速度約束不僅僅局限于單一的最大最小速度范圍,而是進一步給出了多個速度區間,使得約束更具體、更精確.修復結果的定義具體到給定窗口內,在應用時可靈活擴展到整條時間序列,進而使得修復方法具有更廣泛的適用性;

(2)提出了基于多區間速度約束的時間序列修復方法,并給出了相應的具體算法.通過多區間速度約束,給出了修復對象點的修復范圍以及修復候選點,并基于各修復候選點對其給定窗口內的后續時刻產生更加具體的修復范圍,從而對后續修復候選點進一步進行篩選,以確定最終的修復候選點.最后對給定窗口內各時刻所確定的候選點基于圖進行存儲,以便于使用動態規劃的方法進行修復;

(3)針對多區間速度約束的動態規劃修復方法提出了相應的理論及其證明,為修復方法提供理論支持.理論1 表明:在修復候選點內可以找到一條最優修復路徑,使得窗口內的修復距離和最小.此外,當后續點對當前點所生成的修復候選點不在最終的修復范圍內時,理論2 也表明,可以選擇相應的約束點作為新的修復候選點以保證最小的修復距離;

(4)提供單區間特例下速度約束動態規劃修復與SCREEN 方法的分析比較.單區間特例下,在約束范圍的確定以及修復候選點的確定方面,本文所提出的多區間速度約束方法與SCREEN 方法所得到的結果一致.而由于多區間方法在所給定的候選點內根據動態規劃方法選取最優修復路徑,所以本文所提出的修復方法將等同或優于SCREEN 方法;

(5)采用一個人工數據集、兩個真實數據集以及一個帶有真實錯誤的數據集在RMS 錯值、聚類及分類精確率及時間開銷方面進行了實驗,并與包括SCREEN 在內的多種現有相關方法進行了對比.結果表明:本文所提出的多區間速度約束方法在修復效果方面表現最優,同時在時間開銷方面有著較好的權衡.此外,本文采用了多個帶有分類標簽的時序數據集在分類精確率上進行驗證,從精確率結果來看,多區間速度約束方法可為后續包括數據分析以及人工智能在內的研究處理提供更優秀的數據支撐.

1.3 論文結構

本文第2 節給出本文研究相關的基礎定義,對時間序列、多區間速度約束以及修復結果進行解釋,并提供問題形式化定義即修復條件和修復目標.第3 節提出具體基于多區間速度約束的動態規劃修復方法,包括具體方法描述、理論證明、特例分析以及具體算法等.第4 節通過一個人工數據集、兩個真實數據集和一個帶有真實錯誤的數據集,在修復效果和時間性能,以及聚類和分類精確率方面與現有方法進行對比分析,并通過多個數據集,在分類精確率上與現有方法進行比較驗證.在第5 節中對相關工作進行介紹.最后,在第6 節對本文的工作進行分析總結.

2 基礎定義

作為大數據技術及人工智能技術的數據支撐,工業大數據正成為數據相關研究領域的熱點.本文主要研究工業數據中的時間序列數據,為便于敘述,本節將對時間序列、時間戳、速度約束、多區間速度約束以及修復結果等進行定義.

2.1 時間序列定義

時間序列指一系列包含時間戳的數據點,具體而言,在一條數據序列x=x[1],x[2],…中,數據點x[i]指第i個數據點,每個數據點x[i]都具有一個時間戳t[i].簡便起見,下文中將x[i]簡寫為xi,t[i]簡寫為ti.

2.2 多區間速度約束定義

如圖3 所示,在給定窗口w中,給定速度約束區間S包括兩個約束區間,數據點對(x1,x2)滿足速度約束區間,即

同理,(x1,x3)滿足速度約束區間.因此,上述兩對數據點均滿足多區間速度約束S.而(x1,x4)既不滿足s1也不滿足s2,即數據對(x1,x4)不滿足多區間速度約束S.

Fig.3 Example of multi-speed圖3 多區間速度約束示例

2.3 修復結果定義

修復結果x′指在給定窗口w內,將時間戳ti上的數據點xi修復為,修復后時間戳不變,即.根據數據修復中的最小修復原則[2],最終的修復距離可定義為

如圖3 所示,x4修復為,時間戳依舊為t4,該窗口內最終修復距離為

2.4 問題定義

給定一個時間序列x,時間窗口w,窗口內共ω+1 個數據點,窗口起始點xk,窗口內各xj點的速度約束范圍以及多區間速度約束S={s1,s2,…,sm},,其中,r=1,2,…,m.多區間速度約束修復指:在窗口w內找到一個修復結果x′,使得修復后窗口內各點滿足多區間速度約束,同時修復距離最小,即:

其中,窗口內各xj點的速度約束范圍通過xk點之前且在xj點同一窗口內的其他點進行多區間速度約束得出,若xk點前無數據點與xj點共一窗口,則不限定xj的速度約束范圍,具體方法可見第3.1 節.

3 動態規劃修復方法

3.1 速度約束范圍的確定

給定多區間速度約束S,窗口w,窗口內起始數據點xk以及窗口內各點xk,xk+1,xk+2,…,xk+ω,0

為更加清晰地敘述多區間速度約束方法,本節先對數據點xj進行研究,通過其同一窗口內且非給定窗口w內的其他各數據點xi(tj?w≤ti

xk同一窗口內的先前點(i=k?1,k?2,…,k?nk,即:當xk為窗口內最后一個點時,為該窗口內第1 個點,≤w),將根據公式(1)、公式(2)對xk點生成速度約束范圍,并根據公式(3)對各點所生成的約束范圍取交集產生速度約束范圍最終根據公式(4)形成xk的多區間速度約束范圍集合如圖4 所示,灰色區域即為xk的多區間速度約束范圍集合

類似的,xk+1同一窗口內(除去給定窗口w所包含點)的先前點ix′(i=k?1,k?2,…,k?nk,即:當xk+1為窗口內最后一個點時,為該窗口內第1 個點,≤w)將對xk+1點生成速度約束范圍,如圖4藍色區域所示.

Fig.4 Range of multi-interval speed constraints圖4 多區間速度約束范圍

xk+2同一窗口內(除去給定窗口w所包含點)的先前點ix′(i=k?1,k?2,…,k?nk+2,將對xk+2點生成速度約束范圍.在圖4 示例中,xk+2同一窗口內的前述點均在給定窗口w內,所以此時不限定xk+2的速度約束范圍.

以此類推,得出窗口w內所有點(xk,xk+1,xk+2,…,xk+ω)的速度約束范圍:

1.消化道。①寄生于小腸的有：豬蛔蟲、蘭氏類圓線蟲、蛭形巨吻棘頭蟲、姜片吸蟲和豬等孢球蟲。其中豬蛔蟲的危害和流行最為嚴重。②大腸內寄生的有：結節蟲(食道口線蟲)、鞭蟲(毛首線蟲)和結腸小袋蟲，后者多發于南方且人畜共患。③ 胃內有胃圓線蟲，但危害較輕。

3.2 修復候選點的確定

通過觀察數據點與速度約束之間的關系可以發現,速度約束S可以與數據點xi(tk≤ti

給定窗口w內的xk后續點xi(xk+1,xk+2,…,xk+ω),tk

同理,該窗口內的數據點xk+1可由其后續點(xk+2,…,xk+ω)生成候選點集.以此類推,可得到窗w內各數據點xi(i=k,k+1,…,k+ω)的修復候選點集Xi,其中,xk+ω的修復候選點集Xk+ω中只有數據點xk+ω本身,如圖5 所示.

如圖6 所示,空心點為上述方法所求得的候選點,實心點為原數據點,其中:灰色點為不在約束范圍內的無效候選點,其他點為有效候選點.

Fig.5 Capture of repairing candidate points in a given window圖5 給定窗口內各時刻修復候選點的生成

Fig.6 Obtain candidates set Xi according to range 圖6 根據修復候選范圍篩選修復候選點,得到集合Xi

理論1.在多區間速度約束下,一定可以在xk及其修復候選點中找到關于xk的最優修復解

證明:令ω=|{i|tk

(1)若修復后xi未改變,即,此時xi點修復距離為0,如圖8 所示;

Fig.7 Impossible case of smaller than the minimum candidate c1,圖7 小于最小候選點,

Fig.8 between two continuous candidates,,without moving xi圖8 介于兩相鄰候選點之間,無需修復

Fig.9 between two continuous candidates,圖9 介于兩相鄰候選點之間,

Fig.10 between two continuous candidates,圖10 介于兩相鄰候選點之間,

為計算窗口內總修復距離,可以對上述情況(2)和情況(3)中的xi進行計數.

(a)當情況(2)和情況(3)中xi的個數相同時,選擇cj,cj+1中與xk距離更近者作為.當選擇cj時,相應的總修復距離為 Δ(x,x′)=Δ(x,x′)?(?cj)＜Δ(x,x′);當選擇cj+1時,相應的總修復距離為

(b)當情況(2)中xi的個數大于情況(3)中xi的個數,選擇cj+1作為相應的總修復距離為

(c)當情況(2)中xi的個數小于情況(3)中xi的個數,選擇cj作為相應的總修復距離為

類似地,窗口內其他點xi(xk+1,xk+2,…,xk+ω),tk

3.3 修復路徑的確定

由上述內容可知:在以xk為起點的窗口w中,每一個數據點xi均可獲得一個給定速度約束范圍內的修復候選點集合,令該集合內候選點個數為ηi.

如第3.1 節所述,給定多區間速度約束S、窗口w以及窗口內起始數據點xk,窗口內各數據點xj(tk≤tj≤tk+w)均可與其同一窗口內前述各數據點xi(ti

xi的每個修復候選點ci,di均可根據公式(8)、公式(9)對同一窗口w內的后續點xj產生速度約束范圍

其中,tk≤ti

其中,tk≤ti

理論2.在以xk為起點的窗口w中,若數據點xj在速度約束范圍中無修復候選點,則可指定距離原xj點最近的速度約束點作為修復候選點,其中,速度約束點指上述中對xj點所確定的速度約束范圍邊界點,此時修復距離最小.修復候選點集合更新為如下

同理,此修復候選點對后續點產生的修復范圍中若包含已有候選點,則依舊可根據該候選點選擇最優修復路徑;反之,若已有候選點未在該修復范圍之內,則可按理論2 生成后續點的修復候選點,且該條路徑的修復距離最小.

綜上所述,本理論所確定的修復候選點中存在一條最優修復路徑,使得修復距離最小.□

如圖11 所示:從tk時刻開始,對于數據點xi(tk≤ti

Fig.11 Obtain candidates sets according to ranges圖11 根據修復候選范圍篩選修復候選點,得到集合

Fig.12 Generation of edges for repairing path圖12 修復路徑邊生成

Fig.13 Graph of repairing path圖13 修復路徑圖

3.4 特例:單區間速度約束

本節將給出多區間速度約束下的特例情況,單區間速度約束,即只有一個速度約束區間,其中,r=1.由于SCREEN 方法同樣基于速度約束,本節將針對二者進行分析比較.

? 速度約束范圍的確定

由于只存在一個速度約束區間,如第3.1 節所述,xk同一窗口內的先前點(i=k?1,k?2,…,k?nk)將對xk及其同一窗口w內的所有后續點xj(xk+1,xk+2,…,xk+ω)生成相應的速度約束范圍,如圖14 所示.該速度約束范圍與SCREEN 方法中點所生成的速度約束范圍相同.

Fig.14 Special case of single interval speed constraint圖14 單區間速度約束特例

? 修復候選點的確定

與多區間速度約束方法相同,在單一速度區間下,給定窗口w內的xk后續點xi(xk+1,xk+2,…,xk+ω,tk

? 修復路徑圖的確定

與多區間方法相同,在單一速度區間下,窗口w內的每一個數據點xi均可獲得一系列給定速度約束范圍內的修復候選點.每一個修復候選點均可對同一窗口內的后續點產生速度約束范圍,該速度約束范圍與SCREEN方法中的速度約束范圍相同.在該速度約束范圍下,對窗口w內各時刻候選點的選擇可形成一條修復路徑.由于速度約束范圍相同,那么所確定的修復候選點也與原SCREEN 版本中的修復候選點相同.因此,在上述各修復候選點所形成的修復路徑中,必有一條與原SCREEN 版本中的修復路徑相同,而本文根據動態規劃方法選擇了最小修復路徑,所以本文選擇的修復路徑一定優于或等于SCREEN 方法中的修復路徑.

3.5 算 法

本文根據上述修復方法提出了算法1.

算法1.基于多區間速度約束的動態規劃修復方法.

輸入:順序時間序列x,時間窗口w,起始數據點xk,多區間速度約束S;

輸出:修復后的時間序列x′.

如前文所述,在算法1 中,第1 行～第18 行主要用于初步確定修復候選點及速度約束范圍.其中,第5 行～第10 行可以依據公式(1)～公式(4)對給定時間窗口w內的各數據點xi通過其同一窗口且在給定窗口w外的前述xj點生成相應的多區間速度約束范圍集合;第11 行～第17 行可以依據公式(5)～公式(7)對給定時間窗口w內的各數據點xi通過該窗口w內的后續xj點及上述約束范圍集合生成xi點的修復候選點集合Xi.

第19 行～第36 行主要用于確定修復路徑圖.其中,第28 行及第29 行依據公式(8)、公式(9)通過各時刻候選點生成窗口w內后續各時刻點的速度約束范圍,并結合上述約束范圍集合生成新的約束范圍;第30 行～第33 行則根據新的約束范圍篩選出各修復候選點約束下的后續時刻的修復候選點,并形成相應的修復路徑邊,同時賦予邊的權重.最終,通過第37 行的動態規劃方法求解得出最優修復路徑.

由前述定義可知,窗口內數據點的個數最多為w,第1 行～第18 行初步確定修復候選點所需時間為O(w2).在窗口內所產生的修復候選點總數最多為(w?1)×r+1,其中,r為速度約束區間的個數.因此,第19 行～第36 行確定修復路徑圖所需時間為O(w2×((w?1)×r+1)).結合動態規劃所需時間O(((w?1)×r+1)2),整體算法時間復雜度為O(w3×r).作為局部定義算法,本文所提出的多區間速度約束方法可以較為快速地對大數據進行修復,為后續的數據分析以及人工智能研究提供數據基礎.

4 實 驗

為驗證本文所提出的多區間速度約束方法,本節將選擇多個數據集,根據相應的評價標準進行實驗評估,同時將實驗結果與多個現有方法進行對比.具體實驗環境、實驗數據集、評價標準、現有對比方法以及實驗結果如下所述.

4.1 實驗設置

? 實驗環境

本文使用JAVA 語言在如下環境下對各部分內容進行實現,處理器為3.1GHz Intel Core i5,內存為16GB 2133MHz LPDDR3.

? 實驗數據

本文采用一個人工數據集和兩個真實數據集進行實驗.人工數據集包含30 000 個數據點,其速度約束區間主要在[?10,?8]以及[0,2]之間.真實數據集1 為車輛油耗數據,共34 220 個數據點.如第1.1 節例1 所述,數據主要體現耗油和加油兩種行為:考慮到車輛行駛過程中油箱的振蕩,其耗油速度區間設置為[?1,1];而加油行為則會使油位驟然上升,可將加油速度區間設置為[10,70].真實數據集2 為GPS 軌跡數據,共7 962 個數據點,主要采集了個人步行軌跡以及汽車行駛軌跡,結合實際情況以及數據采集信息,步行速度區間為[0,10],汽車行駛速度區間為[30,100].上述3 個數據集均由無錯值的數據點構成,本文采取文獻[4]中所提出的方法,隨機生成新的數值作為錯值來代替原有真值,以形成異常數據點.如下述實驗結果所示,異常率0.1 表示有10%的數據點被隨機替換為異常值.在真實數據油耗集中,所注入的數據值可能會小于0,此數值為異常數據,因為油箱內的油位最小值為0,不可能為負數.同理,所注入的數據值可能會有大于70 的情況,根據本真實數據值的情況,油箱內油位最大值為70,超出該值數據可視為異常數據.當注入數據值在[0,70]范圍內時,由于絕大部分情況下該隨機注入的數據值無法與同一時間窗口內的其他點形成給定閾值范圍內的數據變化速度,此注入的數據值仍可視為異常值.同理,在GPS 數據集以及人工數據集中,隨機注入的數據值可視為異常值.同時,本文使用了海拔數據進一步驗證多區間速度數據方法對真實異常值的修復作用.該數據集為地鐵地面輕軌上行駛過程中所采集的海拔數據.觀察所采集的真實數據發現:該數據具有較大的異常,某些數據點在1s 之內的海拔變化甚至會高達14m.經統計,該數據集共有1 398 個數據點,其中有218 個點為異常數據點.經過整體數據分布情況以及合理性分析,本文選取[?2,1.61]以及[1.9,2]作為該數據的速度約束區間.此外,為進一步驗證本方法為后續數據分析及人工智能所提供的幫助,本文選取了 UCR Time Series Classification Archive(http://www.cs.ucr.edu/～eamonn/time_series_data/)中的5 個數據集,包括數據集Car,Coffee,BeetleFly,Fish 以及InlineSkate,以驗證本方法下修復結果的分類精確率.

4.2 評價標準

本文采用RMS錯值[5]作為修復結果評價標準.令xtruth作為時間序列的真值,xrepair作為修復的時序數據結果.為了評估修復結果與真值之間的相似程度,令Δ(xtruth,xrepair)作為真值xtruth與修復結果xrepair之間的距離,Δ(xtruth,xrepair)越小,修復結果與真值越相近,即修復結果越精確.

此外,考慮到修復后的數據將在后續的數據分析及人工智能方面起著基礎支撐性作用,本文還提出了各數據集進行修復后的聚類及分類結果.本文采取DBSCAN[6]方法對各修復結果進行聚類分析,并選用KNN 方法[7]對各修復結果進行分類,采用了k折交叉驗證[8]方法.本文所使用的聚類及分類精確率[9]如下公式所述:

4.3 現有方法

本文新提出的多區間速度約束方法將與現有的多種修復方法進行比較,包括基于單區間速度約束的SCREEN 方法、基于順序依賴Sequential Dependency[10]的修復方法以及基于否定約束的全局Holistic[11]修復方法.

4.4 實驗結果

本文選擇3 個數據集來對修復方法進行驗證,并對各數據集提供了多種修復方法在不同異常率(異常數據點數/總數據點數)下及不同數據量下的RMS 錯值結果、時間開銷結果以及聚類與分類精確率結果.同時,本文提供了具有真實異常的海拔數據集,并根據多種方法進行修復得出修復后的RMS 錯值結果、時間開銷結果以及聚類與分類精確率結果.此外,本文還通過UCR 時序數據中的5 個數據集對上述各修復方法進行了分類精確率驗證.具體實驗結果如下文所述.

(1)人工數據集

由圖15(a)可發現,本文所提出的多區間速度約束修復方法所表現出的修復效果在各異常率下均優于其他修復方法.其結果趨勢與全局修復Holistic 方法相似,但明顯優于Holistic 方法.

為更加直觀地驗證本文所提方法對數據分析及人工智能方面的影響,圖15(c)及圖15(d)提供了聚類及分類精確率.觀察結果圖可發現:SCREEN 方法及Sequential 方法隨著異常率的增加,其聚類效果顯著下降,甚至遠低于未經修復的錯值數據聚類結果;而本文方法則表現出了最優的聚類結果,與真實結果較為接近,且明顯高于全局修復Holistics 方法.在分類結果方面,與RMS 錯值結果類似,多區間速度約束修復方法與全局Holistic 方法隨著異常率的增加而遠優于SCREEN 方法及Sequential 方法;同時,多區間速度約束方法整體體現出最優的修復效果.該實驗結果表明:相對于其他方法,本文所提出的多區間速度約束方法可以對數據分析與人工智能技術提供更為精確的數據基礎.

Fig.15 Varying rates of anomalies over synthetic data圖15 人工數據集中不同異常率下的修復效果

在時間開銷方面,由圖15(b)可知,本文方法遠低于Holistic 方法.且在不同的異常率下,本文方法時間開銷較為穩定.此外,雖然SCREEN 方法以及Sequential 方法的時間開銷較低,但本方法在各異常率下的RMS 錯值均遠低于上述兩種方法.進一步觀察可發現:隨著異常率的上升,相對于SCREEN 與Sequential 方法,本文所提出的多區間速度約束方法在RMS 錯值及聚類分類精確率方面表現出更加突出的優越性.

關于不同數據量下的修復結果,觀察圖16 可以發現,與不同異常率下的修復結果較為一致,多區間速度約束方法在RMS 錯值方面有著最優的修復效果,且多區間速度約束方法與全局Holistic 方法在RMS 錯值方面遠低于SCREEN 方法及Sequential 方法.

Fig.16 Varying data sizes over synthetic data圖16 人工數據集中不同數據量下的修復效果

在聚類及分類精確率方面,本實驗選取了異常率為0.05 的數據.在聚類精確率方面,在不同數據量下的修復結果中,Sequential 方法表現出了最差的聚類精確率;而多區間速度約束方法有著最高的聚類精確率,且與正確數值下的聚類結果高度接近.在分類精確率方面,SCREEN 方法表現出了最差的分類精確率,而多區間速度約束方法同樣有著最高的分類精確率.同時,本可擴展性實驗結果也表明:在不同的數據規模,甚至是大數據規模下,本文方法可以提供較為優質的數據支撐.此外,在時間開銷方面,本文所提出的多區間速度約束方法低于全局Holistic 方法,在修復效果與時間開銷方面有著較好的權衡.

(2)油耗數據集

關于真實油耗數據集在不同異常率下的實驗,由圖17(a)可發現:與人工數據集較為相似,本文所提出的多區間速度約束修復方法所表現出的修復效果在各異常率下均優于其他修復方法,尤其在異常率大于0.1 的情況下,遠優于SCREEN 方法以及Sequential 方法.結合RMS 錯值與圖17(b)時間開銷結果來看,本文所提出的多區間速度約束方法較好地權衡了修復效果與時間開銷之間的關系,即在時間開銷遠低于Holistic 方法的前提下,給出了優于該方法的修復效果.

此外,在聚類精確率方面,本文所提多區間速度約束方法遠高于未經修復的錯值數據聚類結果;且隨著異常率的增加,其聚類精確率與Holistics 方法相似,遠高于SCREEN 方法及Sequential 方法所得到的修復結果.值得一提的是:在分類精確率方面,SCREEN 方法以及Sequential 方法修復后的結果甚至要低于未修復的錯值數據;而本文所提的多區間速度約束方法以及全局Holistic 方法則遠高于未修復的錯值數據,尤其是在異常率為0.05時,極其接近真實值的修復結果.

Fig.17 Varying rates of anomalies over oil data圖17 油耗數據集中不同異常率下的修復效果

與人工數據集實驗類似,在不同的異常率下,本文方法時間開銷也較為穩定;而SCREEN 與Sequential 方法則隨著異常率的增加,其時間開銷呈明顯上升趨勢.綜合來看,本文所提出的多區間速度約束方法更適用于后續的數據分析及人工智能技術,可以在較短的時間內較為高效地對時間序列進行清洗以提高數據質量,從而為數據分析及人工智能技術提供更精確的數據基礎.

在基于異常率的實驗之外,本實驗提供了如下關于真實油耗數據集在不同數據量下的實驗.由圖18(a)可以發現:與異常率實驗較為一致,多區間速度約束修復方法在各數據集大小下均表現出最優的修復結果.具體從圖18(c)聚類精確率上來看:在不同的數據量下,本文方法所得到的修復結果相較于其他方法有著最高的聚類精確率,且修復結果較為穩定,有著較好的可擴展性.從圖18(d)分類精確率結果上來看:在0.05 的異常率下,本文所提出的多區間速度約束方法表現出了極為優秀的分類結果,其各數據規模下的修復結果與真實值高度相似且接近于1.結合圖18(b)可知:在時間開銷稍高于SCREEN 方法以及Sequential 方法的前提下,本文方法RMS 錯值遠低于上述兩種修復方法.同時,在RMS 錯值較低于Holistic 方法的前提下,本文方法時間開銷遠低于該方法,整體相差兩個數量級.

Fig.18 Varying data sizes over oil data圖18 油耗數據集中不同數據量下的修復效果

(3)GPS 數據集

觀察圖19 中關于真實GPS 數據集在不同異常率下的實驗結果可以發現,該實驗結果在時間開銷上與人工數據集以及真實油耗數據集較為相似.關于RMS 錯值實驗結果,觀察圖19(a)可發現:現有其他方法在此數據集修復結果上較為集中,且多區間速度約束方法明顯優于其他各方法.值得說明的是:由于在上述人工數據集以及真實油耗數據集中,序列為時間等間隔數據,而Sequential 方法是考慮連續兩個數據點之間的數值距離約束,所以此時Sequential 方法與SCREEN 速度約束方法有著較為相似的結果及趨勢.而在此GPS 數據集實驗中,數據并非等時間間隔序列,所以上述兩種方法實驗結果相對存在較大的差異.

由圖19(c)可知:在聚類精確率方面,本文所提方法隨著異常率的提高,其聚類效果遠高于SCREEN 方法、Sequential 方法以及未經修復的錯值數據,且與全局修復Holistics 方法也拉開了一定的距離.同樣,圖19(d)也清晰地表明了本文所提出的多區間速度約束方法在分類精確率上呈現出最優的修復效果,尤其在異常率低于0.25 時,其精確率與真實時序數據的分類精確率較為貼近,且遠高于其他修復方法,尤其是Sequential 修復方法.

為了更好地體現各方法的修復效果,本實驗選取GPS 數據集在0.05 異常率下進行可擴展性實驗,并提供了在不同數據量下的實驗結果.由圖20(a)可發現:隨著數據量的增加,各方法在RMS 錯結果值上均有著或多或少的上升.而在各方法中,多區間速度約束方法下的RMS 錯值結果值增幅最小,這也體現出該方法具有最佳的可擴展性.

在分類精確率方面,本文所提出的多區間速度約束方法也呈現出了最優的分類精確率,同時,Sequential 方法則有著最低的精確率,甚至在某些數據量下(如數據量小于2.3k 時),其分類精確率遠低于未經修復的錯值數據,與不同異常率下的修復結果及不同數據量下的RMS 錯值結果較為一致.而由于在0.05 異常率下的多個方法修復結果的聚類效果較為接近,所以本文進一步選取異常率為0.25 的數據來進行聚類結果的可擴展性實驗,以使各方法下的聚類精確率可以較為清晰地呈現.從圖中可以發現:本文方法在較少的時間開銷下,其聚類精確率與全局修復Holistic 方法較為相似,且較高于Holistics 方法,遠高于Sequential 方法及未經修復的錯值數據.

Fig.19 Varying rates of anomalies over GPS data圖19 GPS 數據集中不同異常率下的修復效果

Fig.20 Varying data sizes over GPS data圖20 GPS 數據集中不同數據量下的修復效果

關于時間開銷方面,由圖20(b)可知:與真實油耗數據集實驗相似,多區間速度約束方法在保持最低RMS 錯值的前提下,其時間開銷處于可接受范圍,整體低于全局Holistics 方法1 個數量級.

(4)海拔數據集

為進一步佐證本文所提多區間速度約束方法在真實數據集中的實用性,本文針對具有真實異常的海拔數據集使用多種修復方法進行實驗,最終得出其RMS 錯值結果、聚類與分類精確率結果以及時間開銷結果,見表1.從表1 中可發現:在RMS 錯值方面,本文所提出的多區間速度約束方法表現出了最優的修復結果,與Holistic方法、SCREEN 方法以及SWAB 方法相比,本文方法RMS 錯值更低,修復結果更精確,且遠優于Sequential 方法;在聚類精確率方面,相較于其他各修復方法,多區間速度約束也呈現出了較好的結果;在分類結果方面,本文所提多區間速度約束方法也優于其他各方法,更接近于正確值所達到的分類精確率;此外,在時間開銷方面,本文所提方法也達到了最少的時間開銷,遠低于具有較優修復結果的Holistic 方法.

Table 1 Altitude dataset with real anomalies表1 帶有真實錯誤的海拔數據集修復效果

(5)UCR 數據集

為了進一步驗證各修復方法在分類效果上的表現,從而為后期包括數據分析及人工智能在內的多種應用做好數據支撐,如前所述,本文選取多個具有分類標簽的時序數據集,以更全面廣泛地驗證本文所提的多區間速度約束方法對后續數據應用所產生的影響.由圖21 發現:在不同數據集下,多區間速度約束方法均呈現了較好的分類結果,遠高于未經修復的錯值數據分類結果,同時與真實值分類精確率較為接近.圖中5 個數據集真實數據分類數目有一定的差異,其中,Car 數據集有4 個分類標簽;Coffee 及BeetleFly 數據集有2 個分類標簽,因此在這兩個數據集中,整體分類精確率較高;與之相反,Fish 及InlineSkate 數據集中有7 個分類標簽,因此如圖所示,其整體分類精確率偏低.然而在這兩個數據集中,各方法修復后的分類結果均遠高于未修復的錯值分類結果,這也進一步表明,數據應用前期的數據清洗修復等步驟對后續的數據分析及人工智能過程有著至關重要的作用.

Fig.21 Classification accuracy under different UCR datasets圖21 UCR 數據集分類精確率

5 相關工作

隨著大數據和人工智能技術的深入發展,作為其技術支持與基礎的數據管理與分析技術也日益成為相關領域研究熱點問題.為了進一步推動數據管理與分析技術,優化大數據和人工智能的產出成果,減少因數據問題而對后續分析研究形成的限制,數據質量問題受到了越來越多的關注.Ji 等人[12]提出了查詢容錯等機制,但該機制必須在容錯效果、性能和實現成本之間進行折衷,且并未對數據查詢等范圍外的數據使用進行處理說明.此外,諸多業內研究者針對數據異常問題提出了多種檢測及修復技術.

5.1 基于平滑的修復方法

基于平滑的修復方法指使用數據平滑技術來減少異常點.基于平滑修復可以減少噪聲點,使數據變化趨勢更順暢平滑,直覺上,該類平滑后的數據有著更少的異常點.其中,SWAB 平滑算法[13]基于線性插值[14]以及回歸技術[15]對時間序列數據進行清洗,由于該算法可以對時間序列進行分段,因此該算法可以支持時間序列數據進行在線清洗.此外,移動平均方法也常用于時間序列數據平滑修復.簡單移動平均值(SMA)是最后k個數據的未加權平均值,該算法以此值來對下一個數據點進行修復.而加權移動平均值(WMA)則對窗口中不同位置的數據點添加了權重設置,例如距離目標數據點越遠的數據權重越低等.相應地,指數加權移動平均值(EWMA)[16]隨時間距離增加添加指數遞減的權重,以適用于非穩態的時間序列[17?19].

基于平滑的修復方法存在較大的修復局限性,為保障時間數據序列的平滑性,平滑修復方法會將異常點附近多個原本正確的真值數據反而過度修復為錯值數據,異常點會極大地影響修復結果的精確性.

5.2 基于約束的修復方法

通常來說,大多數數據在點與點之間具有一定的約束依賴.在關系型數據庫領域,有很多基于完整性約束的清洗算法.一些數據約束規則,例如函數依賴(functional dependency,簡稱FD)[20,21]等,可用于數據清洗修復相關問題中.該類方法通過求解數據的最小修復進行數據清洗,相應的清洗結果會滿足所給定的函數依賴約束規則.而由于約束關系適用于任何一對元組,因此具有最小修改的修復問題通常被認為是NP 難題[22].考慮到這一問題,Beskales 等人[23]提出了基于采樣的數據清洗方法,其基本思想是,從數據修復候選集中抽取部分樣本來進行數據清洗.此外,基于FD 約束存在的另一個問題是,一些真實數據集中無法尋取絕對的FD 約束.因此,Bohannon等人[24]在基于函數依賴的清洗修復中引入了條件概念,即利用條件函數依賴(conditional functional dependency,簡稱CFD)[25,26]作為約束進行數據清洗.然而,由于該方法所需要的約束規則較為繁瑣龐大,所以所形成的算法在時間開銷上不甚理想.在如今大數據及人工智能背景下,該方法無法快速而準確地為后續相關技術操作提供優質的數據支持.

一般情況下,在時間序列數據中,數據值大多為具體的數據,而FD,CFD 等數據約束規則需要遵循嚴格的相等關系,所以基于上述約束的修復方法在時間序列數據中難以產生較好的清洗修復結果.基于此,Fan 等人[27]提出了匹配依賴(matching dependency,簡稱MD),將上述嚴格的相等關系進一步放寬為相似關系,即可以在約束規則的左邊引入相似度度量.進一步地,Song 等人[28]提出了差異依賴(differential dependency,簡稱DD),在約束規則的左右兩邊均引入相似度度量,從而將兩邊的相等關系均放寬為相似關系.此外,Lopatenko 等人[29]提出了基于否定約束(denial constraint,簡稱DC)的規則,進而對基于DC 的數據清洗修復方法進行了研究.Chu 等人也提出了基于DC 的全局修復算法Holistic.

然而,全局修復Holistic 作為一種支持速度約束的技術,僅可用于修復一般表格數據,因此無法支持流數據的在線清洗.而現今的數據分析技術及人工智能技術等更是需要對海量數據進行處理,全局修復方法無法提供相應的技術支撐.本文提出了給定窗口條件下基于多區間速度約束的局部修復方法以支持在線清洗,作為局部方法,本文方法更有利于大數據環境下的數據清洗問題,從而更便于后續的數據管理與分析技術以及人工智能技術.因此如實驗所示:與整體清洗相比,本文所提出的多區間速度約束方法最大可將時間成本降低兩個數量級.此外,順序依賴(sequential dependency)方法不能精確表達速度限制.Sequential 方法主要關注序列中兩個連續數據點的差異,而當數據點之間的時間間隔不同時,Sequential 所給出的依賴并不精確.而基于速度約束的SCREEN 方法僅考慮單一區間的速度約束,當速度約束涉及多個區間時,該修復方法將由于檢測修復不足或過度而無法達到較優的修復結果.

本文所提出的多區間的速度約束考慮了更具體的約束區間以得到更為精確修復結果.如第1.1 節例1 所示,車輛油位變化源于行駛耗油和補充加油兩種行為,考慮到車輛及油箱振蕩情況,那么油位變化速度將在[?1,1]以及[10,70]兩個區間內.單區間速度約束無法表示如此精確的約束條件,進而其修復結果也將產生較大誤差;而多區間速度約束方法將會對數據進行準確的約束,從而可以更廣泛合理地應用.如圖22 所示,本文使用多種約束方法對油耗數據集中100 個數據點進行修復.可以發現:Sequential 方法與SCREEN 方法有著一定的相似性,而由于Sequential 方法僅對連續兩點之間的數據距離進行約束,SCREEN 方法對兩點之間的速度(即考慮數據值及其時間戳之間的關系),所以SCREEN 方法相對更為精確.然而,由于SCREEN 方法只設置單個速度約束區間,一些正常點和異常點無法正確檢測區分.當區間設置為[?1,70]時,由于15:12 時刻一個異常點的的存在,導致后續多個正確值被誤修.而當區間設置為[?1,1]時,又會因為15:09 時刻的加油行為,而將后續大部分正常值誤判為異常值進行過度修復.同理,若將區間設置為[10,70],幾乎所有的點都會被過度修復從而對數據產生更嚴重的破壞.綜上可知,本文所提出的多區間速度約束修復方法可以滿足多速度閾值約束并給出較為精確的修復結果.此外,結合前述各數據集實驗結果可知,本文方法可以在遠低于Holistic 方法的時間開銷下產生更優的修復結果.

Fig.22 Repairing for constraint-based methods圖22 基于多種約束方法下的修復效果

6 結 論

考慮到一般情況下時間序列中時間戳與相應數據值之間具有較強的關聯性,本文提出了基于數據變化速度的多區間速度約束方法.該方法可通過多區間速度約束來獲取時間序列給定窗口內各數據點的速度約束范圍,進而對時序數據進行約束以檢測數據的異常情況.同時,上述多區間速度約束可對窗口內各數據點通過其后續點產生相應的修復候選點,進而本文可采用動態規劃方法從上述修復候選點中選取最優修復路徑,從而獲取修復結果,且該修復結果遵循最小修復原則.為對上述所提修復方法進行驗證,本文通過一個人工數據集、兩個真實數據集(油耗數據集以及GPS 數據集)以及一個具有真實異常的數據集(海拔數據集)來對本文方法及其他現有方法進行實驗.由實驗結果可知:與現存其他修復方法相比,本文所提出的基于多區間速度約束下的動態規劃修復方法遵循最小修復原則,且可應對較為復雜的數據狀況,從而在各異常率及數據量下均有著最低的RMS錯值,即修復效果最佳.同時,考慮到數據質量問題將對后續的數據分析及人工智能技術產生舉足輕重的影響,本文進一步使用多個數據集通過聚類及分類精確率對各方法進行了驗證.在該實驗結果中,本文所提多區間速度約束方法依然表現出了最優的修復效果,在各方法中分類精確率最高.此外,本方法在運行性能時間開銷方面也較為理想,遠低于基于約束的全局修復方法.