基于改進(jìn)DTW 算法的高維時空數(shù)據(jù)關(guān)聯(lián)挖掘方法

周春雷，董新微，季 良，張璧君，許中平

（1.國家電網(wǎng)有限公司大數(shù)據(jù)中心，北京 100052；2.安徽繼遠(yuǎn)軟件有限公司，安徽合肥 230088；3.北京國網(wǎng)信通埃森哲信息技術(shù)有限公司，北京 100052）

與傳統(tǒng)電網(wǎng)不同，智能電網(wǎng)通過分析分布式測量設(shè)備（例如：電力測量單元、變電站、發(fā)電機(jī)、儲能系統(tǒng)和智能電表）收集的大量數(shù)據(jù)，為電網(wǎng)運(yùn)行提供新的以數(shù)據(jù)為中心的服務(wù)。隨著電網(wǎng)智能化水平不斷提高，監(jiān)測電網(wǎng)運(yùn)行狀態(tài)、電能質(zhì)量、設(shè)備運(yùn)行狀態(tài)等過程中產(chǎn)生了大量高維時空數(shù)據(jù)。但是由于數(shù)據(jù)存在冗余和缺失等，所以要對電力系統(tǒng)的空間和時間數(shù)據(jù)進(jìn)行挖掘和分析。

目前，有學(xué)者提出利用區(qū)塊鏈方法評估電網(wǎng)節(jié)點(diǎn)數(shù)據(jù)時空關(guān)聯(lián)特性。該方法挖掘了電壓相量軌跡信息幾何特征，構(gòu)建軌跡運(yùn)動演進(jìn)規(guī)律的特征平面，并通過軌跡距離密度設(shè)計(jì)的參數(shù)自適應(yīng)聚類算法，評估了節(jié)點(diǎn)相似性[1]。但該方法在處理大量數(shù)據(jù)時，效率和運(yùn)算速度都較慢。還有學(xué)者提出基于Apriori關(guān)聯(lián)規(guī)則算法，其先對各個波段進(jìn)行分析，然后再利用這些波段來生成更強(qiáng)的相關(guān)關(guān)系。應(yīng)用Apriori關(guān)聯(lián)規(guī)則算法，首先掃描多個數(shù)據(jù)庫，然后生成大量常用的候選對象，從而使得Apriori 算法具有時間和空間上的復(fù)雜性[2]。其在挖掘大量數(shù)據(jù)時，性能有待完善。在大數(shù)據(jù)時代，傳統(tǒng)的時間—空間軌道數(shù)據(jù)關(guān)聯(lián)的方法，已無法適應(yīng)對數(shù)據(jù)的快速關(guān)聯(lián)和數(shù)據(jù)挖掘的要求，同時也存在著較大的不足。為此，提出了基于改進(jìn)DTW 算法的高維時空數(shù)據(jù)關(guān)聯(lián)挖掘方法。

1 高維時空數(shù)據(jù)關(guān)聯(lián)性判斷

1.1 空間數(shù)據(jù)關(guān)聯(lián)性判斷

從空間梯度特征來看，電網(wǎng)節(jié)點(diǎn)間的空間關(guān)聯(lián)性通常是，在某一時刻鄰近節(jié)點(diǎn)之間的感知數(shù)據(jù)相同或相似。在對簇頭和簇內(nèi)部數(shù)據(jù)進(jìn)行擬合時，其錯誤率低于所規(guī)定的閾值[3]。利用兩個節(jié)點(diǎn)的歷史感知數(shù)據(jù)挖掘出兩個節(jié)點(diǎn)關(guān)系，可以判斷出簇內(nèi)的節(jié)點(diǎn)與簇的空間關(guān)聯(lián)[4]。該方法無須傳輸節(jié)點(diǎn)的感知數(shù)據(jù)，只需將相關(guān)模式發(fā)送給聚集節(jié)點(diǎn)，即可在不進(jìn)行節(jié)點(diǎn)感知數(shù)據(jù)的前提下，將感知到的數(shù)據(jù)恢復(fù)到集群中。

為了保證在一定時間序列下，簇頭節(jié)點(diǎn)oi和簇內(nèi)節(jié)點(diǎn)sj均為連續(xù)的歷史數(shù)據(jù)，這兩個節(jié)點(diǎn)空間相關(guān)性判斷步驟為：

步驟1：計(jì)算兩個節(jié)點(diǎn)形成的差值序列，公式為：

由式（1）可確定，簇頭節(jié)點(diǎn)oi和簇內(nèi)節(jié)點(diǎn)sj產(chǎn)生的差值序列[5]。

步驟2：根據(jù)式（1）計(jì)算兩個節(jié)點(diǎn)差值序列，構(gòu)造簇節(jié)點(diǎn)的原始序列，可表示為z；

步驟3：根據(jù)均值分析兩個序列擬合誤差，公式為：

式中，m表示計(jì)算次數(shù)。

步驟4：如果擬合誤差小于給定的誤差閾值，則判定兩個節(jié)點(diǎn)的數(shù)據(jù)存在空間關(guān)聯(lián)性[6]；反之，則不存在關(guān)聯(lián)性。

1.2 時間數(shù)據(jù)關(guān)聯(lián)性判斷

高維時空數(shù)據(jù)具有周期性變化規(guī)律，從單一節(jié)點(diǎn)獲得的感知數(shù)據(jù)，可以作為基于采樣時間的自變量，而由變數(shù)分段線性關(guān)系得到的感知數(shù)據(jù)，可以視為以采樣時間為基礎(chǔ)的因變量[7]。

在擬合回歸線附近，將感知數(shù)據(jù)按時間序列分布。利用線性回歸方法，建立了一種基于線性回歸的時間數(shù)據(jù)關(guān)聯(lián)性判斷模型，如圖1 所示。

圖1 基于線性回歸的時間數(shù)據(jù)關(guān)聯(lián)性判斷模型

圖1 中，設(shè)節(jié)點(diǎn)的感知數(shù)據(jù)與實(shí)際數(shù)據(jù)絕對誤差為μ，閾值誤差為e，如果μ

2 改進(jìn)DTW算法下高維時空數(shù)據(jù)關(guān)聯(lián)挖掘

利用改進(jìn)的DTW 算法對高維時空數(shù)據(jù)進(jìn)行離散，獲得多個層次的模糊集合，并建立了一個模糊數(shù)據(jù)庫[10]。采用改進(jìn)DTW 算法生成頻繁項(xiàng)集，以此為依據(jù)挖掘高維時空數(shù)據(jù)關(guān)聯(lián)性。

2.1 高維時空數(shù)據(jù)預(yù)處理

對于需要預(yù)處理的高維空間數(shù)據(jù)，利用該數(shù)據(jù)作為參考依據(jù)，使用改進(jìn)DTW 算法實(shí)現(xiàn)了等距離同步處理[11]。詳細(xì)步驟為：

在同一維度上，計(jì)算空間數(shù)據(jù)L1和時間數(shù)據(jù)L2之間的距離，公式為：

式中，wi表示兩組數(shù)據(jù)間的歐氏距離值[12]。

在搜索區(qū)間內(nèi)，依次計(jì)算出距離矩陣?yán)塾?jì)結(jié)果，其公式如下：

式中，i、j分別表示第i個和第j個采樣。根據(jù)計(jì)算結(jié)果繼續(xù)搜索，選擇其中最小值，并將其對應(yīng)的數(shù)據(jù)依次標(biāo)記，獲取高維時空數(shù)據(jù)預(yù)處理結(jié)果。

2.2 高維時空數(shù)據(jù)關(guān)聯(lián)挖掘過程

在高維時空數(shù)據(jù)挖掘中，可以通過時間與空間的關(guān)系生成頻繁項(xiàng)目集，通過最小集合周期生成頻繁項(xiàng)目集[13]。然后對DTW 方法進(jìn)行修改，以進(jìn)一步提升數(shù)據(jù)挖掘的準(zhǔn)確性。詳細(xì)關(guān)聯(lián)挖掘過程如圖2所示。

圖2 關(guān)聯(lián)挖掘過程

由圖2 可知，結(jié)合改進(jìn)DTW 算法，極大提升了高維時空數(shù)據(jù)關(guān)聯(lián)挖掘速度，詳細(xì)步驟如下所示：

步驟1：構(gòu)建高維時空數(shù)據(jù)集

由于改進(jìn)的DTW 算法在關(guān)聯(lián)挖掘過程中需要經(jīng)過大量的計(jì)算步驟，占用了大量的存儲空間[14-15]，因此，為了解決這一問題，設(shè)計(jì)了高維時空數(shù)據(jù)關(guān)聯(lián)挖掘路徑，如圖3 所示。

圖3 關(guān)聯(lián)挖掘路徑

如圖3 所示，將高維數(shù)據(jù)分為三維，分別是一維[1,x1]、二維[x1+1,x2]、三維[x2+1,x3]。對于x1和x3值的計(jì)算可表示為：

式中，r表示采樣點(diǎn)數(shù)；α表示平行四邊形相鄰兩邊一側(cè)的斜率；β表示平行四邊形相鄰兩邊另一側(cè)的斜率。當(dāng)挖掘數(shù)據(jù)不在平行四邊形內(nèi)部時，說明這些數(shù)據(jù)不具有關(guān)聯(lián)性，無需挖掘；反之，則具有關(guān)聯(lián)性，可以挖掘。根據(jù)挖掘結(jié)果，集合高維時空數(shù)據(jù)集[16]。

步驟2：掃描所有的數(shù)據(jù)集，并記錄每次數(shù)據(jù)出現(xiàn)的次數(shù)。依據(jù)需求定義，判定時間和空間數(shù)據(jù)是否處于相同的維度，若存在，則將其記錄于項(xiàng)頭表中；

步驟3：循環(huán)數(shù)據(jù)集，刪除不在項(xiàng)頭表中的數(shù)據(jù)，并按項(xiàng)頭表的增加次序排列數(shù)據(jù)。重新循環(huán)數(shù)據(jù)集后，在產(chǎn)生的頻繁模式樹中，所有的節(jié)點(diǎn)都表示高維度的空間和時間數(shù)據(jù)，而樹枝表示高維時空數(shù)據(jù)出現(xiàn)的次數(shù)；

步驟4：在循環(huán)項(xiàng)頭表中，按遞減次序的條目，查找經(jīng)常模式樹中的條目和條目的樹葉節(jié)點(diǎn)，并剔除重復(fù)節(jié)點(diǎn)數(shù)據(jù)，獲得一個單獨(dú)的樹結(jié)構(gòu)數(shù)據(jù)集，此時的數(shù)據(jù)集就是一個具有關(guān)聯(lián)性的集合[17]。

步驟5：將所有單一路徑的樹狀結(jié)構(gòu)數(shù)據(jù)集輸出，構(gòu)成最終結(jié)果集。

步驟6：將上一步驟的最終結(jié)果集作為模糊屬性集，基于原始數(shù)據(jù)庫建立模糊數(shù)據(jù)庫。設(shè)空間數(shù)據(jù)為空間數(shù)據(jù)L1的支持度，時間數(shù)據(jù)為時間數(shù)據(jù)L2的支持度。規(guī)則L1?L2在數(shù)據(jù)庫K中的支持度可表示為：

由式（6）可知，在模糊關(guān)聯(lián)關(guān)系中計(jì)算模糊支持度，即蘊(yùn)涵度，能夠有效減少挖掘步驟，縮短挖掘所用時間。第h個數(shù)據(jù)蘊(yùn)涵度可表示為：

式中，F(xiàn)IO 表示蘊(yùn)涵度算子。

通過計(jì)算支持度，能夠確定頻繁項(xiàng)集，該結(jié)果即為高維時空數(shù)據(jù)的關(guān)聯(lián)挖掘。

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

為了驗(yàn)證基于改進(jìn)DTW 算法的高維時空數(shù)據(jù)關(guān)聯(lián)挖掘方法的有效性，在Matlab 平臺上通過Unix操作系統(tǒng)進(jìn)行實(shí)驗(yàn)測試。

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

為了使實(shí)驗(yàn)結(jié)果更加明顯，以某電網(wǎng)數(shù)據(jù)為例，對每個時間序列進(jìn)行了擴(kuò)充，得到6 組時間序列，并且從序列第一個數(shù)據(jù)點(diǎn)開始采集，采集變電站、發(fā)電機(jī)、儲能系統(tǒng)和智能電表等不同時空節(jié)點(diǎn)數(shù)據(jù)。在數(shù)據(jù)集中，對時空序列依次進(jìn)行相似度檢索，為實(shí)驗(yàn)提供數(shù)據(jù)支持。

3.2 實(shí)驗(yàn)指標(biāo)確定

關(guān)聯(lián)挖掘誤差計(jì)算公式如式（8）所示：

式中，d表示挖掘次數(shù)；vc表示數(shù)據(jù)未被搜索到的信息。該計(jì)算結(jié)果值越大，說明高維時空數(shù)據(jù)關(guān)聯(lián)挖掘結(jié)果越精準(zhǔn)。

3.3 實(shí)驗(yàn)結(jié)果與分析

分別使用電網(wǎng)節(jié)點(diǎn)時空關(guān)聯(lián)特性評估方法（文獻(xiàn)[1]方法）、基于Apriori關(guān)聯(lián)規(guī)則算法（文獻(xiàn)[2]方法）和基于改進(jìn)DTW 算法的關(guān)聯(lián)挖掘方法（該文方法）進(jìn)行數(shù)據(jù)挖掘。三種方法的挖掘誤差結(jié)果如表1所示。

表1 數(shù)據(jù)挖掘誤差對比分析

由表1 可知，文獻(xiàn)[1]方法的平均挖掘誤差為9.4%，文獻(xiàn)[2]方法的平均挖掘誤差為12.5%，該文方法的平均挖掘誤差為1.6%。因?yàn)樵撐姆椒ㄔ跀?shù)據(jù)預(yù)處理過程中先明確了數(shù)據(jù)距離矩陣?yán)鄯e結(jié)果，并計(jì)算空間數(shù)據(jù)和時間數(shù)據(jù)的支持度并與設(shè)定的閾值對比，從而降低了數(shù)據(jù)關(guān)聯(lián)挖掘誤差。

4 結(jié)束語

文中提出的基于改進(jìn)DTW 算法的高維時空數(shù)據(jù)關(guān)聯(lián)挖掘方法，通過計(jì)算蘊(yùn)涵度確定數(shù)據(jù)之間的支持度，結(jié)合改進(jìn)DTW 算法挖掘高維時空數(shù)據(jù)關(guān)聯(lián)性。通過實(shí)驗(yàn)證明，該方法可以有效提高數(shù)據(jù)挖掘的完整性，減少誤差。然而該研究仍處于單層關(guān)聯(lián)性方面，為了擴(kuò)展該方法的應(yīng)用領(lǐng)域，后期將致力于多層關(guān)聯(lián)性的研究應(yīng)用。