丁小歐,王宏志,靳賀霖,高 猛
(哈爾濱工業大學 計算機學科與技術學院,哈爾濱 150001)
目前,數據正以前所未有的速度不斷產生。隨著各種各樣數據采集設備的普及使用,海量的時序數據日以繼夜的被積累和使用。帶有時間標記的時間序列數據,能夠幫助分析人員對歷史記錄進行有效建模,通過整合相應時間段的有關資料,挖掘提煉有價值的信息。但是,實際的時序數據中廣泛存在數據質量問題。低質量的時態數據,不僅導致數據預處理環節需消耗大量人力物力成本,而且也會導致在實際應用數據挖掘與知識提取分析結果發生偏差和錯誤。隨著數據應用對數據質量要求的提高,時序數據的質量問題也逐漸引起研究領域和應用領域的更多關注,而數據清洗技術是提高時序數據質量的有效方法。
本文聚焦時序數據清洗研究中錯誤數據的檢測與修復兩個主要環節,對時序數據質量管理研究進展及研究現狀進行評析;介紹了通用數據清洗流程;分別介紹時序數據中的錯誤數據檢測、以及錯誤數據修復技術研究進展,并提出未來研究展望。
2002 年,在綜述文獻[1]中,國內首個對數據質量和數據清洗進行了全面分析介紹工作。隨后,在大數據高速發展的時期,數據可用性問題得到廣泛關注。圍繞著數據一致性、精確性、完整性、時效性、實體同一性這5 個核心問題,國內研究人員做了大量工作。2016 年,綜述文獻[2]對大數據可用性進行了深刻剖析,從表達機理、判定理論、演化原理等方面進行詳細介紹,并提出了量質融合管理、劣質容忍計算、深度演化機理等多個具有挑戰性的問題。結合數據質量研究中數據劣質的情況,已有多篇綜述[3-5]對數據錯誤類型進行了詳細分析。文獻[6]對大數據質量從數據質量評估、數據清洗、質量管理等多角度進行了詳細介紹;文獻[7]提出了“數據工程”的概念,介紹了以數據為主題而展開的各項數據處理技術。
而隨著中國現代化進程的發展,各行業領域已經積累并正在產生大量的時間序列數據,例如,在制造領域,現代化的傳感器設備、智能儀表[8]等,能夠實現對生產環境的感知,并對設備的生產狀態進行實時記錄。這些數據中隱含豐富的信息和知識,能夠為系統運行狀態的控制、分析、決策以及規劃提供重要的參考依據。然而,時序數據中的數據質量問題也非常普遍,重復記錄、異常記錄、無效數據、時標不齊等質量問題的存在,限制了對領域數據的深入分析[9]。低質量的工業時間序列數據的清洗,正逐漸成為研究熱點、重點和難點。近5 年來,時間序列清洗的研究呈快速增長趨勢。異常檢測、序列分類、序列模式挖掘等問題,在理論上和實踐中均得到廣泛研究。其中,異常和錯誤數據的識別與檢測是數據清洗和故障檢測研究領域的重點難點問題。
雖然研究人員在數據清洗上進行了長期的探索,取得了一定的理論成果,并投入應用進行實踐。但在時序數據清洗問題上,仍有許多關鍵問題丞待解決,其主要研究問題包括:
(1)時序數據在數據庫系統中存儲、拷貝、轉移,或者在信息系統中跨數據庫調用時,其時間標記(時間戳)可能發生丟失、不可用、時間不統一、時序錯亂、不對齊等問題,導致數據的部分時序信息丟失[9]。
(2)數據的多樣性和復雜性,導致數據中的錯誤模式增多?!芭K數據”產生緣由復雜,低質量數據中通常存在多種的錯誤類型,其中的關聯關系仍然缺乏理論認識[10-11],且對于多種錯誤共存的數據清洗、檢測和修復“臟數據”的計算復雜性會大幅增加[2]。
而目前時序數據清洗研究的不足之處主要包括:
(1)時間序列數據與行業聯系緊密,大量的時序數據通常體現較為明顯的領域特征[12],難以建立通用的理論計算框架。以工業場景為例,時間序列數據的來源廣泛,具有大體量、多源性、連續采樣、價值密度低、動態性強的特點[13]。不同的時間序列模式難以區分。時間序列的值異常情況難以描述和評價,容易引起誤判、漏判。
(2)數據之間相關性考慮不夠充分。在傳感器采集的多維時序數據中,屬性之間具有一定的相關性。多維時序數據中的錯誤模式常有隱匿性強、成因復雜的特點。因此,若僅對每條序列進行獨立的異常檢測,會導致無法準確地識別出一些真正的錯誤問題。序列之間的相關關系和依賴關系有多種類型[14],這些還未被充分地研究。
(3)領域知識尚未得到充分利用。對數據質量問題發生原因和影響關系的挖掘與分析,離不開領域知識的參與。雖然目前知識驅動的異常數據檢測技術,如專家系統(expert system ES)[15]、動態貝葉斯網絡模型(Dynamic Bayesian Network DBN)[16]、知識庫與知識圖譜[17]等已開始被應用于異常診斷和數據清洗問題中,但基于知識的方法往往僅適用于具體的問題,模型方法的遷移性較低。除此之外,領域知識的不完整性和模糊性也加大了知識建模的難度。
(4)方法缺少可擴展性。對數據質量問題的定位、產生原因、模式之間關聯性的計算分析過程,通常需要大量的計算,且高維度和大規模數據會導致模型的計算代價較高[18-19];另一方面,知識模型的局限性也限制了方法的可擴展能力。數據量之大、數據更新之快,使得方法難以實現在可接受的時間范圍內,有效地完成數據質量管理任務。
數據清洗(或稱數據凈化、數據清潔等)是指,對數據集合中存在的不符合規范數據的檢測,并進行數據修復,提高數據質量的過程[6,20]。錯誤數據(或稱臟數據),均造成了對給定數據質量評價的違反結果[4,21]。而錯誤數據的取值,常被認為與真值存在較大距離。數據清洗通常作為數據預處理環節的必要步驟,是公認的修復數據錯誤、提高數據質量必要的有效手段[6,21-22]。
近十幾年來,已有多篇綜述文章及專著(文獻[21-25])從不同的角度和場景需求,對數據清洗技術進行總結和介紹。文獻[21]中總結了傳統數據清洗的典型流程,主要包括錯誤數據檢測和錯誤數據修復兩個核心步驟。此外,數據清洗規則挖掘與提取也是數據清洗流程中可選的重要步驟。傳統數據清洗流程如圖1 所示。
圖1 傳統數據清洗流程[21]Fig.1 A typical data cleaning workflow[21]
文獻[26]從定量和定性兩方面,總結了常見的數據錯誤類型。其中,定性錯誤數據(Qualitative error)包括重復記錄、規則違反、模式違反3 個類型;定量錯誤(Quantitative error)主要包括異常值、離群點等類型。
2019 年,綜述文章[25]中介紹了時間序列數據上的錯誤類型,并歸納總結了當前常用的時間序列數據清洗方法。相比于傳統關系型數據清洗研究對“數據修復”的側重,目前的時序數據清洗主要以錯誤數據檢測、異常值、離群點檢測為主。
錯誤數據檢測是任何數據清洗任務中首要且關鍵的一步,只有對“臟數據”檢測準確,才能實現有效的修復。文獻[21,24]中提出,在數據清洗的檢測階段,關鍵在于檢測什么(What to detect)、怎樣檢測(How to detect)、何時檢測(When to detect)。
在定性錯誤檢測技術研究中,目前形成了以完整性約束作為主要檢測標準的方法體系。例如,針對FDs 的違反檢測[27]、基于否定約束的檢測方法[28]等。在檢測方式上,主要分為算法自動化檢測和人工參與檢測。典型的自動化檢測方法研究的文獻有[27]、Holoclean 方法[28,29]、DBRx 方法[22];人工參與的檢測有基于眾包方法,例如,CrowdER[30]、Corleone[31],以及錯誤數據的解釋方法Scorpion[32]、視圖條件因果溯源(View- conditioned causality tracing)[33]等等。
對數據進行錯誤檢測階段,通常采用異常檢測技術,目標是發現數據中不尋常的、未知的數據值或模式。在異常檢測領域研究中,數據中的異常主要表現為3 類:點異常(point outliers)、(上下文)內容異常(contextual outliers)、聚集型異常(collective outliers)。文獻[34]中將時間序列上的異常分為點異常和結構異常兩種。點異常有加性異常點(additive outlier AO)、創新性異常點(innovational outlier IO)兩種表現形式。結構異常有水平偏移(level shift LS)、方差變化(variance change VC)兩種類型。其中,水平偏移可進一步分為永久性水平變化和瞬時水平變化。文獻[25]將時間序列數據錯誤類型分為4 種:單點小錯誤(single small error)、單點 大 錯 誤(single large error)、連 續 性 錯 誤(continuous errors)和傳輸偏移錯誤(translational error)。
由于點異常通常是以較低頻率出現在數據中,離散的異常點出現具有偶然性。在實際的數據場景中,異常的表現形式往往復雜多變,這就需要對數據點的“長度”和“寬度”加以分析。
2002 年,文獻[35]較早地發現,簡單的點異常檢測方法,難以滿足復雜的實際需求,提出了異常模式(anomalous patterns)的概念,并提出了一個基于規則的異常檢測算法。將每一種異常模式總結為一條規則,每條規則由若干個組件取邏輯“AND” 組成。對于每個組件所包含的每個特征值,比較當前日期的記錄與歷史記錄的差異,并利用統計學方法,對規則上的取值進行評分分析。由于計算限制,文獻[35]中使用的每條規則最多只包含2 個組件。在近十幾年的研究中,時序數據上的序列模式挖掘問題(sequence patterns discovery)一直被研究人員關注[36-37]。
2005 年,文獻[36]提出HOT SAX(Symbolic Aggregate approXimation)這一經典的不尋常子序列挖掘方法;文獻[37]提出了基于K-means模型的階段性時序數據的異常檢測方法。在異常模式檢測的研究中,通常以無監督學習模型為主,而由于不同領域的時序數據模式復雜、多樣,異常序列片段檢測問題仍然面臨許多瓶頸性的挑戰。
隨著單維時間序列數據(Univariate time series UTS)異常檢測研究的深入展開,近年來研究人員也將更多的關注點放在多維時間序列數據上(Multivariate Time Series MTS)。相比于單維時序數據,變量(即維數)的增多使得異常模式樣式也隨之增多,異常數據模式更加多樣、復雜,且識別難度也更高。因此,不僅要將單維序列的異常檢測方法包含在內,還需進一步考慮多個變量之間的相關性等問題。研究MTS 的異常檢測方法時,通常面臨以下問題[38]:一是多維數據的屬性可能是異構、多樣的;二是不同屬性對判斷異常(事件)的“貢獻性”程度不同;其三,異常事件實例的數量往往非常有限。
面對上述難題,在進行MTS 異常檢測時,通常采用統計指標與機器學習模型相結合[37]的方法。有部分文獻利用分類問題模型解決多維時序數據異常檢測,例如決策樹、支持向量機[39]、神經網絡等。這些分類方法通常需要一定規模的異常實例作為訓練數據,對訓練樣本的需求成為樸素分類模型解決異常檢測的一個局限因素。文獻[38]研究了異構時間序列上的異常模式挖掘方法,將數據中異構的屬性轉化成同構的異常評分序列,并用異常評分向量來表示每個故障事件;然后迭代地優化異常模式的特征參數。優化原則主要包括:最大化分離異常模式和正常模式的距離、最大化分離疑似異常實則正常的模式和真實異常模式的距離,以及最小化異常評分向量的平方損失函數。在測試階段,計算異常評分參數與已訓練的異常模式的匹配度,實現對故障的(分類)診斷。
針對多維數據檢測的效率問題,文獻[40]提出了基于kNN 方法的多維異常檢測算法,并利用異常評分機制對觀測點及其鄰居數據的“分離度”進行量化,并采用低階近似方法(low- rank approximation)將高維數據映射到低維空間,實現算法效率上的提升。文獻[41]提出了一種基于分支界限(Branch and Border)的非參數的異常檢測算法,其能在線性時間內實現對數值型、分類型等混合類型時序數據的檢測,并在11 個時序數據集上進行了實驗,驗證了該方法具有較強的有效性和可擴展性。
在實際問題中,異常數據和正常數據難以被簡單地區分開[42]。目前的異常檢測方法通常具有一定的專門性,在通用性和可遷移性的技術突破存在較大難度。雖然近些年異常檢測問題在理論和實際應用中得到了大量的研究,但許多關鍵問題仍未完全解決。相比于傳統關系型數據,時序數據屬性多以數值型為主。因此,時序數據上具有更多、更復雜的錯誤模式。此外,時序數據具有時間屬性,使得許多錯誤模式具有一定的聚集和累積效應,這給序列建模和異常識別均帶來不少的難度。
相比于檢測步驟對錯誤數據“識別”效果的側重,修復步驟的關鍵之處在于如何對錯誤數據進行合理、有效的修復。類似于錯誤數據檢測步驟,錯誤數據的修復研究同樣聚焦于修復目標(What)、修復形式(How)和修復模型(Where)上。在修復目標上,主要有數據驅動、基于規則、以及基于數據和基于規則的融合方法[24]。
相比于時序數據的錯誤檢測,時序數據的清洗研究還尚不完備。文獻[43]中介紹了大數據上定量數據錯誤的清洗方法,將時間序列數據的清洗作為一個特殊場景進行討論。結合時態數據的清洗理論基礎和實產經驗,目前已有的方法主要以基于統計模型和基于約束為主。平滑噪聲(smoothingbased cleaning)是一種常見的數據修復方法。通過調整滑動窗口,計算給定指標,實現對異常部位的平滑修復。常見方法有:滑動平均[44](simple moving average,SMA)利用當前時間點前K個數據點上的取值,做不加權計算;指數加權平均[45](exponentially weighted moving average,EWMA)是對簡單滑動平均的改進。由于距離近的時間點取值的相關性更強,因此對序列進行兩次加權取值計算。平滑的方法雖然簡單常用,但其準確率較低。不同類型時間序列數據的情況復雜,僅僅用上下文相關性進行平滑,無法對持續的異常片段進行準確修復?;贏RIMA模型也是時間序列上的基礎方法,包括了自回歸過程(autoregressive)、滑動平均過程(moving-average)分析等。
基于約束的清洗技術不僅廣泛應用于傳統關系型數據,而且同樣適用于時間序列的數據清洗問題。但是,相比于傳統關系型數據,針對時間序列數據的約束種類不多。相比于傳統關系型數據,時態數據通常具有發展規律、變化趨勢、自相關性、季節性等特點。因此,在時態數據上的約束設計也需要考慮更多因素。文獻[14]聚焦時態數據質量管理,將用于識別錯誤數據的約束分為4 類(見表1),并提出了時態數據質量管理的通用方法。首先,歸納定義出高質量數據需滿足的規則約束條件,將時刻t上高質量數據記為;然后,將測試數據Dt與高質量數據進行比較??衫梦墨I[46]提出的統計失真(statistical distortion)指標,度量測試數據Dt和理想數據之間的差異,即SD(Dt)=Dist(Dt,),找出違反約束的數據。經約束初步檢測出的違反數據(violation)也被稱為小錯誤(glitch)[47]。需要注意的是,利用約束檢測出來的小錯誤并不一定是真正的錯誤,可能是約束參數值設置過于嚴格所導致的誤判。因此,對于違反數據通常需進一步分析、解釋后,再決定如何對其進行處理。
表1 約束種類Tab.1 Types of constraints
相比于傳統關系型數據,針對時間序列數據的約束種類不多。其中,文獻[48]提出了順序依賴(Order Dependencies ODs),ODs 同樣適用于時間序列的清洗。在順序依賴的基礎上,文獻[49]針對序列數據,提出了序列依賴(Sequential dependencies SDs),表示為X→→gY。描述了在以屬性X排序時,連續兩條記錄上屬性Y的取值變化范圍為g。通常,X是數據庫模式R上的一個有序屬性,記錄在屬性Y上的取值是可比較的。序列依賴是目前可用于時間序列清洗問題僅有的約束之一。
由于序列依賴主要針對有序數據集而設計,未對數據的時間戳屬性給予充分考慮。SDs 乃至CSDs 對于相鄰記錄之間某屬性的取值要求較為理想化,難以滿足實際中的數據清洗需求。張奧千[52]等人在序列依賴的基礎上,提出了速度約束。文獻[50-51]還提出了基于速度約束的時間序列清洗問題,并介紹了基于最小修復原則的數據清洗方法。速度約束在識別并修復時間序列數據中的大錯誤效果更好,而在對數據上的小錯誤以及連續性錯誤的識別上具有局限性。文獻[52]提出了基于方差約束的修復方法,以最小修復為原則,找到滿足給定方差約束的修正序列。
考慮到修復方法,通常有兩類策略:一是完全信任給定的約束集,只對數據進行修改和修復;二是不完全信任已有的約束(參數取值),對數據和約束都會進行修正。對于前者,大部分的修復方法通常每一次只針對同一類錯誤問題進行修復。一般采用最小修復原則[51],對原始數據D修改為D',并使Cost(D,D')最小。這里的Cost通常是距離函數或具有距離函數類似性質的代價函數。近年來,Ihab F.Ilyas 等人提出了全面數據清洗(Holistic data cleaning)方法[28-29]。文獻[53]認為在現實問題中,數據會隨時間發生改變,導致既定的約束變得不再準確。因此,提出了約束& 數據的聯合修復模型。運用函數依賴,同時考慮利用約束或者數據本身對違反部分進行修改;并且設計算法實現對約束的更新和修改。由于約束集不總是完備且準確的,文獻[54]研究了允許約束小范圍變化的數據修復方法,提出一個θ-容忍的修復模型。在修復時,允許約束謂詞在θ范圍內的增加和刪除。
數據清洗問題的特點,導致所采用的清洗指標通常是與場景高度相關的,需要用戶、領域知識、問題背景等多方面因素的共同作用,才能實現高質量的數據修復[46]。高質量的數據清洗任務離不開人工的參與。因此,近年來研究人員也在數據清洗研究上展開了更多創新性研究,各類人工參與的修復方法逐漸豐富,Yakout 等人較早引入機器學習方法提升數據清洗的可靠性,并提出GDR(guided data repair)模型[55];綜述文獻[23]介紹了該方法主要包括基于CFD 的臟數據識別、更新策略生成、更新策略排序、基于用于反饋的訓練模型步驟。典型的人工參與的數據清洗系統還有KATARA[17]、Data Tamer[57]等。
在大數據的清洗過程中,有時可靠的數據清洗規則不能輕易獲取。因此,研究人員展開了直接在劣質數據上進行學習和分析的方法。文獻[58]提出了一種從劣質數據中進行學習的方法Dirty Learn(DLearn)。大數據技術的普及和發展,使得許多大數據管理與分析問題變得更為領域化、專業化,這對數據的領域知識背景提出了更多的要求。文獻[59]介紹了人在回路的數據準備技術研究(humanin-the-loop data preparation)進展。近年來,人在回路數據清洗技術的關鍵點主要在于人機交互和眾包清洗策略(crowdsourcing data cleaning)兩方面。在人機交互方面,文獻[56]提出了FALCON 系統,依靠與用戶的交互實現對數據修復。在眾包方法的研究上,文獻[17]提出了基于知識庫和眾包的數據清洗系統——KATARA,旨在彌補既定完整性約束和模型驅動的數據清洗在效果上的局限性,通過訪問主數據或詢問領域專家,來解決數據中的歧義問題。
在以時序數據為主要數據類型的清洗研究中,錯誤數據檢測的研究要比錯誤數據修復的研究更加全面。而在目前的修復方法中,依賴于傳統的統計模型方法居多。但是,簡單修復結果的精準度難以滿足實際要求。由于以OD、SD、SC 為例的約束模型才被提出不久,時序數據修復的理論方法仍需完善。此外,雖然目前已有人工參與的清洗方法被使用,但人機結合的清洗研究中仍有許多關鍵問題未被解決。
本文介紹了目前時序數據質量管理以及時序數據清洗的研究進展,針對錯誤數據檢測以及錯誤數據修復技術進行現狀研究分析。在影響時序數據清洗研究的因素中,既有技術層面,又有管理層面,而對數據質量的評估中,既有主觀維度,又有客觀維度。綜合目前的實際需求,時序數據清洗的未來研究方向包括:
(1)繼續深入考慮數據、錯誤模式之間相關性計算問題;
(2)研究多源、復合型的數據質量管理及數據清洗方法體系;
(3)結合機器學習模型研究智能化的錯誤數據檢測方法,實現對未知、復雜模式的錯誤數據識別;
(4)繼續探索人工參與的數據清洗方法,提高錯誤數據修復的可靠性、準確性;
(5)結合知識工程相關技術,實現對領域知識的有效建模,實現知識融合的數據清洗模型,提高數據清洗結果的可解釋性和有效性。