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

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

2(大數(shù)據(jù)系統(tǒng)軟件國家工程實驗室,北京 100084)

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

1 引 言

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

1.1 問題背景

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

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

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

Fig.1 Example of fuel consumption data圖1 油耗數(shù)據(jù)示例

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

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

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

1.2 主要貢獻

本文主要貢獻如下:

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

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

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

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

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

1.3 論文結(jié)構(gòu)

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

2 基礎定義

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

2.1 時間序列定義

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

2.2 多區(qū)間速度約束定義

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

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

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

2.3 修復結(jié)果定義

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

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

2.4 問題定義

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

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

3 動態(tài)規(guī)劃修復方法

3.1 速度約束范圍的確定

給定多區(qū)間速度約束S,窗口w,窗口內(nèi)起始數(shù)據(jù)點xk以及窗口內(nèi)各點xk,xk+1,xk+2,…,xk+ω,0

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

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

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

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

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

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

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

3.2 修復候選點的確定

通過觀察數(shù)據(jù)點與速度約束之間的關系可以發(fā)現(xiàn),速度約束S可以與數(shù)據(jù)點xi(tk≤ti

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

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

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

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

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

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

證明:令ω=|{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 介于兩相鄰候選點之間,

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

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

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

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

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

3.3 修復路徑的確定

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

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

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

其中,tk≤ti

其中,tk≤ti

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

同理,此修復候選點對后續(xù)點產(chǎn)生的修復范圍中若包含已有候選點,則依舊可根據(jù)該候選點選擇最優(yōu)修復路徑;反之,若已有候選點未在該修復范圍之內(nèi),則可按理論2 生成后續(xù)點的修復候選點,且該條路徑的修復距離最小.

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

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

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

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

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

3.4 特例:單區(qū)間速度約束

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

? 速度約束范圍的確定

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

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

? 修復候選點的確定

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

? 修復路徑圖的確定

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

3.5 算 法

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

算法1.基于多區(qū)間速度約束的動態(tài)規(guī)劃修復方法.

輸入:順序時間序列x,時間窗口w,起始數(shù)據(jù)點xk,多區(qū)間速度約束S;

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

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

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

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

4 實 驗

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

4.1 實驗設置

? 實驗環(huán)境

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

? 實驗數(shù)據(jù)

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

4.2 評價標準

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

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

4.3 現(xiàn)有方法

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

4.4 實驗結(jié)果

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

(1)人工數(shù)據(jù)集

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

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

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

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

關于不同數(shù)據(jù)量下的修復結(jié)果,觀察圖16 可以發(fā)現(xiàn),與不同異常率下的修復結(jié)果較為一致,多區(qū)間速度約束方法在RMS 錯值方面有著最優(yōu)的修復效果,且多區(qū)間速度約束方法與全局Holistic 方法在RMS 錯值方面遠低于SCREEN 方法及Sequential 方法.

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

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

(2)油耗數(shù)據(jù)集

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

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

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

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

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

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

(3)GPS 數(shù)據(jù)集

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

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

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

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

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

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

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

(4)海拔數(shù)據(jù)集

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

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

(5)UCR 數(shù)據(jù)集

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

Fig.21 Classification accuracy under different UCR datasets圖21 UCR 數(shù)據(jù)集分類精確率

5 相關工作

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

5.1 基于平滑的修復方法

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

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

5.2 基于約束的修復方法

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

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

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

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

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

6 結(jié) 論

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