基于改進DTW 算法的高維時空數據關聯挖掘方法

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

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

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

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

1 高維時空數據關聯性判斷

1.1 空間數據關聯性判斷

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

為了保證在一定時間序列下，簇頭節點oi和簇內節點sj均為連續的歷史數據，這兩個節點空間相關性判斷步驟為：

步驟1：計算兩個節點形成的差值序列，公式為：

由式（1）可確定，簇頭節點oi和簇內節點sj產生的差值序列[5]。

步驟2：根據式（1）計算兩個節點差值序列，構造簇節點的原始序列，可表示為z；

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

式中，m表示計算次數。

步驟4：如果擬合誤差小于給定的誤差閾值，則判定兩個節點的數據存在空間關聯性[6]；反之，則不存在關聯性。

1.2 時間數據關聯性判斷

高維時空數據具有周期性變化規律，從單一節點獲得的感知數據，可以作為基于采樣時間的自變量，而由變數分段線性關系得到的感知數據，可以視為以采樣時間為基礎的因變量[7]。

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

圖1 基于線性回歸的時間數據關聯性判斷模型

圖1 中，設節點的感知數據與實際數據絕對誤差為μ，閾值誤差為e，如果μ

2 改進DTW算法下高維時空數據關聯挖掘

利用改進的DTW 算法對高維時空數據進行離散，獲得多個層次的模糊集合，并建立了一個模糊數據庫[10]。采用改進DTW 算法生成頻繁項集，以此為依據挖掘高維時空數據關聯性。

2.1 高維時空數據預處理

對于需要預處理的高維空間數據，利用該數據作為參考依據，使用改進DTW 算法實現了等距離同步處理[11]。詳細步驟為：

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

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

在搜索區間內，依次計算出距離矩陣累計結果，其公式如下：

式中，i、j分別表示第i個和第j個采樣。根據計算結果繼續搜索，選擇其中最小值，并將其對應的數據依次標記，獲取高維時空數據預處理結果。

2.2 高維時空數據關聯挖掘過程

在高維時空數據挖掘中，可以通過時間與空間的關系生成頻繁項目集，通過最小集合周期生成頻繁項目集[13]。然后對DTW 方法進行修改，以進一步提升數據挖掘的準確性。詳細關聯挖掘過程如圖2所示。

圖2 關聯挖掘過程

由圖2 可知，結合改進DTW 算法，極大提升了高維時空數據關聯挖掘速度，詳細步驟如下所示：

步驟1：構建高維時空數據集

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

圖3 關聯挖掘路徑

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

式中，r表示采樣點數；α表示平行四邊形相鄰兩邊一側的斜率；β表示平行四邊形相鄰兩邊另一側的斜率。當挖掘數據不在平行四邊形內部時，說明這些數據不具有關聯性，無需挖掘；反之，則具有關聯性，可以挖掘。根據挖掘結果，集合高維時空數據集[16]。

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

步驟3：循環數據集，刪除不在項頭表中的數據，并按項頭表的增加次序排列數據。重新循環數據集后，在產生的頻繁模式樹中，所有的節點都表示高維度的空間和時間數據，而樹枝表示高維時空數據出現的次數；

步驟4：在循環項頭表中，按遞減次序的條目，查找經常模式樹中的條目和條目的樹葉節點，并剔除重復節點數據，獲得一個單獨的樹結構數據集，此時的數據集就是一個具有關聯性的集合[17]。

步驟5：將所有單一路徑的樹狀結構數據集輸出，構成最終結果集。

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

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

式中，FIO 表示蘊涵度算子。

通過計算支持度，能夠確定頻繁項集，該結果即為高維時空數據的關聯挖掘。

3 實 驗

為了驗證基于改進DTW 算法的高維時空數據關聯挖掘方法的有效性，在Matlab 平臺上通過Unix操作系統進行實驗測試。

3.1 實驗數據集

為了使實驗結果更加明顯，以某電網數據為例，對每個時間序列進行了擴充，得到6 組時間序列，并且從序列第一個數據點開始采集，采集變電站、發電機、儲能系統和智能電表等不同時空節點數據。在數據集中，對時空序列依次進行相似度檢索，為實驗提供數據支持。

3.2 實驗指標確定

關聯挖掘誤差計算公式如式（8）所示：

式中，d表示挖掘次數；vc表示數據未被搜索到的信息。該計算結果值越大，說明高維時空數據關聯挖掘結果越精準。

3.3 實驗結果與分析

分別使用電網節點時空關聯特性評估方法（文獻[1]方法）、基于Apriori關聯規則算法（文獻[2]方法）和基于改進DTW 算法的關聯挖掘方法（該文方法）進行數據挖掘。三種方法的挖掘誤差結果如表1所示。

表1 數據挖掘誤差對比分析

由表1 可知，文獻[1]方法的平均挖掘誤差為9.4%，文獻[2]方法的平均挖掘誤差為12.5%，該文方法的平均挖掘誤差為1.6%。因為該文方法在數據預處理過程中先明確了數據距離矩陣累積結果，并計算空間數據和時間數據的支持度并與設定的閾值對比，從而降低了數據關聯挖掘誤差。

4 結束語

文中提出的基于改進DTW 算法的高維時空數據關聯挖掘方法，通過計算蘊涵度確定數據之間的支持度，結合改進DTW 算法挖掘高維時空數據關聯性。通過實驗證明，該方法可以有效提高數據挖掘的完整性，減少誤差。然而該研究仍處于單層關聯性方面，為了擴展該方法的應用領域，后期將致力于多層關聯性的研究應用。