變熵畫像:一種數量級壓縮物端數據的多粒度信息模型

朝 魯 彭曉暉 徐志偉

1(中國科學院計算技術研究所 北京 100190)2(中國科學院大學 北京 100049)3 (智能處理器研究中心(中國科學院計算技術研究所) 北京 100190) (chaolu@ict.ac.cn)

Fig. 1 From computation offloading to data modelizing圖1 從計算下沉到數據模型化

近年來，數據的爆發式增長給云計算模式帶來了計算負載、網絡帶寬、響應延遲等一系列巨大的挑戰.據IDC預測，全球每年產生的數據量將達到160澤字節(160 ZB),而其中由邊緣設備和終端設備產生的數據大約占據78%[1].利用海量物聯網設備分擔龐大的計算需求，催生了邊緣計算[2-3]、霧計算[4]、物端計算[5-6]等新型計算模式和體系架構.作為云計算的重要補充，它們的共同理念是強調計算應盡可能地分散在靠近用戶和數據源的邊緣或端上，從而針對計算、通信、存儲和功耗等硬件約束優化系統任務分配，改善性能和降低功耗.然而這類模式并未致力于解決以下2個重要問題：1)數據存儲位置決定了計算任務能夠靠近網絡邊緣的最短距離，但網絡邊緣設備的存儲、計算資源以及通信能力相對受限，無法有效存儲和快速傳輸這些從物理世界感知到的原始數據，導致計算無法深度下沉;2)不同計算場景需要獲取不同粒度的信息，在原始數據級實現多粒度查詢和存儲引入了昂貴的計算冗余和空間開銷.如圖1所示，在支持多粒度數據需求的情況下數量級地壓縮感知數據，為資源相對受限環境的應用提供統一數據抽象支持，是這類新型計算模式能夠進一步演化的關鍵挑戰之一.

我們將物聯網環境中面向物理世界并具備與物理世界交互功能的設備稱為物端設備，例如傳感器設備、控制器設備和中小型智能設備.在其上采集或控制的數據稱為物端數據，例如溫度、能耗和事件次數.物端設備和物端數據構成了自然界最根本的數據生產源，其專有的內在特征也是我們設計新型數據抽象的關鍵動機.由物端設備、通信設備、計算機及其周圍環境組成的具有一定物理或概念界限的計算系統稱為物端控域.例如，智能家居、樓宇、以人為中心的可穿戴設備組成的系統等.物端控域的首要目標是對域內產生的事件快速響應，同時降低系統處理計算任務的整體能耗.在資源相對受限環境下，高效且快速地為不同計算任務提供其所需的不同粒度數據是實現這個目標的重要途徑.下面我們將從物端數據和物端設備2方面，挖掘和分析物端控域中這種多粒度信息模型抽象相對于原始數據形式的約束變化.

從物端數據角度看，物端數據具有3個特征：1)數據可廣泛地用時間序列的形式表征.正如同NoSQL數據庫領域使用鍵值對方式描述一切數據一樣，時間戳是天然標識物端數據的“鍵”，而“值”是物端數據所蘊含的數值屬性.2)物理世界數據偏離正常值的頻率是稀疏的.根據環境、能耗和人類行為活動等領域相關實證研究結果[7-10]，來源自然界的物端數據相對于期望的偏離程度通常符合長尾分布，即異常總是少見的，周期化數據卻是常態.如圖2所示，大部分偏離程度低的數據(常態情況)在長尾部分，極少部分偏離程度高的數據(異常情況)在長尾頭部.3)本文提出的一個假說，數據偏離程度導致了觀測者對數據的注意力和需求程度不同，可簡稱為注意力差別假說.具體來說，偏離程度小的常態數據占據大量的比例，因此帶來的信息量小，僅需要用戶少量的注意力，例如呈周期性變化的室內溫度，用戶多查看其周期走勢；偏離程度大的異常數據占據少量比例，帶來的信息量大，需要用戶較多的注意力.例如因為暖氣損壞導致的室內溫度急劇降低，設備應及時通知用戶或報警.這里的“溫度急劇降低”具有大量的信息，需要應用或用戶更多的注意力.該假說在其他領域也有許多應用場景，例如圖片文件的前景輪廓能夠吸引更多的注意力，壓縮算法很少犧牲這部分畫面的質量，而更多犧牲容易被人忽略背景部分畫質.類似的情形也發生在音頻壓縮情景中.這一假說也可以從功能感知[11]理論框架中獲得支持：舍棄不重要的信息，并不影響應用對數據內部隱藏的重要知識的提取.

Fig. 2 The long-tailed distribution of deviations over normal values with data on things圖2 物端數據偏差正常值程度的長尾分布示意圖

總體來說，物端數據第3個特征的注意力差別導致的用戶需求不同體現在3點：

1) 數據質量.注意力聚焦的數據需要較高的精確度，需要準確描述數據周圍的形態；反之精確度可以降低，少量輪廓數據便可以滿足數據分析需求.

2) 數據時效.注意力聚焦的數據可能需要較高的時效性.這類數據通常代表異常事件，需要及時更新數據，并通知上層應用；反之時效可以放寬，甚至存入離線數據倉庫備用.

3) 數據隱私.需要注意力聚焦的數據可能具有較高的價值，如果數據未經脫敏處理容易泄露用戶或環境的指紋特征；反之數據信息價值較低，不易泄露指紋特征.

從物端設備角度看，多數物端設備存在低容量、低性能、低能耗、低帶寬和高延遲等諸多硬件資源約束.因此，當物端設備接入互聯網提供Web服務時，其數據存儲和傳輸服務存在3方面挑戰：

1) 空間占用.大多數物端設備的內存和外存空間從千字節到兆字節級不等，僅能提供非常有限的存儲容量，而提供Web服務需要存儲大量歷史數據，因此，對物端數據進行有效壓縮是數據存儲的關鍵.

2) 傳輸尺寸.物端設備經常采用的IEEE 802.15.4、藍牙等低功耗傳輸技術提供的網絡帶寬極為有限，在物端節點之間傳輸大量的數據會造成高延遲和高能耗.因此節點間大量傳輸數據時，需要壓縮其傳輸尺寸.

3) 查詢速度.如何在性能相對較低的物端設備上進行快速數據查詢，需要新的快速索引機制.

綜上所述，我們圍繞引言介紹的物端數據角度的3個特征來解決物端設備角度的3個挑戰，引入時間序列表示、最大誤差保證的有損壓縮以及長尾分布下的多粒度信息這3個約束，使得物端數據特征和物端設備資源限制匹配.本文首次提出了滿足以上約束的一種多粒度信息模型抽象理論——變熵畫像(variant entropy profile, VEP).其含義是將原始數據向信息層次躍升，如同畫像一樣高度概要地刻畫數據關鍵特征，同時滿足上層應用多樣化需求，允許變化熵值的信息進行存儲或傳輸.同時設計并實現了一種基于時間序列分解原理，且滿足VEP理論的物端數據存儲原型——TSR-VEP.通過使用馬薩諸塞大學發布的Smart*真實樓宇能耗數據集和相關數據挖掘應用進行測試的結果表明，TSR-VEP實現了多粒度信息存儲和查詢，可達到約20倍數據壓縮率以及平均4%的觀測結果誤差率，初步驗證了注意力差別假說，以一種抽象方式統一解決了新型物聯網計算模型遇到的2類缺陷問題.

1 相關工作

圍繞物端信息模型的3個約束，本節將依次介紹相關領域的研究工作：

1) 時間序列存儲

時間序列存儲是物聯網數據存儲領域的重要研究內容.這些存儲技術大多通過關系型數據和NoSQL數據庫來實現，并針對時間序列相關性和頻繁寫的特征，在壓縮效率、索引、執行方式、存儲規模和存儲結構等方面進行優化，如InfluxDB[12]，OpenTSDB[13]等.這些時間序列數據庫在云計算環境中性能優異、可擴展性強，但未針對存在明顯資源約束的物端設備如家庭智能網關、嵌入式設備及傳感器設備等進行優化設計.其較大的存儲占用、I/O密集的特點很難適合物端計算環境.同時，大部分時間序列數據都存在明顯的冷熱數據分離情況，占用了大量的存儲空間，而這類數據庫無法從知識理解層次解決這個問題.

2) 有損數據壓縮

物端數據偏離正常值的頻率符合長尾分布，時間序列數據在時域和值域構成的空間中具有較強的周期性和稀疏性.因此，在壓縮感知等相關領域中，大量的稀疏化技術被應用.本文將這類稀疏化技術按照是否可以通過時間進行索引分為2類：不可時間索引的和可時間索引的數據稀疏化技術.不可時間索引的稀疏化技術通常僅針對數據的值域空間進行壓縮，丟棄了數據內在相關性，因此壓縮還原結果僅能重構值域空間的分布.這類方法包括PCA[14]、大量的神經網絡算法如DNN[15]等.另外循環神經網絡(RNN)[16]可通過自回歸方式進行一定時域相關性建模，但這種方式依然不支持索引.而可時間索引的稀疏化技術同時保留了時域和值域空間數據之間的相關性，因此能夠重構有序時間序列.這類方法包括神經網絡分解(ND)[17]、快速傅里葉變換(FFT)[18]、離散余弦變換(DCT)[19]、離散小波變換(DWT)[20]等.此類稀疏化技術，具備較好的數據擬合和過濾特性，能有效地去除噪聲和異常，實現一定程度的周期化預測.但它們通常利用平均化或比例化的度量進行損失估計以防止出現過擬合情況，如平均絕對誤差(MAE)、均方根誤差(RMSE)等，無法保證單個樣本點的誤差范圍.因此，該類方法雖然有效體現數據的整體趨勢及周期性，但是不適用于有較強精度需求的場景.

另一類有損壓縮方法為了支持任意長度時間序列數據的在線學習壓縮，多采用了分段線性逼近方法，并限制了誤差范圍[21].由于分段表示采用了線性回歸等多種技術，該方法具備有限的預測和快速查詢能力.近年來的一些相關工作利用無窮范式距離L∞(即一組絕對值誤差的最大值)約束誤差，使得還原數據的誤差更容易被人類理解和使用.如分段常數近似方法(PMR-midrange)[22]利用平均值和中位數進行逐段逼近滿足無窮范式距離，具有最高的計算效率，但數據的局部特征基本消失.為了進一步利用局部特征進行壓縮，卡爾斯魯厄大學提出分段壓縮算法[23]利用不同次數多項式進行逐段逼近，在一些波形數據上取得了良好的效果.自適應逼近方法[24]與多模型逼近方法[25]采用了線性函數與非線性核函數的混合方式進行逐段逼近，能夠進一步表達非線性區間，但該方式也犧牲了性能.在這些方法中，卡爾斯魯厄大學的分段壓縮算法在性能和壓縮率上表現極佳，簡潔的算法也適合執行在物端設備環境.然而由于它缺乏對于時間序列波形的整體理解，在針對功耗分析等較高精確度要求的場景下，壓縮率急劇下降.受到真實問題的時間序列建模和數據挖掘工作的啟發，近來也有研究人員借鑒較為成熟的有損失季節性-趨勢分解方式(STL)[26]，通過去除掉時間序列里隱藏的周期和趨勢成分，獲得更高效的分段近似表達.昆士蘭大學提出一種基于STL分解的最大誤差保證方法[27]，通過STL分解工具消除了大量稀疏成分，并用常數分段近似和哈夫曼編碼進行參數壓縮，該工作在有較強周期性的數據集上取得了可觀的壓縮效果.但在周期性較差的真實數據集上，單一的STL周期成分估計方法不利于高效壓縮.

3) 多粒度信息數據挖掘

現階段多粒度數據表達的嘗試主要有2類：計算輸出導致的數據多粒度和視圖導致的數據多粒度.第1種方法使用不同的計算函數生成多粒度信息，例如邊緣計算的智能攝像頭場景中使用臉部特征向量代替完整圖像數據傳輸實現人臉識別工作[28]、在智能插排場景中使用神經網絡的Softmax層數據代替電流波形數據的傳輸[29],這類工作的特點是需要開發者針對特定的應用場景進行數據粒度的定制，數據難以被其他應用共享.第2種方法通常是多維數據庫利用視圖變換方法，形成不同時間、空間和關系粒度的信息塊查詢加速，如DataCube[30]，STREAMCUBE[31]等，這類方法本質上改善了數據的存儲和查詢方式，但在維度較為單一的物端數據上難以發揮優化效果.

綜上所述，本文將結合這3方面相關工作的優勢進行變熵畫像的構建.

2 變熵畫像原語與架構設計

2.1 變熵畫像形式化表達

本節將依照第1節約定的3個約束，給出驚異度(surprisal)和變熵畫像的定義，并確定其具備的性質.

定義1. 驚異度.對于時間點個數為N的時間序列TS={(t1,v1),(t2,v2),…,(tN,vN)}，使用時間序列預測方法進行壓縮編碼和重構得到TS′，則在值的絕對殘差距離Δv構成的分布Γ上，稱自信息量Ii=-log(PΓ(Δvi))為時刻i的驚異度.

定義2. 變熵畫像.對于時間點個數為N的時間序列TS={(t1,v1),(t2,v2),…,(tN,vN)}，給定階數M，各階誤差集ε={εm|0≤m

(1)

其中，映射規則φm是時間序列TS中下標集合的一個子集，TSm={(ti,vi),i∈φm}，并同時滿足約束:

|fm(ti)-vi|≤εm,?i∈φm,

(2)

Ii

(3)

1) 有序性.由式(3)可得，高階VEP總是具有比低階VEP更高的驚異度.

2) 有界性.由式(2)可得，各階VEP還原重構的時間序列滿足各階最大限定誤差.

4) 稀疏性.根據第1節的物端數據稀疏性假設，經過壓縮的函數集參數空間顯著小于原始數據集大小，即‖f‖?|TS|.

2.2 基本原語與接口設計

滿足基礎約束的VEP可有多種實現，為了能夠無縫地在不同節點和環境進行統一傳輸和存儲，所有的VEP實現對外都需要具有相同的數據封裝和操作接口.

VEP采用可移動配置mVEP作為統一的存儲和傳輸載體.mVEP既可用來描述全新的VEP參數配置，也可用來描述已經填充數據的VEP序列化實例.VEP在設備內或節點間進行復制或遷移時，均需要完成VEP和mVEP的轉換.

我們在此定義VEP的最簡操作集合，包括CREATE，APPEND,FORK，QUERY,SUBSCRIBE這5個原語，其定義和功能分別如下所述：

1) 創建

接口聲明：CREATE(mVEP).

輸入：mVEP;

輸出：VEP實例.

接口描述：根據mVEP生成滿足相應條件的VEP實例.其作用是提取mVEP參數創建新的VEP，或從mVEP中恢復已有VEP.

2) 追加

接口聲明：APPEND(T,V).

輸入：時間戳T、數值V;

輸出：無.

3) 分叉

接口聲明：FORK(filter).

輸入：過濾參數filter；

輸出：mVEP.

接口描述：根據過濾參數filter對VEP進行時域、值域或階粒度的拆分與復制，并形成包含VEP序列化信息的mVEP.該接口作用有2點：①用于獲得不同尺寸和粒度的mVEP進行傳輸；②用于裁剪VEP自身參數集.

4) 查詢

接口聲明：QUERY(T).

輸入：時間T;

輸出：值V、[rank].

接口描述：查詢指定時刻T的值V，并返回對應V所處的階數.

5) 訂閱

接口聲明：SUBSCRIBE(filter,callback_func).

輸入：過濾條件filter、待注冊的訂閱回調函數callback_func(T,V,rank);

輸出：訂閱有效時間.

接口描述：對新增數據進行訂閱操作，符合過濾參數的結果會通過callback_func返回.例如可通過filter僅訂閱高階VEP,以異步的方式推送高驚異度數據給訂閱者.

通過5個操作原語的描述，我們已將VEP由數學模型轉換為可訪問信息資源，并部分具備了存儲單元的增添、讀取和刪除操作能力.如表1所示，我們將VEP的操作原語與SQL和HTTP的CRUD方法進行了對比，VEP作為在線時間序列存儲模型，不支持修改操作，但其余的增、讀和刪操作都可以得到有效支持，這使得VEP可輕易被封裝為更高層的存儲表達形式，如HTTP RESTful資源.

Table 1 Comparison of VEP Primitive Operators andCRUD Methods

2.3 趨勢-稀疏-回歸變熵畫像(TSR-VEP)

根據VEP定義，本節將給出VEP的一種具體實現，即趨勢-稀疏-回歸 (TSR-VEP)變熵畫像.TSR-VEP在滿足VEP約束的前提下借鑒了STL分解思想，進一步將時間序列分解為趨勢成分(TC)、稀疏成分(SC)以及殘差回歸成分(RC)，并表示成P=(f,ε,φ)的三元組.如圖3所示，對應的f可利用TSR表示為

(4)

其中，趨勢成分為fTC(ti)，是對整個時間序列粗粒度走勢的近似.稀疏成分為

(5)

是第k段周期特征的近似表示，共K段.殘差回歸成分為

(6)

是第m階有最大誤差保證的殘差近似，也是數據異常程度的體現.

Fig. 3 A demo of data decomposition圖3 數據分解示意圖

(7)

這表明φ始終優先映射高階VEP，而較低階VEP的映射需要減去比其高階的所有映射.因此，當自頂向下建立fRCm(t)函數時，可借用該函數的定義域構建φ.

由于φm在TSR-VEP實現中被隱式定義在函數定義域中，我們需要引入一個新的參數指示φm的配置.設比率τm=|TSm||TS|表示各階數據的拆分比例，我們即可按照圖3所示方法將排序后殘差項Δv進行比例拆分依次確定φm.通常情況下，根據注意力差別假說，應滿足τm>τm+1，εm>εm+1.另外，我們利用τS和εS將稀疏化組件的構建目標約束為：相對于原始時間序列，升序排列的τS百分位重構誤差不應超過εS.

τm與εm的配置策略較為靈活，本文在此提出等熵拆分策略作為一種可選策略.我們希望各階VEP含有相似熵值，即不同粒度的VEP可包含相近的信息不確定度，從而進一步符合注意力差別假說.根據定義1可建立約束如下：

HΓ(ΔVm)=HΓ(ΔVm+1)，

(8)

(9)

(10)

根據注意力差別假說，我們引入非負遞減的驚異度-精度函數I=γ(ε)表示兩者關系，得出：

τmγ(εm)=τm+1γ(εm+1).

(11)

例如我們可定義非負遞減指數函數I=αe-β ε，其中α>0,β>0，并最終獲得兩者關系如下：

(12)

2.4 TSR-VEP計算組件

TSR-VEP在架構上主要由4個組件組成，分別是控制器(Controller)、評估器(Estimator)、稀疏化組件(Sparse Component，簡寫為S)和回歸組件(Regress Component，簡寫為R)，這4個組件作用分別如下：

1) 控制器.維護VEP所有原語的解析和處理、數據緩存和在線窗口緩沖區的控制，及協調創建其他3個組件.

2) 評估器.利用輸入的樣本數據和用戶預定義初始參數進行參數估計與校正，以滿足用戶對于空間占用和精度控制的需求.

3) 稀疏化組件.利用可時間索引的稀疏化算法將原始時間序列數據進行稀疏化表達，從而獲得具有一定周期性預測能力的稀疏壓縮編碼.由于數據存在數值和頻率隨機性，我們無法保證單一的稀疏編碼能夠預測任意長度的數據集，因此我們采用了分段的稀疏編碼對不同時間片段進行壓縮.同時為了降低稀疏參數所占用的空間，系統將在保證稀疏化函數誤差范圍的前提下，自動合并相同或相似的稀疏編碼段.該組件對外提供的方法為添加數據Append和查詢數據Query.目前可選用的稀疏化算法有神經分解網絡ND[17]，FFT[18]，DCT-II[19]等，其中，ND方法通過含有正弦周期性激活函數的神經網絡進行時間序列表征學習，FFT和DCT-II分別通過選取能量最大的一組復數頻域和實數頻域方式進行稀疏化表征.如表 2所示，我們在相同數據集和相同誤差要求下進行了簡單的選型分析.

Table 2 The Selection Analysis of Sparse Components表2 稀疏化組件選型分析

結果顯示，神經網絡分解的ND方法由于能夠精確學習識別時間序列信號的固有頻率，具有最高的壓縮率和預測能力；而其余頻域變換方式僅能夠按基波頻率的倍數展開，難以提取時間序列信號中真實固有頻率的組合.通過測試發現，目前ND的學習訓練時間過長，即使在有GPU加速的情況下，也不能保證任何類型的數據輸入都能在預計迭代次數內完成收斂.雖然該方法具有極大的優化潛力，但過長的訓練時間和無法預計的收斂特性，使其暫時不適用于物端設備.DCT-II的余弦變換方式相對FFT方法具有更緊湊的能量分布，節省了一半的虛數域參數空間.因此，本文最終選擇了相對可以接受的DCT-II方法構建稀疏化組件.

4) 回歸組件.該組件利用能夠保證誤差范圍的分段逼近算法擬合殘差成分和趨勢成分.本文基于卡爾斯魯厄大學提出分段壓縮算法[23]進行了部分修改，新增了低參數空間占用、動態優化數據精度和快速在線數據添加等特性，但并未影響到該算法的核心內容.由于篇幅所限制，本文不再贅述這些改進的具體內容.該組件對外提供的方法為添加數據Append和查詢數據Query.

2.5 變熵畫像核心算法

本節將討論TSR-VEP的核心實現算法，包括參數調整、數據添加和數據查詢這3部分.

1) 參數調整

評估器的參數計算是實現數據多粒度分階的依據，雖然用戶和系統會給定組件的部分缺省參數配置，我們仍需要在運行時為不同數據模式動態校正參數.在TSR-VEP具體實現中，用戶必須給出的參數為分階比率的集合τ、稀疏化組件的εS和τS、最高階的誤差限制εM-1，而其余階誤差參數將通過樣本學習方式進行調整.具體來說，我們將利用式(11)確定最大壓縮率目標下的各階ε誤差.通過對樣本殘差距離的排序，利用τ確定各階殘差的邊界值，并提供Cast和Slice方法將數據添加過程中產生的殘差按照邊界值投入到不同階的殘差回歸組件中.

2) 數據添加

在物端計算環境中，數據的添加需要在線進行，為了兼顧批處理性能優化和低查詢延遲的目標，其采用基于窗口滑動緩沖區的流處理算法.如圖4所示，在線添加新數據T,V時，首先數據會被存入緩沖區，然后依次滑動4類窗口，分別實現快速緩沖、趨勢成分、稀疏成分和殘差成分的處理.在這些窗口滑動過程中，執行流程根據參數的初始狀態情況分為2個階段：參數學習階段和參數就緒階段.在參數學習階段，各組件均采用用戶預設值和缺省值，并持續收集數據樣本填入評估器.當評估器收集到足夠數據后，進行參數估計和各組件的參數校正，執行流程隨后進入參數就緒階段.

算法1. VEP拆分與添加.

需要已初始化的buffer緩沖區、R組件、S組件；

FunctionFeedTrend(T,V)

②Rtrend.Append()；

③buffer.MoveWindow(“trend”).

FunctionFeedSparse(T,V)

①Vtrend←Rtrend.Query(T)，若結果缺失，程序停止；

②S.Append(T,V-Vtrend)；

③buffer.MoveWindow(“sparse”).

FunctionFeedResidue(T,V)

①Vtrend←Rtrend.Query(T)，若結果缺失，程序停止；

②Vsparse←S.Query(T)，若結果缺失，程序停止；

③Vresidue=V-Vtrend-Vsparse；

④RANKS←Cast(|Vresidue|)；

⑥ forrank←0 ～M-1 do

⑦Rrank.Append(T,Vresiduerank)；

⑧ end for

⑨buffer.MoveWindow(“residue”).

在算法1中，FeedTrend函數將T,V數據添加進入回歸組件Rtrend中；FeedSparse函數嘗試將T,V去除趨勢成分并填入稀疏化組件S中；FeedResidue函數嘗試將T,V去除趨勢成分和稀疏成分后得到殘差成分，并根據評估器的區間劃分結果將殘差成分切分為不同階數據，依次添加進不同階對應的回歸組件Rrank中.在這類函數執行過程中，如果發現數據所依賴的去除項有不完全的情況，則不進行窗口滑動，等待所依賴的去除項完備后重新滑動.

Fig. 4 The data flow of online appending圖4 在線新增數據流程

3) 數據查詢

在數據查詢階段，TSR-VEP使用算法2中Query方法，依次查詢各組件數據并按照式(4)進行重新融合.需要注意的是查詢過程中如何利用回歸組件從分階殘差定義域中恢復隱藏的φm信息.如圖5和QueryResidue方法所示，我們將從高階向低階依次進行回歸組件查詢.根據式(7)，各階查詢過程僅保留尚未被高階所覆蓋的值，從而促使最終查詢結果具有盡可能高的精度值.同時，為了確保VEP可查詢任意時刻數據，我們通過Neighbors變量保留了各階數據查詢時的臨近點位置信息，并逐層向低階的臨近點信息收縮合并，得到最終合并數據的臨近點信息，從而可利用Interpolate的線性插值方法進行時間間隙的插值查詢.

Fig. 5 Merging residues of different ranks圖5 不同階殘差的融合示意圖

算法2. VEP合并與查詢.

需要已賦值的各階R部件、S部件；

FunctionQuery(T)

①Vtrend←Rtrend.Query(T)；

②Vsparse←S.Query(T)；

③Vresidue,Neighbors←QueryResidue(T)；

④V←Vtrend+Vsparse+Vresidue；

⑤ returnInterpolate(T,V,Neighbors).

FunctionQueryResidue(T)

① 初始化V*,Neighbors*為與T等長的數組；

② forrank←M-1～0 do

③V,Neighbors←Rrank.Query(T)；

④V*←V*⊕V；*只增擴展*

⑤Neighbors*←Neighbors*?Neighbors；

⑥ end for

⑦ returnV*,Neighbors*.

FunctionInterpolate(T,V,Neighbors)

① 初始化V*為與T等長的數組；

③ if(v=?)

⑥ end if

⑦ end for

⑧ returnV*.

3 實驗與評價

本文將從真實應用場景出發，采用馬薩諸塞大學Smart*項目采集的公寓能耗數據集[32]，并結合Liu等人提出的智能電表分析應用基準測試程序組作為驗證VEP理論的數據挖掘類應用負載[33]，評估VEP理論在不同場景下的正確性和有效性.

實驗選取Smart*項目的2016年公寓數據集，該數據集記錄了114個公寓房間的功耗 (kW)以及實驗地區的環境溫度 (℉)，詳細數據集信息如表3所示：

Table 3 The Details of Smart* Dataset表3 Smart*數據集詳情

智能電表分析應用基準測試程序組包含需要使用功耗和溫度數據的4個應用程序，分別是：1)PAR[34].建立功耗數據的周期性自回歸模型，傾向于分析相鄰時間數據的相關性.2)Histogram.提取功耗的直方圖分布區間參數及對應區間的落點數量，傾向于分析單一用戶的用電走勢.3)Similarity.利用向量余弦判斷不同公寓用電功耗相似程度，傾向于分析多用戶間的用電走勢.4)Threeline[35].建立不同溫度走勢下的用電傾向三線段模型，區分不同公寓的用電習慣，該負載傾向于分析單用戶用電走勢和溫度之間的相關度.

本次TSR-VEP原型采用Python 2.7實現，僅用于原理驗證，并采用Dell PowerEdge R730服務器實驗環境進行模擬測試.服務器具體配置為2顆英特爾至強 E5-2640 v4 2.4 GHz處理器，8條16 GB RDIMM內存，基準測試應用負載選用Matlab語言實現.

我們設定VEP模型自身為f函數，應用負載為觀測者g函數，本節將從3個角度評價VEP模型：1)無應用負載測試loss(x,f′(f(x)))，僅研究VEP自身不被觀察時的數據壓縮和還原過程；2)有應用負載測試loss(g(x),g(f′(f(x))))，研究被應用負載觀察后的數據壓縮和還原過程；3)通過初步測試結果討論VEP在物端的實用性.

3.1 無應用負載情況目標測試

壓縮性能和誤差保證是分析VEP有效性的2個關鍵指標，本實驗針對Smart*數據，通過調整不同的誤差限制條件分析壓縮率變化，本文定義壓縮率為

(13)

Fig. 6 Compression rates with different highest rank error bounds圖6 在不同最高階誤差限制下的壓縮率變化情況

Fig. 7 Compression rates with different weighted average error bounds圖7 在不同加權平均誤差限制下的壓縮率變化情況

圖6顯示不同階數情形下壓縮率在1.96～30.67區間變化，整體上來講，壓縮率和最高階誤差正相關.針對極端情況εM-1=0，即強制VEP進行無損壓縮，壓縮率高度退化，最小為1.96倍.由于回歸組件的高效編碼實現，結果顯示其對時間序列數據仍然有一定的壓縮效果.在εM-1=0.4前后，我們觀察到各階壓縮率曲線出現了交叉點.在該點之前，由于階數增加導致更多的數據被下放到允許較高誤差的低階回歸組件，促使壓縮率一定程度增加.在該點之后，低階容許誤差繼續增大，但回歸組件已經足夠容納全部數據，無法進一步縮減線性分段數量，因此增加階數帶來的壓縮優化較少.同時,圖7進一步顯示了遞增的階數通過放寬各階加權平均后的誤差限制提升了整體壓縮率，但壓縮率的上升速率也隨之減緩.

Fig. 8 The compression ratios of multiple apartments圖8 多公寓壓縮率圖

3.2 有應用負載目標測試

本節分別將114個公寓功耗與溫度的VEP還原數據、DCT還原數據及原始數據作為輸入，進行4組用電分析應用負載為觀測函數的對照實驗.VEP和DCT的構建采用統一參數設定，結合3.1節分析，實驗選定參數為：階數M=3，分階比例依次是τ={0.80,0.15,0.05}，依據式(12)的分階誤差依次為ε={1.48,0.65,0.1}，τS=0.8,εS=1.0.實驗過程首先將原始數據集轉換為VEP和DCT模型；再在相同的時間T下進行查詢，還原得到應用程序所需的輸入數據集；最后將得到的數據集輸入應用負載得到觀測結果.為使不同應用負載和不同公寓的觀測結果能夠統一比較，本實驗以原始數據集的結果為參照量，通過標準差歸一化(Z-Score)和結果平均化的方式得到各公寓的標量觀測結果，即：

(13)

而不同重構方法與應用負載可通過相對于原始數據標量觀測結果的絕對誤差(absolute error)比較.

轉換的VEP和DCT模型的壓縮率如圖8所示，VEP數據存儲空間占用從平均10.8 MB降至平均576 KB，壓縮率在16～43倍之間，平均壓縮倍率為20.67倍.相比之下，無誤差保證的DCT數據存儲空間占用降至223 KB，壓縮率49倍.

通過TSR-VEP的設計可知，周期性越強的家庭用電數據會產生越少的稀疏化組件數量,圖9顯示了本實驗中各公寓VEP模型中的稀疏化組件數量.通過實驗結果分析，18號公寓具有最少的122個稀疏化組件并表現了最佳的周期性，而全部公寓的平均組件數量為309個.對比觀察圖8和圖9，稀疏化組件數量與壓縮率負相關，這也說明了容易被預測的數據通常具備更好的壓縮效率.

接下來我們將針對各類負載結果逐一分析:

Fig. 9 The number of sparse components圖9 稀疏化組件數量

Fig. 10 The comparison results of PAR圖10 PAR實驗對照結果

1) PAR.如圖10所示，VEP觀測結果相對于原始數據觀測結果的絕對誤差在0.000 1和0.22之間，平均絕對誤差是0.07，誤差波動百分比為3.5%.DCT觀測結果相對于原始數據觀測結果的絕對誤差在0.001 5和1.03之間，平均絕對誤差是0.33.測試結果顯示無誤差保證的DCT方法的觀測誤差極大.這是由于PAR應用的部分注意力集中在描述細節走勢的高階信息上，無誤差保證的DCT方法缺失了大量的局部細節與關鍵特征,而VEP彌補了這一缺點.

Fig. 11 The comparison results of Histogram圖11 Histogram實驗對照結果

2) Histogram.如圖11所示，VEP觀測結果相對于原始數據觀測結果的絕對誤差在0.000 7～0.105之間，平均絕對誤差是0.02，誤差波動百分比為1%.DCT觀測結果相對于原始數據觀測結果的絕對誤差在0.000 2～0.23之間，平均絕對誤差是0.04.實驗結果顯示，VEP和DCT與原始數據觀測結果誤差都處于極小的波動范圍，這說明繪制直方圖負載對能耗數據的高階信息注意力較低，其所需的全部必要特征可通過簡單的稀疏化成分提供.

3) Similarity.如圖12所示，VEP觀測結果相對于原始數據觀測結果的絕對誤差在0～0.28之間，平均絕對誤差是0.035，誤差波動百分比為1.75%.DCT觀測結果相對于原始數據觀測結果的絕對誤差在0.38～0.75之間，平均絕對誤差是0.52.實驗結果顯示，VEP誤差波動可以被接受，而DCT的觀測結果呈現出相對實際結果整體向上平移的形態，這是由于無誤差保證的DCT丟失了局部細節，而過于平滑的波形增加了不同公寓用電模式之間的相似性，忽視了應用對高階信息的注意力.VEP則彌補了這一缺點.

Fig. 12 The comparison results of Similarity圖12 Similarity實驗對照結果

4) Threeline.如圖13所示，VEP觀測結果相對于原始數據觀測結果的絕對誤差在0.003～1.49之間，平均絕對誤差是0.2,誤差波動百分比為10%.DCT觀測結果相對于原始數據觀測結果的絕對誤差在0～1.39之間，平均絕對誤差是0.2.實驗結果顯示，VEP和DCT的觀測結果誤差都相對較高，但整體仍可以接受.這類應用的特點是注意力較為分散，即使是低階數據也需要一定注意力，而VEP允許低階數據具備低精度的特點造成了應用的累計誤差.

Fig. 13 The comparison results of Threeline圖13 Threeline實驗對照結果

綜上所述，VEP在盡量減小應用負載觀測誤差的情況下，相對于原始數據存儲實現了平均20.67倍的壓縮率，在不同應用類型的測試上保持了的最低1%、平均4%的誤差波動程度.同時實驗結果顯示PAR,Histogram和Similarity應用都具有高度集中的注意力，初步印證了注意力差別假說的正確性.

3.3 邊緣及物端應用場景可行性探討

目前變熵畫像的研究仍處于初步探索階段，僅使用Python語言快速地實現了驗證原型，并未做面向過多性能和嵌入式芯片的專門優化.本節將從初步測試結果和算法估計給出內存腳跡、數據添加性能、數據查詢性能以及物端設備執行的可行性分析.

針對內存腳跡的實驗結果表明完整加載一個Smart*年度用電數據，需要放置于內存的索引空間僅為35 KB左右，其余的數據部分可放置于外存.若進一步針對不同的時間遠近順序使用放置策略，例如丟棄80%歷史時間點的高階數據，可進一步壓縮內存腳跡到7 KB，從而滿足了部分低端設備的硬件要求.此外，我們也可以通過僅保留低階數據、僅保留高階數據等不同策略，適應差異程度較大的各類硬件環境和應用場景.

在數據添加性能方面，主要時間消耗在建立稀疏化參數和分段逼近擬合算法的過程中.該部分操作利用快速緩存和窗口批處理方式，極大地降低了添加延時.針對Smart*數據的實測顯示，目前平均1 s內可添加約1 000個時間點.而在真實的物端使用場景下，通常數據產生速度為秒級及分鐘級以上，即使物端設備性能有較大的限制，目前的添加速度仍可滿足物端應用的需求.

在數據查詢性能方面，當前VEP實現仍有極大的提升空間.針對將長達一年的Smart*數據從分鐘級降到小時級的批量篩選查詢任務，VEP需要時間約1.5 s，而MySQL查詢時間僅需要0.2 s左右.這部分原因在于目前的VEP實現還沒有采用B -tree[36]等高效索引技術，未來有較大的優化空間.但針對單一時刻的數據查詢，VEP的響應時間為5 ms，已滿足了此類簡單任務的時延需求.

綜上所述，從初步測試結果的估計和推測，TSR-VEP可滿足極其苛刻的物端計算環境.同時，我們也可通過Fork和Subscribe原語實現變熵復制和注意力訂閱，實現不同級別、不同尺寸信息的整體推送或傳輸，從而優化節點間整體的性能功耗并實現數據重新布局.例如，使用Subscribe原語實現異常事件的推送報警，或僅允許Fork低階VEP的方式保護數據交易過程中的用戶隱私.

4 總 結

在物端設備資源相對受限的背景下，為使用統一方式解決物端海量數據的存儲和應用多粒度信息需求問題，本文提出了一種數量級壓縮物端數據的多粒度信息模型——變熵畫像(VEP)，并實現了TSR-VEP數據存儲原型.通過馬薩諸塞大學的Smart*樓宇能耗數據集及智能電表基準測試應用，我們從壓縮率、觀測誤差和運行開銷這3個角度得出以下結論：1)VEP能夠以相對原始數據集最高43倍、平均20.67倍的壓縮率建立多粒度信息模型，甚至在零誤差的極端限制條件下未發生壓縮崩潰，仍然具備1.96倍壓縮率; 2)在實現上述壓縮率的同時，VEP取得了最低1%、平均4%的觀測誤差波動程度，初步驗證了注意力差別假說的有效性; 3)目前VEP添加數據的速度約1 000條/秒，大跨度的批量數據查詢篩選時間為秒級，單一時刻的簡單查詢為毫秒級，內存腳跡開銷為7～35 KB，可滿足物端設備資源相對受限的執行環境.

變熵畫像是邊緣和物端計算場景中具有潛力的一項技術，但仍存在優化空間.例如：1)改進索引和壓縮方法，進一步優化數據添加、查詢性能和數據存儲壓縮比；2)完善變熵畫像理論，從理論模型推導和控制不同應用負載下的觀測結果誤差；3)將變熵畫像融入到物端計算、邊緣計算等計算模式中，與更多真實應用相結合，在接下來的工作中探討變熵畫像對于整個物端控域帶來的優化效果.

ChaoLu, born in 1989. PhD candidate. Student member of CCF. His main research interests include things computing system and distributed data computing framework.

PengXiaohui, born in 1984. Assistant professor. Member of CCF. His main research interests include the architecture and computing models of things computing system.

XuZhiwei, born in 1956. Professor. Member of CCF. His main research interests include the distributed architecture and computing for the masses.