電力時間序列的分布式索引算法

吳裔 郭棋林 陳顥天 郭乃網

摘 要：時間序列的研究已經被應用到越來越多的領域中。越來越多的領域應用需要索引和分析海量的時間序列，代表性的比如金融，電力，生物信息等等。這類應用往往面臨數以億計的時間序列的處理，然后從中識別出一些隱藏的模式來。然而目前對時間序列的索引技術都是單機版本，需要用漫長的時間來對大量的時間序列進行索引，限制了時間序列分析的產出率。提出了一種基于Isax表達的分布式時間序列索引算法，并在Spark分布式計算框架下實現算法。首先，給出了基于Isax的分布式索引算法的樸素實現想法，指明了其存在的問題。然后提出一種先建立索引結構，再將時間序列哈希到相應葉子節點的分布式索引算法。最終，構建了一個完整的電力時間序列的近鄰近似查詢系統，再保證查詢精確率的前提下大大提高了計算效率。并在實驗數據集上證明了算法的正確性、高效性和可擴展性。

關鍵詞：時間序列;分布式;索引

DOI：10.15938/j.jhust.2021.06.011

中圖分類號： TP392

文獻標志碼： A

文章編號： 1007-2683（2021）06-0081-06

A Distributed Algorithm for Indexing Power Time Series

WU Yi1， GUO Qi-lin2， CHEN Hao-tian1， GUO Nai-wang1

（1.State Grid Shanghai Municipal Electric Power Company， Shanghai 200122， China;

2.School of Economics， Fudan University， Shanghai 200433， China）

Abstract：Time series research has been applied to more and more areas. More and more domain applications need to index and analyze massive time series， such as finance， electricity， bioinformatics， and so on. Such applications are often faced with hundreds of millions of time series of processing， and then identify some hidden pattern from the model. Firstly， we give a simple idea of the distributed indexing algorithm based on Isax， which points out its existing problems. Then we propose a distributed indexing algorithm to establish the index structure and then insert the time series to the corresponding leaf node. Finally， this paper constructs a complete approximation query system of power time series， and greatly improves the computational efficiency under the premise of ensuring the accuracy of query. The correctness， efficiency and expansibility of the algorithm are proved on the experimental data set.

Keywords：time series; distributed algorithm; index

0 引 言

隨著配用電網技術的發展、電力采集設備的更新，電力系統積累了海量用電負荷數據。而電網的穩定運行和智能化發展在很大程度上依賴于對這些數據的挖掘分析[1]，如用電預測、錯峰調度、用戶用電行為模式識別、設備狀態和風險評估[2-3]等等。在這個過程中，我們會涉及到數以億計的數據資源的調取、運算以及分類等，而這樣級別的運算量對于計算性能、數據庫性能有著極高的要求，在數據挖掘領域，尤其是每天都有百萬更新數據的電力數據分析領域，用更少的計算資源、更短的時間搜索到更加精確可靠的結果是我們的最終目標，也是所有數據挖掘研究的前提條件。而在這些搜索的背后，都需要近似近鄰查詢。

在大規模的高維時間序列的應用場景中，精確的近鄰查詢需要耗費大量存儲和計算資源，實際應用中效果不理想。近似近鄰查詢技術可以大幅度縮短查詢時間，同時效果比較好的近似近鄰查詢方法都可以保證查詢結果與精確查詢結果近似。由于其在的高應用價值，近似近鄰技術被廣泛應用于信息檢索，統計分析，機器學習等領域。

近年來，時間序列的近似近鄰查詢技術有了很大的進展，但是隨著互聯網的蓬勃發展，需要處理的數據規模越來越大。傳統的單機版索引算法和索引結構往往只能處理小規模數據。大規模數據往往無法做到單機存儲，這些數據往往存儲于分布式系統中且需要一種分布式索引結構來支持查詢和檢索。

隨著google、facebook等企業和實驗室相繼開源了Haoop、Stotm、Spark等分布式計算平臺，有效的管理和分析海量分布式數據成為可能。本文基于Spark分布式計算平臺提出一種使用Isax表達的分布式時間序列索引算法。

本文第2節介紹了Spark分布式計算平臺，Isax表達式以及時間序列上的分布式索引研究進展。第三章介紹了基于Isax的分布式時間序列索引算法及其在Spark上的設計與實現。第四節分析討論了索引算法和基于索引的最近鄰查詢在大規模時間序列數據集上的實驗結果。第五節介紹了算法在電力數據挖掘中的實際應用。第六節對本文工作進行了總結和展望。

1 相關工作

1.1 SPARK與MR編程模型

分布式編程模型（MapReduce，MR）[4]是一種用于并行運算的編程范式，用戶無需關注分布式通信和傳輸的細節，只需關注包裝在map、reduce中的核心業務邏輯，就可在分布式系統上運行自己的程序。簡單的說，MR編程范式采用了”分而冶之”的思想，將一個大而復雜的作業分割成眾多小而簡單的獨立任務，然后將這些任務分發給集群中的各節點獨立執行。MR為用戶提供了一個極其簡單的分布式編程模型。

主流的實現MR編程模型的框架主要有Google的Hadoop平臺和UC Berkeley AMP lab的Spark[5]。相對于Hadoop，Spark啟用了分布式內存數據庫，可以在內存中完成所有的數據分析操作再將結果存入集群，其在迭代計算中速度要遠遠快于Hadoop。同時其提供了更豐富的api接口，以及覆蓋整個數據分析流程的DAG圖，更有利于分布式算法的設計和實現。

1.2 時間序列表達式

時間序列通常維度非常高，高維空間下時間序列呈現稀疏性，導致不符合大數定律，統計結果不具備可信度。時間序列的降維手段主要有分段聚集近似PAA[6]，符號聚集近似SAX[7]和可索引的符號聚集近似iSAX[8]等等。分段段聚集近似PAA[6]。將時間序列在時間軸上劃分為若干段，每段用平均值來表示。SAX[7]將標準化后的時間序列PAA處理，然后根據高斯分布和子段值將序列離散化為符號串。iSAX時SAX基礎之上提出的一種多辨析率的符號化表示，通過選擇不同的基數大小表達不同的辨析率層次。

時間序列的索引方法中，效果比較好的主要有iSAX[8]索引，以及iSAX2.0[9]。iSAX2.0[9]通過增加bulk loading機制和一種基于統計的分裂策略大大減少了索引所需的時間，使得索引算法能夠處理數億級的時間序列。

但是不論是iSAX[8]還是iSAX2.0[9]都是單機版的算法，受到單機內存和計算資源的制約，在面臨更大數據的時間序列時擴展性不足。本文提出一種分布式iSAX索引算法。不僅提高了索引速度，而且具備很強的擴展性。

1.3 分布式相似性索引算法

分布式索引算法不等于相似性索引算法。樹結構相似性索引方法有很多，比如R樹、KD樹等。

經典的KD樹會將原始的數據空間按數據的維度劃分為一棵二叉樹。也有解決kd樹在高維空間退化現象的隨機化kd樹的方法。李天駒等人提出一種面向KD樹建樹過程的多核并行算法-ParK[10]。FLANN[11]中包含的層次Kmeans樹，在每一層都使用Kmeans聚類，若類中節點小于某個閾

值則作為葉子節點，否則是中間節點繼續對節點下的數據進行Kmeans聚類，Kmeans算法可以利用MR框架并行化，相比單機版提升了建樹的速度。但是這樣的Kmeans樹雖然能夠快速的找到近鄰候選集合，但是在樹的每一層都需要進行一次Kmeans聚類所消耗的空間和時間資源還是非常之大。Murphy等的工作中介紹了這種算法的MR版本[12]。

傳統的樹結構索引在大規模數據下往往迎來空間資源不足的局面。而基于哈希的索引方法有著良好的擴展性，適合在分布式環境下處理海量的數據。

局部敏感哈希（LSH）[11]是最常見的數據無關哈希方法。其基本思想是在空間轉換中保持原始空間和轉換后空間的相似性。原始空間中越相似的兩個數據點，經過哈希之后，越有可能被哈希到同一個桶，桶的編號就可以作為他們的整體編碼。常見的有基于歐式距離、余弦距離、Jaccard距離的局部敏感哈希算法。局部敏感哈希算法非常適合利用MR框架并行化，Szmit等[13]已經實現了相應的分布式版本。LSH為了有更好的索引效果，并行化的LSH算法往往需要經歷多輪不同節點間的數據傳輸（shuffle）。本文基于isax索引的特性，提出了一種只需要一次shuffle的基于MR的分布式時間序列索引算法。

2 分布式的時間序列索引算法

2.1 并行模式分析

2.1.1 樸素想法

1）單機版建立isax索引如圖1所示，每條時間序列計算isax表達，并分配到一個節點，如果節點上時間序列的數量超過閾值，則進行split。而split的策略是從左到右依次基數加倍，將父節點上的時間序列根據新基數重新計算isax表達并分配到新的節點上。

2）由上述過程可以發現，每個時間序列在這個樹中的操作是相互獨立的?？梢詫⒚恳粚拥膇sax表達式視為哈希桶的key，每一層的各個節點分別是不同key值的哈希桶。樸素的分布式建樹可以視為一個層次的哈希過程，每一層某個哈希桶中數據量小于閾值為葉子，否則繼續進入下一輪哈希。但是這樣的分布式算法擴展性較差，且面臨一系列問題。

2.1.2 樸素想法存在的問題

1）算法存在數據傾斜問題：其一方面是由于時間序列的分布本身并不均勻，有些中間節點分裂后信息熵減少有限。另一方面是由于程序多次使用shuffle算子。

2）算法耗費大量的傳輸時間，成為性能瓶頸。在建立索引樹的每一層節點時都需要一次shuffle過程，而shuffle過程消耗大量的傳輸時間，是hadoop，spark這類分布式計算平臺的性能瓶頸。

3）解決方案：①讓shuffle算子提高并行度，緩解數據傾斜問題;

②把部分數據清洗掉，比如數據集中中很多0.0的時間序列，往往是導致數據傾斜的原因，需要過濾掉;

③盡量避免join操作，將reduce join改為map join，用廣播的形式存放小rdd。

這些方案能夠大大優化算法的性能，但是卻是治標不治本，算法的shuffle次數依賴于樹的層次無法減少。因此我們提出了一種建立索引不依賴于樹的層次、只需要經過一次shuffle的分布式索引算法。

2.2 算法設計

可以發現，樸素想法中每次shuffle過程的目的只是為了通過獲得哈希到每個索引節點的時間序列數目判斷是否需要分裂。換而言之，每層的shuffle都只是為了獲得樹的索引結構。改進算法的思想就是先通過所有的時間序列通過一次shuffle建立整棵索引樹的結構，再并行的將所有時間序列分配到相應的葉子節點。

算法過程如下：

1）生成一個長度為depth的由每一層基組成的集合。

2）并行對每條時間序列計算其在索引中經過的長度為depth的路徑集合。

3）對所有時間序列的路徑集合中的每個iSAX索引節點進行計數。

4）若某個iSAX索引節點計數值大于閾值，則其是中間節點，否則是葉子節點。

5）并行將每條時間序列插入到葉子節點中

算法通過計算每一個時間序列的路徑，對路徑上所有節點計數，然后根據每個節點計數值與閾值的關系獲得了整棵樹的結構。如表1、表2。

如果分裂閾值為2，那么中間節點為0.2_0.2_1.2， 0.4_0.2_1.2.其他都為葉子節點.因此我們就獲得了iSAX索引樹的形狀。找到時間序列對應的葉子節點的具體的做法是再對時間序列計算一次路徑，找到路徑中第一個不為中間節點的iSAX表達，該表達即時間序列對應的葉子節點.比如對于時間序列t= （-1.3，-0.35，0.35），發現第三層的iSAX表達式0.4_1.4_1.2不在中間節點列表中，將其作為插入的葉子節點表達式.

2.3 索引存儲結構

為了適應分布式的插入和查詢，我們需要放棄單機版的索引存儲方案，因為其會成為整個并行過程中的瓶頸。我們在hadoop大數據分析架構的基礎上，采用Hbase技術對用電數據進行存儲與管理，提出一種基于iSAX的分布式索引技術對用電數據進行存儲索引，實現海量時間序列的高效查詢與匹配，如圖2所示。

在HBase中，建立表用于存放iSAX的索引結構以及所有的原始時間序列。我們將每一個iSAX節點作為一行存放在HBase中，每一個iSAX節點作為一個對象，對象的內容除了原始iSAX的內容還包括節點類型等內容。根節點的key為“root_node_00”，中間節點和葉子節點的key為iSAX表達，value是iSAX索引節點對象序列化的byte數組。

3 實驗和結果分析

3.1 實驗環境

實驗是在Spark平臺下完成的，硬件設備為8臺ubuntu15.04的系統，其中主節點配置為3核16G內存;從設備節點采用配置為3核10G內存。

3.2 實驗數據集

1）上海市浦東居民和工商業用戶的日凍結量，它包括了200萬個電表850天的用電數據，數據集的大小為10GB（以下簡稱200萬用戶用電數據）。

2）典型上海市30萬用戶用電數據，365天日凍結量（以下簡稱30萬用戶用電數據）。

3.3 實驗參數

根據isax索引構建的描述，本實驗設置的參數如下：

1）30萬用戶用電數據：根節點的基數4;

分段數=14;分裂閾值=100;原始時間序列長度=364;

2）100萬、200萬用戶用電數據：根節點的基數4;分段數=17;分裂閾值=100;原始時間序列長度=850;限制最大樹高為52;

3.4 結果及分析

首先對單機版的時間序列索引算法和本文提出的分布式算法的運行效率進行比較.為了證明分布式索引算法的高效性還實現了樸素的分布式索引版本并增加實驗對比。

圖3實驗用來說明本文提出的算法的擴展性。從圖一可以看出在100萬和200萬數據下，隨著節點的增多，算法的運行時間也線性的減少。但是在30萬數據集下，運行時間并沒有隨著節點數量增加而減少，反而有所增加。原因是增加節點減少計算時間的同時，反而消耗了更多的分布式通信調度的時間。因此需要根據數據量選擇合適的并行度。

圖4比較的是單機版及兩種分布式算法在不同規模數據集下的運行效率對比。從圖4可以看出我們的算法在運行效率遠高于樸素的分布式索引算法。這是因為樸素分布式算法在每一層都需要經歷一次shuffle，使得傳輸時間成為了算法的瓶頸。而本文的分布式算法通過先建樹再插入的想法，只需要一次shuffle，從而避免了這個問題。單機版的索引算法在30萬數據下就需要運行8h，在我們的機器配置下無法在超過百萬的數據集下運行。

3.5 查詢效果展示

查詢[7]可以指定返回與查詢序列相似的若干條時間序列數目，我們選取返回5條時間序列為例，展示查詢效果。其中序列1代表查詢序列，序列2-6代表返回的相似時間序列。查詢電表號為2470032、4041308和7073795的相似序列發現，返回的時間序列形狀上查詢時間序列均非常相似。其中綠色時間序列為所要查詢的時間序列?？梢园l現查詢到的時間序列整體上與目標非常接近。

3.6 查詢性能對比

下面分別對本地順序存儲的時間序列和基于Hbase的iSAX索引的時間序列數據進行查詢響應速度對比實驗，結果如表4所示。

比較兩者的平均查詢時間可知，當時間序列的數量超過10000時，在HBase的查詢速度超過在本地。當時間序列的數量較小時，因為本地IO的速度大于網絡IO的速度，所以Hbase的查詢速度小于本地。當時間序列數量越大，Hbase查詢的優越性就越能體現，如表5所示。

分布式索引算法的優勢在于可以快速對海量時間序列建立索引，以此來應對相似序列查詢，這在數據挖掘中有重要意義。同在具體的分析中，如聚類、關聯，異常識別等，通過大幅節約數據從數據庫提取的時間，可以大大加速分析過程。

4 結 論

用電負荷大數據分析為電力系統的穩定運行和智能化發展提供了數據支撐，而快速有效的索引對日益龐大的數據的存儲和讀取至關重要。本文基于上海市浦東新區200萬電表850d時間序列數據，通過Spark平臺實現了分布式索引算法，能夠快速準確的進行時間序列查詢，同時可以建立多條索引，對不同周期的時間序列進行查詢，返回多條相似的完整的時間序列。分布式索引算法避免了通過全局掃描的方法查詢，速度比單機版高數十倍，可以有效的提高數據挖掘的產出率，不僅保證了數據分析的正常運行，還可以和數據挖掘算法有機結合大大提高分析效率。除了用電負荷數據，我們的分布式索引算法同樣可以應用到更多存在海量時間序列數據的領域。

參 考 文 獻：

[1] 張曉晨. 電力大數據應用研究與展望[J]. 山東工業技術， 2017（3）：155.

ZHANG Xiaochen. Research and Prospects of Electric Power Big Data Application[J]. Shandong Industrial Technology， 2017（3）：155.

[2] 鄭海雁， 金農， 季聰，等. 電力用戶用電數據分析技術及典型場景應用[J]. 電網技術， 2015， 39（11）：3147.

ZHEN Haiyan， JIN Nong， JI Cong， et al. Data Analysis Technology and Application of Electric Power User in Typical Scenarios[J]. Power Grid Technology， 2015， 39（11）：3147.

[3] 沈玉玲， 呂燕， 陳瑞峰. 基于大數據技術的電力用戶行為分析及應用現狀[J]. 電氣自動化， 2016， 38（3）：50.

SHEN Yulin， LV Yan， CHEN Ruifeng. Electric Power User Behavior Analysis and Application Status Based on Big Data Technology[J]. Electric Automation， 2016， 38（3）：50.

[4] DEAN J， GHEMAWAT S. Map Reduce： Simplified Data Processing on Large Clusters[J]. Communications of the ACM， 2008， 51（1）： 107.

[5] ZAHARIA M， CHOWDHURY M， FRANKLIN M J， et al. Spark： Cluster Computing with Working Sets[C]// Hot Cloud， 2010： 10.

[6] KEOGH Eamonn， CHAKRABARTI Kaushik， PAZZANI Michael， et al. Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases[J]. Knowledge and Information Systems， 2001， 3（3）： 263.

[7] JUNEJO Imran N.， AGHBARI Zaher Al. Using SAX Representation for Human Action Recognition[J]. Journal of Visual Communication and Image Representation， 2012， 23（6）： 853.

[8] SHIEH Jin， KEOGH Eamonn. iSAX： Disk-aware Mining and Indexing of Massive Time Series Datasets[J]. Data Mining and Knowledge Discovery， 2009， 19（1）： 24.

[9] CAMMERRA A， PALPANAS T， SHIEH J. iSAX2. 0： Indexing and Mining One Billion Teme Serees[C]// International Conference on Data Mining. Washington： IEEE. 2010： 1.

[10]李天駒， 張錚， 張為華. 高效KD樹并行算法優化[J]. 計算機系統應用， 2015， 24（8）：1.

LI Tianju， ZHANG Zheng， ZHANG Weihua. Efficient KD Tree Parallel Algorithm Optimization[J]. Computer System Applicatoin， 2015， 24（8）：1.

[11]MUJA M， LOWE D G. Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration[J]. VISAPP （1）， 2009， 2（331/340）： 2.

[12]HUTCHISON S A. Distributed Kernelized Locality-Sensitive Hashing for Faster Image Based Navigation[R]. Air Force Institute of Technology Wright-Patterson Afb OH Graduate School of Engineering and Management， 2015.

[13]SZMIT R. Locality Sensitive Hashing for Similarity Search Using Map Reduce on Large Scale Data[M]//Language Processing and Intelligent Information Systems. Springer Berlin Heidelberg， 2013： 171.

（編輯：王 萍）

收稿日期： 2020-12-03

基金項目：

國家重點研發計劃項目（2017YFC0803700）;上海市科委科研計劃項目（19DZ2252800）;國家電網公司科技項目（52094016000A）;國網上海市電力公司科技項目（52094020001A）.

作者簡介：

吳 裔（1987—），男，博士，工程師;

陳顥天（1996—），男，博士研究生.

通信作者：

郭棋林（1984—），男，碩士，E-mail：15210240072@fudan.edu.cn.

3073501908223