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

上述相關(guān)學(xué)者研究出的修復(fù)方法，存在修復(fù)過程復(fù)雜，且經(jīng)過這些方法修復(fù)的數(shù)據(jù)仍然存在數(shù)據(jù)漏洞，修復(fù)準(zhǔn)確度較低?，F(xiàn)提出一種基于時空大數(shù)據(jù)的缺失數(shù)據(jù)流關(guān)聯(lián)修復(fù)方法。經(jīng)過仿真證明，本文提出的方法能夠更準(zhǔn)確地計(jì)算缺失數(shù)據(jù)，并在最短的時間內(nèi)對其進(jìn)行高效、準(zhǔn)確地修復(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ù)進(jìn)行設(shè)定[7]，然后對有效的規(guī)則與條件函數(shù)依賴相等、規(guī)則可信度由置信度決定兩方面進(jìn)行證明。

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

關(guān)聯(lián)規(guī)則可通過以下方式進(jìn)行表述：設(shè)I={I1，I2，…，In}是一個任務(wù)集合，T={T1，T2，…，Tm}表示一個事件數(shù)據(jù)集合，事件數(shù)據(jù)集合中的任意事件Ti均是單獨(dú)的任務(wù)集合，即Ti?I。關(guān)聯(lián)規(guī)則的蘊(yùn)含關(guān)系如下：X→Y，其中X?I，Y?I，且X∩Y=φ。X(或Y)是一個任務(wù)的集合，叫做事務(wù)集，將X為前件任務(wù)，Y為后件任務(wù)。當(dāng)關(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}表示一個標(biāo)準(zhǔn)的函數(shù)依賴；Tp是和X與Y相似的模式元素組，設(shè)定了相似屬性在取值范圍方面的約束條件。

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

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

綜上所述，進(jìn)一步對關(guān)聯(lián)規(guī)則R：X→Y進(jìn)行表達(dá)

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ù)依賴相同的表達(dá)式為

φ：[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è)定進(jìn)行證明的具體過程如下

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

X→Y支持度的計(jì)算公式如下

(3)

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

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

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

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

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

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

(8)

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

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

(9)

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

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

(10)

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

(11)

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

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

3 仿真證明

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

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

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

(12)

準(zhǔn)確度百分比(P)的計(jì)算公式如下：

(13)

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

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

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

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

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

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

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

4 結(jié)束語

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