時空大數(shù)據(jù)的缺失數(shù)據(jù)流關(guān)聯(lián)修復(fù)仿真

關(guān)玉欣，李雷孝

(內(nèi)蒙古工業(yè)大學(xué)數(shù)據(jù)科學(xué)與應(yīng)用學(xué)院，內(nèi)蒙古 呼和浩特 010080)

1 引言

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

上述相關(guān)學(xué)者研究出的修復(fù)方法，存在修復(fù)過程復(fù)雜，且經(jīng)過這些方法修復(fù)的數(shù)據(jù)仍然存在數(shù)據(jù)漏洞，修復(fù)準確度較低。現(xiàn)提出一種基于時空大數(shù)據(jù)的缺失數(shù)據(jù)流關(guān)聯(lián)修復(fù)方法。經(jīng)過仿真證明，本文提出的方法能夠更準確地計算缺失數(shù)據(jù)，并在最短的時間內(nèi)對其進行高效、準確地修復(fù)，令修復(fù)結(jié)果更接近原始的時空大數(shù)據(jù)的數(shù)據(jù)流，具有較高的可行性和可信度。

2 時空大數(shù)據(jù)的缺失數(shù)據(jù)流修復(fù)方法

2.1 數(shù)據(jù)流之間的關(guān)聯(lián)規(guī)則

首先對數(shù)據(jù)之間的關(guān)聯(lián)規(guī)則和條件函數(shù)進行設(shè)定[7]，然后對有效的規(guī)則與條件函數(shù)依賴相等、規(guī)則可信度由置信度決定兩方面進行證明。

數(shù)據(jù)之間的關(guān)聯(lián)規(guī)則就是數(shù)據(jù)處理的核心思想，對其進行設(shè)定具體如下：

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

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

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

證明關(guān)聯(lián)規(guī)則和條件函數(shù)依賴相等的具體步驟如下：

關(guān)聯(lián)規(guī)則R：X→Y可以視為關(guān)系模式R的條件函數(shù)依賴。

綜上所述，進一步對關(guān)聯(lián)規(guī)則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)

關(guān)聯(lián)規(guī)則X→Y和條件函數(shù)依賴相同的表達式為

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

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

(2)

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

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

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

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

(3)

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

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

2.2 缺失數(shù)據(jù)填補修復(fù)

根據(jù)2.1節(jié)提到可通過數(shù)據(jù)之間的屬性關(guān)聯(lián)，實現(xiàn)對缺失數(shù)據(jù)的修復(fù)。針對不同時空大數(shù)據(jù)之間的時間、空間和屬性方面的關(guān)聯(lián)性，對時空大數(shù)據(jù)Si和目標數(shù)據(jù)對象Sk之間的時空相似度進行計算，計算公式如下

(4)

(5)

(6)

(7)

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

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

針對缺失目標對象sr，挑選出一個特定的數(shù)據(jù)對象sz，將二者之間的相似度結(jié)合在一起，對數(shù)據(jù)sr的加權(quán)值進行計算，數(shù)據(jù)的加權(quán)值可實現(xiàn)對缺失數(shù)據(jù)sr和相應(yīng)的數(shù)據(jù)臨界點的相似度的結(jié)合。數(shù)據(jù)的加權(quán)值計算公式如下

(8)

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

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

(9)

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

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

(10)

待修復(fù)順序確定后，對缺失部分進行修復(fù)。采用時空大數(shù)據(jù)相似度結(jié)合關(guān)聯(lián)規(guī)則修復(fù)算法對缺失數(shù)據(jù)進行修復(fù)值msr進行計算，計算公式如下

(11)

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

由實驗可知，在最短的時間內(nèi)對缺失數(shù)據(jù)填補進行高效、準確地修復(fù)，修復(fù)結(jié)果更接近原始的時空大數(shù)據(jù)的數(shù)據(jù)流，準確性更高。

3 仿真證明

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

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

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

(12)

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

(13)

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

3.1 實驗結(jié)果

圖1 不同方法對數(shù)據(jù)集修復(fù)的均方值誤差對比

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

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

表1 不同方法對數(shù)據(jù)集修復(fù)的準確度百分比對比

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

4 結(jié)束語

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