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

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

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

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

1 引 言

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

1.1 問題背景

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

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

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

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

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

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

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

1.2 主要貢獻(xiàn)

本文主要貢獻(xiàn)如下:

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

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

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

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

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

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

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

2 基礎(chǔ)定義

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

2.1 時(shí)間序列定義

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

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

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

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

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

2.3 修復(fù)結(jié)果定義

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

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

2.4 問題定義

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

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

3 動(dòng)態(tài)規(guī)劃修復(fù)方法

3.1 速度約束范圍的確定

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

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

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

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

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

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

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

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

3.2 修復(fù)候選點(diǎn)的確定

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

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

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

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

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

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

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

證明:令ω=|{i|tk

(1)若修復(fù)后xi未改變,即,此時(shí)xi點(diǎn)修復(fù)距離為0,如圖8 所示;

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

Fig.8 between two continuous candidates,,without moving xi圖8 介于兩相鄰候選點(diǎn)之間,無需修復(fù)

Fig.9 between two continuous candidates,圖9 介于兩相鄰候選點(diǎn)之間,

Fig.10 between two continuous candidates,圖10 介于兩相鄰候選點(diǎn)之間,

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

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

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

(c)當(dāng)情況(2)中xi的個(gè)數(shù)小于情況(3)中xi的個(gè)數(shù),選擇cj作為相應(yīng)的總修復(fù)距離為

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

3.3 修復(fù)路徑的確定

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

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

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

其中,tk≤ti

其中,tk≤ti

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

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

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

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

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

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

Fig.13 Graph of repairing path圖13 修復(fù)路徑圖

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

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

? 速度約束范圍的確定

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

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

? 修復(fù)候選點(diǎn)的確定

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

? 修復(fù)路徑圖的確定

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

3.5 算 法

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

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

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

輸出:修復(fù)后的時(shí)間序列x′.

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

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

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

4 實(shí) 驗(yàn)

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

4.1 實(shí)驗(yàn)設(shè)置

? 實(shí)驗(yàn)環(huán)境

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

? 實(shí)驗(yàn)數(shù)據(jù)

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

4.2 評價(jià)標(biāo)準(zhǔn)

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

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

4.3 現(xiàn)有方法

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

4.4 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 相關(guān)工作

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

5.1 基于平滑的修復(fù)方法

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

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

5.2 基于約束的修復(fù)方法

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

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

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

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

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

6 結(jié) 論

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