時空大數據的缺失數據流關聯修復仿真

關玉欣，李雷孝

(內蒙古工業大學數據科學與應用學院，內蒙古 呼和浩特 010080)

1 引言

大數據中的數據缺失和來源復雜，導致數據易出現錯誤，給數據處理帶來很大的困難。為避免以上問題，提升自身的使用價值，發揮最大作用，需要對缺失數據進行修復[1]。傳統修復缺失數據的方法一般可分為兩大類：單獨修復法和多目標修復法[2]。單獨修復法包含人工修復法、均值修復法、回歸修復法、冷熱平臺修復法等等。多目標修復法包括隨機回歸修復法、趨勢得分修復法等。從修復的手段來看，均是采用語義規則和統計學理論實現的。這些方法在隱蔽規則探索方面研究不夠透徹，因此還需更加深入分析和研究。對數據的處理在該領域具有很重要的意義，很多相關學者針對數據已經研究出了很多成果。文獻[3]提出基于去除噪聲自編碼網絡的缺失大數據修復方法。該方法通過堆疊去除噪聲干擾的方法，創建自編碼網絡以提取監測數據之間的關聯關系，以這種關聯關系對數據進行訓練，建立支持向量模型對缺失大數據進行檢測，進而對缺失數據進行修復。文獻[4]提出一種基于時空大數據的收縮近鄰缺失數據流修復方法。該方法可分為三部分，第一部分是基于提取的數據樣本和數據特征變量的缺失比值，將該比值應用于對缺失數據的采樣作為入樣概率，并通過該概率實現對數據不等概的收縮；第二部分是基于提取數據樣本之間的距離，挑選出與缺失數據樣本相似的樣本組合成樣本訓練集，最后一部分是創建隨機森林模型，并對缺失數據樣本進行迭代填補修復。文獻[5]提出一種基于全景調整控制統一化數據模型的缺數數據修復方法，該方法針對創建全景數據中存在的低質量數據，運用改進的遺傳優化方法對低質量和不完整數據的均值和協方差進行估計，得出最佳參數；再采用Markov Chain Monte Carlo方法根據估計得出的最佳參數進行缺數數據修復。文獻[6]提出基于分塊填補的缺失數據修復方法。該方法的主要目的是對缺失數據進行分塊處理，單運用和待修復數據具有相似性的數據進行填補修復，進而減少無關數據對缺失數據修復造成的影響。

上述相關學者研究出的修復方法，存在修復過程復雜，且經過這些方法修復的數據仍然存在數據漏洞，修復準確度較低?，F提出一種基于時空大數據的缺失數據流關聯修復方法。經過仿真證明，本文提出的方法能夠更準確地計算缺失數據，并在最短的時間內對其進行高效、準確地修復，令修復結果更接近原始的時空大數據的數據流，具有較高的可行性和可信度。

2 時空大數據的缺失數據流修復方法

2.1 數據流之間的關聯規則

首先對數據之間的關聯規則和條件函數進行設定[7]，然后對有效的規則與條件函數依賴相等、規則可信度由置信度決定兩方面進行證明。

數據之間的關聯規則就是數據處理的核心思想，對其進行設定具體如下：

關聯規則可通過以下方式進行表述：設I={I1，I2，…，In}是一個任務集合，T={T1，T2，…，Tm}表示一個事件數據集合，事件數據集合中的任意事件Ti均是單獨的任務集合，即Ti?I。關聯規則的蘊含關系如下：X→Y，其中X?I，Y?I，且X∩Y=φ。X(或Y)是一個任務的集合，叫做事務集，將X為前件任務，Y為后件任務。當關聯規則X→Y存在時，X成立，則Y也會成立。

針對關聯規則的條件函數依賴可用于數據處理，在數據庫修復上應用廣泛[8]。假設數據之間存在一定關系R，a(R)代表設定在這層關系上的屬性集，并對每個屬性A，滿足A?a(R)，A的取值范圍表示為d(A)，設定在R上的條件函數依賴φ表示為φ：(R：X→Y，Tp)。

其中：X和Y是設定在a(R)的屬性集；{R：X→Y}表示一個標準的函數依賴；Tp是和X與Y相似的模式元素組，設定了相似屬性在取值范圍方面的約束條件。

證明關聯規則和條件函數依賴相等的具體步驟如下：

關聯規則R：X→Y可以視為關系模式R的條件函數依賴。

綜上所述，進一步對關聯規則R：X→Y進行表達

R：X→Y≡[Ai=Ii，Ai+1=Ii+1，…，Ai+n=Ii+n]

→[Aj=Ij，A+1=Ij+1，…，Aj+n=Ij+m]

(1)

關聯規則X→Y和條件函數依賴相同的表達式為

φ：[Ai=Ii，Ai+1=Ii+1，…，Ai+n=Ii+n]

→[Aj=Ij，Aj+1=Ij+1，…，Aj+m=Ij+m]

(2)

由此關聯規則得以證明：條件依賴取決于關聯規則R：X→Y，該規則的挑選原則：R：X→Y具有超高的置信度，同時不會要求過高的支持度。

對上述設定進行證明的具體過程如下

令支持度減小，可發現較多的關聯規則，若支持度較高，則發現的關聯規則較少；當關聯規則R：X→Y轉換成條件函數依賴，如式(2)，那么本文研究的以數據X修復Y為目的，就需要X和Y同時被發現的概率較高。

X→Y支持度的計算公式如下

(3)

式中：s(X)為X的支持度，s(XY)為X，Y的支持度，當c(X→Y)過高時，則X和Y同時被發現概率也較高，由此可見上述設定可被驗證。

挑選較小的支持度、較高的置信度來提升可信關聯規則的數目，由此可搜尋到較多的條件函數依賴。就是依據數據的實際修補需要，運用合理地降低支持度的方法來發現更多的與缺失數據屬性相似的關聯規則，以此來實現對缺失數據的填補和修復，提升數據的使用性。

2.2 缺失數據填補修復

根據2.1節提到可通過數據之間的屬性關聯，實現對缺失數據的修復。針對不同時空大數據之間的時間、空間和屬性方面的關聯性，對時空大數據Si和目標數據對象Sk之間的時空相似度進行計算，計算公式如下

(4)

(5)

(6)

(7)

式中：s代表時空大數據的時間維數，l代表時空大數據的數據流相應位置，|l|代表時空大數據的位置維度，|Di|代表時空大數據屬性的鄰域維度，hT、hS、hA均代表相應維度的劃一因子。時空大數據之間的維度相似程度越大，數據越相似。時空大數據在時間、空間和屬性之間的相似度就是數據之間的最佳相似度[9]。

可通過時空大數據之間的相似度，實現對數據在時間、空間和屬性的互相彌補，以保留較多的數據臨界點，從而緩解時空大數據集中數據流出現連續缺失的情況[10]，臨界點數據發生缺失而不能被修復的情況。

針對缺失目標對象sr，挑選出一個特定的數據對象sz，將二者之間的相似度結合在一起，對數據sr的加權值進行計算，數據的加權值可實現對缺失數據sr和相應的數據臨界點的相似度的結合。數據的加權值計算公式如下

(8)

式中：N(sr)代表目標缺失對象對應的數據臨近點集，Sz代表缺失數據sr和特定數據sz之間的相似性。數據加權值wsr的數值過大，說明缺失數據和相應的數據臨界點的結合效果越好，可用于修復缺失數據的完整數據越多。

針對一個包括t個缺失對象可能的修復順序x，列出所有不同的排序，并利用Bayes聯合概率對排序的置信度進行計算，Bayes聯合概率公式如下

(9)

式中：sN(r)表示用來修復缺失對象sr的數據臨界點集。在對修復順序進行確定之后，后續修讀的數據臨界點不是固定的，缺失對象的加權值也隨之發生變化。p(sr|sN(r))表示用來修復缺數sr的臨界值中添加sN(r)后得出的加權值。

當集合sN(r)為空集時，可對p(sr|sN(r))進行簡化，變成p(sr)，可得出：缺失數據sr的加權值為p(sr)=wsr；當集合sN(r)為非空集合時，結合式(8)可得到

(10)

待修復順序確定后，對缺失部分進行修復。采用時空大數據相似度結合關聯規則修復算法對缺失數據進行修復值msr進行計算，計算公式如下

(11)

式中：a(sN(r))代表用于修復缺失目標對象sr的數據臨界點集的平均值。

由實驗可知，在最短的時間內對缺失數據填補進行高效、準確地修復，修復結果更接近原始的時空大數據的數據流，準確性更高。

3 仿真證明

在計算機上建立實驗平臺，采用Matlab和C語言作為實驗的開發工具，并編寫算法程序。實驗對象選用STD數據庫(Spatial-Temporal Database， 時空數據庫)中的數據，并將數據隨機分為四組，該數據庫專門用來測試數據挖掘技術的公共數據庫，數據庫中有明確的分類，因此可用來驗證本文缺失數據修復的效果。

為了驗證本文研究的修復方法的可行性和可信度，將基于時空大數據的收縮近鄰缺失數據流修復方法、基于分塊填補的缺失數據修復方法和本文所提修復方法進行對比實驗，通過根均方值誤差C和準確度百分比P(單位：%)作為指標評價三種方法。

根均方值誤差(C)的計算公式如下

(12)

準確度百分比(P)的計算公式如下：

(13)

式中：m表示所有缺失數據中達到準確修復的數據數量，h表示修復數據集中缺失數據的數量。該值越大，修復效果越好。

3.1 實驗結果

圖1 不同方法對數據集修復的均方值誤差對比

圖1為不同方法對四組數據集修復的均方值誤差對比，表1為不同方法對隨機抽取一組數據修復的準確度百分比對比。

根據分析上述四組數據修復效果圖可知：由圖1(a～d)可以看出，基于時空大數據的收縮近鄰缺失數據流修復方法在整體上明顯高于其它兩種方法，由此可說明該方法的修復效果不如其它兩種方法的修復效果；對于基于分塊填補的缺失數據修復方法，直觀來看該方法整體別的變化趨勢忽高忽低，狀態不平穩。說明該方法的準確性不能保證；而對于本文研究的修復方法，能夠準確高效地檢測出缺失數據，并加以修復。由圖1可以看出，C值均低于其它兩種方法，說明本文研究的修復方法具有較高的修復準確性，且具有明顯優勢。

表1 不同方法對數據集修復的準確度百分比對比

分析表1可知：準確度百分比用于衡量方法的準確性，由表1可以看出，分塊填補方法的準確度最低，準確度百分比最高值僅為62.08%；收縮近鄰法的準確度百分比最低值為53.79%，最高值為84.23%，這兩種方法的準確度百分比最高值均低于本文研究方法的準確度百分比最低值，由此說明，本文研究的修復方法具有較高的可信度，且修復效果較好。

4 結束語

為了更好地使數據發揮其最大的作用，提升自身的使用價值，需要對大數據中缺失部分進行修復。針對現有方法存在的不足之處，提出一種針對時空大數據的缺失數據流關聯修復方法。利用數據之間的關聯特性，結合數據缺失填補方法，對缺數數據流進行缺失修復。并通過仿真證明，本文研究的修復方法能夠更準確地計算缺失數據，并在最短的時間內對其進行高效、準確地修復，令修復結果更接近原始的時空大數據的數據流。